11.tex

\setcounter{section}{10}

\section{Програмування синтаксичних \allowbreak а\-на\-лі\-за\-то\-рів}

\subsection{Синтаксична діаграма}

\textit{Синтаксична діаграма} --- це орієнтований граф, дуги котрого позначені елементами $(N \cup \Sigma)^\star$. Синтаксична діаграма будується для кожного $A$-правила КС-граматики мови програмування. \medskip

Оскільки вершини такого графа не іменуються, то вони припускаються неявно. Синтаксична діаграма позначається іменем нетермінала, для якого вона будується. \medskip

Мета побудови синтаксичних діаграм для мови програмування на основі КС-граматики:
\begin{itemize}
	\item для кожного $A$-правила КС-граматики будується синтаксична діаграма;
	\item на основі побудови синтаксичної діаграми для деякого нетермінала $A \in N$ будуємо підпрограму, яка аналізує ту частину головної програми, яку вона визначає.
\end{itemize}

Оскільки у більшості випадків при визначенні синтаксису мови програмування ми користуємося множиною рекурсивних правил, то серед підпрограм, які будуються на основі правил граматики, будуть і рекурсивні процедури (рекурсія буде як явна, так і неявна). \medskip

Сформулюємо правила побудови синтаксичного графа:
\begin{enumerate}
	\item Кожен нетермінал з відповідною множиною породжуючих правил $A \mapsto \omega_1 \mid \omega_2 \mid \ldots \mid \omega_p$, $\omega_i \in (N \cup \Sigma)^\star$, $i = \overline{1..p}$ відображається в один синтаксичний граф. \medskip

	Отже, кількість синтаксичних графів рівна кількості нетерміналів граматики $G$.

	\item Для кожного елемента слова $\omega = \alpha_1 \alpha_2 \ldots \alpha_p$, $\alpha_i \in (N \cup \Sigma)$, $i = \overline{1..p}$ будуємо ребро синтаксичного графа та покажемо його таким чином що:
	\begin{itemize}
		\item якщо $\alpha_i = x$, $x \in \Sigma$, де $x$ --- вихідна лексема, то будуємо таке ребро:
		\begin{figure}[H]
			\centering
			\input{img/16}
		\end{figure}

		\item якщо $\alpha_k = A_i \in N$ --- нетермінал граматики, то будуємо таке ребро:
		\begin{figure}[H]
			\centering
			\input{img/17}
		\end{figure}
	\end{itemize}
\end{enumerate}

Тоді, коли правило граматики $G$ має вигляд $A_i \mapsto \alpha_1 A_1 \ldots$ для побудови діаграми скористаємося обома способами:
\begin{figure}[H]
	\centering
	\input{img/18}
\end{figure}

Коли правило граматики $G$ має вигляд $A_i \mapsto \omega_1 \mid \omega_2 \mid \ldots \mid \omega_p$, то відповідний синтаксичний граф буде мати вигляд:
\begin{figure}[H]
	\centering
	\input{img/19}
\end{figure}
де замість $\omega_1, \omega_2, \ldots, \omega_p$ будуються відповідні синтаксичні діаграми. \medskip

Якщо на основі граматики мови програмування побудована множина синтаксичних графів, то можна спробувати зменшити їх кількість, скориставшись підстановкою одних графів у інші. При цьому замість елемента $A_i$ підставляється його синтаксичний граф. Таким чином можна зменшити кількість синтаксичних графів. Для того, щоб забезпечити детермінований синтаксичний аналіз з переглядом вперед на одну лексему, потрібно накласти певні обмеження, а саме: для кожного правила $A_i$ виду  $A_i \mapsto \omega_1 \mid \omega_2 \mid \ldots \mid \omega_p$ з синтаксичною діаграмою наведеного вище вигляду необхідне виконання наступної умови: множини $\text{First}_1(\omega_j) \oplus_1 \text{Follow}_1 (A_i)$, $j = \overline{1..p}$ повинні попарно не перетинатися. Зрозуміло, що ця умова гарантує детермінований вибір шляху при русі по синтаксичній діаграмі.

\subsubsection{Код}

