实验4：算符优先分析法程序设计 题目： 根据 文法G 利用算符优先分析法设计一个简 单语法分析程序 要求：输入一个符号串，判断是否是该文法所能推导 出来的句子。如果是，则输出“Yes”，并能输 出分析过程（格式见教材80页表4.5）；否则， 输出“No”，并输出已经完成的分析过程。 文法G(S): S→a S→b S→(T) T→T,S T→S，使用C语言

以下是算符优先分析法程序设计的C语言代码实现：

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

#define MAXLEN 100 // 最大输入串长度
#define MAXSTACK 100 // 分析栈最大长度

// 定义符号、运算符优先关系表
char priorityTable[6][6] = {
    { '>', '>', '<', '<', '<', '>' },
    { '>', '>', '<', '<', '<', '>' },
    { '>', '>', '>', '>', '<', '>' },
    { '>', '>', '>', '>', '<', '>' },
    { '<', '<', '<', '<', '<', '=' },
    { '>', '>', '>', '>', ' ', '>' }
};

// 将符号转换为表格中的数字
int getSymbolCode(char symbol) {
    switch (symbol) {
    case 'a': return 0;
    case 'b': return 1;
    case '(': return 2;
    case ')': return 3;
    case ',': return 4;
    case '#': return 5;
    default: return -1;
    }
}

// 定义分析栈结构体
typedef struct {
    char symbol; // 符号
    int priority; // 优先级
} StackItem;

// 定义分析栈
StackItem stack[MAXSTACK];
int top = -1; // 栈顶指针

// 将符号入栈
void push(char symbol, int priority) {
    top++; // 栈顶指针加1
    stack[top].symbol = symbol; // 入栈
    stack[top].priority = priority;
}

// 弹出栈顶符号
StackItem pop() {
    StackItem item = stack[top]; // 取出栈顶元素
    top--; // 栈顶指针减1
    return item; // 返回栈顶元素
}

// 获取栈顶符号
StackItem getTop() {
    return stack[top];
}

// 执行算符优先分析
int operatorPrecedenceAnalysis(char* str) {
    int i = 0;
    char currentSymbol; // 当前符号
    char prevSymbol = '#'; // 前一个符号
    int currentPriority; // 当前符号的优先级
    int prevPriority; // 前一个符号的优先级
    StackItem stackItem; // 栈顶元素

    push('#', 5); // 先将#入栈

    // 从左往右扫描输入串
    while (i <= strlen(str)) {
        currentSymbol = str[i]; // 取出当前符号
        currentPriority = getSymbolCode(currentSymbol); // 获取当前符号的优先级

        // 如果当前符号非法，则输出错误信息并退出
        if (currentPriority == -1) {
            printf("Illegal symbol!\n");
            return 0;
        }

        stackItem = getTop(); // 取出栈顶元素
        prevPriority = getSymbolCode(stackItem.symbol); // 获取栈顶符号的优先级

        // 如果当前符号为#，则分析完成，退出循环
        if (currentSymbol == '#' && stackItem.symbol == '#') {
            printf("Yes\n"); // 是该文法所能推导出来的句子
            return 1;
        }

        // 根据符号的优先级进行操作
        if (priorityTable[prevPriority][currentPriority] == '<') {
            push(currentSymbol, currentPriority); // 当前符号入栈
            i++; // 扫描下一个符号
        }
        else if (priorityTable[prevPriority][currentPriority] == '=') {
            pop(); // 弹出栈顶元素
            i++; // 扫描下一个符号
        }
        else if (priorityTable[prevPriority][currentPriority] == '>') {
            stackItem = pop(); // 弹出栈顶元素

            // 输出分析过程
            printf("(%c,", stackItem.symbol);
            while (stackItem.priority >= prevPriority && stackItem.symbol != '#') {
                printf("%d)", stackItem.priority);
                stackItem = pop(); // 弹出栈顶元素
            }
            printf(",");

            push(stackItem.symbol, prevPriority); // 弹出栈顶元素后，当前符号入栈
        }
        else {
            printf("Error: invalid priority!\n"); // 优先级关系表错误
            return 0;
        }
    }

    printf("No\n"); // 不是该文法所能推导出来的句子
    return 0;
}

int main() {
    char str[MAXLEN]; // 输入串

    // 读入输入串
    printf("Enter a string: ");
    scanf("%s", str);

    // 执行算符优先分析
    operatorPrecedenceAnalysis(str);

    return 0;
}

运行程序后，输入符号串，程序将输出分析结果。如果符号串是该文法所能推导出来的句子，则输出“Yes”并输出分析过程；否则，输出“No”并输出已经完成的分析过程。