|
|
< |
= |
< |
|
|||
|
) |
|
> |
> |
|
> |
|
> |
|
P |
|
> |
> |
|
> |
|
> |
|
^ н |
< |
|
|
|
|
|
|
Посмотрим, как заполняется матрица предшествования в табл. 4 на примере символа &. В правиле грамматики B ® B&T (правило 3) этот символ стоит слева от нетерминального символа T. В множество Lt(T) входят символы: ^ ( p. Ставим знак < в клетках матрицы, соответствующих этим символам, в строке для символа &. В то же время в этом же правиле символ & стоит справа от нетерминального символа B. В множество Rt(B) входят символы: & ^ ) p. Ставим знак > в клетках матрицы, соответствующим этим символам, в столбце для символа &. Больше символ & ни в каком правиле не встречается, значит заполнение матрицы для него закончено, берем следующий символ и продолжаем заполнять матрицу таким же методом.
Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Тогда получим следующий вид правил:
P: E ® -E
(правило 1)
E ® E | E&E (правила 2 и 3)
E ® E | E^E (правила 4 и 5)
E ® (E) | p (правила 6 и 7)
Это преобразование не ведет к созданию эквивалентной грамматики и выполняется только после построения всех множеств и матрицы предшествования. Само преобразование выполняется только с целью более эффективного выполнения алгоритма разбора, в который уже заложены необходимые данные о порядке применения правил при создании матрицы предшествования.
3.4 Линеаризация матрицы предшествования
Для компактного хранения матрицы предшествования часто можно использовать следующий прием. По матрице M[n][n], элементы которой принимают только три значения (< = >), попытаемся построить два целочисленных вектора f и g:
M[i][j] равно >, если f[i]>g[j]
M[i][j] равно <, если f[i]<g[j]
M[i][j] равно =, если f[i]=g[j]
Для получения этих векторов используется следующий метод: построить ориентированный граф, содержащий n вершин типа F и n вершин типа G;
- построить ребро графа F[i]->G[j], если i > j
- построить ребро графа F[i]<-G[j], если i < j
- склеить вершины F[i] и G[j], если i = j
Если полученный граф циклический, то линеаризация невозможна. Иначе положить f[i] равным длине самого длинного пути из F[i], g[i] равным длине самого длинного пути из G[i].
4. Руководство пользователя
После запуска программы пользователю предлагается ввести КС-грамматику (ограничение при вводе: длина нетерминала не больше восьми символов). Ввод строки заканчивается нажатием клавиши Enter. Для определения в программе нетерминала используются символы ‘<’ и ‘>’ непосредственно между которыми находится нетерминал, знак или ‘|’, знак присвоить ‘:=’. Новая строка обязательно должна начинаться с нетерминала и последующим символом(и) ‘:=’.
Для начала анализа введённой КС-грамматике нужно нажать клавишу F5 или выбрать в меню пункт «Запуск» (меню вызывается нажатием F9). Перед тем как начать построение матрицы предшествования производится синтаксический анализ введенного текста.
Возможные ошибки при вводе грамматики:
После символа ‘|’ должен обязательно следовать терминал или нетерминал.
В грамматике описан нетерминал <F>, но он нигде не используется (отсутствует в правой части).
В грамматике отсутствует описание нетерминала <ZZZ> (отсутствует в правой части)
Если грамматика введена верно, то начинается построение матрицы (алгоритм описан выше). При возникновении ошибки (один или несколько (не)терминалов имеют более чем одно отношение предшествования) выводится сообщение и в соответствующую ячейку записывается символ Х.
После этого выполняется линеаризация матрицы с помощью графа: для упрощения алгоритма в матрице сначала ведется поиск отношений = при нахождении таковых выполняется склеивание соответствующих вершин. Эта операция избавляет нас от рутинных действий связанных с «перестановкой» связей. Также упрощается описание графа в программе: надобность в хранении связей отсутствует - необходимо лишь хранить количество входящих и выходящих ребер. При построении векторов граф, проверяется на цикличность (при существовании цикла выводится сообщении о невозможности построения функции предшествования).
5. Текст программы
Program KP;
Uses TpCrt,Graph,GrText,DataUnit;
Const Txt='По заданной КС-грамматике построить отношение простого'+
' или операторного предшествования и функцию предшествования,'+
' используя граф линеаризации и алгоритм пересчета с визуализацией'+
' шагов построения графа';
Errors : array [0..10] of String[34] ={ошибки}
(' КС-грамматика синтаксически верна',{0}
' Ожидается ~"<"', {1}
' Ожидается ~">"', {2}
' Ожидается ~":="', {3}
' Требуется нетерминал', {4}
' Требуется терминал', {5}
' Неопределенный нетерминал', {6}
' Неиспользуемый нетерминал', {7}
' Требуется терминал или нетерминал',{8}
' Многоопределенный нетерминал', {9}
' Найдены недопустимые символы'); {10}
menu:array[1..5] of string[10]=
('Открыть','Сохранить','Запуск','Информация','Выход');
Type
notTerm=^List;
List=Record{список терминалов и нетерминалов}
Name:Str10;{терминал или нетерминал}
Next:notTerm;
End;
strBuf=array [1..800] of Char;
matrixPr=array [1..20,1..20] of 0..4;
Var i:Byte;{текущая позиция}
s:String;{текущая строка}
Len:Byte absolute s;
str_:strBuf;{общий буфер для текста}
LenStr:Integer;{всего символов в буфере}
CLine,{кол-во строк}
y:Byte;{текущая строка}
CTerm:Byte;{кол-во нетерминалов}
CTrmNotTrm:Byte;{кол-во нетерминалов и терминалов}
notTerminalS:NotTerm;{нетерминалы встречающиеся в правых частях}
notTerminalL:NotTerm;{нетерминалы в левой части}
Trm_notTrm:NotTerm;{список терминалов и нетерминалов}
LTN:NotTerm;{левые}
RTN:NotTerm;{правые}
tmp:NotTerm;{временная переменная}
matrixPrecede:matrixPr;
LenWin:Byte;{ширина окна}
{$I Dinamic.inc} {процедуры для работы с динамическими переменными}
{$I GraphPr.inc} {графический интерфейс}
{$I ServFunc.inc} {дополнительные процедуры обработки строки}
{----------------------------------------------------------------------------}
Procedure Blank;
(* пропуск управляющих символов и пробелов *)
Begin
While (i<=Len) and (S[i] = #32) do inc(i);
End;
{}
Function Let(s:Char):Boolean;
(* контроль букв *)
Begin
Let:=((s) >= 'A') and ((s) <= 'Z') or (s in RusLetters);
End;
{}
Function Dig (s:Char;Var n:Byte):Boolean;
(* контроль цифр *)
Begin
If (s >= '0') and (s <= '9') Then
Begin
n:=ord(s)-48;
Dig:=true
End
Else Dig:=false
End;
{}
Function Terminal (Var term:String):Boolean;
(* поиск терминала *)
Begin
term:='';
If i<=Len Then
While (i<=Len) and (S[i] in Digits+LatLetters+Punctuation+Service+RusLetters)
and not (s[i]='<') and not (s[i]='>') and not (s[i]='|') Do
Begin
term:=term+s[i];
inc(i);
End;
Terminal:=term > '';
End;
{}
Function notTerminal (Var term:String):Boolean;
(* поиск нетерминала *)
Var
j:word;
n:Byte;
Ex:Boolean;
Begin
Blank;
j:=i;
term:='';
Ex:=True;
If i<=Length(s) Then
If Let(S[i]) Then
Begin
While (i<=Length(s)) and Let(S[i]) or Dig(S[i],n) do
Begin
If (i-j) < 9 Then term:=term+S[i];
inc(i);
End;
If (i-j) > 8 Then
Ex:=False
Else
Blank;
End
Else
Ex:=False
Else
Ex:=False;
notTerminal:=Ex;
End;
{}
Procedure Check;
Var term:String;
Exist,Ex:Boolean;
notT:List;
k:Byte;
Label notTerminalOrTerminal,
OrS,LineS,EndS,Start,New,Gluk;
Begin
Goto Start;
New:{при возникновении ошибки}
DeleteList(NotTerminalS);
DeleteList(NotTerminalL);
DeleteList(Trm_NotTrm);
If not InputText Then Exit;
Start:{один раз}
i:=1;
y:=1;
k:=1;
CTerm:=0;
CTrmNotTrm:=0;
PosStr(1,s);{первая строка}
При использовании материалов активная ссылка на источник обязательна.