Как вычислить результат выражения, используя парсер LR в C - PullRequest
Новая
       41

Как вычислить результат выражения, используя парсер LR в C

0 голосов
/ 29 сентября 2018

Я пишу программу для вычисления значения выражения с использованием парсера 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();
}

Ответы [ 2 ]

0 голосов
/ 29 сентября 2018

У вас более серьезная ошибка, чем неправильно обработанный номер (см., Возможно, другой ответ).

У вас проблемы с пониманием того, как yylex и yyparse работают вместе.

Парсер вызывает lex для получения следующего входного токена и обрабатывает его.Затем он запрашивает у lex следующий токен, пока синтаксический анализатор не достигнет состояния ПРИНЯТЬ и не вернется к вызывающей стороне (вашей основной).

Сначала вы вызываете yylex, а затем yyparse.Хорошо.Лекс получает первый токен, и должен положить его в свой стек .Но это не так.Таким образом, входной токен потерян.Я также не вижу, чтобы вы звонили yylex в yyparse, чтобы получить следующий токен.

Я оставляю вас, чтобы исправить вашу ошибку.это требует некоторой доработки и отладки, которые я не хочу делать.Это твоя домашняя работа.Но я надеюсь, что эта подсказка поможет вам.

И начните учиться использовать отладчик.Он показывает вам путь, по которому идет программа, и значение переменных, поэтому вы можете проверить, нет ли у вас логических ошибок или ошибок.Отладка является неотъемлемой частью изучения языка Си.

0 голосов
/ 29 сентября 2018

В else if (isdigit(ch)) вы должны продолжить чтение ввода, пока оно является цифрой, и обработать его в x, например, 

ch = input[test++];
...
else if (isdigit(ch))
{
    lk.type = NUMBER;
    x= ch - '0';
    while (isdigit(ch=input[test++]))
        x = x*10 + ch - '0';
}
...
// test++; // remove it here.
...