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

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

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

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

Выполнил:
студент группы 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, иначе построение закончено.

После построения множеств L(U) и R(U) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами ^ н и ^ к (начало и конец цепочки). Для них определены следующие отношения предшествования:

^ н < a, " aÎ V, если $ SÞ *ax, где SÎ VN, xÎ V* или (с другой стороны) если aÎ L(S);

^ к > a, " aÎ V, если $ SÞ *xa, где SÎ VN, xÎ V* или (с другой стороны) если aÎ R(S).

Грамматикой операторного предшествования называется приведенная КС-грамматика без l -правил (e-правил), в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов (включая символы ^ н и ^ к).

Отношения предшествования для грамматики операторного предшествования G(VN,VT,P,S) задаются следующим образом:

·     a = b, если и только если существует правило U® xaby Î P или правило U® xaCby, где a,bÎ VT, U,CÎ VN, x,yÎ V*;

·     a < b, если и только если существует правило U® xaCy Î P и вывод CÞ *bz или вывод CÞ *Dbz, где a,bÎ VT, U,C,DÎ VN, x,y,zÎ V*;

·     a > b, если и только если существует правило U® xCby Î P и вывод CÞ *za или вывод CÞ *zaD, где a,bÎ VT, U,C,DÎ VN, x,y,zÎ V*.

В грамматике операторного предшествования различные порождающие правила имеют разные правые части. Для грамматики операторного предшествования тоже строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - Lt(U) или Rt(U):

·     Lt(U) = t, где tÎ VT, U,CÎ VN, zÎ V*;

·     Rt(U) = $ UÞ *zt или $ UÞ *ztC , где tÎ VT, U,CÎ VN, zÎ V*.

Тогда определения отношений операторного предшествования будут выглядеть так:

·     a = b, если $ правило U® xaby Î P или правило U® xaCby, где a,bÎ VT, U,CÎ VN, x,yÎ V*;

·     a < b, если $ правило U® xaCy Î P и bÎ Lt(C), где a,bÎ VT, U,CÎ VN, x,yÎ V*;

·     a > b, если $ правило U® xCby Î P и aÎ Rt(C), где a,bÎ VT, U,CÎ VN, x,yÎ V*.

В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

Для нахождения множеств Lt(U) и Rt(U) используется следующий алгоритм:

Шаг 1. Для каждого нетерминального символа грамматики U строятся множества L(U) и R(U).

Шаг 2. Для каждого нетерминального символа грамматики U ищутся правила вида U® tz и U® Ctz, где tÎ VT, CÎ VN, zÎ V*; терминальные символы t включаются во множество Lt(U). Аналогично для множества Rt(U) ищутся правила вида U® zt и U® ztC.

Шаг 3. Просматривается множество L(U), в которое входят символы U’,U”,... Множество Lt(U) дополняется символами, входящими в Lt(U’), Lt(U”), ... и не входящими в Lt(U). Аналогичная операция выполняется и для множества Rt(U) на основе множества R(U).

Для практического использования матрицу предшествования дополняют символами ^ н и ^ к (начало и конец цепочки). Для них определены следующие отношения предшествования:

^ н < a, " aÎ VT, если $ SÞ *ax или $ SÞ *Cax, где S,CÎ VN, xÎ V* или если aÎ Lt(S);

^ к > a, " aÎ VT, если $ SÞ *xa или $ SÞ *xaC, где S,CÎ VN, xÎ V* или если aÎ Rt(S).

Построим матрицу предшествования для грамматики операторного предшествования.

Рассмотрим в качестве примера грамматику G({S,B,T,J},{-,&,^,(,),p},P,S): (Терминалы выделены жирным шрифтом)

P: S ® -B (правило 1)
B ® T | B&T (правила 2 и 3)
T ® J | T^J (правила 4 и 5)
J ® (B) | p (правила 6 и 7)

Видно, что эта грамматика является грамматикой операторного предшествования.

Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики. Результат построения приведен в табл. 2.

На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики. Результат (второй и третий шаги построения) приведен в табл. 3.

Таблица 2.

Множества крайних правых и крайних левых символов грамматики (по шагам построения)

Таблица 3.

Множества крайних правых и левых терминальных символов грамматики (по шагам построения)

Страницы: 1, 2