Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 52

GATE

Рассмотрим грамматику с нетерминалами N = {S, C, S1}, терминалами T = {a, b, i, t, e} с символом S в качестве начального символа и следующим набором правил:

S --> iCtSS1|a
S1 --> eS|ϵ
C --> b

Грамматика НЕ LL (1), потому что:
(А) это осталось рекурсивным
(B) это правильно рекурсивно
(С) это неоднозначно
(D) Это не является контекстно-свободным.

Ответ: (с)
Объяснение:

Грамматика LL (1) не дает несколько записей в одной ячейке таблицы анализа. Он имеет только одну запись в одной ячейке, поэтому он должен быть однозначным.

Вариант А неверен. Грамматика не остается рекурсивной. Чтобы грамматика оставалась рекурсивной, произведение должно иметь форму A-> Ab, где A — это один нетерминал, а b — любая строка символов грамматики.

Вариант Б неверен . Потому что правильная рекурсивная грамматика не имеет ничего общего с LL (1).

Вариант D неверен . Потому что данная грамматика явно является контекстно-свободной грамматикой. Грамматика — это CFG, если она имеет вид A -> (V∪ T) *, где A — это один нетерминал, а V — это набор нетерминалов, а T — это набор терминалов.

Следовательно, вариант C должен быть правильным. т.е. грамматика неоднозначна.

Но давайте посмотрим, как грамматика неоднозначна.

Если грамматика неоднозначна, то при создании таблицы синтаксического анализа в ячейке должно быть несколько записей. А таблица Parse производится с помощью двух функций: FIRST и FOLLOW.

Таблица синтаксического анализа грамматики не будет иметь несколько записей в ячейке (то есть будет грамматикой LL (1)) тогда и только тогда, когда для каждого произведения вида A-> α | β выполняются следующие условия

1) ПЕРВЫЙ (α) ∩ ПЕРВЫЙ (β) = Φ

2) если FIRST (α) содержит «ε», то FIRST (α) ∩ FOLLOW (A) = Φ и наоборот.

Сейчас,

  • Для производства S-> iCtSS1 | a правило 1 выполняется, потому что FIRST (iCtSS1) IR FIRST (a) = {i} ∩ {a} = Φ
  • Для производства S1-> eS | ε выполняется правило 1, так как FIRST (eS) ∩ FIRST (ε) = {e} ∩ {ε} = Φ. Но здесь из-за 'ε' в FIRST, мы должны проверить правило 2. FIRST (eS) ∩ FOLLOW (S1) = {e} ∩ {e, $} ≠ Φ. Следовательно, правило 2 не выполняется в этом производственном правиле. Поэтому в таблице синтаксического анализа будет несколько записей, поэтому грамматика неоднозначна, а не LL (1).

Пожалуйста, перейдите по этой ссылке, чтобы узнать, как найти ПЕРВЫЙ и СЛЕДУЮЩИЙ:

http://quiz.geeksforgeeks.org/compiler-design-first-in-syntax-analysis/

http://quiz.geeksforgeeks.org/compiler-design-follow-set-in-syntax-analysis/
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2007 | Вопрос 52

0.00 (0%) 0 votes