Кревский И.Г., Селиверстов М.Н., Григорьева К.В. Формальные языки, грамматики и основы построения трансляторов

Подождите немного. Документ загружается.

Министерство образования Российской Федерации

Пензенский государственный университет

И.Г. Кревский, М.Н. Селиверстов, К.В. Григорьева

ФОРМАЛЬНЫЕ ЯЗЫКИ, ГРАММАТИКИ И ОСНОВЫ

ПОСТРОЕНИЯ ТРАНСЛЯТОРОВ

Учебное пособие

(под ред. д.т.н., профессора А.М. Бершадского)

Пенза 2003

УДК 681.3

Рецензенты:

Кафедра «Системы автоматизированного проектирования» Воронежского

государственного технического университета

Доктор технических наук, профессор,

К.Б. Скобельцын

Санкт-Петербургский государственный

технический университет

И.Г. Кревский, М.Н. Селиверстов, К.В. Григорьева

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

пособие / Под ред. А.М. Бершадского – Пенза: Изд

-во Пенз. гос. ун-та, 2002.

– 124 с.: 15 ил., 6 табл., библиогр. 12 назв.

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

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

«Лингвистическое и программное обеспечение САПР и «Теория

вычислительных процессов и структур». Подробно рассмотрены основные

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

восходящий синтаксический

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

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

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

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

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

Приведены методические указания к лабораторным работам с

вариантами заданий, а также требования к курсовому проекту по построению

компиляторов.

Учебное пособие разработано на кафедре «Системы

автоматизированного проектирования» и предназначено для студентов

специальностей 22.03.00 «Системы автоматизированного проектирования» и

35.15.00 «Математическое обеспечение и администрирование

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

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

654600 «Информатика и вычислительная техника», бакалавров по

направлению 552800 «Информатика и вычислительная техника».

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ........................................................................................................... 4

1. СТРУКТУРА КОМПИЛЯТОРА. ТИПЫ ТРАНСЛИРУЮЩИХ

ПРОГРАММ ............................................................................................................ 7

2. ОПРЕДЕЛЕНИЕ ЯЗЫКА. СИНТАКСИС И СЕМАНТИКА ...................... 15

3. КЛАССИФИКАЦИЯ ГРАММАТИК. ИЕРАРХИЯ ХОМСКОГО............. 20

4. ПРОБЛЕМА РАЗБОРА................................................................................... 26

5. ЛЕКСИЧЕСКИЙ АНАЛИЗ ............................................................................ 31

6. КОНЕЧНЫЕ АВТОМАТЫ............................................................................. 35

7. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ ........................................ 40

8. LL(1) - ГРАММАТИКИ.................................................................................. 45

9. ПРЕОБРАЗОВАНИЕ ГРАММАТИК В LL(1) ФОРМУ.............................. 50

10. ПОСТРОЕНИЕ СИНТАКСИЧЕСКОГО ГРАФА ..................................... 56

11. ПОСТРОЕНИЕ ПРОГРАММЫ ГРАММАТИЧЕСКОГО РАЗБОРА ДЛЯ

ЗАДАННОГО СИНТАКСИСА............................................................................ 61

12. ПОСТРОЕНИЕ ТАБЛИЧНО-УПРАВЛЯЕМОЙ ПРОГРАММЫ

ГРАММАТИЧЕСКОГО РАЗБОРА ..................................................................... 66

13. ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ .................................. 71

14. РАБОТА С ТАБЛИЦЕЙ СИМВОЛОВ ...................................................... 84

15. ВОССТАНОВЛЕНИЕ ПРИ СИНТАКСИЧЕСКИХ ОШИБКАХ ............ 88

16. ПОСТФИКСНАЯ ЗАПИСЬ......................................................................... 91

17. ВНУТРЕННИЕ ФОРМЫ ........................................................................... 103

18. МЕТОДЫ ГЕНЕРИРОВАНИЯ КОДА ..................................................... 105

19. ЛИТЕРАТУРА ............................................................................................ 107

