else if then

while B do end else 5; end end

Всю программу можно представить в виде if then else end, где Sg представляет всю часть от первого while до S, а представляет if . .. end. Это первый шаг анализа программы, соответствующий замене одной вершины структурой б на рнс. 1.8.

Продолжая анализ, представим 5д в виде S; {3-это while 63 ... 5 end end). Таким образом, этот шаг анализа соответствует замене вершины на рис. 1.8,6 графом а. Результат

Рис. 1.9. Построение d-cxeMHi

показан на рис. 1.9, а. Далее, имеет вид while В do S- end, где -ЭТО if Br . ., end. Тогда можно заменить левого прямого потомка корня дерева на рис. 1.9, а структурой, изображенной на рис. 1.8,6. Результат показан на рис. 1.9,6.

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

Рис. МО. Окончательная ё-схемз;

рис. 1.11. Вершины дерева помечены соответствующими вершинами ИЛИ контурами d-схемы. □

Приведенный пример в некотором смысле является подделкой. Структура d-схемы, изображенная на рис. 1.11,- это по существу структура, которую построит для первоначальной программы компилятор на этапе синтаксического анализа. Таким образом, похоже, что мы обсуждаем тот же тип синтаксическо1о анализа, что и в разд. 1.2.3. Однако следует иметь в виду, что этот структурный анализ можно проделать, не ссылаясь на программу, а глядя только на d-схему. Более того, мы привели этот пример графопорождающей грамматики из-за его связи

S3 Si Sz S4 Ss Й5 9

pHCi l.U. Дерево, описывающее структуру d-схемы*

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

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

Трудности, возникающие при попытках найти удовлетворительную грамматическую модель для английского языка, хорошо представлены в книге Хомского [1965J. Бобров [19G3J дает обзор усилий, направленных на использование английского языка, или, точнее, некоторого его подмножества, в качестве языка программирования. Обзор теоретических аспектов лингвистики содержится в книге Бар-Хиллела [1964]).

Понятие грамматики, порождающей графы, взято нз работы Пфальиа и Розенфельда (19G9], теории этих грамматик посвящены статьи Моитанари [1970] и Павлидиса [1972]. Одна из первых работ по синтаксическому анализу образов принадлежит Шоу [1970]. Обзор некоторых результатов, полученных в этой области, можно найти у Миллера и Шоу [1968]

1) Рекомендуем также сборник „Автоматический перевод" [I97I], книгу Винограда [1972] и статьи Цейтина [1971] и Вудса [ 1970].-Яриж. перев.

2) См. также [Абэ и др., 1973] и [Фу, 1974].-Яр«ж. перев.

ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ

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

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

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

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

Как и в гл. О и 1, читатель, знакомый с теорией языков, может пропустить илн бегло просмотреть эту главу.

2.1. СПОСОБЫ ОПРЕДЕЛЕНИЯ ЯЗЫКОВ

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

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

2.1.1. Мотивировка

Мы определяем язык L как множество цепочек конечной длины в алфавите 2. Первый важный Штрос; как описать язык L Ё~тоМ случаетПшгда он бесконечен. Разумеется, если L состоит из конечного числа цепочек, то самый очевидный способ-составить список всех цепочек из L.

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

i Известно несколько методов описания языков, удовлетворяющих этому требованию. Один из них состоит в использовании порождающей системы, называемой грамматикой. Цепочки языка строятся точно определенными способами с применением правил грамматики. Одно из преимуществ определения языка с помощью грамматики в том, что операции, производимые в ходе синтаксического анализа и перевода, можно сделать проще, если воспользоваться структурой, которую грамматика приписывает цепочкам („предложениям") языка. Грамматики, особенно контекстно-свободные, мы изучим очень подробно.

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

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

2.1.2. Грамматики

Грамматики образуют, по-видимому, наиболее важный класс генераторов языков. Грамматика -это математическая система, определяющая язык. ОднонреМейТо она является ус1рОЙС1ьим; которое придает Т1епочкам („предложениям") языка полезную структуру. В этом разделе мы рассмотрим класс грамматик, называемых грамматиками Хомского или грамматиками составляющих.

В грамматике, определяющей язык L, используются два конечных непересекающихся множества символов-множество нетерминальных символов, которое часто будет обозначаться буквой N), и множество терминальных символов, обозначаемое S. Из терминальных символов образуются слова (цепочки) определяемого языка. Нетерминальные символы служат для порождения слов языка L способом, который будет объяснен позднее.

Сердцевину грамматики составляет конечное множество Р правил образования, которые описывают процесс порождения цепочек языка. Правило -это просто пара цепочек, или, точнее, элемент множества (N U 2)* N (N U 2)* х (Nu 2)*. Иначе говоря, первой компонентой правила является любая цепочка, содержащая хотя бы один нетерминал, а второй компонентой-любая цепочка.

Например, правилом может быть пара (АВ, CDE). Если уже установлено, что некоторая цепочка а порождается грамматикой (или „выводится" в ней) н а содержит АВ, т. е. левую часть этого правила, в качестве своей подцепочки, то можно образовать новую цепочку р, заменив одно вхождение АВ в сс на CDE. Тогда говорят, что р выводима (или выводится) в данной грамматике. Например, если цепочка FGABH выводима, то FGCDEH тоже выводима. Язык, определяемый грамматикой,-это множество цепочек, которые состоят только из терминалов и выводятся, начиная с одной особой цепочки, состоящей из одного выделенного символа, обычно обозначаемого S.

Соглашение. Правило (а, р) будем записывать в виде а-*-р.

Дадим теперь формальное определение грамматики.

Определение. Грамматикой называется четверка G = (N S Р. S), где f V . .

(1) N -конечное множество нетерминальных символов, или нетерминалов (иногда называемых вспомогательными символами, синтаксическими переменными или понятиями);

1) В соответствии с нашим соглашением об обозначениях алфавитов этот символ является прописной греческой буквой „ню", хотя читателю, вероятно, захочется произносить его как „эн".