Алгоритм разбора
для LL(1)-грамматик

Алгоритм разбора для LL(1)-грамматик

В этом разделе мы рассмотрим еще один метод проверки выводимости в КС-грамматике, называемый по традиции     LL(1)-разбором. Вот его идея в одной фразе: можно считать, что в процессе вывода мы всегда заменяем самый левый нетерминал и нужно лишь выбрать одно из правил; если нам повезет с грамматикой, то выбрать правило можно, глядя на первый символ выводимого из этого нетерминала слова. Говоря более формально, дадим такое

Определение. Левым выводом (слова в грамматике) называется   вывод, в котором на каждом шаге замене подвергается самый левый из нетерминалов.


$\scriptstyle{\blacktriangleright}$ 13.3.1. Для каждого выводимого слова (из терминалов) существует его левый вывод.

Решение. Различные нетерминалы заменяются независимо; если в процессе вывода появилось слово $\ldots K\ldots L\ldots$, где K , L -- нетерминалы, то замены K и L можно производить в любом порядке. Поэтому можно перестроить вывод так, чтобы стоящий левее нетерминал заменялся раньше. (Формально говоря, надо доказывать индукцией по длине вывода такой факт: если из некоторого нетерминала K выводится некоторое слово A , то существует левый вывод A из K .)$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 13.3.2. В грамматике с 4 правилами \begin{eqnarray*}
&& (1)\quad \hbox{\tt E} \to \\  && (2)\quad \hbox{\tt E} \to ...
 ...\to \hbox{\tt (E)}\\  && (4)\quad \hbox{\tt T} \to \hbox{\tt [E]}\end{eqnarray*}найти левый вывод слова $A = \hbox{\tt [()([$\,$])]}$ и доказать, что он единствен.

Решение. На первом шаге можно применить только правило (2): \begin{displaymath}
\hbox{\tt E} \to \hbox{\tt TE} \end{displaymath}Что будет дальше с T? Так как слово A начинается на [, то может примениться только правило (4): \begin{displaymath}
\hbox{\tt E} \to \hbox{\tt TE}\to \hbox{\tt[E]E} \end{displaymath}Первое E должно замениться на TE (иначе вторым символом была бы скобка ]): \begin{displaymath}
\hbox{\tt E} \to\hbox{\tt TE}\to\hbox{\tt [E]E}
 \to\hbox{\tt [TE]E} \end{displaymath}и T должно заменяться по (3): \begin{displaymath}
