\documentclass[12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning,trees}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}
\usepackage{enumitem}


%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\theoremstyle{definition}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\emptyset
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\abstractname{}

\let\yield\Rightarrow
\def\yields{\Rightarrow^*}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\def\LL{{\mathrm{LL}}}
\def\LR{{\mathrm{LR}}}

\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prpfrom[#1]{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }
\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\mathbf{\theproblem}^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0} }
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem .  } }
\def\prsubr{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem)  } }
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$\negthickspace.  } }
\def\prsubrstar{\medskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$)  } }
%прочее
\def\quotient{\backslash\negthickspace\sim}
\begin{document}
\centerline{\LARGE Задание 11}
 
\medskip

\begin{center}
	{\Large LL- и LR-анализ}
\end{center}

\bigskip

{\bf Ключевые слова }\footnote{минимальный необходимый объем понятий и навыков по
этому разделу)}:{\em  язык, контекстно-свободный язык, магазинный автомат, грамматика, $\LL(k)$-грамматика, $\LL(1)$-анализатор, функции $\first, \follow$. %примеры нерегулярных языков;
%поиск подстрок, алгоритм Кнута- Морисса- Пратта.

%языки скобочных выражений (языки Дика). 
}

\section{Нисходящий и восходящий разбор}

Напомним определение вывода КС-грамматики.

\emph{Выводом} цепочки $\alpha$ называется такая последовательность применений правил с указанием раскрываемого нетерминала, что применяя правила из неё начиная с аксиомы получается цепочка $\alpha$. Если цепочка $\alpha$ не содержит нетерминалов, то $\alpha$ принадлежит языку, порождаемому КС-грамматикой. Нам будет удобно пользоваться такими понятиями как левый вывод (правый вывод).  \emph{Левым выводом} называют такой вывод, что на каждом его шаге раскрывается самый левый нетерминал в промежуточной цепочке. Правый вывод определяется аналогично.




Также напомним что мы называем деревом вывода или деревом разбора. С формальным определением дерева разбора вы можете познакомиться, например, в книге Хопкрофта, Мотвани и Ульмана, а мы воспользуемся неформальным описанием этого понятия. \emph{Деревом разбора} для грамматики $G$  называется упорядоченное дерево, в корне которого находится аксиома $S$, каждая вершина помечена нетерминалом, терминалом или пустым словом, если вершина помечена терминалом или $\eps$, то эта вершина является листом, если же вершина помечена нетерминалом $A$, то существует такое правило $ A \to X_1X_2\ldots X_n \in P$ ($X_i \in N\cup T$), что вершины-потомки $A$ помечены символами $X_1, X_2\ldots X_n$ слева направо.

Будем говорить, что для КС-грамматики $G$ слово $w$ разобрано, если известно хотя бы одно из её деревьев вывод.

\emph{Левым разбором } цепочки $\alpha \in (N\cup T)^*$ будем называть последовательность правил, применённых при левом выводе цепочки $\alpha$. \emph{Правым разбором} цепочки $\alpha$ назовём обратную последовательность правил, применённых при правом выводе цепочки $\alpha$.
                                                                                                                                                
%LL(1)-грамматика:
%$$ E \to TE^\prime;\; E^\prime \to +TE^\prime \mid \eps;\; T \to FT^\prime;\; T^\prime \to \times FT^\prime \mid \eps;\; F \to (E) \mid id. $$ 

