О4оо и направлению 5528оо 2Рыбинск 21995. Ббк 32. 973 П-32

 2по высшему образованию

 2технологическая академия

 2В.Н. ПИНАЕВ
 2ФОРМАЛЬНЫЕ МЕТОДЫ ОПИСАНИЯ ЯЗЫКОВ
 2ПРОГРАММИРОВАНИЯ И ПОСТРОЕНИЕ ТРАНСЛЯТОРОВ
конспект лекций

Рекомендовано Учебно-методи-

ческим объединением высших учеб-

ных заведений Российской Федера-

ции по образованию в области ави-

ации, ракетостроения и космоса в

качестве учебного пособия для

студентов высших технических за-

ведений, обучающихся по специаль-

ности 22О4ОО и направлению 5528ОО

 2Рыбинск

 21995

ББК 32.973

П-32

УДК 681.3.О6

рования и построение трансляторов: Конспект лекций/ РГАТА. -

Рыбинск, 1995. - 84 с.
Рассматриваются формальные методы описания синтаксиса

языков программирования, а также принципы построения трансля-

торов. Описывается аппарат формальных грамматик, приводится их

классификация по Хомскому. Обсуждаемые алгоритмы отдельных фаз

трансляции приводятся в виде фрагментов программ или процедур

на языке Паскаль.

Пособие предназначено для студентов, обучающихся по спе-

циальности "220400 - Программное обеспечение вычислительной

техники и автоматизированных систем" или по направлению

"552800 - Информатика и вычислительная техника".

Ил. 17 Табл. 7 Библиогр. 16
Рецензенты:

кафедра информатики и вычислительной техники

Ярославского государственного педагогического

университета;

доктор физ.-мат. наук, профессор И.Л.Братчиков

ISBN 5-88435-О22-8 C Пинаев В.Н., 1995

авиационная технологическая

академия, 1995

.
- 3 -

 2ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 5
1. ТРАНСЛЯТОРЫ, КОМПИЛЯТОРЫ, ИНТЕРПРЕТАТОРЫ 8

1.1. Основные определения 8

1.2. Программно-моделируемые вычислительные машины 9

1.3. Выбор языка реализации 12

1.4. Краткий обзор процесса компиляции 14

1.5. Понятие о проходах 17

2.1. Определения и общие свойства порождающих грамматик 18

2.2. Классификация грамматик 22
3. ВЫВОД ЦЕПОЧЕК 24

3.1. Задача разбора 24

3.2. Дерево разбора 25

3.3. Классификация методов разбора 28

4.1. Регулярные выражения 29

4.2. Конечные автоматы 30

4.3. Лексический анализатор 32

4.4. Пример сканера для языка PL/0 34

4.5. Выход из лексического анализатора 38

.
- 4 -

7.1. Безвозвратный анализ по первому символу 44

7.2. Грамматики и синтаксические диаграммы 47

7.3. Определение LL-грамматик 48

7.4. Таблично-управляемый анализатор для LL(1)-грамматик 49
8. ВОСХОДЯЩИЕ МЕТОДЫ АНАЛИЗА 53

8.1. LR - грамматики 53

8.2. LR-таблицы разбора 53

8.3. Грамматики простого предшествования 55

8.4. Анализатор предшествования 57
9. ГЛОБАЛЬНЫЙ АНАЛИЗАТОР 60
10. ОБРАБОТКА ОШИБОК 63

10.1. Синтаксические ошибки 63

10.2. Контекстные ошибки 65
11. ГЕНЕРАЦИЯ КОДА 66

11.1. Интерпретатор Р-кода 67

11.2. Описание команд Р-кода 71
ЗАКЛЮЧЕНИЕ 75
ЛИТЕРАТУРА 76
ПРИЛОЖЕНИЕ 1. Программа LR-анализатора 77

ПРИЛОЖЕНИЕ 2. Синтаксические диаграммы языка PL/0 82

.
- 5 -
 2ВВЕДЕНИЕ
В настоящее время в мире насчитывается свыше тысячи язы-

ков программирования. Однако язык останется мертворожденным,

если он не будет реализован на ЭВМ. Исключение могут состав-

лять языки, предназначенные для проведения каких-либо формаль-

ных исследований.

Реализация языка означает разработку и использование спе-

