Sly解析器递归定义类型实现及Matlab移植解析器问题咨询

一、Python Sly中expr递归生成的实现机制 #

Sly处理expr这类递归语法规则，并非依赖Python内置函数或类型，而是作为LALR(1)解析器生成器的核心特性来实现：

• 通过@_装饰器收集所有语法规则，示例代码如下：

  @_('expr PLUS term')
  @_('term')
  def expr(self, p):
      if len(p) == 3:
          return p.expr + p.term
      else:
          return p.term
  

• 收集完成后，Sly会自动构建文法，天然支持左递归（无需手动消除，这是LALR与LL解析器的核心区别）。它会生成LR项目集、计算Closure和GoTo函数，最终生成分析表。
• 运行阶段，解析器根据分析表的状态转移处理递归规则：遇到基础规则（expr -> term）时执行归约，遇到递归规则（expr -> expr PLUS term）时先移进符号，再归约为新的expr，不会陷入无限循环。

二、Matlab中实现递归expr规则的方法 #

如果是手写移进归约解析器，核心是实现LALR分析表的状态转移逻辑，步骤如下：

1. 明确文法规则
   先定义带终止项的递归文法，示例：

   expr → expr + term | term
   term → NUM | ( expr )
   

   其中term是递归的基础终止项，保证解析过程能正常终止。
2. 手动生成分析表
   计算LR(1)项目集，生成包含移进、归约、接受动作的状态转移表。比如当栈顶状态对应expr且输入符号为+时执行移进；当栈内匹配expr + term时，归约为expr。
3. 栈模拟实现
   在Matlab中维护状态栈和符号栈两个栈结构：循环读取分词后的Token，根据当前栈顶状态和输入Token查询分析表，执行移进、归约或接受操作，完成递归结构的解析。

若不想手动编写分析表，也可使用Matlab第三方LALR解析器生成工具，通过类似Sly的规则定义方式自动生成解析器。

三、Sly中递归定义类型的实现方式 #

Sly中递归定义语法类型（非终结符）的方式非常直接：在装饰器的规则字符串中直接引用非终结符自身，分两种常见场景：

• 左递归定义（用于处理左结合表达式，比如加减运算）：

  @_('expr PLUS term')
  @_('expr MINUS term')
  @_('term')
  def expr(self, p):
      # 逻辑处理
  

• 右递归定义（用于处理右结合运算，比如幂运算）：

  @_('term POWER expr')
  @_('term')
  def expr(self, p):
      # 逻辑处理
  

Sly内部的处理逻辑：

1. 装饰器会将所有规则收集到文法中，无论是否存在递归引用。
2. 生成分析表时，Sly会自动处理递归带来的项目集，生成合法的状态转移规则，避免无限递归问题。
3. 运行阶段，解析器根据分析表的状态转移，正确处理递归结构的嵌套与归约。

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