LR分析法和语法制导翻译法实现简单算术表达式求值

以下是生成的LR分析表：

状态 | ACTION | GOTO

0 | S5 | 1 1 | S6 | 2 2 | S7 | 3 3 | R4 | - 4 | S5 | 8 5 | R6 | - 6 | R7 | - 7 | R8 | - 8 | S9 | - 9 | R5 | -

其中，S表示移进，R表示规约，数字表示对应的产生式编号。

接下来，我们使用语法制导翻译法来实现简单算术表达式求值。我们需要为每个产生式定义一个语义动作，来计算表达式的值。

对于产生式'L→En'，我们可以定义一个计算表达式值的动作：

L.val = E.val

对于产生式'E→E1+T'，我们可以定义一个将两个操作数相加的动作：

E.val = E1.val + T.val

对于产生式'E→T'，我们可以直接将T的值赋给E：

E.val = T.val

对于产生式'T→T1*F'，我们可以定义一个将两个操作数相乘的动作：

T.val = T1.val * F.val

对于产生式'T→F'，我们可以直接将F的值赋给T：

T.val = F.val

对于产生式'F→(E)'，我们可以直接将E的值赋给F：

F.val = E.val

对于产生式'F→1'、'F→2'、'F→3'、'F→4'、'F→5'，我们可以直接将对应的数字赋给F：

F.val = 对应数字的值

接下来，我们使用LR分析表和语法制导翻译法，来解析输入的表达式，并计算表达式的值。

输入'3*(5+4)+2n'，初始状态为0，栈顶符号为'$'。

读入'3'，栈顶符号为'$3'，根据状态0和输入'3'，查表得到S5，将5压入栈中，栈变为'$35'。
读入''，栈顶符号为'$35'，根据状态5和输入''，查表得到S9，将9压入栈中，栈变为'$359'。
读入'('，栈顶符号为'$359'，根据状态9和输入'('，查表得到S5，将5压入栈中，栈变为'$3595'。
读入'5'，栈顶符号为'$3595'，根据状态5和输入'5'，查表得到S6，将6压入栈中，栈变为'$35956'。
读入'+'，栈顶符号为'$35956'，根据状态6和输入'+'，查表得到S7，将7压入栈中，栈变为'$359567'。
读入'4'，栈顶符号为'$359567'，根据状态7和输入'4'，查表得到S6，将6压入栈中，栈变为'$3595676'。
读入')'，栈顶符号为'$3595676'，根据状态6和输入')'，查表得到R7，执行规约操作，弹出6个符号，栈变为'$3595'，根据产生式'F→(E)'，将F.val设为E.val。
栈顶符号为'$3595'，根据状态5和输入'+'，查表得到R4，执行规约操作，弹出3个符号，栈变为'$35'，根据产生式'T→F'，将T.val设为F.val。
读入'2'，栈顶符号为'$35'，根据状态5和输入'2'，查表得到S6，将6压入栈中，栈变为'$356'。
读入'n'，栈顶符号为'$356'，根据状态6和输入'n'，查表得到R5，执行规约操作，弹出3个符号，栈变为'$3'，根据产生式'E→T'，将E.val设为T.val。
读入'$'，栈顶符号为'$3'，根据状态1和输入'$'，查表得到R6，执行规约操作，弹出1个符号，栈变为空。

最终，我们得到了表达式的值，即L.val，为29。

下面是完整的C语言代码实现：

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

#define MAX_STACK_SIZE 100

typedef struct {
    int val;
} Entry;

Entry stack[MAX_STACK_SIZE];
int top = -1;

void push(Entry e) {
    if (top >= MAX_STACK_SIZE - 1) {
        printf("Stack overflow\n");
        exit(1);
    }
    stack[++top] = e;
}

Entry pop() {
    if (top < 0) {
        printf("Stack underflow\n");
        exit(1);
    }
    return stack[top--];
}

int main() {
    char input[] = "3*(5+4)+2n";
    int i = 0;

    // 初始化栈
    push((Entry) {0});

    while (input[i] != '\0') {
        switch (input[i]) {
            case '1':
                push((Entry) {1});
                i++;
                break;
            case '2':
                push((Entry) {2});
                i++;
                break;
            case '3':
                push((Entry) {3});
                i++;
                break;
            case '4':
                push((Entry) {4});
                i++;
                break;
            case '5':
                push((Entry) {5});
                i++;
                break;
            case '+':
                // 规约操作
                {
                    Entry T = pop();
                    pop();  // 弹出+
                    Entry E1 = pop();
                    pop();  // 弹出E
                    Entry E = pop();
                    // 计算E1+T
                    E.val = E1.val + T.val;
                    push(E);
                }
                break;
            case '*':
                push((Entry) {'*'});
                i++;
                break;
            case '(':
                push((Entry) {'('});
                i++;
                break;
            case ')':
                // 规约操作
                {
                    Entry E = pop();
                    pop();  // 弹出(
                    Entry F = pop();
                    pop();  // 弹出)
                    // 将F的值赋给E
                    E.val = F.val;
                    push(E);
                }
                break;
            case 'n':
                // 规约操作
                {
                    Entry T = pop();
                    pop();  // 弹出n
                    Entry E = pop();
                    // 将T的值赋给E
                    E.val = T.val;
                    push(E);
                }
                break;
            default:
                printf("Invalid input\n");
                exit(1);
        }
    }

    // 规约操作
    while (top > 0) {
        Entry T = pop();
        pop();  // 弹出*
        Entry T1 = pop();
        pop();  // 弹出T
        Entry T_new = (Entry) {0};
        // 计算T1*T
        switch (T.val) {
            case '*':
                T_new.val = T1.val * T_new.val;
                break;
            case '/':
                T_new.val = T1.val / T_new.val;
                break;
            default:
                printf("Invalid input\n");
                exit(1);
        }
        push(T_new);
    }

    // 输出结果
    printf("%d\n", pop().val);

    return 0;
}