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

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

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

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

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


Восходящий синтаксический анализ и LR(k)-грамматики

Восходящий синтаксический анализ и LR(k)-грамматики


Ключевым понятием при рассмотрении восходящего синтаксического анализа является понятие основы.


Определение 8.12. Пусть [math]G=(V,N,S,P)[/math] — КС-грамматика, [math]\xi[/math] — цепочка в объединенном алфавите, [math]A\to\alpha\in P[/math]. При [math]\alpha\sqsubseteq \xi[/math] вхождение [math]\alpha[/math] в [math]\xi~(\beta,\alpha,\gamma)[/math] называют основой, если цепочка [math]\beta A\gamma[/math] выводима из аксиомы [math]S[/math] при условии, что цепочка [math]\xi[/math] выводима из аксиомы [math]S[/math].


Таким образом, по определению, основа — это такое вхождение правой части некоторого правила КС-грамматики в некоторую выводимую из аксиомы цепочку, что после замены этой правой части соответствующим нетерминалом полученная цепочка снова будет выводимой из аксиомы. Заметим, что для не выводимой из аксиомы цепочки любое вхождение правой части некоторого правила в нее можно считать основой.


Замечание 8.13. Ни в коем случае нельзя путать понятие основы в смысле определения 8.12 с понятием основы вхождения.


Пример. Рассмотрим грамматику, задаваемую системой правил:


[math]S\to Ac\mid Bd,\qquad A\to aAb\mid ab,\qquad B\to aBbb\mid abb.[/math]

Возьмем цепочку [math]x=aabbbbd[/math]. Мы видим здесь вхождения двух правых частей правил — [math]ab[/math] и [math]abb[/math]. Вхождение первой цепочки не является основой. Действительно, заменяя [math]ab[/math] нетерминалом [math]A[/math], получим цепочку [math]aAbbbd[/math]. Для этой цепочки существует единственное правило [math]A\to aAb[/math], правая часть которого входит в нее. "Свертывая" цепочку [math]aAb[/math] в нетерминал [math]A[/math], получим [math]Abbd[/math] — слово, в которое не входит ни одна правая часть какого-либо правила данной грамматики. Следовательно, ни полученная цепочка, ни предшествующая ей цепочка не являются выводимыми из аксиомы.


Возвращаемся к цепочке [math]x[/math] и, заменяя подцепочку [math]abb[/math] нетерминалом [math]B[/math], получаем [math]aBbbd[/math], где единственное вхождение правой части правила — [math]aBbb[/math]. Производя замену этого правила нетерминалом [math]B[/math], будем иметь цепочку [math]Bd[/math], которая "свертывается" в аксиому [math]S[/math]. Итак, мы провели в обратном порядке вывод цепочки [math]x[/math] из аксиомы:


[math]S\vdash Bd\vdash aBbbd\vdash aabbbbd.[/math]



Задача восходящего синтаксического анализа


Задача восходящего анализа и состоит в поиске "редукции" исходной терминальной цепочки в аксиому, где на каждом шаге производится поиск основы в текущую цепочку с последующей заменой ее соответствующим нетерминалом, т.е. применяется "инверсия" некоторого правила данной КС-грамматики: правая часть правила заменяется левой. Нетрудно понять, что если мы заменяем на каждом шаге такой "редукции" самую левую основу, то восстанавливаем с конца к началу правый вывод исходной цепочки, а если самую правую основу, то "реконструируем" левый вывод.


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


Один из методов состоит в сопоставлении каждому правилу КС-грамматики некоторого бинарного отношения на множестве [math](V\cup N)^{\ast}[/math]. Вхождение правой части некоторого правила является основой тогда и только тогда, когда его крылья принадлежат сопоставленному данному правилу бинарному отношению. Проблему единственности определяемой таким образом основы, равно как и проблему характеристики класса КС-грамматик, допускающих такую "параметризацию" бинарными отношениями, мы здесь не рассматриваем*.


Ограничимся простым примером.


Рассмотрим грамматику, порождающую множество непустых палиндромов в заданном алфавите [math]V\colon[/math]


[math]S\to\alpha S\alpha\mid\alpha\alpha\mid\alpha,\quad \alpha\in V.[/math]

Каждому правилу сопоставим одно и то же отношение [math]\{(u,v)\colon|u|=|v|\}[/math] так, что этому отношению принадлежат только пары с одинаковой длиной компонент.


Тогда осуществима беступиковая редукция любого палиндрома. Например:


[math]abbccbba\dashv abbSbba\dashv abSba\dashv aSa\dashv S.[/math]

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


[math]abbccbba\dashv aSccbba\dashv aSSbba\dashv aSSSa.[/math]

Неверное определение основы на первом шаге редукции привело к тупиковой (т.е. не содержащей ни одного вхождения правой части какого-либо правила) цепочке, хотя входная цепочка является правильной.


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




