1.11.7. СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР

Задача синтаксического анализатора, находящегося в модуле CMPPRS, - преобразовать поток лексем в абстрактную программу, т.е. в дерево грамматического разбора.

Для выполнения синтаксического анализа, мы используем метод нисходящего грамматического разбора.

Рассмотрим, для примера, следующую грамматику:

$ Предложение = Подлежащее Сказуемое.

$ Подлежащее = "кошки" | "собаки".

$ Сказуемое = "спят" | "едят".

Пусть нам дана последовательность лексем

"собаки" "едят"

и мы хотим узнать, является ли она правильным предложением. Для этого мы должны узнать, может ли эта цепочка быть порождена нетерминалом Предложение. Но из грамматики следует, что множество цепочек, порождаемых нетерминалом Предложение, совпадает с множеством цепочек, порождаемых цепочкой двух нетерминалов Подлежащее Сказуемое. Таким образом, задача сводится к тому, чтобы проверить, нельзя ли от входной цепочки отщепить начало, которое порождается нетерминалом Подлежащее, а затем проверить, что остаток цепочки может быть порожден нетерминалом Сказуемое.

Как отщепить от цепочки начало, порождаемое нетерминалом Подлежащее? Очевидно, что для этого достаточно проверить, что цепочка лексем начинается с лексемы "кошки" или лексемы "собаки".

Таким образом, мы приходим к следующему методу анализа.

Каждому нетерминалу A в грамматике мы ставим в соответствие функцию A, имеющую следующее объявление:

$func? A e.Token = e.Rest;

Эта функция проверяет, что входная цепочка символов e.Token начинается с цепочки символов, выводимой из нетерминала A. Если это действительно так, то функция A отбрасывает от e.Token ее начало, выводимое из нетерминала A и выдает то, что останется, в качестве результата. Если же от e.Token невозможно отщепить начальную цепочку, выводимую из нетерминала A, то функция A выдает в качестве результата неуспех.

Конечно, описанный метод синтаксического анализа подходит только в том случае, если для любого нетерминала A и любой входной цепочки Z существует не более чем один способ отщепить от X цепочку, выводимую из A. Во многих случаях, тем не менее, грамматика может быть преобразована к такому виду, чтобы это ограничение выполнялось. За более подробным обсуждением этого вопроса мы отсылаем читателя к [Вир 85].

Руководствуясь вышеизложенными соображениями, мы можем определить функцию "Предложение", отщепляющую от цепочки символов начальную цепочку, выводимую из нетерминала Предложение, либо терпящую неуспех, если это невозможно.

$func? "Предложение" e.Token = e.Rest;

$func? "Подлежащее" e.Token = e.Rest;

$func? "Сказуемое" e.Token = e.Rest;

$func? Token? s? e.Token = e.Rest;

"Предложение" eZ =

<"Подлежащее" eZ> :: eZ,

<"Сказуемое" eZ> :: eZ,

= eZ;

"Подлежащее" eZ =

\{

<Token? "собаки" eZ> :: eZ = eZ;

<Token? "кошки" eZ> :: eZ = eZ;

};

"Сказуемое" eZ =

\{

<Token? "спят" eZ> :: eZ = eZ;

<Token? "едят" eZ> :: eZ = eZ;

};

Token? s? eZ =

eZ : s? eZ0

= eZ0;

Функция Token? введена для отщепления произвольных терминальных символов.

Теперь мы можем вернуться к рассмотрению модуля CMPPRS.

Здесь мы сталкиваемся с тремя дополнительными проблемами.

Во-первых, исходная программа поступает из сканера не вся целиком, а постепенно, лексема за лексемой. Поэтому аргументом каждой из функций грамматического анализа является не вся цепочка лексем, а только одна лексема, которая была прочитана последней. Эта лексема является первой лексемой из еще не проанализированного остатка программы. Точно так же, функции анализа выдают не весь остаток программы, а только первую лексему из остатка программы. При этом каждая лексема представлена не одним символом, а двумя.

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

