close

Вход

Забыли?

вход по аккаунту

?

Prokofieva

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
СИСТЕМНОЕ ПРОГРАММНОЕ
ОБЕСПЕЧЕНИЕ
Методические указания
к выполнению лабораторных работ
Санкт-Петербург
2012
Составитель Т. Л. Прокофьева
Рецензенты: доктор технических наук, профессор Е. Т. Мирончиков;
доктор технических наук, профессор Ф. А. Таубин
В методических указаниях изложены элементы теории грамматик, инструментальные основы, алгоритмические и программные
средства реализации простейшего компилятора. Достаточно подробно рассматриваются на примерах разработка грамматики, основные фазы компиляции.
Методические указания могут быть эффективно использованы
при изучении дисциплины «Системное программное обеспечение»,
а также при выполнении лабораторных, практических и самостоятельных работ студентами технических специальностей вуза.
Редактор А. В. Подчепаева
Верстальщик С. Б. Мацапура
Сдано в набор 18.09.12. Подписано к печати 08.10.12.
Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. 4,3.
Уч.-изд. л. 4,1. Тираж 100 экз. Заказ № 525.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2012
ОБЩИЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ
Целью выполнения данных лабораторных работ является изучение теоретических основ построения модулей транслятора, а
также получение практических навыков разработки системного
программного обеспечения.
Языковым процессором называется программа по обработке
данных, представленных во входном формате на одном из языков.
Программа выполняет роль перекодировки входного формата в некоторый выходной набор данных. Такие программы разрабатываются на основе синтаксически ориентированных методов и в зависимости от входного и выходного формата данных подразделяются
на следующие четыре типа:
компиляторы;
интерпретаторы;
ассемблеры;
препроцессоры.
Компилятор – это такой языковый процессор, в котором входной формат данных – язык высокого уровня, а выходной формат –
объектный код.
На рис. 1. приведены логические связи компиляторов. Сплошными стрелками показана передача управления, пунктирными –
информационные связи.
Охарактеризуем каждый блок в отдельности и при этом определим сопутствующие понятия.
1. На вход компилятору подается программа на некотором исходном языке. Исходное текстовое представление программы не очень
пригодно для работы компилятора, поэтому во время анализа программа прежде всего разбивается на последовательность лексем.
Множество лексем разбивается на непересекающиеся подмножества – лексические классы. Лексемы попадают в один лексический
класс, если они неразличимы с точки зрения синтаксического анализатора. Например, во время синтаксического анализа все идентификаторы можно считать одинаковыми. При этом сканер строит таблицу внутренних представлений идентификаторов и присваивает
каждой лексеме определённый внутренний код. Таким образом, на
выходе имеем программу на некотором внутреннем языке, где каждый токен заменен на соответствующий ему внутренний код.
3
Исходный текст
Лексемная декомпозиция
программы
Сканер
А
Н
А
Л
И
З
1
Диагностика синтаксиса
Нейтрализация ошибок
Синтаксис
2
Семантика
3
С
И
Н
Т
Е
З
Подготовка
к генерации
Генератор
кода
4
5
Декомпозиция на триады,
тетрады, ПОЛИЗ
Удовлетворение внешних
ссылок, обработка макросов
Оптимизация
Объектный код
КОМПИЛЯТОР
Передача управления
Информационные связи
Рис. 1. Логические связи компилятора
Токен (token – лексема) – некоторая программная единица, которая характеризует определённые категории языка. Традиционно
токенами являются идентификаторы, числовые константы, ключевые слова, знаки операций и т. д. В свою очередь токены состоят из литер. Понятие токена широко используется в иностранной
литературе. В отечественных источниках вместо токена употребляют эквивалентное понятие – лексема. Токен, или лексема, в общем
случае является подмножеством множества терминальных символов, строгое определение которых будет приведено ниже.
4
Литера(литерал) – неделимая информационная единица, из которых набирается текст программы, в простом информационном
понятии нформационное терминальное поле на клавиатуре компьютера или компьютерный алфавит ASCII и EBCDIC. Иначе говоря, это знаковые клавиши на клавиатуре терминала, исключая
служебные и функциональные. Токены(лексемы) могут состоять
из одной или более литер, более строгое математическое понятие
этой категории будет приведено ниже.
Выход сканера – определённый внутренний код, который передается определённым объектам программного сегмента. Так, ключевые слова в языке Си имеют один внутренний ключевой код, разделители – другой, числовые константы – третий и так далее. Сканер анализирует лишь алфавит грамматики языка.
2. Синтаксис – синтаксический анализатор проводит анализ
на соответствие программы на входном языке грамматическим
правилам этого языка и совместно с процессором синтаксических
ошибок занимается обработкой несоответствия синтаксиса грамматики, нейтрализацией этих мест в программе и сообщением пользователю на терминал об этих ошибках. Иногда блоки 1 и 2 в компиляторах совмещены, в этом случае синтаксический анализатор
обращается к сканеру как к функции за очередной лексемой.
3. Семантика – семантический анализатор предполагает смысловую обработку, т. е. из семантически правильных конструкций
генерирует промежуточный набор данных, который представлен
в виде триад, тетрад, ПОЛИЗ и др. Промежуточный набор данных
служит для упрощения генерации кода. Как правило, интерпретатор на третьем блоке заканчивает свою работу.
4. Подготовка к генерации кода – все внешние модули, макросы, встроенные и внешние функции объединяются и таким образом
программа из нескольких функций, макросов собирается в единый
программный сегмент.
5. Генератор кода – обрабатывает промежуточный код в набор
объектных кодов, т. е. переводит программный сегмент в объектный код.
Интерпретатор – для него входной формат данных – язык высокого уровня, выходной формат – промежуточный код, или исполнительный код – после обработки одного оператора, выполнение
его, потом обрабатывается следующий оператор и так далее.
Ассемблер – входной формат – команды ассемблера, близкие к
кодам машины. А выходной формат – исполнительный код или машинные команды для загрузчика.
5
Лабораторная работа № 1
РАЗРАБОТКА ГРАММАТИКИ
ЗАДАННОГО ЯЗЫКА
Цель работы: изучение основных понятий теории регулярных
и КС-грамматик; получение практических навыков обобщения набора ситуаций и использования регулярных выражений; ознакомление с назначением и принципами работы лексических анализаторов (сканеров); получение практических навыков построения
сканера на примере заданного исходного языка.
Для выполнения лабораторной работы требуется разработать
грамматику М-языка, пример программы на М-языке находится в
варианте задания.
Краткие теоретические сведения
Нетерминальные символы (нетерминалы) несут смысловое содержание – конструкция, обобщение. Для начала будем обозначать
нетерминалы печатными прописными буквами латинского алфавита и/или заключать в угловые скобки:
<...> – нетерминальный символ;
A,..., Z – нетерминальные символы.
Примеры. F FF, ALFA, <нетерминал>, A1, <Coshy>
От изменения обозначений нетерминальных символов грамматика не изменяется. Нетерминалы являются связующими элементами грамматики и поэтому их обозначение выбирается произвольно автором грамматики так, чтобы смысловая нотация грамматики
была предметно понятна и легко читается. Так, если разрабатывается грамматика числовой константы, то понятно, что одним из
нетерминальных символов в этой грамматике будет нетерминал
<числовая константа>, который можно обозначить и сокращённо
<ЧК> или просто ЧК, но при этом сокращения читаются хуже и
осложняют понимание грамматики, так как в принятых соглашениях ЧК можно прочитать как два нетерминала.
Терминальные символы (терминалы) могут состоять из одного
и более символов и являются субъектами (буквами) языка. Обозначаются терминалы строчными буквами латинского алфавита или
клавиатурными аббревиатурами:
a,..., z – формальные обозначения терминальных символов;
Примеры: а, =, ** – знак возведения в степень в языке FORTRAN,
6
If, WHILE, DO и т. д. – группа кючевых слов.
Редукция – правило вывода
<a> -> <b> – из нетерминала а следует нетерминал b,
(-> эквивалентно:: = ).
Операция или – |
а | b – терминал a или терминал b.
Пусто – L операция для организации механизма умолчания и
других.
В дальнейшем также вместе с символом L будем использовать
часто употребляемый в литературе сивол µ.
Псевдооперация умолчания – […]
[a] – по определению есть a | L
обозначает, что а может быть, а может и не быть.
Итерация – {…}
{a} – по определению есть a | aa |... | a...a |L
означает, что a может встречаться в цепочке символов 1,2,...n
(n’) число раз, либо вообще не встречаться.
{a}k – аналогично, но n не превышает значение k (n< = k).
Если {} или [] являются элементами алфавита какого-то языка,
то чтобы отличить конструкцию от алфавита, скобки подчёркивают.
Соглашения:
Б – A|B|...|Z, a|b|...|z – это буквы, которые являются терминальным символом из словаря латинского алфавита. Вместе с русской
аббревиатурой Б для обозначения класса букв договоримся также
использовать латинскую аббревиатуру LT (LetTer).
Ц – 0|1|...|9 – это терминальный символ цифрового регистра.
Здесь также договоримся употреблять латинское обозначение для
класса цифр – DT (DigiT).
<идентификатор> – это ещё одна из часто употребляемых конструкций. Договоримся обозначать эту конструкцию(токен) русской аббревиатурой ИД или латинской – id.
Словарь (алфавит) – конечное непустое множество символов.
Словарь обозначается заглавными прописными буквами латинского алфавита, чаще – V и S (возможно с индексами).
Термин «алфавит» как класс или группа символов введён для
обозначения, например, букв русского [А,Б, … Я] или латинского
[A,B, … Z] алфавитов соответственно как прописных так и строчных. В теории формальных языков эта категория приняла лишь
более строгую и конкретную форму.
Пример. A = {a, b}, словарь А состоит из двух терминалов a, b.
7
B = {0,1} – бинарный словарь.
ASCII и EBCDIC – являются примерами компьютерных алфавитов.
Отметим, что словарь в теории формальных грамматик необязательно должен состоять только из терминальных символов.
В общем случае, как будет показано ниже, общий словарь V может
включать множество терминальных символов – Vt вместе с множеством нетерминальных – Vn. Причем Vt и Vn – непересекающиеся
множества.
Цепочки (строки) – конечная последовательность элементов
словаря. Обозначаются строки греческими прописными буквами –
α, β, γ,...
Пример. α = aa, β = abc
Длина цепочки β – обозначается модулем |β| – количество символов словаря.
Пример: | α | = 2 – длина цепочки α.
|L| = 0, | β | = 3.
Конкатенация цепочек – «склеивание», присоединение цепочки. Это основная операция над цепочками.
Пример. α = ab, β = cab, тогда α β = abcab. γ = L, тогда αγ = ab.
Операция коммутативности над цепочками не выполняется в
общем случае. Действительно, если α = ab, β = cab то α β = abcab, но
это не одно и то же, что и βα = cabab.
Грамматикой G называется конечное непустое множество правил вывода – R, множества терминальных символов (терминальный словарь – Vt), множества нетерминальных символов – Vn и начального символа S, который должен встречаться хотя бы один раз
в левой части правила вывода:
G = {Vt, Vn, R, S },
где Vt – конечное множество терминальных символов; Vn – непересекающееся с Vt конечное множество нетерминальных символов;
R – конечный набор порождающих правил вида (S ® І); S – начальный символ, S из Vn, т. е. S Vn.
V = Vt  Vn – объединение словарей или общий словарь терминалов и нетерминалов. По иерархии грамматик Хомского выделяют
4 основные группы языков (и описывающих их грамматик). При
этом наибольший интерес представляют регулярные и контексносвободные (КС) грамматики и языки. Они используются при описании синтаксиса языков программирования. С помощью регуляр-
∈
8
ных грамматик можно описать лексемы языка – идентификаторы,
константы, служебные слова и прочие. На основе КС-грамматик
строятся более крупные синтаксические конструкции – описания
типов и переменных, арифметические и логические выражения,
управляющие операторы, и, наконец, полностью вся программа на
исходном языке.
Рассмотрим несколько примеров, иллюстрирующих введенные
понятия:
а. Задана грамматика Г1.0 и требуется определить язык, порождаемый этой грамматикой.
Г1.0: Vt = {a, b, c}, Vn = {<I>}, R = {<I> ® abc}.
Схема грамматики содержит одно правило, поэтому Г1.0 порождает язык из одного слова
L(Г1.0) = {abc}.
б. Задана грамматика Г1.1 и требуется определить язык, порождаемый этой грамматикой.
Г1.1: Vt = {a, b, c}, Vn = {<I>, <B>, <C>}
R = {<I> ® a<B>, <B> ® <C>d, <B> ® dc, <C> ® $}
Построим все выводы в этой грамматике:
<I> ® a<B> ® a<C>d ® ad,
<I> ® a<B> ® adc.
Следовательно язык L(Г1.1) = {adc, ad}.
В общем случае, если описано множество цепочек, представляющих собой некоторый язык, и требуется построить грамматику,
порождающую это множество цепочек, то следует поступать так:
1) выписать несколько примеров из заданного множества цепочек;
2) проанализировать структуру цепочек, выделяя начало, конец, повторяющиеся символы или группы символов (т. е., определяя закономерности);
3) ввести обозначения для сложных структур, состоящих из
групп символов. Такие обозначения являются нетерминальными
символами искомой грамматики;
4) построить правила для каждой из выделенных структур, используя для задания повторяющихся структур рекурсивные правила;
5) объединить все правила;
6) проверить с помощью выводов возможность получения цепочек с разной структурой.
9
Формы записи грамматики
Форма Бэкуса-Наура
При описании синтаксиса конкретных языков программирования приходится вводить большое число нетерминальных символов, и символическая форма записи теряет свою наглядность.
В этом случае применяют форму Бэкуса-Наура (ФБН), которая
предполагает использование в качестве нетерминальных символов
комбинаций слов естественного языка, заключенных в угловые
скобки, а в качестве разделителя – специального знака, состоящего из двух двоеточий и равенства. Например, если правила <I> ®
<E><L> и <I> ® <E> записаны в символической форме, и символ
<L> соответствует синтаксическому понятию «список», а символ
<E> – «элемент списка», то их можно представить в форме БэкусаНаура так:
<список>:: = <элемент списка><список>,<список>:: = <элемент списка>.
Чтобы сократить описание схемы грамматики, в ФБН разрешается объединять правила c одинаковой левой частью в одно правило, правая часть которого должна включать правые части объединяемых правил, разделенные вертикальной чертой. Используя
объединение правил, для рассматриваемого примера получаем:
<список>:: = <элемент списка><список>|<элемент списка>.
Один из наиболее распространенных способов описания синтаксиса языка – это форма Бэкуса-Наура (Backus J.W., Naur P). Этот
способ был разработан для описания Алгола-60, однако в дальнейшем он использован для многих других языков. При записи грамматики в форме Бэкуса-Наура используются два типа объектов:
основные символы (или терминальные символы, в частности,
ключевые слова);
металингвистические переменные (или нетерминальные символы), значениями которых являются цепочки основных символов
описываемого языка. Металингвистические переменные изображаются словами (русскими или английскими), заключенными в
угловые скобки (<...>), металингвистические связки (:: =, |).
Итерационная форма
Для получения более компактных описаний синтаксиса применяют итерационную форму описания. Такая форма предполагает
введение специальной операции, которая называется итерацией
10
и обозначается парой фигурных скобок со звездочкой. Итерация
вида {a}* определяется как множество, включающее цепочки всевозможной длины, построенные с использованием символа a, и пустую цепочку.
{a}* = {$, a, aa, aaa, aaaa,...}.
Иcпользуя итерацию для описания множества цепочек, задаваемых символическими правилами, для списка получаем:
<L> ® <E><{<E>}*.
Например, описание множества цепочек, каждая из которых
должна начинаться знаком # и может состоять из произвольного
числа букв x и y, может быть представлено в итерационной форме
так:
<I> ® # {x|y}*.
В итерационных формах описания наряду с итерационными
cкобками часто применяют квадратные скобки для указания того,
что цепочка, заключенная в них, может быть опущена. С помощью
таких скобок правила:
<E> ® x<E>y<B>z и <E> ® x<B>z
могут быть записаны так:
<E> ® x[<E>y]<B> z.
Форма Бэкуса-Наура не позволяет задавать контекстные условия. При использовании формы Бэкуса-Наура контекстные условия задаются в словесной форме. Аббревиатура BNF как BackusNaur-Form (БНФ), а ранее она означала Backus-Normal-Form.
Вернёмся к нашему предложению и опишем его метаязыком в
БНФ.
Пусть синтаксис или грамматика заданы следующими правилами:
<предложение>:: = < прилагательное >< подлежащее >< сказуемое >< существительное >
Эта грамматика допускает лишь первый вариант предложения и
не допускает второго варианта с другой семантикой.
Таким образом, на этом примере видно, что синтаксис может
влиять на семантику, т. е. определять смысловое содержание предложения.
При определении синтаксиса языков Pascal и Modula-2 Н. Вирт
использовал расширенную форму Бэкуса-Наура (EBNF):
нетерминалы записываются как отдельные слова;
терминалы записываются в кавычках, например “BEGIN”;
11
вертикальная черта (|), как и прежде, используется для определения альтернатив;
круглые скобки используются для группировки;
квадратные скобки используются для определения возможного
вхождения символа или группы символов;
фигурные скобки используются для определения возможного
повторения символа или группы символов;
символ равенства используется вместо символа;
символ точка используется для обозначения конца правила;
комментарии заключаются между символами (* … *);
эквивалентно [ ].
Пример.
Integer = Sign UnsignedInteger.
UnsignedInteger = digit {digit}.
Sign = ["+"|"–"].
digit = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".
В 1981 году Британский институт стандартов (British Standards
Institute) опубликовал стандарт EBNF. BSI-стандарт получился
более наглядным, чем расширенная форма Бэкуса-Наура, предложенная Виртом:
элементы правил разделяются запятыми;
правила заканчиваются точкой с запятой;
пробелы не являются значащими.
Пример:
Constant Declaration = "CONST",
Constant Identifier, " = ", Constant Expression, ";",
{Constant Identifier, " = ", Constant Expression, ";"};
Constant Identifier = identifier;
Constant Expression = = Expression;
Существуют и другие формы представления грамматик, например ван Вейнгаардена, которые использовались для описания синтаксиса ALGOL 68.
Порядок выполнения работы
1. Получить вариант задания у преподавателя.
2. Подготовить и защитить отчет.
3. Разработать и проверить корректность грамматики.
4. Описать КС-грамматику входного языка в форме БэкусаНаура.
5. Сдать разработанную грамматику преподавателю.
12
Требования к оформлению отчета
Отчет по лабораторной работе должен содержать следующие
разделы:
задание по лабораторной работе;
описание словаря и правил грамматики (в соответствии с вариантом задания);
выводы по проделанной работе.
Контрольные вопросы
1. Какие существуют методы задания языков ? Какие дополнительные вопросы необходимо решить при задании языка программирования ?
2. Что такое грамматика? Дайте определения грамматики.
3. Как выглядит описание грамматики в форме Бэкуса-Наура.
4. Как иначе можно описать грамматику?
5. Какие классы грамматик существуют? Что такое регулярные
грамматики?
6. Дайте определения контекстно-свободной грамматики, выводимости цепочки, непосредственной выводимости, длины вывода.
13
Лабораторная работа № 2
РАБОТА С ТАБЛИЦЕЙ СИМВОЛОВ.
ПРОЕКТИРОВАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
Цель работы: Изучение основных понятий теории грамматик;
написание программы простейшего лексического анализатора.
Для выполнения лабораторной работы требуется написать программу. Входные данные для программы: файл с грамматикой
входного языка, файл с вариантом программы на входном языке.
Программа по разработанной грамматике выполняет лексический
анализ исходного текста из варианта задания, на последовательность лексем с указанием их типов и значений. Текст на исходном
языке задается в виде символьного (текстового) файла. Программа
должна выдавать сообщения о наличие во входном тексте ошибок,
которые могут быть обнаружены на этапе лексического анализа,
опознавать и удалять комментарии неограниченной длины из текста программы на исходном языке. Программа должна допускать
наличие комментариев неограниченной длины во входном файле.
Форму организации комментариев предлагается выбрать самостоятельно.
Форму организации комментариев предлагается описать в грамматике исходного языка.
Краткие теоретические сведения
Работу синтаксического и лексического анализаторов можно
изобразить в виде схемы на рис. 2.
Лексический анализатор (или сканер) – это часть компилятора,
которая читает литеры программы на исходном языке и строит из
них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на
этапе синтаксического анализа и разбора.
Исходная
программа
Сканер
(лексический
анализатор)
Очередная лексема
Обращение
за очередным
словом (лексемой)
Синтаксический
анализатор
Рис. 2. Взаимодействие синтаксического и лексического анализаторов
14
С теоретической точки зрения лексический анализатор не является обязательной, необходимой частью компилятора. Его функции могут выполняться на этапе синтаксического разбора как
обращение к подпрограмме. Однако существует несколько причин, исходя из которых, в состав практически всех компиляторов
включают лексический анализ. Эти причины заключаются в следующем:
упрощается работа с текстом исходной программы на этапе синтаксического разбора и сокращается объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и выкидывает всю незначащую информацию;
для выделения в тексте и разбора лексем возможно применять
простую, эффективную и теоретически хорошо проработанную
технику анализа, в то время как на этапе синтаксического анализа
конструкций исходного языка используются достаточно сложные
алгоритмы разбора;
сканер отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходный программы, структура которого может варьироваться в зависимости от
версии входного языка – при такой конструкции компилятора при
переходе от одной версии языка к другой достаточно только перестроить относительно простой сканер.
Лексический анализ важен для процесса компиляции по нескольким причинам:
a) замена в программе идентификаторов, констант, ограничителей и служебных слов лексемами делает представление программы
более удобным для дальнейшей обработки;
b) лексический анализ уменьшает длину программы, устраняя
из ее исходного представления несущественные пробелы и комментарии;
c) если будет изменена кодировка в исходном представлении
программы, то это отразится только на лексическом анализаторе.
Выбор конструкций, которые будут выделяться как отдельные
лексемы, зависит от языка и от точки зрения разработчиков компилятора. Обычно принято выделять следующие типы лексем:
идентификаторы, служебные слова, константы и ограничители.
Каждой лексеме сопоставляется пара (тип_лексемы, указатель_
на_информацию_о_ней).
Соглашение: эту пару тоже будем называть лексемой, если это
не будет вызывать недоразумений.
15
Таким образом, лексический анализатор – это транслятор, входом которого служит цепочка символов, представляющих исходную программу, а выходом – последовательность лексем.
Очевидно, что лексемы перечисленных выше типов можно описать с помощью регулярных грамматик.
Например, идентификатор (I):
I → a | b|...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9
целое без знака (N):
N→ 0 | 1 |...| 9 | N0 | N1 |...| N9
и т. д.
Функции, выполняемые лексическим анализатором, и состав
лексем, которые он выделяет в тексте исходной программы, могут
меняться в зависимости от версии компилятора. В основном лексические анализаторы выполняют исключение из текста исходной
программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка.
В простейшем случае фазы лексического и синтаксического
анализа могут выполняться компилятором последовательно. Но
для многих языков программирования информации на этапе лексического анализа может быть недостаточно для однозначного
определения типа и границ очередной лексемы. Иллюстрацией такого случая может служить пример оператора программы на языке
Фортран, когда по части текста DO 10 I = 1... невозможно определить тип оператора (а соответственно, и границы лексем). В случае
DO 10 I = 1.15 – это будет присвоение вещественной переменной
DO10I значения константы 1.15 (пробелы в Фортране игнорируются), а в случае DO 10 I = 1,15 – это цикл с перечислением от 1 до 15
по целочисленной переменной I до метки 10.
В большинстве компиляторов лексический и синтаксический
анализаторы – это взаимосвязанные части. Лексический разбор
исходного текста в таком варианте выполняется поэтапно так,
что синтаксический анализатор, выполнив разбор очередной конструкции языка, обращается к сканеру за следующей лексемой.
При этом он может сообщить информацию о том, какую лексему следует ожидать. В процессе разбора может даже происходить
“откат назад”, чтобы выполнить анализ текста на другой основе.
В дальнейшем будем исходить из предположения, что все лексемы
могут быть однозначно выделены сканером на этапе лексического
разбора.
16
Рассмотрим методы и средства, которые обычно используются
при построении лексических анализаторов. В основе таких анализаторов лежат регулярные грамматики, поэтому рассмотрим грамматики этого класса более подробно.
Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную грамматику.
Напомним, что грамматика G = (VT, VN, R, S) называется леволинейной, если каждое правило из R имеет вид A → Bt либо A → t, где
A, B – нетерминалы, t – терминал.
Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом ^ – признаком конца цепочки.
Для грамматик этого типа существует алгоритм определения
того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):
1) первый символ исходной цепочки a1a2...an^ заменяем нетерминалом A, для которого в грамматике есть правило вывода A → a1
(другими словами, производим «свертку» терминала a1 к нетерминалу A);
2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа
от него очередной терминал ai исходной цепочки.
Грамматика для записи регулярных выражений (в порядке убывания приоритета):
<р>* – повторение 0 или более раз;
<р>+ – повторение 1 или более раз;
<р>? – необязательный фрагмент;
<р><р> – конкатенация;
<р>{m,n} – повторение от m до n раз;
<р>{m} – повторение m раз;
<р>{m,} – повторение m или более раз;
^<р> – фрагмент в начале строки;
<р>$ – фрагмент в конце строки;
<р>|<р> – любое из выражений;
<р>/<р> – первое выражение, если за ним следует второе;
(р) – скобки, используются для группировки.
Пример. Регулярное выражение ^[^aeiou]*$ означает любую
строку, не содержащую букв a, e, i, o, u.
Это эквивалентно построению дерева разбора методом «снизувверх»: на каждом шаге алгоритма строим один из уровней в дереве
разбора, «поднимаясь» от листьев к корню.
17
При работе этого алгоритма возможны следующие ситуации:
1) прочитана вся цепочка; на каждом шаге находилась единственная нужная «свертка»; на последнем шаге свертка произошла
к символу S. Это означает, что исходная цепочка a1a2...an^ Î L(G);
2) прочитана вся цепочка; на каждом шаге находилась единственная нужная «свертка»; на последнем шаге свертка произошла
к символу, отличному от S. Это означает, что исходная цепочка
a1a2...an ^ Î L(G);
3) на некотором шаге не нашлось нужной свертки, т. е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было
бы правило вывода B → Aai. Это означает, что исходная цепочка
a1a2...an^ Î L(G);
4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, т. е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями,
и поэтому непонятно, к какому из них производить свертку. Это
говорит о недетерминированности разбора. Анализ этой ситуации
будет дан ниже.
Допустим, что разбор на каждом шаге детерминированный. Для
того чтобы быстрее находить правило с подходящей правой частью,
зафиксируем все возможные свертки (это определяется только
грамматикой и не зависит от вида анализируемой цепочки).
Это можно сделать в виде таблицы, строки которой помечены
нетерминальными символами грамматики, столбцы – терминальными. Значение каждого элемента таблицы – это нетерминальный
символ, к которому можно свернуть пару «нетерминал-терминал»,
которыми помечены соответствующие строка и столбец.
Например, для грамматики G = ({a, b, ^}, {S, A, B, C}, P, S), такая
таблица будет выглядеть следующим образом:
a
b
⊥
A
A
C
-
C
A
B
S
B
C
B
-
S
-
-
-
Где P: S → C^, C → Ab | Ba, A → a | Ca, B → b | Cb.
Знак “-” ставится в том случае, если для пары “терминал-нетерминал” свертки нет.
18
Но чаще информацию о возможных свертках представляют
в виде диаграммы состояний (ДС) – неупорядоченного ориентированного помеченного графа, который строится следующим
образом:
1) строят вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала – одну вершину), и еще одну
вершину, помеченную символом, отличным от нетерминальных
(например, H). Эти вершины будем называть состояниями. H – начальное состояние;
2) соединяем эти состояния дугами по следующим правилам:
для каждого правила грамматики вида W → t соединяем дугой
состояния H и W (от H к W) и помечаем дугу символом t;
для каждого правила W → Vt соединяем дугой состояния V и W
(от V к W) и помечаем дугу символом t;
Диаграмма состояний для грамматики G:
H
a
b
A
a
b
b
B
C
S
a
Алгоритм разбора по диаграмме состояний:
1) объявляем текущим состояние H;
2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной
символ исходной цепочки и переходим из текущего состояния в
другое состояние по дуге, помеченной этим символом. Состояние, в
которое мы при этом попадаем, становится текущим.
При работе этого алгоритма возможны следующие ситуации
(аналогичные ситуациям, которые возникают при разборе непосредственно по регулярной грамматике):
1) прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежит
L(G);
19
2) прочитана вся цепочка; на каждом шаге находилась единственная «нужная» дуга; в результате последнего шага оказались
в состоянии, отличном от S. Это означает, что исходная цепочка не
принадлежит L(G);
3) на некотором шаге не нашлось дуги, выходящей из текущего
состояния и помеченной очередным анализируемым символом. Это
означает, что исходная цепочка не принадлежит L(G);
4) на некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходящих из текущего состояния, помеченных очередным анализируемым символом, но ведущих в разные состояния. Это говорит о недетерминированности разбора. Анализ этой
ситуации будет приведен ниже.
Диаграмма состояний определяет конечный автомат, построенный по регулярной грамматике, который допускает множество
цепочек, составляющих язык, определяемый этой грамматикой.
Состояния и дуги ДС – это графическое изображение функции переходов конечного автомата из состояния в состояние при условии,
что очередной анализируемый символ совпадает с символом-меткой дуги.
Среди всех состояний выделяется начальное (считается, что в
начальный момент своей работы автомат находится в этом состоянии) и конечное (если автомат завершает работу переходом в это
состояние, то анализируемая цепочка им допускается).
Определение: конечный автомат – это пятерка M = (Q, ∑, δ, q0,
F), где
Q – конечное множество состояний;
∑ – конечное множество допустимых входных символов;
δ – отображение множества Q х ∑ в множество P(Q), определяющее поведение управляющего устройства (эту функцию часто называют функцией переходов);
• q0 Î Q – начальное состояние управляющего устройства;
• F ⊆ Q – множество заключительных состояний (может быть
одно заключительное состояние);
δ(A, t) = B означает, что из состояния A по входному символу t
происходит переход в состояние B.
Определение: конечный автомат допускает цепочку a1a2...an,
если δ(H, a1) = A1; δ(A1, a2) = A2;...; δ(An–2, an–1) = A n–1; δ(A n–1,
a n) = S, где ai Î Σ , Aj Q, S Î F; j = 1, 2,..., n–1; i = 1, 2,..., n; q0 –
начальное состояние; S – одно из заключительных состояний.
Определение: множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.
∈
20
Для более удобной работы с диаграммами состояний введем несколько соглашений:
a) если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то будем изображать одну дугу, помеченную всеми этими символами;
b) непомеченная дуга будет соответствовать переходу при любом
символе, кроме тех, которыми помечены другие дуги, выходящие
из этого состояния;
c) введем состояние ошибки (ER); переход в это состояние будет
означать, что исходная цепочка языку не принадлежит.
По диаграмме состояний легко написать анализатор для регулярной грамматики.
Например, для грамматики G = ({a,b, ^}, {S,A,B,C}, P, S), где P:
S → C^
С → Ab | Ba
A → a | Ca
B → b | Cb
анализатор будет таким:
#include <stdio.h>
int scan_G(){
enum state {H, A, B, C, S, ER}; /* множество состояний */
enum state CS; /* CS – текущее состояние */
FILE *fp;/*указатель на файл, в котором находится
анализируемая цепочка */
int c;
CS = H;
fp = fopen ("data","r");
c = fgetc (fp);
do {switch (CS) {
case H: if (c = = 'a') {c = fgetc(fp); CS = A;}
else if (c = = 'b') {c = fgetc(fp); CS = B;}
else CS = ER;
break;
case A: if (c = = 'b') {c = fgetc(fp); CS = C;}
else CS = ER;
break;
case B: if (c = = 'a') {c = fgetc(fp); CS = C;}
else CS = ER;
break;
21
case C: if (c = = 'a') {c = fgetc(fp); CS = A;}
else if (c = = 'b') {c = fgetc(fp); CS = B;}
else if (c = = '⊥') CS = S;
else CS = ER;
break;
}
} while (CS ! = S && CS ! = ER);
if (CS = = ER) return -1; else return 0;
}
О недетерминированном разборе
При анализе по регулярной грамматике может оказаться, что
несколько нетерминалов имеют одинаковые правые части и поэтому неясно, к какому из них делать свертку (см. ситуацию 4 в описании алгоритма). В терминах диаграммы состояний это означает,
что из одного состояния выходит несколько дуг, ведущих в разные
состояния, но помеченных одним и тем же символом.
Например, для грамматики G = ({a,b, ^}, {S,A,B}, R, S), где
R = {S → A^, A → a | Bb, B → b | Bb}, разбор будет недетерминированным (так как у нетерминалов A и B есть одинаковые правые
части – Bb).
Такой грамматике будет соответствовать недетерминированный
конечный автомат.
Определение: недетерминированный конечный автомат (НКА) –
это пятерка (K, VT, F, H, S), где K – конечное множество состояний; VT – конечное множество допустимых входных символов;
F – отображение множества K × VT в множество подмножеств K; H
Î K – конечное множество начальных состояний; S Î K – конечное
множество заключительных состояний.
F(A, t) = {B1, B2,..., Bn} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний Bi,
i = 1, 2,...,n.
В этом случае можно предложить алгоритм, который будет перебирать все возможные варианты сверток (переходов) один за другим; если цепочка принадлежит языку, то будет найден путь, ведущий к успеху; если будут просмотрены все варианты и каждый
из них будет завершаться неудачей, то цепочка языку не принадлежит. Однако такой алгоритм практически неприемлем, поскольку при переборе вариантов мы, скорее всего, снова окажемся перед
проблемой выбора и, следовательно, будем иметь «дерево отложенных вариантов».
22
Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков,
определяемых детерминированными конечными автоматами.
Это означает, что для любого НКА всегда можно построить детерминированный КА, определяющий тот же язык.
Алгоритм построения детерминированного КА по НКА.
Вход: M = (K, VT, F, H, S) – недетерминированный конечный
автомат. Выход: M’ = (K’, VT, F’, H’, S’) – детерминированный конечный автомат, допускающий тот же язык, что и автомат М.
Метод
1. Множество состояний К’ состоит из всех подмножеств множества К.
Каждое состояние из К’ будем обозначать [A1A2...An], где Ai Î K.
2. Отображение F’ определим как F’([A1A2...An], t) = [B1B2...
Bm], где для каждого 1 < = j < = mF(Ai, t) = Bj для каких-либо
1 < = i < = n.
3. Пусть H = {H1, H2,..., Hk}, тогда H’ = [H1, H2,..., Hk].
4. Пусть S = {S1, S2,..., Sp}, тогда S’ – все состояния из K’, имеющие вид [...Si...], Si Î S для какого-либо 1 < = i < = p.
В множестве K’ могут оказаться состояния, которые недостижимы из начального состояния, их можно исключить.
Проиллюстрируем работу алгоритма на примере.
Пусть задан НКА M = ({H, A, B, S}, {0, 1}, F, {H}, {S}), где
F(H, 1) = B F(B, 0) = A.
F(A, 1) = B F(A, 1) = S, тогда соответствующий детерминированный конечный автомат будет таким:
K’ = {[H], [A], [B], [S], [HA], [HB], [HS], [AB], [AS], [BS], [HAB],
[HAS], [ABS], [HBS], [HABS]}
F’([A], 1) = [BS] F’([H], 1) = [B]
F’([B], 0) = [A] F’([HA], 1) = [BS]
F’([HB], 1) = [B] F’([HB], 0) = [A]
F’([HS], 1) = [B] F’([AB], 1) = [BS]
F’([AB], 0) = [A] F’([AS], 1) = [BS]
F’([BS], 0) = [A] F’([HAB], 0) = [A]
F’([HAB], 1) = [BS] F’([HAS], 1) = [BS]
F’([ABS], 1) = [BS] F’([ABS], 0) = [A]
F’([HBS], 1) = [B] F’([HBS], 0) = [A]
F’([HABS], 1) = [BS] F’([HABS], 0) = [A]
S’ = {[S], [HS], [AS], [BS], [HAS], [ABS], [HBS], [HABS]}
23
Достижимыми состояниями в получившемся КА являются [H],
[B], [A] и [BS], поэтому остальные состояния удаляются.
Таким образом, M’ = ({[H], [B], [A], [BS]}, {0, 1}, F’, H, {[BS]}),
где F’([A], 1) = [BS] F’([H], 1) = [B]
F’([B], 0) = [A].
Для грамматик этого класса, как мы уже видели, существует
простой и эффективный алгоритм анализа того, принадлежит ли
заданная цепочка языку, порождаемому этой грамматикой. Однако перед лексическим анализатором стоит более сложная задача: он
должен сам выделить в исходном тексте цепочку символов, представляющую лексему, а также преобразовать ее в пару (тип_лексемы, указатель_на_информацию_о_ней). Для того чтобы решить
эту задачу, опираясь на способ анализа с помощью диаграммы состояний, введем на дугах дополнительный вид пометок – пометкидействия. Теперь каждая дуга в ДС может выглядеть так:
A
t1,t2,...,tn
D1,D2,...,Dm
B
Смысл ti прежний – если в состоянии A очередной анализируемый символ совпадает с ti для какого-либо i = 1, 2,... n, то осуществляется переход в состояние B; при этом необходимо выполнить
действия D1, D2,...,Dm.
Вход лексического анализатора – символы исходной программы
на М-языке (вариант задания); результат работы – исходная программа в виде последовательности лексем (их внутреннего представления).
Лексический анализатор для модельного языка будем писать
в два этапа: сначала построим диаграмму состояний с действиями
для распознавания и формирования внутреннего представления
лексем, а затем по ней напишем программу анализатора.
Первый этап: разработка ДС.
Представление лексем: все лексемы М-языка разделим на несколько классов; классы перенумеруем:
служебные слова – 1;
ограничители – 2;
константы (целые числа) – 3;
идентификаторы – 4.
Внутреннее представление лексем – это пара (номер_класса,
номер_в_классе).
24
Номер_в_классе – это номер строки в таблице лексем соответствующего класса.
Соглашение об используемых переменных, типах и функциях
1 Пусть есть переменные: buf – буфер для накопления символов
лексемы;
c – очередной входной символ;
d – переменная для формирования числового значения константы;
TW – таблица служебных слов М-языка;
TD – таблица ограничителей М-языка;
TID – таблица идентификаторов анализируемой программы;
TNUM – таблица чисел-констант, используемых в программе.
Таблицы TW и TD заполнены заранее, так как их содержимое
не зависит от исходной программы; TID и TNUM будут формироваться в процессе анализа; для простоты будем считать, что все таблицы одного типа; пусть tabl – имя типа этих таблиц, ptabl – указатель на tabl.
2. Пусть есть функции:
void clear (void); – очистка буфера buf;
void add (void); – добавление символа с в конец буфера buf;
int look (ptabl Т); – поиск в таблице Т лексемы из буфера buf; результат: номер строки таблицы с информацией о лексеме либо 0,
если такой лексемы в таблице Т нет;
int putl (ptabl Т); – запись в таблицу Т лексемы из буфера buf,
если ее там не было; результат: номер строки таблицы с информацией о лексеме;
int putnum (); – запись в TNUM константы из d, если ее там не
было; результат: номер строки таблицы TNUM с информацией о
константе-лексеме;
void makelex (int k, int i); – формирование и вывод внутреннего
представления лексемы; k – номер класса, i – номер в классе;
void gc (void) – функция, читающая из входного потока очередной символ исходной программы и заносящая его в переменную с;
void id_or_word (void); – функция, определяющая является ли
слово в буфере buf идентификатором или служебным словом и формирующая лексему соответствующего класса;
void is_dlm (void); – если символ в буфере buf является разделителем, то формирует соответствующую лексему, иначе производится переход в состояние ER.
Диаграмма состояний для лексического анализатора:
25
gc();
‘-’
H
add();gc();
буква, цифра
буква
ID
clear();add();gc();
цифра
d=c-’0’;gc();
id_or_word();
d=d*10+(c-’0’);gc();
цифра
NUM
makelex(3,putnum());
gc();
{
COM
gc();
}
gc();
ER
:
ASS
gc();
=
makelex(2,N⊥);
DLM
makelex(2,N:);
gc(); makelex(2,N:=);
FIN
clear(); add();
is_dlm();
Замечания:
1) символом Nx в диаграмме (и в тексте программы) обозначен
номер лексемы x в ее классе;
2) по нашей диаграмме знак «! = « представлен двумя лексемами, хотя нужно сделать одну лексему, по аналогии с «: = «. Соответствующие изменения надо сделать и в синтаксическом анализаторе.
Второй этап: по ДС пишем программу
#define BUFSIZE 80
extern ptabl TW, TID, TD, TNUM;
char buf[BUFSIZE]; /* для накопления символов лексемы */
26
int c; /* очередной символ */
int d; /* для формирования числового значения константы */
enum state {H, ID, NUM, COM, ASS, DLM, ER, FIN};
enum state TC; /* текущее состояние */
FILE* fp;
void clear(void); /* очистка буфера buf */
void add(void); /* добавление символа с в конец буфера buf */
int look(ptabl); /* поиск в таблице лексемы из buf;
результат: номер строки таблицы либо 0 */
int putl(ptabl); /* запись в таблицу лексемы из buf,
если ее
там не было; результат: номер строки
таблицы */
int putnum(); /* запись в TNUM константы из d, если
ее там
не было; результат: номер строки таблицы
TNUM */
int j; /* номер строки в таблице, где находится лексема,
найденная функцией look */
void makelex(int,int); /* формирование и вывод внутреннего
представления лексемы */
void id_or_word(void) { if (j = look(TW)) makelex(1,j);
else { j = putl(TID); makelex(4,j);}
}
void is_dlm(void) {if(j = look(TD)) {makelex(2,j);
gc(); ТС = H;}
TC = ER;}
void gc(void) { c = fgetc(fp);}
void scan (void)
{TC = H;
fp = fopen("prog","r"); /* в файле "prog" находится
текст
исходной программы */
gc();
do {switch (TC) {
case H:
if (c = = ' ') gc();
else if (isalpha(c))
27
{clear(); add();gc(); TC = ID;}
else if (isdigit (c))
{d = c – '0'; gc(); TC = NUM;}
else if (c = = '{') { gc(); TC = COM;}
else if (c = = ':')
{ gc(); TC = ASS;}
else if (c = = '^')
{makelex(2, N^); TC = FIN;}
else TC = DLM;
break;
case ID:
if (isalpha(c) || isdigit(c)) {add(); gc();}
else {id_or_word(); TC = H;}
break;
case NUM:
if (isdigit(c)) {d = d*10+(c – '0'); gc();}
30
else {makelex (3, putnum()); TC = H;}
break;
/*........... */
} /* конец switch */
} /* конец тела цикла */
while (TC ! = FIN && TC ! = ER);
if (TC = = ER) printf("ERROR !!!\n");
else printf("O.K.!!!\n");
}
Порядок выполнения работы
1. Получить вариант задания у преподавателя;
2. Написать и отладить программу на ЭВМ;
3. Сдать работающую программу преподавателю;
4. Подготовить и защитить отчет.
Требования к оформлению отчета
Отчет должен содержать следующие разделы:
задание по лабораторной работе;
описание алгоритма работы сканера или граф конечного автомата для распознавания цепочек (в соответствии с вариантом задания);
28
текст программы (оформляется после выполнения программы
на ЭВМ);
выводы по проделанной работе.
Контрольные вопросы
1. Что такое трансляция, компиляция, транслятор, компилятор?
2. Из каких процессов состоит компиляция? Расскажите об общей структуре компилятора.
3. Какую роль выполняет лексический анализ в процессе компиляции?
4. Как связаны лексический и синтаксический анализ?
5. Дайте определение цепочки, языка.
6. Какие существуют методы задания языков? Какие дополнительные вопросы необходимо решить при задании языка программирования?
7. Что такое грамматика? Дайте определения грамматики.
8. Как выглядит описание грамматики в форме Бэкуса-Наура.
9. Какие классы грамматик существуют? Что такое регулярные
грамматики?
10. Дайте определения контекстно-свободной грамматики, выводимости цепочки, непосредственной выводимости, длины вывода.
11. Что такое конечный автомат? Дайте определение детерминированного и недетерминированного конечных автоматов.
12. Какие проблемы необходимо решить при построении сканера на основе конечного автомата?
29
Лабораторная работа № 3
СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ.
ПОСТРОЕНИЕ ПРОСТЕЙШЕГО ДЕРЕВА ВЫВОДА
Цель работы: изучение основных понятий теории грамматик,
ознакомление с алгоритмами синтаксического анализа (разбора)
для некоторых классов КС-грамматик, получение практических
навыков создания простейшего синтаксического анализатора для
заданной грамматики.
Для выполнения лабораторной работы требуется дописать программу, которая выполняет синтаксический анализ входного
текста в соответствии с заданием и разработанной грамматикой,
строит дерево разбора заданной программы, порождает таблицу
идентификаторов. Текст на входном языке задается в виде символьного (текстового) файла, являющегося результатом лабораторной работы № 2. Допускается исходить из условия, что текст
содержат не более одного предложения входного языка. Программа должна выдавать сообщения о наличие во входном тексте
ошибок.
Рекомендуется программу разбить на три составные части: лексический анализ, построение цепочки вывода и построение дерева
вывода. Полученная после лексического анализа цепочка должна
во второй части программы рассматриваться в соответствии с алгоритмом разбора. При неудачном завершении алгоритма выдается
сообщение об ошибке, при удачном – строится цепочка вывода. После построения цепочки вывода на ее основе строится дерево разбора, в котором символы последовательно заменяются на лексемы
из таблицы лексем.
Длину идентификаторов и строковых констант считать ограниченной 32 символами.
Краткие теоретические сведения
По иерархии грамматик Хомского выделяют 4 основные группы языков (и описывающих их грамматик). При этом наибольший
интерес представляют регулярные и контексно-свободные (КС)
грамматики и языки. Они используются при описании синтаксиса языков программирования. С помощью регулярных грамматик
можно описать лексемы языка – идентификаторы, константы, служебные слова и прочие. На основе КС-грамматик строятся более
30
крупные синтаксические конструкции – описания типов и переменных, арифметические и логические выражения, управляющие
операторы, и, наконец, полностью вся программа на исходном
языке.
Входные цепочки регулярных языков распознаются с помощью
конечных автоматов (КА). Они лежат в основе сканеров, выполняющих лексический анализ и выделение слов в тексте программы
на входном языке. Результатом работы сканера является преобразование исходной программы в список или таблицу лексем. Дальнейшую ее обработку выполняет другая часть компилятора – синтаксический анализатор. Его работа основана на использовании
правил КС-грамматики, описывающих конструкции исходного
языка.
Взаимодействие лексического и синтаксического анализатора
рассматривалось в предыдущей лабораторной работе, здесь же будем изучать алгоритмы, лежащие в основе синтаксического анализа. Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая
представляется в виде уже выделенных слов входного языка, и
преобразовать ее в вид, удобный для дальнейшей семантической
(смысловой) обработки и генерации кода. Одним из таких способов
представления является дерево синтаксического разбора.
Соглашение
1. Об используемых переменных и типах:
пусть лексический анализатор выдает лексемы типа struct lex
{int class; int value;};
при описанном выше характере взаимодействия лексического
и синтаксического анализаторов естественно считать, что лексический анализатор – это функция getlex с прототипом struct lex getlex
(void);
в переменной struct lex curr_lex будем хранить текущую лексему, выданную лексическим анализатором.
2. Об используемых функциях:
int id (void); – результат равен 1, если curr_lex.class = 4, т. е.
curr_lex представляет идентификатор, и 0 – в противном случае;
int num (void); – результат равен 1, если curr_lex.class = 3, т. е.
curr_lex представляет число-константу, и 0 – в противном случае;
int eq (char * s); – результат равен 1, если curr_lex представляет
строку s, и 0 – иначе;
void ERROR (void) – функция обработки ошибки; при обнаружении ошибки работа анализатора прекращается.
31
Тогда метод рекурсивного спуска реализуется с помощью следующих процедур, создаваемых для каждого нетерминала грамматики:
для P → program D1; B⊥
void P (void){
if (eq ("program")) curr_lex = getlex();
else ERROR();
D1();
if (eq (";")) curr_lex = getlex(); else ERROR();
B();
if (!eq ("⊥")) ERROR();
}
для D1 → var D {, D}
void D1 (void){
if (eq ("var")) curr_lex = getlex();
else ERROR();
D();
while (eq (","))
{curr_lex = getlex (); D();}
}
для D → I {,I}: [ int | bool ]
void D (void){
if (!id()) ERROR();
else {curr_lex = getlex();
while (eq (","))
{curr_lex = getlex();
if (!id()) ERROR();
else curr_lex = getlex ();
}
if (!eq (":")) ERROR();
else {curr_lex = getlex();
if (eq ("int") || eq ("bool"))
curr_lex = getlex();
else ERROR();}
}
}
для E1 → T {[ + | – | or ] T}
void E1 (void){
T();
while (eq ("+") || eq ("-") || eq ("or"))
{curr_lex = getlex(); T();}
}
32
Для остальных нетерминалов грамматики модельного языка
процедуры рекурсивного спуска пишутся аналогично. «Запуск»
синтаксического анализатора:
... curr_lex = getlex(); P();...
О семантическом анализе
Контекстно-свободные грамматики, с помощью которых описывают синтаксис языков программирования, не позволяют задавать
контекстные условия, имеющиеся в любом языке.
Примеры наиболее часто встречающихся контекстных условий:
a) каждый используемый в программе идентификатор должен
быть описан, но не более одного раза в одной зоне описания;
b) при вызове функции число фактических параметров и их типы
должны соответствовать числу и типам формальных параметров;
c) обычно в языке накладываются ограничения на типы операндов любой операции, определенной в этом языке; на типы левой и правой частей в операторе присваивания; на тип параметра
цикла; на тип условия в операторах цикла и условном операторе
и т.п.
Проверку контекстных условий часто называют семантическим
анализом. Его можно выполнять сразу после синтаксического анализа, некоторые требования можно контролировать во время генерации кода (например, ограничения на типы операндов в выражении), а можно совместить с синтаксическим анализом.
Выберем последний вариант: как только синтаксический анализатор распознает конструкцию, на компоненты которой наложены
некоторые ограничения, проверяется их выполнение. Это означает, что на этапе синтаксического анализа придется выполнять некоторые дополнительные действия, осуществляющие семантический контроль.
Если для синтаксического анализа используется метод рекурсивного спуска, то в тела процедур РС-метода необходимо вставить
вызовы дополнительных «семантических» процедур (семантические действия). Причем, как показывает практика, удобнее вставить их сначала в синтаксические правила, а потом по этим расширенным правилам строить процедуры РС-метода. Чтобы отличать
вызовы семантических процедур от других символов грамматики,
будем заключать их в угловые скобки. Фактически, мы расширили
понятие контекстно-свободной грамматики, добавив в ее правила
вывода символы-действия.
33
Например, пусть в грамматике есть правило
A → a<D1>B<D1;D2> | bC<D3>,
здесь A, B, C Î VN; a, b Î VT; <Di> означает вызов семантической
процедуры Di, i = 1, 2, 3. Имея такое правило грамматики, легко
написать процедуру для метода рекурсивного спуска, которая будет выполнять синтаксический анализ и некоторые дополнительные действия:
void A() {
if (c = = 'a') {c = fgetc(fp); D1(); B(); D1(); D2();}
else if (c = = 'b') {c = fgetc(fp); C(); D3();}
else ERROR();
}
Пример. Написать грамматику, которая позволит распознавать
цепочки языка
L = {α Î (0,1)+^ | α содержит равное количество 0 и 1}.
Этого можно добиться, пытаясь чисто синтаксическими средствами описать цепочки, обладающие этим свойством. Но гораздо
проще с помощью синтаксических правил описать произвольные
цепочки из 0 и 1, а потом вставить действия для отбора цепочек с
равным количеством 0 и 1:
S → <k0 = 0; k1 = 0;> A^
A → 0 <k0 = k0+1> A | 1 <k1 = k1+1> A |
0 <k0 = k0+1; check()> | 1 <k1 = k1+1; check()>, где
void check()
{ if (k0 ! = k1) { printf("ERROR !!!"); exit(1);}
else { printf("SUCCESS !!!\n");exit(0);}
}
Теперь по этой грамматике легко построить анализатор, распознающий цепочки с нужными свойствами.
Семантический анализатор для М-языка
Контекстные условия, выполнение которых нам надо контролировать в программах на М-языке, таковы:
1) любое имя, используемое в программе, должно быть описано
и только один раз;
2) в операторе присваивания типы переменной и выражения
должны совпадать;
3) в условном операторе и в операторе цикла в качестве условия
возможно только логическое выражение;
34
4) операнды операции отношения должны быть целочисленными;
5) тип выражения и совместимость типов операндов в выражении определяются по обычным правилам (как в Паскале).
Проверку контекстных условий совместим с синтаксическим
анализом. Для этого в синтаксические правила вставим вызовы
процедур, осуществляющих необходимый контроль, а затем перенесем их в процедуры рекурсивного спуска.
Обработка описаний
Для контроля согласованности типов в выражениях и типов выражений в операторах, необходимо знать типы переменных, входящих в эти выражения.
Кроме того, нужно проверять, нет ли повторных описаний идентификаторов. Эта информация становится известной в тот момент,
когда синтаксический анализатор обрабатывает описания. Следовательно, в синтаксические правила для описаний нужно вставить
действия, с помощью которых будем запоминать типы переменных
и контролировать единственность их описания.
Лексический анализатор запомнил в таблице идентификаторов
TID все идентификаторы-лексемы, которые были им обнаружены в
тексте исходной программы. Информацию о типе переменных и о
наличии их описания естественно заносить в ту же таблицу.
Пусть каждая строка в TID имеет вид
struct record {
char *name; /* идентификатор */
int declare; /* описан ? 1-"да", 0-"нет" */
char *type; /* тип переменной */
...
};
Тогда таблица идентификаторов TID – это массив структур
#define MAXSIZE_TID 1000
struct record TID [MAXSIZE_TID];
причем i-я строка соответствует идентификатору-лексеме вида (4,i).
Лексический анализатор заполнил поле name; значения полей
declare и type будем заполнять на этапе семантического анализа.
Для этого нам потребуется следующая функция:
void decid (int i, char *t) – в i-й строке таблицы TID контролирует
и заполняет поле declare и, если лексема (4,i) впервые встретилась в
разделе описаний, заполняет поле type:
void decid (int i, char *t)
{if (TID [i].declare) ERROR(); /*повторное описание */
35
else {TID [i].declare = 1; /* описан ! */
strcpy (TID [i].type, t);} /* тип t ! */
}
Раздел описаний имеет вид
D → I {,I}: [int | bool],
т. е. имени типа (int или bool) предшествует список идентификаторов. Эти идентификаторы (вернее, номера соответствующих им
строк таблицы TID) надо запоминать (например, в стеке), а когда
будет проанализировано имя типа, заполнить поля declare и type в
этих строках.
Для этого будем использовать функции работы со стеком целых
чисел:
void ipush (int i); /* значение i – в стек */
int ipop (void); /* из стека – целое */
Будем считать, что (-1) – "дно" стека; тогда функция
void dec (char *t)
{int i;
while ((i = ipop()) ! = -1)
decid(i,t);
}
считывает из стека номера строк TID и заносит в них информацию
о наличии описания и о типе t.
С учетом этих функций правило вывода с действиями для обработки описаний будет таким:
D → < ipush (-1) > I < ipush (curr_lex.value) >
{, I < ipush (curr_lex.value) >}:
[ int < dec ("int") > | bool < dec ("bool") > ]
Контроль контекстных условий в выражении
Пусть есть функция
char *gettype (char *op, char *t1, char *t2),
которая проверяет допустимость сочетания операндов типа t1 (первый операнд) и типа t2 (второй операнд) в операции op; если типы
совместимы, то выдает тип результата этой операции; иначе – строку «no».
Типы операндов и обозначение операции будем хранить в стеке;
для этого нам нужны функции для работы со стеком строк:
void spush (char *s); /* значение s – в стек */
char *spop (void); /* из стека – строку */
36
Если в выражении встречается лексема-целое_число или логические константы true или false, то соответствующий тип сразу заносим в стек с помощью
spush(«int») или spush(«bool»).
Если операнд – лексема-переменная, то необходимо проверить,
описана ли она; если описана, то ее тип надо занести в стек. Эти
действия можно выполнить с помощью функции checkid:
void checkid (void)
{int i;
i = curr_lex.value;
if (TID [i].declare) /* описан? */
spush (TID [i].type); /* тип – в стек */
else ERROR(); /* описание отсутствует */
}
Тогда для контроля контекстных условий каждой тройки – «операнд-операция-операнд» будем использовать функцию checkop:
void checkop (void)
{char *op;
char *t1;char *t2;
char *res;
t2 = spop(); /* из стека – тип второго операнда */
op = spop(); /* из стека – обозначение операции */
t1 = spop(); /* из стека – тип первого операнда */
res = gettype (op,t1,t2); /* допустимо ? */
if (strcmp (res, "no")) spush (res); /* да! */
else ERROR(); /* нет! */
}
Для контроля за типом операнда одноместной операции not будем использовать функцию checknot:
void checknot (void)
{ if (strcmp (spop (), "bool")) ERROR();
else spush ("bool");}
Теперь главный вопрос: когда вызывать эти функции?
В грамматике модельного языка задано старшинство операций:
наивысший приоритет имеет операция отрицания, затем в порядке убывания приоритета – группа операций умножения (*, /, and),
группа операций сложения (+,-,or), операции отношения.
E → E1 | E1 [ = | < | > ] E1
E1 → T {[ + | – | or ] T}
37
T → F {[ * | / | and ] F}
F → I | N | [ true | false ] | not F | (E)
Именно это свойство грамматики позволит провести синтаксически-управляемый контроль контекстных условий.
Сравните грамматики, описывающие выражения, состоящие из
символов +, *, (,), i:
G1: E → E+E | E*E | (E) | i G4: E → T | E+T
G2: E → E+T | E*T | T T → F | T*F
T → i | (E) F → i | (E)
G3: E → T+E | T*E | T
G4: E → T | T+E
T → i |(E) T → F | F*T
F → i | (E)
Оцените, насколько они удобны для трансляции выражений.
Правила вывода выражений модельного языка с действиями
для контроля контекстных условий:
E → E1 | E1 [ = | < | > ] < spush (TD [curr_lex.value]) > E1 <checkop() >
E1 → T { [ + | – | or ] < spush (TD [curr_lex.value]) > T < checkop() >}
T → F { [ * | / | and ] < spush (TD [curr_lex.value]) > F < checkop() >}
F → I < checkid() > | N < spush («int») > | [ true | false ] < spush
(«bool») > |
not F < checknot() > | (E)
TD – это таблица ограничителей, к которым относятся и знаки
операций; будем считать, что это массив
#define MAXSIZE_TD 50
char * TD[MAXSIZE_TD];
именно из этой таблицы по номеру лексемы в классе выбираем обозначение операции в виде строки.
Контроль контекстных условий в операторах
S → I: = E | if E then S else E | while E do S | B | read (I) | write (E)
1. Оператор присваивания I: = E
Контекстное условие: в операторе присваивания типы переменной I и выражения E должны совпадать.
В результате контроля контекстных условий выражения E в стеке останется тип этого выражения (как тип результата последней
операции); если при анализе идентификатора I проверить, описан
ли он, и занести его тип в тот же стек (для этого можно использовать
функцию checkid()), то достаточно будет в нужный момент считать
из стека два элемента и сравнить их:
38
void eqtype (void)
{ if (strcmp (spop (), spop ())) ERROR();}
Следовательно, правило для оператора присваивания:
I <checkid()>: = E <eqtype()>
2. Условный оператор и оператор цикла
if E then S else S | while E do S
Контекстные условия: в условном операторе и в операторе цикла в качестве условия возможны только логические выражения.
В результате контроля контекстных условий выражения E в стеке останется тип этого выражения (как тип результата последней
операции); следовательно, достаточно извлечь его из стека и проверить:
void eqbool (void)
{if (strcmp (spop(), "bool")) ERROR();}
Тогда правила для условного оператора и оператора цикла будут
такими:
if E <eqbool()> then S else S | while E <eqbool()> do S
В итоге получаем процедуры для синтаксического анализа методом рекурсивного спуска с синтаксически-управляемым контролем контекстных условий, которые легко написать по правилам
грамматики с действиями.
В качестве примера приведем функцию для нетерминала D (раздел описаний):
#include <string.h>
#define MAXSIZE_TID 1000
#define MAXSIZE_TD 50
char * TD[MAXSIZE_TD];
struct record
{char *name;
int declare;
char *type;
/*... */
};
struct record TID [MAXSIZE_TID];
/* описание функций ERROR(), getlex(), id(), eq(char *),
типа struct lex и переменной curr_lex – в алгоритме
рекурсивного спуска для М-языка */
void ERROR(void);
struct lex {int class; int value;};
39
struct lex curr_lex;
struct lex getlex (void);
int id (void);
int eq (char *s);
void ipush (int i);
int ipop (void);
void decid (int i, char *t)
{if (TID [i].declare) ERROR();
else {TID [i].declare = 1; strcpy (TID [i].type, t);}
}
void dec (char *t)
{int i;
while ((i = ipop()) ! = -1) decid (i,t);}
void D (void)
{ipush (-1);
if (!id()) ERROR();
else {ipush (curr_lex.value);
curr_lex = getlex ();
while (eq (","))
{curr_lex = getlex ();
if (!id ()) ERROR ();
else {ipush (curr_lex.value);
curr_lex = getlex();}
}
if (!eq (":")) ERROR();
else {curr_lex = getlex ();
if (eq ("int")) {curr_lex = getlex ();
dec ("int");}
else if (eq ("bool"))
{curr_lex = getlex();
dec ("bool");}
else ERROR();
}
}
}
Порядок выполнения работы
1. Получить вариант задания у преподавателя.
2. Написать и отладить программу на ЭВМ.
3. Подготовить и защитить отчет.
4. Сдать работающую программу преподавателю.
40
Требования к оформлению отчета
Отчет должен содержать следующие разделы:
Задание по лабораторной работе;
Краткое изложение цели работы;
Запись заданной грамматики входного языка в форме БэкусаНаура;
Множества крайних правых (FIRST) терминальных символов;
Текст программы (оформляется после выполнения программы
на ЭВМ).
Контрольные вопросы
1. Какую роль выполняет синтаксический анализ в процессе
компиляции?
2. Какие типы грамматик существуют? Как связаны типы грамматик и языков?
3. Дайте определение приведенной грамматики, грамматики в
нормальной форме Хомского.
4. Поясните правила построения дерева вывода грамматики.
5. Как вычисляются отношения для грамматик операторного
предшествования?
6. Расскажите о задаче разбора. Что такое распознаватель языка?
7. Расскажите об общих принципах работы распознавателя языка.
8. Что такое перенос, свертка? Для чего необходим алгоритм
«перенос-свертка»?
9. Как работает алгоритм «перенос-свертка» (объясните на своем примере)?
41
Лабораторная работа № 4
ГЕНЕРАЦИЯ И ОПТИМИЗАЦИЯ ОБЪЕКТНОГО КОДА
Цель работы: изучение основных принципов генерации компилятором объектного кода для линейного участка программы, ознакомление с методами оптимизации результирующего объектного
кода с помощью свертки и исключения лишних операций.
Для выполнения лабораторной работы требуется написать программу, которая на основании внутреннего представления (дерева
синтаксического разбора) порождает объектный код и выполняет затем его оптимизацию. В качестве исходного дерева синтаксического
разбора рекомендуется взять дерево, которое порождает программа,
построенная по заданию предыдущей лабораторной работы № 3.
Программу рекомендуется построить из трех основных частей:
первая часть – порождение дерева синтаксического разбора (по результатам лабораторной работы № 3), вторая часть – реализация
алгоритма порождения объектного кода по дереву разбора и третья
часть – оптимизация порожденного объектного кода. Результатом
работы должна быть построенная на основании заданного предложения грамматики программа на объектном языке. В качестве
объектного языка предлагается взять язык ассемблера для процессоров типа Intel 80x86 в реальном режиме (возможен выбор другого
объектного языка по согласованию с преподавателем). Все встречающиеся в исходной программе идентификаторы считать простыми
скалярными переменными, не требующими выполнения преобразования типов. Ограничения на длину идентификаторов и констант
соответствуют требованиям предыдущей лабораторной работы.
Краткие теоретические сведения
В данной работе алгоритм преобразования триад в команды языка ассемблера предлагается разработать самостоятельно. В тривиальном виде такой алгоритм заменяет каждую триаду на последовательность соответствующих команд, а результат ее выполнения
запоминается во временной переменной с некоторым именем (например, TMPi, где i – номер триады). Тогда вместо ссылки на эту
триаду в другой триаде будет подставлено значение этой переменной. Однако алгоритм может предусматривать и оптимизацию временных переменных.
Основные свойства языка внутреннего представления программ:
42
a) он позволяет фиксировать синтаксическую структуру исходной программы;
b) текст на нем можно автоматически генерировать во время
синтаксического анализа;
c) его конструкции должны относительно просто транслироваться в объектный код либо достаточно эффективно интерпретироваться.
Генерация объектного кода – это перевод компилятором внутреннего представления исходной программы в результирующую
объектную программу на языке ассемблера или непосредственно на
машинном языке (машинных кодах).
Генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые
действия по подготовке к генерации кода: распределено адресное
пространство под функции и переменные, проверено соответствие
имен и типов переменных, констант и функций в синтаксических
конструкциях исходной программы и т. д.
Оптимизация программы – это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы. Оптимизация выполняется на этапах подготовки к
генерации и непосредственно при генерации объектного кода.
Лучшие оптимизирующие компиляторы могут получать объектные программы из сложных исходных программ, написанных
на языках высокого уровня, почти не уступающие по качеству программам на языке ассемблера. Временные и трудовые затраты на
создание такой программы существенно меньше, чем при ее реализации на ассемблере. У современных компиляторов существуют
возможности выбора тех или иных критериев оптимизации, исходя из которых оценивается эффективность объектной программы.
Так, с одной стороны, возможна оптимизация с минимизацией размера программы, с другой стороны – оптимизация с увеличением
скорости ее выполнения. При этом не требуется изменять текст
программы на исходном языке.
Все эти преимущества говорят в пользу применения оптимизации. Единственным, но существенным недостатком оптимизации
является необходимость тщательной ее проработки при создании
компилятора. Используемые методы оптимизации ни при каких
условиях не должны приводить к изменению “смысла” исходной
программы (т. е. к таким ситуациям, когда результат выполнения
программы изменяется после ее оптимизации). К сожалению, не
43
все методы оптимизации, используемые создателями компиляторов, могут быть теоретически обоснованы и доказаны для всех
возможных видов исходных программ. Поэтому большинство компиляторов предусматривает возможность отключать те или иные
из возможных методов оптимизации. (Часто при оптимизации
компиляторы выдают предупреждения разработчику программы,
если тот или иной ее участок вызывает подозрения в отношении
правильности его “смысла”). Применение оптимизации также нецелесообразно в процессе отладки исходной программы.
Различаются две основные категории оптимизирующих преобразований:
преобразования исходной программы (в форме ее внутреннего
представления в компиляторе), не зависящие от результирующего
объектного языка;
преобразования результирующей объектной программы.
Последний тип преобразований может зависеть не только от
свойств объектного языка (что очевидно), но и от архитектуры вычислительной системы, на которой будет выполняться результирующая программа. (Так, например, при оптимизации может учитываться объем кэш-памяти и методы организации конвейерных
операций центрального процессора). Этот тип преобразований здесь
рассматриваться не будет. Именно эти преобразования могут повлиять на “смысл” исходной программы. В большинстве случаев они
являются “ноу-хау” производителей компиляторов и строго ориентированы на определенные архитектуры вычислительных машин.
Методы преобразования программы зависят от типов синтаксических конструкций исходного языка. Теоретически разработаны
методы оптимизации для многих типовых конструкций языков
программирования. Далее будут рассмотрены только методы оптимизации линейных участков – они встречаются в любой программе
и составляют существенную часть программного кода.
Линейный участок программы – это выполняемая по порядку последовательность операций, имеющая один вход и один выход. Чаще
всего линейный участок содержит последовательность арифметических операций и операторов присвоения значений переменным.
Прежде чем перейти к вопросам оптимизации линейных участков рассмотрим их внутреннее представление в компиляторе.
Алгоритм генерации объектного кода по дереву вывода
Возможны различные формы внутреннего представления синтаксических конструкций исходной программы в компиляторе.
44
На этапе синтаксического разбора часто используется форма, именуемая деревом вывода (методы его построения рассматривались в
предыдущих лабораторных работах). Но формы представления, используемые на этапах синтаксического анализа, оказываются неудобными в работе при генерации и оптимизации объектного кода.
Поэтому перед оптимизацией и непосредственно генерацией объектного кода внутреннее представление программы преобразуется
в одну из соответствующих форм записи.
Некоторые общепринятые способы внутреннего представления
программ:
префиксная запись;
обратная польская запись операций (постфиксная запись);
тетрады операций;
триады операций;
собственно команды ассемблера;
многоадресный код с явно именуемыми результатами;
многоадресный код с неявно именуемыми результатами;
связные списочные структуры, представляющие синтаксическое дерево.
В основе каждого из этих способов лежит некоторый метод представления синтаксического дерева.
Обратная польская запись – это постфиксная запись операций.
Преимуществом ее является то, что все операции записываются непосредственно в порядке их выполнения. Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек.
Тетрады представляют собой запись операций в форме из четырех составляющих: <операция>(<операнд1>,<операнд2>,<ре
зультат>). Тетрады используются редко, так как требуют больше
памяти для своего представления, чем триады, не отражают взаимосвязи операций и, кроме того, плохо отображаются в команды
ассемблера и машинные коды, так как в наборах команд большинства современных машин не встречаются операции с тремя
операндами.
Триады представляют собой запись операций в форме из трех
составляющих: <операция>(<операнд1>,<операнд2>), при этом
один или оба операнда могут быть ссылками на другую триаду в
том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи
последовательно номеруют для удобства указания ссылок одних
триад на другие. Например, выражение A: = B*C + D – B*10, записанное в виде триад будет иметь вид:
45
1) * ( B, C )
2) + ( ^1, D )
3) * ( B, 10 )
4) - ( ^2, ^3 )
5) : = ( A, ^4 )
Здесь операции обозначены соответствующим знаком (при этом
присвоение также является операцией), а знак ^ означает ссылку
операнда одной триады на результат другой.
Команды ассемблера удобны тем, что при их использовании
внутреннее представление программы полностью соответствует
объектному коду и сложные преобразования не требуются. Однако использование команд ассемблера требует дополнительных
структур для отображения их взаимосвязи. Кроме того, внутреннее представление программы получается зависимым от результирующего кода, а это значит, что при ориентации компилятора на
другой результирующий код потребуется перестраивать как само
внутреннее представление программы, так и методы его обработки
в алгоритмах оптимизации (при использовании триад или тетрад
этого не требуется).
Для построения внутреннего представления объектного кода
(в дальнейшем – просто кода) по дереву вывода может использоваться простейшая рекурсивная процедура. Эта процедура прежде всего должна определить тип узла дерева – он соответствует
типу операции, символ которой находится в листе дерева для текущего узла. Этот лист является средним листом узла дерева для
бинарных операций и крайним левым листом – для унарных операций. После определения типа процедура строит код для узла дерева в соответствии с типом операции. Если все узлы следующего
уровня для текущего узла есть листья дерева, то в код включаются
операнды, соответствующие этим листьям, и получившийся код
становится результатом выполнения процедуры. Иначе процедура должна рекурсивно вызвать сама себя для генерации кода нижележащих узлов дерева и результат выполнения включить в свой
порожденный код.
Поэтому для построения внутреннего представления объектного кода по дереву вывода в первую очередь необходимо разработать
формы представления объектного кода для четырех случаев, соответствующих видам текущего узла дерева вывода:
оба нижележащих узла дерева – листья (терминальные символы
грамматики);
только левый нижележащий узел является листом дерева;
46
только правый нижележащий узел является листом дерева:
оба нижележащих узла не являются листьями дерева.
Рассмотрим построение двух видов внутреннего представления
по дереву вывода:
построение ассемблерного кода по дереву вывода;
построение списка триад по дереву вывода.
Построение ассемблерного кода по дереву вывода
В качестве языка ассемблера возьмем язык ассемблера процессоров типа Intel 80x86. При этом будем считать, что операнды могут быть помещены в 16-разрядные регистры процессора и в коде
результирующей объектной программы могут использоваться регистры AX (аккумулятор) и DX (регистр данных), а также стек для
хранения промежуточных результатов.
Тогда четырем формам текущего узла дерева будут соответствовать следующие фрагменты кода на языке ассемблера (табл. 1):
Таблица 1
Преобразование типовых узлов дерева вывода в код на языке ассемблера
Результирующий код
Вид узла дерева
Узел 1
Узел 1
1
Узел
oper 1
oper 1
1
oper
act
act
act
oper 2
oper 2
2
oper
Узел 1
Узел 1
1
Узел
Операнд 1
Операнд
Операнд 1
1
act
act
act
Узел 2
Узел 2
2
Узел
Узел 1
Узел 1
1
Узел
Узел 2
Узел 2
2
Узел
act
act
act
oper 2
oper 2
2
oper
Узел 1
Узел
Узел 1
1
Узел 2
Узел
Узел 2
2
act
act
act
Узел 3
Узел
Узел 3
3
Примечание
mov ax,oper1 act – команда соответствуюact ax,oper2 щей операции
oper1,oper2 – операнды (листья дерева)
Code(Узел 2) Узел 2 – нижележащий узел
mov dx,ax
(не лист!) дерева
mov ax,oper1 Code(Узел 2) – код, порожact ax,dx
даемый процедурой для нижележащего узла
Code(Узел 2) Code(Узел 2) – код, порожact ax,oper2 даемый процедурой для нижележащего узла
Code(Узел 2)
push ax
Code(Узел 3)
mov dx,ax
pop ax
act ax,dx
Code(Узел 2) – код, порождаемый процедурой для нижележащего узла
Code(Узел 3) – код, порождаемый процедурой для нижележащего узла
push и pop – команды сохранения результатов в стеке и
извлечения результатов из
стека
47
Рассмотрим пример дерева вывода для выражения A: = B*C +
D – B*10 на рис. 3 и соответствующий ему фрагмент кода на языке
ассемблера, построенный по описанным выше правилам (обратите
внимание, что для операции присваивания используется отдельный код, не подпадающий под общие правила).
U1
A
B
:=
U2
U3
-
U4
+
D
*
C
U5
B
*
10
Рис. 3. Дерево вывода для арифметического выражения
Шаг 1. Code(U2)
mov A,ax ;операция присваивания
Шаг 2. Code(U3)
push ax
Code(U5)
mov dx,ax
pop ax
sub ax,dx
mov A,ax ;операция присваивания
Шаг 3. Code(U4)
add ax,D
push ax
Code(U5)
mov dx,ax
pop ax
sub ax,dx
mov A,ax ;операция присваивания
Шаг 4. mov ax,B
mul ax,C
add ax,D
48
push ax
Code(U5)
mov dx,ax
pop ax
sub ax,dx
mov A,ax
;операция присваивания
Шаг 4. mov ax,B
mul ax,C
add ax,D
push ax
mov ax,B
mul ax,10
mov dx,ax
pop ax
sub ax,dx
mov A,ax
;операция присваивания
Полученный объектный код на языке ассемблера, очевидно, может быть оптимизирован, однако для его обработки требуются специальные (ориентированные именно на данный язык ассемблера)
методы и структуры, учитывающие взаимосвязь операций. Кроме
того, ориентация на определенный язык ассемблера сводит на нет
универсальность метода. Так, в приведенном примере, используется команда mul, которая в ранних версиях процессоров фирмы
Intel имеет ограничения на типы операндов, а следовательно, в
универсальном компиляторе не может быть использована так, как
в данном примере. Это потребует, чтобы генерация кода для узлов
дерева шла в зависимости не только от операндов, но и от типа операции (даже в приведенном примере такую зависимость пришлось
установить для операции присваивания).
Обычно подобные проблемы решаются таким образом, что вместо команд непосредственно языка ассемблера используются команды некоторого близкого к нему промежуточного псевдокода.
Большинство этих команд один в один отображаются затем в команды языка ассемблера, другие же однозначно преобразуются в
фиксированную последовательность команд.
Построение списка триад по дереву вывода
Триады являются универсальной, машинно-независимой формой
внутреннего представления в компиляторе результирующей объектной программы, а потому не требуют оговорки дополнительных условий при генерации кода. Триады взаимосвязаны между собой, по49
этому для установки корректной взаимосвязи процедура генерации
кода должна получать также текущий номер i очередной триады.
Тогда четырем формам текущего узла дерева будут соответствовать последовательности триад объектного кода (табл. 2):
Таблица 2
Преобразование типовых узлов дерева вывода
в последовательность триад
Результирующий код
Вид узла дерева
i) act (oper1,
oper2)
Узел
Узел 1
1
oper
oper 1
1
act
act
oper 2
2
oper
Узел 1
Узел 1
1
Узел
oper 1
Операнд 1
1
Операнд
oper 1
Операнд 1
Узел
2
Узел 2
Операнд 1
Узел 2
Узел 2
2
Узел
Узел 2
Узел 2
act
act
act
Узел 1
Узел 1
Узел 1
1
Узел
act
act
act
act
Узел 1
Узел 1
Узел 1
1
Узел
act
act
act
act
Узел 1
Узел 1
act
act
oper 2
Узел 2
2
Узел
oper 2
Узел 2
oper 2
2
oper
Узел 2
oper 2
Узел
3
Узел 3
oper 2
Узел 3
Узел 1
Узел 2
50
act
Узел 3
i) Code(Узел
2,i)
i+j) act(oper1,
^i+j-1)
Примечание
act – тип триады
oper1,oper2 – операнды (листья дерева вывода)
Узел 2 – нижележащий
узел дерева вывода
Code(Узел 2,i) – последовательность триад, порождаемая для Узла 2, начиная с
триады с номером i
j – количество триад, порождаемых для Узла 2
i) Code(Узел Узел 2 – нижележащий
2,i)
узел дерева вывода
i+j) act(^i+j-1, Code(Узел 2,i) – последоваoper2)
тельность триад, порождаемая для Узла 2, начиная с
триады с номером i
j – количество триад, порождаемых для Узла 2
i) Code(Узел Узел 2, Узел 3 – нижележа2,i)
щие узлы дерева вывода
i+j) Code
Code(Узел 2,i) – последова(Узел 3,i+j)
тельность триад, порождаi+j+k)
емая для Узла 2, начиная с
act(^i+jтриады с номером i
1,^i+j+k-1)
j – количество триад, порождаемых для Узла 2
Code(Узел 3,i+j) – последовательность триад, порождаемая для Узла 3, начиная
с триады с номером i+j
k – количество триад, порождаемых для Узла 3
Рассмотрим тот же пример дерева вывода для выражения
A: = B*C + D – B*10 на рис. 4 и соответствующую ему последовательность триад.
U1
A
B
:=
U2
U3
-
U4
+
D
*
C
U5
B
*
10
Рис. 4. Дерево вывода для арифметического выражения
Шаг 1. 1) Code(U2,1)
i) : = (A,^i-1)
Шаг 2. 1) Code(U3,1)
j) Code(U5,j)
i-1) -(^j-1,^i-2)
i) : = (A,^i-1)
Шаг 3. 1) Code(U4,1)
k) +(^k-1,D)
j) Code(U5,j)
i-1) -(^j-1,^i-2)
i) : = (A,^i-1)
Шаг 4. 1) *(B,C)
2) +(^1,D)
3) Code(U5,3)
i-1) -(^j-1,^i-2)
i) : = (A,^i-1)
Шаг 5. 1) *(B,C)
2) +(^1,D)
3) *(B,10)
4) -(^2,^3)
5) : = (A,^4)
Следует обратить внимание, что в данном алгоритме последовательные номера триад (а следовательно, и ссылки на них) устанав51
ливаются не сразу. Это не имеет значение при рекурсивной организации процедуры, но при другом способе обхода дерева вывода в
программе генерации кода лучше увязывать триады между собой
именно по ссылке (указателю), а не по порядковому номеру.
Для триад разработаны универсальные (машинно-независимые)
алгоритмы оптимизации кода. После их выполнения (оптимизации внутреннего представления) триады могут быть преобразованы в команды на языке ассемблера.
Оптимизация объектного кода методом свертки
Свертка объектного кода – это выполнение во время компиляции тех операций исходной программы для которых значения операндов уже известны. Поэтому нет необходимости многократно выполнять их в самой результирующей программе – вполне достаточно один раз выполнить их при ее компиляции.
Простейший вариант свертки – выполнение в компиляторе операций, операндами которых являются константы. Несколько более
сложен процесс определения тех операций, значения которых могут быть известны в результате выполнения других операций. Для
этого служит специальный алгоритм свертки.
Алгоритм свертки работает со специальной таблицей T, которая содержит пары <переменная>-<константа> для всех переменных, значения которых уже известны. Кроме того, алгоритм
свертки помечает те операции во внутреннем представлении программы, для которых в результате свертки уже не требуется генерация кода. Так как при выполнении алгоритма свертки учитывается взаимосвязь операций, то удобной формой представления для
него являются триады, так как в других формах представления
операций (таких как тетрады или команды ассемблера) требуются
дополнительные структуры, чтобы отразить связь результатов одних операций с операндами других.
Алгоритм свертки триад последовательно просматривает триады линейного списка и для каждой триады делает следующее.
1. Если операнд есть переменная, которая содержится в таблице
T, то операнд заменяется на соответствующее значение константы.
2. Если операнд есть ссылка на особую триаду типа C(K,0), то
операнд заменяется на значение константы K.
3. Если все операнды триады являются константами, то триада
может быть свернута. Тогда данная триада выполняется и вместо
нее помещается особая триада вида C(K,0), где K – константа, результат выполнения свернутой триады. (При генерации кода для
52
особой триады объектный код не порождается, а потому она в дальнейшем может быть просто исключена).
4. Если триада является присваиванием типа A: = B, тогда:
если B – константа, то A со значением константы заносится в таблицу T (если там уже было старое значение для A, то это старое
значение исключается);
если B – не константа, то A вообще исключается из таблицы T,
если оно там есть.
Рассмотрим пример выполнения алгоритма.
Пусть фрагмент исходной программы (записанной на языке
типа Паскаль) имеет вид:
I: = 1 + 1;
I: = 3;
J: = 6*I + I;
Ее внутреннее представление в форме триад будет иметь вид:
1) + (1,1);
2) : = (I, ^1);
3) : = (I, 3);
4) * (6, I);
5) + (^4, I);
6) : = (J, ^5).
Процесс выполнения алгоритма свертки можно отразить в табл. 3.
Таблица 3
Пример работы алгоритма свертки
Триада
Шаг 1
1
2
3
4
5
6
Т
C (2, 0)
: = (I, ^1)
: = (I, 3)
* (6, I)
+ (^4, I)
: = (J, ^5)
(,)
Шаг 2
Шаг 3
Шаг 4
C (2, 0)
C (2, 0)
C (2, 0)
: = (I, 2)
: = (I, 2) : = (I, 2)
: = (I, 3)
: = (I, 3) : = (I, 3)
* (6, I)
* (6, I)
C (18, 0)
+ (^4, I)
+ (^4, I)
+ (^4, I)
: = (J, ^5) : = (J, ^5) : = (J, ^5)
(I, 2)
(I, 3)
(I, 3)
Шаг 5
Шаг 6
C (2, 0)
C (2, 0)
: = (I, 2)
: = (I, 2)
: = (I, 3)
: = (I, 3)
C (18, 0)
C (18, 0)
C (21, 0)
C (21, 0)
: = (J, ^5) : = (J, 21)
(I, 3)
(I, 3) (J, 21)
Если исключить особые триады типа C(K,0) (которые не порождают объектного кода), то в результате выполнения свертки получим следующую последовательность триад:
1) : = (I, 2);
2) : = (I, 3);
3) : = (J, 21);
53
Оптимизация объектного кода
методом исключения лишних операций
Определим понятие лишней операции. Операция линейного
участка с порядковым номером i считается лишней, если существует
более ранняя идентичная ей операция с порядковым номером j и никакая переменная, от которой зависит эта операция, не изменялась
никакой третьей операций, имеющей порядковый номер между i и j.
Алгоритм исключения лишних операций просматривает операции в порядке их следования. Так же, как и алгоритму свертки, алгоритму исключения лишних операций проще всего работать с триадами, потому что они полностью отражают взаимосвязь операций.
Чтобы следить за внутренней зависимостью переменных и триад
алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам:
изначально для каждой переменной ее число зависимости равно
0, так как в начале работы программы значение переменной не зависит ни от какой триады;
после обработки i-й триады, в которой переменной A присваивается некоторое значение, число зависимости A (dep(A)) получает
значение i, так как значение A теперь зависит от данной i-й триады;
при обработке i-й триады ее число зависимости (dep(i)) принимается равным значению 1+(максимальное из чисел зависимости
операндов).
Таким образом, при использовании чисел зависимости триад и
переменных можно утверждать, что если i-я триада идентична j-й
триаде (j<i), то i-я триада считается лишней в том и только в том
случае, когда dep(i) = dep(j).
Алгоритм исключения лишних операций использует в своей работе также особого вида триады SAME(j,0), которые означают, что
некоторая триада i идентична триаде j.
Алгоритм исключения лишних операций последовательно просматривает триады линейного участка. Он состоит из следующих
шагов, выполняемых для каждой триады:
1) если операнд ссылается на особую триаду вида SAME(j,0), то
он заменяется на ссылку на триаду с номером j (^j);
2) вычисляется число зависимости текущей триады с номером i,
исходя из чисел зависимости ее операндов;
3) если существует идентичная j-я триада, причем j<i и dep(i)
= dep(j), то текущая триада i заменяется на триаду особого вида
SAME(j,0);
54
4) если текущая триада есть присвоение, то вычисляется число
зависимости соответствующей переменной.
Рассмотрим работу алгоритма на примере:
D: = D + C*B;
A: = D + C*B;
C: = D + C*B;
Этому фрагменту программы будет соответствовать следующая
последовательность триад:
1) * (C, B)
2) + (D, ^1)
3) : = (D, ^2)
4) * (C, B)
5) + (D, ^4)
6) : = (A, ^5)
7) * (C, B)
8) + (D, ^7)
9) : = (C, ^8)
Работу алгоритма отобразим в табл. 4.
Таблица 4
Пример работы алгоритма исключения лишних операций
Обрабатываемая
триада i
1) * (C, B)
2) + (D, ^1)
3): = (D, ^2)
4) * (C, B)
5) + (D, ^4)
6): = (A, ^5)
7) * (C, B)
8) + (D, ^7)
9): = (C, ^8)
Числа зависимости
переменных
A
B
C
D
0
0
0
0
0
6
6
6
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
3
3
3
3
3
3
3
Числа зависимости
триад dep(i)
1
2
3
1
4
5
1
4
5
Триады, полученные
после выполнения
алгоритма
1) * (C, B)
2) + (D, ^1)
3): = (D, ^2)
4) SAME (1, 0)
5) + (D, ^1)
6): = (A, ^5)
7) SAME (1, 0)
8) SAME (5, 0)
9): = (C, ^5)
Теперь, если исключить триады особого вида SAME(j,0), то в
результате выполнения алгоритма получим следующую последовательность триад:
1) * (C, B)
2) + (D, ^1)
55
3) : = (D, ^2)
4) + (D, ^1)
5) : = (A, ^4)
6) : = (C, ^4)
Обратите внимание, что в итоговой последовательности изменилась нумерация триад и номера в ссылках одних триад на другие.
Если в программе компилятора в качестве ссылок использовать не
номера триад, а непосредственно указатели на них, то изменение
ссылок в таком варианте не потребуется.
Общий алгоритм генерации и оптимизации
объектного кода
Теперь рассмотрим общий вариант алгоритма генерации кода,
который получает на входе дерево вывода (построенное в результате синтаксического разбора) и создает по нему фрагмент объектного кода линейного участка результирующей программы.
Алгоритм должен выполнить следующую последовательность
действий:
построить последовательность триад на основе дерева вывода;
выполнить оптимизацию кода методом свертки;
выполнить оптимизацию кода методом исключения лишних
операций;
преобразовать последовательность триад в последовательность
команд на языке ассемблера (полученная последовательность команд и будет результатом выполнения алгоритма).
Алгоритм преобразования триад в команды языка ассемблера
– это единственная машинно-зависимая часть общего алгоритма.
При преобразовании компилятора для работы с другим результирующим объектным кодом потребуется изменить только эту часть,
при этом все алгоритмы оптимизации и внутреннее представление
программы останутся неизменными.
В данной работе алгоритм преобразования триад в команды языка ассемблера предлагается разработать самостоятельно. В тривиальном виде такой алгоритм заменяет каждую триаду на последовательность соответствующих команд, а результат ее выполнения
запоминается во временной переменной с некоторым именем (например, TMPi, где i – номер триады). Тогда вместо ссылки на эту
триаду в другой триаде будет подставлено значение этой переменной. Однако алгоритм может предусматривать и оптимизацию временных переменных.
56
Генерация внутреннего представления программ
(интерпретатор)
Результатом работы синтаксического анализатора должно быть
некоторое внутреннее представление исходной цепочки лексем, которое отражает ее синтаксическую структуру. Программа в таком
виде в дальнейшем может либо транслироваться в объектный код,
либо интерпретироваться.
Чаще всего синтаксическим деревом называют дерево вывода
исходной цепочки, в котором удалены вершины, соответствующие
цепным правилам вида A → B, где A, B Î VN.
Выберем в качестве языка для представления промежуточной
программы постфиксную запись (ее часто называют ПОЛИЗ –
польская инверсная запись). В ПОЛИЗе операнды выписаны слева
направо в порядке их использования. Знаки операций стоят таким
образом, что знаку операции непосредственно предшествуют ее
операнды. Например, обычной (инфиксной) записи выражения
a*(b+c)–(d–e)/f
соответствует такая постфиксная запись:
abc+*de–f/–
Обратите внимание на то, что в ПОЛИЗе порядок операндов
остался таким же, как и в инфиксной записи, учтено старшинство
операций, а скобки исчезли.
Более формально постфиксную запись выражений можно определить таким образом:
1) если Е является единственным операндом, то ПОЛИЗ выражения Е – это этот операнд;
2) ПОЛИЗом выражения Е1 θ Е2, где θ – знак бинарной операции, Е1 и Е2 операнды для θ, является запись E1’ E2’ θ, где E1’ и
E2’ – ПОЛИЗ выражений Е1 и Е2 соответственно;
3) ПОЛИЗом выражения θ E, где θ – знак унарной операции, а
Е – операнд θ, является запись E’ θ, где E’ – ПОЛИЗ выражения Е;
4) ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.
Запись выражения в такой форме очень удобна для последующей
интерпретации (т. е. вычисления значения этого выражения) с помощью стека: выражение просматривается один раз слева направо,
при этом:
если очередной элемент ПОЛИЗа – это операнд, то его значение
заносится в стек;
если очередной элемент ПОЛИЗа – это операция, то на «верхушке» стека сейчас находятся ее операнды (это следует из определе57
ния ПОЛИЗа и предшествующих действий алгоритма); они извлекаются из стека, над ними выполняется операция, результат снова
заносится в стек;
когда выражение, записанное в ПОЛИЗе, прочитано, в стеке
останется один элемент – это значение всего выражения.
Для интерпретации, кроме ПОЛИЗа выражения, необходима дополнительная информация об операндах, хранящаяся в таблицах.
Может оказаться так, что знак бинарной операции по написанию совпадает со знаком унарной; например, знак «-» в большинстве языков программирования означает и бинарную операцию
вычитания, и унарную операцию изменения знака. В этом случае
во время интерпретации операции «-» возникнет неоднозначность:
сколько операндов надо извлекать из стека и какую операцию выполнять. Устранить неоднозначность можно, по крайней мере, двумя способами:
a) заменить унарную операцию бинарной, т. е. считать, что «-а»
означает «0-а»;
b) либо ввести специальный знак для обозначения унарной операции; например, «-а» заменить на «&a». Важно отметить, что это
изменение касается только внутреннего представления программы
и не требует изменения входного языка.
Теперь необходимо разработать ПОЛИЗ для операторов входного языка. Каждый оператор языка программирования может быть
представлен как n-местная операция с семантикой, соответствующей семантике этого оператора. Оператор присваивания
I: = E
в ПОЛИЗе будет записан как
I E: =
где ": = " – это двухместная операция, а I и Е – ее операнды; I означает, что операндом операции ": = " является адрес переменной I,
а не ее значение.
Оператор перехода в терминах ПОЛИЗа означает, что процесс
интерпретации надо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было
ссылаться на элементы ПОЛИЗа, будем считать, что все они перенумерованы, начиная с 1 (допустим, занесены в последовательные
элементы одномерного массива).
Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператор перехода goto L в ПОЛИЗе можно записать как
p!, где ! – операция выбора элемента ПОЛИЗа, номер которого равен p.
58
Немного сложнее окажется запись в ПОЛИЗе условных операторов и операторов цикла.
Введем вспомогательную операцию – условный переход «по
лжи» с семантикой
if (not B) then goto L
Это двухместная операция c операндами B и L. Обозначим ее !F,
тогда в ПОЛИЗе она будет записана как B p !F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.
Семантика условного оператора
if B then S1 else S2
с использованием введенной операции может быть описана так:
if (not B) then goto L2; S1; goto L3; L2: S2; L3:...
Тогда ПОЛИЗ условного оператора будет таким:
B p2 !F S1 p3 ! S2...,
где pi – номер элемента, с которого начинается ПОЛИЗ оператора,
помеченного меткой Li, i = 2,3.
Семантика оператора цикла while B do S может быть описана
так:
L0: if (not B) then goto L1; S; goto L0; L1:....
Тогда ПОЛИЗ оператора цикла while будет таким:
B p1 !F S p0 !...,
где pi – номер элемента, с которого начинается ПОЛИЗ оператора,
помеченного меткой Li, i = 0,1.
Операторы ввода и вывода М-языка являются одноместными
операциями.
Пусть R – обозначение операции ввода, W – обозначение операции вывода. Тогда оператор ввода read (I) в ПОЛИЗе будет записан как I R; оператор вывода write (E) – как E W.
Постфиксная польская запись операторов обладает всеми свойствами, характерными для постфиксной польской записи выражений, поэтому алгоритм интерпретации выражений пригоден для
интерпретации всей программы, записанной на ПОЛИЗе (нужно
только расширить набор операций; кроме того, выполнение некоторых из них не будет давать результата, записываемого в стек).
Постфиксная польская запись может использоваться не только
для интерпретации промежуточной программы, но и для генерации по ней объектной программы. Для этого в алгоритме интерпретации вместо выполнения операции нужно генерировать соответствующие команды объектной программы.
59
Синтаксически управляемый перевод
На практике синтаксический, семантический анализ и генерация внутреннего представления программы часто осуществляются
одновременно. Существует несколько способов построения промежуточной программы. Один из них, называемый синтаксически
управляемым переводом, особенно прост и эффективен.
В основе синтаксически управляемого перевода лежит уже известная нам грамматика с действиями (см. раздел о контроле контекстных условий). Теперь, параллельно с анализом исходной цепочки лексем, будем выполнять действия по генерации внутреннего представления программы. Для этого дополним грамматику
вызовами соответствующих процедур генерации.
Содержательный пример – генерация внутреннего представления программы для М-языка – приведен ниже, а здесь в качестве
иллюстрации рассмотрим более простой пример.
Пусть есть грамматика, описывающая простейшее арифметическое выражение:
E → T {+T}
T → F {*F}
F → a | b | (E)
Тогда грамматика с действиями по переводу этого выражения в
ПОЛИЗ будет такой:
E → T {+T <putchar('+')>}
T → F {*F <putchar('*')>}
F → a <putchar('a')> | b<putchar('b')> | (E)
Этот метод можно использовать для перевода цепочек одного
языка в цепочки другого языка (что, собственно, мы и делали, занимаясь переводами в ПОЛИЗ цепочек лексем).
Например, с помощью грамматики с действиями выполним перевод цепочек языка
L1 = {0n1m | n> = 0, m>0}
в соответствующие цепочки языка
L2 = {ambn | n> = 0, m>0}:
Язык L1 можно описать грамматикой
S → 0S | 1A
A → 1A |ε
Вставим действия по переводу цепочек вида 0n1m в соответствующие цепочки вида ambn:
60
S → 0S <putchar('b')> | 1 <putchar('a')> A
A → 1 <putchar('a')> A |ε
Теперь при анализе цепочек языка L1 с помощью действий будут порождаться соответствующие цепочки языка L2.
Генератор внутреннего представления
программы на М-языке
Каждый элемент в ПОЛИЗе – это лексема, т. е. пара вида (номер_
класса, номер_в_классе). Нам придется расширить набор лексем:
1) будем считать, что новые операции (!, !F, R, W) относятся
к классу ограничителей, как и все другие операции модельного
языка;
2) для ссылок на номера элементов ПОЛИЗа введем лексемы класса 0, т. е. (0,p) – лексема, обозначающая p-й элемент в
ПОЛИЗе;
3) для того чтобы различать операнды-значения-переменных
и операнды-адреса-переменных (например, в ПОЛИЗе оператора
присваивания), операнды-значения будем обозначать лексемами
класса 4, а для операндов-адресов введем лексемы класса 5.
Будем считать, что генерируемая программа размещается в массиве P, переменная free – номер первого свободного элемента в этом
массиве:
#define MAXLEN_P 10000
struct lex
{int class;
int value;}
struct lex P [ MAXLEN_P];
int free = 0;
Для записи очередного элемента в массив P будем использовать
функцию put_lex:
void put_lex (struct lex l)
{P[ free++] = l;}
Кроме того, введем модификацию этой функции – функцию
put_lex5, которая записывает лексему в ПОЛИЗ, изменяя ее класс
с 4-го на 5-й (с сохранением значения поля value):
void put_lex5 (struct lex l)
{ l.class = 5; P[ free++] = l;}
Пусть есть функция
struct lex make_op(char *op),
61
которая по символьному изображению операции op находит в таблице ограничителей соответствующую строку и формирует лексему вида (2, i), где i – номер найденной строки.
Генерация внутреннего представления программы будет проходить во время синтаксического анализа параллельно с контролем
контекстных условий, поэтому для генерации можно использовать
информацию, «собранную» синтаксическим и семантическим анализаторами; например, при генерации ПОЛИЗа выражений можно
воспользоваться содержимым стека, с которым работает семантический анализатор.
Кроме того, можно дополнить функции семантического анализа
действиями по генерации:
void checkop_p (void)
{char *op; char *t1; char *t2; char *res;
t2 = spop(); op = spop(); t1 = spop();
res = gettype (op,t1,t2);
if (strcmp (res, "no"))
{spush (res);
put_lex (make_op (op));} /* дополнение! – операция
op заносится в ПОЛИЗ */
else ERROR();
}
Тогда грамматика, содержащая действия по контролю контекстных условий и переводу выражений модельного языка в ПОЛИЗ, будет такой:
E → E1 | E1 [ = | > | < ] < spush (TD [curr_lex.
value]) > E1< checkop_p() >
E1 → T { [ + | – | or] < spush (TD [curr_lex.value])
>T < checkop_p() >}
T → F { [ * | / | and] < spush (TD [curr_lex.value])
>F < checkop_p() >}
F → I < checkid(); put_lex (curr_lex) > | N <
spush("int"); put_lex (curr_lex) > |
[ true | false ] < spush ("bool"); put_lex (curr_lex)
> |not F < checknot(); put_lex (make_op ("not")) > |
(E)
Действия, которыми нужно дополнить правило вывода оператора присваивания, также достаточно очевидны:
S → I < checkid(); put_lex5 (curr_lex) >: =
E < eqtype(); put_lex (make_op (“: = “)) >
62
При генерации ПОЛИЗа выражений и оператора присваивания
элементы массива P заполнялись последовательно. Семантика условного оператора if E then S1 else S2 такова, что значения операндов для операций безусловного перехода и перехода «по лжи» в момент генерации операций еще неизвестны:
if (!E) goto l2; S1; goto l3; l2: S2; l3:...
Поэтому придется запоминать номера элементов в массиве P, соответствующих этим операндам, а затем, когда станут известны их
значения, заполнять пропущенное.
Пусть есть функция
struct lex make_labl (int k),
которая формирует лексему-метку ПОЛИЗа вида (0,k).
Тогда грамматика, содержащая действия по контролю контекстных условий и переводу условного оператора модельного языка в
ПОЛИЗ, будет такой:
S → if E < eqbool(); pl2 = free++; put_lex (make_op
("!F")) >
then S < pl3 = free++; put_lex (make_op ("!"));
P[pl2] = make_labl (free) >
else S < P[pl3] = make_lable (free) >
Переменные pl2 и pl3 должны быть локализованы в процедуре
S, иначе возникнет ошибка при обработке вложенных условных
операторов.
Аналогично можно описать способ генерации ПОЛИЗа других
операторов модельного языка.
Интерпретатор ПОЛИЗа для М-языка
Польская инверсная запись была выбрана нами в качестве языка внутреннего представления программы, в частности, потому,
что записанная таким образом программа может быть легко проинтерпретирована.
Идея алгоритма очень проста: просматриваем ПОЛИЗ слева
направо; если встречаем операнд, то записываем его в стек; если
встретили знак операции, то извлекаем из стека нужное количество операндов и выполняем операцию, результат (если он есть) заносим в стек и т. д.
Итак, программа на ПОЛИЗе записана в массиве P; пусть она состоит из N элементов-лексем. Каждая лексема – это структура
struct lex {int class; int value;},
63
возможные значения поля class:
0 – лексемы-метки (номера элементов в ПОЛИЗе);
1 – логические константы true либо false (других лексем – служебных слов в ПОЛИЗе нет);
2 – операции (других лексем-ограничителей в ПОЛИЗе нет);
3 – целые константы;
4 – лексемы-идентификаторы (во время интерпретации будет
использоваться значение);
5 – лексемы-идентификаторы (во время интерпретации будет
использоваться адрес).
Считаем, что к моменту интерпретации распределена память
под константы и переменные, адреса занесены в поле address таблиц TID и TNUM, значения констант размещены в памяти.
В программе-интерпретаторе будем использовать некоторые переменные и функции, введенные нами ранее.
void interpreter(void) {
int *ip;
int i, j, arg;
for (i = 0; i< = N; i++)
{curr_lex = P[i];
switch (curr_lex.class) {
case 0: ipush (curr_lex.value); break;
/* метку ПОЛИЗа – в стек */
case 1: if (eq ("true")) ipush (1);
else ipush (0); break;
/* логическое значение – в стек */
case 2: if (eq ("+")) {ipush (ipop() + ipop()); break};
/* выполнили операцию сложения, результат – в стек*/
if (eq ("-"))
{arg = ipop(); ipush (ipop() – arg); break;}
/* аналогично для других двухместных арифметических
и логических операций */
if (eq ("not")) {ipush (!ipop()); break;};
if (eq ("!")) {j = ipop(); i = j-1; break;};
/* интерпретация будет продолжена с j-го элемента
ПОЛИЗа */
if (eq ("!F")) {j = ipop(); arg = ipop();
if (!arg) {i = j-1}; break;};
/* если значение arg ложно, то интерпретация будет
продолжена с j -го элемента ПОЛИЗа, иначе порядок не
изменится */
64
if (eq (": = ")) {arg = ipop(); ip = (int*)ipop();
*ip = arg; break;};
if (eq ("R")) {ip = (int*) ipop();
scanf(“%d”, ip); break;};
/* “R” – обозначение операции ввода */
if (eq ("W")) {arg = ipop();
printf (“%d”, arg); break;};
/* “W” – обозначение операции вывода */
case 3: ip = TNUM [curr_lex.value].address;
ipush(*ip); break;
/* значение константы – в стек */
case 4: ip = TID [curr_lex.value].address;
ipush(*ip); break;
/* значение переменной – в стек */
case 5: ip = TID [curr_lex.value].address;
ipush((int)ip); break;
/* адрес переменной – в стек */
} /* конец switch */
} /* конец for */
}
Порядок выполнения работы
1. Получить вариант задания у преподавателя.
2. Изучить алгоритм генерации объектного кода по дереву синтаксического разбора.
3. Разработать фрагменты объектного кода, реализующие на
языке ассемблера простейшие операции в заданной грамматике.
4. Выполнить генерацию объектного кода вручную для выбранного простейшего примера. Проверить корректность результата.
5. Изучить алгоритмы оптимизации результирующего кода методом свертки и методом исключения лишних операций.
6. Вместо пп. 3-4 выбрать в качестве внутреннего представления
программы ПОЛИЗ и написать программу-интерпретатор с ПОЛИЗ.
7. Подготовить и защитить отчет.
8. Написать и отладить программу на ЭВМ.
9. Сдать работающую программу преподавателю.
Требования к оформлению отчета
Отчет должен содержать следующие разделы:
задание по лабораторной работе;
краткое изложение цели работы;
65
запись заданной грамматики входного языка в форме Бэкуса-Наура;
фрагменты объектного кода на языке ассемблера для операций
заданной грамматики;
простейший пример генерации кода по дереву синтаксического
разбора;
текст программы (оформляется после выполнения программы
на ЭВМ).
Контрольные вопросы
1. Что такое транслятор, компилятор и интерпретатор? Расскажите об общей структуре компилятора.
2. Как строится дерево вывода (синтаксического разбора)? Какие исходные данные необходимы для его построения?
3. Объясните работу алгоритма генерации объектного кода по
дереву синтаксического разбора.
4. За счет чего обеспечивается возможность генерации кода на
разных объектных языках по одному и тому же дереву?
5. Какую роль выполняет генерация объектного кода в процессе
компиляции?
3. Какие данные необходимы компилятору для генерации объектного кода? Какие действия выполняет компилятор перед генерацией?
4. Дайте определение понятию оптимизации программы. Для
чего используется оптимизация?
5. Какие существуют методы оптимизации объектного кода?
6. Что такое триады и для чего они используются? Какие еще существуют методы для представления объектных команд?
7. Объясните работу алгоритма свертки.
8. Что такое лишняя операция? Что такое “число зависимости”?
9. Объясните работу алгоритма исключения лишних операций.
ВАРИАНТЫ ЗАДАНИЙ
Для всех вариантов задаётся общая часть в которую входит следующее. Ключевые слова, обозначающие начало и конец программы, описание типа, ввод и вывод, присваивание, true, false.
Разделители: +, -, _, (,), =, <, >,,;,”, “, ‘,’ и пробел.
Идентификаторы должны начинаться с буквы, не включать в
себя разделители, количество позиций не должно превышать 14.
x, y, z – условные обозначения переменных. Разрешается заменять их другими идентификаторами. Все начальные присвоения
дописать, если необходимо.
66
Текст программы должен допускать использование комментариев. Вариант задания выбирается по согласованию с преподавателем. Язык реализации студент выбирает самостоятельно.
Контекстные условия:
1) любое имя, используемое в программе, должно быть описано
и только один раз;
2) в операторе присваивания типы переменной и выражения
должны совпадать;
3) в условном операторе и в операторе цикла в качестве условия
возможно только логическое выражение;
4) операнды операции отношения должны быть целочисленными;
5) тип выражения и совместимость типов операндов в выражении определяются по обычным правилам; старшинство операций
задано синтаксисом. В любом месте программы, кроме идентификаторов, служебных слов и чисел, может находиться произвольное
число пробелов и комментариев вида {< любые символы, кроме } и
^(символ конца текста исходной программы)>}.
True, false, read и write – служебные слова (их нельзя переопределять, как стандартные идентификаторы Паскаля). Сохраняется
паскалевское правило о разделителях между идентификаторами,
числами и служебными словами.
1) PROGRAMM;
integer x;
bool y;
integer z;
x = 3;
y = true;
z = (x+2) – (x+convert(y,’integer’));
FUNC convert(bool y, integer s);
ENDF;
END;
2) PROGRAMM;
float x;
integer y;
integer z;
x = 3.25;
y = 5;
  z = (3+2) – (y+convert(x,’integer’));
 FUNC convert(float y, integer s);
 ENDF;
 END;
67
Рекомендуемая литература
1. Хантер Р. Проектирование и конструирование компиляторов, М., 1984.
2. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. М., 2011.
3. Льюис Ф. и др. Теоретические основы построения компиляторов. М., 1979.
4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М., 1978.
5. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М., 1975.
6. Мартыненко Б. К. Формальные грамматики и языки. Элементы теории трансляции. 2008.
7. Волкова И. А., Руденко Т. В. Формальные грамматики и языки. Элементы теории трансляции. М., 1999.
СОДЕРЖАНИЕ
Общие теоретические положения....................................................
Лабораторная работа № 1. Разработка грамматики заданного языка....
Лабораторная работа № 2. Работа с таблицей символов. Проектирование лексического анализатора.....................................................
Лабораторная работа № 3. Синтаксический и семантический анализ.
Лабораторная работа № 4. Генерация и оптимизация объектного кода..
Варианты заданий.........................................................................
Рекомендуемая литература............................................................
68
3
6
14
42
66
68
Документ
Категория
Без категории
Просмотров
1
Размер файла
1 549 Кб
Теги
prokofiev
1/--страниц
Пожаловаться на содержимое документа