LR(k)-грамматика


Неформально LR(k)-грамматика, [math]k\geqslant0[/math], — это КС-грамматика, в которой основа однозначно определяется по левому крылу вхождения правой части некоторого правила вывода ("левому контексту") и по не более чем k-буквенному префиксу правого крыла ("правого контекста"). Строго понятие LR(k)-грамматики вводится весьма сложно, и мы его опускаем.


Оказывается, что класс языков, порождаемых LR(k)-грамматиками, может быть охарактеризован в терминах детерминированных МП-автоматов (ДМП-автоматов).


Прежде чем определять ДМП-автоматы, введем в рассмотрение модификацию МП-автомата, называемую расширенным МП-автоматом, которая как раз ориентирована на представление восходящего синтаксического анализа.


Говоря коротко, отличие расширенного МП-автомата от обычного состоит в том, что в магазине можно заменять не только верхний символ, но и непустую цепочку символов, расположенную в верхних ячейках магазина, так, что первый ее символ есть верхний символ магазина, второй символ — символ, расположенный под верхним, и т.д.


Формально расширенный МП-автомат определяется совершенно так же, как обычный (см. определение 8.7), но функция переходов задается системой команд вида [math]qa\alpha\to r\beta[/math], где [math]a\in V\cup\{\lambda\}[/math]; [math]\alpha[/math] и [math]\beta[/math] — магазинные цепочки, причем [math]\alpha[/math] не пуста.


При записи системы команд расширенного МП-автомата условимся записывать магазинные цепочки от "дна" магазина к его "верху".


Можно доказать, что расширенные МП-автоматы допускают в точности тот же класс языков, что и обычные, т.е. можно доказать, что по любому расширенному МП-автомату можно построить эквивалентный ему МП-автомат в смысле определения 8.7. Далее будем говорить "МП-автомат", имея в виду расширенный МП-автомат.


Определение 8.13. МП-автомат называют детерминированным (ДМП-автоматом), если из любой его конфигурации непосредственно выводится не более чем одна конфигурация.


Нетрудно доказать следующее утверждение.


Теорема 8.13. МП-автомат является ДМП-автоматом тогда и только тогда, когда для любой упорядоченной пары [math](q,\alpha)\in Q\times\Gamma^{+}[/math] верно одно из двух:


1) для любого [math]a\in V[/math] существует не более одной команды с левой частью [math]qa\alpha[/math], причем если для некоторого [math]a\in V[/math] такая команда существует, то не существует команды с левой частью [math]q\lambda\alpha[/math] и не существует ни одной команды с левой частью [math]qa'\alpha'[/math], где [math]a'\in\{a,\lambda\}[/math] и [math]\alpha'[/math] является концом цепочки [math]\alpha[/math];


2) существует не более одной команды с левой частью [math]q\lambda\alpha[/math], причем если такая команда существует, то не существует ни одной команды с левой частью [math]qa\alpha'[/math], где [math]a\in V\cup\{\lambda\}[/math] и [math]\alpha'[/math] — конец цепочки [math]\alpha[/math], и не существует ни одной команды с левой частью [math]qa\alpha,~a\in V[/math].




Связь между ДМП-автоматами и LR(k)-грамматиками


Связь между ДМП-автоматами и LR(k)-грамматиками устанавливается следующей теоремой.


Теорема 8.14. Язык допускается ДМП-автоматом тогда и только тогда, когда он порождается некоторой LR(k)-грамматикой.


Определение 8.14. Язык называют детерминированным КС-языком, если он допускается некоторым ДМП-автоматом.


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


Для детерминированных КС-языков может быть предложена стратегия восходящего анализа, называемая стратегией "перенос–свертка". Суть ее состоит в следующем: входная цепочка посимвольно переписывается в магазин до тех пор, пока в магазине не сформируется основа (однозначно определяемая прочитанной частью цепочки и не более чем [math]k[/math] буквами непрочитанной части для некоторого фиксированного [math]k\geqslant0[/math]).


Сформированная в магазине основа заменяется соответствующим нетерминалом. Если после этой замены в верхних ячейках магазина опять получилась основа, то она вновь "свертывается" в нетерминал, и так до тех пор, пока не окажется, что либо вся входная цепочка прочитана, а в магазине кроме начального символа в верхней ячейке осталась аксиома грамматики, либо цепочка еще не прочитана, а в верху магазина основы нет, либо, наконец, цепочка прочитана, а в верху магазина ни аксиомы, ни основы нет.


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


Согласно теореме 8.14, подобный алгоритм может быть запрограммирован в системе команд некоторого ДМП-автомата (точнее, ДМП-автомата с выходной лентой, на которой записываются номера применяемых правил грамматики и/или сигнал ошибки).