$func A sC sI = sC sI tX;

где sC sI соответствует очередной лексеме, а tX - результат перевода отщепленной части программы в абстрактный синтаксис.

В третьих, если обнаруживается синтаксическая ошибка, синтаксический анализатор должен выдавать не просто неуспех, а ошибку вида $error(Oe), где Oe - сообщение, как-то описывающее ошибку. Поэтому функции анализа объявлены как безоткатные.

Абстрактная программа имеет следующий синтаксис:

$ t.Program = (Program t.Statement).

$ t.Statement =

$ (Assign s.Name t.Expr) |

$ (If t.Test t.Statement t.Statement) |

$ (While t.Test t.Statement) |

$ (Read s.Name) |

$ (Write t.Expr) |

$ (Seq t.Statement t.Statement)

$ (Skip).

$ t.Test = (Test s.Comp-Oper t.Expr t.Expr).

$ t.Expr =

$ (Const s.Value) |

$ (Name s.Name) |

$ (Op t.Oper t.Expr t.Expr).

$ s.Comp-Oper = Eq | Ne | Gt | Ge | Lt | Le.

$ s.Oper = Add | Sub | Div | Mul.

$ s.Name = s.Word.

$ s.Value = s.Int.

Таким образом, любая конструкция в абстрактном синтаксисе как правило принимает следующий вид:

(SkeyWord Ot1 Ot2 ... OtN)

где ключевое слово SkeyWord - это символ-слово, являющееся названием конструкции, а объектные термы Ot1, Ot2, ..., OtN - вложенные конструкции, тоже представленные в абстрактном синтаксисе. Соответствие между конструкциями в конкретном и абстрактном синтаксисе очевидно, и мы не будем останавливаться на этом вопросе более подробно.

Ниже приведена реализация модуля CMPPRS:

**

** File: CMPPRS.RF

**

$use CMPSCN;

$func Program sC sI = sC sI tX;

$func Statement-Seq sC sI = sC sI tX;

$func Rest-St-Seq sC sI tX0 = sC sI tX;

$func Statement sC sI = sC sI tX;

$func Test sC sI = sC sI tX;

$func Expr sC sI = sC sI tX;

$func Rest-Expr sC sI tX1 = sC sI tX;

$func Term sC sI = sC sI tX;

$func Rest-Term sC sI tX1 = sC sI tX;

$func Factor sC sI = sC sI tX;

$func Comp-Op sC sI = sC sI s.Comp-Oper;

$func? Add-Op? sC sI = sC sI s.Oper;

$func? Mul-Op? sC sI = sC sI s.Oper;

$func? Token? sI? sC sI = sC sI ;

$func Accept sI? sC sI = sC sI ;

$func? Name? sC sI = sC sI s.Name;

$func? Value? sC sI = sC sI s.Value;

 

Parse s.Chl =

<Init-Scanner s.Chl>,

<Program <Read-Token>> :: sC sI t.Program,

<Term-Scanner>,

{ ** Проверяем, что остаток программы

sC sI : Key Eof ** пуст.

= t.Program;

= $error sC sI " instead of Eof after the program";

};

Program sC sI = ** Программа.

<Statement-Seq sC sI> :: sC sI tX,

= sC sI (Program tX);

Statement-Seq sC sI = ** Последовательность

<Statement sC sI> :: sC sI tX0, ** операторов.

= <Rest-St-Seq sC sI tX0>;

Rest-St-Seq sC sI tX0 =

\? {

<Token? ";" sC sI> :: sC sI \!

<Statement-Seq sC sI> :: sC sI tX,

= sC sI (Seq tX0 tX);

\!

= sC sI tX0;

};

Statement sC sI = ** Оператор.

