ЫЧЕБНОЕ ПОСОБИЕ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
В.И. ЖИГАЛОВ
ТРАНСЛЯТОРЫ САПР РЭУ
Учебное пособие
Утверждено
на заседании редсовета
13 мая 1999 г.
Москва
Издательство МАИ
1999
Жигалов В.И. Трансляторы САПР РЭУ: Учебное пособие. - М.: Изд-во
МАИ, 1999. - 76с.: ил.
В пособии, представляющем собой курс лекций, посвященный
теоретической базе трансляторов САПР, дается анализ естественного
языка, описание проблем трансляции, методов трансляции
арифметических выражений, а также формальные модели грамматик и
их свойства. Введены понятия грамматики с фразовой структурой,
языка, синтезирования строк, сентенциальной формы. Описывается
графическая интерпретация в виде обычных двоичных деревьев и их
свойства; даны алгоритмы построения цепочек правил подстановок. На
базе изложенной теории приводятся структуры данных и блок схемы
наиболее известных алгоритмов грамматического разбора сверху вниз и
снизу вверх.
Для студентов, изучающих теоретические основы трансляторов САПР.
Рецензенты: З.Н. Русакова
В.И. Хорхордин
Н.И. Латаиова
ISBN 5-7035-2371-0 © Московский авиационный институт, 1999
1.	ЕСТЕСТВЕННЫЕ И ФОРМАЛЬНЫЕ ЯЗЫКИ
1.1.	АНАЛИЗ ЕСТЕСТВЕННОГО ЯЗЫКА
Естественный язык (ЕЯ), исторически используемый в науке для
определения понятий, постоянно модернизируется и совершенствуется
для более полного и точного описания объектов. Современный
естественный язык существует в трех основных формах: звуковой, язык
жестов, письменный. Анализ Е Я выполняют с разными целями, и
результаты используют для множества различных практических
приложений.
Рассмотрим естественные языки с точки зрения их пригодности к
трансляции и алгоритмизации.
В теории алгоритмов применяется письменный язык, в котором
завершённая форма Е Я есть предложение,
Здесь синтаксис - совокупность правил, по которым строят правильные
предложения.
Семантика - совокупность способов, с помощью которых предложению
ставится в соответствие определённый смысл.
Нижеперечисленные особенности ЕЯ не позволяют использовать его для
записи алгоритмов и трансляторов:
1)	зависимость синтаксиса от семантики;
2)	неоднозначность, многозначность предложения;
3)	расплывчатость смысла, то есть неточность предложения;
4)	возможность парадоксальных предложений.
1	.Зависимость синтаксиса от семантики
Зависимость состоит в том, что способ построения предложения зависит
от его смысла.
Пример:
-	Я видел оленя. Я видел пень.
-	Я видел олень. (Предложение построено неправильно.)
Существительное может менять смысл и структуру предложения в
зависимости от рода.
Пример:
-	Кравчук ехал.
3
- Кравчук ехала.
Эти примеры показывают также и зависимость синтаксиса от
семантики.
Чтобы построить предложение, нужно понимать смысл.
2	.Многозначность предложения
Различают синтаксическую и семантическую неоднозначность, или
многозначность.
Синтаксическая многозначность: предложения, построенные по
различным правилам, опознаются одинаковыми.
Семантическая многозначность: одно предложение имеет несколько
толкований.
Синтаксическая многозначность сопровождается семантической.
Пример:
-	Коса.
-	Русая коса.
-	Острая коса.
-	Курская коса.
-	Бытие определяет сознание.
3	, Расплывчатость смысла предложения
Это свойство, близкое, на первый взгляд, к многозначности, связано
только с семантикой языка и не всегда приводит к отрицательным
результатам. При описании алгоритмов неточность ЕЯ недопустима.
Пример:
-	Девушка была похожа на цветок.
Такое сравнение можно встретить у И.С. Тургенева, при этом нет
необходимости в уточнении цвета и вида цветка.
^Возможность парадоксальных предложений
Парадоксальность легко иллюстрируется примером.
Пример:
-	Данное предложение ложно.
4
(Если предложение истинно, то смысл этого высказывания ложен, и
наоборот.)
Для исключения парадоксов необходим язык, в котором невозможны
предложения, содержащие утверждения о них самих, а также
невозможны циклические цепочки предложений, в которых первое
предложение говорит о втором, второе - о третьем и т.д., а последнее - о
первом.
Кроме перечисленных свойств, выделяют еще два:
•	смысл предложения естественного языка может зависеть от причин, не
относящихся к языку, например - от ситуации в обществе
•	изменчивость языка, благодаря которой ЕЯ пополняются постоянно
новыми словами.
Все эти особенности естественных языков создают трудности при их
использовании в теории алгоритмов.
1.2.	ИСКУССТВЕННЫЕ ЯЗЫКИ. ФОРМАЛЬНЫЕ ЯЗЫКИ
В 1887г. был создан международный искусственный язык эсперанто. У
эсперанто простая грамматика, но, с точки зрения программирования,
он имеет мало преимуществ перед ЕЯ. Искусственный язык, удобный для
теории алгоритмов, должен удовлетворять следующим требованиям:
1)	подчиняться строгим синтаксическим правилам;
2)	поскольку число правил конечно, они не должны зависеть от
смысла получаемых с их помощью предложений; .
3)	форма и смысл предложения должны однозначно соответствовать
друг другу;
4)	искусственный язык не должен допускать парадоксов.
Удовлетворяющие данным требованиям языки называют формальными.
Если формальный язык при этом получен путём отбора некоторого
подмножества предложений естественного языка, то этот язык называют
формализованным . Одним из первых формальных языков был язык
обоснования математики, на этом языке были сформулированы
основные аксиомы теории множеств. Появилась математическая
дисциплина - метаматематика, или теория доказательств. Совокупность
аксиом, правил вывода и теорем называется теорией, а такой подход к
обоснованию математики называется формалистическим.
Существуют различные формальные языки, в том числе языки без
смысла и теории, но они правильные, их теоремы выводятся из аксиом.
Такие языки использовались для исследований и для обучения, в них
5
можно отделить синтаксис от семантики. Когда рассматривается
синтаксис независимо от семантики, наличие смысла не отрицается, но
при изучении структуры он игнорируется. Можно сформулировать
совершенный, с точки зрения синтаксиса, язык, но при неудачно
заданной семантике этот язык будет неформальным. Поэтому
необходимо оговорить форму задания синтаксиса и семантики языка.
Языки взаимодействия человека и машины имеют свои особенности. Для
ЭВМ команды и данные - это хранящиеся в памяти и обрабатываемые
наборы двоичных кодов. Первой попыткой сделать общение с ЭВМ
более естественным было использование восьмеричного и
шестнадцатеричного представления чисел. Дальнейшие работы привели
к различным развитым лингвистическим средствам современного
математического обеспечения.
Можно выделить основные факторы, которые способствовали развитию
языков программирования:
1	.Мнемоника - возможность использования понятных для человека
символов и фраз в конструкциях машинного языка.
2	.Парадигма - объединение нескольких, внешне несвязанных, команд в
одну группу, осмысленную и логически завершённую для программиста.
Ъ.Структура данных. Основной структурой данных большинства
современных ЭВМ является одномерный массив элементов памяти,
состоящий из битов. Число их фиксировано. Размер элемента памяти
соответствует одному символу алфавита. Иногда элементы памяти
называют словами, их размеры колеблются от 12 до 60 бит. Элементы
памяти характеризуются абсолютными адресами. Таким образом,
имеется так называемая логическая структура данных. Кроме
логической, используется ещё и физическая структура. Основная задача
языков программирования - дать возможность программисту составить
свой алгоритм в терминах логической структуры данных. Простым
примером применения логической структуры данных в
программировании является массив.
В качестве причины, стимулирующей развитие языков, выделяют
машинную независимость программ. Полная машинная независимость
встречается редко. Для эффективности и быстроты работы программы
обычно описывают часть выполняемых ею функций на машинном
языке.
6
1.3. ТРАНСЛЯЦИЯ
Программу на языке высокого уровня необходимо откомпилировать,
т.е. перевести на язык машинных команд.
Компилятор - э1о программа ЭВМ, читающая исходную программу на
языке высокого уровня и генерирующая эквивалентную ей объектную
программу на машинном языке.
Процесс компиляции делится на две части:
1. Трансляция входного языка. Фразы и конструкции входного языка
анализируются и переводятся в элементы промежуточного
представления, содержащие информацию, достаточную для составления
объектной и далее выходной программы на стадии генерации.
2. Генерация кода машинного уровня. Конечный результат работы
машинных алгоритмов будем представлять диаграммой, указывающей
связь между различными частями исходной программы. Эго объектное
представление компьютер затем использует для генерации машинных
команд или интерпретации.
В режиме интерпретации процессор обрабатывает объектную
программу почти одновременно с чтением промежуточных форм и
выполняет соответствующие им машинные операции. При этом
выходная загрузочная программа, подлежащая дальнейшему
выполнению, не вырабатывается. Режим интерпретации позволяет
быстро обрабатывать этап компиляции, но он достаточно медлителен на
этапе выполнении программы . Тип компилятора выбирается в
зависимости от его предполагаемого использования . Первые
компиляторы появились в 1956-58 г., на компилятор с языка Фортран
для IBM 704 было затрачено 18 человеко-лет.
1.4.	СТРУКТУРА ДАННЫХ
Наибольшее распространение получили структуры магазинный СТЕК.
СТЕК - линейная последовательность слов переменной ограниченной
длины. Магазинный стек иногда называют памятью, работающей по
принципу: последним пришёл - первым ушёл (LIFO). Под СТЕКом
можно понимать линейную последовательность слов переменной, но
ограниченной длины. В СТЕКе выделяют два адреса: база-основание и
голова-вершина. Все обращения к содержимому СТЕКа выполняются
7
через их адреса. Заполнение СТЕКа начинается с базы, т.е. адрес i-ro
элемента СТЕКа определяется выражение^: база+i-l, i =1... и.
Элементы заносятся в СТЕК и удаляются с вершины. Пустой СТЕК
обозначим символом, помещенным в основание х- Засылкой Z будем
называть добавление к СТЕКу символа Z. Значение переменной голова
увеличивается на 1, a Z заносится в ячейку памяти, определяемой новым
значением переменной голова. Выборка - это изъятие символа из СТЕКа
с уменьшением значения переменной голова на 1. Результат выборки
есть содержимое удаленного элемента СТЕКа.
Транслятор преобразует символьные данные, что предполагает
использование списков. Списки состоят нз элементов, или узлов. Каждый
узел содержит информацию двух типов:
- внутреннюю - содержимое узла,
- внешнюю - связь узла с другими узлами списка.
Строка - список последовательности символов, вида Al,...,Ai,...,An.
Каждый узел содержит один символ Ai и указатель на Ai+1. В
большинстве языков не больше двух указателей (двоичное ветвление),
хотя возможно произвольное число указателей. Любую схему можно
преобразовать в двоичную.
1.5.	ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ
Определение 1.1. Множество - это неупорядоченная совокупность
объектов, называемых элементами.
Элементы - это все, что может быть определено правилом или именем.
Существует два способа задания множеств:
1)	перечисление имен объектов; 2) указание правила, проверяющего
принадлежность любого объекта выделенному множеству. Такое
правило называется предикатом.
Предикат - это определенная для всех объектов функция, такая, что если
Р -предикат, X -объект, то:
либо (Р(х) - истина, и X принадлежит множеству),
либо (Р(х) - ложь, и X не принадлежит множеству).
Пусть множества обозначаются прописными буквами, например Е-
множество, которое может быть определено перечислением имен
переменных в виде (Al...Ап) или предикатом Е=(х|Р(х)), т.е. X является
8
элементом Е тогда и только тогда, когда Р(х) - истина. Принадлежность
элемента X множеству Е обозначим Хе£.
Пустое множество - множество, не содержащее элементов.
Для множества определяются три основные операции.
Определение 1.2. Объединение двух множеств:
Е{]Т=(х\ХеЕ или Хе1).
Определение 1.3. Пересечение:
ЕГ\Т=(х\ХеЕ и Хе1}.
Определение 1.4, Разность:
Е-Т = (Х\ХеЕ и ХеТ).
Все элементы одного множества обладают, как правило, одним
свойством.
Пример: Все целые, все дробные числа, все точки плоскости.
Выделяют универсальное множество U, которое содержит все объекты
или элементы в данной ситуации. С использованием универсального
множества можно определить операцию дополнения.
Определение 1.5. Дополнение:
E = U-E,
где Е - дополнение, содержащее все элементы универсального
множества, не принадлежащие Е.
Определение 1.6, Равенство множеств Е и Г:
Е= Т, при X 6 Е тогда и только тогда, когда X е Т.
9
Определение 1.7. Е подмножество Т:
ЕсТ тогда и только тогда, когда все элементы Е принадлежат
также и множеству Т. т.е. из X е Е следует, что X е Т.
Е правильное подмножество Т,
то есть ЕсТ, когда Е подмножество Т, но Е * Г.
1.6.	СТРОКИ
Операторы программ состоят из последовательностей символов,
которые называют строками.
Определение 1.8, Строка - это упорядоченная последовательность
элементов (al, а2, аЗ,... , ап) или al а2 а3...ап. Строку часто обозначают
символом с чертой. При помощи оператора сочленения можно составить
строку из элементов или других строк. Оператор сочленения
обозначается точкой между элементами.
Пример'.
а = al а2...ап, Ь= Ы Ь2...bn, тогда
а . b= al a2...an bl...bm
Иногда используется пустая строка е.
Сочленение двух строк, одна из которых g определяется следующим
образом:
а. е = е . а = а
Определение 1.9. Подстрокой строки а = al а2...ап называется
произвольная последовательная выборка элементов из строки а , т.е.
b= Ы b2...bm является подстрокой а тогда, когда существует такое i > 1,
что:
Ь[— а,,
Ьг — Янь •••
bm = ai+m.i, где индекс i+m-1 < и.
Определение 1.10. Сочленением двух множеств S . Т является множество
[ab | а е I и Ъ е 7} .
Пусть S = { а,Ь }, Т = { c,d },
тогда Z . Т = { ас , ad , be , bd }
Сочленение S . Z можно записать в виде Е2.
10
Длина строки а обозначается | а |, так что
если a s Zn, то | а | = п.
Определение 1.11. Для любого конечного множества S есть специальное
множество S", называемое свободной полугруппой и определяемое
следующим образом:
L* = { а | а е для некоторого п или а = е}.
Иначе, для каждого а из Z* справедливо: либо а = е ,
либо существует п такое, что а е S .
Отсюда следует, что а - конечная строка, такая, что | а | = п, и все
элементы строки а £ 2.
1.7. ГРАФЫ
Определение 1.12, Граф - это множество Z элементов, называемых
вершинами, и множество Ф пар вершин {а , Ь}, называемых рёбрами.
Вершины можно рассматривать как точки в пространстве, а пары
вершин - как их связи.
Пусть есть граф S = {a,b,c,d};
Ф={{аЬ} { b с } {cd} {da}}, который описывается двумя
диаграммами:
Определение 1.13. Ориентированный граф - граф, у которого рёбрами
являются упорядоченные пары вершин - ориентированные рёбра или
дуги.
Дуга (ab) отличаемся от (Ьа) направлением стрелки, выходящей из
вершины - хвоста и входящей в вершину - голову дуги. В множестве
рёбер Ф дуги будем описывать в круглых скобках - ( ), а рёбра в
фигурных - {}.
Определение 1.14. Путь - последовательность вершин al...ат, где т > 2,
такая, что для 1 < i < ш-1 существует ребро между вершинами а; и ai+).
Для ориентированных графов путь - это последовательность дуг, для
которой голова одной является хвостом следующей.
И
Определение 1.15, Связанные вершины - это вершины, для которых
существует путь из одной в другую.
1.8. ДЕРЕВЬЯ
Определение 1.16. Дерево - это ориентированный граф, в котором:
1)все вершины, кроме одной, называемой корнем, находятся в голове
только одной дуги;
2) корень дерева не находится в голове какой-либо дуги;
3) корень связан с каждой вершиной дерева.
Схематическое изображение дерева имеет следующий вид:
Определение 1.17. Поддерево - подмножество дерева, которое само можно
рассматривать как дерево.
Выделение поддерева - это отсечение всей структуры выше и части
структуры ниже этой вершины.
Примеры построения поддеревьев для рассматриваемого выше дерева
можно представить в виде:
1) b 2) d 3) b d 4) с
Л |	/ \ Л
е f f е f by
Структуры 1, 2 являются поддеревьями; структура 3 д<е является ни
деревом, ни поддеревом; структура 4 - не поддерево, т.к. она не является
подмножеством рассматриваемого дерева.
Для описания деревьев часто используют термины родословной семьи.
Определение 1.18, Двоичное дерево - это дерево, у которого вершины
имеют не более двух потомков.
12
Определение 1.19. Ориентированное дерево - это дерево, в котором для
каждой вершины все потомки упорядочены по отношению друг к другу.
Если а,Ь,с - потомки вершины g ориентированного дерева, то они
образуют упорядоченное множество. Поэтому на рисунке деревья могут
быть одинаковыми, по общему определению деревьев, но разными
ориентированными деревьями.
1.9. ОБХОДЫ ДЕРЕВЬЕВ
Для генерации команд компилятор должен исследовать все вершины
дерева в заранее определенном порядке.
Определение 1.20, Обход дерева - это упорядоченная последовательность
вершин дерева, в которой каждая вершина встречается только один раз.
Под это определение подходит любая произвольная последовательность
или перебор вершин. Практически полезны воспроизводимые обходы с
конкретными формальными алгоритмами. Их существует много.
Рассмотрим два различных практически реализованных алгоритма. В
обоих алгоритмах каждое дерево рассматривается как корень с
последовательностью поддеревьев и имеет следующий вид:
/|\
bed
/I I
е f g
Поддерево 1
b
Поддерево 2 Поддерево 3
с	d
Л	I
е f	g
Эти поддеревья можно считать деревьями (по определению) и
рассматривать как корни с потомками. Такие алгоритмы реализуются в
виде рекурсивной процедуры.
Алгоритмы обхода сверху и снизу можно представить в виде.
Алгоритм 1, Обход сверху
1. Выбрать корень.	/
2. Выбрать последовательно каждое поддерево слева направо/сверху
вниз.
13
Алгоритм 2. Обход снизу
1. Выбрать последовательно каждое поддерево слева направо, снизу
вверх.
2. Выбрать корень.
Рассмотрим на примере эти алгоритмы
Обходы:
сверху a,b,c,e,f,d,g,
снизу b,e,f,c,g,d,a.
2.	ТРАНСЛЯЦИЯ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ
Арифметическое выражение - часть языка. На примере арифметических
выражений можно рассматривать проблемы трансляции с языков
программирования, т.к. язык математических формул является
простейшей моделью языка ЭВМ.
Арифметические выражения являются важным элементом языков
программирования, и их трансляция входит в функции любого
компилятора.
В этом разделе под трансляцией понимается получение группы
последовательных операций, результатом выполнения которых является
значение арифметических выражений. При этом мы не будем различать
константы и неизвестные переменные( те и другие называют
операндами). Кроме того, не важно, когда выполняется вычисление: в
процессе компиляции или после.
При описании алгоритма используется понятие просмотра.
Просмотр - это чтение всей входной строки. Все алгоритмы делят на
одно-, двух- и т.д. просмотровые.
14
2.1.	ТРОЙКИ
Большинство арифметических операций двуместные, т.е. включают в
себя два операнда. Достаточно часто встречаются алгебраические
тройки элементов, состоящие из двух операндов и результата:
Ес = Б, # Ег,
где Ес - результат; # - операция, а Еь Ег - левый и правый операнды.
Тройка - базовая форма, на наличие которой анализируется любое
выражение.
Для каждого выражения транслятор должен найти последовательность
операций (троек), при выполнении которой с заданными значениями
переменных вычисляется значение всего выражения.
В сложных выражениях большое число промежуточных троек не
используется. Поэтому целесообразно выделение временных переменных
при трансляции выражения.
Введём эти переменные - Ть где индекс i [l...k] - это временная
промежуточная переменная, не используемая в программе, а
используемая в трансляторе во время работы. Она хранится не в памяти,
а в регистре.
Количество временных переменных заранее неизвестно, и транслятор во
время работы должен экономить временную память.
Пример-. Пусть имеется выражение:
g=((a+b)*cd+e*f)
Т1=а+Ь ТЗ=Т1*Т2
T2=cd	T4=e*f
g=T3+T4.
В этом представлении временные переменные используются
нерационально.
При другом представлении:
Т1=а+Ь
T2=cd	T2=e*f
Т1=Т1*Т2	g=Tl+T2.
Следовательно, для вычисления этого выражения достаточно двух
высокоскоростных регистров, при этом время вычисления сокращается
до 40%.
15
2.2.	РАННИЕ (ПЕРВЫЕ) МЕТОДЫ
Перед первыми разработчиками трансляторов стояли такие вопросы.
1.	Когда нужны временные переменные, и как их использовать при
вычислениях?
2.	Если выражение представлено как строка операндов и операций, то
какую операцию надо выполнять первой?
В алгоритме Рутисхаузера предполагалось, что выражение
характеризуется полной скобочной структурой и не учитывается
приоритетность. Первоочередной выполняется операция в скобках.
Форма а + b * с - незаконна по данному алгоритму.
Например в языке APL выражение при отсутствии скобок вычисляется
справа налево. Поэтому эта формула вычисляется верно, а выражение b
* с + а будет рассчитано неверно.
Обрабатывая выражение с полной скобочной структурой, алгоритм
Рутисхаузера присваивает каждому символу S(j) из входной строки
число N(j).
В алгоритме используются следующие обозначения:
S(j) - j-й символ,
N(j) - j-e число,
NMAX - содержит максимальное число, присвоенное N.
Алгоритм: Присвоить.
П1: N(0) <-О, J <-0;
П2: J <- J+1, если готово, то N(J) <- 0 и выход;
ПЗ: если S(J) это "(" или "операнд", то N(J) <- N(J-1)+1 и переход
на П2;
П4: N(J) N(J-1)-1 и переход на П2.
S(0) - является пробелом, находящимся перед фактическим началом
строки, при этом конечное значение J на 1 больше длины строки.
16
Пример:
Задано выражение:
_а+(Ь*с)_,
тогда присваивание чисел будет выполняться согласно таблице:
J: 012345678
S(J): _ а + (Ь * с )_
N(J): 010121210
В выражении может появится более одной такой структуры, а
транслятор выбирает первую встретившуюся. Эта структура
соответствует последовательности символов вида:
L операнд!# операнд? R
L- левая скобка или левый конец выражения,
R- правая скобка или правый конец выражения.
При обнаружении такой структуры значение двуместного выражения
вычисляется и запоминается во временной ячейке Ti (Ti <- операнд! #
операнд?). Обработанные три символа вместе с L, R удаляются , если L и
R скобки, а на их место помещается Ti со значением N=K-1. Если при
этом L и R концы строки, то процесс завершен; иначе алгоритм
повторяет поиск NMAX.
Пример после однократной обработки:
S(j): а + Ti
N(j): 010 10,
где Ti=(b х с)
17
Рассмотрим более сложный пример на метод Рутисхаузера:
Генепиоуемые тпойки!		Арифметическое, выражение
1.	Т1 =а + Ь	_(((a + b)*c) + d) : (*e + (a:f))_ 0 123 4 3 4 3232 1 21 0 1 2 1 23 2 321 0 3 _((Tl*c) + d):(e + (a:f))_
2.	Т1 =Т1 *с	0 12 3 2 32 1 21 0 12 1 23 2 321 0 2 _(Tl + d) : (e + (a:f))_
3.	Т2 = а : f	012 1 21 0 12 1 23 2 321 0 2 _(T1 + d):(e + T2)_
4.	Т1 =Т1 +d	012 1 210121 210 1 _T1 :(e + T2)_
5.	Т2 = е + Т2	0 1 012 1 210 1 _T1: T2_
6.	Т1 = Т1 : Т2	0 10 10 0
2.3.	СТЕКОВЫЕ АЛГОРИТМЫ
Метод Рутисхаузера требует полной скобочной структуры, что является
существенным недостатком. Бауэр и Замельзон предложили
эффективный метод. Основные составляющие этого метода были СТЕК
и таблица переходов.
Один СТЕК используется при трансляции выражения Т, другой - во
время исполнения Е. Транслятор прочитывает выражение один раз слева
направо и вырабатывает последовательность команд двух видов: Ki, К^.
Ki-представляет команду выбора числа по имени i и засылки в СТЕК Е.
Ю - команда выбора двух верхних операндов из СТЕКа Е, выполнения
над ними операции и занесения результата в вершину СТЕКа Е. Когда
при просмотре входной строки считываемый символ является операндом
i, выдается команда Ki с индексом i и транслятор переходит к
следующему символу. Если считываемый символ является операцией £,
18
то производится одно из следующих фиксированных действий:
засылается в СТЕК Т либо выдается команда К^.
В таблице переходов указывается, какие действия должен выполнить
транслятор. Каждой операции языка здесь соответствует строка и
столбец. Элемейтами таблицы являются директивы транслятору в виде
возможных четырех действий транслятора после считывания операции
Операции в вершине СТЕКа Т обозначим буквой т).
1.	Заслать в Т и читать следующий символ;
2.	Генерировать Кп, заслать в Т, читать следующий символ;
3.	Читать из Т, читать следующий символ (используется для удаления
скобок);
4.	Генерировать Кл, читать из Т, повторить с тем же входным символом.
В таблице выделены специальные команды - это конец процесса и
ошибка, которые предписывают транслятору остановиться и выдать
соответствующую команду. Процессор выбирает элементы таблицы,
используя в качестве одного индекса ц верхнюю операцию СТЕКа Т, в
качестве второго £ -операцию, прочитанную последней из входной
строки. Если СТЕК Т пуст, то считается, что выражение прочитано.
Таблица переходов представляется в виде
	X	(	+		*	/	)	
