Вопросы сложности анализа конъюнктивных грамматик

Оглавление
1 Введение 4
2 Определения и простейшие свойства 19
2.1 Грамматика.............................................. 19
2.2 Формулы................................................. 21
2.3 Вывод................................................... 22
2.4 Данна вывода............................................ 25
2.5 Дерево вывода........................................... 26
2.6 Линейные конъюнктивные грамматики....................... 28
2.7 Однозначные и неоднозначные грамматики...................29
3 Выразительные возможности конъюнктивных грамматик 32
3.3 Грамматики для классических не-контекстно-свободных
языков..................................................32
3.2 Грамматики для некоторых других абстрактных языков . . 34
3.3 Построение грамматик для языков всех вычислений данного вычислительного устройства...........................41
3.4 Грам?аатики для простейших языков программирования . . 45
4 Нормальные формы 53
4.1 с-конъюнкты............................................. 53
4.2 Единичные конъюнкты..................................... 55
4.3 Бинарная нормальная форма............................61
4.4 Линейная нормальная форма ..............................64
5 Распознавание и синтаксический анализ 68
5.1 Алгоритм для грамматик в бинарной нормальной форме . 68
5.2 Алгоритм для грамматик в линейной нормальной форме . 72
о.З Алгоритм для грамматик общего вида................... 7-1
5.4 Алгоритм для линейных грамматик общего вида..........96
1
Оглавление
2
5.5 Алгоритм нисходящего раэбора............................. 99
о.6 Метод рекурсивного спуска................................117
5.7 Алгоритм восходящего разбора.............................123
5.8 Сравнение алгоритмов синтаксического анализа.............150
6 Задана принадлежности 153
6.1 Полиномиальное решение задачи принадлежности 154
6.2 P-полнота задачи принадлежности..........................158
6.3 Р-пол нога задачи принадлежности для линейных
конъюнктивных грамматик..................................161
7 Задача генерации строк 1С4
7.1 Постановка задачи как задачи распознавания свойств . . . 165
7.2 Сложность для конъюнктивных и линейных
конъюнктивных грамматик..................................169
7.3 Сложность задачи для распространённых вычислительных устройств....................................171
7.4 Анализ результатов.......................................180
8 Вопросы описательной сложности 183
8.1 Терминология ............................................183
8.2 Описание контекстно-свободных языков конъюнктивными
грамматиками.............................................184
8.3 Нерекурсивная оценка роста описательной сложности ... 189
9 Дополнительные вопросы 194
9.1 Неразрешимые задачи.................,.....................194
9.2 Сложность распознавания конъюнктивных языков по
памяти ...............................................199
9.3 Связь с другими семействами языков.......................203
9.4 Росг длин строк из конъюнктивных языков..................207
9.5 Конъюнктивные грамматики н системы языковых уравнений208
10 Заключение 220
А Генератор синтаксических анализаторов Whale Calf 224
А.1 Введение..................................................224
А.2 Написание грамматики......................................226
А.З Использование сгенерированных анализаторов................227
А.4 Алгоритмы синтаксического анализа.........................229
А.4.1 Табличный алгоритм для произвольных грамматик 229
А.4.2 Нисходящий конъюнктивный алгоритм SLL(Ar) . . . 230
Оглавление
3
А 4.3 Восходящий конъюнктивный ЬЯ-аналпз..............231
А.4.4 Алгоритмы для грамматик в нормальных формах . 232
Глава 1
Введение
Выразительная мощность контекстно-свободных грамматик, как неоднократно отмечалось в математической и лингвистической литературе, недостаточна дія описания большинства практически используемых языков: сегодня общепринято представление о том, что все естественные языки содержат не-хомтекстно-евободные конструкции (см. обсуждение и библиографические ссылки н (8)), а не-коитекстно-свободность языков программирования была строго доказана (11) применительно к языку А^о! СО ещё в 19(52 году.
Рассмотрение задач из различных предметных областей и установление не-контекстно свободное™ их языкового представления привело авторов работы (7| к заключению, что “мир, по всей в иди мостя, не контекстно-свободен...”
Поэтому вопрос нахождения языковой модели, адекватной встречающимся на практике языкам, исключительно важен и по этой причине стал темой многочисленных исследований.
Семейство коктекстно-завпашых языков, следующее в классической иерархии Хомского вслед за семейством контекстно-свободных, может на первый взгляд показаться решением проблемы. Действительно, контекстно-зависимые ірамматики позволяют описывать очень широкий класс языков; как отмечается в (20|, “практически любой мыслимый язык контекстно-зависим, поскольку все существующие доказательства не-контекстн(хіааисимости языков основаны на диагональном методе". Однако, с точки зрения практических приложений, этот класс оказывается слишком широким; задача принадлежноегн ;иія контекстно-зависимых грамматик РБРАСЕ-подна, что сильно затрудняет любое их использование. Кроме того, выразительные средства, предоставляемые хонтсхстно-зависимыми грамматиками, напоминают скорее замысловатый язык программирования, чем
4
Глава /. Введение
5
средство задания синтаксиса; процесс составления контекстно-зависимой грамматики для данного языка сродни написанию программы на ассемблере, а последующие попытки понять, как грамматика работает, можно сравнить только с чтением машинного кода. Совпадение класса контекстно-зависимых языков с классом сложности ХБРАСЕ(п) в некоторой степени объясняет эту особенность.
Так как контекстно-свободные грамматики являются достаточно удобным и использовании инструментом для формального задания языков, многие попытки построения языковых моделей сводились к расширению формализма контекстно-свободных грамматик различными дополнительными конструкциями, некоторым образом специфицирующими условия, при которых могут применяться отдельные правила грамматик.
Например, рассматривались контекстно-свсбодные грамматики с тем или иным образом заданными ограничения;.« на последовательность шагов вывода — грамматики с контролируемым выводом. Различные классы таких грамматик рассмотрены в |8).
Одним из формализмов, построенных на основе контекстно-свободных грамматик, являются конъюнктивные грамматики, введённые автором в [34, 33, 36]. Конъюнктивные грамматики обобщают контекстно-свободные грамматики путем расширения формализма правил явной операцией пересечения. Правила конъюнктивных грамматик имеют вид
А -ь оцк... &сгя, (1.1)
где А — нетерминальный символ, п ^ I, о< — строки над полным алфавитом грамматики, называемые конъюнктами. Правило вида (1.1) неформально означает, что из нетерминала А может быть выведена любая строка, которая может быть выведена из каждой а, в отдельности, то есть операция конъюнкции имеет семантику теоретико-множественного пересечения. Формальное определение КОНЪЮНКТИВНЫХ грамматик даёгся таким образом, что, в случае если каждое правило грамматики состоит ровно из одного конъюнкта, грамматика порождает тот же язык, что и аналогично записываемая контекстно-свободная грамматика — то есть конъюнктивные грамматики являются корректным обобщением контекстно-свободных грамматик.
Пересечение контсксшо-свободных языков изучалось с первых лет теории формальных языков. Из не-хонтексгно-свободности языка {ап&"еп | п > 0} легко следует незамкнугость класса контсксшо-свободных языков относительно пересечения (см, например, [17], р. 198). Классический результат, неразрешимость определения пустоты
Глава J. Введение
б
пересечения двух данных хонтексгно-свободных языков, был получен в [4] путем сведения проблемы соответствия Поста к рассматриваемой задаче. Отсюда следует неразрешимость многих других задач распознавания свойств контекстно-свободных языков и грамматик включения, эквивалентности, регулярности, неоднозначности (ambiguity), существенной неоднозначности (inherent ambiguity), а также конгекстно-свободнссгн пересечения двух языков; обзор разрешимых и неразрешимых задач для контекстно-свободных языков даётся, например, в [17].
В [12] было показано, что любое рекурсивно перечислимое множество может быть представлено в виде гомоморфного образа пересечения двух контекстно-свсбодных языков.
Класс языков, получаемый замыканием класса контекстно свободных языков относительно пересечения, был впервые рассмотрен в [32], где было установлено, что языки из этого класса образуют бесконечную иерархию гДе ~ класс языков, представимых в виде
пересечения к контсксгно-свободных языков; доказательство этого факта непосредственно вытекает из следующего результата, полученного в [32]: для любого к > 2 язык
Lk > К а?... afcctf а!?... а* | Vj ij 2 0} (1.2a)
над алфавитом
Е*в{аі,оз,...,ад} (1.2b)
представим в виде пересечения к контекстно-свободных языков, по не представим в виде пересечения к — 1 контекстно-свободного языка.
В работах [53, 64] было получено несколько новых результатов относительно конечных пересечений контекстно-свободных языков: в частности, было доказано, что язык
I.cu. = {tccto | w е {а, Ь)’) (1.3)
не представим в виде такого пересечения. Кроме того, в этих работах
рассматривалось замыкание семейства детерминированных контекстно-свободных языков относительно всех теоретико-множественных операций, и доказывалось, что язык LU4U не принадлежит и этому семейству, то есть конечного числа детерминированных магазинных автоматов недостаточно для того, чтобы представить язык L4<cv и виде булевской формулы над результатами работы этих автоматов.
Глава J. Введение
7
Дальнейшее исследование замыкания семейства контекстно-свободных языков относительно пересечения было проведено в работе [29], где обосновывается значимость этого класса языков для лингвистических приложений и делается попытка систематического рассмотрения свойств этого класса, которому авторы этой работы дали название пересекающие* контекстно-свободных языхов (intersective context-free languages. ICF). Для класса языков, представимых в виде пересечения к контекстно-свободных языков, используется название fc-lCF. Это число к — то есть количество пересекаемых языков — используется в работе |29] и качестве меры описательной сложности, и относительно этой меры даются верхние оценки сложности некоторых операций над языками. Показана незамкнутого, класса пересекающихся контекстно-свободных языков относительно дополнения. Замкнутость этого класса относительно конкатенации н звёздочки сформулировано в качестве открытой проблемы.
Работа [29] примечательна в первую очередь тем, что в пей впервые предлагается использование пересечений контекстно-свободных ЯЗЫКОВ для практических применений. Однако теоретические результаты, полученные в [29], недвусмысленно указывают на неизбежные затруднения, которые возникнут у всякого, кто попытается на практике определять языки с помощью конечных наборов контекстно-свободных грамматик, задающих пересечение языков. Легко выразимое пересечение языков — это, фактически, всё, чем может похвастаться этот формализм; уже для объединения языков нет лучшей верхней оценки роста описательной сложности, чем квадратичная, что дает представление о том, с какими трудностями придётся столкнуться пользователю, желающему описать объединение двух данных языков из этого семейства- Открытость вопроса о замкнутости класса относительно конкатенации и звёздочки окончательно ставит под сомнение практическую пригодность данной модели.
В |33] вводится понятие альтернирующих контекстно-свободных гра.и.ивтик (alternating context-free grammars), внешне разительно схожих с конъюнктивными. Однако, семантика этого объекта принципиально отличается от семантики конъюнктивных грамматик, поскольку рассматривается введение в кснтекстно-сеободний вывод универсального недетерминизма (universal nondeterminism), который не всегда соответствует пересечению порождаемых отдельными нетерминальными символами языков. Как оказывается, универсальный недетерминизм в контекстно-свободном выводе — значительно более мощная операция, чем пересечение языков; однако её несоответствие какой бы то нп было естественно мыслимой операции над. языками
Глава Г Введение
8
сильно затрудняет её применение для задания языков. С практической точки зрения, альтернирующие контекстно-свободные грамматики, как и контекстно-зависимые грамматики, представляют из себя весьма неудобный в использовании язык программирования.
В [33) делается попытка обосновать эквивалентность семейства языков, порождаемых альтернирующими контекстносвободными грамматиками, семейству. принимаемому альтернирующими магазинными автоматами (что, согласно [5, 28] означало бы также эквивалентность классу языков, принимаемых детерминированными машинами Тьюринга за экспоненциальное время). Однако, как отмечается в [21], приведённые в работе [33] доказательства содержат ряд существенных ошибок. В [211 доказывается более слабый результат: эквивалентность поОм> южестеа альтернирующих контекстно-свободных грамматик всему классу альтернирующих магазинных автоматов. Справедливость результата в формулировке (33] остаётся открытой проблемой.
Рассмотрев выразительные средства основных вычислительных моделей, так или иначе связанных с пересечением кокгехстно-свободных языков, перейдём к описательным характеристикам конъюнктивных грамматик. Практическая ценность конъюнктивных грамматик как средства описания языков обусловлена следующими их свойствами:
• Выразительные средства конъюнктивных грамматик содержат все выразительные средства контекстно-свободных, и, кроме тою, дополнительную операцию пересечения, соответствующую вполне естественной мыслительной операции рассмотрения объекта, удовлетворяющего нескольким условиям одновременно.
Таким образом, для любых конъюнктивных языков Ь\,1а языки
являются конъюнктивными, и поданным грамматикам 2 ДЛЯ языков грамматики для языков (1.4а)-(1.4<1) всегда могут
Сыть очевидным образом построены.
• Выразительная мощность конъюнктивных грамматик превосходит выразительную мощность контекстно-свободных, поскольку существуют конъюнктивные языки, не являющиеся контекстно-свободными (например. {опЬ"с" п ^ 0}), и даже (например, уже
Ь\ и Ь2 Ь\ • Ь-2
(1.4а)
(1.4Ь)
(1.4с)
(1.4с1)
Глада 1. Введение
9
упоминавшийся (1.3) язык {uictu | ui 6 {а,6}’}} не представимые в виде конечного пересечения контекстно-свободных языков |34, 36).
• Конъюнктивные грамматики могут быть использованы для очень краткого задания некоторых контекстно-свободных языков: ках показывается в [36] на примере последовательности языков
Lw = {испи«Г | w 6 {о, 6}*, п > 0}, (1.5)
переход от конъюнктивных грамматик к контекстно-свободны?л может принести к неограниченному росту относительно меры описательной сложности Var (минимальное число нетерминалов в грамматике для данного языка).
Рос7 относительно меры описательной сложности Symb (минимальное число символов, необходимое для задания данного языка), при переходе от конъюнктивных грамматик к контекстно-свободным. как показано в [36], неограничен никакой рекурсивной функцией.
Удобность выразительных средств некоторой грамматической модели, широта класса порождаемых ею языков и возможность краткого описания этих языков это, однако, не всё, что требуется для успешного применения модели в приложениях. Необходимы эффективные алгоритмы решения понижающих на практике задач анализа это в первую очередь алгоритмы определения принадлежности строки языку (алгоритмы распознавания). R дополнение к самим алгоритмам распознавания требуется наличие некоторого способа представления принадлежности строки языку, который позволил бы использовать грамматику не только дня проверки правильности синтаксической структуры, но и для разбора этой структуры, выявления того смысла, который обретает строка в терминах данной грамматики. Для контекстно-свободных грамматик таким способом представления является дерево вывода (дерево раэбора); именно концепция дерева вывода позволяет успешно использовать этот класс грамматик для анализа самых различных языков.
Теория синтаксического анализа контекстпоснободных языков весьма обширна повсеместное использование контекстно-свободных грамматик для определения языков привело к созданию множества различных алгоритмов распознавания и синтаксического анализа для этого класса грамматик, у каждого из которых есть свои достоинства, делающие его привлекательным для своего класса задач. Рассмотрим наиболее известные из этих алгоритмов.
Глава J. Введение
10
.Алгоритм Cocke-Kas ami-Younger [24, 55] применим к любой контекстно-свободной грамматике в нормальной форме Хомского и работает за время О (гг3) (где п — длина поданной на вход алгоритма строки), используя 0(д1) памяти. Этот алгоритм основан на методе динамического программирования: для того, чтобы выяснить, можно ли вывести входную строку из стартового символа грамматики, алгоритм строит дія каждой подстроки входной строки множество тех нетерминалов, из которых выводима эта подстрока; так как таких подстрок насчитывается л • (л — 1)/2, отсюда следует квадратичная сложность по памяти. Основной недостаток этого алгоритма состоит в том, что он требует предварительного приведения грамматики к нормальной форме Хомского; кроме того, то дерево разбора, которое легко может быть построено на основе созданных алгоритмом структур данных, относится именно к преобразованной грамматике, а не к исходной, что это сильно мешает практическому использованию этого дерева Однако именно в этом алгоритме в чистом виде выражена та идея, на которой основаны более универсальные и более эффективные алгоритмы.
Алгоритм h'arley (10] представляет из себя обобщение алгоритма Cocke-Kasamj-Younger на случай произвольных контекстно-свободных грамматик. Подобно тому, как алгоритм Cocke Kasami Younger вычисляет для каждой подстроки входной строки множество тех нетерминалов, из которых эта строка выводима, алгоритм Earley для каждой подстроки определяет множество правил грамматики с выделенными позициями (правім с точкой, обозначаемых через .4 —» а • 0), в которых предшествующая точке часть тела правила порождает данную подстроку. Принадлежность правила с точкой вида 5 -> о- множеству, соответствующему всей строке, как нетрудно видеть, означает принадлежность строки языку. Сложность алгоритма Earley остаётся кубической.
Алгоритм Grahain-Harrison Ruzzo |15, 16, 17] представляет из себя усовершенствованную версию алгоритма Earley, способную за один шаг работы просчитывать выводы пухлых строк вида 0 =^’ с и цепные выводы вида А =>* В. Сложность этого алгоритма остаётся хубической, одиако зависящая от грамматики константа, как праві сто, меньше, чем и алгоритме Earley.
Среди алгоритмов, имеющих чисто теоретическое значение, следует отметить алгоритм Valiant’a [50], основанный на сведении задачи распознавания строхи длины п к вычислению O(logn) произведений булевских матриц размера п х п. Таким образом, используя алгоритм Strasseif а [47] умножения квадратных матриц за время 0{nlO£'7), можно
Глава 1. Введение
11
распознавать принадлежность строки длины п контекстно-свободному языку :ta время С • п1о*>7. Однако константа С при этом настолько велика, что практическое применение этого алгоритма распознавания почти исключено.
Также стоит отметать воспаривший над реальностью алгоритм R.ytter’a (45], позволяющий распознавать принаддежнехть ст]юки контекстно-свободному языку за время 0(log?j) на параллельной системе, состоящей из 0(пв) процессоров.
Дня полноты рассмотрения алгоритмов распознавания для контекстно-свободных грамматик упомянем также алгоритм [31], использующий 0((Jogn)2) ячеек памяти, единственное предназначение которого — установление включения класса контекстно-свободных языков в D$PACE((logn)2).
Перечисленные выше практические алгоритмы оГгьедиияеп то, что они применимы к любому контекстно-свободному языку (включая недетерминированные и даже существенно неоднозначные языки), и их временная сложность пропорциональна кубу длины входа- Однако задачи обработки многих искусственных языков предъявляют несколько иные требования к алгоритмам синтаксического анализа: во-первых, искусственно построенные языки, как правило, принадлежат достаточно “хорошим” классам, и потому от алгоритма не требуется поддержка контекстно-свободных языков общего вида; во-вторых, распознаваемые строки могут быть очень длинными (например, программы на алгоритмических языках), и потому время работы алгоритма должно быть линейным от длины входной строки; в-третьих, сами грамматики могут быть весьма велики, и потому временная сложность алгоритма не должна зависеть от размера грамматики — или, по крайней мере, эта зависимость должна быть ис слишком существенной.
Как бы навстречу этим пожеланиям были созданы алгоритмы LL н
LR.
Алгоритм нисходящего (top-down) синтаксического анализа LL(A) [26, 30) по данной грамматике и входной сгроке пытается непосредственно построить левый контекстно-свободный вывод то есть такой, в котором на каждой шаге правило применяется к самому левому нетерминалу в текущей сентенциальной форме. При этом в памяти алгоритма, организованной в виде стека, хранится только правая часть сентенциальной формы, начинающаяся с самого левого нетерминала; терминальные символы, составляющие её левую половину, отбрасываются непосредственно после проверки на равенство с соответствующими символами входной строки Для выбора очередного правила, применяемого к нетерминалу, используются к первых
Гланя І. /введение
12
символов входной строки: класс грамматик, для которых этот выбор детерминирован, называется классом 1Х(&) грамматик. Сложность алгоритма ЬЬ(Л) пропорцлоиальпа длине контекстно-свободного вывода входной строки, и потому линейна от длины этой строки.
Алгоритм ЬЬ(£) часто реализуют вручную с помощью метода рекурсивного спуска: нетерминальным символам ставятся в соответствие процедуры, выбору одною из нескольких правил — условные операторы, стоящие в начале каждой процедуры н рассматривающие первые к символов входной строки, телам правил — последовательность вызолов процедур. При исполнении программы стек вызова фактически хранит правую часть сентенциальной формы в виде адресов возврата и локальных переменных.
Семейства ИД&)-языков (для А: > 1) образуют бесконечную иерархию
Бесконечное объединение и*!.1 £(ЬЬ(А)) является собственным подмножеством класса детерминированных контекстносвободных языков; пример детерминированного контекстно-свободного языка, не являющегося 1Х(&) ни для какого к — язык
Тем не менее, класс ЬЬ(1) языков всё же достаточно широк, чтобы включать в себя многие практически полезные языки в частности, ЬЦ1) грамматик достаточно для описания синтаксиса достаточно несложных языков программирования. Однако алгоритм налаїает достаточно жёсткие требования па вид ірамматики (например, запрещена левая рекурсия, то есть правила вида .4 —» Аа, и косвенная левая рекурсия, представляемая правилами вида А -* 0Аа, где {)■=*' <). Эти требования сильно затрудняют практітческое использование алгоритма, но всё же ов остаётся достаточно привлекательных^ из-за лёгкости своей реализации.
Наибольшее распространение в практике синтаксического анализа получил алгоритм восходящего (ЬоШлп-нр) анализа ГД (25). Этот алгоритм позволяет проводить синтаксический анализ любого детерминированного контекстно-свободного языка за линейное нремя от ,длины входной строки. Ьй-анализатор имеет магазинную память, в которой хранится прочитанная часть строки в частично разобранном виде (то есть вместо исходных терминальных символов в этой строке могут находиться нетерминалы, из которых выводихш её подстроки). На каждом шаге работы Ш-анализатор либо (і) продвигает один
£(Щ1)) с £(Щ2)) с ... С £(ЬЦ*)) с ...
(1.6)
{апсЬп | п > 0} и {<Лй2* л > 0}
(1.7)
Глава 1. Введение
13
символ из непрочитанной части входной строки на верхушку магазина, либо (И) заменяет верхние 0 или более символов магазина, образующие правую часть какого-то правила грамматики, на нетерминал из левой части этого правила, либо (iii) принимает решение о принятии или (iv) отвержении входной строки. Выбор между этими действиями осуществляется конечным автоматом, прочитывающим магазин снизу вверх и также, возможно, принимающим во внимание один или несколько первых символов из непрочитанной части строки. Этот автомат строится по данной грамматике; различные модификации алгоритма LR отличаются методом построения этого автомата и тем, каким образом автомат использует непрочитанную часть строки.
Первоначальная версия этого атгоритма, LR(i) (где к ^ О число принимаемых во внимание символов из непрочитанной части входной строки), предложенная в 19(15 годе' Knuth’oM в работе (25), приводила к построению автоматов сравнительно больших размеров уже в случав к = 1. что, учитывая ограниченную память компьютеров того времени, препятствовало практическому использованию алгоритма. Чтобы устранить это препятствие, в работе (9) были предложены два новых метода построения LR-автоматов, SLR(l) (simple LR(1)) и его улучшенная версия LALR(l) (lookahead LALR(l)), применимые к несколько более ограниченному классу грамматик, чем LR(1), но зато создающие автоматы такого же размера, как алгоритм LR(U). Класс принимаемых языков остаётся однако, как и в случае LR(fc) (fc ^ 1), классом всех детерминированных контекстно-свободных языков, что делает этот метод весьма привлекательным для применения в реальных программах; именно на этой модификации алгоритма LK работает большинство генераторов синтаксических анализаторов, используемых в индустриальном программировании.
Последующие исследования в области классического (детерминированного) LR-аналкза проходили под знаком практической пользы: строились более эффективные по времени работы алгоритмы построения 1.А1Л(1)-та6лиц, разрабатывались различные методы обработки синтаксических ошибок, предлагались модификации всею алгоритма, позволяющие немного расширить класс поддерживаемых грамматик Обширная библиография работ, посвящённых классическому LR-анализу и его простейшим расширениям, даётся в монографии [6).
Алгоритм обобщённого LR-анализа (49) — это надстройка над классическим алгоритмом LR, позволяющая реализовать недетерминизм в выборе действия за счёт одновременного хранения всех конфигураций магазина, которые могли бы появиться на данном шаге вычисления,
Глава 1. Введение
14
и параллельного выполнения всех возможных ветвей вычисления. Эти конфигурации (число которых может расти экспоненциально от длины прочитанной части строки) хранятся и компактной форме в графо-структурированной магазинной памяти анализатора. Алгоритм применим к любому контекстно-свободному языку; наиболее поздняя версия алгоритма применима и к любой контекстно-свободной грамматике- Прем я выполнения алгоритма полином, зависящий от грамматики. Для любой LR-грамматики это время будет линейным, и вычисление алгоритма будет повторять вычисление соответствующего автомата. Таким образом, этот алгоритм обеспечивает приемлемое время работы на как на “хороших", так и на “плохих” грамматиках, что делает cm весьма удобным для практического применения.
Систематический обзор алгоритмов синтаксического анализа для контекстно-свободных языков даётся в работе [46|, где предлагается унифицированный подход к построению и анализу этих алгоритмов --схемы разбора (parsing schemata); в терминах этого подхода описываются и сравниваются между собой основные алгоритмы и устанавливаются взаимосвязи между ними.
Существование описанных выше алгоритмов анализа контекстно-свободных языков во многом и ответственно за популярность контекстно-свободных грамматик в практических приложениях: пи для какого другого формализма задания языков не существует такого количества эффективных средств их разбора.
Оказывается, что для конъюнктивных языков можно разработать более-менее схожие по сложностным характеристикам и методам работы алгоритмы:
i. Для любого конъюнктивной» языка существует алгоритм распознавания, работающий за время 0(п3) от длины строки и использующий 0{пг) памяти, причём этот алгоритм, как п все рассмотренные ниже, может быть эффективно построен по данной
грамматике [35, 36).
п. Как и для контекстно-свободных грамматик (алгоритм Graham -Harrison-Ruzzo), для конъюнктивных грамматик существуют алгоритмы распознавания, не требующие предварительного преобразования грамматики, которые также работают за кубическое время (39).
Ш. Существует эффективно распознаваемое подмножество личейн'м конъюнктивных языков (обобщающих линейные контекстно-свободные языки), для которых существует алгоритм
Глава I. Введение
15
синтаксического анализа, работающий за квадратичное время и использующий 0{п) ячеек памяти [36];
К1. Существуют специализированные алгоритмы распознавания для конъюнктивных грамматик [37. 40], позволяющие производить синтаксический анализ некоторых языков за линейное время от длины распознаваемой строки.
Сформулируем основные достоинства контекстно-свободных грамматик, которые обуславливают их широкое применение, и на которые представляется разумным ориентироваться при разработке новых формализмов описания языков:
}. Класс языков. Класс контекстносвободных языков достаточно широк, чтобы позволять описывать достаточно сложные синтаксические структуры. Этот класс можно рассматривать как некий минимум, который должна уметь порождать грамматическая модель.
и. Описательные средства. Контекстно-свободные грамматики предоставляют интуитивно понятный набор операций, позволяющих легко задавать объединение и конкатенацию языков, в тахже давать рекурсивные определения.
ш. Эффективные алгоритмы распознавания. Существует множество различных алгоритмов распознавания принадлежности строки контекстно-свободному языку.
IV. Форма представления принадлежности строки языку. Понятие дерева разбора, наглядно представляющею принадлежность строки языку, даёт рождение синтаксическому анализу.
Вводимые нами конъюнктивные грамматики расширяют по сравнению с контекстно-свободными грамматиками как класс языков, тах и набор описательных средств, и при этом для них существуют столь же эффективные алгоритмы распознавания, как и для контекстно-свободных грамматик, результат выполнения которых может быть наглядно представлен в виде дерева со склеенными листьями. Эти обстоятельства в совокупности обосновывают потенциальную практическую значимость семейства котлонхтивиых грамматик.
Данная работа организована следующим образом: в главе
2 формально определяется класс конъюнктивных грамматик,
Глава 7. Введение
16
определяется язык, порождаемый грамматикой, исследуются простейшие свойства этого класса, вводится понятие дерева вывода (дерева со склеенными листьями), рассматривается длина вывода как сложностная характеристика конъюнктивных грамматик, определяются важные подклассы линейных и однозначных конъюнктивных грамматик.
Глава 3 повествует о выразительных возможностях конъюнктивных грамматик; большую часть главы занимает описание способов построения конъюнктивных грамматик для некоторых представляющих интерес абстрактных языков. Кроме того, в целях демонстрации возможностей этого класса приводится конъюнктивная грамматика для модельного языка программирования, включающая в себя полную проверку соответствия програхгмы формальному описанию этого языка.
Глава 4 посвящена нормальным формам для конъюнктивных грамматик. Вводится бинарная нормальная форма, в которой правила имеют вид А -э В\С\к. ..&ВтСт, А -і а или 5 -> с, а также линейная нормальная форма для линейных конъюнктивных грамматик. Дается алгоритм приведения произвольной конъюнктивной грамматики х бинарной нормальной форме и другой алгоритм, преобразующий любую линейную конъюнктивную грамматику к грамматике в линейной нормальной форме.
В главе 5 представлены наиболее важные результаты данной работы — даются семь различпых алгоритмов распознавания и синтаксического анализа для конъюнктивных грамматик. Это алгоритм д.гя грамматик в бинарной нормальной фороле., работающий за кубическое время и использующий квадратичную память; алгоритм для линейных грамматик а линейной нормальной форме, временная сложность которого квадратична, а пространственная — линейна; табличный алгоритм для грамматик общего вида, обобщающий алгоритм для грамматих в бинарной нормальной форме иа случай произвольных конъюнктивных грамматик и сохраняющий сложкостные характеристики этого алгоритма; вариация табличного алгоритма для грамматик общего вида, применимая к линейным конъюнктивным грамматикам и имеющая такую же сложность, как алгоритм лчя грамматик в линейной нормальной форме; алгоритм нисходящего разбора, развивающий идею контекстно-свободного алгоритма £Х(А;); метод рекурсивного спуска для конъюнктивных грамматик; и, наконец, алгоритм восходящего разбора, представляющий из себя дальнейшее обобщение упомянутого выше оГхібщенного алгоритма І.Л.
На основе алгоритмов из главы 5 в главе 6 покалывается полиномннальность задачи принад<хежмсти для конъюнктивных
Глава 1. Введемте
17
грамматики, тх> есть задачи определения, принадлежит ли данная на входе строка языку, порождаемому данной на входе конъюнктивной грамматикой; приводится алгоритм решения задачи принадлежности, работающий за время 0(п*) от общей длины записи грамматики и строки '^го позволяет получить важный теоретический результат: задача принадлежности для конъюнктивных грамматик Р-полна.
В главе 7 полиномиальная разрешимость задачи принадлежности для конъюнктивных грамматик используется для доказательства утверждения об ^-полноте задачи определения существования строки, лежащей лексикографически между двух данных строк и принадлежащей языку, порождаемому данной конъюнктивной грамматикой. Смысл рассмотрения задачи в такой постановке состоит в том. что между этой задачей распознавания свойств и практической задачей генерации строк, принадлежащих языку, существуют определённые связи, позволяющие сопоставлять сложность этих задач. В главе также устанавливается сложность этой же задачи для распространённых классов автоматов и грамматик: она >Л,СЮ8РАСЕ-полна для детерминированных и недетерминированных конечных автоматов, Р-полна для контекстно-свободных грамматик, МР-полна для альтернирующих конечных автоматов п Р ЭР АСЕ-пол на для контекстно-зависимых грамматик.
В главе 8 рассматривается описательная сложность конъюнктивных грамматик, и даются два результата о краткости представления контекстно-свободных языков и конечных пересечений контекстно-свободных языков конъюнктивными грамматиками: во-первых, на простом примере показывается, что переход «/г описания контекстно-свободных языков конъюнктивными грамматиками к описанию контекстно-свободными может привести к неограниченному росту числа нетерминальных символов и числа правил; во-вторых, показывается отсутствие рекурсивной верхней оценки роста длины описания при переходе от представления конечных пересечений контекстно-свободных языков конъюнктивными грамматиками к представлению наборами контекстно-свободных языков.
Глава 9 затрагивает некоторые дополнительные вопросы теории конъюнктивных грамматик, имеющие в основном теоретическое значение: изучаются вопросы разрешимости некоторых задач
распознавания свойств конъюнктивных грамматик; даётся оценка сложности распознавания принадлежности строки конъюнктивному языку по памяти; рассматривается соотношение семейства конъюнктивных языков с некоторыми другими известными семействами языков — в частности, устанавливается положение
Глава, i. Введение
18
семейства конъюнктивных языков в классической иерархии Хомского; показывается, что длины последовательных строк, принадлежащих конъюнктивному языку, могут расти быстрее любой данной рекурсивной функции; дастся характеризация конъюнктивных языков системами языковых уравнений некоторого вида.
В приложении А описывается разработанный автором генератор синтаксических анализаторов Whale Calf [52], реализующий все рассмотренные в работе алгоритмы распознавания ддя конъюнктивных грамматик; приложение А с незмачителышми сокращениями воспроизводит русскоязычную версию документации к этой программе.
Глава 2 Определения и простейшие свойства
2.1 Грамматика
Конъюнктивная грамматика определяется почти так же, как контекстно-свободная грамматика, но её правила могут состоять более чем из одного конъюнкта.
Определение 2.1. Конъюнктивная грамматика это четвёрка С = (£,Л',/*,5), где Е я — пепересекающиеся конечные непустые множества терминальных и нетерминальных символов соответственно; Р конечное множество правил грамматик, каждое из которых имеет вид
А -> щк... &огп (А <с. Лг, п £ 1, V* о* Є (Еи ЛГ)*), (2.1)
где строки называются конъюнктами и. как будет показано далее, можно без ограничения общности считать, что они различны, я что их порядок несущественен; Б Є N — нетерминал, выделенный в качестве стартового символа.
Пусть V — объединение £ и ЛГ. Дополнительно будут использоваться три специальных символа и 7; предполагается, что ни один >тз
них не принадлежит V. Определим У^Е \JNKJ “)*}.
Для обозначения нескольких правил для одною нетерминала будет использоваться следующая нотация:
А -» ац & ... &а(я, | ... | ат1&... (2.2)
Определение 2.2 (Конъюнкт). Пусть С = (Е,ЛГ,/*,5) —
конъюнктивная грамматика, Л Є ЛГ, т] € V*. .А —» 7 называется
19
Глава 2. Определения и простейшие Свойства
20
конъюнктом, осли для нсхоторого правила А -> а1&...&аа Є Р существует і (1 < і ^ п), такое что т) = а*.
Множество всех конъюнктов дайной грамматики будет обозначаться через
соп}ііп(І8{С!) = {А -> а | ЗА -+ ... коп Є Р, Зі Є (1, п]: а» = а}
(2.3)
В соответствии с определяемой ниже семантикой конъюнктивных грамматик, правило (2.1) означает, что из нетерминала в левой части можно вывести любую строку терминалов, которая может быть выведена из каждого из конъюнктов, образующих правую часть.
Рассмотрим следующий пример конъюнктивной грамматики:
Пример 2.1. Конъюнктивная грамматика для языка (аТс" | л > 0}:
5 -> АР к С}С А -*аА\ (
Р -> ЬРс | <
<2 ->а()Ь | с С —> сС | (
Очевидно, что нетерминалы А, Р, С1 и С порождают языки {а'|і ^ 0},
{^о> | > 0}, {а*6* | Л > 0} и {с* | ^ 0} соответственно. Поэтому 5
порождает
{да |»,> £ 0} П {«*ЬУ I к, 0} = {а*Ьясп Ю 0} (2.4)
РСли рассматривать грамматику как распознающее устройство, то можно сказать, что нетерминал 5 “запускает” два параллельных вычисления — АР и (}С — над одним и тем же набором данных, причём АР сравнивает между собой количество символов Ь и с, а С}С сравнивает количество о и Ь. как показано на рис. 2.1.
А Р
а ... а Ь ... Ь с ... с
V---------------------✓ч-,---'
О с
Рис. 2.1: Работа грамматики для языка {а"Ьпсп ] п ^ 0).
Глава 2. Определения и простейшие свойства
21
2.2 Формулы
Подобно контоксгно-свободной грамматике, конъюнктивная грамматика порождает строки путём недетерминированного преобразования сентенциальных форм, начиная со стартового символа и заканчивая строкой, составленной из терминальных символов. Однако объекты, преобразуемые в ходе такого вывода, имеют более сложную структуры, чем в контекстно-свободном случае:
Определение 2.3. Пусть О = (Е, А', Р, 5) — конъюнктивная
грамматика. Множество конъюнктивных формул 7 — это минимальное подмножество V , удовлетворяющее следующим условиям:
I Е и Лг С 7.
п. е € 7.
ш. Если Л, В € 7 (где А Ф е, В Ф с), то АВ е 7.
IV. Если Аи• • ■: А, € 7 (где п ^ 1; Л может равняться <), го
Чтобы сделать запись более понятной, пустые подстроки, появляющиеся в формулах в соответствии с (И), будут записываться явным образом, т.е. формула (Л()&) будет записываться в виде (.4(е)Ьс).
Конъюнктивные формулы естественным образом представимы в виде биполярных последовательно-параллельных сетей (П-сетей), определяемых индуктивно по структуре формулы, где символы НЗ Е и .V и упомянутые (-подстроки образуют отдельные дуги, помеченные символами из Еи Лги{(}, конкатенация представлена последовательной композицией, а конъюнкции представлена параллельной композицией, как показано на рис. 2.2.
Рис. 2.2: П-сети, соответствующие формулам (а) з € Еи Л' (Ь) е (с) А В (с1) (Л&...&Л,)-
Заметим, что каждой формуле А соответствует в точности одна П-сеть (которая будет обозначаться П(Л)), но для каждой П-сети