Математическая теория формальных языков

Синтаксический разбор

Разбить на страницы
Показывать лекцию целиком

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

13.1. Нисходящий разбор

Определение 13.1.1. Процесс нахождения дерева вывода слова w в заданной контекстно-свободной грамматике называется синтаксическим разбором или синтаксическим анализом (parsing).

Определение 13.1.2. Протоколом левостороннего вывода в контекстно-свободной грамматике $$G = \lalg N , \Sigma , P , S \ralg $$ будем называть последовательность правил, примененных в этом выводе. Формально говоря, протоколом левостороннего вывода$$\omega_0 , \omega_1 , \ldots , \omega_n$$ является последовательность$$( A_1 \tto \alpha_1 ) , \ldots , ( A_n \tto \alpha_n ) ,$$ где для каждого i < n, если $$\omega_i = u B \theta $$ и $$\omega_{i+1} = u \beta \theta $$ для некоторых $$u \in \Sigma^* $$, $$B \in N $$, $$\theta \in \ns ^* $$, $$\beta \in \ns ^* $$, то Ai+1 = B и $$\alpha_{i+1} = \beta $$.

Пример 13.1.3. Рассмотрим контекстно-свободную грамматику$$\begin{align*} S \; {\to} \; c , \\ S \; {\to} \; dS , \\ S \; {\to} \; aSeSb . \end{align*}$$ Дереву вывода$$\xymatrix @=6pt { S\ar[ddllll]\ar[ddll]\ar[dd]\ar[ddrr]\ar[ddrrrr] \\ \\ a S\ar[dd] e S\ar[ddl]\ar[ddr] b \\ \\ c d S\ar[dd] \\ \\ c }$$ соответствует левосторонний вывод$$S \pRightarrow aSeSb \pRightarrow aceSb \pRightarrow acedSb \pRightarrow acedcb .$$ Протоколом этого вывода является последовательность$$( S \to aSeSb ) ,\ ( S \to c ) ,\ ( S \to dS ) ,\ ( S \to c ) .$$

Лемма 13.1.4. Разным левосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

Замечание 13.1.5. Протокол левостороннего вывода в контекстно-свободной грамматике является естественным описанием соответствующего дерева вывода в порядке префиксного обхода (preorder traversal). (При префиксном обходе упорядоченного дерева первым посещается корень этого дерева, затем выполняется префиксный обход первого непосредственного потомка корня, затем второго и т. д.)

Например, протокол левостороннего вывода из примера 13.1.3 задает процесс постепенного конструирования дерева вывода, изображенный ниже.$$\newcommand{\rb}[1]{\raisebox{0pt}[8pt]{$#1$}} \entrymodifiers={=<3.3mm>[o]} \xymatrix@=0mm{ \boldsymbol{S} \\ \\ \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ \boldsymbol{S}\boldsymbol{S}\\ \\ \\ \\ \rb{a}\rb{\boldsymbol{e}}\rb{\boldsymbol{b}} \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ S\ar[ddddll]\boldsymbol{S}\\ \\ \\ \\ \rb{a}\rb{c}\rb{e}\rb{\boldsymbol{b}} \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ S\ar[ddddll]S\ar[dddd]\ar[ddr]\\ \\ \boldsymbol{S}\\ \\ \rb{a}\rb{c}\rb{e}\rb{d}\rb{\boldsymbol{b}} \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ S\ar[ddddll]S\ar[dddd]\ar[ddr]\\ \\ S\ar[ddr]\\ \\ \rb{a}\rb{c}\rb{e}\rb{d}\rb{c}\rb{b} }$$

Определение 13.1.6. Левым разбором (left parse) слова w в контекстно-свободной грамматике G называется протокол любого левостороннего вывода слова w в грамматике G.

Пример 13.1.7. Левым разбором слова

aceaacecbecbb

в грамматике из примера 13.1.3 является последовательность$$\begin{multiline*} ( S \tto aSeSb ) ,\ ( S \tto c ) ,\ ( S \tto aSeSb ) ,\\ ( S \tto aSeSb ) ,\ ( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto c ) . \end{multiline*}$$

Определение 13.1.8. Процесс нахождения левого разбора слова w в заданной контекстно-свободной грамматике G называется нисходящим разбором (top-down parsing).

Определение 13.1.9. Вычислительным процессом МП-автомата M будем называть конечную последовательность его конфигураций, каждая из которых (кроме первой) получается из предыдущей одним тактом работы автомата M.

Пример 13.1.10. Рассмотрим МП-автомат$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{ab,\varepsilon:E} \rloop{0,-1} ^{aa,E:\varepsilon} \ar "1,2" <0.6mm> ^{b,\varepsilon:D} *=[o][F=]{2} \ar "1,1" <0.6mm> ^{a,\varepsilon:D} \rloop{0,1} ^{\varepsilon,D:\varepsilon} \rloop{0,-1} ^{b,E:\varepsilon} }$$ из примера 10.2.8. Последовательность$$\begin{multiline*} \lp 1 , bab , \varepsilon \rp ,\ \lp 2 , ab , D \rp ,\ \lp 1 , b , DD \rp ,\ \lp 2 , \varepsilon , DDD \rp ,\\ \lp 2 , \varepsilon , DD \rp ,\ \lp 2 , \varepsilon , D \rp ,\ \lp 2 , \varepsilon , \varepsilon \rp \end{multiline*}$$ является вычислительным процессом этого МП-автомата.

Определение 13.1.11. Если в некотором вычислительном процессе МП-автомата $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ первая конфигурация имеет вид $$\lp s , w , \varepsilon \rp $$, где $$s \in I $$ и $$w \in \Sigma^* $$, а последняя конфигурация имеет вид $$\lp q , \varepsilon , \varepsilon \rp $$, где $$q \in F $$, то будем говорить, что этот вычислительный процесс допускает слово w.

Пример 13.1.12. Вычислительный процесс из примера 13.1.10 допускает слово bab.

Замечание 13.1.13. МП-автомат M допускает слово $$w \in \Sigma^* $$ тогда и только тогда, когда некоторый вычислительный процесс МП-автомата M допускает слово w.

Определение 13.1.14. Протоколом вычислительного процесса МП-Автомата $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ будем называть последовательность переходов, примененных в этом вычислительном процессе. Формально говоря, протоколом вычислительного процесса$$\lp q_0 , w_0 , \alpha_0 \rp ,\ \lp q_1 , w_1 , \alpha_1 \rp ,\ldots ,\ \lp q_n , w_n , \alpha_n \rp$$ является последовательность переходов$$\lp \lp q_0 , x_1 , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp ,\ldots ,\ \lp \lp q_{n-1} , x_n , \beta_n \rp , \lp q_n , \gamma_n \rp \rp ,$$ где для каждого i между 1 и n слово xi определяется равенством $$w_{i-1} = x_i w_i $$, а через $$\beta_i $$ и $$\gamma_i $$ обозначены кратчайшие слова из $$\Gamma^* $$, удовлетворяющие условиям$$\begin{align*} \lp \lp q_{i-1} , x_i , \beta_i \rp , \lp q_i , \gamma_i \rp \rp \in \Delta ,\\ \alpha_{i-1} = \beta_i \zeta ,\\ \alpha_i = \gamma_i \zeta \end{align*}$$ для некоторого слова $$\zeta \in \Gamma ^* $$.

Пример 13.1.15. Протоколом вычислительного процесса из примера 13.1.10 является последовательность$$\begin{multiline*} \lp \lp 1 , b , \varepsilon \rp , \lp 2 , D \rp \rp ,\ \lp \lp 2 , a , \varepsilon \rp , \lp 1 , D \rp \rp ,\ \lp \lp 1 , b , \varepsilon \rp , \lp 2 , D \rp \rp ,\\ \lp \lp 2 , \varepsilon , D \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , D \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , D \rp , \lp 2 , \varepsilon \rp \rp . \end{multiline*}$$

Определение 13.1.16. Для каждой контекстно-свободной грамматики $$G = \lalg N , \Sigma , P , S \ralg $$ обозначим через $$G_\eos $$ контекстно-свободную грамматику $$\lalg N \cup \{ S_\eos \} , \Sigma \cup \{ \eos \} , P_\eos , S_\eos \ralg $$, где $$\eos $$ и $$S_\eos $$ - два различных новых символа, не принадлежащие множеству $$N \cup \Sigma $$, и $$P_\eos = P \cup \{ S_\eos \tto S \eos \} $$. Грамматику $$G_\eos $$ будем называть грамматикой с маркером конца строки. Терминальный алфавит грамматики $$G_\eos $$ (то есть множество $$\Sigma \cup \{ \eos \} $$ ) будем обозначать через $$\Sigma_\eos $$. Нетерминальный алфавит $$N \cup \{ S_\eos \} $$ будем обозначать через $$N_\eos $$.

Пример 13.1.17. Рассмотрим контекстно-свободную грамматику G с терминальным алфавитом $$\Sigma = \{ \trm{m} , \trm{n} , \trm{+} , \trm{-} , \trm{*} , \trm{/} , \trm{(} , \trm{)} , \eos \} $$, вспомогательным алфавитом N = {S,A,B,C} и правилами$$\begin{align*} A \; {\to} \; A \trm{+} B , B \; {\to} \; B \trm{*} C , C \; {\to} \; \trm{(} A \trm{)} , \\ A \; {\to} \; A \trm{-} B , B \; {\to} \; B \trm{/} C , C \; {\to} \; \trm{m} , \\ A \; {\to} \; B , B \; {\to} \; C , C \; {\to} \; \trm{n} . \end{align*}$$ Ей соответствует следующая грамматика $$G_\eos $$ с маркером конца строки:$$\begin{align*} T \; {\to} \; A \eos , B \; {\to} \; B \trm{*} C , C \; {\to} \; \trm{(} A \trm{)} , \\ A \; {\to} \; A \trm{+} B , B \; {\to} \; B \trm{/} C , C \; {\to} \; \trm{m} , \\ A \; {\to} \; A \trm{-} B , B \; {\to} \; C , C \; {\to} \; \trm{n} . \\ A \; {\to} \; B , \end{align*}$$

Замечание 13.1.18. Очевидно, что $$L ( G_\eos ) = L ( G ) \cdot \{ \eos \} $$.

Лемма 13.1.19. Если $$\smash[b]{ S_\eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta \eos \theta } $$, где $$\eta \in \ns ^* $$ и $$\theta \in \ns ^* $$, то $$\theta = \varepsilon $$.

Доказательство. Очевидно, что если $$\smash[b]{ S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \omega } $$, то слово $$\omega $$ не содержит символа $$S_\eos $$.

Теперь докажем индукцией по длине вывода, что если $$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta \eos \theta $$, то $$\theta = \varepsilon $$. Пусть на последнем шаге в этом выводе применялось правило $$( A \tto \alpha ) \in P $$.

Если $$| \alpha |_\eos > 0 $$, то $$A = S_\eos $$, что невозможно (очевидно, что если $$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \omega $$, то слово $$\omega $$ не содержит символа $$S_\eos $$ ).

Если $$| \alpha |_\eos = 0 $$, то рассмотрим два случая. При$$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta_1 A \eta_2 \eos \theta \myunderset{ G_\eos }{\Rightarrow } \eta_1 \alpha \eta_2 \eos \theta$$ равенство $$\theta = \varepsilon $$ обеспечивается предположением индукцией. Случай$$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta \eos \theta_1 A \theta_2 \myunderset{ G_\eos }{\Rightarrow } \eta \eos \theta_1 \alpha \theta_2$$ невозможен, так как предположение индукции дает $$\theta_1 A \theta_2 = \varepsilon $$.

Определение 13.1.20. Пусть даны контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ и МП-автомат $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$. Будем говорить, что МП-автомат M - нисходящий магазинный анализатор (или предсказывающий анализатор, top-down, left-to-right parser, predictive parser) для грамматики G, если $$L ( M ) = L ( G_\eos ) $$ и существует такой гомоморфизм $$r \colon \Delta^* \to P_\eos^* $$, что для каждого вычислительного процесса (МП-автомата M ), допускающего слово $$w \in \Sigma_\eos^* $$, образ протокола этого вычислительного процесса при гомоморфизме $$r $$ является протоколом некоторого левостороннего вывода слова w в грамматике $$G_\eos $$. (При задании гомоморфизма r конечные множества $$\Delta $$ и $$P_\eos $$ рассматриваются как два алфавита.)

Пример 13.1.21. Рассмотрим контекстно-свободную грамматику $$G_\eos $$ из примера 13.1.17. Язык $$L ( G_\eos ) $$ распознается недетерминированным МП-автоматом $$M = \lalg \{ 1 , 2 \} , \Sigma , \Gamma , \Delta , \{ 1 \} , \{ 2 \} \ralg $$, где$$\Gamma = \{ A , B , C , \trm{+} , \trm{-} , \trm{*} , \trm{/} , \trm{)} , \eos \}$$ и$$\begin{align*} {} \Delta = \{ \lp \lp 1 , \varepsilon , \varepsilon \rp , \lp 2 , A \eos \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \varepsilon , A \rp , \lp 2 , A \trm{+} B \rp \rp ,\ \lp \lp 2 , \varepsilon , A \rp , \lp 2 , A \trm{-} B \rp \rp ,\ \lp \lp 2 , \varepsilon , A \rp , \lp 2 , B \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \varepsilon , B \rp , \lp 2 , B \trm{*} C \rp \rp ,\ \lp \lp 2 , \varepsilon , B \rp , \lp 2 , B \trm{/} C \rp \rp ,\ \lp \lp 2 , \varepsilon , B \rp , \lp 2 , C \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{(} , C \rp , \lp 2 , A \trm{)} \rp \rp ,\ \lp \lp 2 , \trm{m} , C \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \trm{n} , C \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{+} , \trm{+} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{-} , \trm{-} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{*} , \trm{*} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{/} , \trm{/} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{)} , \trm{)} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \eos , \eos \rp , \lp 2 , \varepsilon \rp \rp \} . \end{align*}$$ Легко убедиться, что МП-автомат M является нисходящим магазинным анализатором для грамматики G из примера 13.1.17.

