\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



\def\xquad{\noindent\phantom{X}\quad}


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


\def\RExpr{\mathsf{RExpr}}

\def\attr{\mathsf{attr}}
\def\val{\mathsf{val}}
\def\ord{\mathsf{ord}}

\def\firstpos{\mathsf{firstpos}}
\def\lastpos{\mathsf{lastpos}}
\def\nullable{\mathsf{nullable}}
\def\followpos{\mathsf{followpos}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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 обсуждаемы в качестве бонусных на зачёте.

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

\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$~"--- \emph{аванцепочка}~"--- слово длины не больше $k$ (параметр $\LR(k)$ анализатора) над алфавитом $\Sigma\cup\{\$\}$ (возможно пустое), а <<$\cdot$>>~"--- вспомогательный символ, \emph{курсор}, который встречается ровно один раз.

Определим недетерминированный $\LR(k)$-автомат Кнута для грамматики $G$. Множество состояний автомата~"--- $\LR(k)$-ситуации грамматики $G$. Начальное состояние автомата~"--- ситуация\footnote{Эта ситуация и ещё одна $[S^\prime \to S \cdot, \$ ]$ формально не удовлетворяет определению выше; мы выделяем их в особый случай, что бы не тратить на обсуждение этого технического момента много времени.} $[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] $$

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

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

%$S \to aSb \mid a$.


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


\upr Постройте $\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 Грамматика $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$, анализатор отвергает.

\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$.


\begin{comment}
S -> Ab
A -> aAa
A -> B
B -> b
\end{comment}


\prend


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

\prend

\prp На рис.~\ref{fig:LRaut} приведен автомат $\LR(1)$-анализатора (запись $A \to$ обозначает правило $A \to \eps$).
\begin{figure}
 \centerline{\includegraphics[width=300px]{LR4.png}}
 \caption{автомат $\LR(1)$-анализатора}\label{fig:LRaut}
\end{figure}
В приведенной ниже конфигурации $\LR$-анализатора  в первой компоненте (содержимом магазина) опущены состояния автомата. В процессе разбора строки $z\in L(G)$ автомат оказался в конфигурации $\langle c F * F W, + a + a \rangle$. Требуется:

\prsub	Восстановить состояния автомата в содержимом магазина.

\prsub	Восстановить какую-либо из возможных строк $z\in L(G)$, разбор которой мог привести к этой конфигурации.

\prsub	Продемонстрировать процесс разбора на этой строке. Решение обоснуйте.

\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

\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

\end{comment}

\prp Грамматика $\RExpr = \langle \{E,T\}, \{a, b, +, {}^*, (, ) \}, P, E \rangle$ имеет множество правил $P:$  
$$ E \to  T+E \mid TE \mid T \qquad T \to (E) \mid T^* \mid a \mid b $$ 
и порождает регулярные выражения над алфавитом $\{a,b\}$.

%E -> T+E | TE |  T  
%T -> (E) |  T* | a | b




\prsub Постройте для грамматики $\RExpr$ $\LR(1)$-анализатор\footnote{Анализатор для этой грамматики довольно громоздкий. Постройте его с помощью программы, например на сайте \url{http://lrk.umeta.ru}, используйте программу для выполнения последующих пунктов.}.

\prsub Дополните грамматику $\RExpr$ до атрибутной так, чтобы она вычисляла атрибуты $\firstpos, \lastpos$ и $\nullable$ согласно алгоритму их вычисления при построении ДКА по РВ. Считайте атрибуты $\firstpos$, $\lastpos$ и $\nullable$ у терминалов заданными: на практике перед вычислением атрибутов происходит препроцессинг, во время которого могут быть заданы атрибуты терминалов, если это требуется.

\smallskip
\noindent\underline{{Указание}}. Вычисление атрибута нужно определять через функцию, которую можно описать на языке программирования или псевдокоде. Пример вычисления атрибута $\nullable$ для правила $E_0 \to T+E_1$:
%$$  \quad  =  $$

\medskip
\noindent$E_0[\nullable] = $ \textbf{function}( $T[\nullable]$, $E_1[\nullable]$)\{\\
\xquad	\textbf{if}( $T[\nullable]$ \textbf{or} $E_1[\nullable]$)\{\\
\xquad\quad		\textbf{return} \textsf{True};\\
\xquad	\}\,\textbf{else}\{ \textbf{return} \textsf{False}; \} \\
\}

\prsubstar Добавьте в атрибутную схему вычисление атрибута $\followpos$.

\prsub С помощью анализатора постройте дерево разбора для РВ~$(a+ab)^*+ab^*$ и вычислите атрибуты $\firstpos, \lastpos$, $\nullable$ (*$\followpos$) согласно атрибутной схеме (предварительно задав атрибуты у терминалов).

\begin{comment}
	\begin{algorithm}[H]%algorithm2e
		$E[\nullable] = $ \textbf{function}( $T_1[\nullable]$, $T_2[\nullable]$)\{
		
		
		\}
		\end{algorithm}	
\end{comment}

%\vspace{-1ex}
%$$ E \to TE^\prime;\quad E^\prime \to +TE^\prime \mid \eps;\quad T \to FT^\prime;$$ 
%\vspace{-3ex}
%$$ T^\prime \to \times FT^\prime \mid \eps;\qquad F \to (E) \mid \id.  $$

\prend



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

