Главная Промышленная автоматика.

ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

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

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

Алгоритмы, рассматриваемые во втором разделе главы, носят табличный характер; это алгоритм Кока-Янгера - Касами и алгоритм Эрли. Они затрачивают емкость и время п. Алгоритм Эрли работает для любой КС-грамматики и для пего требуется время п, если грамматика однозначная.

Алгоритмы этой главы включены в книгу главным образом для того, чтобы пояснить внутренние проблемы, связанные с построением анализаторов. С самого начала следует вполне определенно заявить, что в большинстве практических применений надо избегать возвратных алгоритмов разбора. Даже табличные методы (а они асимптотически гораздо более быстрые, чем алгоритмы с возвратами) неприемлемы, если для интересующего нас языка существует грамматика, к которой применимы более эффективные алгоритмы, описываемые в гл. 5 и 6. Можно почти не сомневаться в том, что фактически для всех языков программирования существуют легко анализируемые грамматики, к которым эти алгоритмы применимы.

Методы данной главы могут оказаться полезными в таких приложениях, когда исходные грамматики не обладают теми специальными свойствами, которых требуют алгоритмы, рассматриваемые в гл. 5 и 6. Например, если требуются неоднозначные

4.1, синтаксический анализ с возвратами

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

4.1. СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ

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

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

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

В этом разделе мы опишем, как можно детерминированно моделировать недетерминированный МП-преобразователь, используя возвраты. Затем исследуем два специальных случая. Первый- нисходящий анализ с возвратами, при котором для входной цепочки строится левый разбор. Во втором случае восходящий анализ с возвратами дает правый разбор.

4>1.1. Моделирование МП-преобразователя

Рассмотрим МП-преобразователь Р и лежащий в его основе МП-автомат М. Если дана входная цепочка w, то нам было бы Удобно знать, что. Хотя М может недетерминированно перепро-



Допустим, ЧТО нам надо разобрать входную цепочку аасЬс. На рис. 4.1 изображено дерево, представляющее возможные последовательности тактов, которые может сделать Т для этого входа.

Cfi с г

Рис. 4.1. Последовательности тактов анализатора.

Вершина Cq представляет начальную конфигурацию {q, aacbc, S, е). Правила, определяющие Т, показывают, что из Со можно перейти в две следующие конфигурации, а именно Cy-{q, acbc, SbS, 1) и = ((/, acbc,S, 2). (Упорядочение здесь произвольное.) Из анализатор Т может перейти в конфигурации - (, с6б\ 11) и = (9, б-6с, SbS, 12). Из с3м0жно перейти в конфигурации Cjj [q, cbc, SbS, 21) и = (9, cbc, S, 22). Остальные конфигурации определяются однозначно.

Один из способов нахождения всех разборов данной входной цепочки состоит в определении всех допускающих конфигураций, достижимых из Со в дереве конфигураций. Это можно сделать, прослеживая все возможные пути, начинающиеся в Сц и заканчивающиеся в конфигурации, из которой дальнейший переход невозможен. Можно ввести порядок, в котором будут перебираться пути, упорядочив выборы очередных тактов, доступных анализатору Т, для. каждой комбинации состояния, входного символа и верхнего символа магазина. Например, в том случае, когда применимо правило 6(9, а, S), возьмем (9, SbS, 1) в качестве первого выбора и (9, S, 2) - в качестве второго выбора.

Посмотрим теперь, как можно определить все допускающие Конфигурации анализатора Т, систематически прослеживая все возможные для Т последовательности тактов. Допустим, что из 0, делая первый выбор, мы получаем Q. Из С у, снова делая Первый выбор, получаем С3. Продолжая в том же духе, мы прослеживаем последовательность конфигураций С, С, С, С, е, е.. Веритина С. представляет заключительную конфигура-.ию (9, е, bS, 1133), которая не является допускающей. Чтобы

бовать много гюследовательностей тактов, каждая из них ограничена по длине. Если это так, то последовательности можно перепробовать в некотором разумном порядке. Если для входа W возможны бесконечные последовательности тактов, то по крайней мере в одном смысле нельзя осуществить полное прямое моделирование МП-автомата М.

Определеиие. МП-автомат M = (Q, 2, Г, б, Qo, Zo, F) называется незациклиеающимсЯу если для каждой цепочки wY: найдется такая константа k, что если (q, Zo)h-"((7. У) то k. МП-преобразователь назовем незацикливающимся, если лежащий в его основе МП-автомат незацикливающийся.

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

Заметим, что условие отсутствия циклов и е-правил на самом деле не очень ограничительно. Для каждого КС-языка существует грамматика, удовлетворяющая этим условиям, и, более того, ее можно получить из произвольной КС-грамматики, порождающей этот язык, с помощью простых преобразований (алгоритмы 2.10 и 2.11). Далее, если исходная грамматика однозначна, то преобразованная грамматика лево- и правопокрывает ее. Отсутствие левой рекурсии в этом смысле более стеснительное условие. Хотя для каждого КС-языка существует грамматика без левой рекурсии (теорема 2.18), может не быть покрывающей грамматики, удовлетворяющей этому условию (см. упр. 3.4.29).

Для того чтобы продемонстрировать, что такое анализ с возвратами и вообще моделирование недетерминированного МП-преобразователя, рассмотрим грамматику G с правилалш

(1) S~-aSbS

(2) S-aS

(3) Sc

Левым анализатором для G служит МП-преобразователь Т с функцией переходов, определяемой равенствами

6(9, а, S) = {(9, SbS: 1), (q, S, 2)} 6(9, с, S) = {iq, e, 3)\ 6(9. b, b) = {iq, e)}



