Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
4 Требования к содержанию работы
Работа должна иметь следующую структуру и состоять из разделов.
Введение
1 Постановка задачи
2 Формальная модель задачи
3 Спецификация основных процедур и функций
3.1 Лексический анализатор
3.2 Синтаксический анализатор
3.3 Семантический анализатор
3.4 Генерация внутреннего представления программы
3.5 Интерпретатор программы
4 Структурная организация данных
4.1 Спецификация входных данных
4.2 Спецификация выходных данных
5 Разработка алгоритма решения задачи
5.1 Укрупненная схема алгоритма программного средства
5.2 Детальная разработка алгоритмов отдельных подзадач
6 Установка и эксплуатация программного средства
7 Работа с программным средством
Заключение
Список использованных источников
Приложение А – Текст программы
Приложение Б – Контрольный пример
Введение. Во введении кратко описывается состояние вопроса разработки компиляторов, формулируются цель и задачи курсовой работы, а также актуальность и обоснованность их решения.
Постановка задачи. Поставленная преподавателем задача разбивается на ряд подзадач, которые необходимо решить для достижения цели курсовой работы.
Формальная модель задачи. Данный раздел содержит положения из теории формальных языков, грамматик и автоматов, лежащие в основе разработки компилятора модельного языка.
Спецификации основных процедур и функций. Для каждой программной единицы необходимо представить входные данные, функции, которые выполняются, и результаты ее работы.
Разработка алгоритма решения задачи. На основе анализа всех функций, которые должно выполнять проектируемое программное средство, необходимо разработать и описать алгоритм решения задачи. В зависимости от выполнения или невыполнения тех или иных условий, показать порядок и последовательность решения задачи. Логическую структуру программного средства представить с помощью укрупненной схемы алгоритма.
Детальная разработка алгоритмов отдельных подзадач. В этом разделе должна быть представлена логическая структура модулей и процедур, составляющих данное программное средство. Для модулей, которые имеют сложную логическую структуру, описание может быть иллюстрировано схемой алгоритма.
Структурная организация данных. В этом разделе необходимо описать данные, используемые в программном средстве (файлы, массивы, и т.д.) их структуру, типы и т.д. Если данные имеют сложную структуру, то описание необходимо пояснять графическими схемами.
Установка программного средства. Описываются все действия, необходимые для установки программного средства (ПС) на ПЭВМ. Также объем, занимаемый ПС на жестком магнитном диске, минимальный объем оперативной памяти, необходимый для его эксплуатации, и другие технические характеристики оборудования.
Работа с программным средством. Здесь поясняется обращение к программе, способы передачи управления, вызов программы и др. Должна быть описана последовательность выполнения работы, средства защиты, разработанные в данном ПС, реакция ПС на неверные действия пользователя.
Заключение. В заключении приводятся основные выводы и перспективы дальнейшего развития представленного ПС.
Список использованных источников представляет собой перечень всей литературы, которая была использована при разработке ПС и оформлении документации на него. Список использованных источников формируется в том порядке, в котором были ссылки на использованную литературу, с указанием издательства, года издания и количества листов в книге согласно СТП101-00.
Приложения должны содержать текст ПС, контрольные и тестовые примеры, результаты работы ПС.
5 Индивидуальные варианты задания
Таблица 5.1 - Операции группы «отношение»
|
Номер |
Синтаксис группы операций(в порядке следования: неравно, равно, меньше, меньше или равно, больше, больше или равно) |
|
1 |
<операции_группы_отношения>:: = < > | = | < | <= | > | >= |
|
2 |
<операции_группы_отношения>:: = != | = = | < | <= | > | >= |
|
3 |
<операции_группы_отношения>::= NE | EQ | LT | LE | GT | GE |
Таблица 5.2 - Операции группы «сложение»
|
Номер |
Синтаксис группы операций(в порядке следования: сложение, вычитание, дизъюнкция) |
|
1 |
<операции_группы_сложения>:: = + | - | or |
|
2 |
<операции_группы_сложения>:: = + | - | || |
|
3 |
<операции_группы_сложения>:: = plus | min | or |
Таблица 5.3 - Операции группы «умножение»
Номер |
Синтаксис группы операций(в порядке следования: умножение, деление, конъюнкция) |
|
1 |
<операции_группы_умножения>::= * | / | and |
|
2 |
<операции_группы_умножения>:: = * | / | && |
|
3 |
<операции_группы_умножения>::= mult | div | and |
Таблица 5.4 - Унарная операция
Номер |
Синтаксис операции |
|
1 |
<унарная_операция>::= not |
|
2 |
<унарная_операция>::= ! |
|
3 |
<унарная_операция>::= ~ |
Выражения языка задаются правилами:
<выражение>::= <операнд>{<операции_группы_отношения> <операнд>}
<операнд>::= <слагаемое> {<операции_группы_сложения> <слагаемое>}
<слагаемое>::= <множитель> {<операции_группы_умножения> <множитель>}
<множитель>::= <идентификатор> | <число> | <логическая_константа> |
<унарная_операция> <множитель> | (<выражение>)
<число>::= <целое> | <действительное>
<логическая_константа>::= true | false
<идентификатор>::= <буква> {<буква> | <цифра>}
<буква>::= 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 /} (B | b)
<восьмеричное>::= {/ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 /} (O | o)
<десятичное>::= {/ <цифра> /} [D | d]
<шестнадцатеричное>::= <цифра> {<цифра> | A | B | C | D | E | F | a | b |
c | d | e | f} (H | h)
Правила, описывающие действительные числа:
<действительное>::= <числовая_строка> <порядок> |
[<числовая_строка>] . <числовая_строка> [порядок]
<числовая_строка>::= {/ <цифра> /}
<порядок>::= ( E | e )[+ | -] <числовая_строка>
Правила, определяющие структуру программы (вторая цифра варианта), представлены в таблице 5.5.
Таблица 5.5 – Структура программы
|
Номер |
Структура программы |
|
1 |
<программа>::= program var <описание> begin <оператор> {; <оператор>} end. |
|
2 |
<программа>::= «{» {/ (<описание> | <оператор>) ; /} «}» |
|
3 |
<программа> = {/ (<описание> | <оператор>) ( : | переход строки) /} end |
Правила, определяющие раздел описания переменных (третья цифра варианта), показаны в таблице 5.6.
Таблица 5.6 - Синтаксис команд описания данных
|
Номер |
Синтаксис команд описания данных |
|
1 |
<описание>::= {<идентификатор> {, <идентификатор> } : <тип> ;} |
|
2 |
<описание>::= dim <идентификатор> {, <идентификатор> } <тип> |
|
3 |
<описание>::= <тип> <идентификатор> { , <идентификатор> } |
Таблица 5.7- Описание типов данных
|
Номер |
Описание типов (в порядке следования: целый, действительный, логический) |
|
1 |
<тип>::= % | ! | $ |
|
2 |
<тип>::= integer | real | boolean |
|
3 |
<тип>::= int | float | bool |
<оператор>::= <составной> | <присваивания> | <условный> |
<фиксированного_цикла> | <условного_цикла> | <ввода> |
<вывода>
Составной оператор описан в таблице 5.8.
Таблица 5.8 - Синтаксис составного оператора
|
Номер |
Синтаксис оператора |
|
1 |
<составной>::= <оператор> { ( : | перевод строки) <оператор> } |
|
2 |
<составной>::= begin <оператор> { ; <оператор> } end |
|
3 |
<составной>::= «{» <оператор> { ; <оператор> } «}» |
Оператор присваивания описан в таблице 5.9.
Таблица 5.9 - Синтаксис оператора присваивания
|
Номер |
Оператор присваивания |
|
1 |
<присваивания>::= <идентификатор> ass <выражение> |
|
2 |
<присваивания>::= <идентификатор> := <выражение> |
|
3 |
<присваивания> ::= [ let ] <идентификатор> = <выражение> |
Оператор условного перехода задан в таблице 5.10.
Таблица 5.10 - Синтаксис оператора условного перехода
|
Номер |
Оператор условного перехода |
|
1 |
<условный>::= if <выражение> then <оператор> [ else <оператор>] |
|
2 |
<условный>::= if (<выражение>) <оператор> [else <оператор>] |
|
3 |
<условный>::= if <выражение> then <оператор> [else <оператор>] end_else |
Оператор цикла с фиксированным числом повторений описан в таблице 5.11.
Таблица 5.11 - Синтаксис оператора цикла с фиксированным числом повторений
|
Номер |
Синтаксис оператора |
|
1 |
<фиксированного_цикла>::= for <присваивания> to <выражение> do <оператор> |
|
2 |
<фиксированного_цикла>::= for <присваивания> to <выражение> [step <выражение>] <оператор> next |
|
3 |
<фиксированного_цикла>::= for ( [<выражение>] ; [<выражение>] ; [<выражение>] ) <оператор> |
Условный оператор цикла задан в таблице 5.12.
Таблица 5.12 - Синтаксис условного оператора цикла
|
Номер |
Синтаксис оператора |
|
1 |
<условного_цикла>::= while <выражение> do <оператор> |
|
2 |
<условного_цикла>::= while (<выражение>) <оператор> |
|
3 |
<условного_цикла>::= do while <выражение> <оператор> loop |
Оператор ввода описан в таблице 5.13.
Таблица 5.13 - Синтаксис оператора ввода
|
Номер |
Синтаксис оператора |
|
1 |
<ввода>::= read (<идентификатор> {, <идентификатор> }) |
|
2 |
<ввода>::= readln идентификатор {, <идентификатор> } |
|
3 |
<ввода>::= input (<идентификатор> {пробел <идентификатор>}) |
Оператор вывода представлен в таблице 5.14.
Таблица 5.14 - Синтаксис оператора вывода
|
Номер |
Синтаксис оператора |
|
1 |
<вывода>::= write (<выражение> {, <выражение> }) |
|
2 |
<вывода>::= writeln <выражение> {, <выражение> } |
|
3 |
<вывода>::= output (<выражение> { пробел <выражение> }) |
Многострочные комментарии в программе (шестая цифра варианта) определены в таблице 5.15. Индивидуальные номера вариантов представлены в таблице 5.16.
Таблица 5.15 – Синтаксис многострочных комментариев
|
Номер |
Признак начала комментария |
Признак конца комментария |
|
1 |
{ |
} |
|
2 |
/* |
*/ |
|
3 |
(* |
*) |
Таблица 5.16 – Индивидуальные номера вариантов
|
Номер варианта |
Номер задания |
Номер варианта |
Номер здания |
|
1 |
111111 |
16 |
223122 |
|
2 |
122211 |
17 |
223322 |
|
3 |
113211 |
18 |
231123 |
|
4 |
113311 |
19 |
232223 |
|
5 |
121132 |
20 |
233323 |
|
6 |
121212 |
21 |
311111 |
|
7 |
123112 |
22 |
311211 |
|
8 |
123312 |
23 |
311311 |
|
9 |
131111 |
24 |
332211 |
|
10 |
132111 |
25 |
313311 |
|
11 |
211121 |
26 |
321122 |
|
12 |
213222 |
27 |
321222 |
|
13 |
213321 |
28 |
323122 |
|
14 |
221122 |
29 |
331133 |
|
15 |
222222 |
30 |
331233 |
6 Контрольные вопросы для самопроверки
1) Назовите основные способы описания синтаксиса языков программирования.
2) Дайте определение понятия «формальная грамматика».
3) Перечислите основные метасимволы, используемые в РБНФ.
4) Изобразите графические примитивы диаграмм Вирта.
5) Дайте определение понятию «компилятор».
6) Каждый ли компилятор является транслятором?
7) Назовите известные Вам компилируемые языки программирования.
8) Перечислите основные функции компилятора.
9) Назовите этапы компиляции.
10) Охарактеризуйте общую схему работы компилятора.
11) Что называется проходом компилятора?
12) Что называется лексемой языка программирования?
13) Какие задачи выполняет лексический анализатор программы?
14) Какой тип грамматик по классификации Хомского лежит в основе лексического анализа программы?
15) Перечислите основные группы лексем языков программирования.
16) Что представляет собой диаграмма состояний с действиями?
17) Расскажите алгоритм разбора цепочек по ДС с действиями.
18) Составьте диаграмму состояний с действиями для модельного языка.
19) Напишите функцию сканирования текста программы на модельном языке по ДС с действиями.
20) Каково назначение синтаксического анализатора программы?
21) Какой тип грамматик по классификации Хомского лежит в основе синтаксического анализа программы?
22) В чем сущность метода рекурсивного спуска?
23) Назовите необходимые условия применимости метода рекурсивного спуска.
24) Какие эквивалентные преобразования КС-грамматик Вам известны?
25) Расскажите алгоритм построения дерева нисходящего разбора для цепочек грамматики.
26) Какой вывод цепочки грамматики называется левосторонним?
27) В чем заключается специфика синтаксически управляемого перевода?
28) Перечислите основные задачи семантического анализатора.
29) Предложите один из возможных способов обработки описаний программы.
30) Запишите синтаксические правила модельного языка, дополненные процедурами семантического анализа программы.
31) Дайте сравнительную характеристику известных форм внутреннего представления программы.
32) Запишите правила перевода в ПОЛИЗ выражений и операторов модельного языка.
Список использованных источников
1 Афанасьев А.Н. Формальные языки и грамматики: Учебное пособие. – Ульяновск: УлГТУ, 1997. – 84с.
2 Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. – М.: Изд. дом «Вильямс», 2001. – 768с.
3 Братчиков И.Л. Синтаксис языков программирования / Под ред. С.С. Лаврова. – М.: Наука, 1975. - 262с.
4 Вайнгартен Ф. Трансляция языков программирования / Под ред. Мартынюка В.В.- М.: Мир, 1977. - 192с.
5 Вильямс А. Системное программирование в Windows 2000 для профессионалов. – СПб.: Питер, 2001. – 624с.
6 Волкова И.А., Руденко Т.В. Формальные языки и грамматики. Элементы теории трансляции. – М.: Диалог-МГУ, 1999. – 62с.
7 Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. – СПб: Питер, 2001. – 736с.
8 Грис Д. Конструирование компиляторов для цифровых вычислительных машин: Пер. с англ. – М.: Мир, 1975. – 544с.
9 Дворянкин А.И. Основы трансляции: Учебное пособие. – Волгоград: ВолгГТУ, 1999. – 80с.
10 Жаков В.И., Коровинский В.В., Фильчаков В.В. Синтаксический анализ и генерация кода. – СПб.: ГААП, 1993. – 26с.
11 Ишакова Е.Н. Теория формальных языков, грамматик и автоматов: Методические указания к лабораторному практикуму. – Оренбург: ГОУ ВПО ОГУ, 2004. – 54с.
12 Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов. – СПб.: Корона принт, 2000. – 256с.
13 Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979. - 654с.
14 Пантелеева И.А. Методы трансляции: Конспект лекций. – Новосибирск: Изд-во НГТУ, 1998. – Ч.2. – 51с.
15 Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под ред. А. Матросова. – СПб: Питер, 2002. – 688с.
16 Рейуорд-Смит В. Теория формальных языков. Вводный курс: Пер. с англ. – М.: Радио и связь, 1988. – 128с.
17 Серебряков В.И. Лекции по конструированию компиляторов. – М.: МГУ, 1997. – 171с.
18 Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб. пособие. – М.: Финансы и статистика, 2004. – 320с.
19 Федоров В.В. Основы построения трансляторов: Учебное пособие. – Обнинск: ИАТЭ, 1995. – 105с.
20 Хантер Р. Проектирование и конструирование компиляторов: Пер. с англ. – М.: Финансы и статистика, 1984. – 232с.
Приложение А
(обязательное)
Пример оформления титульного листа лабораторной работы
Федеральное агентство связи
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
“Поволжский университет телекоммуникаций и информатики”
Факультет информационных систем и технологий
Кафедра программного обеспечения вычислительной техники
и управления в технических системах
ЛАБОРАТОРНАЯ РАБОТА
(16 пт)
по теории языков программирования и методов трансляции
Разработка компилятора модельного языка
(16 пт)
Пояснительная записка
ГОУ ОГУ 220400.5404.13 ПЗ
Руководитель работы
_______________Бахарева Н.Ф.
"____"______________2010г.
Исполнитель
студент гр. 01ПО1 _______________Ковальчук С.В.
"____"______________2010г.
Самара 2010
Примечание – Остальные надписи размером 14 пт.
Приложение Б
(обязательное)
Пример оформления содержания лабораторной работы
Содержание
Введение 3
1 Постановка задачи 4
2 Формальная модель задачи 5
3 Спецификация основных процедур и функций 8
3.1 Лексический анализатор 8
3.2 Синтаксический анализатор 9
3.3 Семантический анализатор 10
3.4 Генерации внутреннего представления программы 11
3.5 Интерпретатор программы 12
4 Структурная организация данных 13
4.1 Спецификация входной информации 13
4.2 Спецификация выходной информации 14
5 Разработка алгоритма решения задачи 15
5.1 Укрупненная схема алгоритма программного средства 16
5.2 Детальная разработка алгоритмов отдельных подзадач 18
6 Установка и эксплуатация программного средства 20
7 Работа с программным средством 21
Заключение 24
Список использованных источников 25
Приложение А – Текст программы 26
Приложение Б – Контрольный пример 31
6 Алгоритм решения задачи
Укрупненная схема алгоритма программного средства представлена на рисунке 6.1.
Приложение В
(обязательное)
Пример оформления приложений лабораторной работы
Приложение А
(обязательное)
Контрольный пример
Результаты работы лексического анализатора представлены на рисунке А.1.
Рисунок А.1 – Выходные данные лексического анализатора
Приложение Б
(обязательное)
Текст программы
la.h
#include <grids.hpp>
#include <fstream.h>
#include <string.h>
#include <vector>
#include <string>
using std::string;
using std::vector;
// структура, описывающая лексему
struct par{
long n; // номер таблицы
long k; // номер в таблице
};
typedef vector<string> wordtable;
typedef vector<par> parvec;
// состояния диаграммы
enum states {SH, // начало
SI, // идентификатор
SN, // число (до точки)
SND, // дробная часть
SNS, // знак порядка
SNP, // порядок
SO, // ограничитель
SC, // комментарий
SL, // <
SG, // >
SS, // :
SDT, // .
SER, // ошибка
SV}; // выход
class LA;
// класс сканер
class Scanner{
public:
LA * A; // связанный лексический анализатор
string instr; // входная строка с исходным текстом
unsigned long pos; // позиция в строке
long z; // найденная позиция в таблице
long errcode; // код ошибки
char cur; // текущий символ
string S; // строка, формирующая лексему
states State; // состояние дмаграммы
int Scan(); // метод-сканер
char gc(){ // считывание следующего символа
if (pos >= instr.size()){
State = SV;
return cur;
}
return (cur = instr[pos++]);
}
bool letter(){ // проверка символа на букву
return isalpha(cur);
}
bool digit(){ // проверка символа на цифру
return isdigit(cur);
}
long look(wordtable * t); // поиск лексемы S в таблице t
long put(wordtable * t){ // помещение лексемы в таблицу
z = look(t);
if (z >= 0)
return z;
t->push_back(S);
return (z = (t->size() - 1));
}
void out(long n, long z);
};
// класс лексический анализатор
class LA{
public:
wordtable R; // таблица служебных слов
wordtable D; // таблица разделителей
wordtable I; // таблица идентификаторов
wordtable N; // таблица чисел
parvec res; // вектор пар чисел - результат лексического анализа
Scanner S; // сканер
void InTables(char *fname); // ввод таблиц R и D из файла
void OutTable(TStringGrid * G, wordtable * X); // вывод таблицы в StringGrid
int Scan(string s); // сканирование
string ErrorMsg(int code); // сообщение об ошибке по коду
string GetResult(); // сформировать результат в виде строки
void OutTables(char *fname); // вывод таблиц I и N в файл
void OutResult(char *fname); // вывод результата в файл
};
la.cpp
#include "la.h"
// перевод строки в нижний регистр
void tolower(string &s){
for (unsigned long i = 0; i < s.length(); i++)
s[i] = tolower(s[i]);
}
int Scanner::Scan(){
par t;
pos = 0;
State = SH;
errcode = 0;
gc();
while(State != SV && State != SER){
while(State != SV && cur != '\n' && isspace(cur))
gc();
if (State == SV)
break;
if (letter()){ // буква
State = SI;
S = cur;
for(gc(); State != SV && (letter() || digit()); gc())
S += cur;
//tolower(S);
look(&A->R);
if (z >= 0)
out(0, z);
else {
put(&A->I);
out(3, z);
}
} else if (digit()){ //число
State = SN;
S = cur;
for(gc(); State != SV && (digit() || strchr("ABCDEFabcdef", cur)); gc())
S += cur;
if (strchr("HhDdOoBb", cur)){
S += cur;
gc();
} else if (cur == '.'){ // дробная часть
State = SND;
S += cur;
for(gc(); State != SV && digit(); gc())
S += cur;
if (cur == 'e' || cur == 'E'){ // порядок
S += cur;
gc();
State = SNS;
if (cur == '+' || cur == '-'){
S += cur;
gc();
}
State = SNP;
for(; State != SV && digit(); gc())
S += cur;
}
} else if ((digit() || cur == '+' || cur == '-') && (S[S.length() - 1] == 'e' || S[S.length() - 1] == 'E')){ // порядок
State = SNP;
for(gc(); State != SV && digit(); gc())
S += cur;
}
put(&A->N);
out(2, z);
} else if (cur == '{'){ // комментарий
State = SC;
for(gc(); State != SV && cur != '}'; gc());
if (State == SV){
errcode = 1;
break;
}
gc();
} else if (cur == '<'){ // < <= <>
State = SL;
gc();
if (cur == '=' || cur == '>'){
S = "<";
S += cur;
gc();
}
else
S = "<";
look(&A->D);
out(1, z);
} else if (cur == '>'){ // > >=
State = SG;
gc();
if (cur == '='){
S = ">=";
gc();
}
else
S = ">";
look(&A->D);
out(1, z);
} else if (cur == ':'){ // : :=
State = SS;
gc();
if (cur == '='){
S = ":=";
gc();
}
else
S = ":";
look(&A->D);
out(1, z);