Часто при вычислениях нам приходится иметь дело с объектами, обладающими структурой. Грамматическая структура английского предложения состоит из подлежащего, сказуемого, группы дополнения и прочих элементов. Структурными элементами программы для вычислительной машины являются подпрограмма, процедура, выражение. Блок-схеме соответствует структура из многоугольников и линий. Массив данных имеет структуру, которая определяется соответствующими индексами. Перечень таких примеров можно было бы продолжить. У нас может возникнуть желание описывать подобные структуры таким образом, чтобы суметь потом оперировать с соответствующими классами, как мы оперируем с классом грамматически правильных английских предложений, с классом синтаксически правильных алгольных программ или с классом правильно сформированных массивов или файлов определенного вида. Такие описания пригодятся для того, чтобы мы могли определять, принадлежит ли заданный объект определенному классу, или чтобы мы могли получать примеры элементов класса, или чтобы мы могли оперировать с целыми классами, например при поиске пересечения двух классов. Структура сама по себе тоже может интересовать нас. Например, грамматическая структура предложения помогает нам интерпретировать его смысл, раскрывая связи между частями. Аналогично структура алгольной программы показывает нам нужные связи между соответствующими частями и тем самым помогает компилировать эту программу. Так, структура алгольного выражения

a+bXc+d

может быть изображена в виде

а+Ьхc+d

который показывает, какие части арифметического выражения связаны знаком плюс, а какие -знаком умножения. Если бы

2 ДЖ5 Фостер

6 /. Введение

соответствующая структура имела вид

п п

0+ 6 X с +

то интерпретация выражения была бы совершенно другой.

Поэтому нам нужны формальные описания структур объектов. Поскольку раньше всего были изучены грамматические описания предложений, то обычно пользуются терминологией, заимствованной из лингвистики, хотя целью рассмотрений могут оказаться и нелингвистические применения грамматик. В этой книге мы будем иметь дело только с одномерными объектами, а именно с последовательностями (предложениями) из неделимых элементов (слов). Под структурой (грамматическим разбором) предложения будут пониматься порядок и структура его частей. Мы будем пользоваться так называемыми контекстно-свободными грамматиками. Они не являются единственным средством описания структур предложений, но обычно именно на них основывается применение грамматик для компиляции [1, 7, 10. 13, 15].

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

Грамматики, используемые для описания языков программирования, гораздо более просты, чем те грамматики, которые нужны для естественных языков. Поэтому мы никоим образом не будем затрагивать последних, и всюду далее подразумевается, что рассматриваемые грамматики непригодны для естественных языков [8]. Языки программирования разрабатываются с таким расчетом, чтобы было легко читать и писать на них (а также компилировать с них), поэтому они обычно имеют

/. Введение i

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

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

В скобочной записи оно приобретает вид

(({a-\-b) + iicXd)Xe)) + f) и задача грамматического разбора становится тривиальной, так как скобки описывают структуру. Однако такое систематическое внесение скобок в алгольное выражение или в английское предложение сделало бы текст неудобочитаемым, и поэтому обычно скобки отсутствуют, а ставятся они только тогда, когда без них нельзя обойтись. У нас может появиться желание различать разные способы образования групп символов. Если переписать предыдущее выражение, употребляя круглые скобки для групп, соответствующих знаку плюс, и квадратные скобки для групп, соответствующих знаку умножения, то оно будет выглядеть следующим образом:

(iia + b) + [[cXd]Xe]) + f)

Возможна и такая запись:

Выражение

Сложить

Сложить

Умножить

Сложить Умножиты

a+b+cxdxe+Z

КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ

2.1. ТЕРМИНОЛОГИЯ

Мы будем пользоваться следующими терминами и обозначениями. Построенные надлежащим образом последовательности будут называться предложениями. Они будут состоять из упорядоченных объектов, называемых словами. Мы не будем касаться структуры слов, а предположим, что умеем как-то распознавать слова. В примере на стр. 7 символы а, Ь, с, d, е, и +. X были словами. Слова будут записываться строчными буквами или будут такими символами, как + и Х- Для описательных целей мы будем пользоваться некоторыми отличными от слов символами, которые будем называть классами. Их называют также нетерминальными символами. В предыдущем примере Сложить, Умножить и Выражение были классами. Классы будут всегда обозначаться прописными буквами. Предложение - это особый класс, который обычно обозначается символом 5. Всякому классу будет соответствовать набор возможных структурных вариантов, каждый из которых состоит из упорядоченных элементов, являющихся либо словами, либо классами. Эти варианты называются правилами подстановки. Таким образом, вся грамматика состоит из набора слов (словаря), набора классов, названия особого класса, т.е. предложения, и из набора правил подстановки.

В качестве простейшего примера рассмотрим грамматику со словарем а, Ь, с, d, с классами 5 и 7 , с символом предложения 5 и с правилами подстановки, записываемыми следующим образом:

S->a\bTTd T-*bc\a

