文章/答案/技术大牛

发布

社区首页 >专栏 >基于解析器组合子的语法解析器(上)

基于解析器组合子的语法解析器(上)

原创

黄啊码

发布于 2022-06-20 01:40:02

2.7K00

代码可运行

文章被收录于专栏：黄啊码【CSDN同名】黄啊码【CSDN同名】

运行总次数：0

代码可运行

基于解析器组合子的语法解析器(上)

1.语法的来源

语法，在语言学中是指任意自然语言中句子、短语以及词汇等语法单位的语法结构与语法意义的规律，本质上即音义结合体之间的结合规律。在程序语言的范畴上，描述的则是基于文本的源码以特定规则放置，来表达其特有的语义内涵。

在语法的描述上，可以以任意方式来表达，但为保证准确无异议，通常都会采用 BNF 范式及其衍生版本等方式来进行形式化的定义，避免自然语言带来的歧义性。

Expr::=<Var>∣<Number>∣func(<Var>){<Expr>}Expr ::= <Var> | <Number> | func ( <Var> ) \{ <Expr> \}Expr::=<Var>∣<Number>∣func(<Var>){<Expr>}

上述栗子中描述了一个表达式的简单定义，ExprExprExpr是表达式的符号名称，其可以由VarVarVar(变量)、NumberNumberNumber(数字)或funcfuncfunc(函数)中的任意一个替换，其中funcfuncfunc的参数是一个VarVarVar，函数体是另一个ExprExprExpr。

2.如何解析语法

2.1 解析语法的运作

语法解析的运作，是将输入的原始文本按照给定的语法规则，在一定的上下文环境中，通过扫描和匹配，将原始文本转换为具有特定语义的结构化数据。例如，在解析1 + 2这样的原始文本时，如果依据Expr::=Expr+ExprExpr ::= Expr + ExprExpr::=Expr+Expr的语法规则，则可以将其转换为根节点为+，两个子节点各为1和2的树状结构。

2.2 解析语法的方案

市面上的语法解析方案已经非常成熟，从手写的递归下降分析到自动生成解析代码的 Yacc、ANTLR 生成器等等。另外可使用的算法也非常丰富，包括 LL、LR 以及其各种衍生变体。在实际使用中，由于 Yacc、ANTLR 等生成器使用自己特有的语法来描述目标语言的语法规则，在调试与维护中难免有诸多不便。因此，现在有许多语言重新选择了手写解析器，以开发语言自身来描述目标语言的语法规则，从而可以更好的优化与扩展。今天要介绍的解析器组合子，便是手写递归下降分析器中的一种。

2.3 Racket语言

本文所采用的开发语言，是一门很容易上手的 Lisp 方言 —— Racket，其使用的S表达式与模式匹配等特性，可以有效的控制解析过程整体的复杂度，避免由于语言自身的细节干扰所带来的诸多麻烦。

由于Racket等Lisp方言通常使用S表达式作为语法，其与市面上常见的编程语言语法有较大差异，因此在这里简要介绍一下本文所使用到的部分。

2.3.1 S表达式

S表达式可以由单个元素构成(如数字、变量等), 也可以由括号框选的复合元素嵌套组合构成。例如(+ (* 1 2) 3)，其中最外层的S表达式由+、(* 1 2)和3构成，而(* 1 2)又是由*、1和2构成。

S表达式既可以描述程序，也可以描述数据(列表)。在描述程序时，括号括起的整个表达式被理解为函数(宏)调用，其括号中的左起第一个元素，用来描述整个表达式的功能，后续的元素，则作为该功能所依赖的参数。例如(* 1 2)，其中*表示该表达式是一个乘法运算，而1和2，则作为该乘法运算的两个参数。在描述数据时，如果与描述程序的S表达式同时存在时，便需要对其进行区分标记。在Racket中，不做任何标记的S表达式，会作为程序表达，而作为数据的S表达式，则需要使用(quote (x y z))的方式进行标记，通常简写为'(x y z) 。

2.3.2 define与lambda

当需要定义一个符号时，可以使用define来实现，例如定义x等于5，则可以表达成(define x 5)，后续使用x时则等价于使用5。

对于匿名函数的表达，则需要使用lambda来实现，例如声明一个乘法函数，可以表示为(lambda (x y) (* x y))。其中(x y)表示该函数的参数列表，此处有x、y两个参数，(* x y)则作为该函数的函数体。在该函数被调用时，x和y会被替换为实际参数后，执行对应的操作。如果需要操作函数的整个参数列表，则可以将参数列表的括号去掉，以list的方式进行使用，例如(lambda nums (apply + nums))。

