c - 为什么我的 C Yacc/lex 计算器无法正确解析？

Question

我使用 C Yacc 和 Lex 构建了一个计算器，可以存储 26 个字母变量。它应该是这样的:

Example Input:
a = 55-3;
b = c = a-42;
a+b*c;
c = 6;
a = b;
a = 10000;
b = 100000;
a*b;
a*b*10;
c/d;
d/c;
^D

Example Output:
52
10
152
6
0
10000
100000
1000000000
overflow
dividebyzero
0

以下是我的代码无法正常工作的一些示例:

$ ./cexpr
a = 7;
7

b = 6;
6

c = a = b;
6

a = 8;
8

(a + b);
14

a + b;
syntax error

Invalid expression.
$ ./cexpr
4 + 5;
9

a = 6 + 1 * 5;
11

(a + 1);
overflow
11

a + 1;
syntax error

Invalid expression.
$ ./cexpr
6 * 3;
18

6 & 90;
2

4 >> 6;
0

8 ^ 3;
1

85 + 6;
91

8 / 4;
syntax error

Invalid expression.

我已经将程序设置为通过创建许多非终结符来使用运算符优先级进行解析。

莱克斯:

    %{
    #include "y.tab.h"
%}

%{
    void yyerror(char *);
%}

%%
[0-9]+      { sscanf(yytext, "%d", &yylval.num);
            return NUM; }
[a-z]       { yylval.num = *yytext - 'a';
            return VAR; }
"dump"      { yylval.string=strdup(yytext);
            return DUMP; }
"clear"     { yylval.string=strdup(yytext);
            return CLEAR; }
[ /t]+      {}
.           { return yytext[0]; }

Yacc:

%{
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
%}

%union {
  int num;
  char *string;
}

%token <num> NUM
%token <num> VAR
%token <string> DUMP
%token <string> CLEAR
%type <num> expr1
%type <num> expr2
%type <num> expr3
%type <num> expr4
%type <num> expr5
%type <num> expr6
%type <num> expr7
%type <num> expr8
%type <num> assign
%type <num> value

%{
    void yyerror(char *);
    int yylex();
    int alph[26];
    int INT_MAX = 2147483649;
    void val_dump();
    void val_clear();
%}

%%
commands:
        |   commands command
        ;

command :   assign ';'      { printf("%d\n", $1); }
        |   DUMP ';'        { val_dump(); }
        |   CLEAR ';'       { val_clear(); }
        ;

assign  :   VAR '=' assign  { alph[$1] = $3; $$ = alph[$1]; }
        |   VAR '+' '=' assign  { alph[$1] += $4; $$ = alph[$1]; }
        |   VAR '-' '=' assign  { alph[$1] -= $4; $$ = alph[$1]; }
        |   VAR '*' '=' assign  { alph[$1] *= $4; $$ = alph[$1]; }
        |   VAR '/' '=' assign  { alph[$1] /= $4; $$ = alph[$1]; }
        |   VAR '%' '=' assign  { alph[$1] %= $4; $$ = alph[$1]; }
        |   VAR '<' '<' '=' assign  { alph[$1] <<= $5; $$ = alph[$1]; }
        |   VAR '>' '>' '=' assign  { alph[$1] >>= $5; $$ = alph[$1]; }
        |   VAR '&' '=' assign  { alph[$1] &= $4; $$ = alph[$1]; }
        |   VAR '^' '=' assign  { alph[$1] ^= $4; $$ = alph[$1]; }
        |   expr1           { $$ = $1; }
        ;

// The higher the number the higher the precedence.
// Parenthesis is alwaays first.

expr1   :   expr1 '|' expr1 { $$ = $1 | $3; }
        |   '(' expr1 ')'   { $$ = $2; }
        |   expr2           { $$ = $1; }
        ;

expr2   :   expr2 '^' expr2 { $$ = ($1 | $3) & !( $1 & $3); }
        |   '(' expr1 ')'   { $$ = $2; }
        |   expr3           { $$ = $1; }
        ;

expr3   :   expr3 '&' expr3 { $$ = $1 & $3; }
        |   '(' expr1 ')'   { $$ = $2; }
        |   expr4           { $$ = $1; }
        ;

expr4   :   expr4 '<' '<' expr4 { $$ = $1 << $4; }
        |   expr4 '>' '>' expr4 { $$ = $1 >> $4; }
        |   '(' expr1 ')'   { $$ = $2; }
        |   expr5           { $$ = $1; }
        ;

expr5   :   expr5 '+' expr5 { if ($1 <= INT_MAX - $3) $$ = $1 + $3; else printf("overflow\n"); }
        |   expr5 '-' expr5 { $$ = $1 - $3; }
        |   '(' expr1 ')'   { $$ = $2; }
        |   expr6           { $$ = $1; }
        ;

