Лои. Лекция 2025-09-16

LR-анализатор

LR-анализатор

LR-анализатором расширенной грамматики $G$ называется таблица Action/GOTO, в которой строки соответствуют состояниям какого-то ДКА $A$, построенного по грамматике $G$, столбцы символам из $\Sigma \cup \Gamma \cup \{⊣\}$

	ACTION		GOTO
Состояние	$\Sigma$	$⊣$	$\Gamma$

Множество действий ACTION может быть 4 видов:

• ​ - допуск
• $\leftarrow q$ - перенос ($q$ - название состояния в соответсвующем LR(0)-автомате, по которому строится анализатор)
• $\otimes n$ - свертка (по правилу с номером $n$)
• $err<n>$ - ошибка анализа с номером $n$ (опционально)

В столбцах нетерминалов GOTO стоят состояния автомата $A$

Вид автомата $A$ зависит от вида анализатора, который требуется построить

Также так могут называть автомат с магазинной памятью, который работает по правилам, опирающимся на таблицу анализатора

Link to original

Бесконфликтный LR-анализатор

LR-анализатор называется бесконфликтным, если в каждой его ячейке action не более одного действия

Возможны 2 вида конфликтов

• перенос-свертка
• свертка-свертка

Link to original

LR-анализатор будет бесконфликтным, если он построен по LR(0)-грамматике

LR(0)-грамматика

Пусть:

• $G$ - контекстно-свободная грамматика
• $G^{\prime }$ - расширенная грамматика, соответствующая $G$
• $A$ - LR(0)-автомат, построенный по $G^{\prime }$

Тогда:

$G$ называется LR(0)-грамматикой, если каждое состояние автомата $A$ содержащее LR(0)-пункт с точкой $\bullet$ на конце (то есть пункты вида $[A\to \alpha \bullet ],A\in \Gamma ,\alpha \in {\Sigma \cup \Gamma }^{\ast }$) содержит единственный этот пункт

Link to original

Пример LR(0)-грамматики

Грамматика $G=\{S^{\prime }\to S,S\to aDc,D\to Db|b\}$, рассмотренная ранее является LR(0), так как ее LR(0)-автомат удовлетворяет определению

Алгоритм построения LR(0)-анализатора

LR(0)-анализатор

LR-анализатор построенный по LR(0)-грамматике

Link to original

Алгоритм. Построение LR(0)-анализатора

Вход

LR(0)-грамматика

Выход

LR(0)-анализатор

Алгоритм

Построим LR(0)-автомат $(Q,\Sigma \cup \Gamma ,\delta ,\nabla ,Q)$ по входной грамматике (должны уже были построить для проверки, что входная грамматика LR(0)-грамматика)

Заполнение столбцов ACTION

0. Занумеровать правила грамматики от одного до $k$
1. В строке, соответствующей состоянию $[S^{\prime }\to S\bullet ]$ в столбце $⊣$ заносим допуск ​
2. В строках, соответствующих состоянию автомата $[A\to \alpha \bullet ]$, кроме заполненной ранее (состояние $[S^{\prime }\to S\bullet ]$), в каждом столбце (включая $⊢$) заносим свертку $\otimes n$ ($n:A\to \alpha$ ), $n=1\dots k$
3. В строках $q$, соответствующих состояниям, не заполненным ранее, для $a\in \Sigma \cup \{⊣\}$ заносим перенос $\leftarrow (q,a)=\leftarrow q_i$, если $\delta (q,a)\ne \varnothing$

Заполнение столбцов GOTO

В каждой строке $q$ для $A\in \Gamma$ заносим состояние $\delta (q,A)$, если функция перехода определена

Link to original

Пример построение LR(0)-анализатора

Построим по той же LR(0)-грамматике $G=\{S^{\prime }\to S,S\to aDc,D\to Db|b\}$ ее LR(0)-анализатор

LR(0)-автомат грамматики:

Правила грамматики нумеруем в естественном порядке

Сам LR(0)-анализатор: заполняется согласно алгоритму выше

Что можно сказать, глядя на LR-анализатор

• Пустые ячейки в анализаторе означают, что входная цепочка не соответствует правилам языка
• В столбцах ACTION можно добавить действия, называемые обработчиками ошибок
• В столбцах GOTO обращение к пустым ячейкам невозможно

Пример работы анализатора

Рассмотрим анализ цепочки $\omega =abbc$ по построенному анализатору

состояние	№ такта	стек	указатель	действие
$\nabla$	1	$\nabla$	$\diamond abbc⊣$	Перенос $a$
$a^1$	2	$\nabla a^1$	$a\diamond bbc⊣$	Перенос $b$
$b^1$	3	$\nabla a^1{b}^1$	$ab\diamond bc⊣$	свертка по 4 : $D\to b$
$D^1=\text{GOTO}(a^1,D)$	4	$\nabla a^1{D}^1$	$ab\diamond bc⊣$	свертка по 3 : $D\to Db$
$b^2$	5	$\nabla a^1{D}^1{b}^2$	$abb\diamond c⊣$	свертка по 2 : $S\to aDc$
$D^1=\text{GOTO}(a^1,D)$	6	$\nabla a^1{D}^1$	$abb\diamond c⊣$	Перенос $c$
$c^1$	7	$\nabla a^1{D}^1{c}^1$	$abbc\diamond ⊣$	свертка по 2 : $S\to aDc$
$S^1=\text{GOTO}(\nabla ,S)$	8	$\nabla S^1$	$abbc\diamond ⊣$	допуск

Восстановленный вывод:

$$S\Rightarrow aDc\Rightarrow aDc\Rightarrow aDbc\Rightarrow abbc\Rightarrow abbc\Rightarrow abbc$$

Вычеркиваем лишнее:

$$S\Rightarrow aDc\Rightarrow aDc\Rightarrow aDbc\Rightarrow abbc\Rightarrow abbc\Rightarrow abbc$$

Окончательный восстановленный вывод:

$$S\Rightarrow aDc\Rightarrow aDbc\Rightarrow abbc$$

Восстановленное дерево вывода: