- •4. Эквивалентные преобразования кс- и а-грамматик
- •4.1. Декомпозиция правил грамматики
- •4.2. Исключение тупиков
- •4.3. Обобщенные кс-грамматики и приведение их к удлиняющей
- •4.4. Устранение левой рекурсии и левая факторизация
- •5. Свойства автоматных и контекстно-свободных
- •5.1. Общий вид цепочек а-языков
- •5.2. Общий вид цепочек кс-языков
- •5.3. Операции над языками
- •5.3.1. Операции над кс-языками
- •5.3.2. Операции над а-языками
- •5.3.3. Выводы для практики
- •5.4. Неоднозначность кс-грамматик и языков
- •6. Автоматы и преобразователи с магазинной
- •6.1. Основные определения
- •6. 2. Эквивалентность мп-автоматов и кс-грамматик
- •6. 3. Детерминированные мп-автоматы и кс-языки
- •6. 4. Преобразователи с магазинной памятью
- •6. 5. Моделирование мп-преобразователей
5.3.3. Выводы для практики
В результате операций над языками получается новое множество цепочек, то есть новый язык, который “собран из кусков”, состоит из частей исходных языков. С практической точки зрения очень важно, что язык можно разложить на более простые языки и формировать сложный язык на базе простых языков и операций над ними. Так если нам известен язык букв Lб (любая латинская буква) и язык цифр Lц , то можно совершенно тривиально определить язык идентификаторов Lи конкатенацию языка букв и итерацию объединения языка букв и языка цифр:
Lи = Lб (Lб Lц ).
Отметим, что при реализации на ЭВМ программы синтаксического анализа различных языков лучше всего представлять в виде логических процедур-функций, дающих положительный ответ в случае принадлежности цепочки или ее фрагмента рассматриваемому языку и отрицательный при обнаружении ошибок. При таком построении итерация языка подменяется вызовом соответствующей процедуры внутри цикла; конкатенация - последовательным вызовом процедур анализа составляющих языков; объединение - альтернативным вызовом процедур; подстановка - заменой анализа терминала на процедуру анализа подставляемого языка.
Пример 5.4. Рассмотри простейший язык записи результатов шахматного матча для одного из его участников, цепочки которого имеют вид:
+ победы = ничьи - поражения;
где победы, ничьи и поражения представляются в виде целых констант без знака или имен переменных (идентификаторов). Данный язык
L = L+ Lблок L= Lблок L - Lблок L; ,
где L + = {+}, L = = {=}, L - = {-}, L блок = L и L к , Lи = Lб (Lб Lц ) , L к = Lц+, Lб = {a,b,...,y,z}, Lц = {0,1,...,9}, L;={;}.
Ниже представлена программа на языке Паскаль, реализующая синтаксический анализ цепочек предложенного языка. В ней выделены процедуры-функции анализа букв, цифр, идентификаторов, констант и блоков. Предусмотрен ввод серии строк для анализа и признаком конца тестирования данного анализатора служит ввод пустой строки. В процессе обработки строк языка осуществляется формирование массивов идентификаторов и констант, которые выводятся по завершении тестирования. Кроме фатальных ошибок, приводящих к завершению обработки текущей строки, предусмотрены сообщения об ошибках - предупреждениях о переполнении констант и идентификаторов. Позиции ошибок вместе с сообщениями о них формируют массив ошибок MEr, который выводится по завершению анализа строки.
program analppn;
uses TPCrt;
type Idn = string[8]; { тип для идентификатора }
CEr = 0..4; { код ошибки }
var
Str: string; { входная строка }
Lst: byte absolute Str; { количество символов в строке }
Ist: word; { индекс по входной строке }
Midn: array [0..100] of idn; { массив идентификаторов }
Mcon: array [0..100] of word; { массив констант }
Imi, Imc: word; { индексы массивов midn и mcon }
s: char; n: byte; { рабочие переменная }
MEr: array [0..4] of string; { строки сообщений об ошибках}
IEr: word; { индекс ошибок }
cod: CEr;
i: word;
const
{ сообщения в программе }
WroIdn = ' Количество символов в идентификаторе > 8-ми';
WroCon = ' Переполнение константы';
ErVic = ' Ошибка в победах';
ErDraw = ' Ошибка в ничьих';
ErDet = ' Ошибка в поражениях';
ErFin = ' Ожидается ";"';
OK = ' Строка синтаксически верна';
Inq = ' Введите строку >';
procedure Blank;
(* пропуск управляющих символов и пробелов *)
begin
while (Ist <= Lst) and (Str[Ist] <= #32) do inc(Ist)
end {Blank};
function Let (s:char): boolean;
(* контроль букв *)
begin
Let:=(UpCase(s) >= 'A') and (UpCase(s) <= 'Z')
end { Let };
function Dig (s: char; var n: byte): boolean;
(* контроль цифр *)
begin
if (s >= '0') and (s <= '9') then begin
n:=ord(s)-48 {-ord('0')}; Dig:=true end
else Dig:=false
end {Dig};
function Ident (var id: Idn): boolean;
(* анализ идентификатора *)
var
i: word;
begin
Blank; i:=Ist; id:=''; Ident:=false;
if Let(Str[Ist]) then begin
while Let(Str[Ist]) or Dig(Str[Ist],n) do begin
if (Ist-i) < 8 then id:=id+Str[Ist];
inc(Ist);
end;
if (Ist-i) > 7 then begin
inc(Ier); MEr[Ier]:=WroIdn; MEr[0,i+7]:='^'
end;
Ident:=true; Blank
end
end {Ident};
function Cons (var c: word): boolean;
(* анализ константы *)
var
ov: boolean; { признак переполнения }
begin Blank;
ov:=false; c:=0; Cons:=false;
while Dig(Str[Ist],n) do begin
Cons:=true;
if not(ov) then
if (c < 6553) or ((c=6553) and (n <= 5)) then c:=c*10+n
else begin
ov:=true; inc(Ier); MEr[Ier]:=WroCon; MEr[0,Ist]:='^'
end;
inc(Ist);
end; Blank;
end {Cons};
function Block (s: char): boolean;
(* анализ блока, начинающегося с символа-параметра s и
содержащего идентификатор или константу в качестве продолжения *)
begin
block:=true; Blank;
if Str[Ist] = s then begin inc(Ist);
if Ident(Midn[Imi]) then inc(Imi)
else
if Cons(Mcon[Imc]) then inc(Imc)
else begin MEr[0,Ist]:='^'; block:=false end
end
else begin MEr[0,Ist]:='^'; block:=false end
end {Block};
function Anal: CEr;
(* анализ строки c возвратом кода ошибки *)
begin
Anal:=0;
if not(Block('+')) then begin Anal:=1; exit end;
if not(Block('=')) then begin Anal:=2; exit end;
if not(Block('-')) then begin Anal:=3; exit end;
if Str[Ist] <> ';' then begin MEr[0,Ist]:='^'; Anal:=4 end
end {analizer};
procedure Parser;
(* анализ с выдачей сообщений об ошибках *)
begin
Ier:=0; Ist:=1;
FillChar(MEr[0,1],80,' '); MEr[0,0]:=#80;
cod:=Anal;
WriteLn(MEr[0]);
for i:=1 to Ier do
WriteLn(MEr[i]);
case cod of
0: WriteLn(OK);
1: WriteLn(ErVic);
2: WriteLn(ErDraw);
3: WriteLn(ErDet);
4: WriteLn(ErFin)
end
end {Parser};
begin
Imi:=0; Imc:=0;
while true do begin
WriteLn(Inq);
ReadLn(Str);
IF Lst = 0 then break;
Parser;
end;
if (Imi > 0) or (Imc > 0) then begin
WriteLn(' ИДЕНТИФИКАТОРЫ КОНСТАНТЫ');
i:=0;
repeat
if i < Imi then Write(Midn[i]:11)
else Write(' ':11);
if i < Imc then Write(Mcon[i]:15);
WriteLn; inc(i);
until (i >= Imi) and (i >= Imc)
end;
ReadKey;
end.