Создание простых элементов закрытия LR Parser - PullRequest
Новая
       51

Создание простых элементов закрытия LR Parser

1 голос
/ 05 февраля 2012

Предположим, Г (расширенная грамматика): 

E' - > E
E  - > E+T|T
T  - > T*F|F
F -  > (E)|id

Итак, на одном из уровней создания ДФА я достиг этого: (I6 в книге драконов) 

    I6                   I9
 ---------            ---------
|E -> E+.T|          | E->E+T. |   
|T -> .T*F|     T    | T->T.*F |
|T -> .F  |  ----->   ---------
|F -> .(E)|       
|F -> .id |
 ---------

Мне интересно, почему мы не добавляем T->.F и F->.(E) и F->.id к I9?

Когда мы достигаем T во входной строке, мы должны добавить T ->. Fи теперь мы достигли F, и мы должны добавить F ->. (E) и F ->. id.

Почему I9 не содержит их?

1 Ответ

2 голосов
/ 06 февраля 2012

Это из-за того, как работают алгоритмы замыкания и перехода. Поскольку, когда вы создаете I9 с помощью GOTO (T) на I6, точка перемещается на один шаг вправо над любым T и добавляет их в новый набор. Этот набор затем является набором I9 GOTO. Те, у кого нет буквы T справа от точки в I6, не будут добавлены в набор I9 GOTO. После выполнения GOTO вы получаете набор I9 

E->E+T.
T->T.*F

Когда вы применяете замыкание на множестве I9, вы расширяете каждый нетерминал справа от точки. На I9 у вас нет нетерминалов справа от точки, поэтому расширять нечего.

Я недавно сделал сообщение об очень похожей, хотя и немного более сложной проблеме, которая может помочь, если вам нужны дополнительные разъяснения, Вычисление закрытия LR1

...