Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Работа № 103486
Наименование:
Курсовик Транслятор с подмножества языка Ruby
Информация:
Тип работы: Курсовик.
Предмет: Программирование.
Добавлен: 31.01.2017.
Год: 2014.
Страниц: 37 в pdf.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
Содержание Введение ... ... ... 2 1. Анализ технического задания ... ... 3 2. Описание языка ... ... . 4 3. Выбор и обоснование архитектуры системы ... ... 6 4. Выбор и обоснование алгоритмов ... ... 8 5 Описание программы ... ... 14 6 Методика испытаний ... ... 15 Список используемой литературы ... ... 20 Приложение………..21 Изм. Введение С появлением первых компьютеров программисты серьезно задумались над проблемой кодирования компьютерных программ. Уже с конца 40-х го- дов стали появляться первые примитивные языки программирования высоко- го уровня. В них решаемая задача записывалась в виде математических фор- мул, а затем переводилась символ за символом в коды. В дальнейшем специ- альные программы превращали эти коды в двоичный машинный код. Такой программой является транслятор. Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на ре- зультирующем (выходном) языке. То есть транслятор – это часть про- граммного обеспечения, он представляет собой набор машинных команд и данных и выполняется компьютером. Все составные части транслятора представляют собой фрагменты и модули программы со своими входны- ми и выходными данными. Исходными данными для работы транслятора служит текст входной программы – некоторая последовательность предложений входного языка программирования, удовлетворяющая синтаксическим требованиям. Идея транслятора легла в основу создания различных языков програм- мирования, одним из которых является Руби – универсальный, интерпрети- руемый высокоуровневый язык программирования. Синтаксис Руби прост в изучении, в нем придается особое значение читаемости кода, а это сокращает затраты на сопровождение программных продуктов. Итак, чтобы создать транслятор, необходимо прежде всего выбрать входной и выходной языки, построить грамматику входного языка, про- извести лексический, синтаксический и анализ сложного арифметического выражения Изм. Лист № докум. Подп. Дата Лист 1. Анализ технического задания В данной курсовой работе необходимо реализовать транслятор подмножества языка Ruby. Исходя из темы курсовой работы, необходимо, чтобы в программе поддерживались: ?идентификаторы, значащие первые 8 символов. ?Оператор цикла for in ?Сложное арифметическое выражение. Синтаксический разбор – на основе LR-грамматик. Разбор арифметических выражений должен выполняться по методу Бауэра Замельзона. Данная курсовая работа выполняется в несколько этапов: Лексический анализ включает в себя сканирование исходного текста программы, распознавание лексем и их классификацию. Выходная информация подается для дальнейшей обработки транслятором на этапе синтаксического разбора. Синтаксический разбор выполняет выделение синтаксических конструкций в тексте исходной программы, обработанной лексическим анализатором. На этом же этапе проверяется синтаксическая правильность программы. Разбор сложного арифметического выражения – последовательный перевод арифметического выражения в матричную форму записи. Изм. Лист № докум. Подп. Дата Лист 2. Описание языка При записи программы на языке Руби используются символы трех категорий: буквы, цифры, специальные знаки и символ пробел, который используется как разделитель и для оформления программы. К первой категории относятся 26 строчных и прописных букв латинского алфавита и символ “_”, при этом регистр букв не учитывается. Вторая категория – десять арабских цифр. Специальными знаками языка в данном подмножестве языка являются символы: (, ), [, ], =, +, .., *, -, ;, /, ., $: С помощью перечисленных символов образуются величины, выражения и операторы, которые составляют элементы языка. При построении элементов языка используются элементарные конструкции, представляющие собой неделимые символы, образованные из нескольких первичных символов (буквы, цифр, специальных знаков) – идентификаторы,числа служебные слова (терминалы). Идентификаторы состоят из букв и цифр, причем на первом месте должна стоять буква. Длина имени ограничена 8 символами. Числовыми значениями в данном подмножестве языка могут быть только целые числа. Служебными словами в данном подмножестве являются: FOR, IN, END. Сложное арифметическое выражение состоит из элементарных конструкций – идентификаторов, чисел, знаков операций и скобок, которые записываются согласно правилам записи математических выражений. Исходя из правил написания операторов языка, можно составить грамматику данного подмножества языка Руби: Грамматика языка: ‹прог›::=‹спис_опер› $ ‹спис_опер›::=‹опер›|‹спис_опер›‹опер› ‹опер›::=‹услов›|‹присв› ‹присв›::=id=‹сл_ар_выр›; Изм. Лист № докум. Подп. Дата Лист ‹услов›::=for id in ‹диапоз› ‹спис_опер›end ‹диапоз›::=[‹спис_послед›]|lit..lit ‹спис_послед›::=‹послед›|‹спис_послед›,‹послед› ‹послед›::=lit,lit|lit Изм. Лист № докум. Подп. Дата Лист 3. Выбор и обоснование архитектуры системы Для решения поставленной задачи был выбран язык Object Pascal и среда программирования Embarcadero Rad Studio XE4. Задача проектирования транслятора состоит из нескольких подзадач, рассмотренных в анализе технического задания. Реализация каждой из этих задач требует организации определенных процедур и функций, находящихся в основном файле. Программа не имеет дополнительных модулей. Все элементы интерфейса находятся на одной форме. Для решения тех или иных задач в программе используются следующие процедуры: procedure error(oshib:integer); - процедура вывода ошибки procedure sled(); - процедура получения следующего элемента по ТСС procedure rectcc(lexem:string; var theend:integer; table:TStringGrid; var tsstheend:integer; tcctable:TStringGrid; number:integer); procedure SDVIG; - процедура сдвига для LR разбора procedure perehod(a:integer) – процедура перехода к нужному состоянию LR разбора procedure priveden(a:integer; s:string); - процедура приведения к соответствующему правилу грамматики для LR разбора procedure kOP2(operation:strin ); - процедура извлечения из стека Е тройки символов procedure ArifmVyr(); - процедура разбора арифметического выражения procedure LRanalizer(); - процедура LR разбора procedure D1(); процедуры действий метода Бауэра Замельзона соответствующие таблице переходов. procedure D2(); procedure D3(); procedure D4(); procedure D5(); procedure D6(); Изм. Лист № докум. Подп. Дата Лист Глобальные переменные и массивы: Terms: array [0..6] of string=(for,in,end); - Массив служебных слов языка Ruby. tek: string; - Строковая переменная, в которой хранится текущий символ грамматики. index integer; - Переменная, хранящая индекс текущего символа грамматики в ТСС. Stek_E:array [0..30] of string; - стек Е хранящий операнды арифметического выражения. Stek_T:array [0..30] of string; - стек Т хранящий операции арифметического выражения. SS: array [1..100] of byte; - массив хранящий текущие переходы по состояниям SR:array[1..100] of string; - стек хранящий текущее правило грамматики mastss: array [0..1, 0..200] of string; - Таблица ТСС. maslek: array [0..1, 0..30] of string; - Таблица лексем. masrazd: array [0..1, 0..30] of string; - Таблица разделителей. maslit: array [0..1, 0..30] of string; - Таблица литералов. masid: array [0..1, 0..30] of string; - Таблица идентификаторов. lexems: array [0..1 ,0..100] of string; - Таблица лексем. Изм. Лист № докум. Подп. Дата Лист 4. Выбор и обоснование алгоритмов 4.1 Алгоритм лексического разбора Первой основной задачей алгоритма является разбиение входной строки на лексемы. Второй - заполнение соответствующих таблиц. Лексический анализ производится построчно за один полный просмотр исходной программы. Первая задача решается путем преобразования строки текста программы в таблицу лексем, которая содержит текст программы в виде лексем каждая из которых имеет определенный тип – литерал, идентификатор или разделитель. Текст исходной программы состоит из лексических единиц. Распознавание таких объектов, как идентификаторы и литералы выполняются на основе правил языка. После выделения лексемы из входной строки, если она является литералом, то она добавляется в таблицу лексем и ей присваивается тип "L". Если лексема является идентификатором или разделителем, то она заносится в таблицу с типом "I" или "R" соответственно. Вторая задача - просмотр таблицы лексем и заполнение соответствующих таблиц. В процессе просмотра таблицы лексем, лексема в зависимости от типа добавляется в таблицу терминалов, идентификаторов, разделителей или литералов. Добавление происходит только в том случае, когда она еще не находится в таблице. Каждая лексема также добавляется в таблицу стандартных символов в виде номера таблицы и номера строки в соответствующей таблице. 4.2 Алгоритм построения синтаксического анализатора по восходящему методу разбора : 1) Построить присоединённую грамматику 2) Ввести маркерную точку 3) Для каждого нетерминала отмеченного маркером выписать порождаемые им правила с маркером перед самым левым сиволом правой части. 4) Список правил полученных после п. 1-3 назвать состояниями Изм. Лист № докум. Подп. Дата Лист 5) Для каждого символа помеченного маркерной точкой построить переход в другое состояние. Для построения анализатора необходимы: 1) Граф состояний: Состояние Предыдущие состояния Правило грамматики Переход 0 - прог?‹спис_опер›$ ‹спис_опер›?‹опер› ‹спис_опер›?‹спис_опер› ‹опер› ‹опер›?‹услов› ‹опер›?‹присв› ‹присв›?‹сл_ар_выр› ‹услов›?‹диапоз›‹спис_опер›end 1 0 прог‹спис_опер›? ‹спис_опер›‹спис_опер› ?‹опер› ‹опер›?‹услов› ‹опер›?‹присв› ‹присв›?‹сл_ар_выр› ‹услов›?‹диапоз›‹спис_опер›end 2 0 ‹спис_опер›‹опер›? 3 0 ‹опер›‹услов›? 4 0 ‹опер›‹присв›? 5 0 ‹присв›?‹сл_ар_выр› 6 0 ‹услов›?‹диапоз›‹спис_опер›end 7 1 прог‹спис_опер›? 8 1 ‹спис_опер›‹спис_опер› ‹опер›? 9 5 ‹присв›?‹сл_ар_выр› Изм. Лист № докум. Подп. Дата Лист 10 6 ‹услов›?‹диапоз›‹спис_опер›end 11 11 ‹присв›‹сл_ар_выр›? 12 10 ‹услов›?‹диапоз›‹спис_опер›end ‹диапоз›?‹спис_послед› ‹диапоз›? 13 11 ‹присв›‹сл_ар_выр›? 14 12 ‹услов›‹диапоз›?‹спис_опер›end ‹спис_опер›?‹опер› ‹спис_опер›?‹спис_опер›‹опер› ‹опер›?‹услов› ‹опер›?‹присв› ‹присв›?‹сл_ар_выр› 15 12 ‹диапоз›?‹спис_послед› ‹спис_послед›::=?‹послед› ‹спис_послед›?‹спис_послед›‹послед› ‹послед›::=?lit,lit ‹послед›::=?lit 16 12 ‹диапоз›? 17 14 ‹услов›‹диапоз›‹спис_опер›?end 18 15 ‹диапоз›‹спис_послед›? 19 15 ‹спис_послед›::=‹послед›? 20 15 ‹спис_послед›‹спис_послед›?‹послед› 21 15 ‹послед›::=lit?,lit ‹послед›::=lit? 22 16 ‹диапоз›? 23 17 ‹услов›‹диапоз›‹спис_опер› end? 24 18 ‹диапоз›‹спис_послед›]? Изм. Лист № докум. Подп. Дата Лист 25 20 ‹спис_послед›‹спис_послед›?‹послед› ‹послед›::=?lit,lit ‹послед›::=?lit 26 21 ‹послед›::=lit,?lit 27 21 ‹диапоз›? 28 24 ‹спис_послед›‹спис_послед›‹послед›? 29 26 ‹послед›::=lit, lit? 2) Решающая таблица LR –анализатора: Состояние Стек разбора Вход Действие 0 ‹ прог › e ‹спис_опер› ‹опер› ‹услов› ‹присв› id for Конец разбора Сдвиг 1 2 3 4 5 6 1 ‹спис_опер› $ ‹опер› ‹услов› ‹присв› id for Сдвиг 11 12 3 4 5 6 2 ‹опер› Приведение(-1, ‹спис_опер›) 3 ‹услов› Приведение(-1, ‹опер›) 4 ‹присв› Приведение(-1, ‹опер›) 5 id = Сдвиг 9 6 for id Сдвиг 10 7 $ Приведение(-2, ‹ прог ›) 8 ‹опер› Приведение(-2, ‹спис_опер›) 9 = ‹сл_ар_выр› Сдвиг 11 10 Id in Сдвиг 12 Изм. Лист № докум. Подп. Дата Лист 11 ‹сл_ар_выр› ; Сдвиг 13 12 in ‹диапоз› [ lit Сдвиг 14 15 16 13 ; Приведение(-4, ‹присв›) 14 ‹диапоз› ‹спис_опер› ‹опер› ‹услов› ‹присв› id Сдвиг 17 2 4 5 6 15 [ ‹спис_послед› ‹послед› ‹спис_послед› lit ] , Сдвиг 18 19 20 21 16 lit .. Сдвиг 22 17 ‹спис_опер› end Сдвиг 23 18 ‹спис_послед› ] Сдвиг 24 19 ‹послед› Приведение(-1, ‹спис_послед›) 20 ‹спис_послед› , Сдвиг 25 21 Lit Lit , , ] Сдвиг Приведение(-1, ‹послед›) 26 22 .. lit Сдвиг 27 23 end Приведение(-6,‹услов›) 24 ] Приведение(-3, ‹ диапоз ›) 25 , ‹послед› lit Сдвиг 28 21 26 , lit Сдвиг 29 27 lit Приведение(-3, ‹послед›) 28 ‹послед› Приведение(-3, ‹спис_послед›) 29 lit Приведение(-3, ‹послед›) Изм. Лист № докум. Подп. Дата Лист 4.3 Алгоритм разбора сложного арифметического выражения Алгоритм разбора сложного логического выражения необходимо выполнить методом Бауэра - Замельзона. В методе используются два стека и таблица переходов. Один стек, обозначим его E, используется для хранения операндов, другой стек – Т для хранения знаков операций. Над стеком Е выполняются две операции: К(id) – выбрать элемент с именем id из входного потока, положить на вершину стека Е, перейти к следующему элементу входного потока;К(ОР) – извлечь два верхних операнда из стека Е, записать тройку: (ОР, операнд, операнд) в матрицу арифметического (логического) оператора; записать результат на вершину стека Е. Приведём вид таблицы переходов для алгебраических выражений: В таблице переходов задаются действия, которые должен выполнить транслятор при разборе выражения. Возможны шесть действий при прочтении операции ОР из входной строки (ОР1 – операция на вершине стека Т): I Поместить операцию ОР на вершину стека Т; читать следующий символ строки. II Извлечь символ из стека Т (?ОР1), генерировать команду К(ОР1); поместить операцию ОР на вершину стека Т; читать следующий символ строки. III Исключить символ из стека Т; читать следующий символ строки. IV Извлечь символ из стека Т (?ОР1), генерировать команду К(ОР1); поместить операцию ОР на вершину стека Т. V Ошибка. Конец разбора. VI Успешное завершение разбора. Алгоритм метода: Просматриваем входную последовательность элементов слеванаправо. Если подлежащий анализу элемент идентификатор или литерал, то выполняем операцию K(id) и переходим к следующему элементу входного потока. Если текущий элемент – знак операции, то читаем элемент с вершины стека, из таблицы переходов выбираем действие, соответствующее паре (элемент c вершины стека, символ входного потока). Выполняем выбранное действие. Изм. Лист № докум. Подп. Дата Лист 5 Описание программы 5.1 Описание интерфейса Для запуска программы необходимо обратиться к исполняемому файлу Project1.exe. Через несколько секунд на экране появляется окно программы. Визуальный интерфейс программы интуитивно понятен и удобен. В поле «Код программы» пользователь может написать нужный ему код или же воспользоваться уже существующим, воспользовавшись кнопкой «Open». После написания нужного кода следует нажать на кнопку «Analysis». После этого левее поля «Код программы» заполнятся последовательность лексем,а правее ТСС и разбор сложного арифметического выражения. Во вкладке «Таблицы» заполняться таблицы Терминалов, Разделителей, Литералов и Идентификаторов. Рис.5.1 Скриншот программы 5.2 Минимальные требования Программа запускается под управлением операционной системы Windows 7\8\8.1. Для её работы требуется от 12 Мбайт свободной оперативной памяти, видеоадаптер EGA/VGA и процессор не ниже Pentium3. Изм. Лист № докум. Подп. Дата Лист 6 Методика испытаний Тестирование программного средства это процесс выполнения его программ на некотором наборе данных, для которых заранее известны результаты или известно правило поведения программы. В ходе тестирования программа была проверена на правильных и неправильных данных на соответствие техническому заданию и функциональную пригодность. 1. Тестирование программы при отсутствии лексических, синтаксических ошибок и ошибок в выражении: а) Рис. 6.1 Успешный разбор Изм. Лист № докум. Подп. Дата Лист б) Рис . 6.2 Успешный разбор 2. Тестирование программы при наличии лексических и синтаксических ошибок: а) В арифметическом выражении отсутствует один операнд Рис. 6.3 Ошибка в арифметическом выражении при выталкивании из стека Е стек становиться пустым а тройка сиволов операнд1 операд2 операция не полностью извлечена (отсутсвует операнд2) Изм. Лист № докум. Подп. Дата Лист б) Цикл for in Ошибки при описании цикла: Рис. 6.4 Ошибка в правиле: «for id in ‹диапоз›‹спис_опер›end». После написания for id in транслятор ждет ввода диапозона значений в виде [lit,lit,lit…] или lit..lit но открытая квадратная скобка или литерал отсутствуют. Изм. Лист № докум. Подп. Дата Лист в) Проверка на равенство открывающихся и закрывающихся скобок в арифметическом выражении: Рис. 6.5 Ошибка в процедуре ArifmVyr() Так как процедура, реализующая сложное арифметическое выражение дошла до символа «;», а «)» оставался в стеке T, программа прерывает работу и предупреждает пользователя об ошибке. Результаты тестирования показали, что программа правильно выполняет свою задачу при различных вариантах исходного текста. Изм. Лист № докум. Подп. Дата Лист Заключение В результате выполнения данного курсового проекта был создан транслятор программы на подмножестве языка Ruby. Данная программа выполняет лексический, синтаксический разборы, а так же разбор сложного арифметического выражения. Для синтаксического разбора был использован метод LR(k)-грамматик. Для разбора сложного арифметического выражения - метод Бауэра Замельзона. При обнаружении ошибки в исходной программе, разработанная программа выдает подробное сообщение об ошибке, если ошибок нет, то выдает сообщение об успешном выполнении заданных раборов. Таким образом, разработанная в ходе проектирования программа - транслятор соответствует требованиям технического задания. Изм. Лист № докум. Подп. Дата Лист Список используемой литературы 1. Архангельский А.Я. Программирование в Delphi 7. – М.: ООО «Бином-Пресс»,2003 г. – 1152с.: ил. 2. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. – Спб.: Питер, 2001. - 736с. 3. Разработка компиляторов: метод. Указ. По курсовому проектированию. – Муром: ИПЦ МИВлГУ, 2007 – 52с. 4. Фаронов В.В. Delphi. Программирование на языке высокого уровня: Учебник для вузов – Спб.: Питер, 2006. – 640с.: ил. 5. Юров В. Ассемблер. - Спб.: Питер, 2000. – 624с. Изм. Лист № докум. Подп. Дата Лист Приложение Код программы: unit Unit1; interface uses Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.Grids, Vcl.ComCtrls; type TForm1 = class(TForm) OpenDialog1: TOpenDialog; Memo1: TMemo; Open: TButton; Analisys: TButton; StringGrid1: TStringGrid; PageControl1: TPageControl; lexemy: TTabSheet; tablizy: TTabSheet; TabTerm: TStringGrid; TabLiter: TStringGrid; TabPerem: TStringGrid; TabRazd: TStringGrid; TCC: TStringGrid; Label1: TLabel; Label2: TLabel; Label3: TLabel; Label4: TLabel; Label5: TLabel;...
* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.