由于Racket是一门函数式语言，函数可以被作为参数和返回值进行传递。因此，如果需要返回一个函数，则可以直接在函数体内声明另一个函数即可，例如(lambda (x) (lambda (y) (+ x y)))，其被调用时，会返回一个(lambda (y) (+ x y))函数作为返回值，其中x的值是外部函数调用时传递的实际参数。

3.解析器组合子(Parser Combinator)

解析器组合子本质上是一种高阶对象，其接收多个其他解析器作为参数，构造出一个新的解析器。通过组合的方式由简到繁、由小到大的描绘出目标语言的语法规则。解析器组合子描述的分析器易于构造、结构良好、具有可读性且易于维护，很适用于规模不大且需要快速开发的场景。解析器组合子一般采用自顶向下的递归下降分析法，并在分析的过程中配合 GLL 等算法的思想，可以较好的处理左递归文法及二义文法。

3.1 如何实现解析器组合子

解析器组合子是由小到大、由简到繁构成的解析器。因此首先要实现的，便是其中最基础的单元构件。

3.1.1 解析器的接口定义

在实现单元构建之前，需要先来梳理一下解析器的功能。对于每一个解析器，其目标是将输入的内容，按照一定的规则进行匹配，之后将匹配的结果作为输出向后传递，作为下一个解析器的输入，以此往复，直到最后得出想要的结果为止。

基于上述描述，可以得出，解析器需要有一个输入源，以及一个在当前环节执行成功或失败后的下一步操作。于是可以将其定义为：

(lambda (src k-succ k-fail) ...)
复制代码

其中，src是输入源，k-succ是当次解析成功后的下一步操作，k-fail是当次解析失败后的下一步操作，参数名中的k，描述的是continuation的含义，代表着接下来要做的事情。

3.1.2 单位元解析器

在定义完解析器的接口后，便可以开始构造最基础的元解析器。

首先要引入的，是二个是最简单的解析器，其不对输入进行任何解析，只是单纯的认为当次解析的结果为成功或失败，在概念上与加法中的0和乘法中的1相似，作为单位元来使用：

;不解析, 直接返回成功
(define @:succ
  (lambda ()
    (lambda (src k-succ k-fail)
      (k-succ src))))

;不解析, 直接返回错误
(define @:fail
  (lambda ()
    (lambda (src k-succ k-fail)
      (k-fail src))))
复制代码

由于 Racket 对标识符命名的约束极少，只有特定几个字符不能用来命名，为了便于区分，对于元解析器的命名，均已@:开头(元->圆->@)，来表达其所属的范畴。

3.2.3 序列、选择解析器

有了单位元解析器，便可以组合出接下来的两个最重要的复合解析器——序列解析与选择解析：

;序列匹配: 全部成功才成功
(define @:seq
  (lambda *ps
    ;当前解析器匹配成功后, 执行下一个解析器, 只要有一个匹配失败, 则整体就失败
    ;p1.succ -> p2.succ -> ... -> pn.succ -> @:succ
    (foldr
      (lambda (p p-succ)
        ;这里返回一个新的解析器
        (lambda (src k-succ k-fail)
          (p src (lambda (cur) (p-succ cur k-succ k-fail)) k-fail)))
      (@:succ)
      *ps)))

;选择匹配: 任意成功则成功
(define @:opt
  (lambda *ps
    ;当前解析器匹配失败后, 执行下一个解析器, 只要有一个匹配成功, 则整体就成功
    (foldr
      (lambda (p p-fail)
        ;这里返回一个新的解析器
        (lambda (src k-succ k-fail)
          (p src k-succ (lambda (cur) (p-fail src k-succ k-fail)))))
      (@:fail)
      *ps)))
复制代码

其中，*ps表示接收多个解析器参数，并将其作为列表使用。foldr和其他语言中的reduce函数相同，不过是从列表的末尾开始递归。

序列解析器通过接收多个子解析器，以从头到尾的顺序依次连接，只有输入源通过了全部的解析后，才认为当次的解析成功，在逻辑上与and相同。选择解析器的功能与序列解析器相似，但表达的是or的概念，只要有一个子解析器匹配成功，则认为当次的解析成功。

