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