Разработка компиляторов



         

Состояния 2 и 3


Теперь предположим, что выполнен перенос открывающей круглой скобки. Этому случаю соответствует ситуация [S-> (.L)] . То есть на вершине магазина окажется открывающая круглая скобка, а входная цепочка должна начинаться с некоторой цепочки, которая выводится из L и перед которой находится открывающая круглая скобка. Таким образом, к нашей ситуации мы должны добавить все ситуации, получающиеся из правил, левая часть которых суть нетерминал L , т.е. [L->.L,S] и [L->.S] . Помимо этого, поскольку правая часть правила L->S начинается нетерминалом S , мы должны добавить все ситуации, получающиеся из правил, левая часть которых суть нетерминал S , т.е. [S->.L] и [S->.x] . Таким образом, новое состояние, в которое автомат перейдет после переноса в магазин открывающей круглой скобки, определяется ситуациями:

[S-> (.L)]
[L->.L, S]
[L->.S]
[S->.(L)]
[S->.x]

Это состояние 2. Мы можем изобразить часть первой строки таблицы переходов автомата:

()x,$
0s3 s2

Понятно, что в состоянии 0 свертка выполняться не может.

Обсудим, что произойдет, если в состоянии 0 мы оказались после анализа некоторой цепочки, которая выводится из аксиомы грамматики. Это может случиться, если после переноса x или открывающей круглой скобки произошла свертка по правилу, левая часть которого - S . Все символы правой части такого правила будут извлечены из магазина, и анализатор будет выполнять переход для символа S в состоянии 0. Этому случаю соответствует ситуация [S'-> S.$] , определяющая состояние 3.




Содержание  Назад  Вперед