Строгая теория LR(k)-грамматик весьма сложна и никак не может быть даже фрагментарно изложена в рамках настоящего курса.




Мы рассмотрим в заключение один пример.


Пример 8.26. Приведем ДМП-автомат для анализа языка правильных скобочных структур, порождаемых грамматикой [math]S\to()\mid(S)\mid SS[/math]. Точнее, мы рассмотрим язык правильных скобочных структур с "концевым маркером" [math]\star[/math]: записывая на ленту правильную скобочную структуру, в конце ставим символ [math]\star[/math].


Система команд анализирующего ДМП-автомата имеет следующий вид:


[math]\begin{array}{lrlrlr}q_0a\Box\to q_1\Box a,&(1)&\qquad q_1\lambda(S)\to q_1S,&(4)& \qquad q_1\lambda\Box a\to q_0\Box a,&(7)\\[2pt] q_0aa'\to q_1a'a,&(2)&\qquad q_1\lambda SS\to q_1S,&(5)& \qquad q_1a\Box S\to q_1\Box Sa,&(8)\\[2pt] q_1\lambda()\to q_1S,&(3)&\qquad q_1\lambda\gamma\to q_0\gamma,&(6)&\qquad q_1\star\Box S\to q_2\Box.&(9)\\ \end{array}[/math]

В этой системе команд [math]q_0[/math] и [math]q_2[/math] — соответственно начальное заключительное состояния; [math]a\in\{(,)\};~a'\in\{(,),S\};~\Box[/math] — начальный символ магазина (называемый иногда "маркером дна магазина"); [math]\gamma[/math] — произвольная цепочка, длина которой равна 3 и которая не равна [math](S)[/math] и не оканчивается цепочкой [math]()[/math] или [math]SS[/math].


Легко убедиться в том, что записанная система команд действительно определяет ДМП-автомат (см. теорему 8.13).


Команды (1) и (2) обеспечивают перенос в магазин входной цепочки, команды (3)-(5) — команды свертки, команды (6)-(8) обеспечивают переход из фазы свертки в фазу переноса, если в магазине нет основы, а команда (9) переводит автомат в заключительное ("допускающее") состояние в случае правильной входной цепочки.


Проанализируем на данном ДМП-автомате цепочку [math]x=(())()\star[/math], которая является правильной скобочной структурой. Имеем последовательность конфигураций*:


[math]\begin{aligned} \boldsymbol{\big\langle} q_0,(())()\star,\Box\boldsymbol{\big\rangle} &\vdash \boldsymbol{\big\langle} q_1,())()\star,\Box(\boldsymbol{\big\rangle} \vdash \boldsymbol{\big\langle} q_0,())()\star,\Box(\boldsymbol{\big\rangle} \vdash \boldsymbol{\big\langle} q_1,))()\star,\Box((\boldsymbol{\big\rangle} \vdash \boldsymbol{\big\langle} q_0,))()\star,\Box((\boldsymbol{\big\rangle}\vdash\\[4pt] &\vdash \boldsymbol{\big\langle} q_1,)()\star,\Box(()\boldsymbol{\big\rangle}\vdash \boldsymbol{\big\langle} q_1,)()\star, \Box(S\boldsymbol{\big\rangle}\vdash \boldsymbol{\big\langle} q_0,)()\star,\Box(S\boldsymbol{\big\rangle}\vdash \boldsymbol{\big\langle} q_1,()\star,\Box(S)\boldsymbol{\big\rangle} \vdash\\[4pt] &\vdash \boldsymbol{\big\langle} q_1,()\star,\Box S\boldsymbol{\big\rangle}\vdash\boldsymbol{\big\langle} q_1,)\star,\Box S(\boldsymbol{\big\rangle}\vdash\boldsymbol{\big\langle} q_0,)\star,\Box S(\boldsymbol{\big\rangle}\vdash \boldsymbol{\big\langle} q_1,\star,\Box S()\boldsymbol{\big\rangle}\vdash \\[4pt] &\vdash \boldsymbol{\big\langle} q_1,\star,\Box SS\boldsymbol{\big\rangle}\vdash \boldsymbol{\big\langle} q_1,\star,\Box S\boldsymbol{\big\rangle}\vdash \boldsymbol{\big\langle} q_2,\lambda,\Box \boldsymbol{\big\rangle}. \end{aligned}[/math]

*Здесь мы использовали угловые скобки [math]\langle\rangle[/math] для обозначения конфигураций, чтобы не путать с круглыми скобками [math]()[/math], являющимися терминалами грамматики.


Рассмотрение перехода от LR(k)-грамматик к ДМП-автоматам и наоборот выходит за рамки нашего изложения. На простейшем примере мы продемонстрировали только работу детерминированного восходящего анализатора.


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


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

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