циальной программы,"понимающей" тексты на этом языке. Такая

программа называется  2транслятором 0. Для начинающего програм-

миста написание транслятора - большая и сложная работа. А так

как в практических приложениях часто возникает потребность в

своем, возможно, не очень сложном, но чрезвычайно удобном для

вас языке, то понятно, как важно уметь ориентироваться в воп-

росах разработки и реализации трансляторов. Примерами таких

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

языки управления некими объектами, различные препроцессоры.

Даже выбранная форма и структура входных данных для какой-либо

вашей программы по существу является неким языком.

Одновременно возникает актуальная до настоящего времени

задача представления (то есть - описания) языка программирова-

ния. Такое описание необходимо и для тех, кто желает узнать и

понять новый язык, и для тех, кто разрабатывает транслятор

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

так как только аккуратное формальное описание языка программи-

рования позволит избежать различных трактовок его конструкций,

а, следовательно, и их смысла.

Значимость описания полезна еще и по другой причине. Лю-

бой формализм позволяет перейти на более высокий уровень

абстракции, охватывающий уже гораздо больше конкретных вариан-

тов, один из которых и служит толчком к этой абстракции. Вот

что сказал Эдсгер В. Дейкстра 14 августа 1972 года в речи при

вручении ему премии Тьюринга: "... наиболее важным видом дея-

тельности компетентного программиста можно считать эффективную

эксплуатацию его способности к абстрагированию. ... Какие

последствия может иметь знание и сознательное использование

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

что если бы это было известно 15 лет тому назад, то, например,

шаг от БНФ к синтаксически ориентированным компиляторам занял

бы несколько минут вместо нескольких лет".

Различное понимание читателями одного и того же текста

типично для естественных языков. Да и сам по себе используемый

язык может быть многозначным. Вот один из примеров: "Он встре-

тил ее на поляне с цветами". Здесь возможны сразу три интерп-

ретации. Чтобы преодолеть подобные трудности, автор текста вы-

нужден специальным образом оговаривать использование тех или

иных слов или словосочетаний, дублировать основную мысль ка-

ким-либо способом. Последнее приводит к разрастанию текста в

целом и, следовательно, к затруднению его восприятия. Примером

такого разрастания может служить и настоящий абзац. ( Впрочем,

не исключено, что это разрастание и естественная многознач-

ность русского языка могли привести к тому, что читатель не

смог понять излагаемой здесь автором идеи.)

Итак, наличие формального описания языка программирования

снижает вероятность его неверного толкования и позволяет авто-

матизировать (до некоторой степени) разработку соответствующе-

го транслятора.

Традиционно описание языка состоит из описания его лекси-

ческих, синтаксических и семантических свойств. Для первых

двух составляющих разработаны соответствующие формализмы. Су-

ществуют методы и для описания семантики, но их формальное

применение при разработке транслятора представляется достаточ-

но затруднительным.

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

рекомендуется освоить главу 5 "Структура языков и транслято-

ров" в книге Никлауса Вирта "Алгоритмы + структуры данных =

программы" [3]. Кстати, обратите внимание, выпущено два изда-

ния этой книги. Первое основано на языке ПАСКАЛЬ, а второе

использует язык МОДУЛА-2. Во втором издании нет упомянутой

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

глубже заинтересуется теорией формальных языков и методами

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

ратурой [1,2,4,6-11]. Автор считает необходимым отметить, что

при подготовке данного текста существенно использовались пере-

численные издания.

Основная цель подготовки данного пособия заключалась в

том, чтобы собрать вместе теоретический материал и примеры

практических реализаций так, чтобы начинающий программист мог

использовать их в своей работе. Хотя по теории трансляции и

существует хорошая литература, но, во-первых, она недоступна

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

библиотеках, и, во-вторых, нет краткого варианта курса, соче-

тающего и теоретические, и практические аспекты обсуждаемых

вопросов. Поэтому автор, не претендуя на оригинальность

текста, надеется, что его труд окажется полезным.

Пособие предназначено для студентов, обучающихся по спе-

циальности "220400 - Программное обеспечение вычислительной

техники и автоматизированных систем" или по направлению

"552800 - Информатика и вычислительная техника". Излагаемый

материал может использоваться в курсах "Построение транслято-

