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



         

Неоднозначные грамматики. Конфликты "перенос-свертка"


Вопрос неоднозначности становится особенно важным в процессе построения управляющей таблицы анализатора LR(k)-языка, так как неоднозначность грамматики приводит к конфликтам при построении таблицы.

Рассмотрим сначала конфликты типа перенос-свертка (shift/reduce). Конфликты данного типа возникают, когда в процессе работы анализатора возникает выбор между переносом текущего символа на вершину стека и сверткой последовательности, расположенной на вершине стека.

Пример. Пусть дана грамматика G1, имеющая следующий набор правил:

(1) stmt-> if expr then stmt
(2) stmt-> if expr then stmt else stmt
(3) stmt-> other
(1) stmt->if expr then stmt
(2) stmt->if expr then stmt else stmt
(3) stmt->other

, где other мы используем для обозначения других операторов.

На следующем слайде рассмотрим, что происходит при анализе следующей входной цепочки:

if E1 then if E2 then S1 else S2.




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