Синтаксический разбор текста по заданной грамматике с построением дерева разбора. Назначение таблицы идентификаторов. Метод упорядоченного списка. Назначение лексического анализатора. Процесс программирования работы недетерминированного МП-автомата.
Аннотация к работе
Компилятор - программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд. Большинство компиляторов переводят программу с некоторого высокоуровневого языка программирования в машинный код, который может быть непосредственно выполнен компьютером. В первой части работы ставится задача разработать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице.Входной язык представляет собой подмножество языка программирования Pascal. Программа на данном языке может включать в себя символы латиницы, цифры, знак “_ “, символьные константы, различные операторы. Текст на входном языке содержится в текстовом файле. Набор идентификаторов организуются в таблицу по методу упорядоченного списка. операндами в выражениях могут выступать идентификаторы и константы (один символ, заключенный в одинарные кавычки);Таблица используется на всех стадиях работы компилятора и формируется на этапе лексического анализа. Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе и накапливаются в таблице символов или таблице идентификаторов.Элементы записываются в таблицу в порядке возрастания. Так как упорядочивание таблицы идентификаторов происходит на всех этапах обращения к таблице, то для ее построения можно пользоваться только алгоритмом прямого упорядоченного включения элементов. При добавлении нового элемента в таблицу идентификаторов он сначала добавляется в конец таблицы, а затем идет переупорядочивание элементов таблицы идентификаторов.В результате работы было выявлено, что недостатком такого метода является требование упорядочивания таблицы идентификаторов на всех этапах обращения к этой таблице.Лексический анализатор (или сканер) - это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка.Распознаватель лексем языка для данной грамматики задан конечным детерминированным автоматом, схема которого представлена на рисунках 3, 4 и 5. Состояния соответствуют: Н - начальное состояние; P1, P2, P3, P4 - состояния, соответствующие ключевому слову “prog”; En1, En2 - состояния, соответствующие ключевому слову “end”; I1, I2 - состояния, соответствующие ключевому слову “if”;Спроектированный лексический анализатор выполняет лексический анализ входного текста в соответствии с заданной грамматикой и порождает таблицу лексем с указанием их типов.Лексический анализатор выделяет в тексте лексемы языка. Программа выполняет лексический анализ входного языка, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора.Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Разработанный алгоритм, позволяет для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами). Доказано, что время работы этого алгоритма пропорционально n3, где n - длина входной цепочки. Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка - большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.Множество правил грамматики имеет вид: >”A” |….| ”Z” |….| ”a” |….| ”z” |”_” Грамматика является грамматикой операторного предшествования, так как она не содержит l-правил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики. , На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики.В первой части работы был разработан программа, которая получает на входе набор идентификаторов, организует таблицу идентификаторов методом упорядоченного списка, позволяет осуществить многократный поиск идентификатора в этой таблице.
План
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. ОПИСАНИЕ ВХОДНОГО ЯЗЫКА
2. ОРГАНИЗАЦИЯ ТАБЛИЦЫ ИДЕНТИФИКАТОРОВ
2.1 Назначение таблицы идентификаторов
2.2 Метод упорядоченного списка
2.3Результат выполнения программы
3. ПРОЕКТИРОВАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
3.1 Назначение лексического анализатора
3.2 Граф переходов лексического анализатора
3.3 Результат выполнения программы
4. ПОСТРОЕНИЕ СИТАКСИЧЕСКОГО АНАЛИЗАТОРА
4.1 Дерево вывода
4.2 Синтаксический анализатор
4.3 Таблицы предшествования
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
Вывод
В результате выполнения курсовой работы для заданного входного языка были построены отдельные части компилятора.
В первой части работы был разработан программа, которая получает на входе набор идентификаторов, организует таблицу идентификаторов методом упорядоченного списка, позволяет осуществить многократный поиск идентификатора в этой таблице.
Во второй части работы была написана программа, которая выполняет лексический анализ входного текста и порождает таблицу лексем с указанием их типов и значений.
Третья часть курсовой работы была посвящена разработке программы, которая порождает таблицу лексем и выполняет синтаксический разбор текста с построением дерева разбора.
Отдельные части компилятора, разработанные в данной курсовой работе, дают представление о технике и методах, лежащих в основе построения компиляторов.
Список литературы
1. Гордеев А. В. Молчанов Л. Ю. Системное программное обеспечение, - СПБ.: Питер. 2002. - 734с.
2. Кампапиец Р. II. Манькоп Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Учеб. пособие для высших и средних учебных заведений. - СПБ.: КОРОНА Принт, 2000. -256 с.
3. Гордеев А. В. Операционные системы: Учебник для вузов.
2-е изд.-СПБ.: Питер, 2004. - 416 с.
4. Олифер В. Г., Олифер Н.А. Сетевые операционные системы. - СПБ.: Питер. 2002. - 544 с.