Определение 13.1.22. Сентенциальной формой (sentential form) грамматики $$G = \lalg N , \Sigma , P , S \ralg $$ называется любое слово в алфавите $$N \cup \Sigma $$, выводимое из начального символа S.

Пример 13.1.23. Слова S, aSeaceSbb, aceaacecbecbb являются сентенциальными формами грамматики из примера 13.1.3.

Определение 13.1.24. Пусть дана контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$. Определим три функции $$\first_G $$, $$\follow_G $$ и $$\director_G $$, связанные с грамматикой G. Для краткости будем писать просто FIRST, FOLLOW и DIRECTOR.

Функция FIRST ставит в соответствие каждому слову $$\omega \pin \ns ^* $$ множество тех терминальных символов, с которых начинаются слова, выводимые из $$\omega $$, то есть$$\first( \omega ) \bydef \{ b \in \Sigma \mid ( \exists \theta \in \ns ^* ) \, \omega \overstar{\Rightarrow} b \theta \} .$$

Функция FOLLOW ставит в соответствие каждому нетерминальному символу A множество тех терминальных символов, которые могут встречаться в сентенциальных формах непосредственно справа от A, то есть$$\follow( A ) \bydef \{ b \in \Sigma \mid ( \exists \eta \in \ns ^* ) \, ( \exists \theta \in \ns ^* ) \, S \overstar{\Rightarrow} \eta A b \theta \} .$$

Функция DIRECTOR ставит в соответствие каждому правилу $$( A \tto \alpha ) \in P $$ множество терминальных символов, определяемое следующим образом: если $$\alpha \overstar{\Rightarrow} \varepsilon $$, то$$\director( A \tto \alpha ) \bydef \first( \alpha ) \cup \follow( A ) ,$$ иначе$$\director( A \tto \alpha ) \bydef \first( \alpha ) .$$

Пример 13.1.25. Рассмотрим контекстно-свободную грамматику из примера 13.1.3. Очевидно, что$$\begin{align*} \first( c ) = \{ c \} ,\\ \first( dS ) = \{ d \} ,\\ \first( aSeSb ) = \{ a \} ,\\ \follow( S ) = \{ b , e \} ,\\ \director( S \tto c ) = \{ c \} ,\\ \director( S \tto dS ) = \{ d \} ,\\ \director( S \tto aSeSb ) = \{ a \} . \end{align*}$$

