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

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 в которой: