将非LL(1)文法转换为LL(1)文法通常需要消除左递归和提取左公因子。以下是使用Python实现这两个主要步骤的示例代码： ```python # 消除左递归 def eliminate_left_recursion(grammar): new_grammar = {} for non_terminal, rules in grammar.items(): left_recursive_rules = [] non_left_recursive_rules = [] for rule in rules: if rule.startswith(non_terminal): left_recursive_rules.append(rule[1:]) else: non_left_recursive_rules.append(rule) if left_recursive_rules: new_non_terminal = non_terminal + "'" new_grammar[non_terminal] = [rule + new_non_terminal for rule in non_left_recursive_rules] new_grammar[new_non_terminal] = [rule + new_non_terminal for rule in left_recursive_rules] + [""] else: new_grammar[non_terminal] = rules return new_grammar # 提取左公因子 def left_factor(grammar): new_grammar = {} for non_terminal, rules in grammar.items(): prefix_count = {} for rule in rules: if rule: prefix = rule[0] if prefix not in prefix_count: prefix_count[prefix] = [] prefix_count[prefix].append(rule[1:]) new_rules = [] for prefix, sub_rules in prefix_count.items(): if len(sub_rules) > 1: new_non_terminal = non_terminal + "'" new_rules.append(prefix + new_non_terminal) new_grammar[new_non_terminal] = sub_rules else: new_rules.append(prefix + sub_rules[0]) new_grammar[non_terminal] = new_rules return new_grammar # 示例非LL(1)文法 grammar = { 'E': ['E+T', 'T'], 'T': ['T*F', 'F'], 'F': ['(E)', 'id'] } # 消除左递归 grammar = eliminate_left_recursion(grammar) # 提取左公因子 grammar = left_factor(grammar) print("转换后的LL(1)文法:") for non_terminal, rules in grammar.items(): print(f"{non_terminal} -> {' | '.join(rules)}") ``` 在上述代码中，`eliminate_left_recursion` 函数用于消除文法中的左递归，`left_factor` 函数用于提取左公因子。通过依次调用这两个函数，可以将非LL(1)文法转换为LL(1)文法。