Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

• Введение
• 1. Организация таблицы идентификаторов
• 1.1 Исходные данные
• 1.2 Назначение таблицы идентификаторов
• 1.3 Метод бинарного дерева
• 1.4 Метод цепочек
• 1.6 Вывод
• 2. Проектирование лексического анализатора
• 2.1 Исходные данные
• 2.2 Назначение лексического анализатора
• 2.3 Схема распознавателя
• 2.4 Результат выполнения программы
• 2.5 Вывод
• 3. Построение дерева вывода
• 3.1 Исходные данные
• 3.2 Синтаксический анализатор
• 3.3 Таблицы предшествования
• 3.4 Результат выполнения программы
• 3.5 Вывод
• Заключение
• Список литературы
• Приложение А - Листинги программы

Введение

Компилятор - программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.

Большинство компиляторов переводят программу с некоторого высокоуровневого языка программирования в машинный код, который может быть непосредственно выполнен компьютером.

Целью данной курсовой работы является изучение составных частей, основных принципов построения и функционирования компиляторов, практическое освоение методов построения составных частей компилятора для заданного входного языка.

Курсовая работа заключается в создании отдельных частей компилятора заданного языка.

В первой части работы ставится задача разработать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Программа должна сообщать среднее число коллизий и среднее количество сравнений, выполняемых для поиска идентификатора.

Во второй части работы требуется разработать программу, которая выполняет лексический анализ входного текста по заданной грамматике и порождает таблицу лексем с указанием их типов и значений.

В третьей части работы требуется разработать программу, которая на основании таблицы лексем выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора.

Результатами курсовой работы являются программная реализация заданного компилятора и пояснительная записка, оформленная в соответствии с требованиями стандартов и задания на курсовую работу.

В качестве среды разработка для реализации программы использован язык программирования C++ и система программирования Borland CBuilder 6.

1. Организация таблицы идентификаторов

1.1 Исходные данные

На входе имеется набор идентификаторов, которые организуются в таблицу по одному из двух методов (метод бинарного дерева и метод цепочек). Необходима возможность осуществления многократного поиска идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длина идентификатора ограничена 32 символами.

Первый метод организации таблицы - бинарное дерево. Второй - метод цепочек.

Требуется, чтобы программа сообщала число коллизий и количество сравнений, выполняемых при поиске идентификатора.

1.2 Назначение таблицы идентификаторов

Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе и накапливаются в таблице символов или таблице идентификаторов. Любая таблица символов состоит из набора полей, количество которых равно числу идентификаторов программы. Каждое поле содержит в себе полную информацию о данном элементе таблицы. Под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры.

В данной работе мы сравним два метода организации таблицы идентификаторов: метод бинарного дерева и метод цепочек.

1.3 Метод бинарного дерева

Метод построения таблиц, при котором таблица имеет форму бинарного дерева. Каждый узел дерева представляет собой элемент таблицы, причем корневой узел является первым элементом. При построении дерева элементы сравниваются между собой, и в зависимости от результатов, выбирается путь в дереве. Предположим, что надо записать новый идентификатор. Для него выбирается левое поддерево, если этот идентификатор меньше текущего, если же идентификатор больше, выбирается правое поддерево. В случае если текущий узел не является концевым, переходим в следующий узел (согласно выбранному направлению) и опять сравниваем добавляемый идентификатор с текущим.

Для данного метода число требуемых сравнений и форма получившегося дерева во многом зависят от того порядка, в котором поступают идентификаторы.

Блок-схема метода бинарного дерева представлена на рисунке 1.1



Рис. 1. 1 - Блок-схема метода бинарного дерева; а) - Блок-схема алгоритма метода бинарного дерева; б) - Блок-схема функции добавления идентификатора; в) - Блок-схема функции поиска идентификатора

1.4 Метод цепочек

Блок-схема метода цепочек списка представлена на рисунке 1.2



Рис. 1.2 - Блок-схема метода цепочек; а) - Блок-схема алгоритма метод цепочек; б) - Блок-схема функции добавление идентификатора; в) - Блок-схема функции поиска идентификатора

1.5 Результат выполнения программы

Рис. 1.3 - Результаты сравнения методов организации таблицы идентификаторов

При поиске идентификаторов в таблицах организованных методом бинарного дерева и методом цепочек было установлено, что количество сравнений в бинарном дереве в несколько раз больше, чем в методе цепочек.

1.6 Вывод

компилятор заданный язык идентификатор

Для сравнения методов организации таблицы идентификаторов был разработан модуль, иллюстрирующий их работу.

Было выявлено, что метод цепочек является более эффективным, чем метод бинарного дерева, так как для поиска идентификатора используется меньшее количество сравнений.

