07.tex

\setcounter{section}{6}

\section{Синтаксичний аналіз в мовних процесорах}

\subsection{Синтаксичний аналіз}

Для визначення синтаксичної компоненти мови програмування використовують кон\-текст\-но-вільні граматики (КС-граматики). На відміну від скінченно-автоматних граматик потужність класу КС-граматик достатня, щоб визначити майже всі так звані синтаксичні властивості мов програмування. Якщо цього недостатньо, то розглядають деякі спрощення у граматиках типу 2
або параметричні КC-граматики. \medskip

Звичайно, із синтаксичною компонентою мови програмування пов'\-я\-за\-на семантична компонента. Тоді, якщо ми говоримо про семантику мови програмування, ми вимагаємо семантичної однозначності для кожної вірно написаної програми. За аналогією з семантикою, при описі синтаксичної компоненти мови програмування необхідно користуватися однозначними граматиками. \medskip

Граматика $G$ називається \textit{неоднозначною}, якщо існує декілька варіантів виводу $\omega$ в $G$ $\left(\omega \in L(G)\right)$. \medskip

\textbf{Приклад.} Розглянемо таку граматику $G = \left\langle N, \Sigma, P, S\right\rangle$ з двома правилами у схемі $P$: $S \Rightarrow S + S$, і $S \Rightarrow a$. Покажемо, що для ланцюжка $\omega = a + a + a$ існує щонайменше два варіанти виводу:
\begin{enumerate}
	\item $S \Rightarrow S + S \Rightarrow S + S + S \Rightarrow a + S + S \Rightarrow a + a + S \Rightarrow a + a + a$.
	\item $S \Rightarrow S + S \Rightarrow a + S \Rightarrow a + S + S \Rightarrow a + a + S \Rightarrow a + a + a$.
\end{enumerate}

\subsubsection{Стратегії виведення}

В теорії граматик розглядається декілька стратегій виведення ланцюжка $\omega$ в $G$. Визначимо дві стратегії які будуть використані в подальшому. \medskip\

\textit{Лівостороння стретегія виводу} ланцюжка $\omega$ в $G$ --- це послідовність кроків безпосереднього виводу, при якій на кожному кроці до увагі береться перший зліва направо нетермінал. \medskip

\textit{Правостороння стратегія виводу} $\omega$ в $G$ протилежна лівосторонній стратегії. \medskip

З виводом $\omega$ в $G$ пов'язане синтаксичне дерево, яке визначає синтаксичну структуру програми.

\subsubsection{Синтаксичні дерева}

\textit{Синтаксичне дерево виведення} $\omega$ в $G$ --- це впорядковане дерево, корінь котрого позначено аксіомою, в проміжних вершинах знаходяться нетермінали, а на кроні --- елементи з $\Sigma \cup \{\varepsilon\}$. Побудова синтаксичного дерева виведення $\omega$ в $G$ виконується покроково з урахуванням стратегії виводу $\omega$ в $G$. \medskip


\textbf{Алгоритм [побудови синтаксичного дерева ланцюжка $\omega$ в \allowbreak граматиці $G$ урахуванням лівосторонньої стратегії виводу].}
\begin{enumerate}
	\item Будуємо корінь дерева та позначимо його аксіомою $S$.

	\item В схемі $P$ граматики $G$ візьмемо правило виду $S \Rightarrow \alpha_1 \alpha_2 \ldots \alpha_p$, де $\alpha_i \in N \cup \Sigma \cup \{\varepsilon\} $	і побудуємо дерево висоти 1: 
	\begin{figure}[H]
		\centering
		\input{img/10-1}
	\end{figure}

	\item На кроні дерева, побудованого на попередньому кроці, візьмемо перший зліва направо нетермінал. Нехай це буде $\alpha_i$. Тоді в схемі $P$ виберемо правило виду $\alpha_i \Rightarrow \beta_1 \beta_2 \ldots \beta_l$, де $\beta_i \in N \cup \Sigma \cup \{\varepsilon\}$ і побудуємо наступне дерево: 
	\begin{figure}[H]
		\centering
		\input{img/11-1}
	\end{figure}

	Цей крок виконується доки на кроні дерева є елементи з $N$.
\end{enumerate}

Зауважимо очевидні факти, що випливають з побудови синтаксичного дерева:
\begin{itemize}
	\item крона дерева, зображеного на попередньому малюнку наступна:
	\begin{equation}
		\alpha_1 \alpha_2 \ldots \alpha_{i - 1} \beta_1 \beta_2 \ldots \beta_l \alpha_{i + 1} \ldots \alpha_p;
	\end{equation}
	\item ланцюжок $\alpha_1 \alpha_2 \ldots \alpha_{i - 1} \in \Sigma^\star$ з крони --- термінальний ланцюжок;
	\item для однозначної граматики $G$ існує лише одне синтаксичне дерево виводу $\omega$ в $G$.
\end{itemize}

\subsubsection{Власне аналіз}

Будемо говорити, що ланцюжок $\omega \in \Sigma^\star$, побудований на основі граматики $G$ (зрозуміло, що вважаємо, що $\omega \in L(G)$) \textit{проаналізований}, якщо відоме одне з його дерев виводу. \medskip

Зафіксуємо послідовність номерів правил, які були використані під час побудови синтаксичного дерева виводу $\omega$ в $G$ з урахуванням стратегії виводу. \medskip

\textit{Лівостороннім аналізом} $\pi$ ланцюжка $\omega \in L(G)$ будемо називати послідовність номерів правил, які були використані при лівосторонньому виводі $\omega$ в $G$. \medskip

