c - Lex yacc 移位/减少错误

Question

我正在学习 lex 和 yacc 编程，以及这个 yacc 程序来验证和评估算术表达式，从而给我带来 25shift/reduce 冲突。在阅读其他 stackoverflow 解释后，我明白问题是优先的，但是，我不确定如何使用错误处理来解决。我想知道是否有人可以帮助我。

我尝试过这样的关联处理程序:

%token VARNAME
%token DIGIT
%token EQ
%token ADD SUB MULT DIV
%token LPAREN RPAREN
%token END
%left ADD SUB MULT DIV LPAREN
%right RPAREN END
%nonassoc EQ VARNAME DIGIT

但是，它不起作用，我很困惑。这是我的 1.y 文件:

%{
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char* argv[])
{
    FILE *fp;
    extern FILE *yyin;
    extern int yylex();
    extern int yyparse();
    extern int yydebug;

    yydebug = 1;
    if (argc == 2)
    {
        fp = fopen(argv[1], "r");
        if (!fp)
        {
        fprintf (stderr, "Usage: %s <filename>\n", argv[0]);
        }
        else
        {
            yyin = fp;
            yyparse();
            fprintf (stdout, "***PARSE COMPLETE***\n");
        }
    }
    else 
        fprintf (stderr, "Usage: %s <filename>\n", argv[0]);
}

void yyerror (const char *err)
{
    fprintf (stderr, "Error: %s\n", err);
}

%}

%token VARNAME
%token DIGIT
%token EQ
%token ADD SUB MULT DIV
%token LPAREN RPAREN
%token END

%%
    statement:
    END
    |
    expression END  
    {printf ("DONE!\n");};
    |
    error 
    { printf(" INVALID EXPRESSION\n"); }
;

expression: 
    VARNAME 
    {printf("PARSED A VARIABLE!\n");};
    |
    DIGIT 
    {printf("PARSED A DIGIT!\n");};
    |
    expression ADD expression
    {printf("PARSED A PLUS SIGN!\n");};
    |
    expression SUB expression
    {printf("PARSED A MINUS SIGN!\n");};
    |
    expression MULT expression
    {printf("PARSED A MULTPLY SIGN!\n");};
    |
    expression DIV expression
    {printf("PARSED A DIVIDE SIGN!\n");};
    |
    expression EQ expression
    {printf("PARSED A EQUALS SIGN!\n");};
    |
    LPAREN expression RPAREN
    {printf("PARSED A PARENTHESIS!\n");};
    ;

%%

我尝试过这样的关联处理程序:

%token VARNAME
%token DIGIT
%token EQ
%token ADD SUB MULT DIV
%token LPAREN RPAREN
%token END
%left ADD SUB MULT DIV LPAREN
%right RPAREN END
%nonassoc EQ VARNAME DIGIT

这个关联正确吗？

Answer 1

GNU bison manual 中很好地涵盖了这些问题.

正如@Jonathan Leffler 所说:

You need to specify the precedence and associativity of the operators. Look up %left, %right and %nonassoc. Or write the grammar in a different manner altogether. For example, the grammar in the C standard doesn't need the precedence levels or associativity.

The %token items look plausible. I think %left does not need LPAREN; nor does %right need RPAREN. I'm not sure whether you need %nonassoc at all. I'm assume that the 'code'( at the start and the )'code' at the end are artefacts of trying to format a comment. Normally, you want ADD and SUB at a lower priority than MULT and DIV.

在算术示例中，通常通过将语法编写为以下方式来解决这些问题:

expression : term
           | term ADD expression
           | term SUB expression
            ;

term : factor
     | factor MULT term
     | factor DIV term
     ;

factor : VARNAME
       | DIGIT
       | LPAREN expression RPAREN
       ;

现在您拥有了以明确语法定义的运算符的结合性和优先级。