expr6   :   expr6 '*' expr6 { if ($1 <= INT_MAX / $3) $$ = $1 * $3; else printf("overflow\n"); }
        |   expr6 '/' expr6 { if ($3 != 0) $$ = $1 / $3; else printf("dividebyzero\n"); }
        |   expr6 '%' expr6 { if ($3 != 0) $$ = $1 % $3; else printf("dividebyzero\n"); }
        |   '(' expr1 ')'   { $$ = $2; }
        |   expr7           { $$ = $1; }
        ;

expr7   :   '-' expr7       { $$ = - $2; }
        |   '(' expr1 ')'   { $$ = $2; }
        |   expr8           { $$ = $1; }
        ;

expr8   :   '~' expr8       { $$ = ~ $2; }
        |   '(' expr1 ')'   { $$ = $2; }
        |   value           { $$ = $1; }
        ;

value   :   NUM             { $$ = $1; }
        |   VAR             { $$ = alph[$1]; }
        ;

%%

int main()
{
    if (yyparse())
        printf("\nInvalid expression.\n");
    else
        printf("\nCalculator off.\n");
}

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

void val_dump(){
    char c = 'a';
    for (int i = 0; i < 26; i++) {
        printf("%c: %d\n", (c++), alph[i]);
    }
}

我无法准确理解这里发生了什么。

Answer 1

INT_MAX 问题并不能解释所有这些错误。主要问题是你的语法到处都是。我很惊讶它并不含糊。请查找大多数标准语言的语法。例如，括号只能出现在一个产生式中，在本例中是 expr8. 并且所有这些 expr1, expr2, ... 非终结符都有标准名称:逻辑表达式、and-表达式、or-表达式、表达式、术语、因子、主要。

// The higher the number, the higher the precedence.

没有。在您编写的语法中，数字越大，优先级越低。

// Parenthesis is always first

不应该的。按照通常的写作顺序，它应该出现在最后，优先级从低到高。

你的语法应该是这样的:

commands
    : /* empty */
    | commands command
    ;

command
    : assign ';'      { printf("%d\n", $1); }
    | DUMP ';'        { val_dump(); }
    | CLEAR ';'       { val_clear(); }
    ;

assign 
    : VAR '=' assign  { alph[$1] = $3; $$ = alph[$1]; }
    | VAR '+' '=' assign  { alph[$1] += $4; $$ = alph[$1]; }
    | VAR '-' '=' assign  { alph[$1] -= $4; $$ = alph[$1]; }
    | VAR '*' '=' assign  { alph[$1] *= $4; $$ = alph[$1]; }
    | VAR '/' '=' assign  { alph[$1] /= $4; $$ = alph[$1]; }
    | VAR '%' '=' assign  { alph[$1] %= $4; $$ = alph[$1]; }
    | VAR '<' '<' '=' assign  { alph[$1] <<= $5; $$ = alph[$1]; }
    | VAR '>' '>' '=' assign  { alph[$1] >>= $5; $$ = alph[$1]; }
    | VAR '&' '=' assign  { alph[$1] &= $4; $$ = alph[$1]; }
    | VAR '^' '=' assign  { alph[$1] ^= $4; $$ = alph[$1]; }
    | logical-expression           { $$ = $1; }
    ;

logical-expression
    : and-expression
    | logical-expression '|' and-expression { $$ = $1 | $3; }
    ;

and-expression
    : xor-expression
    | and-expression '&' xor-expression           { $$ = $1; }
    ;

xor-expression
    : shift-expression
    | xor-expression '^' shift-expression { $$ = $1 ^ $3; }
    ;

shift-expression
    : expression
    | shift-expresion '<' '<' expression { $$ = $1 << $3; }
    | shift-expresion '>' '>' expression { $$ = $1 >> $3; }
    ;

expression
    : term
    | expression '+' term { if ($1 <= INT_MAX - $3) $$ = $1 + $3; else printf("overflow\n"); }
    | expression '-' term { $$ = $1 - $3; }
    ;

term
    : factor
    | term '*' factor { if ($1 <= INT_MAX / $3) $$ = $1 * $3; else printf("overflow\n"); }
    | term '/' factor { if ($3 != 0) $$ = $1 / $3; else printf("dividebyzero\n"); }
    | term '%' factor { if ($3 != 0) $$ = $1 % $3; else printf("dividebyzero\n"); }
    ;

factor
    : primary
    | '-' primary { $$ = -$2; }
    /* And why not have primary '+'? It costs nothing. */
    | '+' primary { $$ = $2; }
    | '~' primary { $$ = ~ $2; }
    ;

primary
    : value
    | '(' logical-expression ')'   { $$ = $2; }
    ;

value
    : NUM             { $$ = $1; }
    | VAR             { $$ = alph[$1]; }
    ;

E&OE