總之最近經過一陣猛烈的攪動之後,我的 parser 能處理的文法終於接近當年在學校修 compiler 的時候所要求的 B language 了,說來慚愧,當年寫 compiler 作業的時候 parser 只是裡面一個作業,要在 2-3 週裡面寫完的,結果現在搞半天寫不出個毛,果然上班跟上學還是不一樣,在學校可以全心全意投入寫 code ,週末的時候還可以熬個夜把作業寫出來;現在上班白天要改公司的 code ,晚上回家累個半死不想寫 code 只想開卡車(欸。
本篇講到的程式碼目前還沒推到遠端上,相關的程式碼可以參考:
AST 的資料結構:cast
型別的資料結構:ctype
既然現在可以處理比較複雜的文法了,再來要做什麼?想說就像作業的要求一樣,把我們處理好的 AST 用 graphviz 寫出去,是會有多難?
整個 dump graphviz 的進入點是一個函式,接收要倒出來的 AST 跟一個 out,out 的型別是 std::io::Write 的 dyn Write,這樣不管你是要寫到 stdout, stderr 還是寫到檔案都能傳進來,介面會是一樣的,函式的實作當然就是直接了當的把該印的東西都寫出去;另外實作一個 dump_node 幫我們把寫出一個 node 給獨立出來,id 會自動不斷累加,讓 node 的編號不會重複。
fn dump_graphviz(ast: CastTop, out: &mut dyn Write) { writeln!(out, "Digraph AST").unwrap(); writeln!(out, "{{").unwrap(); writeln!(out, "label = \"AST_Graph.gv\"").unwrap(); writeln!(out, "node{} [label = \"PROGRAM_NODE\"]", 0).unwrap(); ast.make_node(out, &mut 0); writeln!(out, "}}").unwrap(); } fn dump_node(out: &mut dyn Write, id: &mut u32, label: &str) { *id += 1; writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap(); }另外我們要實作的是 make_node,這裡很自然的就是先宣告一個 trait,AST 裡面所有的物件都要實作這個 trait ,就都有 make_node 可以用了。
trait ToGraphviz { fn make_node(&self, out: &mut dyn Write, id: &mut u32); } impl ToGraphviz for CastTop { fn make_node(&self, out: &mut dyn Write, id: &mut u32) { match self { CastTop::FuncDeclList(v) => { let cur_id = *id; for decl in v { dump_node(out, id, "DECLARATION_NODE FUNCTION_DECL"); decl.make_node(out, id); } if *id != cur_id { // new node writeln!(out, "node{} -> node{} [style = bold]", cur_id, cur_id + 1).unwrap(); } }, } } } impl ToGraphviz for FuncDecl { fn make_node(&self, out: &mut dyn Write, id: &mut u32) { let parent = *id; dump_node(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", "int")); dump_node(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", self.fun_name)); dump_node(out, id, "PARAM_LIST_NODE"); dump_node(out, id, "BLOCK_NODE"); for i in parent..*id { writeln!(out, "node{} -> node{} [style = {}]", i, i+1, if i == parent {"bold"} else {"dashed"}).unwrap(); } } }* :本來的作業要求連結第一個 child 的必須是實線,其他的用虛線,這裡沿用
這個實作的問題顯而易見,我們的輸出的實作跟資料綁死了,所以每個 node 裡面的實作都是大費周章,而且 code 很醜。
我們要更抽象化一點,其實輸出樹的邏輯是這樣子的:先寫 child 的 node,然後是自己,回傳自己的 id 給 parent,這樣上一層的人才能畫 edge 出來。
我們實作一個 dump_children 的函式,這個函式會用現在的 id 印出現在的 parent,然後把它跟所有傳進來的 children 畫線連起來:
fn dump_children(out: &mut dyn Write, id: &mut u32, label: &str, children: &[u32]) -> u32 { writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap(); let mut prev = *id; for child in children { writeln!(out, "node{} -> node{} [style = {}]", prev, child, if prev == *id { "bold" } else { "dashed" }).unwrap(); prev = *child; } *id+=1; *id-1 }因為 Rust 函式參數沒有預設值也沒有 overload,為了方便我們可以創一個 dump_nochild 的函式,這樣比較方便:
fn dump_nochild(out: &mut dyn Write, id: &mut u32, label: &str) -> u32 { dump_children(out, id, label, &[]) }現在 make_node 的實作都可以用 dump_children 或 dump_nochild 實作,先對自己的 child 們呼叫 make_node,把回傳值(也就是 child 們印完的 root)收集起來再用 dump_children 印出去就行了:
impl ToGraphviz for CastTop { fn make_node(&self, out: &mut dyn Write, id: &mut u32) -> u32 { match self { CastTop::FuncDeclList(v) => { let children : Vec<_> = v.iter().map(|n| n.make_node(out, id)).collect(); dump_children(out, id, "PROGRAM_NODE", &children); }, } *id } } impl ToGraphviz for FuncDecl { fn make_node(&self, out: &mut dyn Write, id: &mut u32) -> u32 { let children = [ dump_nochild(out, id, "IDENTIFIER_NODE int NORMAL_ID"), dump_nochild(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", self.fun_name)), dump_nochild(out, id, "PARAM_LIST_NODE"), dump_nochild(out, id, "BLOCK_NODE")]; dump_children(out, id, "DECLARATION_NODE FUNCTION_DECL", &children) } }這樣看起來就好多了,不過我們還能更進一步,仔細觀察上面的 dump_children 的話,就會發現我們還能用 fold 的方式改寫:
// print node, and link with all children fn dump_children(out: &mut dyn Write, id: &mut u32, label: &str, children: &[u32]) -> u32 { *id+=1; writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap(); children.iter().fold(*id, |mut prev, child| { writeln!(out, "node{} -> node{} [style = {}]", prev, child, if prev == *id { "bold" } else { "dashed" }).unwrap(); prev = *child; prev}); *id }老實說,每次我費了這麼大的工夫,把一堆本來
每個函式都要帶著 out 跟 id 走,很不方便,用一個 struct 把它們裝起來:
struct DumpGraphviz { out: Box<dyn Write>, id: u32 }dump_children 跟 dump_nochild 變成 DumpGraphviz 的實作,介面變成:
fn dump_children(&mut self, label: &str, children: &[u32]) -> u32 fn dump_nochild(&mut self, label: &str) -> u32make_node 的介面則是:
fn make_node(&self, visit: &mut DumpGraphviz) -> u32整體就變得清爽多了。
天底下沒有新鮮事,其實我就是在實作 visitor pattern,只是還沒把 visitor 整個抽出來讓不同的 visitor 可以在這上面實作。最後輸出的成品長這個樣子:
我有個小小的體悟,就是寫程式不要妄想一步登天,除非如強者我同學 AZ 大大那樣一眼就把超大程式的架構都畫出來,而且實作起來都不會亂掉。
我上一次的實作就是衝太快,翻著 C standard 想要一開始就照著 C standard 實作,然後文法寫得亂七八糟反而連簡單的文法都會大噴射無法處理;與其如此,不如先支援基本的功能,等 parser 跟文法處理都完善之後再慢慢把其他功能加上去。
我覺得用蓋房子比喻的話,寫大程式要像西敏寺那樣的大教堂一樣,先從一個功能完整的小教堂開始,然後把小部分拆掉蓋個更大更豪華的(有看過一個動畫片在演示這個過程的,只不過沒有公開版);如果一次就想蓋個超大的教堂,最後可能弄成一團廢墟,連禮拜的功能都沒有。
沒有留言:
張貼留言