语法分析预测分析程序事例

以下是一个简单的语法分析预测分析程序的例子，用于识别给定的输入字符串是否符合以下语法规则：

S -> ( L )
L -> L , id | id

其中，S是起始符号，L是非终结符号，id是终结符号，逗号“,”和括号“()”是分隔符。

# 预测分析表
predictive_table = {
    ('S', '('): ('S', ['(', 'L', ')']),
    ('L', 'id'): ('L', ['id']),
    ('L', '('): ('L', ['L', ',', 'id'])
}

# 语法分析函数
def parse(input_string):
    stack = ['$','S']
    input_list = input_string.split()
    input_list.append('$')
    input_index = 0
    while len(stack) > 0 and input_index < len(input_list):
        top = stack[-1]
        lookahead = input_list[input_index]
        if top == lookahead:
            stack.pop()
            input_index += 1
        elif top in predictive_table and lookahead in predictive_table[top]:
            production = predictive_table[top, lookahead]
            stack.pop()
            for symbol in reversed(production[1]):
                stack.append(symbol)
        else:
            return False
    return True if input_index == len(input_list) else False

# 测试
print(parse('( id )'))  # True
print(parse('( id , id )'))  # True
print(parse('( id , )'))  # False
print(parse('( id id )'))  # False

该程序使用预测分析表来确定下一步应该采取哪个产生式。在分析过程中，将输入字符串和当前栈顶进行比较，如果相同，则将它们都从栈和输入列表中弹出；如果不同，则使用预测分析表查找下一个产生式，并将其反向压入栈中。如果栈为空或者输入列表已被完全读取，则分析成功并返回True，否则分析失败并返回False。