Реализация синтаксического блока. Применение конечного автомата, страница 5

            if(FndIdCode(symbol)->dcl==0){

                sprintf(ErrStr,"идентификатор %s не объявлен", FndIdCode(symbol)->name);

              ErrMes(ilst, Errstr);

            }

            FPRT;NS;

            if (symbol == EQ) {

                FPRT1(ASGN);NS;

                Expr();

                if (symbol == SCOL){

                          FPRT;NS;

                }else ErrMes(ilst,"нет ; в операторе присваивания");

            } else ErrMes(ilst,"нет знака = в операторе присваивания");

            ExeOp();

   }

}

void ListIO(void){

   if(symbol>=BEGTBL && symbol<=ENDTBL){

            if(FndIdCode(symbol)->dcl==0){

                sprintf(ErrStr,"идентификатор %s не объявлен", FndIdCode(symbol)->name);

                ErrMes(ilst, Errstr);

           }

            FPRT;NS;

            if (symbol == COMMA) {

                FPRT;NS;

                ListIO();

            }

   } 

}

void Expr(void){

}

Разбор выражений

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

Как известно, есть 3 способа записи выражений:

1.  инфиксная          a+b

2.  префиксная        +ab

3.  постфиксная       ab+

Префиксная и постфиксная формы известны как, соответственно, прямая и обратная польские записи (по стране ее изобретателя, поляка, Яна Лукашевича). Это, так называемые бесскобочные формы записи.

Среди множества известных алгоритмов перехода от инфиксной формы записи выражения к обратной польской, рассмотрим следующий, состоящий из трех действий:

1.  G₁ – если при чтении выражения слева направо встречается идентификатор, печатаем его;

2.  G₂ – если при чтении выражения слева направо встречается знак операции, заносим его в стек;

3.  G₃ – если при чтении выражения слева направо встречается конец выражения или подвыражения, извлекаем знак из стека и печатаем его.

Пусть наша грамматика состоит всего из двух операций одного приоритета, + и -. Порождающие правила такой грамматики имеют вид:

<expr> à <item> + <expr>

<expr> à <item> - <expr>

<expr> à <item>

<item> à l

Эта же самая грамматика, но с символами действмя:

<expr> à <item> + {G₂} <expr> {G₃}

<expr> à <item> - {G₂} <expr> {G₃}

<expr> à <item>

<item> à l {G₁}

Пример программной реализации.

#include <stdio.h>

…

char stack[80], *top,  // стек знаков операций

     ibuf[80],  *pr,        // входной буфер

     obuf[80],  *pw;      // выходной буфер

void expr(void);

void  item(void);

…

Головнаяпроцедура

. . .

     strcpy(ibuf,Edit1->Text.c_str());

     pr=ibuf; pw=obuf; top=stack;

     expr();

     *pw='\0';

     Edit2->Text= obuf;

  . . .

void expr(void){

  item();

  if (*pr=='+' || *pr=='-'){

     *top++ = *pr++;

     expr();

     *pw++ = *--top;

  }

}

void item(void){

    *pw++ = *pr++;

}

Но при этом, если мы введем a+b-h-k, то получим после разбора abhk--+. А это не совсем то, что требовалось, нам нужноab+h-k-, для чего надо определять не окончание всего выражения, а конец подвыражения, т.е. ситуации, когда появились через знак операции два операнда. Изменим грамматику, введя для этой ситуации новый нетерминальный символ item2. Новая грамматика и текст программы будут иметь вид.

<expr> à <item> + {G₂} <item2>

<expr> à <item> - {G₂} <item2>

<expr> à <item>

<item2> à <item> {G₃}+ {G₂} <item2>

<item2> à <item> {G₃}- {G₂} <item2>

<item2> à <item> {G₃}

<item> à l {G₁}

.   .   .

void item2(void);

.   .   .

void expr(void){

  item();

  if (*pr=='+' || *pr=='-'){

     *top++ = *pr++;

     item2();

  }

}

void item2(void){

  item();

  *pw++ = *--top;

  if (*pr=='+' || *pr=='-'){

     *top++ = *pr++;

     item2();

  }

}

void item(void){

   *pw++ = *pr++;

}

И здесь уже в нашем случае будет ответ: ab+h-k-

А теперь добавим в нашу грамматику операции умножения и деления, т.к. это операции более высокого уровня приоритета, чем + и -, то в грамматике их надо разбирать после item и item2.

<expr> à <item> + {G₂} <item2>

<expr> à <item> - {G₂} <item2>

<expr> à <item>

<item2> à <item> {G₃}+ {G₂} <item2>

<item2> à <item> {G₃}- {G₂} <item2>

<item2> à <item> {G₃}

<item> à <factor> * {G₂} <factor2>

<item> à < factor> / {G₂} < factor 2>

<item> à < factor>

<factor2> à < factor> {G₃} *  {G₂} < factor2>

<factor2> à <factor> {G₃} /  {G₂} <factor2>

<factor2> à <factor> {G₃}

<factor2> à  l {G₁}

В программе изменения начнутся с функции item.

void item(void){

  factor();

  if (*pr=='*' || *pr=='/'){

     *top++ = *pr++;

     factor2();

  }

}

void factor2(void){

  factor();

  *pw++ = *--top;

  if (*pr=='*' || *pr=='/'){

     *top++ = *pr++;

     factor2();

  }

}

void factor(void){

   *pw++ = *pr++;

}

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

Т.о. в порядке убывания приоритета можно разместить операции:

Операция		Порядок выполнения
|	Или	Слева-направо
&	И	Слева-направо
<    >    =    <=    >=    <>	Отношения	Слева-направо
+     -	Сложить, вычесть	Слева-направо
*     /	Умножить, разделить	Слева-направо
!    -      **	Отрицание, унарный минус, возведение в степень	Справа-налево

<expr>      à <litem> | {G₂} <litem2>

<expr>      à <litem> {G₃}

<litem2>   à <litem2> {G₃} | {G₂} <litem2>

< litem2>  à <litem> {G₃}