7-5 LL(1)分析-最左推导 本题目为LL(1)分析程序最后一步，输出最左推导序列。 输入格式: 输入一个上下文无关文法，先输入文法产生式条数，再输入各个产生式，字符“ε”用“@”表示。 输入一个待分析的字符串，以"#"结束。 输出格式: 输出待分析字符串的最左推导。 输入样例: 在这里给出一组输入。例如： 9 S->MH S->a H->LSo H->@ K->dML K->@ L->eHf M->K M->bLM bef# 输出样例: 在这里给出相应的输出。例如： S=>MH=>bLMH=>beHfMH=>befMH=>befKH=>befH=>bef 代码长度限制 100 KB 时间限制 400 ms 内存限制 128 MB

由于题目中给出的是 LL(1) 文法，因此我们可以先构建 LL(1) 预测分析表，然后使用预测分析表进行最左推导。

下面给出完整的 Python 代码实现：

# 构建 LL(1) 预测分析表
def build_predictive_table(grammar):
    # 计算非终结符集合和终结符集合
    non_terminals = set()
    terminals = set()
    for left, right in grammar:
        non_terminals.add(left)
        for symbol in right:
            if symbol.isupper():
                non_terminals.add(symbol)
            else:
                terminals.add(symbol)
    # 构建预测分析表
    table = {}
    # 初始化预测分析表
    for non_terminal in non_terminals:
        table[non_terminal] = {}
        for terminal in terminals:
            table[non_terminal][terminal] = None
    # 填充预测分析表
    first_sets = compute_first_sets(grammar)
    follow_sets = compute_follow_sets(grammar, first_sets)
    for i, (left, right) in enumerate(grammar):
        for terminal in first_sets[right[0]]:
            table[left][terminal] = i
        if '@' in first_sets[right[0]]:
            for terminal in follow_sets[left]:
                table[left][terminal] = i
        for j in range(len(right) - 1):
            if '@' in first_sets[right[j]]:
                for terminal in first_sets[right[j + 1]]:
                    table[left][terminal] = i
                if j == len(right) - 2 and '@' in first_sets[right[j + 1]]:
                    for terminal in follow_sets[left]:
                        table[left][terminal] = i
    return table

# 计算 FIRST 集合
def compute_first_sets(grammar):
    first_sets = {}
    # 初始化 FIRST 集合
    for left, right in grammar:
        first_sets[left] = set()
    for terminal in TERMINALS:
        first_sets[terminal] = {terminal}
    first_sets['@'] = {'@'}
    # 不断循环直到 FIRST 集合不再变化
    while True:
        updated = False
        for left, right in grammar:
            old_first_set = first_sets[left].copy()
            if right[0] == '@':
                first_sets[left].add('@')
            elif right[0] in TERMINALS:
                first_sets[left].add(right[0])
            else:
                first_sets[left] |= first_sets[right[0]]
            for symbol in right[1:]:
                if '@' not in first_sets[symbol]:
                    break
                first_sets[left] |= first_sets[symbol] - {'@'}
            if first_sets[left] != old_first_set:
                updated = True
        if not updated:
            break
    return first_sets

# 计算 FOLLOW 集合
def compute_follow_sets(grammar, first_sets):
    follow_sets = {}
    # 初始化 FOLLOW 集合
    for left, right in grammar:
        follow_sets[left] = set()
    follow_sets[grammar[0][0]] = {'#'}
    # 不断循环直到 FOLLOW 集合不再变化
    while True:
        updated = False
        for left, right in grammar:
            for i, symbol in enumerate(right):
                if symbol in TERMINALS:
                    continue
                old_follow_set = follow_sets[symbol].copy()
                if i == len(right) - 1:
                    follow_sets[symbol] |= follow_sets[left]
                for j in range(i + 1, len(right)):
                    if '@' not in first_sets[right[j]]:
                        follow_sets[symbol] |= first_sets[right[j]] - {'@'}
                        break
                    follow_sets[symbol] |= first_sets[right[j]] - {'@'}
                    if j == len(right) - 1:
                        follow_sets[symbol] |= follow_sets[left]
                if follow_sets[symbol] != old_follow_set:
                    updated = True
        if not updated:
            break
    return follow_sets

# 使用 LL(1) 预测分析表进行最左推导
def leftmost_derivation(grammar, table, input_string):
    stack = ['#', grammar[0][0]]
    derivation = []
    i = 0
    while True:
        top = stack[-1]
        if top in TERMINALS:
            if top == input_string[i]:
                stack.pop()
                derivation.append(input_string[i])
                i += 1
            else:
                return None
        else:
            production_index = table[top][input_string[i]]
            if production_index is None:
                return None
            production = grammar[production_index]
            stack.pop()
            stack += reversed(production[1])
            derivation.append(production[1])
        if stack == ['#', grammar[0][0]] and input_string[i] == '#':
            return derivation

# 读入文法和待分析字符串
n = int(input())
grammar = []
for i in range(n):
    left, right = input().split('->')
    right = right.split()
    grammar.append((left, right))
input_string = input().strip() + '#'

# 计算终结符集合
TERMINALS = set()
for left, right in grammar:
    for symbol in right:
        if symbol not in TERMINALS and not symbol.isupper():
            TERMINALS.add(symbol)

# 构建 LL(1) 预测分析表
table = build_predictive_table(grammar)

# 使用 LL(1) 预测分析表进行最左推导
derivation = leftmost_derivation(grammar, table, input_string)

# 输出最左推导
if derivation is not None:
    print('=>'.join(derivation))
else:
    print('error')

该算法的时间复杂度为 $O(n^3)$，其中 $n$ 表示文法中的符号数目。