99614
Разработка транслятора с ограниченного подмножества языка высокого уровня
Курсовая
Информатика, кибернетика и программирование
Описание синтаксиса реализуемого языка в форме Бэкуса-Наура. Синтаксическое дерево языка. Описание разработанного программного обеспечения. Краткое описание лексического анализатора. Классы лексем. Примеры входного и выходного фалов для лексического анализатора. Краткое описание синтаксического анализатора
Русский
2016-09-26
47.15 KB
2 чел.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра АСУ
Пояснительная записка к курсовой работе
по предмету: «Теория формальных языков и компиляторов»
на тему: «разработка транслятора с ограниченного подмножества языка высокого уровня»
Вариант №1 конструкция DO...WHILE
Выполнил: студент гр. АВТ-113
Селютин И.
Преподаватель: Мыссак М.С.
Новосибирск
2014
Постановка задачи 3
Начальные данные 3
Описание синтаксиса реализуемого языка в форме Бэкуса-Наура 4
Синтаксическое дерево языка 5
Описание разработанного программного обеспечения 7
Краткое описание лексического анализатора 7
Классы лексем 7
Примеры входного и выходного фалов для лексического анализатора 9
Краткое описание синтаксического анализатора 11
Тестирование 14
Листинг 18
Разработать грамматику языка высокого уровня, добавив в него конструкцию DO<Список операторов>WHILE <Выражение>.
Разработать лексический и синтаксический анализатор для данной грамматики
Базовая конструкция языка
Во всех вариантах все переменные должны быть объявлены до начала
вычислений.
<Буква> буква латинского алфавита (a...z).
<Цифра> цифра от 0 до 9.
<Программа> ::= <Объявление переменных> <Описание вычислений>
<Описание вычислений> ::= <Список присваиваний>
<Объявление переменных> ::= Var <Список переменных>
<Список переменных> ::= <Идент> | <Идент> , <Список переменных>
<Список присваиваний> ::= <Присваивание> |
<Присваивание> <Список присваиваний>
<Присваивание> ::= <Идент> = <Выражение>
<Выражение> ::= <Ун.оп.> <Подвыражение> | <Подвыражение>
<Подвыражение> :: = ( <Выражение> ) | <Операнд> |
< Подвыражение > <Бин.оп.> <Подвыражение>
<Ун.оп.> ::= "-"
<Бин.оп.> ::= "-" | "+" | "*" | "/"
<Операнд> ::= <Идент> | <Const>
<Идент> ::= <Буква> <Идент> | <Буква>
<Const> ::= <Цифра> <Const> | <Цифра>
На одной строке может быть только объявление переменных или один оператор присваивания.
Дополнительная конструкция
DO
<Список операторов>
WHILE <Выражение>
В базовой конструкции языка я изменил нетерминальный символ <Идент>, задающий правила записи идентификаторов. Я изменил это правило так, чтобы в идентификаторе помимо букв могли быть и цифры, при этом начинаться он должен с буквы. В связи с этим в грамматике появились новый нетерминал <Буква и Цифра>.
Так же к базовой конструкции я добавил дополнительную конструкцию DO…WHILE. Для этого понадоилось добавить нетерминальные символы <Цикл>, <Условие>,<Логическое выражение>, <Логический знак>, <Знак сравнения>.
<Программа> ::= <Объявление переменных>
<Описание вычислений>
<Описание вычислений> ::= <Список присваиваний>
<Объявление переменных> ::= Var <Список переменных>
<Список переменных> ::= <Идент> | <Идент> ,
<Список переменных>
<Список присваиваний> ::= <Присваивание> | <Цикл> | <Присваивание> <Список присваиваний> | <Цикл>
<Список присваиваний>
<Присваивание> ::= <Идент> = <Выражение>
<Цикл> ::= do <Список присваиваний> while ( <Условие> )
<Условие> ::= <Логическое выражение> |
<Логическое выражение> <Логический знак> <Условие>
<Логическое выражение> ::= ( <Выражение> <Знак сравнения> <Выражение> )
<Логический знак> ::= "or" | "and"
<Знак сравнения> ::= ">" | "<" | "==" | "!="
<Выражение> ::= <Ун.оп.> <Подвыражение> | <Подвыражение>
<Подвыражение> :: = ( <Выражение> ) | <Операнд> | < Подвыражение > <Бин.оп.> <Подвыражение>
<Ун.оп.> ::= "-"
<Бин.оп.> ::= "-" | "+" | "*" | "/"
<Операнд> ::= <Идент> | <Const>
<Идент> ::= <Буква> <Буква и Цифра> | <Буква>
<Буква и Цифра> ::= <Буква> <Буква и Цифра> | <Цифра> <Буква и Цифра> | <Буква> | <Цифра>
<Const> ::= <Цифра> <Const> | <Цифра>
Изобразим синтаксическое дерево с грамматикой G[<Program>] для следующих входных данных:
var a, b, c
a = b + c*(3-a)
do
c = 3 * a
while (a>1 or b<5)
<programma>
------ <ObyavleniePeremennih>
- ------ var
- ------ <SpisokPeremennih>
- - ------ a
- - ------ ,
- - ------ <SpisokPeremennih>
- - - ------ b
- - - ------ ,
- - - ------ <SpisokPeremennih>
- - - - ------ c
- - - - ------ ENTER
------ <OpisanieVichisleniy>
- - <SpisokPrisvaivaniy>
- - ------ a
- - ------ =
- - ------ <E>
- - - ------ <T>
- - - - ------ <O>
- - - - - ------ b
- - - - ------ <B>
- - - ------ <A>
- - - - ------ +
- - - - ------ <T>
- - - - - ------ <O>
- - - - - - ------ c
- - - - - ------ <B>
- - - - - - ------ *
- - - - - - ------ <O>
- - - - - - - ------ (
- - - - - - - ------ <E>
- - - - - - - - ------ <T>
- - - - - - - - - ------ <O>
- - - - - - - - - - ------ 3
- - - - - - - - - ------ <B>
- - - - - - - - ------ <A>
- - - - - - - - - ------ -
- - - - - - - - - ------ <T>
- - - - - - - - - - ------ <O>
- - - - - - - - - - - ------ a
- - - - - - - - - - - <B>
- - - - - - - - - ------ <A>
- - - - - - - ------ )
- - - - - - ------ <B>
- - - - ------ <A>
- - ------ ENTER
- - ------ <SpisokPrisvaivaniy>
- - - ------ do
- - - ------ ENTER
- - - ------ <SpisokPrisvaivaniy>
- - - - ------ c
- - - - ------ =
- - - - ------ <E>
- - - - - ------ <T>
- - - - - - ------ <O>
- - - - - - - ------ 3
- - - - - - ------ <B>
- - - - - - - ------ *
- - - - - ------ <A>
- - - - - - ------ <T>
- - - - - - - ------ <O>
- - - - - - - - ------ a
- - - - - - - ------ <B>
- - - - - - ------ <A>
- - - - ------ ENTER
- - - - - <SpisokPrisvaivaniy>
- - - - - ------ while
- - - - - ------ (
- - - - - ------ <Uslovie>
- - - - - - ------ <E>
- - - - - - - ------ <T>
- - - - - - - - ------ <O>
- - - - - - - - - ------ a
- - - - - - - - ------ <B>
- - - - - - - - <A>
- - - - - - ------ >
- - - - - - ------ <E>
- - - - - - - ------ <T>
- - - - - - - - ------ <O>
- - - - - - - - - ------1
- - - - - - - - ------ <B>
- - - - - - - ------ <A>
- - - - - - ------ or
- - - - - - ------ <Uslovie>
- - - - - - - ------ <E>
- - - - - - - - ------ <T>
- - - - - - - - - ------ <O>
- - - - - - - - - - ------ b
- - - - - - - - - ------ <B>
- - - - - - - - ------ <A>
- - - - - - - ------ <
- - - - - - - ------ <E>
- - - - - - - - ------ <T>
- - - - - - - - - ------ <O>
- - - - - - - - - - ------ 5
- - - - - - - - - ------ <B>
- - - - - - - - - <A>
- - - - - ------ ) - -
- - - - - ------ ENTER
Лексически анализатор как составная часть языкового процессора стоит на первой фазе обработки исходного текста. Его функцией является лексическая свертка исходного текста программы в символы, идентифицируемые в дальнейшем как ключевые слова, числовые константы, встроенные функции и так далее. Кроме того, на этапе лексического анализа происходит так называемая фильтрация незначащей части текста.
Незначащей частью текста мой лексический анализатор будет считать вспомогательные символы, которые не являются носителями смыслового содержания текста. Такими символами являются символы табуляции „\t‟, пробелы „ ‟ и комментарии. Эти символы используются только при редактировании исходного текста, когда необходимо соблюдать определенное форматирование текста и повысить читабельность.
Комментарием считается строка вида /*…*/. Всё, что будет находиться между скобками комментариев, лексический анализатор пометит как комментарий и на этапе синтаксического анализа эта часть текста не будет анализироваться.
Таблица 1 - Классы лексем, различаемые лексическим анализатором
Класс лексем |
Описание |
Пример |
Код |
Целое число без знака |
К данному классу относятся лексемы, состоящие из последовательности цифр. |
3 941 35 |
1 |
Идентификатор |
К данному классу относятся лексемы, состоящие из последовательности цифр и букв латинского алфавита, причём начинаться должны с буквы. |
a bd34 mas1 a1b2 |
2 |
Знаки арифметических операций |
К данному классу относятся лексемы, являющиеся знаком арифметической операции, таким как + - */ = |
+ - * / = |
3 4 5 6 9 |
Скобки |
( ) |
7 8 |
|
Комментарии |
К данному классу относятся лексемы, начинающиеся символами /* и заканчивающиеся символами */ |
/*комментарий*/ |
10 |
ошибка - идентификатор начинается с цифры |
К данному классу относятся лексемы, состоящие из последовательности цифр и букв латинского алфавита, начинающиеся с цифры |
3sd 234rfd 3s |
11 |
ошибка недопустимый символ |
К данному классу относятся лексемы, состоящие из символа или последовательности символов, не входящие в состав известных классов лексем |
% @#$ #_%^& |
12 |
Ключевое слово var |
var |
15 |
|
Ключевое слово do |
do |
17 |
|
Ключевое слово while |
while |
18 |
|
Ключевое слово or |
or |
20 |
|
Ключевое слово and |
and |
21 |
|
Разделительный знак |
К данному классу относятся лексемы, являющиеся знаком , |
, |
16 |
Знаки сравнения |
К данному классу относятся лексемы, являющиеся логическими знаками сравнения |
> < == != |
22 23 24 25 |
Знак конца строки |
К данному классу относятся лексемы, являющиеся признаком конца строки |
\n |
19 |
Лексический анализатор распознаёт лексемы и присваивает им код, сопоставляющий лексему соответствующему классу из таблицы 1. Так же запоминается строка, в которой расположена данная лексема, начальная и конечная позиция. Вся информация запоминается в массив структур, имеющих следующий синтаксис:
struct scaner{
int row; //номер строки
int pos_start; //начальная позиция
int pos_end; //конечная позиция
char* leksema; //лексема
int code; //код лексемы
};
Из массива структур вся информация переписывается в результирующий файл scanner.txt
Входной текст:
var a, 3d, @#
sum = 56 * (a-sd)
ai = k/(a+b*(3d-##))
k = 0
do
a = k * 2
k = k + 1
while ( k<20 or 56-a<100 and 23*(3+f)<2 )
d=k /*hgd*/
Выходной файл scanner.txt
#0 leksema = "var" code = 15 row = 0 pos_start = 0 pos_end = 2
#1 leksema = "a" code = 2 row = 0 pos_start = 4 pos_end = 4
#2leksema = "," code = 16 row = 0 pos_start = 5 pos_end = 5
#3leksema = "3d" code = 11 row = 0 pos_start = 7 pos_end = 8
#4leksema = "," code = 16 row = 0 pos_start = 9 pos_end = 9
#5leksema = "@#" code = 12 row = 0 pos_start = 11 pos_end = 12
#6leksema = "ENTER" code = 19 row = 0 pos_start = 13 pos_end =13
#7leksema = "sum" code = 2 row = 1 pos_start = 0 pos_end = 2
#8leksema = "=" code = 9 row = 1 pos_start = 4 pos_end = 4
#9leksema = "56" code = 1 row = 1 pos_start = 6 pos_end = 7
#10leksema = "*" code = 5 row = 1 pos_start = 9 pos_end = 9
#11leksema = "(" code = 7 row = 1 pos_start = 11 pos_end = 11
#12leksema = "a" code = 2 row = 1 pos_start = 12 pos_end = 12
#13leksema = "-" code = 4 row = 1 pos_start = 13 pos_end = 13
#14leksema = "sd" code = 2 row = 1 pos_start = 14 pos_end = 15
#15leksema = ")" code = 8 row = 1 pos_start = 16 pos_end = 16
#16leksema = "ENTER" code = 19 row = 1 pos_start = 18 pos_end=18
#17leksema = "ai" code = 2 row = 2 pos_start = 0 pos_end = 1
#18leksema = "=" code = 9 row = 2 pos_start = 4 pos_end = 4
#19leksema = "k" code = 2 row = 2 pos_start = 6 pos_end = 6
#20leksema = "/" code = 6 row = 2 pos_start = 7 pos_end = 7
#21leksema = "(" code = 7 row = 2 pos_start = 8 pos_end = 8
#22leksema = "a" code = 2 row = 2 pos_start = 9 pos_end = 9
#23leksema = "+" code = 3 row = 2 pos_start = 10 pos_end = 10
#24leksema = "b" code = 2 row = 2 pos_start = 11 pos_end = 11
#25leksema = "*" code = 5 row = 2 pos_start = 12 pos_end = 12
#26leksema = "(" code = 7 row = 2 pos_start = 13 pos_end = 13
#27leksema = "3d" code = 11 row = 2 pos_start = 14 pos_end = 15
#28leksema = "-" code = 4 row = 2 pos_start = 16 pos_end = 16
#29leksema = "##" code = 12 row = 2 pos_start = 17 pos_end = 18
#30leksema = ")" code = 8 row = 2 pos_start = 19 pos_end = 19
#31leksema = ")" code = 8 row = 2 pos_start = 20 pos_end = 20
#32leksema = "ENTER" code = 19 row = 2 pos_start = 21 pos_end=21
#33leksema = "k" code = 2 row = 3 pos_start = 0 pos_end = 0
#34leksema = "=" code = 9 row = 3 pos_start = 2 pos_end = 2
#35leksema = "0" code = 1 row = 3 pos_start = 4 pos_end = 4
#36leksema = "ENTER" code = 19 row = 3 pos_start = 5 pos_end = 5
#37leksema = "do" code = 17 row = 4 pos_start = 0 pos_end = 1
#38leksema = "ENTER" code = 19 row = 4 pos_start = 2 pos_end = 2
#39leksema = "a" code = 2 row = 5 pos_start = 0 pos_end = 0
#40leksema = "=" code = 9 row = 5 pos_start = 2 pos_end = 2
#41leksema = "k" code = 2 row = 5 pos_start = 4 pos_end = 4
#42leksema = "*" code = 5 row = 5 pos_start = 6 pos_end = 6
#43leksema = "2" code = 1 row = 5 pos_start = 8 pos_end = 8
#44leksema = "ENTER" code = 19 row = 5 pos_start = 9 pos_end = 9
#45leksema = "k" code = 2 row = 6 pos_start = 0 pos_end = 0
#46leksema = "=" code = 9 row = 6 pos_start = 2 pos_end = 2
#47leksema = "k" code = 2 row = 6 pos_start = 4 pos_end = 4
#48leksema = "+" code = 3 row = 6 pos_start = 6 pos_end = 6
#49leksema = "1" code = 1 row = 6 pos_start = 8 pos_end = 8
#50leksema = "ENTER" code = 19 row = 6 pos_start = 9 pos_end = 9
#51leksema = "while" code = 18 row = 7 pos_start = 0 pos_end = 4
#52leksema = "(" code = 7 row = 7 pos_start = 6 pos_end = 6
#53leksema = "k" code = 2 row = 7 pos_start = 8 pos_end = 8
#54leksema = "<" code = 23 row = 7 pos_start = 9 pos_end = 9
#55leksema = "20" code = 1 row = 7 pos_start = 10 pos_end = 11
#56leksema = "or" code = 20 row = 7 pos_start = 13 pos_end = 14
#57leksema = "56" code = 1 row = 7 pos_start = 16 pos_end = 17
#58leksema = "-" code = 4 row = 7 pos_start = 18 pos_end = 18
#59leksema = "a" code = 2 row = 7 pos_start = 19 pos_end = 19
#60leksema = "<" code = 23 row = 7 pos_start = 20 pos_end = 20
#61leksema = "100" code = 1 row = 7 pos_start = 21 pos_end = 23
#62leksema = "and" code = 21 row = 7 pos_start = 25 pos_end = 27
#63leksema = "23" code = 1 row = 7 pos_start = 29 pos_end = 30
#64leksema = "*" code = 5 row = 7 pos_start = 31 pos_end = 31
#65leksema = "(" code = 7 row = 7 pos_start = 32 pos_end = 32
#66leksema = "3" code = 1 row = 7 pos_start = 33 pos_end = 33
#67leksema = "+" code = 3 row = 7 pos_start = 34 pos_end = 34
#68leksema = "f" code = 2 row = 7 pos_start = 35 pos_end = 35
#69leksema = ")" code = 8 row = 7 pos_start = 36 pos_end = 36
#70leksema = "<" code = 23 row = 7 pos_start = 37 pos_end = 37
#71leksema = "2" code = 1 row = 7 pos_start = 38 pos_end = 38
#72leksema = ")" code = 8 row = 7 pos_start = 40 pos_end = 40
#73leksema = "ENTER" code = 19 row = 7 pos_start = 41 pos_end=41
#74leksema = "d" code = 2 row = 8 pos_start = 0 pos_end = 0
#75leksema = "=" code = 9 row = 8 pos_start = 1 pos_end = 1
#76leksema = "k" code = 2 row = 8 pos_start = 2 pos_end = 2
#77leksema = "/*hgd*/" code = 10 row = 8 pos_start = 4 pos_end=10
#78leksema = "ENTER" code = 19 row = 8 pos_start = 11 pos_end=11
Так как моя грамматика не является автоматной и в определении нетерминала может рекурсивно вызываться этот же определяемый нетерминал, то целесообразно реализовать синтаксический анализатор методом рекурсивного спуска. Основная идея метода рекурсивного спуска состоит в том, что каждому нетерминалу грамматики ставится в соответствие определенная функция, которая распознает цепочку, порождаемую этим нетерминалом. Эти функции вызываются в соответствии с правилами грамматики, причем иногда вызывают сами себя рекурсивно. Следовательно, языком реализации этого метода может быть лишь такой язык, который допускает рекурсию (в моём случае это язык C++).
Итак, синтаксический анализатор содержит следующие функции:
Programma(TObject *Sender, int &j, scaner *mas) входными данными являются следующие аргументы: &j порядковый номер лексемы, с которой следует начинать синтаксический анализ (передача производится по ссылке, чтобы изменение счётчика j сохранились при выходе из функции); scaner *mas массив структур, содержащий лексемы, полученные в результате лексического анализа текста. Данная функция последовательно вызывает функции ObyavleniePeremennih(Sender, j, mas) и OpisanieVichisleniy(Sender, j, mas).
ObyavleniePeremennih(TObject *Sender, int &j, scaner *mas) данная функция проверяет наличие ключевого слова var в начале текста. Если ключевое слово найдено, то вызывается функция SpisokPeremennih(Sender, j, mas), иначе выводится сообщение об ошибке " Отсутствует var" (см. рис.1) и происходит завершение функции.
SpisokPeremennih(TObject *Sender, int &j, scaner *mas) функция, реализующая синтаксический анализ символов строки, следующих после ключевого слова var. При обнаружении ошибок выводятся соответствующие предупреждения (см. рис.2).
OpisanieVichisleniy(TObject *Sender, int &j, scaner *mas) данная функция вызывает функцию SpisokPrisvaivaniy(Sender, j, mas).
SpisokPrisvaivaniy(TObject *Sender, int &j, scaner *mas) данная функция производит синтаксический анализ основного текста кода (т.е. весь остальной текст после объявления переменных):
E(TObject *Sender, int &j, scaner *mas, int h) данная функция осуществляет синтаксический анализ арифметических выражений. Здесь появился новый аргумент int h. Он применяется для того, чтобы различить, из какой функции вызвана функция Е. Если из операторы присваивания, то h=0, если из условия цикла while, то h=1. Это нужно для того, чтобы корректно производить синтаксический разбор выражений в условии цикла while, так как там заканчивать разбор нужно не при конце строки, как в операторе присваивания, а при встречи ключевых слов or или and или встречи знаков логического сравнения <, >, ==, !=. При обнаружении синтаксических ошибок в арифметическом выражении, выводятся соответствующие предупреждения (см. рис.4,5,6,15).
Функция Е использует для синтаксического разбора арифметических выражений вспомогательные функции T(Sender, j, mas, h), A(Sender, j, mas, h), O(Sender, j, mas, h) и B(Sender, j, mas, h). Порядок взаимодействия данных функций можно отобразить с помощью следующей грамматики G[E]:
E → TA
A → ε | + TA | - TA
T → ОВ
В → ε | *ОВ | /ОВ
О → num | id | (E)
Данный алгоритм обнаружения синтаксических ошибок в арифметических выражениях реализуется методом рекурсивного спуска.
Uslovie(TObject *Sender, int &j, scaner *mas) данная функция вызывает функцию LogicheskoeVyrajenie(Sender, j, mas), которая осуществляет синтаксический анализ логического выражения вида <Выражение> <Знак сравнения> <Выражение>. Затем, если после выполнения данной функции следует лексема or или and, то опять вызывается функция LogicheskoeVyrajenie(Sender, j, mas), и так далее до конца строки. Если в логическом выражении найдены синтаксические ошибки, то выводятся соответствующие предупреждения (см. рис.12,14,15).
LogicheskoeVyrajenie(TObject *Sender, int &j, scaner *mas) данная функция вызывает функцию E(Sender, j, mas, 1), затем, если после выражения, проанализированного функцией Е, следует знак логического сравнения (>,<, ==, !=), то опять вызывается функция E(Sender, j, mas, 0), иначе выводится сообщение об ошибке «В условии выхода из цикла не хватает знака сравнения > или <» (см. рис.12,14).
А также другие работы, которые могут Вас заинтересовать | |||
68864. | ІННОВАЦІЙНА ДІЯЛЬНІСТЬ ПІДПРИЄМСТВА ТА ЇЇ ЕФЕКТИВНІСТЬ | 201 KB | |
Суть науково-технічного прогресу полягає у безперервному процесі одержання і нагромадження наукових знань їх матеріалізації в елементи техніки та впровадження останньої у виробництво і всі сфери життя. Такі зміни виявляються насамперед у появі специфічної ланки машин автоматичного керуючого пристрою який долає... | |||
68865. | ЯКІСТЬ ПРОДУКЦІЇ ТА ЇЇ КОНКУРЕНТОСПРОМОЖНІСТЬ | 175 KB | |
Поняття якості продукції та її основні показники Важливою умовою підвищення ефективності сучасного промислового виробництва є постійне поліпшення якості продукції. Підвищення якості продукції необхідно розглядати з соціальної технічної і економічної точок зору. | |||
68866. | ФОРМИ РАЦІОНАЛЬНОЇ ОРГАНІЗАЦІЇ ВИРОБНИЦТВА | 110 KB | |
Поняття форм і показники рівня концентрації виробництва Процес концентрації виробництва це процес зосередження виробництва на дедалі більших підприємствах який характеризується зростанням питомої ваги великих підприємств у загальному випуску продукції даної галузі або в її сумарній потужності. | |||