\begin{Example}\label{GTree}
	Грамматики $G = (N,T,P,E)$, и $G_\pi = (N,T',P',E)$, $T = \{a, +, *\}$ заданы правилами:
	\begin{multicols}{2}		
		\begin{align}
		 	E &\to E+T\\
		 	E &\to T\\
		 	T &\to T*F\\
			T &\to F\\
		 	F &\to (E)\\
		 	F &\to a
		\end{align}
		
		\begin{align*}
		 	E &\to 1ET\\
		 	E &\to 2T\\
		 	T &\to 3TF\\
			T &\to 4F\\
		 	F &\to 5E\\
		 	F &\to 6
		\end{align*}
	\end{multicols}

	Построим дерево разбора для слова $w = a + (a * a)$ и дерево вывода в грамматики $G'$, соответствующее выводу $w$ :
	\newpage
	
	\begin{multicols}{2}
		\begin{flushleft}
			
		\begin{tikzpicture}
			\node {$E$} %root
				child{ node   {$T$}
				 	child{ node {$T$}
						child{ node{$F$}
							child{ node {$a$} }
						}
					}
					child{ node {$*$} }
					child{ node {$F$}
						child{ node {$($}  }
						child{ node {$E$}  
							child{ node{$E$}
								child{ node{$T$}
									child{ node{$F$}
										child{ node {$a$} }										
									}
								}
							}
							child{ node{$+$} }
							child{ node{$T$}
								child{ node{$F$}
									child{ node {$a$} }										
								}
							}
						}
						child{ node {$)$}  }
					}
			};
		\end{tikzpicture}
				\end{flushleft}
		\begin{flushright}
			
		\begin{tikzpicture}
			\node {$E$} %root
				child{ node{$2$} }
				child{ node   {$T$}
					child{ node{$3$} }
				 	child{ node {$T$}
						child{ node{$4$} }				
						child[sibling angle=90,clockwise from=0]{ node{$F$}
							child[sibling angle=0,clockwise from=270]{ node {$6$} }
						}
					}
					child{ node {$F$}
						child{ node {$5$}  }
						child{ node {$E$} 
							child{ node{$1$} } 
							child{ node{$E$}
								child{ node{$2$} }
								child[sibling angle=90,clockwise from=0]{ node{$T$}
									child[sibling angle=0,clockwise from=270]{ node{$4$} }
									child[level distance = 1.75cm, sibling angle=0,clockwise from=300]{ node{$F$}
										child[sibling angle=0,clockwise from=270]{ node {$6$} }										
									}
								}
							}
							child{ node{$T$}
								child{ node{$4$} }
								child{ node{$F$}
									child{ node {$6$} }										
								}
							}
						}
					}
			};
		\end{tikzpicture}
				\end{flushright}	
	\end{multicols}
	
	Если грамматика $G$ выводит слово $w$, то применяя соответствующие правила в $G'$ выводим из неё слово $\pi_l(w)$, соответствующее левому выводу слова $w$.
\end{Example}
	Назовём \emph{переводом} бинарное отношение $T$, действующее из языка $L_1$ в язык $L_2$. Если пара слов $(u,v) $ удовлетворяет отношению $ T$, то будем говорить, что слово $u$ транслируется переводом $T$ в слово $v$, а слово $v$ будем называть \emph{выходом} для $u$. 
	Мы будем рассматривать синтаксически управляемые переводы. Неформально, перевод является синтаксически управляемым, если существует пара грамматик, правила которых занумерованы и если на шаге вывода из одной грамматики получена цеапочка $\alpha$, а для соответствующего шага вывода из другой грамматики получена цепочка $\beta$, то любой нетерминал входящий в цепочку $\alpha$, входит и в цепочку $\beta$ с одинаковой кратностью. Например, в лингвистике нетерминалы могут соответствовать частям речи. Тогда при переводе с одного языка на другой подлежащее перейдёт в подлежащее, а сказуемое в сказуемое, таким образом, синтаксис определяет некоторые особенности семантики языка. Эта особенность также весьма полезна и при построении компиляторов. Формально, перевод называется синтаксически управляемым, если есть синтаксически управляемая схема (СУ-схема), его реализующая. Определим формально СУ-схему.

\begin{Def}
	Синтаксически управляемой схемой назовём пятёрку $T = (N, \Sigma, \Delta, R, S)$, где $N$ множество нетерминалов, $\Sigma$ и $\Delta$ алфавиты входа и выхода схемы, $R$ -- множество правил вида $A \to \alpha, \beta$, причём нетерминалы входящие в цепочку $\alpha$ входят также и в цепочку $\beta$, причём с той же кратностью. 