Такая запись означает, что имеются два структурных варианта для 5: либо а, либо сначала Ь, затем Т, затем Т, затем d. Для класса Т также имеются два структурных варианта. Тогда существуют пять правильных предложений:

а

bbcbcd bbcad babcd baad

Описываемые в этой книге методы грамматического разбора предназначены для компиляции программ для вычислительных машин, однако при этом затрагиваются и некоторые проблемы синтаксического анализа естественных языков. От читателя не требуется предварительных знаний о формальных грамматиках и работе компиляторов, но предполагается некоторое знакомство с основами программирования для вычислительных машин. Алгоритмы грамматического разбора описываются на несколько модифицированном варианте языка Алгол, понимание которого не вызовет затруднений у читателя, знакомого с языком Алгол-60. Чтобы избежать громоздких программ, применяются методы обработки списков. Краткий обзор основных сведений об этих методах приводится в приложении 1.

В гл. 2 приводятся некоторые элементарные определения и примеры грамматик. В гл. 3 рассматривается общая проблематика грамматического разбора. Глава 4 посвящена методам грамматического разбора, применимым к любым контекстно-свободным грамматикам. В гл. 5 рассматриваются некоторые ограниченные классы грамматик, для которых можно обеспечить высокую скорость синтаксического анализа. В гл. 6 речь идет о преобразованиях грамматик и, в частности, о получении эквивалентных грамматик, более удобных для синтаксического анализа, чем исходные грамматики. Из гл. 7, а также из первой части гл. 6 можно получить краткое представление о том, как разбор структуры программы может использоваться для компиляции.

Впервые синтаксический анализ применялся в компиляторах Брукера и Морриса [3, 4, 5] и Айронса [21, 22]. Более подробную библиографию содержит отличная обзорная статья Фельдмана и Гриса [10].

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

2. Контекстно-свободные грамматики

Будем говорить, что эти предложения могут быть выведены из S; возможность вывода предложения babcd указывается так:

S-*babcd

Часть предложения, которая выводится из какого-то класса, называется фразой. Таким образом, в предложении babcd имеется фраза а, выводимая из Т, и фраза be, также выводимая ИЗ?.

Правила подстановки могут рассматриваться как наборы правил для переписывания классов, и процесс вывода babcd из S может рассматриваться следующим образом. Начинаем с символа предложения

и заменяем его на один из соответствующих ему вариантов

bTTd

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

bTbcd

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

babcd

Будем говорить также, что bTbcd выводится из S:

S-* bTbcd

и что а выводится из Т:

Т->а

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

S.I. Терминология

И

В приведённом выше примере мы могли бы выполнять по следовательность операций подстановки двумя способами:

bTTd bTbcd babcd

или

bTTd baTd babcd

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

Г

а не прослеживать последовательность операций подстановки.

Тем не менее легко придумать грамматики с двусмысленным грамматическим разбором. Пример

S->TT

Т-*-а \аа

дает нам два различных грамматических разбора для предложения ааа, а именно

г

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

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

идентификатор

идентификатор + идентификатор

идентификатор + идентификатор -\- идентификатор

то мы вольны интерпретировать идентификатор не как конкретный набор букв и, д, е, н, т, и, ф, и, к, а, т, о, р, а как общее представление для множества различных объектов при условии, что эти объекты не будут смешиваться со знаком -}- Такое слово будет называться представляюиим. Мы будем пользоваться двумя представляющими словами; первое из них, идентификатор (сокращенно ид), обозначает множество последовательностей из букв и цифр, начинающихся с буквы, второе число употребляется в обычном смысле. Для приведенной выше грамматики правильным является, например, следующее предложение:

abc + d2 + хуЫ

Мы будем рассматривать грамматики, удовлетворяющие следующим правилам. Не должно существовать выводов

Х-*Х

где X - любой класс. Такие выводы ничего не добавляют к множеству описываемых предложений, но создают возможность бесконечных возвратов при грамматическом разборе {X является X, который является X ...). Каждый класс должен появляться при некотором выводе из S. Если какой-то класс никогда не появляется, то он не приносит пользы для описания предложений и поэтому может быть исключен.

Для всякого класса должен найтись по крайней мере один терминальный вывод. Это означает, что не должно существовать классов, подобных классу У, для которого единственное правило подстановки имеет вид

и никогда не породит терминальную строку.

2.2. ПРИМЕРЫ ГРАММАТИК И ИХ СВОЙСТВ

В этом параграфе мы рассмотрим некоторые типичные грамматики и опишем их свойства, имеющие отношение к грамматическому разбору.

2.2. Примеры грамматик и их свойств

Грамматики, описывающие конечные наборы допустимых предложений, представляют сравнительно мало интереса. Заслуживают внимания те случаи, когда множества предложений бесконечны. Для того чтобы грамматически описывать такие бесконечные множества, необходимо применять рекурсию. Рекурсия означает, что в некоторой выводимой из класса X последовательности элементов (слов и классов) должно найтись вхождение X. Типичным примером является описание множества арифметических выражений, образуемых из идентификаторов и знаков -f и X. Для этого часто используется следующая грамматика, в которой рекурсивны оба класса $ и Г:

5->7S-l-7

Т-* идентификатор \ Т X идентификатор В этой грамматике типичный грамматический разбор предложения имеет вид

Г

т

а

т

е

Класс X, для которого существует вывод

Х-*Хо.

где а непустая последовательность элементов, называется рекурсивным слева; в рассмотренном примере оба класса 5 и Г являются рекурсивными слева. Аналогично класс X, для которого существует вывод

где р - непустая последовательность элементов, будет называться рекурсивным справа.

Другая типичная грамматика описывает выражения, включающие идентификаторы, знаки +, X и круглые скобки, и имеет вид

5->7S-l-7

Т->Р\ТХР P->ud\{S)

и

2. Контекстно-свободные грамматики

Здесь все классы 5, Г и Р являются рекурсивными. Типичный грамматический разбор предложения выглядит так:

г

р

Р

1/д

Р

г

т

i X

е

Г

) + /

в + 6 X ( Класс X, для которого существует вывод

где аир - непустые последовательности элементов, называется самовставляемым. Классы S, Т и Р являются самовставляемыми и, кроме того, классы 5 и Г - рекурсивные слева.

Может оказаться, что две различные грамматики описывают одно и то же множество предложений. Например, описанное ранее множество выражений, включающих идентификаторы и знаки 4- и X. можно было бы описать и такой грамматикой:

Sud\ud + S\udXS

Однако при использовании этой грамматики типичный грамматический разбор выглядит несколько иначе:

ид ид ид ид ид I I I I I

2.2. Примеры грамматик и их свойств

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

При всем сказанном класс контекстно-свободных грамматик слишком широк, и в его рамках могут описываться слишком запутанные грамматики. Например, рассмотрим грамматику

s->a \aSa

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

Грамматический разбор

грамматический разбор можно осуществить следующим способом, основанным на схеме, которая была предложена Эмере-лом [34]. Если заданы конкретное предложение и грамматика, строим треугольник

axb+cxd+e

И пытаемся заполнить внутреннюю часть треугольника непротиворечивым деревом вывода, которое представляет грамматический разбор:

Г

т

Г

т

Т

+ в

В принципе не имеет значения то, как мы пытаемся заполнить внутреннюю часть треугольника. Мы можем заполнять треугольник от вершины вниз

a\b+cxd+e

3. Грамматический разбор

ИЛИ снизу к вершине

т

ид ид

. . . I I axA + cxrf-l-e

I I

ид ид ид

или же от левого угла

г

г

ид ид

axi + cxrf-f-e

или в любом другом порядке. Однако порядок заполнения треугольника может в большой степени влиять на эффективность процесса.

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

т

т

Т

ttXb + cxd+e

применяя Правило подстановки

Т->ТХид

Этот конкретный шаг подходит для начальной локальной ситуации и окажется правильным также и на последующих

3. Грамматический разбор

этапах грамматического разбора. В некоторой локальной ситуации мы можем избрать шаг

т

т

ид ид ид ид \ V. Ь Л- с V. d + е

применяя правило подстановки

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

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

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

3. Грамматический разбор

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

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

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

Для иллюстрации рассмотрим грамматику

S-ya\aSa

Если производить для этой грамматики разбор сверху вниз

ааааа

то на первом шаге имеем

на втором шаге

и на третьем шаге

Мы руководствовались здесь следующим априорным критерием. Если осталось одно незатронутое слово, применяем подстановку

S->a

в противном случае применяем

S-*aSa

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

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

УНИВЕРСАЛЬНЫЕ МЕТОДЫ ГРАММАТИЧЕСКОГО РАЗБОРА

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

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

d е f g h i

или снизу вверх и слева направо

1 Р Р с d е f g

h i

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

3 Дж. Фостер

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

4.1. РАЗБОР СВЕРХУ ВНИЗ

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

S->T\T + S

Т->ид\идХТ

где ид - представление для идентификаторов. Начнем с разбора предложения

а + ЬХс

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

Начинаем с символа S и заменяем его на соответствующие варианты; в данном случае правильной окажется замена на Т S.Ha последующих шагах, если первый символ оказывается словом, то он сравнивается с первым символом предложения, и в случае совпадения этот символ исключается и из предложения, и из последовательности элементов. Эта последовательность представляет возможную структуру оставшейся части предложения. Если же первый символ обозначает класс, то он заменяется на один из вариантов, соответствующих этому классу. Поскольку мы правильно подбираем подстановки, сравниваемые слова будут совпадать, но в общем случае они могут оказаться различными, и это означало бы неудачу разбора. Ниже приводятся последовательные шаги всего анализа с указанием остатка предложения, остатка разбора и текущего дерева разбора для каждого этапа.

-t- Ь X с

b X с

t X с

b X с

иду.Т

а + Ь У. с S

а + b X с T+S Т + S

а + b У с

+ Ь X с ид +S Т + S

о * X с

г -f S

а -f- i X с S

а + Ь % t

ид т

а -i- * X и

Т

ид к Т

а + Ь У. с