\hbox{\tt E}\to\hbox{\tt TE}\to\hbox{\tt [E]E}
 \to\hbox{\tt [TE]E}\to\hbox{\tt [(E)E]E} \end{displaymath}Далее первое E должно замениться на пустое слово (иначе третьей буквой слова будет ( или [ -- только на эти символы может начинаться слово, выводимое из T): \begin{displaymath}
\hbox{\tt E}\to\hbox{\tt TE}\to\hbox{\tt [E]E}
 \to\hbox{\tt [TE]E}\to\hbox{\tt [(E)E]E}\to\hbox{\tt [()E]E} \end{displaymath}и далее \begin{displaymath}
\ldots\to \hbox{\tt [()TE]E}
 \to\hbox{\tt [()(E)E]E}
 \to\hbox{\tt [()(TE)E]E}
 \to\hbox{\tt [()([E]E)E]E}\to\end{displaymath}\begin{displaymath}
\to\hbox{\tt [()([$\,$]E)E]E}
 \to\hbox{\tt [()([$\,$])E]E}
 \to\hbox{\tt [()([$\,$])]E}
 \to\hbox{\tt [()([$\,$])]}\end{displaymath}$\scriptstyle\blacktriangleleft$

Что требуется от грамматики, чтобы такой метод поиска левого вывода был применим? Пусть, например, на очередном шаге самым левым нетерминалом оказался нетерминал K , т.е. мы имеем слово вида AKU , где A -- слово из терминалов, а U -- слово из терминалов и нетерминалов. Пусть в грамматике есть правила \begin{eqnarray*}
K&\to& L M N\\  K&\to& P Q\\  K&\to& R\end{eqnarray*}Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор, глядя на первый символ той части входного слова, которая выводится из KU .

Рассмотрим множество Нач(LMN ) тех терминалов, с которых   начинаются непустые слова, выводимые из LMN . (Это множество равно Нач(L ), объединенному с Нач(M ), если из L выводится пустое слово, а также с Нач(N ), если из L и из M выводится пустое слово.) Чтобы описанный метод был применим, надо, чтобы Нач(LMN ), Нач(PQ ) и Нач(R ) не пересекались. Но этого мало. Ведь может быть так, например, что из LMN будет выведено пустое слово, а из слова U будет выведено слово, начинающееся на букву из Нач(PQ ). Следующие определения учитывают эту проблему.

Напомним, что определение выводимости в КС-грамматике было дано только для слова из терминалов. Оно очевидным образом обобщается на случай слов из терминалов и нетерминалов. Можно также говорить о выводимости одного слова (содержащего терминалы и нетерминалы) из другого. (Если говорится о выводимости слова без указания того, откуда оно выводится, то всегда подразумевается выводимость в грамматике, т.е. выводимость из начального нетерминала.)

Для каждого слова X из терминалов и нетерминалов через Нач(X ) обозначаем множество всех терминалов, с которых начинаются непустые слова из терминалов, выводимые из X . (В случае, если из любого нетерминала выводится хоть одно слово из терминалов, не играет роли, рассматриваем ли мы при определении Нач(X ) слова только из терминалов или любые слова. Мы будем предполагать далее, что это условие выполнено.)

Для каждого нетерминала K через Послед(K )   обозначим множество терминалов, которые встречаются в выводимых (в грамматике) словах сразу же за K . (Не смешивать с Посл(K ) предыдущего раздела!) Кроме того, в Послед(K ) включается символ EOI, если существует выводимое слово, оканчивающееся на K .

Для каждого правила \begin{displaymath}
K \to V \end{displaymath}(где K -- нетерминал, V -- слово, содержащее терминалы и нетерминалы) определим множество направляющих терминалов,         обозначаемое Напр($K\to V$). По определению оно равно Нач(V ), к которому добавлено Послед(K ), если из V выводится пустое слово.

Определение. Грамматика называется LL(1)-грамматикой, если для любых правил $K\to V$ и $K\to W$ с одинаковыми левыми частями множества Напр($K\to V$) и Напр($K\to W$) не пересекаются.


$\scriptstyle{\blacktriangleright}$ 13.3.3. Является ли грамматика \begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt K \char93 }\\  \hbox{\tt K}&\to&\end{eqnarray*}(выводимыми словами являются последовательности диезов) LL(1)-грамматикой?

Решение. Нет: символ # принадлежит множествам направляющих символов для обоих правил (для второго -- поскольку # принадлежит Послед(K )).$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 13.3.4. Написать LL(1)-грамматику для того же языка.

Решение:

\begin{eqnarray*}
\hbox{\tt K}&\to&\hbox{\tt \char93  K}\\  \hbox{\tt K}&\to&\end{eqnarray*}Как говорят, << леворекурсивное>> правило заменено на << праворекурсивное>>.

Следующая задача показывает, что для LL(1)-грамматики существует не более одного возможного продолжения левого вывода.


$\scriptstyle{\blacktriangleright}$ 13.3.5. Пусть дано выводимое в LL(1)-грамматике слово X , в котором выделен самый левый нетерминал K : X=AKS , где A -- слово из терминалов, S -- слово из терминалов и нетерминалов. Пусть существуют два различных правила грамматики с нетерминалом K в левой части, и мы применили их к выделенному в X нетерминалу K , затем продолжили вывод и в конце концов получили два слова из терминалов, начинающихся на A . Доказать, что в этих словах за началом A идут разные буквы. (Здесь к числу букв мы относим EOI.)

Решение. Эти буквы принадлежат направляющим множествам различных правил.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 13.3.6. Доказать, что если слово выводимо в LL(1)-грамматике, то его левый вывод единствен.

Решение. Предыдущая задача показывает, что на каждом шаге левый вывод продолжается однозначно.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 13.3.7. Грамматика называется леворекурсивной, если из некоторого нетерминала K выводится слово, начинающееся с K , но не совпадающее с ним. Доказать, что леворекурсивная грамматика, в которой из каждого нетерминала выводится хотя бы одно непустое слово из терминалов и для каждого нетерминала существует вывод (начинающийся с начального нетерминала), в котором он встречается, не является LL(1)-грамматикой.

 

Решение. Пусть из K выводится KU , где K -- нетерминал, а U -- непустое слово. Можно считать, что это левый вывод (другие нетерминалы можно не заменять). Рассмотрим вывод \begin{displaymath}
K \leadsto KU \leadsto KUU \leadsto \ldots\end{displaymath}(знак $\leadsto$ обозначает несколько шагов вывода) и левый вывод $K \leadsto A$, где A -- непустое слово из терминалов. На каком-то шаге второй вывод отклоняется от первого, а между тем по обоим путям может быть получено слово, начинающееся на A (в первом случае это возможно, так как сохраняется нетерминал K , который может впоследствии быть заменен на A ). Это противоречит возможности однозначного определения правила, применяемого на очередном шаге поиска левого вывода. (Oднозначность выполняется для выводов из начального нетерминала, и надо воспользоваться тем, что K по предположению встречается в таком выводе.)$\scriptstyle\blacktriangleleft$

Таким образом, к леворекурсивным грамматикам (кроме тривиальных случаев) LL(1)-метод неприменим. Их приходится преобразовывать к эквивалентным LL(1)-грамматикам -- или пользоваться другими методами распознавания.


$\scriptstyle{\blacktriangleright}$ 13.3.8. Используя сказанное, построить алгоритм проверки выводимости слова из терминалов в LL(1)-грамматике.

Решение. Мы следуем описанному выше методу поиска левого вывода, храня лишь часть слова, находящуюся правее уже прочитанной части входного слова. Другими словами, мы храним слово S из терминалов и нетерминалов, обладающее такими свойствами (прочитанную часть входа обозначаем через A):
1.
слово AS выводимо в грамматике;
2.
любой левый вывод входного слова проходит через стадию AS
Эти свойства вместе будем обозначать <<(И)>>.

Вначале A пусто, а S состоит из единственного символа -- начального нетерминала.

Если в некоторый момент S начинается на терминал t и $\hbox{\tt t} = \hbox{\tt Next}$, то можно выполнить команду Move и удалить символ t, являющийся начальным в S, поскольку при этом AS не меняется.

Если S начинается на терминал t и $\hbox{\tt t}\neq\hbox{\tt Next}$, то входное слово невыводимо -- ибо по условию любой его вывод должен проходить через AS. (Это же справедливо и в случае $\hbox{\tt Next} = \hbox{\tt EOI}$.)

Если S пусто, то из условия (И) следует, что входное слово выводимо тогда и только тогда, когда $\hbox{\tt Next} = \hbox{\tt EOI}$.

Остается случай, когда S начинается с некоторого нетерминала K. По доказанному выше все левые выводы из S слов, начинающихся на символ Next, начинаются с применения к S одного и того же правила -- того, для которого Next принадлежит направляющему множеству. Если таких правил нет, то входное слово невыводимо. Если такое правило есть, то нужно применить его к первому символу слова S -- при этом свойство (И) не нарушится. Приходим к такому алгоритму:

 S := пустое слово;
 error := false;
 {error => входное слово невыводимо;}
 {not error => (И)}
 while (not error) and not ((Next=EOI) and (S пусто))
 | |  do begin
 | if (S начинается на терминал, равный Next) then begin
 | | Move; удалить из S первый символ;
 | end else if (S начинается на терминал, не равный Next)
 | |           then begin
 | | error := true;
 | end else if (S пусто) and (Next <> EOI) then begin
 | | error := true;
 | end else if (S начинается на нетерминал и Next входит в
 | |    направляющее множество одного из правил для этого
 | |    нетерминала) then begin
 | | применить это правило
 | end else if (S начинается на нетерминал и Next не входит
 | |  в направляющее множество ни одного из правил для этого
 | |  нетерминала) then begin
 | | error := true;
 | end else begin
 | | {так не бывает}
 | end;
 end;
 {входное слово выводимо <=> not error}
Алгоритм заканчивает работу, поскольку при появлении терминала в начале слова S происходит чтение со входа или остановка, а бесконечный цикл сменяющих друг друга нетерминалов в начале S означал бы, что грамматика леворекурсивна. (А мы можем предполагать, согласно предыдущей задаче, что это не так: нетерминалы, не встречающиеся в выводах, а также нетерминалы, из которых не выводится непустого слова, несложно удалить из грамматики.)$\scriptstyle\blacktriangleleft$


Замечания


$\scriptstyle{\blacktriangleright}$ 13.3.9.  При проверке того, относится ли данная грамматика к типу LL(1), необходимо вычислить Послед(T ) и Нач(T ) для всех нетерминалов T . Как это сделать?

Решение. Если в грамматике есть, например, правило $K\to L\,M\,N$, то \begin{displaymath}
\footnotesize
\begin{tabular}
{rcll}
${\hbox{\rm Нач}}\,(L)$...
 ...}}\,(L),$ &
 если из $M$ выводимо пустое слово,\\ \end{tabular}\end{displaymath} Подобные правила позволяют постепенно порождать множества Нач(T ), а затем и Послед(T ), для всех терминалов и нетерминалов T . При этом началом служит \begin{displaymath}
{\hbox{\tt EOI}} \in {\hbox{\rm Послед}}\,(K)\end{displaymath}для начального нетерминала K и \begin{displaymath}
z \in {\hbox{\rm Нач}}\,(z)\end{displaymath}для любого терминала z . Порождение заканчивается, когда применение правил перестает давать новые элементы множеств Нач(T ) и Послед(T ).$\scriptstyle\blacktriangleleft$



pvv
1/8/1999