РЕФЕРАТ
Курсовой проект
Пояснительная записка: 30 с., 5 рис., 3 схем программ и алгоритмов, 3 библиографического источника.
ТЕРМИНАЛ, НЕТЕРМИНАЛ, ГРАММАТИКА, ФУНКЦИЯ ПРЕДШЕСТВОВАНИ, ГРАФ, ЛИНЕАРИЗАЦИЯ.
В курсовом проекте разработан алгоритм и соответствующая ему программа, позволяющая по введённой пользователем КС-грамматике построить функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа. Грамматика может быть введена как в самой программе, так и из текстового файла. Также существует возможность сохранения результата. Программа написана на языке Pascal 7.0.
СОДЕРЖАНИЕ
СОДЕРЖАНИЕ...................................................................................................................................................................... 3
1. Постановка задачи............................................................................................................................................... 4
2. Описание структуры данных..................................................................................................................... 5
3. Грамматики предшествования................................................................................................................. 6
3.1 Грамматики простого предшествования................................................................... 6
3.2 Грамматики операторного предшествования........................................................ 8
3.3 Пример построения матрицы предшествования................................................. 10
3.4 Линеаризация матрицы предшествования.............................................................. 13
4. Руководство пользователя....................................................................................................................... 13
5. Текст программы................................................................................................................................................. 15
6. Список использованных источников............................................................................................. 30
1. Постановка задачи
По заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа.
2. Описание структуры данных
Типы:
Для хранения терминалов и терминалов используется тип:
notTerm=^List;
List=Record{список терминалов и нетерминалов}
Name:Str10;{терминал или нетерминал}
Next:notTerm;
End;
Для хранения грамматики (текста) используется:
strBuf=array [1..800] of Char;
Матрица предшествования:
matrixPr=array [1..20,1..20] of 0..4;
Функция предшествования:
FuncPr=array [1..2,1..20] of Byte;
Процедуры и функции (основные):
Ввод грамматики осуществляется функцией:
FunctionInputText:Boolean;
Для синтаксического анализа КС-грамматики используется процедура:
Procedure Check;
Для нахождения «левых» и «правых» используется процедура:
Procedure SearchLR;
Построение матрицы предшествования выполняет процедура:
Procedure Matrix;
Построение функции предшествования осуществляется процедурой:
Procedure FuncPrecede;
Грамматики предшествования
КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:
· простого предшествования;
· расширенного предшествования;
· слабого предшествования;
· смешанной стратегии предшествования;
· операторного предшествования.
Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.
Грамматики простого предшествования
Грамматикой простого предшествования называют такую КС-грамматику G (VN, VT, P,S), V = VTÈ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Î V *.
2. Различные порождающие правила имеют разные правые части.
Отношения =, < и > называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования - это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если Si > Sj, то не обязательно, что Sj < Si (поэтому знаки предшествования иногда помечают специальной точкой: =×, <×, × >)
Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:
· Si < Si+1, если символ Si+1 - крайний левый символ некоторой основы;
· Si > Si+1, если символ Si - крайний правый символ некоторой основы;
· Si = Si+1, если символы Si и Si+1 принадлежат одной основе.
Исходя из этих соотношений выполняется разбор строки для грамматики предшествования.
На основании отношений предшествования строят матрицу предшествования грамматики. Строки матрицы предшествования помечаются первыми символами, столбцы - вторыми символами отношений предшествования, а в клетки матрицы на пересечении соответствующих столбца и строки помещаются знаки отношений. При этом пустые клетки матрицы говорят о том, что между данными символами нет ни одного отношения предшествования.
Матрицу предшествования грамматики можно построить, опираясь непосредственно на определения отношений предшествования, но удобнее воспользоваться двумя дополнительными множествами - множеством крайних левых и множеством крайних правых символов относительно нетерминалов грамматики. Эти множества определяются следующим образом:
· L (U) = {T | $ UÞ *Tz}, U,TÎ V, zÎ V * - множество крайних левых символов относительно нетерминального символа U (цепочка z может быть и пустой цепочкой);
· R (U) = {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Î L (D), где U,DÎ VN, x,yÎ V *;
· Si > Sj (" Si,SjÎ V), если $ правило U® xCSjy Î P и SiÎ R (C) или $ правило U® xCDy Î P и SiÎ R (C), SjÎ L (D), где U,C,DÎ VN, x,yÎ V *.
Такое определение отношений удобнее на практике, так как не требует построения выводов, а множества L (U) и R (U) могут быть построены для каждого нетерминального символа UÎ VN по очень простому алгоритму:
Шаг 1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части. Во множество L (U) включаем самый левый символ из правой части правил, а во множество R (U) - самый крайний символ правой части. Переходи к шагу 2.
Шаг 2. Для каждого нетерминального символа U: если множество L (U) содержит нетерминальные символы грамматики U’,U”,..., то его надо дополнить символами, входящими в соответствующие множества L (U’), L (U”),... и не входящими в L (U). Ту же операцию надо выполнить для R (U).
Шаг 3. Если на предыдущем шаге хотя бы одно множество L (U) или R (U) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено.
После построения множеств L (U) и R (U) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами ^ н и ^ к (начало и конец цепочки). Для них определены следующие отношения предшествования:
^ н < a, " aÎ V, если $ SÞ *ax, где SÎ VN, xÎ V * или (с другой стороны) если aÎ L (S);
^ к > a, " aÎ V, если $ SÞ *xa, где SÎ VN, xÎ V * или (с другой стороны) если aÎ R (S).