ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по курсу "Информационные технологии" на тему "Построение функции предшествования по заданной КС-грамматике"
РЕФЕРАТ
Курсовой проект
Пояснительная записка: 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;
Процедуры и функции (основные):
Ввод грамматики осуществляется функцией:
Function InputText:Boolean;
Для синтаксического анализа КС-грамматики используется процедура:
Procedure Check;
Для нахождения «левых» и «правых» используется процедура:
Procedure SearchLR;
Построение матрицы предшествования выполняет процедура:
Procedure Matrix;
Построение функции предшествования осуществляется процедурой:
Procedure FuncPrecede;
3. Грамматики предшествования
КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:
· простого предшествования;
· расширенного предшествования;
· слабого предшествования;
· смешанной стратегии предшествования;
· операторного предшествования.
Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.
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), если