基于导数的解析（Parsing with derivatives）中间节点实现问题咨询

问题背景 #

我正在研究导数解析的derp-latest版本代码，处理自然CFG解析时遇到两个问题：

• 目前能生成解析树，但无法输出中间节点名称，只能得到纯结构
• 已知有Haskell实现可以生成带中间节点的解析树，但我无法理解该实现的代码

我尝试给∘（连接运算符）显式添加节点名称，测试效果尚可，但不确定这种方法是否正确；同时还没找到★（闭包运算符）的解决方案，暂时在D函数中注释掉了相关代码。

现有代码 #

(define-lazy-struct δ {lang})
(define-lazy-struct ∪ {this that})
(define-lazy-struct ∘ {name left right})
(define-lazy-struct ★ {lang})
(define-lazy-struct → {lang reduce})

; Derivative:
(define/memoize (D c p)
  #:order ([p #:eq] [c #:equal])
  (match p
    [(∅)           (∅)]
    [(ε _)         (∅)]
    [(δ _)         (∅)]
    [(token p?)    (cond
                     [(equal? p? c) (ε (set c))] ; [(p? c) (ε (set c))]
                     [else   (∅)])]
    
    [(∪ p1 p2)     (∪ (D c p1) 
                      (D c p2))]
    ; [(★ p1)        (∘ (D c p1) p)]
    [(→ p1 f)      (→ (D c p1) f)]
    [(∘ name p1 p2)     (∪ (∘ name (δ p1) (D c p2))
                           (∘ name (D c p1) p2))]))

(define/fix (parse-null p)
  #:bottom (set)
  (match p
    [(ε S)        S] ; 
    [(∅)          (set)]
    [(δ p)        (parse-null p)]
    [(token _)    (set)]
    [(★ _)        (set '())]
    [(∪ p1 p2)    (set-union (parse-null p1) (parse-null p2))]
    [(∘ name p1 p2)    (for*/set ([t1 (parse-null p1)]
                                  [t2 (parse-null p2)])
                         (cons name (cons t1 t2)))]
    [(→ p1 f)     (for/set ([t (parse-null p1)])
                    (f t))]))

测试案例 #

测试1：基础CFG解析 #

(define N (∪ (∘ "N" (token 'man) (ε (set '())))
             (∘ "N" (token 'girl) (ε (set '())))
             ))

(define Det (∪ (∘ "Det" (token 'the) (ε (set '())))
           (∘ "Det" (token 'a) (ε (set '())))
           ))

(define V (∪ (token 'kill)
             (token 'hit)
             ))

(define NP (∪ (∘ "NP" Det N)
          (∘ "NP" N (ε (set '())))))

(define VP (∘ "VP" V NP))

(parse '(kill girl girl) VP)

输出结果（符合预期）：

> (set '("VP" kill "NP" ("Det" the) "N" girl))

测试2：嵌套节点解析 #

(define NP2 (∘ "NP2" NP (ε (set '()))))

(parse '(girl) NP2)

输出结果（符合预期）：

> (set '("NP2" ("NP" ("N" girl))))

我的问题 #

1. 这种给∘显式添加节点名称的实现方法是否正确？有没有更优的方案？
2. 如果该方法正确，如何修复★运算符的处理逻辑？

解答 #

问题1：∘运算符的实现正确性与优化方案 #

你的实现思路是正确的。在导数解析中，∘对应CFG中的非终结符连接规则，给它绑定节点名称后，在parse-null中通过cons name (cons t1 t2)将节点名与子树组合，完全符合解析树的结构要求，测试结果也验证了这一点。

更优方案可以从以下方向考虑：

• 统一元数据管理：给所有需要生成节点的语法构造（∘、★等）都添加名称字段，而不是仅给∘单独扩展，让节点命名逻辑在语法结构层面保持一致，降低后续维护成本。
• 解耦解析树构造逻辑：用独立的“标签”结构包裹语法规则（比如(label "NP" p)），而非修改原有∘的结构。这样对导数解析的核心逻辑侵入更小，也能灵活控制哪些规则需要生成节点名称。

问题2：★运算符的修复方案 #

★（闭包运算符）对应CFG中的重复规则（如A → A α | ε），要生成带节点名称的解析树，需要给★添加名称字段，并修改D函数与parse-null的处理逻辑：

步骤1：修改★的结构定义

给★添加name字段，用于存储节点名称：

(define-lazy-struct ★ {name lang})

步骤2：恢复并修改D函数中的★处理逻辑

闭包的导数公式为D_c(p★) = (D_c p) ∘ p★，这里需要保留节点名称，生成带对应名称的∘结构：

[(★ name p1)  (∘ name (D c p1) p)] ; p为当前的★节点，递归处理闭包

步骤3：修改parse-null中的★处理逻辑

闭包的空解析结果是ε（空序列），而匹配到重复内容时，需要用节点名称包裹所有子树。利用闭包的定义★p = ε ∪ p ∘ ★p，可以这样实现：

[(★ name p1)
 (letrec ([null-★ (set-union
                   (set '()) ; 空序列
                   (for*/set ([t (parse-null p1)]
                              [t★ null-★])
                     (cons name (cons t t★))))])
   null-★)]

测试示例

定义带名称的闭包：

(define List (★ "List" N))
(parse '(man girl) List)

预期输出：

(set '() ("List" ("N" man)) ("List" ("N" man) ("N" girl)))

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