Лои. ДЗ 2025-10-21

Формулировка задачи

Расширив грамматику $G$, построить ее LR(0)-автомат:

$$G=\{D\to L:T,L\to L;a|a,T\to i\}$$

Решение

Построение расширенной грамматики $G^{\prime }$ по $G$

Соответствующая $G$ расширенная грамматика $G^{\prime }$ строится по определению

$$G^{\prime }=\{S\to D,D\to L:T,L\to L;a|a,T\to i\}$$

Построение LR(0)-автомата по грамматике $G^{\prime }$

Построим по определению

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

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

Link to original

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

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

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

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

$$\delta (q,x)=\{\begin{array}{ll}\{[A\to {\beta }_{1}x\bullet {\beta }_2]\}& q=[A\to {\beta }_1\bullet x{\beta }_2],x\in \Sigma \cup \Gamma \\ \{[B\to \bullet \gamma ]\}& q=[A\to {\beta }_1\bullet B{\beta }_2],x=\epsilon ,B\in \Gamma \end{array},{\beta }_1,{\beta }_2,\gamma \in (\Sigma \cup \Gamma {)}^{\ast }$$Link to original

Построим Автомат LR(0)-пунктов, сразу замыкая состояния по $\epsilon$ в одно состояние

stateDiagram-v2
    [*] --> $$S$$
    $$S$$ --> $$D$$ : $$D$$
    $$S$$ --> $$L$$ : $$L$$
    $$S$$ --> $$a_1$$ : $$a$$
    $$L$$ --> #58; : #58;
    $$L$$ --> $$;$$ : #59;
    #58; --> $$T$$ : $$T$$
    #58; --> $$i$$ : $$i$$
    $$;$$ --> $$a_2$$ : $$a$$

    classDef finalState fill:#c8e6c9,stroke:#4caf50,stroke-width:3px
    
    class D finalState
    class a1 finalState
    class T finalState
    class i finalState
    class a2 finalState

• $S=\{[S\to \bullet D],[D\to \bullet L:T],[L\to \bullet L;a],[L\to \bullet a]\}$
• $D=\{[S\to D\bullet ]\}$
• $L=\{[D\to L\bullet :T],[L\to \bullet ;a]\}$
• $a_1=\{[L\to a\bullet ]\}$
• $:=\{[D\to L:\bullet T],[T\to \bullet i]\}$
• $;=\{[L\to L;\bullet a]\}$
• $T=\{[D\to L:T\bullet ]\}$
• $i=\{[T\to i\bullet ]\}$
• $a_2=\{[L\to L;a\bullet ]\}$

$G^{\prime }$ является LR(0)-грамматикой. Поэтому можем построить ее LR(0)-анализатор с использованием алгоритма построения LR(0)-анализатора

Построение LR(0)-анализатора для грамматики $G^{\prime }$

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

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

Link to original

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(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

Нумерация правил грамматики

1. $S\to D$
2. $D\to L:T$
3. $L\to L;a$
4. $L\to a$
5. $T\to i$

Состояние	ACTION					GOTO
	$a$	$;$	$:$	$i$	$⊣$	$D$	$L$	$T$
$S$	$\leftarrow a_1$	$e_1$	$e_1$	$e_1$	$e_2$	$D$	$L$
$D$	$e_8$	$e_8$	$e_8$	$e_8$	​
$L$	$e_3$	$\leftarrow ;$	$\leftarrow :$	$e_4$	$e_5$
$T$	$\otimes 2$	$\otimes 2$	$\otimes 2$	$\otimes 2$	$\otimes 2$
$a_1$	$\otimes 4$	$\otimes 4$	$\otimes 4$	$\otimes 4$	$\otimes 4$
$a_2$	$\otimes 3$	$\otimes 3$	$\otimes 3$	$\otimes 3$	$\otimes 3$
$;$	$\leftarrow a_2$	$e_6$	$e_6$	$e_6$	$e_6$
$:$	$e_7$	$e_7$	$e_7$	$\leftarrow i$	$e_7$			$T$
$i$	$\otimes 5$	$\otimes 5$	$\otimes 5$	$\otimes 5$	$\otimes 5$

• $e_1$ - В начале строки допустим только символ a
• $e_2$ - Пустая строка недопустима
• $e_3$ - Символы a не могут идти рядом
• $e_4$ - Символы a и i не могут стоять рядом
• $e_5$ - Строка не может закончиться символом a
• $e_6$ - После i может идти только символ a
• $e_7$ - После символа : может следовать только i
• $e_8$ - После символа i не могут стоять символы