基於解析器組合子的語法解析器(上)
基於解析器組合子的語法解析器(上)
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] <<<, 備註我的花名成功率更高哦~ 😘