В дальнейшем для заполнения таблицы идентификаторов исходной программы будем использовать метод цепочек.

2. Проектирование лексического анализатора

2.1 Исходные данные

Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдает сообщения о наличие во входном тексте ошибок, которые могут быть обнаружены на этапе лексического анализа.

Предусмотрены следующие варианты операторов входной программы:

· оператор присваивания вида <переменная>:=<выражение>;

· условный оператор вида if <выражение> then <оператор>

· либо if <выражение> then <оператор> else <оператор>;

· составной оператор вида begin... end;

· оператор цикла do <оператор> while <выражение>;

· арифметические операции сложения (+), вычитания (-), декремент (--);

· операции сравнения «меньше» (<), «больше» (>), «равно» (=);

· логические операции and, or, not;

· операндами в выражениях могут выступать идентификаторы и константы;

· все идентификаторы должны восприниматься как переменные целого типа.

2.2 Назначение лексического анализатора

Лексический анализатор (или сканер) - это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.

В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка.

2.3 Схема распознавателя

Распознаватель лексем языка для данной грамматики задан конечным детерминированным автоматом, схема которого представлена на рисунке 2.1.

Рис. 2.1 - Схема распознавателя

h - начальное состояние автомата

S - конечное состояние автомата

Заданные правила могут быть записаны в форме Бэкуса-Наура.

G(VT, VN, P, S)

VT - множество терминальных символов;

VN - множество нетерминальных символов;

P - множество правил;

S - целевой символ.

Регулярная грамматика входного языка имеет вид:

G (

{0..9, p, r, o,g, e, n, d, t, h, l, s, b, I, w, `+', -, `;', `(`, `)', =, `>', `<', '/', '*'},

{h, A, B, C, D, E, H, G, K, L, M, R, N, O, P, I, J, Q, V, W, X, Y, Z, T, U, F, AA, AM, AB, AC, AD, AG, AF, AH, AI, AE, AK, AL, AJ, AN, AO, AP, AQ, AR, AT, AU, AV, AW, AX, FF, RR}

P, S

)

P:

S > prog L end.

L > O | L;O | L;

B> B or C | C

D > G | not D

G > E < E | E>E | E=E | (B)

K > G then O

M > K else O

Q > O while G

O > if M | if K| begin L end | do Q | c:=E

E > E-F | E+F | E-- | F

F > (E) | c | g

2.4 Результат выполнения программы

Результаты разбора входных выражений на лексемы представлен на рисунке 2.2

Рис. 2.2 - Результаты разбора входных выражений на лексемы

2.5 Вывод

Спроектированный лексический анализатор выполняет лексический анализ входного текста в соответствии с заданной грамматикой и порождает таблицу лексем с указанием их типов. Программа выводит также сообщения о наличие во входном тексте ошибок. Этот алгоритм послужит в дальнейшем базой для построения дерева вывода в 3 части курсовой работы.

3. Построение дерева вывода

3.1 Исходные данные

Программа выполняет лексический анализ входного, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдавать сообщения о наличие во входном тексте ошибок.

Лексический анализатор выделяет в тексте лексемы языка. Полученная после лексического анализа цепочка во второй части программы рассматриваться в соответствии с алгоритмом разбора. После построения цепочки вывода на ее основе строится дерево разбора.

Длину идентификаторов и строковых констант считать ограниченной 32 символами.

Исходная грамматика имеет вид:

S > prog L end.

L > O | L;O | L;

B> B or C | C

C> C and D | D

D > G | not D

G > E < E | E>E | E=E | (B)

K > G then O

M > K else O

Q > O while G

O > if M | if K| begin L end | do Q | c:=E

E > E-F | E+F | E-- | F

F > (E) | c | g

3.2 Синтаксический анализатор

Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Одним из таких способов представления является дерево синтаксического разбора.

Программирование работы недетерминированного МП-автомата - это сложная задача. Разработанный алгоритм, позволяет для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами).

Доказано, что время работы этого алгоритма пропорционально n³, где n - длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n². Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка - большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.

КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.

Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:

· простого предшествования;

· расширенного предшествования;

· слабого предшествования;

· смешанной стратегии предшествования;

· операторного предшествования.

3.3 Таблицы предшествования

Множество правил грамматики имеет вид:

S > prog L end.

L > O | L;O | L;

B> B or C | C

C> C and D | D

D > G | not D

G > E < E | E>E | E=E | (B)

K > G then O

M > K else O

Q > O while G

O > if M | if K| begin L end | do Q | c:=E

E > E-F | E+F | E-- | F

F > (E) | c | g

Грамматика является грамматикой операторного предшествования, так как она не содержит -правил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики.

Таблица 3.1

Множества крайних правы и крайних левых символов

Символ (U)	Начало построения	Результат
	L(U)	R(U)	L(U)	R(U)
