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



         

Неоднозначные грамматики. Приоритет операций


Пример. Рассмотрим грамматику G3

(1) E->id
(2) E->num
(3) E->E*E
(4) E->E+E

Рассмотрим процесс анализа входной цепочки 2*3+4 .

Содержимое стека Необработанная часть входной цепочки Действие
$2*3+4shift
$2*3+4reduce [2]
$E*3+4shift
$E*3+4shift
$E*3+4reduce [2]
$E*E+4shift

После выполнения последнего описанного шага возникают две альтернативы: либо (а) произвести свертку последовательности, находящейся на вершине стека, используя правило 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




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