Как правильно реализовать if-statment с помощью yacc?

Question

Я пытаюсь реализовать оператор if в yacc.Я уже написал код несколько месяцев назад, но я не уверен в том, что я сделал.Вот что мне нужно сделать:

  if(condition_1) { z=constant_1; } 
  else_if(condition_2) {z=constant_2;}
  else_if ...
  … 
  … 
  else_if(condition_N-1) {z=constant_N-1;}
  else { z=constant_N;}

Где condition_1..N-1 должно включать только var-operation(<,>,==,!=)-var или var-operation-constatnt, например, x <5, y == x и так далее.Переменная должна быть только 'x' или 'y' и инициализирована перед оператором if (в противном случае устанавливается на ноль).В конце я должен напечатать вывод переменной 'z'.Я пытаюсь выполнить его, и кажется, что он работает правильно, но я не знаю, сделал ли я какую-то ошибку, которая могла привести к ошибке.Любая помощь будет признательна.</p>

Вот файл lex:

%{
#include "y.tab.h"
void yyerror (char *s);
int yylex();
%}

%%

"print"             {return PRINT;}
"exit"              {return EXIT_COMMAND;}
"if"                {return IF;}
"elseif"            {return ELSEIF;}
"elif"              {return ELSEIF;}
"else"              {return ELSE;}
"("             {return LP;}
")"             {return RP;}
"{"             {return GLP;}
"}"             {return GRP;}
"=="                {return EQEQ;}
"="             {return EQ;}
"!="                {return NEQ;}
";"             {return SEMI;}
"<"             {return LT;}
">"             {return GT;}

"x"             {return _X;}
"y"             {return _Y;}
"z"             {return _Z;}
[-]?[0-9]+          {yylval.val = atoi(yytext); return NUMBER;}
[ \t\n]+            ;
.               ;



%%

вот файл yacc:

%{
void yyerror (char *s);     /* Viene chiamato in caso di errore sintattico o grammatico */
int yylex();
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int x = 0,y = 0, z = 0;

%}

%union {
    int val;
    int a;
}

%token          PRINT
%token          EXIT_COMMAND
%token          IF
%token          ELSEIF
%token          ELSE
%token          _X
%token          _Y
%token          _Z
$token          _VAR
%token<val>         NUMBER
%token          LP
%token          RP
%token          GLP
%token          GRP
%token          EQEQ
%token          EQ
%token          NEQ
%token          SEMI
%token          LT
%token          GT
%type<a>        then
%type<a>        condition

/* assignment */
%right EQ


%start main_program

%%


main_program:   
        | main_program rule
        ;                 

rule:         '\n'
        | init_variables 
        | if_condition                  
        | printing 
        | EXIT_COMMAND                      {printf("Uscita dal programma in corso...\n"); exit(0);}
        | error rule                        {yyerrok;} /* skip line */
          ;


printing:     PRINT _X                      {printf("\nx=%d\n",x);} 
        | PRINT _Y                      {printf("\ny=%d\n",y);}                 
        | PRINT _Z                      {printf("\nz=%d\n",z);}
          ;


init_variables: 
          _X EQ NUMBER SEMI                 {x = $3;}
        | _Y EQ NUMBER SEMI                 {y = $3;}
          ;

if_condition:     IF LP condition RP GLP then GRP else_condition    {if($3 == 1){z=$6;} printf("\nz=%d\n",z);}  
        ;


condition:    _X LT NUMBER                      {if(x<$3){$$=1;}else{$$=0;}}
        | _X GT NUMBER                      {if(x>$3){$$=1;}else{$$=0;}}
        | _X EQEQ NUMBER                    {if(x==$3){$$=1;}else{$$=0;}}
        | _X NEQ NUMBER                     {if(x!=$3){$$=1;}else{$$=0;}}

        | _X LT _VAR                        {if(x<$3){$$=1;}else{$$=0;}}
        | _X GT _VAR                        {if(x>$3){$$=1;}else{$$=0;}}
        | _X EQEQ _VAR                      {if(x==$3){$$=1;}else{$$=0;}}
        | _X NEQ _VAR                       {if(x!=$3){$$=1;}else{$$=0;}}

        | _Y LT _VAR                        {if(y<$3){$$=1;}else{$$=0;}}
        | _Y GT _VAR                        {if(y>$3){$$=1;}else{$$=0;}}
        | _Y EQEQ _VAR                      {if(y==$3){$$=1;}else{$$=0;}}
        | _Y NEQ _VAR                       {if(y!=$3){$$=1;}else{$$=0;}}

        | _Y LT NUMBER                      {if(y<$3){$$=1;}else{$$=0;}}
        | _Y GT NUMBER                      {if(y>$3){$$=1;}else{$$=0;}}
        | _Y EQEQ NUMBER                    {if(y==$3){$$=1;}else{$$=0;}}
        | _Y NEQ NUMBER                     {if(y!=$3){$$=1;}else{$$=0;}}

          ;

then:         _Z EQ NUMBER SEMI                 {$$ = $3;}
          ;

else_condition:   ELSE GLP then GRP                 {z = $3;}
        | ELSEIF LP condition RP GLP then GRP else_condition    {if($3 == 1){z=$6;}}
          ;

%%

void yyerror(char *s){
    printf("ERRORE: %s\n",s);
}

int yywrap(){
    return 1;
}

int main (void){
    return yyparse();
}                   

Answer 1

Ваш код будет работать, но способ его работы может быть неожиданным и не очень общим.

В действительности, else в вашем синтаксисе вводит в заблуждение. Можно было бы ожидать

if      (condition1) { statement1; }
else if (condition2) { statement2; }
else                { statement3; }

только для проверки condition2, если condition1 ложно, и для выполнения statement3 только если оба условия ложны. Но ваш код не закорачивает. Каждый тест оценивается, и предложение else является безусловным. Глядя на код, кажется, что else не существует.

Однако код работает. Это почему? Это потому, что это выполняется задом наперед. По сути, оценка происходит так, как если бы вышесказанное было написано;

{ statement3; }
if (condition2) { statement2; }
if (condition1) { statement1; }

Это работает только потому, что все операторы ограничены установкой значения z. Таким образом, последний оператор, который выполняет, выигрывает, и выполнение оценки в обратном направлении дает точно правильный ответ.

Так что все в порядке, если вы понимаете, как это работает. Но он не очень общий и совсем не эффективный.

Во-первых, как это работает. Грубо говоря, контекстно-свободная грамматика может представлять список двумя способами:

left_list : element | left_list element
right_list: element | element right_list

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

Если вы добавили действия для создания списка в вышеупомянутые произведения, вам нужно будет протолкнуть element в конец left_list, но сдвинуть element в начало right_list. Но дело не только в том, к какой стороне списка добавляется новый элемент. Это также порядок оценки побочных эффектов.

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

(Это не влияет на порядок побочных эффектов в действиях для element. element s всегда обрабатываются слева направо.)

В вашей грамматике есть два типа списка: сама программа и операторы if. Программа представляет собой список правил слева, а побочные эффекты заключаются в действиях правил, которые оцениваются слева направо. Но операторы if являются правыми списками предложений (где рекурсия заканчивается другим элементом, предложением else), и побочные эффекты присутствуют в действиях списка. Вот почему он оценивает задом наперед.

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

Кроме того, правильное рекурсивное производство действительно использует стек. Если у оператора if есть много предложений, он будет использовать много стека анализатора. Может даже превышать ограничение стека синтаксического анализатора.