SLR (1) Вовлечены парсер и epsilon

Предположим, у меня есть следующая грамматика:

S → X  
X → a | ϵ

Если бы эта грамматика не была задействована ϵ, я бы построил первое состояние, например:

S' → .S
S → .X
X → .a

а как насчет символа ϵ? Стоит ли включать:

X → .ϵ

тоже?

Если да ... при создании следующих состояний ... следует ли мне делать GOTO(Io,ϵ), будучи Io этим первым состоянием?


parsing grammar theory language-theory compiler-theory
person Oscar Mederos    schedule 28.06.2011    source источник

Ответы (2)


arrow_upward
11
arrow_downward

Поскольку ϵ не является самим терминалом, вы должны удалить его из своего правила, которое дает вам

X → .

Тогда позже у вас не будет странного GOTO с "символом" ϵ, а вместо этого будет ваше состояние

S' → S.

является принимающим состоянием на вашем графике.

person Howard    schedule 28.06.2011
comment
В этом есть смысл. Есть ли у вас какой-либо пример парсера LR, применяемого к грамматике, где задействован эпсилон:? - person Oscar Mederos; 28.06.2011
comment
@Oscar К сожалению, у меня нет примера, демонстрирующего, как действовать. Но это должно быть несложно построить вручную на основе вашей грамматики. - person Howard; 28.06.2011
comment
Я подтвердил это в книге, которую прочитал сегодня;) Это именно то, что вы сказали. Благодарю за ваш ответ. - person Oscar Mederos; 28.06.2011

arrow_upward
17
arrow_downward

Я согласен с Говардом. Ваше состояние в DFA должно содержать следующий элемент: x → . Вот DFA, который я нарисовал для парсера SLR (1), который распознает грамматику, использующую два вида эпсилон: SLR (1) DFA

person Rose Perrone    schedule 28.04.2012
comment
У меня проблема с этим отсканированным примером. Давайте посмотрим на T (n): T - ›. (E) goto (T (n), () = {[T -› (. E)], [E - ›. TX], [T-› . (E)], [T - ›. IntY]} если это так, то, следовательно, для T (n + 1): X -›. + E не должно быть: goto (T (n + 1), +) = {[X - ›+. E], [E -›. TX], [T - ›. (E)], [T-› .intY]}? Вместо этого в примере у меня есть: goto (T (n +1), +) = {[X - ›+. E], [E -›. TX]} Почему мы не включаем продукцию goto (T (n + 1), +) для T? - person Joanna; 22.06.2017
comment
Вы правы @joanna. Хотя я не понимаю, что вы подразумеваете под T (n) и T (n + 1), LR-состояние, о котором вы говорите, а именно {[X - ›+. E], [E -›. TX]}, должно включать продукции для T через предсказание. В текущей формулировке нет возможности перейти из данного состояния, поскольку справа от точки нет терминалов. - person corwin.amber; 14.08.2017