Войти в мой кабинет
Регистрация
ГОТОВЫЕ РАБОТЫ / КУРСОВАЯ РАБОТА, ИНФОРМАТИКА

Разработка и реализация простейшего компилятора по заданному варианту №9

happy_woman 324 руб. КУПИТЬ ЭТУ РАБОТУ
Страниц: 27 Заказ написания работы может стоить дешевле
Оригинальность: неизвестно После покупки вы можете повысить уникальность этой работы до 80-100% с помощью сервиса
Размещено: 15.10.2020
Для построения компилятора будут использованы методы, освоенные в ходе выполнения практических работ по курсу «Теоретические основы информатики». Вариант по выполнению курсовой работы: 35 Типы констант: 16 – шестнадцатеричные; Дополнительные операции: ++ - инкремент (увеличение значения переменной на 1); Тип дополнительного оператора цикла: цикл с постусловием вида do <оператор> while <выражение>; Типы комментариев: Комментарий за двойной косой чертой до конца строки “//…” Метод оптимизации: свёртка объектного кода; Тип данных: Integer;
Введение

Цель работы заключается в изучении составных частей и основных принципов построения и функционирования компиляторов. А также практическое освоение методов построения простейших компиляторов для заданной грамматики входного языка. Курсовая работа заключается в создании и реализации компилятора по заданной грамматике. В результате выполнения курсовой работы мы получим программную реализацию компилятора по заданному варианту. Для программной реализации компилятора были использованы: язык программирования С++ и интегрированная среда разработки Visual Studio 2017. Для создания полноценного компилятора нам необходимо реализовать некоторые составные части: 1. Лексический анализатор. 2. Синтаксический анализатор. 3. Генерация кода.
Содержание

Введение 3 1 Лексический анализатор 4 1.1 Грамматика входного языка 4 1.2 Описание выбранного способа организации таблицы идентификаторов 5 1.3 Описание лексического анализатора 6 1.4 Результаты работы лексического анализатора 13 2 Синтаксический анализатор 15 2.1 Построение распознавателя 15 2.2 Построение основной грамматики 18 2.3 Реализация синтаксического распознавателя 19 2.4 Результаты работы синтаксического анализатора 20 3 Генерация кода 23 3.1 Общие принципы генерации кода 23 3.2 Общий алгоритм генерации и оптимизации объектного кода 24 Заключение 25 Список используемых источников 26 Приложение А 27
Список литературы

1. Павловская Т. А. – C++. Процедурное и объектно-ориентированное программирование: Учебник для вузов. Стандарт 3-го поколения. – СПБ.: Питер, 2015. – 496 с.: ил. 2. Молчанов А. Ю. Системное программное обеспечение. Лабораторный практикум. — СПб.: Питер, 2005. — 284 с.: ил. 3. Молчанов А. Ю. Системное программное обеспечение: Учебник для вузов. 3-е изд.— СПб.: Питер, 2010. — 400 с.: ил. 4. Bjarne Stroustrup. The C++ Programming Language. Fourth Edition. Addison Wesley, 2013. 5. Ben Klements. 21st Century C. Second Edition. O’Reilly, 2015.
Отрывок из работы