\textbf{Приклад:} Для граматики $G = \left\langle N, \Sigma, P, S\right\rangle$ зі схемою $P$:
\begin{align}
	S &\Rightarrow S + T \\
	S &\Rightarrow T \\
	T &\Rightarrow T \times F \\
	T &\Rightarrow F \\
	F &\Rightarrow (S) \\
	F &\Rightarrow a
\end{align}
і для ланцюжка $\omega = a \times (a + a)$ побудуємо лівосторонній аналіз $\pi$: \medskip

Виведення має вигляд:
\begin{multline*}
	S \Rightarrow T \Rightarrow T \times F \Rightarrow F \times F \Rightarrow a \times F \Rightarrow a \times (S) \Rightarrow a \times (S + T) \Rightarrow \\
	\Rightarrow a \times (T + T) \Rightarrow a \times (F + T) \Rightarrow a \times (a + T) \Rightarrow a \times (a + F) \Rightarrow a \times (a + a).
\end{multline*}

З наведеного вище виводу ланцюжка $\omega \in L(G)$ лівосторонній аналіз $\pi$ буде: $\pi = (2, 3, 4, 6, 5, 1, 2, 4, 6, 4, 6)$, а синтаксичне дерево виводу $\omega = a \times (a + a)$ наступне:
\begin{figure}[H]
	\centering
	\input{img/12}
\end{figure}

\subsubsection{Синтез дерева за аналізом}

Нехай $\pi$ --- лівосторонній аналіз ланцюжка $\omega \in L(G)$. Знаючи $\pi$ досить легко побудувати (відтворити) синтаксичне дерево. Відтворення (синтез) синтаксичного дерева можна виконати, скориставшись однією з стратегій синтаксичного аналізу:
\begin{itemize}
	\item стратегія ``зверху донизу'';
	\item стратегія ``знизу догори''.
\end{itemize}

Стратегія синтаксичного аналізу \textit{``зверху донизу''} --- це побудова синтаксичного дерева крок за кроком починаючи від кореня до крони. \medskip

\textbf{Алгоритм [синтезу синтаксичного дерева на основі лівостороннього аналізу $\pi$ ланцюжка $\omega \in L(G)$].}
\begin{enumerate}
	\item Побудуємо корінь дерева та позначимо його аксіомою $S$. Нехай аналіз $\pi$ має вигляд $\pi = (p_1, p_2, \ldots, p_m)$, тоді:

	\item Побудуємо дерево висоти один, взявши зі схеми $P$ правило з номером $p_1$ виду $S \Rightarrow \alpha_1 \alpha_2 \ldots \alpha_p$:
	\begin{figure}[H]
		\centering
		\input{img/13-1}
	\end{figure}

	\item На кроні дерева, отриманого на попередньому кроку, візьмемо перший зліва направо нетермінал (нехай це буде нетермінал $\alpha_i$) та правило з номером $p_j$ вигляду: $\alpha_i \Rightarrow \beta_1 \beta_2 \ldots \beta_l$ та побудуємо нове дерево:
	\begin{figure}[H]
		\centering
		\input{img/14-1}
	\end{figure}

	Даний пункт виконувати доти, доки не переглянемо всі елементи з $\pi$.
\end{enumerate}

\subsubsection{Проблеми стратегії ``зверху донизу''}

Сформулюємо декілька проблему для стратегії аналізу ``зверху донизу'': \medskip

У загальному випадку у класі КС-граматик існує проблема неоднозначності (недетермінізму) виводу $\omega \in L(G)$. Як приклад можемо розглянути граматику з ``циклами''. Це така граматика, у якої в схемі $P$ існує така послідовність правил за участю нетермінала $A_i$, що: $A_i \Rightarrow A_j$ і $A_j \Rightarrow A_i$, де $A_j$ --- будь-який нетермінал граматики $G$. \medskip

Як наслідок, граматики з ліворекурсивним нетерміналом для стратегії аналізу ``зверху донизу'' недопустимі. \medskip % це ж чому? 

Зауважимо, що існують підкласи класу КС-граматик, які природно забезпечують стратегію аналізу ``зверху донизу''. Один з таких підкласів --- це $LL(k)$-граматики, які забезпечують синтаксичний аналіз ланцюжка $\omega \in L(G)$ за час $O(n)$, де $n = \vert \omega \vert$, та при цьому аналіз є однозначним.

\subsection{Контрольні запитання}

\begin{enumerate}
	\item Які граматики називаються однозначними? % не неоднозначні, тобто ті в яких у довільного ланцюжка не більше одного виведення
	\item Які дві стратегії виведення ви знаєте? % право- і ліво-стороння
	\item Що таке синтаксичне дерево виведення? % кроінь аксіома, з вершини стрілки у вершини що отримуються з неї безпосереднім виведенням...
	\item Що таке лівосторонній аналіз ланцюжка? % послідовність номерів правил схеми граматики викристаних при виведенні
	\item Що таке синтез дерева за аналізом? % процес побудоваи синтаксичного дерева виведення ланцюжка за синтаксичним аналізом цього ланцюжка
	\item Які дві стратегії синтезу дерева за аналізом ви знаєте? % зверху донизу і знизу догори
	\item Що таке граматика з циклами і які проблеми вона створює для стратегії ``згори донизу''? % граматика у схемі якої є правила $A_i \Rightarrow A_j \Rightarrow A_i$, вона призводить до неоднозначності виведення
	\item Який підклас КС-граматик забезпечує стратегію аналізу ``зверху донизу''? % LL(k), ми скоро визначимо цей підклас
\end{enumerate}