\documentclass[14pt,oneside,final]{extreport}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{tocbibind}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{vmargin}
\setpapersize{A4}
\setmarginsrb{2cm}{2cm}{1.5cm}{2cm}{0pt}{0mm}{0pt}{13mm}
\newenvironment{compactitemize}
{
    \begin{list}
    {{$\bullet$}}
    {
        \setlength\partopsep{0pt}
        \setlength\parskip{0pt}
        \setlength\parsep{0pt}
        \setlength\topsep{0pt}
        \setlength\itemsep{0pt}
    }
}
{
    \end{list}
}
\sloppy
\begin{document}
\section*{Формальные грамматики}
\subsection*{Основные понятия}
\textbf{Алфавит} - это конечное множество символов. \\
\textbf{Цепочка} -- последовательность символов. \\
\textbf{Терминальная цепочка} -- последовательность терминальных символов. \\
\textbf{Язык} -- множество терминальных цепочек.
\par\noindent
\textbf{Грамматика} -- это четвёрка $G = (N, T, P, S)$, где:
\begin{compactitemize}
\item $N$ -- множество нетерминальных символов (напр. $A, B, C...$);
\item $T$ -- алфавит терминальных символов ($N \cap T = \emptyset$);
\item $P$ -- конечное множество правил вывода \\
$P = \{\alpha \rightarrow \beta \mid \alpha \in (N \cup T)^+;\:\beta \in (N \cup T)^*\}$;
\item $S \in N$ -- аксиома (или начальный символ) грамматики.
\end{compactitemize}
\par\noindent
\textbf{Язык, порождённый грамматикой} -- множество всех терминальных цепочек, выводимых из аксиомы грамматики.
$L(G) = \{W \mid W \in T^*, S \Rightarrow^+ W\}$
\par\noindent
\textbf{Сентенциальная форма} -- последовательность символов (терминалов и нетерминалов), выводимых из начального символа (аксиомы).\\
\textbf{Основа цепочки} -- это подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по
которому к левой части правила соответствует одному шагу в обращении правостороннего вывода.\\
\textbf{Основа сентенциальной формы} -- позиция в сентенциальной форме, которая заменена в следующей сентенциальной форме.\\
\textbf{Основа правой сентенциальной формы $z$} -- это правило вывода $A \rightarrow v$ и позиция в $z$, в которой может быть найдена цепочка $v$ такая,
что в результате замены $v$ на $A$ получается предыдущая сентенциальная форма в правостороннем выводе $z$. Таким образом, если $S \Rightarrow $${}_r$$avb$,
то $A \rightarrow v$ в позиции, следующей за $a$ - это основа цепочки $avb$. Подцепочка $b$ справа от основы содержит только терминальные символы.
\par\noindent
Грамматика называется \textbf{неоднозначной,} если для некоторой цепочки существует хотя бы два дерева вывода.
\par\noindent
Символ $x$ называется \textbf{недостижимым,} если он не входит ни в одну сентенциальную форму (не существует вывода $S \Rightarrow^* \alpha x \beta$).\\
Символ $x$ называется \textbf{бесплодным,} если из него нельзя вывести ни одну терминальную цепочку (не существует вывода $x \Rightarrow w, w \in T^*$).\\
\textbf{Бесполезный символ} -- это недостижимый или бесплодный символ.\\
\textbf{Приведённая грамматика} -- это грамматика, не содержащая бесплодных и недостижимых символов.
\par\noindent
\textbf{Множество $FIRST(A)$} -- множество терминальных символов, которыми начинаются цепочки, выводимые из $A$ в грамматике $G$.\\
\textbf{Множество $FOLLOW(A)$} -- множество терминальных символов, которые следуют за цепочками, выводимыми из $A$ в грамматике $G$.\\
\textbf{Множество $FIRST1$} -- множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или
$\epsilon$, если $u \Rightarrow^* \epsilon$.
\par\noindent
\textbf{Лемма о разрастании}
Для любого КС-свободного языка $L$ существуют целые числа $l, k$ такие, что $\forall \alpha \in L, \mid\alpha\mid > l$ представима в виде $\alpha = uvwxy$, где:
\begin{compactitemize}
\item $\mid vwx\mid \leq k$;
\item $vx \not= \epsilon$;
\item $uv^iwx^iy \in L \:\forall i \geq 0$.
\end{compactitemize}
\par\noindent
\textbf{Лемма о накачке}
Для любого регулярого языка $L$ существует натуральное число $p(L) \geq 1$ такое, что $\forall \alpha \in L, \mid w \mid \geq p$, представима в виде
$\alpha = xyz$, где:
\begin{compactitemize}
\item $\mid y\mid \geq 1$;
\item $\mid xy \mid \leq p$;
\item $xy^iz \in L \:\forall i \geq 0$.
\end{compactitemize}

