如何使用 yacc 正确实现 if 语句？

Question

我正在尝试在 yacc 中实现一个 if 语句。几个月前我已经写了一些代码，但我不确定我做了什么。这是我必须做的：

  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' 的输出。我尝试执行它，它似乎工作正常，但我不知道我是否犯了一些可能导致错误的错误。任何帮助将不胜感激。

这是 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 = ;}
        | _Y EQ NUMBER SEMI                 {y = ;}
          ;

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


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

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

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

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

          ;

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

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

%%

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; }

仅在 condition1 为假时测试 condition2，并且仅在两个条件都为假时才执行 statement3。但是你的代码不会短路。每个测试都会被评估，else 子句是无条件的。查看代码，就好像 else 不存在一样。

但是，代码有效。这是为什么？这是因为它向后执行。实际上，评估的进行就像上面写的一样；

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

之所以有效，是因为所有语句都仅限于设置 z 的值。因此，最后执行的语句获胜，并且向后进行评估会产生正确的答案。

没关系，只要您了解它的工作原理即可。但是不是很通用，效率也不是很高。

首先，它是如何工作的。粗略地说，上下文无关文法可以用两种方式表示列表：

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

这两个公式识别相同的输入，但它们代表不同的解析。对于运算符，我们称它们为 left- 和 right-associative。在列表的情况下，区别在于元素添加到列表的方式：在 left_list 中，连续的元素被添加到列表的末尾，而在 right_list 中，它们被添加到开始。

如果您在上述作品中添加了创建列表的操作，则必须将element推到left_list的末尾，但是shiftelement进入right_list开头。但这不仅仅是将新元素添加到列表的哪一侧。也是副作用的评价顺序。

重要的见解是内部列表是在它出现在产品中的时候完全构建的。在 left_list 的情况下，该构造发生在 element 甚至被解析之前，因此 left_list 操作中的副作用被评估 left-to-right。在 right_list 的情况下，构造发生在最后，因此所有的评估都会叠加，直到最终 right_list: element 减少生产。只有这样才能评估其他操作，因为它们会从堆栈中弹出。

（这不会影响 element 的操作中 side-effects 的顺序。element 始终处理 left-to-right。）

语法中有两种类型的列表：程序本身和 if 语句。该程序是 left-list 规则，side-effects 在规则操作中，它们被评估 left-to-right。但是 if 语句是 right-lists 子句（其中递归以不同的元素终止，else 子句）并且副作用在列表操作中。所以这就是它向后评估的原因。

现在，如果目的只是解析一次输入并对其求值，那么很明显，解析整个表达式然后丢弃除第一个成功条件之外的所有内容并不完全有效。当遇到真正的条件时就停止会好得多。此外，评估 left-to-right 并在找到真实条件时停止将避免 side-effects 不只是抵消以前的条件时出现问题。因此，更通用的解决方案将不依赖于向后评估。

而且，正确的递归产生式确实是用到了栈。如果 if 语句有很多子句，它会使用很多解析器堆栈。它甚至可能超过解析器的堆栈限制。

如何使用 yacc 正确实现 if 语句？

How to correctly implement an if-statment using yacc?

yacc

if-statement

lex