LL(1) 语法分析程序

LL(1)语法分析程序是一种自顶向下的语法分析方法，它可以根据输入的文法的FIRST(α)和FOLLOW(U)集，自动生成文法的预测分析表，并且可以判断该文法是否为LL(1)文法。LL(1)文法是指满足以下条件的上下文无关文法：
1. 对于文法中的每个非终结符A，FIRST(A)和FOLLOW(A)中没有交集。
2. 对于文法中的每个产生式A->α，FIRST(α)中不包含ε，则对于任意终结符a∈FIRST(α)，都有A->α是A->a的唯一产生式。

下面是LL(1)语法分析程序的基本流程：
1. 根据输入的文法，构造文法的FIRST集和FOLLOW集。
2. 根据文法的FIRST集和FOLLOW集，构造预测分析表。
3. 读入待分析的字符串，初始化分析栈和输入缓冲区。
4. 从输入缓冲区读入一个符号，将其与分析栈栈顶的符号进行比较。
5. 如果两个符号相同，则将它们都弹出；如果栈顶符号是非终结符，则查找预测分析表，将对应的产生式推入分析栈中；如果栈顶符号是终结符，则从输入缓冲区读入下一个符号。
6. 重复步骤4和5，直到分析栈为空或者输入缓冲区为空。

下面是一个LL(1)语法分析程序的Python实现示例：

# 输入文法的产生式
productions = {
    'E': ['T', 'E\''],
    'E\'': ['+', 'T', 'E\''],
    'T': ['F', 'T\''],
    'T\'': ['*', 'F', 'T\''],
    'F': ['(', 'E', ')'],
    'F': ['id']
}

# 输入文法的终结符和非终结符
terminals = ['+', '*', '(', ')', 'id']
non_terminals = ['E', 'E\'', 'T', 'T\'', 'F']

# 构造FIRST集
first = {
    'E': ['(', 'id'],
    'E\'': ['+', 'ε'],
    'T': ['(', 'id'],
    'T\'': ['*', 'ε'],
    'F': ['(', 'id']
}

# 构造FOLLOW集
follow = {
    'E': [')', '$'],
    'E\'': [')', '$'],
    'T': ['+', ')', '$'],
    'T\'': ['+', ')', '$'],
    'F': ['+', '*', ')', '$']
}

# 构造预测分析表
table = {}
for non_terminal in non_terminals:
    table[non_terminal] = {}
    for terminal in terminals:
        table[non_terminal][terminal] = []

for non_terminal in non_terminals:
    for production in productions[non_terminal]:
        if production == 'ε':
            for terminal in follow[non_terminal]:
                table[non_terminal][terminal].append(production)
        elif production in terminals:
            table[non_terminal][production].append(production)
        else:
            for terminal in first[production]:
                if terminal != 'ε':
                    table[non_terminal][terminal].append(production)
            if 'ε' in first[production]:
                for terminal in follow[non_terminal]:
                    table[non_terminal][terminal].append(production)

# 读入待分析的字符串
input_str = input('请输入待分析的字符串：')

# 初始化分析栈和输入缓冲区
stack = ['$']
stack.append('E')
input_buffer = list(input_str)
input_buffer.append('$')

# LL(1)语法分析程序
while len(stack) > 0 and len(input_buffer) > 0:
    top = stack[-1]
    next_input = input_buffer[0]
    if top == next_input:
        stack.pop()
        input_buffer.pop(0)
    elif top in non_terminals:
        production = table[top][next_input][0]
        if production == 'ε':
            stack.pop()
        else:
            stack.pop()
            for symbol in reversed(production):
                stack.append(symbol)
    else:
        print('Error: Invalid input string')
        break

if len(stack) == 0 and len(input_buffer) == 0:
    print('Input string is valid')
else:
    print('Input string is invalid')