ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовому проекту по курсу "Информационные технологии" на тему "Построение функции предшествования по заданной КС-грамматике"

РЕФЕРАТ

Курсовой проект

Пояснительная записка: 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), если