基于解析器组合子的语法解析器(上)
基于解析器组合子的语法解析器(上)
1.语法的来源
语法，在语言学中是指任意自然语言中句子、短语以及词汇等语法单位的语法结构与语法意义的规律，本质上即音义结合体之间的结合规律。在程序语言的范畴上，描述的则是基于文本的源码以特定规则放置，来表达其特有的语义内涵。
在语法的描述上，可以以任意方式来表达，但为保证准确无异议，通常都会采用 BNF 范式及其衍生版本等方式来进行形式化的定义，避免自然语言带来的歧义性。
$$
Expr ::= |
上述栗子中描述了一个表达式的简单定义，$Expr$是表达式的符号名称，其可以由$Var$(变量)、$Number$(数字)或$func$(函数)中的任意一个替换，其中$func$的参数是一个$Var$，函数体是另一个$Expr$。
2.如何解析语法
2.1 解析语法的运作
语法解析的运作，是将输入的原始文本按照给定的语法规则，在一定的上下文环境中，通过扫描和匹配，将原始文本转换为具有特定语义的结构化数据。例如，在解析1 + 2这样的原始文本时，如果依据$Expr ::= 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 解析器的接口定义
在实现单元构建之前，需要先来梳理一下解析器的功能。对于每一个解析器，其目标是将输入的内容，按照一定的规则进行匹配，之后将匹配的结果作为输出向后传递，作为下一个解析器的输入，以此往复，直到最后得出想要的结果为止。
基于上述描述，可以得出，解析器需要有一个输入源，以及一个在当前环节执行成功或失败后的下一步操作。于是可以将其定义为：
scheme
(lambda (src k-succ k-fail) ...)
其中，src是输入源，k-succ是当次解析成功后的下一步操作，k-fail是当次解析失败后的下一步操作，参数名中的k，描述的是continuation的含义，代表着接下来要做的事情。
3.1.2 单位元解析器
在定义完解析器的接口后，便可以开始构造最基础的元解析器。
首先要引入的，是二个是最简单的解析器，其不对输入进行任何解析，只是单纯的认为当次解析的结果为成功或失败，在概念上与加法中的0和乘法中的1相似，作为单位元来使用：
```scheme ;不解析, 直接返回成功 (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 序列、选择解析器
有了单位元解析器，便可以组合出接下来的两个最重要的复合解析器——序列解析与选择解析：
```scheme ;序列匹配: 全部成功才成功 (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序列的解析器：
``scheme
;匹配字符的解析器
(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 ?、*及+解析器
有了序列匹配与选择匹配，接下来便可以构造出更加实用的三个解析器：正则表达式中的?(零个或一个)、*(零个或多个)和+(一个或多个)。
```scheme ;匹配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 个或多个的解析器：
``scheme
((@:* (&: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 的起始行列号记录下来，便于与源文件中的位置进行关联。因此，其结构可以简单定义如下：
scheme
'(token symbol (row col))
其中，token是对象的类型标记；如果symbol是数字时，则转换为数字存储，否则依旧以字符串存储。
4.2.2 词法解析器的上下文环境
在解析的过程中，由于字符序列的匹配是通过更小的解析器来完成的，因此需要一个缓存空间来容纳每一步的中间产品，因此对于输入源，其结构可以简单定义如下：
scheme
'(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 子解析器的实现
有了上述对相关结构的定义，则可以定义出匹配单个字符的解析器：
``scheme
;通用的匹配解析器
(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 的解析器：
scheme
;将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-?!]*
标识符的首字符必须为字母，之后可以跟任意多个字母、数字或-?!等符号，其对应的解析器为：
scheme
(define %:identifier
(lambda ()
(%:token
(@:seq
(%:alpha)
(@:* (@:opt (%:alpha) (%:digit) (%:char #\-) (%:char #\?) (%:char #\!))))
list->string)))
可以看到，解析器组合子在描述构成规则时，与定义几乎一致，直观明了。list->string描述了需要将stash-ls中的字符列表转换为字符串存储。
接下来描述数字的定义规则：
number = (+|-)?\d+(\.\d+)?
数字支持最简单的整数和浮点数表达，暂不支持科学计数法及非十进制数字。其对应的解析器为：
scheme
(define %:number
(lambda ()
(%:token
(@:seq
(@:? (@:opt (%:char #\+) (%:char #\-)))
(@:+ (%:digit))
(@:? (@:seq (%:char #\.) (@:+ (%:digit)))))
list->number)))
接下来描述注释的定义规则：
comment = #[^\n]*
注释的起始为#，之后直至换行符之前的所有符号，都算作注释的内容。其对应的解析器为：
scheme
(define %:comment
(lambda ()
(%:token
(@:seq
(%:char #\#)
(@:* (%:match (lambda (ch) (not (eq? ch #\newline))))))
list->string)))
有了上述的标识符、数字及注释解析器后，还有部分符号和空白符需要解析，其对应的解析器为：
```scheme ;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)))
```
对于空白和注释，在本文的语境下，可以将其简单的进行丢弃处理，因此，还需要新增一个处理丢弃的解析器：
scheme
(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)))))
最后，组合上述的几个解析器，便可以构造出最终的词法解析器：
scheme
;(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 流为：
scheme
((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 节点的定义。
scheme
(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 语法解析器的上下文环境
与词法解析器一样，语法解析器的定义也是由子解析器组合而成，因此同样存在中间态，所以在上下文的结构中，也需要暂存中间态的空间，其描述如下：
scheme
'(stx token-ls ast-space)
其中，ast-space是一个栈结构，由多层列表组成，每当暂存的 token 列表满足一个 AST 节点时，便将其整体出栈，组合成一个 AST 节点后，再重新入栈。
例如，当栈顶结构如下所示时，其栈顶已经符合func的 AST 定义，因此可以通过将其替换成ast-func结构，重新入栈：
```scheme ;替换前 (((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 子解析器的实现
语法解析器的定义，不同于词法解析器的地方在于，其内部会递归的调用，为了保证在互相调用时，不会造成死循环，因此，需要给每一个解析器都额外包一层函数，延迟内部的求值时机。对于延迟包装的实现，可以通过宏来实现：
scheme
(define-syntax-rule
($:: (name params ...) parser)
(define name
(lambda (params ...)
(lambda *as
(apply parser *as)))))
简述了语法解析的上下文后，便可以给出同词法解析器相似的通用匹配解析器：
scheme
($:: ($: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)))]))])))
有了通用的匹配解析器后，便可以依次构造出标识符解析器、数字解析器：
```scheme (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关键字，之后需要区分的是参数列表，最后是函数具体的表达式列表。因此，在定义复杂表达式的解析器前，首先增加一个对暂存区压栈的解析器：
scheme
($:: ($: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解析器：
``scheme
($:: ($: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：
```scheme ($:: ($:expr) (@:opt ($:call) ($:sample-expr)))
($:: ($:sample-expr) (@:opt ($:var) ($:num) ($:func) ($:cond))) ```
至此，语法解析器的定义已经完成。对其输入上述词法解析器的结果后，可以得到如下结构的语法树，为了便于阅读，此处略去具体的行列号：
scheme
(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)))
对于更复杂且嵌套多层调用的源码，也可以得到正确的语法树：
```scheme 带有多层嵌套且多次调用的源码： 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))) ```
5.总结
本文通过描述解析器组合子的定义与实现，实现了源码文本到语法树的整体流程。在接下来的文章中，会引入 GLL 的思想来处理左递归文法和二义文法，以及增加对匹配出错的定位报告，更加完善解析器的功能。
hi, 我是快手电商的Kaso.Lu
快手电商无线技术团队正在招贤纳士🎉🎉🎉! 我们是公司的核心业务线, 这里云集了各路高手, 也充满了机会与挑战. 伴随着业务的高速发展, 团队也在快速扩张. 欢迎各位高手加入我们, 一起创造世界级的电商产品~
热招岗位: Android/iOS 高级开发, Android/iOS 专家, Java 架构师, 产品经理(电商背景), 测试开发... 大量 HC 等你来呦~
内部推荐请发简历至 >>>我们的邮箱: [email protected] <<<, 备注我的花名成功率更高哦~ 😘