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 代码实现： ```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$ 表示文法中的符号数目。