Построение функции предшествования по заданной КС-грамматике

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА
Кафедра информационных систем и технологий

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

Выполнил:
студент группы 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

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.    Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:

·     S_i = S_j (" S_i,S_jÎV), если и только если $ правило U® xS_iS_jy Î P, где UÎ VN, x,yÎ V^*;

·     S_i < S_j (" S_i,S_jÎV), если и только если $ правило U® xS_iDy Î P и вывод DÞ *S_jz, где U,DÎ VN, x,y,zÎ V^*;

·     S_i > S_j (" S_i,S_jÎV) , если и только если $ правило U® xCS_jy Î P и вывод CÞ *zS_i или $ правило U® xCDy Î P и выводы CÞ *zS_i и DÞ *S_jw, где U,C,DÎ VN, x,y,z,wÎ V^*.