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

АННОТАЦИЯ

Целью курсовой работы является:

- овладение и закрепление навыков построения лексического анализатора;

- овладение и закрепление навыков построения синтаксического анализатора;

- исследование принципов работы компилятора на каждом этапе обработки входной последовательности;

- овладение и закрепление навыков оформления документации;

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

Перечень терминов:

ЛА - Лексический анализ

СА - Синтаксический анализ

ОПД - Обратная польская запись

ЯВУ - Язык высокого уровня

МП-автомат - автомат с магазинной памятью

ВВЕДЕНИЕ

Данный документ содержит описание и характеристику программы, написанной на основе задания на курсовую работу по теме «Условные операторы описание простых типов языка Си. Предиктивный анализатор».

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

В приложении 1 приведено техническое задание на курсовую работу.

В приложении 2 содержатся блок-схемы алгоритмов программы.

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

Приложение 4 содержит граф конечного автомата

Приложение 5 содержит листинг программы.

Данный программный продукт является программной реализацией компонентов транслятора (таких как лексический и синтаксический анализ) для некоторых конструкций языка программирования Си.

Использование этого программного средства направлено на:

- изучение принципов работы лексического анализатора,

- изучение принципов работы синтаксического анализатора,

- анализ принадлежности входных строк искомой грамматике,

- трансляцию заданной инструкции в форму внутреннего представления,

- оценку и исправление возможных ошибок,

в рамках учебного курса по дисциплине «Теория языков программирования и методов трансляции».

1. Общие сведения

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

1).. Программа позволяет:

? считать введенную пользователем конструкцию языка и провести лексический анализ этой конструкции, результатом которого является псевдокод;

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

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

Для работы программы необходима операционная система Windows 9x / Me / NT /XR. Программа также предусматривает работу с нестандартным компонентом dxOrgChart (производится вывод деревьев в удобной для просмотра форме), для чего потребуется установить в Delphi палитру компонентов ExpressOrgChart.

1.1 Функциональное назначение

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

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

· Синтаксический анализ входной последовательности на соответствие грамматике;

· Построение дерева разбора, строки вывода синтаксического разбора;

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

1.2 Описание логической структуры

1.2.1 Общая схема работы компилятора

Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что ЯВУ стали основными средствами разработки программ.

Общая схема работы компилятора показана на рис.1, из неё видно, что процесс компиляции состоит из двух основных этапов - анализа и синтеза.

Рис.1 Общая схема работы компилятора

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

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

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

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

Фазы компиляции.

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

a) Лексический анализ:

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

б) Синтаксический разбор

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

в) Семантический анализ

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

г) Подготовка к генерации кода

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

д) Генерация кода

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

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

1.2.2 Описание предметной области

Предметной областью являются конструкции условных операторов if-else и ?: и простые типы языка Си.

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

1) if условие оператор_1;

2) if условие оператор_1;

else оператор_2;

3) условие ? оператор_1;

4) условие ? оператор_1 : оператор_2;

Простые типы в языке Си объявляются так:

тип переменная_1, переменная_2, … переменная_n;

Рассмотрим элементы этих конструкций. Можно выделить следующие зарезервированные слова: if, else, ?, :.. После if находится выражение условие. Это выражение должно быть логического типа, т.е однозначно определяться как «истина» или «ложь». Если логическое выражение принимает значение «истина», то выполняется оператор оператор_1. Иначе, если есть зарезервированное слово else, то выполняется оператор оператор_2. В конструкции с оператором ?: перед зарезервированным словом ? находится выражение условие, которое также должно быть логического типа. Если это выражение принимает значение «истина», то выполняется оператор оператор_1. Иначе, если есть зарезервированное слово :, то выполняется оператор оператор_2. В описании переменных переменная_1, переменная_2, … переменная_n - список переменных в которых имена переменных разделены запятыми, тип - задает тип переменных из данного списка и является идентификатором типа.

1.2.3 Фаза компиляции «Лексический анализатор»

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

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

Этапы работы лексического анализатора:

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

2. После этого проводится идентификация лексемы. Она выполняется путём сравнения лексемы с эталонным значением. Сначала проверяется, не относится ли лексема к классу операторов. Если нет, то идёт проверка на то, не является ли лексема разделителем. Далее последовательно проверяется принадлежность лексемы к классам идентификаторы и ключевые слова.

3. После проведения успешной идентификации лексемы формируется её образ - дескрипторный код, он помещается в выходной поток лексического анализатора. В случае неуспешной идентификации формируются сообщения об ошибках в написании слов программы.

В рамках задания на курсовую работу представлены следующие классы лексем (Таблицы 1-4):

Табл. 1 Класс лексем «Операторы»

Лексема	Код замены
>	>
<	<
=	=
+	+
-	-
*	*
/	/
==	r
!=	a

Табл. 2 Класс лексем «Разделители»

Лексема	Код замены
;	;
,	,
(	(
)	)
{	{
}	}

Табл. 3 Класс лексем «Идентификаторы»

Лексема	Код замены
id	d
type	t
number	n

Табл. 4 Класс лексем «Ключевые слова»:

Лексема	Код замены
if	i
else	e
?	f
:	l

Рассмотрим работу лексического анализатора (ЛА) на примере:

На вход ЛА подаются следующие входные данные:

boolean k;

int a;

{

if k==0 a=1; else a=5;

}

ЛА читает текст исходной программы и выделяет в её тексте лексемы входного языка.

Таким образом, на выходе лексического анализатора мы имеем следующую цепочку:

td;td;{idrnd=n;ed=n;}

Эта цепочка подается на вход синтаксического анализатора (СА).

1.2.4 Фаза компиляции «Синтаксический анализатор»

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

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

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

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

Согласно индивидуальному заданию рассмотрим LL-метод (предиктивный анализатор).

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

Существует класс грамматик, основанный именно на этом принципе -- выборе одной альтернативы из множества возможных на основе нескольких очередных символов в цепочке. Это так называемые LL(k)-грамматики. Грамматика обладает свойством LL(k), k > 0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего положения считывающей головки во входной цепочке символов. Грамматика называется LL(k)-грамматикой, если она обладает свойством LL(k) для некоторого k > 0. Название «LL(k) » несет определенный смысл. Первая литера «L» происходит от слова «left» и означает, что входная цепочка символов читается в направлении слева направо. Вторая литера «L» также происходит от слова «left» и означает, что при работе распознавателя используется левосторонний вывод. Вместо «k» в названии класса грамматики стоит некоторое число, которое показывает, сколько символов надо рассмотреть, чтобы однозначно выбрать одну из множества альтернатив.