Пример 13.1.26. Рассмотрим контекстно-свободную грамматику $$G_\eos $$ из примера 13.1.17. Очевидно, что$$\begin{align*} \director( B \tto C ) = \{ \trm{(} , \trm{m} , \trm{n} \} ,\\ \director( B \tto B \trm{/} C ) = \{ \trm{(} , \trm{m} , \trm{n} \} ,\\ \director( B \tto B \trm{*} C ) = \{ \trm{(} , \trm{m} , \trm{n} \} . \end{align*}$$

Пример 13.1.27. Пусть контекстно-свободная грамматика $$G \peq \lalg N , \Sigma , P , S \ralg $$ не содержит бесполезных символов. Пусть даны правило $$( A \tto \alpha ) \in P $$ и символ $$b \in \Sigma $$. Тогда утверждение$$b \in \director( A \tto \alpha )$$ равносильно тому, что найдутся такие $$x \in \Sigma^* $$, $$y \in \Sigma^* $$ и $$\theta \in \ns ^* $$, что$$S \overstar{\Rightarrow} x A \theta \quad\text{и}\quad x \alpha \theta \overstar{\Rightarrow} x b y .$$

Теорема 13.1.28. Пусть дана контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$. Пусть $$G_\eos = \lalg N_\eos , \Sigma_\eos , P_\eos , S_\eos \ralg $$ - соответствующая контекстно-свободная грамматика с маркером конца строки, приведенная в определении 13.1.16. Обозначим через M МП-автомат $$\lalg Q , \Sigma_\eos , \Gamma , \Delta , \{ \qinitial \} , \{ \varepsilon \} \ralg $$, где$$Q = \{ v \in \Sigma_\eos^* \mid | v | \leq 1 \} \cup \{ \qinitial \} ,$$ $$\qinitial \notin \Sigma_\eos^* $$, $$\Gamma = N_\eos \cup \Sigma_\eos $$ и$$\begin{align*} \Delta = \{ \lp \lp \qinitial , \varepsilon , \varepsilon \rp , \lp \varepsilon , S_\eos \rp \rp \} \cup {} \\ \myqquad \cup \{ \lp \lp \varepsilon , a , \varepsilon \rp , \lp a , \varepsilon \rp \rp \mid a \in \Sigma_\eos \} \cup {} \\ \myqquad \cup \{ \lp \lp a , \varepsilon , a \rp , \lp \varepsilon , \varepsilon \rp \rp \mid a \in \Sigma_\eos \} \cup {} \\ \myqquad \cup \{ \lp \lp b , \varepsilon , A \rp , \lp b , \alpha \rp \rp \mid ( A \tto \alpha ) \in P_\eos ,\ b \in \director_{ G_\eos }( A \tto \alpha ) \} . \end{align*}$$ Тогда МП-автомат M является нисходящим магазинным анализатором для грамматики G.

Доказательство. Индукцией по количеству тактов можно доказать, что если $$\lp v , w , \beta \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$, где $$v \in \Sigma_\eos^* $$, то $$\smash[b]{ \beta \overstar{\myunderset{ G_\eos }{\Rightarrow }} v w } $$. Следовательно, $$L ( M ) \subseteq L ( G_\eos ) $$.

С другой стороны, докажем, что если в грамматике $$G_\eos $$ выводится $$S_\eos \overstar{\lmarrow} u \beta $$ и $$\beta \overstar{\lmarrow} b w $$, где $$u \in \Sigma_\eos^* $$, $$\beta \in \ns ^* $$, $$b \in \Sigma_\eos $$, $$w \in \Sigma_\eos^* $$, то $$\lp b , w , \beta \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$.

Проведем доказательство индукцией по сумме длины слова bw и длины вывода $$\beta \overstar{\lmarrow} b w $$. Случай |bw| = 1, $$\beta = b w $$ образует базис индукции (очевидно, что $$\lp b , \varepsilon , b \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$ ). Проверим теперь шаг индукции. Так как $$\beta \overstar{\Rightarrow} b w $$ и $$b w \neq \varepsilon $$, то $$\beta \neq \varepsilon $$. Если $$\beta = A \theta $$, где $$A \in N $$, то вывод $$\beta \overstar{\lmarrow} b w $$ имеет вид$$A \theta \lmarrow \alpha \theta \overstar{\lmarrow} b w ,$$ где $$( A \tto \alpha ) \in P_\eos $$ и в силу леммы 13.1.27 $$b \in \director_{ G_\eos }( A \tto \alpha ) $$. Отсюда получаем, что $$\lp b , w , A \theta \rp \vdash \lp b , w , \alpha \theta \rp $$, и остается применить предположение индукции для левосторонних выводов $$S_\eos \overstar{\lmarrow} u \alpha \theta $$ и $$\alpha \theta \overstar{\lmarrow} b w $$. Если же $$\beta = a \beta' $$, где $$a \in \Sigma_\eos $$, то, очевидно, a = b и $$\beta' \overstar{\lmarrow} w $$. Если $$w = \varepsilon $$, то $$b = \eos $$ и в силу леммы 13.1.19 $$\beta' = \varepsilon $$, но этот случай уже рассмотрен в базисе индукции. Пусть $$w \neq \varepsilon $$. Тогда w = b'w' для некоторых $$b' \in \Sigma_\eos $$ и $$w' \in \Sigma_\eos^* $$. Обозначим u' = ub. Применяя предположение индукции для левосторонних выводов $$S_\eos \overstar{\lmarrow} u' \beta' $$ и $$\beta' \overstar{\lmarrow} b' w' $$, получаем $$\lp b' , w' , \beta' \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$. Согласно построению МП-автомата M имеем$$\lp b , b' w' , b \beta' \rp \vdash \lp \varepsilon , b' w' , \beta ' \rp \vdash \lp b' , w' , \beta ' \rp .$$ Шаг индукции доказан. Теперь легко проверить, что выполняется $$L ( G_\eos ) \subseteq L ( M ) $$.

Гомоморфизм $$r \colon \Delta^* \to P_\eos^* $$ задается соотношениями$$\begin{align*} r ( \lp \lp b , \varepsilon , A \rp , \lp b , \alpha \rp \rp ) = ( A \tto \beta ) ,\\ r ( \mathfrak{d} ) = \varepsilon \mathspace\text{для остальных}\mathspace \mathfrak{d} \in \Delta . \end{align*}$$

Пример 13.1.29. Рассмотрим контекстно-свободную грамматику из примера 13.1.3. Грамматика с маркером конца строки имеет правила$$\begin{align*} T \; {\to} \; S \eos , \\ S \; {\to} \; c , \\ S \; {\to} \; dS , \\ S \; {\to} \; aSeSb . \end{align}$$ Соответствующий нисходящий магазинный анализатор M, построенный в теореме 13.1.28, имеет приведенный ниже вид.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{a} \ar "2,3" <0.6mm> ^{\varepsilon,a:\varepsilon} \rloop{-1,0} ^{\varepsilon,T:S\boldsymbol{\$}} \rloop{0,1} ^{\varepsilon,S:aSeSb} *=[o][F-]{b} \ar "2,3" <0.6mm> ^{\varepsilon,b:\varepsilon} *=[o][F-]{c} \ar "2,3" <0.6mm> ^{\varepsilon,c:\varepsilon} \rloop{1,0} ^{\varepsilon,T:S\boldsymbol{\$}} \rloop{0,1} ^{\varepsilon,S:c} \\ *=[o][F-]{q_{\textrm{s}}} \ar @`{+/l16mm/} [] ^{} \ar "2,3" ^{\varepsilon,\varepsilon:T} *=[o][F=]{\varepsilon} \ar "1,1" <0.6mm> ^{a,\varepsilon:\varepsilon} \ar "1,3" <0.6mm> ^{b,\varepsilon:\varepsilon} \ar "1,5" <0.6mm> ^{c,\varepsilon:\varepsilon} \ar "3,5" <0.6mm> ^{d,\varepsilon:\varepsilon} \ar "3,3" <0.6mm> ^{e,\varepsilon:\varepsilon} \ar "3,1" <0.6mm> ^{\boldsymbol{\$},\varepsilon:\varepsilon} \\ *=[o][F-]{\boldsymbol{\$}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{\$}:\varepsilon} *=[o][F-]{e} \ar "2,3" <0.6mm> ^{\varepsilon,e:\varepsilon} *=[o][F-]{d} \ar "2,3" <0.6mm> ^{\varepsilon,d:\varepsilon} \rloop{1,0} ^{\varepsilon,T:S\boldsymbol{\$}} \rloop{0,-1} ^{\varepsilon,S:dS} }$$

Определение 13.1.30. Контекстно-свободная грамматика $$G \peq \lalg N , \Sigma , P , S \ralg $$ принадлежит классу LL(1), если для любых двух правил $$( A \tto \alpha ) \in P_\eos $$ и $$( A \tto \beta ) \in P_\eos $$, где $$\alpha \neq \beta $$, множества $$\director_{ G_\eos }( A \tto \alpha ) $$ и $$\director_{ G_\eos }( A \tto \beta ) $$ не пересекаются.

Замечание 13.1.31. Первая буква L в названии класса LL(1) означает, что входное слово читается слева направо (left-to-right). Вторая буква L означает, что строится левосторонний вывод (leftmost derivation). Число 1 указывает на то, что на каждом шаге для принятия решения используется один символ неразобранной части входного слова.

Пример 13.1.32. Грамматика из примера 13.1.3 принадлежит классу LL(1), а грамматика из примера 3.1.17 этому классу не принадлежит.

Теорема 13.1.33. МП-автомат M, построенный в теореме 13.1.28 по контекстно-свободной грамматике G, является детерминированным тогда и только тогда, когда грамматика G принадлежит классу LL(1).

Теорема 13.1.34. Грамматики из класса LL(1) порождают только детерминированные контекстно-свободные языки.

Теорема 13.1.35. Пусть контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ не содержит бесполезных символов. Система множеств $$\first( \omega ) $$ (где $$\omega \in \ns ^* $$ ) состоит из наименьших ( по включению ) множеств, удовлетворяющих следующим условиям:

  • если $$\phi \overstar{\Rightarrow} \varepsilon $$, то $$b \in \first( \phi b \psi ) $$ для всех $$b \in \Sigma $$ и $$\psi \in \ns ^* $$ ;
  • если $$\phi \overstar{\Rightarrow} \varepsilon $$, то $$\first( A ) \subseteq \first( \phi A \psi ) $$ для всех $$A \in N $$ и $$\psi \in \ns ^* $$ ;
  • если $$( A \tto \alpha ) \in P $$, то $$\first( \alpha ) \subseteq \first( A ) $$.
    •

    Теорема 13.1.36. Пусть контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ не содержит бесполезных символов. Система множеств $$\follow( A ) $$ ( где $$A \in N $$ ) состоит из наименьших ( по включению ) множеств, удовлетворяющих следующим условиям:

  • если $$B \in N $$ и $$( A \tto \phi B \psi ) \in P $$, то $$\first( \psi ) \subseteq \follow( B ) $$ ;
  • если $$B \in N $$, $$( A \tto \phi B \psi ) \in P $$ и $$\psi \overstar{\Rightarrow} \varepsilon $$, то$$\follow( A ) \subseteq \follow( B ) .$$

    • Замечание 13.1.37. Теоремы 13.1.35 и 13.1.36 дают алгоритм проверки принадлежности контекстно-свободной грамматики G классу LL(1). Можно предположить, что грамматика G не содержит бесполезных символов (их можно устранить).

    Сначала необходимо вычислить значения $$\first_{ G_\eos }( \omega ) $$ параллельно для всех слов $$\omega $$, являющихся суффиксами правых частей правил грамматики $$G_\eos $$. Для этого постепенно пополняем множества $$\first_{ G_\eos }( \omega ) $$ (начав с пустых множеств), используя условия, приведенные в теореме 13.1.35.

    Затем необходимо вычислить значения $$\follow_{ G_\eos }( A ) $$ параллельно для всех вспомогательных символов A. Для этого постепенно пополняем множества $$\follow_{ G_\eos }( A ) $$ (начав с пустых множеств), используя условия, приведенные в теореме 13.1.35.

    В заключение вычислим значения $$\director_{ G_\eos }( A \tto \alpha ) $$ для всех правил $$A \tto \alpha $$, следуя определению функции $$\director $$, и проверим условия из определения 13.1.30.

    Теорема 13.1.38. Пусть даны контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ и символ $$A \in N $$. Пусть$$P = P_0 \cup \{ A \tto A \alpha_1 , \ldots , A \tto A \alpha_n , A \tto \beta_1 , \ldots , A \tto \beta_m \} ,$$ где множество P0 не содержит правил с левой частью A и ни одно из слов $$\beta_1 , \ldots , \beta_m $$ не начинается с символа A. Тогда грамматика G эквивалентна контекстно-свободной грамматике $$G' = \lalg N \cup \{ A' \} , \Sigma , P' , S \ralg $$, где A' - новый символ, не принадлежащий множеству $$N \cup \Sigma $$, и$$P' = P_0 \cup \{ A \squeeze{\tto} \beta_1 A' , \ldots , A \squeeze{\tto} \beta_m A' , A' \squeeze{\tto} A' \alpha_1 , \ldots , A' \squeeze{\tto} A' \alpha_n , A' \squeeze{\tto} \varepsilon \} .$$

    Пример 13.1.39. Если к контекстно-свободной грамматике $$G_\eos $$ из примера 13.1.17 два раза применить преобразование из теоремы 13.1.38 (для вспомогательного символа A и для вспомогательного символа B ), то получим эквивалентную грамматику G' с правилами$$\begin{align*} S \; {\to} \; A \eos , B \; {\to} \; C D , C \; {\to} \; \trm{(} A \trm{)} , \\ A \; {\to} \; B E , D \; {\to} \; \trm{*} C D , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \trm{+} B E , D \; {\to} \; \trm{/} C D , C \; {\to} \; \trm{n} . \\ E \; {\to} \; \trm{-} B E , D \; {\to} \; \varepsilon , \\ E \; {\to} \; \varepsilon , \end{align*}$$ После упрощения получаем грамматику G'' с правилами$$\begin{align*} S \; {\to} \; A \eos , D \; {\to} \; \trm{*} C D , C \; {\to} \; \trm{(} C D E \trm{)} , \\ A \; {\to} \; C D E , D \; {\to} \; \trm{/} C D , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \trm{+} C D E , D \; {\to} \; \varepsilon , C \; {\to} \; \trm{n} . \\ E \; {\to} \; \trm{-} C D E , \\ E \; {\to} \; \varepsilon , \end{align*}$$ Язык L(G'') распознается детерминированным МП-автоматом $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$, где $$Q = \{ \qinitial , \varepsilon \} $$, $$\Gamma = \{ C , E , D , \trm{)} , \eos \} $$, $$I = \{ \qinitial \} $$, $$F = \{ \varepsilon \} $$ и$$\begin{align*} {} \Delta=\{ \lp\lp\qinitial,\varepsilon,\varepsilon\rp, \lp\varepsilon,CDE\eos\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{*},D\rp, \lp\varepsilon,CD\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{/},D\rp, \lp\varepsilon,CD\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{+},DE\rp, \lp\varepsilon,CDE\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{-},DE\rp, \lp\varepsilon,CDE\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{)},DE\trm{)}\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\eos,DE\eos\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{m},C\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{n},C\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{(},C\rp, \lp\varepsilon,CDE\trm{)}\rp\rp \}. \end{align*}$$ Можно доказать, что МП-автомат M является нисходящим магазинным анализатором для грамматики$$\begin{align*} A \; {\to} \; C D E , D \; {\to} \; \trm{*} C D , C \; {\to} \; \trm{(} C D E \trm{)} , \\ E \; {\to} \; \trm{+} C D E , D \; {\to} \; \trm{/} C D , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \trm{-} C D E , D \; {\to} \; \varepsilon , C \; {\to} \; \trm{n} . \\ E \; {\to} \; \varepsilon , \end{align*}$$

    Пример 13.1.40. Пусть $$\Sigma = \{ \trm{m} , \trm{n} , \trm{-} , \trm{*} \} $$ и $$N = \{ A , B , C \} $$. Рассмотрим контекстно-свободную грамматику G с правилами$$\begin{align*} A \; {\to} \; C D E , D \; {\to} \; \trm{*} C D , \\ E \; {\to} \; \trm{-} C D E , D \; {\to} \; \varepsilon , \\ E \; {\to} \; \varepsilon , C \; {\to} \; \trm{m} , \\ C \; {\to} \; \trm{n} . \end{align*}$$ Грамматика с маркером конца строки имеет правила$$\begin{align*} T \; {\to} \; A \eos , D \; {\to} \; \trm{*} C D , \\ A \; {\to} \; C D E , D \; {\to} \; \varepsilon , \\ E \; {\to} \; \trm{-} C D E , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \varepsilon , C \; {\to} \; \trm{n} . \end{align*}$$ Соответствующий нисходящий магазинный анализатор M, построенный в теореме 13.1.28, имеет приведенный ниже вид.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{\boldsymbol{m}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{m}:\varepsilon} \rloop{0,-1} ^{\varepsilon,T:A\boldsymbol{\$}} \rloop{-1,0} ^{\varepsilon,A:CDE} \rloop{0,1} ^{\varepsilon,C:\boldsymbol{m}} *=[o][F-]{q_{\textrm{s}}} \ar @`{+/l16mm/} [] ^{} \ar "2,3" ^{\varepsilon,\varepsilon:T} *=[o][F-]{\boldsymbol{\$}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{\$}:\varepsilon} \rloop{1,0} ^{\varepsilon,D:\varepsilon} \rloop{0,-1} ^{\varepsilon,E:\varepsilon} \\ % *=[o][F=]{\varepsilon} \ar "1,1" <0.6mm> ^{\boldsymbol{m},\varepsilon:\varepsilon} \ar "3,1" <0.6mm> ^{\boldsymbol{n},\varepsilon:\varepsilon} \ar "3,3" <0.6mm> ^{\boldsymbol{*},\varepsilon:\varepsilon} \ar "3,5" <0.6mm> ^{\boldsymbol{-},\varepsilon:\varepsilon} \ar "1,5" <0.6mm> ^{\boldsymbol{\$},\varepsilon:\varepsilon} \\ *=[o][F-]{\boldsymbol{n}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{n}:\varepsilon} \rloop{0,-1} ^{\varepsilon,T:A\boldsymbol{\$}} \rloop{-1,0} ^{\varepsilon,A:CDE} \rloop{0,1} ^{\varepsilon,C:\boldsymbol{n}} *=[o][F-]{\boldsymbol{*}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{*}:\varepsilon} \rloop{0,-1} ^{\varepsilon,D:\boldsymbol{*}CD} *=[o][F-]{\boldsymbol{-}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{-}:\varepsilon} \rloop{1,0} ^{\varepsilon,D:\varepsilon} \rloop{0,-1} ^{\varepsilon,E:\boldsymbol{-}CDE} }$$ Легко убедиться, что грамматика G принадлежит классу LL(1) и МП-автомат M является детерминированным.

    Упражнение 13.1.41. Существует ли детерминированный нисходящий магазинный анализатор для грамматики$$\begin{align*} S \; {\to} \; bScS , \\ S \; {\to} \; bS , \\ S \; {\to} \; a ? \end{align*}$$

    Упражнение 13.1.42. Принадлежит ли грамматика$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; bS , \\ S \; {\to} \; cSS \end{align*}$$ классу LL(1)?

    Упражнение 13.1.43. Принадлежит ли грамматика$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; Sb , \\ S \; {\to} \; SSc \end{align*}$$ классу LL(1)?

    13.2. Восходящий разбор

    Определение 13.2.1. Протоколом правостороннего вывода в контекстно-свободной грамматике $$G = \lalg N , \Sigma , P , S \ralg $$ будем называть обращенную последовательность правил, примененных в этом выводе. Формально говоря, протоколом правостороннего вывода$$\omega_0 , \omega_1 , \ldots , \omega_n$$ является последовательность$$( A_1 \tto \alpha_1 ) , \ldots , ( A_n \tto \alpha_n ) ,$$ где для каждого i<n, если $$\omega_i = \eta B v $$ и $$\omega_{i+1} = \eta \beta v $$ для некоторых $$\eta \in \ns ^* $$, $$B \in N $$, $$v \in \Sigma^* $$, $$\beta \in \ns ^* $$, то An-i = B и $$\alpha_{n-i} = \beta $$.

    Пример 13.2.2. Рассмотрим контекстно-свободную грамматику$$\begin{align*} S \; {\to} \; c\\ S \; {\to} \; dS\\ S \; {\to} \; aSeSb \end{align*}$$ и дерево вывода$$\xymatrix @=6pt { S\ar[ddllll]\ar[ddll]\ar[dd]\ar[ddrr]\ar[ddrrrr] \\ \\ a S\ar[dd] e S\ar[ddl]\ar[ddr] b \\ \\ c d S\ar[dd] \\ \\ c }$$ из примера 13.1.3. Этому дереву вывода соответствует правосторонний вывод$$S \pRightarrow aSeSb \pRightarrow aSedSb \pRightarrow aSedcb \pRightarrow acedcb .$$ Протоколом этого вывода является последовательность$$( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto dS ) ,\ ( S \tto aSeSb ) .$$

    Лемма 13.2.3. Разным правосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

    Протокол правостороннего вывода в контекстно-свободной грамматике является естественным описанием соответствующего дерева вывода в порядке постфиксного обхода (postorder traversal). (Постфиксный обход упорядоченного дерева можно определить рекурсивно так: сначала выполняется постфиксный обход первого непосредственного потомка корня, затем второго и т. д., а в самом конце посещается корень дерева.)

    Например, протокол правостороннего вывода из примера 13.2.2 задает процесс постепенного конструирования дерева вывода, изображенный ниже.$$\newcommand{\rb}[1]{\raisebox{0pt}[8pt]{$ #1 $}} \entrymodifiers={=<3.3mm>[o]} \xymatrix @=0mm { \boldsymbol{S}\ar[ddddll] \\ \\ \\ \\ \rb{\boldsymbol{a}} \rb{c} \\%} \\ %\xymatrix @=0mm { \boldsymbol{S}\ar[ddddll] \\ \\ \boldsymbol{S}\ar[ddr] \\ \\ \rb{\boldsymbol{a}} \rb{c} \rb{\boldsymbol{e}} \rb{\boldsymbol{d}} \rb{c} \\%} \\ %\xymatrix @=0mm { \boldsymbol{S}\ar[ddddll] \boldsymbol{S}\ar[dddd]\ar[ddr] \\ \\ S\ar[ddr] \\ \\ \rb{\boldsymbol{a}} \rb{c} \rb{\boldsymbol{e}} \rb{d} \rb{c} \\%} \\ %\xymatrix @=0mm { \boldsymbol{S}\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm> \\ \\ S\ar[ddddll] S\ar[dddd]\ar[ddr] \\ \\ S\ar[ddr] \\ \\ \rb{a} \rb{c} \rb{e} \rb{d} \rb{c} \rb{b} }$$

    Определение 13.2.5. Правым разбором (right parse) слова w в контекстно-свободной грамматике G называется протокол любого правостороннего вывода слова w в грамматике G.

    Пример 13.2.6. Правым разбором слова aceaacecbecbb в грамматике из примера 13.2.2 является последовательность$$\begin{multiline*} ( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto aSeSb ) ,\\ ( S \tto c ) ,\ ( S \tto aSeSb ) ,\ ( S \tto aSeSb ) . \end{multiline*}$$

    Определение 13.2.7. Процесс нахождения правого разбора слова w в~заданной контекстно-свободной грамматике G называется восходящим разбором (bottom-up parsing).

    Определение 13.2.8. Пусть даны контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ и МП-автомат $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$. Будем говорить, что МП-автомат M - восходящий магазинный анализатор (bottom-up, left-to-right parser) для грамматики G, если $$L ( M ) = L ( G_\eos ) $$ и существует такой гомоморфизм $$r \colon \Delta^* \to P_\eos^* $$, что для каждого вычислительного процесса (МП-автомата M ), допускающего слово $$w \in \Sigma_\eos^* $$, образ протокола этого вычислительного процесса при гомоморфизме r является протоколом некоторого правостороннего вывода слова w в грамматике $$G_\eos $$.

    Пример 13.2.9. Рассмотрим контекстно-свободную грамматику $$G_\eos $$ из примера 13.1.17. Язык $$L ( G_\eos ) $$ распознается недетерминированным МП-автоматом $$M = \lalg \{ 1 , 2 \} , \Sigma , \Gamma , \Delta , \{ 1 \} , \{ 2 \} \ralg $$, где$$\Gamma = \{ A , B , C , \trm{+} , \trm{-} , \trm{*} , \trm{/} , \trm{(} \}$$ и$$\begin{align*} {} \Delta=\{ \lp\lp1,\trm{+},\varepsilon\rp, \lp1,\trm{+}\rp\rp,\ \lp\lp1,\trm{-},\varepsilon\rp, \lp1,\trm{-}\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\trm{*},\varepsilon\rp, \lp1,\trm{*}\rp\rp,\ \lp\lp1,\trm{/},\varepsilon\rp, \lp1,\trm{/}\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\trm{(},\varepsilon\rp, \lp1,\trm{(}\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\varepsilon,B\trm{+}A\rp, \lp1,A\rp\rp,\ \lp\lp1,\varepsilon,B\trm{-}A\rp, \lp1,A\rp\rp,\ \lp\lp1,\varepsilon,B\rp, \lp1,A\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\varepsilon,C\trm{*}B\rp, \lp1,B\rp\rp,\ \lp\lp1,\varepsilon,C\trm{/}B\rp, \lp1,B\rp\rp,\ \lp\lp1,\varepsilon,C\rp, \lp1,B\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\trm{)},A\trm{(}\rp, \lp1,C\rp\rp,\ \lp\lp1,\trm{m},\varepsilon\rp, \lp1,C\rp\rp,\ \lp\lp1,\trm{n},\varepsilon\rp, \lp1,C\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\eos,A\rp, \lp2,\varepsilon\rp\rp \}. \end{align*}$$ Можно проверить, что МП-автомат M является восходящим магазинным анализатором для грамматики G из примера 13.1.17.

    Определение 13.2.10. Контекстно-свободная грамматика $$G \peq \lalg N , \Sigma , P , S \ralg $$ принадлежит классу LR(1), если для любых $$\eta_1 \in ( N_\eos \cup \Sigma_\eos )^* $$, $$\eta_2 \in ( N_\eos \cup \Sigma_\eos )^* $$, $$A_1 \in N_\eos \cup \Sigma_\eos $$, $$A_2 \in N_\eos \cup \Sigma_\eos $$, $$b \in \Sigma_\eos $$, $$v_1 \in \Sigma_\eos^* $$, $$v_2 \in \Sigma_\eos^* $$, $$\alpha_1 \in ( N_\eos \cup \Sigma_\eos )^* $$, $$\alpha_2 \in ( N_\eos \cup \Sigma_\eos )^* $$ из условий$$\begin{align*} S_\eos \overstar{\rmarrow} \eta_1 A_1 b v_1 ,\\ S_\eos \overstar{\rmarrow} \eta_2 A_2 b v_2 ,\\ ( A_1 \tto \alpha_1 ) \in P_\eos ,\\ ( A_2 \tto \alpha_2 ) \in P_\eos ,\\ \eta_1 \alpha_1 = \eta_2 \alpha_2 \end{align*}$$ следует, что A1 = A2 и $$\alpha_1 = \alpha_2 $$.

    Замечание 13.2.11. Классу LR(1) принадлежат те языки, для которых возможен восходящий разбор слова при чтении слева направо с заглядыванием на один символ вперед.

    Замечание 13.2.12. Буква L в названии класса LR(1) означает, что входное слово читается слева направо (left-to-right). Буква R означает, что строится правосторонний вывод (rightmost derivation). Число 1 указывает на то, что на каждом шаге для принятия решения используется один символ неразобранной части входного слова.

    Теорема 13.2.13. Для каждой грамматики из класса LR(1) существует детерминированный восходящий магазинный анализатор.

    Доказательство можно найти в [2, с. 420-447].

    Теорема 13.2.14. Грамматики из класса LR(1) порождают только детерминированные контекстно-свободные языки.

    Теорема 13.2.15. Каждая грамматика из класса LL(1) принадлежит также классу LR(1).

    Упражнение 13.2.16. Найти все правые разборы слова bbacba в грамматике$$\begin{align*} S \; {\to} \; bScS , \\ S \; {\to} \; bS , \\ S \; {\to} \; a . \end{align*}$$

    Упражнение 13.2.17. Найти детерминированный восходящий магазинный анализатор для грамматики$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; Sb , \\ S \; {\to} \; SSc . \end{align*}$$

    Упражнение 13.2.18. Найти детерминированный восходящий магазинный анализатор для грамматики$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; bS , \\ S \; {\to} \; cSS . \end{align*}$$

    Страницы:

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

    13.1. Нисходящий разбор

    Определение 13.1.1. Процесс нахождения дерева вывода слова w в заданной контекстно-свободной грамматике называется синтаксическим разбором или синтаксическим анализом (parsing).

    Определение 13.1.2. Протоколом левостороннего вывода в контекстно-свободной грамматике $$G = \lalg N , \Sigma , P , S \ralg $$ будем называть последовательность правил, примененных в этом выводе. Формально говоря, протоколом левостороннего вывода$$\omega_0 , \omega_1 , \ldots , \omega_n$$ является последовательность$$( A_1 \tto \alpha_1 ) , \ldots , ( A_n \tto \alpha_n ) ,$$ где для каждого i < n, если $$\omega_i = u B \theta $$ и $$\omega_{i+1} = u \beta \theta $$ для некоторых $$u \in \Sigma^* $$, $$B \in N $$, $$\theta \in \ns ^* $$, $$\beta \in \ns ^* $$, то Ai+1 = B и $$\alpha_{i+1} = \beta $$.

    Пример 13.1.3. Рассмотрим контекстно-свободную грамматику$$\begin{align*} S \; {\to} \; c , \\ S \; {\to} \; dS , \\ S \; {\to} \; aSeSb . \end{align*}$$ Дереву вывода$$\xymatrix @=6pt { S\ar[ddllll]\ar[ddll]\ar[dd]\ar[ddrr]\ar[ddrrrr] \\ \\ a S\ar[dd] e S\ar[ddl]\ar[ddr] b \\ \\ c d S\ar[dd] \\ \\ c }$$ соответствует левосторонний вывод$$S \pRightarrow aSeSb \pRightarrow aceSb \pRightarrow acedSb \pRightarrow acedcb .$$ Протоколом этого вывода является последовательность$$( S \to aSeSb ) ,\ ( S \to c ) ,\ ( S \to dS ) ,\ ( S \to c ) .$$

    Лемма 13.1.4. Разным левосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

    Замечание 13.1.5. Протокол левостороннего вывода в контекстно-свободной грамматике является естественным описанием соответствующего дерева вывода в порядке префиксного обхода (preorder traversal). (При префиксном обходе упорядоченного дерева первым посещается корень этого дерева, затем выполняется префиксный обход первого непосредственного потомка корня, затем второго и т. д.)

    Например, протокол левостороннего вывода из примера 13.1.3 задает процесс постепенного конструирования дерева вывода, изображенный ниже.$$\newcommand{\rb}[1]{\raisebox{0pt}[8pt]{$#1$}} \entrymodifiers={=<3.3mm>[o]} \xymatrix@=0mm{ \boldsymbol{S} \\ \\ \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ \boldsymbol{S}\boldsymbol{S}\\ \\ \\ \\ \rb{a}\rb{\boldsymbol{e}}\rb{\boldsymbol{b}} \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ S\ar[ddddll]\boldsymbol{S}\\ \\ \\ \\ \rb{a}\rb{c}\rb{e}\rb{\boldsymbol{b}} \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ S\ar[ddddll]S\ar[dddd]\ar[ddr]\\ \\ \boldsymbol{S}\\ \\ \rb{a}\rb{c}\rb{e}\rb{d}\rb{\boldsymbol{b}} \\ \\ S\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm>\\ \\ S\ar[ddddll]S\ar[dddd]\ar[ddr]\\ \\ S\ar[ddr]\\ \\ \rb{a}\rb{c}\rb{e}\rb{d}\rb{c}\rb{b} }$$

    Определение 13.1.6. Левым разбором (left parse) слова w в контекстно-свободной грамматике G называется протокол любого левостороннего вывода слова w в грамматике G.

    Пример 13.1.7. Левым разбором слова

    aceaacecbecbb

    в грамматике из примера 13.1.3 является последовательность$$\begin{multiline*} ( S \tto aSeSb ) ,\ ( S \tto c ) ,\ ( S \tto aSeSb ) ,\\ ( S \tto aSeSb ) ,\ ( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto c ) . \end{multiline*}$$

    Определение 13.1.8. Процесс нахождения левого разбора слова w в заданной контекстно-свободной грамматике G называется нисходящим разбором (top-down parsing).

    Определение 13.1.9. Вычислительным процессом МП-автомата M будем называть конечную последовательность его конфигураций, каждая из которых (кроме первой) получается из предыдущей одним тактом работы автомата M.

    Пример 13.1.10. Рассмотрим МП-автомат$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{ab,\varepsilon:E} \rloop{0,-1} ^{aa,E:\varepsilon} \ar "1,2" <0.6mm> ^{b,\varepsilon:D} *=[o][F=]{2} \ar "1,1" <0.6mm> ^{a,\varepsilon:D} \rloop{0,1} ^{\varepsilon,D:\varepsilon} \rloop{0,-1} ^{b,E:\varepsilon} }$$ из примера 10.2.8. Последовательность$$\begin{multiline*} \lp 1 , bab , \varepsilon \rp ,\ \lp 2 , ab , D \rp ,\ \lp 1 , b , DD \rp ,\ \lp 2 , \varepsilon , DDD \rp ,\\ \lp 2 , \varepsilon , DD \rp ,\ \lp 2 , \varepsilon , D \rp ,\ \lp 2 , \varepsilon , \varepsilon \rp \end{multiline*}$$ является вычислительным процессом этого МП-автомата.

    Определение 13.1.11. Если в некотором вычислительном процессе МП-автомата $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ первая конфигурация имеет вид $$\lp s , w , \varepsilon \rp $$, где $$s \in I $$ и $$w \in \Sigma^* $$, а последняя конфигурация имеет вид $$\lp q , \varepsilon , \varepsilon \rp $$, где $$q \in F $$, то будем говорить, что этот вычислительный процесс допускает слово w.

    Пример 13.1.12. Вычислительный процесс из примера 13.1.10 допускает слово bab.

    Замечание 13.1.13. МП-автомат M допускает слово $$w \in \Sigma^* $$ тогда и только тогда, когда некоторый вычислительный процесс МП-автомата M допускает слово w.

    Определение 13.1.14. Протоколом вычислительного процесса МП-Автомата $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$ будем называть последовательность переходов, примененных в этом вычислительном процессе. Формально говоря, протоколом вычислительного процесса$$\lp q_0 , w_0 , \alpha_0 \rp ,\ \lp q_1 , w_1 , \alpha_1 \rp ,\ldots ,\ \lp q_n , w_n , \alpha_n \rp$$ является последовательность переходов$$\lp \lp q_0 , x_1 , \beta_1 \rp , \lp q_1 , \gamma_1 \rp \rp ,\ldots ,\ \lp \lp q_{n-1} , x_n , \beta_n \rp , \lp q_n , \gamma_n \rp \rp ,$$ где для каждого i между 1 и n слово xi определяется равенством $$w_{i-1} = x_i w_i $$, а через $$\beta_i $$ и $$\gamma_i $$ обозначены кратчайшие слова из $$\Gamma^* $$, удовлетворяющие условиям$$\begin{align*} \lp \lp q_{i-1} , x_i , \beta_i \rp , \lp q_i , \gamma_i \rp \rp \in \Delta ,\\ \alpha_{i-1} = \beta_i \zeta ,\\ \alpha_i = \gamma_i \zeta \end{align*}$$ для некоторого слова $$\zeta \in \Gamma ^* $$.

    Пример 13.1.15. Протоколом вычислительного процесса из примера 13.1.10 является последовательность$$\begin{multiline*} \lp \lp 1 , b , \varepsilon \rp , \lp 2 , D \rp \rp ,\ \lp \lp 2 , a , \varepsilon \rp , \lp 1 , D \rp \rp ,\ \lp \lp 1 , b , \varepsilon \rp , \lp 2 , D \rp \rp ,\\ \lp \lp 2 , \varepsilon , D \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , D \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \varepsilon , D \rp , \lp 2 , \varepsilon \rp \rp . \end{multiline*}$$

    Определение 13.1.16. Для каждой контекстно-свободной грамматики $$G = \lalg N , \Sigma , P , S \ralg $$ обозначим через $$G_\eos $$ контекстно-свободную грамматику $$\lalg N \cup \{ S_\eos \} , \Sigma \cup \{ \eos \} , P_\eos , S_\eos \ralg $$, где $$\eos $$ и $$S_\eos $$ - два различных новых символа, не принадлежащие множеству $$N \cup \Sigma $$, и $$P_\eos = P \cup \{ S_\eos \tto S \eos \} $$. Грамматику $$G_\eos $$ будем называть грамматикой с маркером конца строки. Терминальный алфавит грамматики $$G_\eos $$ (то есть множество $$\Sigma \cup \{ \eos \} $$ ) будем обозначать через $$\Sigma_\eos $$. Нетерминальный алфавит $$N \cup \{ S_\eos \} $$ будем обозначать через $$N_\eos $$.

    Пример 13.1.17. Рассмотрим контекстно-свободную грамматику G с терминальным алфавитом $$\Sigma = \{ \trm{m} , \trm{n} , \trm{+} , \trm{-} , \trm{*} , \trm{/} , \trm{(} , \trm{)} , \eos \} $$, вспомогательным алфавитом N = {S,A,B,C} и правилами$$\begin{align*} A \; {\to} \; A \trm{+} B , B \; {\to} \; B \trm{*} C , C \; {\to} \; \trm{(} A \trm{)} , \\ A \; {\to} \; A \trm{-} B , B \; {\to} \; B \trm{/} C , C \; {\to} \; \trm{m} , \\ A \; {\to} \; B , B \; {\to} \; C , C \; {\to} \; \trm{n} . \end{align*}$$ Ей соответствует следующая грамматика $$G_\eos $$ с маркером конца строки:$$\begin{align*} T \; {\to} \; A \eos , B \; {\to} \; B \trm{*} C , C \; {\to} \; \trm{(} A \trm{)} , \\ A \; {\to} \; A \trm{+} B , B \; {\to} \; B \trm{/} C , C \; {\to} \; \trm{m} , \\ A \; {\to} \; A \trm{-} B , B \; {\to} \; C , C \; {\to} \; \trm{n} . \\ A \; {\to} \; B , \end{align*}$$

    Замечание 13.1.18. Очевидно, что $$L ( G_\eos ) = L ( G ) \cdot \{ \eos \} $$.

    Лемма 13.1.19. Если $$\smash[b]{ S_\eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta \eos \theta } $$, где $$\eta \in \ns ^* $$ и $$\theta \in \ns ^* $$, то $$\theta = \varepsilon $$.

    Доказательство. Очевидно, что если $$\smash[b]{ S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \omega } $$, то слово $$\omega $$ не содержит символа $$S_\eos $$.

    Теперь докажем индукцией по длине вывода, что если $$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta \eos \theta $$, то $$\theta = \varepsilon $$. Пусть на последнем шаге в этом выводе применялось правило $$( A \tto \alpha ) \in P $$.

    Если $$| \alpha |_\eos > 0 $$, то $$A = S_\eos $$, что невозможно (очевидно, что если $$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \omega $$, то слово $$\omega $$ не содержит символа $$S_\eos $$ ).

    Если $$| \alpha |_\eos = 0 $$, то рассмотрим два случая. При$$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta_1 A \eta_2 \eos \theta \myunderset{ G_\eos }{\Rightarrow } \eta_1 \alpha \eta_2 \eos \theta$$ равенство $$\theta = \varepsilon $$ обеспечивается предположением индукцией. Случай$$S \eos \overstar{\myunderset{ G_\eos }{\Rightarrow }} \eta \eos \theta_1 A \theta_2 \myunderset{ G_\eos }{\Rightarrow } \eta \eos \theta_1 \alpha \theta_2$$ невозможен, так как предположение индукции дает $$\theta_1 A \theta_2 = \varepsilon $$.

    Определение 13.1.20. Пусть даны контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ и МП-автомат $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$. Будем говорить, что МП-автомат M - нисходящий магазинный анализатор (или предсказывающий анализатор, top-down, left-to-right parser, predictive parser) для грамматики G, если $$L ( M ) = L ( G_\eos ) $$ и существует такой гомоморфизм $$r \colon \Delta^* \to P_\eos^* $$, что для каждого вычислительного процесса (МП-автомата M ), допускающего слово $$w \in \Sigma_\eos^* $$, образ протокола этого вычислительного процесса при гомоморфизме $$r $$ является протоколом некоторого левостороннего вывода слова w в грамматике $$G_\eos $$. (При задании гомоморфизма r конечные множества $$\Delta $$ и $$P_\eos $$ рассматриваются как два алфавита.)

    Пример 13.1.21. Рассмотрим контекстно-свободную грамматику $$G_\eos $$ из примера 13.1.17. Язык $$L ( G_\eos ) $$ распознается недетерминированным МП-автоматом $$M = \lalg \{ 1 , 2 \} , \Sigma , \Gamma , \Delta , \{ 1 \} , \{ 2 \} \ralg $$, где$$\Gamma = \{ A , B , C , \trm{+} , \trm{-} , \trm{*} , \trm{/} , \trm{)} , \eos \}$$ и$$\begin{align*} {} \Delta = \{ \lp \lp 1 , \varepsilon , \varepsilon \rp , \lp 2 , A \eos \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \varepsilon , A \rp , \lp 2 , A \trm{+} B \rp \rp ,\ \lp \lp 2 , \varepsilon , A \rp , \lp 2 , A \trm{-} B \rp \rp ,\ \lp \lp 2 , \varepsilon , A \rp , \lp 2 , B \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \varepsilon , B \rp , \lp 2 , B \trm{*} C \rp \rp ,\ \lp \lp 2 , \varepsilon , B \rp , \lp 2 , B \trm{/} C \rp \rp ,\ \lp \lp 2 , \varepsilon , B \rp , \lp 2 , C \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{(} , C \rp , \lp 2 , A \trm{)} \rp \rp ,\ \lp \lp 2 , \trm{m} , C \rp , \lp 2 , \varepsilon \rp \rp ,\ \lp \lp 2 , \trm{n} , C \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{+} , \trm{+} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{-} , \trm{-} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{*} , \trm{*} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{/} , \trm{/} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \trm{)} , \trm{)} \rp , \lp 2 , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp 2 , \eos , \eos \rp , \lp 2 , \varepsilon \rp \rp \} . \end{align*}$$ Легко убедиться, что МП-автомат M является нисходящим магазинным анализатором для грамматики G из примера 13.1.17.

    Определение 13.1.22. Сентенциальной формой (sentential form) грамматики $$G = \lalg N , \Sigma , P , S \ralg $$ называется любое слово в алфавите $$N \cup \Sigma $$, выводимое из начального символа S.

    Пример 13.1.23. Слова S, aSeaceSbb, aceaacecbecbb являются сентенциальными формами грамматики из примера 13.1.3.

    Определение 13.1.24. Пусть дана контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$. Определим три функции $$\first_G $$, $$\follow_G $$ и $$\director_G $$, связанные с грамматикой G. Для краткости будем писать просто FIRST, FOLLOW и DIRECTOR.

    Функция FIRST ставит в соответствие каждому слову $$\omega \pin \ns ^* $$ множество тех терминальных символов, с которых начинаются слова, выводимые из $$\omega $$, то есть$$\first( \omega ) \bydef \{ b \in \Sigma \mid ( \exists \theta \in \ns ^* ) \, \omega \overstar{\Rightarrow} b \theta \} .$$

    Функция FOLLOW ставит в соответствие каждому нетерминальному символу A множество тех терминальных символов, которые могут встречаться в сентенциальных формах непосредственно справа от A, то есть$$\follow( A ) \bydef \{ b \in \Sigma \mid ( \exists \eta \in \ns ^* ) \, ( \exists \theta \in \ns ^* ) \, S \overstar{\Rightarrow} \eta A b \theta \} .$$

    Функция DIRECTOR ставит в соответствие каждому правилу $$( A \tto \alpha ) \in P $$ множество терминальных символов, определяемое следующим образом: если $$\alpha \overstar{\Rightarrow} \varepsilon $$, то$$\director( A \tto \alpha ) \bydef \first( \alpha ) \cup \follow( A ) ,$$ иначе$$\director( A \tto \alpha ) \bydef \first( \alpha ) .$$

    Пример 13.1.25. Рассмотрим контекстно-свободную грамматику из примера 13.1.3. Очевидно, что$$\begin{align*} \first( c ) = \{ c \} ,\\ \first( dS ) = \{ d \} ,\\ \first( aSeSb ) = \{ a \} ,\\ \follow( S ) = \{ b , e \} ,\\ \director( S \tto c ) = \{ c \} ,\\ \director( S \tto dS ) = \{ d \} ,\\ \director( S \tto aSeSb ) = \{ a \} . \end{align*}$$

    Пример 13.1.26. Рассмотрим контекстно-свободную грамматику $$G_\eos $$ из примера 13.1.17. Очевидно, что$$\begin{align*} \director( B \tto C ) = \{ \trm{(} , \trm{m} , \trm{n} \} ,\\ \director( B \tto B \trm{/} C ) = \{ \trm{(} , \trm{m} , \trm{n} \} ,\\ \director( B \tto B \trm{*} C ) = \{ \trm{(} , \trm{m} , \trm{n} \} . \end{align*}$$

    Пример 13.1.27. Пусть контекстно-свободная грамматика $$G \peq \lalg N , \Sigma , P , S \ralg $$ не содержит бесполезных символов. Пусть даны правило $$( A \tto \alpha ) \in P $$ и символ $$b \in \Sigma $$. Тогда утверждение$$b \in \director( A \tto \alpha )$$ равносильно тому, что найдутся такие $$x \in \Sigma^* $$, $$y \in \Sigma^* $$ и $$\theta \in \ns ^* $$, что$$S \overstar{\Rightarrow} x A \theta \quad\text{и}\quad x \alpha \theta \overstar{\Rightarrow} x b y .$$

    Теорема 13.1.28. Пусть дана контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$. Пусть $$G_\eos = \lalg N_\eos , \Sigma_\eos , P_\eos , S_\eos \ralg $$ - соответствующая контекстно-свободная грамматика с маркером конца строки, приведенная в определении 13.1.16. Обозначим через M МП-автомат $$\lalg Q , \Sigma_\eos , \Gamma , \Delta , \{ \qinitial \} , \{ \varepsilon \} \ralg $$, где$$Q = \{ v \in \Sigma_\eos^* \mid | v | \leq 1 \} \cup \{ \qinitial \} ,$$ $$\qinitial \notin \Sigma_\eos^* $$, $$\Gamma = N_\eos \cup \Sigma_\eos $$ и$$\begin{align*} \Delta = \{ \lp \lp \qinitial , \varepsilon , \varepsilon \rp , \lp \varepsilon , S_\eos \rp \rp \} \cup {} \\ \myqquad \cup \{ \lp \lp \varepsilon , a , \varepsilon \rp , \lp a , \varepsilon \rp \rp \mid a \in \Sigma_\eos \} \cup {} \\ \myqquad \cup \{ \lp \lp a , \varepsilon , a \rp , \lp \varepsilon , \varepsilon \rp \rp \mid a \in \Sigma_\eos \} \cup {} \\ \myqquad \cup \{ \lp \lp b , \varepsilon , A \rp , \lp b , \alpha \rp \rp \mid ( A \tto \alpha ) \in P_\eos ,\ b \in \director_{ G_\eos }( A \tto \alpha ) \} . \end{align*}$$ Тогда МП-автомат M является нисходящим магазинным анализатором для грамматики G.

    Доказательство. Индукцией по количеству тактов можно доказать, что если $$\lp v , w , \beta \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$, где $$v \in \Sigma_\eos^* $$, то $$\smash[b]{ \beta \overstar{\myunderset{ G_\eos }{\Rightarrow }} v w } $$. Следовательно, $$L ( M ) \subseteq L ( G_\eos ) $$.

    С другой стороны, докажем, что если в грамматике $$G_\eos $$ выводится $$S_\eos \overstar{\lmarrow} u \beta $$ и $$\beta \overstar{\lmarrow} b w $$, где $$u \in \Sigma_\eos^* $$, $$\beta \in \ns ^* $$, $$b \in \Sigma_\eos $$, $$w \in \Sigma_\eos^* $$, то $$\lp b , w , \beta \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$.

    Проведем доказательство индукцией по сумме длины слова bw и длины вывода $$\beta \overstar{\lmarrow} b w $$. Случай |bw| = 1, $$\beta = b w $$ образует базис индукции (очевидно, что $$\lp b , \varepsilon , b \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$ ). Проверим теперь шаг индукции. Так как $$\beta \overstar{\Rightarrow} b w $$ и $$b w \neq \varepsilon $$, то $$\beta \neq \varepsilon $$. Если $$\beta = A \theta $$, где $$A \in N $$, то вывод $$\beta \overstar{\lmarrow} b w $$ имеет вид$$A \theta \lmarrow \alpha \theta \overstar{\lmarrow} b w ,$$ где $$( A \tto \alpha ) \in P_\eos $$ и в силу леммы 13.1.27 $$b \in \director_{ G_\eos }( A \tto \alpha ) $$. Отсюда получаем, что $$\lp b , w , A \theta \rp \vdash \lp b , w , \alpha \theta \rp $$, и остается применить предположение индукции для левосторонних выводов $$S_\eos \overstar{\lmarrow} u \alpha \theta $$ и $$\alpha \theta \overstar{\lmarrow} b w $$. Если же $$\beta = a \beta' $$, где $$a \in \Sigma_\eos $$, то, очевидно, a = b и $$\beta' \overstar{\lmarrow} w $$. Если $$w = \varepsilon $$, то $$b = \eos $$ и в силу леммы 13.1.19 $$\beta' = \varepsilon $$, но этот случай уже рассмотрен в базисе индукции. Пусть $$w \neq \varepsilon $$. Тогда w = b'w' для некоторых $$b' \in \Sigma_\eos $$ и $$w' \in \Sigma_\eos^* $$. Обозначим u' = ub. Применяя предположение индукции для левосторонних выводов $$S_\eos \overstar{\lmarrow} u' \beta' $$ и $$\beta' \overstar{\lmarrow} b' w' $$, получаем $$\lp b' , w' , \beta' \rp \overstar{\vdash} \lp \varepsilon , \varepsilon , \varepsilon \rp $$. Согласно построению МП-автомата M имеем$$\lp b , b' w' , b \beta' \rp \vdash \lp \varepsilon , b' w' , \beta ' \rp \vdash \lp b' , w' , \beta ' \rp .$$ Шаг индукции доказан. Теперь легко проверить, что выполняется $$L ( G_\eos ) \subseteq L ( M ) $$.

    Гомоморфизм $$r \colon \Delta^* \to P_\eos^* $$ задается соотношениями$$\begin{align*} r ( \lp \lp b , \varepsilon , A \rp , \lp b , \alpha \rp \rp ) = ( A \tto \beta ) ,\\ r ( \mathfrak{d} ) = \varepsilon \mathspace\text{для остальных}\mathspace \mathfrak{d} \in \Delta . \end{align*}$$

    Пример 13.1.29. Рассмотрим контекстно-свободную грамматику из примера 13.1.3. Грамматика с маркером конца строки имеет правила$$\begin{align*} T \; {\to} \; S \eos , \\ S \; {\to} \; c , \\ S \; {\to} \; dS , \\ S \; {\to} \; aSeSb . \end{align}$$ Соответствующий нисходящий магазинный анализатор M, построенный в теореме 13.1.28, имеет приведенный ниже вид.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{a} \ar "2,3" <0.6mm> ^{\varepsilon,a:\varepsilon} \rloop{-1,0} ^{\varepsilon,T:S\boldsymbol{\$}} \rloop{0,1} ^{\varepsilon,S:aSeSb} *=[o][F-]{b} \ar "2,3" <0.6mm> ^{\varepsilon,b:\varepsilon} *=[o][F-]{c} \ar "2,3" <0.6mm> ^{\varepsilon,c:\varepsilon} \rloop{1,0} ^{\varepsilon,T:S\boldsymbol{\$}} \rloop{0,1} ^{\varepsilon,S:c} \\ *=[o][F-]{q_{\textrm{s}}} \ar @`{+/l16mm/} [] ^{} \ar "2,3" ^{\varepsilon,\varepsilon:T} *=[o][F=]{\varepsilon} \ar "1,1" <0.6mm> ^{a,\varepsilon:\varepsilon} \ar "1,3" <0.6mm> ^{b,\varepsilon:\varepsilon} \ar "1,5" <0.6mm> ^{c,\varepsilon:\varepsilon} \ar "3,5" <0.6mm> ^{d,\varepsilon:\varepsilon} \ar "3,3" <0.6mm> ^{e,\varepsilon:\varepsilon} \ar "3,1" <0.6mm> ^{\boldsymbol{\$},\varepsilon:\varepsilon} \\ *=[o][F-]{\boldsymbol{\$}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{\$}:\varepsilon} *=[o][F-]{e} \ar "2,3" <0.6mm> ^{\varepsilon,e:\varepsilon} *=[o][F-]{d} \ar "2,3" <0.6mm> ^{\varepsilon,d:\varepsilon} \rloop{1,0} ^{\varepsilon,T:S\boldsymbol{\$}} \rloop{0,-1} ^{\varepsilon,S:dS} }$$

    Определение 13.1.30. Контекстно-свободная грамматика $$G \peq \lalg N , \Sigma , P , S \ralg $$ принадлежит классу LL(1), если для любых двух правил $$( A \tto \alpha ) \in P_\eos $$ и $$( A \tto \beta ) \in P_\eos $$, где $$\alpha \neq \beta $$, множества $$\director_{ G_\eos }( A \tto \alpha ) $$ и $$\director_{ G_\eos }( A \tto \beta ) $$ не пересекаются.

    Замечание 13.1.31. Первая буква L в названии класса LL(1) означает, что входное слово читается слева направо (left-to-right). Вторая буква L означает, что строится левосторонний вывод (leftmost derivation). Число 1 указывает на то, что на каждом шаге для принятия решения используется один символ неразобранной части входного слова.

    Пример 13.1.32. Грамматика из примера 13.1.3 принадлежит классу LL(1), а грамматика из примера 3.1.17 этому классу не принадлежит.

    Теорема 13.1.33. МП-автомат M, построенный в теореме 13.1.28 по контекстно-свободной грамматике G, является детерминированным тогда и только тогда, когда грамматика G принадлежит классу LL(1).

    Теорема 13.1.34. Грамматики из класса LL(1) порождают только детерминированные контекстно-свободные языки.

    Теорема 13.1.35. Пусть контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ не содержит бесполезных символов. Система множеств $$\first( \omega ) $$ (где $$\omega \in \ns ^* $$ ) состоит из наименьших ( по включению ) множеств, удовлетворяющих следующим условиям:

  • если $$\phi \overstar{\Rightarrow} \varepsilon $$, то $$b \in \first( \phi b \psi ) $$ для всех $$b \in \Sigma $$ и $$\psi \in \ns ^* $$ ;
  • если $$\phi \overstar{\Rightarrow} \varepsilon $$, то $$\first( A ) \subseteq \first( \phi A \psi ) $$ для всех $$A \in N $$ и $$\psi \in \ns ^* $$ ;
  • если $$( A \tto \alpha ) \in P $$, то $$\first( \alpha ) \subseteq \first( A ) $$.
    •

    Теорема 13.1.36. Пусть контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ не содержит бесполезных символов. Система множеств $$\follow( A ) $$ ( где $$A \in N $$ ) состоит из наименьших ( по включению ) множеств, удовлетворяющих следующим условиям:

  • если $$B \in N $$ и $$( A \tto \phi B \psi ) \in P $$, то $$\first( \psi ) \subseteq \follow( B ) $$ ;
  • если $$B \in N $$, $$( A \tto \phi B \psi ) \in P $$ и $$\psi \overstar{\Rightarrow} \varepsilon $$, то$$\follow( A ) \subseteq \follow( B ) .$$

    • Замечание 13.1.37. Теоремы 13.1.35 и 13.1.36 дают алгоритм проверки принадлежности контекстно-свободной грамматики G классу LL(1). Можно предположить, что грамматика G не содержит бесполезных символов (их можно устранить).

    Сначала необходимо вычислить значения $$\first_{ G_\eos }( \omega ) $$ параллельно для всех слов $$\omega $$, являющихся суффиксами правых частей правил грамматики $$G_\eos $$. Для этого постепенно пополняем множества $$\first_{ G_\eos }( \omega ) $$ (начав с пустых множеств), используя условия, приведенные в теореме 13.1.35.

    Затем необходимо вычислить значения $$\follow_{ G_\eos }( A ) $$ параллельно для всех вспомогательных символов A. Для этого постепенно пополняем множества $$\follow_{ G_\eos }( A ) $$ (начав с пустых множеств), используя условия, приведенные в теореме 13.1.35.

    В заключение вычислим значения $$\director_{ G_\eos }( A \tto \alpha ) $$ для всех правил $$A \tto \alpha $$, следуя определению функции $$\director $$, и проверим условия из определения 13.1.30.

    Теорема 13.1.38. Пусть даны контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ и символ $$A \in N $$. Пусть$$P = P_0 \cup \{ A \tto A \alpha_1 , \ldots , A \tto A \alpha_n , A \tto \beta_1 , \ldots , A \tto \beta_m \} ,$$ где множество P0 не содержит правил с левой частью A и ни одно из слов $$\beta_1 , \ldots , \beta_m $$ не начинается с символа A. Тогда грамматика G эквивалентна контекстно-свободной грамматике $$G' = \lalg N \cup \{ A' \} , \Sigma , P' , S \ralg $$, где A' - новый символ, не принадлежащий множеству $$N \cup \Sigma $$, и$$P' = P_0 \cup \{ A \squeeze{\tto} \beta_1 A' , \ldots , A \squeeze{\tto} \beta_m A' , A' \squeeze{\tto} A' \alpha_1 , \ldots , A' \squeeze{\tto} A' \alpha_n , A' \squeeze{\tto} \varepsilon \} .$$

    Пример 13.1.39. Если к контекстно-свободной грамматике $$G_\eos $$ из примера 13.1.17 два раза применить преобразование из теоремы 13.1.38 (для вспомогательного символа A и для вспомогательного символа B ), то получим эквивалентную грамматику G' с правилами$$\begin{align*} S \; {\to} \; A \eos , B \; {\to} \; C D , C \; {\to} \; \trm{(} A \trm{)} , \\ A \; {\to} \; B E , D \; {\to} \; \trm{*} C D , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \trm{+} B E , D \; {\to} \; \trm{/} C D , C \; {\to} \; \trm{n} . \\ E \; {\to} \; \trm{-} B E , D \; {\to} \; \varepsilon , \\ E \; {\to} \; \varepsilon , \end{align*}$$ После упрощения получаем грамматику G'' с правилами$$\begin{align*} S \; {\to} \; A \eos , D \; {\to} \; \trm{*} C D , C \; {\to} \; \trm{(} C D E \trm{)} , \\ A \; {\to} \; C D E , D \; {\to} \; \trm{/} C D , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \trm{+} C D E , D \; {\to} \; \varepsilon , C \; {\to} \; \trm{n} . \\ E \; {\to} \; \trm{-} C D E , \\ E \; {\to} \; \varepsilon , \end{align*}$$ Язык L(G'') распознается детерминированным МП-автоматом $$M \peq \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$, где $$Q = \{ \qinitial , \varepsilon \} $$, $$\Gamma = \{ C , E , D , \trm{)} , \eos \} $$, $$I = \{ \qinitial \} $$, $$F = \{ \varepsilon \} $$ и$$\begin{align*} {} \Delta=\{ \lp\lp\qinitial,\varepsilon,\varepsilon\rp, \lp\varepsilon,CDE\eos\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{*},D\rp, \lp\varepsilon,CD\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{/},D\rp, \lp\varepsilon,CD\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{+},DE\rp, \lp\varepsilon,CDE\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{-},DE\rp, \lp\varepsilon,CDE\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{)},DE\trm{)}\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\eos,DE\eos\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{m},C\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{n},C\rp, \lp\varepsilon,\varepsilon\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp\varepsilon,\trm{(},C\rp, \lp\varepsilon,CDE\trm{)}\rp\rp \}. \end{align*}$$ Можно доказать, что МП-автомат M является нисходящим магазинным анализатором для грамматики$$\begin{align*} A \; {\to} \; C D E , D \; {\to} \; \trm{*} C D , C \; {\to} \; \trm{(} C D E \trm{)} , \\ E \; {\to} \; \trm{+} C D E , D \; {\to} \; \trm{/} C D , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \trm{-} C D E , D \; {\to} \; \varepsilon , C \; {\to} \; \trm{n} . \\ E \; {\to} \; \varepsilon , \end{align*}$$

    Пример 13.1.40. Пусть $$\Sigma = \{ \trm{m} , \trm{n} , \trm{-} , \trm{*} \} $$ и $$N = \{ A , B , C \} $$. Рассмотрим контекстно-свободную грамматику G с правилами$$\begin{align*} A \; {\to} \; C D E , D \; {\to} \; \trm{*} C D , \\ E \; {\to} \; \trm{-} C D E , D \; {\to} \; \varepsilon , \\ E \; {\to} \; \varepsilon , C \; {\to} \; \trm{m} , \\ C \; {\to} \; \trm{n} . \end{align*}$$ Грамматика с маркером конца строки имеет правила$$\begin{align*} T \; {\to} \; A \eos , D \; {\to} \; \trm{*} C D , \\ A \; {\to} \; C D E , D \; {\to} \; \varepsilon , \\ E \; {\to} \; \trm{-} C D E , C \; {\to} \; \trm{m} , \\ E \; {\to} \; \varepsilon , C \; {\to} \; \trm{n} . \end{align*}$$ Соответствующий нисходящий магазинный анализатор M, построенный в теореме 13.1.28, имеет приведенный ниже вид.$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ *=[o][F-]{\boldsymbol{m}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{m}:\varepsilon} \rloop{0,-1} ^{\varepsilon,T:A\boldsymbol{\$}} \rloop{-1,0} ^{\varepsilon,A:CDE} \rloop{0,1} ^{\varepsilon,C:\boldsymbol{m}} *=[o][F-]{q_{\textrm{s}}} \ar @`{+/l16mm/} [] ^{} \ar "2,3" ^{\varepsilon,\varepsilon:T} *=[o][F-]{\boldsymbol{\$}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{\$}:\varepsilon} \rloop{1,0} ^{\varepsilon,D:\varepsilon} \rloop{0,-1} ^{\varepsilon,E:\varepsilon} \\ % *=[o][F=]{\varepsilon} \ar "1,1" <0.6mm> ^{\boldsymbol{m},\varepsilon:\varepsilon} \ar "3,1" <0.6mm> ^{\boldsymbol{n},\varepsilon:\varepsilon} \ar "3,3" <0.6mm> ^{\boldsymbol{*},\varepsilon:\varepsilon} \ar "3,5" <0.6mm> ^{\boldsymbol{-},\varepsilon:\varepsilon} \ar "1,5" <0.6mm> ^{\boldsymbol{\$},\varepsilon:\varepsilon} \\ *=[o][F-]{\boldsymbol{n}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{n}:\varepsilon} \rloop{0,-1} ^{\varepsilon,T:A\boldsymbol{\$}} \rloop{-1,0} ^{\varepsilon,A:CDE} \rloop{0,1} ^{\varepsilon,C:\boldsymbol{n}} *=[o][F-]{\boldsymbol{*}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{*}:\varepsilon} \rloop{0,-1} ^{\varepsilon,D:\boldsymbol{*}CD} *=[o][F-]{\boldsymbol{-}} \ar "2,3" <0.6mm> ^{\varepsilon,\boldsymbol{-}:\varepsilon} \rloop{1,0} ^{\varepsilon,D:\varepsilon} \rloop{0,-1} ^{\varepsilon,E:\boldsymbol{-}CDE} }$$ Легко убедиться, что грамматика G принадлежит классу LL(1) и МП-автомат M является детерминированным.

    Упражнение 13.1.41. Существует ли детерминированный нисходящий магазинный анализатор для грамматики$$\begin{align*} S \; {\to} \; bScS , \\ S \; {\to} \; bS , \\ S \; {\to} \; a ? \end{align*}$$

    Упражнение 13.1.42. Принадлежит ли грамматика$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; bS , \\ S \; {\to} \; cSS \end{align*}$$ классу LL(1)?

    Упражнение 13.1.43. Принадлежит ли грамматика$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; Sb , \\ S \; {\to} \; SSc \end{align*}$$ классу LL(1)?

    13.2. Восходящий разбор

    Определение 13.2.1. Протоколом правостороннего вывода в контекстно-свободной грамматике $$G = \lalg N , \Sigma , P , S \ralg $$ будем называть обращенную последовательность правил, примененных в этом выводе. Формально говоря, протоколом правостороннего вывода$$\omega_0 , \omega_1 , \ldots , \omega_n$$ является последовательность$$( A_1 \tto \alpha_1 ) , \ldots , ( A_n \tto \alpha_n ) ,$$ где для каждого i<n, если $$\omega_i = \eta B v $$ и $$\omega_{i+1} = \eta \beta v $$ для некоторых $$\eta \in \ns ^* $$, $$B \in N $$, $$v \in \Sigma^* $$, $$\beta \in \ns ^* $$, то An-i = B и $$\alpha_{n-i} = \beta $$.

    Пример 13.2.2. Рассмотрим контекстно-свободную грамматику$$\begin{align*} S \; {\to} \; c\\ S \; {\to} \; dS\\ S \; {\to} \; aSeSb \end{align*}$$ и дерево вывода$$\xymatrix @=6pt { S\ar[ddllll]\ar[ddll]\ar[dd]\ar[ddrr]\ar[ddrrrr] \\ \\ a S\ar[dd] e S\ar[ddl]\ar[ddr] b \\ \\ c d S\ar[dd] \\ \\ c }$$ из примера 13.1.3. Этому дереву вывода соответствует правосторонний вывод$$S \pRightarrow aSeSb \pRightarrow aSedSb \pRightarrow aSedcb \pRightarrow acedcb .$$ Протоколом этого вывода является последовательность$$( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto dS ) ,\ ( S \tto aSeSb ) .$$

    Лемма 13.2.3. Разным правосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

    Протокол правостороннего вывода в контекстно-свободной грамматике является естественным описанием соответствующего дерева вывода в порядке постфиксного обхода (postorder traversal). (Постфиксный обход упорядоченного дерева можно определить рекурсивно так: сначала выполняется постфиксный обход первого непосредственного потомка корня, затем второго и т. д., а в самом конце посещается корень дерева.)

    Например, протокол правостороннего вывода из примера 13.2.2 задает процесс постепенного конструирования дерева вывода, изображенный ниже.$$\newcommand{\rb}[1]{\raisebox{0pt}[8pt]{$ #1 $}} \entrymodifiers={=<3.3mm>[o]} \xymatrix @=0mm { \boldsymbol{S}\ar[ddddll] \\ \\ \\ \\ \rb{\boldsymbol{a}} \rb{c} \\%} \\ %\xymatrix @=0mm { \boldsymbol{S}\ar[ddddll] \\ \\ \boldsymbol{S}\ar[ddr] \\ \\ \rb{\boldsymbol{a}} \rb{c} \rb{\boldsymbol{e}} \rb{\boldsymbol{d}} \rb{c} \\%} \\ %\xymatrix @=0mm { \boldsymbol{S}\ar[ddddll] \boldsymbol{S}\ar[dddd]\ar[ddr] \\ \\ S\ar[ddr] \\ \\ \rb{\boldsymbol{a}} \rb{c} \rb{\boldsymbol{e}} \rb{d} \rb{c} \\%} \\ %\xymatrix @=0mm { \boldsymbol{S}\ar[ddddddlllll]<-1mm>\ar[ddl]\ar[ddddddl]\ar[ddr]\ar[ddddddrrrrr]<1mm> \\ \\ S\ar[ddddll] S\ar[dddd]\ar[ddr] \\ \\ S\ar[ddr] \\ \\ \rb{a} \rb{c} \rb{e} \rb{d} \rb{c} \rb{b} }$$

    Определение 13.2.5. Правым разбором (right parse) слова w в контекстно-свободной грамматике G называется протокол любого правостороннего вывода слова w в грамматике G.

    Пример 13.2.6. Правым разбором слова aceaacecbecbb в грамматике из примера 13.2.2 является последовательность$$\begin{multiline*} ( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto c ) ,\ ( S \tto aSeSb ) ,\\ ( S \tto c ) ,\ ( S \tto aSeSb ) ,\ ( S \tto aSeSb ) . \end{multiline*}$$

    Определение 13.2.7. Процесс нахождения правого разбора слова w в~заданной контекстно-свободной грамматике G называется восходящим разбором (bottom-up parsing).

    Определение 13.2.8. Пусть даны контекстно-свободная грамматика $$G = \lalg N , \Sigma , P , S \ralg $$ и МП-автомат $$M = \lalg Q , \Sigma , \Gamma , \Delta , I , F \ralg $$. Будем говорить, что МП-автомат M - восходящий магазинный анализатор (bottom-up, left-to-right parser) для грамматики G, если $$L ( M ) = L ( G_\eos ) $$ и существует такой гомоморфизм $$r \colon \Delta^* \to P_\eos^* $$, что для каждого вычислительного процесса (МП-автомата M ), допускающего слово $$w \in \Sigma_\eos^* $$, образ протокола этого вычислительного процесса при гомоморфизме r является протоколом некоторого правостороннего вывода слова w в грамматике $$G_\eos $$.

    Пример 13.2.9. Рассмотрим контекстно-свободную грамматику $$G_\eos $$ из примера 13.1.17. Язык $$L ( G_\eos ) $$ распознается недетерминированным МП-автоматом $$M = \lalg \{ 1 , 2 \} , \Sigma , \Gamma , \Delta , \{ 1 \} , \{ 2 \} \ralg $$, где$$\Gamma = \{ A , B , C , \trm{+} , \trm{-} , \trm{*} , \trm{/} , \trm{(} \}$$ и$$\begin{align*} {} \Delta=\{ \lp\lp1,\trm{+},\varepsilon\rp, \lp1,\trm{+}\rp\rp,\ \lp\lp1,\trm{-},\varepsilon\rp, \lp1,\trm{-}\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\trm{*},\varepsilon\rp, \lp1,\trm{*}\rp\rp,\ \lp\lp1,\trm{/},\varepsilon\rp, \lp1,\trm{/}\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\trm{(},\varepsilon\rp, \lp1,\trm{(}\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\varepsilon,B\trm{+}A\rp, \lp1,A\rp\rp,\ \lp\lp1,\varepsilon,B\trm{-}A\rp, \lp1,A\rp\rp,\ \lp\lp1,\varepsilon,B\rp, \lp1,A\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\varepsilon,C\trm{*}B\rp, \lp1,B\rp\rp,\ \lp\lp1,\varepsilon,C\trm{/}B\rp, \lp1,B\rp\rp,\ \lp\lp1,\varepsilon,C\rp, \lp1,B\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\trm{)},A\trm{(}\rp, \lp1,C\rp\rp,\ \lp\lp1,\trm{m},\varepsilon\rp, \lp1,C\rp\rp,\ \lp\lp1,\trm{n},\varepsilon\rp, \lp1,C\rp\rp,\ \\\hphantom{{}={}\{}%\} \lp\lp1,\eos,A\rp, \lp2,\varepsilon\rp\rp \}. \end{align*}$$ Можно проверить, что МП-автомат M является восходящим магазинным анализатором для грамматики G из примера 13.1.17.

    Определение 13.2.10. Контекстно-свободная грамматика $$G \peq \lalg N , \Sigma , P , S \ralg $$ принадлежит классу LR(1), если для любых $$\eta_1 \in ( N_\eos \cup \Sigma_\eos )^* $$, $$\eta_2 \in ( N_\eos \cup \Sigma_\eos )^* $$, $$A_1 \in N_\eos \cup \Sigma_\eos $$, $$A_2 \in N_\eos \cup \Sigma_\eos $$, $$b \in \Sigma_\eos $$, $$v_1 \in \Sigma_\eos^* $$, $$v_2 \in \Sigma_\eos^* $$, $$\alpha_1 \in ( N_\eos \cup \Sigma_\eos )^* $$, $$\alpha_2 \in ( N_\eos \cup \Sigma_\eos )^* $$ из условий$$\begin{align*} S_\eos \overstar{\rmarrow} \eta_1 A_1 b v_1 ,\\ S_\eos \overstar{\rmarrow} \eta_2 A_2 b v_2 ,\\ ( A_1 \tto \alpha_1 ) \in P_\eos ,\\ ( A_2 \tto \alpha_2 ) \in P_\eos ,\\ \eta_1 \alpha_1 = \eta_2 \alpha_2 \end{align*}$$ следует, что A1 = A2 и $$\alpha_1 = \alpha_2 $$.

    Замечание 13.2.11. Классу LR(1) принадлежат те языки, для которых возможен восходящий разбор слова при чтении слева направо с заглядыванием на один символ вперед.

    Замечание 13.2.12. Буква L в названии класса LR(1) означает, что входное слово читается слева направо (left-to-right). Буква R означает, что строится правосторонний вывод (rightmost derivation). Число 1 указывает на то, что на каждом шаге для принятия решения используется один символ неразобранной части входного слова.

    Теорема 13.2.13. Для каждой грамматики из класса LR(1) существует детерминированный восходящий магазинный анализатор.

    Доказательство можно найти в [2, с. 420-447].

    Теорема 13.2.14. Грамматики из класса LR(1) порождают только детерминированные контекстно-свободные языки.

    Теорема 13.2.15. Каждая грамматика из класса LL(1) принадлежит также классу LR(1).

    Упражнение 13.2.16. Найти все правые разборы слова bbacba в грамматике$$\begin{align*} S \; {\to} \; bScS , \\ S \; {\to} \; bS , \\ S \; {\to} \; a . \end{align*}$$

    Упражнение 13.2.17. Найти детерминированный восходящий магазинный анализатор для грамматики$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; Sb , \\ S \; {\to} \; SSc . \end{align*}$$

    Упражнение 13.2.18. Найти детерминированный восходящий магазинный анализатор для грамматики$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; bS , \\ S \; {\to} \; cSS . \end{align*}$$

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^