Федеральное агентство связи
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
“Поволжский университет телекоммуникаций и информатики”
Факультет информационных систем и технологий
Кафедра программного обеспечения вычислительной техники
и управления в технических системах
КУРСОВАЯ РАБОТА
по теории языков программирования и методов трансляции
Разработка компилятора модельного языка
Пояснительная записка
Руководитель работы
_______________
"____"______________2014г.
Исполнитель
студентка гр. ПО-12у __________________
"____"______________2014г.
Самара 2014
Содержание
Введение 3
1. Постановка задачи 5
2. Формальная модель задачи 6
2.1 Формальные грамматики 6
2.2 Формы Бэкуса-Наура (БНФ) 6
2.3 Расширенные формы Бэкуса-Наура (РБНФ) 7
3. Спецификация основных процедур и функций 9
3.1 Лексический анализатор 9
3.2 Синтаксический анализатор 14
3.3 Семантический анализатор 14
4. Разработка алгоритма решения задачи 16
5. Структурная организация данных 17
5.1Спецификация входной информации 17
5.2Спецификация выходной информации 17
6. Установка и эксплуатация ПО 18
ЗАКЛЮЧЕНИЕ 19
СПИСОК ЛИТЕРАТУРЫ 20
Приложение 1. Проверка работоспособности программы 21
Приложение 2. Листинг программы 212
Введение
Компилятор - это программа, которая осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблере.
Несмотря на более чем полувековую историю вычислительной техники, формально годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма творческим процессом. Лишь появление теории формальных языков и строгих математических моделей позволило перейти от творчества к науке. Именно благодаря этому, стало возможным появление сотен новых языков программирования.
Несмотря на то, что к настоящему времени разработаны тысячи различных языков и их компиляторов, процесс создания новых приложений в этой области не прекращается. Это связно как с развитием технологии производства вычислительных систем, так и с необходимостью решения все более сложных прикладных задач. Такая разработка может быть обусловлена различными причинами, в частности, функциональными ограничениями, отсутствием локализации, низкой эффективностью существующих компиляторов. Поэтому, основы теории языков и формальных грамматик, а также практические методы разработки компиляторов лежат в фундаменте инженерного образования по информатике и вычислительной технике.
Цель курсовой работы:
-закрепление теоретических знаний в области теории формальных языков, грамматик, автоматов и методов трансляции;
-формирование практических умений и навыков разработки собственного компилятора модельного языка программирования;
закрепление практических навыков самостоятельного решения инженерных задач, развитие творческих способностей студентов и умений пользоваться технической, нормативной и справочной литературой.
В настоящее время в мире появляются более новые языки программирования и не каждый из ныне существующих трансляторов могут прочитать программы, написанный на новом языке, и перевести его в другой язык. Поэтому сейчас разрабатываются новые трансляторы, в этом и заключается актуальность данной курсовой работы.
1. Постановка задачи
Разработать компилятор модельного языка, выполнив следующие действия:
1. Написать пример программы, раскрывающих особенности конструкций учебного языка программирования, отразив его функциональные возможности.
2. Составить таблицу лексем для тестового примера.
3. Разработать программное средство, реализующее лексический анализ текста программы на входном языке.
4. Вывести примеры таблиц идентификаторов и чисел.
5. Реализовать синтаксический анализатор текста программы на модельном языке методом рекурсивного спуска.
6. Дополнить синтаксический анализатор процедурами проверки семантической правильности программы на модельном языке в соответствии с контекстными условиями варианта.
2. Формальная модель задачи
Существуют три основных метода описания синтаксиса языков программирования: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта.
2.1 Формальные грамматики
Определение.Формальной грамматикой называется четверка вида:
,
где VN- конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);
VT - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.),VTVN =;
Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (VT VN)+ (VT VN)*; элемент (, ) множества Р называется правилом вывода и записывается в виде (читается: «из цепочки выводится цепочка »);
S - начальный символ грамматики, S VN.
Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи .
2.2 Формы Бэкуса-Наура (БНФ)
Метаязык, предложенный Бэкусом и Науром, использует следующие обозначения:
- символ «::=» отделяет левую часть правила от правой (читается: «определяется как»);
- нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки «<» и «>»;
- терминалы - это символы, используемые в описываемом языке;
- правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или»).
2.3 Расширенные формы Бэкуса-Наура (РБНФ)
Для повышения удобства и компактности описаний, в РБНФ вводятся следующие дополнительные конструкции (метасимволы):
- квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;
- фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;
сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;
круглые скобки «(» и «)» используются для ограничения альтернативных конструкций.
В соответствии с данными правилами синтаксис модельного языка будет выглядеть следующим образом:
<буква>:: =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)
<идентификатор>::= <буква>{ <буква> | <цифра> }
<число> ::= {/<цифра> /}
<ключевое_слово>::= dim |ass | % |!| $ | if | then | else | for | to | do| while | end |read |write | true | false
<разделитель>::= <> | = | < | < = | >| >= | ( | ) | { | }| / | * | :
<программа>= {/(<описание> | <оператор>) (: | переходстроки) /} end
<описание>::= dim<идентификатор> {, <идентификатор> }<тип>
<составной>::= <оператор> { ( : | перевод строки) <оператор> }
<присваивания>::= <идентификатор>ass<выражение>
<условный>::= if<выражение>then<оператор>[ else<оператор>]
<фиксированного_цикла>::= for<присваивания>to<выражение>do<оператор>
<условного_цикла>::= while<выражение>do<оператор>
<ввода>::= read (<идентификатор> {, <идентификатор> })
<вывода>::= write (<выражение> {, <выражение> })
3. Спецификация основных процедур и функций
3.1 Лексический анализатор
Лексический анализатор (ЛА) – это первый этап процесса компиляции, на котором символы, составляющие исходную программу, группируются в отдельные минимальные единицы текста, несущие смысловую нагрузку – лексемы.
Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобному для последующей обработки. ЛА использует регулярные грамматики.
ЛА необязательный этап компиляции, но желательный по следующим причинам:
1) замена идентификаторов, констант, ограничителей и служебных слов лексемами делает программу более удобной для дальнейшей обработки;
2) ЛА уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии;
3) если будет изменена кодировка в исходном представлении программы, то это отразится только на ЛА.
В процедурных языках лексемы обычно делятся на классы:
1) операторы;
2) разделители;
3) числа;
4) идентификаторы.
Каждая лексема представляет собой пару чисел вида (n, k), где n – номер таблицы лексем, k - номер лексемы в таблице.
Входные данные ЛА - текст транслируемой программы на входном языке.
Выходные данные ЛА - списковая структура, содержащая лексемы в числовом представлении.
Для модельного языка таблица операторов(1):
0. dim 1. end 2. % 3. ! 4. $
5. read 6. write 7. for 8. to 9. do
10. while 11. if 12. then 13. else 14. true 15. false
Таблицаразделителей(2):
0. <> 1. = 2. < 3. <=
4. > 5. >= 6. + 7. -
8. or 9. / 10. not 11.
12. * 13. : 14. ass 15. and
16. ( 17. ) 18. . 19. { 20. }
Таблицы идентификаторов (4) и таблица чисел(3) формируются в ходе лексического анализа.
Опишем результаты работы лексического анализатора для модельного языка М.
Входные данные ЛА:
dim A,I %:
dim Min %:
Min ass 32767:
for I ass 1 to 10 do
read (A)
if A< Min then Min ass A: {poiskminimalnogo}
write(Min):
end
Выходные данные ЛА:
(0,0) (3,0) (1,18) (3,1) (0,2) (1,13) (1,11) (0,0) (3,2) (0,2) (1,13) (1,11) (3,2) (1,14) (2,0) (1,13) (1,11) (0,7) (3,1) (1,14) (2,1) (0,8) (2,2) (0,9) (1,11) (0,5) (1,16) (3,0) (1,17) (1,11) (0,11) (3,0) (1,2) (3,2) (0,12) (3,2) (1,14) (3,0) (1,13) (1,11) (0,6) (1,16) (3,2) (1,17) (1,13) (1,11) (0,1)
Анализ текста проводится путем разбора по регулярным грамматикам и опирается на способ разбора по диаграмме состояний, снабженной дополнительными пометками-действиями. Для удобства разбора вводится дополнительное состояние диаграммы ERR, попадание в которое соответствует появлению ошибки в алгоритме разбора. Переход по дуге, не помеченной ни одним символом, осуществляется по любому другому символу, кроме тех, которыми помечены все другие дуги, выходящие из данного состояния.
Составим ЛА для модельного языка . Предварительно введем следующие обозначения для переменных, процедур и функций.
Переменные:
1) СН – очередной входной символ;
2) S – буфер для накапливания символов лексемы;
3) B – переменная для формирования числового значения константы;
4) CS – текущее состояние буфера накопления лексем с возможными значениями: P – начало, I – идентификатор, N – число, С – комментарий, M – конец программы («.»), D – дробное число, D1 – знак после «е», D2 – считывание степени, D3 – запись дробного числа, NB – запись 2-го числа, NV – запись 8-го числа, NS – 16-го числа, ND – запись десятичного числа, NH – проверка 16-е число или ошибка, L1 – проверка знака «>=» и «<>», L2 –проверка знака «<=», V – выход, ER –ошибка;
6) t - таблица лексем анализируемой программы с возможными значениями: TW – таблица служебных слов М-языка, TL – таблица ограничителей М-языка, TI – таблица идентификаторов программы, TC – таблица целых чисел, TD – таблица вещественных чисел;
7) z - номер лексемы в таблице t (если лексемы в таблице нет, то z=0).
LEX – переменная, содержащая текущую лексему, считанную из файла лексем;
8) gl – процедура считывания очередной лексемы из файла лексем в переменную LEX;
9) EQ(S) – логическая функция, проверяющая, является ли текущая лексема LEX лексемой для S;
10) NUM - логическая функция, проверяющая, является ли LEX числом.
Процедуры и функции:
1) gc – процедура считывания очередного символа текста в переменную СН;
2) let – логическая функция, проверяющая, является ли переменная СН буквой;
3) digit - логическая функция, проверяющая, является ли переменная СН цифрой;
4) nill – процедура очистки буфера S;
5) add – процедура добавления очередного символа в конец буфера S;
6) look(n,k) – процедура поиска лексемы из буфера S в таблице с номером n с возвращением номера лексемы в таблице, k – количество элементов в таблице;
7) put(t) – процедура записи лексемы из буфера S в таблицу t, если там не было этой лексемы, возвращает номер данной лексемы в таблице;
8) out(n, k) – процедура записи пары чисел (n, k) в файл лексем;
10) nill – очистке бефера S;
11) let – проверка является ли символ буквой;
Рис. 1 – Диаграмма состояний с действиями для модельного языка М
3.2 Синтаксический анализатор
Задача синтаксического анализатора: провести разбор текста программы, сопоставив его с эталоном, данным в описании языка. Для синтаксического разбора используются контекстно-свободные грамматики (КС-грамматика).
Один из эффективных методов синтаксического анализа – метод рекурсивного спуска.
Метод рекурсивного спуска или нисходящий разбор – это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному контекстно-свободной грамматикой (КС-грамматика).
Входные данные – файл лексем в числовом представлении.
Выходные данные – заключение о синтаксической правильности программы или сообщение об имеющихся ошибках.
3.3 Семантический анализатор
В ходе семантического анализа проверяются отдельные правила записи исходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями.
В программе синтаксический и семантический анализаторы совмещены и осуществляются параллельно.
Соблюдение контекстных условий для языка М предполагает три типа проверок:
1) обработка описаний;
2) анализ выражений;
3) проверка правильности операторов.
В оптимизированном варианте синтаксический и семантический анализаторы совмещены и осуществляются параллельно. Поэтому процедуры СеА будем внедрять в ранее разработанные процедуры СиА.
Вход: файл лексем в числовом представлении.
Выход: заключение о семантической правильности программы или о типе обнаруженной семантической ошибки.
Задача обработки описаний – проверить, все ли переменные программы описаны правильно и только один раз.
Задача анализа выражений – проверить описаны ли переменные, встречающиеся в выражениях, и соответствуют ли типы операндов друг другу и типу операции.
Задачи проверки правильности операторов:
1) выяснить, все ли переменные, встречающиеся в операторах, описаны;
2) установить соответствие типов в операторе присваивания слева и справа от символа «=»;
3) определить, является ли выражение E в операторах условия и цикла булевым.
Задача решается проверкой типов в соответствующих местах программы.
На основе лексем с помощью рекурсивного спуска анализируется цепочка идущих лексем и на выходе получается программа в виде дерева, в узлах (Node) которого проводится одна маленькая операция.
Если при анализе цепочек лексем возникает ошибка или встретилась неизвестная лексема или лексема не принадлежащая анализируемому оператору, то вызывается исключение с текстом ошибки.
4. Разработка алгоритма решения задачи
Рис.2 Общая схема работы компилятора
5. Структурная организация данных
5.1 Спецификация входной информации
В программе используется три типа класса:
classLexicalAnalysis для лексического анализа;
classParsing для синтаксического и семантического анализа
classError для вывода ошибок
Входными данными данного программного средства является текст программы на модельном языке. В главное окно программы вводится текст, который в последующем анализируется и интерпретируется в машинный исполняемый код.
Таблица 1 – Входная информация
Имя Тип Назначение
Text string Текст программы на модельном языке
5.2 Спецификация выходной информации
Выходными данными является заключение о лексической, синтаксической и семантической правильности введенной программы, или сообщение об ошибке с указанием номера строки и характером ошибки. А также запускается консольное приложение, непосредственно реализующее описанный в тексте программы алгоритм.
Таблица 2 – Выходная информация
Имя Тип Назначение
numbers List<string> Список чисел, результат работы лексического анализатора
identif List<string> Список идентификаторов, результат работы лексического анализатора
lexList List<Lex> Список лексем, результат работы лексического анализатора
6. Установка и эксплуатация ПО
Для того чтобы установить данное программное средство на ПК необходимо подключить носитель (CD, FlashDevice), на котором это программное средство находится. Далее необходимо открыть проводник, найти данный носитель информации, найти на нем данное программное средство и скопировать его на локальный диск (винчестер).
Данное программное средство позволяет быстро получить результат, не требуя больших затрат ресурсов компьютера. Оно предназначено для использования в семействе операционных систем MSWindows. Поставляется оно в виде одного файла размером 28 Кбайт. Для работы необходимо запустить исполняемыйexe-файл.
ЗАКЛЮЧЕНИЕ
Разработали на языке программирования C# в среде MicrosoftVisualStudio 2010 на базе Microsoft NET Framework4.0 программное средство, реализующее компилятор модельного языка программирования.
Программное средство способно выполнять следующие функции:
- ввод и редактирование текста программ, написанных на определенном модельном языке;
- производить лексический анализ программ;
- выполнять синтаксическую и семантическую проверку программ;
В случае возникновения ошибок на любом из этапов работы программы информирует о них пользователя.
Программное средство протестировано на различных программах, написанных на модельном языке.
СПИСОК ЛИТЕРАТУРЫ
1. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. – М.: Изд. дом «Вильямс», 2001. – 768с.
2. Опалева Э. А., Самойленко В. П. Языки программирования и методы трансляции. – СПб.: БХВ-Петербург, 2005. – 480 с.: ил.
3. Ишакова Е. Н. Разработка компиляторов: Методические указания к курсовой работе. – Оренбург: ГОУ ОГУ, 2005. – 50 с.
4. Афанасьев А.Н. Формальные языки и грамматики: Учебное пособие. – Ульяновск: УлГТУ, 1997. – 84с.
5. Волкова И.А., Руденко Т.В. Формальные языки и грамматики. Элементы теории трансляции. – М.: Диалог-МГУ, 1999. – 62 с.
6. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под ред. А. Матросова. – СПб: Питер, 2002. – 688с.
7. Рейуорд-Смит В. Теория формальных языков. Вводный курс: Пер. с англ. – М.: Радио и связь, 1988. – 128с.
8. Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб.пособие. – М.: Финансы и статистика, 2004. – 320с.
9. Федоров В.В. Основы построения трансляторов: Учебное пособие. – Обнинск: ИАТЭ, 1995. – 105с.
Приложение 1. Проверка работоспособности программы
Рис.3- Лексический анализ
Рис.3- Синтаксический и семантический анализ
Приложение 2. Листинг программы
namespaceAnalis
{
publicclassError : Exception
{
string text;
public Error(string text)
{
this.text = text;
}
publicstring Text
{
get { return text; }
}
}
publicclassLexAnalis// лексическийанализ
{
publicenumTypeLex//типылексем
{
Operator = 0,
Separator = 1,
Constant = 2,
Ident = 3,
Nothing,
Err
};
publicstaticstring[] separators = newstring[]
{
"<>", "=", "<", "<=", ">", ">=", "+", "-","or", "/", "not", "
", "*", ":", "ass", "and", "(", ")", ",", "{", "}"
};
publicstaticstring[] operators = newstring[]
{
"dim", "end", "%", "!", "$", "read", "write", "for", "to", "do", "while", "if", "then", "else" , "true", "false"
};
stringprog;
string value;
TypeLextypeLex;
int index;
charch;
intpos;
List<string>identif;
List<string> constants;
publicLexAnalis(string program)
{
this.prog = program;
identif = newList<string>();
constants = newList<string>();
Comment();
}
boolComment() // проверка комментария
{
if (pos<prog.Length) // если меньше длины программы
{
ch = prog[pos]; // считываем символ
if (ch == {) // если начало комментария
{
while (pos<prog.Length&&prog[pos] != }) pos++; // ищем конец комментария
pos++;
if (pos<prog.Length)
ch = prog[pos];
else
{
ch = (char)0;
returnfalse; //если не закрыт то false
}
}
pos++;
returntrue; // еслизакрыт true
}
else
{
ch = (char)0;
returnfalse;
}
}
publicTypeLex Next() // определениетипалексем
{
TypeLex ret = TypeLex.Nothing;
value = "";
typeLex = TypeLex.Nothing;
while (ch != 0) // покане 0
{
if (ch == )
Comment();
elseif (char.IsDigit(ch)) // проверканацифру
{
value = string.Empty;
while (char.IsDigit(ch) || ch == .) // проверкавещественного
{
value += ch;
Comment();
}
index = constants.IndexOf(value); // ищемвхождения
if (index< 0) // если нет, то добавляем в массив констант
{
index = constants.Count;
constants.Add(value);
}
ret = TypeLex.Constant;
break;
}
elseif (char.IsLetterOrDigit(ch)) // проверкатипачисла
{
value = string.Empty;
while (char.IsLetterOrDigit(ch))
{
value += ch;
Comment();
}
index = IsSepar(value); // проверканаразделитель
if (index >= 0)
ret = TypeLex.Separator;
else
{
index = IsOper(value);
if (index >= 0)
{
ret = TypeLex.Operator; // проверканаоператор
}
else
{
index = identif.IndexOf(value);
if (index < 0)
{
index = identif.Count;
identif.Add(value);
}
ret = TypeLex.Ident;
}
}
break;
}
else
{
value = String.Empty;
value = value + ch;
index = IsSepar(value);
if (index >= 0)
ret = TypeLex.Separator;
else
{
index = IsOper(value);
if (index >= 0)
{
ret = TypeLex.Operator;
}
else
{
ret = TypeLex.Err;
value = "неизвестныйсимвол " + ch + "";
thrownewError(value);
}
}
Comment();
break;
}
}
typeLex = ret;
return ret;
}
intIsSepar(string v)
{
for (int i = 0; i <separators.Length; i++)
if (separators[i] == v)
return i;
return -1;
}
intIsOper(string v)
{
for (int i = 0; i <operators.Length; i++)
if (operators[i] == value)
return i;
return -1;
}
publicstring Value
{
get { return value; }
set { this.value = value; }
}
publicint Index
{
get { return index; }
}
publicList<string>Identif
{
get { returnidentif; }
}
publicList<string> Numbers
{
get { return constants; }
}
publicTypeLex Type
{
get{ returntypeLex; }
}
}
}
using System;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.Threading.Tasks;
usingSystem.Globalization;
usingSystem.Windows.Forms;
namespaceAnalis
{
publicclassParsing
{
LexAnalislexer;
stringtextError;
publicList<string>dimvars;
public Parsing(LexAnalislexer)
{
this.lexer = lexer;
textError = string.Empty;
dimvars = newList<string>();
}
LexAnalis.TypeLexNext(boolIgnEndStr = false) // получаемтипследующегосимвола
{
while (true)
{
LexAnalis.TypeLex type = lexer.Next();
if (!IgnEndStr || lexer.Value != "
")
return type;
}
}
publicNodeParseProgram() // разборпрограммы
{
LexAnalis.TypeLexlexem = Next(true);
{
Blockblock = newBlock();
if (lexem == LexAnalis.TypeLex.Operator&&lexer.Value == "dim") // если dim илиоператор
{
bool flag = false;
while (true)
{
Next(true);
if (lexer.Value == "dim")
{
flag = false;
continue;
}
if (lexer.Type == LexAnalis.TypeLex.Ident&& !flag) // еслиидентификтор
{
block.Append(ParseTypeVar()); // определяемтипидентификаторп
}
else
{
block.Append(ParseInstruct());
returnnewPrg(block, string.Empty);
}
flag = true;
}
}
else
thrownewAnalis.Error("Отсутствует dim илиоператор");
}
}
publicNodeParseInstructs() // разбороператоров
{
Blockblock = newBlock();
while (true)
{
if (lexer.Type == LexAnalis.TypeLex.Ident)
block.Append(ParseVarEqually());
elseif (lexer.Value == "for")
block.Append(ParseFor());
elseif (lexer.Value == "while")
block.Append(ParseWhile());
elseif (lexer.Value == "if")
block.Append(ParseIf());
elseif (lexer.Value == "read")
block.Append(ParseRead());
elseif (lexer.Value == "write")
block.Append(ParseWrite());
elseif (lexer.Value == "end")
{
return block;
}
elseif (lexer.Value == ":")
{
Next();
}
elseif (lexer.Value == "
")
{
Next(true);
return block;
}
elseif (lexer.Type == LexAnalis.TypeLex.Operator)
return block;
else
break;
}
thrownewAnalis.Error("Нетконцапрограммы");
}
publicNodeParseInstruct() // разбор end
{
Blockblock = newBlock();
while (true)
{
Nodenode = ParseInstructs();
block.Append(node);
if (lexer.Value == "end")
{
Next(true);
break;
}
}
return block;
}
publicNodeParseBlock() // разборблоковоператоров
{
returnParseInstructs();
}
publicNodeParseVarEqually() // проверкаобъявленалипеременнаяраннее
{
string name = lexer.Value;
if (dimvars.IndexOf(name) < 0)
thrownewAnalis.Error("Переменная " + name + " не объявлена");
LexAnalis.TypeLexlexem = Next();
if (lexer.Value == "ass")
{
Next();
Nodeexpr = ParseExpr();
returnnewVar(name, expr);
}
else
thrownewAnalis.Error("Ожидался ass, встретился " + lexer.Value);
}
publicNodeParseTypeVar() // разбор переменной по типам
{
List<string>vars = newList<string>();
if (dimvars.IndexOf(lexer.Value) > 0) thrownewAnalis.Error("Переменная " + lexer.Value + " ужеобъявлена ");
vars.Add(lexer.Value);
LexAnalis.TypeLexlexem = Next(true);
while (lexer.Value == ",")
{
lexem = Next(true);
if (lexem == LexAnalis.TypeLex.Ident)
{
if (dimvars.IndexOf(lexer.Value) > 0)
thrownewAnalis.Error("Переменная " + lexer.Value + " ужеобъявлена ");
vars.Add(lexer.Value);
}
else
thrownewAnalis.Error("Ожидалсяидентификатор, встретился " + lexer.Value);
lexem = Next();
}
if (lexem == LexAnalis.TypeLex.Operator&& (lexer.Value == "%" || lexer.Value == "!" || lexer.Value == "$"))
{
stringtypeName = lexer.Value;
Next(true);
dimvars.AddRange(vars);
returnnewTypeVar(typeName, vars);
}
elseif (lexer.Value == "ass") returnParseVarEqually();
else
thrownewAnalis.Error("Типпеременной " + lexer.Value + "неизвестен");
}
publicNodeParseFor() // разбороператора for
{
Next();
Node from = ParseVarEqually();
if (lexer.Value == "to")
{
Next(true);
Node to = ParseExpr();
if (lexer.Value == "do")
{
Next(true);
Node block = ParseBlock();
returnnewFor(from, to, block);
}
else
thrownewAnalis.Error("Отсутствует do вцикле for ");
}
else
thrownewAnalis.Error("Отсутствует to вцикле for ");
}
publicNodeParseWhile() // разбороператора while
{
Next();
Nodeexpr = ParseExpr();
if (lexer.Value == "do")
{
Next(true);
Node block = ParseBlock();
returnnewOpWhile(expr, block);
}
else
thrownewAnalis.Error("Отсутствует do вцикле while ");
}
publicNodeParseIf() // разбороператора if
{
Next();
Nodeexpr = ParseExpr();
if (lexer.Value == "then")
{
Next(true);
NodeblockThen = ParseBlock();
NodeblockElse = null;
if (lexer.Value == "else")
{
Next(true);
blockElse = ParseBlock();
}
returnnewOpIf(expr, blockThen, blockElse);
}
else
thrownewAnalis.Error("Отсутствует then вцикле if ");
}
publicNodeParseRead() // разбороператора read
{
Next();
List<string>vars = newList<string>();
if (lexer.Value == "(")
{
while (Next() == LexAnalis.TypeLex.Ident)
{
vars.Add(lexer.Value);
if (Next() == LexAnalis.TypeLex.Separator)
{
if(lexer.Value == ")" ) break;
if (lexer.Value != ",")
thrownewAnalis.Error("Отсутствует , в операторе read");
}
}
Next();
returnnewOpRead(vars);
}
else
thrownewAnalis.Error("Отсутствует , воператоре read");
}
publicNodeParseWrite() // разбороператора write
{
Next();
List<Node>vars = newList<Node>();
if (lexer.Value == "(")
{
while (true)
{
Next();
vars.Add(ParseExpr());
if (lexer.Type == LexAnalis.TypeLex.Separator)
{
if (lexer.Value == ")")
{
break;
}
if (lexer.Value == ",")
{
}
else
thrownewAnalis.Error("Отсутствует ) воператоре write");
}
}
Next();
returnnewOpWrite(vars);
}
else
thrownewAnalis.Error("Отсутствует ( воператоре write");
}
intOpOrder(string op) // опеределениепорядка
{
switch (op)
{
case"<>": case"=": case"<": case"<=": case">": case">=":
return 0;
case"+": case"-": case"or":
return 1;
case"*": case"/": case"and":
return 2;
}
thrownewAnalis.Error("Неизвестнаяоперация " + op);
}
publicNodeParseExpr() // разбороперацийспеременными
{
Exprexpr = newExpr();
Stack<int>opOrder = newStack<int>();
Stack<string>opName = newStack<string>();
while (true)
{
if (lexer.Type == LexAnalis.TypeLex.Constant)
{
string type = "!";
if (lexer.Value.IndexOf(.) >= 0)
type = "%";
expr.Append(1, lexer.Value, double.Parse(lexer.Value, CultureInfo.InvariantCulture.NumberFormat), type);
}
elseif (lexer.Type == LexAnalis.TypeLex.Ident)
{
int i = dimvars.IndexOf(lexer.Value);
if (i < 0)
thrownewAnalis.Error("Переменная " + lexer.Value + " необъявлена");
expr.Append(2, lexer.Value, 0, string.Empty);
}
elseif (lexer.Value == "not")
{
string op = lexer.Value;
Next();
if (lexer.Type == LexAnalis.TypeLex.Constant)
expr.Append(1, lexer.Value, double.Parse(lexer.Value), "%");
elseif (lexer.Type == LexAnalis.TypeLex.Ident)
{
if (dimvars.IndexOf(lexer.Value) < 0)
thrownewAnalis.Error("Переменная " + lexer.Value + " необъявлена");
expr.Append(2, lexer.Value, 0, string.Empty);
}
else
thrownewAnalis.Error("Ожидалосьчислоилиидентификатор, вместо " + lexer.Value);
expr.Append(3, op, 0, string.Empty);
}
elseif (lexer.Value == "(")
{
opOrder.Push(-1);
opName.Push(lexer.Value);
Next();
continue;
}
else
thrownewAnalis.Error("Ожидалосьчислоилиидентификатор, вместо " + lexer.Value);
Next();
if (lexer.Type == LexAnalis.TypeLex.Separator)
{
if ( lexer.Value == ":" || lexer.Value == "
" || lexer.Value == ",")
{
break;
}
elseif (lexer.Value == ")")
{
bool LP = false;
while (opOrder.Count> 0)
{
int o = opOrder.Pop();
string name = opName.Pop();
if (o == -1)
{
LP = true;
break;
}
expr.Append(0, name, 0, string.Empty);
}
if (!LP) break;
Next();
}
if (lexer.Type == LexAnalis.TypeLex.Separator)
{
int o = OpOrder(lexer.Value);
if (opOrder.Count> 0 &&opOrder.Peek() >= o)
{
opOrder.Pop();
expr.Append(0, opName.Pop(), 0, string.Empty);
}
opOrder.Push(o);
opName.Push(lexer.Value);
}
else
if (lexer.Type == LexAnalis.TypeLex.Operator)
break;
else
thrownewAnalis.Error("Ожидаласьоперация , вместо " + lexer.Value);
}
else
if (lexer.Type == LexAnalis.TypeLex.Operator )
break;
else
thrownewAnalis.Error("Ожидаласьоперацияилиразделитель, вместо " + lexer.Value);
Next();
}
while (opName.Count> 0)
expr.Append(0, opName.Pop(), 0, string.Empty);
returnexpr;
}
}
abstractpublicclassNode
{
}
publicclassPrg : Node
{
Node block;
string name;
publicPrg(Node block, string name)
{
this.block = block;
this.name = name;
}
}
publicclassBlock : Node
{
List<Node> nodes;
public Block()
{
nodes = newList<Node>();
}
publicvoid Append(Node node)
{
nodes.Add(node);
}
}
publicclassTypeVar : Node
{
List<string>vars;
string type;
publicTypeVar(string type, List<string>vars)
{
this.type = type;
this.vars = vars;
}
}
publicclassVar : Node
{
string name;
Nodeexpr;
publicVar(string name, Nodeexpr)
{
this.name = name;
this.expr = expr;
}
}
publicclassFor : Node
{
Node from;
Node to;
Node block;
public For(Node from, Node to, Node block)
{
this.from = from;
this.to = to;
this.block = block;
}
}
publicclassOpWhile : Node
{
Nodeexpr;
Node block;
publicOpWhile(Nodeexpr, Node block)
{
this.expr = expr;
this.block = block;
}
}
publicclassOpIf : Node
{
Nodeexpr;
NodeblockThen;
NodeblockElse;
publicOpIf(Nodeexpr, NodeblockThen, NodeblockElse)
{
this.expr = expr;
this.blockThen = blockThen;
this.blockElse = blockElse;
}
}
publicclassOpRead : Node
{
List<string>vars;
publicOpRead(List<string>vars)
{
this.vars = vars;
}
}
publicclassOpWrite : Node
{
List<Node> nodes;
publicOpWrite(List<Node>vars)
{
this.nodes = vars;
}
}
publicclassExpr : Node
{
classItem
{
publicint type;
publicstring name;
publicdoublenum;
publicstringtypeVar;
}
List<Item> items;
publicExpr()
{
items = newList<Item>();
}
publicvoid Append(int type, string name, doublenum, stringtypeVar)
{
Itemitem = newItem();
item.type = type;
item.name = name;
item.num = num;
item.typeVar = typeVar;
items.Add(item);
}
}
}
Разработка компилятора модельного языка
Курсовая работа по предмету «Программирование»