基於解析器組合子的語法解析器(上)

語言: CN / TW / HK

基於解析器組合子的語法解析器(上)

1.語法的來源

語法,在語言學中是指任意自然語言中句子、短語以及詞彙等語法單位的語法結構與語法意義的規律,本質上即音義結合體之間的結合規律。在程序語言的範疇上,描述的則是基於文本的源碼以特定規則放置,來表達其特有的語義內涵。

在語法的描述上,可以以任意方式來表達,但為保證準確無異議,通常都會採用 BNF 範式及其衍生版本等方式來進行形式化的定義,避免自然語言帶來的歧義性。

$$ Expr ::= | | func ( ) { } $$

上述栗子中描述了一個表達式的簡單定義,$Expr$是表達式的符號名稱,其可以由$Var$(變量)、$Number$(數字)或$func$(函數)中的任意一個替換,其中$func$的參數是一個$Var$,函數體是另一個$Expr$。

2.如何解析語法

2.1 解析語法的運作

語法解析的運作,是將輸入的原始文本按照給定的語法規則,在一定的上下文環境中,通過掃描和匹配,將原始文本轉換為具有特定語義的結構化數據。例如,在解析1 + 2這樣的原始文本時,如果依據$Expr ::= Expr + Expr$的語法規則,則可以將其轉換為根節點為+,兩個子節點各為12的樹狀結構。

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)又是由*12構成。

S表達式既可以描述程序,也可以描述數據(列表)。在描述程序時,括號括起的整個表達式被理解為函數(宏)調用,其括號中的左起第一個元素,用來描述整個表達式的功能,後續的元素,則作為該功能所依賴的參數。例如(* 1 2),其中*表示該表達式是一個乘法運算,而12,則作為該乘法運算的兩個參數。在描述數據時,如果與描述程序的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)表示該函數的參數列表,此處有xy兩個參數,(* x y)則作為該函數的函數體。在該函數被調用時,xy會被替換為實際參數後,執行對應的操作。如果需要操作函數的整個參數列表,則可以將參數列表的括號去掉,以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) ;將輸入源解構為strres,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))))) ```

其中,標識符解析的判斷邏輯是,符號不能為關鍵字且必須為字母開頭。

對於複雜表達式(funccond等),在解析的過程中,需要對暫存的棧空間增加新的層級,來區分每一部分的 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解析器,便可以繼續定義funccondcall解析器:

``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)))]))) ```

其中,funccond解析器基本同 EBNF 範式,在解析的過程中,額外增加了處理暫存空間的子解析器,但並沒有改變語法本身的描述,唯一的不同在於call的定義。由於call的 EBNF 定義中,其右側的產生式第一項便是Expr,屬於左遞歸語法,對於這樣的式子,普通的遞歸下降解析器無法簡單的處理,因此需要將其轉換為非左遞歸的描述,將遞歸的部分剝離出來,放在產生式的右側,避免死循環。另外,@:map的作用是,將解析成功後的結果在傳遞給下一個解析器前,做一次變換操作。

函數的連續調用,可以將其轉換為以下方式來描述:

在之後的文章中,會通過引入 GLL 的思想來支持左遞歸文法及二義文法。

最後,定義上述轉換後的exprsimple-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] <<<, 備註我的花名成功率更高哦~ 😘