В совокупности все LL(k)-грамматики для всех k>0 образуют класс LL-грамматик.

Алгоритм разбора входных цепочек для LL(k)-грамматик носит название «k-предсказывающего алгоритма».

Требование k > 0, безусловно, является разумным -- для принятия решения о выборе той или иной альтернативы МП-автомату надо рассмотреть хотя бы один символ входной цепочки. Если представить себе LL-грамматику с k = 0, то в такой грамматике вывод совсем не будет зависеть от входной цепочки. В принципе такая грамматика возможна, но в ней будет всего одна единственная цепочка вывода. Поэтому практическое применение языка, заданного такого рода грамматикой, представляется весьма сомнительным.

Для LL(k)-грамматик известны следующие полезные свойства:

· всякая LL(k)-грамматика для любого k>0 является однозначной;

· существует алгоритм, позволяющий проверить, является ли заданная грамматика LL(k)-грамматикой для строго определенного числа k.

Есть, однако, неразрешимые проблемы для произвольных КС-грамматик:

· не существует алгоритма, который бы мог проверить, является ли заданная КС-грамматика LL(k)-грамматикой для некоторого произвольного числа k;

· не существует алгоритма, который бы мог преобразовать произвольную КС-грамматику к виду LL(k)- грамматики для некоторого k (или доказать, что преобразование невозможно).

Для LL(1)-грамматики, очевидно, для каждого нетерминального символа не может быть двух правил, начинающихся с одного и того же терминального символа. Поскольку все LL(k)-грамматики используют левосторонний нисходящий распознаватель, основанный на алгоритме с подбором альтернатив, очевидно, что они не могут допускать левую рекурсию. Поэтому никакая леворекурсивная грамматика не может быть LL-грамматикой. Следовательно, первым делом при попытке преобразовать грамматику к виду LL-грамматики необходимо, устранить в ней левую.

Класс LL-грамматик широк, но все же он недостаточен для того, чтобы покрыть все возможные синтаксические конструкции в языках программирования (к ним относим все детерминированные КС-языки). Известно, что существуют детерминированные КС-языки, которые не могут быть заданы LL(к)-грамматикой ни для каких k. Однако LL-грамматики удобны для использования, поскольку позволяют построить распознаватели с линейными характеристиками (линейной зависимостью требуемых для работы алгоритма распознавания вычислительных ресурсов от длины входной цепочки символов).

Для построения LL(1)-анализатора понадобятся специальные множества FIRST и FOLLOW .

Множество FIRST находится по правилам:

1) Если X - терминал, то FIRST(X) = {X};

2) Если имеется продукция вида Х > е, добавляем е к FIRST(X);

3) Если Х - нетерминал и имеется продукция Х > Y1Y2…Yk, то поместим а в FIRST(Х), если для некоторого i а FIRST(Yi) и е входит во все множества FIRST(Y1)… FIRST(Yi-1), т.е. Y1 --- Yi-1 > е. Если е имеется во всех FIRST(Yi), i=1...k, то добавляем е к FIRST(Х).

Множество FOLLOW находится по правилам:

1) Поместим $ в FOLLOW(S), где S - стартовый символ, а $ - правый ограничитель входного потока.

2) Если имеется продукция А>бВв, то все элементы множества FIRST(в), кроме , помещаются во множество FOLLOW(В).

3) Если имеется продукция А>бВ или А>бВв, где FIRST(в) содержит (т.е. в), то все элементы из множества FOLLOW(A) помещаются во множество FOLLOW(В).

Согласно правилам грамматики и построенным множествам FIRST и FOLLOW строим таблицу предиктивного анализа по существующему алгоритму:

1) Для каждой продукции грамматики А> выполняем шаги 2. и 3.

2) Для каждого терминала а из FIRST() добавляем А> в ячейку М[А,а].

3) Если в FIRST() входит , для каждого терминала b из FOLLOW(A) добавим А> в ячейку М[A,b]. Если входит в FIRST(), а $ - в FOLLOW(A), добавим А> в ячейку M[A,$].

4) Сделаем каждую неопределенную ячейку таблицы М указывающей на ошибку.

Проделаем данные построения для заданной грамматики.

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

G=(TV,NV,S,P)

