编译原理实验算符优先分析算法

算符优先分析法是一种自下而上的语法分析方法，它可以用于分析和处理算术表达式、布尔表达式等。下面是算符优先分析法的实现步骤：

1. 定义终结符和非终结符：终结符是指不能再分解的基本符号，如数字、运算符等；非终结符是指可以分解成其他符号的符号，如表达式、语句等。

2. 定义运算符之间的优先关系和结合性质：将运算符按照优先级从高到低排列，相同优先级的运算符再按照结合性质（左结合或右结合）进行排列。

3. 构造算符优先关系表：根据定义的运算符优先关系和结合性质，构造算符优先关系表。表中的行和列分别表示两个相邻的运算符，表中的元素表示它们之间的优先关系（“<”表示优先级低，“>”表示优先级高，“=”表示优先级相等）。

4. 进行语法分析：将输入的表达式转换成一个个终结符和非终结符的序列，然后根据算符优先关系表进行分析。具体地，从左到右扫描输入序列，将扫描到的符号压入栈中，同时比较栈顶符号和下一个输入符号之间的优先关系，如果栈顶符号的优先级低于或等于下一个输入符号的优先级，则将下一个输入符号压入栈中；否则，从栈中弹出一个或多个符号进行归约，直到栈顶符号的优先级低于或等于下一个输入符号的优先级。

5. 进行表达式求值：在进行归约时，如果遇到两个相邻的终结符之间有一个运算符，则可以对它们进行求值，并将结果压入栈中。最终，栈中只剩下一个值，即为表达式的值。

下面是一个简单的算符优先分析法的实现例子，用于分析和处理四则运算表达式：

# 定义终结符和非终结符
terminals = ['+', '-', '*', '/', '(', ')', 'num']
non_terminals = ['E', 'T', 'F']

# 定义运算符之间的优先关系和结合性质
precedence = {
    '+': {'+': '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>', 'num': '<'},
    '-': {'+': '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>', 'num': '<'},
    '*': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>', 'num': '<'},
    '/': {'+': '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>', 'num': '<'},
    '(': {'+': '<', '-': '<', '*': '<', '/': '<', '(': '<', ')': '=', 'num': '<'},
    ')': {'+': '>', '-': '>', '*': '>', '/': '>', '(': ' ', ')': '>', 'num': ' '},
    'num': {'+': '>', '-': '>', '*': '>', '/': '>', '(': ' ', ')': '>', 'num': ' '}
}

# 构造算符优先关系表
table = {}
for i in range(len(terminals)):
    table[terminals[i]] = {}
    for j in range(len(terminals)):
        table[terminals[i]][terminals[j]] = precedence[terminals[i]][terminals[j]]

# 进行语法分析
def parse(expr):
    stack = ['#']
    tokens = expr.split()
    for token in tokens:
        while table[stack[-1]][token] == '>':
            op = stack.pop()
            if op in ['+', '-', '*', '/']:
                b = stack.pop()
                a = stack.pop()
                stack.append(str(eval(a + op + b)))
            else:
                stack.pop()
        if table[stack[-1]][token] == '<' or table[stack[-1]][token] == '=':
            stack.append(token)
        else:
            raise ValueError('Invalid expression')
    while stack[-1] != '#':
        op = stack.pop()
        if op in ['+', '-', '*', '/']:
            b = stack.pop()
            a = stack.pop()
            stack.append(str(eval(a + op + b)))
        else:
            raise ValueError('Invalid expression')
    return stack[0]

# 进行表达式求值
expr = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
result = parse(expr)
print(result) # 输出：3.0001220703125