Подальше програмування синтаксичного аналізатора можна звести до наступних примітивів:
\begin{itemize}
	\item для фрагмента синтаксичної діаграми вигляду 
	\begin{figure}[H]
		\centering
		\input{img/20}
	\end{figure}
	відповідний фрагмент програми (наприклад, мовою С) матиме вигляд:
	\begin{verbatim}
	extern int lexem_code;  // код лексеми, яку виділив сканер
	extern char lexem_text[];  // текст лексеми
	...
	if (lexem_code == code_x) get_lexem();
	else error();
	\end{verbatim}

	\item для фрагмента синтаксичної діаграми вигляду
	\begin{figure}[H]
		\centering
		\input{img/21}
	\end{figure}
	відповідний фрагмент програми матиме вигляд:
	\begin{verbatim}
	// виклик функції, яка побудована для синтаксичної 
	// діаграми побудованої для нетермінала A_i.
	f_A_i();
	\end{verbatim}
	\item для фрагмента синтаксичної діаграми вигляду
	\begin{figure}[H]
		\centering
		\input{img/22}
	\end{figure}
	відповідний фрагмент програми матиме вигляд:
	\begin{verbatim}
	extern int lexem_code;
	extern char lexem_text[];
	...
	{
	    if (lexem_code == code_alpha_1) get_lexem();
	    else error();
	    f_A_1();
	    ...
	}
	\end{verbatim}
	\item для фрагмента синтаксичної діаграми вигляду
	\begin{figure}[H]
		\centering
		\input{img/23}
	\end{figure}
	для кожного $\omega_i$, $i = \overline{1..p}$ знайдемо множину
	\begin{equation}
	    \text{First}_1(\omega_i) \oplus_1 \text{Follow}_1(A) = L_i = \left\{a_i^1, a_i^2, \ldots, a_i^{n_i}\right\}.
	\end{equation}

	Оскільки за умовою $L_i \cap L_j = \varnothing$, $i \ne j$, то відповідний фрагмент програми на мові С матиме вигляд:
	\begin{verbatim}
	extern int lexem_code;
	extern char lexem_text[];
	...
	void f_A_i(void) {
	    switch(lexema_code) {
	        case code_a_1_1:
	        case code_a_1_2:
	        ...
	        case code_a_1_n_1:
	            ...  // фрагмент програми для w_1
	            break;
	        case code_a_2_1:
	        case code_a_2_2:
	        ...
	        case code_a_2_n_2:
	            ...  // фрагмент програми для w_2
	            break;
	        ...
	        ...
	        ...
	        case code_a_p_1:
	        case code_a_p_2:
	        ...
	        case code_a_p_n_p:
	            ...  // фрагмент програми для w_p
	            break;
	        default: 
	            error();
	    }
	}  // кінець функції для нетермінала A_i
	\end{verbatim}
\end{itemize}

Відмітимо, що до того, як зменшувати кількість синтаксичних діаграм шляхом суперпозиції одних діаграм в інші, необхідно знайти контексти виду $\text{First}_1(\omega_i) \oplus_1 \text{Follow}_1(A)$ для тієї синтаксичної діаграми нетермінала $A$, для якої ми виконуємо операцію суперпозиції. Ці контексти ми використаємо при програмуванні синтаксичного аналізатора на основі синтаксичної діаграми, у яку підставлено синтаксичну діаграму для нетермінала $A_i$.

\subsubsection{Одна особливість}

Досить часто при визначенні синтаксису мови програмування користуються синтаксичними правилами виду $A_i \mapsto \alpha_1 \alpha_2 \ldots \alpha_p A_i \mid \varepsilon$. Тоді синтаксична діаграма буде мати вигляд:
\begin{figure}[H]
	\centering
	\input{img/24}
\end{figure}

Для вище наведеної синтаксичної діаграми відповідні множини будуть:
\begin{equation}
    \text{First}_1(\alpha_1 \alpha_2 \ldots \alpha_p A_i) \oplus_1 \text{Follow}_1(A_i) = L_1 = \left\{a_1^1, a_1^2, \ldots, a_1^{n_1}\right\}
\end{equation}
Відповідний фрагмент програми мовою С матиме вигляд:
\begin{verbatim}
extern int lexem_code;
extern char lexem_text[];
void A_i(void) {
    while (
        lexem_code == code_a_1_1 ||
        lexem_code == code_a_1_2 ||
        ... ||
        lexem_code == code_a_1_n_1
    ) {
        ...  // фрагмент програми для слова w
    }
}  // кінець підпрограми для нетермінала A_i
\end{verbatim}

Виконавши аналіз варіантів побудови синтаксичного аналізатора на основі синтаксичних діаграм, покажемо вигляд основної --- main-про\-гра\-ми:
\begin{verbatim}
int lexem_code;
char lexem_text[1<<8];
int main () { 
    get_lexem();
    axiom();  // процедура, пов'язана з аксіомою S граматики
}
\end{verbatim}

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

\begin{enumerate}
	\item Який граф називається синтаксичною діаграмою?
	\item Як на синтаксичній діаграмі позначаються термінали і нетермінали?
	\item Як на синтаксичній діаграмі позначаються прості (без $\vert$) і складені (з $\vert$)  правила?
	\item Напишіть фрагмент коду (наприклад на мові С) для обробки терміналів і нетерміналів.
	\item Напишіть фрагмент коду (наприклад на мові С) для обробки простих (без $\vert$) і складених (з $\vert$) правил.
	\item Як на синтаксичній діаграмі позначаються правила вигляду $A \mapsto \omega \mid \varepsilon$?
	\item Напишіть фрагмент коду (наприклад на мові С) для обробки правил вигляду $A \mapsto \omega \mid \varepsilon$.
\end{enumerate}