Как анализировать заданную грамматику LALR(1)

У меня возникли проблемы с разбором следующей грамматики с использованием метода LALR.

s -> y
y -> dX | ydX
X -> e | Zd
z -> F | epsilon

Сначала я в порядке, вот состояние элемента 0: (разделяет состояния просмотра вперед)

s -> .y, $
y -> .dX, $d
y -> .ydX, $d

Теперь это нормально, но когда вы переходите в состояние 1 с терминала d, я путаюсь. Моя книга имеет состояние 2 следующим образом:

y -> d.X, $d
X -> .e, $d
X -> .Zd, $d
Z -> .f, d
Z -> ., d

Откуда упреждающий терминал «d» появился в нетерминале X? Я думал, что dX происходит от .dX, у которого есть опережающие терминалы "$" и $d". Но при выполнении E-замыкания не должны ли опережающие прогнозы быть первым из $d, который равен "$"? Почему это "$", или "d"? Я думал, что это может происходить из другого состояния, так как это LALR, но состояние, в котором я в конечном итоге сливаюсь с состоянием 1, также не имеет d в предварительном просмотре. Может кто-нибудь объяснить мне, почему существует пара "d" с "$" в опережении этого состояния?Спасибо.


compiler-construction automata lalr lr1
person Ryan Foster    schedule 05.11.2019    source источник
comment
$d здесь нет двухсимвольного просмотра вперед; это сокращение для набора {$, d}. FIRST набора состоит из всех символов, которые находятся в FIRST элемента набора, поэтому FIRST({$, d}) это в точности {$, d}.   -  person rici    schedule 05.11.2019

Ответы (1)


arrow_upward
0
arrow_downward

S$->Y$->dX$ в этой последовательности вывода после d далее X равно {$}

S$->Y$->ydX$->dXdX$ в этом выводе после первого d далее следует X равно {d}

обе последовательности вывода покрываются в одном и том же состоянии после покрытия первого символа во входных данных 'd'

person Venkatesh Nandigama    schedule 05.11.2019
comment
Я все еще в замешательстве. Я понимаю, что при просмотре грамматики то, что следует за X, равно {d}, но меня всегда учили, что при выполнении E-замыкания вы берете первую строку, которая идет после этого нетерминала. Почему это не работает в данном случае? - person Ryan Foster; 05.11.2019
comment
Есть два случая: случай 1: A->aBβ мы возьмем FIRST(β), но если FIRST(β) содержит null или A->aB, то следует рассмотреть все, что следует за A. - person Venkatesh Nandigama; 05.11.2019