Методы синтаксического анализа КС языков

Проблема синтаксического анализа для КС-языков состоит в построении алгоритма, который по любой КС-грамматике [cbm]G=(V,N,S,P)[/cbm] и цепочке [cbm]x[/cbm] в ее терминальном алфавите [cbm]V[/cbm] распознает, принадлежит ли [cbm]x[/cbm] языку [cbm]L(G)[/cbm] , порождаемому грамматикой [cbm]G[/cbm] . В случае положительного ответа на вопрос алгоритм должен строить дерево вывода [cbm]x[/cbm] в грамматике [cbm]G[/cbm] .

Существование такого алгоритма следует из факта разрешимости проблемы принадлежности для КС-языков. Мы рассмотрим некоторые алгоритмы синтаксического анализа для определенных классов КС-языков.

Прототипом синтаксического анализатора является МП-автомат, который строится по данной КС-грамматике, но такой МП-автомат, как мы видели, является в общем случае недетерминированным и может даже для допустимой цепочки построить вывод, который заканчивается тупиковой конфигурацией. Чтобы на основе такого распознавателя построить алгоритм синтаксического анализа (и тем самым превратить распознаватель в анализатор), нужно разработать определенный механизм управления выводом на множестве конфигураций МП-автомата. Этот механизм должен обеспечить эффективный поиск допускающей последовательности конфигураций для допустимых цепочек. В частности, может быть поставлена задача разработки алгоритма беступикового, или однопроходного, анализа. Беступиковый анализ имеет место, если получение тупиковой конфигурации в процессе анализа означает "неправильность" анализируемой цепочки, т.е. тот факт, что она не принадлежит языку, порождаемому заданной грамматикой. Беступиковый анализ, как можно показать, невозможен в случае произвольного КС-языка, но для некоторых (достаточно широких) классов КС-языков он может быть реализован. Некоторые алгоритмы беступикового синтаксического анализа мы очень коротко рассмотрим в этом дополнении.

Существуют две основные стратегии синтаксического анализа:

1) нисходящий анализ (называемый также анализом "сверху вниз", или анализом "разверткой");

2) восходящий анализ (анализ "снизу вверх", "сверткой").

В нисходящем анализе дерево вывода цепочки строится от корня к листьям, т.е. дерево вывода "реконструируется" в прямом порядке, и аксиома грамматики "развертывается" в цепочку. В восходящем анализе дерево вывода строится от листьев к корню и анализируемая цепочка "свертывается" в аксиому.

Рассмотрим две стратегии анализа по очереди.


Нисходящий анализ. LL(k)-грамматики

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

Существует класс грамматик, называемых LL(k)-грамматиками, в которых применяемая команда однозначно определяется:

1) прочитанной частью [cbm]w[/cbm] входной цепочки; эту цепочку [cbm]w[/cbm] называют левым контекстом;

2) находящимся в данный момент в верхней ячейке магазина нетерминальным символом [cbm]A[/cbm] ;

3) началом (префиксом) [cbm]{v}[/cbm] непрочитанной части цепочки, состоящим не более чем из [cbm]k[/cbm] букв [cbm](k\geqslant1)[/cbm] ; этот префикс называют аванцепочкой (рис. 8.37).

Методы синтаксического анализа КС языков

Эта информация, по которой беступиковый анализатор выбирает нужную команду на каждом шаге работы с входной цепочкой, организована в виде управляющей таблицы (конкретные формы таких таблиц будут рассмотрены ниже). При этом левый вывод цепочки [cbm]x=wvu[/cbm] , если [cbm]x\in L(G)[/cbm] , может быть представлен следующим образом: из аксиомы выводится цепочка [cbm]wA\alpha[/cbm] , затем нетерминал [cbm]A[/cbm] заменяется в соответствии с правилом [cbm]A\to\gamma[/cbm] и из цепочки [cbm]\gamma\alpha[/cbm] выводится терминальная цепочка [cbm]vu[/cbm] , где

[cbm]|v|\leqslant k,\qquad S\mathop{\vdash^{\ast}}\limits^{l} wA\alpha \mathop{\vdash}\limits^{l} w\gamma\alpha\mathop{\vdash^{\ast}}\limits^{l} wvu[/cbm] (символ [cbm]\mathop{\vdash}\limits^{l}[/cbm] означает левую выводимость).

