Построение функции предшествования по заданной КС-грамматике

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВАКафедра информационных систем и технологий ПОЯСНИТЕЛЬНАЯ ЗАПИСКАк курсовому проекту по курсу Информационные технологии на темуПостроение функции предшествования по заданной КС-грамматике Выполнил студент группы 634 Абраров А.М.Руководитель проектаШамашов М.А.Дата сдачиОценка Самара 2001 г. РЕФЕРАТ Курсовой проект Пояснительная записка 30 с 5 рис 3 схем программ и алгоритмов, 3 библиографического источника.

ТЕРМИНАЛ, НЕТЕРМИНАЛ, ГРАММАТИКА, ФУНКЦИЯ ПРЕДШЕСТВОВАНИ, ГРАФ, ЛИНЕАРИЗАЦИЯ. В курсовом проекте разработан алгоритм и соответствующая ему программа, позволяющая по введнной пользователем КС-грамматике построить функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа. Грамматика может быть введена как в самой программе, так и из текстового файла. Также существует возможность сохранения результата.Программа написана на языке Pascal 0. СОДЕРЖАНИЕ СОДЕРЖАНИЕ 1. Постановка задачи 2. Описание структуры данных 3. Грамматики предшествования 3.1 Грамматики простого предшествования 6 3.2 Грамматики операторного предшествования 3.3 Пример построения матрицы предшествования 3.4 Линеаризация матрицы предшествования 4. Руководство пользователя 5. Текст программы 6. Список использованных источников 1. Постановка задачи По заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа. 2. Recordсписок терминалов и нетерминалов NameStr10терминал или нетерминал NextnotTerm End Для хранения грамматики текста используется strBufarray 1 800 of Char Матрица предшествования matrixPrarray 1 20,1 20 of 4 Функция предшествования FuncPrarray 1 2,1 20 of Byte Процедуры и функции основные Ввод грамматики осуществляется функцией Function InputTextBoolean Для синтаксического анализа КС-грамматики используется процедура Procedure Check Для нахождения левых и правых используется процедура Procedure SearchLR Построение матрицы предшествования выполняет процедура Procedure Matrix Построение функции предшествования осуществляется процедурой Procedure FuncPrecede 3. Грамматики предшествования КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.

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

Выделяют следующие типы грамматик предшествования простого предшествования расширенного предшествования слабого предшествования смешанной стратегии предшествования операторного предшествования.

Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования. 3.1 Грамматики простого предшествования Грамматикой простого предшествования называют такую КС-грамматику GVN,VT,P,S, VVTИVN в которой 1. Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования Si Sj Si,SjО V, если и только если правило U xSiSjy О P, где UО VN, x,yО V Si Sj Si,SjО V, если и только если правило U xSiDy О P и вывод DЮ Sjz, где U,DО VN, x,y,zО V Si Sj Si,SjО V , если и только если правило U xCSjy О P и вывод CЮ zSi или правило U xCDy О P и выводы CЮ zSi и DЮ Sjw, где U,C,DО VN, x,y,z,wО 2. Различные порождающие правила имеют разные правые части. Отношения , и называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов.

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

Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если Si Sj, то не обязательно, что Sj Si поэтому знаки предшествования иногда помечают специальной точкой Ч , Ч , Ч Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам Si Si1, если символ Si1 - крайний левый символ некоторой основы Si Si1 , если символ Si - крайний правый символ некоторой основы Si Si1 , если символы Si и Si1 принадлежат одной основе.

Исходя из этих соотношений выполняется разбор строки для грамматики предшествования.

На основании отношений предшествования строят матрицу предшествования грамматики.

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

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

Эти множества определяются следующим образом LU T UЮ Tz, U,TО V, zО V - множество крайних левых символов относительно нетерминального символа U цепочка z может быть и пустой цепочкой RU T UЮ zT, U,TО V, zО V - множество крайних правых символов относительно нетерминального символа U. Тогда отношения предшествования можно определить так Si Sj Si,SjО V, если правило U xSiSjy О P, где UО VN, x,yО V Si Sj Si,SjО V, если правило U xSiDy О P и SjО LD, где U,DО VN, x,yО V Si Sj Si,SjО V , если правило U xCSjy О P и SiО RC или правило U xCDy О P и SiО RC, SjО LD, где U,C,DО VN, x,yО V. Такое определение отношений удобнее на практике, так как не требует построения выводов, а множества LU и RU могут быть построены для каждого нетерминального символа UО VN по очень простому алгоритму Шаг 1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части.