例如要从HelloWorld中匹配到Hello序列，首先需要构造一个匹配字符的解析器，之后按照Hello的顺序依次将对应字符的解析器传递给序列解析器，便可生成一个可以匹配Hello序列的解析器：

;匹配字符的解析器
(define &:char
  (lambda (ch)
    (lambda (src k-succ k-fail)
      ;将输入源解构为`str`和`res`, `str`为输入的字符串, `res`为命中匹配后的结果
      (match-let ([`(,str ,res) src])
        (if (eq? (string-ref str 0) ch)
          ;如果字符串的首字母和`ch`相同, 则认为匹配成功
          ;将`str`中命中的字符剔除, 并将其保存在`res`中
          (k-succ `(,(substring str 1) ,(cons ch res)))
          ;否则认为匹配失败
          (k-fail src))))))

;生成匹配`Hello`的解析器
(define &:hello
  (lambda ()
    ;将`Hello`按顺序传入
    (@:seq (&:char #\H) (&:char #\e) (&:char #\l) (&:char #\l) (&:char #\o))))

((&:hello)
 ;构造输入源, '() 提供一个容纳匹配结果的地方
 (list "HelloWorld" '())
 ;匹配成功时的回调
 (lambda (cur)
   (match-let ([`(,str ,res) cur])
     (printf "res: ~a~nstr: ~a~n" (reverse res) str)))
 ;匹配失败时的回调
 (lambda (cur)
   (error '&:hello "match failure")))

;输出结果:
;res: (H e l l o)
;str: World
复制代码

3.2.4 `?`、`*`及`+`解析器

有了序列匹配与选择匹配，接下来便可以构造出更加实用的三个解析器：正则表达式中的?(零个或一个)、*(零个或多个)和+(一个或多个)。

;匹配0个或1个
(define @:?
  (lambda (p)
    (@:opt p (@:succ))))

;匹配0个或多个
(define @:*
  (lambda (p)
    ;这里会依赖`@:+`, 为了避免在调用时出现死循环, 通过包裹一层`lambda`来实现延迟求值
    (lambda *as (apply (@:opt (@:+ p) (@:succ)) *as))))

;匹配1个或多个
(define @:+
  (lambda (p)
    ;这里会依赖`@:*`, 为了避免在调用时出现死循环, 通过包裹一层`lambda`来实现延迟求值
    (lambda *as (apply (@:seq p (@:* p)) *as))))
复制代码

由于@:*与@:*互相递归，为了在调用时避免形成死循环，因此通过外包一层函数来达到延迟求值的目的。

例如要从aaabcc中匹配尽可能多的a，则可以向@:*传递一个匹配a的解析器，来生成可以匹配 0 个或多个的解析器：

((@:* (&:char #\a))
 (list "aaabcc" '())
 (lambda (cur)
   (match-let ([`(,str ,res) cur])
     (printf "res: ~a~nstr: ~a~n" (reverse res) str)))
 (lambda (cur)
   (error '&:hello "match failure")))

;输出结果
;res: (a a a)
;str: bcc
复制代码

至此，几个最核心的元解析器就介绍完了，下面，通过使用上述的元解析器，来实现一个具体的词法解析器。

4.词法解析器与语法解析器

4.1 目标语言的定义

在实现词法解析器之前，首先来定义一下需要解析的目标语言——MiniLambda(随便起了一个名字)，其是一个由表达式构成，包含数字、函数和条件判断的简单语言。表达式内部可以嵌套子表达式，以#开头的一行作为注释，函数可以作为参数和返回值进行传递。其定义如下：

例如：

# comment
func (x) {
  cond {
    eq?(x, 0) -> 1
    else -> mul(x, x)
  }
}(5)
复制代码

4.2 词法解析器的定义与实现

词法解析器的目的，是将程序文本按照词法规则，解析为一组由特定字符序列组合而成的 token 列表，作为后续的语法解析器的输入。

4.2.1 token 的结构

在解析的时，为了保留更多的源文件上下文信息，可以将每一个 token 的起始行列号记录下来，便于与源文件中的位置进行关联。因此，其结构可以简单定义如下：

'(token symbol (row col))
复制代码

其中，token是对象的类型标记；如果symbol是数字时，则转换为数字存储，否则依旧以字符串存储。

4.2.2 词法解析器的上下文环境

在解析的过程中，由于字符序列的匹配是通过更小的解析器来完成的，因此需要一个缓存空间来容纳每一步的中间产品，因此对于输入源，其结构可以简单定义如下：

'(lex char-list stash-list token-list (cur-row cur-col) (row col))
复制代码

其中，char-list是待匹配的字符流，stash-list是记录匹配中间态的列表，token-list是记录已经匹配到的 token 流，(cur-row cur-col)和(row col)分别记录了当前步骤的行列号与当前匹配 token 的起始行列号。

4.2.3 子解析器的实现

有了上述对相关结构的定义，则可以定义出匹配单个字符的解析器：

;通用的匹配解析器
(define %:match
  (lambda (func) ;接收一个检测函数
    (lambda (src k-succ k-fail)
      (match src
        ;如果当前字符流已空, 则认为匹配失败
        [`(lex ,(? empty?) . ,_)
          (k-fail src)]
        [`(lex (,cur . ,rst) ,stash-ls ,token-ls (,cur-row ,cur-col) ,idx)
          (cond
            ;如果检测失败, 则认为匹配失败
            [(not (func cur))
             (k-fail src)]
            ;对于非换行符, 则递增列号
            [(not (eq? cur #\newline))
             (k-succ `(lex ,rst ,(cons cur stash-ls) ,token-ls (,cur-row ,(add1 cur-col)) ,idx))]
            ;对于换行符, 则将列号置为1, 同时递增行号
            [(k-succ `(lex ,rst ,(cons cur stash-ls) ,token-ls (,(add1 cur-row) 1) ,idx))])]))))

;匹配字母
(define %:alpha
  (lambda ()
    (%:match char-alphabetic?)))

;匹配数字
(define %:digit
  (lambda ()
    (%:match char-numeric?)))

;匹配指定字符
(define %:char
  (lambda (char)
    (%:match (curry eq? char))))
复制代码

之后，再定义一个可以将准备好的字符列表转换为 token 的解析器：

;将stash-ls中保存的已经匹配到的字符转换为token对象
(define %:token
  (lambda (p func) ;由外部指定stash-ls的合成规则
    (lambda (src k-succ k-fail)
      (p src
        (lambda (cur)
          (match cur
            [`(lex ,char-ls ,stash-ls ,token-ls ,cur-idx ,idx)
              ;stash-ls的更新是通过压栈的方式操作的, 因此里需要对其做一个反转, 恢复正确的顺序
              (let ([token `(token ,(func (reverse stash-ls)) ,idx)])
                (k-succ `(lex ,char-ls () ,(cons token token-ls) ,cur-idx ,cur-idx)))]
              ;如果解构失败, 则认为匹配失败
            [_(begin (pretty-printf "%:token ~a~n" cur) (k-fail cur))]))
        k-fail))))
复制代码

有了可以将字符列表转换为 token 的解析器后，接下来便可以定义匹配具体 token 的解析器了。

首先可以定义的，是标识符的解析器，其对应的词法规则可以通过如下正则描述：

identifier = \w[\w\d-?!]*
复制代码

标识符的首字符必须为字母，之后可以跟任意多个字母、数字或-?!等符号，其对应的解析器为：

(define %:identifier
  (lambda ()
    (%:token
     (@:seq
      (%:alpha)
      (@:* (@:opt (%:alpha) (%:digit) (%:char #\-) (%:char #\?) (%:char #\!))))
      list->string)))
复制代码

可以看到，解析器组合子在描述构成规则时，与定义几乎一致，直观明了。list->string描述了需要将stash-ls中的字符列表转换为字符串存储。

接下来描述数字的定义规则：

number = (+|-)?\d+(\.\d+)?
复制代码

数字支持最简单的整数和浮点数表达，暂不支持科学计数法及非十进制数字。其对应的解析器为：

(define %:number
  (lambda ()
    (%:token
     (@:seq
      (@:? (@:opt (%:char #\+) (%:char #\-)))
      (@:+ (%:digit))
      (@:? (@:seq (%:char #\.) (@:+ (%:digit)))))
      list->number)))
复制代码

接下来描述注释的定义规则：

comment = #[^\n]*
复制代码

注释的起始为#，之后直至换行符之前的所有符号，都算作注释的内容。其对应的解析器为：

(define %:comment
  (lambda ()
    (%:token
     (@:seq
      (%:char #\#)
      (@:* (%:match (lambda (ch) (not (eq? ch #\newline))))))
      list->string)))
复制代码

有了上述的标识符、数字及注释解析器后，还有部分符号和空白符需要解析，其对应的解析器为：

;symbol = !\alpha
(define %:symbol
  (lambda ()
    (%:token
      (%:match (lambda (ch) (not (or (char-alphabetic? ch) (char-numeric? ch)))))
      list->string)))

;whitespace => \S+
(define %:whitespace
  (lambda ()
    (%:token
      (@:+ (%:match char-whitespace?))
      list->string)))

(define %:string
  (lambda (str)
    (%:token
     ;这里将字符串映射为解析器列表转入`@:seq`
     (apply @:seq (map (lambda (ch) (%:match (curry eq? ch)))
                       (string->list str)))
     list->string)))
复制代码

对于空白和注释，在本文的语境下，可以将其简单的进行丢弃处理，因此，还需要新增一个处理丢弃的解析器：

(define %:skip
  (lambda (p)
    (lambda (src k-succ k-fail)
      (p src
        (lambda (cur)
          (match cur
            [`(lex ,char-ls ,stash-ls ,token-ls ,cur-idx ,idx)
              (k-succ `(lex ,char-ls ,stash-ls ,(if (empty? token-ls) token-ls (cdr token-ls)) ,cur-idx ,cur-idx))]
            [_(begin (pretty-printf "%:skip ~a~n" cur) (k-fail cur))]))
        (~ k-fail)))))
复制代码

最后，组合上述的几个解析器，便可以构造出最终的词法解析器：

;(identifier|number|skip(whitespace+)|skip(comment)|->|symbol)+
(define %:scan
  (lambda ()
    (lambda (src k-succ k-fail)
      ((@:+
        (@:opt
         (%:identifier)
         (%:number)
         (%:skip (%:whitespace))
         (%:skip (%:comment))
         (%:string "->")
         (%:symbol)))
       src
       (lambda (cur)
         (match cur
           [`(lex ,char-ls ,stash-ls ,token-ls ,cur-idx ,idx)
             (k-succ (reverse token-ls))]
           [_(begin (pretty-printf "%:scan ~a~n" cur) (k-fail cur))]))
       k-fail))))
复制代码

以介绍 MiniLambda 时的源码为例，在通过词法解析器后，生成的 token 流为：

((token func (3 1))
 (token ( (3 6))
 (token x (3 7))
 (token ) (3 8))
 (token { (3 10))
 (token cond (4 3))
 (token { (4 8))
 (token eq? (5 5))
 (token ( (5 8))
 (token x (5 9))
 (token , (5 10))
 (token 0 (5 12))
 (token ) (5 13))
 (token -> (5 15))
 (token 1 (5 18))
 (token else (6 5))
 (token -> (6 10))
 (token mul (6 13))
 (token ( (6 16))
 (token x (6 17))
 (token , (6 18))
 (token x (6 20))
 (token ) (6 21))
 (token } (7 3))
 (token } (8 1))
 (token ( (8 2))
 (token 5 (8 3))
 (token ) (8 4)))
复制代码

4.3 语法解析器的定义与实现

有了词法解析器，下一步便是基于 token 流进行语法解析了。

4.3.1 AST 的结构

语法解析器的构造与词法解析器类似，首先给出的，是各个 AST 节点的定义。

(ast-var symbol idx)
(ast-num number idx)
(ast-func args exprs idx)
(ast-cond (pred expr)* expr idx)
(ast-call func args* idx)
复制代码

每种节点的定义，基本与 EBNF 中的描述一致，只是额外附带了idx字段，便于解析出错时报告其在源码中的具体位置。有关错误的处理，会在之后详细介绍。

4.3.2 语法解析器的上下文环境

与词法解析器一样，语法解析器的定义也是由子解析器组合而成，因此同样存在中间态，所以在上下文的结构中，也需要暂存中间态的空间，其描述如下：

'(stx token-ls ast-space)
复制代码

其中，ast-space是一个栈结构，由多层列表组成，每当暂存的 token 列表满足一个 AST 节点时，便将其整体出栈，组合成一个 AST 节点后，再重新入栈。

例如，当栈顶结构如下所示时，其栈顶已经符合func的 AST 定义，因此可以通过将其替换成ast-func结构，重新入栈：

;替换前
(((ast-num 123 (1 15)))
 ((ast-var b (1 10)) (ast-var a (1 7)))
 ((ast-text func (1 1)))
 ())

;替换后
(((ast-func
   ((ast-var a (1 7)) (ast-var b (1 10)))
   ((ast-num 123 (1 15)))
   (1 1))))

复制代码

4.3.3 子解析器的实现

语法解析器的定义，不同于词法解析器的地方在于，其内部会递归的调用，为了保证在互相调用时，不会造成死循环，因此，需要给每一个解析器都额外包一层函数，延迟内部的求值时机。对于延迟包装的实现，可以通过宏来实现：

(define-syntax-rule
  ($:: (name params ...) parser)
  (define name
    (lambda (params ...)
      (lambda *as
        (apply parser *as)))))
复制代码

简述了语法解析的上下文后，便可以给出同词法解析器相似的通用匹配解析器：

($:: ($:match func)
     (lambda (src k-succ k-fail)
       (match src
         ;token流为空, 则认为匹配失败
         [`(stx ,(? empty?) . ,_)
           (k-fail src)]
         [`(stx ((token ,tkn ,idx) . ,rst) (,ret-stk . ,ast-stk))
           (let ([ret (func tkn idx)])
             (match ret
               ;外部返回了error, 则认为匹配失败
               [`(ast-error) (k-fail src)]
               ;外部要求跳过
               [`(ast-skip) (k-succ `(stx ,rst (,ret-stk . ,ast-stk)))]
               ;其他情况, 则认为匹配成功
               [_(k-succ `(stx ,rst (,(cons ret ret-stk) . ,ast-stk)))]))])))
复制代码

有了通用的匹配解析器后，便可以依次构造出标识符解析器、数字解析器：

(define *$:keyword* '("func" "cond" "else" "call"))

($:: ($:var)
     ($:match
      (lambda (tkn idx)
        (if
          (and
           (string? tkn)
           (not (member tkn *$:keyword*))
           (positive? (string-length tkn))
           (char-alphabetic? (string-ref tkn 0)))
         `(ast-var ,(string->symbol tkn) ,idx)
         `(ast-error)))))

($:: ($:num)
     ($:match
      (lambda (tkn idx)
        (if (number? tkn)
         `(ast-num ,tkn ,idx)
         `(ast-error)))))
复制代码

其中，标识符解析的判断逻辑是，符号不能为关键字且必须为字母开头。

对于复杂表达式(func、cond等)，在解析的过程中，需要对暂存的栈空间增加新的层级，来区分每一部分的 token 序列。例如，在func的匹配中，首先需要区分的是func关键字，之后需要区分的是参数列表，最后是函数具体的表达式列表。因此，在定义复杂表达式的解析器前，首先增加一个对暂存区压栈的解析器：

($:: ($:new-space [mark #f])
     (@:map
       (@:succ)
       (match-lambda
         [`(stx ,token-ls (,ret-stk . ,ast-stk))
          `(stx ,token-ls (,(if mark `(,mark) `()) ,ret-stk . ,ast-stk))])))
复制代码

外部可以通过mark参数指定该层的名称，默认为空。

有了new-space解析器，便可以继续定义func、cond及call解析器：

($:: ($:skip text)
     ($:match
      (lambda (tkn idx)
        (if (equal? tkn text)
         `(ast-skip)
         `(ast-error)))))

($:: ($:text text)
     ($:match
      (lambda (tkn idx)
        (if (equal? tkn text)
         `(ast-text ,tkn ,idx)
         `(ast-error)))))

($:: ($:func)
     (@:map
       (@:seq
         ($:new-space)
         ($:text "func")
         ($:skip "(")
         ($:new-space)
         (@:? (@:seq (@:* (@:seq ($:var) ($:skip ","))) ($:var)))
         ($:skip ")")
         ($:skip "{")
         ($:new-space)
         (@:+ ($:expr))
         ($:skip "}"))
       (match-lambda
         [`(stx ,token-ls (,exprs ,args ((ast-text "func" ,idx)) ,ret-stk . ,ast-stk))
           (let ([ast (cons `(ast-func ,(reverse args) ,exprs ,idx) ret-stk)])
            `(stx ,token-ls (,ast . ,ast-stk)))])))

($:: ($:cond)
     (@:map
      (@:seq
       ($:new-space)
       ($:text "cond")
       ($:skip "{")
       ($:new-space)
       (@:* (@:seq ($:expr) ($:skip "->") ($:expr)))
       ($:new-space)
       (@:seq ($:skip "else") ($:skip "->") ($:expr))
       ($:skip "}"))
      (match-lambda
        [`(stx ,token-ls ((,else-expr) ,pair-exprs ((ast-text "cond" ,idx)) ,ret-stk . ,ast-stk))
          (let loop ([pair-exprs pair-exprs] [cond-exprs '()])
            (match pair-exprs
              [`()
                (let ([ast (cons `(ast-cond ,cond-exprs ,else-expr ,idx) ret-stk)])
                 `(stx ,token-ls (,ast . ,ast-stk)))]
              [`(,cond-expr ,pred-expr . ,rst)
                (loop rst (cons `(,pred-expr ,cond-expr) cond-exprs))]))])))

($:: ($:call)
     (@:map
      (@:seq
       ($:new-space)
       ($:sample-expr)
       (@:+
        (@:seq
         ($:skip "(")
         ($:new-space "args")
         (@:? (@:seq (@:* (@:seq ($:expr) ($:skip ","))) ($:expr)))
         ($:skip ")"))))
      (match-lambda
        [`(stx ,token-ls ((,argss ... "args") ... (,func) ,ret-stk . ,ast-stk))
          (let ([ast-call (foldr (lambda (args func) `(ast-call ,func ,(reverse args) (0 0))) func argss)])
           `(stx ,token-ls (,(cons ast-call ret-stk) . ,ast-stk)))])))
复制代码

其中，func和cond解析器基本同 EBNF 范式，在解析的过程中，额外增加了处理暂存空间的子解析器，但并没有改变语法本身的描述，唯一的不同在于call的定义。由于call的 EBNF 定义中，其右侧的产生式第一项便是Expr，属于左递归语法，对于这样的式子，普通的递归下降解析器无法简单的处理，因此需要将其转换为非左递归的描述，将递归的部分剥离出来，放在产生式的右侧，避免死循环。另外，@:map的作用是，将解析成功后的结果在传递给下一个解析器前，做一次变换操作。

函数的连续调用，可以将其转换为以下方式来描述：

在之后的文章中，会通过引入 GLL 的思想来支持左递归文法及二义文法。

最后，定义上述转换后的expr与simple-expr：

($:: ($:expr)
     (@:opt
      ($:call)
      ($:sample-expr)))

($:: ($:sample-expr)
     (@:opt
      ($:var)
      ($:num)
      ($:func)
      ($:cond)))
复制代码

至此，语法解析器的定义已经完成。对其输入上述词法解析器的结果后，可以得到如下结构的语法树，为了便于阅读，此处略去具体的行列号：

(ast-call
 (ast-func
  ((ast-var x))
  ((ast-cond
    (((ast-call
       (ast-var eq?)
       ((ast-var x) (ast-num 0)))
      (ast-num 1)))
    (ast-call
     (ast-var mul)
     ((ast-var x) (ast-var x))))))
 ((ast-num 5)))
复制代码

对于更复杂且嵌套多层调用的源码，也可以得到正确的语法树：

带有多层嵌套且多次调用的源码：
func (Y) {
  Y(func (fact) {
      func (n) {
        cond {
          eq?(n, 1) -> 1
          else -> mul(n, fact(sub(n, 1)))
        }
      }
    })
}(func (wrap-func) {
    func (r-func) {
      r-func(r-func)
    }(func (real-func) {
        wrap-func(func (arg) {
          real-func(real-func)(arg)
        })
      })
  })(5)

语法树:
(ast-call
 (ast-call
  (ast-func
   ((ast-var Y))
   ((ast-call
     (ast-var Y)
     ((ast-func
       ((ast-var fact))
       ((ast-func
         ((ast-var n))
         ((ast-cond
           (((ast-call
              (ast-var eq?)
              ((ast-var n) (ast-num 1)))
             (ast-num 1)))
           (ast-call
            (ast-var mul)
            ((ast-var n)
             (ast-call
              (ast-var fact)
              ((ast-call
                (ast-var sub)
                ((ast-var n) (ast-num 1))))))))))))))))
  ((ast-func
    ((ast-var wrap-func))
    ((ast-call
      (ast-func
       ((ast-var r-func))
       ((ast-call (ast-var r-func) ((ast-var r-func)))))
      ((ast-func
        ((ast-var real-func))
        ((ast-call
          (ast-var wrap-func)
          ((ast-func
            ((ast-var arg))
            ((ast-call
              (ast-call
               (ast-var real-func)
               ((ast-var real-func)))
              ((ast-var arg)))))))))))))))
 ((ast-num 5)))
复制代码