3.9考虑文法G[S]:S->(T)|a+S|a T->T，S｜S 第一步消除文法的左递归及提取公共左因子,然后第二步对每个非终结符写出不带回溯的递归 写出实现以上两步的代码（python）

在处理文法G[S]的左递归和提取公共左因子时，可以按照以下步骤编写Python代码：

首先，我们需要创建一个函数来合并公共左因子（这里就是"("和"S"），以及消除左递归。在这个例子中，我们可以看到公共左因子是一个简单的"("，而左递归体现在S -> a + S的形式上。

def eliminate_left_recursion(grammar):
    # 初始化一个空的变换规则字典
    transformed_rules = {}

    # 提取公共左因子
    left_factor = ""
    for rule in grammar.split("|"):
        if rule.startswith("(") and not rule[1:].startswith("("):  # 如果是公共左因子开头
            left_factor += rule[0]
            rule = rule[1:]
        transformed_rules[left_factor + rule] = rule

    # 消除左递归
    new_rules = []
    for rule in transformed_rules.values():
        if "+" in rule:
            # 将左递归替换为非递归形式
            non_recursive_rule = rule.replace("+", " * ").replace(rule.split("+")[1], "")
            non_recursive_rule = f"( {non_recursive_rule} )"
            new_rules.append(f"{rule[:-1]} -> {non_recursive_rule}")
        else:
            new_rules.append(rule)

    return "|".join(new_rules)

接下来，我们需要将非递归的规则转换成不包含回溯的形式，也就是将所有的"->"替换为"->>":

def convert_to_no_backtracking(grammar):
    no_backtracking_rules = [rule.replace("->", "->>") for rule in grammar.split("|")]
    return "|".join(no_backtracking_rules)

# 使用上面的函数处理给定的文法
original_grammar = "S->(T)|a+S|a\nT->T，S｜S"
no_left_recursion_grammar = eliminate_left_recursion(original_grammar)
final_grammar = convert_to_no_backtracking(no_left_recursion_grammar)

print("最终的无左递归和回溯的文法:")
print(final_grammar)

#