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

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

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

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


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

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


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


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


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


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


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

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


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


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




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


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


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


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

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

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


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

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


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

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


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


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


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


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


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




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


S\to aSbSc\mid aSb\mid bSc\mid d.

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


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

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


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

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


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


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




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


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


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




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


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

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


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


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

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


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


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




Нетерминал S


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


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


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


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

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


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


F_2\bigl(abA(aa)^n\bigr)\cap F_2\bigl(\lambda(aa)^n\bigr)=\varnothing.

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




Нетерминал A


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


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


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


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

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


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


\begin{aligned}&\mathit{Table~8.1} \qquad\qquad\qquad \text{Avancepochka}\\&\begin{array}{|c||c|c|c|c|c|c|c|} \hline \text{Neterminal} & aa& ab& ba& bb& a& b& \lambda\\\hline S& 2&1&-&-&-&-&2\\ A& 3&3&4&-&-&4&-\\\hline \end{array}\end{aligned}

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


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


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


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


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


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

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


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

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


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


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


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


\begin{aligned}\mathit{Table~8.2}~&\\ \begin{array}{|c|c|c|c|}\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}& \end{aligned}

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


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




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


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


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


\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}

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


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


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

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

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


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


S\to A\mid B,\qquad A\to aAb\mid0,\qquad B\to aBbb\mid1.

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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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