Во множество LU включаем самый левый символ из правой части правил, а во множество RU - самый крайний символ правой части.

Переходи к шагу 2. Шаг 2. Для каждого нетерминального символа U если множество LU содержит нетерминальные символы грамматики U ,U то его надо дополнить символами, входящими в соответствующие множества LU , LU, и не входящими в LU. Ту же операцию надо выполнить для RU. Шаг 3. Если на предыдущем шаге хотя бы одно множество LU или RU для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено.

После построения множеств LU и RU по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами н и к начало и конец цепочки.Для них определены следующие отношения предшествования н a, aО V, если SЮ ax, где SО VN, xО V или с другой стороны если aО LS к a, aО V, если SЮ xa, где SО VN, xО V или с другой стороны если aО RS. 3.2 Грамматики операторного предшествования Грамматикой операторного предшествования называется приведенная КС-грамматика без l -правил e-правил, в которой правые части продукций не содержат смежных нетерминальных символов.

Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов включая символы н и к. Отношения предшествования для грамматики операторного предшествования GVN,VT,P,S задаются следующим образом a b, если и только если существует правило U xaby О P или правило U xaCby, где a,bО VT, U,CО VN, x,yО V a b, если и только если существует правило U xaCy О P и вывод CЮ bz или вывод CЮ Dbz, где a,bО VT, U,C,DО VN, x,y,zО V a b, если и только если существует правило U xCby О P и вывод CЮ za или вывод CЮ zaD, где a,bО VT, U,C,DО VN, x,y,zО V. В грамматике операторного предшествования различные порождающие правила имеют разные правые части.

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

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - LtU или RtU LtU t UЮ tz или UЮ Ctz, где tО VT, U,CО VN, zО V RtU t UЮ zt или UЮ ztC , где tО VT, U,CО VN, zО V. Тогда определения отношений операторного предшествования будут выглядеть так a b, если правило U xaby О P или правило U xaCby, где a,bО VT, U,CО VN, x,yО V a b, если правило U xaCy О P и bО LtC, где a,bО VT, U,CО VN, x,yО V a b, если правило U xCby О P и aО RtC, где a,bО VT, U,CО VN, x,yО V. В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

Для нахождения множеств LtU и RtU используется следующий алгоритм Шаг 1. Для каждого нетерминального символа грамматики U строятся множества LU и RU. Шаг 2. Для каждого нетерминального символа грамматики U ищутся правила вида U tz и U Ctz, где tО VT, CО VN, zО V терминальные символы t включаются во множество LtU. Аналогично для множества RtU ищутся правила вида U zt и U ztC. Шаг 3. Просматривается множество LU, в которое входят символы U ,U Множество LtU дополняется символами, входящими в LtU , LtU, и не входящими в LtU. Аналогичная операция выполняется и для множества RtU на основе множества RU. Для практического использования матрицу предшествования дополняют символами н и к начало и конец цепочки.

Для них определены следующие отношения предшествования н a, aО VT, если SЮ ax или SЮ Cax, где S,CО VN, xО V или если aО LtS к a, aО VT, если SЮ xa или SЮ xaC, где S,CО VN, xО V или если aО RtS. 3.3 Пример построения матрицы предшествования Построим матрицу предшествования для грамматики операторного предшествования.

Рассмотрим в качестве примера грамматику GS,B,T,J p,P,S Терминалы выделены жирным шрифтом P S -B правило 1B T BT правила 2 и 3T J TJ правила 4 и 5J B p правила 6 и 7 Видно, что эта грамматика является грамматикой операторного предшествования.

Построим множества крайних левых и крайних правых символов LU, RU относительно всех нетерминальных символов грамматики.Результат построения приведен в табл. 2. На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов LtU, RtU относительно всех нетерминальных символов грамматики. Результат второй и третий шаги построения приведен в табл. 3. Таблица 2. Множества крайних правых и крайних левых символов грамматики по шагам построения СимволШаг 1 начало построенияПоследний шаг результатULURULURUJ p p p pTJ TJJ T pJ pBT BTT B J pT J pS-B-B T J pТаблица 3. Множества крайних правых и левых терминальных символов грамматики по шагам построения СимволШаг 1 начало построенияПоследний шаг результатULtURtULtURtUJ p p p pT p pB p pS pНа основе этих множеств и правил грамматики G построим матрицу предшествования грамматики табл. 4. Таблица 4. Матрица предшествования грамматики Символы-p к- P н Посмотрим, как заполняется матрица предшествования в табл. 4 на примере символа . В правиле грамматики B BT правило 3 этот символ стоит слева от нетерминального символа T. В множество LtT входят символы p. Ставим знак в клетках матрицы, соответствующих этим символам, в строке для символа . В то же время в этом же правиле символ стоит справа от нетерминального символа B. В множество RtB входят символы p. Ставим знак в клетках матрицы, соответствующим этим символам, в столбце для символа . Больше символ ни в каком правиле не встречается, значит заполнение матрицы для него закончено, берем следующий символ и продолжаем заполнять матрицу таким же методом. Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы.

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

