Ишакова Е.Н. Разработка компиляторов - Методические указания к курсовой работе (1082246), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

<ввода>:: = read(<идентификатор>)

<вывода>:: = write(<выражение>)

<выражение>:: = <сумма> | <сумма> ( = | < | >) <сумма>

<сумма> ::= <произведение> { (+ | - | ) <произведение>}

<произведение>:: = <множитель> { (* | / | ) <множитель>}

<множитель>:: = <идентификатор> | <число> | <логическая_константа> |

 <множитель> | (<выражение>)

<логическая_константа>:: = true | false

Диаграммы Вирта

В метаязыке диаграмм Вирта используются графические примитивы, представленные на рисунке 2.1.

При построении диаграмм учитывают следующие правила:

• каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно изображаются на противоположных сторонах;

• каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

• альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;

• должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу);

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

1) 2) 3)

1) – терминальный символ, принадлежащий алфавиту языка;

2) – постоянная группа терминальных символов, определяющая название лексемы, ключевое слово и т.д.;

3) – нетерминальный символ, определяющий название правила;

4) – входная дуга с именем правила, определяющая его название;

5) – соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах.

Рисунок 2.1 – Графические примитивы диаграмм Вирта

блок

4)

5)

блок

Пример 1.4. Описание синтаксиса модельного языка М с помощью диаграмм

Описание синтаксиса модельного языка М с помощью диаграмм Вирта представлено на рисунке 2.2.

цифра

Рисунок 2.2 – Синтаксические правила модельного языка М

буква

идентификатор

число

ключевое_слово

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 2

разделитель

п рограмма

о писание

т ело

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 3

оператор

п

идентификатор

выражение

рисваивания

у словный

ц икла

составной

в вода

в ывода

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 4

в ыражение

с умма

п роизведение

операнд

логическая_константа

Рисунок 2.2 – Синтаксические правила модельного языка М, лист 5

Пример 2.4. Программа на модельном языке М, вычисляющая среднее арифметическое чисел, введенных с клавиатуры.

program

var k, n, sum: int;

begin

read(n);

sum:= 0;

i:=1;

while i<=n do

begin

read(k);

sum:=sum+k;

k:=k+1

end;

write(sum/n)

end.

2.2 Общая структура компилятора

Определение 2.2. Компилятор – это программа, которая осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблере.

Основные функции компилятора:

1) проверка исходной цепочки символов на принадлежность к входному языку;

2) генерация выходной цепочки символов на языке машинных команд или ассемблере.

Процесс компиляции состоит из двух основных этапов: синтеза и анализа. На этапе анализа выполняется распознавание текста исходной программы и заполнение таблиц идентификаторов. Результатом этапа служит некоторое внутреннее представление программы, понятное компилятору.

На этапе синтеза на основании внутреннего представления программы и информации, содержащейся в таблице идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код.

Данные этапы состоят из более мелких этапов, называемых фазами. Состав фаз и их взаимодействие зависит от конкретной реализации компилятора. Но в том или ином виде в каждом компиляторе выделяются следующие фазы:

1. лексический анализ;

2. синтаксический анализ;

3. семантический анализ;

4. подготовка к генерации кода;

5. генерация кода.

Определение 2.3. Процесс последовательного чтения компилятором данных из внешней памяти, их обработки и помещения результатов во внешнюю память, называется проходом компилятора.

По количеству проходов выделяют одно-, двух-, трех- и многопроходные компиляторы. В данном пособии предлагается схема разработки трехпроходного компилятора, в котором первый проход – лексический анализ, второй - синтаксический, семантический анализ и генерация внутреннего представления программы, третий – интерпретация программы.

Общая схема работы компилятора представлена на рисунке 2.3.

Рисунок 2.3 – Общая схема работы компилятора

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

Определение 2.4. Лексический анализатор (ЛА) – это первый этап процесса компиляции, на котором символы, составляющие исходную программу, группируются в отдельные минимальные единицы текста, несущие смысловую нагрузку – лексемы.

Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобному для последующей обработки. ЛА использует регулярные грамматики.

ЛА необязательный этап компиляции, но желательный по следующим причинам:

1) замена идентификаторов, констант, ограничителей и служебных слов лексемами делает программу более удобной для дальнейшей обработки;

2) ЛА уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии;

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

В процедурных языках лексемы обычно делятся на классы:

1. служебные слова;

2. ограничители;

3. числа;

4. идентификаторы.

Каждая лексема представляет собой пару чисел вида (n, k), где n – номер таблицы лексем, k - номер лексемы в таблице.

Входные данные ЛА - текст транслируемой программы на входном языке.

Выходные данные ЛА - файл лексем в числовом представлении.

Пример 2.5. Для модельного языка М таблица служебных слов будет иметь вид:

1) program; 2) var; 3) int; 4) bool; 5) begin; 6) end; 7) if; 8) then; 9) else; 10) while; 11) do; 12) read; 13) write; 14) true; 15) false.

Таблица ограничителей содержит:

1) . ; 2) ; ; 3) , ; 4) : ; 5) := ; 6) (; 7) ) ; 8) + ; 9) - ; 10) * ; 11) / ; 12) ; 13)  ; 14)  ; 15) = ; 16) > ; 17) <.

Таблицы идентификаторов и чисел формируются в ходе лексического анализа.

Пример 2.6. Описать результаты работы лексического анализатора для модельного языка М.

Входные данные ЛА: program var k, sum: int; begin k:=0;…

Выходные данные ЛА: (1, 1) (1, 2) (4, 1) (2, 3) (4, 2) (2, 4) (1, 3) (2, 2) (1, 5) (4, 1) (2, 5) (3, 1) (2, 2)…

Анализ текста проводится путем разбора по регулярным грамматикам и опирается на способ разбора по диаграмме состояний, снабженной дополнительными пометками-действиями. В диаграмме состояний с действиями каждая дуга имеет вид, представленный на рисунке 2.4. Смысл этой конструкции: если текущим является состояние А и очередной входной символ совпадает с для какого либо i, то осуществляется переход в новое состояние В, при этом выполняются действия D₁, D₂, …, D_m.

Для удобства разбора вводится дополнительное состояние диаграммы ER, попадание в которое соответствует появлению ошибки в алгоритме разбора. Переход по дуге, не помеченной ни одним символом, осуществляется по любому другому символу, кроме тех, которыми помечены все другие дуги, выходящие из данного состояния.

Рисунок 2.4 – Дуга ДС с действиями

Алгоритм 2.1. Разбор цепочек символов по ДС с действиями

Шаг 1. Объявляем текущим начальное состояние ДС H.

Шаг 2. До тех пор, пока не будет достигнуто состояние ER или конечное состояние ДС, считываем очередной символ анализируемой строки и переходим из текущего состояния ДС в другое по дуге, помеченной этим символом, выполняя при этом соответствующие действия. Состояние, в которое попадаем, становится текущим.

ЛА строится в два этапа:

1) построить ДС с действиями для распознавания и формирования внутреннего представления лексем;

Характеристики

Список файлов книги