c - 如何在 C 中使用 LR 解析器计算表达式结果

Question

我正在编写一个程序，使用 LR 解析器(2 个堆栈轨道)计算表达式值。该代码适用于个位数。它将 0-9 中的两个整数相加或相乘，但对于像 12+5*10 这样的两位数，它会失败。代码如下。我在评论中添加了连接双数的逻辑，我在其中检查标记是否为数字。

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

void push(int);
void shift(int);
void reduce(int);
void yyerror();
void lex_error();

#define NUMBER 256
#define PLUS 257
#define STAR 258
#define LPAREN 259
#define RPAREN 260
#define END 261
#define EXPRESSION 0
#define TERM 1
#define FACTOR 2
#define ACC 999


int action[12][6]={
{5, 0, 0, 4, 0, 0}, {0, 6, 0, 0, 0, ACC},{0,-2, 7, 0,-2,-2},
{0,-4,-4, 0,-4,-4}, {5, 0, 0, 4, 0, 0}, {0,-6,-6, 0,-6,-6},
{5, 0, 0, 4, 0, 0}, {5, 0, 0, 4, 0, 0}, {0, 6, 0, 0,11, 0},
{0,-1, 7, 0,-1,-1}, {0,-3, -3, 0,-3,-3}, {0,-5,-5, 0,-5,-5} };

int go_to[12][3]={
{1,2,3},{0,0,0}, {0,0,0},{0,0,0},{8,2,3},{0,0,0},
{0,9,3},{0,0,10},{0,0,0},{0,0,0},{0,0,0},{0,0,0} };

int prod_left[7]={0,EXPRESSION,EXPRESSION,TERM,TERM,FACTOR,FACTOR};
int prod_length[7]={0,3,1,3,1,3,1};
int stack[1000];
int value[1000];
int top=-1;
int sym;

typedef struct _token {
  int   type,   /* type of token (AND_TOK, etc.) */
   varno;   /* number of a VAR_TOK token */
} token;

token lk;
char *input;

token yylex() {
static int init = 1;    /* set to true first time through */
static char ch;     /* lookahead character */
char    s[100];
int i,x;
int num=0;
static int test = 0;

/* put nonsense value in for debugging */

lk.type = -1;
lk.varno = 0;

/* if at end of file, return an EOF token */

if (feof (stdin)) {
lk.type = END;
return lk;
}

/* if uninitialized, initialize the lookahead character */

if (init) {
init = 0;
}

ch = input[test++];

printf("character value in check token is %c\n", ch);
if(ch=='+')
    lk.type = PLUS;
else if(ch=='*')
    lk.type = STAR;
else if(ch=='(')
    lk.type = LPAREN;
else if(ch==')')
    lk.type = RPAREN;
else if (isdigit(ch))
{
    lk.type = NUMBER;
    x= ch - '0';
    while (isdigit(ch=input[test++]))
        x = x*10 + ch - '0';
    lk.varno = x;
}
/*while (lk.type==256)
 {
 num = num * 10;
 num = num + x - '0';
 }*/
else if (ch=='$')
    lk.type = END;
else{
    printf("character value befora saying illegal token %c\n", ch);
    lex_error();
}

 //test++;

 return lk;
}
int yyparse() {
int i;
int num = 0;
stack[++top]=0; // initial state
printf("token type is %d\n", lk.type);
printf("token type is %d\n", lk.type);
printf("token number value is %d\n", lk.varno);

do {
    i=action[stack[top]][lk.type-256]; // get relation
    printf("I value is %d\n", i);
    if (i==ACC){
        printf("success !\n");
        printf("value is ! %d \n", value[1]);
    }
    else if (i>0){ // shift
        printf("i is greater than 0 so calling shift\n");
        shift(i);
    }
    else if (i<0){ // reduce
        printf("i is less than 0 so calling reduce with - value %d \n", -i);
        reduce(-i);
    }
    else
        yyerror(); }
while (i!=ACC);
}

void push(int I) {
top++;
//printf("stack top after push is %d \n", stack[top]);
stack[top]=I;
//printf("stack top after assigning i is %d \n", stack[top]);
}

void shift(int I) {
//printf("pushing I value in stack is %d\n", I);
push(I);
value[top]=lk.varno;
yylex();
//printf("next token in shift is %d\n", sym);
}

void reduce(int I) {
int old_top;
/*printf("Top in reduce is %d\n", top);
printf("I in reduce is %d\n", I);
printf("Top in reduce is %d\n", top);
printf("prod prod_length in reduce is %d\n", prod_length[I]);*/
top-=prod_length[I];
//printf("top after minus in reduce is %d\n", top);
old_top=top;
//printf("oldtop in reduce is %d\n", old_top);
push(go_to[stack[old_top]][prod_left[I]]);

switch (I) {
    case 1: value[top]=value[old_top+1]+value[old_top+3];
    break;
    case 2: value[top]=value[old_top+1];
    break;
    case 3: value[top]=value[old_top+1]*value[old_top+3];
    break;
    case 4: value[top]=value[old_top+1];
    break;
    case 5: value[top]=value[old_top+2];
    break;
    case 6: value[top]=value[old_top+1];
    break;
    default: yyerror("parsing table error");
    break;
    }
}

void yyerror() {
printf("syntax error\n");
exit(1);
}

void lex_error() {
printf("illegal token\n");
exit(1);
}

void main () {
printf("Enter the expression: ");
input = malloc(sizeof(char) * 1024);
scanf("%s",input); 
yylex();
yyparse();
}

Answer 1

您遇到的错误比未正确解析的数字更严重(请参阅其他答案)。

您在理解 yylex 和 yyparse 如何协同工作时遇到问题。

解析器调用 lex 来获取下一个输入标记并对其进行处理。然后它向 lex 询问下一个标记，直到解析器到达 ACCEPT 状态并返回给调用者(您的 main)。

您首先调用 yylex，然后调用 yyparse。美好的。 Lex 获得第一个标记，应该将其放入您的堆栈。但事实并非如此。所以输入 token 丢失了。我也没有看到您在 yyparse 中调用 yylex 来获取下一个标记。

我留给你来修正你的错误。它需要我不愿意做的大量返工和调试。这是你的功课。但我希望这个提示对您有所帮助。

并开始学习使用调试器。它向您显示程序采用的路径和变量的值，因此您可以检查您是否犯了任何逻辑错误或有错误。调试是学习 C 语言不可或缺的一部分。