Описанное выше представление левого вывода цепочки [cbm]wvu[/cbm] предполагает, что мы произвольно в этом выводе фиксировали некий шаг, состоящий в замене нетерминала [cbm]A[/cbm] посредством применения правила вывода [cbm]A\to\gamma[/cbm] . Так как в левом выводе на каждом шаге производится замена самого левого вхождения нетерминального символа, то слева от [cbm]A[/cbm] в цепочке [cbm]wA\alpha[/cbm] , полученной перед рассматриваемым шагом, должны быть только терминальные символы. Следовательно, определенный выше левый контекст [cbm]w[/cbm] есть не что иное, как левое крыло вхождения нетерминала [cbm]A[/cbm] в цепочку [cbm]wA\alpha[/cbm] .

Моделируя этот левый вывод, т.е. читая записанную на входной ленте цепочку [cbm]x=wvu[/cbm] , МП-автомат читает левый контекст [cbm]w[/cbm] , а затем с помощью управляющей таблицы, "видя" в магазине символ [cbm]A[/cbm] , учитывая левый контекст [cbm]w[/cbm] и зная аванцепочку [cbm]{v}[/cbm] , принимает единственно правильное решение, применяя команду, соответствующую правилу [cbm]A\to\gamma[/cbm] . Так на интуитивном уровне можно определить ключевое свойство LL(k)-грамматики.

Переходим теперь к построению формального определения LL(k)-грамматики.

Пусть дана КС-грамматика [cbm]G[/cbm] . Для цепочки а в объединенном алфавите грамматики [cbm]G[/cbm] и положительного натурального [cbm]k[/cbm] определим множество [cbm]F_k(\alpha)[/cbm] , состоящее из всех терминальных цепочек, которые либо выводятся из цепочки а (если их длина строго меньше [cbm]k[/cbm] ), либо являются k-буквенными префиксами терминальных цепочек, выводимых из [cbm]\alpha[/cbm] (обратим внимание на то, что везде речь идет о левом выводе).

Таким образом, [cbm]F_k(\alpha)= \bigl\{v\colon (\alpha\mathop{\vdash^{\ast}}\limits^{l}v)\& (|v|<k)\lor (\exists x\in V^{\ast})(\alpha\mathop{\vdash^{\ast}}\limits^{l}vx)\& (|v|=k)\bigr\}[/cbm] .

Нетрудно видеть, что для всякой терминальной цепочки [cbm]x[/cbm] получим [cbm]F_k(x)= \{x\}[/cbm] , если [cbm]|x|\leqslant k[/cbm] , и [cbm]F_k(x)= \{x(1)x(2)\ldots x(k)\}[/cbm] , если [cbm]|x|>k[/cbm] . Множества [cbm]F_k(\alpha)[/cbm] (для разных цепочек [cbm]\alpha[/cbm] ) иногда будем называть [cbm]F_k[/cbm] -множествами.


Пример 8.23. Зададим грамматику [cbm]G[/cbm] с терминальным алфавитом [cbm]\{a,b,c,d\}[/cbm] и нетерминальным алфавитом, состоящим из одной аксиомы [cbm]S[/cbm] , следующим множеством правил вывода:

[cbm]S\to aSbSc\mid aSb\mid bSc\mid d.[/cbm]

Вычислим множество [cbm]F_3(aSbSc)[/cbm] . Первая буква всех терминальных цепочек, выводимых из заданной, уже фиксирована — это буква [cbm]a[/cbm] . Нетерминал [cbm]S[/cbm] может быть заменен буквой [cbm]d[/cbm] , после чего возникнет трехбуквенный префикс [cbm]adb[/cbm] . Но символ [cbm]S[/cbm] можно заменить и цепочками [cbm]aSbSc,~ aSb,~bSc[/cbm] . В силу этого первые две буквы цепочки, выводимой из исходной, могут быть либо [cbm]aa[/cbm] , либо [cbm]ab[/cbm] . Продолжение вывода, как нетрудно понять, может дать третью букву — либо [cbm]a[/cbm] , либо [cbm]b[/cbm] , либо [cbm]d[/cbm] . Окончательно получаем

[cbm]F_3(aSbSc)= \{adb,\, aaa,\, aab,\, aad,\, aba,\, abb,\, abd\}.[/cbm]

Определение 8.11. КС-грамматику [cbm]G=(V,N,S,P)[/cbm] называют LL(k)-грамматикой (для произвольно фиксированного [cbm]k\geqslant1[/cbm] ), если для любых [cbm]w\in V^{\ast},~ A\in N,~\alpha\in(V\cup N)^{\ast}[/cbm] , таких, что существуют левые выводы

