采用算符优先分析法对表达式 （不包括括号运算）进行分析，并给出四元式序列。，c语言代码实现

假设我们要对表达式 `i + j * k - m` 进行算符优先分析，其优先级表如下：

| | + | - | \* | / | i | j | k | m | $ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| + | > | > | < | < | < | < | < | < | > |
| - | > | > | < | < | < | < | < | < | > |
| \* | > | > | > | > | < | < | < | < | > |
| / | > | > | > | > | < | < | < | < | > |
| i | < | < | < | < | - | - | - | - | > |
| j | < | < | < | < | - | - | - | - | > |
| k | < | < | < | < | - | - | - | - | > |
| m | < | < | < | < | - | - | - | - | > |
| $ | < | < | < | < | - | - | - | - | - |

其中 `>` 表示优先级高于，`<` 表示优先级低于，`-` 表示不可能出现的情况。

使用算符优先分析法可得四元式序列如下：

1. t1 = j * k
2. t2 = i + t1
3. t3 = t2 - m

下面是 C 语言实现算符优先分析法的代码：

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

#define MAX_SIZE 50

// 运算符优先级表
char priority_table[9][9] = {
    {'>', '>', '<', '<', '<', '<', '<', '<', '>'},
    {'>', '>', '<', '<', '<', '<', '<', '<', '>'},
    {'>', '>', '>', '>', '<', '<', '<', '<', '>'},
    {'>', '>', '>', '>', '<', '<', '<', '<', '>'},
    {'<', '<', '<', '<', '-', '-', '-', '-', '>'},
    {'<', '<', '<', '<', '-', '-', '-', '-', '>'},
    {'<', '<', '<', '<', '-', '-', '-', '-', '>'},
    {'<', '<', '<', '<', '-', '-', '-', '-', '>'},
    {'<', '<', '<', '<', '<', '<', '<', '<', '-'}
};

// 符号栈
char stack[MAX_SIZE];
int top = -1;

// 操作数栈
char opd_stack[MAX_SIZE][MAX_SIZE];
int opd_top = -1;

// 操作符栈
char opr_stack[MAX_SIZE];
int opr_top = -1;

// 向符号栈中压入一个符号
void push(char c) {
    if (top == MAX_SIZE - 1) {
        printf("Stack overflow\n");
        exit(1);
    }
    stack[++top] = c;
}

// 从符号栈中弹出一个符号
char pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        exit(1);
    }
    return stack[top--];
}

// 向操作数栈中压入一个操作数
void push_opd(char *s) {
    if (opd_top == MAX_SIZE - 1) {
        printf("Operand stack overflow\n");
        exit(1);
    }
    strcpy(opd_stack[++opd_top], s);
}

// 从操作数栈中弹出一个操作数
void pop_opd(char *s) {
    if (opd_top == -1) {
        printf("Operand stack underflow\n");
        exit(1);
    }
    strcpy(s, opd_stack[opd_top--]);
}

// 向操作符栈中压入一个操作符
void push_opr(char c) {
    if (opr_top == MAX_SIZE - 1) {
        printf("Operator stack overflow\n");
        exit(1);
    }
    opr_stack[++opr_top] = c;
}

// 从操作符栈中弹出一个操作符
char pop_opr() {
    if (opr_top == -1) {
        printf("Operator stack underflow\n");
        exit(1);
    }
    return opr_stack[opr_top--];
}

// 获取两个操作数和一个操作符，生成一个新的四元式
void gen(char *opd1, char *opd2, char opr, char *result) {
    static int count = 0;
    sprintf(result, "t%d", ++count);
    printf("%s = %s %c %s\n", result, opd1, opr, opd2);
}

// 从符号栈中扫描一个符号
char get_symbol() {
    if (top == -1) {
        return '$';
    }
    return stack[top];
}

// 判断两个运算符的优先级关系
char precede(char opr1, char opr2) {
    int i, j;
    switch (opr1) {
        case '+': i = 0; break;
        case '-': i = 1; break;
        case '*': i = 2; break;
        case '/': i = 3; break;
        case 'i': i = 4; break;
        case 'j': i = 5; break;
        case 'k': i = 6; break;
        case 'm': i = 7; break;
        case '$': i = 8; break;
        default: printf("Invalid operator %c\n", opr1); exit(1);
    }
    switch (opr2) {
        case '+': j = 0; break;
        case '-': j = 1; break;
        case '*': j = 2; break;
        case '/': j = 3; break;
        case 'i': j = 4; break;
        case 'j': j = 5; break;
        case 'k': j = 6; break;
        case 'm': j = 7; break;
        case '$': j = 8; break;
        default: printf("Invalid operator %c\n", opr2); exit(1);
    }
    return priority_table[i][j];
}

// 对表达式进行算符优先分析
void analyze_expression(char *expr) {
    int i, j, len;
    char symbol, opr, opd1[MAX_SIZE], opd2[MAX_SIZE], result[MAX_SIZE];

    len = strlen(expr);
    push('$');
    for (i = 0; i < len; i++) {
        symbol = expr[i];
        while (precede(get_symbol(), symbol) == '>') {
            opr = pop();
            if (opr == '+' || opr == '-' || opr == '*' || opr == '/') {
                pop_opd(opd2);
                pop_opd(opd1);
                gen(opd1, opd2, opr, result);
                push_opd(result);
            }
            else if (opr == 'i' || opr == 'j' || opr == 'k' || opr == 'm') {
                push_opd(&opr);
            }
        }
        if (precede(get_symbol(), symbol) == '<') {
            push(symbol);
        }
    }
    while (get_symbol() != '$') {
        opr = pop();
        if (opr == '+' || opr == '-' || opr == '*' || opr == '/') {
            pop_opd(opd2);
            pop_opd(opd1);
            gen(opd1, opd2, opr, result);
            push_opd(result);
        }
    }
    printf("%s\n", opd_stack[opd_top]);
}

int main() {
    char expr[] = "i+j*k-m";
    analyze_expression(expr);
    return 0;
}

在该程序中，`push` 和 `pop` 分别用于操作符号栈，`push_opd` 和 `pop_opd` 分别用于操作数栈，`push_opr` 和 `pop_opr` 分别用于操作符栈。`precede` 函数用于判断两个运算符的优先级关系，`gen` 函数用于生成新的四元式。`analyze_expression` 函数实现算符优先分析算法，其实现步骤跟上面讲解的一致。