20. ЛАБОРАТОРНЫЕ РАБОТЫ..................................................................... 108

ЛАБОРАТОРНАЯ РАБОТА №1. РАЗРАБОТКА ЛЕКСИЧЕСКОГО

АНАЛИЗАТОРА .............................................................................................. 109

ЛАБОРАТОРНАЯ РАБОТА №2. РАЗРАБОТКА СИНТАКСИЧЕСКОГО

АНАЛИЗАТОРА .............................................................................................. 110

ЛАБОРАТОРНАЯ РАБОТА №3. ФОРМИРОВАНИЕ ПОСТФИКСНОЙ

ЗАПИСИ............................................................................................................ 112

ЛАБОРАТОРНАЯ РАБОТА №4. РАЗРАБОТКА ГЕНЕРАТОРА КОДА

.. 113

ПРИЛОЖЕНИЕ А. ВАРИАНТЫ ЗАДАНИЙ К ЛАБОРАТОРНЫМ

РАБОТАМ......................................................................................................... 117

ПРИЛОЖЕНИЕ Б. ТРЕБОВАНИЯ К КУРСОВОМУ ПРОЕКТУ............... 123

ВВЕДЕНИЕ

Большую часть программы курса «Лингвистическое и программное

обеспечение САПР» занимают вопросы, связанные с изучением формальных

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

этой дисциплины студентам специальности 22.03.00 «Системы

автоматизированного проектирования» освоение данного материала требует

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

изучения теоретических основ построения трансляторов. Именно поэтому

значительная

часть лабораторного практикума и курсовое проектирование по

дисциплине «Лингвистическое и программное обеспечение САПР»

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

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

обеспечения САПР, технологий структурного и объектно-ориентированного

программирования, тем более что большая часть этого материала в ПГУ

вынесена в отдельные дисциплины регионального

компонента. Также не

рассмотрены языки проектирования САПР, поскольку их рассмотрению

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

Можно сказать, что изучение теоретических основ и приобретение

практических навыков написания транслятора имеют большое

воспитательное значение. Не секрет, что многие студенты информационных

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

программный код

, абсолютно не умеют правильно поставить задачу,

искренне не понимают, что любая программа будет эффективно и корректно

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

спроектирована. Разработка транслятора - это прекрасный способ понять на

собственном опыте, что, не выполнив предварительных этапов (например, не

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

детерминированный

анализ грамматики), невозможно сделать хорошо

работающую программу.

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

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

знания, литературы по этим вопросам явно недостаточно. Значительная часть

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

единичных экземплярах, а порой просто утеряна. Отличительной

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

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

заданий на лабораторные работы и на курсовое проектирование. Эта часть

материалов является расширением ранее опубликованного в [1].

Так как в процессе преподавании данной дисциплины параллельно

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

приходится идти на компромисс между краткостью и полнотой изложения

теории.

В ряде книг [2,3] представлены описания трансляторов почти без

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

рассмотрения разработки транслятора с минимальным изложением теории

представляет посвященная данной теме глава [4]. Материалы этой книги

были во многом использованы в главах 2 и 10-12 настоящего пособия.

Несколько более формальное описание разработки транслятора представлено

в [5]. В наибольшей степени компромисс между

необходимой строгостью

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

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

[6]. Эта книга может быть особенно полезна при углубленном изучении

материала глав 3-9 данного пособия.

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

[7], но соответствующий раздел книги рассматривает лишь небольшую часть

материала. При написании главы 16 настоящего пособия были частично

использованы материалы [8]. Более детальное и подробное рассмотрение

вопросов формальных языков и грамматик можно найти в [9-11]. Как видно

из списка литературы, большая часть ее была издана в 70-80 годы. Отрадно,

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

компьютерным технологиям. Материалы недавно изданной [12] были

использованы при написании главы 13.

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

части дисциплины «Теория вычислительных процессов и структур»

специальности 35.15.00 «Математическое обеспечение и администрирование

информационных систем», а также сходных курсов, изучаемых студентами

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

специалистов 65.46.00 и подготовки бакалавров 55.28.00 «Информатика и