ров", "Теоретические основы систем программирования", "Основы

теории вычислительных процессов и структур", "Трансляция язы-

ков программирования". От читателя требуются знания по курсам

"Дискретная математика" и "Конструирование программ и языки

программирования", так как отдельные алгоритмы иллюстрируются

на языке ПАСКАЛЬ.

Автор благодарен своему научному руководителю и рецензен-

ту Братчикову Игорю Леонидовичу, заведующему лабораторией ка-

федры МПОЭВС Ефимову Евгению Владимировичу, а также всем чле-

нам кафедры за полезные советы по устранению многих шерохова-

тостей и изъянов в изложении материала.

.
- 8 -

 21. ТРАНСЛЯТОРЫ, КОМПИЛЯТОРЫ, ИНТЕРПРЕТАТОРЫ
 21.1. Основные определения
Мы начнем изложение материала с уточнения некоторых поня-

тий [7]. Под вычислительной машиной в самом общем виде понима-

ется устройство для хранения алгоритмов и структур данных и

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

представлено это устройство, можно говорить либо о реальной

физической конструкции, либо о некой гипотетической или вирту-

альной машине. Последняя может не иметь ни микросхем, ни кабе-

лей, ни других деталей. Тогда предполагается, что такая машина

представлена в программно-моделируемом виде.

Любая вычислительная машина содержит в себе устройство

для исполнения команд. Это устройство должно определить оче-

редную команду, выполнить соответствующие ей действия и подго-

товиться к приему следующей команды. Результат работы програм-

мы определяется конечным состоянием машины.

Из сказанного следует важный вывод: машинный язык - это

необязательно язык низкого уровня. Теоретически любой язык

высокого уровня может быть реализован аппаратно. Но по сущест-

ву это будет  1программно-аппаратная вычислительная машина 0, вы-

полняемая на специальной  1микропрограммируемой вычислительной

 1машине.  0В конечном итоге все определяется потребностями и эко-

номическими возможностями.

Реализация языка программирования на конкретной машине

заключается в создании некоторого способа преобразования про-

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

С этой целью разрабатываются трансляторы.

Под  2транслятором  0понимается специальная программа, кото-

рая переводит  1исходную программу 0 в эквивалентную ей  1объектную

 1программу 0. Процесс такого преобразования называется  1трансляци 0-

 1ей 0. Язык, на котором написана обрабатываемая программа, назы-

вается исходным, а язык, на котором записывается результирую-

щая программа, называется объектным. В качестве исходного и

объектного языков могут выступать как языки низкого, так и

языки высокого уровня.

Транслятор, преобразующий текст на языке высокого уровня

в объектную программу на языке низкого уровня (близкого к ма-
- 9 -

шинному) или языке ассемблера, называется  2компилятором 0. После

компиляции полученная объектная программа обычно не может быть

исполнена непосредственно. Дальнейшая ее обработка связана с

применением программ, которые могут быть отнесены к специаль-

ного типа трансляторам:

1) под  1программой 0  2ассемблер  0понимается транслятор, преоб-

разующий программу на  1языке ассемблера 0 (автокод) в программу

на машинном языке в некоторой форме (абсолютный или перемещае-

мый формат);

2) под  2загрузчиком  0понимается транслятор, преобразующий

программу на языке, близком к машинному, но не содержащую пол-

ностью всей информации об используемых абсолютных значениях

адресов; результатом работы загрузчика является программа го-

товая к выполнению на вычислительной машине.

Таким образом, полный цикл трансляции программы может

включать в себя несколько этапов. Например, трансляция прог-

раммы на язык ассемблера, получение перемещаемого кода (ас-

семблирование), формирование последовательности машинных ко-

манд. И только после этого программу можно выполнить на компь-

ютере. Впрочем, сама компиляция может допускать несколько эта-

пов преобразования исходной программы.

 21.2. Программно-моделируемые вычислительные машины
Конечная цель - выполнение исходной программы - может

быть достигнута и без формирования машинного кода. Этот иной

вариант заключается в разработке специальной программно-моде-

лируемой машины, набор команд которой приближен к операторам

входного языка. Как обычно на вход машины подается обрабатыва-

емая программа. Далее осуществляется возможное преобразование

программы в промежуточную форму, которая может быть обработана

