Лои. Лекция 2025-10-07

LR* анализ. Обработчик ошибок

Задача

построить LR*-распознаватель с обработчиком ошибок для языка формул высказываний, содержащих только $\neg ,\vee ,\wedge ,(,),x$ с учетом приоритета операций:

1. $\vee$
2. $\wedge$
3. $\neg$

Грамматику построить легко:

$$G=\{S\to \neg S|S\wedge S|S\vee S|(S)|x\}$$

Построенная грамматика не является однозначной

Построим LALR-автомат (для построения можно использовать этот способ)

Заполнение таблицы анализатора

Комментарий: после работы распознавателя ошибок невозможно восстановить вывод обрабатываемой цепочки

Пример разбора цепочки без ошибок

Приведем пример разбора цепочки $x\vee \neg x\wedge x$

Такт	Стек	Обрабатываемое слово	Действие
1	$\nabla$	$\diamond x\vee \neg x\wedge x⊣$	Находимся в состоянии $\nabla$, на каретке видим символ $x$ $\Rightarrow$ (смотрим в таблицу ACTION анализатора) Перенос $\leftarrow x$ Кладем состояние $x$ в стек Переходим в состояние $x$ Сдвигаем каретку на один символ вправо
2	$\nabla x$	$x\diamond \vee \neg x\wedge x⊣$	Находимся в состоянии $x$, на каретке видим символ $\vee$ $\Rightarrow$ (смотрим в таблицу ACTION анализатора) Свертка $\otimes 5$ (свертка по правилу $S\to x$) Вытаскиваем из стека одно состояние (число вытаскиваемых элементов равно размеру цепочки в правой части правила, по которому происходит свертка) Кладем в стек $GOTO(\nabla ,S)=S^1$ (смотрим в таблицу GOTO анализатора) ($\nabla$ потому что этот символ оказался на вершине стека после вытаскивания элементов в предыдущем пункте. $S$, потому что в правиле, по которому происходит свертка, левая часть равна $S$) Переходим в состояние $S^1$
3	$\nabla S^1$	$x\diamond \vee \neg x\wedge x⊣$	Перенос $\leftarrow \vee$ Рассуждения, аналогичные такту 1
4	$\nabla S^1\vee$	$x\vee \diamond \neg x\wedge x⊣$	Перенос $\leftarrow \neg$ Рассуждения, аналогичные такту 1
5	$\nabla S^1\vee \neg$	$x\vee \neg \diamond x\wedge x⊣$	Перенос $\leftarrow x$ Рассуждения, аналогичные такту 1
6	$\nabla S^1\vee \neg x$	$x\vee \neg x\diamond \wedge x⊣$	Свертка $\otimes 5$ Рассуждения аналогичные такту 2
7	$\nabla S^1\vee \neg S^2$	$x\vee \neg x\diamond \wedge x⊣$	Свертка $\otimes 1$ Рассуждения аналогичные такту 2
8	$\nabla S^1\vee S^3$	$x\vee \neg x\diamond \wedge x⊣$	Перенос $\leftarrow \wedge$ Рассуждения, аналогичные такту 1
9	$\nabla S^1\vee S^3\wedge$	$x\vee \neg x\wedge \diamond x⊣$	Перенос $\leftarrow x$ Рассуждения, аналогичные такту 1
10	$\nabla$ $S^1\vee S^3\wedge x$	$x\vee \neg x\wedge x\diamond ⊣$	Свертка $\otimes 5$ Рассуждения аналогичные такту 2
11	$\nabla$ $S^1\vee S^3\wedge S^4$	$x\vee \neg x\wedge x\diamond ⊣$	Свертка $\otimes$ 2 Рассуждения аналогичные такту 2
12	$\nabla$ $S^1\vee S^3$	$x\vee \neg x\wedge x\diamond ⊣$	Свертка $\otimes 3$
13	$\nabla$ $S^1$	x V $\to$ x ∧ x $\diamond$ $⊣$	Находимся в состоянии $S^1$, на каретке видим конец строки $⊣$ $\Rightarrow$ (смотрим в таблицу ACTION анализатора) допуск ​

Пример разбора цепочки с ошибками. Выявление ошибок

Приведем пример разбора цепочки $x\vee \neg \wedge x$

Такт	Стек	Обрабатываемое слово	Действие
1	$\nabla$	$\diamond x\vee \neg \wedge x⊣$	Перенос $\leftarrow x$ Рассуждения, аналогичные такту 1 предыдущего разбора
2	$\nabla x$	$x\diamond \vee \neg \wedge x⊣$	Свертка $\otimes 5$ Рассуждения, аналогичные такту 2 предыдущего разбора
3	$\nabla S^1$	$x\diamond \vee \neg \wedge x⊣$	Перенос $\leftarrow \vee$ Рассуждения, аналогичные такту 1 предыдущего разбора
4	$\nabla S^1\vee$	$x\vee \diamond \neg \wedge x⊣$	Перенос $\leftarrow \neg$ Рассуждения, аналогичные такту 1 предыдущего разбора
5	$\nabla S^1\vee \neg$	$x\vee \neg \diamond \wedge x⊣$	Находимся в состоянии $\neg$, на каретке видим $\wedge$ $\Rightarrow$ (смотрим в таблицу ACTION анализатора) Ошибка $err1$ (пропустили операнд, вставить x) Вставляем перед кареткой $x$
6	$\nabla S^1\vee \neg$	$x\vee \neg \diamond x\wedge x⊣$	Перенос $\leftarrow x$ Рассуждения, аналогичные такту 1 предыдущего разбора
7	$\nabla S^1\vee \neg x$	$x\vee \neg x\diamond \wedge x⊣$	Свертка $\otimes 5$ Рассуждения, аналогичные такту 2 предыдущего разбора
8	$\nabla S^1\vee \neg S^2$	$x\vee \neg x\diamond \wedge x⊣$	Свертка $\otimes 1$ Рассуждения, аналогичные такту 2 предыдущего разбора
9	$\nabla S^1\vee S^3$	$x\vee \neg x\diamond \wedge x⊣$	Перенос $\leftarrow \wedge$ Рассуждения, аналогичные такту 1 предыдущего разбора
10	$\nabla S^1\vee S^3\wedge$	$x\vee \neg x\wedge \diamond x⊣$	Перенос $\leftarrow x$ Рассуждения, аналогичные такту 1 предыдущего разбора
11	$\nabla$ $S^1\vee S^3\wedge x$	$x\vee \neg x\wedge x\diamond ⊣$	Свертка $\otimes 5$ Рассуждения, аналогичные такту 2 предыдущего разбора
12	$\nabla$ $S^1\vee S^3\wedge S^4$	$x\vee \neg x\wedge x\diamond ⊣$	Свертка $\otimes$ 2 Рассуждения, аналогичные такту 2 предыдущего разбора
13	$\nabla$ $S^1\vee S^3$	$x\vee \neg x\wedge x\diamond ⊣$	Свертка $\otimes 3$
14	$\nabla$ $S^1$	$x\vee \neg x\wedge x\diamond ⊣$	допуск ​ Рассуждения, аналогичные такту 13 предыдущего разбора