X	конец		1	1	1	1	1	ошибка
(	ошибка	1	1	1	1	1	3	
+	4	1	2	2	I	1	4	
-	4	1	2	2	1	1	4	
*	4	1	4	4	2	2	4	
1	4	1	4	4	2	2	4	
19
Структурная схема стекового транслятора
20
Рассмотрим работу транслятора на примере выражения:
(a*b+c*d)/(a-d)+b*c
т	Считанный символ	Дейст- вие	Коман да
Л	(	1	
(	а		Ка
(	*	1	
(*	ь		КЬ
(*	+	4	К*
(	повторить +	1	
(+	с		К.
(+	*	1	
(+*	d		Kd
(+*	)	4	К*
(+	повторить)	4	К+
(	повторить)	3	
Л	/	1	
/	(	1	
/(	а		Ка
/(	-	1	
/(-	d		Kd
/(-	)	4	К-
/(	повторить)	3	
/	+	4	К/
Л	повторить +	1	
+	ь		КЬ
+	*	1	
+*	с		Кс
+*	Л	4	К*
+	Л	4	к+
Л	Л	конец	
Полученная последовательность команд имеет вид:
Ка, КЬ, К*, Кс, Kd, К*, К+, Ка, Kd, К-, К/, Kb, Кс, К*, К+.
Опустив К, получим: ab*cd*+ad-/bc*+
Эта бесскобочная структура есть польская запись.
21
Исполняющая программа использует СТЕК Е и читает польскую
запись слева направо. Операнд при чтении заносится в СТЕК Е.
Операция при чтении применяется к двум верхним элементам Е. Для
записи, выдаваемой транслятором, не возникает проблем (явных и
неявных) старшинства операций. Программа выполняется слева
направо. Временная память автоматически управляется СТЕКом Е и
содержит все промежуточные значения.
3.	ФОРМАЛЬНЫЕ МОДЕЛИ ГРАММАТИК
3.1.	СИНТАКСИС И СЕМАНТИКА
Известно, что синтаксис языка - это множество всех правил, согласно
которым его основные символы - слова составляются в предложение; а
семантика языка - это множество правил интерпретации значения или
смысла предложения.
Правила, по которым составляются предложения, обычно изменяются
значительно реже смысла входящих в них слов. Поэтому синтаксис
языка часто считают не зависящим от смысла. Однако смысл в
значительной степени определяется синтаксисом.
3.2.	ТЕРМИНАЛЬНЫЕ СИМВОЛЫ И СИНТАКСИЧЕСКИЕ
ПЕРЕМЕННЫЕ
Терминальные символы - это базовые элементы, из которых
конструируются строки и предложения. Терминальными символами
могут быть не только буквы, но и слова. Числа, записанные в разных
системах счисления, тоже можно считать терминальными символами.
Поскольку дайна терминальных символов может быть больше единицы,
в программу транслятора включают специальную программу -
препроцессор.
В задачу программы препроцессора входит распознавание много-
элементных терминальных символов при чтении входной строки, а затем
передача транслятору одноэлементного внутреннего представления
символов (препроцессор - это синтаксически ориентированный
транслятор). В соответствии с заданными синтаксическими правилами
из базовых букв и цифр составляются операнды, которые препроцессор
анализирует, собирает операнды в таблицу и передает транслятору
внутренний символ. Следовательно, множество терминальных символов,
22
используемых пользователем, может не совпадать с множеством
терминальных символов транслятора. Синтаксис, используемый для
описания операндов, более простой, чем синтаксис полного
естественного языка.
Синтаксическая переменная - это переменная, принимающая значение из
некоторого множества.
Будем обозначать терминальные символы прописными латинскими
буквами, а синтаксические переменные - строчными греческими;
строчными латинскими буквами будем обозначать и терминальные, и
переменные символы.
Имя переменной будем заключать в "< >". Синтаксической переменной в
русском языке может быть часть речи. Синтаксические переменные
будем использовать при построении предложений и определении
грамматики, однако синтаксические переменные отсутствуют в
построенном предложении.
3.3.	СИНТЕЗ СТРОК
Например, понятие <предложение> в рамках грамматики русского языка
может состоять из понятий существительное во множественном число
и <глагол во множественном число.
Пример-. Самолеты летают.
<Сущ. в мн.ч.> <Гл. в мн.ч.>
Описание правил составления строк терминальных символов является
целью всех грамматик. Основная операция, используемая при
построении предложения, - это подстановка (замена переменной на часть
строки), которая обозначается X. Эту операцию можно применять к
любой строке, в которой встречается переменная
у=А £ В, с учетом х, где х=С у
у=АСу В
Пример'.
Пусть задана синтаксическая переменная <оператор GOTO>.
Справа от команды GOTO обычно указывается операторная метка.
23
Можно ввести новую синтаксическую переменную -«операторная метках
Таким образом, правила формирования или построения оператора
можно выразить в виде правила подстановки:
•«оператор GOTO>-> GOTO -«операторная метка>
Предположим, что все метки состоят из четырёхзначного числа, слева от
которого буква А. Левая строка непосредственно порождает правую, и
эту операцию непосредственного порождения можно записать в виде:
GOTO «операторная метка> => GOTO А<четырехзначное число>
Если одна строка получается из другой с помощью одной или более
подстановок, то используется => со * и говорят, что левая строка
порождает правую. Вышеописанные выражения можно записать более
кратко:
«оператор GOTO> =*> GOTO А «четырехзначное число>
Правил подстановок с одинаковыми левыми частями может быть
несколько. Допустим, что метки состоят из четырехзначных чисел, перед
которыми ставится буква В. Имеются два правила подстановки,
определяющие операторную метку:
«операторная метка>-> А «четырехзначное число>
«операторная метка>-> В «четырехзначное число>
Любое из этих правил может быть использовано в любом месте строки.
Обобщаем:
«операторная метка>-> <буква> «четырехзначное число>
<буква>-> А
<буква>-> В
Поэтому справедливо:
«операторная метка> =*> А<четырехзначное число>
«операторная метка> =*> В«четырехзначное число>
24
Из примера следует, что для любого языка может быть несколько
грамматик, порождающих этот язык.
Эквивалентные грамматики - две различные грамматики G1 и G2,
которые порождают одинаковые множества предложений.
3.4.	ОПРЕДЕЛЕНИЕ ГРАММАТИК
Формализуем введенные понятия. Как отмечалось, множество со знаком
* означает множество строк конечной длины, элементы которых
принадлежат этому множеству (включая е - пустую строку).
S - множество терминальных символов, а Т - множество переменных
символов.
Определение 3.1 Правило подстановки
Правило подстановки - это упорядоченная_пара строк (_х, у), где х есть
множество всех строк за исключением е, хе{Т*-е}, а уе(ТиЕ)*, т.е. у
есть множество строк конечной длины, элементы которых принадлежат
объединению множеств переменных и терминальных символов.
Правило подстановки записывается в виде ( х-> у), при этом левая часть
правила есть корень правила, а правая есть аргумент.
Определение 3.2. Грамматика с фразовой структурой (ГФС)
Грамматика с фразовой структурой - это упорядоченная четверка
G=(E, Т, П, о).
S - множество терминальных символов.
Т - множество переменных символов.
П - промежуточное множество правил подстановок в S и Т.
о - начальный символ грамматики или переменный символ из Т,
такой, что о—> у является правилом подстановки из множества П для
некоторой строки у.
Примеры описания грамматик:
1.	ГФС - (S={A,B}, Т={а,Р,у}, П={а->АВА, ар~>В, Р->Ва}, а)
2.	не ГФС -(Е={А,В), Т={а,р,у}, П={а->АВА, ар->В, В->Ва, а->е}, а)
Определение 3.3 Непосредственное порождение
Пусть х и_у - произвольные строки терминальных и переменных
символов [_х и_у е (_Е u Т )*], где х ф е. х непосредственно
порождает у ( х => у) тогда и только тогда, когда х содержит
25
подстроку а>2 (_ х= col со2 соЗ) такую, что со2_- корень правила
со2-> 2изП, а у - результат подстановки Z вместо со2, у= col Z соЗ
Определение 3.4. Порождение
Пусть х и у - строки из опр. 3.3. х порождает(=*>)_у тогда и только
тогда, когда существует множество строк zl, z2, ... , zn при п>2 таких,
что справедливы следующие выражения:
zl= х, zn= у и любое Zj=> Zj+i
для всех i=l,2,..,n-l, т.е. имеется последовательность одной или
нескольких подстановок:	_
х = zl => z2 => ... => zn = у
Пример. Пусть задана грамматика
G = ({A,B,C}, {а,р,у,ст},П,ст)
П = { ст->а₽ : 1
а—>АВ :2
Ру->а :3
р-> С :4}
Для заданного множества правил подстановок справедливо следующее
утверждение:
2
а)	АаС=>ААВС
Над знаком непосредственного порождения обычно указывают номер
правила подстановки, а корень правила подчеркивается.
3
б)	Руа => аа
в)	руа =*>АВАВ
3	2	2
Руд =>аа =>АВа =>АВАВ
Но выражение в) можно получить и из других последовательностей:
3	2	2
руа => аа => аАВ=> АВАВ
2	3	2
Руа_=> руАВ=> аАВ => АВАВ
Отсюда, если X порождает Y( X =♦> Y), то это не означает
единственную последовательность применяемых правил. Действительно,
26
первые две последовательности имеют одинаковый порядок правил
подстановок, но являются все же разными преобразующими
последовательностями, т.е. для однозначного определения
последовательности подстановок недостаточно определить порядок
применения пра'вил.
Фактически язык - это множество строк терминальных символов,
построенных по правилам, задаваемым грамматикой.
Определение 3.5. Язык
Пусть G=(L,T,n,o) - ГФС. Язык грамматики G- это множество Л строк
терминальных символов (ЛсЕ*) такое, что строка:
ХеЛ
выполняется тогда, когда она получена из начальной переменной ст, т.е.:
ст =*> X, при этом Л называют предложением языка.
Определение 3.6. Сентенциальная форма
Сентенциальная форма грамматики С=(£,Т,П,ст) , обозначаемая - S,
есть строка терминальных и/или переменных символов, полученная из ст:
S e(SuT)*, ст =*> S
Пусть задана грамматика простого языка (с небольшим числом
терминальных и переменных символов), порождающая множество строк
буквы А нечётной длины
G=({A},{a},n,a)
П= {а-> ААа	: 1
а-> А	:2}
Можно показать, что эта грамматика действительно порождает
множество конечных строк буквы А.
Известна также грамматика Гинзбурга. Она порождает строки из буквы
А длины f(n), для п> 1,2... ,где f(n)= £ i, и называется также порождающей
грамматикой для f(n).
Gg = ({А},{а,р,уЛ,ц,у,т,ст},П,ст)
П = {ст->цту :1
у-» г/	:2
у->ц:3
тц->^а :4
т^тр :5
27
>pv :6
vt—>tv	:7
va->pA :8
0t—»t0	:9
0a—>aA .10
цц—>£	: 11}
Существует формальное доказательство того, что грамматика Go
является порождающей для f(n), то есть предполагается, что: xeA(G) и
формально доказывается, что х будет иметь длину f(n). Однако такое
доказательство достаточно громоздко, поэтому ограничимся описанием
сравнения формальных представлений приведённых двух простых
грамматик.
Отличие предыдущего примера грамматики простого языка от Gg в том,
что для этой грамматики можно было представить единственную форму
для всех промежуточных сентенциальных форм в последовательности
подстановок. В последнем случае (для Gg ) эта форма постоянно
изменяется, кроме того, иногда появляются альтернативные структуры,
т.е. возникают дополнительные трудности, которых не было в
предыдущем случае.
3.5.	СПЕЦИАЛЬНЫЕ КЛАССЫ ГРАММАТИК
Определение 3.7. Контекстно-свободная грамматика(КСГ)
Грамматика G=(S,T,n,cr) называется контекстно-свободной тогда и
только тогда, когда она является ГФС и корни всех правил подстановки
х —> у из множества П являются одинаковыми переменными ( хеТ ).
Отдельные правила, обладающие этим свойством, называются
контекстно-свободными правилами подстановки.
Определение 3.8. Контекстно-зависимая грамматика (КЗГ)
Грамматика G=(S,T,n,c) будет контекстно-зависимой грамматикой
тогда и только тогда, когда она есть ГФС и каждое правило
подстановки х_->_у из множества П представляется в виде: x=_Ui,
£, Uz ; У= Ui, z, U2 , где z - строка или подстрока, причем z*e.
Отдельные правила, обладающие таким свойством, называются
контекстно-зависимыми правилами подстановки.
В КСГ каждая подстановка содержит замену одной переменной на
строку (возможно пустую). В КЗГ выполняется такая же замена, т.е. одну
переменную заменяет строка, но не пустая. Переменная должна
28
появиться в отдельном контексте : Ui - слева, U2 - справа. Таким
образом, будем считать, что контекст может быть как правым, так и
левым.
Хотя правила подстановки в КЗГ кажутся более ограниченными, но КЗГ
является более общим классом грамматик. Если контексты Ui, U2 в
каждом правиле равны пустой строке е, большинство контекстно-
свободных языков можно считать контекстно-зависимыми. Однако КСГ,
у которой аргумент одного или нескольких правил равен пустой строке,
не является контекстно-зависимой грамматикой.
Пример: Заданы два правила:
5->А :1
£а-»Аа :2
По определению, правило 1 - контекстно-свободное, а правило 2 -
контекстно-зависимое.
Применим оба правила к входной строке В^аС. Обе подстановки
порождают одинаковый результат, который не является пустой заменой.
1
В^аС => ВАаС
2
В^аС => ВАаС
Однако правило 1 можно применить и к строке В£у, а правило 2
применить к ней нельзя.
Следовательно, когда контекст правила совпадает с контекстом строки,
контекстно-зависимое правило ведет себя как обычная замена одной
переменной.
Если контекст не подходит, то замену выполнять нельзя.
Примеры КСГ и КЗГ
Пусть S= {А,В,С}, Т= {а,Р,у} в грамматике G=(S,T,n,o)
1. П={а-»Р	:1	
Р->АВа	2}	G-КСГ
2. П={а-»аР	:1	
аР-»ау	:2	
у-»АВа	:3}	G-КЗГ
3. П={а->ар	:1	
аР-»Ру	:2	
Р->А	;3}	G-ГФС, но не КСГ и не КЗГ
29
Рассмотрим пример контекстно-свободной грамматики языка множества
арифметических выражений.
Пусть Са=(Е,Т,П,ст) =(A,B,C,D, - ,Z)u{(,),*,/,+,-,?}
Т={<арифметическое выражение:», <операция типа сложения:», <терм>,
<операция типа умножения:», <первичное>, <множитель>, <операнд>}
П= {«операция типа сложения>—>+	:1
«операция типа сложения:»-» -	:2
«операция типа умножения:»-»*	:3
«операция типа умножения:»-»/	:4
<первичное>-»«операнд>	:5
<первичное>—>(<арифметическое выражение:») :6
<множитель>—><первичное>	:7
<множитель>—><мно5китель>1' <первичное>	:8
<терм>—><множитель>	:9
<терм>—><терм> «операция типа умножения:»
«множитель:»	:10
«арифметическое выражение:»—><терм>	: 11
«арифметическое выражение:»—><операция типа
сложения:» <терм>	: 12
«арифметическое выражение:» -^«арифметическое
выражение>«операция типа сложения>«терм> : 13
< операнд:»—> А	: 14
«операнд:»-» В	; 15
<операнд>-»7	:40
Следовательно, язык A(G) есть множество всех строк символов в Z
( хеЕ*) таких, что:
«арифметическое выражение:» =*> х
Пример'.
Покажем, что выражение (А+В) принадлежит A(G), то есть является
языком грамматики G.
30
11	9
«Арифметическое выражение> => <терм> => <множитель>
7	6
=> <первичное> => («арифметическое выражение>)
13
=>(<арифмет. выражение><операция типа сложения>«терм>)
11
=> (<терм> <операция типа сложения> <терм>)
9
=> (<множитель> «операция типа сложения> <терм>)
7
=> (<первичное> «операция типа сложения> <терм>)
5
=> (<операнд> «операция типа сложения> <терм>)
14
=> (А «операция типа сложения> <терм>)
1
=> (А + <терм>)
9
=> (А + <множитель>)
7
=> (А + <первичное>)
5
=> (А + <операнд>)
15
=> (А + В)
4. СВОЙСТВА ФОРМАЛЬНЫХ ГРАММАТИК
Теория контекстно-свободных языков разработана достаточно широко.
В рамках курса изучим свойства КСГ, наиболее полезные при
разработке алгоритмов трансляции.
4.1. ЛОКАЛИЗОВАННАЯ СТРУКТУРА
Контекстно-свободные грамматики обладают свойством локальности,
заключающимся в том, что результаты подстановки, выполненной в
некоторой области строки, остаются в этой области.
31
Для формализации этого утверждения доказывается одна лемма и две
теоремы. В целях упрощения воспользуемся графической
интерпретацией одной из этих теорем о разбиении вывода на локальные
подвыводы.
xlx2 ... х1 ... xj ... xn	х1х2 ... xl... |xj ... хп
и*	и* | и*
yly2 ... ys ... yt ... ym	yly2 ... ys... I yt ... ym
Предположим, что имеется сентенциальная форма
х = xl х2 хЗ
Пусть у сентенциальная форма, выводимая из х (х =*> у).
Тогда существует разбиение у = у1 у2 уЗ такое, что общая
подстановка разбивается на множество полученных параллельных
последовательностей правил подстановок. Это позволяет разбивать на
независимые подчасти построение предложений и их анализ.
Для доказательства того, что свойство локализации не распространяется
на языки, не являющиеся контекстно-свободными, рассмотрим
грамматику GN=(E,T,n,cr), для которой в П входят следующие правила
подстановки:
П= {<э—>ра : 1
а—>аа :2
ца->ац :3}
Строки х = цаааа и у = аааац - это сентенциальные формы в Gn
и можно вывести _
х =*> у повторными применением правила 3.
Действительно:
3	3	3	3
цаааа =>ацааа =>аацаа =>аааца =>аааац
Очевидно, эти строки противоречат теореме о разбиении, которая верна
для контекстно-свободных грамматик. Правило 3 не является
контекстно-свободным и позволяет символу ц продвигаться по строке,
проходя через любые границы разбиения.
32
4.2. ИСПОЛЬЗОВАНИЕ СВОЙСТВА ЛОКАЛИЗАЦИИ.
НЕЗАВИСИМОСТЬ ПОРЯДКА ПРАВИЛ ПОДСТАНОВКИ.
КАНОНИЧЕСКАЯ ФОРМА
Теорема 4.1 Пусть вывод х=*> у получается последовательностью
правил подстановки_Р1, Р2, РЗ,..., Pi, Pi+1,..., Рп. Пусть можно сделать
разбиение: х = х! х2 и у - у! у2 такое,что Pi войдет в цепочку
правил для вывода х2_ =*> у2, a Pi+1 войдет в цепочку_ правил для
вывода х1 =*> yl. Тогда порождение х =*> у получится
последовательностью правил подстановки:
Р1,Р2,...,Pi-1, Pi+1, Pi, Pi+2,... ,Pn
По теореме 4.1, порядок выполнения подстановок может быть изменен
без изменения конечного результата. Полученная последовательность
является фактически той же самой цепочкой правил подстановки, при
этом двумерная структура (дерево), которой является правило
подстановки, практически представляется как одномерная строка.
Пример:
Задана строка и правила подстановки A£BvC
£->В	:1
v-> В	:2
Имеются всего две возможные последовательности
1	2
A^BvC => ABBvC => АВВВС
2	1
A^BvC => А^ВВС => АВВВС
Кроме того, эти две возможные подстановки можно выполнить
параллельно:
А £| BvC
Ui U2
А В I ВВС
Вводится единственная форма представления - каноническая
последовательность правил.
33
Определение 4.1. Каноническая форма. Каноническая последовательность
правил
Pl Р2 Рп-1
Пусть Z1 =*> Zn. Последовательность Zl => Z2 => .... => Zn
называется канонической последовательностью правил тогда и только
тогда, когда каждое правило подстановки применяется к самой левой
переменной, имеющейся в строке.
Каноническая форма любой последовательности правил Р1,... ,Рп для X
=*> Y может быть получена с помощью многократного применения
следующего приема:
Пусть X = XI Х2. Если Pi встречается в последовательности для: Х2
=*> Y2, a Pi+1 в последовательности для: XI =*> Y1, тогда Pi и Pi+1
надо поменять местами. Потеореме 4.1, новая последовательность также
будет верной для X =*> Y.
Предположим, что после конечного числа перестановок получилась
последовательность Р1,...,Рп, в которой дальнейшие перестановки
невозможны, тогда конечная цепочка каноническая. Очевидно, что это
утверждение справедливо, т.к. либо каждое правило Pi+1 применяется к
подстроке из X, находящейся справа от подстроки, к которой
применяется Pi , либо Pi+1 применяется к переменной, встречающейся в
аргументе для Pi.
Если имеется предложение, у которого более одной канонической
последовательности правил, начинающихся с начальной переменной, то
порождающая его грамматика называется неоднозначной.
У одного и того же языка может быть много грамматик, порождающих
его, и не все из них обязательно неоднозначны. Язык может порождаться
как неоднозначными, так и однозначными грамматиками.
Пример: Грамматика с множеством правил :
П = { о-+аР : 1
о-+Ар :2
а->А :3
Р->В :4}
Эта грамматика порождает в качестве языка единственную строку АВ,
но канонических последовательностей правил для этой строки 2:
1	3
34
ст =>аВ=>АВ
2	4
ст =>Ар=>АВ, поэтому грамматика G неоднозначная.
Но грамматика с множеством правил
П = { ст-»аВ : 1
а—>А :2} порождает тот же самый язык АВ однозначно.
4.3.	ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ЦЕПОЧЕК ПРАВИЛ
ПОДСТАНОВКИ
Выберем интуитивно более удовлетворительное представление
последовательностей подстановок. В этом представлении каждую
последовательность подстановок будем представлять в одной форме.
Пусть £->Ul.... Un является правилом подстановки в грамматике.
Графическое представление этой подстановки реализуется в виде графа:
£
/|\
U1 U2...Un
Корневой, или родительской, вершиной является левая часть, или корень
правила. Отходящие вниз слева направо вершины - это символы правой
строки, записанные в том же порядке. Граф последовательности
подстановок получается присоединением к вершине той подстановки из
последовательности, которая заменяет данную переменную.
Пример-.
П = { ст—>аВ : 1
а-»А : 2}
Строка АВ порождается следующей цепочкой подстановок:
1	2
ст => аВ => АВ
35
Граф:
ст
/\
а В
/
А
Более сложный пример - дерево, представляющее цепочку,
порождающую выражение ( А + В ) * С с помощью грамматики Ga
(арифметических выражений).
Дерево:
<Арифметическое выражение>
<Терм>
/ I \
<терм> <операция <множитель>
/ типа умножения>
<множитель>	|
<первичное>	|
/ I \ I
/	<арифм.выр>	)	|
/ / \ \ \ \
| <терм> < операция	\	\
|	| типа +> <терм> \	\
| <множитель> ||	\	\
II II \ \
| <первичное> | <множитель> \	\
II II \ \
| <операнд> | <первичное> |	|
|	|	| <операнд>
(А + В ) *
<первичное>
<операнд>
36
Пример: (предложение русского языка)
< предложение>
/ \
<группа подлежащего>	<группа сказуемого
/ \ / \
<прилагательное> <существительное> <глагол> <дополнение>
I I	I /	\
|	|	| <прилаг.> <сущ.>
I	I	III
Способный студент получил хорошую оценку.
По определению, неоднозначным является предложение, имеющее
несколько различных последовательностей правил или деревьев
подстановок.
Примером может быть предложение "Мать любит дочь", в котором
неоднозначность реализуется графически и имеет два варианта
толкования:
(А) <предложение>
/ \
<подлежащее> <группа сказуемого>
I	/ \
<существительное>	/	\
|	<глагол> <дополнение>
|	|	<существительное>
I	I I
Мать	любит дочь.
(В) ' <предложение>
/ \
<группа сказуемого> <подлежащее>
/	\	I
/	\ <существительное>
<дополнение> <глагол>	|
I	I	I
I	I	I
<существительное> |	|
I	I	I
Мать любит дочь.
37
4.4.	ДВОИЧНЫЕ ДЕРЕВЬЯ ТРАНСЛЯЦИИ
Двоичные деревья трансляции формируются из произвольного дерева
подстановок. Для формирования двоичного дерева к произвольному
дереву применяется специальная процедура, т.е., если Т - произвольное
дерево, то эквивалентное двоичное дерево В(Т) строится применением
двух правил ко всем парам вершин дерева Т. Пусть а и b - две вершины в
Т.
1.	Вершина b - это левый потомок вершины а в В(Т) тогда
и только тогда, когда b - самый левый потомок вершины а в дереве Т.
2.	Вершина b - это правый потомок вершины а в В(Т) тогда
и только тогда, когда b - ближайший из правых братьев а в дереве Т.
Ниже представлены произвольное дерево Т и эквивалентное ему
двоичное дерево В(Т):
Т а В(Т) а
/|\ /
bed	b-c-d
Двоичный эквивалент примера с предложением "Способный студент
получил хорошую оценку":
<предложение>
/
<группа подаежащего>
/ \
<прилагательное>
<группа сказуемого>
/
/ \
/
/
/
/
/
/
Способный
<существительное> <глагол>
/ / \
/	/ <дополнение>
/ / /
/	/ <прилагательное>
/ / / \
/	II <существительное>
III	/
студент получил хорошую оценку.
38
Пример'.
Более сложным примером может быть двоичное дерево
арифметического выражения (А + В) * С.
Произвольное дерево по сравнению с двоичным кажется более удобным.
Все терминальные символы расположены на концах веток, и, немного
изменив форму дерева (не изменяя содержания), можно получить
анализируемое предложение в правильном (исходном) порядке.
В двоичном дереве все терминальные символы равномерно
распределены по дереву, форма предложения изменяется и читать его
сложнее.
Все переменные символы произвольного' дерева являются
промежуточными вершинами с потомками, а терминальные символы
потомков не имеют. Они же являются терминальными вершинами
дерева, т.е. произвольное дерево является более простым для понимания.
Достоинства двоичного дерева - удобство интерпретации с его помощью
алгоритмов трансляции и некоторые другие, обусловленные его
структурными свойствами.
4.5.	СВОЙСТВА ДВОИЧНОГО ДЕРЕВА
Левосторонняя	(правосторонняя)	цепочка двоичного дерева
последовательность вершин al, а2,..., an (n > 1), где ai есть левый
(правый) потомок ai-1 для i=2,...,n
Цепочка al, а2,..., ап содержится в цепочке Ы, Ь2,..., bm, если
существует) > 0 такое, что ai = bj+1, для i = 1,2,...,п, где n < m. При этом
al, а2,..., ап будет подцепочкой цепочки Ы, Ь2,..., bm.
Максимальная цепочка содержится только в самой себе
Двоичное дерево
al
/
а2
/ \
аЗ аб
/ \ / \
а4 а5 а7 а8
39
Левосторонняя цепочка
al а2
/ /
а2	аЗ
/	/
аЗ	а4
Правосторонняя цепочка
аб	а2
\ \
а8 аб
Максимальная левосторонняя
цепочка
al
/
2
/
аЗ аб
/ /
а4 а? а8
Максимальная правосторонняя цепочка
а2
\
аЗ аб
\ \
а4 а5 а8
Левосторонние цепочки можно определить для Т так же, как и для В(Т).
Пусть задано П =	{ сг-»арС	:	1
а-»А	:	2
Р~>В	:	3 }
1	2	3
а => арС => АРС => АВС
40
На основе определения преобразования можно сформулировать
следующие леммы.
Лемма 4.1, Левосторонние цепочки в В(Т) являются левосторонними
цепочками в Т, и наоборот.
Пусть задано дерево Т Из дерева Т формируется
ст	дерево В(Т)
/|\	о
а₽С	/
/ /	а-р-С
АВ	/ /
А В
Поскольку братья, выходящие из вершины дерева Т, являются членами
правых частей некоторых правил подстановки, то справедлива лемма
4.2.
Лемма 4.2. Максимальная правосторонняя цепочка в В(Т) является
аргументом некоторого правила подстановки Р. Предок первой
вершины в цепочке есть корень Р.
В примере максимальная правосторонняя цепочка В(Т) имеет вид
а
\
\
С
и является аргументом первого правила подстановки.
Предок а есть ст - корень этого правила подстановки. Поскольку у
каждой переменной вершины в Т имеется хотя бы один потомок,
справедлива следующая лемма 4.3 о максимальных левосторонних
цепочках.
41
Лемма 4.3. Максимальная левосторонняя цепочка в В(Т) содержит
только один терминальный символ, являющийся последней вершиной в
цепочке.
с
/
а Р
/ /
АВС
4.6.	ФРАЗЫ
Фразы в сентенциальной форме - это подстроки, каждая из которых
получена в последовательности подстановок из одной переменой.
Так как переменная, из которой получена фраза, необязательно является
начальной переменной, то фразы необязательно являются
сентенциальными формами.
Определение 4.2.
Пусть х - сентенциальная форма в _языке_Л(О), и пусть выполнено
разбиение х на три подстроки: х = х1 х2 хЗ, тогда х2 - фраза из х
тогда и только тогда, когда^уществует^последовательность подстановок
для х, содержащая строку увида:у= х1 £ хЗ,
где с =*> у =*> х
В графической интерпретации х2 - фраза тогда и только тогда, когда х2
является строкой символов, выходящих из одной вершины
В дереве трансляции, представленном ниже, ABCD - фраза, так же как -
ВС и аРу.
с
Л
а Р
/ /|\
А а Р у
/ Л \
А ВС D
42
Фраза, не содержащая никаких других фраз, называется простой
фразой.
Простая фраза - А, ВС.
Основа предложения - самая левая простая фраза предложения. Основой
предложения AABCD является первая буква А.
4.7.	8 - СВОБОДНАЯ ГРАММАТИКА
Для решения задач трансляции необходимо модифицировать
грамматики. Однако при модификации нужно сохранить структурность,
т.е. выразительность грамматики, или семантическую интерпретацию.
Одна из таких модификаций состоит в удалении правил подстановки с
пустыми строками в правых частях. Модифицированная таким
образом грамматика называется s - свободной грамматикой. Для
заданной грамматики G = (Е,Т,П,о) рассмотрим алгоритм,
позволяющий построить модифицированную GM , которая является е-
свободной.
Алгоритм:
1.	Пусть П1 = U для всех £-> йеП , U*e }, т.е. пусть П1 будет
множеством всех правил подстановок, у которых аргумент не равен е.
2.	Пусть Ф = {^ | ^=*>е в G}, где Ф - множество всех переменных, из
которых можно вывести е в грамматике G.
3.	П2 строят из П следующим образом: для каждого правила
подстановки £-> йеП, если U = U1 v U2 , где U1 и(или) U2 не
пусты, а уеФ, то £-> U1 U2 включается в П2.
4.	Из П1 и П2 - формируется Пм.
Пм = Ш и П2
43
Пример-.
П = { о—>АЕ,В	: 1
: 2
^->А	: 3 }
Тогда:
Ш = {а->А£В	:1
^->А	:2}
Ф={^} , П2={а->АВ)
и Пм={а->АЕ,В :1
а->АВ :2
^->А	:3}
В примере A(G) есть A(GM).
Это утверждение можно распространить на общий случай.
Рассмотрим следующие правила подстановки грамматики G:
П = {о-^	:1
£->А
:2
:3)
Пусть Пм - множество правил подстановки для е-свободной грамматики
GM, построенной из G при помощи описанного алгоритма:
Пм = {	: 1
. Jj->A : 2 }, тогда
A(G) = { А, е}, a A(GM) = { А } - отсюда вытекает теорема:
Теорема 4.2,
Пусть G(S,T,n,a) - грамматика и GM - это с- свободная грамматика,
построенная рассмотренным алгоритмом. Тогда:
A(G„) = A(G)- {е}.
44
5.	СТРУКТУРА ДВОИЧНЫХ ДЕРЕВЬЕВ ТРАНСЛЯЦИИ
Первые алгоритмы, рассматриваемые здесь, ориентированы на общие
контекстно-свободные языки.
Каждый алгоритм может быть реализован различными программами,
т.к. на разработку программ влияют следующие факторы :
1.	Тип ЭВМ.
2.	Язык программирования.
3.	Вид используемого транслятора.
Первый метод грамматического разбора, который будем рассматривать,
это грамматический разбор сверху вниз.
Для описания метода используем простой алгоритм.
Пусть грамматика G с начальной переменной ст, a S - некоторое
предложение в языке, порожденное грамматикой G. Задачу трансляции
представим в виде: задан корень дерева, надо получить
S1,52,..8п(терминальные символы, или некоторое предложение языка).
Грамматический разбор сверху вниз соответствует названию. Дерево
заполняется сверху вниз, слева направо, начиная с вершины. При этом
двоичное представление дерева позволяет проще описать структуру
дерева трансляции.
5.1.	СКЕЛЕТЫ
Пусть построено двоичное дерево трансляции, начиная с ст и кончая
предложением языка SI,..., Sn.
Определение 5.1.
Позвоночник - это максимальная левосторонняя цепочка от ст к S1.
Пример'. Пусть существует двоичное дерево трансляции S],S2,S3,
позвоночник которого записывается в виде (ст,al, a2,Sl)
45
дерево трансляции позвоночник
дерева (а, а1, а2, S1)
a / al / \ a2 S3 / \ SI a3 / S2	a / al / a2 / SI
Пусть задан позвоночник (о, al, a2,..., am, S1) двоичного дерева.
Каждая вершина позвоночника - это левый элемент максимальной
правосторонней цепочки, являющейся аргументом правила подстановки
(кроме а).
Определение 5.2.
Скелетом дерева подстановок называется позвоночник вместе с
максимальными правосторонними цепочками, выходящими из него.
Получение скелета - это первый шаг при построении полного дерева.
Для однозначного предложения можно построить единственное дерево
подстановок и, следовательно, только один скелет. Все предполагаемые
скелеты должны проверяться поочередно до тех пор, пока не будет'
найдено правильное дерево трансляции. Для систематизации поиска
деревья нужно упорядочивать.
5.2.	УПОРЯДОЧЕНИЕ СКЕЛЕТОВ
Пусть имеется некоторый скелет дерева трансляции (см. следующую
страницу).
Каждая ветвь представляет собой правило подстановки вида:
aj -> aj+1 bl Ь2 ... bk
46
в скелете, представленном ниже:
о
номер правила - i 1 /
’al
/
aj
ij+1/
aj+1
... \
in/ \
an	bl
in+1/	\
/	b2
SI	\
bk
Здесь все правила подстановок пронумерованы, и с каждой ветвью
связан номер соответствующего правила. Таким образом, скелет может
быть представлен однозначно конечной упорядоченной
последовательностью: (il, i2, i3,...).
Определение 5.3. Порядок использования правил (индекс скелета)
Индекс скелета - последовательность номеров правил подстановки,
соответствующих правосторонним цепочкам скелета, рассматриваемым
сверху вниз.
Для упорядочения индексов скелета можно использовать
лексикографический порядок, используемый для упорядочения слов.
Пусть даны две последовательности чисел R и Т:
R=(rl,r2,..,m)
T=(tl,t2,..,tn)
Необходимо упорядочить R по отношению к Т по заданной
упорядоченности индивидуальных элементов.
Или задано отношение порядка между ri и ti, такое, что для всех i либо
ri>ti, либо ri=ti, либо ri<ti. Таким образом, процесс упорядочения R и Т
состоит в том, что вначале анализируют первые элементы каждой
последовательности. При этом:
47
1)	если rl >t 1 , то считают, что R>T;
2)	если rl<tl, то R<T;
3)	если rl=tl, то необходимо исследовать вторые элементы, затем третьи
и так далее до конца последовательности.
Формально R<>T (R упорядоченно к Т) тогда и только тогда, когда
существует некоторое i>l, такое, что ri<>ti и rk=tk для всех k<i.
Считают, что R=T, когда rk=tk для всех к: 1<к<п.
При сравнении скелетов различной длины используют следующее
свойство-.
Пусть R =(г1,г2,...,гп)
T=(tl,t2,...,tm)
R и Т - два индекса скелетов двоичного дерева трансляции и m>n , тогда
R и Т должны отличаться в первых п элементах, по крайней мере, m *
tn.
Действительно, так как m=Sl соответственно есть терминальный
символ, а элемент tn по лемме 4.3 (максимальная левосторонняя цепочка
содержит единственный терминальный символ, являющийся последней
вершиной в цепочке) должен быть переменным символом.
Следовательно, любые два скелета различной длины должны
различаться в своих первых п членах, где п - длина меньшего скелета.
5.3.	ПОСТРОЕНИЕ СКЕЛЕТА
Алгоритм построения левосторонней цепочки достаточно прост.
Сложность - в поиске следующего скелета для этого дерева трансляции.
При описании алгоритма будем использовать специальные, но наиболее
простые структуры данных для правил подстановок. Необходимые для
генерации скелетов данные будем хранить в виде множества таблиц
подстановок. Для каждой переменной а имеется своя таблица,
содержащая запись для каждого правила подстановки с корнем а.'
Выбираемая информация из таблицы - это номер правила и самый левый
элемент правой части правила.
Пример-. Пусть в грамматике G заданы следующие правила подстановки
с корнем а:
48
П={...
а—> А
а-> уа
а->С
:3
:5
:8}
Таблица подстановок для этих правил будет иметь вид:
Nnn	номер	элемент
1	3	А
2	5	Y
3	8	С
4	X	X
К записи этой таблицы обращаются по имени столбца (номер, элемент) и
номеру строки. Поскольку количество строк различно - имеется
специальная строка конца, содержащая символ X-
Для приведенного примера записи можно представить в виде:
номер(а,2)=5
элемент(а,3)=С
элемент(а,4)=х
Кроме таблиц подстановок, при построении левосторонней цепочки
используют другую таблицу, называемую матрицей связи. Эта матрица
может быть организована различными способами. Будем ее
рассматривать как логическую функцию двух параметров. Обозначим
эту матрицу как связь (а,Ь), где
а - переменный символ,
b - любой символ.
Эта функция принимает значение истина, если существует левосторонняя
цепочка от вершины а к символу Ь, и ложь - если такой цепочки нет.
Для построения левосторонней цепочки определим процедуру
"Цепочка". Параметрами этой процедуры является переменные:
(a, S, LHC, отказ).
а- начальная переменная для формируемой цепочки,
S- терминальный символ на конце цепочки,
LHC- результирующий вектор, содержащий индекс скелета,
отказ - логическая переменная, принимающая значение истина в
случае, если процедура не может построить цепочку.
49
В первом варианте алгоритма используется матрица связи для проверки
существования цепочки от а к S . Если такая цепочка(а,^1,^2,....5)
существует, то существует правило подстановки вида а-* £1... :i с
индексом i, и поэтому соответствующая запись должна находиться в
таблице подстановок для а в некоторой строке N такой таблицы.
Чтобы найти следующий элемент цепочки от а к S, производится поиск в
таблице подстановок для переменой £1 такой записи i, что функция связь
(элемент^ ,i),S) = истина, т.е. находится левый потомок £1 , элемент
(£1 ,i), который соединяется с S через левостороннюю цепочку.
В общем случае, когда алгоритм находит промежуточную вершину £к с
индексом к, он производит поиск записи i в таблице подстановок для £к
такой, что связь (элемент (^K,i),S) =истина.
Если в процессе работы алгоритма окажется элемент (^K,i)=S, то работа
завершена.
Рассмотрим далее, как обрабатываются леворекурсивные правила
подстановок. Допустим, существует леворекурсивное правило
подстановки с корнем £к. Это правило имеет вид:
£к->£к... : i.
В зависимости от положения записей в таблице подстановки может
оказаться, что первой выбирается запись вида:
индекс элемент
I
В этом случае, поскольку левосторонняя цепочка от £к к S существует, то
с,к опять добавляется к частично завершенной цепочке.
Алгоритм зацикливается, постоянно прибавляя £к к частично
завершенной цепочке.
Определение 5.4. Леворекурсивные правила подстановок.
Множество правил подстановок называется леворекурсивным, если
существует возможная левосторонняя цепочка (о, £1, £2, ... £n, S),
порождаемая этим множеством, от переменной ст к некоторому
терминальному символу S , в которой два различных символа £,i и £j
равны.
Для того чтобы избежать подобных ситуаций, будем использовать
грамматики, не являющиеся леворекурсивными. Это ограничение не
затрагивает сами языки. Кроме того, разрешается правая рекурсия.
Поэтому нет отрицательного влияния на семантику..
50
Блок-схема алгоритма построения левосторонней цепочки
(К описанным ранее переменным добавляется еще четыре.)
т - содержит значение последнего символа, добавляемого к цепочке,
р - проверяемый символ во время поиска в таблице подстановок,
I - место в таблице подстановок, проверяемое в данный момент,
J - параметр индексации при построении вектора LHC.
51
5.4.	РАСШИРЕННЫЙ АЛГОРИТМ ЦЕПОЧЕК
Можно показать, что выделяемая рассмотренным алгоритмом
левосторонняя цепочка является первой в списке всех правильных
лексикографических упорядоченных левосторонних цепочек от а к S.
Чтобы использовать этот алгоритм в программе грамматического
разбора сверху вниз, его необходимо расширить. Поскольку в
грамматическом разборе сверху вниз поиск производится среди всех
возможных скелетов, алгоритм должен уметь находить следующий
скелет после заданного.
Предположим, что такая расширенная процедура существует, а самая
последняя выходная строка является строкой номеров правил
подстановки( il, i2.in ), и представляет некоторую левостороннюю
цепочку от а к S. Следующая в лексикографическом порядке цепочка
имеет длину не менее и и начинается с подстроки( il, i2,..., in-i). Ее индекс
(il,...,in-ijl,...jm). Таким образом, поиск следующей ' левосторонней
цепочки начинается с замены последнего звена предыдущей цепочки.
Если прежняя цепочка (a,pl,..., Pn-i,S), то на следующем шаге
устанавливается новое звено из рй-i в S, причем такой подстановкой, для
которой запись в таблице подстановок для pn-i следует первой за
записью для подстановки in.
Чтобы в таблице переходов для pn-i найти следующее правило
подстановки, которое связывает pn-i с S левосторонней цепочкой, нужно
знать, где находится запись для подстановки in. Этот элемент
информации будет называться ключевым , а связанный с левосторонней
цепочкой вектор- вектором "ключ”. Ключ(к) - место к-й подстановки
цепочки в таблице подстановок для рк-1.
Таблица подстановок для а
индекс |элемент
1:	1	а
2:	6	pl
Таблица подстановок для pl
52
Таблица подстановок для ₽2
индекс	элемент
1:	3	а
2:	7	S
3:	8	рз
Таблица подстановок для рЗ
индекс! элемент
1: 9 IS
Предположим, что "индекс" последней левосторонней цепочки от а к S
(6,4,7), тогда "ключом" будет строка (2,1,2), поскольку правила
располагаются по строкам следующим образом:
правила строки
6-2
4	-	1
7	-	2
Очередная цепочка от р2 к S при дальнейшей работе алгоритма строится
следующим образом. Для получения ещё одной цепочки последний
элемент "ключа" увеличивается и проверяется соотношение связь
(элемент ($2,У)$)=истина.
Поскольку связь существует, то к цепочке присоединяется следующий
элемент рЗ и исследуется таблица подстановок для РЗ, после чего
построение цепочки завершается.
Получаем: Индекс(6,4,8,9)
Ключ (2,1,3,1)
Полнота построения всех цепочек оценивается по отсутствию отказа. В
процессе работы алгоритма может произойти отказ, но в предыдущем
алгоритме эту возможность проверяют на первом шаге, при этом
соотношение отказ - ложь свидетельствовало о том, что цепочка
существует.
Введем обозначения для описания алгоритма.
а - корень левосторонней цепочки
S - терминальный символ
LHC - при вводе последняя полученная цепочка, при выводе -
содержит новую цепочку.
отказ - принимает значение истина при отрицательном результате
работы алгоритма.
ключ- связан с LHC и указывает места правил в таблице
подстановок.
53
длина- длина массивов LHC и ключа и равна нулю при первом
обращении к программе.
Выделение корня правила I по номеру подстановки выполняет
программа корень(I).
Неформальное описание алгоритма расширенной цепочки
1.	Если длина не равна 0, то перейти к 2, иначе, если связь(а,8) = ложь, то
отказ = истина, иначе отказ = ложь.
Рабочая = а, 1=1 и перейти к 3.
(При первом обращении необходимо проверить наличие связи между а и
S. Если она существует, то заносят начальные значения и выполняют
поиск первой цепочки.)
2.	Последнее звено = ЬНС(длина). Рабочая = корень(последнее звено); I
= ключ(длина) +1.
(Поскольку это не первое обращение, надо начинать поиск с последней
переменной в цепочке.)
3.	Проба следующей вершины = элементфабочая, I). Если проба
следующей вершины = х, то перейти к 5; если проба следующей вершины
= S, то перейти к 6; если связь(проба следующей вершины, S) = истина,
то перейти к шагу 4; иначе 1 = 1+1. Повторить 3.
(Эта внутренняя часть алгоритма ищет продолжения от вершины
рабочая к терминальному символу S, проверяя таблицу подстановок для
вершины рабочая на связь с определенным элементом, шаг 5
обрабатывает случай, когда поиск закончился отказом, шаг 4 - когда
поиск успешный, шаг 6 - когда цепочка завершена.)
4.	ЬНС(длина) = номер(рабочая, I), рабочая = проба следующей
вершины, ключ(длина) = I, длина = дпина+1,1 = 1, перейти к 3.
(Выбранное правило добавляется к цепочке, и алгоритм продолжает
поиск следующей вершины.)
5.	Ключ(длина) = 0, ЬНС(длина) = 0, длина = длина - 1. Если длина не
равна 0, перейти к 2, отказ = истина, выход с отказом.
(Поскольку нельзя продолжить цепочку от последней вершины дерева,
то возвращаются на одно звено и начинают новый поиск продолжения
цепочки; если вернуться невозможно, то считают, что построить
следующую цепочку нельзя.)
6.	ЬНС(длина) = номерфабочая, I), ключ(длина) = I. Выход.
(Сформирована следующая цепочка LHC, процедура выдает ее и
заканчивает работу.)
54
Блок - схема алгоритма расширенной цепочки
55
6.	ГРАММАТИЧЕСКИЙ РАЗБОР СВЕРХУ ВНИЗ
Построение дерева выполняется практически алгоритмом формирования
расширенной цепочки. Выделяют главную процедуру, она хранит
информацию и обращается к этому алгоритму.
6.1.	УПОРЯДОЧЕНИЕ ПОИСКА ЦЕПОЧЕК
Упорядочение сформированных цепочек определяется
последовательностью вершин в скелете. Для строки S1,S2,..,S8 получим
скелет в виде
а
/
а!
/ \
а2 а8
/ \
аЗ аб
/ \
а4 а7
/ \
S1 а5
S2 S3 S4 S5 S6 S7 S8
Каждое Si для 8 > i > 2 принадлежит поддереву, выходящему только из
одной вершины а5, аб, а7, а8.
Отметим, что потомки а5 слева от потомков аб, которые в свою очередь
слева от потомков а7, так как или одна фраза содержит другую
полностью, или они совершенно различны. Поддерево от а5 к строке,
начинающейся с S2, должно быть построено первым. Следующим
строится поддерево от аб к терминальной строке и т.д.
56
Предположим, завершено построение поддерева от а5 к
рассматриваемой строке, причем частично построенное дерево имеет
следующий вид:
/
al
/ \
а2 а8
/ \
аЗ аб
/ \
а4 а7
/ \
S1 а5
/
S2
I
S3 S4 S5 S6 S7 S8
Далее аб связывается с терминальной строкой, начинающейся в S4.
Алгоритм обладает свойством рекурсивности: построение поддерева из
а5 к терминальной строке S2..S8 является повторением исходной задачи
построения дерева из о к S1...S8. Допустим, поддерево из а5 в S2
обладает более сложной структурой.
/ а9 / \	/ а9 Л
S2 аЮ
S2 аЮ
S3
Построение поддерева начинается с генерации скелета, и строится
дерево из аЮ в S3, как показано выше.
57
6.2.	СТРУКТУРА ДАННЫХ
Для работы алгоритма выделяется три области памяти. Стек вход -
используется для терминальных символов входной строки. Стек выдача -
для хранения результата грамматического разбора. Стек корень - для
временного хранения вершин, из которых строятся поддеревья.
Хранить информацию в стеках удобно для реализации рекурсивных
процедур. Временные данные можно хранить и удалять над данными
старых задач. При построении скелета из а в S1 стек корень заполняется
справа и имеет вид:
конец списка
X
а8 а7 аб
а5
вершина
Конец списка здесь обозначается %.
Поддеревья строятся из вершин стека корень по мере их появления на
вершине стека во время обработки. Поскольку дерево а5 должно быть
построено до построения аб, то алгоритм начинает поиск новых
поддеревьев для дерева из а5. Новые вершины запоминаются над
старыми, и стек корень имеет вид:
вершина
% а8 а7 аб аЮ
Допустим, попытка построить дерево закончилась неудачно в середине
грамматического разбора. В этом случае стек корень имеет вид:
X al a2 I ... pi I р2
вершина
Вершины с метками pi - это вершины в поддереве, корнем которого
является aj. Если построить дерево из aj не получилось, то в стеке могут
оказаться некоторые Р, которые необходимо удалить для дальнейшей
нормальной работы алгоритма. Поэтому в стеке корень нужно
определить границу между вершинами последнего построения поддерева
и вершинами, связанными с предыдущей прерванной попыткой. Эта
граница обозначается символом разделителя |-. Кроме того, нужна
граница при разгрузке стека выдача, когда транслятор возвращается из
неудачной попытки построить поддерево. Для этого будет
использоваться другой символ разделителя -|. Смысл разделителя в
том, что записи за ним в стеке выдача относятся к предыдущей
58
левосторонней цепочке. При наличии последнего разделителя алгоритм
отступает дальше по дереву, уничтожая этот скелет и пытаясь построить
новый.
Разделитель -| записывается в стек выдача при нахождении нового
скелета, а разделитель отделяет в стеке корень новые вершины скелета.
Пусть в процессе грамматического разбора получено частично
построенное дерево:
al
/
a2
I \
a3 а5
/ \ /\
S1 а4 S3 аб
/
S2
В этом случае стеки корень и выдача будут иметь вид:
стек корень
вершина
стек выдача
	4	S3	а5	4	S2	а4	4	S1	аЗ	а2	al	
вершина
Далее нужно построить цепочку от аб к S4.
Если такое дерево не существует, то алгоритм возвращается обратно.
Поскольку вершины а5 и а4 могут обладать другой структурой
поддеревьев, то не следует отбрасывать весь скелет с корнем al. Сначала
устраняется предыдущая цепочка S3 - а5, и процессор пытается
построить другую цепочку от а5 к S3.
Предположим, что такой цепочки тоже нет. Алгоритм отходит снова и
устраняет очередную цепочку из стека выдача.
Теперь структура данных имеет вид:
59
стек корень вершина
аб а5 а4
стек выдача
-| S1 аЗ а2 а1
Предположим, что больше нет цепочки от а4 к S2. Алгоритм опять
делает отход и обнаруживает , что пройдены все вершины с корнем al.
Об этом свидетельствует символ разделителя -|, который находится на
вершине стека выдача, при этом все содержимое стека корень до символа
разделителя р должно быть исключено. Затем исключается следующая
цепочка в стеке выдача, а корень al заносится в стек корень для поиска
еще одной левосторонней цепочки .
6.3.	АЛГОРИТМ РАЗБОРА СВЕРХУ ВНИЗ
Блок-схема алгоритма состоит из трех частей.
В первой части ищется следующий корень, который должен быть связан
со следующим входным символом поддерева. Вершины запоминаются в
стеке корень. Если символ на вершине стека корень является
терминальным, он сравнивается с символом стека вход, и если совпадает
с ним, то посылается в стек выдача, если нет, то вызывается программа
"Отход". Эта программа организует возврат при неудачной попытке.
Во второй части выполняется обращение к программе поиска
следующей (расширенной) цепочки, проверяется результат и, в
зависимости от результата, либо выполняется обращение к программе
отход, либо выдается полученная левосторонняя цепочка.
В третьей части проверяется завершенность работы, и если стек корень и
стек вход пусты оба, то работа программы завершена. Если только один
пуст, то построенное дерево некорректно и выполняется отход.
60
1-я часть алгоритма
Присвоить начальные
значен. стекам Ввод н
Корень
Выбирать из стека
Корень до а
ввода
61
2-я часть алгоритма
Алгоритм "Выдать результаты" строит левостороннюю цепочку вместе
с соответствующими данными в стеке выдача. Если имеются вершины
скелета цепочки, не связанные со входной строкой, то они записываются
в стек корень. При этом вершины скелета связаны со входной строкой в
порядке от нижней правосторонней цепочки вверх и от самого левого
символа в каждой цепочке направо. Поскольку стек корень является
структурой данных типа "последним пришел первым ушел", то вершины
скелета записывают начиная с верхней правосторонней цепочки вниз,
справа налево.
Программа "Отход" распаковывает стек выдача в поиске последней
левосторонней цепочки, которую она может удалить из стека. Она
встречается с одной из трех возможных ситуаций:
62
1.	Терминальный символ, являющийся поддеревом из некоторой
вершины - он не может иметь другого дерева (сам является своим
поддеревом). Программа "Отход" игнорирует его и продолжает работу.
2.	Наличие символа }- означает, что следующая последовательность
должна быть левосторонней цепочкой, либо поддеревом, либо .
3.	Левосторонняя цепочка от переменного символа к
терминальному, заканчивающаяся символом -|. Программа
возвращается обратно по стеку выдача до тех пор, пока не обнаружит
СИМВОЛ 4.
6.4.	НЕОДНОЗНАЧНОСТЬ РЕЗУЛЬТАТА
Пусть дерево трансляции имеет вид :
ст
/
al
/ \
а2 а4
/ / \
а2 S5 а5
/ \	/ \
S1 аЗ	аб S8
\ / \ / \
S2 S3 S4 S6 а7
/
S7
Обход сверху этого дерева трансляции, с выделением левосторонних
цепочек чёрточками, имеет вид:
ста 1 a2S 1 /S2/a3S3/S4/a4S5/a5a6S6/a7S7/S8
Вертикальные черточки делят эту строку на последовательность
левосторонних цепочек, оканчивающихся терминальным символом. Это
разбиение соответствует работе транслирующей программы (если
порядок левосторонних цепочек изменить на обратный). Следовательно,
результат работы программы грамматического разбора сверху вниз
также является обходом сверху дерева трансляции.
63
Однако этот обход неоднозначен. Одна и та же строка может
представлять обход сверху различных деревьев. Обход дерева:
oala2SlS2
/
al
/
/
z / \
SI S2
/
al
/ \
a2 S2
/
SI
Здесь расположение терминального символа S2 однозначно определить
нельзя. Конец левосторонней цепочки можно определить по
терминальному символу, у которого не может быть потомков. Однако у
правосторонних цепочек таких характерных символов нет. Поэтому
введем специальный ограничивающий символ для правосторонней
цепочки и обозначим его Q. Теперь, предполагая, что Q не принадлежит
ни множеству терминальных, ни множеству переменных символов (то
есть это новый символ), мы можем связать его с концом правой строки
(аргументом) правила подстановки.
Деревья из приведенного выше примера преобразуются к виду:
ст
/
al
/ \
a2 S2
/ \ \
si a q
\
/
al
/ \
а2 Q
/\
SI S2
\ \
Q Q
64
Обходы этих деревьев имеют вид :
aala2SlQS2QQ
oala2SlQQS2Q
После исключения неоднозначности можно восстанавливать дерево
трансляции по стеку выдача, поскольку этот стек содержит всю
информацию о дереве.
7.	ГРАММАТИЧЕСКИЙ РАЗБОР СНИЗУ ВВЕРХ
В грамматическом разборе снизу вверх дерево строится с самых нижних
поддеревьев, которые объединяются в новую подстроку, являющуюся
сентенциальной формой - S.
Результат первого шага при трансляции строки методом снизу вверх
может быть представлен, например, в виде дерева, изображенного ниже:
a
/|\
SI S2 S3 S4 S5 ...Sn
Теперь новая строка, подаваемая на вход транслятора, образуется из
старой заменой S3 S4 S5 на корень правила а:
SlS2aS6...Sn
7.1.	ПОИСК ОСНОВ
Ранее была определена основа сентенциальной формы как самая левая
простая фраза формы, где простая фраза - это фраза, не содержащая
других фраз. Все символы в простой фразе исходят из одной вершины.
Алгоритм грамматического разбора снизу вверх, подобно разбору
сверху вниз, читает каждый раз слева направо по одному символу
входной строки. Таким образом, если алгоритм настроен на поиск
простой фразы, то фраза, которую он находит, будет кандидатом в
основы. Как и в грамматическом разборе сверху вниз, здесь
порождаются потенциальные левосторонние цепочки и находятся
потенциальные основы.
При движении по входной строке на каждом шаге алгоритм пытается
найти основу, оканчивающуюся в данном месте. Ниже этот процесс
изображен графически.
65
Пример:
а2
/ I \
SI S2S3 S4S5 S6 S7 S8
\ \ | / Т - указатель
а1 ввода
Здесь процессор выбрал из входной строки символ S5. Возможны две
подстроки, оканчивающиеся в S5: одна подстрока соответствует правилу
подстановки al-»S2 S3 S4 S5 : il, а вторая - правилу a2-*S3 S4 S5 :i2.
Следовательно, либо слева от S5 фраза не существует, либо она уже
опробована и отброшена. Далее необходимо выполнить анализ фраз.
Алгоритм анализа содержит две процедуры: подстановки и отхода.
Предположим, что первым выбрано правило il по его порядковому
номеру. Используется подстановка вместо аргумента этого правила его
корня, выдается полученное дерево и строка принимает вид:
SI al S6 S7 S8.
Указатель ввода пока еще находится на символе S5. Если нет простой
фразы, оканчивающейся на al или на любом символе справа от него , то
алгоритму нужно выполнить отход и восстановить предыдущую фразу.
Поскольку дальнейших подстановок слева от предыдущей сделано быть
не может, то самая последняя подстановка должна быть представлена
самым правым переменным символом в частично сведенной входной
строке. Номер подстановки должен храниться в выходном списке или
вместе с переменным символом во входной строке для нахождения
следующей возможной фразы.
7.2.	ПРИМЕР ГРАММАТИЧЕСКОГО РАЗБОРА СНИЗУ ВВЕРХ
Рассмотрим простой пример отхода в грамматическом разборе снизу
вверх. Пусть имеется элементарное множество подстановок:
П= {<арифметическое выражение>-> А + <первичное>:1
<первичное>—>А	:2
<первичное>—>А * <первичное>: 3}
66
Входное предложение этого языка задано в виде:
S=A+A*A
Дерево трансляции для данного выражения S имеет вид:
< арифметическое выражение>
/ I \
А + <первичное>
/ I \
А * <первичное>
А
Шаги отхода обозначим символом В , а основу , анализируемую на
предыдущем шаге, будем подчеркивать. Основой дерева является самая
правая буква А, но первой возможной основой будет первая
появляющаяся слева буква А.
Вначале грамматического разбора снизу вверх предполагается, что
новая сентенциальная форма в канонической последовательности
подстановок будет иметь вид: <первичное> + А ♦ А. Два другие символа
А далее также будут преобразованы в <первичное>.
Процесс разбора как последовательность сентенциальных форм имеет
вид:
1.	А+А*А
2.	<первичное>+ А * А
3.	<первичное> + <первичное> * А
4.	<первичное> + <первичное> ♦ <первичное>
Возможности обнаружения простых фраз нет , нужен отход.
Восстанавливается предыдущая строка.
5.	<первичное>+<первичное> * А (В)
В новой строке других основ нет, поэтому опять отход.
6.	<первичное> + А ♦ А	(В)
7.	<первичное> + А * <первичное>
8.	<первичное> + <первичное>
9.	<первичное>+А * <первичное> (В)
10.	<первичное> + А ♦ А	(В)
67
П.А+А*А	(В)
12.	A+ <первичное> * А
13.	А+ <первичное> * <первичное>
14.	А+ <первичное>* А	(В)
15А+А*А	(В)
(В)
16.	А+ А * <первичное>
17.	А+ <первичное>
18.	<арифметическое выражение>
7.3.	СТРУКТУРЫ ДАННЫХ
Во время работы алгоритма трансляции оперативные данные хранятся в
трех стеках: один - для ввода, другой - для вывода и третий - для
временного хранения данных. Соответственно они называются стеками
ввод, выдача и хранение. Взаимосвязи этих стеков можно
проиллюстрировать графически, как показано ниже.
Символы выбираются по одному из стека ввод и передаются в стек
хранение. Блок сравнения проверяет, не содержит ли правая часть стека
хранение возможной простой фразы. При обнаружении возможной
основы эта основа передается в стек выдача.
Каждый из этих списков обладает своей структурой. Простейший из них
список ввод. Это обычная строка терминальных символов,
рассматриваемая как стек, вершина которого находится в начале строки.
стек хранение ----- /-----а стек выдача
блок сравнения
стек ввод
При выборе элементов из стека ввод происходит чтение входной строки
слева направо. При обнаружении возможной основы и записи ее корня
вместо нее в стеке хранение, программе нужно записать вместе с
переменным символом и номер правила подстановки. Причем, если для
этого корня возникнет необходимость отхода, поисковая программа
будет знать, откуда начать поиск. Следовательно, в стеке хранение для
каждой записи имеются два элемента. Если символ .терминальный, то
второй элемент равен 0; если он переменный, то второй элемент является
68
номером правила подстановки, используемого для его получения. Итак,
стек хранение может выглядеть, например, так:
символ
в	1	а	А	
0	11	12	0	
индекс
При отходе последняя простая фраза выбирается из стека выдача и
засылается обратно в стек хранение. Структура стека выдача должна
быть такова, чтобы в нем могли содержаться все данные из стека
хранение, и поэтому запись бывает, как правило, двойного размера. Как
в грамматическом разборе сверху вниз, алгоритм снизу верх должен
иметь возможность отличать в стеке выдача последовательные фразы
друг от друга. Поэтому снова вводится дополнительный символ -|,
разделяющий фразы.
7.4.	АЛГОРИТМ РАЗБОРА СНИЗУ ВВЕРХ
В начале работы алгоритма вся входная строка целиком хранится в стеке
ввод. Два других стека - хранение и выдача - пусты. При успешном
завершении грамматического разбора стек ввод пуст, стек выдача
содержит последовательность символьных строк, разделенных знаками
, а в стеке хранение записана переменная предложения ст, так как к ней
сводится вся строка в грамматическом разборе снизу вверх.
вершина
|S1 |S2 |... |Sn |Л
стек ввод
вершина
ы
стек выдача
вершина
ixrzz:
стек хранение
69
Если грамматический разбор завершается успешно, то стек ввод
полностью освобождается. При этом стек выдача будет содержать
строки, разделённые знаками , а стек хранение - переменную о
вершина
стек ввод
вершина
а	S1	-1	...	X,
12	0			_х
X	ст
	11
стек выдача
вершина
стек хранения
Работа алгоритма может завершиться неудачей. Это произойдет в том
случае, когда стек хранение пуст, а алгоритм отхода ищет в нем
переменную. Однако поскольку стек хранение пуст, стек выдача также
должен быть пуст, а стек ввод вновь должен содержать целое
предложение (конфигурация возвращается в начальное состояние).
Блок-схема алгоритма грамматического разбора снизу вверх
представлена ниже.
70
Блок-схема алгоритма грамматического разбора снизу вверх
Неформальное описание алгоритма снизу вверх
1.	Если стек ввод пуст, то перейти к 4; иначе выбрать из ввод в стек
хранение, номер=0;
(Выбирается очередной входной символ)
2.	Искать правило подстановки с номером большим, чем номер, у
которого аргумент совпадает с верхней подстрокой в стеке хранение.
Если такого правила не существует, то перейти к 1;
(Поиск основы)
3.	Из стека хранение в стек выдача передать совпавшую подстроку,
поместить корень и номер совпавшего правила в стек хранение. Номер =
О, перейти к 2;
(Выдача совпавшей подстроки).
4.	Если стек хранение содержит только о с соответствующим <номером
правила> на вершине, то выход - успех;
71
(Проверка завершенности)
5.	Выбирать из стека хранение в стек ввод до тех пор, пока <переменная>
с соответствующим <номером правила> не окажутся на вершине стека
хранение, если нет, то выход - неудача.
Иначе выбрать из стека хранение, номер = <номер правила>.
Выбирать из стека выдача в стек хранение до тех пор, пока не
обнаружится символ , выбрать из стека выдача, перейти к 2.
(Отход)
7.5.	ВОССТАНОВЛЕНИЕ
Восстановление заключается в преобразовании полученной в результате
разбора информации во входную строку. После завершения
грамматического разбора вся информация о процессе разбора
содержится в стеке выдача. Следовательно, содержимое стека выдача
необходимо преобразовать при восстановлении в первоначальное
предложение. Процесс восстановления может быть осложнён
неоднозначностью выходного результата.
При грамматическом разборе сверху вниз для исключения
неоднозначности вводился дополнительный символ. Для
грамматического разбора снизу вверх эта модификация не обязательна.
В процессе отхода происходит реконструкция предыдущей
сентенциальной формы, так что восстановление является простой
рекурсивной адаптацией отхода.
Неформальное описание алгоритм восстановления
1.	Пусть si будет верхней фразой в стеке выдача.
2.	Пусть si+i будет результатом подстановки следующей фразы в стеке
выдача вместо крайней правой переменной в si.
3.	Если_стек выдача пуст, то последняя из построенных сентенциальных
форм sm является первоначальным входным предложением.
Стек выдача должен читаться снизу вверх, при этом фразы выбираются в
нужном для интерпретатора или компилятора порядке, поскольку
трансляция выполняется в том же порядке снизу вверх.
72
ЛИТЕРАТУРА
1	.Ф. Вайнгартен. Трансляция языков программирования. - М.: Мир,
1977.
2	.Д. Фелдман, Д. Грис. Системы построения трансляторов // Сб.
Алгоритмические языки. Вып. 5. - М.: ВЦ АН СССР ,1971.
3	. Ф.Хопгуд. Методы компиляции. - М.: Мир, 1972.
4	. Толковый словарь по вычислительным системам/ Под ред. В.
Иллингуорта и др.; Пер. с англ. Е.К. Масловского. - М.:
Машиностроение, 1990.
73
ОГЛАВЛЕНИЕ
1	.Естественные и формальные языки.................... 3
1.1	.Анализ естественного языка........................3
1.2.	Искусственные языки. Формальные языки...............5
1.3.	Трансляция..........................................7
1.4.	Структура данных....................................7
1.5.	Основные понятия теории множеств..................8
1.6.	Строки .............................................Ю
1.7.	Графы...............................................И
1.8.	Деревья........................................... 12
1.9.	Обходы деревьев................................... 13
2	.Трансляция арифметических выражений.................14
2.1.	Тройки............................................ 15
2.2.	Ранние (первые) методы.............................16
2.3.	Стековые алгоритмы.................................18
3	.Формальные модели грамматик.........................22
3.1.	Синтаксис и семантика..............................22
3.2.	Терминальные символы и синтаксические переменные. ... 22
3.3.	Синтез строк. . ...................................23
3.4.Определение грамматик...............................25
3.5.	Специальные классы грамматик.......................28
4	.Свойства формальных грамматик.......................31
4.1.	Локализованная структура...........................31
4.2.	Использование свойства локализации. Независимость порядка
правил подстановки. Каноническая форма................33
4.3.	Графическое представление цепочек правил подстановки. . .35
4.4.	Двоичные деревья трансляции....................... 38
4.5.	Свойства двоичного дерева......................... 39
4.6.	Фразы............................................. 42
4.7.	е - свободная грамматика.......................... 43
5	. Структуры двоичных деревьев трансляции............ 45
5.1.	Скелеты............................................45
5.2.	Упорядочение скелетов...........................   46
5.3.	Построение скелета.................................48
5.4.	Расширенный алгоритм цепочек...................... 52
6	. Грамматический разбор сверху вниз. . ............. 56
6.1.	Упорядочение поиска цепочек....................... 56
6.2.	Структура данных...................................58
6.3.	Алгоритм разбора сверху вниз.......................60
6.4.	Неоднозначность результата.........................63
7	. Грамматический разбор снизу вверх................. 65
7.1.	Поиск основ.............................'..........65
7.2.	Пример грамматического разбора снизу вверх.........66
74
7.3.	Структуры данных.................................. 68
7.4.	Алгоритм разбора снизу вверх.......................69
7.5.	Восстановление. ...................................72
Литература............................................. 73
Тем. план 1999, поз. 29
Жигалов Владимир Иванович
Трансляторы САПР РЭУ
Редактор М.С. Винниченко_________________________
Подписано в печать 14.03.2000.
Бум. газетная. Формат 60x84 1/16. Печать офсетная.
Усл. печ. л. 4,42. Уч.-изд.л. 4,5. Тираж 150.
Зак. 2059/1346. С. 11.___________________________
Типография издательства МАИ
125871, Москва, Волоколамское шоссе, 4