\subsection*{Иерархия Хомского}
Если на грамматику $G = (N, T, P, S)$ не накладываются никакие ограничения, то её называют \textbf{грамматикой типа 0,} или \textbf{грамматикой без ограничений.}
\par\noindent
Если:
\begin{compactitemize}
\item каждое правило грамматики, кроме $S \rightarrow \epsilon$, имеет вид $\alpha \rightarrow \beta,\: \mid\alpha\mid\leq\mid\beta\mid$;
\item в том случае, когда $S \rightarrow \epsilon \in P$, символ $S$ не встречается в правых частях правил;
то грамматику называют \textbf{грамматикой типа 1,} или \emph{неукорачивающей} грамматикой.
\end{compactitemize}
\par\noindent
Если каждое правило $p \in P$ грамматики имеет вид $A \rightarrow \alpha, A \in N,\\\alpha \in (N \cup T)^*$, то такая грамматика называется
\textbf{грамматикой типа 2} или \emph{контекстно-свободной} грамматикой.
\par\noindent
Если каждое правило $p \in P$ имеет вид $A \rightarrow xB$ или $A \rightarrow x$ (соответственно $A \rightarrow Bx$ или $A \rightarrow x$), где
$A, B \in N, x \in T^*$, то такая грамматика называется \textbf{грамматикой типа 3} или \textbf{леволинейной}
(соответственно, \textbf{праволинейной}) грамматикой.
\par\noindent
Из определения иерархии следует, что $Z_0 \supseteq Z_1 \supseteq Z_2 \supseteq Z_3$.\\
\textbf{Утверждение}\\$Z_0 \supset Z_1 \supset Z_2 \supset Z_3$.\\
Данное утверждение доказывается конструктивно (путём построения соответствующих грамматик).
\par\noindent
Грамматика находится в \textbf{нормальной форме} Хомского, если правила вывода имеют вид:
\begin{compactitemize}
\item либо $A \rightarrow BC; A, B, C \in N$;
\item либо $A \rightarrow a; a \in T^+$;
\item либо $S \rightarrow \epsilon$, и в этом случае $S$ не встречается в правых частях правил.
\end{compactitemize}

\subsection*{Выводы, однозначность, детерминированность и прочие вопросы}
Определим на множестве $(N \cup T)^*$ грамматики $G = (N, T, P, S)$ бинарное отношение выводимости $\Rightarrow$ следующим образом: если
$\delta \rightarrow \gamma \in P$, то\\$\alpha\delta\beta \Rightarrow \alpha\gamma\beta\:\forall \alpha, \beta \in (N \cup T)^*$.
\begin{compactitemize}
\item Eсли $\alpha_1 \Rightarrow \alpha_2$, то $\alpha_2$ непосредственно выводима из $\alpha_1$.
\item Eсли $\alpha \Rightarrow^k \beta (k \geq 0)$, то существует последовательность шагов\\
$\gamma_0 \Rightarrow \gamma_1 \Rightarrow \ldots \Rightarrow \Gamma_k$, где
$\alpha = \gamma_0$ и $beta = \gamma_k$.
\end{compactitemize}
Последовательность цепочек $\gamma_0, \gamma_1, \ldots, \gamma_k$ в этом случае называется
выводом $\beta$ из $\alpha$.
\par\noindent
КС-грамматика называется \textbf{однозначной} или \textbf{детерминированной,} если всякая выводимая терминальная цепочка имеет только одно дерево вывода
(соотвественно только один левый и только один правый вывод).\\
КС-грамматика называется \textbf{неоднозначной,} если для некоторой цепочки существует хотя бы два различных дерева вывода.
\par\noindent
\textbf{Левосторонний вывод} -- такой вывод, на каждом шаге которого заменяется самый левый нетерминал.\\
\textbf{Правосторонний вывод} -- такой вывод, на каждом шаге которого заменяется самый правый нетерминал.
\par\noindent
Грамматика называется \textbf{леворекурсивной,} если в ней имеется нетерминал $A$ такой, что существует вывод $A \Rightarrow^+ Aw$ для некоторой цепочки $w$.
\par\noindent
\textbf{Атрибутная грамматика} -- это четвёрка $AG = (G, A_S, A_I, R)$, где:
\begin{compactitemize}
\item $G = (N, T, P, S)$ -- приведённая контекстно-свободная грамматика;
\item $A_S$ - конечное множество синтезируемых элементов;
\item $A_I$ --конечное множество наследуемых атрибутов, $A_S \cap A_I = \emptyset$;
\item $R$ -- конечное множество семантических правил.
\end{compactitemize}