и выполнена на нашей виртуальной машине. Описанный подход по-

лучил название  1интерпретации 0, а виртуальная машина называется

 1интерпретатором 0 входного языка.

Разработка транслятора представляется достаточно сложной

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

машинному. Поэтому принципиальная возможность отказаться от

обязательной компиляции в машинные коды и вместо этого разра-

ботать соответствующий интерпретатор, в некоторых случаях яв-

ляется чуть ли не панацеей от всех бед.

Выбор схемы трансляции определяется не только сложностью

задачи перевода, а и во многом зависит от свойств реализуемого

языка. Представим себе ситуацию, когда язык программирования

разрешает модифицировать программу в процессе ее выполнения.

Примерами таких языков могут служить языки Бейсик и Пролог.

Понятно, что ни один компилятор будет не в состоянии породить

машинный код заранее неизвестной конструкции. Следующий пример

показывает, как бывает заманчиво пользоваться возможностью ди-

намической модификации программы.

 2Пример. 0 Пусть мы хотим напечатать таблицу значений функ-

ции. Логично было бы считать, что исходными данными здесь яв-

ляются интервал и шаг (для которых строится таблица), и алгеб-

раическое выражение, определяющее функцию. Ниже приведена

программа на одном из диалектов Бейсика. Идея заключается в

следующем. Первоначально в тексте программы отсутствует необ-

ходимая строка печати результата. Эта строка формируется в

процессе работы программы и выводится временно в файл A.DAT.

Далее, через оператор динамического слияния OVERLAY к основной

программе присоединяется программа из файла, и выполнение про-

должается.
10 PRINT "ВВЕДИТЕ ИНТЕРВАЛ И ШАГ ПОСТРОЕНИЯ ТАБЛИЦЫ"

20 INPUT A,B,H

30 PRINT "ЗАДАЙТЕ ВЫЧИСЛЯЕМОЕ ВЫРАЖЕНИЕ (НАПРИМЕР, SIN(X))"

40 INPUT S$

50 OPEN "A.DAT" FOR OUTPUT AS FILE #1

60 PRINT #1,"100 PRINT X,";S$

70 CLOSE #1

80 OVERLAY "A.DAT" LINE 90 \ REM МОДИФИКАЦИЯ ПРОГРАММЫ

90 FOR X=A TO B STEP H

100 REM ЗДЕСЬ ПОЯВИТСЯ ОПЕРАТОР ПЕЧАТИ

110 NEXT X

120 END
Заманчивая простота приведенного решения не должна засло-

нять всех проблем, связанных с модификацией программы. Кто в

такой ситуации берет на себя ответственность за синтаксическую

корректность добавляемого фрагмента? Как должна поступить

исполняющая система, если будут обнаружены ошибки в новых опе-

раторах? Так как заранее неизвестно, как может модифициро-

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

все свои модули до конца работы.

Таким образом, если даже вам предъявят исполняемый модуль

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

будьте уверены, что либо на самом деле в данной реализации

запрещена модификация пользовательской программы в процессе ее

работы, либо же в этом исполняемом модуле присутствуют элемен-

ты виртуальной машины, которая в конечном счете обеспечивает

интерпретацию динамически появляющихся программных элементов.

В сущности мы имеет дело с модулем, объединяющим входную прог-

рамму и среду исполнения.

Интерпретация отдельного оператора исходной программы

заключается в его декодировании и выполнении операций, при-

писываемых этому оператору. Представим себе, что наш оператор

должен выполняться в цикле тысячи раз. Тогда интерпретатор

тысячи раз будет выполнять декодирование. В других случаях де-

кодирование некоторых операторов может вовсе не потребоваться,

если в процессе исполнения программы управление ни разу не бу-

дет на них передано. Этой особенностью интерпретатора объясня-

ется обнаружение синтаксических ошибок в, казалось бы, уже от-

лаженных программах.

Идея интерпретации настолько естественна и объективно не-

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

ре. Причина этого в том, что нам нужны языки высокого и сверх-

высокого уровня, которые невозможно реализовать полностью ап-

паратно, если не использовать принципов микропрограммирования,

которые задают все ту же интерпретацию. Еще одна причина при-

менения элементов интерпретации состоит в экономии памяти, так

