如何验证两个LR(1)分析表功能等价及LR(1)生成器测试资源

一、验证两个LR(1)分析表功能一致（状态编号不同） #

状态编号只是生成器内部的标识，核心是状态的项目集（含LR(1)展望符）和动作/转移逻辑的一致性，按以下步骤验证：

• 建立状态映射：把两个生成器的状态按「项目集+展望符完全匹配」配对，比如参考的状态7和你的状态9，只要它们的所有LR(1)项目（包括每个项目的展望符集合）完全相同，就标记为对应状态。
• 校验动作表：对每一对映射状态(s_ref, s_your)，遍历所有终结符：
  • 若参考表是「移进s_ref'」，你的表必须是「移进s_your'」，且s_ref'和s_your'是映射对；
  • 若参考表是「归约产生式P」，你的表必须也是归约完全相同的P；
  • 接受动作必须在相同的输入上下文触发。
• 校验转移表：对每一对映射状态，遍历所有非终结符，参考表转移到s_ref'，你的表必须转移到对应的s_your'。
• 用测试用例跑对比：拿同一组输入（合法/非法）分别跑两个分析器，只对比动作序列（移进哪个符号、归约哪个产生式、接受/报错），不用管状态编号，只要动作完全一致就说明功能等价。

二、不含ε产生式的复杂测试语法 #

以下几种资源/语法可以直接用：

• 扩展表达式语法：支持多运算符和函数调用，比如：

  E → E + T | E - T | T
  T → T * F | T / F | F
  F → (E) | id | id(ArgList)
  ArgList → ArgList , E | E
  

• C语言子集（无ε版）：聚焦变量声明、赋值、结构化语句，比如：

  Program → DeclList StmtList
  DeclList → DeclList Decl | Decl
  Decl → Type Id ;
  Type → int | float | char
  StmtList → StmtList Stmt | Stmt
  Stmt → AssignStmt | IfStmt | Block
  AssignStmt → Id = Expr ;
  IfStmt → if ( Expr ) Block else Block
  Block → { StmtList }
  Expr → Expr + Term | Term
  Term → Id | Num | ( Expr )
  

• 教材改编示例：龙书、虎书里的LR(1)示例，去掉所有含ε的产生式即可，比如把原有的Stmt → ε删掉，调整成必须有语句块。

三、避免遍历输入的无限循环 #

列表类语法会产生无限多输入，不用全遍历，用有限覆盖策略：

• 覆盖所有产生式：每个产生式至少被归约一次，比如对E→E+T，测试id（归约T→id、E→T）、id+id（归约E→E+T）、id+id+id（多次归约E→E+T）。
• 覆盖所有动作类型：测试移进、归约、接受、报错四种场景，比如报错场景测id+（缺少右操作数）、(id（未闭合括号）。
• 覆盖状态转移路径：因为LR(1)的状态数是有限的，遍历所有状态的所有可能输入符号（终结符），验证每个状态的动作是否符合预期，确保没有遗漏的转移逻辑。
• 等价类划分：把输入分成合法/非法两大块，合法块再按结构分（单表达式、带括号、带函数调用、嵌套块等），非法块分（符号错误、语法不完整、类型不匹配等），每个类选1-2个代表测试。

内容的提问来源于stack exchange，提问作者Chris Geo