\section*{Машина Тьюринга и связанные определения}
\textbf{Недетерминированная машина Тьюринга} -- это шестёрка
$M = (Q, \Gamma, T, F, q_0, \sigma)$, где:
\begin{compactitemize}
\item $Q$ -- конечное непустое множество состояний;
\item $\Gamma$ -- конечный алфавит;
\item $T$ -- входной алфавит, $T \subseteq \Gamma \cup {\epsilon}$;
\item $q_0 \in Q$ -- начальное состояние;
\item $F \subseteq Q$ -- множество конечных состояний;
\item $\sigma$ -- функция переходов, определённая как отображение\\
$\sigma: (Q \setminus F) \times \Gamma \rightarrow 2^{Q \times \Gamma \times \{L, R\}}$.
\end{compactitemize}
\par\noindent
\textbf{Детерминированная машина Тьюринга} -- это шестёрка
$M = (Q, \Gamma, T, F, q_0, \sigma)$, где:
\begin{compactitemize}
\item $Q$ -- конечное непустое множество состояний;
\item $\Gamma$ -- конечный алфавит;
\item $T$ -- входной алфавит, $T \subseteq \Gamma \cup {\epsilon}$;
\item $q_0 \in Q$ -- начальное состояние;
\item $F \subseteq Q$ -- множество конечных состояний;
\item $\sigma$ -- функция переходов, определённая как отображение\\
$\sigma: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$.
\end{compactitemize}
\par\noindent
Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает.
\par\noindent
\textbf{Конфигурацией} машины Тьюринга называется тройка $(q, w, i)$, где:
\begin{compactitemize}
\item $q \in Q$ -- состояние машины Тьюринга;
\item $w \in \Gamma^*$ -- вход, помещаемый на ленту машины Тьюринга ($w = a_1 \ldots a_n$);
\item $i \in Z$ -- положение головки машины Тьюринга.
\end{compactitemize}
\par\noindent
Язык, \textbf{допускаемый} машиной Тьюринга -- множество таких слов $w$, что машина Тьюринга, находясь в состоянии $(q_0, w, 1)$, может достигнуть через конечное
число переходов состояния $q \in F$.\\
\textbf{Линейно-ограниченный автомат} -- это недетерминированная машина Тьюринга, которая не может выходить за область входной строки.
\par\noindent
\textbf{Утверждения}
\begin{compactitemize}
\item класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0;
\item линейно-ограниченные автоматы распознают КЗ-языки (т.е. языки класса 1); языки класса 0 распознаются только машинами Тьюринга с неограниченной памятью.
\end{compactitemize}

