2018年8月25日 星期六

用 PEG 寫一個 C parser

故事是這樣子的,之前我們寫了一個自創的程式語言 Simple Language ,還用了 Rust 的 pest 幫他寫了一個 PEG parser,雖然說它沒有支援新加入的函式等等,本來想說如果年底的
MOPCON 投稿上的話就把它實做完,結果沒上,看來是天意要我不要完成它(欸

總而言之,受到傳說中的 jserv 大神的感召,就想說來寫一個複雜一點的,寫個 C language 的 PEG parser 如何?然後我就跳坑了,跳了才發現此坑深不見底,現在應該才掉到六分之一深界一層吧 QQQQ。
目前的成果是可以剖析 expression 並依照正確運算子順序處理,還有部分的 statement 也能正常剖析,因為通常能處理 expression 跟 statement 剖析裡麻煩的工作就完成 50 %,決定寫小文介紹一下,啊不過我還沒處理 expression 出現轉型的時候該怎麼辦,array reference 出現要怎麼辦,所以這部分可能還會改。
本來專案想取名叫 rcc 或 rucc,但這樣的專案名稱早就被其他人的 rust c compiler 用掉了,因為寫 Rust 的人好像都很喜歡用元素來當專案名稱,這個專案的名字就叫 Carbon 了XD。

其實寫這個跟寫 simple parser 沒什麼差,只是語法更加複雜,複雜之後就容易寫得沒有結構化;PEG 有個好處是在處理基礎的結構的時候,比起用 regular expression 各種複雜組合還要簡潔,像是 floating point 的時候,這是 C floating point 的語法,雖然這還不含 floating point 的 hex 表達式,但不負責任的臆測,要加上 hex 的支援只要多個 (decimal | hex) 的選擇就好了:
sign = { "+" | "-" }
fractional = { digit* ~ "." ~ digit+ | digit+ ~ "." }
exponent = { ("e" | "E") ~ sign? ~ digit+ }
floating_sfx = { "f" | "F" | "l" | "L" }
floating = @{ fractional ~ exponent? ~ floating_sfx? }

不過脫離基本結構,開始往上層架構走的時候麻煩就來了。
我的感想是,在大規模的語言剖析上 PEG 其實不是一個很好用的剖析方式,寫起來太隨興,沒有一套科學分析的方法告訴你怎麼樣寫比較好,甚至怎麼寫是對的,就連 C standard 的寫法都是用 CFG 可以處理的格式寫的,PEG 畢竟比較年輕才沒人鳥它;在傳統 CFG,List 就是用 List -> List x 那套來表達,在 PEG 裡卻可以直接把剖析的文法用 +, * 重複,層數相較 CFG 可以有效扁平化,相對應的壞處是很容易寫到壞掉,目前為止花了很大的心力在調整語法各部分的結構,非常耗費時間。

例如在剖析函式的內容,C 語法大概是這樣定義的:
compound_statement -> block_list
block_list -> block_list block
block -> declaration_list | statement_list
declaration_list -> declaration_list declaration
statement_list -> statement_list statement

上面這段大致體現了 declaration 跟 statement 交錯的寫法,一開始寫的時候,直譯就翻成
compound_statement -> block*
block -> declaration* ~ statement*

很直覺對吧?但上述的語法會直接進到無窮迴圈,上下層兩個連續的 * 或 + 是 PEG 語法的大忌,當上層跳入 * 無窮嘗試的時候,下層就算沒東西 match 了,照樣可以用 * 的空集合打發掉;同理上層是 + 下層是 * 也不行,理由相同;真正的寫法是上層用 * ,下層用 + ,在沒東西的時候由下層回傳無法匹配讓上層處理。
這個例子最後的寫法其實是這樣:
compound_statement -> block*
block -> (declaration | statement)+

或者是這樣,反正轉成 AST 之後也沒人在意 block 到底是只有 declaration 、只有 statement 還是兩個都有,乾脆把所有 declaration 跟 statement 都攪進一個 block 裡:
compound_statement -> block
block -> (declaration | statement)*

這個例子很明顯的體現出 PEG 文法的問題,透過文法加上 ?+*,我們可以很有效的把本來的 list 打平到一層語法,但連接數層的 +* 就需要花費時間調解層與層之間的融合,是一件複雜度有點高的事情。
很早之前在看參考資料的時候有看到這句,現在蠻有很深的體會:「我覺得用 PEG 類工具可以很快的擼出一個語法,是日常工作中的靠譜小助手,但要實現一個編程語言什麼的話,還得上傳統的那一套。」(註:原文為簡體中文此處直翻正體中文)
像是我的 simple parser 跟 regex parser,用 PEG 寫起來就很簡明,一到 C 這種複雜語言就頭大了;CFG 那邊的人大概會指著 PEG 的人說,你們 PEG 的人就是太自由了,哪像我們當年(誒

剖析寫完再來還要把文法轉譯成 AST。
在實作上大量參考強者我學長 suhorng 大大的 haskell C compiler 實作,想當初跟學長一起修 compiler,那時候我還很廢(其實現在也還是很廢),光是寫 C lex/yacc 能把作業寫出來不要 crash 就謝天謝地了,然後學長上課的時候 haskell 敲一敲筆電就把作業寫完了 QQQQ。

用 rust 的 pest PEG 套件寫轉換的程式,大部分都是 match rule ,看是哪種 Rule 之後去呼叫對應的函式來處理。
在expression 的部分可以直接使用 pest 提供的 precedence climbing 功能,無論是文法或建 AST 都很簡單,文法甚至可以收到一行,因為 expression 都是一樣的格式:
expression -> unary_expr (binary_op unary_expr)*
再到 precedence climbing 為所有 op 分出順序,就像 climb.rs 裡面那壯觀的 C operator 優先次序:
fn build_precedence_climber() -> PrecClimber<Rule> {
  PrecClimber::new(vec![
    Operator::new(Rule::op_comma,    Assoc::Left),
    Operator::new(Rule::op_assign_add,   Assoc::Right) |
    Operator::new(Rule::op_assign_sub,   Assoc::Right) |
    Operator::new(Rule::op_assign_mul,   Assoc::Right) |
    Operator::new(Rule::op_assign_div,    Assoc::Right) |
    Operator::new(Rule::op_assign_mod,  Assoc::Right) |
    Operator::new(Rule::op_assign_lsh,    Assoc::Right) |
    Operator::new(Rule::op_assign_rsh,    Assoc::Right) |
    Operator::new(Rule::op_assign_band, Assoc::Right) |
    Operator::new(Rule::op_assign_bor,    Assoc::Right) |
    Operator::new(Rule::op_assign_bxor,  Assoc::Right) |
    Operator::new(Rule::op_assign_eq,     Assoc::Right),
    Operator::new(Rule::op_qmark,    Assoc::Right) |
    Operator::new(Rule::op_colon,    Assoc::Right),
    Operator::new(Rule::op_or,       Assoc::Left),
    Operator::new(Rule::op_and,      Assoc::Left),
    Operator::new(Rule::op_bor,      Assoc::Left),
    Operator::new(Rule::op_bxor,     Assoc::Left),
    Operator::new(Rule::op_band,     Assoc::Left),
    Operator::new(Rule::op_eq,       Assoc::Left) |
    Operator::new(Rule::op_ne,       Assoc::Left),
    Operator::new(Rule::op_gt,       Assoc::Left) |
    Operator::new(Rule::op_lt,       Assoc::Left) |
    Operator::new(Rule::op_ge,       Assoc::Left) |
    Operator::new(Rule::op_le,       Assoc::Left),
    Operator::new(Rule::op_lsh,      Assoc::Left) |
    Operator::new(Rule::op_rsh,      Assoc::Left),
    Operator::new(Rule::op_add,      Assoc::Left) |
    Operator::new(Rule::op_sub,      Assoc::Left),
    Operator::new(Rule::op_mul,      Assoc::Left) |
    Operator::new(Rule::op_div,      Assoc::Left) |
    Operator::new(Rule::op_mod,      Assoc::Left),
  ])
}

match 之後一定有些規則是無法處理的,例如 match statement 的時候就不用管 op_binary 的 rule,這裡我寫了一個函式來承接這個規則,Rust 函式的 ! 型別相當於 C 的 noreturn,已經確定這個還是不會回傳值了,印出錯誤訊息後就讓程式崩潰;這個函式就能在任何 match 的 _ arm 上呼叫。
fn parse_fail(pair: Pair<Rule>) -> ! {
  let rule = pair.as_rule();
  let s = pair.into_span().as_str();
  unreachable!("unexpected rule {:?} with content {}", rule, s)
}
這樣這個函式就能出現在任何地方,例如 match 當中,每一條分支都應該要得到同樣的型別,不過這個函數可以是例外,畢竟它確定不會再回來了:
match (rule) {
  Rule::op_incr => Box::new(CastStmt::StmtPostfix(CastUnaryOperator::INCR, primary)),
  Rule::op_decr => Box::new(CastStmt::StmtPostfix(CastUnaryOperator::DECR, primary)),
  _ => parse_fail(pair),
}
我自己是覺得,把 PEG 文法剖析出來的結果轉換到 AST 上面,麻煩程度差不多就跟寫一個 recursive descent parser 差不多,而且用了 PEG 套件很難在使用者給了不正確程式時,給出有意義的錯誤訊息,我用的 pest 最多只能指著某個 token 大叫不預期這個 token ,預期要是哪些哪些。
到頭來要給出好一點的錯誤訊息跟發生錯誤的回歸能力,也許還真的只能像 gcc, llvm 一樣,直接幹一個 recursive descent parser。

不過以下是我不負責任的想法,我我暗暗覺得 PEG 的語法和 recursive descent parser 之間應該有某種對應的關係,也就是說,如果設計好 PEG ,應該能給出一個不錯的 recursive descent parser 的骨架,搭配使用者設計好在哪些文法遇到哪些錯誤該如何處理函式群,生出一個 recursive descent parser 來;不過以上只是不負責任的臆測,請各位看倌不要太當真。

這個專案其實還在草創階段,還有超多東西沒有支援(其實連個像樣的功能都沒有吧...),各位看倌大大手下留情QQQQ

下一步我也還沒想好怎麼做,之前有看到 rucc 的專案,是直接使用 rust 跟 LLVM 組合的套件,把剖析的程式碼直接轉成 LLVM IR,也許可以參考這種做法也說不定。


2018年8月17日 星期五

寫了一個不知道幹什麼用的 regex library 跟 parser

故事是這樣子的,之前寫 understanding computation 的時候,發現 regular expression 的實作,只有最基本的五種:empty 匹配空字串,literal 匹配文字、repeat * 匹配零個或多個 regex、concatenate 匹配連續的 regex、choose 匹配嘗試數個 regex。
大約幾天前想到也許可以把這個 project 拓展一些,讓它威力更強力一點點,順便當個練習。

預計要加入的東西有:
  • 支援 +, ? 兩種擴展的重複方式。
  • 支援 “.” 匹配 any character。
  • 支援 "[]", "[^]" 匹配在/不在集合中的字元。

+跟? 是最簡單的,它們和狀態機的設計無關,只要修改產生狀態機的方式即可;"*" 的時候是引入一個 start_state,將 start_state 和原本狀態機的 accept_state 加入新的 accept_state,並用 free_move 將 accept_state 跟原本狀態機的 start_state 連起來。
+ 的話是新的 start_state 不會是 accept_state 的一員。
? 的話是原本狀態機的 accept_state 不會用 free_move 和 start_state 連線。

Any 相對也很好做,本來我們的 farule 是一個 struct ,現在變成一個帶 enum type 的 struct,該有的都有:一個 state 到另一個 state;取決於 enum type ,會使用不同的 match 規則來決定適不適用規則。
像是 Any 就是全部都適用,literal char 的話會是比較一下字元是否相同。

[] 的實作…我發現到之前的實作,不太容易實作出 [^] 的規則。
[] 相對容易,簡單看來它就只是把裡面所有的字元變成 choose rule,例如 [a-z] -&gt; a|b|c..|z,但 [^] 就不同了,因為在 NFA 裡面,一個輸入的字元會跟所有可以嘗試的 rule 去匹配,但我們不可能把 [^] 之外所有的字元都接一個 choose 去 accept state (好吧理論上可以),如果在 [^a-z] 把 a-z 接去一個 dummy state, 用一個 any rule 接去 accept state,表示任何輸入的字元在嘗試 any rule 的時候都會通過它漏到 accept state 去。
最後還是在一條 rule set 裡面,保留所有可匹配字元的方式解決 QQ,這樣一來 match 一個字元的 rule 就變成這個 rule 的子集(不過為了方便還是保留這個 rule),接著 regex 的 [] [^] 就只是直接轉譯成 Rule set 就行了。

剩下的應該就只有改一下 PEG parser,這部分比較沒什麼,其實寫這個 project 沒什麼突破性的部分,大部分都是做苦工,好像沒什麼好值得說嘴的。
而且這樣改還有一個後遺症,就是匹配變得只能在 NFA 下進行,不能轉成 DFA 來做了,因為如 rule any, rule set 都會讓我們無法走訪目前所有可能的匹配結果,目前我看到市面上(?) 的 regular expression 實作,也都不是用這種 NFA 的方式在實作的,所以說我寫這個 project 到底是為了什麼……。

寫文章附上原始碼是常識我知道我知道:
https://github.com/yodalee/nfa_regex

當然還是有一些好玩的東西,例如測試可以任我寫:
https://github.com/yodalee/nfa_regex/blob/master/src/regular_expressions/mod.rs#L132