Тогда получим следующий вид правил P E -E правило 1E E EE правила 2 и 3E E EE правила 4 и 5E E p правила 6 и 7 Это преобразование не ведет к созданию эквивалентной грамматики и выполняется только после построения всех множеств и матрицы предшествования.

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

По матрице Mnn, элементы которой принимают только три значения , попытаемся построить два целочисленных вектора f и g Mij равно , если fi gj Mij равно , если fi gj Mij равно , если figj Для получения этих векторов используется следующий метод построить ориентированный граф, содержащий n вершин типа F и n вершин типа G - построить ребро графа Fi- Gj, если i j - построить ребро графа Fi -Gj, если i j - склеить вершины Fi и Gj, если i j Если полученный граф циклический, то линеаризация невозможна.

Иначе положить fi равным длине самого длинного пути из Fi, gi равным длине самого длинного пути из Gi. 4. Руководство пользователя После запуска программы пользователю предлагается ввести КС-грамматику ограничение при вводе длина нетерминала не больше восьми символов. Ввод строки заканчивается нажатием клавиши Enter. Для определения в программе нетерминала используются символы и непосредственно между которыми находится нетерминал, знак или , знак присвоить . Новая строка обязательно должна начинаться с нетерминала и последующим символоми . Для начала анализа введнной КС-грамматике нужно нажать клавишу F5 или выбрать в меню пункт Запуск меню вызывается нажатием F9. Перед тем как начать построение матрицы предшествования производится синтаксический анализ введенного текста.

Возможные ошибки при вводе грамматики После символа должен обязательно следовать терминал или нетерминал.

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

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