\section*{Регулярные множества, выражения и грамматики}
\textbf{Регулярное множество} в алфавите $T$ определяется следующим образом:
\begin{compactitemize}
\item $\emptyset$ -- регулярное множество в алфавите $T$;
\item $\{a\}$ -- регулярное множество в алфавите $T$ для каждого $a \in T$;
\item $\{\epsilon\}$ -- регулярное множество в алфавите $T$;
\item если $P$ и $Q$ -- регулярные множества в алфавите $T$, то регулярны множества:
    \begin{compactitemize}
    \item $P \cup T$ (объединение);
    \item $PQ$ (конкатенация, $\{pq \mid p \in P, q \in Q\}$;
    \item $P^*$ (итерация, $P^* = \{\epsilon\} \cup P \cup PP \cup PPP \cup \ldots$);
    \end{compactitemize}
\item ничто другое не является регулярным множеством в алфавите $T$.
\end{compactitemize}
\par\noindent
\textbf{Регулярное выражение} -- это форма записи регулярного множества.
Регулярное выражение и обозначаемое им регулярное множество в данном алфавите $T$ определяются следующим образом:
\begin{compactitemize}
\item $\emptyset$ -- обозначает множество $\emptyset$ в данном алфавите $T$;
\item $a$ - обозначает множество $\{a\}$;
\item $\epsilon$ -- обозначает множество $\{\epsilon\}$ в данном алфавите $T$;
\item если регулярные выражения $p$ и $q$ обозначают регулярные множества $P$ и $Q$ в данном алфавите $T$ соответственно, то регулярное выражение:
    \begin{compactitemize}
    \item $(p \mid q)$ обозначает множество $P \cup Q$ в данном алфавите $T$;
    \item $(pq)$ обозначает множество $PQ$ в данном алфавите $T$;
    \item $(p^*)$ обозначает множество $P^*$ в данном алфавите $T$;
    \end{compactitemize}
\item ничто другое не является регулярным выражением в данном алфавите $T$.
\end{compactitemize}
\par\noindent
\textbf{Регулярные грамматики} -- это праволинейные и леволинейные грамматики.
\par\noindent
Функция $nullable(n)$ для каждого узла $n$ синтаксического дерева регулярных выражений даёт значение \verb!true!, если поддеревья данного узла могут породить
пустое слово, и \verb!false! в противном случае.\\
Функция $firstpos(n)$ для каждого узла $n$ синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках,
генерируемых подвыражением с вершиной $n$.\\
\begin{table}[h!]
\centering
\begin{tabular}{|c|c|}
\hline узел $n$ & $firstpos(n)$ \\ \hline
$\epsilon$ & $\emptyset$ \\ \hline
$i \not= \epsilon$ & $\{i\}$ \\ \hline
$u \mid v$ & $firstpos(u) | firstpos(v)$ \\ \hline
$u.v$ & $nullable(u)$ ? $firstpos(u) \cup firstpos(v)$ : $firstpos(u)$ \\ \hline
$v^*$ & $firstpos(v)$ \\ \hline
\end{tabular}
\caption{Построение $firstpos(n)$}
\end{table}
Функция $lastpos(n)$ для каждого узла $n$ синтаксического дерева регулярных выражений даёт множество позиций, которым соответствуют последние символы в цепочках,
генерируемых подвыражениями с вершиной $n$.\\
\begin{table}[h!]
\centering
\begin{tabular}{|c|c|}
\hline узел $n$ & $lastpos(n)$ \\ \hline
$\epsilon$ & $\emptyset$ \\ \hline
$i \not= \epsilon$ & $\{i\}$ \\ \hline
$u \mid v$ & $lastpos(u) | lastpos(v)$ \\ \hline
$u.v$ & $nullable(v)$ ? $lastpos(u) \cup lastpos(v)$ : $lastpos(v)$ \\ \hline
$v^*$ & $lastpos(v)$ \\ \hline
\end{tabular}
\caption{Построение $lastpos(n)$}
\end{table}
Функция $followpos(i)$ для позиции $i$ есть множество позиций $j$ таких, что существует некоторая строка $\ldots cd \ldots$, входящая в язык, описываемый
регулярным выражением, такая, что позиция $i$ соответствует вхождению $c$, а позиция $j$ — вхождению $d$.
\par\noindent
\textbf{Утверждение}\\
Любой конечный автомат распознает регулярное множество цепочек символов входного алфавита. Верно и обратное -- для любого регулярного языка можно построить распознающий его конечный автомат.

\section*{Автоматы}
\textbf{Недетерминированный конечный автомат} -- это пятёрка
$M = (Q, T, F, q_0, \sigma)$, где:
\begin{compactitemize}
\item $Q$ -- конечное непустое множество состояний;
\item $T$ -- входной алфавит;
\item $q_0 \in Q$ -- начальное состояние;
\item $F \subseteq Q$ -- множество конечных состояний;
\item $\sigma$ -- функция переходов, определённая как отображение\\
$\sigma: Q \times(T \cup \{\epsilon\}) \rightarrow 2^Q$, такое, что $\sigma(q,a) = \{r : q \rightarrow_a r\}$.
\end{compactitemize}
\par\noindent
\textbf{Детерминированный конечный автомат} -- это пятёрка
$M = (Q, T, F, q_0, \sigma)$, где:
\begin{compactitemize}
\item $Q$ -- конечное непустое множество состояний;
\item $T$ -- конечный входной алфавит;
\item $q_0 \in Q$ -- начальное состояние;
\item $F \subseteq Q$ -- множество конечных состояний;
\item $\sigma$ -- функция переходов, определённая как отображение $\sigma:Q \times T \rightarrow Q$
\end{compactitemize}
\par\noindent
Недетерминированный конечный автомат является обобщением детерминированного.
\par\noindent
\textbf{Утверждение}\\
Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали (такие автоматы называются эквивалентными).\\
В детерменированном автомате из одного состояния допускается не более одного перехода для каждого символа алфавита, в недетерменированном - произвольное
количество. Кроме того, в НКА возможны $\epsilon$-переходы.
\par\noindent
\textbf{Конфигурацией автомата} $M = (Q, T, D, q_0, \sigma)$ называется пара $(q, \omega) \in Q \times T^*$,
где $q$ -- текущее состояние управляющего устройства, а $\omega$ -- цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа
от неё.
\par\noindent
Два состояния $q_i$ и $q_j$ называются \textbf{эквивалентными ($q_i \sim q_j$),} если\\
$\forall z \in T^* \sigma(q_i,z) \in T \Leftrightarrow \sigma(q_j,z) \ in T$.\\
Два состояния $q_i$ и $q_j$ называются \textbf{различимыми,} если они не являются эквивалентными.
\par\noindent
Автомат $M$ \textbf{допускает цепочку $\omega$,} если $M(q_0, \omega) \mid-^* (q, \omega), \forall q \in \sigma$.\\
\textbf{Языком, допускаемым автоматом} $M$, называется множество входных цепочек, допускаемых автоматом $M$, то есть множество\\
$L(M) = \{\omega \mid \omega \in T^*$ и $(q_0, \omega) \mid-^* (q, \epsilon), \forall q \in \sigma\}$.
\par\noindent
\textbf{$\epsilon$-замыкание} множества состояний $R, R \subseteq Q$ -- множество состояний НКА, достижимых из состояний, входящих в $R$, посредством только
переходов по $\epsilon$, то есть множество $S = U_{q \in R}\{p \mid (q, \epsilon) \mid-^* (p, \epsilon)\}$.\\
\textbf{Расширенная функция переходов} множества состояний $R, R \subseteq Q$ по $a$ -- множество состояний КА, в которые есть переход на входе $a$ для состояний
из $R$, то есть множество $S = U_{q \in R}\{p \mid p \in \sigma(q, a)\}$.

\subsection*{Автоматы с магазинной памятью}
\textbf{Недетерминированный МП-автомат} -- это семёрка $M = (Q, T, \Gamma, \sigma, q_0, Z_0, F)$, где:
\begin{compactitemize}
\item $Q$ -- конечное множество состояний, представляющее всевозможные состояния управляющего устройства;
\item $T$ -- конечный входной алфавит;
\item $\Gamma$ -- конечный алфавит магазинных символов;
\item $\sigma$ -- отображение $Q \times (T \cup \{\epsilon\}) \times \Gamma \rightarrow 2^{Q \times \Gamma^*}$, называемое функцией переходов;
\item $q_0 \in Q$ -- начальное состояние управляющего устройства;
\item $Z_0 \in \Gamma$ -- символ, находящийся в магазине в начальный момент (начальный символ магазина);
\item $F \subseteq Q$ -- множество заключительных состояний.
\end{compactitemize}
\par\noindent
\textbf{Детерминированный МП-автомат} -- это семёрка $M = (Q, T, \Gamma, \sigma, q_0, Z_0, F)$, где:
\begin{compactitemize}
\item $Q$ -- конечное множество состояний, представляющее всевозможные состояния управляющего устройства;
\item $T$ -- конечный входной алфавит;
\item $\Gamma$ -- конечный алфавит магазинных символов;
\item $\sigma$ -- отображение $Q \times (T \cup \{\epsilon\}) \times \Gamma \rightarrow Q \times \Gamma^*$, называемое функцией переходов;
\item $q_0 \in Q$ -- начальное состояние управляющего устройства;
\item $Z_0 \in \Gamma$ -- символ, находящийся в магазине в начальный момент (начальный символ магазина);
\item $F \subseteq Q$ -- множество заключительных состояний.
\end{compactitemize}
Кроме того, должны выполняться следующие условия:
\begin{compactitemize}
\item множество $D(q, a, Z)$ содержит не более одного элемента $\forall q \in Q, a \in T \cup \{\epsilon\}, Z_0 \in \Gamma$;
\item если $D(q, \epsilon, Z) \not= \emptyset$, то $D(q, a, Z) = \emptyset \forall a \in T$.
\end{compactitemize}
\par\noindent
\textbf{Конфигурацией МП-автомата} называется тройка $(q, w, u)$, где
\begin{compactitemize}
\item $q \in Q$ -- текущее состояние магазинного устройства;
\item $w \in T^*$ -- непрочитанная часть входной цепочки; первый символ цепочки $w$ находится под входной головкой; если $w = \epsilon$, то считается,
что входная лента прочитана;
\item $u \in \Gamma^*$ — содержимое магазина; самый левый символ цепочки $u$ считается вершиной магазина; если $u = \epsilon$, то магазин считается пустым.
\end{compactitemize}
\par\noindent
\textbf{Тактом работы} МП-автомата называется бинарное отношение $\mid-$, определённое на множестве конфигураций:\\$(q, aw, Zu) \mid- (p, w, vu)$, если
$D(q, a, z) \ni (p, v);\:q, p \in Q, a \in T \cup \{\epsilon\},$\\$w \in T^*, Z \in \Gamma, u, v \in \Gamma^*$.
\par\noindent
Цепочка $w$ \textbf{допускается} МП-автоматом, если $(q_0, w, Z_0)\mid-^* (q, \epsilon, u)$ для некоторых $q \in F$ и $u \in \Gamma^*$. Язык, \textbf{допускаемый}
МП-автоматом -- множество всех цепочек, допускаемых этим автоматом.\\
В случае, когда цепочка $w$ допускается МП-автоматом, если\\
$(q_0, w, Z_0)\mid-^* (q, \epsilon, \epsilon)$ для некоторого $q \in Q$, говорят, что автомат допускает
цепочку \textbf{опустошением магазина.}
\par\noindent
\textbf{Утверждение}\\
Языки, порождаемые КС-грамматиками, и языки, допускаемые недетерминированными МП-автоматами, совпадают.

\section*{LL(k) и LR(k)}
Контекстно-свободная грамматика называется \textbf{$LL(1)$ грамматикой} тогда и только тогда, когда выполняются следующие два условия:
\begin{compactitemize}
\item для каждого нетерминала, являющегося левой частью нескольких правил, $A \rightarrow \alpha_1 | \alpha_2 | \ldots | \alpha_n$ необходимо, чтобы
$FIRST(\alpha_i) \cap FIRST(\alpha_j) = \emptyset,$ $i \not= j$;
\item для каждого аннулирующего нетерминала $A \Rightarrow^* \$$ необходимо, чтобы $FIRST(A) \cap FOLLOW(A) = \emptyset$.
\end{compactitemize}
\par\noindent
Грамматика, для которой таблицы анализа не имеют неоднозначно определённых входов, называется $LL(1)$.\\
Грамматика, для которой можно построить таблицу $LR$ разбора, называется \textbf{$LR$ грамматикой.}
\par\noindent
Грамматика называется $LR(1)$, если из условий:
\begin{compactitemize}
\item $S' \Rightarrow $${}_r$$uAw \Rightarrow $${}_r$$uvw$;
\item $S' \Rightarrow $${}_r$$zBx \Rightarrow $${}_r$$uvy$;
\item $FIRST(v) = FIRST(y)$
\end{compactitemize}
следует, что $uAy = zBx$ (т.е. $u = z, A = B$ и $x = y$).
\par\noindent
\textbf{Конфигурация} $LR$ анализатора -- это пара, первая компонента которой -- содержимое стека, а вторая -- непросмотренный вход:
$(S_0 X_1 S_1 X_2 S_2 \ldots X_m S_m, A_i A_{i + 1} \ldots A_n \$)$.
Эта конфигурация соответствует правой сентенциальной форме $X_1 X_2 \ldots m A_i A_{i + 1} \ldots A_n$.
\par\noindent
\textbf{Замыкание} множества $LR(1)$ ситуаций, допустимых для некоторого активного префикса $z$ -- это множество всех $LR(1)$ ситуаций, допустимых для этого
префикса.
\par\noindent
$LR$ анализатор выполняет \textbf{4 типа действий:}
\begin{compactitemize}
\item \verb!Shift!;
\item \verb!Reduce!;
\item \verb!Accept!;
\item \verb!Reject!.
\end{compactitemize}
При выполнении действия \verb!Shift!, верхний символ входа переносится в магазин, а затем на верх магазина помещается состояние \verb!action!
(предыдущее состояние, взятый символ.\\
При выполнении действия \verb!Reduce!, из стека убирается правая часть правила и добавляется левая и состояние \verb!goto!
(последнее состояние в магазине, символ из левой части правила).
\par\noindent
В канонической системе множеств $LR(1)$ ситуаций может возникать \textbf{2 типа конфликтов:}
\begin{compactitemize}
    \item \verb!Shift - Reduce! (невозможно выбрать действие);
    \item \verb!Reduce - Reduce! (невозможно выбрать правило, относительно которого применяется действие).
\end{compactitemize}

\end{document}
