САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА Кафедра информационных систем и технологий
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по курсу "Информационные технологии" на тему "Построение функции предшествования по заданной КС-грамматике"
Выполнил: студент группы 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
По заданной КС-грамматике построить отношение простого или операторного предшествования и функцию предшествования, используя граф линеаризации и алгоритм пересчета с визуализацией шагов построения графа.
Типы:
Для хранения терминалов и терминалов используется тип:
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;
КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:
· простого предшествования;
· расширенного предшествования;
· слабого предшествования;
· смешанной стратегии предшествования;
· операторного предшествования.
Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.
Грамматикой простого предшествования называют такую КС-грамматику 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,TÎ V, zÎ V* - множество крайних левых символов относительно нетерминального символа U (цепочка z может быть и пустой цепочкой);
· R(U) = T , 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, иначе построение закончено.
Страницы: 1, 2, 3, 4, 5
