Содержание
Введение ………………………………………………………………………. 3
1. Организация таблицы идентификаторов ………………………………. 4
1.1 Исходные данные …………………………………………………... 4
1.2 Назначение таблиц идентификаторов …………………………….. 4
1.3 Рехеширование с помощью произведения ……………………….. 5
1.4 Упорядоченный список ……………………………………………. 8
1.5 Результаты ………………………………………………………….. 11
2. Проектирование лексического анализатора …………………………… 12
2.1 Исходные данные …………………………………………………... 12
2.2 Принципы работы лексического анализатора ……………………. 12
2.3 Схема распознавателя ……………………………………………… 14
2.4 Результаты ………………………………………………………….. 17
3. Проектирование синтаксического анализатора ……………………….. 19
3.1 Исходные данные …………………………………………………... 20
3.2 Построение синтаксического анализатора ……………………….. 21
3.3 Результаты ………………………………………………………….. 22
Заключение ……………………………………………………………………. 24
Список использованной литературы ………………………………………... 25
Приложение А – Исходный текст программы ……………………………… 26
Приложение Б – Граф состояний лексического анализатора ……………… 38
Приложение В – Матрица операторного предшествования ……………….. 45
Введение
Программа, написанная на машинном языке какой-либо конкретно взятой ЭВМ, может быть выполнена на ней непосредственно. Однако программирование на машинном языке является очень трудоемким, и поэтому программы пишутся на языках, имеющих более символическую и стилизованную форму, которая легче для человеческого понимания. Отсюда возникает потребность в переводе текста программы из одной формы представления в другую. Эту функцию выполняет транслятор – программа, которая переводит входную программу на исходном языке в эквивалентную ей выходную программу на результирующем языке. Чтобы создать транслятор, необходимо выбрать входной и выходной языки. Одной из разновидностей транслятора является компилятор – программа, которая осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблера. Компиляторы являются самым распространенным видом трансляторов. Они имеют самое широкое практическое применение благодаря широкому распространению всевозможных языков программирования.
Целью курсовой работы является изучение составных частей, основных принципов построения и функционирования компиляторов, практическое освоение методов построения простейших компиляторов для заданного входного языка. Для выполнения курсовой работы использована среда разработки Delphi 7.
1. Организация таблицы идентификаторов
1.1 Исходные данные
Требуется написать программу, чтобы сравнить два способа организации таблицы идентификаторов. Идентификаторы должны считываться из файла и размещаться в таблицах с помо¬щью заданных методов. Программа должна выполнять многократный поиск указанных идентификаторов по тре¬бованию пользователя. В процессе поиска идентификатора в таб¬лицах должно подсчитываться количество сравнений и среднее число сравнений для сопоставления эффективности используемых методов.
В курсовом проекте используется сопоставление двух методов: хеш-адресация (метод разрешения коллизий: рехешированием с помощью произведения) и упорядоченный список.
1.2 Назначение таблиц идентификаторов
Таблица идентификаторов (ТИ) – это специальным образом организованный набор данных, который служит для хранения информации об исходной программе. Каждое поле таблицы содержит всю необходимую компилятору информацию об элементе, может пополняться по мере работы компилятора. Под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры.
Структура данных таблицы идентификаторов должна со¬держать в обязательном порядке поле имени идентификатора, а также поля дополнительной информации об идентификаторе по усмотрению разработчиков компилятора, но в курсовом проекте хранение какой-либо дополнительной информации об идентификаторах можно не организовывать. Таблицы идентификаторов реализованы в виде статических массивов.
1.3 Хеш-адресация с рехешированием.
Хэш-адресация заключается в использовании значения, возвращаемого хэш-функцией, в качестве адреса ячейки из некоторого массива данных. В курсовом проекте хэш-функция будет выдавать сумму ко¬дов первого и второго элементов строки, если строка содер¬жит один символ, то хэш-функция берется от одного элемента.
Для решения проблемы коллизии используем метод рехеширования с помощью произведения, новую хеш-функцию получаем по формуле:
hi(A) = ( h(A)∙i ) mod Nm, (1)
где i – число возникновения коллизий, а Nm – максимальное значение из области значений (равное 509).
Согласно этому методу – хеш-адресации – если для элемента A адрес n0 = h(А), вычисленный с помощью хэш-функции, указывает на уже занятую ячейку, то необходимо вычислить значение функции n1 = h1(А) и проверить занятость ячейки по адресу n1. Если и она занята, то вычисляется значение h2(A), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(A) не совпадет с h(А). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице.
В целом рехеширование позволяет добиться неплохих результатов для эффективного поиска элемента в таблице, но эффективность метода сильно зависит от заполненности таблицы идентификаторов и качества используемой хеш-функции – чем реже возникают коллизии, тем выше эффективность. Требование неполного заполнения таблицы ведет к неэффективному использованию объема доступной памяти.
Блок-схема добавления и поиска элемента в таблице идентификаторов методом хеш-адресации представлен на рис. 1 и рис. 2.
Рис. 1 Блок-схема добавления элемента методом хеш-адресации
Блок-схема поиска элемента в таблице идентификаторов методом хеш-адресации представлена на рис. 2.
Рис.2 Блок-схема поиска элемента в ТИ методом хеш-адресации
1.4 Упорядоченный список
Метод организации таблицы идентификаторов, в котором при добавлении надо перестраивать весь список, т.е. упорядочивать его согласно некоторому условию.
В этом методе применяется бинарный или логарифмический способ поиска элементов. Алгоритм этого поиска заключается в следующем: искомый символ сравнивается с элементом (N+1)/2 в середине таблицы; если этот элемент не является искомым, то мы должны просмотреть только блок элементов, пронумерованных от 1 до (N+1)/2 – 1, или блок элементов от (N+1)/2 + 1 до N в зависимости от того, меньше или больше искомый элемент того, с которым его сравнивали. Затем процесс повторяется с блоком в два раз меньшего размера. Так продолжается до тех пор, пока либо не будет найден искомый элемент, либо алгоритм не дойдет до очередного блока.
Так как на каждом шаге число элементов, которые могут содержать искомый элемент, сокращается в 2 раза, максимальное число сравнений равно 1+log2(N).
Недостатком данного метода в том, что для поиска требуется упорядочивание таблицы идентификаторов, следовательно, время заполнения будет зависеть от числа добавляемых элементов.
Блок-схемы добавления и поиска элемента в упорядоченном списке представлены на рис. 3 и рис. 4.
Рис. 3. Блок-схема алгоритма добавления элемента в упорядоченный список
Рис. 4 Блок-схема алгоритма поиска элемента в упорядоченном списке
1.5 Результаты
Полученные результаты (рис. 5) говорят о том, что при поиске в методе хеш-адресации с рехешированием количество операций сравнения, чем при упорядоченном списке. А так как чаще всего компилятору приходится искать идентификатор, то, следовательно, метод хеш-адресации с рехешированием более эффективен.
Рис. 5 Экранная форма организации таблиц идентификаторов
2. Проектирование лексического анализатора
2.1 Исходные данные
Требуется написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием и по¬рождает таблицу лексем с указанием их типов и значений. Текст на входном язы¬ке задается в виде символьного (текстового) файла. Программа должна выдавать сообщения о наличии во входном тексте ошибок, которые могут быть обнаруже¬ны на этапе лексического анализа.
Входной язык содержит:
операторы цикла “do” и “while”;
идентификаторы;
круглые открывающиеся и закрывающиеся скобки;
операторы сравнения “<”, “>”, “=”;
знак присваивания “:=” ;
составные операторы “begin” и “end”;
условные операторы “if”, “then”, “else” и “endif”;
ключевые слова начала и конца программы “prog” и “end.”;
разделяющий знак “;”.
логические операторы “not”, “and” и “or”;
арифметические операции сложения, вычитания, умножения и деления;
комментарии внутри * и *;
константы в двоичной форме.
2.2 Принципы работы лексического анализатора
Лексический анализатор – это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходно¬го языка. На вход лексического анализатора поступает текст исходной програм¬мы, а выходная информация передастся для дальнейшей
обработки компилято¬ром на этапе синтаксического анализа и разбора.
Лексема (лексическая единица языка) – это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка. Лексемами языков программирования являются иден¬тификаторы, константы, ключевые слова языка, знаки операций и т. п.
В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также вы¬деление лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, знаков операций, разделителей и ключевых (служебных) слов входного языка.
Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем. Этот перечень представляется в виде таблицы, называемой таблицей лексем.
Язык описания констант и идентификаторов в большинстве случаев является регулярным, то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы (КА).
Любой КА может быть задан с помощью пяти параметров: М(Q, V,δ,q0,F),
где: Q – множество состояний автомата;
V – конечное множество допустимых входных символов;
d – функция переходов автомата;
q0ÎQ – начальное состояние автомата;
FÍQ – множество конечных состояний автомата.
Алгоритм работы простейшего лексического анализатора:
просматривается входной поток символов программы на исходном языке до обнаружения очередного символа, ограничивающего лексему;
для выбранной части входного потока выполняется функция распознавания лексемы;
при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этану;
при неуспешном распознавании лексемы, она помещается в поле ошибочных лексем, и делается попытка распознать следующую лексему (идет возврат к перво¬му этану алгоритма).
Работа лексического анализатора продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.
2.3 Схема распознавателя
Распознаватель – это специальный алгоритм, который позволяет определить принадлежность цепочки символов заданному языку.
Схема распознавателя представлена на рисунке 2:
Рис.6 Схема распознавателя
Во входном языке константы заданы в двоичной форме. Двоичная константа должна содержать цифры 0 и 1 .Имена идентификаторов должны содержать только английские буквы и цифры.
Грамматика входного языка в форме Бэкуса-Наура:
^ – знак пробела.
Для удобства введем дополнительные обозначения:
x1 – все символы
x2 – все симв. кроме ^
x3 – все симв. кроме 0..9
x4 – все симв. кроме }
x5 – все симв. кроме A..F,0..9,^
x6 – все симв. кроме a..z, 0..9,^
x7 – все симв. кроме a..z, 0..9
x8 – символы a..g, i..z, 0..9
x9 – символы a..d, f..z, 0..9
x10 – символы a..e, g..z, 0..9
x11 – символы a..q, s..z, 0..9
x12 – символы a..n, p..z, 0..9
x13 – символы a..f, h..z, 0..9
x14 – символы a..k, m, o..z, 0..9
x15 – символы a..c, e..z, 0..9 x16 – символы a..h, j..z, 0..9
x17 – символы a..r, t..z, 0..9
x18 – символы a..k, m..z, 0..9
x19 – символы a..s, u..z, 0..9
x20 – символы a..m, o..z, 0..9
x21 – все симв. кроме =
x22 – все симв. кроме ^ , h
x23 – символы a..z, 0..9
x24 – символы 0..9, A..F
x25 – символы 1..9, A..F
x26 – символы 0..9
x27 – символы 1..9
x28 – все симв. кроме a..z, 0..9, ∙
x29 – символы a..c, e..h, j..z, 0..9
G ( {0..9, a..z, A..F, ;, <, >, +, -, (, ), :, =, ^ }, { S, E, H F1, F2 B1, B2, B3, OR, OR1, IR, IR1, IR2, NR, NR1, NR2, T, I, P1, P2, Z, C, D, DO, DO1, WH, WH1, WH2, WH3, WH4, BE, BE1, BE2, BE3, BE4, EN, EN1, EN2, EN3, EN4, EN5, PR, PR1, PR2, PR3, IF, IF1, TH, TH1, EL1, EL2, EL3, SH, SH1, KO}, P, S )
P:
S®^|B1^|B2^|B3^|KO^|T^|F1^|F2^|P2^|Z^|IR^|IR1^|IR2^|IN^|
IN1^|IN2^|I^|ORx6|OR^|WH^|WH1^|WH2^|WH3^|WH4^|DO^|DO1^| BE^|BE1^|BE2^|BE3^|BE4^|PR^|PR1^|PR2^|PR3^|EN^|EN1^|EN2^|EN3^|EN4^|EN5^|EL1^|EL2|EL3^|TH^|TH1^|TH2^|TH3^|IF^|IF1^|
T® ;
F1® )
F2® (
Z® +|-|*|/
KO® {
B1® <
B2® >
B3® =
IR® a
IR1® IRn
IR2® IR1d
IN® n
IN1® INo
IN2® IN1t
OR® o
OR1® ORr
C® x27|Cx26
D® 0
SH® Dh
SH1® SHx25|SH1x24
DO® d
DO1® DOo
WH® w
WH1® WHh
WH2® WH1i
WH3® WH2l
WH4® WH3e
PR® p
PR1® PRr
PR2® PR1o
PR3® PR2g
BE® b
BE1® BEe
BE2® BE1g
BE3® BE2i
BE4® BE3n
EN® e
EN1® n
EN2® EN1d
EN3® EN2∙
EN4® EN2i
EN5® EN4f
EL1®ENl
EL2® EL1s
EL3®EL2e
IF® i
IF1® IFf
TH® t
TH1® THh
TH2®TH1e
TH3®TH2n
I®IRx20|IR1x15|IR2x23|INx12|IN1x19|IN2x23|Ix23|ORx11|OR1x23|
WHx8|WH1x16|WH2x18|WH3x9|WH4x23|DOx12|DO1x23|BEx9|BE1x13|
BE2x16|BE2x16|BE3x20|BE4x23|PRx11|PR1x12|PR2x13|PR3x23|ENx14|
EN1x15|EN2x29|EN4x10|EN5x23|EL1x17|EL2x9|EL3x23|THx8|TH1x9|TH2x20|
TH3x23|IFx10|IF1x23
Конечный детерминированный автомат M’({S, E, H F1, F2 B1, B2, B3, OR, OR1, IR, IR1, IR2, NR, NR1, NR2, T, I, P1, P2, Z, C, D, DO, DO1, WH, WH1, WH2, WH3, WH4, BE, BE1, BE2, BE3, BE4, EN, EN1, EN2, EN3, EN4, EN5, PR, PR1, PR2, PR3, IF, IF1, TH, TH1, EL1, EL2, EL3, SH, SH1, KO},{0..9, a..z, A.F, ;, <, >, +, -, *, /, (, ), :, =, ^ },d,H,{S}), который распознает язык, заданный этой грамматикой, представлен приложении Б. Начальным состоянием автомата является состояние H, конечным S. Поскольку КА работает с непрерывным потомком лексем, перейдя в конечное состояние, он тут же должен возвращаться в начальное, чтобы распознавать очередную лексему. Поэтому в моделируемой программе эти два состояния объединяются. В автомат введено особое состояние E, обозначающее состояние «ошибка». В это состояние КА переходит всегда, когда получает на вход символ, по которому нет переходов из текущего состояния.
2.4 Результаты
В результате своей работы лексический анализатор формирует таблицу лексем и таблицу идентификаторов (рис. 7).
Рис.7 Экранная форма результатов работы лексического анализатора
Построенный лексический анализатор позволяет выде¬лять в тексте исходной программы лексемы следующих типов:
операторы цикла “do” и “while”;
идентификаторы;
круглые открывающиеся и закрывающиеся скобки;
операторы сравнения “<”, “>”, “=”;
знак присваивания “:=”;
составные операторы “begin” и “end”;
условные операторы “if”, “then” ,“else”, “endif”;
ключевые слова начала и конца программы “prog” и “end.”;
разделяющий знак “;”;
логические операторы “not”, “and” и “or”;
арифметические операции сложения, вычитания, умножения и деления;
комментарии между * и *;
константы в двоичной форме.
Если обнаружена неверная лексема лексический анализатор помещает ее в поле ошибочных лексем и продолжает дальнейшую работу, пока не будет достигнут конец файла. Если комментарии не будут закрыты, то работа лексического анализатора прекращается, и выдается сообщение об ошибке (рис. 8).
Рис. 8 Экранная форма ошибки «Не закрыт комментарий»
Также заполняется таблица идентификаторов с помощью выбранного метода – хеш-адресации с рехешированием с помощью произведения.
3. Проектирование синтаксического анализатора
3.1 Исходные данные
Требуется написать программу, которая выполняет синтаксический разбор цепочки символов по заданной грамматике с построением дерева разбора. На вход синтаксического анализатора поступает информация, содержащаяся в таблице лексем, заполненная на этапе лексического анализа. При наличии во входной цепочке текста, соответствующего заданному языку, про¬грамма должна строить и отображать дерево синтаксического разбора. Если же текст во входной цепочке содержит синтаксические ошибки, программа должна выдавать сообщения об ошибке.
Входной язык задан с помощью следующей КС-грамматики:
G({prog, end., if, then, else, endif, begin, end, while, do, and, or, not, =, <,>, (, ), -, +, a, ;, :=}, {S, L, O, B, C, K, D, E, T}, P,S))
с правилами Р:
S ® prog L end.
L ® O | L ; O | L;
O ® if B then O else O endif | if B then O endif | begin L end |
do O while (B) | a := E
B ® B or C | C
C® C and D | D
D ® E < E | E > E | E = E | (B) | not (B)
E ® E – F | E + F | E * F | E / F |E
F ® (E) | a
Жирным шрифтом в грамматике и в правилах выделены терминальные символы.
3.2 Построение синтаксического анализатора
Синтаксический анализатор выполняет две основные задачи: проверка правильности конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразование её в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Одним из таких способов представления является дерево синтаксического разбора.
Класс КС-языков допускает распознавание с помощью недетерминированного автомата со стековой (или магазинной) памятью – МП-автомата.
Схема МП-автомата представлена на рисунке 9:
Рис.9 Схема МП-автомата
МП-автоматом выполняется алгоритм «сдвиг-свертка» для грамматики операторного предшествования. Для моделирования его работы необходима входная цепочка символов и стек, в котором автомат может обращаться не только к самому верхнему символу, но и к некоторой цепочке символов на вершине стека. После завершения алгоритма «свиг-свертка» решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в состоянии, когда в стеке находятся начальный символ грамматики и символ конца строки. Выполнение алгоритма может быть прервано, если на одном из его шагов возникла ошибка.
В курсовом проекте КС-грамматика является грамматикой операторного предшествования. Для построения анализатора на основе этой грамматики, необходимо построить матрицу операторного предшествования. Для этого на первом шаге нужно получить множество крайних левых и крайних правых символов из правил грамматики G. Полученное множество представлено в табл.1.
Таблица 1
Множество крайних левых и крайних правых символов
Символы U L(U) R(U)
F (, a ) , a
E E, F, (, a F, ) , a
D (, not, E, F, a E, F, ) , a
C C, D, (, not, E, F, a D, E, F, ) , a
B B, C, D, (, not, E, F, a C, D, E, F, ) , a
O if, begin, do, a endif, end, E, ), F, a
L O, L, if, begin, do, a O, ;, endif, end, E, ), F, a
S prog end.
На втором шаге, после многократного анализа, получили множество крайних левых и крайних правых терминальных символов из правил грамматики G. Полученное множество представлено в табл.2.
Таблица 2
Множество крайних левых и крайних правых терминальных символов
Символы U Lt(U) Rt (U)
F (, a ) , a
E -, +, *, /, (, a -, +, *, /, ) , a
D <, >, =, (, not, -, +, *, /, a <, >, =, ), -, +, *, /, a
C and, <, >, =, (, not, -, +, *, /, a and, <, >, =, ), -, +, *, /, a
B or, and, <, >, =, (, not, -, +, *, /, a or, and, <, >, =, ), -, +, *, /, a
O if, begin, do, a endif, end, ), :=, -, +, *, /, a
L ;, if, begin, do, a ;, endif, end, ), :=, -, +, *, /, a
S prog end.
F (, a ) , a
На основе грамматики и табл.2 строим матрицу операторного предшествования. Матрица операторного предшествования представлена в приложении B. Также, для практического использования, матрицу предшествования дополняем символами ^н и ^к (начало и конец цепочки).
Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Построенная таким образом грамматика называется «остовной» грамматикой.
Основная грамматика, полученная на основе исходной грамматики:
G({prog, end., if, then, else, endif, begin, end, while, do, and, or, not, =, <, >, (, ), -, +, a, ;, :=}, {E,B}, P,S))
Р’:
E ® prog E end. – правило № 1
E ® E | E ; | E;E – правила № 2 и 4
E® if B then E else E endif| if B then E endif| begin E end | do E while (B) | a := E – правила № 5–9
B ® B or B | B – правила № 10–11
B® B and B | B – правила № 12 и 13
B ® E < E | E > E | E = E | (E) | not (B)| B – правила № 14–19
E ® E – E | E + E | E * E| E / E | E – правила № 20–24
E ® (E) | a – правила № 25–26
3.3 Результаты
В результате выполнения программы построен синтаксический анализатор на основе грамматики операторного предшествования. Синтаксический анализ по¬зволяет проверять соответствие структуры исходного текста заданной граммати¬ке входного языка. А также синтаксический анализ позволяет обнаруживать любые син¬таксические ошибки во входной программе.
После обработки входного файла лексическим анализатором и построения таблицы лексем (рисунок 3), если не возникло лексических ошибок, строится дерево вывода (рис. 9).
Рис.9 Экранная форма дерева вывода
При наличии ошибки пользо¬вателю выдается сообщение (рис. 10).
Рис. 10 Экранная форма сообщения об ошибке в конструкции предложения
Заключение
В результате выполнения курсовой работы изучены и проанализированы два метода организации таблиц идентификаторов, и по результатам работы этих двух методов выбран метод хеш-адресации, так как операция поиска этим методом выполняется эффективнее, чем методом упорядоченного списка (бинарный поиск). А также для заданного входного языка написаны программы лексического и синтаксического анализатора. Результатом работы лексического анализатора является таблица лексем и и таблица идентификаторов. В случае обнаружения неверной лексемы лексический анализатор помещает ее в поле ошибочных лексем и продолжает дальнейшую работу, пока не будет достигнут конец файла. Данные, полученные в результате работы лексического анализатора, используются при синтаксическом анализе, то есть входной цепочкой символов для синтаксического анализатора будет информация взятая из таблицы лексем. Результатом работы синтаксического анализа является дерево вывода.
Список литературы
1. Молчанов А. Ю. Системное программное обеспечение. Лабораторный практикум. – Спб.: Питер, 2005. – 284 с.: ил.
2. Гордеев А. В. Молчанов Л. Ю. Системное программное обеспечение, – СПб.: Питер. 2002. – 734с.
3. Конспект лекций по системному программному обеспечению.
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, Grids, Math;
type
TAutoState = (AUTO_E,AUTO_H,AUTO_F1,AUTO_F2,AUTO_B1,AUTO_B2,AUTO_B3,AUTO_OR,AUTO_OR1,AUTO_IR,
AUTO_IR1,AUTO_IR2,AUTO_NR,AUTO_NR1,AUTO_NR2,AUTO_T,AUTO_I,AUTO_P1,AUTO_P2,AUTO_Z,AUTO_C,AUTO_D,
AUTO_DO,AUTO_DO1,AUTO_WH,AUTO_WH1,AUTO_WH2,AUTO_WH3,AUTO_WH4,
AUTO_BE,AUTO_BE1,AUTO_BE2,AUTO_BE3,AUTO_BE4,AUTO_EN,AUTO_EN1,AUTO_EN2,AUTO_EN3,AUTO_EN4,AUTO_EN5,
AUTO_PR,AUTO_PR1,AUTO_PR2,AUTO_PR3,AUTO_IF,AUTO_IF1,AUTO_TH,AUTO_TH1,
AUTO_EL1,AUTO_EL2,AUTO_EL3,AUTO_KO,AUTO_KO1,AUTO_KO2,AUTO_DEC);
TForm1 = class(TForm)
PageControl1: TPageControl;
TabSheet1: TTabSheet;
TabSheet2: TTabSheet;
Memo2: TMemo;
OpenDialog1: TOpenDialog;
StringGrid1: TStringGrid;
Button1: TButton;
Button4: TButton;
Label1: TLabel;
Memo1: TMemo;
Button2: TButton;
Memo3: TMemo;
Memo4: TMemo;
Memo5: TMemo;
Memo6: TMemo;
StringGrid2: TStringGrid;
StringGrid3: TStringGrid;
Button3: TButton;
Button5: TButton;
Edit1: TEdit;
Memo7: TMemo;
Button6: TButton;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Label6: TLabel;
Label7: TLabel;
GroupBox1: TGroupBox;
Label8: TLabel;
Label9: TLabel;
GroupBox2: TGroupBox;
Label12: TLabel;
Label15: TLabel;
Button7: TButton;
Memo8: TMemo;
TabSheet3: TTabSheet;
TreeView1: TTreeView;
Edit3: TEdit;
Button8: TButton;
Label10: TLabel;
Button9: TButton;
procedure FormCreate(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure Button6Click(Sender: TObject);
procedure Button7Click(Sender: TObject);
procedure Button8Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
ukazatel,vssrav,knop,knop1:integer;
srsrav,srsrav1,vssrav1: real;
inputString:TStringList;
end;
const
PredMatrix:array [1..26,1..26] of char=
( {pr end. ; if then els enf beg end do wle a := or and not < > = ( ) - + * / !}
{prog} ( ,=,<,<, , , ,<, ,<, ,<, , , , , , , , , , , , , , ),
{end.} ( , ,>, , , ,>, ,>, , ,>, , , , , , , , ,>, , , , ,>),
{;} ( ,>,>,<, , , ,<,>,<, ,<, , , , , , , , , , , , , , ),
{if} ( , , , ,=, , , , , , ,<, ,<,<,<,<,<,<,<, ,<,<,<,<, ),
{then} ( , , ,<, ,=,=,<, ,<, ,<, , , , , , , ,<, , , , , , ),
{else} ( , , ,<, , ,=,<, ,<, ,<, , , , , , , ,<, , , , , , ),
{endif}( ,>,>, , ,>,>, ,>,<,>, , , , , , , , , , , , , , , ),
{begin}( , ,<,<, , , ,<,=,<, ,<, , , , , , , , , , , , , , ),
{end} ( ,>,>, , ,>,>, ,>, , , , , , , , , , , , , , , , , ),
{do} ( , , ,<, , , ,<, ,<,=,<, , , , , , , , , , , , , , ),
{while}( ,>,>, , , ,>, ,>, , ,<, , , , , , , ,=, , , , , , ),
{a} ( ,>,>, ,>,>,>, ,>,>,>, ,=,>,>,>,>,>,>, ,>,>,>,>,>, ),
{:=} ( ,>,>, , ,>,>, ,>,>, ,<, , , , , , , ,<,>,<,<,<,<, ),
{or} ( , , , ,>, , , , , , ,<, ,>,<,<,<,<,<,<,>,<,<,<,<, ),
{and} ( , , , ,>, , , , , , ,<, ,>,<,<,<,<,<,<,>,<,<,<,<, ),
{not} ( , , , ,>, , , , , , ,<, ,>,<,<,<,<,<,<,>,<,<,<,<, ),
{<} ( , , , ,>, , , , , , ,<, ,>,<, , , , ,<,>,<,<,<,<, ),
{>} ( , , , ,>, , , , , , ,<, ,>,<, , , , ,<,>,<,<,<,<, ),
{=} ( , , , ,>, , , , , , ,<, ,>,<, , , , ,<,>,<,<,<,<, ),
{(} ( , , , , , , , , , , ,<, ,<,<,<,<,<,<,<,=,<,<,<,<, ),
{)} ( ,>,>, ,>,>,>, ,>,>,>, , ,>,>, ,>,>,>, ,>,>,>,>,>, ),
{-} ( ,>,>, ,>,>,>, ,>,>,>,<, ,>,>, ,>,>,>, ,>,>,>,>,>, ),
{+} ( ,>,>, ,>,>,>, ,>,>,>,<, ,>,>, ,>,>,>, ,>,>,>,>,>, ),
{*} ( ,>,>, ,>,>,>, ,>,>,>,<, ,>,>, ,>,>,>, ,>,>,>,>,>, ),
{/} ( ,>,>, ,>,>,>, ,>,>,>,<, ,>,>, ,>,>,>, ,>,>,>,>,>, ),
{!} (<, , , , , , , , , , , , , , , , , , , , , , , , , ));
{Îïèñàíèå ïðàâèë ãðàììàòèêè}
grammar:array [1..26] of string=
(progEend.,E,E;E,E;,ifBthenEelseEendif,ifBthenEendif,beginEend,doEwhile(E),a:=E,
BorB,B,BandB,B,notB,B,E<E,E>E,E=E,(B),E-E,E+E,E*E,E/E,E,(E),a);
term:array [1..26] of string=
(prog,end.,;,if,then,else,endif,begin,end,do,while,a,:=,or,and,not,<,>,=,(,),-,+,*,/,!);
notterm:array [1..26] of char=
(E,E,E,E,E,E,E,E,E,
B,B,B,B,B,B,B,B,B,B,
E,E,E,E,E,E,E);
CanonO:array [1..26,1..7] of string=
((prog,E,end.,,,,),
(E,,,,,,),
(E,;,E,,,,),
(E,;,,,,,),
(if,B,then,E,else,E,endif),
(if,B,then,E,endif,,),
(begin,E,end,,,,),
(do,E,while,(,B,),),
(a,:=,E,,,,),
(B,or,B,,,,),
(B,,,,,,),
(B,and,B,,,,),
(B,,,,,,),
(not,B,,,,,),
(B,,,,,,),
(E,<,E,,,,),
(E,>,E,,,,),
(E,=,E,,,,),
((,B,),,,,),
(E,-,E,,,,),
(E,+,E,,,,),
(E,*,E,,,,),
(E,/,E,,,,),
(E,,,,,,),
((,E,),,,,),
(a,,,,,,));
var
Form1: TForm1;
implementation
function IndMatrix(SymS:String):integer;
var i:integer;
begin
indMatrix:=0;
if term[1]=SymS then IndMatrix:=1;
for i:=1 to 26 do
if term[i]=SymS then IndMatrix:=i;
end;
function inArray(myS:String;A:Array of string;N:integer):boolean;
var i:integer;
begin
inArray:=False;
if myS=prog then inArray:=true;
for i:=1 to N do
if myS=A[i] then begin inArray:=true end;
end;
function NomRul(myS:String):integer;
var i:integer;
begin
NomRul:=0;
if (myS=grammar[1])then NomRul:=1;
for i:=1 to 26 do
if grammar[i]=myS then NomRul:=i;
end;
function findnt(myS:String):string;
begin
findnt:=;
findnt:=notterm[nomRul(myS)]
end;
{$R *.dfm}
function Hesh(St:string):integer;
var dlina:integer;
begin
dlina:=length(St);
if dlina=0 then Result:=0
else
begin
dlina:=length(St);
if dlina=0 then Result:=0 else
begin
if dlina=1 then
Result:=ord(St[1])
else
Result:=ord(St[1])+ord(St[2]);
end;
end;
end;
procedure TForm1.FormCreate(Sender: TObject);
var i:integer;
begin
Memo1.Text:=;
Memo2.Text:=;
StringGrid1.Cells[0,0]:=Íîìåð;
StringGrid1.Cells[1,0]:=Çíà÷åíèå;
StringGrid1.Cells[2,0]:=Ëåêñåìà;
srsrav:=0;
knop:=0;
vssrav:=0;
srsrav1:=0;
knop1:=0;
vssrav1:=0;
Edit1.Text:=;
Edit3.Text:=;
Memo3.Text:=;
Memo4.Text:=;
Memo5.Text:=;
Memo6.Text:=;
Memo7.Text:=;
Memo8.Text:=;
StringGrid2.Cells[0,0]:=ÕÔ;
StringGrid2.Cells[1,0]:=Èäåí-ð;
StringGrid3.Cells[0,0]:=Íîìåð;
StringGrid3.Cells[1,0]:=Èäåí-ð;
for i:=1 to 510 do
begin
StringGrid3.Cells[0,i]:=IntToStr(i);
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
Const N1=26;
N2=21;
N3=26;
N4=5;
var ind,dl,i,j,fl,zn,jkj,fll:integer;
st,str,sInput:string;
iState:TAutoState;
label 1,2,M1,M2,Myend,zap,tree;
begin
fll:=0;
inputString:=TStringList.Create;
inputString.Sorted:=False;
if OpenDialog1.Execute then Memo1.Lines.LoadFromFile(OpenDialog1.FileName) ;
for i:=0 to 2 do
for j:=1 to 999 do
StringGrid1.Cells[i,j]:= ;
j:=Memo1.Lines.Count;
ind:=1;
for i:=1 to j do
begin
str:=;
sInput:=Memo1.Lines[i-1];
sInput:=sInput+ ;
dl:=Length(sInput);
iState:=AUTO_H;
fl:=0;
zn:=0;
for jkj:=1 to dl do
begin
st:=sInput[jkj];
case iState of
AUTO_H:
case sInput[jkj] of
: begin iState:=AUTO_KO;str:=str+st;end;
(: begin iState:=AUTO_F1;str:=str+st; end;
): begin iState:=AUTO_F2;str:=str+st; end;
;: begin iState:=AUTO_T;str:=str+st; end;
o: begin iState:=AUTO_OR;str:=str+st; end;
a: begin iState:=AUTO_IR;str:=str+st; end;
n: begin iState:=AUTO_NR;str:=str+st; end;
d: begin iState:=AUTO_DO;str:=str+st; end;
w: begin iState:=AUTO_WH;str:=str+st; end;
b: begin iState:=AUTO_BE;str:=str+st; end;
e: begin iState:=AUTO_EN;str:=str+st; end;
p: begin iState:=AUTO_PR;str:=str+st; end;
i: begin iState:=AUTO_IF;str:=str+st; end;
t: begin iState:=AUTO_TH;str:=str+st; end;
c,f..h,j..m,q..s,u,v,x..z: begin iState:=AUTO_I;str:=str+st; end;
:: begin iState:=AUTO_P1;str:=str+st; end;
+,-,*,/:begin iState:=AUTO_Z;str:=str+st; end;
>: begin iState:=AUTO_B1;str:=str+st; end;
<: begin iState:=AUTO_B2;str:=str+st; end;
=: begin iState:=AUTO_B3;str:=str+st; end;
2..9: begin iState:=AUTO_E;str:=str+st; end;
0,1: begin iState:=AUTO_D;str:=str+st; end;
: begin iState:=AUTO_H;str:=;end;
else begin iState:= AUTO_E;str:=str+st; end;
end;
AUTO_KO:
case sInput[jkj] of
*:begin iState:=AUTO_KO1;str:=str+st;fll:=1; end;
else begin iState:=AUTO_E;end;
end;
AUTO_KO1:
case sInput[jkj] of
*:begin iState:=AUTO_KO2;str:=str+st; end;
else begin iState:=AUTO_KO1;end;
end;
AUTO_KO2:
case sInput[jkj] of
:begin iState:=AUTO_H;fll:=0;end;
else begin iState:=AUTO_KO1;end;
end;
AUTO_TH:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
h: begin iState:=AUTO_TH1;str:=str+st;end;
a..g,i..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_TH1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
e: begin iState:=AUTO_BE3;str:=str+st;end;
a..d,f..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_IF:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
f: begin iState:=AUTO_IF1;str:=str+st;end;
a..e,g..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_IF1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_PR:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
r: begin iState:=AUTO_PR1;str:=str+st;end;
a..q,s..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_PR1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
o: begin iState:=AUTO_PR2;str:=str+st;end;
a..n,p..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_PR2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
g: begin iState:=AUTO_PR3;str:=str+st;end;
a..f,h..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_PR3:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_EN:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
n: begin iState:=AUTO_EN1;str:=str+st;end;
l: begin iState:=AUTO_EL1;str:=str+st;end;
a..k,m,o..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_EN1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
d: begin iState:=AUTO_EN2;str:=str+st;end;
a..c,e..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_EN2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
.: begin iState:=AUTO_EN3;str:=str+st;end;
i: begin iState:=AUTO_EN4;str:=str+st;end;
a..h,j..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_EN3:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_EN4:
case sInput[jkj] of
f: begin iState:=AUTO_EN5;str:=str+st;end;
a..e,g..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_EN5:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_EL1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
s: begin iState:=AUTO_EL2;str:=str+st;end;
a..r,t..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_EL2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
e: begin iState:=AUTO_EL3;str:=str+st;end;
a..d,f..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_EL3:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_BE:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
e: begin iState:=AUTO_BE1;str:=str+st;end;
a..d,f..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_BE1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
g: begin iState:=AUTO_BE2;str:=str+st;end;
a..f,h..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_BE2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
i: begin iState:=AUTO_BE3;str:=str+st;end;
a..h,j..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_BE3:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
n: begin iState:=AUTO_BE4;str:=str+st;end;
a..m,o..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_BE4:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_WH:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
h: begin iState:=AUTO_WH1;str:=str+st;end;
a..g,i..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_WH1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
i: begin iState:=AUTO_WH2;str:=str+st;end;
a..h,j..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_WH2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
l: begin iState:=AUTO_WH3;str:=str+st;end;
a..k,m..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_WH3:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
e: begin iState:=AUTO_WH4;str:=str+st;end;
a..d,f..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_WH4:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_DO:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
o: begin iState:=AUTO_DO1;str:=str+st;end;
a..n,p..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_DO1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=15;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_NR:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
o: begin iState:=AUTO_NR1;str:=str+st;end;
a..n,p..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_NR1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
t: begin iState:=AUTO_NR2;str:=str+st;end;
a..s,u..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_NR2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=14;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_IR:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
n: begin iState:=AUTO_IR1;str:=str+st;end;
a..m,o..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_IR1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
d: begin iState:=AUTO_IR2;str:=str+st;end;
a..c,e..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_IR2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=13;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_OR:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
r: begin iState:=AUTO_OR1;str:=str+st;end;
a..q,s..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_OR1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=12;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_B1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=9;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_B2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=10;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_B3:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=11;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_F1:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=1;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_F2:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=7;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_T:
case sInput[jkj] of
:begin iState:=AUTO_H;fl:=1;zn:=8; end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_I:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=2;end;
a..z,0..9:begin iState:=AUTO_I;str:=str+st; end;
else begin iState:=AUTO_E; str:=str+st; end;
end;
AUTO_P1:
case sInput[jkj] of
=:begin iState:=AUTO_P2;str:=str+st;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_P2:
case sInput[jkj] of
:begin iState:=AUTO_H;fl:=1;zn:=3;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_Z:
case sInput[jkj] of
: begin iState:=AUTO_H;fl:=1;zn:=4;end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_D:
case sInput[jkj] of
:begin iState:=AUTO_H;fl:=1;zn:=16;end;
0,1: begin iState:=AUTO_D;str:=str+st; end;
else begin iState:=AUTO_E;str:=str+st; end;
end;
AUTO_E: begin
if sInput[jkj]<> then
begin
iState:=AUTO_E;
str:=str+st;
end
else
begin
iState:=AUTO_H;
Memo8.Lines.Append(str);
str:=;
end;
end;
end;
if fll=0 then
if fl=1 then
begin
StringGrid1.Cells[0,ind]:=IntToStr(ind);
StringGrid1.Cells[1,ind]:=str;
case zn of
1: begin StringGrid1.Cells[2,ind]:=Îòêðûâàþùàÿñÿ ñêîáêà;inputString.Add(();end;
2: begin StringGrid1.Cells[2,ind]:=Ïåðåìåííàÿ;inputString.Add(a);end;
3: begin StringGrid1.Cells[2,ind]:=Îïåðàòîð ïðèñâàèâàíèÿ;inputString.Add(:=);end;
4: begin StringGrid1.Cells[2,ind]:=Àðèôìåòè÷åñêàÿ îïåðàöèÿ;inputString.Add(StringGrid1.Cells[1,ind]); end;
7: begin StringGrid1.Cells[2,ind]:=Çàêðûâàþùàÿñÿ ñêîáêà;inputString.Add());end;
8: begin StringGrid1.Cells[2,ind]:=Ðàçäåëèòåëü;inputString.Add(;);end;
9: begin StringGrid1.Cells[2,ind]:=Îïåðàâòîð ñðàâíåíèÿ "áîëüøå";inputString.Add(>);end;
10: begin StringGrid1.Cells[2,ind]:=Îïåðàâòîð ñðàâíåíèÿ "ìåíüøå";inputString.Add(<);end;
11: begin StringGrid1.Cells[2,ind]:=Îïåðàâòîð ñðàâíåíèÿ "ðàâíî";inputString.Add(=);end;
12: begin StringGrid1.Cells[2,ind]:=Ëîãè÷åñêîå "èëè";inputString.Add(or);end;
13: begin StringGrid1.Cells[2,ind]:=Ëîãè÷åñêîå "è";inputString.Add(and);end;
14: begin StringGrid1.Cells[2,ind]:=Ëîãè÷åñêîå "íå";inputString.Add(not);end;
15: begin StringGrid1.Cells[2,ind]:=Êëþ÷åâîå ñëîâî;inputString.Add(StringGrid1.Cells[1,ind]);end;
16: begin StringGrid1.Cells[2,ind]:=Äâîè÷íàÿ êîíñòàíòà;inputString.Add(a);end;
end;
str:=;
ind:=ind+1;
fl:=0;
end;
end;
end;
if fll=1 then
begin ShowMessage(Íå çàêðûò êîìåíòàðèé!!!)
end ;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
close;
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
close;
end;
procedure TForm1.Button3Click(Sender: TObject);
var i,k,dlina,hash,j,kol:integer;
stroka:string;
a:string;
max1,lk,li,min,max,p,lj,sr,lf:integer;
label 1,2;
begin
for i:=1 to 510 do
begin
StringGrid2.Cells[0,i]:=IntToStr(i);
end;
j:=0;
k:=2;
kol:=0;
ukazatel:=0;
dlina:=memo3.Lines.Count;
if dlina<>0 then
begin
for i:=0 to dlina-1 do
begin
stroka:=memo3.Lines[i];
hash:=Hesh(stroka);
if (StringGrid2.cells[1,hash])= then
begin
StringGrid2.cells[1,hash]:=stroka;
end
else
begin
1: if (StringGrid2.cells[1,hash])=stroka then
begin
memo4.Lines[j]:=Óäàëåí ïîâòîð +stroka;
j:=j+1;
ukazatel:=ukazatel+1;
goto 2;
end
else
begin
kol:=kol+1;
hash:=(Hesh(stroka)*k) mod 509;
if (StringGrid2.cells[1,hash])= then
begin
StringGrid2.cells[1,hash]:=stroka;
end
else
begin
k:=k+1;
goto 1;
end;
end;
end;
2: end;
end;
Label8.Caption:=Êîë-âî êîëëèçèé +inttostr(kol);
for li:=1 to 510 do
begin
StringGrid3.Cells[1,li]:=;
end;
lk:=0;
p:=Memo3.Lines.Count;
if p>=1 then
begin
StringGrid3.Cells[1,1]:=Memo3.Lines[0];
memo6.Lines[0]:=Memo3.Lines[0];
end;
for li:=1 to p-1 do
begin
lf:=0;
min:=0;
max:=510;
a:=Memo3.Lines[li];
while max-min<>1 do
begin
sr:=(max+min) div 2;
if StringGrid3.Cells[1,sr]=a then
begin
Memo4.Lines[lk]:=Óäàëåí ïîâòîð +a;
lk:=lk+1;
lf:=1;
break;
end
else
if (StringGrid3.Cells[1,sr]>a) or (StringGrid3.Cells[1,sr]=) then
max:=sr
else
min:=sr;
end;
lj:=509;
if lf=0 then
begin while lj>min do
begin
StringGrid3.Cells[1,lj+1]:=StringGrid3.Cells[1,lj];
lj:=lj-1;
end;
StringGrid3.Cells[1,max]:=a;
memo6.Lines.Append(a)
end;
end;
while (StringGrid3.Cells[1,max1]<>) do
begin
max1:=max1+1;
end;
end;
procedure TForm1.Button5Click(Sender: TObject);
var max1,k,hash,dlina,i,srav,j,si: integer;
stroka: string;
min,max,sr,sravn:integer;
a:string;
label met1,met2,met3;
begin
memo5.Lines[0]:=;
memo7.Lines[0]:=;
k:=2;
srav:=0;
stroka:=Edit1.Text;
if stroka= then
begin
memo5.Lines[0]:=Ïîëå ïóñòî!;
memo7.Lines[0]:=Ïîëå ïóñòî!;
goto met3;
end;
hash:=Hesh(stroka);
for i:=1 to 510 do
begin
srav:=srav+1;
if StringGrid2.Cells[0,hash]=IntToStr(hash) then
begin
if stroka=StringGrid2.Cells[1,hash] then
begin
memo5.Lines[0]:=Èäåí-ð +stroka+ íàéäåí! Åãî íîìåð + IntToStr(hash);
goto met1;
end
else
begin
for j:=1 to 510 do
begin
srav:=srav+1;
hash:=(Hesh(stroka)*k) mod 509;
k:=k+1;
if StringGrid2.Cells[0,hash]=IntToStr(hash) then
begin
if stroka=StringGrid2.Cells[1,hash] then
begin
memo5.Lines[0]:=Èäåí-ð +stroka+ íàéäåí! Åãî íîìåð + IntToStr(hash);
goto met1;
end;
end
else memo5.Lines[0]:=Èäåí-ð +stroka+ íå íàéäåí!;
end;
end;
end
else begin
memo5.Lines[0]:=Èäåí-ð +stroka+ íå íàéäåí!;
goto met1; end;
end;
met1: Label9.Caption:=Êîë-âî ñðàâíåíèé +inttostr(srav);
dlina:=memo6.Lines.Count;
for si:=1 to dlina do
begin
k:=2;
srav:=0;
stroka:=memo6.Lines[si-1];
hash:=Hesh(stroka);
for i:=1 to 510 do
begin
srav:=srav+1;
if StringGrid2.Cells[0,hash]=IntToStr(hash) then
begin
if stroka=StringGrid2.Cells[1,hash] then
begin
goto met2;
end
else
begin
for j:=1 to 510 do
begin
srav:=srav+1;
hash:=(Hesh(stroka)*k) mod 509;
k:=k+1;
if StringGrid2.Cells[0,hash]=IntToStr(hash) then
begin
if StringGrid2.Cells[1,hash]=stroka then
begin
goto met2;
end;
end;
end;
end;
end
else
goto met2;
end;
met2: vssrav:=vssrav+srav;
end;
srsrav:=vssrav/dlina;
vssrav:=0;
srsrav:=0;
knop1:=knop1+1;
sravn:=0;
max1:=1;
dlina:=Memo6.Lines.Count;
while (StringGrid3.Cells[1,max1]<>) do
begin
max1:=max1+1;
end;
for i:=1 to 10 do
begin
min:=0;
max:=max1;
a:=Edit1.Text;
while (StringGrid3.Cells[1,sr]<>a) and (max-min<>1) do
begin
sravn:=sravn+1;
sr:=(max+min) div 2;
if (StringGrid3.Cells[1,sr]>a) or (StringGrid3.Cells[1,sr]=) then
begin
max:=sr;
end
else
begin
min:=sr;
end;
end;
end;
if StringGrid3.Cells[1,sr]=a then
Memo7.Lines[0]:=Èäåí-ð +a+ íàéäåí! Åãî íîìåð + IntToStr(sr)
else Memo7.Lines[0]:=Èäåí-ð +a+ íå íàéäåí!;
dlina:=dlina-(dlina-max1);
srsrav1:=1+log2(dlina);
Label12.Caption:=Êîë-âî ñðàâíåíèé +inttostr(sravn);
met3: end;
procedure TForm1.Button6Click(Sender: TObject);
var i: integer;
begin
for i:=1 to 510 do StringGrid2.Cells[1,i]:=;
for i:=1 to 510 do StringGrid2.Cells[2,i]:=;
for i:=1 to 510 do StringGrid3.Cells[1,i]:=;
for i:=0 to Memo6.Lines.Count-1 do Memo6.Text:=;
for i:=0 to Memo3.Lines.Count-1 do Memo3.Text:=;
for i:=0 to Memo4.Lines.Count-1 do Memo4.Text:=;
for i:=0 to Memo5.Lines.Count-1 do Memo5.Text:=;
for i:=0 to Memo7.Lines.Count-1 do Memo7.Text:=;
Label8.Caption:=Êîë-âî êîëëèçèé;
Label9.Caption:=Êîë-âî ñðàâíåíèé;
Label12.Caption:=Êîë-âî ñðàâíåíèé;
Edit1.Text:=;
end;
procedure TForm1.Button7Click(Sender: TObject);
begin
if OpenDialog1.Execute then Memo3.Lines.LoadFromFile(OpenDialog1.FileName) ;
end;
procedure TForm1.Button8Click(Sender: TObject);
label Myend,zap,tree;
var SymbStack:TStringList;{âõîäíàÿ ñòðîêà è ñòýê ñîîòâåòñòâåííî}
i,j,verh,k,vetv,n,m:integer;
gamma,MyinS,syms,tek,cep:String;
mycase:char;
CepofV:array [1..100]of integer;
begin
TTreeView(TreeView1).Items.Clear;
for i:=0 to inputString.Count-1 do MyinS:=MyinS+InputString[i];
if inputString.Count=0 then
begin
ShowMessage(Òàáëèöà ëåêñåì èëè èñõîäíûé ôàéë íå çàãðóæåíû);
exit
end;
inputString.Add(!);
{Îáúÿâëÿåì ñòýê}
SymbStack:=TStringList.Create;
SymbStack.Sorted:=False;
SymbStack.Add(!);
i:=0;
k:=0;
cep:=;
while i<=inputString.Count-1 do
begin
verh:=SymbStack.Count-1;
syms:=SymbStack[verh];
while (not(inArray(SymbStack[verh],term,26))) do verh:=verh-1;
if (SymbStack[verh]=!) and (inputString[i]=!) then goto MyEnd;
mycase:=PredMatrix[IndMatrix(SymbStack[verh]),IndMatrix(inputString[i])];
if ((mycase=<)or(mycase==))then
begin {ñäâèã}
SymbStack.Add(inputString[i]);
i:=i+1;
end
else
if (mycase=>)
then
begin {ñâåðòêà}
gamma:=;
tek:=;
for j:=SymbStack.Count-1 downto 0 do
if not(inArray(SymbStack[j],term,26)) then
begin
gamma:=SymbStack[j]+gamma;
SymbStack.Delete(j)
end
else
if (inArray(SymbStack[j],term,26))and(tek=) then
begin
tek:=SymbStack[j];
gamma:=SymbStack[j]+gamma;
SymbStack.Delete(j)
end
else
if predMatrix[Indmatrix(SymbStack[j]),IndMatrix(tek)]== then
begin
tek:=SymbStack[j];
gamma:=SymbStack[j]+gamma;
SymbStack.Delete(j)
end
else break;
if findnt(gamma)<>
then
begin
SymbStack.Add(findnt(gamma));
k:=k+1;
CepofV[k]:=NomRul(gamma);
cep:=inttostr(CepofV[k])+ +cep;
end
else
begin {îøèáêà}
ShowMessage(Îøèáêà! Öåïî÷êà +gamma+ íåäîïóñòèìà);
goto tree
end;
end;
if mycase= then
begin {îøèáêà}
ShowMessage(Îøèáêà! Ñèìâîëû +Symbstack[verh]+ è +InputString[i]+ íå ìîãóò ñëåäîâàòü äðóã çà äðóãîì);
goto tree;
end;
end;
Myend:Edit3.Text:=cep;
{âûâîä äåðåâà}
tree:n:=k;
with TreeView1 do
begin
Items.Add(Nil,E);
vetv:=0;
for k:=n downto 1 do begin
m:=Items.Count;
if k<n then
for i:=m-1 downto 0 do
if Items[i].Text=notterm[CepofV[k]] then
if Items[i].HasChildren=False then
begin
vetv:=i;
goto zap
end;
zap: for i:=1 to 7 do
if CanonO[CepofV[k],i]<> then
Items.AddChild(Items[vetv],CanonO[CepofV[k],i])
end;
FullExpand
end;
end;
end.
Фрагмент графа переходов КА для пробела, разделяющего знака, комментариев, операторов сравнения “<”, “>” и “=” представлен на рис. 1.
Рис.1. Фрагмент графа переходов КА операций сравнения, комментарий, разделяющего знака.
Фрагмент графа переходов КА для круглых открывающихся и закрывающихся скобок, знаков присваивания, сложения, вычитания, умножения и деления представлен на рис.2.
Рис.2. Фрагмент графа переходов КА для скобок, разделяющего знака
и знаков присваивания, сложения, вычитания, умножения и деления
Фрагмент графа переходов КА для идентификатора, операторов сравнения “not”, “and” представлен на рис.3.
Рис.3. Фрагмент графа переходов КА идентификатора и операторов сравнения “not”, “and”
Фрагмент графа переходов КА для оператора сравнения “or”, целых чисел и двоичной константы представлен на рис.4.
Рис.4. Фрагмент графа переходов КА для оператора сравнения “or”, целых чисел и двоичной константы.
Фрагмент графа переходов КА операторов цикла “do” и “while” представлен на рис.5.
Рис.5. Фрагмент графа переходов КА для операторов цикла “do” и “while”.
Фрагмент графа переходов КА для служебных слов “begin” и “prog” представлен на рис.6.
Рис.6. Фрагмент графа переходов КА для служебных слов “begin” и “prog”.
Фрагмент графа переходов КА для служебных слов “end”, “end.”, “endif” и “else” представлен на рис.7.
Рис.7. Фрагмент графа переходов КА для служебных слов “end”, “end.”, “endif” и “else”.
Фрагмент графа переходов КА служебных слов “then” и “if” представлен на рис.8.
Рис.8. Фрагмент графа переходов КА для служебных слов “then” и “if”.
Разработка отдельных фаз компиляции для заданного входного языка
Курсовая работа по предмету «Программирование»