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

Вопрос неоднозначности становится особенно важным в процессе построения управляющей таблицы анализатора 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.

Содержание раздела