[cbm]S\mathop{\vdash^{\ast}}\limits^{l} wA\alpha\mathop{\vdash}\limits^{l} w\beta\alpha\mathop{\vdash^{\ast}}\limits^{l} wy,\quad S\mathop{\vdash^{\ast}}\limits^{l} wA\alpha\mathop{\vdash}\limits^{l} w\gamma\alpha\mathop{\vdash^{\ast}}\limits^{l} wz[/cbm] , из [cbm]F_k(y)=F_k(x)[/cbm] следует [cbm]\beta=\gamma[/cbm] .

Таким образом, из этого определения следует, что для LL(k)-грамматики левый контекст [cbm]w[/cbm] нетерминала [cbm]A[/cbm] в цепочке [cbm]wA\alpha[/cbm] и не более чем [cbm]k[/cbm] символов, с которых начинается терминальная цепочка [cbm]y[/cbm] , выводимая из [cbm]A\alpha[/cbm] , однозначно определяют то правило, которое нужно применить к цепочке [cbm]wA\alpha[/cbm] (заменяя в ней выделенное, т.е. первое, вхождение нетерминала [cbm]A[/cbm] ), чтобы сделать очередной шаг в левом выводе цепочки [cbm]wy[/cbm] (и именно этой цепочки!) из аксиомы грамматики [cbm]G[/cbm] . При совпадении множеств [cbm]F_k(y)[/cbm] и [cbm]F_k(z)[/cbm] , как следует из сформулированного определения, указанные два вывода "сливаются" в один, т.е. тогда [cbm]y=z[/cbm] .

Определение LL(k)-грамматики является само по себе труднопроверяемым. Нужно какое-то условие, проверка которого позволила бы дать ответ на вопрос, является ли заданная КС-грамматика LL(k)-грамматикой. Доказывается, что дать ответ на этот вопрос можно, только фиксировав число [cbm]k[/cbm] . Построить же алгоритм, отвечающий на вопрос, является ли данная КС-грамматика LL(k)-грамматикой для некоторого [cbm]k[/cbm] (не задавая его заранее), невозможно.

Следующая теорема (формулируемая без доказательства) дает соответствующий критерий (необходимое и достаточное условие) при фиксированном [cbm]k[/cbm] .


Теорема 8.12. КС-грамматика [cbm]G[/cbm] является LL(k)-грамматикой (для фиксированного [cbm]k\geqslant1[/cbm] ) тогда и только тогда, когда для любой цепочки [cbm]w\in V^{\ast}[/cbm] выполняется следующее условие: для любых [cbm]A\in N,~\alpha\in (V\cup N)^{\ast}[/cbm] , таких, что [cbm]S\mathop{\vdash^{\ast}}\limits^{l}[/cbm] , и любых двух различных правил [cbm]A\to\beta[/cbm] и [cbm]A\to\gamma[/cbm] грамматики [cbm]G[/cbm] имеет место [cbm]F_k(\beta\alpha)\cap F_k(\gamma\alpha)=\varnothing[/cbm] .

Условие теоремы называют часто LL(k)-условием. Его следует проверять, фиксируя по очереди левые контексты (т.е. различные цепочки [cbm]w[/cbm] ) для всех нетерминалов грамматики.

Рассмотрим пример, в котором, используя теорему 8.12, мы убедимся в том, что заданная КС-грамматика является LL(k)-грамматикой (для фиксированного [cbm]k[/cbm] ).


Пример 8.24. Грамматика [cbm]G[/cbm] задается системой правил

[cbm]S\to abA\mid\lambda,\quad (1)\mid(2)\quad\qquad A\to Saa\mid b.\quad (3)\mid(4)[/cbm]

Докажем, что данная грамматика является LL(2)-грамматикои. Чтобы проверить условие теоремы 8.12, достаточно для каждого нетерминала [cbm]B\in\{S,A\}[/cbm] нашей грамматики проделать следующее:

1) вычислить все такие цепочки [cbm]w\in\{a,b\}^{\ast}[/cbm] и [cbm]\alpha\{a,b,S,A\}[/cbm] , что имеет место левая выводимость

[cbm]S\mathop{\vdash^{\ast}}\limits^{l}wB\alpha;[/cbm]
(8.26)

