递归下降LL(1)语法分析程序

递归下降LL(1)语法分析程序是一种基于递归的自顶向下的语法分析方法，用于分析和验证给定文法的输入串是否符合该文法。它通过递归地调用子程序来实现对输入串的分析。

以下是一个简单的递归下降LL(1)语法分析程序的示例：

# 定义文法规则
grammar = {
    'E': [['T', 'E\'']],
    'E\'': [['+', 'T', 'E\''], ['']],
    'T': [['F', 'T\'']],
    'T\'': [['*', 'F', 'T\''], ['']],
    'F': [['(', 'E', ')'], ['id']]
}

# 构造LL(1)分析表
analysis_table = {
    ('E', 'id'): ['T', 'E\''],
    ('E\'', '+'): ['+', 'T', 'E\''],
    ('E\'', ')'): [''],
    ('T', 'id'): ['F', 'T\''],
    ('T\'', '+'): [''],
    ('T\'', '*'): ['*', 'F', 'T\''],
    ('T\'', ')'): [''],
    ('F', 'id'): ['id'],
    ('F', '('): ['(', 'E', ')']
}

# 递归下降LL(1)语法分析函数
def parse(input_str):
    stack = ['$','E'] # 初始化分析栈
    input_str += '$' # 在输入串末尾添加结束符$
    i = 0 # 输入串指针
    while len(stack) > 0:
        top = stack[-1] # 栈顶符号
        if top == input_str[i]:
            stack.pop() # 匹配成功，弹出栈顶符号和输入串指针后移
            i += 1
        elif top in grammar.keys():
            production = analysis_table[(top, input_str[i])] # 查找分析表
            if production[0] == '':
                stack.pop() # 空产生式，弹出栈顶符号
            else:
                stack.pop() # 弹出栈顶符号
                stack.extend(reversed(production)) # 将产生式逆序入栈
        else:
            print("Error: Invalid input!")
            return False
    if input_str[i] == '$':
        print("Input is valid!")
        return True
    else:
        print("Error: Invalid input!")
        return False

# 测试语法分析程序
parse('id+id*id')

该程序首先定义了一个文法规则和LL(1)分析表。然后，通过递归下降的方式，从栈中取出符号进行匹配，并根据分析表进行相应的推导和规约操作，直到栈为空且输入串已经被完全匹配。