\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}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Enumerations  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Rnum}[1]{\expandafter{\romannumeral #1\relax}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}


%%%%%%%%%%%%%%  Fancy underline & comments %%%%%%%%%%%%%%%%
\usepackage[normalem]{ulem}
\usepackage{color} 
\usepackage{xcolor}

\usepackage{enumerate}

\usepackage{marginnote}

\newcommand{\malert}[2][]{\marginpar{\color{WildStrawberry}\ifthenelse{\equal{#1}{}}{\vspace{-2ex}}{\vspace{-2ex}\vspace{#1}}  #2}}
\definecolor{DarkGray}{HTML}{666666}
\newcommand{\mcomment}[2][]{\marginpar{\ifthenelse{\equal{#1}{}}{\vspace{-2ex}}{\vspace{-2ex}\vspace{#1}} \color{DarkGray} #2}}
\newcommand\reduline{\bgroup\markoverwith
      {\textcolor{red}{\rule[-0.5ex]{2pt}{0.4pt}}}\ULon}

\usepackage{dashrule}

\newcommand\alertuline{\bgroup\markoverwith
      {\color{WildStrawberry}{\hdashrule[-0.5ex]{2pt}{0.4pt}{1pt}}}\ULon}

\newcommand\commentuline{\bgroup\markoverwith
			      {\color{DarkGray}{\hdashrule[-0.5ex]{2pt}{0.4pt}{1pt}}}\ULon}


\newcommand\reddasheduline{\useunder{\uuline}{\bfseries}{\textbf}}

\newcommand{\acomment}[1]{
	\bigskip
	\centerline{\framebox{
	\begin{minipage}{13cm}
		\begin{center}
			\emph{
					#1
			}
		\end{center} 
	\end{minipage}
	}}
	\bigskip
}

%%%%%% Shortcuts %%%%%

\let\rpar\reversemarginpar
\let\aul\alertuline
\let\cul\commentuline


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\newcounter{prvar}


\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\prpvar{\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;({\rm\Rnum{\theprvar}}).  }\setcounter{subproblem}{0} }
\def\prpv{\medskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0} }
\def\prv{\medskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}. \setcounter{subproblem}{0} }

\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\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}{\sf \thesubproblem .} }
\def\prsubr{\medskip\noindent\stepcounter{subproblem}{\sf \thesubproblem)} }
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{$\mathsf{\thesubproblem^*}$\negthickspace.  } }
\def\prsubrstar{\medskip\noindent\stepcounter{subproblem}{\sf $\mathsf{\thesubproblem^*}$)  } }

\newcommand{\bracketspace}[1]{\phantom{(}\!\!{#1}\!\!\phantom{)}}

\DeclareDocumentCommand{\Prpvar}{ O{null} O{} }{
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem 
% 	\ifthenelse{\equal{#1}{null}}{  }{ {\sf $\bm\langle$\bracketspace{#1}$\bm\rangle$}}
%	~\!\!(\bracketspace{{\rm\Rnum{\theprvar}}}).  }\setcounter{subproblem}{0} 
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0} 
%
	\,{\sf $\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}}.

}
%\DeclareDocumentCommand{\Prpvar}{ O{level} O{meta} m }{\prpvar}


\DeclareDocumentCommand{\Prp}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача \theproblem 
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}
%\DeclareDocumentCommand{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^* $
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}

\DeclareDocumentCommand{\Prpd}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^\dagger$ 
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}


\def\prend{
	\bigskip
	\bigskip
}



\def\quotient{\backslash\negthickspace\sim}
\begin{document}
\centerline{\LARGE Задание 12}
 
\medskip

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

\bigskip

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

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


\textbf{Это задание, которое не требуется сдавать на проверку!} %На семинаре я расскажу о том как строить LL и LR таблицы в \TeX с помощью специальной программы, поэтому при желании можете отправить это задание в качестве бонусного. Основными для обсуждения в качестве бонусных будут задачи на автомат Кнута. %Задачи 4-6 обсуждаемы в качестве бонусных на зачёте.

Для самопроверки используйте онлайн-конструктор анализаторов (см. описание на сайте).

\section{$\LR(0)$-анализаторы}

Параметр $k$ в $\LR(k)$ анализаторах~"--- число предпросматриваемых символов, по которым анализатор принимает решение какое из действий <<сдвиг>> или <<свёртка>> совершить на текущем такте. На первый взгляд может показаться, что $k\geq 1$, однако существуют и $\LR(0)$-анализаторы. $\LR(0)$-анализатор принимает решение не зная какой символ находится на входной ленте. Как же такое возможно?

Принимать решение без предпросмотра возможно, поскольку не смотря на независимость решений для произвольного символа, переходы между состояниями $\LR(0)$-автомата Кнута по-прежнему зависят от символа помещённого в стек. В управляющей таблице $\LR(0)$-анализатора каждому состоянию соответствует ровно одно действие (независимо от символа входа). В остальном, $\LR(0)$-анализаторы не отличаются от $\LR(1)$-анализаторов, изученных на семинаре.

$\LR(0)$-анализатор принимает слово, если оказался в конфигурации $(I_0SI_1,\$, p_np_{n-1}\ldots p_n)$, где $p_i$~"--- номер правила, а состоянию $I_1$ соответствует действие \textbf{Accept}.


\prp Постройте $\LR(0)$-анализатор для грамматики $S \to aSb\mid b$. Продемонстрируйте работу анализатора ан слове $aabbb$ и постройте по результатам работы дерево разбора.
Если затрудняетесь, то воспользуйтесь конструктором анализаторов.

\bigskip

Как понять, является ли грамматика $\LR(0)$- или $\LR(1)$-грамматикой? (точнее, какое из чисел $0$ или $1$ является минимальным $k$). Есть критерий $\LR(k)$-грамматик, записанный, например, в книге Ахо и Ульмана, но он достаточно сложный и мы не будем приводить его здесь. Мы приведём следующий рецепт.

Постройте $\LR(1)$-анализатор и если в управляющей таблице некоторому состоянию $I_m$, в зависимости от символа, соответствуют два разных правила свёртки (в том числе и \textbf{Accept}) или для по одному символу должна быть операция сдвиг, а по другому~"--- свёртка, то это заведомо не $\LR(0)$-грамматика. Действительно, состояния $\LR(0)$-автомата Кнута отличаются от состояний $\LR(1)$-автомата Кнута только в следующем. Каждому состоянию $\LR(1)$-автомата соответствует состояние $\LR(0)$-автомата; последнее содержит ситуацию\footnote{Мы опускаем аванцепочку в $\LR(0)$-ситуациях, поскольку её длина ноль.} $[A \to \alpha \cdot X \beta ]$ тогда и только тогда, когда в первом есть ситуация вида $[A \to \alpha \cdot X \beta, u]$. Это свойство легко вытекает из процедуры детерминизации. Таким образом, если в некотором состоянии $\LR(1)$-автомата есть две разных операции (по разным символам), то при построении $\LR(0)$-анализатора, в некотором состоянии (множестве ситуаций) потребуется совершить две разных операции.
	

\section{Задачи}

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




\prp Язык $L$ задан неоднозначной КС-грамматикой $$G =  \{  \{ S \} ,  \{ (, ) \} ,  \{ S  \to  (S)  \mid  SS  \mid  () \} , S \}.$$ Написать $\LL(1)-$грамматику для языка $L$.
\prend

\prp	Дана грамматика $G =  \{\;  \{ A, S \} ,\;  \{ a, b, c \} ,\;  \{\; S  \to  Aa  \mid  b  \mid   \eps ;\; A  \to  Ab  \mid  c \;\} ,\; S\; \}$. Является ли грамматика $G$ $\LR(k)-$грамматикой? При положительном ответе на вопрос найти минимальное $k$ и построить соответствующий анализатор. Построить дерево разбора для цепочки $cbba$.

\prend

\prp Дана грамматика $G = \{\;  \{ A, S \} ,\;  \{ a \} ,\;  \{\; S  \to  A;\;$\linebreak $ A  \to  aAa  \mid  a\; \} ,\; S \}$. Является ли грамматика $G$ $\LR(k)-$грамматикой? При положительном ответе на вопрос найти минимальное $k$ и построить соответствующий анализатор. Построить дерево разбора для цепочки $aaaaa$.
\prend


\prp Дана грамматика $G =  \{\;  \{ A,S \} ,\;  \{ a, b, c \} ,\;  \{ S \to Aa\mid b;\; $\linebreak $A \to Ab\mid c\; \} ,\; S\; \}$ . Является ли грамматика $G$ $\LR(k)-$грамматикой? При положительном ответе на вопрос найти минимальное $k$ и построить соответствующий анализатор. Продемонстрировать работу анализатора на цепочке $cbbab$.

\prend



\begin{comment}
	



\prp Зафиксируем КС-грамматику $G$ и рассмотрим множество её $\LR(0)$-ситуаций. Будем говорить, что между двумя ситуациями $\alpha.X\beta$ и $\alpha X.\beta$ определён переход по $X\in N\cup T$.
Конечный автомат, в качестве состояний которого выступают $\LR(0)$-ситуации, а переходы определены по правилу, указанному выше, называют $\LR(0)$-автоматом или автоматом Кнута.

\prsub Выпишите все $\LR(0)$-ситуации для грамматики $G$, заданной правилами $S\to aS\mid b$.  

\prsub Постройте автомат Кнута для грамматики $G$.

\prsub Постройте $\LR(0)$-анализатор для грамматики $G$. Сравните автомат Кнута с таблицей переходов $\LR(0)$-анализатора для грамматики $G$.

\prend

\prp Грамматика $G$ задана правилами  $$S\to Ab,\quad
A\to aAa,\quad
A\to B,\quad
B\to b.$$ 

\prsub Построить $\LR(1)$ и $\LR(0)$-анализаторы для грамматики $G$ по алгоритму из курса. 


\prsub Постройте $\LR(0)$-анализатор по $\LR(1)$-анализатору из пункта {\sf 1} следующим образом. Сотрите все аванцепочки и постройте управляющую таблицу $\LR(0)$-анализатора по получившемуся автомату Кнута. Верно ли, что полученный $\LR(0)$-анализатор является аналиазтором для грамматики $G$? То есть для любого слова, порождаемого $G$, анализатор строит корректный правый разбор, а слова не порождаемые $G$, анализатор отвергает.

%\prsub Верно ли, что при стирании аванцепочек в таблицах для $\LR(1)$-анализатора и (соответствующего перестроения управляющей таблицы), получается анализатор, \aul{эквивалентный}\malert{Хорошо бы дать удачное определение эквивалентности.} построенному $\LR(0)$-анализатору?

\prsub Покажите, что $\LR(0)$-анализатор для грамматики $G$ из пункта {\sf 1} можно построить путём применения следующей процедуры, схожей с процедурой минимизации ДКА, к $\LR(0)$-автомату, полученному из\linebreak $\LR(1)$-анализатора в пункте {\sf 2}. 

В случае минимизации $\LR(0)$-автомата, все состояния с операциями свёртки оказываются на первом шаге в разных группах (разных ящиках), если свёртки происходят по разным правилам; состояния с операциями сдвига находятся в одном ящике. Далее процедура минимизации $\LR(0)$-автомата не отличается от процедуры минимизации ДКА.
\prend

\end{comment}




\subsection{Контрольные вопросы}

\prp При построении $\LR(1)-$анализатора для грамматики $G$ в одном множестве оказались ситуации $[A \to .aA\alpha,b]$ и $[B \to \beta.a,a]$, где $\alpha, \beta $ некоторые цепочки из $ (N\cup T)^*$. Может ли грамматика $G$ быть $\LR(0)$-грамматикой?



\end{document}