\end{Def}

Как легко видеть, из языка $L(G)$ существует СУ-перевод в язык $L(G')$, схема которого строится по грамматикам. А именно множество $R$ строится по соответствующим парам правил, описанных выше. 

\upr Предъявить алгоритм построения по грамматики $G$ синтаксический перевод $T_l$, переводящий слово $w$ из $L(G)$ в левый вывод данного слова $\pi_l(w)$.

Восходящий разбор строится аналогично по правому выводу.

\upr Построить правый вывод $w = a+(a*a)$ по дереву разбора. По правому выводу построить разбор $\pi_r(w)$.

\upr Построить по описанной выше грамматике $G$ схему СУ-перевода, реализующую перевод $w \to \pi_r(w)$. Предъявить алгоритм построения схемы данного СУ-перевода по грамматике.

\begin{comment}
	

\section{Функция $\first$}
При построении (детерминированных) анализатаров по грамматике, нам потребуется определять множество первых $k$ символов слов, выводимых из цепочки $\alpha \in (N\cup T)^*$. Для этого мы будем использовать функцию $\first_k$, которая определена через функцию $\first_1$ или просто $\first$. Таким образом умение вычислять функцию $\first$ является ключевым при построении анализаторов.

Формально, 
$$
	\first_k(\alpha) = \{ w[1,k]\, |\, \alpha \yield w, |w| > k  \} \cup \{ w\,|\, \alpha \yield w, |w| < k\}
$$

Если $\alpha \yield \eps$, то пустое слово лежит в $\first_k (\alpha)$.

Приведём процедуру вычисления функции $\first(\alpha)$. 

\emph{\textbf{Идея алгоритма:}} Если $\alpha = X_1X_2\ldots X_n$ начинается с терминала $\sigma$, то первым символом может быть только этот терминал, таким образом, мы сразу получаем ответ $\sigma$. Если же $\alpha$ начинается с нетерминала, то $\first(\alpha) = \first(X_1)$, если из нетерминала $X_1$ не выводится пустое слово, и $\first(\alpha) = \first(X_1)\cup \first(X_2X_3\ldots X_n)$, если $X_1 \yield \eps$. 


Таким образом, мы описали вычисление функции $\first$ на множестве терминалов и цепочек, начинающихся с терминалов, осталось описать вычисление функции на множестве нетерминалов, как видно вычисление функции $\first$ на множестве сентенциальных форм сводится к вычислению функции на отдельных нетерминалах.


Пусть мы вычисляем функцию $\first(X)$ для нетерминала $X$. Рассмотрим все правила вида $X \to \beta$. Очевидно, что $\first(\beta)$ является подмножеством $\first(X)$, но просто добавляя множество $\first(\beta)$ к $\first(X)$ мы получим порочный круг, в случае правил вида $ X \to Xa$. Как нам избежать порочного круга при вычислении множества $\first(X)$? 


Определим множества $F_i(Y),\ Y \in N$. При $i = 0$ для любого нетерминала $Y$, множество $F_i(Y) = \es$, или $ \{\eps\}$, если есть правило $Y\to \eps$. На $i-$ом шаге алгоритма будем вычислять множества $F_i(X)$ следующим образом. В начале шага $F_i(X)$ включает себя множество $F_{i-1}(X)$ Если есть правило $X \to \beta = Y_1Y_2\ldots Y_n$ и $Y_1$ -- терминал или $\beta$ -- пустое слово, то добавим к множеству $F_i(X)$ элемент $Y_1$ (быть может пустое слово). Если же $Y_1$ -- нетерминал, и при этом пустое слово не лежит в $F_{i-1}(Y_1)$, то добавим к множеству $F_i(X)$ множество $F_{i-1}(Y_1)$ и вычислим множество $F_{i}(Y_1)$. Если же $\eps \in F_{i-1}(Y_1)$, то добавим к $F_i(X)$ множество $F_i(Y_1)\setminus\{\eps\}$ и повторим описанную операцию для $\beta = Y_2\ldots Y_n$.

Алгоритм останавливается, как только для каждого нетерминала $Y$, множества $F_i$ и $F_{i-1}$ совпадают.

\begin{flushleft}
	
\emph{\textbf{Алгоритм}:} 
\end{flushleft}
\setlist[1]{itemsep=-3pt}
\begin{itemize}
	\item[ ] \emph{Шаг 0.}  Для каждого терминала $\sigma$ положим $F_i(\sigma) = \sigma$ для любого $i$. Для каждого нетерминала $Y$, если есть правило $Y\to \eps$,  положим $F_0(Y) = \{\eps\}$, иначе положим $F_0(Y) = \es$.
	\item[ ] \emph{Шаг i.} Добавить к множеству $F_i(X)$ множество $F_{i-1}(X)$. Для каждого правила $X \to \beta = Y_1\ldots Y_n$ выполнить:
	\item[ ] \quad $j = 1$
	\item[ ] \quad Пока $\eps \in F_{i-1}(Y_j)$
	\item[ ] \qquad добавить $F_{i-1}(Y_j)\setminus\{\eps\}$ к $F_i(X)$, 
	\item[ ] \qquad увеличить $j$.
	\item[ ] \quad Если $\eps \in F_{i-1}(Y_1)\cap F_{i-1}(Y_2)\cap\ldots \cap F_{i-1}(Y_n)$, добавить $\eps$ к $F_i(X)$,
	\item[ ] \emph{Остановка.} $F_i(Y) = F_{i-1}(Y)$ для любого $Y$ из $N$. Положить $\first(X) = F_i(X)$.
\end{itemize}





\upr Доказать корректность данного алгоритма.

\section{Функция $\follow$}

Помимо префикса порождаемого цепочкой $\beta$ нас будет интересовать также и множество слов, которые могут следовать после слова, выведенного из цепочки $\beta$. Запишем сначала формальное определение функции $\follow_k$.

$$
	\follow_k(\beta) = \{ w\,|\, S \yield \alpha\beta\gamma, w \in \first_k(\gamma) \}.
$$

Неформально, в множестве $\follow_k(\beta)$ содержатся те слова, которые могут следовать за словом, выведенным из $\beta$, в цепочке $\alpha\beta\gamma$, выводимой из аксиомы. Длина этих слов ограничена $k$, что означает, что если $\gamma \yield w$ и длина слова $w$ меньше $k$, то $w$ лежит в множестве $\follow_k(\beta)$, а если же  длина слова $w$ больше $k$, то в множестве $\follow_k(\beta)$ лежит префикс $w$ длины $k$. 

Аналогично функции $\first$, мы будем обозначать $\follow_1$ как $\follow$.

Мы будем часто пользоваться функцией $\follow_k$ в теоретических целях и для обозначения объектов, однако на практике мы будем вычислять функцию $\follow$ только на множестве нетерминалов.



Приведём алгоритм для вычисления функции $\follow$.

\textbf{\emph{Идея алгоритма:}} Если в грамматике есть правило $A \to \alpha X\beta$, то за словом, выведенным из нетерминала $X$ следует слово выведенное из $\beta$, таким образом множество $\follow(X) $ включает в себя множество $ \first(\beta)$. Если, при этом из цепочки $\beta$ выводимо пустое слово, то за словом, выводимым из нетерминала $X$ следует слово из множества $\follow(A)$, поскольку из вывода

$$ S \yields \gamma A w \yield \gamma \alpha X \beta w \yield  \gamma \underbrace{\alpha X}_{A} w  $$

следует, что если элемент $\first(w) $ лежит в множестве $ \follow(A)$, то элемент $\first(w) $ лежит так же в множестве $ \follow(X)$. Таким образом, по определению функции $\follow$, если в грамматике есть правило $\A \to \alpha X \beta$ и при этом из цепочки $\beta $ выводимо пустое слово, то множество $\follow(X) $ включает в себя множество $ \follow (A)$. В частности, возможно что $\beta = \eps$, поэтому при наличии в грамматике правила $A \to \alpha X$, справедливо $\follow(X) \supseteq \follow (A)$.

В итоге, мета-алгоритм сводится к следующим шагам:

\begin{itemize}
	\item Вычислить множества $\first$ для грамматики $G$;
	\item Для правил $A \to \alpha X \beta$ добавить $\first(\beta)\setminus\{\eps\}$ к $\follow(X)$;
	\item Для правил $A \to \alpha X \beta$, таких что, $\eps \in \first(\beta)$ добавить $\follow(A)$ к $\follow(X)$.
\end{itemize}

\upr Доказать корректность данного мета-алгоритма. То есть, что все элементы множеств $\follow$ будут найдены и ничего лишнего найдено не будет.

\begin{Remark}
	По хорошему, возникает проблема с тем, лежит ли пустое слово в $\follow(X)$. Эта проблема решается следующим образом: ко всем словам, порождаемым $G$ добавляется маркер конца слова, и если этот маркер оказывается в $\follow(X)$, то пустое слово принадлежит $\follow(X)$. Для этого по грамматике $G$ строится пополненная грамматика $G^\prime$, которая содержит правило $S^\prime \to S\$$, где $\$$ -- маркер конца слова. Все остальные правила грамматики $G^\prime$ взяты из грамматики $G$. На практике, функция $\follow$ используется в анализаторах, на вход которым и так подаётся пополненная грамматика, поэтому решать проблему наличия пустого слова в множестве $\follow(X)$ не надо. 	
\end{Remark}

Теперь опишем сам алгоритм. Идея алгоритма схожа с индуктивным вычислением множеств $\first$.

\newpage

\emph{\textbf{Алгоритм}:} 

\setlist[1]{itemsep=-3pt}
\begin{itemize}
	\item[ ] \emph{Шаг 0.}  Для каждого нетерминала $Y$ положим $F_0(Y) = \es$. Вычислим значение функции $\first$ для грамматики $G$. 
	\item[ ] \emph{Шаг i.}  Положить множество $F_i(X)$ равным множеству $F_{i-1}(X)$. Для каждого правила $A \to \alpha X \beta$ добавить $\first(\beta)\setminus\{\eps\}$ к $F_i(X)$; Если $\eps \in \first(\beta)$ добавить $F_{i-1}(A)$ к $F_{i}(X)$.
	\item[ ] \emph{Остановка.} Как только $F_i(Y) = F_{i-1}(Y)$ для любого $Y$ из $N$. Положить $\follow(X) = F_i(X)$.
\end{itemize}

\end{comment}


\section{От $\first$ к $\first_k$}

Алгоритмы вычисления $\first$ и $\follow$ приведены в предыдущем задании. Основное, что нужно понять из этого раздела~"--- определение функции $\first_k$. Остальное нужно для понимания как перейти от $\LL(1)$-грамматик к $\LL(k)$-грамматикам, а позже~"--- от $\LR(1)$-анализаторов к $\LR(k)$-анализаторам.

Сначала введём вспомогательную операцию на множествах. Пусть $L_1$ и $L_2$ некоторые языки.  Тогда язык $L_1 \oplus_k L_2$ состоит из всех таких слов $w$, что либо в языке $L_1$ есть слово $w_1$ длины не меньшей $k$ и $w = w_1[1,k]$, либо слово $x$ длины не большей $k$ лежит в $L_1$, слово $y$ лежит в $L_2$, слово $u$ есть их конкатенация $xy$ и, наконец, $w = u[1,k]$, если $|u| > k$ или просто $w = u$, если $|u| < k$. Формально
$$
 	L_1 \oplus_k L_2 = \{ w\,|\, \exists x \in L_1, \exists y \in L_2, u = xy, |u| \leq k \Rightarrow w = u, |u| > k \Rightarrow w = u[1,k]  \}
$$ 
Другой вариант формального определения, чтобы окончательно запутать читателя:
$$
 	L_1 \oplus_k L_2 = \{ xy\,|\,  x \in L_1, y \in L_2,  |xy| \leq k   \} \cup \{ u[1,k] \,|\,  \exists x \in L_1, \exists y \in L_2, u = xy,  |xy| > k  \}
$$ 

%Доопределим операцию $\oplus_k$ для пустого множества. Для любого языка $L$, $L \oplus_k \es = \es \oplus_k L = \es$.

Из определения операции $\oplus_k$ следует, что для $X_1, X_2,\ldots X_n \in N\cup T$ справедливо
 $$\first_k(X_1X_2\ldots X_n) = \first_k(X_1)\oplus_k \first_k(X_2)\oplus_k\ldots\oplus_k\first_k(X_n). $$ 

Фактически, когда мы вычисляли функцию $\first$, мы вычисляли её используя оператор $\oplus_1$. Перепишем алгоритм вычисления функции $\first$ для вычисления функции $\first_k$.

\begin{flushleft}
\emph{\textbf{Алгоритм}:} 
\end{flushleft}
\setlist[1]{itemsep=-3pt}
\begin{itemize}
	\item[ ] \emph{Шаг 0.} Для каждого терминала $\sigma$ положим $F_i(\sigma) = \sigma$ для любого $i$. Для каждого нетерминала $Y$, рассмотрим все правила вида $Y \to x\alpha, $ где $x$ -- слово (быть может пустое!), а цепочка $\alpha$ либо начинается с нетермнинала, либо пуста. Если $|x| \geq k$ , добавим к множеству $F_0(Y) $ слово $ x[1,k]$. Иначе, если $\alpha = \eps$, добавим к множеству $F_0(Y) $ слово $x$.
	\item[ ] \emph{Шаг i.} Добавить к множеству $F_i(X)$ множество $F_{i-1}(X)$. Для каждого правила $X \to \beta = Y_1\ldots Y_n$
	\item[ ] \qquad добавить к $F_i(X)$ множество $F_{i-1}(Y_1)\oplus_k  \ldots \oplus_k F_{i-1}(Y_n)$, 
	\item[ ] \qquad вычислить $F_i(Y_j)$, для $j = 1..n$
	\item[ ] \emph{Остановка.} $F_i(Y) = F_{i-1}(Y)$ для любого $Y$ из $N$. Положить $\first_k(X) = F_i(X)$.
\end{itemize}

\upr Доказать корректность работы данного алгоритма.
\bigskip

На практике удобно вычислять функцию $\first_k$ для всех нетерминалов сразу.  

\section{$\LL(k)$-грамматики}

Мы не будем строить анализаторы для $\LL(k)$-грамматик, где $k>1$ в силу нехватки времени. Тем не менее, мы будем работать с определением $\LL(k)$-грамматики и её свойствами.

Вспомним, что грамматика является $\LL(k)$-грамматикой тогда и только тогда, когда она левоанализируема, т.е. существует детерминированный анализатор (ДМП-автомат с выходом), который реализует СУ перевод $w \to \pi_l(w)$.

С таким определением не очень удобно работать с точки зрения анализа грамматики, поэтому мы будем также использовать эквивалентное ему определение.

\begin{Theorem}
	Грамматика является $\LL(k)$-грамматикой тогда и только тогда, когда для любых двух правил $A \to \beta, A \to \gamma$, $\first_k(\gamma\alpha)\cap \first_k(\beta\alpha) = \es $ для таких $\alpha$, что $ S \yields_l wA\alpha$.
\end{Theorem}

Не все грамматики, задающие $\LL$-языки являются $\LL$-грамматиками. Но некоторые из них можно преобразовать к $\LL(k)$-грамматике используя такие приёмы как левая факторизация и удаление левой рекурсии. Изучите эти приёмы по книжке Серебрякова или по Ахо и Ульману.

\section{Подготовка к изучению $\LR$-анализа}

$\LR$-анализаторы устроены гораздо сложнее, чем $\LL$-анализаторы. Их построение можно изучить по книге Серебрякова, а за подробностями обратиться к книге Ахо и Ульмана, оригиналной статье Кнута или тексту на странице курса. В этом разделе мы приведём технические конструкции, нужные для построения $\LR(1)$-анализатора.


Зафиксируем пополненную грамматику $G$. Назовём $\LR(k)$-ситуацией набор  $$[ A \to X_1X_2\ldots X_i\cdot X_{i+1}\ldots X_n, u],$$ где $A \to X_1\ldots X_n$~"--- правило $G$, $u$~"--- слово длины не больше $k$ (параметр $\LR(k)$ анализатора) над алфавитом $\Sigma\cup\{\$\}$ (возможно пустое), а <<$\cdot$>>~"--- вспомогательный символ, который встречается ровно один раз.

Определим недетерминированный $\LR(k)$-автомат Кнута для грамматики $G$. Множество состояний автомата~"--- $\LR(k)$-ситуации грамматики $G$. Начальное состояние автомата~"--- ситуация $[S^\prime \to \cdot S, \$ ]$. Переходы определены следующим образом:

Если состояние~"--- ситуация вида $[A \to \alpha\cdot B\gamma, u]$, то для каждого правила $B\to \beta$ и каждого слова $v \in \first_{k}(\gamma u)$ определён $\eps$ переход $$ [A \to \alpha\cdot B\gamma, u]\xrightarrow{\eps} [B \to \cdot\beta,v] $$

Для состояния (ситуации) $[A \to \alpha\cdot X\gamma, u]$, где $X \in \Sigma\cup N$ определён переход  
$$[A \to \alpha\cdot X\gamma, u] \xrightarrow{X} [A \to \alpha X\cdot \gamma, u] $$

Множество принимающих состояний несущественно для дальнейшего использования автомата Кнута, будем считать, что оно пусто.

\section{Задачи}

В первых двух задачах под грамматикой $G$ понимается грамматика, порождающая арифметические выражения.

\prp Построить дерево вывода, левые и правые разборы для слова $((a))$ в грамматике $G$, определённой выше.


\prp Постройте $\LL(1)$-анализатор для грамматики $\mathsf{Expr}$ из предыдущего задания. Продемонстрируйте его работу на слове $id+id\times id$ и, в случае успеха, постройте дерево разбора по результатам работы аналтзатора.

\begin{comment}
	

\prp Построить детерминированный левый анализатор для грамматики
\setcounter{equation}{0}
\begin{align}
	S &\to 0S\\
	S &\to 1S\\
	S &\to \eps
\end{align} 


\prstar Добавим в грамматику $G$ правило $E \to \eps$. Вычислите значение функции $FIRST(E)$.

\end{comment}

\prp Докажите, что грамматика не является $\LL(1)$-грамматикой, но является $\LL(2)$-грамматикой. Вычислите функции $\first_2$ и $\follow_2$ для всех нетерминалов.
\begin{align*}
	S &\to aAaa|bAba\\
	A &\to b|\eps
\end{align*}

\prp Написать для грамматики  эквивалентную $\LL(1)$-грамматику, построить $\LL(1)$-анализатор и продемонстрировать его работу на слове $baab$. 
$$ S \to baaA|babA\qquad A\to \eps|Aa|Ab$$
%\prend

\prp Постройте недетерминированный $\LR(1)$-автомат Кнута для грамматики $S \to aSb \mid a$. Детерминизируйте этот автомат по алгоритму из курса~"--- вы получите детерминированный автомат Кнута, с помощью которого строится управляющая таблица $\LR(1)$-анализатора. При построении автомата Кнута используйте только состояния, достижимые из начального.

\prpstar Докажите, что язык $a^*\cup a^nb^n$ не является $\LL$-языком.



\end{document}

\prp Для грамматики написать эквивалентную $\LL(1)$-грамматику и вычислить функции $\first$ и $\follow$ для каждого нетерминала. Постройте по получившейся грамматике $\LL(1)$-анализатор.
\begin{align*}
	S &\to ba|A\\
	A &\to a|Aab|Ab
\end{align*}