Цель работы - Разработка компилятора подмножества языка Паскаль на язык Ассемблера
Изучение составных частей, основных принципов построения и функционирования компиляторов.
Создание компилятора с заданного подмножества языка Паскаль с незначительными модификациями и упрощениями (полное описание входного и выходного языков дано далее в задании для каждого варианта).
Задание
Входной язык компилятора должен удовлетворять следующим требованиям:
- - входная программа начинается ключевым словом 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'.
Похожие статьи
-
Граф переходов конечного автомата лексического анализатора Исходная КС-грамматика G({prog, end., if, else, then, begin, end, while, do, or, and, not,...
-
Turbo Pascal, О Turbo Pascal, История - Работа с языком Турбо Паскаль
Среда разработки Turbo Pascal 7.1 (Рис 1) О Turbo Pascal Turbo Pascal (произносится "турбо паскаль") -- Интегрированная среда разработки программного...
-
ВВЕДЕНИЕ - Работа с языком Турбо Паскаль
Язык турбо паскаль Что такое язык программирования, для чего нужен. Для чего используется графика. Целью данной курсовой работы является рассмотрение...
-
В связи с увеличением числа сотрудников, работающих в компании, а также с расширением рабочего проекта, возникла проблема, связанная с версионностью...
-
Основные понятия баз данных. Цели использования баз данных - Разработка базы данных
В широком смысле слова база данных (БД) - это совокупность сведений о конкретных объектах реального мира в какой-либо предметной области. Для удобной...
-
Методика анимации - Работа с языком Турбо Паскаль
Эффект анимации достигается быстрым чередованием кадров постепенно изменяемого изображения. При этом нежелательно формировать каждый кадр целиком,...
-
Краски, палитры, заполнения - Работа с языком Турбо Паскаль
Процедура SetCOlor. Устанавливает текущий цвет для вводимых линий и символов. Заголовок: Procedure SetColor(Color: Word); Здесь Color - текущий цвет....
-
ФУНКЦИИ И ПРОЦЕДУРЫ, Модуль Graph, Координаты, окна, страницы - Работа с языком Турбо Паскаль
Модуль Graph Модуль Graph Турбо Паскаля содержит около пятидесяти различных процедур и функции, предназначенных для работы с графическим экраном. В этом...
-
Алгоритм работы декодера кода Рида - Маллера будем разрабатывать на основе уже приведенных выше уравнений. Алгоритм приведен на рисунке 12. В начале...
-
Разработка приложения на языке C++ - Программирование на языке C++
C++ - объектно-ориентированный язык программирования. Разработан в 1998--2001 годах группой инженеров под руководством Андерса Хейлсберга в компании...
-
МОДУЛИ - Язык программирования Паскаль
Наличие модулей в Turbo Pascal позволяет программировать и отлаживать программу по частям, создавать библиотеки подпрограмм и данных, воспользоваться...
-
Объектно-ориентированные языки - Инструментальные средства разработки экспертных систем
В главе 12 мы уже обращали ваше внимание на то, что формат правил хорошо согласуется с представлением знаний в форме "при выполнении условий СЬ ..., С"...
-
ВВЕДЕНИЕ - Разработка программы на языке C++, реализующей игру "Морской бой"
Данная курсовая работа направлена на изучение принципов объектно-ориентированного программирования. Разработать программу на языке C++, реализующую игру...
-
Выбор средств реализации информационной системы Названные в параграфе 1.4. настоящей работы задачи могут быть решены тремя типами средств автоматизации:...
-
Ввиду того, что для языка JAPE не предусмотрен специализированный редактор, разработчики рекомендуют использовать Vim[10] или Eclipse[11], ассоциировав...
-
"WWWSQLDesigner" позиционируется как абсолютно бесплатный, доступный для пользователей, универсальный веб-редактор, значительно упрощающий процесс...
-
Несмотря на то, что к IoT Hub можно подключиться напрямую, используя протоколы HTTP или AMQP), Microsoft также предоставляет разные SDK для разных языков...
-
Кроме поддержки интерпретатора порождающих правил, описанного в главе 5, CLIPS обладает следующими функциональными возможностями: - для определения...
-
История функционального программирования - Основные свойства функциональных языков программирования
Широко известно, что теоретические основы императивного программирования были заложены еще в 30-х годах XX века учеными Аланом Тьюрингом и Джоном фон...
-
Наименование программы Полное наименование программы - Модуль ипотечного кредитования банковской информационной системы "БИС". Краткое наименование...
-
Пример программы построения анимации - Работа с языком Турбо Паскаль
Unit unit1; Interface uses graph; Type arpo = array [1..4] of PointType; {хранит коорд. Вершин прямоугольника} { Справка: PointType = Record X, Y :...
-
Тестирование, Анализ работы - Разработка программы на языке C++, реализующей игру "Морской бой"
Чтобы проверить корректность работы программы нужно провести тестирование. Бой с противником продолжается до полной победы, т. е. пока не будут...
-
Рекурсивная программа построения снежинки Написать программу, строящую на экране изображение: Изображение строится по следующему правилу: строится...
-
Общение пользователя с системой MathCAD 2000 происходит на уровне так называемого входного языка, максимально приближенного к обычному языку описания...
-
ОПЕРАТОР ВВОДА ДЛЯ ЧТЕНИЯ ФАЙЛА, ОПЕРАТОР ВЫВОДА - Язык программирования Паскаль
Оператор ввода для чтения файла обладает всеми свойствамии обычного оператора READ. Вкачестве параметров могут быть переменные; каждая переменная поучает...
-
Актуальность Сегодня всемирная популярность социальных информационных сетей продолжает набирать обороты, все большее пользователей не может отказать себе...
-
Введение - Разработка веб-редактора для описания лексико-семантических шаблонов на визуальном языке
Объем неупорядоченной и неструктурированной текстовой информации неуклонно растет, поэтому задача ее быстрой и качественной обработки актуальна сегодня...
-
Цель Работы - использовать принципы архитектуры "Документ-Представление" для выборки и сохранения данных в файлах, а также взаимодействия элементов меню,...
-
Цель Работы - научиться использовать элемент управления ListBox а также основные методы класса СListBox. Использование возможности контроля правильности...
-
Цель Работы - изучить приемы создания и использования шаблонов классов. - Теоретические сведения Достаточно часто встречаются классы, объекты которых...
-
Цель Работы - изучить одну из базовых концепций ООП, наследование классов в С++, заключающуюся в построении цепочек классов, связанных иерархически,...
-
Объект ориентированный класс программирование Цель Работы - изучить методику создания одномерных динамических символьных массивов при помощи...
-
Для того, чтобы интерпретировать XML представление в язык JAPE, был использован язык преобразования XSLT [18]. Данный язык и будет служить транслятором,...
-
ЗАКЛЮЧЕНИЕ - Разработка программы на языке C++, реализующей игру "Морской бой"
В данной курсовой работе была разработана игра "Морской бой". В программе использовались классы, наследование, виртуальные методы. В качестве языка...
-
Емкость, бит -16К x 1 Время цикла записи считывания - 370нс Напряжение питания - 5В,12В,-12В Потребляемая мощность: в режиме хранения - 40 мВт В режиме...
-
Проектирование визуальных конструкций Вторая глава описывает процесс трансформации текстового языка JAPE в визуальный язык, который позволит описывать...
-
JAPE позволяет анализировать текст на основе регулярных выражений. Грамматика этого языка состоит из фаз, которые сдержат в себе набор шаблонов и/или...
-
Для написания АИС использовались следующие языки программирования, программные средства и библиотеки: - Язык программирования PHP 5.4; -...
-
В среде электронного ресурса ИИС "MD_SLAGMELT" (Рис. 6) для доступа к компоненту "моделирование" необходима учетная запись (пара логин/пароль) (Рис.7)....
-
Наименование и область применения Наименование: Автоматизированная информационная система "Отель" в дальнейшем именуемая АИС "Отель". Область применения:...
Цель работы - Разработка компилятора подмножества языка Паскаль на язык Ассемблера