Разработка компиляторов
Неоднозначные грамматики. Приоритет операций
Пример. Рассмотрим грамматику G3
| (1) | E | -> | id |
| (2) | E | -> | num |
| (3) | E | -> | E*E |
| (4) | E | -> | E+E |
Рассмотрим процесс анализа входной цепочки 2*3+4 .
| $ | 2*3+4 | shift |
| $2 | *3+4 | reduce [2] |
| $E | *3+4 | shift |
| $E* | 3+4 | shift |
| $E*3 | +4 | reduce [2] |
| $E*E | +4 | shift |
После выполнения последнего описанного шага возникают две альтернативы: либо (а) произвести свертку последовательности, находящейся на вершине стека, используя правило 3, либо (б) произвести перенос символа + на вершину стека. Так как приоритет умножения больше приоритета сложения, следует сделать свертку. Однако, это противоречит общему правилу, согласно которому, в случае конфликта перенос-свертка, перенос является предпочтительной операцией (которое было таким удобным способом разрешить конфликт в первом случае).
В данной ситуации существует эквивалентная грамматика G 4 , в которой цепочка 2*3+4 имеет единственный вывод:
| (1) | E | -> | E+T |
| (2) | E | -> | T |
| (3) | T | -> | T*F |
| (4) | T | -> | F |
| (5) | F | -> | id |
| (6) | F | -> | num |
