#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define STACK_SIZE 256
typedef enum{S, R, A} Action;
typedef enum{E, T, F, STATE} Type;
typedef enum{EOL, ADD, MULT, LARC, RARC, I, NON} Symbol;
// LR表用
typedef struct{
Action action;
int state;
}LR;
// スタック用
typedef struct{
Type type;
int value;
}Item;
LR lr_table[12][6]; // LR表
LR goto_table[12][3]; // Goto表
Item stack[STACK_SIZE]; // スタック
int sp; // スタックポインタ
void init_table(void);
void init_stack(void);
void print_stack(void);
Item pop(void);
void push(Item);
Item peek(void);
Symbol convert(int);
int eval(char*);
int main(){
char *exp1="1+2";
char *exp2="(1+2)*3";
char *exp3="(3+4*5)+(4+8*1)";
init_table();
printf("%s = %d\n", exp1, eval(exp1));
printf("%s = %d\n", exp2, eval(exp2));
printf("%s = %d\n", exp3, eval(exp3));
return 0;
}
// LR表の初期化
void init_table(){
lr_table[0][LARC].action = S; lr_table[0][LARC].state = 5;
lr_table[0][I].action = S; lr_table[0][I].state = 4;
lr_table[1][EOL].action = R; lr_table[1][EOL].state = 4;
lr_table[1][ADD].action = R; lr_table[1][ADD].state = 4;
lr_table[1][MULT].action = R; lr_table[1][MULT].state = 4;
lr_table[1][RARC].action = R; lr_table[1][RARC].state = 4;
lr_table[2][EOL].action = R; lr_table[2][EOL].state = 2;
lr_table[2][ADD].action = R; lr_table[2][ADD].state = 2;
lr_table[2][MULT].action = S; lr_table[2][MULT].state = 6;
lr_table[2][RARC].action = R; lr_table[2][RARC].state = 2;
lr_table[3][EOL].action = A; lr_table[3][EOL].state = 0;
lr_table[3][ADD].action = S; lr_table[3][ADD].state = 7;
lr_table[4][EOL].action = R; lr_table[4][EOL].state = 6;
lr_table[4][ADD].action = R; lr_table[4][ADD].state = 6;
lr_table[4][MULT].action = R; lr_table[4][MULT].state = 6;
lr_table[4][RARC].action = R; lr_table[4][RARC].state = 6;
lr_table[5][LARC].action = S; lr_table[5][LARC].state = 5;
lr_table[5][I].action = S; lr_table[5][I].state = 4;
lr_table[6][LARC].action = S; lr_table[6][LARC].state = 5;
lr_table[6][I].action = S; lr_table[6][I].state = 4;
lr_table[7][LARC].action = S; lr_table[7][LARC].state = 5;
lr_table[7][I].action = S; lr_table[7][I].state = 4;
lr_table[8][ADD].action = S; lr_table[8][ADD].state = 7;
lr_table[8][RARC].action = S; lr_table[8][RARC].state = 11;
lr_table[9][EOL].action = R; lr_table[9][EOL].state = 3;
lr_table[9][ADD].action = R; lr_table[9][ADD].state = 3;
lr_table[9][MULT].action = R; lr_table[9][MULT].state = 3;
lr_table[9][RARC].action = R; lr_table[9][RARC].state = 3;
lr_table[10][EOL].action = R; lr_table[10][EOL].state = 1;
lr_table[10][ADD].action = R; lr_table[10][ADD].state = 1;
lr_table[10][MULT].action = S; lr_table[10][MULT].state = 6;
lr_table[10][RARC].action = R; lr_table[10][RARC].state = 1;
lr_table[11][EOL].action = R; lr_table[11][EOL].state = 5;
lr_table[11][ADD].action = R; lr_table[11][ADD].state = 5;
lr_table[11][MULT].action = R; lr_table[11][MULT].state = 5;
lr_table[11][RARC].action = R; lr_table[11][RARC].state = 5;
goto_table[0][E].action = NON; goto_table[0][E].state = 3;
goto_table[0][T].action = NON; goto_table[0][T].state = 2;
goto_table[0][F].action = NON; goto_table[0][F].state = 1;
goto_table[5][E].action = NON; goto_table[5][E].state = 8;
goto_table[5][T].action = NON; goto_table[5][T].state = 2;
goto_table[5][F].action = NON; goto_table[5][F].state = 1;
goto_table[6][F].action = NON; goto_table[6][F].state = 9;
goto_table[7][T].action = NON; goto_table[7][T].state = 10;
goto_table[7][F].action = NON; goto_table[7][F].state = 1;
}
// スタック初期化
void init_stack(){ sp=0;}
// スタックのアイテムをポップ
Item pop(){ return stack[--sp];}
// スタックにアイテムを追加
void push(Item item){
if(sp>STACK_SIZE) exit(1);
stack[sp++] = item;
}
// スタックの一番上を見る
Item peek(void){ return stack[sp-1];};
// スタックを表示
void print_stack(void){
int i;
for(i = 0;i < sp;i++){
printf("[%d, %d], ", stack[i].type, stack[i].value);
}
printf("\n");
}
// 文字を対応するシンボルに変換
Symbol convert(int c){
if(c == EOL) return EOL;
if(isdigit(c)) return I;
switch(c){
case '+': return ADD;
case '*': return MULT;
case '(': return LARC;
case ')': return RARC;
}
return NON;
}
// 式を評価して値を返す
int eval(char* expression){
int i = 0, len = strlen(expression)-1, state, c;
Item x;
LR a, g;
Symbol s;
Item base = {STATE, 0};
init_stack();
push(base);
while(1){
//print_stack();
c = i > len ? EOL : expression[i];
state = pop().value;
s = convert(c);
a = lr_table[state][s];
if(a.action == S){ // シフト操作
x.type=STATE; x.value=state; push(x);
x.type=I; x.value=c; push(x);
x.type=STATE; x.value=a.state; push(x);
i++;
}else if (a.action == R){ // 還元操作
Item item1, item2;
Type type;
switch(a.state){
case 1: // E -> E + T
item1 = pop();
pop(); // discard state
pop(); // discard "+"
pop(); // discard state
item2 = pop();
state = peek().value;
x.type=E; x.value=item1.value+item2.value;
push(x);
type = E;
break;
case 2: // E -> T
item1 = pop();
state = peek().value;
x.type=E; x.value=item1.value;
push(x);
type = E;
break;
case 3: // T -> T * F
item1 = pop();
pop(); // discard state
pop(); // discard "*"
pop(); // discard state
item2 = pop();
state = peek().value;
x.type=T; x.value=item1.value*item2.value;
push(x);
type = T;
break;
case 4: // T -> F
item1 = pop();
state = peek().value;
x.type=T; x.value=item1.value;
push(x);
type = T;
break;
case 5: // F -> ( E )
pop(); // discard ")"
pop(); // discard state
item1 = pop();
pop(); // discard state
pop(); // discard "("
state = peek().value;
x.type=F; x.value=item1.value;
push(x);
type=F;
break;
case 6: // F -> i
item1 = pop();
state = peek().value;
x.type=F; x.value=item1.value-'0';
push(x);
type=F;
break;
default: perror("error1"); exit(1);
}
g=goto_table[state][type];
x.type=STATE; x.value=g.state;
push(x);
}else if(a.action == A){ // Accept
break;
}else{
perror("error2"); exit(1);
}
}
return stack[1].value;
}