Синтаксический анализ А-языков

Схема алгоритма и программа, анализирующая принадлежность цепочки заданному А-языку, строиться тривиально по графу состояний А-грамматики. Каждой вершине графа, кроме заключительной и “ошибочной”, соответствует блок выбора очередного символа анализируемой цепочки. Каждому ребру, точнее пометке ребра,- блок анализа символа с последующим переходом к тому или иному блоку выбора. Каждому пути по графу соответствует путь по схеме и программе. Процесс построения анализатора рассмотрим на примере анализатора чисел с фиксированной точкой.

Числа с фиксированной точкой имеют целую и дробную часть и могут описываться, например, следующей автоматной грамматикой:

S®+Nï-Nï0Fï1Cï…ï9Cï0T

T®.D

N®1Cï…ï9Cï0T

C®0Fï…ï9Fï0Cï…ï9Cï.D

D®0Dï…ï9Dï0Fï…ï9F .

Для приведения грамматики к вполне детерминированной форме предварительно выполняется ее модификация: вводится предконечное состояние F’, символ конца цепочки - ^, затем все правила вида: A®a заменяются на A®aF’ и добавляется правило F’®^F. Для обозначения ошибочного состояния вводится нетерминал - E.

Теорема: Для любой А-грамматики существует эквивалентная ей А-грамматика во вполне детерминированной форме.

Доказательство: Доказательство включает две части: доказательство существования такой грамматики (оно конструктивное, то есть предлагается алгоритм построения для произвольной автоматной грамматики, автоматной грамматики во вполне детерминированной форме) и доказательство того факта, что построенная грамматика эквивалентна исходной. В этом пункте докажем первую часть теоремы.