TV=( `d', `t', `n', `i', `e', `f', `l', `r', `a', `;', `,', `{', `}', `(', `)', `<', `>', `=', `+', `-', `*', `/')

NV=(S, B, E, C, H, A, D, F, K, J, I, W, Z, M, N)

P={

S->E{B}

B->$|A|iM

E->$|tC;E

C->dH

H->$|,C

A->tC;E|{B}|d=J;B|N

D->$|eB

F->$|lB

K->J|n|d

J->KI

I->$|WK

W->+|-|*|/

Z->>|<|r|a

M->(KZK)BD|KZKBD

N->(KZK)fBF|KZKfBF

}

Запись правил грамматики G в форме Бэкуса-Наура:

<Старт>-><описание типа>{<тело программы>}

<тело программы>->$|<тело программы2>|i<операнды после if>

<описание типа>->$|t<переменные>;<описание типа>

< переменные >->d<список переменных>

< список переменных >->$|,< переменные >

< тело программы2>->t< переменные >;<описание типа>|{< тело программы >}|d=<выражение>;< тело программы >|<оператор ?:>

< операция else >->$|e< тело программы >

< операция :>->$|l< тело программы >

<идентификатор>-><выражение>|n|d

<выражение>-><идентификатор ><операция>

<операция>->$|< арифметические операции >< идентификатор >

<арифметические операции>->+|-|*|/

<операции отношения>->>|<|r|a

<операнды после if>->(<идентификатор><операции отношения><идентификатор >)< тело программы ><операция else>|< идентификатор >< операции отношения >< идентификатор >< тело программы >< операция else >

< оператор ?:>->(< идентификатор >< операции отношения >< идентификатор >)f< тело программы ><операция :>|< идентификатор >< операции отношения >< идентификатор >f< тело программы >< операция :>

Запись правил грамматики в графическом виде:

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

· Точка входа (не обозначается на диаграмме, из нее начинается входная дуга графа)

· Нетерминальный символ (обозначается прямоугольником, в который вписано обозначение символа)

· Цепочка терминальных символов (обозначается овалом, кругом или прямоугольником с закругленными краями, внутрь которого вписана цепочка)

· Узловая точка (обозначается закрашенным кружком)

· Точка выхода (не обозначается на диаграмме, в нее входит выходная дуга графа)

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

Синтаксические диаграммы для нетерминальных символов грамматики G

S:

B:

E:

C:

H:

A:

D:

F:

K:

J:

I:

W:

Z:

M:

N:

Рис. 2-18. Синтаксические диаграммы грамматики G

Множества FIRST и FOLLOW строятся программно (рис. 19).



Рис 19. Множества First и Follow.

Рис. 20. Таблица предиктивного анализа

Т.к. в таблице нет ячеек, где бы было более одной записи, значит эта грамматика из класса LL-грамматик.

Для построения программного анализатора, воспользуемся алгоритмом разбора[1] строки по таблице предиктивного анализа (рис. 20).

Алгоритм разбора:

Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале магазин содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a], где A -нетерминал, и a - терминал или символ $.

Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действие анализатора.

Имеются три возможности.

1. Если X=a=$, анализатор останавливается и сообщает об успешном окончании разбора.

2. Если X=a<>$, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.

3. Если X - нетерминал, программа заглядывает в таблицу M[X,a]. По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a]={X->UVW}, анализатор заменяет X на верхушке магазина на WVU {на верхушке U}. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a]=error, анализатор обращается к подпрограмме анализа ошибок.

Пример разбора входной строки, принадлежащей заданной грамматике:

boolean k;

int a;

{

if k==0 a=1; else a=5;

}

Выходом лексического анализатора является следующая цепочка лексем:

td;td;{idrnd=n;ed=n;}

Эта цепочка подается на вход синтаксического анализатора (СА), далее часть процесса синтаксического разбора представлена на рисунке 21.

Рис. 21. Разбор строки

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

Листинг программной реализации c пояснениями представлен в Приложении 5.

1.2.5 Алгоритм построения дерева разбора

Деревом разбора грамматики G(VT,VN,P,S) называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

Каждая вершина дерева обозначается символом грамматики A (VTuVN)

· корнем дерева является вершина, обозначенная целевым символом грамматики -- S;

· листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки;

· если некоторый узел дерева обозначен нетерминальным символом А VN а связанные с ним узлы -- символами b1,b2,bn; n>0,n>=i>0: то в грамматике G(VT,VN,P,S) существует правило А-> b1,b2,bn Р.

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

Часть дерева разбора для рассмотренной выше строки представлена ниже

компилятор алгоритм польский синтаксический



Рис. 22 Часть дерева разбора

1.2.6 Реализация внутреннего представления программы

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

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

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

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

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

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

Для представленной выше строки обратная польская запись выглядит, как «t d t d d n r d n = d n =».

1.3 Используемые технические средства

Системные требования:

1) Операционная система Windows 98/ME/2000/XP

2) Процессор не ниже Intel Pentium 100, 32 Mb ОЗУ, клавиатура, мышь.

3) Тип монитора и видеоадаптера значения не имеют.

1.4 Вызов и загрузка

Для запуска программы необходимо запустить исполняемый файл “Project1.exe.” В силу того, что исполняемый файл не велик большого значения объём ОЗУ на работу программы не оказывает.

1.5 Входные данные

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

Лексемы во входной строке должны разделятся пробелами. Селектор может быть записан как любая последовательность символов.

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

1.6 Выходные данные

Выходными данными являются:

1. Строка вывода, дерево вывода.

2. Сообщение об ошибке, если введенная пользователем конструкция не соответствует правилам грамматики.

ЗАКЛЮЧЕНИЕ

Данная работа является завершающим этапом изучения дисциплины «Теория языков программирования и методы трансляции». Основным предметом данной дисциплины является рассмотрение процесса компиляции. Особое внимание уделяется этапам лексического, синтаксического и семантического анализа, а также изучению формальных методов описания языков программирования.

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

ПРИЛОЖЕНИЕ 1

Блок-схемы алгоритма

Рис.П2.1 Общая блок-схема программа



Рис.П2.2 Блок-схема алгоритма ЛА



Рис.П2.3 Блок-схема алгоритма предикативного синтаксического анализатора

ПРИЛОЖЕНИЕ 2

Руководство пользователя

1. Общие сведения о программе

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

2. Описание запуска

Программа не требует установки. Запуск программы осуществляется открытием файла с расширением .exe. Для работы с программой необходим файл “Grammatika.txt”.

3. Описание пользовательского интерфейса

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



Рис. П3.1. Интерфейс программы.

4. Сообщения пользователю

1)Сообщение при нажатии на кнопку «Провести лексический анализ», если до этого не был загружен пример

2). При возникновении ошибки во время лексического анализа

3). При успешном выполнении синтаксического анализа

4). При возникновении ошибки во время синтаксического анализа

ПРИЛОЖЕНИЕ 3

Граф переходов конечного автомата

Рис. П4.1 Граф переходов конечного автомата

ПРИЛОЖЕНИЕ 4

Листинг программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Buttons, Grids, ComCtrls, dxorgchr;

const NT=['A'..'Z'];

type

Stack=^ElementS; //стек

ElementS=record

inf:char;

link:stack;

end;

TForm1 = class(TForm)

Memo1: TMemo;

SpeedButton1: TSpeedButton;

PageControl1: TPageControl;

TabSheet1: TTabSheet;

SpeedButton6: TSpeedButton;

Memo4: TMemo;

Label1: TLabel;

Edit2: TEdit;

Label3: TLabel;

PageControl2: TPageControl;

TabSheet2: TTabSheet;

TabSheet3: TTabSheet;

TabSheet4: TTabSheet;

TabSheet5: TTabSheet;

SG5: TStringGrid;

SG3: TStringGrid;

SG4: TStringGrid;

SG2: TStringGrid;

SG6: TStringGrid;

SG8: TStringGrid;

SG7: TStringGrid;

SG1: TStringGrid;

SG9: TStringGrid;

Edit1: TEdit;

TabSheet6: TTabSheet;

Memo2: TMemo;

Label2: TLabel;

Button1: TButton;

Button2: TButton;

StringGrid1: TStringGrid;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

TabSheet8: TTabSheet;

Label9: TLabel;

Memo3: TMemo;

TabSheet7: TTabSheet;

Label8: TLabel;

SpeedButton3: TSpeedButton;

SpeedButton5: TSpeedButton;

Edit3: TEdit;

StringGrid2: TStringGrid;

SpeedButton9: TSpeedButton;

TabSheet9: TTabSheet;

dx1: TdxOrgChart;

SpeedButton8: TSpeedButton;

TabSheet10: TTabSheet;

Button10: TButton;

Memo8: TMemo;

Edit4: TEdit;

procedure SpeedButton1Click(Sender: TObject);

procedure FillTables;

procedure GetLexicalOutput(rez,lex_type:string);

procedure FormCreate(Sender: TObject);

procedure SpeedButton6Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure SpeedButton3Click(Sender: TObject);

procedure SpeedButton5Click(Sender: TObject);

procedure SpeedButton9Click(Sender: TObject);

procedure SpeedButton8Click(Sender: TObject);

procedure Button10Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

type

rec=record

h:char;

l:string;

end;

mnoj=set of char;

var

Form1: TForm1;

implementation

uses Unit2, Unit3;

{$R *.dfm}

var

a:integer;

Select: TGridRect;

//правила грамматики

Rule: array ['A'..'Z',1..45] of string;

count:byte; //число правил

notterm:array[0..50] of char; //26

First: array['A'..'Z',1..45] of mnoj; //мн-во First

Follow: array['A'..'Z',1..45] of mnoj;//мн-во Follow

term: array[0..26] of char;

mas,massiv:array[0..200]of string;

step:integer;

terminals:set of char;

STop,STemp:Stack;

masx: array [1..19] of string=('i','e','f','l','r','a',';',',','(',')','{','}','<','>','=','+','-','*','/');

masp: array [1..19] of string=('3','3','3','3','6','6','-2','1','5','5','5','5','6','6','2','8','8','9','9');

procedure TForm1.FillTables;

begin

SG1.Cells[0,0]:='№';

SG1.Cells[1,0]:='Тип Лексемы';

SG1.Cells[2,0]:='Значение';

SG1.Cells[3,0]:='Код замены';

SG6.Cells[0,0]:='№';

SG6.Cells[1,0]:='Тип Лексемы';

SG6.Cells[2,0]:='Значение';

SG6.Cells[3,0]:='Код замены';

SG7.Cells[0,0]:='№';

SG7.Cells[1,0]:='Тип Лексемы';

SG7.Cells[2,0]:='Значение';

SG7.Cells[3,0]:='Код замены';

SG8.Cells[0,0]:='№';

SG8.Cells[1,0]:='Тип Лексемы';

SG8.Cells[2,0]:='Значение';

SG8.Cells[3,0]:='Код замены';

SG9.Cells[0,0]:='№';

SG9.Cells[1,0]:='Тип Лексемы';

SG9.Cells[2,0]:='Значение';

SG9.Cells[3,0]:='Код замены';

//ключевые слова

SG2.Cells[0,0]:='Лексема';

SG2.Cells[1,0]:='Код замены';

SG2.Cells[0,1]:= 'if';

SG2.Cells[0,2]:= 'else';

SG2.Cells[0,3]:= '?';

SG2.Cells[0,4]:= ':';

SG2.Cells[1,1]:= 'i';

SG2.Cells[1,2]:= 'e';

SG2.Cells[1,3]:= 'f';

SG2.Cells[1,4]:= 'l';

SG3.Cells[0,0]:='Лексема';

SG3.Cells[1,0]:='Код замены';

SG3.Cells[0,1]:= ';';

SG3.Cells[0,2]:= ',';

SG3.Cells[0,3]:= '(';

SG3.Cells[0,4]:= ')';

SG3.Cells[0,5]:= '{';

SG3.Cells[0,6]:= '}';

SG3.Cells[1,1]:= ';';

SG3.Cells[1,2]:= ',';

SG3.Cells[1,3]:= '(';

SG3.Cells[1,4]:= ')';

SG3.Cells[1,5]:= '{';

SG3.Cells[1,6]:= '}';

SG4.Cells[0,0]:='Лексема';

SG4.Cells[1,0]:='Код замены';

SG4.Cells[0,1]:= 'id';

SG4.Cells[0,2]:= 'type';

SG4.Cells[0,3]:= 'number';

SG4.Cells[1,1]:= 'd';

SG4.Cells[1,2]:= 't';

SG4.Cells[1,3]:= 'n';

SG5.Cells[0,0]:='Лексема';

SG5.Cells[1,0]:='Код замены';

SG5.Cells[0,1]:= '>';

SG5.Cells[0,2]:= '<';

SG5.Cells[0,3]:= '=';

SG5.Cells[0,4]:= '+';

SG5.Cells[0,5]:= '-';

SG5.Cells[0,6]:= '*';

SG5.Cells[0,7]:= '/';

SG5.Cells[0,8]:= '==';

SG5.Cells[0,9]:= '!=';

SG5.Cells[1,1]:= '>';

SG5.Cells[1,2]:= '<';

SG5.Cells[1,3]:= '=';

SG5.Cells[1,4]:= '+';

SG5.Cells[1,5]:= '-';

SG5.Cells[1,6]:= '*';

SG5.Cells[1,7]:= '/';

SG5.Cells[1,8]:= 'r';

SG5.Cells[1,9]:= 'a';

end;

procedure TForm1.GetLexicalOutput(rez,lex_type:string);

var

i,j,k:integer;

Symbol:string;

s:string;

begin

Symbol:='';

//Edit2.Text:='';

if rez[1]=' ' then Delete(rez,1,1);

if lex_type='keyword' then

begin

for i:=0 to SG2.RowCount do

if SG2.Cells[0,i]=rez then Symbol:=SG2.Cells[1,i];

for j := 1 to SG8.RowCount-1 do

if SG8.Cells[2,j]=rez

then begin Edit2.Text:=EDit2.Text+'('+'40,'+IntTostr(j-1)+')';

//b:=false;

rez:='';

end;

if (rez <>'') then

begin

i:=SG8.RowCount;

SG8.Cells[0,i]:=IntTostr(i-1);

SG8.Cells[1,i]:=lex_type;

SG8.Cells[2,i]:=rez;

SG8.Cells[3,i]:=Symbol;

SG8.RowCount:=i+1;

SG8.FixedRows:=1;

Edit2.Text:=EDit2.Text+'('+'40,'+IntTostr(i-1)+')';

end;

end;

if lex_type='razdel' then

begin

for i:=0 to SG3.RowCount do

if SG3.Cells[0,i]=rez then Symbol:=rez;

//Symbol:=SG3.Cells[1,i]

for j := 1 to SG6.RowCount-1 do

if SG6.Cells[2,j]=rez

then begin Edit2.Text:=EDit2.Text+'('+'20,'+IntTostr(j-1)+')';

//b:=false;

rez:='';

end;

if (rez <>'') then

begin

i:=SG6.RowCount;

SG6.Cells[0,i]:=IntTostr(i-1);

SG6.Cells[1,i]:=lex_type;

SG6.Cells[2,i]:=rez;

SG6.Cells[3,i]:=Symbol;

Edit2.Text:=EDit2.Text+'('+'20,'+IntTostr(i-1)+')';

SG6.RowCount:=i+1;

SG6.FixedRows:=1;

end;

end;

if(lex_type='type') then

begin

for i:=0 to SG4.RowCount do

if SG4.Cells[0,i]='type' then Symbol:=SG4.Cells[1,i];

for j := 1 to SG7.RowCount-1 do

if SG7.Cells[2,j]=rez

then begin Edit2.Text:=EDit2.Text+'('+'30,'+IntTostr(j-1)+')';

//b:=false;

rez:='';

end;

if (rez <>'') then

begin

i:=SG7.RowCount;

SG7.Cells[0,i]:=IntTostr(i-1);

SG7.Cells[1,i]:=lex_type;

SG7.Cells[2,i]:=rez;

SG7.Cells[3,i]:=Symbol;

Edit2.Text:=EDit2.Text+'('+'30,'+IntTostr(i-1)+')';

SG7.RowCount:=i+1;

SG7.FixedRows:=1;

end;

end;

if(lex_type='znak') then

begin

for i:=0 to SG5.RowCount do

if SG5.Cells[0,i]=rez then Symbol:=SG5.Cells[1,i];

for j := 1 to SG1.RowCount-1 do

if SG1.Cells[2,j]=rez

then begin Edit2.Text:=EDit2.Text+'('+'10,'+IntTostr(j-1)+')';

rez:='';

end;

if (rez <>'') then

begin

i:=SG1.RowCount;

SG1.Cells[0,i]:=IntTostr(i-1);

SG1.Cells[1,i]:=lex_type;

SG1.Cells[2,i]:=rez;

SG1.Cells[3,i]:=Symbol;

Edit2.Text:=EDit2.Text+'('+'10,'+IntTostr(i-1)+')';

SG1.RowCount:=i+1;

SG1.FixedRows:=1;

end;

end;

if(lex_type='id') then

begin

for i:=0 to SG4.RowCount do

if SG4.Cells[0,i]='id' then Symbol:=SG4.Cells[1,i];

for j := 1 to SG7.RowCount-1 do

if SG7.Cells[2,j]=rez

then begin Edit2.Text:=EDit2.Text+'('+'30,'+IntTostr(j-1)+')';

//b:=false;

rez:='';

end;

if (rez <>'') then

begin

i:=SG7.RowCount;

SG7.Cells[0,i]:=IntTostr(i-1);

SG7.Cells[1,i]:=lex_type;

SG7.Cells[2,i]:=rez;

SG7.Cells[3,i]:=Symbol;

Edit2.Text:=EDit2.Text+'('+'30,'+IntTostr(i-1)+')';

SG7.RowCount:=i+1;

SG7.FixedRows:=1;

end;

end;

if(lex_type='number') then

begin

for i:=0 to SG4.RowCount do

if SG4.Cells[0,i]='number' then Symbol:=SG4.Cells[1,i] ;

for j := 1 to SG7.RowCount-1 do

if SG7.Cells[2,j]=rez

then begin Edit2.Text:=EDit2.Text+'('+'30,'+IntTostr(j-1)+')';

//b:=false;

rez:='';

end;

if (rez <>'') then

begin

i:=SG7.RowCount;

SG7.Cells[0,i]:=IntTostr(i-1);

SG7.Cells[1,i]:=lex_type;

SG7.Cells[2,i]:=rez;

SG7.Cells[3,i]:=Symbol;

Edit2.Text:=EDit2.Text+'('+'30,'+IntTostr(i-1)+')';

SG7.RowCount:=i+1;

SG7.FixedRows:=1;

end;

end;

if Symbol='' then

begin

ShowMessage('Для данной лексемы ' +rez+ ' не определен код');

Exit;

end

else

begin

Edit1.text:=Edit1.text+Symbol;

Edit4.Text:=Edit4.Text+Symbol+' ';

s:=Edit4.Text;

k:=length(s);

if (s[k-3]='>') or (s[k-3]='<') or (s[k-3]='r') or (s[k-3]='a') then

Edit4.Text:=Edit4.Text+';'+' ';

Button10.Enabled:=true;

//Edit2.Text:=EDit2.Text+s1;

if rez <>'' then

begin

i:=SG9.RowCount;

SG9.Cells[0,i]:=IntTostr(i-1);

SG9.Cells[1,i]:=lex_type;

SG9.Cells[2,i]:=rez;

SG9.Cells[3,i]:=Symbol;

SG9.RowCount:=i+1;

SG9.FixedRows:=1;

end;

end;

end;

procedure LA;

label lab;

type TSost=(q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15

,q16,q17,q18,q19,q20,q21,q22,q23,q24,q25,q26,q27,q28,q29,

q30,q31,q32,q33,q34,q35,q36,q37,q38,q70);

var

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

Ter: set of char;

flag:boolean;

counts, j,i,i_old:integer;

g:integer;

Sost:TSost;

len:integer;

s:string;

st1,fff,OutStr,InStr,InStrClear: string; //Выходная строка

Psevdo:string; // Строка для псевдокода

vspom,porogd,rez,lex_type,qprev:string;

flagdel:boolean;

begin

counts:=0; flagdel:=false;

while counts<=form1.Memo1.Lines.Count-1 do

begin

s:=form1.memo1.Lines.Strings[counts];

inc(counts);

i:=1;

while i<=length(s) do

begin

if ((s[i]=' ') and (s[i+1]=' ')) or (s[i]=#9 ) and (flagdel<>true) then

Delete(s,i,1)

else

if (s[i]='/') and (s[i+1]='/') then

begin

delete(s,i,length(s)-i+1);

i:=i-1;

end

else

if (s[i]=' ') and (i=length(s)) then

delete(s,i,1)

else

if s[i]=']' then

begin

flagdel:=false ;

inc(i);

delete(s,1,1);

end

else

if (s[i]='[') or (flagdel=true) then

begin

Delete(s,1,1);

flagdel:=true;

end

else

inc(i);

end;

form1.memo4.lines.add(s);

end;

for i:=0 to Form1.Memo4.Lines.Count do

begin

if Form1.Memo4.Lines[i]='' then InStrclear:=InStrclear else

InStrclear:=InStrclear+' '+Form1.Memo4.Lines[i];

end;

// InStrClear:=MakeClearStr(instr);

InStrclear:=InStrclear+' ';

//Начало разбора автоматом

Sost:=q0;

len:=length(InStrClear);

OutStr:='';

i:=1;

i_old:=1;

while i<=len do

begin

case Sost of

q0:

case InStrClear[i] of

'i': Sost:=q1;//int,if

'c' : Sost:=q3;//char

'b': Sost:=q6;//boolean

'l': Sost:=q12;//long

'f': Sost:=q15;//float

'd': Sost:=q19; //double

'e': Sost:=q26; //else

'?',':': Sost:=q29; //?-if :-else

';',',','(',')','{','}': Sost:=q33; //разделители

'=','<','>','/','+','-','*','!': sost:=q31;

' ': Sost:=q0;

'0'..'9':Sost:=q37;

else Sost:=q35;

end;

q1:

case InStrClear[i] of

'n': Sost:=q2;//int

'f':Sost:=q29; //if

else Sost:=q70;

end;

q2:

case InStrClear[i] of

't': Sost:=q24;//int

else Sost:=q70;

end;

q3:

case InStrClear[i] of

'h': Sost:=q4;//char

else Sost:=q70;

end;

q4:

case InStrClear[i] of

'a': Sost:=q5;//char

else Sost:=q70;

end;

q5:

case InStrClear[i] of

'r': Sost:=q24;//char

else Sost:=q70;

end;

q6:

case InStrClear[i] of

'o': Sost:=q7;//boolean

else Sost:=q70;

end;

q7:

case InStrClear[i] of

'o': Sost:=q8;//boolean

else Sost:=q70;

end;

q8:

case InStrClear[i] of

'l': Sost:=q9;//boolean

else Sost:=q70;

end;

q9:

case InStrClear[i] of

'e': Sost:=q10;//boolean

else Sost:=q70;

end;

q10:

case InStrClear[i] of

'a': Sost:=q11;//boolean

else Sost:=q70;

end;

q11:

case InStrClear[i] of

'n': Sost:=q24;//boolean

else Sost:=q70;

end;

q12:

case InStrClear[i] of

'o': Sost:=q13;//long

else Sost:=q70;

end;

q13:

case InStrClear[i] of

'n': Sost:=q14;//long

else Sost:=q70;

end;

q14:

case InStrClear[i] of

'g': Sost:=q24;//long

else Sost:=q70;

end;

q15:

case InStrClear[i] of

'l': Sost:=q16;//float

else Sost:=q70;

end;

q16:

case InStrClear[i] of

'o': Sost:=q17;//float

else Sost:=q70;

end;

q17:

case InStrClear[i] of

'a': Sost:=q18;//float

else Sost:=q70;

end;

q18:

case InStrClear[i] of

't': Sost:=q24;//float

else Sost:=q70;

end;

q19:

case InStrClear[i] of

'o': Sost:=q20;//double

else Sost:=q70;

end;

q20:

case InStrClear[i] of

'u': Sost:=q21;//double

else Sost:=q70;

end;

q21:

case InStrClear[i] of

'b': Sost:=q22;//double

else Sost:=q70;

end;

q22:

case InStrClear[i] of

'l': Sost:=q23;//double

else Sost:=q70;

end;

q23:

case InStrClear[i] of

'e': Sost:=q24;//double

else Sost:=q70;

end;

q24:

case InStrClear[i] of

' ': Sost:=q25;

else Sost:=q35;

end;

q26:

case InStrClear[i] of

'l': Sost:=q27;//else

else Sost:=q70;

end;

q27:

case InStrClear[i] of

's': Sost:=q28;//else

else Sost:=q70;

end;

q28:

case InStrClear[i] of

'e': Sost:=q29;//else

else Sost:=q70;

end;

q29:

case InStrClear[i] of

' ': Sost:=q30;

else Sost:=q35;

end;

q31:

case InStrClear[i] of

' ','a'..'z','0'..'9': Sost:=q32;

'=':Sost:=q31;

// : Sost:=q32;

// :Sost:=q32;

else Sost:=q35;

end;

q33:

case InStrClear[i] of

' ','a'..'d','f'..'z','0'..'9',';': Sost:=q34;

'e': Sost:=q26; //else

else Sost:=q35;

end;

q35:

case InStrClear[i] of

':','=','<','>',' ',';',',','/','+','-','*','!': Sost:=q36;

'a'..'z': Sost:=q35;

'0'..'9':Sost:=q35;

else Sost:=q70;

end;

q37:

case InStrClear[i] of

' ','=','<','>',';',',','/','+','-','*':Sost:=q38;//считаем строку цифр num

'0'..'9':Sost:=q37;

else Sost:=q70;

end;

else ShowMessage('No stase');

end;//End of State case

if Sost=q70 then

begin

ShowMessage('Произошла ошибка. Неправильный символ "'+InStrClear[i]+'"');

Sost:=q0;

i_old:=i;

i:=i-1;

// exit;

end;

if Sost=q30 then

begin

rez:=Copy(InStrClear,i_old,(i-i_old));

Trim(rez);

lex_type:='keyword';

Form1.GetLexicalOutput(rez,lex_type);

Sost:=q0;

i_old:=i;

i:=i-1;

end;

if Sost=q34 then

begin

//rez:=Copy(InStrClear,i,1);

rez:=Copy(InStrClear,i_old,(i-i_old));

Trim(rez);

lex_type:='razdel';

Form1.GetLexicalOutput(rez,lex_type);

Sost:=q0;

i_old:=i;

i:=i-1;

end;

if Sost=q32 then

begin

//rez:=Copy(InStrClear,i,1);

rez:=Copy(InStrClear,i_old,(i-i_old));

Trim(rez);

lex_type:='znak';

Form1.GetLexicalOutput(rez,lex_type);

Sost:=q0;

i_old:=i;

i:=i-1;

end;

if Sost=q25 then

begin

rez:=Copy(InStrClear,i_old,(i-i_old));

Trim(rez);

lex_type:='type';

Form1.GetLexicalOutput(rez,lex_type);

Sost:=q0;

i_old:=i;

i:=i-1;

end;

if(Sost=q38) then

begin

rez:=Copy(InStrClear,i_old,(i-i_old));

Trim(rez);

lex_type:='number';

Form1.GetLexicalOutput(rez,lex_type);

Sost:=q0;

i_old:=i;

i:=i-1;

end;

if Sost=q36 then

begin

rez:=Copy(InStrClear,i_old,(i-i_old));

Trim(rez);

lex_type:='id';

Form1.GetLexicalOutput(rez,lex_type);

Sost:=q0;

i_old:=i;

i:=i-1;

end;

inc(i);

end;

end;

procedure TForm1.SpeedButton1Click(Sender: TObject);

var

i,j,q: Integer;

b:boolean;

rez,lex_type,Symbol:string;

begin

//SG1.RowCount:=1;

i:=0;

lex_type:='';

rez:='';

Symbol:='';

for i := 0 to 3 do

for j := 1 to SG1.RowCount+1 do begin

SG1.Cells[i,j]:='';

SG1.RowCount:=0;

end;

for i := 0 to 3 do

for j := 1 to SG6.RowCount+1 do begin

SG6.Cells[i,j]:='';

SG6.RowCount:=0;

end;

for i := 0 to 3 do

for j := 1 to SG7.RowCount+1 do begin

SG7.Cells[i,j]:='';

SG7.RowCount:=0;

end;

for i := 0 to 3 do

for j := 1 to SG8.RowCount+1 do begin

SG8.Cells[i,j]:='';

SG8.RowCount:=0;

end;

Edit1.Text:='';

Edit2.Text:='';

Edit4.Text:='';

memo4.Clear;

if memo1.Text='' then application.MessageBox('Введите пример!','Внимание!',mb_iconwarning);

la;

edit3.Text:=edit1.Text;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

FillTables;

form1.StringGrid1.Cells[1,0]:='First';

form1.StringGrid1.Cells[2,0]:='Follow';

form1.StringGrid2.Cells[0,0]:='Стек';

form1.StringGrid2.Cells[1,0]:='Входная лента';

form1.StringGrid2.Cells[2,0]:='Выходная лента';

end;

procedure TForm1.SpeedButton6Click(Sender: TObject);

var f:textfile;

st:string;

begin

memo1.Clear;

if not(Fileexists(inttostr(a)+'.txt')) then a:=1;

Assignfile(f,inttostr(a)+'.txt');

reset(f);

while not(eof(f)) do begin

readln(f,st);

memo1.Lines.add(st);

end;

closefile(f);

a:=a+1;

form1.SpeedButton1.Enabled:=true;

end;

procedure showgrammar(s:string);

var ffile:textfile; str:string;

begin

form1.Memo2.Clear;

assignfile(ffile,s);

reset(ffile);

while not Eof(ffile) do

begin

readln(ffile,str);

form1.Memo2.Lines.Add(str);

end;

closefile(ffile);

end;

procedure FirstSet ();

label step1,step2,step3,final;

var

i,j,k:byte;

step: byte;//номер прохода по алгоритму

symbol,s:char;

temp:string;

flag:boolean;

begin

step:=1;//первый проход

//первый шаг

step1: begin

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];

for k:=1 to Count-1 do

begin

temp:=Rule[symbol,k];//одно правило для нетерминала symbol

if (length(temp)<>0) then

if temp[1]<>'$' then First[symbol,step]:=First[symbol,step]+[temp[1]];

end;

temp:='';

end;

step:=step+1;

end;

//второй шаг

step2: begin

k:=step;

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];//нетерминал

for j:=0 to Form1.Memo2.Lines.Count-1 do

begin

{если в First для symbol

входят другие нетерминалы, то объединяем соответствующие множества}

if(symbol<>notterm[j])and(notterm[j] in First[symbol,step-1])then

begin

First[symbol,k]:=First[symbol,k-1]+First[notterm[j],step-1];

k:=k+1;

end;

end;

First[symbol,step]:=First[symbol,k-1];

k:=step;

end;

end;

//3 шаг

step3: begin

flag:=false;

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

//проверка мн-в на равенство

if First[notterm[i],step]<>First[notterm[i],step-1] then

begin

flag:=true;

step:=step+1;

//если не равны то вернутся к шагу 2

goto step2;

end;

end;

if flag=false then

begin

step:=step+1;

goto final;

end;

end;

//конец алгоритма

final: begin

//удаление нетерминалов из First

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];

for j:=0 to Form1.Memo2.Lines.Count-1 do

begin

if (notterm[j] in First[symbol,step-1])then

begin

First[symbol,k]:=First[symbol,k-1]-[notterm[j]];

k:=k+1;

end;

end;

First[symbol,1]:=First[symbol,k-1];

k:=step;

end;

Form1.StringGrid1.RowCount:=Form1.Memo2.Lines.Count+1;

//вывод в таблицу

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

temp:='';

for s:=#32 to #125 do

if (s in First[notterm[i],1]) then

if s=#32 then temp:=temp+' '+''' ''' else temp:=temp+' '+s;

Form1.StringGrid1.Cells[0,i+1]:=notterm[i];

Form1.StringGrid1.Cells[1,i+1]:=temp;

end;

end;

end;

procedure FollowSet();

label step1,step2,step3,step4,step5,step6,final;

var

//вспомогательные множества

Follow1,Follow2, HelpFollow:array['A'..'Z',1..60] of mnoj;

i,j,k,step,n,num:byte;

temp,str:string;

symbol,s:char;

flag,bool:boolean;

begin

step:=1;

//первоначально множества пусты

for s:='A' to 'Z' do

for i:=1 to 40 do Follow[s,i]:=[];

// 1 шаг

step1: begin

k:=step;

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];

{в Follow для нетерминала symbol добавляем все символы, стоящие за symbol в правилах

из правой части грамматики}

temp:='';

str:='';

for num:=0 to Form1.Memo2.Lines.Count-1 do

begin

for n:=1 to Count-1 do

begin

temp:=Rule[notterm[num],n];//одно правило для нетерминала

if (length(temp)<>0) then

begin

for j:=1 to length(temp) do

if temp[j]=symbol then str:=copy(temp,j+1,length(temp)-j) ;

if str<>'' then begin

for j:=1 to length(str) do

begin

Follow[symbol,k]:=Follow[symbol,k-1]+[str[j]];

k:=k+1;

end;

str:='';

Follow[symbol,step]:=Follow[symbol,k-1];

k:=step+1;

end; end; end;

end; end;

end;

step2: begin

{добавляем символ # во множество Follow стартового нетерминала}

Follow[notterm[0],step+1]:=Follow[notterm[0],step]+['#'];

Follow[notterm[0],step]:=Follow[notterm[0],step+1];

step:=step+1;

end;

step3: begin

k:=step;

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];//нетерминал

Follow1[symbol,k-1]:=Follow[symbol,step];

for j:=0 to Form1.Memo2.Lines.Count-1 do

begin

{если во множество Follow для рассматриваемого нетерминала symbol

входят другие нетерминалы, то объединяем его со множеством

First входящего нетерминала}

if(symbol<>notterm[j])and(notterm[j] in Follow[symbol,step-1])then

begin

Follow1[symbol,k]:=Follow1[symbol,k-1]+First[notterm[j],1];

k:=k+1;

end;

end;

Follow1[symbol,step]:=Follow1[symbol,k-1];

k:=step;

end;

end;

step4: begin

k:=step;

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];//нетерминал

Follow2[symbol,k-1]:=Follow1[symbol,step];

{если во множество Follow1 для рассматриваемого нетерминала symbol

входят другие нетерминалы и существует правило B->$, то объединяем его

со мноржеством Follow1 входящего нетерминала}

for j:=0 to Form1.Memo2.Lines.Count-1 do

begin

if(symbol<>notterm[j])and(notterm[j] in Follow1[symbol,step])then

begin

bool:=false;

for n:=1 to count-1 do

if Rule[notterm[j],n]='$' then bool:=true;

if (bool=true) then

begin

Follow2[symbol,k]:=Follow2[symbol,k-1]+Follow1[notterm[j],step];

k:=k+1;

end;

end;

end;

Follow2[symbol,step]:=Follow2[symbol,k-1];

k:=step;

end;

end;

step5: begin

k:=step;

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];//нетерминал

HelpFollow[symbol,k-1]:=Follow2[symbol,step];

for j:=0 to Form1.Memo2.Lines.Count-1 do

begin

{если для некоторого терминала B существует правило

B->aSymbol, то объединяем Follow2(Symbol) и Follow2(B)}

if(symbol<>notterm[j])then

begin

temp:='';

for n:=1 to count-1 do

begin

temp:=Rule[notterm[j],n];

if (temp<>'')and(temp[length(temp)]=symbol) then

begin

HelpFollow[symbol,k]:=HelpFollow[symbol,k-1]+Follow2[notterm[j],step];

k:=k+1;

end;

end;

end;

end;

Follow[symbol,step]:=HelpFollow[symbol,k-1];

k:=step;

end;

end;

step6:begin

flag:=false;

for i:=0 to Form1.Memo2.Lines.Count-1 do

//проверка множеств на равенство

if Follow[notterm[i],step]<>Follow[notterm[i],step-1] then flag:=true;

//если множества не равны возвращаемся к шагу 3

if flag=true then

begin

step:=step+1;

for i:=0 to Form1.Memo2.Lines.Count-1 do

Follow[notterm[i],step]:=Follow[notterm[i],step-1];

goto step3;

end;

//если множества равны, то переходим к завершающему этапу

if flag=false then

begin

step:=step+1;

goto final;

end;

end;

//конец алгоритма

final: begin

//удаление нетеминалов из множеств Follow

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

symbol:=notterm[i];

for j:=0 to Form1.Memo2.Lines.Count-1 do

begin

if (notterm[j] in Follow[symbol,step-1])then

begin

Follow[symbol,k]:=Follow[symbol,k-1]-[notterm[j]];

k:=k+1;

end;

end;

Follow[symbol,1]:=Follow[symbol,k-1];

k:=step;

end;

//вывод в таблицу

for i:=0 to Form1.Memo2.Lines.Count-1 do

begin

temp:='';

for s:=#32 to #125 do

begin

if (s in Follow[notterm[i],1]) then

if s=#32 then temp:=temp+' '+''' ''' else temp:=temp+' '+s;

end;

Form1.StringGrid1.Cells[2,i+1]:=temp;

end;

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i,j:byte;

temp,res:string;

s:char;

begin

memo2.Clear;

for i:=1 to Form2.StringGrid1.RowCount do

for j:=1 to Form2.StringGrid1.ColCount do

stringgrid1.Cells[j,i]:='';

showgrammar('gramatika.txt');

count:=1;

for i:=0 to Memo2.Lines.Count-1 do

begin

temp:=Form1.Memo2.Lines[i];

j:=4;

s:=temp[1];

notterm[i]:=s;

res:='';

while j<=length(temp) do

begin

if (temp[j]<>'|') then

res:=res+temp[j];//считываем правило

if (temp[j]='|') or (j=length(temp))

then

begin

Rule[s,count]:=res;

count:=count+1;

res:='';

end;

j:=j+1;

end;

end;

FirstSet();

FollowSet();

end;

//вставка в таблицу разбора

procedure Paste (terminal:char; neterminal:char; temp:string);

var

i,j:byte;

begin

for i:=1 to Form2.StringGrid1.RowCount do

if Form2.StringGrid1.Cells[0,i]=neterminal then

for j:=1 to Form2.StringGrid1.ColCount do

if Form2.StringGrid1.Cells[j,0]=terminal then

Form2.StringGrid1.Cells[j,i]:=temp;

end;

procedure GetTerminal;

var

i,j:byte;

temp: string;

begin

Terminals:=[];

//для удобства массив терминалов

//сначала заполним символом #6

for i:=0 to 26 do

term[i]:=#6;

//терминалы введены в строку редактирования

temp:='d t n i e f l r a ; , { } ( ) < > = + - * /';