close

Вход

Забыли?

вход по аккаунту

?

SPO PZ

код для вставкиСкачать
 Введение
Ни для кого не секрет, что компьютер понимает только свой собственный, машинный язык. Язык Ассемблер - язык программирования низкого уровня, наиболее приближен к машинному коду и понятен для человека. Кроме Ассемблера существует множество языков программирования высокого уровня. Перевод команд с языков низкого и высокого уровня в машинный язык, понятный компьютеру, осуществляет компилятор. Компилятор - программа, предназначенная для трансляции высокоуровневого языка в абсолютный код или, иногда, в язык ассемблера. Входной информацией для компилятора (исходный код) является описание алгоритма или программа на проблемно-ориентированном языке, а на выходе компилятора - эквивалентное описание алгоритма на машинно-ориентированном языке (объектный код).
Курсовая работа заключается в создании компилятора с заданного подмножества языка Pascal с незначительными модификациями и упрощениями. Целью данной курсовой работы является изучение составных частей, основных принципов построения и функционирования компилятора, практическое освоение методов построения составных частей компилятора для заданного входного языка.
Процесс компиляции в данной курсовой работе состоит из следующих этапов:
* Лексический анализ. На этом этапе последовательность символов исходного файла преобразуется в последовательность лексем.
* Синтаксический (грамматический) анализ. Последовательность лексем преобразуется в дерево разбора.
* Оптимизация. Выполняется удаление излишних конструкций и упрощение кода с сохранением его смысла.
* Генерация кода. Из промежуточного представления порождается код на целевом языке (язык Ассемблер).
Для реализации данной курсовой работы используется среда программирования Borland Delphi 7 и язык программирования Object Pascal.
1. Грамматика входного языка
Язык - заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого языка является алфавит, определяющий набор допустимых символов языка. Для языков программирования алфавит - это чаще всего набор символов, которые можно ввести с клавиатуры. Для реализации компилятора необходимо задать язык. Язык можно задать тремя способами:
* Перечислением всех допустимых цепочек языка.
* Указанием способа порождения цепочек языка (задание грамматики языка).
* Определением метода распознавания цепочек языка.
Второй способ предусматривает описание правил, с помощью которого строятся цепочки языка. Этот способ подходит для описания входного языка.
Грамматика - описание способа построения предложений некоторого языка. Определив грамматику языка, можно получить правила порождения цепочек символов, принадлежащих этому языку. Язык, заданный грамматикой G, определяется как L(G).
Формально грамматика G определяется как четверка G(VT, VN, P, S), где:
* VT - множество терминальных символов;
* VN - множество нетерминальных символов: ;
* P - множество правил (продукций) грамматики вида ;
* S - целевой (начальный) символ грамматики .
Множество называют полным алфавитом грамматики G. Множество терминальных символов VT содержит символы, которые входят в алфавит языка, порождаемого грамматикой. Множество нетерминальных символов VN содержит символы, которые определяют слова, понятия, конструкции языка. Контекстно-свободная грамматика в форме Бэкуса-Наура:
G ({ prog, end., if, then, else, begin, end, while, do, and, or, not, =, <, >,<>, (, ), {, }, -, +, *, /, a, c, ;, :=}, {S, L, O, B, C, K, D, H, E, F},P, S)
P:
S → prog L end.
L → O | L ; O | L ;
O → if B then O else O| if B then O| begin L end| do O while (B) | a:=E
B → B or C | C
C → C and D | D
D → not D | H
H → E < E | E > E | E = E |E<>E| (B)
E → E - T | E + T | E * T | E / T | T
F → (E) | a | c
Нетерминальные символы грамматики имеют следующий смысл:
* S - вся программа,
* L - последовательность операторов(может состоять из одного оператора),
* O - оператор,
* B, C, D - логическое выражение и его элементы,
* H - операции сравнения или логические выражения в скобках,
* E,F - арифметические выражения и его элементы,
* a - переменная (A..Z, a..z, 2..9),
* с - константа (0..1).
Всего в построенной грамматике G 27 правил.
2. Организация таблиц идентификаторов
Для работы компилятор должен оперировать характеристиками основных элементов исходной программы - переменных, констант, функций и других лексических единиц входного языка. У всех лексических единиц есть уникальное имя и компилятор должен уметь анализировать элементы по их именам. Задача компилятора заключается в том, чтобы хранить некоторую информацию, связанную с каждым элементом исходной программы, и иметь доступ к этой информации по имени элемента. Для решения этой задачи компилятор организует специальные хранилища данных, называемые таблицами идентификаторов. Для организации таблиц идентификаторов можно использовать разные способы: от простейших - в виде списков, до сложных хэш-функций. В данной курсовой работе используется комбинированный способ - комбинация хеш-адресации и бинарного дерева. Такой способ достаточно эффективен и не требует разработки сложной хэш-функции.
3. Лексический анализатор
Задача лексического анализатора - распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами входного языка являются:
* Ключевые слова (prog, end., if, then, else, begin, end, do, while, end, not, or, and);
* Разделители (круглые скобки и точка с запятой);
* Знаки операций (присваивание, сравнения, сложение, вычитание, умножение и деление);
* Идентификаторы;
* Константы и переменные;
* Комментарии.
Так как в данном языке лексический анализатор всегда может однозначно определить границы лексемы, то нет необходимости в его взаимодействии с синтаксическим анализатором.
На рисунке 1 изображен граф переходов конечного автомата без учета ключевых слов. Граф выполнен в программе JFLAP, предназначенной для рисования и анализа конечных автоматов.
Условные обозначения:
А - любой алфавитно-цифровой символ;
А(*) - любой алфавитно-цифровой символ, кроме перечисленных в скобках;
П - любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки);
Б - любая буква английского алфавита или символ подчеркивания;
Б - любая буква английского алфавита или символ подчеркивания, кроме перечисленных в скобках;
Ц - любая цифра от 0 до 9;
Рисунок 1 - Граф переходов конечного автомата
F - функция обработки таблицы лексем, вызываема при переходе КА из одного состояния в другое; Обозначения ее аргументов:
* v - переменная, запомненная при работе КА;
* d - константа, запомненная при работе КА;
* a - текущий входной символ КА.
4. Синтаксический анализатор
В основе синтаксического анализатора лежит распознаватель текста исходной программы, построенный на основе грамматики входного языка. Вообще, синтаксический анализатор - это часть компилятора, которая отвечает за выявление и проверку синтаксических конструкций входного языка. В задачу синтаксического анализатора входит:
* Найти и выделить синтаксические конструкции в тексте исходной программы;
* Установить тип и проверить правильность каждой синтаксической конструкции;
* Представить синтаксические конструкции в виде, удобном для дальнейшей генерации текста результирующей программы.
Для построения синтаксического анализатора используется анализатор на основе грамматик операторного предшествования. Этот анализатор является линейным распознавателем (время анализа линейно зависит от длины входной цепочки). Для построения анализатора на основе грамматики операторного предшествования необходимо построить матрицу операторного предшествования. Таблица 1 - Множества крайних левых и правых символов
Символ UL(U)R(U)Sprogend.LL, OO,E, F, ), a, c, end, ;O if, begin, do, aO,E, F, ), a, c, endBB, C, D, (, E, F, a, cC,D, H, E, F, ), a, cCC, D, not, (,E,F, a, cD, H, E, F, ), a, cD (, not, E, F, a, cH, E, F, ), a, cHE, F, (, a, cE, F, ), a, cEE, F, (, a, cF, ), a, cF(, a, c), a, c Таблица 2 - Множества крайних левых и правых терминальных символов
ULt(U)Rt(U)Sprogend.L;, if, begin, do, a;, else, then, end, while, :=, -, +, ), /, *, a, cOif, begin, do, aelse, then, end, while, :=, -, +, /, *, ), a, cBor, and, not, <, >, =, (, -, +, /, *, a, cor, and, <, >, =, ), -, +, /, *, a, cCand, not, <, >, =, (, -, +, /, *, a, cand, <, >, =, ), -, +, /, *, a, cDnot, <, >,<>, =, (, -, +, /, *, a, c <, >, =,<>, ), -, +, /, *, a, cH <, >,<>, =, (, -, +, /, *, a, c<, >,<>, =, ), -, +, /, *, a, cE(, -, +, /, *, a, c), -, +, /, *, a, cF(, a, c), a, c С помощью полученных множеств терминальных символов построена матрица предшествования. Результат представлен в таблице 3.
Отношения предшествования обозначаются знаками "=", "<", ">".Отношение предшествования между двумя соседними символами распознаваемой строки соответствует трем следующим вариантам:
* Bi < Bi+1, если символ Bi+1 - крайний левый символ некоторой основы (это отношение между символами можно назвать "предшествует основе");
* Bi > Bi+1, если символ Bi - крайний правый символ некоторой основы (это отношение между символами можно назвать "следует за основой");
* Bi = Bi+1, если символы Bi и Bi+1 принадлежат основе (это отношение между символами можно назвать "составляют основу").
Таблица 3 - Матрица предшествования
Остовная грамматика имеет вид:
G' ({ prog, end., if, then, else, begin, end, do, while, and, or, not, =, <, >,<>, (, ), -, +, *, /, a, c, ;, :=}, {E}, P', S)
P':
E → program E end.
E → E | E ; E | E ;
E → if E then E else E| if E then E| begin E end| do E while (E)| a:=E
E → E or E | E
E → E and E | E
E → not E | E
E → E < E | E > E | E = E | E <>= E| (E) E → E - E | E + E | E * E | E / E | E
E → (E) | a | c
Преобразованная остовная грамматика:
G' ({ prog, end., if, then, else, begin, end, do, while, and, or, not, =, <, >,<>, (, ), -, +, *, /, a, c, ;, :=}, {E}, P', S)
E → program E end.
E → E | E ; E | E ;
E → if B then E else E | if B then E | begin E end | do E while (E)| E
E → a:=E
B → B or B | B
B → B and B | B
B → not B | B
B → E < E | E > E | E = E| E <> E | (B) E → E - E | E + E | E * E | E / E | E
E → (E) | a | c
На выходе синтаксического анализатора будет дерево синтаксического разбора.
5. Порождение результирующего кода
Для порождения результирующего кода используется рекурсивный алгоритм порождения списка триад на основе дерева синтаксического разбора.
Генерация объектного кода - перевод компилятором внутреннего представления исходной программы в цепочку символов выходного языка. Для того, чтобы компилятор мог построить код результирующей программы для синтаксической конструкции входного языка, используется метод, который называется синтаксически управляемым переводом. Основная идея СУ-перевода заключается в том, что каждому правилу входного языка компилятора сопоставляется одно или несколько (или ни одного) правил входного языка в соответствии с семантикой входных и выходных правил.
Внутреннее представление программы - в форме триад (многоадресный код с неявно именуемым результатом).
Триады представляют собой запись операций в форме из трех составляющих: операция и два операнда. Особенность триад является то, что один или оба операнда могут быть ссылкой на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно нумеруют для удобства указания ссылок одних триад на другие. 6. Оптимизация объектного кода
Оптимизация программы - это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы. Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода.
В курсовой работе использован такой вид оптимизирующих преобразований как исключение избыточных операций.
Исключение избыточных вычислений заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды.
Операция линейного участка с порядковым номером i считается лишней операцией, если существует идентичная ей операция с порядковым номером j, j<i и никакой операнд, обрабатываемый операцией с порядковым номером i, не изменялся никакой другой операцией, имеющей порядковый номер между i и j.
Общий алгоритм генерации и оптимизации объектного кода имеет вид:
* Построить последовательность триад на основе дерева вывода;
* Выполнить оптимизацию кода методом исключения лишних операций для линейных участков результирующей программы;
* Преобразовать последовательность триад в последовательность команд на языке ассемблера.
7. Организация компилятора
Рисунок 2 - Общий вид компилятора
Генератор ассемблерного кода ориентирован на процессоры Intel 80386 и более поздних модификаций в защищенном режиме работы. В этом режиме в процессоре доступно шесть регистров общего назначения по 32 бит каждый: eax, ebx, ecx, edx, esi, edi.
Входная программа имеет вид:
prog
D:=010;
B:=001;
C:=100;
A:=C + InpVar;
D:=C+B+010;
C:=A * B / C;
G:=((C) +(A*B)) - (InpVar + 1) + (A + B);
E:=(G - 22) - (A + B);
CompileTest := 0;
if (a<b or a<c and( e=0 and(d=0
and (b<c or (a<c and (c<>e or not(b=0)))))))
a:=0 else a:=1;
if (InpVar > 0 or 1 <> InpVar) do begin
a:=a+(b+1) end;
while (a<1) else CompileTest := InpVar+1;
end.
Полный текст модулей компилятора в приложении А.
Заключение
В процессе реализации данной курсовой работы был создан компилятор, который производит преобразование кода исходной программы с заданного подмножества языка Pascal на язык Ассемблер.
Данный компилятор способен обрабатывать входной язык согласно заданию. Операции, которые не присутствуют в задании, компилятор распознает как синтаксическую ошибку.
Так же компилятор в состоянии производить оптимизацию объектного кода методом исключения лишних операций, что позволяет сократить объем результирующего ассемблерного кода.
Компилятор выполняет обработку исходной программы за 5 проходов:
* Лексический анализ исходного текста и построение таблицы лексем.
* Синтаксический анализ по таблице лексем и построение дерева синтаксического разбора.
* Построение списка триад по дереву синтаксического разбора.
* Оптимизация списка триад методом исключения лишних операций.
* Построение результирующего ассемблерного кода по списку триад.
На каждом проходе компилятора исходными данными являются результаты, полученные при выполнении предыдущего прохода.
Построенный компилятор хорошо показывает технику и методы, лежащие в основе построения компиляторов.
Список литературы
1. Системное программное обеспечение: Лабораторный практикум / А.Ю. Молчанов - СПб.: Питер, 2005. -284с.
2. Системное программное обеспечение/ А.В.Гордеев, А.Ю.Молчанов - СПб.: Питер, 2003. -736с. 3. Assembler: Учебник для вузов / В.И.Юров - СПб.: Питер, 2003. - 637с.
Приложение А
program Cursov;
uses
Forms,
FormLab4 in 'FormLab4.pas' {CursovForm},
FncTree in 'FncTree.pas',
Triads in 'Triads.pas',
TblElem in 'TblElem.pas',
LexType in 'LexType.pas',
LexElem in 'LexElem.pas',
LexAuto in 'LexAuto.pas',
SyntRule in 'SyntRule.pas',
SyntSymb in 'SyntSymb.pas',
TrdType in 'TrdType.pas',
TrdMake in 'TrdMake.pas',
TrdCalc in 'TrdCalc.pas',
TrdAsm in 'TrdAsm.pas',
TrdOpt in 'TrdOpt.pas';
{$R *.RES}
begin
Application.Initialize;
Application.Title := 'Term Paper SPO';
Application.CreateForm(TCursovForm, CursovForm);
Application.Run;
end.
unit LexAuto; {!!! Зависит от входного языка !!!}
interface
{ Модуль, обеспечивающий построение таблицы лексем
по исходному тексту программы }
uses Classes, TblElem, LexType, LexElem;
{ Функция создания списка лексем по исходному
тексту программы }
function MakeLexList(listFile: TStrings;
listLex: TLexList): integer;
implementation
uses SysUtils, FncTree;
type
{ Перечень всех возможных состояний конечного автомата }
TAutoPos = (
AP_START,AP_IF1,AP_IF2,AP_NOT1,AP_NOT2,AP_NOT3,
AP_ELSE1,AP_ELSE2,AP_ELSE3,AP_ELSE4,AP_END2,AP_END3,
AP_PROG1,AP_PROG2,AP_PROG3,AP_PROG4,AP_OR1,AP_OR2,
AP_BEGIN1,AP_BEGIN2,AP_BEGIN3,AP_BEGIN4,AP_BEGIN5,
AP_AND1,AP_AND2,AP_AND3,AP_SUB,AP_MUL,AP_DEL,
AP_WHILE1,AP_WHILE2,AP_WHILE3,AP_WHILE4,AP_WHILE5,
AP_COMM,AP_COMM2,AP_COMMSG,AP_ASSIGN,AP_VAR,AP_CONST,
AP_DO1,AP_DO2,AP_SIGN,AP_LT,AP_FIN,AP_ERR);
function MakeLexList(listFile: TStrings;
listLex: TLexList): integer;
{ Функция создания списка лексем по исходному
тексту программы }
var
i,j,iCnt,iStr, { Переменные и счетчики циклов }
iAll,{ Счетчик общего количества входных символов }
{ Переменные для запоминания позиции начала лексемы }
iStComm,iStart: integer;
posCur: TAutoPos;{ Текущее состояние конечного автомата }
{ Строки для временного хранения результатов }
sCurStr,sTmp: string;
{ Несколько простых процедур для работы со списком лексем }
procedure AddVarToList(posNext: TAutoPos; iP: integer);
{ Процедура добавления переменной в список }
begin
{ Выделяем имя переменной из текущей строки }
sTmp := System.Copy(sCurStr,iStart,iP-iStart);
{ При создании переменной она сначала заносится
в таблицу идентификаторов, а потом ссылка на нее -
в таблицу лексем }
listLex.Add(TLexem.CreateVar(AddTreeVar(sTmp),
iStComm,i,iStart));
iStart := j;
iStComm := iAll-1;
posCur := posNext;
end;
procedure AddVarKeyToList(keyAdd: TLexType;
posNext: TAutoPos);
{ Процедура добавления переменной и
разделителя в список }
begin
{ Выделяем имя переменной из текущей строки }
sTmp := System.Copy(sCurStr,iStart,j-iStart);
{ При создании переменной она сначала заносится
в таблицу идентификаторов, а потом ссылка на нее -
в таблицу лексем }
listLex.Add(TLexem.CreateVar(AddTreeVar(sTmp),
iStComm,i,iStart));
{ Добавляем разделитель после переменной }
listLex.Add(TLexem.CreateKey(keyAdd,iAll,i,j));
iStart := j;
iStComm := iAll-1;
posCur := posNext;
end;
function MyPower(a,b:real):real;
begin
Result := exp(b*ln(a));
end;
procedure AddConstToList(posNext: TAutoPos; iP: integer);
{ Процедура добавления константы в список }
var
l,d:Real;
k:byte;
begin
{ Выделяем константу из текущей строки }
sTmp := System.Copy(sCurStr,iStart,iP-iStart);
k:=0;
d:=0;
l:=length(sTmp);
repeat
inc(k);
d:=d+StrToInt(sTmp[k])*MyPower(2,(l-k));
until l=k;
{ Заносим константу в список вместе с ее значением }
listLex.Add(TLexem.CreateConst({StrToInt(sTmp)}round(d),
iStComm,i,iStart));
iStart := j;
iStComm := iAll-1;
posCur := posNext;
end;
procedure AddConstKeyToList(keyAdd: TLexType;
posNext: TAutoPos);
{ Процедура добавления константы и разделителя в список }
var
l,d:Real;
k:byte;
begin
{ Выделяем константу из текущей строки }
sTmp := System.Copy(sCurStr,iStart,j-iStart);
k:=0;
d:=0;
l:=length(sTmp);
repeat
inc(k);
d:=d+StrToInt(sTmp[k])*MyPower(2,(l-k));
until l=k;
{ Заносим константу в список вместе с ее значением }
listLex.Add(TLexem.CreateConst({StrToInt(sTmp)}round(d),iStComm,
i,iStart));
{ Добавляем разделитель после константы }
listLex.Add(TLexem.CreateKey(keyAdd,iAll,i,j));
iStart := j;
iStComm := iAll-1;
posCur := posNext;
end;
procedure AddKeyToList(keyAdd: TLexType;
posNext: TAutoPos);
{ Процедура добавления ключевого слова или
разделителя в список }
begin
listLex.Add(TLexem.CreateKey(keyAdd,iStComm,i,iStart));
iStart := j;
iStComm := iAll-1;
posCur := posNext;
end;
procedure Add2KeysToList(keyAdd1,keyAdd2: TLexType;
posNext: TAutoPos);
{ Процедура добавления ключевого слова и
разделителя в список }
begin
listLex.Add(TLexem.CreateKey(keyAdd1,iStComm,i,iStart));
listLex.Add(TLexem.CreateKey(keyAdd2,iAll,i,j));
iStart := j;
iStComm := iAll-1;
posCur := posNext;
end;
procedure KeyLetter(chNext: char; posNext: TAutoPos);
{ Процедура проверки очередного символа ключевого слова }
begin
case sCurStr[j] of
':': AddVarToList(AP_ASSIGN,j);
'-': AddVarKeyToList(LEX_SUB,AP_SIGN);
'+': AddVarKeyToList(LEX_ADD,AP_SIGN);
'=': AddVarKeyToList(LEX_EQ,AP_SIGN);
'>': AddKeyToList(LEX_GT,AP_SIGN);
'<': AddVarToList(AP_LT,j);
'(': AddVarKeyToList(LEX_OPEN,AP_SIGN);
')': AddVarKeyToList(LEX_CLOSE,AP_START);
'*': AddVarKeyToList(LEX_MUL,AP_START);
'/': AddVarKeyToList(LEX_DEL,AP_START);
';': AddVarKeyToList(LEX_SEMI,AP_START);
'{': AddVarToList(AP_COMM,j);
' ',#10,#13,#9: AddVarToList(AP_START,j);
else
if sCurStr[j] = chNext then posCur := posNext
else
if sCurStr[j] in ['0'..'9','A'..'Z','a'..'z','_']
then posCur := AP_VAR
else posCur := AP_ERR;
end{case list};
end;
procedure KeyFinish(keyAdd: TLexType);
{ Процедура проверки завершения ключевого слова }
begin
case sCurStr[j] of
'-': AddKeyToList(keyAdd,AP_SUB);
'+': Add2KeysToList(keyAdd,LEX_ADD,AP_SIGN);
'*': Add2KeysToList(keyAdd,LEX_MUL,AP_SIGN);
'/': Add2KeysToList(keyAdd,LEX_DEL,AP_SIGN);
'=': Add2KeysToList(keyAdd,LEX_EQ,AP_SIGN);
'>': Add2KeysToList(keyAdd,LEX_GT,AP_SIGN);
'<': AddKeyToList(keyAdd,AP_LT);
'(': Add2KeysToList(keyAdd,LEX_OPEN,AP_SIGN);
')': Add2KeysToList(keyAdd,LEX_CLOSE,AP_START);
';': Add2KeysToList(keyAdd,LEX_SEMI,AP_START);
'0'..'9','A'..'Z','a'..'z','_': posCur := AP_VAR;
'{': AddKeyToList(keyAdd,AP_COMMSG);
' ',#10,#13,#9: AddKeyToList(keyAdd,AP_SIGN);
else posCur := AP_ERR;
end{case list};
end;
begin
{ Обнуляем общий счетчик символов и результат функции }
iAll := 0;
Result := 0;
iStComm := 0;
{ Устанавливаем начальное состояние конечного автомата }
posCur := AP_START;
{ Цикл по всем строкам входного файла }
iCnt := listFile.Count-1;
for i:=0 to iCnt do
begin
{ Позиция начала лексемы - первый символ }
iStart := 1;
{ Запоминаем текущую строку }
sCurStr := listFile[i];
{ Цикл по всем символам текущей строки }
iStr := Length(sCurStr);
for j:=1 to iStr do
begin
{ Увеличиваем общий счетчик символов }
Inc(iAll);
{ Моделируем работу конечного автомата в зависимости
от состояния КА и текущего символа входной строки }
case posCur of
AP_START:
begin
{ В начальном состоянии запоминаем позицию
начала лексемы }
iStart := j;
iStComm := iAll-1;
case sCurStr[j] of
'b': posCur := AP_BEGIN1;
'i': posCur := AP_IF1;
'p': posCur := AP_PROG1;
'e': posCur := AP_ELSE1;
'w': posCur := AP_WHILE1;
'd': posCur := AP_DO1;
'o': posCur := AP_OR1;
'a': posCur := AP_AND1;
'n': posCur := AP_NOT1;
':': posCur := AP_ASSIGN;
'-': AddKeyToList(LEX_SUB,AP_SIGN);
'+': AddKeyToList(LEX_ADD,AP_SIGN);
'/': AddKeyToList(LEX_DEL,AP_SIGN);
'*': AddKeyToList(LEX_MUL,AP_SIGN);
'=': AddKeyToList(LEX_EQ,AP_SIGN);
'>': AddKeyToList(LEX_GT,AP_SIGN);
'<': posCur := AP_LT;
'(': AddKeyToList(LEX_OPEN,AP_SIGN);
')': AddKeyToList(LEX_CLOSE,AP_START);
';': AddKeyToList(LEX_SEMI,AP_START);
'0'..'1': posCur := AP_CONST;
'A'..'Z','c','f'..'h','j'..'m','2'..'9',
'q'..'v','x'..'z','_': posCur := AP_VAR;
'{': posCur := AP_COMM;
' ',#10,#13,#9: ;
else posCur := AP_ERR;
end{case list};
end;
AP_SIGN:
begin
{ Состояние, когда может встретиться
унарный минус }
iStart := j;
iStComm := iAll-1;
case sCurStr[j] of
'b': posCur := AP_BEGIN1;
'i': posCur := AP_IF1;
'p': posCur := AP_PROG1;
'e': posCur := AP_ELSE1;
'w': posCur := AP_WHILE1;
'd': posCur := AP_DO1;
'o': posCur := AP_OR1;
'a': posCur := AP_AND1;
'n': posCur := AP_NOT1;
'-': AddKeyToList(LEX_SUB,AP_SIGN);
'(': AddKeyToList(LEX_OPEN,AP_SIGN);
')': AddKeyToList(LEX_CLOSE,AP_START);
'0'..'1': posCur := AP_CONST;
'A'..'Z','c','f'..'h','j'..'m','2'..'9',
'q'..'v','x'..'z','_': posCur := AP_VAR;
'{': posCur := AP_COMMSG;
' ',#10,#13,#9: ;
else posCur := AP_ERR;
end{case list};
end;
AP_LT:
{ Знак меньше или знак неравенства? }
case sCurStr[j] of
'b': AddKeyToList(LEX_LT,AP_BEGIN1);
'i': AddKeyToList(LEX_LT,AP_IF1);
'p': AddKeyToList(LEX_LT,AP_PROG1);
'e': AddKeyToList(LEX_LT,AP_ELSE1);
'w': AddKeyToList(LEX_LT,AP_WHILE1);
'd': AddKeyToList(LEX_LT,AP_DO1);
'o': AddKeyToList(LEX_LT,AP_OR1);
'a': AddKeyToList(LEX_LT,AP_AND1);
'n': AddKeyToList(LEX_LT,AP_NOT1);
'>': AddKeyToList(LEX_NEQ,AP_SIGN);
'-': Add2KeysToList(LEX_LT,LEX_SUB,AP_SIGN);
'(': Add2KeysToList(LEX_LT,LEX_OPEN,AP_SIGN);
'0'..'1': AddKeyToList(LEX_LT,AP_CONST);
'2'..'9','A'..'Z','c','f'..'h','j'..'m','q'..'v','x'..'z','_': AddKeyToList(LEX_LT,AP_VAR);
'{': AddKeyToList(LEX_LT,AP_COMMSG);
' ',#10,#13,#9: AddKeyToList(LEX_LT,AP_SIGN);
else posCur := AP_ERR;
end{case list};
AP_ELSE1:
{ "else", или же "end", или переменная? }
case sCurStr[j] of
'l': posCur := AP_ELSE2;
'n': posCur := AP_END2;
':': AddVarToList(AP_ASSIGN,j);
'-': AddVarKeyToList(LEX_SUB,AP_SIGN);
'/': AddVarKeyToList(LEX_DEL,AP_SIGN);
'*': AddVarKeyToList(LEX_MUL,AP_SIGN);
'+': AddVarKeyToList(LEX_ADD,AP_SIGN);
'=': AddVarKeyToList(LEX_EQ,AP_SIGN);
'>': AddKeyToList(LEX_GT,AP_SIGN);
'<': AddVarToList(AP_LT,j);
'(': AddVarKeyToList(LEX_OPEN,AP_SIGN);
')': AddVarKeyToList(LEX_CLOSE,AP_START);
';': AddVarKeyToList(LEX_SEMI,AP_START);
'{': AddVarToList(AP_COMM,j);
'0'..'9','A'..'Z','a'..'k','m',
'o'..'z','_': posCur := AP_VAR;
' ',#10,#13,#9: AddVarToList(AP_START,j);
else posCur := AP_ERR;
end{case list};
AP_IF1: KeyLetter('f',AP_IF2);
AP_IF2: KeyFinish(LEX_IF);
AP_ELSE2: KeyLetter('s',AP_ELSE3);
AP_ELSE3: KeyLetter('e',AP_ELSE4);
AP_ELSE4: KeyFinish(LEX_ELSE);
AP_OR1: KeyLetter('r',AP_OR2);
AP_OR2: KeyFinish(LEX_OR);
AP_DO1: KeyLetter('o',AP_DO2);
AP_DO2: KeyFinish(LEX_DO);
AP_AND1: KeyLetter('n',AP_AND2);
AP_AND2: KeyLetter('d',AP_AND3);
AP_AND3: KeyFinish(LEX_AND);
AP_NOT1: KeyLetter('o',AP_NOT2);
AP_NOT2: KeyLetter('t',AP_NOT3);
AP_NOT3: KeyFinish(LEX_NOT);
AP_PROG1: KeyLetter('r',AP_PROG2);
AP_PROG2: KeyLetter('o',AP_PROG3);
AP_PROG3: KeyLetter('g',AP_PROG4);
AP_PROG4: KeyFinish(LEX_PROG);
AP_WHILE1: KeyLetter('h',AP_WHILE2);
AP_WHILE2: KeyLetter('i',AP_WHILE3);
AP_WHILE3: KeyLetter('l',AP_WHILE4);
AP_WHILE4: KeyLetter('e',AP_WHILE5);
AP_WHILE5: KeyFinish(LEX_WHILE);
AP_BEGIN1: KeyLetter('e',AP_BEGIN2);
AP_BEGIN2: KeyLetter('g',AP_BEGIN3);
AP_BEGIN3: KeyLetter('i',AP_BEGIN4);
AP_BEGIN4: KeyLetter('n',AP_BEGIN5);
AP_BEGIN5: KeyFinish(LEX_BEGIN);
AP_END2: KeyLetter('d',AP_END3);
AP_END3:
{ "end", или же "end.", или переменная? }
case sCurStr[j] of
'-': Add2KeysToList(LEX_END,LEX_SUB,AP_SIGN);
'+': Add2KeysToList(LEX_END,LEX_ADD,AP_SIGN);
'/': Add2KeysToList(LEX_END,LEX_DEL,AP_SIGN);
'*': Add2KeysToList(LEX_END,LEX_MUL,AP_SIGN);
'=': Add2KeysToList(LEX_END,LEX_EQ,AP_SIGN);
'>': Add2KeysToList(LEX_END,LEX_GT,AP_SIGN);
'<': AddKeyToList(LEX_END,AP_LT);
'(': Add2KeysToList(LEX_END,LEX_OPEN,AP_SIGN);
')': Add2KeysToList(LEX_END,LEX_CLOSE,AP_START);
';': Add2KeysToList(LEX_END,LEX_SEMI,AP_START);
'.': AddKeyToList(LEX_FIN,AP_START);
'0'..'9','A'..'Z','a'..'z','_':
posCur := AP_VAR;
'{': AddKeyToList(LEX_END,AP_COMMSG);
' ',#10,#13,#9: AddKeyToList(LEX_END,AP_SIGN);
else posCur := AP_ERR;
end{case list};
AP_ASSIGN:
case sCurStr[j] of
'=': AddKeyToList(LEX_ASSIGN,AP_SIGN);
else posCur := AP_ERR;
end{case list};
AP_VAR:
case sCurStr[j] of
':': AddVarToList(AP_ASSIGN,j);
'-': AddVarKeyToList(LEX_SUB,AP_SIGN);
'/': AddVarKeyToList(LEX_DEL,AP_SIGN);
'*': AddVarKeyToList(LEX_MUL,AP_SIGN);
'+': AddVarKeyToList(LEX_ADD,AP_SIGN);
'=': AddVarKeyToList(LEX_EQ,AP_SIGN);
'>': AddVarKeyToList(LEX_GT,AP_SIGN);
'<': AddVarToList(AP_LT,j);
'(': AddVarKeyToList(LEX_OPEN,AP_SIGN);
')': AddVarKeyToList(LEX_CLOSE,AP_START);
';': AddVarKeyToList(LEX_SEMI,AP_START);
'0'..'9','A'..'Z','a'..'z','_':
posCur := AP_VAR;
'{': AddVarToList(AP_COMM,j);
' ',#10,#13,#9: AddVarToList(AP_START,j);
else posCur := AP_ERR;
end{case list};
AP_CONST:
case sCurStr[j] of
':': AddConstToList(AP_ASSIGN,j);
'-': AddConstKeyToList(LEX_SUB,AP_SIGN);
'/': AddConstKeyToList(LEX_DEL,AP_SIGN);
'*': AddConstKeyToList(LEX_MUL,AP_SIGN);
'+': AddConstKeyToList(LEX_ADD,AP_SIGN);
'=': AddConstKeyToList(LEX_EQ,AP_SIGN);
'>': AddConstKeyToList(LEX_GT,AP_SIGN);
'<': AddConstToList(AP_LT,j);
'(': AddConstKeyToList(LEX_OPEN,AP_SIGN);
')': AddConstKeyToList(LEX_CLOSE,AP_START);
';': AddConstKeyToList(LEX_SEMI,AP_START);
'0'..'9','A'..'F': posCur := AP_CONST;
'{': AddConstToList(AP_COMM,j);
' ',#10,#13,#9: AddConstToList(AP_START,j);
else posCur := AP_ERR;
end{case list};
AP_COMM:
case sCurStr[j] of
'}': posCur := AP_START;
end{case list};
AP_COMMSG:
case sCurStr[j] of
'}': posCur := AP_SIGN;
end{case list};
end{case pos};
{ Проверяем, не достигнут ли конец строки }
if j = iStr then
begin
{ Конец строки - это конец текущей лексемы }
case posCur of
AP_IF2: AddKeyToList(LEX_IF,AP_SIGN);
AP_PROG4: AddKeyToList(LEX_PROG,AP_START);
AP_ELSE4: AddKeyToList(LEX_ELSE,AP_START);
AP_BEGIN5: AddKeyToList(LEX_BEGIN,AP_START);
AP_WHILE5: AddKeyToList(LEX_WHILE,AP_SIGN);
AP_END3: AddKeyToList(LEX_END,AP_START);
AP_OR2: AddKeyToList(LEX_OR,AP_SIGN);
AP_DO2: AddKeyToList(LEX_DO,AP_SIGN);
AP_AND3: AddKeyToList(LEX_AND,AP_SIGN);
AP_NOT3: AddKeyToList(LEX_NOT,AP_SIGN);
AP_LT: AddKeyToList(LEX_LT,AP_SIGN);
AP_FIN: AddKeyToList(LEX_FIN,AP_START);
AP_CONST: AddConstToList(AP_START,j+1);
AP_ASSIGN: posCur := AP_ERR;
AP_IF1,AP_PROG1,AP_PROG2,AP_PROG3,
AP_ELSE1,AP_ELSE2,AP_ELSE3,
AP_OR1,AP_DO1,AP_AND1,AP_AND2,AP_NOT1,AP_NOT2,
AP_WHILE1,AP_WHILE2,AP_WHILE3,AP_WHILE4,
AP_END2,AP_BEGIN1,AP_BEGIN2,AP_BEGIN3,AP_BEGIN4,
AP_VAR: AddVarToList(AP_START,j+1);
end{case pos2};
end;
{ Проверяем не была ли ошибка в лексемах }
if posCur = AP_ERR then
begin
{ Если была ошибка, вычисляем позицию
ошибочной лексемы }
iStart := (j - iStart)+1;
{ и запоминаем ее в виде фиктивной лексемы в начале
списка для детальной диагностики ошибки }
listLex.Insert(0,
TLexem.CreateInfo('Недопустимая лексема',
iAll-iStart,i,iStart));
{ Если ошибка, прерываем цикл }
Break;
end;
end{for j};
{ В конце строки увеличиваем общий счетчик символов
на 2: конец строки и возврат каретки }
Inc(iAll,2);
{ Если ошибка, запоминаем номер ошибочной строки
и прерываем цикл }
if posCur = AP_ERR then
begin
Result := i+1;
Break;
end;
end{for i};
{ Если комментарий не был закрыт, то это ошибка }
if posCur in [AP_COMM,AP_COMMSG] then
begin
listLex.Insert(0,
TLexem.CreateInfo('Незакрытый комментарий',
iStComm,iCnt,iAll-iStComm));
Result := iCnt;
end
else
if not (posCur in [AP_START,AP_SIGN,AP_ERR]) then
{ Если КА не в начальном состоянии -
это неверная лексема }
begin
listLex.Insert(0,
TLexem.CreateInfo('Незавершенная лексема',
iAll-iStart,iCnt,iStart));
Result := iCnt;
end;
end;
end.
unit SyntRule; {!!! Зависит от входного языка !!!}
interface
{ Модуль, содержащий описание матрицы предшествования
и правил грамматики }
uses LexType, Classes;
const
RULE_LENGTH = 7; { максимальная длина правила
(в расчете на символы грамматики) }
RULE_NUM = 36; { общее количество правил грамматики }
var
{ Матрица операторного предшествования }
GramMatrix: array[TLexType,TLexType] of char =
( {pr. end. ; if ( ) else beg end do whl a c := or and < > = <> not - + / * !}
{pr.} (' ','=','<','<',' ',' ',' ','<',' ','<',' ','<',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{end.}(' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ','>'),
{;} (' ','>','>','<',' ',' ',' ','<','>','<','=','<',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{if} (' ',' ',' ',' ','=',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{(} (' ',' ',' ',' ','<','=',' ',' ',' ',' ',' ','<','<',' ','<','<','<','<','<','<','<','<','<','<','<',' '),
{)} (' ','>','>','<',' ','>','=','<','>','<',' ','<',' ',' ','>','>','>','>','>','>',' ','>','>','>','>',' '),
{else}(' ','>','>','<',' ',' ','>','<','>','<',' ','<',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{beg.}(' ',' ','<','<',' ',' ',' ','<','=','<',' ','<',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{end} (' ','>','>',' ',' ',' ','>',' ','>',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{do} (' ',' ','=','<',' ',' ','>','<','<',' ','<','<',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{whil}(' ','>','>',' ','=',' ',' ',' ',' ',' ',' ','<',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{a} (' ','>','>',' ',' ','>','>',' ','>',' ',' ',' ',' ','=','>','>','>','>','>','>',' ','>','>','>','>',' '),
{c} (' ','>','>',' ',' ','>','>',' ','>',' ',' ',' ',' ',' ','>','>','>','>','>','>',' ','>','>','>','>',' '),
{:=} (' ','>','>',' ','<',' ','>',' ','>',' ',' ','<','<',' ',' ',' ',' ',' ',' ',' ',' ','<','<','<','<',' '),
{or} (' ',' ',' ',' ','<','>',' ',' ',' ',' ',' ','<','<',' ','>','<','<','<','<','<','<','<','<','<','<',' '),
{and} (' ',' ',' ',' ','<','>',' ',' ',' ',' ',' ','<','<',' ','>','>','<','<','<','<','<','<','<','<','<',' '),
{<} (' ',' ',' ',' ','<','>',' ',' ',' ',' ',' ','<','<',' ','>','>',' ',' ',' ',' ',' ','<','<','<','<',' '),
{>} (' ',' ',' ',' ','<','>',' ',' ',' ',' ',' ','<','<',' ','>','>',' ',' ',' ',' ',' ','<','<','<','<',' '),
{=} (' ',' ',' ',' ','<','>',' ',' ',' ',' ',' ','<','<',' ','>','>',' ',' ',' ',' ',' ','<','<','<','<',' '),
{<>} (' ',' ',' ',' ','<','>',' ',' ',' ',' ',' ','<','<',' ','>','>',' ',' ',' ',' ',' ','<','<','<','<',' '),
{not} (' ',' ',' ',' ','=',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '),
{-} (' ','>','>',' ','<','>','>',' ','>',' ',' ','<','<',' ','>','>','>','>','>','>',' ','>','>','>','>',' '),
{+} (' ','>','>',' ','<','>','>',' ','>',' ',' ','<','<',' ','>','>','>','>','>','>',' ','>','>','>','>',' '),
{/} (' ','>','>',' ','<','>','>',' ','>',' ',' ','<','<',' ','>','>','>','>','>','>',' ','>','>','>','>',' '),
{*} (' ','>','>',' ','<','>','>',' ','>',' ',' ','<','<',' ','>','>','>','>','>','>',' ','>','>','>','>',' '),
{!} ('<',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '));
{ Правила исходной грамматики }
GramRules: array[1..RULE_NUM] of string =
('progEend.','E','E;E','E;','if(B)EelseE','if(B)E',
'beginEend','doE;while(B)','a:=E','BorB','E/E','B',
'BandB','E<E','E>E','E=E','E<>E','(B)','not(B)',
'E-E','E+E','(E)','a','c','B;B','E;B','a:=B','B+E',
'E+B','B-E','E-B','E/B','B/E',
'E*E','E*B','B*E');
function MakeSymbolStr(iRuleNum: integer): string;
{ Функция корректировки отношений предшествования
для расширения матрицы предшествования }
function CorrectRule(cRule: char; lexTop,lexCur: TLexType;
symbStack: TList): char;
implementation
uses SyntSymb;
function MakeSymbolStr(iRuleNum: integer): string;
begin
if iRuleNum in [10..20] then Result := 'B'
else Result := 'E';
end;
function CorrectRule(cRule: char; lexTop,lexCur: TLexType;
symbStack: TList): char;
var j: integer;
begin
{ Корректируем отношение для символа "else", если в стеке
не логическое выражение }
Result := cRule;
if (cRule = '=') and (lexTop = LEX_CLOSE)
and (lexCur = LEX_ELSE) then
begin
j := TSymbStack(symbStack).Count-1;
if (j > 2)
and (TSymbStack(symbStack)[j-2].SymbolStr <> 'B')
then Result := '>';
end;
end;
end.
3
Документ
Категория
Рефераты
Просмотров
62
Размер файла
448 Кб
Теги
spo
1/--страниц
Пожаловаться на содержимое документа