вычислительная техника

1. СТРУКТУРА КОМПИЛЯТОРА. ТИПЫ

ТРАНСЛИРУЮЩИХ ПРОГРАММ

Каждый компьютер способен непосредственно выполнять

ограниченный набор относительно простых команд. Любые более сложные

действия представляются последовательностью таких команд. Для

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

переводят в последовательность команд машинного кода.

Исходная программа

(написанная на каком-либо языке

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

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

непосредственного выполнения.

Компилятор

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

строку символов определенного вида (т.е. текст программы на исходном

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

Компиляторам присущ ряд общих черт, что упрощает процесс создания

компилирующих программ. В состав любого компилятора входят три

основных компонента:

- лексический анализатор (блок сканирования);

синтаксический анализатор;

- генератор кода машинных команд.

Принцип действия анализаторов можно описать с помощью

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

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

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

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

. Такими

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

(например, IF,DO и др.), имена переменных, константы и знаки операций

(например,* или +). Далее эти слова рассматриваются как неделимые

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

программы на лексемы следует фаза синтаксического анализа

, называемая

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

следования операторов. Например, для предложения IF, имеющего вид IF

выражение THEN предложение; грамматический разбор состоит в том, чтобы

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

выражением следует лексема THEN, за которой в свою очередь следует

правильное предложение, оканчивающееся знаком ";". Последним

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

, который использует результаты

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

пригодную к выполнению. Хотя в состав любого компилятора входят все три

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

разнообразными способами. Рассмотрим наиболее распространенные

варианты взаимосвязи между этими компонентами.

ОБЪЕКТНЫЙ КОД

БЛОК СКАНИРОВАНИЯ

(ПРОХОД 1)

СИНТАКСИЧЕСКИЙ

АНАЛИЗАТОР

(ПРОХОД 2)

ГЕНЕРАТОР КОДА

(ПРОХОД 3)

ИСХОДНАЯ ПРОГРАММА

ФАЙЛ ЛЕКСЕМ

ФАЙЛ ПОСТФИКСНОЙ ЗАПИСИ

Рис.1.1. Трехпроходный транслятор.

Блок сканирования считывает исходную программу и представляет ее в

форме файла лексем. Синтаксический анализатор читает этот файл и выдает

новое представление программы, например, в постфиксной форме. Наконец,

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

программы.

Компилятор такого вида называется трехпроходным (рис.1.1), так как

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

файл в постфиксной форме).

Недостаток:

Невысокая скорость выполнения, так как в большинстве

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

осуществляются сравнительно медленно.

Преимущества:

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

связь между обрабатывающими блоками осуществляется только через файлы

данных, любой проход может быть реализован независимо от остальных. Это

обеспечивает:

1. Возможность автономной разработки различных блоков компилятора

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

промежуточных файлов.

2. Гибкость компилятора. Например, для реализации одного и того

же

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

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

специальные генераторы кода для каждого типа компьютера. При

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

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

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

общего генератора кода

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

(модули различных фаз компиляции можно загружать по очереди,

выгружая при этом предыдущий).

Для достижения высокой скорости компиляции применяется

компилятор с однопроходной структурой (рис.1.2). На рисунке связи по

управлению показаны сплошными линиями, передача данных – пунктиром.

Исходная

программа

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

Синтаксический анализатор

Лексема

Фрагмент

постфиксной

записи

Генератор кода

Фрагмент

объектного

кода

Рис.1.2. Однопроходный транслятор.

В этом случае синтаксический анализатор выступает в роли основной

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

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

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

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

постфиксной записи,

после чего он обращается к генератору кода, который

создает объектный код для этого фрагмента программы.

Преимущество:

Максимальная эффективность и скорость выполнения, так как

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

к файлам минимально (только чтение из исходного и запись в объектный

файлы).

Недостатки:

1. Проблемы при организации переходов вперед. Например, во время

обработки предложения

GOTO метка;

могут встретиться трудности, так как "метка" еще не встречалась в тексте

программы.