2) фиксировав "левый контекст" [cbm]w[/cbm] , для каждой пары различных правил вывода [cbm]B\to\gamma[/cbm] и [cbm]B\to\beta[/cbm] вычислить множества [cbm]F_2(\beta\alpha)[/cbm] и [cbm]F_2(\gamma\alpha)[/cbm] . Для всех таких а, что при фиксированном w выполняется (8.26), и убедиться в том, что их пересечение пусто.

Если выполнение пункта 2 для всех возможных левых контекстов w и всех нетерминалов В подтвердит истинность условия теоремы 8.12, то тем самым и будет доказано, что перед нами LL(2)-грамматика.

Следует заметить, что в общем случае вычисление пар цепочек [cbm](w,\alpha)[/cbm] , удовлетворяющих условию (8.26) (для всех нетерминалов [cbm]B[/cbm] КС-грамматики), требует применения специального алгоритма. Но для конкретной грамматики нашего примера эти пары цепочек достаточно просто вычисляются из анализа выводов грамматики. По очереди проанализуем оба нетерминала, т.е. [cbm]S[/cbm] и [cbm]A[/cbm] , грамматики [cbm]G[/cbm] .


Нетерминал S

В этом случае имеем, во-первых, тривиальную выводимость [cbm]S\vdash^0S[/cbm] за нуль шагов, т.е. в этом случае цепочки [cbm]w[/cbm] и [cbm]\alpha[/cbm] обе являются пустыми: [cbm]w=\alpha=\lambda[/cbm] . Нетерминал S может быть заменен согласно правилу (1) с правой частью [cbm]abA[/cbm] или согласно правилу (2) с пустой правой частью. Вычислим тогда множества [cbm]F_2(abA)[/cbm] и [cbm]F_2(\lambda)[/cbm] . Ясно, что [cbm]F_2(abA)= \{ab\}[/cbm] , а [cbm]F_2(\lambda)=\{\lambda\}[/cbm] и эти множества не пересекаются.

Проанализируем теперь, каким образом в заданной грамматике может быть выведена из аксиомы [cbm]S[/cbm] за число шагов, большее нуля, цепочка вида [cbm]wS\alpha[/cbm] для некоторых терминальной цепочки [cbm]w[/cbm] и цепочки в объединенном алфавите [cbm]\alpha[/cbm] .

Так как вхождение [cbm]S[/cbm] может возникнуть только после применения правила (3), а чтобы применить его, нужно сначала применить правило (1), то, чередуя применение этих правил [cbm]n\geqslant1[/cbm] раз, получим вывод:

[cbm]S\vdash abA\vdash abSaa\vdash ababAaa\vdash ababSaaaa\vdash \ldots\vdash (ab)^nS(aa)^n.[/cbm]
(8.27)

Это значит, что все возможные пары [cbm](w,\alpha)[/cbm] , такие, что [cbm]S\mathop{\vdash^{\ast}}\limits^{l}wS\alpha[/cbm] (с учетом уже ранее рассмотренного случая, когда обе цепочки пусты), есть [cbm]w=(ab)^n[/cbm] и [cbm]\alpha=(aa)^n,~ n\geqslant0[/cbm] .

Вычисляем множества [cbm]F_2(abA(aa)^n)[/cbm] и [cbm]F_2(\lambda(aa)^n)[/cbm] для различных [cbm]n\geqslant0[/cbm] . Первое множество, как нетрудно видеть, для всех [cbm]n[/cbm] будет равно [cbm]\{ab\}[/cbm] , a второе при [cbm]n=0[/cbm] будет состоять из одной пустой цепочки, а при [cbm]n>0[/cbm] — из цепочки [cbm]aa[/cbm] , т.е. можно утверждать, что для всех [cbm]n\geqslant0[/cbm] пересечение

[cbm]F_2\bigl(abA(aa)^n\bigr)\cap F_2\bigl(\lambda(aa)^n\bigr)=\varnothing.[/cbm]

Итак, для нетерминала [cbm]S[/cbm] (аксиомы грамматики [cbm]G[/cbm] ) условие теоремы 8.12 выполнено.


Нетерминал A

Рассматривая вывод (8.27), легко убедиться в том, что все пары [cbm](w,\alpha)[/cbm] , для которых имеет место левая выводимость [cbm]S\mathop{\vdash^{\ast}}\limits^{l} wA\alpha[/cbm] , есть [cbm]w=(ab)^n,~ \alpha=(aa)^{n-1}[/cbm] для всех [cbm]n\geqslant1[/cbm] .