как некоторую информацию выгоднее хранить в исходном виде.

Итак, под  2интерпретатором  0понимается такой транслятор,

который, возможно, порождает некий вариант объектной програм-

мы, но главное - сам же его и исполняет. При этом, всякая

конструкция исходной программы интерпретируется каждый раз,

когда её необходимо исполнить.

.
- 12 -

 21.3. Выбор языка реализации

мировать транслятор? Здесь возможны два граничных случая. Если

за язык реализации выбрать машинный язык, то надежда получить

эффективный программный продукт натыкается на трудности прог-

раммирования и отладки. С другой стороны, язык высокого уровня

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

рости трансляции и исполнения. Поэтому на практике в зависи-

мости от преследуемых целей выбирается тот или иной вариант

или их комбинация.

Язык высокого уровня может быть языком реализации только

при условии, что для него самого уже существует соответствую-

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

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

желательно разрабатывать транслятор, предназначенный для одной

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

тем, что там уже есть развитое программное обеспечение.

Если наш транслятор реализован на одном компьютере, а вы-

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

такой транслятор называется  2кросс-компилятором 0.

Удобно отображать характеристики транслятора в виде спе-

циальной Т-образной схемы. На рисунке 1 представлена Т-образ-

ная схема АБВ, соответствующая транслятору, для которого А -

входной язык, Б - выходной язык, В - язык реализации.
 ш1.0

┌───────────┐

│ А Б │

└───┐ ┌───┘

└───┘
 ш0

Рис. 1. Т-образная схема транслятора
Можно представить себе вариант двухступенчатого трансля-

тора, где язык реализации одной ступени является входным язы-

ком другой. Тогда сочленение двух Т-образных схем означает не-

кую обобщенную итоговую схему трансляции. Эта итоговая схема

может быть приписана к первым двум ступеням (на уровень выше).

На рисунке 2 приведен пример такого сочленения. Символы итого-

вой схемы (3) выделены на рисунке жирным шрифтом. Здесь как бы
- 13 -

свертка двух Т-образных схем (1 и 2) порождает третью. То есть

текст транслятора 1 после обработки его транслятором 2 превра-

щяется в транслятор 3 (с теми же входным и выходным языками,

но другим языком реализации).

Можно сформулировать формальные правила стыковки схем:

1) примыкающие в горизонтальном направлении языки должны

попарно совпадать;

2) входной и выходной языки итоговой схемы должны совпа-

дать с соответствующими языками первой схемы.

1───────────┐ 3───────────┐

│ А Б │ │  2А Б  0│

└───┐ 2───┴───┴───┐ ┌───┘

│ В │ В С │  2С 0 │

└───┴───┐ ┌───┴───┘

│ Г │

└───┘
 ш0

ла сочетания при этом остаются теми же.

В шестидесятых годах среди программистов была популярна

идея создания универсального машинно-независимого языка низко-

го уровня UNCOL. Предлагалось реализовывать этот язык на каж-

дом компьютере. Далее для каждого нового языка программирова-

ния L следовало в первую очередь разработать транслятор с вы-

ходным языком UNCOL (рис. 3).

┌─────────────┐

│ L UNCOL│

└───┐ ┌───┘

│UNCOL│

└─────┘
 ш0

компьютеров потребует (M+N) трансляторов: M трансляторов

для перевода на UNCOL и N трансляторов для перевода на машин-

ный язык каждого компьютера. Иная схема - отдельная реализация

каждого языка для каждой машины - потребует (M*N) транслято-

ров. Можно считать, что проект UNCOL это просто идея одного

общего машинного языка (и тогда компьютеры просто будут нераз-
- 14 -

личимы). Однако дело здесь в другом. Использование UNCOL-мето-

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

Очевидная неэффективность получающегося транслятора компенси-

руется общим снижением времени на разработку одного транслято-

ра вместо N необходимых. Еще один довод: предложенная схема

может применяться как временный вариант использования языка до

тех пор, пока не будет создан эффективный транслятор.

 21.4. Краткий обзор процесса компиляции
На рисунке 4 приведена принципиальная схема компилятора

[4]. Сплошные стрелки показывают порядок исполнения отдельных

модулей (фаз компиляции), а пунктирные - обозначают направле-

ние информационных потоков. В зависимости от особенностей