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

SLR(1) - анализатор. SLR(1)-грамматика

Пусть грамматика $G$ не является LR(0)-грамматикой. Применим к ней алгоритм построения LR(0)-анализатора. Полученный LR-анализатор будет конфликтным

Есть модификация этого алгоритма, которая позволяет даже по не LR(0)-грамматике построить бесконфликтный LR-анализатор для определенного класса грамматик

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

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

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

Link to original

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

Модификация алгоритма, обеспечивающая построение бесконфликтного LR-анализатора для более широкого, чем LR(0) класса грамматик

Вход

Расширенная грамматика

Выход

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

Алгоритм

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

0. Занумеровать правила грамматики от одного до $k$
1. Построить LR(0)-автомат $(Q,\Sigma \cup \Gamma ,\delta ,\nabla ,Q)$ по входной грамматике
2. Построить множества FOLLOW (можно воспользоваться алгоритмом построение множества FOLLOW)
3. В строке, соответствующей состоянию $[S^{\prime }\to S\bullet ]$ в столбце $⊣$ заносим допуск ​
4. В каждой строке $q$ (состояние автомата), не заполненной в 3):
   • Для каждого пункта $p=[A\to \alpha \bullet ]\in q$ в столбцах $a\in FOLLOW(A)$ заносим свертку $\otimes n$ ($n$ - номер соответствующего правила рассматриваемого пункта $p$)
   • Для каждого пункта $[A\to {\beta }_1\bullet a{\beta }_2]\in q,{\beta }_1,{\beta }_2\in (\Sigma \cup \Gamma {)}^{\ast },a\in \Sigma$ в столбце $a$ заносим перенос $\leftarrow \delta (q,a)$

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

В каждой строке $q$ для каждого пункта $[A\to {\beta }_1\bullet B{\beta }_2]\in q,{\beta }_1,{\beta }_2\in (\Sigma \cup \Gamma {)}^{\ast },B\in \Gamma$ в столбец $B$ заносим состояние $\delta (q,B)$

Link to original

SLR(1)-грамматика

Расширенная грамматика, такая что построенный по ней SLR(1)-анализатор является бесконфликтным

Пусть:

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

Тогда:

$G$ называется SLR(1)-грамматикой, если $A$ является бесконфликтным

Link to original

Комментарий про вложенность классов LR(0) и SLR(1) грамматик

Всякая LR(0)-грамматика является SLR(1)-грамматикой

$$\{LR(0)\}\subset \{SLR(1)\}$$

Пример построения SLR(1)-анализатора

Возьмем грамматику $G=\{S^{\prime }\to S,S\to aDb,D\to Db|b\}$

Построим по ней LR(0)-автомат:

В силу вида состояния $b^2$ грамматика не является LR(0)-грамматикой

Строим множества FIRST и далее FOLLOW (для нетерминалов)

По алгоритму выше составляем SLR(1)-анализатор

Утверждение. Достаточное условие бесконфликтности SLR(1)-анализатора

Если в LR(0)-автомате, построенном по расширенной грамматике для каждого состояния $q$ с пунктами вида $[A_1\to \alpha \bullet ]$ и $[A_2\to \gamma \bullet ]$ множества FOLLOW$(A_1)$ и FOLLOW$(A_2)$ не пересекаются, то SLR(1)-анализатор построенный по такой грамматике не будет иметь конфликтов типа свертка-свертка

Link to original

LR(1)-автомат. LR(1)-анализатор, LR(1)-грамматика

LR(1)-пункт

LR(1)-пунктом расширенной грамматики $G=(\Sigma ,\Gamma ,P,S)$ называется набор $(A,{\beta }_1,{\beta }_2,a)$, где:

• $A\to {\beta }_1{\beta }_2$ - правило вывода грамматики
• $a\in \Sigma \cup \{⊣\}$

Обозначается как $[A\to {\beta }_1\bullet {\beta }_2,a]$

Link to original

Ядро LR(1)-пункта

Для LR(1)-пункта $[A\to {\beta }_1\bullet {\beta }_2,a]$ его ядром называется LR(0)-пункт $[A\to {\beta }_1\bullet {\beta }_2]$

Link to original

Допустимый для активного префикса LR(1)-пункт

В расширенной грамматике $G=(\Sigma ,\Gamma ,\_,S^{\prime })$ её LR(1)-пункт $[A\to {\beta }_1\bullet {\beta }_2,a]$ допустим для активного префикса $\gamma ={\gamma }^{\prime }{\beta }_1$ некоторой r-формы ${\gamma }^{\prime }{\beta }_1{\beta }_{2}v$, если существует правосторонний вывод

$$S^{\prime }{\Rightarrow }^{\ast }{\gamma }^{\prime }Av\Rightarrow {\gamma }^{\prime }{\beta }_1{\beta }_{2}v{\Rightarrow }^{\ast }uv$$

и цепочка $v$ начинается с символа $a$

• ${\gamma }^{\prime },{\beta }_1,{\beta }_2\in (\Sigma \cup \Gamma {)}^{\ast }$
• $u,v\in \Sigma$

Link to original

Комментарий: В процессе анализа после переноса в стек ${\beta }_2$ во входном потоке будет $a$, поскольку $v$ – необработанная часть цепочки

Автомат LR(1)-пунктов

Определяется по аналогии с автоматом LR(0)-пунктов

Автоматом LR(1)-пунктов расширенной грамматики $G=(\Sigma ,\Gamma ,P,S^{\prime })$ называется неполный эпсилон-НКА $(Q,\Sigma \cup \Gamma ,\delta ,q_0,Q)$, где

• $Q$ — множество LR(1)-пунктов грамматики $G$
• $q_0=[S^{\prime }\to \bullet S,⊣]$

Функция переходов $\delta$ задается следующим образом:

$$\delta (q,x)=\{\begin{array}{ll}\{[A\to {\beta }_{1}x\bullet {\beta }_2,a]\}& \text{если }q=[A\to {\beta }_1\bullet x{\beta }_2,a],x\in \Sigma \cup \Gamma ,a\in \Sigma \cup \{⊣\}\\ \{[B\to \bullet \gamma ,b]\}& \text{если }q=[A\to {\beta }_1\bullet B{\beta }_2,a]\text{ и }x=\epsilon ,B\in \Gamma ,a\in \Sigma \cup \{⊣\},b\in FIRST({\beta }_{2}a)\end{array},{\beta }_1,{\beta }_2,\gamma \in (\Sigma \cup \Gamma {)}^{\ast }$$

Где $FIRST({\beta }_{2}a)$ - множество FIRST от цепочки ${\beta }_{2}a$

Полагать, что $FIRST(⊣)=⊣$

Link to original

Комментарий: В процессе построения переходов такого автомата появляются только допустимые LR(1)-пункты

LR(1)-автомат

Определяется по аналогии с LR(0)-автоматом

эпсилон-замыкание автомата LR(1)-пунктов

Link to original

Комментарий: Возможно (и проще) построить LR(1)-автомат сразу, не прибегая к построению автомата LR(1)-пунктов

Пример построения LR(1)-автомата

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

По определению автомата потребуется множество FIRST. Найдем его, воспользовавшись, например, алгоритмом:

LR(1)-автомат автомат тогда будет выглядеть следующим образом

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

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

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

Link to original

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

Вход

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

Выход

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

Алгоритм

Подготовка

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

Заполнение таблицы 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

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

Расширенная грамматика называется LR(1)-грамматикой, если LR(1)-анализатор, построенный по этой грамматике не содержит конфликтов

Link to original

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

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

По определению рассмотренная грамматика $G$ является LR(1)-грамматикой