Цель работы - Разработка компилятора подмножества языка Паскаль на язык Ассемблера

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

Создание компилятора с заданного подмножества языка Паскаль с незначительными модификациями и упрощениями (полное описание входного и выходного языков дано далее в задании для каждого варианта).

Задание

Входной язык компилятора должен удовлетворять следующим требованиям:

    - входная программа начинается ключевым словом prog и заканчивается ключевым словом end; - входная программа может быть разбита на строки произвольным образом, все пробелы и переводы строки должны игнорироваться компилятором; - текст входной программы может содержать комментарии любой длины, которые должны игнорироваться компилятором (вид комментария задан в варианте задания); - входная программа должна представлять собой единый модуль, содержащий линейную последовательность операторов, вызовы процедур и функций не предусматриваются; - должны быть предусмотрены следующие варианты операторов входной программы: - оператор присваивания вида :=; - условный оператор вида if then , либо if then else ; - составной оператор вида begin ... end; - оператор цикла, предусмотренный вариантом задания; - выражения в операторах могут содержать следующие операции (минимум): - арифметические операции сложения (+) и вычитания (-); - операции сравнения меньше (<), больше (>), равно (=); - логические операции "и" (and), "или" (or), "нет" (not); - дополнительные арифметические операции, предусмотренные вариантом задания; - операндами в выражениях могут выступать идентификаторы (переменные) и константы (тип допустимых констант указан в варианте задания); - все идентификаторы, встречающиеся в исходной программе, должны восприниматься как переменные, имеющие тип, заданный в варианте задания (предварительное описание идентификаторов в исходной программе не требуется).

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

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

Индивидуальный вариант задания

№ п/п

Тип допустимых констант

Дополнительные арифметические операции

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

Тип комментария

1.

Двоичные

Умножение (*), деление (/)

1

1

Типы дополнительных операторов цикла:

1 - цикл с предусловием вида while <выражение> do <оператор>;

Типы комментариев:

1 - комментарий в фигурных скобках: {...}

Грамматика входного языка в форме Бэкуса-Наура

<начало>>prog

<буква>>a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

<все_цифры>> 0|1|2|3|4|5|6|7|8|9

<идентификатор>><буква>{<буква>}|{<буква><все_цифры>}

<цифра>>0|1

<число>><цифра>{<цифра>}

<знак_слож_выч>>+|-

<знак_умн_дел>>*|/

<операц_присвоен>> :=

<завершение_оператора>>;

<множитель>> <число>|<идентификатор>|(<формула>)

<слагаемое>> <множитель>{<знак_умн_дел><множитель>}

<формула>> <слагаемое> {<знак_слож_выч><слагаемое>}

<оператор>><идентификатор><операц_присвоен><формула><завершение_оператора>

<логич_операц>>or|nor|<|>|<>

<логич_оператор>>(<идентификатор>|<число>)<логич_операц>(<идентификатор>|<число>)

<операт_условн>>if(<логич_оператор>)then{<оператор>}{else<оператор>}

<операт_цикла>>while(<логич_оператор>)do<оператор>

<открыв_фигур_скобка>>{

<закрыв_фигур_скобка>>}

<комментарий>><открыв_фигур_скобка><любые_символы><закрыв_фигур_скобка>

<конец>>end.

Описание выбранного способа организации таблицы идентификаторов

Для организации таблицы идентификаторов выберем комбинированный способ, поскольку в нем отсутствуют ограничения на количество входных идентификаторов, и он не требует разработки сложной и эффективной хэш-функции (разработка комбинированной таблицы в данном случае проще, чем выбор хорошей хэш-функции).

В качестве такого способа возьмем комбинацию хэш-адресации и бинарного дерева.

В качестве хэш-функции будем использовать сумму кодов первой и средней буквы. При этом для идентификаторов длины в 1 и 2 символа необходимо сделать исключение и в качестве хэш-адреса для них будет возвращаться код первой буквы.

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

Графически это можно изобразить следующим образом

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

Описание лексического анализатора

Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:

ключевые слова : prog, end., begin, end, if, then, else, while, do, and, or, not;

идентификаторы: любые последовательности латинских символов и цифр;

константы: двоичное представление числа;

знаки операций: =, <, >, -, +, *, /;

оператор присваивания: :=;

разделитель: ;, (, );

комментарии, заключенные в { }.

Лексический анализатор имеет дело с такими объектами, как различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык констант и идентификаторов в большинстве случаев является регулярным - то есть, может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы. Существуют правила, с помощью которых для любой регулярной грамматики может быть построен недетерминированный конечный автомат, распознающий цепочки языка, заданного этой грамматикой.

Недетерминированный конечный автомат задается пятеркой:

M=(Q,,,q0,F)

Где: Q - конечное множество состояний автомата;

- конечное множество допустимых входных символов;

- заданное отображение множества Q* во множество подмножеств P(Q) : Q*P(Q) (иногда называют функцией переходов автомата);

Q0Q - начальное состояние автомата;

FQ - множество заключительных состояний автомата.

Работа автомата выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии qiQ, считывает очередной символ w из входной цепочки символов и изменяет свое состояние на qi+1=(qi, w), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом. Считается также, что перед тактом 1 автомат находится в начальном состоянии q0.

Графически автомат отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют функции перехода. Если функция перехода предусматривает переход из состояния q в q' по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q'.

Похожие статьи




Цель работы - Разработка компилятора подмножества языка Паскаль на язык Ассемблера

Предыдущая | Следующая