S	prog	end.	prog	end.
L	O L	O;	OL if begin do c	OMKQEGF --) c g end;
B	B C	C	BCDG not E(F c g	CDQEF --) c g end
C	C D	D	CDG not E(F c g	DGEF --) c g end
D	G not	GD	G not E(F c g	DGEF --) c g end
G	E(	E)	E(F c g	EF --) c g end
K	G	O	GE (FCD	OMKQEGF --) c g end
M	K	O	GKE(F c g	OMKQEGF --) c g end
Q	O	G	If begin do c	GE)F--c g
O	If begin do c	MK end Q E	EF do c	MK end QEOGF--) cg
E	E F	F --	EF (c g	F--) c g
F	(c g	) c g	(c g	) c g

На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов L_t(U), R_t(U) относительно всех нетерминальных символов грамматики.

Таблица 3.2

Множества крайних правых и крайних левых терминальных символов

Символ (U)	Начало построения	Результат
	L(U)	R(U)	L(U)	R(U)
S	prog	end.	prog	end.
L	;	;	if begin do c	if end do:= else then while - + --; < > =) c g
B	or	or	or and not < > = (- + -- c g	and not - + --; < > =) c g
C	and	and	and not < > = (- + -- c g	not <> =) -+ --) c g and
D	not	not	or not < > = (- + -- c g	< > =) not - + -- c g
G	< > = (	< > =)	< > = (- + -- c g	< > =) - + -- c g
K	then	then	< > = (- + -- c g	then if end do:= else while - + -- < > =)cg
M	else	else	< > = (- + -- c g then else	then if end do:= else while - + -- < > =)cg
Q	while	while	while if begin do c	while < > = - + -- c g
O	if begin do c	if end do:= c	if begin do c	if end do then:= else while - + -- <>=)cg
E	- + --	- + --	- + -- (c g	- + --) c g
F	(c g	) c g	(c g	) c g

На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики:

Таблица 3.3

Матрица предшествования исходной грамматики

prog

end.

;

or

and

not

<

>

=

(

)

if

then

else

do

while

:=

-

+

--

c

g

begin

end

over

prog

-

<

<

-

-

-

-

-

-

-

-

<

-

<

<

-

-

-

-

-

<

-

<

-

-

end.

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

>

;

-

>

>

>

-

-

-

-

-

-

>

<

-

>

<

>

<

-

-

-

<

-

<

>

-

or

-

-

-

>

<

<

<

<

<

<

>

-

-

-

-

-

-

<

<

<

<

<

-

>

-

and

-

-

-

>

>

<

-

-

-

<

>

-

-

-

-

-

-

<

<

<

<

-

-

-

-

not

-

-

-

>

>

<

<

<

<

<

>

-

-

-

-

-

-

<

<

<

<

<

-

-

-

<

-

>

>

>

>

-

-

-

-

<

>

-

>

>

-

>

-

<

<

<

<

<

-

>

-

>

-

>

>

>

>

-

-

-

-

<

>

-

>

>

-

>

-

<

<

<

<

<

-

>

-

=

-

>

>

>

>

-

-

-

-

<

>

-

>

>

-

>

-

<

<

<

<

<

-

>

-

(

-

-

-

<

<

<

<

<

<

<

=

-

-

-

-

-

-

<

<

<

<

<

-

-

-

)

-

>

>

>

>

-

>

>

>

-

>

-

>

>

-

-

-

>

>

>

-

-

-

>

-

if

-

>

>

-

-

-

<

<

<

<

-

-

<

<

-

>

-

<

<

<

<

<

-

>

-

then

-

>

>

-

-

-

-

-

-

-

-

<

-

>

<

>

<

-

-

-

<

-

<

>

-

else

-

>

>

-

-

-

-

-

-

-

-

<

-

>

<

>

<

-

-

-

<

-

<

>

-

do

-

>

<

-

-

-

-

-

-

-

<

<

-

<

<

<

<

-

-

-

<

-

<

>

-

while

-

>

>

-

-

-

<

<

<

<

-

-

-

>

-

>

-

<

<

<

<

<

-

>

-

:=

-

>

>

-

-

-

-

-

<

-

-

-

-

>

-

>

-

<

<

<

<

<

-

>

-

-

-

>

>

>

>

-

>

>

>

<

>

-

>

>

-

>

-

>

>

>

<

<

-

>

-

+

-

>

>

>

>

-

>

>

>

<

>

-

>

>

-

>

-

>

>

>

<

<

-

>

-

--

-

>

>

>

>

-

>

>

>

-

>

-

>

>

-

>

-

>

>

>

-

-

-

>

-

c

-

>

>

>

>

-

>

>

>

-

>

-

>

>

-

>

>

>

>

>

-