Нетерминал [cbm]A[/cbm] является левой частью двух правил вывода (3) и (4) с правыми частями [cbm]Saa[/cbm] и [cbm]b[/cbm] соответственно. Вычисляем соответствующие F2-множества: [cbm]F_2(Saa(aa)^{n-1})=\{ab,aa\}[/cbm] , а [cbm]F_2(b(aa)^{n-1})=\{b\}[/cbm] , если [cbm]n=1[/cbm] , и [cbm]F_2(b(aa)^{n-1})=\{ba\}[/cbm] , если [cbm]n>1[/cbm] . Как видно, при всех [cbm]n[/cbm] пересечение указанных множеств пусто. Тем самым доказано, что и для нетерминала А критерий теоремы 8.12 выполнен и заданная грамматика является LL(2)-грамматикой.

Полученный результат показывает также, что эта грамматика является LL(2)-грамматикой, не являясь LL(1)-грамматикой. Действительно, для нетерминала [cbm]S[/cbm] получим

[cbm]F_1(abA(aa)^n)=\{a\}[/cbm] при всех [cbm]n\geqslant0[/cbm] , а [cbm]F_1(\lambda(aa)^n)=\{a\}[/cbm] при всех [cbm]n\geqslant1[/cbm] .

Следовательно, при всех [cbm]n\geqslant1[/cbm] указанные множества совпадут, что означает невыполнение LL(1)-условия. Заметим, что для нетерминала [cbm]A[/cbm] LL(1)-условие выполняется.

Результаты анализа представлены в табл. 8.1.

[cbm]\begin{array}{|c|c|c|c|c|c|c|c|}\multicolumn{8}{r}{\mathit{Table~8.1}} \\\hline \begin{matrix}\\[-12pt] \text{Neterminal} \\[-12pt] \end{matrix} & \multicolumn{7}{c}{\text{Avancepochka}}\vline \\\cline{2-8} & aa& ab& ba& bb& a& b& \lambda\\\hline S& 2&1&-&-&-&-&2\\ A& 3&3&4&-&-&4&-\\\hline \end{array}[/cbm]

Внутри таблицы указаны номера применяемых правил. Прочерк означает, что данная пара (нетерминал, аванцепочка) не определяет никакого правила, и возникновение такой пары в процессе анализа сигнализирует о синтаксической ошибке.

Мы видим, что в данном случае номер применяемого на каждом шаге правила вывода однозначно определяется только двумя факторами: нетерминалом в верхней ячейке магазина и аванцепочкой. LL(k)-грамматики, в которых выполняется такое условие, называют сильными LL(к)-грамматиками.

Таблица подобного вида для сильной LL(k)-грамматики и является примером управляющей таблицы. Именно она обеспечивает в данном случае тот механизм управления выводом, который позволяет МП-автомату, построенному по заданной сильной LL(k)-грамматике, на каждом шаге однозначно выбирать правило вывода и для "правильной" цепочки строить ее левый вывод, а для "неправильной" — сигнализировать об ошибке.

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

Пример 8.25. Зададим грамматику [cbm]G_1[/cbm] системой правил

[cbm]\begin{array}{ll}S\to aAaa\mid bAba,&\qquad (1)\mid(2)\\ A\to b\mid\lambda.&\qquad (3)\mid(4) \end{array}[/cbm]

Для этой грамматики легко построить все ее деревья вывода (рис. 8.38) и проверить LL(k)-условие.

Методы синтаксического анализа КС языков

В данном случае [cbm]S\mathop{\vdash^{\ast}}\limits^{l}wS\alpha[/cbm] влечет [cbm]w=\lambda,~ \alpha=\lambda[/cbm] и [cbm]F_2(aAaa)=\{ab,aa\}[/cbm] , а [cbm]F_2(bAba)=\{bb\}[/cbm] , то есть [cbm]F_2(aAaa)\cap F_2(bAba)=\varnothing[/cbm] .

Из [cbm]S\mathop{\vdash^{\ast}}\limits^{l}wS\alpha[/cbm] следует, что [cbm]w=a[/cbm] или [cbm]w=b[/cbm] . Если [cbm]w=a[/cbm] , то [cbm]\alpha=aa[/cbm] .

Если же [cbm]w=b[/cbm] , то [cbm]\alpha=ba[/cbm] и [cbm]F_2(bba)=\{bb\},~ F_2(\lambda ba)= \{ba\}[/cbm] , и в этом случае также [cbm]F_2(bba)\cap F_2(\lambda ba)=\varnothing[/cbm] . Таким образом, рассматриваемая грамматика есть LL(2)-грамматика.

