LR分析法与语法制导翻译法实现简单算术表达式求值(C语言)

// LR分析表 int action_table[10][7] = { {5, 0, 0, 4, 0, 0, 0}, {0, 6, 0, 0, 0, 0, 999}, {0, -2, 7, 0, -2, -2, -2}, {0, -4, -4, 0, -4, -4, -4}, {5, 0, 0, 4, 0, 0, 0}, {0, -6, -6, 0, -6, -6, -6}, {5, 0, 0, 4, 0, 0, 0}, {5, 0, 0, 4, 0, 0, 0}, {0, -1, 7, 0, -1, -1, -1}, {0, -3, -3, 0, -3, -3, -3} };

int goto_table[10][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} };

// 符号栈 int symbol_stack[100]; int top = -1;

// 值栈 int value_stack[100]; int vtop = -1;

// 语法制导翻译函数 void reduce() { int op = symbol_stack[top--]; int v1, v2; switch(op) { case 1: // E -> E1 + T v1 = value_stack[vtop--]; v2 = value_stack[vtop--]; value_stack[++vtop] = v1 + v2; break; case 2: // E -> T break; case 3: // T -> T1 * F v1 = value_stack[vtop--]; v2 = value_stack[vtop--]; value_stack[++vtop] = v1 * v2; break; case 4: // T -> F break; case 5: // F -> (E) break; case 6: // F -> 1 value_stack[++vtop] = 1; break; case 7: // F -> 2 value_stack[++vtop] = 2; break; case 8: // F -> 3 value_stack[++vtop] = 3; break; case 9: // F -> 4 value_stack[++vtop] = 4; break; case 10: // F -> 5 value_stack[++vtop] = 5; break; } }

// LR分析函数 int parse(char input) { int state = 0; int i = 0; while(1) { int lookahead; if(input[i] == 'n') { lookahead = 0; } else if(input[i] == '+') { lookahead = 1; } else if(input[i] == '') { lookahead = 2; } else if(input[i] == '(') { lookahead = 3; } else if(input[i] == ')') { lookahead = 4; } else if(input[i] == '1') { lookahead = 5; } else if(input[i] == '2') { lookahead = 6; } else if(input[i] == '3') { lookahead = 7; } else if(input[i] == '4') { lookahead = 8; } else if(input[i] == '5') { lookahead = 9; } else if(input[i] == '\0') { lookahead = 6; } else { printf('Error: invalid input\n'); return -1; } int action = action_table[state][lookahead]; if(action == 0) { printf('Error: invalid input\n'); return -1; } else if(action == 999) { return value_stack[vtop]; } else if(action > 0) { symbol_stack[++top] = action; state = action; i++; } else { int reduce_num = -action; for(int j = 0; j < reduce_num; j++) { reduce(); } int goto_state = goto_table[symbol_stack[top]][reduce_num - 1]; symbol_stack[++top] = goto_state; state = goto_state; } } }

int main() { char input[100]; printf('请输入算术表达式：'); scanf('%s', input); int result = parse(input); printf('结果为：%d\n', result); return 0; }