PAYATHON 2026

递归下降解析遇到公共前缀时，应局部处理还是重构整个文法？

数据小许

对于题目中的赋值表达式，建议先做局部改写：解析公共的表达式部分，遇到 AssignmentOperator 后再决定是否构造赋值节点，并检查左侧是否符合 LeftHandSide。为了处理这一处冲突，不必把整个 JLS grammar 改写成严格的 LL(1) 文法。

这种处理需要明确解析函数的输入、输出和停止位置。这些约定比让每个函数逐字对应规范产生式更有帮助。

FIRST/FIRST 冲突不等于文法有歧义

仅凭当前的 identifier，无法判断应选择 AssignmentExpression 的哪个候选分支。这是预测分支的问题，并不能证明完整输入存在两种合法的解析结果。

读取 b 时也不必马上确定 b = c 属于哪个分支。可以先按表达式的优先级规则解析，等当前表达式结束后，如果下一个 token 是 =，再做决定。

公共前缀可能比单个 identifier 长得多：

object.field = value;
array[index] = value;
object.items[index].field = value;

因此，只在读取 identifier 时多看一个 token，无法普遍解决问题。先解析公共部分，也能避免为了寻找赋值运算符而重复扫描这部分输入。

在赋值表达式入口统一处理

可以将题目中的思路写成以下伪代码：

parseAssignmentExpression():
    left = parseConditionalExpression()

    if peekToken() not in AssignmentOperators:
        return left

    operator = consumeToken()
    requireLeftHandSideSyntax(left)
    right = parseExpression()

    return AssignmentNode(left, operator, right)

这段伪代码有三个前提：

  • parseConditionalExpression() 按优先级解析条件表达式，在遇到它不接受的顶层赋值运算符时停止。
  • requireLeftHandSideSyntax() 根据所支持的文法检查左侧的语法形态。
  • parseExpression() 能进入赋值表达式解析，从而继续处理右侧的赋值。

右侧调用 parseExpression()，与题目给出的 Assignment: LeftHandSide AssignmentOperator Expression 一致。如果你的 Java 子集把 Expression 简化为 AssignmentExpression，也可以直接调用 parseAssignmentExpression()。两者是否等价，取决于表达式入口是否还支持其他形式。

实现采用的识别步骤因此发生了变化。只要最终接受的输入符合目标文法，就不必将这种变化视为偏离规范的错误。

通过右侧递归保留赋值的右结合性

对于：

a = b = c;

外层先解析出 a，遇到 = 后进入右侧的表达式解析。右侧再解析 b，遇到第二个 = 后继续递归，最终形成：

Assignment(
    a,
    Assignment(b, c)
)

也就是：

a = (b = c);

不要用普通循环不断把已有结果作为新的左侧来构造赋值节点，否则容易错误地产生 (a = b) = c 的结构。

左侧检查要区分语法和语义

先解析 ConditionalExpression 会暂时接受一些不能作为赋值左侧的表达式，例如：

a + b = c;
f() = c;

识别到赋值运算符后，必须拒绝这些输入。前面的部分能解析为表达式，不代表它可以作为 AssignmentNode 的左侧。

对题目给出的文法，左侧的语法检查应对应 ExpressionName、FieldAccess 和 ArrayAccess。检查方法取决于 AST 的设计：可以检查节点类型，也可以让表达式解析结果携带语法类别信息。

检查时应注意两个边界：

  • 保留判断语法合法性所需的信息。如果 AST 提前消除了括号等语法结构，后续可能无法准确判断某个表达式是否符合目标文法。
  • 语法形态合法不代表赋值在语义上也合法。名称是否表示可赋值变量、目标是否受到 final 限制、左右类型是否兼容，通常还需要在名称解析和类型检查阶段判断。

因此，requireLeftHandSideSyntax() 应负责语法检查，避免把所有赋值合法性检查都混进解析函数。

让局部处理有固定边界

可以明确各函数的约定：

  • parseConditionalExpression() 返回条件表达式，不消费当前层的赋值运算符。
  • parseAssignmentExpression() 负责识别赋值运算符、检查左侧语法形态并构造赋值节点。
  • parseExpression() 作为表达式入口，根据所支持的 Java 子集分派。

不要为了处理赋值，让 parseConditionalExpression() 直接消费顶层赋值。其他调用点可能依赖它原有的语法边界。

“在赋值运算符前停止”只针对当前层。嵌套结构内部能否包含赋值，应由对应的产生式决定，不能扫描到任何 = 就立即停止。

AssignmentOperators 集合和 LeftHandSide 检查可以集中维护，避免不同解析路径各自复制规则。报错时尽量保留左侧表达式和运算符的位置，以便报告“赋值左侧不合法”或“赋值运算符后缺少表达式”等具体原因。

什么时候需要进一步重构文法

这里的局部处理本身也是文法改写，涉及赋值表达式这一小块。

如果某种公共前缀反复出现在多个入口，或者局部判断开始依赖深层调用状态，值得把这部分文法和对应解析代码一起整理。仅为了消除所有 FIRST/FIRST 冲突而全面重写规范文法，未必能改善手写解析器的可维护性。

实践中可以保留规范中的概念和命名，在采用不同识别步骤的地方注明对应产生式、改写原因和额外检查。

测试应覆盖接受范围和 AST 结构

完整测试集能降低回归风险，但测试数量本身不能证明局部改写与目标文法等价。测试需要覆盖正常输入、非法输入和分支边界。

针对这里的改动，可以重点检查：

测试输入检查重点
表达式入口中的 a + b * c普通表达式的优先级保持正确
a = b = c;AST 表示右结合赋值
object.field = value;FieldAccess 可以作为赋值左侧
array[index] = value;ArrayAccess 可以作为赋值左侧
a + b = c;拒绝不合法的赋值左侧
f() = c;拒绝方法调用表达式作为赋值左侧
a = ;报告缺少右侧表达式

如果子集支持复合赋值、条件运算符或其他表达式形式，还应增加它们与赋值相邻或嵌套的用例。除了检查解析是否成功，还应断言 AST 结构，并确认语句解析后到达预期的下一个 token，防止解析器只接受合法前缀而遗漏剩余输入。

备注：内容仅供参考。