При построении векторов граф, проверяется на цикличность при существовании цикла выводится сообщении о невозможности построения функции предшествования. 5. Текст программы Program KP Uses TpCrt,Graph,GrText,DataUnit Const TxtПо заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа Errors array 0 10 of String34 ошибки КС-грамматика синтаксически верна,0 Ожидается , 1 Ожидается , 2 Ожидается , 3 Требуется нетерминал, 4 Требуется терминал, 5 Неопределенный нетерминал, 6 Неиспользуемый нетерминал, 7 Требуется терминал или нетерминал,8 Многоопределенный нетерминал, 9 Найдены недопустимые символы 10 menuarray1 5 of string10 Открыть,Сохранить,Запуск,Информация,Выхо д Type notTermList ListRecordсписок терминалов и нетерминалов NameStr10терминал или нетерминал NextnotTerm End strBufarray 1 800 of Char matrixPrarray 1 20,1 20 of 0 4 Var iByteтекущая позиция sStringтекущая строка LenByte absolute s strstrBufобщий буфер для текста LenStrIntegerвсего символов в буфере CLine,кол-во строк yByteтекущая строка CTermByteкол-во нетерминалов CTrmNotTrmByteкол-во нетерминалов и терминалов notTerminalSNotTermнетерминалы встречающиеся в правых частях notTerminalLNotTermнетерминалы в левой части TrmnotTrmNotTermсписок терминалов и нетерминалов LTNNotTermлевые RTNNotTermправые tmpNotTermвременная переменная matrixPrecedematrixPr LenWinByteширина окна I Dinamic.inc процедуры для работы с динамическими переменными I GraphPr.inc графический интерфейс I ServFunc.inc дополнительные процедуры обработки строки Procedure Blank пропуск управляющих символов и пробелов Begin While i Len and Si 32 do inci End Function LetsCharBoolean контроль букв Begin Lets A and s Z or s in RusLetters End Function Dig sCharVar nByteBoolean контроль цифр Begin If s 0 and s 9 Then Begin nords-48 Digtrue End Else Digfalse End Function Terminal Var termStringBoolean поиск терминала Begin term If i Len Then While i Len and Si in DigitsLatLettersPunctuationServiceRusLet ters and not si and not si and not si Do Begin termtermsi inci End Terminalterm End Function notTerminal Var termStringBoolean поиск нетерминала Var jword nByte ExBoolean Begin Blank ji term ExTrue If i Lengths Then If LetSi Then Begin While i Lengths and LetSi or DigSi,n do Begin If i-j 9 Then termtermSi inci End If i-j 8 Then ExFalse Else Blank End Else ExFalse Else ExFalse notTerminalEx End Procedure Check Var termString Exist,ExBoolean notTList kByte Label notTerminalOrTerminal, OrS,LineS,EndS,Start,New,Gluk Begin Goto Start Newпри возникновении ошибки DeleteListNotTerminalS DeleteListNotTerminalL DeleteListTrmNotTrm If not InputText Then Exit Startодин раз i1 y1 k1 CTerm0 CTrmNotTrm0 PosStr1,sпервая строка If s Then Goto New LineSновая строка GotoXY1,10Writes Длина анализ.строки ,Lengths, 1310,y,y, всего строк ,Cline Blank If not si Then Begin Error1 Goto New End Else Begin inci Blank If not notTerminalterm Then Begin Error4 Goto New End Else Beginесть нетерминал Blank If not si Then Begin Error2 Goto New End Elseзаписываем нетерминал Begin NotT.Name term If SearchNotTerminalL,NotT 0 Then Beginмногоопределенный Error9 Goto New End If SearchTrmNotTrm,NotT0 Then Begin CompleteTrmNotTrm,NotTв общий список теминаловнетерминалов incCTrmNotTrm End CompleteNotTerminalL,NotTлев. часть incCTerm inci Blank If not Copys,i,2 Then Begin Error3 Goto New End Else Beginесть inci,2 notTerminalOrTerminalпосле обязательный терминал или нетерминал Blank If si Thenнетерминал Begin inci Blank If notTerminalterm Then Beginесть нетерминал Blank If si Thenзаписываем нетерминал Begin NotT.Name term CompleteNotTerminalS,NotT If SearchTrmNotTrm,NotT0 Then Begin CompleteTrmNotTrm,NotTв общий список теминаловнетерминалов incCTrmNotTrm End inci Blank Goto OrSможет быть знак ИЛИ End Else Begin Error2нет Goto New End End Else Begin Error4нет нетерминала, но есть Goto New End End Elseтерминал If Terminalterm Thenзаписываем терминал Begin NotT.Nameterm If SearchTrmNotTrm,NotT0 Then Begin CompleteTrmNotTrm,NotTв общий список теминаловнетерминалов incCTrmNotTrm End Blank Goto OrS End Else Begin Error8нет нетерминала или терминала Goto New End OrS If i Len Then Goto Glukобходим глюк If si Thenзнак ИЛИ Begin inci Goto notTerminalOrTerminal End Elseзнака ИЛИ нет Begin Blank If i Len Thenконец строки Gluk If y CLine Thenдошли до конца строки Begin следующ. стр incy posStry,s If s Then Goto EndS i1 Goto LineS End Elseконец файла Goto EndS Else Goto notTerminalOrTerminalзнака ИЛИ нет End End End End End EndS проверка нетерминалов tmpNotTerminalL. Nextпропускаем первый existTrue y2 While tmp Nil and Exist Do Begin NotTtmp ExistSearchNotTerminalS,NotT 0 tmptmp.Next incy End decy i1 While i y Do Beginпозицианируем на нужную строку в s строка с ошибкой posStry,s inci End If not Exist Thenнеиспользуемый нетерминал Begin i1 Error7 Goto New End tmpNotTerminalS existTrue While tmp Nil and Exist Do Begin NotTtmp ExistSearchNotTerminalL,NotT 0 tmptmp.Next End If not Exist Thenнеопределенный нетерминал Begin i1 y0 ExFalse While not Ex Do Beginпозицианируем на нужную строку incy PosStry,sв s строка с ошибкой iPosNotT.name,s Exi 0 End Error6 Goto New End Window5,21,59,25 TextColor15 TextBackGround1 WriteLNErrors0 readkey End Procedure SearchLR Function SearchInBlocknBytelNotTerminfListByte Var jByte ExBoolean Begin If l Nil Then Begin j1 While l Nil and n j Do Begin If l.Name0 Then incj ll.Next End ExFalse While l nil and l.Name inf.Name and Not Ex Do Begin incj If l.Name0 Then ExTrue ll.next End End If lNil or Ex Then SearchInBlock0 Else SearchInBlockj End Procedure InsListInBlocknByte lNotTermx,dList Var qNotTerm jByte Begin If lNil Then WriteLNВнимание Внутренняя ошибка 03 Else Begin j1 While l Nil and n j Do Begin If l.Name0 Then incj ll.Next End While l Nil and l.Name x.Name Do ll.Next If l Nil Then Begin newq q.Named.Name q.Nextl.Next l.Nextq End End End Procedure AddListLRNotTerm Var tmp,pNotTerm tmp2NotTerm tmpNameStr10 y,jByte infList inf2List Begin y1 tmpListLRсписок с разделителями ptmp Repeat ищем нетерминал в левых или правых tmpp tmp2NotTerminalL While tmp Nil and Pos ,tmp.Name 1 Do Begin If tmp.Name0 Then incy tmptmp.Next End If tmpNil Then pNil Else If tmp.Next Nil Then ptmp.Nextсохраняем позицию указатель на следующий Else pNil tmpNametmp.Name i1 ищем tmpName в правых или левых If tmp Nil Then SeektmpName,ListLR,tmp tmp указывает на элемент с которого нужно начать добавлять inf2.NametmpName While tmp Nil and tmp.Name 0 Do Begin inf.Nametmp.Name нужно проверить на повторяющиеся If SearchInBlocky,ListLR,inf0 Then InsListInBlocky,ListLR,inf2,inf tmptmp.Next End Until pNil End Var tmpList termString Label More,Next Begin предполагаем что грамматика не содержит ошибок анализ грамматики без отслеживания ошибок y1 i1 Repeat PosStry,s Blank iPos,S1i ставим после MoreBlank If si Then Begin inci Blank Terminalterm tmp.Name term If SearchInBlocky,LTN,tmp0 and term Then CompleteLTN,tmpдобавляем левый Blank inci End Else Begin Terminalterm tmp.Nameterm If SearchInBlocky,LTN,tmp0 and term Then CompleteLTN,tmpдобавляем левый If i-1Len Then после или после только один терминал CompleteRTN,tmp End If i Len Then Goto Nextпоследний в строке был терминал While i Len and Si1 Do inciдо конца правила If si Then последний в правиле нетерминал Begin While i 1 and si Do deci inci Blank Terminaltermпоследний нетерминал tmp.Name term If SearchInBlocky,RTN,tmp0 and term Then CompleteRTN,tmpдобавляем правый inciпропуск If si Then Begin inci Goto More End End Elseпоследний в правиле терминал Begin While i 1 and notsi or si or si Do deci inci Blank Terminalterm tmp.Nameterm If SearchInBlocky,RTN,tmp0 and term Then CompleteRTN,tmpдобавляем правый If si Then Begin inci Goto More End End If i Len Thenпрошли не всю строку Goto More nextincy tmp.Name0после каждой строки ставим разделитель CompleteLTN,tmpдобавляем левый CompleteRTN,tmpдобавляем правый Until y CLine после цикла получили предварительные левые и правые, их еще надо дополнить For y1 To 10 Do Begin AddLTn AddRTn End получили левые и правые, разделенные 0 End Procedure Matrix Procedure Precede Label More,Next Var mi,mjByte tmpList pNotTerm term,term2String ExBoolean Begin y1 i1 Repeat PosStry,s Blank iPos,S1i ставим после MoreBlank If si Then Begin inci Blank Terminalterm tmp.Name term term2tmp.Name Blank inci miSearchTrmnotTrm,tmp If Terminalterm Thenнетерминал за ним терминал Begin tmp. Nameterm mjSearchTrmnotTrm,tmp Exmatrixprecedemi,mj0 If not Ex Then matrixprecedemi,mj4 Else matrixprecedemi,mj3 pRTN Seekterm2,RTN,p While p Nil and p.Name 0 Do Begin tmp.Namep.Name miSearchTrmnotTrm,tmp Exmatrixprecedemi,mj0 If not Ex Then matrixprecedemi,mj4 Else matrixprecedemi,mj2 pp. Next End End Else If i Len Then Goto Next Else If si Then Begin inci Goto More End Blank If si Then Begin inci Goto More End If i Len Thenне дошли до конца правила Begin ii-Lengthterm While si Do deci Goto More End End Else Begin Terminalterm tmp.Nameterm miSearchTrmnotTrm,tmp Blank If i Len Thenпоследний в правиле терминал Goto Next If si Thenза терминалом следует нетерминал Begin inci Terminalterm tmp.Name term mjSearchTrmnotTrm,tmp записываем в матрицу Exmatrixprecedemi,mj0 If not Ex Then matrixprecedemi,mj4 Else matrixprecedemi,mj3 pLTN Seektmp.Name,LTN,p While p Nil and p.Name 0 Do Begin tmp.Namep.Name mjSearchTrmnotTrm,tmp Exmatrixprecedemi,mj0 If not Ex Then matrixprecedemi,mj4 Else matrixprecedemi,mj1 pp.Next End Blank inci Blank If si Then Begin inci Goto More End If i Len Thenне дошли до конца правила Begin ii-Lengthterm-2 Goto More End End Else If i Len Then Begin If si Then Begin inci Goto More End за терминалом терминал tmp.Nameterm miSearchTrmnotTrm,tmp Terminalterm tmp.Nameterm mjSearchTrmnotTrm,tmp Exmatrixprecedemi,mj0 If not Ex Then matrixprecedemi,mj4 Else matrixprecedemi,mj3 ii-Lengthterm End End If i Len Thenпрошли не всю строку Goto More nextincy Until y CLine End Procedure WrtSymboli,j,cByte Begin Case c of 1Begin OutTextXY18i25,27j24-40, PutPixel18i255,27j243-40,3 End 2Begin OutTextXY18i25,27j24-40, PutPixel18i25-1,27j243-40,3 End 3Begin OutTextXY18i25,25j243-40, PutPixel18i252,25j243-40,3 End 4OutTextXY18i25,25j243-40,X End End Var sdigString2 jByte x,yByte tmpNotTerm tmp2NotTerm ErrorBoolean PicPointer sizeWord Begin Message30,15,15,7 False Zoom Message30,15,15,7,Матрица предшествования,False TabCTrmNotTrm1,10,20 WriteGrГРАММАТИКА,440,360,200 For j1 To CLine Do Begin PosStrj,s LineStrs,400,375j13 End TextColor14 TextBackGround0 Window1,1,80,28 x2 y24 GotoXY50,2 WriteLNЛевые Правые SetColor14 tmpTrmNotTrm tmp2notTerminalL For i1 To CTrmNotTrm Do Begin Stri,sdig OutTextXY18i25,25,sdig OutTextXY18,35i24,sdig incy If y29 Then Begin incx,13 y25 End GotoXYx,y TextColor14 Writesdig TextColor3 Writetmp.Name GotoXY43,2i If tmp2 Nil Then Writetmp2.Name tmp2tmp2.Next tmptmp.

