САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П.

КОРОЛЕВА

Кафедра информационных систем и технологий

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по курсу

"Информационные технологии" на тему

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

Выполнил:

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