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

Гибридный метод построения LR-автомата. LALR(1)-грамматика

LALR-автомат

LALR-автомат

Детерменированный конечный автомат, построенный по LR(1)-автомату следующим образом:

1. Формируемый автомат считать исходным LR(1)-автоматом
2. Пока в формируемом автомате два множества (состояния) LR(1)-пунктов имеют одинаковое множество ядер, то объединить эти множества в одно, назвать полученный автомат формируемым

Link to original

Пример LALR-автомата

Пример: LR(1)-автомат, построенный по грамматике $G=\{S^{\prime }\to S,S\to ac\mid bDc\mid Da,D\to a\}$ в лекции является LALR-автоматом

Сокращенный способ построения LALR-автомата

Для построения LALR-автомата используется LR(0)-автомат, в котором к пунктам (находятся в состоянии автомата) добавляются необходимые символы после запятой (для получения LR(1)-пунктов). Соответственно количество состояний LALR-автомата совпадает с количеством состояний LR(0)-автомата, построенного по той же расширенной грамматике.

Пример построения LALR-автомата сокращенным способом

$G=S^{\prime }\to S,S\to aAa|aBb|bAb|bBa,A\to c,B\to c$

Часть LR(1)-автомата для $G$. Видно, что данная грамматика является LR(1)-грамматикой

Часть LALR-автомата для грамматики $G$. Видно, что грамматика $G$ не LALR(1)-грамматика, поскольку появился конфликт (можно увидеть наглядно, если построить LALR(1)-анализатор)

LALR(1)-анализатор

LALR(1)-анализатор

LR-анализатор, построенный по алгоритму построения LALR(1)-анализатора

Link to original

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

Комментарий: практически совпадает с алгоритмом построения LR(1)-анализатора, за исключением того, что строится по LALR-автомату вместо LR(1)-автомата

Вход

Расширенная грамматика $G=(\Sigma ,\Gamma ,P,S)$

Выход

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

Алгоритм

Подготовка

Построить LALR-автомат $(Q,\Sigma \cup \Gamma ,\delta ,\nabla ,Q_0)$ по входной грамматике $G$

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

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

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

В каждой строке $q$ для каждого $B\in \Gamma$:

• Если существует пункт $[A\to {\beta }_1\bullet B{\beta }_2,b]$, то в столбце $B$ заносим состояние $\delta (q,B)$, $B\in \Gamma$

Link to original

Комментарий: всякий LALR-автомат является LR(1)-автоматом (в смысле бесконфликтности соответствующих анализаторов (1, 2))

$$LALR(1)\subset LR(1)$$

Следствие:

$$LR(0)\subset LARL(1)$$

Замечание:

$$SLR(1)\subset LALR(1)$$