-

-

>

-

g

-

>

>

>

>

-

>

>

>

-

>

-

>

>

-

>

-

>

>

>

-

-

-

>

-

begin

-

-

<

<

-

-

-

-

-

-

-

<

-

-

<

-

<

-

-

-

<

-

<

<

-

end

-

>

>

-

-

-

-

-

-

-

-

-

-

>

-

>

-

-

-

-

-

-

-

>

-

bgn

<

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

3.4 Результат выполнения программы

Результаты построения дерева разбора входных выражений представлены на рисунке 3.1.

Рис. 3.1 - Результаты построения дерева разбора

По последовательности правил «свертки» легко строится цепочка вывода и дерево синтаксического разбора. Дерево строится сверху вниз путем последовательного применения правил. Алгоритм разбора порождает правосторонний вывод.

3.5 Вывод

Была разработана программа, производящая построение дерева вывода заданных логических выражений и проверяющая их синтаксис.

Заключение

В результате выполнения курсовой работы для заданного входного языка были построены отдельные части компилятора.

В первой части работы был разработан программа, которая получает на входе набор идентификаторов, организует таблицу идентификаторов методом цепочек и методом бинарного дерева, позволяет осуществить многократный поиск идентификатора в этих таблицах.

Было также выявлено, что метод цепочек более эффективен, чем метод бинарного дерева, так как для поиска идентификатора в таблице организованной методом цепочек используется меньшее количество сравнений.

Во второй части работы была написана программа, которая выполняет лексический анализ входного текста и порождает таблицу лексем с указанием их типов и значений.

Третья часть курсовой работы была посвящена разработке программы, которая порождает таблицу лексем и выполняет синтаксический разбор текста с построением дерева разбора.

Отдельные части компилятора, разработаные в данной курсовой работе, дают представление о технике и методах, лежащих в основе построения компиляторов.

Список литературы

1. Гордеев А. В. Молчанов Л. Ю. Системное программное обеспечение, - СПб.: Питер. 2002. - 734с.

2. Кампапиец Р. II. Манькоп Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Учеб. пособие для высших и средних учебных заведений. - СПб.: КОРОНА Принт, 2000. - 256 с.

3. Гордеев А. В. Операционные системы: Учебник для вузов. 2-е изд.-СПб.: Питер, 2004. - 416 с.

4. Олифер В. Г., Олифер Н.А. Сетевые операционные системы. - СПб.: Питер. 2002. - 544 с.

Приложение А - Листинги программы

String input_line[256];

String stack[256];

String terminal[32];

String rules[32];

String input_rules[256];

int index_rule;

int **mega_matrix;

int all_rules=0;

int comment=0;

class TForm1:: Identificator // класс идентификатора

{

public:

char *Name;

int Right;

int Left;

Identificator ()

{

Name = new char[32];

Right=0;

Left=0;

}

int Hash()

{

return (Name[0]|Name[strlen(Name)-1]);

}

};

int TForm1::AddToHashTableChane(int IDindex,Identificator *IDTable,int *HashTable)

{ //добавление ид-ра в таблицу методом цепочек

if (!HashTable[IDTable[IDindex].Hash()])

{

HashTable[IDTable[IDindex].Hash()]=IDindex;

mTextChane->Lines->Add((IDTable[IDindex].Name));

mTextChane->Text=mTextChane->Text+ "-> в хэш ";

}

else

{

mTextChane->Lines->Add((IDTable[IDindex].Name));

mTextChane->Text=mTextChane->Text+ " коллизия ";

int HashIndex = HashTable[IDTable[IDindex].Hash()];

int fl=0;

colis_chane++;

do

{

mTextChane->Text=mTextChane->Text+ "R";

if(IDTable[HashIndex].Right!=0)

{

HashIndex = IDTable[HashIndex].Right;

colis_chane++;

}

else

{

IDTable[HashIndex].Right=IDindex;

fl=1;

}

}while(!fl);

}

}

int TForm1::SearchIdChane(char *ID,Identificator *IDTable,int *HashTable) // поиск в табл. метода цепочек

{

int HashID=ID[0]|ID[strlen(ID)-1];

if (!HashTable[HashID])

{

return -1;

}

else

{

int HashIndex = HashTable[HashID];

int fl=0;

cmp_count_chane = 1;

do

{

cmp_count_chane++;

if (strcmp(IDTable[HashIndex].Name,ID)==0) return(HashIndex);

else

{

if (strcmp(IDTable[HashIndex].Name,ID)!=0)

if(IDTable[HashIndex].Right!=0) HashIndex = IDTable[HashIndex].Right;

else return -1;

}

}while(1);

}

}

int TForm1:: A(char ch) // функции состояния автомата

