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

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

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

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) Осуществляется добавление семантических правил в анализатор.