如何将二元运算符表达式规则转为LL(1)文法并生成左结合AST

原左递归文法无法直接用于LL(1)分析，你提到的右递归改造方案虽然能识别合法语句，但会生成右结合的AST。要实现左结合AST，需要调整文法的递归逻辑并配合语义动作的节点累积：

调整后的LL(1)文法 #

program    ::= statement
statement  ::= expression ;
expression ::= number rest-expr
rest-expr  ::= binary-operator number rest-expr
             | ε

核心思路：通过语义动作实现左结合 #

LL(1)文法本身要求消除左递归，所以语法层面还是用右递归结构，但通过递归下降分析中的节点累积，可以生成左结合AST。对应的递归下降伪代码逻辑如下：

# 解析表达式入口
def parse_expression():
    # 先解析第一个数字，作为初始左节点
    left_node = parse_number()
    # 传入左节点处理后续运算符
    return parse_rest_expr(left_node)

# 处理后续运算符链，携带当前左节点
def parse_rest_expr(current_left):
    # 若当前前瞻符号是二元运算符
    if lookahead_token in binary_operators:
        # 消耗运算符
        op = consume_operator()
        # 解析运算符后的数字作为右节点
        right_node = parse_number()
        # 构建新的左结合节点：用当前左节点和新右节点结合
        new_left = create_ast_node(op, current_left, right_node)
        # 把新节点作为左节点，继续处理后续运算符
        return parse_rest_expr(new_left)
    # 无后续运算符，返回当前累积的左节点
    else:
        return current_left

效果示例 #

对于语句4 + 3 + 3;，处理流程为：

1. 解析4得到节点N4，传入parse_rest_expr
2. 识别+，解析3得到N3，构建节点+(N4, N3)，传入parse_rest_expr
3. 识别+，解析3得到N3，构建节点+(+(N4, N3), N3)，传入parse_rest_expr
4. 无后续运算符，返回最终节点，即左结合的AST

这种方案既满足LL(1)文法的无左递归、无回溯要求，又能生成符合左结合语义的AST。

内容的提问来源于stack exchange，提问作者bruh bruhbruhbruh69