определить, существует ли другая заключительная конфигурация, МОЖНО вернуться (сделать «возврат») по дереву, пока не встретится конфигурация, для которой возможен другой, еще не рассмотренный выбор очередного такта. Поэтому мы должны быть в с0ст0ян1ш восстановить конфигурацию по конфигурации С7. Возврат к из С, может включать обратный сдвиг головки на входе, восстановление предыдущего содержимого магазина и удаление выходных символов, выданных при переходе от Сб к С. Восстановив С, мы должны сделать новый выбор очередного такта (если таковой возможен). Так как в вершине Q других выборов нет, мы продолжаем возврат к Сь и далее к Cg и Cj. ;

Из Cj; с помощью второго выбора такта для правила б (<?, а, S) можно получить конфигурацию С. Затем, переходя через конфигурации Сд и Cq, можно получить конфигурацию С - {q, е, е, 1233), которая оказывается допускающей.

После этого можно выдать в качестве выхода левый разбор 1233. Если мы заинтересованы в получении только одного разбора входной цепочки, то можно остановиться. Но если нас интересуют все разборы, можно вернуться к конфигурации С и затем испробовать все конфигурации, достижимые из С. Вершина С представляет другую допускающую конфигурацию, а именно [q, е, е, 2133).

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

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

) Лучше было бы назвать такой алгоритм переборным. Термин «недетерминированный алгоритм» обычно употребляют в том же смысле, что и «не* детернинираааиный автомат» (произвольного типа). - Прим. перев.

При синтаксическом анализе задается обычно грамматика, а не МП-преобразователь. Поэтому мы обсудим сейчас восходящий и нисходящий анализ прямо в терминах заданной грамматики, а не левого или правого анализатора для нее. Однако способ работы соответствующих алгоритмов состоит именно в последовательном моделировании анализатора с магазинной памятью. Но вместо обхода всевозможных последовательностей тактов анализатора мы будем обходить всевозможные выводы, совместимые с данным входом.

4.1.2. Неформальное описание нисходящего разбора

Происхождение названия нисходящего синтаксического анализа связано с тем, что дерево разбора входной цепочки строится сверху вниз, начиная с корня и нисходя к листьям. Начнем с того, что возьмем какую-нибудь грамматику н для каждого нетерминала занумеруем в некотором порядке все правые части правил, у которых левой частью является данный нетерминал (их называют альтернативами этого нетерминала), т. е. если А--cCj I ...I а„ - все Л-правила данной грамматики, то припишем некоторый порядок цепочкам а- (альтернативам нетерминала А).

Например, рассмотрим грамматику, упомянутую в предыдущем разделе. Ее S-правила

S~aSbSlaS\c

будем использовать в том порядке, как они написаны, т. е. aSbS будет первой альтернативой нетерминала S, aS - второй и с-третьей. Допустим, что входная цепочка -аасЬс. В дальнейших рассуждениях мы будем употреблять входной указатель, который в начальный момент указывает на самый левый символ входной цепочки.

Коротко говоря, нисходящий анализатор пытается построить дерево вывода входной цепочки следующим образом. Процесс начинается с дерева, состоящего из одной вершины, помеченной 5. Это начальная активная вершина. Затем рекурсивно Выполняются такие шаги:

(1) Если активная вершина помечена нетерминалом, скажем А, то выбрать первую его альтернативу, скажем ... Хд, и добавить прямых потомков вершины А с метками Х, Сделать Х активной вершиной. Если k = 0, сделать активной Вершину, расположенную непосредственно справа от А.

(2) Если активная вершина помечена терминалом, скажем а, t-paBHHTb текущий входной символ с а. Если они совпадают, Сделать активной вершину, расположенную непосредственно

А. Ахо, Дж. Ульыаы. т, 1 321





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 [52] 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.146