САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА
Кафедра информационных систем и технологий
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту по курсу
"Информационные технологии" на тему
"Построение функции предшествования по заданной КС-грамматике"
Выполнил:
студент группы 634 Абраров А.М.
Руководитель проекта:
Шамашов М.А.
Дата сдачи:
Оценка:
Самара 2001 г.
РЕФЕРАТ
Курсовой проект
Пояснительная записка: 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
По заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа.
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;
Процедуры и функции (основные):
Ввод грамматики осуществляется функцией:
Function InputText:Boolean;
Для синтаксического анализа КС-грамматики используется процедура:
Procedure Check;
Для нахождения «левых» и «правых» используется процедура:
Procedure SearchLR;
Построение матрицы предшествования выполняет процедура:
Procedure Matrix;
Построение функции предшествования осуществляется процедурой:
Procedure FuncPrecede;
КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:
· простого предшествования;
· расширенного предшествования;
· слабого предшествования;
· смешанной стратегии предшествования;
· операторного предшествования.
Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.
3.1 Грамматики простого предшествования
Грамматикой простого предшествования называют такую КС-грамматику 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).
3.2 Грамматики операторного предшествования
Грамматикой операторного предшествования называется приведенная КС-грамматика без l -правил (e-правил), в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов (включая символы ^ н и ^ к).
Отношения предшествования для грамматики операторного предшествования G(VN,VT,P,S) задаются следующим образом:
· a = b, если и только если существует правило U® xaby Î P или правило U® xaCby, где a,bÎ VT, U,CÎ VN, x,yÎ V*;