1153 lines
71 KiB
TeX
1153 lines
71 KiB
TeX
\documentclass[a4paper, final]{article}
|
||
%\usepackage{literat} % Нормальные шрифты
|
||
\usepackage[14pt]{extsizes} % для того чтобы задать нестандартный 14-ый размер шрифта
|
||
\usepackage{tabularx}
|
||
\usepackage[T2A]{fontenc}
|
||
\usepackage[utf8]{inputenc}
|
||
\usepackage[russian]{babel}
|
||
\usepackage{amsmath}
|
||
\usepackage[left=25mm, top=20mm, right=20mm, bottom=20mm, footskip=10mm]{geometry}
|
||
\usepackage{ragged2e} %для растягивания по ширине
|
||
\usepackage{setspace} %для межстрочно го интервала
|
||
\usepackage{moreverb} %для работы с листингами
|
||
\usepackage{indentfirst} % для абзацного отступа
|
||
\usepackage{moreverb} %для печати в листинге исходного кода программ
|
||
\usepackage{pdfpages} %для вставки других pdf файлов
|
||
\usepackage{tikz}
|
||
\usepackage{graphicx}
|
||
\usepackage{afterpage}
|
||
\usepackage{longtable}
|
||
\usepackage{float}
|
||
|
||
|
||
|
||
% \usepackage[paper=A4,DIV=12]{typearea}
|
||
\usepackage{pdflscape}
|
||
% \usepackage{lscape}
|
||
|
||
\usepackage{array}
|
||
\usepackage{multirow}
|
||
|
||
\renewcommand\verbatimtabsize{4\relax}
|
||
\renewcommand\listingoffset{0.2em} %отступ от номеров строк в листинге
|
||
\renewcommand{\arraystretch}{1.4} % изменяю высоту строки в таблице
|
||
\usepackage[font=small, singlelinecheck=false, justification=centering, format=plain, labelsep=period]{caption} %для настройки заголовка таблицы
|
||
\usepackage{listings} %листинги
|
||
\usepackage{xcolor} % цвета
|
||
\usepackage{hyperref}% для гиперссылок
|
||
\usepackage{enumitem} %для перечислений
|
||
\usepackage{latexsym} %для символа \leadsto
|
||
|
||
\newcommand{\specialcell}[2][l]{\begin{tabular}[#1]{@{}l@{}}#2\end{tabular}}
|
||
|
||
|
||
\setlist[enumerate,itemize]{leftmargin=1.2cm} %отступ в перечислениях
|
||
|
||
\hypersetup{colorlinks,
|
||
allcolors=[RGB]{010 090 200}} %красивые гиперссылки (не красные)
|
||
|
||
% подгружаемые языки — подробнее в документации listings (это всё для листингов)
|
||
\lstloadlanguages{ SQL}
|
||
% включаем кириллицу и добавляем кое−какие опции
|
||
\lstset{tabsize=2,
|
||
breaklines,
|
||
basicstyle=\footnotesize,
|
||
columns=fullflexible,
|
||
flexiblecolumns,
|
||
numbers=left,
|
||
numberstyle={\footnotesize},
|
||
keywordstyle=\color{blue},
|
||
inputencoding=cp1251,
|
||
extendedchars=true
|
||
}
|
||
\lstdefinelanguage{MyC}{
|
||
language=SQL,
|
||
% ndkeywordstyle=\color{darkgray}\bfseries,
|
||
% identifierstyle=\color{black},
|
||
% morecomment=[n]{/**}{*/},
|
||
% commentstyle=\color{blue}\ttfamily,
|
||
% stringstyle=\color{red}\ttfamily,
|
||
% morestring=[b]",
|
||
% showstringspaces=false,
|
||
% morecomment=[l][\color{gray}]{//},
|
||
keepspaces=true,
|
||
escapechar=\%,
|
||
texcl=true
|
||
}
|
||
|
||
\textheight=24cm % высота текста
|
||
\textwidth=16cm % ширина текста
|
||
\oddsidemargin=0pt % отступ от левого края
|
||
\topmargin=-1.5cm % отступ от верхнего края
|
||
\parindent=24pt % абзацный отступ
|
||
\parskip=5pt % интервал между абзацами
|
||
\tolerance=2000 % терпимость к "жидким" строкам
|
||
\flushbottom % выравнивание высоты страниц
|
||
|
||
|
||
% Настройка листингов
|
||
\lstset{
|
||
language=python,
|
||
extendedchars=\true,
|
||
inputencoding=utf8,
|
||
keepspaces=true,
|
||
% captionpos=b, % подписи листингов снизу
|
||
}
|
||
|
||
\begin{document} % начало документа
|
||
|
||
|
||
|
||
% НАЧАЛО ТИТУЛЬНОГО ЛИСТА
|
||
\begin{center}
|
||
\hfill \break
|
||
\hfill \break
|
||
\normalsize{МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ\\
|
||
федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский политехнический университет Петра Великого»\\[10pt]}
|
||
\normalsize{Институт компьютерных наук и кибербезопасности}\\[10pt]
|
||
\normalsize{Высшая школа технологий искусственного интеллекта}\\[10pt]
|
||
\normalsize{Направление: 02.03.01 <<Математика и компьютерные науки>>}\\
|
||
|
||
\hfill \break
|
||
\hfill \break
|
||
\hfill \break
|
||
\hfill \break
|
||
\large{Лабораторная работа №5}\\
|
||
\large{<<Реализация LL(1)-анализатора>>}\\
|
||
\large{по дисциплине}\\
|
||
\large{<<Математическая логика и теория автоматов>>}\\
|
||
\large{Вариант 15}\\
|
||
|
||
% \hfill \break
|
||
\hfill \break
|
||
\end{center}
|
||
|
||
\small{
|
||
\begin{tabular}{lrrl}
|
||
\!\!\!Студент, & \hspace{2cm} & & \\
|
||
\!\!\!группы 5130201/20102 & \hspace{2cm} & \underline{\hspace{3cm}} &Тищенко А. А. \\\\
|
||
\!\!\!Преподаватель & \hspace{2cm} & \underline{\hspace{3cm}} & Востров А. В. \\\\
|
||
&&\hspace{4cm}
|
||
\end{tabular}
|
||
\begin{flushright}
|
||
<<\underline{\hspace{1cm}}>>\underline{\hspace{2.5cm}} 2025г.
|
||
\end{flushright}
|
||
}
|
||
|
||
\hfill \break
|
||
% \hfill \break
|
||
\begin{center} \small{Санкт-Петербург, 2025} \end{center}
|
||
\thispagestyle{empty} % выключаем отображение номера для этой страницы
|
||
|
||
% КОНЕЦ ТИТУЛЬНОГО ЛИСТА
|
||
\newpage
|
||
|
||
\tableofcontents
|
||
|
||
|
||
\newpage
|
||
|
||
\section*{Введение}
|
||
\addcontentsline{toc}{section}{Введение}
|
||
Лабораторная №5 заключается в следующем. Для заданной вариантом грамматики необходимо:
|
||
\begin{itemize}
|
||
\item Построить множества FIRST и FOLLOW для каждого нетерминала.
|
||
\item Построить таблицу выбора (lookup table).
|
||
\item Реализовать детерминированный левый анализатор (проверка принадлежности цепочки грамматике).
|
||
\item Назначить семантические действия части заданных продукций (например, генерация машинноориентированного кода).
|
||
\end{itemize}
|
||
|
||
\textit{Исходная грамматика в варианте 15 состояла из следующих продукций}:
|
||
\vspace{-0.3cm}
|
||
\begin{verbatim}
|
||
S -> B A b
|
||
A -> a A B C | b B | a
|
||
B -> b
|
||
C -> c A
|
||
\end{verbatim}
|
||
|
||
Однако, как будет показано в разделе математического описания, данная грамматика не является LL(1)-грамматикой из-за неоднозначности в выборе продукций для нетерминала $A$. Поэтому в работе используется модифицированная версия грамматики с удаленной продукцией $A \rightarrow a$.
|
||
|
||
|
||
\newpage
|
||
\section {Математическое описание}
|
||
\subsection{Анализ исходной грамматики и её модификация}
|
||
|
||
Исходная грамматика варианта 15 содержала следующие продукции:
|
||
\vspace{-0.3cm}
|
||
\begin{verbatim}
|
||
S -> B A b
|
||
A -> a A B C | b B | a
|
||
B -> b
|
||
C -> c A
|
||
\end{verbatim}
|
||
|
||
При попытке построения LL(1)-анализатора для данной грамматики обнаруживается неоднозначность в таблице синтаксического анализа. Конкретно, при рассмотрении нетерминала $A$ и входного терминала $a$ возникает конфликт между двумя продукциями:
|
||
\begin{itemize}
|
||
\item $A \rightarrow a$
|
||
\item $A \rightarrow a A B C$
|
||
\end{itemize}
|
||
|
||
Обе продукции начинаются с терминала $a$, что означает, что $a \in \texttt{FIRST}(a)$ и $a \in \texttt{FIRST}(a A B C)$. Следовательно, анализатор не может однозначно определить, какую продукцию применить при встрече символа $a$ на входе и нетерминала $A$ на вершине стека.
|
||
|
||
Для получения корректной LL(1)-грамматики была выполнена модификация: удалена продукция $A \rightarrow a$. Таким образом, итоговая грамматика, используемая в данной работе, имеет вид:
|
||
\vspace{-0.3cm}
|
||
\begin{verbatim}
|
||
S -> B A b
|
||
A -> a A B C | b B
|
||
B -> b
|
||
C -> c A
|
||
\end{verbatim}
|
||
|
||
Данная модификация устраняет неоднозначность и позволяет построить корректную таблицу синтаксического анализа для LL(1)-анализатора. Язык, порождаемый модифицированной грамматикой, остается достаточно выразительным для демонстрации принципов работы LL(1)-анализатора.
|
||
|
||
\subsection{Иерархия грамматик Хомского}
|
||
Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. На Рис.~\ref{fig:homsky} представлены все четыре типа грамматик (по типу продукций, из которых они состоят) и отношения между ними.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.8\linewidth]{img/homsky.png}
|
||
\caption{Иерархия грамматик Хомского}
|
||
\label{fig:homsky}
|
||
\end{figure}
|
||
|
||
Любая автоматная грамматика является контекстно-свободной, любая контекстно-свободная грамматика является контекстно-зависимой, любая контекстно-зависимая грамматика является неограниченной.
|
||
|
||
\subsection{Контекстно-свободные грамматики}
|
||
|
||
Контекстно-свободные грамматики являются частным случаем формальных грамматик, в которых левые части всех продукций содержат только один нетерминальный символ. Это означает, что все продукции имеют вид $A \rightarrow \beta$, где $A$ — нетерминальный символ, а $\beta$ — произвольная цепочка терминалов и нетерминалов.
|
||
|
||
Модифицированная грамматика этого варианта лабораторной работы задаётся в виде следующего списка продукций:
|
||
\begin{verbatim}
|
||
S -> B A b
|
||
A -> a A B C | b B
|
||
B -> b
|
||
C -> c A
|
||
\end{verbatim}
|
||
|
||
Она, очевидно, является контекстно-свободной, так как в левых частях всех продукций присутствует только один нетерминальный символ. Также можно сразу заметить, что грамматика не является автоматной, так как в списке есть продукции, в правых частях которых присутствуют несколько нетерминалов.
|
||
|
||
Язык, порождаемый грамматикой, очевидно, не сложнее контекстно-свободного. Также, по продукции \texttt{A -> a A B C}, можно сделать вывод, что язык не является автоматным. Эта продукция является рекурсивной и порождает вложенную структуру, которая не может быть описана конечным автоматом.
|
||
|
||
Пример дерева вывода для цепочки языка, порождаемого грамматикой, представлен на Рис.~\ref{fig:tree}.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/tree.png}
|
||
\caption{Дерево вывода для цепочки $b a b b b c b b b$.}
|
||
\label{fig:tree}
|
||
\end{figure}
|
||
|
||
|
||
\subsection{LL(k)-анализаторы и LL(k)-грамматики}
|
||
|
||
Синтаксический LL-анализатор -- это нисходящий синтаксический анализатор для некоторого подмножества контекстно-свободных грамматик, известных как LL-грамматики. При этом не все контекстно-свободные грамматики являются LL-грамматиками.
|
||
|
||
Буквы L в выражении «LL-анализатор» означают, что входная строка анализируется слева направо (left to right), и при этом строится её левосторонний вывод (leftmost derivation).
|
||
|
||
LL-анализатор называется LL(k)-анализатором, если данный анализатор использует предпросмотр на k токенов (лексем) при разборе входного потока. Грамматика, которая может быть распознана LL(k)-анализатором без возвратов к предыдущим символам, называется LL(k)-грамматикой. Язык, который может быть представлен в виде LL(k)-грамматики, называется LL(k)-языком.
|
||
|
||
Как будет показано далее, грамматика, рассматриваемая в этом варианте лабораторной работы является LL(1)-грамматикой, так как для неё можно однозначно заполнить таблицу LL(1) синтаксического анализа. Это означает, что для распознавания любой цепочки грамматики, анализатору достаточно просматривать входной поток только на один символ вперёд для принятия решения о том, какое правило грамматики необходимо применить.
|
||
|
||
|
||
\subsection{Алгоритм построения LL(1) таблицы синтаксического анализа}
|
||
Чтобы заполнить таблицу синтаксического анализа, необходимо установить, какое правило грамматики синтаксический анализатор должен выбрать, если нетерминальное $A$ находится на вершине его стека и символ $a$ — во входном потоке. Легко заметить, что такое правило должно иметь форму $A \rightarrow w$ и что у языка, соответствующего $w$, должна быть по крайней мере одна строка, начинающаяся с $a$.
|
||
|
||
С этой целью мы определяем \textbf{множество \texttt{FIRST()} для $w$}, обозначенное как $\texttt{FIRST}(w)$, как множество терминалов, которые могут быть найдены в начале любой строки в $w$, и $\varepsilon$, если пустая строка также принадлежит $w$.
|
||
|
||
Учитывая грамматику с правилами $A_1 \rightarrow w_1, \dots, A_n \rightarrow w_n$, можно вычислить $\texttt{FIRST}(w_i)$ и $\texttt{FIRST}(A_i)$ для каждого правила следующим образом:
|
||
|
||
\begin{enumerate}
|
||
\item Инициализировать каждое множество $\texttt{FIRST}(A_i)$ пустым множеством.
|
||
\item Добавить $\texttt{FIRST}(w_i)$ к $\texttt{FIRST}(A_i)$ для каждого правила $A_i \rightarrow w_i$, где $\texttt{FIRST}(w_i)$ определяется следующим образом:
|
||
\begin{itemize}
|
||
\item $\texttt{FIRST}(a w') = \{ a \}$ для каждого терминала $a$
|
||
\item $\texttt{FIRST}(A w') = \texttt{FIRST}(A)$ для каждого нетерминального $A$ с $\varepsilon \notin \texttt{FIRST}(A)$
|
||
\item $\texttt{FIRST}(A w') = \left( \texttt{FIRST}(A) \setminus \{ \varepsilon \} \right) \cup \texttt{FIRST}(w')$ для каждого нетерминального $A$ с $\varepsilon \in \texttt{FIRST}(A)$, включая случай $A_i \rightarrow A$, то есть $w' = \varepsilon$, в этом случае $\texttt{FIRST}(A w') = \texttt{FIRST}(A)$
|
||
\item $\texttt{FIRST}(\varepsilon) = \{ \varepsilon \}$
|
||
\end{itemize}
|
||
\item Повторять шаг 2, пока в множествах $\texttt{FIRST}$ происходят изменения.
|
||
\end{enumerate}
|
||
|
||
Однако множеств \texttt{FIRST()} недостаточно, чтобы построить таблицу синтаксического анализа. Так происходит, потому что правая сторона $w$ правила могла бы в конечном счёте быть приведена к пустой строке. Таким образом синтаксический анализатор должен также использовать правило $A \rightarrow w$, если $\varepsilon \in \texttt{FIRST}(w)$ и во входном потоке символ, который может следовать за $A$. Поэтому также необходимо построить \textbf{множество \texttt{FOLLOW()} для $A$}, которое определяется как множество терминалов $a$, таких что существует строка символов $\alpha A a \beta$, которая может быть получена из начального символа.
|
||
|
||
Вычисление множеств \texttt{FOLLOW()} для нетерминалов в грамматике выполняется следующим образом:
|
||
|
||
\begin{enumerate}
|
||
\item Инициализировать $\texttt{FOLLOW}(S) = \{ \$ \}$, а все остальные множества $\texttt{FOLLOW}(A_i)$ пустыми, где \$ — специальный терминал, служащий для указания конца входной цепочки.
|
||
\item Если есть правило формы $A_j \rightarrow w A_i w'$, тогда:
|
||
\begin{itemize}
|
||
\item Если терминал $a \in \texttt{FIRST}(w')$, то добавить $a$ в $\texttt{FOLLOW}(A_i)$
|
||
\item Если $\varepsilon \in \texttt{FIRST}(w')$, то добавить $\texttt{FOLLOW}(A_j)$ в $\texttt{FOLLOW}(A_i)$
|
||
\item Если $w'$ имеет длину 0, то добавить $\texttt{FOLLOW}(A_j)$ в $\texttt{FOLLOW}(A_i)$
|
||
\end{itemize}
|
||
\item Повторять шаг 2, пока в множествах \texttt{FOLLOW()} происходят изменения.
|
||
\end{enumerate}
|
||
|
||
Теперь можно точно определить, какие правила будут содержаться в таблице синтаксического анализа. Если $T[A, a]$ обозначает ячейку в таблице для нетерминального $A$ и терминала $a$, то:
|
||
|
||
\begin{itemize}
|
||
\item $T[A,a]$ содержит правило $A \rightarrow w$ тогда и только тогда, когда:
|
||
\begin{itemize}
|
||
\item $a \in \texttt{FIRST}(w)$ при проходе правила $A \rightarrow w$, или
|
||
\item $\varepsilon \in \texttt{FIRST}(w)$ и $a \in \texttt{FOLLOW}(A)$
|
||
\end{itemize}
|
||
\end{itemize}
|
||
|
||
Если таблица будет содержать не более одного правила в каждой ячейке, то синтаксический анализатор сможет однозначно определить, какое правило необходимо применить на каждом шаге разбора. В этом случае грамматику является \textbf{LL(1)} грамматикой.
|
||
|
||
\subsection{Множества FIRST и FOLLOW для заданной грамматики}
|
||
|
||
Приведём множества FIRST и FOLLOW для всех нетерминалов заданной грамматики.
|
||
|
||
Множества FIRST:
|
||
\vspace{-0.3cm}
|
||
\begin{verbatim}
|
||
FIRST(S) = {b}
|
||
FIRST(A) = {a, b}
|
||
FIRST(B) = {b}
|
||
FIRST(C) = {c}
|
||
\end{verbatim}
|
||
|
||
Множества FOLLOW:
|
||
\vspace{-0.3cm}
|
||
\begin{verbatim}
|
||
FOLLOW(S) = {$}
|
||
FOLLOW(A) = {b}
|
||
FOLLOW(B) = {a, b, c}
|
||
FOLLOW(C) = {b}
|
||
\end{verbatim}
|
||
|
||
\subsection{Таблица синтаксического анализа для заданной грамматики}
|
||
|
||
Таблица синтаксического анализа для заданной грамматики представлена в таблице~\ref{tab:syntax_analysis}.
|
||
|
||
\begin{table}[h!]
|
||
\centering
|
||
\caption{Таблица синтаксического анализа для заданной грамматики.}
|
||
\footnotesize
|
||
\begin{tabular}{|c|c|c|c|c|}
|
||
\hline
|
||
& \textbf{a} & \textbf{b} & \textbf{c} & \textbf{\$} \\
|
||
\hline
|
||
S & - & B A b & - & - \\
|
||
A & a A B C & b B & - & - \\
|
||
B & - & b & - & - \\
|
||
C & - & - & c A & - \\
|
||
\hline
|
||
\end{tabular}
|
||
\label{tab:syntax_analysis}
|
||
\end{table}
|
||
|
||
Если при распознавании цепочки синтаксический анализатор встречает ячейку с прочерком, то это означает, что входная цепочка не принадлежит языку, порождаемому грамматикой. В таком случае синтаксический анализатор завершает работу и возвращает сообщение об ошибке.
|
||
|
||
\subsection{Алгоритм разбора предложений}
|
||
|
||
Перед запуском алгоритма разбора в стек помещаются два символа:
|
||
\begin{itemize}
|
||
\item Специальный символ~\$ — признак конца входной цепочки.
|
||
\item Начальный символ грамматики (на вершину стека).
|
||
\end{itemize}
|
||
|
||
Cинтаксический анализатор выполняет три различных вида действий в зависимости от того, находится ли на вершине стека нетерминал, терминал или специальный символ~\$.
|
||
|
||
\begin{enumerate}
|
||
\item \textbf{Если на вершине стека — нетерминал}, то в таблице синтаксического анализа ищется правило грамматики, находящееся на пересечении строки и столбца, соответствующих этому нетерминалу на вершине стека и текущему входному символу. Если же в указанной ячейке таблицы правило отсутствует — синтаксический анализатор останавливается и сообщает об ошибке.
|
||
|
||
\item \textbf{Если на вершине стека — терминал}, то синтаксический анализатор сравнивает его с текущим входным символом. Если они равны, то входной символ считывается, а соответствующий символ из вершины стека — удаляется.
|
||
|
||
\item \textbf{Если на вершине стека — специальный символ~\$}, и текущий символ на ленте также равен~\$, то синтаксический анализатор сообщает об успешном распознавании цепочки. В противном случае — сообщает об ошибке. В обоих случаях происходит останов анализатора.
|
||
\end{enumerate}
|
||
|
||
Эти шаги повторяются до тех пор, пока не произойдёт останов. После останова мы получаем либо сообщение об ошибке, либо сообщение об успешном распознавании цепочки.
|
||
|
||
\subsection{Алгоритм генерации цепочек}
|
||
|
||
Генерация цепочек происходит следующим образом:
|
||
\begin{enumerate}
|
||
\item В список помещается начальный символ грамматики.
|
||
\item Осуществляется проход по списку. Первый встреченный нетерминал заменяется на его случайно выбранную продукцию, после чего проход начинается заново.
|
||
\item Алгоритм завершается, когда в списке не осталось нетерминалов.
|
||
\end{enumerate}
|
||
|
||
Этот алгоритм не позволяет контролировать длину предложения. Также алгоритм может не сходиться в общем случае. Но вероятность того, что алгоритм попадет в петлю убывает геометрически с ростом длины цепочки, так что на практике этот метод работает.
|
||
|
||
\subsection{Семантические действия}
|
||
|
||
Каждой продукции можно сопоставить некоторое семантическое действие, которое будет выполняться при применении этой продукции, во время распознавания цепочки. Таким образом, можно, например, генерировать машинный код.
|
||
|
||
В данной лабораторной работе в качестве семантических действий решено было использовать генерацию инструкций для Java Virtual Machine. JVM это стековая виртуальная машина, её инструкции изменяют содержимое стека. Примеры инструкций:
|
||
\begin{itemize}
|
||
\item \texttt{iconst\_1} — положить целочисленное значение 1 на вершину стека.
|
||
\item \texttt{isub} — вычесть верхнее целочисленное значение стека из предыдущего и положить результат на вершину стека.
|
||
\item \texttt{iadd} — сложить два верхних целочисленных значения стека и положить результат на вершину стека.
|
||
\end{itemize}
|
||
|
||
При распознавании цепочки можно, например, генерировать инструкции, в результате выполнения которых на вершине стека окажется следующее целочисленное значение:
|
||
$$\#b - 2 \times \#a + 3 \times \#c$$
|
||
|
||
где $\#a$, $\#b$, $\#c$ — это количества вхождений символов $a$, $b$, $c$ в цепочку соответственно.
|
||
|
||
Для этого продукции были сопоставлены со следующими инструкциями:
|
||
\begin{itemize}
|
||
\item $S \rightarrow B A b$ $\leadsto$ \texttt{iconst\_1}
|
||
\item $A \rightarrow a A B C$ $\leadsto$ \texttt{iconst\_2 isub}
|
||
\item $A \rightarrow b B$ $\leadsto$ \texttt{iconst\_1 iadd}
|
||
\item $B \rightarrow b$ $\leadsto$ \texttt{iconst\_3 iadd}
|
||
\item $C \rightarrow c A$ $\leadsto$ \texttt{iconst\_3 iadd}
|
||
\end{itemize}
|
||
|
||
Тогда при левом выводе цепочки \texttt{babbbcbbb}, будет сгенерирована следующая последовательность инструкций:
|
||
\begin{verbatim}
|
||
iconst_1 # [1] - значение на вершине стека
|
||
iconst_1 iadd # [2]
|
||
iconst_2 isub # [0]
|
||
iconst_1 iadd # [1]
|
||
iconst_1 iadd # [2]
|
||
iconst_1 iadd # [3]
|
||
iconst_3 iadd # [6]
|
||
iconst_1 iadd # [7]
|
||
iconst_1 iadd # [8]
|
||
\end{verbatim}
|
||
|
||
Значение на вершине стека в конце выполнения всех инструкций равно 8. Поскольку в цепочке \texttt{babbbcbbb} 7 символов $b$, 1 символ $a$ и 1 символ $c$, то и значение выражения $\#b - 2 \times \#a + 3 \times \#c$ для этой цепочки равно 8.
|
||
|
||
|
||
\newpage
|
||
\section{Особенности реализации}
|
||
|
||
\subsection{Задание правил грамматики}
|
||
|
||
Грамматика задаётся в виде текстового файла, в котором каждая строка соответствует одной продукции. Синтаксис задания продукций соответствует общепринятому, за исключением того, что вместо $\varepsilon$ используется слово <<\texttt{epsilon}>> и любые символы грамматики должны быть разделены пробелами.
|
||
|
||
|
||
\subsection{Класс \texttt{Grammar}}
|
||
|
||
Класс \texttt{Grammar} содержит в себе всю информацию о грамматике, а также методы для работы с ней. Код конструктора класса представлен в листинге \ref{lst:grammar_constructor}. Конструктор класса принимает на вход строку, содержащую описание грамматики и объект типа \texttt{Callable[[int, tuple[str, list[str]]], None]} -- функцию-колбэк, которая будет вызываться при применении продукции. Эта функция должна принимать два аргумента: номер продукции и кортеж, содержащий левую и правую части продукции. Далее конструктор вызывает методы для парсинга продукций, нахождения терминалов, вычисления множеств FIRST и FOLLOW, заполнения таблицы синтаксического анализа.
|
||
|
||
\begin{lstlisting}[caption={Код конструктора класса \texttt{Grammar}.}, label={lst:grammar_constructor}]
|
||
class Grammar:
|
||
EPSILON: str = "epsilon"
|
||
|
||
def __init__(
|
||
self,
|
||
text: str,
|
||
semantic_action: Callable[[int, tuple[str, list[str]]], None] | None = None,
|
||
):
|
||
self.productions: OrderedDict[str, list[list[str]]] = OrderedDict()
|
||
self.start_symbol: str = ""
|
||
self._parse_productions(text)
|
||
|
||
self.terminals: set[str] = set()
|
||
self._find_terminals()
|
||
|
||
self.first_sets: dict[str, set[str]] = {}
|
||
self._calculate_first_sets()
|
||
|
||
self.follow_sets: dict[str, set[str]] = {}
|
||
self._calculate_follow_sets()
|
||
|
||
self.lookup_table: dict[str, dict[str, list[str]]] = {}
|
||
self._fill_lookup_table()
|
||
|
||
# Сопостовляем уникальный номер с каждым правилом
|
||
self.rule_numbers = {}
|
||
rule_idx = 1
|
||
for nt, rules in self.productions.items():
|
||
for rule in rules:
|
||
self.rule_numbers[(nt, tuple(rule))] = rule_idx
|
||
rule_idx += 1
|
||
|
||
# Semantic action callback
|
||
self.semantic_action = semantic_action
|
||
\end{lstlisting}
|
||
|
||
|
||
\subsubsection{Метод \texttt{\_parse\_productions}}
|
||
|
||
Метод \texttt{\_parse\_productions} выполняет разбор текстового описания грамматики и создаёт внутреннее представление продукций. Код метода представлен в листинге~\ref{lst:parse_productions}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar и строку text типа str, содержащую текстовое представление грамматики.
|
||
|
||
Метод не возвращает значений явно, но заполняет словарь productions и устанавливает переменную start\_symbol в объекте класса.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{\_parse\_productions}.}, label={lst:parse_productions}]
|
||
def _parse_productions(self, text: str):
|
||
for line in text.splitlines():
|
||
line = line.strip()
|
||
if not line:
|
||
continue
|
||
|
||
non_terminal, rule = line.split("->")
|
||
if self.start_symbol == "":
|
||
self.start_symbol = non_terminal.strip()
|
||
|
||
non_terminal = non_terminal.strip()
|
||
rules = [
|
||
[
|
||
symbol.strip('"')
|
||
for symbol in re.findall(r"\".*?\"|\S+", rule.strip())
|
||
if symbol.strip('"') != self.EPSILON
|
||
]
|
||
for rule in rule.split("|")
|
||
]
|
||
|
||
if non_terminal not in self.productions:
|
||
self.productions[non_terminal] = []
|
||
|
||
self.productions[non_terminal].extend(rules)
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{\_calculate\_first\_sets}}
|
||
|
||
Метод \texttt{\_calculate\_first\_sets} вычисляет множества FIRST для всех символов грамматики. Код метода представлен в листинге~\ref{lst:calculate_first_sets}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar.
|
||
|
||
Метод не возвращает значений явно, но заполняет словарь first\_sets в объекте класса.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{\_calculate\_first\_sets}.}, label={lst:calculate_first_sets}]
|
||
def _calculate_first_sets(self):
|
||
# Инициализация FIRST для всех символов
|
||
for non_terminal in self.productions:
|
||
self.first_sets[non_terminal] = set()
|
||
|
||
# Для терминалов FIRST содержит только сам терминал
|
||
for terminal in self.terminals:
|
||
self.first_sets[terminal] = {terminal}
|
||
|
||
# Вычисление FIRST для нетерминалов
|
||
changed = True
|
||
while changed:
|
||
changed = False
|
||
for non_terminal, rules in self.productions.items():
|
||
for rule in rules:
|
||
if not rule: # Пустое правило (эпсилон)
|
||
if "" not in self.first_sets[non_terminal]:
|
||
self.first_sets[non_terminal].add("")
|
||
changed = True
|
||
else:
|
||
all_can_derive_epsilon = True
|
||
for i, symbol in enumerate(rule):
|
||
# Добавляем все символы из FIRST(symbol) кроме эпсилон
|
||
first_without_epsilon = self.first_sets[symbol] - {""}
|
||
old_size = len(self.first_sets[non_terminal])
|
||
self.first_sets[non_terminal].update(first_without_epsilon)
|
||
if len(self.first_sets[non_terminal]) > old_size:
|
||
changed = True
|
||
|
||
# Если symbol не может порождать эпсилон, прерываем
|
||
if "" not in self.first_sets[symbol]:
|
||
all_can_derive_epsilon = False
|
||
break
|
||
|
||
# Если все символы в правиле могут порождать эпсилон,
|
||
# то и нетерминал может порождать эпсилон
|
||
if (
|
||
all_can_derive_epsilon
|
||
and "" not in self.first_sets[non_terminal]
|
||
):
|
||
self.first_sets[non_terminal].add("")
|
||
changed = True
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{\_calculate\_follow\_sets}}
|
||
|
||
Метод \texttt{\_calculate\_follow\_sets} вычисляет множества FOLLOW для нетерминальных символов грамматики. Код метода представлен в листинге~\ref{lst:calculate_follow_sets}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar.
|
||
|
||
Метод не возвращает значений явно, но заполняет словарь follow\_sets в объекте класса.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{\_calculate\_follow\_sets}.}, label={lst:calculate_follow_sets}]
|
||
def _calculate_follow_sets(self):
|
||
# инициализировать Fo(S) = { $ }, а все остальные Fo(Ai) пустыми множествами
|
||
for non_terminal in self.productions:
|
||
self.follow_sets[non_terminal] = set()
|
||
|
||
# Добавляем символ конца строки $ для начального символа
|
||
self.follow_sets[self.start_symbol].add("$")
|
||
|
||
# Повторяем, пока в наборах Follow происходят изменения
|
||
changed = True
|
||
while changed:
|
||
changed = False
|
||
|
||
# Для каждого нетерминала Aj в грамматике
|
||
for non_terminal_j, rules in self.productions.items():
|
||
|
||
# Для каждого правила Aj → w
|
||
for rule in rules:
|
||
|
||
# Для каждого символа в правиле
|
||
for i, symbol in enumerate(rule):
|
||
|
||
# Если символ - нетерминал Ai
|
||
if symbol in self.productions:
|
||
# w' - остаток правила после Ai
|
||
remainder = rule[i + 1 :] if i + 1 < len(rule) else []
|
||
|
||
# Если есть терминалы после Ai (w' не пусто)
|
||
if remainder:
|
||
# Вычисляем First(w')
|
||
first_of_remainder = self._first_of_sequence(remainder)
|
||
|
||
# Если терминал a находится в First(w'), то добавляем a к Follow(Ai)
|
||
for terminal in first_of_remainder - {""}:
|
||
if terminal not in self.follow_sets[symbol]:
|
||
self.follow_sets[symbol].add(terminal)
|
||
changed = True
|
||
|
||
# Если epsilon находится в First(w'), то добавляем Follow(Aj) к Follow(Ai)
|
||
if "" in first_of_remainder:
|
||
old_size = len(self.follow_sets[symbol])
|
||
self.follow_sets[symbol].update(
|
||
self.follow_sets[non_terminal_j]
|
||
)
|
||
if len(self.follow_sets[symbol]) > old_size:
|
||
changed = True
|
||
|
||
# Если w' пусто (Ai в конце правила), то добавляем Follow(Aj) к Follow(Ai)
|
||
else:
|
||
old_size = len(self.follow_sets[symbol])
|
||
self.follow_sets[symbol].update(
|
||
self.follow_sets[non_terminal_j]
|
||
)
|
||
if len(self.follow_sets[symbol]) > old_size:
|
||
changed = True
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{\_first\_of\_sequence}}
|
||
|
||
Метод \texttt{\_first\_of\_sequence} вычисляет множество FIRST для последовательности символов. Код метода представлен в листинге~\ref{lst:first_of_sequence}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar и список символов sequence.
|
||
|
||
Метод возвращает множество (set) строк, представляющих FIRST для заданной последовательности.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{\_first\_of\_sequence}.}, label={lst:first_of_sequence}]
|
||
def _first_of_sequence(self, sequence):
|
||
"""Вычисляет множество FIRST для последовательности символов"""
|
||
if not sequence:
|
||
return {""}
|
||
|
||
result = set()
|
||
all_can_derive_epsilon = True
|
||
|
||
for symbol in sequence:
|
||
# Добавляем First(symbol) без эпсилон к результату
|
||
result.update(self.first_sets[symbol] - {""})
|
||
|
||
# Если symbol не может порождать эпсилон, останавливаемся
|
||
if "" not in self.first_sets[symbol]:
|
||
all_can_derive_epsilon = False
|
||
break
|
||
|
||
# Если все символы могут порождать эпсилон, добавляем эпсилон к результату
|
||
if all_can_derive_epsilon:
|
||
result.add("")
|
||
|
||
return result
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{\_fill\_lookup\_table}}
|
||
|
||
Метод \texttt{\_fill\_lookup\_table} заполняет таблицу синтаксического анализа для LL(1)-грамматики. Код метода представлен в листинге~\ref{lst:fill_lookup_table}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar.
|
||
|
||
Метод не возвращает значений явно, но заполняет словарь lookup\_table в объекте класса или вызывает исключение, если грамматика не является LL(1).
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{\_fill\_lookup\_table}.}, label={lst:fill_lookup_table}]
|
||
def _fill_lookup_table(self):
|
||
# Для каждого нетерминала A
|
||
for non_terminal, rules in self.productions.items():
|
||
# Формируем таблицу синтаксического анализа
|
||
self.lookup_table[non_terminal] = {}
|
||
|
||
# Для каждого правила A → w
|
||
for rule in rules:
|
||
# Вычисляем First(w)
|
||
first_of_rule = self._first_of_sequence(rule)
|
||
|
||
# Для каждого терминала a в First(w)
|
||
for terminal in first_of_rule - {""}:
|
||
# Если T[A,a] уже содержит правило, грамматика не LL(1)
|
||
if terminal in self.lookup_table[non_terminal]:
|
||
raise ValueError(
|
||
"Грамматика не является LL(1)-грамматикой.\n"
|
||
f"Конфликт в ячейке [{non_terminal}, {terminal}]\n"
|
||
f"Новое правило: {non_terminal} -> {' '.join(rule)};\n"
|
||
f"Существующее правило: {non_terminal} -> {self.lookup_table[non_terminal][terminal]}"
|
||
)
|
||
|
||
# Добавляем правило в таблицу
|
||
self.lookup_table[non_terminal][terminal] = rule
|
||
|
||
# Если эпсилон в First(w), то для каждого b в Follow(A)
|
||
if "" in first_of_rule:
|
||
for terminal in self.follow_sets[non_terminal]:
|
||
# Если T[A,b] уже содержит правило, грамматика не LL(1)
|
||
if terminal in self.lookup_table[non_terminal]:
|
||
raise ValueError(
|
||
"Грамматика не является LL(1)-грамматикой.\n"
|
||
f"Конфликт в ячейке [{non_terminal}, {terminal}]\n"
|
||
f"Новое правило: {non_terminal} -> {' '.join(rule)};\n"
|
||
f"Существующее правило: {non_terminal} -> {self.lookup_table[non_terminal][terminal]}"
|
||
)
|
||
|
||
# Добавляем правило в таблицу
|
||
self.lookup_table[non_terminal][terminal] = rule
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{format\_rules}}
|
||
|
||
Метод \texttt{format\_rules} форматирует все правила грамматики для удобного представления. Код метода представлен в листинге~\ref{lst:format_rules}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar.
|
||
|
||
Метод возвращает строку (str), содержащую все правила грамматики с их номерами.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{format\_rules}.}, label={lst:format_rules}]
|
||
def format_rules(self) -> str:
|
||
result = []
|
||
sorted_rules = sorted(self.rule_numbers.items(), key=lambda x: x[1])
|
||
|
||
for rule, number in sorted_rules:
|
||
non_terminal, symbols = rule
|
||
rule_text = f"{number}: {non_terminal} -> {' '.join(symbols)}"
|
||
result.append(rule_text)
|
||
|
||
return "\n".join(result)
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{format\_lookup\_table}}
|
||
|
||
Метод \texttt{format\_lookup\_table} форматирует таблицу синтаксического анализа для удобного представления. Код метода представлен в листинге~\ref{lst:format_lookup_table}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar.
|
||
|
||
Метод возвращает строку (str), содержащую таблицу синтаксического анализа в виде таблицы с использованием библиотеки PrettyTable.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{format\_lookup\_table}.}, label={lst:format_lookup_table}]
|
||
def format_lookup_table(self) -> str:
|
||
table = PrettyTable()
|
||
terminals = list(self.terminals)
|
||
table.field_names = [""] + terminals + ["$"]
|
||
|
||
for non_terminal in self.productions:
|
||
row = [non_terminal]
|
||
for terminal in terminals + ["$"]:
|
||
if terminal in self.lookup_table[non_terminal]:
|
||
rule = self.lookup_table[non_terminal][terminal]
|
||
rule_num = self.rule_numbers.get((non_terminal, tuple(rule)), "")
|
||
row.append(f"{rule_num}: {' '.join(rule)}")
|
||
else:
|
||
row.append(" - ")
|
||
table.add_row(row)
|
||
return str(table)
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{format\_first\_sets}}
|
||
|
||
Метод \texttt{format\_first\_sets} форматирует множества FIRST для удобного представления. Код метода представлен в листинге~\ref{lst:format_first_sets}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar.
|
||
|
||
Метод возвращает строку (str), содержащую множества FIRST для всех символов грамматики.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{format\_first\_sets}.}, label={lst:format_first_sets}]
|
||
def format_first_sets(self) -> str:
|
||
"""Форматирует множества FIRST в читаемый вид."""
|
||
result = []
|
||
result.append("Множества FIRST:")
|
||
result.append("=" * 40)
|
||
|
||
# Сортируем для гарантии порядка вывода
|
||
for symbol in sorted(self.first_sets.keys()):
|
||
# Заменяем пустую строку на эпсилон для лучшей читаемости
|
||
first_set = {
|
||
self.EPSILON if item == "" else item for item in self.first_sets[symbol]
|
||
}
|
||
result.append(f"FIRST({symbol}) = {{{', '.join(sorted(first_set))}}}")
|
||
|
||
return "\n".join(result)
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{format\_follow\_sets}}
|
||
|
||
Метод \texttt{format\_follow\_sets} форматирует множества FOLLOW для удобного представления. Код метода представлен в листинге~\ref{lst:format_follow_sets}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar.
|
||
|
||
Метод возвращает строку (str), содержащую множества FOLLOW для всех нетерминалов грамматики.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{format\_follow\_sets}.}, label={lst:format_follow_sets}]
|
||
def format_follow_sets(self) -> str:
|
||
"""Форматирует множества FOLLOW в читаемый вид."""
|
||
result = []
|
||
result.append("Множества FOLLOW:")
|
||
result.append("=" * 40)
|
||
|
||
# Обрабатываем только нетерминалы
|
||
for non_terminal in sorted(self.productions.keys()):
|
||
follow_set = self.follow_sets.get(non_terminal, set())
|
||
result.append(
|
||
f"FOLLOW({non_terminal}) = {{{', '.join(sorted(follow_set))}}}"
|
||
)
|
||
|
||
return "\n".join(result)
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{analyze}}
|
||
|
||
Метод \texttt{analyze} выполняет синтаксический анализ входной последовательности токенов с использованием LL(1)-алгоритма. После применения продукции метод вызывает функцию-колбэк, представляющую семантические действия, если она была задана при создании объекта класса Grammar. Код метода представлен в листинге~\ref{lst:analyze}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar и список input\_tokens типа list[str], представляющий последовательность входных токенов.
|
||
|
||
Метод возвращает список (list) целых чисел, содержащий номера применённых правил в процессе анализа.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{analyze}.}, label={lst:analyze}]
|
||
def analyze(self, input_tokens: list[str]) -> list[int]:
|
||
input_tokens = input_tokens.copy()
|
||
input_tokens += ["$"]
|
||
input_pos = 0
|
||
|
||
# Инициализируем стек с терминальным символом и начальным символом
|
||
stack = ["$", self.start_symbol]
|
||
|
||
rules_applied = []
|
||
|
||
while stack:
|
||
top = stack[-1]
|
||
|
||
current_symbol = (
|
||
input_tokens[input_pos] if input_pos < len(input_tokens) else "$"
|
||
)
|
||
|
||
# Случай 1: Верхний символ стека - нетерминал
|
||
if top in self.productions:
|
||
# Ищем правило в таблице синтаксического анализа
|
||
if current_symbol in self.lookup_table[top]:
|
||
# Получаем правило
|
||
production = self.lookup_table[top][current_symbol]
|
||
|
||
# Удаляем нетерминал из стека
|
||
stack.pop()
|
||
|
||
# Добавляем правило в rules_applied
|
||
rule_number = self.rule_numbers[(top, tuple(production))]
|
||
rules_applied.append(rule_number)
|
||
|
||
# Execute semantic action if provided
|
||
if self.semantic_action:
|
||
self.semantic_action(rule_number, (top, production))
|
||
|
||
# Добавляем правило в стек в обратном порядке
|
||
for symbol in reversed(production):
|
||
stack.append(symbol)
|
||
else:
|
||
expected_symbols = list(self.lookup_table[top].keys())
|
||
raise ValueError(
|
||
f"Syntax error: expected one of {expected_symbols}, got '{current_symbol}'"
|
||
)
|
||
|
||
# Случай 2: Верхний символ стека - терминал
|
||
elif top != "$":
|
||
if top == current_symbol:
|
||
# Удаляем терминал из стека
|
||
stack.pop()
|
||
# Переходим к следующему символу ввода
|
||
input_pos += 1
|
||
else:
|
||
raise ValueError(
|
||
f"Syntax error: expected '{top}', got '{current_symbol}'"
|
||
)
|
||
|
||
# Случай 3: Верхний символ стека - $
|
||
else: # top == "$"
|
||
if current_symbol == "$":
|
||
# Успешный синтаксический анализ
|
||
stack.pop() # Удаляем $ из стека
|
||
else:
|
||
raise ValueError(
|
||
f"Syntax error: unexpected symbols at end of input: '{current_symbol}'"
|
||
)
|
||
|
||
return rules_applied
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{generate}}
|
||
|
||
Метод \texttt{generate} генерирует случайное предложение по заданной грамматике. Код метода представлен в листинге~\ref{lst:generate}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar и необязательный параметр symbol типа str или None, указывающий начальный символ для генерации.
|
||
|
||
Метод возвращает кортеж (tuple), содержащий список терминалов и список номеров применённых правил.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{generate}.}, label={lst:generate}]
|
||
def generate(self, symbol: str | None = None) -> tuple[list[str], list[int]]:
|
||
"""Генерирует предложение по заданной грамматике. Возвращает список терминалов
|
||
и список номеров применённых правил."""
|
||
|
||
if symbol is None:
|
||
return self.generate(self.start_symbol)
|
||
|
||
# Если символ - терминал, возвращаем его
|
||
if symbol not in self.productions:
|
||
return [symbol], []
|
||
|
||
# Выбираем случайное правило для нетерминала
|
||
rules = self.productions[symbol]
|
||
chosen_rule = random.choice(rules)
|
||
|
||
# Получаем номер выбранного правила
|
||
rule_number = self.rule_numbers[(symbol, tuple(chosen_rule))]
|
||
|
||
# Инициализируем результаты
|
||
terminals = []
|
||
rule_numbers = [rule_number]
|
||
|
||
# Разворачиваем каждый символ в правой части правила
|
||
for s in chosen_rule:
|
||
sub_terminals, sub_rules = self.generate(s)
|
||
terminals.extend(sub_terminals)
|
||
rule_numbers.extend(sub_rules)
|
||
|
||
return terminals, rule_numbers
|
||
\end{lstlisting}
|
||
|
||
\subsubsection{Метод \texttt{generate\_derivation\_steps}}
|
||
|
||
Метод \texttt{generate\_derivation\_steps} преобразует список номеров правил в последовательность шагов вывода. Код метода представлен в листинге~\ref{lst:generate_derivation_steps}.
|
||
|
||
Метод принимает ссылку на объект класса Grammar и список rule\_numbers типа list[int], содержащий номера правил для применения.
|
||
|
||
Метод возвращает список (list) строк, представляющий каждый шаг вывода предложения.
|
||
|
||
\begin{lstlisting}[caption={Код метода \texttt{generate\_derivation\_steps}.}, label={lst:generate_derivation_steps}]
|
||
def generate_derivation_steps(self, rule_numbers: list[int]) -> list[str]:
|
||
"""Преобразует список номеров правил в последовательность шагов вывода.
|
||
Возвращает список строк, представляющих каждый шаг вывода."""
|
||
|
||
# Получаем соответствие между номерами правил и самими правилами
|
||
rule_details = {num: rule for rule, num in self.rule_numbers.items()}
|
||
|
||
# Начинаем с начального символа
|
||
current = self.start_symbol
|
||
steps = [current]
|
||
|
||
# Применяем каждое правило по порядку
|
||
for rule_num in rule_numbers:
|
||
if rule_num in rule_details:
|
||
non_terminal, replacement = rule_details[rule_num]
|
||
|
||
# Находим первое вхождение нетерминала и заменяем его
|
||
words = current.split()
|
||
for i, word in enumerate(words):
|
||
if word == non_terminal:
|
||
words[i : i + 1] = replacement
|
||
break
|
||
|
||
current = " ".join(words)
|
||
steps.append(current)
|
||
|
||
return steps
|
||
\end{lstlisting}
|
||
|
||
\subsection{Функция \texttt{load\_grammar}}
|
||
|
||
Функция \texttt{load\_grammar} загружает грамматику из файла и возвращает объект класса \texttt{Grammar}. Функция принимает необязательный параметр filename типа str, указывающий имя файла с грамматикой. Функция возвращает None в случае ошибки и объект класса Grammar в случае успешной загрузки грамматики. Код функции представлен в листинге~\ref{lst:load_grammar}. Также в ней задаются семантические действия, которые будут выполняться при применении продукций, и сохраняются в файлы множества FIRST и FOLLOW и таблица синтаксического анализа.
|
||
|
||
\begin{lstlisting}[caption={Код функции \texttt{load\_grammar}.}, label={lst:load_grammar}]
|
||
def load_grammar(filename: str = "grammar.txt") -> Grammar | None:
|
||
try:
|
||
# #b - 2 * #a + 3 * #c
|
||
actions = [
|
||
lambda rule_number, applied_count, _: print(
|
||
f"Rule #{rule_number} (applied x{applied_count} times): iconst_1"
|
||
),
|
||
lambda rule_number, applied_count, _: print(
|
||
f"Rule #{rule_number} (applied x{applied_count} times): iconst_2 isub"
|
||
),
|
||
lambda rule_number, applied_count, _: print(
|
||
f"Rule #{rule_number} (applied x{applied_count} times): iconst_1 iadd"
|
||
),
|
||
lambda rule_number, applied_count, _: print(
|
||
f"Rule #{rule_number} (applied x{applied_count} times): iconst_1 iadd"
|
||
),
|
||
lambda rule_number, applied_count, _: print(
|
||
f"Rule #{rule_number} (applied x{applied_count} times): iconst_3 iadd"
|
||
),
|
||
]
|
||
|
||
with open(filename, "r", encoding="utf-8") as file:
|
||
text = file.read()
|
||
grammar = Grammar(text, ActionsListWithAppliedCount(actions))
|
||
|
||
# Сохраняем информацию о грамматике в файлы
|
||
with open("grammar_rules.txt", "w", encoding="utf-8") as output_file:
|
||
output_file.write(grammar.format_rules())
|
||
print("Правила грамматики с номерами сохранены в grammar_rules.txt")
|
||
|
||
with open("grammar_lookup_table.txt", "w", encoding="utf-8") as output_file:
|
||
output_file.write(grammar.format_lookup_table())
|
||
print(
|
||
"Таблица синтаксического анализа сохранена в grammar_lookup_table.txt"
|
||
)
|
||
|
||
with open("grammar_first.txt", "w", encoding="utf-8") as output_file:
|
||
output_file.write(grammar.format_first_sets())
|
||
print("Множества FIRST сохранены в grammar_first.txt")
|
||
|
||
with open("grammar_follow.txt", "w", encoding="utf-8") as output_file:
|
||
output_file.write(grammar.format_follow_sets())
|
||
print("Множества FOLLOW сохранены в grammar_follow.txt")
|
||
|
||
print(f"Грамматика успешно загружена из файла {filename}")
|
||
return grammar
|
||
except FileNotFoundError:
|
||
print(f"Ошибка: Файл {filename} не найден")
|
||
return None
|
||
except ValueError as e:
|
||
print(f"Ошибка при загрузке грамматики: {e}")
|
||
return None
|
||
except Exception as e:
|
||
print(f"Неизвестная ошибка: {e}")
|
||
return None
|
||
\end{lstlisting}
|
||
|
||
\subsection{Функция \texttt{main}}
|
||
|
||
Функция \texttt{main} реализует интерактивную консольную оболочку для взаимодействия с пользователем. Код функции представлен в листинге~\ref{lst:main}.
|
||
|
||
\begin{lstlisting}[caption={Код функции \texttt{main}.}, label={lst:main}]
|
||
def main():
|
||
print("Программа для работы с LL(1)-грамматиками")
|
||
print("=" * 60)
|
||
print("Варианты команд:")
|
||
print(" - load <файл> - загрузить грамматику из файла (по умолчанию grammar.txt)")
|
||
print(" - check <строка> - проверить, соответствует ли строка грамматике")
|
||
print(" - generate - сгенерировать случайную строку по грамматике")
|
||
print(" - exit - выход из программы")
|
||
print("=" * 60)
|
||
|
||
# Загружаем грамматику по умолчанию при старте
|
||
grammar = load_grammar()
|
||
|
||
while True:
|
||
command = input("\nВведите команду: ").strip()
|
||
|
||
if not command:
|
||
continue
|
||
|
||
parts = command.split(maxsplit=1)
|
||
cmd = parts[0].lower()
|
||
|
||
if cmd == "exit":
|
||
print("Выход из программы.")
|
||
break
|
||
|
||
elif cmd == "load":
|
||
filename = "grammar.txt"
|
||
if len(parts) > 1:
|
||
filename = parts[1].strip()
|
||
grammar = load_grammar(filename)
|
||
|
||
elif cmd == "check":
|
||
input_string = ""
|
||
if len(parts) > 1:
|
||
input_string = parts[1].strip()
|
||
check_string(grammar, input_string)
|
||
|
||
elif cmd == "generate":
|
||
generate_string(grammar)
|
||
|
||
else:
|
||
print(f"Неизвестная команда: {cmd}")
|
||
print("Доступные команды: load, check, generate, exit")
|
||
\end{lstlisting}
|
||
|
||
\newpage
|
||
\section{Результаты работы программы}
|
||
Результаты работы программы представлены на Рис.~\ref{fig:result1}.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.9\linewidth]{img/result1.png}
|
||
\caption{Результаты работы программы.}
|
||
\label{fig:result1}
|
||
\end{figure}
|
||
|
||
\newpage
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.6\linewidth]{img/wrong.png}
|
||
\caption{Реакция программы на некорректный пользовательский ввод.}
|
||
\label{fig:wrong}
|
||
\end{figure}
|
||
|
||
На Рис.~\ref{fig:wrong} представлена реакция программы на некорректный пользовательский ввод.
|
||
|
||
\begin{lstlisting}[caption={Содержимое файла \texttt{grammar\_first.txt}.}, label={lst:grammar_first}, basicstyle=\ttfamily]
|
||
Множества FIRST:
|
||
========================================
|
||
FIRST(A) = {a, b}
|
||
FIRST(B) = {b}
|
||
FIRST(C) = {c}
|
||
FIRST(S) = {b}
|
||
FIRST(a) = {a}
|
||
FIRST(b) = {b}
|
||
FIRST(c) = {c}
|
||
\end{lstlisting}
|
||
|
||
\begin{lstlisting}[caption={Содержимое файла \texttt{grammar\_follow.txt}.}, label={lst:grammar_follow}, basicstyle=\ttfamily]
|
||
Множества FOLLOW:
|
||
========================================
|
||
FOLLOW(A) = {b}
|
||
FOLLOW(B) = {a, b, c}
|
||
FOLLOW(C) = {b}
|
||
FOLLOW(S) = {$}
|
||
\end{lstlisting}
|
||
|
||
\begin{lstlisting}[caption={Содержимое файла \texttt{grammar\_lookup\_table.txt}.}, label={lst:grammar_lookup_table}, basicstyle=\ttfamily]
|
||
+---+------------+----------+--------+-----+
|
||
| | a | b | c | $ |
|
||
+---+------------+----------+--------+-----+
|
||
| S | - | 1: B A b | - | - |
|
||
| A | 2: a A B C | 3: b B | - | - |
|
||
| B | - | 4: b | - | - |
|
||
| C | - | - | 5: c A | - |
|
||
+---+------------+----------+--------+-----+
|
||
\end{lstlisting}
|
||
|
||
В листингах~\ref{lst:grammar_first}, \ref{lst:grammar_follow} и \ref{lst:grammar_lookup_table} представлено содержимое файлов \texttt{grammar\_first.txt}, \texttt{grammar\_follow.txt} и \texttt{grammar\_lookup\_table.txt} соответственно.
|
||
|
||
|
||
\newpage
|
||
\section*{Заключение}
|
||
\addcontentsline{toc}{section}{Заключение}
|
||
В ходе выполнения лабораторной работы была реализована программа -- синтаксический анализатор для LL(1)-грамматик. С его помощью для заданной грамматики были построены множества FIRST и FOLLOW для всех нетерминалов и таблица синтаксического анализа. Программа-анализатор также включает в себя функции для проверки принадлежности цепочки языку, заданному грамматикой, и генерации случайных цепочек. Также программа позволяет задать семантические действия, которые будут выполняться при применении продукций. Для демонстрации возможностей программы в качестве семантических действий решено было использовать генерацию инструкций для Java Virtual Machine.
|
||
|
||
Из достоинств выполнения лабораторной работы можно выделить, во-первых, возможность задания грамматики в отдельном текстовом файле, что позволяет легко изменять и расширять её без модификации программного кода. Во-вторых, программа автоматически проверяет, что введенная грамматика является LL(1)-грамматикой, и вычисляет множества FIRST и FOLLOW для всех нетерминалов, а также таблицу синтаксического анализа. В противном случае, программа выводит сообщение об ошибке, в котором указывается на конкретные правила грамматики, между выбором которых возникает неоднозначность. В третьих, программа позволяет легко задавать произвольные семантические действия в виде функций или объектов колбэков, которые будут вызываться при применении продукций.
|
||
|
||
К недостаткам текущей реализации можно отнести то, что алгоритм генерации не контролирует длину предложений, что может приводить к избыточно длинным или коротким цепочкам.
|
||
|
||
Функционал программы несложно масштабировать. Например, несложно добавить функцию для визуализации дерева вывода распознаваемой цепочки, пусть даже в текстовом виде, в классе Grammar уже есть все необходимые для этого данные. Кроме того, класс Grammar может служить хорошей основой для создания полноценного LL(k) анализатора.
|
||
|
||
На выполнение лабораторной работы ушло около 4 часов, основная часть кода была взята из лабораторной работы №3. Работа была выполнена в среде разработки Visual Studio Code. Программа написана на Python версии 3.13.
|
||
|
||
\newpage
|
||
\section*{Список литературы}
|
||
\addcontentsline{toc}{section}{Список литературы}
|
||
|
||
\vspace{-1.5cm}
|
||
\begin{thebibliography}{0}
|
||
\bibitem{vostrov}
|
||
Востров, А.В. Курс лекций по дисциплине <<Математическая логика>>. URL \url{https://tema.spbstu.ru/compiler/} (дата обращения 01.04.2025 г.)
|
||
\bibitem{lutz}
|
||
Лутц, М. Изучаем Python. 5-е изд. / М. Лутц. — СПб.: Питер, 2019. — 1216 с.
|
||
\end{thebibliography}
|
||
|
||
\end{document} |