Next End tmp2LTN i3 GotoXY50,WhereY While tmp2 Nil Do Begin If tmp2.Name0 Then Begin GotoXY50,WhereY inci End GotoXYWhereX,i If tmp2.Name 0 Then Writetmp2.Name tmp2tmp2.Next End tmp2RTN i3 GotoXY70,WhereY While tmp2 Nil Do Begin If tmp2.Name0 Then Begin GotoXY70,WhereY inci End GotoXYWhereX,i If tmp2.Name 0 Then Writetmp2.Name tmp2tmp2.Next End Precede SetColor3 ErrorFalse For j1 To CTrmNotTrm Do For i1 To CTrmNotTrm Do Begin If MatrixPrecedej,i4 Then ErrorTrue WrtSymboli,j2,MatrixPrecedej,i End If Error Then Begin TextColor15 TextBackGround1 Message30,15,15,7,Нажмите любую клавишу, True VerticalRetrace SaveWindowGraphCooX20,GraphCooY12,GraphC ooX621,GraphCooY19,Pic,size TextBackGround4 TextColor14 OpenWindow20,12,60,17,3, Внимание ,True WriteLnМатрица предшествования содержит ошибки Write Построение функции предшествования Write невозможно Attention363,243 ReadKey LoadWindowGraphCooX20,GraphCooY12,size,p ic End End основная программа Begin Init InitText If InputText Then Begin Check SearchLR Matrix ClearBuf ReadKey End GraphWriteOff CloseGraph End. 6. Список использованных источников 1. Грис Д. Конструирование компиляторов для цифровых вычислительных машин.

М. Мир, 1975. 2. Шамашов М.А. Основные структуры данных и алгоритмы компиляции. Самара Университет Наяновой, 1999. 3. Шамашов М.А. Теория формальных языков.

Грамматики и автоматы.

Самара Университет Наяновой, 1996. 4. Интернет сайт WWW.CodeNet.ru.