\? {

<Name? sC sI> :: sC sI s.Name \!

<Accept ":=" sC sI> :: sC sI,

<Expr sC sI> :: sC sI t.Expr,

= sC sI (Assign s.Name t.Expr);

<Token? "IF" sC sI> :: sC sI \!

<Test sC sI> :: sC sI t.Test,

<Accept "THEN" sC sI> :: sC sI,

<Statement sC sI> :: sC sI t.Then,

<Accept "ELSE" sC sI> :: sC sI,

<Statement sC sI> :: sC sI t.Else,

= sC sI (If t.Test t.Then t.Else);

<Token? "WHILE" sC sI> :: sC sI \!

<Test sC sI> :: sC sI t.Test,

<Accept "DO" sC sI> :: sC sI,

<Statement sC sI> :: sC sI t.Do,

= sC sI (While t.Test t.Do);

<Token? "READ" sC sI> :: sC sI \!

<Name? sC sI> :: sC sI s.Name,

= sC sI (Read s.Name);

<Token? "WRITE" sC sI> :: sC sI \!

<Expr sC sI> :: sC sI t.Expr,

= sC sI (Write t.Expr);

<Token? "(" sC sI> :: sC sI \!

<Statement-Seq sC sI> :: sC sI t.Stmt,

<Accept ")" sC sI> :: sC sI,

= sC sI t.Stmt;

\!

= sC sI (Skip);

};

Test sC sI = ** Условие.

<Expr sC sI> :: sC sI t.Expr1,

<Comp-Op sC sI> :: sC sI t.Op,

<Expr sC sI> :: sC sI t.Expr2,

= sC sI (Test t.Op t.Expr1 t.Expr2);

Expr sC sI = ** Выражение.

<Term sC sI> :: sC sI t.X0,

= <Rest-Expr sC sI t.X0>;

Rest-Expr sC sI t.X1 =

\? {

<Add-Op? sC sI> :: sC sI s.Op \!

<Term sC sI> :: sC sI t.X2,

= <Rest-Expr sC sI (Op s.Op t.X1 t.X2)>;

\!

= sC sI t.X1;

};

Term sC sI = ** Слагаемое.

<Factor sC sI> :: sC sI t.X0,

= <Rest-Term sC sI t.X0>;

Rest-Term sC sI t.X1 =

\? {

<Mul-Op? sC sI> :: sC sI s.Op \!

<Factor sC sI> :: sC sI t.X2,

= <Rest-Term sC sI (Op s.Op t.X1 t.X2)>;

\!

= sC sI t.X1;

};

Factor sC sI = ** Множитель.

\? {

<Name? sC sI> :: sC sI s.Name \!

= sC sI (Name s.Name);

<Value? sC sI> :: sC sI s.Value \!

= sC sI (Const s.Value);

<Token? "(" sC sI> :: sC sI \!

<Expr sC sI> :: sC sI t.Expr,

<Accept ")" sC sI> :: sC sI,

= sC sI t.Expr;

\!

$error "Invalid factor start: " sC sI;

};

Comp-Op sC sI = ** Операция отношения.

{

sC : Key,

("=" Eq) ("<>" Ne) ("<=" Le) ("<" Lt) (">=" Ge) (">" Gt)

: e (sI s.Op) e

= <Read-Token> s.Op;

= $error "Invalid comparison operation: " sC sI;

};

Add-Op? Key sI = ** Аддитивная операция.

("+" Add) ("-" Sub) : e (sI s.Op) e

= <Read-Token> s.Op;

Mul-Op? Key sI = ** Мультипликативная операция.

("*" Mul) ("/" Div) : e (sI s.Op) e

= <Read-Token> s.Op;

** Эта функция пытается отщепить ключевое слово sI?.

** Если это не удается, то результатом является неуспех.

Token? sI? Key sI? = <Read-Token>;

** Эта функция пытается отщепить ключевое слово sI?.

** Если это не удается, то результатом является ошибка.

Accept

{

sI? Key sI? = <Read-Token>;

sI? sC sI = $error sC sI " instead of " Key sI?;

};

** Имя переменной.

Name? Name sI = <Read-Token> sI;

** Значение.

Value? Value sI = <Read-Token> sI;