Как понять алгоритм LALR Shift / Reduce - PullRequest
Новая
       23

Как понять алгоритм LALR Shift / Reduce

3 голосов
/ 29 марта 2011

Я пытаюсь прочитать Построение компилятора Никлауса Вирта. На странице 23 он начинает описывать, как LALR будет анализировать выражение x*(y+z) с учетом следующей грамматики: 

E  = T  | E "+" T. expression 
T  = F  | T "*" F. term 
F  = id | "(" E ")". factor

Он продолжает показывать сокращение как: 

     Action   Stack     Remaining
1             x         * (y + z) 
2    S        x         * (y + z) 
3    R        F         * (y + z) 
4    R        T         * (y + z) 
6    S        T*          (y + z) 
7    S        T*(          y + z) 
8    S        T*(y           + z) 
9    R        T*(F           + z) 
10   R        T*(T           + z) 
11   R        T*(E           + z) 
12   S        T*(E+            z) 
13   S        T*(E + z          ) 
14   R        T*(E + F          ) 
15   R        T*(E + T          ) 
16   R        T*(E              ) 
17   S        T*(E) 
18   R        T*F 
19   R        T 
20   R        E

Где действие - S (для сдвига) или R (для сокращения ... Я добавил номера строк для ясности). Поэтому я думаю, что понимаю, как перейти от шагов 1 к 4 и от 4 до 20, но я не понимаю саму 4. Например, шаг 1 помещает x в стек. x представляет RHS правила «F», поэтому происходит уменьшение -> F. F представляет 1-е «ИЛИ» правила «T», и поэтому может произойти другое уменьшение -> T. Если это правильно (что я не конечно?), тогда почему бы не заменить T на E, так как T представляет первое «ИЛИ» RHS правила «E». Это потому, что правило E имеет, так сказать, подразумеваемое «EOF» (а поскольку мы не достигли EOF, оно не может уменьшиться)? Или это потому, что в этой точке это неоднозначно (T также представляет 1-ю часть 2-го «ИЛИ» RHS правила T ... т. Е. T "*" F)? Или это что-то совсем другое?

Спасибо!

1 Ответ

5 голосов
/ 29 марта 2011

Парсер использует два критерия, чтобы решить, какое действие (сдвиг или уменьшение) предпринять дальше.Первый - это когда токены в стеке соответствуют правой стороне производства.После шага 4 T в стеке соответствует произведению E = T, поэтому, если бы это был критерий only , он мог бы уменьшиться в этой точке.Тем не менее, синтаксический анализатор также смотрит на перспективу (т. Е. Первый токен в «оставшихся»), чтобы решить, какое действие предпринять.Нет правила, в котором в качестве префикса используется E "*", поэтому сокращение недопустимо, и единственным действием является сдвиг.После шага 20 выработка E = T является действительной, потому что (как вы уже догадались) в качестве маркера упреждения существует EOF, который соответствует.

Обратите внимание, что могут возникнуть некоторые неоднозначные грамматикии в сдвиге, и в действии сокращения.В этих случаях Бизон решает в пользу «смены».См. Документы Bison для более подробной информации.Однако приведенная выше грамматика не является двусмысленной;достаточно одного знака внимания, чтобы сделать его однозначным.

...