Сведем полученные результаты в табл. 8.2.

[cbm]\begin{array}{|c|c|c|c|}\multicolumn{4}{r}{\mathit{Table~8.2}} \\\hline \text{Leviy~kontekst}& \text{Neterminal}& \text{Avancepochka}& \text{Primenyamoe~pravilo}\\\hline \lambda& S& ab& (1)\\ & & aa& (1)\\\hline \lambda& S& bb& (2)\\\hline a& A& ba& (3)\\ & & aa& (4)\\\hline b& A& bb& (3)\\ & & ba& (4)\\\hline \end{array}[/cbm]

Из табл. 8.2 следует, что одна и та же пара [cbm](A,ba)[/cbm] не определяет однозначно применяемого правила и требуется информация о левом контексте.

Из этой же таблицы видно, что данная грамматика не является LL(1)-грамматикой, поскольку, например, однобуквенная аванцепочка [cbm]b[/cbm] вместе с нетерминалом [cbm]A[/cbm] и левым контекстом [cbm]b[/cbm] не определяет однозначно применямого правила.


Таким образом, для сильных LL(k)-грамматик МП-автомат, который строится по КС-грамматике, может быть преобразован в синтаксический анализатор путем добавления к нему управляющей таблицы и выходной ленты (первоначально пустой), на которой автомат пишет номера правил в порядке их применения, а также сигнал ошибки. В результате анализа для правильной цепочки, записанной на входной ленте, на выходной ленте появится ее левый вывод (точнее, "протокол" левого вывода в виде последовательности номеров применимых правил), а для неправильной цепочки на выходной ленте появится сообщение об ошибке (в виде какого-нибудь специального символа).

Представим теперь протоколы анализа некоторых цепочек в грамматике [cbm]G[/cbm] примера 8.24.

Пусть [cbm]x=ababbaa[/cbm] ; имеем последовательность конфигураций (четвертая компонента конфигурации — содержимое выходной ленты):

[cbm]\begin{aligned}(q,ababbaa,S,\lambda)&\vdash (q,ababbaa,abA,1)\vdash^2 (q,abbaa, A,1)\vdash (q,abbaa,S,13)\vdash\\ &\vdash (q,abbaa,abAaa,131)\vdash^2 (q,baa,Aaa,131)\vdash\\ &\vdash (q,baa,baa,1314)\vdash^3 (q,\lambda,\lambda,1314). \end{aligned}[/cbm]

Обратим внимание на то, что на каждом шаге вывода наш автомат-анализатор в существенном отличии от обычного распознавателя, который может легко "заблудиться" (особенно при выборе альтернативы для нетерминала [cbm]A[/cbm] ), использует информацию управляющей таблицы.

Посмотрим, как отработает такой анализатор синтаксическую ошибку. Берем цепочку [cbm]y=abbb[/cbm] , имеем

[cbm](q,abbb,S,\lambda)\vdash (q,abbb,abA,1)\vdash^2 (q,bb,A,1)\vdash (q,bb,A, 1"ERROR"),[/cbm]

так как пара [cbm](A,bb)[/cbm] не определяет никакого правила.

Для не сильной LL(k)-грамматики учет левых контекстов в общем случае весьма сложен, и мы его здесь не рассматриваем.

Приведем, наконец, простой пример грамматики с терминальным алфавитом [cbm]\{a,b,0,1\}[/cbm] , не являющейся LL(k)-грамматикой ни для какого [cbm]k\colon[/cbm]

[cbm]S\to A\mid B,\qquad A\to aAb\mid0,\qquad B\to aBbb\mid1.[/cbm]

Для любого [cbm]k\geqslant1[/cbm] имеем [cbm]S\mathop{\vdash}\limits^{l} A\mathop{\vdash^{\ast}}\limits^{l} a^k0b^k[/cbm] , [cbm]S\mathop{\vdash}\limits^{l} B\mathop{\vdash^{\ast}}\limits^{l} a^k1b^{2k}[/cbm] .

Одинаковый префикс [cbm]a^k[/cbm] не дает возможности отождествить цепочки [cbm]\beta=A[/cbm] и [cbm]\gamma=B[/cbm] , т.е. нет возможности обеспечить выбор альтернативы для нетерминала [cbm]S[/cbm] .

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: