доказательство того, что грамматика является LL (1)

Мне дана следующая грамматика:

S -> A a A b | B b B a
A -> epsilon
B -> epsilon

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

First(S) = {a,b}
First(A) = First(B) = epsilon

Follow(S) = {$}
Follow(A) = {a,b}
Follow(B) = {a,b}

когда я строю таблицу разбора, то по алгоритму получаю конфликт под символом $... что за хрень я делаю не так??

     a       b      $
 A                   A-> epsilon
 B                   B-> epsilon
 S                   S -> AaAb
                     S -> BbBa

ничего, если я получу 2 произведения меньше $ или что-то в этом роде?? или я неправильно строю таблицу разбора? пожалуйста, помогите, я новичок в курсе компилятора


parsing computer-science compiler-construction lookahead
person sam smith    schedule 09.03.2015    source источник
comment
Является ли эта грамматика LR(0)? А как насчет SLR(1)?   -  person Rishabh Gupta    schedule 20.10.2017

Ответы (1)


arrow_upward
4
arrow_downward

Есть крошечная ошибка. Алгоритм следующий из книги дракона,

for each rule (S -> A):
    for each terminal a in First(A):
        add (S -> A) to M[S, a]

    if First(A) contains empty:
        for each terminal b in Follow(S):
            add (S -> A) to M[S, b]

Давайте возьмем их один за другим.

  • S -> AaAb. Вот, First(AaAb) = {a}. Так что добавьте S -> AaAb к M[S, a].
  • S -> BbBa. Вот, First(BbBa) = {b}. Так что добавьте S -> BbBa к M[S, b].
  • A -> epsilon. Вот, Follow(A) = {a, b}. Так что добавьте A -> epsilon к M[A, a] и M[A, b].
  • B -> epsilon. Вот, Follow(B) = {a, b}. Так что добавьте B -> epsilon к M[B, a] и M[B, b].
person shonku    schedule 22.01.2017