1 Лексический анализатор 1.1 Грамматика входного языка Входной язык может быть построен с помощью КС-грамматики G({prog, end., if, then, begin, end, do, while, and, or, not, <, >, = , :=, ;, (, ), -, +, ++, a, c}, {S, L, O, B, C, D, E, F}, P, S) с правилами P: S? prog L end. L ? O | L; O | L; O ? begin L end | do O while(B) | if(B) then O | a:= E | E B ? B or C | C C ? C and D | D D ? E < E | E > E | E = E| (B) | not(B) E ? E - F | E + F | F++ | ++F | F F ? (E) | a | c Жирным шрифтом выделены терминальные символы. Описание грамматики построено по форме Бэкуса — Наура. Всего в построенной грамматике G 26 правил. Нетерминальные символы грамматики имеют следующий смысл: 1) S — вся программа; 2) L — последовательность операторов (может состоять из одного оператора); 3) O — оператор (пять видов: составной оператор, оператор цикла, неполный условный оператор, оператор присваивания, оператор добавление инкременты); 4) B, C — логическое выражение и его элементы; 5) D — операция сравнения или логическое выражение в скобках; 6) E, F — арифметическое выражение и его элементы; 7) Операция инкремента обозначается терминальным символом (++); 8) Константы и переменные обозначены двумя различными терминальными символами — a и c соответственно — это говорит о том, что они должны различаться на этапе синтаксического анализа; 9) Операция отрицания not обязательно требует после себя выражения в скобках. 1.2 Описание выбранного способа организации таблицы идентификаторов Для организации таблицы идентификаторов воспользуемся результатами, полученными в ходе лабораторной работы №2. В данной лабораторной работе мы разбирали методы организации таблицы идентификаторов с помощью метода простого рехеширования и метода рехеширования с использованием псевдослучайных чисел. Результаты сравнения данных методов рехеширования представлены в таблице 1. Таблица 1 Сравнение методов организации таблиц идентификаторов Количество идентификаторов % заполнения таблицы Кол-шагов при заполнении методом рехеширования с использованием произведения (1 метод) Кол-шагов при заполнении методом рехеширования с использованием псевдослучайных чисел (2 метод) 1 метод / 2 метод 2 метод /1 метод 200 20 13 819 13 719 1,007 0,993 400 40 26 250 26 629 0,986 1,014 600 60 40 508 41 497 0,976 1,024 800 80 65 547 69 445 0,944 1,060 1000 100 271 835 250 301 1,086 0,921 Данная таблица показывает, что оба метода практически одинаковы. 1.3 Описание лексического анализатора Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются: • одиннадцать ключевых слов языка (prog, end., if, then, begin, end, do, while, and, or, not); • разделители: открывающая и закрывающая круглые скобки, точка с запятой; • знаки операций: присваивание, сравнение, сложение, вычитание и инкремента; • идентификаторы; • шестнадцатеричные константы без знака; Кроме всего перечисленного распознаватель должен различать и исключать из входного текста комментарии по заданию, описанные выше (всё что после двойной косой черты — комментарий). Идентификатор — это произвольная последовательность малых и прописных букв латинского алфавита (от A до Z и от a до z), цифр (от 0 до 9) и знака подчёркивания (_), начинающаяся с буквы или знака подчёркивания. Шестнадцатеричная константа — это последовательность, начинающаяся с 0x и заканчивающаяся буквой диапазоном от A до F или числом от 0 до 9. Операторы (всего 4 вида): • Составной оператор вида begin … end; • Неполный условный оператор вида if <выражение> then <оператор>; • Оператор цикла с постусловием вида do <оператор> while <выражение>; • Оператор присваивания вида <переменная> := <выражение>. Границами лексем для данного распознавателя будут служить пробел, знак табуляции, знак перевода строки и возврат каретки, круглые скобки, две косые черты (комментарий), точка с запятой, знак двоеточия, а так же операции: +, -, <, >, =, ++. При этом нужно также учитывать, что круглые скобки, точка с запятой, знаки арифметических операций и инкремент тоже являются лексемами, две косые черты служат началом комментария, а знак двоеточия является частью знака присваивания, всё вышеперечисленное является границами лексем. В данном языке лексический анализатор в состоянии сам определить границы лексемы, исходя из этого нет необходимости в его взаимодействии с синтаксическим анализатором и другими элементами компилятора. Ниже будет представлен Конечный Автомат, на основе которого строиться распознаватель для Лексического Анализатора (рис. 1, рис. 2, рис. 3, рис. 4, рис. 5, рис. 6). Рисунок 1 — Граф переходов сокращенного КА (без учёта ключевых слов) Рисунок 2 — Граф переходов для ключевого слова prog Рисунок 3 — Граф переходов для ключевых слов begin, end и end. Рисунок 4 — Граф переходов для ключевых слов if и then Рисунок 5 — Граф переходов для ключевых слов do и while Рисунок 6 — Граф переходов для ключевых слов and, or, not На фрагментах графа переходов КА, изображенных на рис. 1,2,3,4,5,6, приняты следующие обозначения: • А ? любой алфавитно-цифровой символ; • П ? любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки); • Б ? любая буква английского алфавита (прописная или строчная) или символ подчёркивания (_); • Б (*) ? любая буква английского алфавита (прописная или строчная) или символ подчеркивания (_), кроме перечисленных в скобках; • Ц ? любая цифра от 0 до 9; • F ? функция обработки таблицы лексем, вызываемая при переходе КА из одного состояния в другое. Обозначение ее аргументов: 1. v ? переменная, запомненная при работе КА; 2. d ? константа, запомненная при работе КА; 3. a ? текущий входной символ КА. С учётом данных обозначений, полностью КА описывается следующим образом: M (Q, ?, ?, q0, F): Q = {BEGIN, G, V, P1, P2, P3, P4, I1, I2, T1, T2, T3, T4, B1, B2, B3, B4, B5, E1, E2, E3, E4, A1, A2, A3, O1, O2, D1, D2, N1, N2, N3, W1, W2, W3, W4, W5, K1, K2, C1, C2, C3, INCREMENT1, INCREMENT2, ERROR1, ERROR2} ? = A (все допустимые алфавитно-цифровые символы); q0 = BEGIN; F = {F}. • состояние G соответствует оператору присваивания (:=); • состояние V соответствует идентификатору; • состояния P1,P2,P3,P4 соответствуют ключевому слову prog; • состояния I1,I2 соответствуют ключевому слову if; • состояния T1,T2,T3,T4 соответствуют ключевому слову then; • состояния B1,B2,B3,B4,B5 соответствуют ключевому слову begin; • состояния E1,E2,E3,E4 соответствуют ключевым словам end и end.; • состояния A1,A2,A3 соответствуют ключевому слову and; • состояния O1,O2 соответствуют ключевому слову or; • состояния D1,D2 соответствуют ключевому слову do; • состояния N1,N2,N3 соответствуют ключевому слову not; • состояния W1,W2,W3,W4,W5 соответствуют ключевому слову while; • состояния K1,K2 соответствуют комментария (//…); • состояния C1,C2,C3 соответствуют константе; • состояния INCREMENT1,INCREMENT2 соответствуют операции инкремент; • состояния ERROR1, ERROR2 соответствуют ошибке; 1.4 Результаты работы лексического анализатора В результате работы лексического анализатора на выходе мы должны получить два файла: • Таблица лексем; • Таблица идентификаторов; Таблица лексем содержит в себе текс исходной программы, обработанный лексическим анализатором. В неё входят все возможные типы лексем, кроме того, любая лексема может встречаться в ней любое количество раз. Таблица лексем состоит из трёх столбцов: 1. Лексема (распознанная лексема из входного текста программы); 2. Тип лексемы; 3. Значение (некое кодовое обозначение); Таблица идентификаторов содержит только определённые типы лексем — идентификаторы и константы. В неё не попадают такие лексемы, как ключевые (служебные) слова входного языка, знаки операций и разделители. Кроме того, каждая лексема (идентификатор или константа) может встречаться в таблице идентификаторов только один раз.
Не смогли найти подходящую работу?
Вы можете заказать учебную работу от 100 рублей у наших авторов.
Оформите заказ и авторы начнут откликаться уже через 5 мин!
Похожие работы
Курсовая работа, Информатика, 30 страниц
500 руб.
Курсовая работа, Информатика, 29 страниц
348 руб.
Курсовая работа, Информатика, 30 страниц
400 руб.
Служба поддержки сервиса
+7(499)346-70-08
Принимаем к оплате
Способы оплаты
© «Препод24»

Все права защищены

Разработка движка сайта

/slider/1.jpg /slider/2.jpg /slider/3.jpg /slider/4.jpg /slider/5.jpg