lr分析程序

LR分析是一种自底向上的语法分析方法，常用于编译器中的语法分析。下面是一个简单的LR分析程序示例：

1. 定义文法产生式和文法符号。

# 定义文法产生式
E → E + T | T
T → T * F | F
F → ( E ) | id

# 定义文法符号
tokens = ['id', '+', '*', '(', ')']

2. 构建LR分析表。

# 定义LR分析表
action = [
    {'id': 's5', '(': 's4'},
    {'+': 's6', '$': 'acc'},
    {'*': 's7'},
    {'+': 'r2', '*': 'r2', ')': 'r2', '$': 'r2'},
    {'id': 's5', '(': 's4'},
    {'+': 'r4', '*': 'r4', ')': 'r4', '$': 'r4'},
    {'id': 's5', '(': 's4'},
    {'id': 's5', '(': 's4'},
    {'+': 'r6', '*': 'r6', ')': 'r6', '$': 'r6'},
    {'+': 's6', ')': 'r8', '$': 'r8'},
    {'+': 'r1', '*': 's7', ')': 'r1', '$': 'r1'},
    {'+': 'r3', '*': 'r3', ')': 'r3', '$': 'r3'},
    {'+': 'r5', '*': 'r5', ')': 'r5', '$': 'r5'}
]
goto = [
    {'E': 1, 'T': 2, 'F': 3},
    {},
    {},
    {},
    {'E': 8, 'T': 2, 'F': 3},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {}
]

3. 实现LR分析器。

# 实现LR分析器
def lr_parser(tokens, action, goto):
    stack = [0]
    i = 0
    while True:
        state = stack[-1]
        token = tokens[i]['type']
        if token not in action[state]:
            return False
        action_type, action_value = action[state][token][0], int(action[state][token][1:])
        if action_type == 's':
            stack.append(token)
            stack.append(action_value)
            i += 1
        elif action_type == 'r':
            production = action_value
            lhs, rhs = productions[production]
            for _ in range(len(rhs) * 2):
                stack.pop()
            state = stack[-1]
            stack.append(lhs)
            stack.append(goto[state][lhs])
        elif action_type == 'acc':
            return True

4. 运行LR分析器并输出结果。

# 运行LR分析器并输出结果
tokens = [{'type': 'id'}, {'type': '+'}, {'type': 'id'}, {'type': '*'}, {'type': 'id'}, {'type': '$'}]
if lr_parser(tokens, action, goto):
    print('Accepted')
else:
    print('Rejected')

以上就是一个简单的LR分析程序示例，可以用于分析输入的语法是否符合定义的文法。