Пусть имеется А-грамматика G=<S,V_T,V_N,R>. Эта грамматика приводится к модифицированной форме. В результате получим:V_T={^,…}; V_N={S,F^',F,…}

А-грамматика во вполне детерминированной форме из модифицированной строится следующим образом: 1.G=<V_T,V_N,<S>,R>, <S>=S,<F>=F, <F^'>=F^'

Если в исходной грамматике имеется правило вида: A®aB, то в новой, построенной грамматике будет правило:<A>®a<B>.

Если в исходной грамматике имеются правила вида: A®aB₁ï…ïaB_n, то в результирующей грамматике будет правило: <A>®a<B₁…B_n>

Для появившихся новых нетерминалов добавляются правила вида: <B₁…B_n>®c<C₁…C_n>, если в исходной грамматике имеются правила следующего вида: B₁®cC₁,….B₁®cCn_{. . .} B_n®cC1,….B_n®cC_n

При этом в новый нетерминал нетерминалы C_i включаются один раз. В результате такого построения для любого терминала а существует единственное правило вида: <…A…>®a<…B…>. 

Используя описанный алгоритм, приведем к вполне детерминированной формe А-грамматику чисел с фиксированной точкой.

<S>®+<N>ï-<N>ï 0<FT>ï1<C>ï…ï9<C>

<T>®.<D>

<N>®1<C>ï…ï9<C>ï0<T>

<C>®0<FC>.ï…ï9<FC>ï.<D>

<D>®0<FD>ï…ï9<FD>

<F^’>®^<F>

<F^’T>®^<F>ï.<D>

<F^’C>®^<F>ï0<F^’C>ï…ï9<F^’C>ï.<D>

<F^’D>®^<F>ï0<F^’D>ï…ï9<F^’D>. Переобозначим нетерминалы следующим образом: <S> - S, <N> - A, <F^”T> - B, <C> - C, <D> - D, <T> - G,

<F^’C> - H, <F^’D> - I. Получим: S®+Aï-Aï0Bï1Cï..ï9C

A®1Cï..ï9Cï0G

C®0Hï..ï9Hï.D

G®.D

D®0Iï…ï9I

B®.Dï;F

H®0Hï…ï9Hï.D

I®0Iï…ï9Iï;F Граф для полученной грамматики имеет вид:

Рисунок 1.5 – Граф состояний А-грамматики чисел с фиксированной точкой

Анализатор - это программа, позволяющая определить принадлежность цепочки языку, порождаемому некоторой грамматикой. Ниже приведена программа, анализирующая правильность написания чисел с фиксированной точкой (автомат Глини) на языке Turbo Pascal.

Type Tsost: (S,A,B,C,D,G,H,I,F,E);

Var Sost : Tsost; (*Текущее соcтояние*)

St : String[255];(*Входная строка-цепочка символов языка*)

j : integer;(*Тек. номер позиции в строке*)

k : char;(*Тек. символ строки*)

x,z,q : real;(*x- число,z – знак, q- значение порядка дробной части числа*)

Begin

J:=1; sost:=S; read(st);

X:=0; z:=+1.; q:=0.1;

While((sost<>F) and(sost<>E)and(j<>length(st))) do

Begin

k:=st[j};

Inc(j);

Case sost of

S: case k of

‘-‘: begin

sost:=A;

z:=-1;

end;

‘+’: begin

sost:=A;

end;

‘0’: begin

sost:=B;

end;

‘1’..’9’: begin

sost:=C;

x:=x*10.+(ORD(k)-48)

{48=ORD(0)}

end;

else

begin writeln(‘Ошибка-ожидается знак или цифра’);

sost:=E;

end;

end;{case}

A: case k of

‘0’ : begin

sost:=G;

end;

‘1’..’9’ : begin

sost:=C;

x:=x*10.0+(ORD(k)-48);

end;

else begin writeln(‘Ошибка в целой части числа’);

sost:=E;

end:

end;{case}

B:case k of

‘.’ : begin

sost:=D;

end;

‘;’ : sost:=F;

else(*сообщение об ошибке и sost:=E*)

end;{case}

C: case k of

‘0’..’9’: begin

sost:=H;

x:=x*10.0+(ORD(k)-48);

end;

‘.’ : begin

Sost:=E;

еnd;

else begin writeln(‘Ошибка! Ожидается точка’);

sost:=E;

end;

end;{case}

G: if k=’.’ Then sost:=D

еlse begin writeln(‘Ошибка! Ожидается точка’);

sost:=E;

end;

H: case k of

‘0’..’9’ : begin

Sost:=H;

x:=x*10.+(ORD(k)-48);

end;

‘.’ : sost:=D;

else begin writeln(‘Ошибка! Ожидается точка или цифра’);

sost:=E;

end;

end;{case}

D: case k of

‘0’..’9’ : begin

sost:=I;

x:=x+(ORD(k)-48)*q; q:=q/10;

else begin writeln(‘Ошибка!’);

sost:=E;

end;

end;{case}

I: case k of

‘0’..’9’: begin

sost:=I;

x:=x+(ORD(k)-48)*q: q:=q/10:

end;

‘;’ : sost:=F;

else begin writeln(‘Ошибка!’);

sost:=E;

end;

end;{case}

F: writeln(‘Число сформировано’);

X:=x*z;

E : writeln(‘Обнаружена ошибка’);

end{case по состояниям};

end {while};

end.

Семантикой для данного анализатора является значение числа.

Способы включения семантики:

1) применение функции Val(S:String; Var x; Var Code:Integer) (добавляется в состояние F);

2) последовательное формирование числа при переходе автомата в соответствующие состояния:

x:=0, z:=1, q:=0.1

x:=z*(x*10+(значение текущей цифры числа х))

x:=x+(значение текущей цифры числа х)*q, где x – формируемое число, z- знак числа, q – значение прядка текущей цифры дробной части числа.

Алгоритм построения анализатора:

1) Составляется автоматная грамматика.

2) Если полученная грамматика недетерминированная, то она приводится к вполне детерминированной форме.

3) По полученной грамматике строится граф состояний.

4) В соответствие с графом пишется программа.

5) Осуществляется добавление семантических правил в анализатор.