ш0
2Упражнение. 0Предложите варианты диагностики возможных
ошибок во входной цепочке при использовании таблицы предшест-
вования.
29. ГЛОБАЛЬНЫЙ АНАЛИЗАТОР
Глобальный анализатор, известный также под названием ана-
лизатора Унгера [2], реализует нисходящий метод синтаксическо-
го анализа. Этот метод относится к числу рекурсивных методов,
и поэтому может быть причислен к множеству методов, объединен-
ных названием "методы рекурсивного спуска".
.
- 61 -
Преимущества метода Унгера заключаются в следующем:
- достаточно простой алгоритм анализа;
- наличие непосредственной связи между алгоритмом анализа
и грамматикой, что способствует повышению надежности програм-
мирования анализатора;
- глобальный характер метода позволяет включать в анали-
затор элементы генерации объектного кода, так как в каждый мо-
мент известно правило вывода, по которому производится разбор,
хотя компоненты этого правила еще не до конца разобраны.
Вообще говоря, метод Унгера не является детерминирован-
ным. Тем не менее, как и в случае LL - и LR-анализаторов, а
также анализатора предшествования, можно сформулировать опре-
деленные ограничения, накладываемые на исходную грамматику,
при выполнении которых анализ будет выполняться без возвратов.
На этих ограничениях мы останавливаться не будем.
Перейдем к описанию основной идеи метода.
Пусть имеется некоторая КС-грамматика с начальным симво-
лом I. Основу анализатора составляет рекурсивная функция
MATCH(N, x), где N - некоторый нетерминальный символ, а x -
терминальная цепочка. Функция MATCH возвращает значение true,
если в грамматике возможен вывод: N=>x, в противном случае
функция возвращает значение false.
Проверка выводимости N=>x начинается с выбора одного из
имеющихся правил вывода для нетерминала N. Пусть выбрано неко-
торое правило вида: N-> x1 N1 x2 N2 ... xt. Если цепочка x не
может быть представлена в виде x=x1 z1 x2 z2 ... xt, то выби-
рается следующее правило. Если более правил нет, функция фор-
мирует отрицательный результат. Если же сопоставление найдено,
то результат определяется выводимостью: N1=>z1, N2=>z2, ... ,
N(t-1)=>x(t-1). Для этого рекурсивно вызываются функции MATCH
с соответствующими параметрами.
Если хотя бы одна функция возвращает результат false, то
проверяется следующий вариант разбиения. И так продолжается
для всех оставшихся разбиений и правил вывода.
Таким образом, для того, чтобы убедиться в принадлежности
цепочки x языку с начальным символом I, необходимо вызвать
булевскую функцию MATCH(I, x).
Для ускорения работы анализатора применяются так называе-
мые ускоряющие тесты. Перечислим некоторые из них.
- 62 -
2Тест "на длину". 0 Прежде чем проверять выводимость цепоч-
ки, следует убедиться, что эта цепочка не имеет длину больше
или меньше, чем длины цепочек, выводимых из рассматриваемого
нетерминала.
2Тест "на начало". 0 Прежде чем проверять выводимость цепоч-
ки, следует убедиться, что эта цепочка имеет начальный символ,
принадлежащий множеству начальных символов для цепочек, выво-
димых из рассматриваемого нетерминала.
2Тест "на конец". 0 Прежде чем проверять выводимость цепоч-
ки, следует убедиться, что эта цепочка имеет конечный символ,
принадлежащий множеству конечных символов для цепочек, выводи-
мых из рассматриваемого нетерминала.
2Тест "на середину". 0 Прежде чем проверять выводимость це-
почки, следует убедиться, что эта цепочка не имеет внутренних
символов, недопустимых для цепочек, выводимых из рассматривае-
мого нетерминала.
2Тест "на скобки". 0Если для грамматики выделено подмно-
жество терминальных символов, называемых скобочными и правые
части всех правил вывода имеют правильную скобочную структуру,
то применим следующий тест: прежде чем проверять выводимость
цепочки, следует убедиться, что эта цепочка имеет правильную
скобочную структуру.
2Упражнение. 0Для проверки перечисленных тестов требуется
выполнить подготовительную работу по анализу грамматики:
1) опишите процедуры формирования множеств начальных, ко-
нечных и внутренних символов для нетерминалов грамматики. Эти
множества называются PRE(N), POST(N), ALPHA(N);
2) опишите процедуру определения минимальной и максималь-
ной длин цепочек, выводимых для заданного нетерминала грамма-
тики (обратите внимание: может оказаться, что из нетерминала
могут выводиться цепочки любой длины, то есть максимальная
длина цепочки будет тогда равна бесконечности).
.
- 63 -
210. ОБРАБОТКА ОШИБОК
210.1. Синтаксические ошибки
До сих пор мы рассматривали действия анализатора лишь по
установлению соответствия или несоответствия входной цепочки
данному языку. В качестве побочного эффекта определялась
структура предложения. Если встречалась недопустимая конструк-
ция, то анализатор прекращал работу. На практике встречается
такое, но, пожалуй, это не лучший выход из положения. Кроме
того, мы не затрагивали вопросы диагностирования ошибок. А что
же более всего нас устроило бы в ошибочной ситуации? Вот неко-
торые желательные качества транслятора:
- наиболее полная и точная диагностика по обнаруженной
ошибке,
- по возможности полное перечисление всех допущенных оши-
бок,
- минимальное количество "наведенных" ошибок.
Анализатор в ошибочной ситуации, чтобы продолжить разбор,
должен "понять", что же имел в виду автор неправильной прог-
раммы. Решить эту задачу в полном объеме практически невозмож-
но. Здесь же мы сформулируем лишь некоторые рекомендации [3]:
21 0) входной язык должен быть достаточно простым, чтобы эф-
фективно решать задачу восстановления в ошибочной ситуации.
(Примеры упрощения языка: введение специальных служебных слов,
добавление всевозможных сбалансированных скобочных символов,
полная спецификация всех об"ектов, запрещение принципа умолча-
ния);
22 0) процедура анализа, обнаружившая ошибку, не должна
прекращать работу. Она должна продолжить чтение входной цепоч-
ки до момента, возможного для продолжения анализа. У классиков
это требование звучит так: "Не поднимай панику!". Однако, для
диалоговых трансляторов целесообразно сразу сообщать об обна-
руженной ошибке.
Если язык уже определен, то остается сделать упор на реа-
лизацию второй рекомендации. Для этого каждая процедура анали-
за должна располагать множеством внешних символов (ограничите-
лей), и тогда чтение входной цепочки после обнаружения ошибки
можно будет продолжить без синтаксического анализа до ближай-
- 64 -
шего символа из этого множества. Очень часто в роли внешнего
символа выступает точка с запятой.
С другой стороны, ошибка может заключаться именно в про-
пуске этого внешнего символа. Тогда нежелательно пропускать
целиком конструкцию до следующего внешнего символа. Поэтому,
добавим к внешним символам символы, начинающие новые конструк-
ции (такие как: begin, for, if и прочее). Эти символы называ-
ются символами возобновления. Ниже приводится процедура Test,
сообщающая об ошибке с номером n и продолжающая поиск внешнего
символа (s1) или символа возобновления (s2).
procedure Test (s1, s2 : symset; n : integer);
begin
if not(sym in s1) then
begin
Error(n);
s1:=s1+s2;
while not(sym in s1) do
Getsym
end
end;
Эта процедура должна вызываться всякой процедурой анали-
за, обнаружившей ошибку.
Заметим, что если пропущен какой-либо внешний символ, то
наличие символов возобновления, по существу, позволяет испра-
вить эту ошибку и продолжать анализ как ни в чем не бывало.
Ниже приведен пример фрагмента процедуры анализа составного
оператора (см. анализатор языка PL/0).
. . .
if sym=begisym then
begin
Getsym;
Statement([semicolon, endsym]+fsys);
{ здесь fsys - используемый формальный параметр процедуры ана-
лиза составного оператора. }
{ Процедура Statement при обнаружении ошибки через Test найдет
или внешний символ, или символ возобновления }
- 65 -
while sym in [semicolon]+statbegsys do
{ пока ";" или начало оператора }
begin
if sym=semicolon
then Getsym
else Error('отсутствует...');
statement([semicolon, endsym]+fsys)
end;
if sym=endsym then Getsym
else Error('требуется ...');
end
Конечно, все варианты предусмотреть невозможно, однако,
хороший транслятор должен обладать следующими свойствами:
1) никакая цепочка не должна приводить к катастрофе;
2) все конструкции, которые по определению языка являются
незаконными, должны обнаруживаться и отмечаться;
3) ошибки должны правильно диагностироваться и не должны
приводить, по возможности, к наведенным ошибкам;
4) предлагаемые транслятором действия по устранению оши-
бок должны носить характер рекомендаций и не должны порождать
новых ошибок, если следовать этим рекомендациям.
210.2. Контекстные ошибки
Обычно, языки программирования описываются КС - граммати-
ками, но, как известно, этого недостаточно. Как быть с кон-
текстными свойствами языка? Здесь возможны два пути: усложне-
ние формального аппарата описания языка или написание конкрет-
ных контекстных проверок в данном трансляторе. Что касается
первого пути, то здесь следует отметить атрибутные грамматики
[9,11], позволяющие описывать большинство контекстных условий.
В нашей стране, в частности, велись работы в этом направлении
в Москве (проект системы построения трансляторов СУПЕР - син-
таксически-управляемый перевод).
Второй путь достаточно хорошо проработан и заключается в
создании и контроле всевозможных таблиц.
.
- 66 -
Например, для контроля единственности описаний переменных
величин используется таблица идентификаторов. Если реализуемый
язык имеет блочную структуру, то и помещаемый в таблицу иден-
тификатор, помечается значением уровня блока. Иногда необходи-
мые проверки включаются в грамматику. Получающиеся грамматики
называются атрибутными, но здесь мы их не рассматриваем.
2Упражнение. 0 Сформулируйте необходимые проверки для конт-
роля единственности и обязательности описания всех величин.
Отметим, что некоторые из контекстных условий могут быть
проверены уже на стадии лексического анализа.
211. ГЕНЕРАЦИЯ КОДА
Излагаемый в данной главе материал взят из уже цитирован-
ной работы Вирта [13], а также представляет собой скромный
вклад автора [14-16].
Как уже отмечалось, процесс компиляции можно разбить на
несколько этапов. После того, как программа проанализирована,
сформированы необходимые служебные таблицы, определена син-
таксическая структура, компилятор должен перейти к построению
объектного кода. Чтобы не ориентироваться на какой-то конкрет-
ный машинный язык, проиллюстрируем процесс генерации на приме-
ре некоторого условного языка. В качестве такого языка возьмем
промежуточный язык Вирта известный под названием Р-кода [13].
В данной работе [13] Р-код применяется как выходной язык
транслятора. Входным языком является подмножество языка
Паскаль. Это подмножество получило название Паскаль-S. По
сравнению с полным Паскалем в этом подмножестве отсутствуют
записи с вариантами, оператор присоединения и оператор перехо-
да. На рисунке 15 приведена соответствующая Т-схема.
ш1
┌───────────────────────────────┐
│ Паскаль-S Р-код │
└──────────┐ ┌──────────┘
│ Паскаль │
└─────────┘
Рис. 15. Схема трансляции языка Паскаль-S
ш0
Нам интересна эта реализация, так как ее принципы можно
рассмотреть в рамках учебного пособия. В то же время вырази-
- 67 -
тельная мощность Р-кода позволяет использовать его после неко-
торого расширения в качестве выходного языка для многих импе-
ративных языков.
Идея расширения кода интересна и сама по себе. Представим
себе, что у нас имеется программа интерпретатора. Пусть неко-
торый новый язык отличается, скажем, управляющими операторами.
Тогда можно попытаться дополнить наш Р-код новыми командами,
удобными для предствления этих операторов. Обычно в этом слу-
чае изменения интерпретирующей машины могут быть незначитель-
ны, а этап генерации существенно упрощается, так как команды
объектного языка оказываются приближенными к операторам вход-
ного языка. Вряд ли Р-код может претендовать на роль уни-
версального объектного языка, но трансляция на него императив-
ных языков вполне возможна. В специальной литературе печата-
лись исследования по применению Р-кода для трансляции таких
языков как Фортран и Алгол-60.
Ниже представлен интерпретатор Р-кода, кратко описаны ко-
манды и приведены примеры синтаксического разбора отдельных
конструкций и генерации соответствующих команд. Структура слу-
жебных таблиц подробно не рассматривается, но в необходимых
случаях имеются ссылки на извлекаемую из этих таблиц информа-
цию.
211.1. Интерпретатор Р-кода
Программа на Р-коде представляется в виде последователь-
ности команд. Каждая команда содержит код операции и, возмож-
но, один или два операнда. Некоторые команды не используют
операндов. Такая программа подается на вход специальной маши-
ны, которую мы будем представлять в виде интерпретатора.
Вместе с программой интерпретатор будет получать таблицы
идентификаторов, блоков, структур, массивов, констант и неко-
торую иную информацию. В процессе работы интерпретатор создает
и использует стек (назовем его - S) и специальный массив
(DISPLAY). Условимся, что переменная Т всегда указывает на
последний занятый элемент стека. В одном элементе стека может
быть размещено значение целого, вещественного, символьного или
логического типа.
.
- 68 -
Под каждый активный блок (процедуру) в стеке будет отво-
диться своя секция, начинающаяся с так называемого маркера
секции. Маркер занимает пять элементов стека. Переменная В
указывает на начало последней секции в стеке. Пять элементов
маркера используются следующим образом:
- S[B] - здесь размещается результат (значение) функции,
если блок является функцией;
- S[B+1] - адрес возврата (номер команды Р-кода);
- S[B+2] - статическое звено - указывает на секцию в сте-
ке, соответствующую блоку, содержащему описание данной проце-
дуры;
- S[B+3] - динамическое звено - содержит ссылку на преды-
дущую секцию стека;
- S[B+4] - ссылка на часть таблицы идентификаторов, соот-
ветствующих данной процедуре.
Кроме маркера в секции стека размещаются значения локаль-
ных переменных данного блока.
Покажем на примере, как выглядят статическая и динами-
ческая цепочки. Пусть исходная программа написана на языке
Паскаль и ее структура такова:
Program M;
. . .
Procedure A;
Procedure B;
var X:integer;
begin
. . .
C;
. . .
end; { B }
Procedure C;
var X:integer;
begin
. . .
end; { C }
begin
. . .
B;
- 69 -
. . .
end; { A }
begin
. . .
A;
. . .
end.
Каждому идентификатору сопоставим уровень, на котором он
описан. Уровни идентификаторов вычисляются на этапе синтакси-
ческого анализа и хранятся в таблице идентификаторов. В нашем
примере идентификатор A описан на уровне 1, а идентификатор B
- на уровне 2. И в процедуре B, и в процедуре C описан иденти-
фикатор X, ему будет сопоставлен уровень 3.
Первоначально в стеке будет только одна секция - секция
блока М. При исполнении вызова процедуры A в стеке будет выде-
лена секция A, а при вызове процедуры В добавится секция В. На
рис. 16 изображен стек к этому моменту. В данном случае дина-
мическая и статическая цепочки совпадают. Многоточием на
рисунке обозначены элементы стека, используемые для размещения
переменных соответствующих секций и хранения промежуточных
значений вычисляемых выражений.
ш1
┌──────────────────┐ - динамическая цепочка
│ ┌───┼──────────────┐
├──────────────┼───┴──────────┬───┴──────────┬───────────────
│ секция M │ секция A │ секция B │ продолжение
├──────┬───────┼──────┬───────┼──────┬───────┤
│маркер│ .... │маркер│ .... │маркер│ .... │ стека S
├──────┴───────┼──┬───┴───────┴──┬───┴───────┴───────────────
│ └──┼──────────────┘
└─────────────────┘ - статическая цепочка
ш0
Рис. 16. Динамическая и статическая цепочки (до вызова С)
Таким образом, в стеке в любой момент времени размещены
секции, соответствующие активным блокам. Однако, не все из них
могут быть доступны. Для удобства реализации интерпретатора
формируется массив DISPLAY. В i-ый элемент этого массива за-
писывается адрес секции, соответствующей доступному блоку
уровня i. В момент активизации процедуры В массив DISPLAY име-
ет вид: DISPLAY[1] - адрес секции М, DISPLAY[2] - адрес секции
A, DISPLAY[3] - адрес секции B.
- 70 -
Таким образом, через базовое значение DISPLAY[3] и смеще-
ние внутри секции доступно значение переменной X процедуры B
(смещение для каждой переменной хранится в таблице идентифика-
торов).
На рисунке 17 показан стек после вызова процедуры С, ко-
торая как и процедура В, находится на уровне 3. Массив DISPLAY
при этом изменится следующим образом: DISPLAY[1] - адрес сек-
ции М, DISPLAY[2] - адрес секции A, DISPLAY[3] - адрес секции
С.
ш1
┌───────────────┐
│ ┌───┼───────────┐ - динамическая цепочка
│ │ │ ┌───┼───────────┐
├───────────┼───┴───────┼───┴───────┬───┴───────┬────────────
│ секция M │ секция A │ секция B │ секция С │ продолжение
├──────┬────┼──────┬────┼──────┬────┼──────┬────┤
│маркер│... │маркер│... │маркер│... │маркер│... │ стека S
├──────┴────┼──┬───┴────┴──┬───┴────┴──┬───┴────┴────────────
│ ├──┼───────────┘ │
│ └──┼───────────────────────┘
└──────────────┘ - статическая цепочка
ш0
Рис. 17. Динамическая и статическая цепочки (после вызова С)
Хотя на уровне 3 и находятся сейчас две процедуры, одна-
ко, благодаря массиву DISPLAY, путаницы в адресах переменных X
не возникает, так как сейчас через DISPLAY[3] доступна лишь
секция С.
В заключение опишем принципиальную схему работы интерпре-
татора. Здесь и далее РС - счетчик команд, IR - исполняемая
команда, PS - номер состояния интерпретатора, ORDER - массив
команд (объектный код). Среди состояний интерпретатора выделе-
на группа состояний, называемых ошибочными. Например, в оши-
бочное состояние интерпретатор переходит при попытке выполне-
ния деления на 0. Ошибочные состояния одновременно являются и
заключительными. Но не все заключительные состояния являются
ошибочными. Например, интерпретатор перейдет в заключительное
состояние, если размеры стека не позволяют разместить очеред-
ную секцию. При переходе в заключительное состояние интерпре-
татор прекращает работу. Ниже приведен алгоритм основного цик-
ла интерпретатора:
1) инициализация стека и рабочих переменных и массивов;
2) извлечение очередной исполняемой команды
- 71 -
3) исполнение команды IR;
4) если текущее состояние PS является заключительным, то
перейти на пункт 5, иначе перейти на пункт 2;
5) вывод сообщения о результате выполнения программы.
211.2. Описание команд Р-кода
Краткое описание команд Р-кода мы изложим по оригиналу
[13] с одним изменением: коды операций будем задавать мнемони-
ческими обозначениями, а не числовыми значениями. Запись
S[T].I будет означать элемент на вершине стека интерпретируе-
мый как целое значение, S[T].R - как вещественное, S[T].B -
как булевское, S[T].C - как литерное.
2КОМАНДЫ ЗАГРУЗОК. 0Команды загрузок включают в себя: заг-
рузка адреса (обозначение - 2ЗА 0), загрузка значения ( 2ЗЗ 0), заг-
рузка литерала ( 2ЗЛ 0), разгрузка по адресу ( 2РАЗГ 0).
Команды 2ЗА 0и 2ЗЗ 0используют два операнда команды (X и Y).
При выполнении этих команд на вершину стека помещается адрес
(то есть номер элемента стека) или значение. Операнд X играет
роль номера доступной секции в стеке, а Y - смещение от начала
этой секции. Следовательно, адрес самой величины вычисляется
по формуле: DISPLAY[X]+Y.
Команда загрузки литерала использует один операнд Y. По
этой команде интерпретатор размещает на вершине стека значение
операнда Y.
По команде разгрузки содержимое верхнего элемента стека
размещается по адресу, который предварительно записан в
S[T-1].I. После выполнения этой команды значение указателя T
уменьшается на 2.
2КОМАНДЫ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ. 0В Р-коде предусмотрено
одиннадцать команд арифметических операций. Операнды X и Y не
используются. Например, команда 2СЦ 0(Сложение Целых) работает с
величинами, расположенными на вершине стека. Результат помеща-
ется на место первого операнда:
S[T-1].I:=S[T-1].I+S[T].I; T:=T-1.
- 72 -
2КОМАНДЫ СРАВНЕНИЙ И ЛОГИЧЕСКИХ ОПЕРАЦИЙ. 0Эти команды вы-
полняются аналогично предыдущим.
2КОМАНДЫ ПЕРЕХОДОВ. 0По команде 2БП 0(Безусловный Переход)
счетчик команд PC принимает значение второго операнда Y (зна-
чение первого операнда X не анализируется). Для организации
ветвлений предназначена команда условного перехода 2УП 0: если на
вершине стека находится булевское значение FALSE, то счетчик
команд получает значение Y, в противном случае он увеличива-
ется на 1.
2КОМАНДЫ ЦИКЛОВ. 0Выполнение циклов рассмотрим на примере
конструкции:
for <Имя>:=<Выражение1> to <Выражение2> do <Тело>
При трансляции этого цикла будут сгенерированы следующие
команды или их группы (справа приведены комментарии):
2ЗА 0 % Загрузка адреса переменной цикла <Имя>
2Code1 0 % Группа команд для вычисления <Выражение1>
2Code2 0 % Группа команд для вычисления <Выражение2>
2FOR1UP 0 % Проверка необходимости входа в цикл
2Code3 0 % Группа команд тела цикла
2FOR2UP 0 % Увеличение значения переменной цикла
% и проверка перехода на повторение цикла
Исполнение команды FOR1UP заключается в разгрузке значе-
ния <Выражение1> по адресу переменной <Имя> и сравнении значе-
ний <Выражение1> и <Выражение2>. Если первое окажется больше
второго, то программный счетчик PC получает новое значение,
равное аргументу Y:
{ FOR1UP: } H1:=S[T-1].I;
if H1<=S[T].I then S[S[T-2].I].I:=H1
else begin PC:=Y; T:=T-3 end
Ниже приводится интерпретация команды FOR2UP:
{ FOR2UP: } H2:=S[T-2].I; H1:=S[H2].I+1;
if H1<=S[T].I then
begin S[H2].I:=H1; PC:=Y end
else T:=T-3
Похожим образом обрабатываются другие виды циклов.
- 73 -
2ПРОЧИЕ КОМАНДЫ. 0Для работы с процедурами предназначены
команды 2УМ 0(Установить маркер) и 2ВЫЗОВ 0(ВЫЗОВ процедуры). Ин-
терпретатор, выполняя эти команды, формирует маркер секции,
устанавливает новые значения T и PC. Команда 2КП 0(Конец Проце-
дуры) используется при выходе из процедуры, при этом должен
измениться (или точнее, восстановиться) массив DISPLAY;
последнее обеспечивает команда 2ИЗМЕНИТЬ 0. Последняя команда
2КОНЕЦ 0 обозначает переход в заключительное состояние.
В заключение приведем два примера. Используемые ниже про-
цедуры Emit и Emit1 задают генерацию команды с указанным аргу-
ментом кодом. Кроме того, вторая процедура формирует операнд
Y, используя для этого второй аргумент. Напомним, что рекур-
сивные процедуры анализа выражений и операторов получают пара-
метром множество символов возобновления для продолжения разбо-
ра в случае обнаружения ошибочной ситуации.
2Пример 1. 0Разбор конструкции условного оператора с гене-
рацией Р-кода.
Ниже будет использоваться описание:
item = record
typ:types;
ref:index { index=-xmax..+xnax }
end;
Здесь поле typ задает тип переменной, а поле ref - ссылку
в таблицу идентификаторов (назначение поля ref зависит от зна-
чения поля typ и может быть иным).
Procedure Ifstatement;
var PC1, PC2 : integer;
X:item; {поле TYP типа ITEM будет использованo как
признак типа анализируемого выражения}
begin
{ "if" - был уже прочитан, поэтому начинаем разбор с
логического выражения }
Getsym;
{ процедура анализа выражения; первым аргументом заданы
символы возобновления анализа, второй аргумент - тип
выражения}
Expression(FSYS+[THENSY],X);
if not(X. TYP in [BOOLS]) then ERROR { Если тип
- 74 -
результата не булевский, то - ошибка};
PC1:=PC; Emit("УП"); { запоминание текущего значения PC,
и генерация команды
условного перехода пока с еще не
заполненным операндом Y}
if sym=THENSY then Getsym
else Error;{после выражения должен сле-
довать символ "then" }
Statement(FSYM+[ELSESY]);
{ процедура анализа оператора и генерация
соответствующего кода }
if sym=ELSESYM then
begin
Getsym;
{ Запоминание текущего адреса РС,
генерация безусловного перехода для
окончания ветви "then" условного
оператора }
PC2:=PC; Emit("БП");
{ Восстановление ранее пропущенного
операнда в команде условного
перехода }
ORDER[PC1].Y:=PC;
Statement(FSYM);{Анализ оператора}
{ Восстановление операнда }
ORDER[PC2].Y:=PC
end
else ORDER[PC1].Y:=PC
end { Ifstatement }
2Пример 2. 0 Разбор цикла с предусловием, и генерация кода:
Procedure Whilestatement;
var PC1, PC2 : integer;
X:item;
begin
{ "while" - был уже прочитан, поэтому начинаем разбор с
логического выражения }
Getsym;
PC1:=PC; { запоминание текущего значения PC }
- 75 -
Expression(FSYS+[DOSY],X);{ процедура анализа выражения }
if not(X. TYP in [BOOLS])
then ERROR { Если тип результата не булевский,
то - ошибка};
PC2:=PC; Emit("УП"); {запоминание текущего значения PC,
и генерация команды условного
перехода пока с еще не
заполненным операндом Y}
if sym=DOSY then Getsym
else Error;{после выражения должен сле-
довать символ "do" }
Statement(FSYS); {процедура анализа оператора }
Emit1("БП",PC1);
ORDER[PC2].Y:=PC
end { Whilestatement }
Полный текст синтаксического анализатора (включая генера-
цию кода) и интерпретатора для языка ПАСКАЛЬ-S был опубликован
[13]. Отметим, что в [3] приводится подобный анализатор и ин-
терпретатор для языка PL/0 (по сравнению с языком ПАСКАЛЬ-S
язык PL/0 весьма примитивен). Кроме того можно посоветовать
посмотреть полные примеры разработок компиляторов в литературе
[5,12].
2ЗАКЛЮЧЕНИЕ
Мы рассмотрели все основные этапы разработки транслятора,
начиная с описания реализуемого языка и кончая гипотетической
объектной машиной. Безусловно, рамки учебного пособия не поз-
воляют осветить материал в полном объеме. За пределами нашего
курса оказались сложные вопросы оптимизации объектного кода и
методы оптимального распределения памяти под данные и програм-
му. Мы почти не обсуждали, какое влияние оказывает входной
язык на выбор методов реализации; интересна задача определения
числа проходов транслятора и т. д. Для глубокого изучения пред-
мета рекомендуется познакомиться с литературой. И, конечно,
для "полного погружения" в обсуждаемую тему обязательно нужна
самостоятельная работа.
.
- 76 -
2ЛИТЕРАТУРА
1. , Информатика. Вводный курс: В 2-х
ч.: Пер. с нем.-М.:Мир, 1990.
2. Братчиков языков программирования.-
М.:Наука, 1975.
3. Алгоритмы + структуры данных = программы: Пер.
с англ.-М.:Мир, 1985.
4. Конструирование компиляторов для цифровых вы-
числительных машин: Пер. с англ.-М.:Мир, 1975.
5. Разработка Паскаль-компилятора:Учеб. посо-
бие по спецкурсу. - Пермь:Перм. ун-т, 1993.
6. Теоретические осно-
вы проектирования компиляторов.- М.:Мир, 1979.
7. Языки программирования: разработка и реализа-
ция: Пер. с англ.-М.:Мир, 1979.
8. Рейнуорд- Дж. Теория формальных языков. Вводный
курс: Пер. с англ.-М.:Радио и связь, 1988.
9. Семантика языков программирования. Сб. статей,-
М.:Мир, 1980.
10. Теория синтаксического анализа, пе-
ревода и компиляции: Пер. с англ.-М.:Мир, 1978.
11. Проектирование и конструирование компилято-
ров: Пер. с англ.-М.:Финансы и статистика, 1984.
12. Хендрикс Дж. Компилятор Си для микроЭВМ: Пер. с
англ.-М.:Радио и связь, 1989.
13. Wirth N. Pascal S: a subset and its implemantation.-
Berichte des Instituts fur Informatik.- Zuerich, 1975.
14. Пинаев промежуточного языка для многоя-
зыкового транслятора-интерпретатора, ориентированного на обу-
чение языкам программирования/ЛГУ.-Ленинград, 1983-23с.-Деп. в
ВИНИТИ 6.04.83г., N1 828-83.
15. Пинаев многоязыкового диалогового
транслятора, предназначенного для обучения/ЛГУ.- Ленинград,
1983.-23с.-Деп. в ВИНИТИ 2.09.83г., N 5020-83.
16. Пинаев возможности безвозвратного
анализа методом Унгера по заданной грамматике и системе тес-
тов / РАТИ. - Рыбинск, 19с. - Деп. в ВИНИТИ 15.05.84г.,
N 3096-84.
.
- 77 -
2ПРИЛОЖЕНИЕ 1
2Программа LR-анализатора
Program test;
Type
{возможные операции: останов, сдвиг, свертка, ошибка }
operation = (halt, move, curt, err);
symbol = (id, rea, col, en, S,I, D,invalid); { тип символа }
{правило с символом левой части и длиной правой части}
rule = record
lpart:symbol;
l :integer
end;
Var
gram:array[1..4] of rule; { грамматика }
f, fg:boolean;
s1:array[0..100] of symbol;{ стек символов }
s2:array[0..100] of integer;{ стек состояний }
sym, symcopy:symbol;
x, k,p, t,len:integer;
type_op:operation;
tp:string;
procedure Getsym; { чтение очередного символа }
var ch:char;
begin
{если флаг fg=false, то была свертка и чтение не требуется}
if not eoln or not fg
then
begin
if fg then
begin
repeat read(ch); write(ch) until ch<>' ';
case ch of
'a','b','c','d':sym:=id;
',' :sym:=col;
'r' :sym:=rea;
'#' :sym:=en;
- 78 -
else sym:=invalid
end
end
else begin sym:=symcopy; fg:=true end
end
else
sym:=invalid;
symcopy:=sym
end;
{вспомогательная функция для обеспечения вывода символов}
function ps(sym:symbol):string;
begin
case sym of
col:ps:=',';
id:ps:='id';
rea:ps:='real';
en:ps:='#';
D:ps:='Id';
S:ps:='S';
I:ps:='Idlist'
end
end;
{ определение конца цепочки }
function End_of_chain:boolean;
begin
End_of_chain:=eoln
end;
{ задание LR-таблицы (см. пример LR-таблицы в разделе 8.2)}
procedure Op(sym:symbol;p:integer);
begin
if sym=invalid
then
type_op:=err
else
begin
type_op:=err;
if (sym=S) and (p=1) then
begin type_op:=halt; k:=0 end;
if (sym=rea) and (p=1) then
- 79 -
begin type_op:=move; k:=2 end;
if (sym=I) and (p=2) then
begin type_op:=move; k:=5 end;
if (sym=D) and (p=2) then
begin type_op:=move; k:=4 end;
if (sym=id) and (p=2) then
begin type_op:=move; k:=3 end;
if (sym=col) and (p=3) then
begin type_op:=curt; k:=4 end;
if (sym=en) and (p=3) then
begin type_op:=curt; k:=4 end;
if (sym=col) and (p=4) then
begin type_op:=curt; k:=3 end;
if (sym=en) and (p=4) then
begin type_op:=curt; k:=3 end;
if (sym=col) and (p=5) then
begin type_op:=move; k:=6 end;
if (sym=en) and (p=5) then
begin type_op:=curt; k:=1 end;
if (sym=id) and (p=6) then
begin type_op:=move; k:=3 end;
if (sym=D) and (p=6) then
begin type_op:=move; k:=7 end;
if (sym=col) and (p=7) then
begin type_op:=curt; k:=2 end;
if (sym=en) and (p=7) then
begin type_op:=curt; k:=2 end;
end;
case type_op of
halt: tp:='Halt';
move: tp:='Move';
curt: tp:='Curt';
err: tp:='Err'
end
end;
.
- 80 -
begin
{ Задание левых частей правил вывода грамматики
и длин правых частей (см. пример из раздела 8.1)}
gram[1].lpart:=S; gram[1].l:=2 ;
gram[2].lpart:=I; gram[2].l:=3 ;
gram[3].lpart:=I; gram[3].l:=1 ;
gram[4].lpart:=D; gram[4].l:=1 ;
writeln;
fg:=true; f:=true;
p:=1; t:=1;
s2[t-1]:=p; s1[t-1]:=en;
while not (End_of_chain and fg) do
begin
if f then Getsym;
{ вывод служебной таблицы (см. таблицу 5)}
write(' !',p, ps(sym),t,' s1:');
for x:=1 to t-1 do write(ps(s1[x])); write(' s2:');
for x:=1 to t-1 do write(s2[x]);
Op(sym, p); { определение команды }
writeln(' Op:',tp, k);
case type_op of
{ интерпретация команд LR-таблицы }
halt: if End_of_chain and (t=1)
and (sym=S) then
begin writeln('O"k'); fg:=true end
else
begin
writeln('ending expected');
fg:=true;
if not End_of_chain then readln
end;
.
- 81 -
move: begin
s1[t]:=sym; s2[t]:=k; p:=k; t:=t+1; f:=true
end;
curt: begin
fg:=false;
len:=gram[k].l;
t:=t-len;
sym:=gram[k].lpart;
p:=s2[t-1];
f:=false
end;
err : writeln('Error')
end
end
end.
.
- 82 -
2ПРИЛОЖЕНИЕ 2
2Синтаксические диаграммы языка PL/0
ш1
Программа ┌──────┐
────────────┤ блок ├── 2. 0 ──>
└──────┘
Блок
───┬───> const ──┬── имя ── = ─── число ────┐
│ │ │
│ , │
│ │ │
├<───── ; ────┴──────────────────────────┘
│
├────> var ───┬── имя ───┐
│ │ │
│ , │
│ │ │
├────── ; ────┴──────────┘
│
├<───────────────────────── ; ───────────┐
│ │
│ ┌──────┐ │
├─> procedure ─── имя ─── ; ───┤ блок ├──┘
│ └──────┘
│ ┌──────────┐
└─>─┤ оператор ├─────>
└──────────┘
Оператор ┌──────────┐
───┬────> имя ───── := ─────┤ выражение├─────┬──>
│ └──────────┘ │
│ │
├────> call ────── имя ───────────────────┤
│ │
│ ┌──────────┐ │
├────> begin ──┬─┤ оператор ├──┬─ end ────┤
│ │ └──────────┘ │ │
│ └────── ; ──────┘ │
│ │
│ ┌─────────┐ ┌──────────┐ │
├──> if ─┤ условие ├─ then ─┤ оператор ├──┤
│ └─────────┘ └──────────┘ │
│ │
│ ┌─────────┐ ┌──────────┐ │
├─> while ─┤ условие ├─ do ─┤ оператор ├──┤
│ └─────────┘ └──────────┘ │
│ │
└─────────────────────────────────────────┘
.
- 83 -
Условие ┌──────────┐
──┬──────> odd ─────────┤ выражение├───────────────┬─>
│ └──────────┘ │
│ │
│ ┌──────────┐ │
└─┤ выражение├─┬───┬───┬───┬───┬───┐ │
└──────────┘ │ │ │ │ │ │ │
│ │ │ │ │ │ │
V V V V V V │
= <> < > <= >= │
│ │ │ │ │ │ │
│ │ │ │ │ │ ┌──────────┐│
└───┴───┴───┴───┴───┴─┤ выражение├┘
└──────────┘
Выражение ┌── + ──┐ ┌───────────┐
─────────────┬─┼───────┼──┤ слагаемое ├──┬─>
│ └── - ──┘ └───────────┘ │
│ │
│ │
│ │
└───────────────────────────┘
Слагаемое ┌── + ──┐ ┌───────────┐
─────────────┬─┼───────┼──┤ множитель ├──┬─>
│ └── - ──┘ └───────────┘ │
│ │
│ │
│ │
└───────────────────────────┘
Множитель
───┬───────────── имя ─────────────┬───────>
│ │
│ │
│ │
├──────────── число ────────────┤
│ │
│ │
│ ┌──────────┐ │
└── ( ────┤ выражение├──── ) ───┘
└──────────┘
ш0
.
2Учебное издание
2
2ФОРМАЛЬНЫЕ МЕТОДЫ ОПИСАНИЯ ЯЗЫКОВ
2ПРОГРАММИРОВАНИЯ И ПОСТРОЕНИЕ ТРАНСЛЯТОРОВ
2Конспект лекций
Зав. РИО
Гончаренко
Лицензия ЛР N О2О284 от 13.11.91г.
Подписано в печать
Формат 60х84 1/16
Усл. п. л. 4,8 Уч.-изд. л. 5,2
Заказ 52 Тираж Цена договорная
Рыбинская государственная авиационная технологическая академия
Отпечатано в Рыбинской государственной авиационной технологи-
ческой академии
3.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
