Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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


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


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


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

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


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


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




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


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


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


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

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

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


Схема аеанцепочки

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


[math]|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[/math] (символ [math]\mathop{\vdash}\limits^{l}[/math] означает левую выводимость).

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


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


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


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


Таким образом, [math]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\}[/math].


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




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


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

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


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

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


[math]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[/math], из [math]F_k(y)=F_k(x)[/math] следует [math]\beta=\gamma[/math].

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


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


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




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


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


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




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


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

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


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


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

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


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


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




Нетерминал S


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


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


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


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

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


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


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

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




Нетерминал A


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


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


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


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

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


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


[math]\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}[/math]

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


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


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


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


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


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

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


Деревья вывода грамматики

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


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


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


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


[math]\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}[/math]

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


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




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


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


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


[math]\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}[/math]

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


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


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

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

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


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


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

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


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved