Как эта грамматика LL (1)?

12

Это вопрос из Книги Дракона. Это грамматика:

SAaAbBbBa
Aε
Bε

Вопрос состоит в том, как показать, что это LL (1), но не SLR (1).

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

Подскажите пожалуйста как это LL (1) и как это доказать?

Винаяк Гарг
источник
6
Я не очень знаком с грамматиками, но кажется, что язык этой грамматики конечен. L={ab,ba}
Нейц
@Nejc: Да, это так!
Винаяк Гарг

Ответы:

11

Во-первых, давайте дадим номер вашей продукции.

1 2 S B b B a 3 A ε 4 B εSAaAb
SBbBa
Aε
Bε

Давайте вычислим первый и последуем за множествами. Для небольших примеров, подобных этим, достаточно использовать интуицию об этих наборах.

FIRST(S)={a,b}FIRST(A)={}FIRST(B)={}FOLLOW(A)={a,b}FOLLOW(B)={a,b}

Теперь давайте вычислим таблицу . По определению, если мы не получим конфликты, грамматика будет L L ( 1 ) .LL(1)LL(1)

    a | b |
-----------
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

Поскольку нет конфликтов, грамматика .LL(1)

Теперь для таблицы . Во-первых, автомат L R ( 0 ) .SLR(1)LR(0)

state 0SAaAbSBbBaABA1B5
state 1SAaAba2
state 2SAaAbAA3
state 3SAaAbb4
state 4SAaAbb
state 5SBbBab6
state 6SBbBaBB7
state 7SBbBaa8
state 8SBbBa

SLR(1)S

    a     | b     | A | B |
---------------------------
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

SLR(1)LALR(1)a LALR(1)b

LL(1)LALR(1)

Алекс тен Бринк
источник
Спасибо! Я правильно построил First & Follow, но ошибся при составлении таблицы.
Винаяк Гарг
10

Если вас не спрашивают, вам не нужно создавать таблицу LL (1), чтобы доказать, что это грамматика LL (1). Вы просто вычисляете наборы FIRST / FOLLOW, как Алекс:

FIRST(S)=a,bFIRST(A)=εFIRST(B)=εFOLLOW(A)=a,bFOLLOW(B)=a,b

И тогда по определению грамматика LL (1) должна:

  1. Если и - это два разных правила грамматики, то это должно быть . Следовательно, два набора не имеют общего элемента.AaAbFIRST(a)FIRST(b)=
  2. Если для любого нетерминального символа вас есть , то это должно быть . Следовательно, если для нетерминального символа есть нулевая продукция, то наборы FIRST и FOLLOW не могут иметь никакого общего элемента.AΑεFIRST(A)FOLLOW(A)=

Итак, для данной грамматики:

  1. У нас есть начиная с то время как и у них нет общих элементов.FIRST(AaAb)FIRST(BbBa)=FIRST(AaAb)={a}FIRST(BbBa)={b}
  2. FIRST(A)FOLLOWA)= так , а , и теперь начиная с то время какСЛЕДУЮЩИЙ ( A ) = ПЕРВЫЙ ( B ) СЛЕДУЮЩИЙ ( B ) = ПЕРВЫЙ ( B ) = { ε } СЛЕДУЙТЕ ЗА ( B ) = { a , b }FIRST(A)={a,b}FOLLOW(A)=FIRST(B)FOLLOW(B)=FIRST(B)={ε}FOLLOW(B)={a,b} .

Что касается анализа SLR (1), я думаю, что он безупречен!

Итан
источник
Добро пожаловать! Чтобы улучшить этот ответ, почему бы вам не применить то, что вы заявляете, к имеющейся грамматике?
Рафаэль
Рад быть здесь !! Ответили на ваш запрос, и я думаю, что дал подробное объяснение!
Итан
Спасибо! Обратите внимание, что мы можем использовать LaTeX здесь, как я редактировал для вашей математики.
Рафаэль
Вау, спасибо! это отличное объяснение. Но я думаю, что в приложении есть какая-то ошибка. Разве не First (A) = {эпсилон}? Я думаю, что вы поменялись местами и следуйте.
Винаяк Гарг
FIRST (A) действительно является эпсилоном, но так как вы хотите рассчитать FIRST-набор всего правого члена, A -> ε просто показывает, что у нас есть пустое произведение, и первый символ терминала, который вы видите (и, следовательно, его FIRST-набор), равен терминальный символ а. Надеюсь, это помогло!
Итан
0

Ищите достаточное условие, которое делает грамматику LL (1) (подсказка: посмотрите на ПЕРВЫЕ множества).

Найдите необходимое условие, которому должны соответствовать все грамматики SLR (1) (подсказка: посмотрите на следующие СЛЕДУЮЩИЕ наборы).

AProgrammer
источник