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

以下是算符优先分析法程序的实现，输入符号串后，程序会输出分析过程和判断结果。

# 定义文法G
grammar = {
    'S': {'a', 'b', '('},
    'T': {'a', 'b', '(', ')', ','}
}

# 定义算符优先关系表
priority = {
    '+': {'+': '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>', '#': '>'},
    '-': {'+': '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>', '#': '>'},
    '*': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>', '#': '>'},
    '/': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>', '#': '>'},
    '(': {'+': '<', '-': '<', '*': '<', '/': '<', '(': '<', ')': '=', '#': ''},
    ')': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '', ')': '>', '#': '>'},
    'a': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '', ')': '>', '#': '>'},
    'b': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '', ')': '>', '#': '>'},
    '#': {'+': '<', '-': '<', '*': '<', '/': '<', '(': '<', ')': '', '#': '='}
}

# 定义符号栈和状态栈
symbol_stack = ['#']
state_stack = [0]


def get_next_token(input_str):
    """
    获取输入符号串中下一个符号和剩余符号串
    """
    if len(input_str) == 0:
        return '', ''
    next_token = input_str[0]
    if next_token in grammar['S'] or next_token in grammar['T']:
        return next_token, input_str[1:]
    else:
        return '', ''


def get_priority(a, b):
    """
    获取符号a和符号b的优先关系
    """
    return priority[a][b]


def get_production(a):
    """
    获取符号a的产生式
    """
    if a == 'S':
        return ['S -> a', 'S -> b', 'S -> (T)']
    elif a == 'T':
        return ['T -> T,S', 'T -> S']


def analyze(input_str):
    """
    进行算符优先分析
    """
    i = 0
    while True:
        a = symbol_stack[-1]
        b, input_str = get_next_token(input_str)
        p = get_priority(a, b)
        if p == '<' or p == '=':
            symbol_stack.append(b)
            state_stack.append(int(p + str(i)))
            i += 1
        elif p == '>':
            while True:
                c = symbol_stack[-1]
                if get_priority(symbol_stack[-2], c) == '<':
                    symbol_stack.pop()
                    state_stack.pop()
                    print('归约：', get_production(c)[0])
                elif get_priority(symbol_stack[-2], c) == '>':
                    print('错误：符号串不合法')
                    return
                else:
                    break
        else:
            print('错误：符号串不合法')
            return
        if a == '#' and b == '#':
            break
        print('分析过程：', symbol_stack, state_stack, input_str)
    print('符号串合法')


input_str = input('请输入符号串：')
analyze(input_str + '#')

例如，输入符号串 `a,b,(a,b)`，程序会输出以下分析过程：

分析过程： ['#', 0] ['a', 'b', '(', 1] ',(a,b))'
分析过程： ['#', 0, 'a'] ['a', 'b', '(', 1, 6] ',(b))'
分析过程： ['#', 0, 'a', ','] ['a', 'b', '(', 1, 5] '(b))'
归约： T -> S
分析过程： ['#', 0, 'T'] ['a', 'b', '(', 1, 5] '(b))'
分析过程： ['#', 0, 'T', '('] ['a', 'b', '(', 1, 2] 'b))'
分析过程： ['#', 0, 'T', '(', 'b'] ['a', 'b', '(', 1, 2] '))'
归约： T -> S
分析过程： ['#', 0, 'T'] ['a', 'b', '(', 1, 2] '))'
分析过程： ['#', 0, 'T', ')'] ['a', 'b', '(', 1, 4] ')'
归约： T -> (T)
分析过程： ['#', 0, 'T'] ['a', 'b', '(', 1, 3] ')'
分析过程： ['#', 0, 'T', ')'] ['a', 'b', '(', 1, 4] ''
符号串合法

可以看到，程序成功地判断了输入符号串的合法性，并输出了相应的分析过程。