ID: 99614

Название работы: Разработка транслятора с ограниченного подмножества языка высокого уровня

Категория: Курсовая

Предметная область: Информатика, кибернетика и программирование

Описание: Описание синтаксиса реализуемого языка в форме Бэкуса-Наура. Синтаксическое дерево языка. Описание разработанного программного обеспечения. Краткое описание лексического анализатора. Классы лексем. Примеры входного и выходного фалов для лексического анализатора. Краткое описание синтаксического анализатора

Язык: Русский

Дата добавления: 2016-09-26

Размер файла: 47.15 KB

Работу скачали: 1 чел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра АСУ

Пояснительная записка к курсовой работе

по предмету: «Теория формальных языков и компиляторов»

на тему: «разработка транслятора с ограниченного подмножества языка высокого уровня»

Вариант №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) – данная функция производит синтаксический анализ основного текста кода (т.е. весь остальной текст после объявления переменных):

1. Если в строке отсутствует знак присваивания “=”, то выводится сообщение об ошибке “ ожидается конструкция вида id=<выражение>” (см. рис.6)
2. Если перед знаком присваивания находится не идентификатор, то выводится соответствующее сообщение об ошибке (см. рис.5,7)
3. Если строка начинается с символов “id = ” (где id – это идентификатор), то вызывается функция E(Sender, j, mas, 0), осуществляющая синтаксический анализ выражения, идущего после знака присвоить.
4. Если в строке находится ключевое слово do, то функция инкрементирует специальную переменную flagdo, изначально равную нулю. В дальнейшем, если найдено ключевое слово while, то данная переменная декрементируется, и в конце синтаксического анализа проверяется значение переменной flagdo, и, если оно не равно нулю, значит, нарушен баланс операторов do…while, и выводится соответствующее сообщение об ошибке (см. рис.7) .
5. Если первой лексемой строки является ключевое слово while, то во-первых, проверяется переменная flagdo, и, если она равна нулю, значит перед оператором while отсутствует оператор do, и выводится соответствующее сообщение об ошибке (см. рис.8) . Во-вторых, проверяется наличие каких либо символов в строке после ключевого слова while, и, если их нет, то выводится соответствующее сообщение об ошибке (см. рис.13) . Иначе, если после ключевого слова while не следует открывающая скобка “(“, то выводится соответствующее сообщение об ошибке (см. рис.10). Если после while следует символ “(“, то вызывается функция Uslovie(Sender, j, mas), осуществляющая синтаксический анализ условия цикла while. После выполнения данной функции проверяется наличие закрывающей скобки “)”, и, при её отсутствии, выводится соответствующее сообщение об ошибке (см. рис.10, 14).

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).

Тестирование

Листинг

14