{

if(ch=='r') return 2;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: B(char ch)

{

if(ch=='o') return 3;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: C(char ch)

{

if(ch=='g') return 4;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: D(char ch)

{

if(ch=='\0') return 999;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: E(char ch)

{

if(ch=='n') return 6;

if(ch=='l') return 11;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: H(char ch)

{

if(ch=='d') return 7;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: G(char ch)

{

if(ch=='.') return 8;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: K(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: L(char ch)

{

if(ch=='=') return 10;

else return 666;

}

int TForm1:: M(char ch)

{

if(ch=='\0') return 999;

else return 666;

}

int TForm1:: R(char ch)

{

if(ch=='s') return 23;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: N(char ch)

{

if(ch=='f') return 13;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: O(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: P(char ch)

{

if(ch=='h') return 15;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: I(char ch)

{

if(ch=='e') return 16;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: J(char ch)

{

if(ch=='n') return 17;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: Q(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: V(char ch)

{

if(ch=='e') return 19;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: W(char ch)

{

if(ch=='g') return 20;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: X(char ch)

{

if(ch=='i') return 21;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: Y(char ch)

{

if(ch=='n') return 22;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: Z(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: T(char ch)

{

if(ch=='e') return 24;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: U(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: F(char ch)

{

if(ch=='\0') return 999;

else return 666;

}

int TForm1:: FF(char ch)

{

if(ch=='-') return 26;

if(ch=='\0') return 999;

else return 666;

}

int TForm1:: AA(char ch)

{

if(ch=='\0') return 999;

else return 666;

}

int TForm1:: AM(char ch)

{

if(ch=='\0') return 999;

else return 666;

}

int TForm1:: AB(char ch)

{

if(ch=='n') return 29;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AC(char ch)

{

if(ch=='d') return 30;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AD(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AG(char ch)

{

if(ch=='r') return 32;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AF(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AH(char ch)

{

if(ch=='o') return 34;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AI(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AE(char ch)

{

if(ch=='o') return 36;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AK(char ch)

{

if(ch=='t') return 37;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AL(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AJ(char ch)

{

if(ch=='h') return 39;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AN(char ch)

{

if(ch=='i') return 40;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AO(char ch)

{

if(ch=='l') return 41;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AP(char ch)

{

if(ch=='e') return 42;

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AQ(char ch)

{

if(ch=='\0') return 999;

else return 777;

}

int TForm1:: AR(char ch)

{

if(ch=='*') return 45;

else return 666;

}

int TForm1:: AT(char ch)

{

comment=1;

if(ch=='*') return 46;

else return 45;

}

int TForm1:: AU(char ch)

{

if(ch=='/') return 47;

else return 45;

}

int TForm1:: AV(char ch)

{

if(ch=='\0') {comment=0; return 999;}

else return 666;

}

int TForm1:: AW(char ch)

{

if((ch>='0')&&(ch<='9')) return 48;

if((ch>='a')&&(ch<='f')) return 49;

if(ch=='\0') return 999;

else return 666;

}

int TForm1:: AX(char ch)

{

if((ch>='0')&&(ch<='9')) return 49;

if((ch>='a')&&(ch<='f')) return 49;

if(ch=='\0') return 999;

else return 666;

}

int TForm1::h(char ch)

{

if(ch=='p') return 1;

if(ch=='e') return 5;

if(ch==':') return 9;

if(ch=='i') return 12;

if(ch=='t') return 14;

if(ch=='b') return 18;

if(ch=='a') return 28;

if(ch=='o') return 31;

if(ch=='-') return 50;

if(ch=='('||ch==')') return 27;

if(ch=='+'||ch=='<'||ch=='>'||ch=='=') return 25;

if(ch=='d') return 33;

if(ch=='n') return 35;

if(ch=='/') return 43;

if(ch==';') return 51;

if(ch=='w') return 38;

if((ch>='0')&&(ch<='9')) return 48;

else return 777;

}

int TForm1:: IDF(char ch)

{

if((ch>='0')&&(ch<='9')) return 777;

if((ch>='a')&&(ch<='z')) return 777;

if(ch=='\0') return 999;

else return 666;

}

int TForm1:: RR(char ch)

{

if(ch=='\0') return 999;

else return 666;

}

String TForm1::GetState(int st) // функция определение состояния автомата по его номеру

{

String res;

switch(st) {

case 0: res = "h"; break;

case 1: res = "A"; break;

case 2: res = "B"; break;

case 3: res = "C"; break;

case 4: res = "D"; break;

case 5: res = "E"; break;

case 6: res = "H"; break;

case 7: res = "G"; break;

case 8: res = "K"; break;

case 9: res = "L"; break;

case 10: res = "M"; break;

case 11: res = "R"; break;

case 12: res = "N"; break;

case 13: res = "O"; break;

case 14: res = "P"; break;

case 15: res = "I"; break;

case 16: res = "J"; break;

case 17: res = "Q"; break;

case 18: res = "V"; break;

case 19: res = "W"; break;

case 20: res = "X"; break;

case 21: res = "Y"; break;

case 22: res = "Z"; break;

case 23: res = "T"; break;

case 24: res = "U"; break;

case 25: res = "F"; break;

case 26: res = "AA"; break;

case 27: res = "AM"; break;

case 28: res = "AB"; break;

case 29: res = "AC"; break;

case 30: res = "AD"; break;

case 31: res = "AG"; break;

case 32: res = "AF"; break;

case 33: res = "AH"; break;

case 34: res = "AI"; break;

case 35: res = "AE"; break;

case 36: res = "AK"; break;

case 37: res = "AL"; break;

case 38: res = "AJ"; break;

case 39: res = "AN"; break;

case 40: res = "AO"; break;

case 41: res = "AP"; break;

case 42: res = "AQ"; break;

case 43: res = "AR"; break;

case 45: res = "AT"; break;

case 46: res = "AU"; break;

case 47: res = "AV"; break;

case 48: res = "AW"; break;

case 49: res = "AX"; break;

case 50: res = "FF"; break;

case 51: res = "RR"; break;

case 777: res = "IDF"; break;

case 666 :res="Err"; break;

case 999 :res="S"; break;

}

return res;

}

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

sgrTable->Rows[0]->Add("Лексема");

sgrTable->Rows[0]->Add("Тип лексемы");

sgrTable->Rows[0]->Add("Лексема");

index_rule = 0;

}

//---------------------------------------------------------------------------

void TForm1::AddTerminal(String filename) // считывание терминальных символов

{

FILE *input;

char *temp;

temp = new char[32];

input = fopen(filename.c_str(),"r");

int i=0;

while (strcmp(temp,"over"))

{

fscanf(input,"%s",temp);

terminal[i]=temp;

i++;

}

terminal[i]="#";

for(int j=0;j<i;j++) {

sgMatrix->Cols[j+1]->Add(terminal[j]);

if(terminal[j]=="over") sgMatrix->Rows[j+1]->Add("bgn");

else sgMatrix->Rows[j+1]->Add(terminal[j]);

}

sgMatrix->ColCount = i+1;

sgMatrix->RowCount = i+1;

AddMatrix(input,i);

fclose(input);

}

void TForm1::AddMatrix(FILE *input,int n) // считывание матрицы предшествования

{

int i=0;

char *temp;

temp = new char [32];

mega_matrix = new int *[n];

for (int i = 0; i < n; i++)

mega_matrix[i] =new int[n];

while(!feof(input))

{

fscanf(input,"%s",temp);

for(int j=0;j<n;j++) {

fscanf(input,"%s",temp);

if(temp[0]=='<') mega_matrix[i][j] = 1;

if(temp[0]=='>') mega_matrix[i][j] = 2;

if(temp[0]=='=') mega_matrix[i][j] = 0;

if(temp[0]=='-') mega_matrix[i][j] = -1;

sgMatrix->Cells[j+1][i+1] = temp;

}

i++;

}

}

int TForm1:: index_terminal(String trm) // функция определния индекса терминала в массиве терм. симв.

{

int count=0;

if(trm=="bgn") trm = "over";

while(terminal[count]!="#") {

if(trm==terminal[count]) return count;

count++;

}

return -1;

}

int TForm1::first_terminal(int count) // функция возвращает первый терминальный символ в стеке

{

for(int i=count;i!=0;i--)

{

if(index_terminal(stack[i])!=-1) return i;

}

}

int TForm1::cmp_substr(String sub1, String sub2) // функция сравнения двух символов

{

if(index_terminal(sub1)>=0&&index_terminal(sub2)>=0)

return mega_matrix[index_terminal(sub1)][index_terminal(sub2)];

else return -1;

}

void TForm1::sdvig(int count_s,int count_l) // функция сдвига

{

stack[count_s+1]=input_line[count_l];

}

int TForm1::AddRules() // функция добавления правил грамматики

{

char *temp = new char [32];

FILE *input = fopen("Rules.txt","r");

int i=0;

while(!feof(input))

{

fgets(temp,256, input);

rules[i] = String(temp);

rules[i].SetLength(rules[i].Length()-1);

while(rules[i].Pos(" ")) {rules[i].Delete(rules[i].Pos(" "),1);}

i++;

}

return i;

}

int TForm1::cmp_rules(String rls,int n) //функция сравнение правил

{

for(int i=0;i<n;i++)

{

if(rls==rules[i]) return i;

}

return -1;

}

int TForm1::package(int count_st,int n) //функция свертки

{

String trm,tV,Vt,VVt,V;

int ftrm = first_terminal(count_st);

trm = stack[ftrm];

tV = trm + stack[ftrm+1];

Vt = stack[ftrm-1] + trm;

V = stack[ftrm-1] + trm + stack[ftrm+1];

VVt = stack[ftrm-2]+ stack[ftrm-1]+trm;

if(cmp_rules(trm,n)>=0)

{

int rez = cmp_rules(trm,n);

stack[ftrm]="S";

input_rules[index_rule]=IntToStr(rez);

index_rule++;

return 0;

}

if(cmp_rules(V,n)>=0)

{

int rez = cmp_rules(V,n);

String right_empty = stack[ftrm+1];

stack[ftrm-1]="S";

stack[ftrm]="";

stack[ftrm+1]="";

input_rules[index_rule]=IntToStr(rez);

index_rule++;

if(right_empty=="") return 1; else return 2;

}

if(cmp_rules(Vt,n)>=0)

{

int rez = cmp_rules(Vt,n);

stack[ftrm-1]="S";

stack[ftrm]="";

input_rules[index_rule]=IntToStr(rez);

index_rule++;

return 1;

}

if(cmp_rules(tV,n)>=0)

{

int rez = cmp_rules(tV,n);

stack[ftrm]="S";

stack[ftrm+1]="";

input_rules[index_rule]=IntToStr(rez);

index_rule++;

return 1;

}

if(cmp_rules(VVt,n)>=0)

{

int rez = cmp_rules(VVt,n);

stack[ftrm-2]="S";

stack[ftrm-1]="";

stack[ftrm]="";

input_rules[index_rule]=IntToStr(rez);

index_rule++;

return 2;

}

return -1;

}

String TForm1::Conclude(String X,char *temp,int i) // определение типа лексемы

{

if(X=="AM") {

input_line[i]=AnsiString(temp);

return("Круглая скобка");

}

if(X=="RR") {

input_line[i]=AnsiString(temp);

return("Разделительный символ");

}

if(X=="AX") {

input_line[i]="g";

return("Константа");

}

if(X=="F" || X=="FF" || X=="AA") {

input_line[i]=AnsiString(temp);

return("Знак операции");

}

if(X=="AD" || X=="AL" || X=="AF") {

input_line[i]=AnsiString(temp);

return("Логическая операция");

}

if(X=="G" || X=="M" || X=="O" || X=="Q"|| X=="U"|| X=="Z"||X=="AI"||X=="AQ") {

input_line[i]=AnsiString(temp);

return("Оператор");

}

if(X=="AT" || X=="AV") return("Комментарий");

if(X=="D" || X=="K") {

input_line[i]=AnsiString(temp);

return("Слово начала/конца программы");

}

if(X=="AW") {

input_line[i]="g";

return("Число");

}

if(X=="Err") return("Ошибка");

else {

input_line[i]="c";

return("Идентификатор");

}

}

String TForm1::Analiz(char *wInput) // функция анализа лексемы

{

int i = 0;

int State=0;

String Way="h";

String last="";

if(comment==1) State = 45;

do {

switch (State) {

case 0: State = h(wInput[i]); break;

case 1: State = A(wInput[i]); break;

case 2: State = B(wInput[i]); break;

case 3: State = C(wInput[i]); break;

case 4: State = D(wInput[i]); break;

case 5: State = E(wInput[i]); break;

case 6: State = H(wInput[i]); break;

case 7: State = G(wInput[i]); break;

case 8: State = K(wInput[i]); break;

case 9: State = L(wInput[i]); break;

case 10: State = M(wInput[i]); break;

case 11: State = R(wInput[i]); break;

case 12: State = N(wInput[i]); break;

case 13: State = O(wInput[i]); break;

case 14: State = P(wInput[i]); break;

case 15: State = I(wInput[i]); break;

case 16: State = J(wInput[i]); break;

case 17: State = Q(wInput[i]); break;

case 18: State = V(wInput[i]); break;

case 19: State = W(wInput[i]); break;

case 20: State = X(wInput[i]); break;

case 21: State = Y(wInput[i]); break;

case 22: State = Z(wInput[i]); break;

case 23: State = T(wInput[i]); break;

case 24: State = U(wInput[i]); break;

case 25: State = F(wInput[i]); break;

case 26: State = AA(wInput[i]); break;

case 27: State = AM(wInput[i]); break;

case 28: State = AB(wInput[i]); break;

case 29: State = AC(wInput[i]); break;

case 30: State = AD(wInput[i]); break;

case 31: State = AG(wInput[i]); break;

case 32: State = AF(wInput[i]); break;

case 33: State = AH(wInput[i]); break;

case 34: State = AI(wInput[i]); break;

case 35: State = AE(wInput[i]); break;

case 36: State = AK(wInput[i]); break;

case 37: State = AL(wInput[i]); break;

case 38: State = AJ(wInput[i]); break;

case 39: State = AN(wInput[i]); break;

case 40: State = AO(wInput[i]); break;

case 41: State = AP(wInput[i]); break;

case 42: State = AQ(wInput[i]); break;

case 43: State = AR(wInput[i]); break;

case 45: State = AT(wInput[i]); break;

case 46: State = AU(wInput[i]); break;

case 47: State = AV(wInput[i]); break;

case 48: State = AW(wInput[i]); break;

case 49: State = AX(wInput[i]); break;

case 50: State = FF(wInput[i]); break;

case 51: State = RR(wInput[i]); break;

case 777: State = IDF(wInput[i]); break;

case 999: State = IDF(wInput[i]); break;

case 666 : break;

}

Way=Way +"-"+GetState(State);

if(GetState(State)!="S") last = GetState(State);

}while (wInput[i++]!='\0');

return last;

}

void __fastcall TForm1::Button1Click(TObject *Sender) // непосредственно загрузка входного текста

{

colis_chane=0;

int i=1;

char *temp;

temp = new char[32];

TableChane = new Identificator[256];

FILE *inFile;

inFile=fopen("input.txt","r");

for (int i=0;i<=255;i++){HashTableChane[i]=0;}

mTextChane->Lines->Clear();

while (!feof(inFile))

{

fscanf(inFile, "%s", temp);

strcpy(TableChane[i].Name,temp);

AddToHashTableChane(i,TableChane,HashTableChane);

String last = Analiz(temp);

sgrTable->Rows[i]->Add(temp);

sgrTable->Rows[i]->Add(Conclude(last,temp,i-1));

sgrTable->Rows[i]->Add(input_line[i-1]);

i++;

input_line[i-1]="over";

sgrTable->RowCount = i;

}

fclose(inFile);

String Way;

mSource->Lines->LoadFromFile("input.txt");

mSource2->Lines->LoadFromFile("input.txt");

mRules->Lines->LoadFromFile("Rules.txt");

AddTerminal("hyper_matrix.txt");

all_rules = AddRules();

int count_stack;

stack[0] = "bgn";

Button3->Enabled = true;

}

void __fastcall TForm1::Button3Click(TObject *Sender) // строим цепочку вывода

{

int stack_index = 0;

int lines_index = 0;

stack[0]="bgn";

String temp;

int cmp_rez;

int left;

int fl = 0;

while(1)

{

if((input_line[lines_index]=="over") && (stack[1]=="S") && (stack[2]=="")) break;

cmp_rez = cmp_substr(stack[first_terminal(stack_index)],input_line[lines_index]);

if(cmp_rez==1 || cmp_rez==0)

{

sdvig(stack_index,lines_index);

lines_index++;

stack_index++;

}

if(cmp_rez==2)

{

left = package(stack_index,all_rules);

if(left == -1) {fl=1; break; }

else stack_index= stack_index - left;

}

if(cmp_rez==-1) {fl=1; break; }

}

if (fl==1) {

Edit1->Text= "Неправильная конструкция";

} // далее можно поставить нужный разделительный символ (сейчас пробел " ")

else for(int k = 0; k< index_rule; k++) temp += IntToStr(StrToInt(input_rules[k])+1) + " ";

Edit1->Text=temp;

Button4->Enabled = true;

}

void TForm1::AddChild(String child,int ind_item) // добавление листьев к дереву

{

int lenght = child.Length();

char *rezult_child;

String temp_string="";

rezult_child = new char [lenght];

TTreeNode *Node1;

Node1 = tree->Items->Item[ind_item];

strcpy(rezult_child,child.c_str());

for(int i=0;i<lenght;i++)

{

temp_string = temp_string + rezult_child[i];

if(temp_string=="S")

{

tree->Items->AddChild(Node1,temp_string);

temp_string="";

}

if(rezult_child[i+1]!='.')

if(index_terminal(temp_string)>=0)

{

tree->Items->AddChild(Node1,temp_string);

temp_string="";

}

}

}

void __fastcall TForm1::Button4Click(TObject *Sender) // строим дерево

{

TTreeNode *Node1;

tree->Items->Clear();

tree->Items->Add(NULL, "S");

Node1 = tree->Items->Item[0];

for(int j = index_rule; j>0 ;j--)

{

int n = tree->Items->Count;

for (int i=n-1;i>=0 ;i--)

{

if(tree->Items->Item[i]->HasChildren == false)

if(tree->Items->Item[i]->Text =="S")

{

AddChild(rules[StrToInt(input_rules[j-1])],i);

break;

}

}

}

}

//---------------------------------------------------------------------------

Размещено на Allbest.ru