2018年6月16日 星期六

實作麻雀雖小五臟俱全的程式語言

故事是這樣子的,很早以前曾經看過 understanding computation 這本書,這本書第二章的內容,是利用操作語義(operational semantic)的方式,自訂一款極簡程式語言,非常簡單但已經有 if 判斷式,while 迴圈等功能。
最近剛修完 coursera 上面的 programming language,其中有一個作業也是用 racket 的操作語義定義一款程式語言, 這個程式語言更複雜,在資料結構上支援 pair -> list,同時還支援函式,這是之前 Understanding Computation 沒有實做的部分。
花了幾天的時間,把過去的 code 擴展了一些,在那上面實作了函式,在這裡就簡單介紹一下相關的內容,還有一些個人的心得,心得內容可能有對有錯,如果有錯就請路過野生的大大們指教一下:
要看到原本的內容,可以參考之前發在這個 blog 的筆記,還有 Github 上面的原始碼。
https://yodalee.blogspot.com/2016/03/rust-recursive-structure.html
https://github.com/yodalee/computationbook-rust/tree/master/src/the_meaning_of_programs/simple
本次修改的程式碼則可見:
https://github.com/yodalee/simplelang

所謂操作語義,就是明白的定義程式的各指令實際執行起來是如何,實際執行的機器當然是一台虛擬機,模擬執行的過程。原本書裡面有兩種操作語義的方式,一種是小步 reduce,每次將程式的內容變小一些些;一種則是直接 evaluate,有什麼結果直接計算出來。
要實作函式的部分,我把 reduce 的實作刪掉了,因為我實在不知道要怎麼用 reduce 實作函式,reduce 每次只會拿一個指令,然後把它縮小一些些,但在處理 function 上,只要進到 function 內部就要代換成另一個環境給它,步步執行的 reduce 做不到這點。
因為我的程式是來自於 Understanding Computation,所以裡面有些 code 像 while, sequence 是來自書中,其實我們有了 function ,就可以用 recursive 的方式取代 while,sequence 也可以適度修改,例如把 assign 變成如 let var = val in expression 的形式,在環境裡將一個值賦值給變數之後,以這個環境執行第二個 expression,就不需要 sequence 這樣的語法了;這部分大家自己知道就好。

看一個最簡單的例子:加法。
首先我們定義我們程式的單位:Node,要實作加法需要實作兩種 Node,代表數字和代表加法運算的 Node,接著我們就可以用 Node::number(100) 代表數字,用 Node::add(Node::nubmer(3), Node::number(4)) 代表加法;另外要實做一個 evaluate 函式,讀入一個 Node 並做出對應的操作,例如加法是分別把兩個參數都 evaluate 過,用 value 取值,用我們熟悉的加法加起來;其他運算如乘法、判斷用的大於、小於,都是類似的實作。

再深入一點要實作變數,例如 x = 10,就會需要環境 (environment.rs),它是 evaluate 需要的參數,實作是一個簡單的 HashMap,將變數名稱映射到相對應的 Node 上面,注意是 Node 不是實際地址,在我們的實作下輸入地址都是虛擬化為 Node;如此一來就能定義 Variable 跟 Assign 兩種 Node,分別會從環境中拿出值和將某段程式賦予給某個變數 。

再來就是複雜一些的 Pair, List,先定義 pair 以及兩個輔助用的 fst, snd Node,一個 pair 其實就是把兩個程式組合在一起,之後可以用 fst 跟 snd 取出第一個和第二個的值。
在這裡我們偷懶一下,重複使用 donothing 這個 Node 來表示 list 的結尾,一個 list 即是表示為許多 pair 的嵌套,最後一個 pair 的第二個 Node 必須是 donothing。
使用 iter 搭配 fold 就能輕易將 rust 的 integer vec 轉成我們這個程式語言中的 integer list,從最後一個元素開始,一個一個用 pair 與上一次的結果組合起來。
pub fn vec_to_list(v: Vec) -> Box {
  v.iter().rev()
   .fold(Node::donothing(), |cdr, car| Node::pair(Node::number(*car), cdr))
}
結果:
pair (1, pair (2, pair (3, pair (4, pair (5, do-nothing)))))

這裡有個小小的心得是,程式和資料其實是不可分開的,當我們在組合程式的過程,定義一些特定的組合方式就能將程式轉為資料,反之亦然;雖然這是我偷懶的關係,但 DoNothing 可以是程式,表示不做任何事情,也可以是資料,用來表示 pair 的結尾;程式和資料其實是一體兩面,端視我們執行的時候怎麼處理它。

我們來看一下函數,我們創了三個相關的 Node:
  • Fun:參數是一個 string 作為函數名稱,一個 string 作為變數名稱,還有一個 Node 是函式內部的程式碼。
  • Closure: 我一直很好奇 closure 到底有沒有標準中文翻譯,看到有些翻譯稱為閉包,Closure 是執行時遇到 Func 產生的東西,包含函式內的程式碼,以及 evaluate Fun 時的環境。
  • Call:以給定的參數傳給一個 Closure 並執行。
把 Fun 丟進 evaluate 會把當下的環境打包起來,生成一個 Closure;如果是 Closure 的話就不會特別做什麼。
Call 是最複雜的,它有下列幾個步驟:
  1. 把 closure 跟參數 evaluate 過,如果拿到的不是closure 就會發生錯誤。
  2. 將 closure 儲存的環境跟函式取出來。
  3. 在這個環境中加上兩個新的變數:一個是函數名稱指向自己這個 closure,這樣在函式內 Call 自己的名字就能做到遞迴呼叫的效果; Fun 的參數名稱指向傳進來的變數值。
  4. 用新的環境去 evaluate Fun 所帶的程式。
其實如果寫過 closure ,了解相關的概念之後,再去看下面這個 functionalC 的 repository 就滿好懂的了,如果要實作 Functional Programming 裡面的概念,函式都要自帶一個執行的環境,才能把函式像 first class member 一樣丟來丟去,由於 C 的函式並沒有強制要求這點,所以這一個 repository 裡面才會自己定義 closure 這個 struct ,基本上和我的定義一樣,都包含一個真正要執行的函式,還有執行的環境。
struct closure {
  void *(*fn)(list *);
  list *env;
};
再深入一點,假設程式一開始先設定 1000 個變數,然後再定義一個函式,這個函式要包含的環境是否需要這 1000 個變數?如果完整複製所有環境,太浪費空間了,實際上我們只需要記下函式中真正需要的變數即可,以下面這個函數為例子:
let x_add_y = Node::fun(
  "add1", "y",
  Node::add(Node::variable("x"), Node::variable("y")));
它接受一個參數 y 並將它和變數 x 相加 ,這時只要記錄 x ,其他變數都不需要保存,連變數 y 也不需要,因為 y 一定會在呼叫函式的時候被參數 y 給蓋掉(Shadow)。
變數 x 我們稱之為 free variable ,沒有被程式中的 assign 賦值或是以參數的方式掩蓋掉,它在執行時可視我們的環境設定自由變動。

我在 evaluate.rs 另外寫了一個 cal_free_vars 的函式來計算一段程式內的自由變數,它會生成兩個 HashSet 記錄出現過的變數跟自由變數,然後丟給 helper 函式處理。
大部分的處理方式都差不多,就是一路遞迴往下呼叫,像加法就是分別對兩個 Node 計算內部的自由變數;比較不一樣的是 Variable, Assign, Fun;在 Assign 跟 Fun 的地方,分別要把變數名稱、函數名稱跟參數名稱加到變數名單中,如果 Variable 取用的變數還沒在變數名單內,這個變數就是自由變數。
最後修改 evaluate Fun 的地方:
let free_vars = get_free_vars(self);
let mut new_env = Environment::new();
for var in free_vars {
  new_env.add(&var, env.get(&var));
}
用 get_free_vars 得到函式內的自由變數,生成一個新的環境,從現在的環境取得自由變數的值,用新的環境產生 closure;如果環境中沒有自由變數的值,環境的實作會直接崩潰,強制在執行函式的時候,環境中必須要有它的記錄。
以上大概就是一個有函式的程式語言會需要的實作,基本上這個語言能做到一些相當複雜的事,例如遞迴跟 currying 等,在 evaluate.rs 裡有一些相關的測試,例如階乘的遞迴實作:
fn test_simple_big_function_recursive() {
    let factor = Node::fun("factor", "x", Node::if_cond_else(
            Node::gt(Node::variable("x"), Node::number(1)),
            Node::multiply(Node::variable("x"),
              Node::call(Node::variable("factor"), 
              Node::subtract(Node::variable("x"), Node::number(1)))),
            Node::number(1)));
    let statement = Node::sequence(
        Node::assign("entry", factor),
        Node::assign("result", Node::call(Node::variable("entry"), Node::number(10)))
    );
    let mut env = Environment::new();
    println!("{}", statement.evaluate(&mut env));
    assert_eq!(3628800, env.get("result").value());
}
寫完這款程式語言,我開始覺得其實我是在寫個虛擬機,或者說有點像在實作一台電腦。
我們先把所有的資料:數值、真假值虛擬化為 Node 這個單位,一切的操作都是在 Node 上進行;就像真實的 CPU,也是將數字轉化為記憶體內部的 0, 1,在加法這個指令被執行的時候,會拿出記憶體的內容,通過一連串的邏輯閘變成輸出,再存回記憶體。 記憶體就好比我們的 Node,邏輯閘實作則是 evaluate,CPU 執行 x86 指令這款「語言」對應我們自訂的程式語言,只是CPU是真實的機器,我的程式是一台虛擬機 。
程式其實根基於數學,加法是一個概念,我們只是透過 CPU/電腦的實作,亦或是這篇文的操作語義,用虛擬機模擬出加法這個概念,所謂「程式語言」應是數學之神座下超凡的存在。 我們用上人類智慧的極致,打造 CPU,打造電腦,試著去追趕的這神聖的目標,追之求之,卻稱這款模倣的玩意兒為「程式語言」,何等自傲?想想不禁啞然失笑。

2018年6月9日 星期六

東京區知性學習之旅

故事是這樣子的,四月看完了上季霸權之一<比宇宙更遠的地方>,隨意瀏覽相關資料時,發現第三集的極地科學館在東京立川,而且初代南極探測船宗谷,一直都擺在台場的船之科學館進行公開展示,之前去的時候竟然都不知道,點進船之科學館的網站看到正好到 6/10 有特展,當下感到一陣衝動,就訂下五月底為期四天的東京宅爆聖地巡禮知性學習之旅。

機票:
機票選用香草航空,它的好處是有紅眼班,可以最大化旅行的時間效率
去程 JW100 0150 台北 -> 0610 成田
回程 JW107 2200 成田 -> 1255 台北
因為是五月初訂機票,加一件行李來回加起來 9000-10000,其實沒有特別便宜,頂多省個2~3000, 不過記得我跟朋友有這段經典的對話:
A: 都這個價格你幹嘛不搭華航或是長榮?
B: 因為傳統航空的時間都比較差。
A: 原來那個叫做時間比較差喔
反正現在年輕還可以燃燒新鮮的肝來換旅遊時間,再過個幾年大概就不能這樣玩了,特別是去程 0150 的飛機,我幾乎睡不到 2 hr 就被窗戶射進來的陽光照醒了,如果不是在 skyliner 上有睡一下,第一天早上搞不好只能呆在飯店大廳補眠。

住宿:
三個晚上的住宿,下塌ホテルマイステイズ上野イースト,離上野車站走路大概10分鐘,如果是地下鐵就是銀座線稻荷町站。
個人建議在東京玩的話,住宿可以選擇東京車站以北、上野、日暮里、王子、往西到池袋、往東到淺草。
東京車站附近因為比較貴通常不選;上野到日暮里是最理想的,因為從成田機場搭京成 skyliner,在東京的兩個停靠站就是上野跟日暮里,王子和池袋分別可以透過京濱東北線和山手線在15分鐘內抵達日暮里,轉搭 skyliner 非常方便,當然再遠一點也不是不行,山手線沿線時間算好就是了。

通訊:
因為這次可能會和同行者分開行動,所以我們分別申請了網路漫遊,我是使用中華電信 7 天 1G 168 的方案,不貴而且網路速度不差;有了這個基本上已經打爆市面上所有 SIM 卡了,不用插卡,價格也算實惠,1GB 省著點也不是一般人在一個星期用得完的量。

交通:
從成田進到東京市的交通,選擇京成 skyliner ,搭配後兩天的行程選配東京地鐵兩日券,地下鐵跟都營都可以搭,隨意轉乘任我行,如果沒有一日券就要注意在兩個系統間切換的話要另外付錢;另外通常從地下鐵系統換去都營都有一點距離,必要的時候請使用 hyperdia 這類路線規劃軟體,不然隨便走個 700 公尺轉車也不是不可能的。
還有手線跟中央線是 JR 的,換車也要付錢(不同系統的路線也不玩轉乘優惠那一套)。

大致行程與景點,我實際的路線有些許差異,第一天下午我跑去找之前來東京認識的人了,這裡綜合我跟同行者的行程,大致記錄一下:

第一天:
因為上午 06 才飛到,視飛機上的睡眠狀況而定,睡眠狀況不佳可以在飯店大廳多休息一下,排行程的時候有料到這個狀況,所以第一天行程只排台場,累的話就 1500 可以 check in 之後早早回飯店休息。

成田機場第三航廈飲食部:早餐
築地市場 :海鮮午餐,有興趣的話可以加逛築地本願寺。

台場:船之博物館宗谷開放<比宇宙更遠的地方>,特展到 6/10,除了前甲板和輪機室進不去,其他的地方包括主控室都有開放參觀,又是免費上船,值得一看。
回程的時候可以走一小段路去看台場的鋼彈,已經換成新機型了,待到晚上有燈光秀。
東京車站:<Lovelive Snow Halation>,這是我同學去的,不是他說我壓根不知道原來 snow halation 的場地是在東京車站。或者直接拉去秋葉原神田明神社<Lovelive>也可以,這次因為我們兩個都去過就跳過這個點。

交通除了台場之外,都搭配上面的地鐵/都營1-3日券;說實在台場沒有什麼特別好玩的東西,兩家交通線都不是都營或者地下鐵系統,百合海鷗線又超級貴,每次去都要大噴錢…後來就很不想去。

第二天:
淺草:雷門、淺草寺(嚴格來說 lovelive 也來過這裡),這裡大概是大眾景點了我們就跳過介紹吧

鷲宮:鷲宮神社<Lucky Star>,其實就是個鄉間神社,要不是 lucky star 我猜沒多少人會特別排這個點吧,此行真正的目的是東武動物公園,只是鷲宮正好就在旁邊就順便來一下

午餐在東武動物公園站吃連鎖餐廳解決。

東武動物公園<動物朋友>:來這裡看 fururu。來的時候剛好東武動物公園在跟動物朋友進行第二波合作到 7/1,各種動物都有插動物朋友的立牌,不過立牌的尺寸非常的小,有些還藏到非常奇怪的地方,一不留神就會錯過

秋葉原:Game Center 打 Lovelive AC 機台<Lovelive>:打機台也是很重要的,特別是 Lovelive AC 機台台灣都沒有進
簡單來說就是把手機的遊戲畫面變成機台畫面,打節奏改用按鈕打,再怎麼暴力打都沒關係(X,比較要注意的大概是介面設計,九個打節奏的按鈕只是選擇,要按右下角的藍色按鈕跟左下角的紅色按鍵才是確認跟取消;100塊錢可以打三首歌,非常便宜,機台也都有支援電子票證付款,推廣期間優惠五塊錢,想積少成多可以多多用電子票證付款。
由於不是每間遊戲中心都會有,最好先查閱官網稼動站舖一覽確認一下,當然秋葉原地區店舖是最多,這家沒有換下一家就是了。

交通在市內的移動,如早上上野到淺草,晚上去秋葉原,都用 skyliner 買到的一日券。
去鷲宮跟東武動物公園則是用東武鐵道,從淺草搭車。在曳舟跟久喜間要改搭急行,車程大約 40 分鐘。往久喜也有 JR 鐵道可以選擇,一般來說 JR 都會比私鐵便宜一丁點,這樣大家就自己選擇
晚上的行程也可以排晴空塔,這次我們都沒興趣所以沒有上去看夜景,但其實晴空塔的夜景應該是我看過數一數二好的。

第三天:立川

國立極地研究所南極、北極科學館<比宇宙更遠的地方>:來的時候剛好也遇到跟<比宇宙更遠的地方>的合作,不過距離合作開始已經有一段時間,有些立牌跟看板都開始撤掉了,這裡展品內容十分豐富,資料、模型、體驗一應俱全,又是免費入場,超級划算的展場景點。
午餐:三井立飛 lalaport,在單軌立飛站,因為有單日票怎麼搭都沒差,這裡週末人會非常多要注意一下(把它想成林口三井就是了)

 多摩動物公園,藪貓<動物朋友>:大老遠跑來這裡就為了看藪貓,如果要看他們的藪貓跳躍表演,就要關注一下他們的官網,左邊的日曆可以看每日的活動,下一次的表演是 6/23。
晚餐:新宿風雲兒沾麵,本次吃到最好吃的一餐,雖然要排一點隊不過非常值得。
新宿都廳夜景:看免錢的夜景,同時可以看到晴空塔跟東京鐵塔,就是視野被新宿附近的大樓所遮蔽,沒有晴空塔夜景那種一望無際的感覺,但反正是免錢的,不要要求太多。
新宿 SEGA 遊戲中心,Lovelive AC 機台<Lovelive>:因為六月開始有東條希生日活動,活動剛開放馬上來打XD。

立川其實不算近的景點,比一般人會去的吉祥寺、三鷹等再遠許多,遠到想用 JR 東京近郊一日券都沒辦法,只能乖乖刷電子票。我們是從上野先到神田,再換中央線快速到立川,單程 640 元,只要搭上急行或特快,基本上是一小時內可到。
在立川可以利用當地的立川 monorail,一日券搭配多摩動物公園入場券只要1000元,再搭去極地博物館絕對值回票價。

第四天:川越
這天只是找個一日遊景點填時間,倒是沒有一定要去哪裡。

川越冰川神社,關東有名的結緣神社之一,可以在這裡用釣魚抽籤,看看滿滿的風車。川越也有不少租和服浴衣體驗,不去關西也能體驗和服浴衣,算是東京近郊一個想體驗古風不錯的一日遊景點;午餐就在川越老街上的餐廳解決。
池袋,Lovelive AC 機台<Lovelive>,昨天還沒達成東條希活動的條件,今天怎麼能放過?再打兩場XD,打完就要回去啦。
成田機場第三航廈飲食部晚餐

交通我們從池袋出發,用東武東上線的 700 元一日券(或搭配公車 950 元),可以來回池袋跟川越間一次,同樣搭急行的話只要約 40 分鐘就會抵達川越,在川越就全程換步行。
回程就搭山手線到日暮里搭回程的 skyliner。

四天的行程大概就是這樣,算是會走滿多路的行程,必要時請評估自己腳力,特別是兩個動物公園佔地廣闊,東武動物公園從東走到西要 2km,應該一天破 10000 步都算滿簡單的。
在日本搭火車絕對不要搭各停,會快非常多,東京特別是如此,第二天到第四天的東武、立川、川越,搭上急行列車大約 40 分鐘都會抵達,如果搭各停可能就會超過一小時;不過通常(只是通常,不保證),他們都會安排各停列車在某一站等急行列車,這時只要走去對面換車即可。

ps. 以上照片部分由強者我同學 JJL 提供

2018年5月10日 星期四

使用 procedence climbing 正確處理運算子優先順序

上一篇我們說完如何用 Rust 的 PEG 套件 pest 生成簡單的程式碼分析器,但其實還有一些沒有解決的問題,像是 1 * 2 + 3 * 4 = 20,這是因為我們在處理 expression 時沒有處理運算子優先次序,只是從左到右掃過一遍。
真正的 parsing 要考慮運算子優先權跟括號等等,例如:
1 + 2 + 3 -> ((1 + 2) + 3) : Left associative(左相依)
1 + 2 * 3 -> (1 + (2 * 3)) : * 優先權高於 +
2 ^ 3 ^ 4 -> (2 ^ (3 ^ 4)) : Right associative(右相依)

在這裡我們要介紹 precedence climbing 這套演算法,假設我們已經有了 Term (op Term)* 這樣的序列,現在要將它 parse 成 syntax tree,可以參考這篇的內容

precedence climbing 其實不難,首先我們會先讀進一個 token 作為 lhs token,優先權為 0。
接著持續取得下一個 operator 的優先權和 associative,如果運算子優先權 >= 目前優先權,則:
right associative,以同樣的優先權,遞迴呼叫 parse。
left associative ,則以高一級的優先權遞迴呼叫 parse。

虛擬碼大概如下:
climb (min_precedence)
  lhs = get_token()
  while next_op precedence >= min_precedence
    op associative is left:
      next_precedence = min_precedence + 1
    op associative is right:
      next_precedence = min_precedence
    rhs = climb (next_precedence)
    lhs = op (lhs, rhs)

  return lhs
來個簡單的範例:如果所有運算子都是 left associative 、同樣優先權,例如 1+2+3+4,lhs 剖析出 1 之後,以高一級的優先權呼叫 climb,所有遞迴呼叫的 climb 都不會進到 while,而是直接回傳剖析到的第一個 token 給第一次呼叫 climb 的 while loop 作為 rhs, parse 成 (((1+2)+3)+4)。
如果是遇到更高權限的運算子,則呼叫的 climb 會進到 while loop ,把後面的 token 都消耗掉再回傳其 lhs,可能因為這樣因此取名為 precedence climbing。

當然,比起我們自己實作,pest 裡面已經幫我們實作好了,只是在文件裡面都沒有提及,我也是看了用 huia-parser 這個用 pest 作 parsing 的 project ,才知道原來有這個功能可以用。

廢話不多說直接來寫,首先我們要在 Project 中引入 pest 的 precedence climbing 實作:
use pest::prec_climber::{Assoc, PrecClimber, Operator};
我們需要建好一個 PrecClimber 的物件,這個物件會儲存一個 Operator 的 Vec,優先權依順序增加,如果有相同優先權的運算子,則用 | 連接,每個 Operator 中會保存 parser 中定義的 Rule 跟 Assoc::Left 或 Assoc::Right,例如我們的 simple 的定義(這裡我加上一個 op_sub 來示範 | 的用法):
let PREC_CLIMBER = PrecClimber::new(vec![
    Operator::new(Rule::op_lt,  Assoc::Left),
    Operator::new(Rule::op_add, Assoc::Left) | Operator::new(Rule::op_sub, Assoc::Left),
    Operator::new(Rule::op_mul, Assoc::Left)
])
要剖析的時候則是呼叫 PrecClimber 的 climb 函式,它的型態乍看之下有點複雜:
pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
where
    P: Iterator<Item = Pair<'i, R>>,
    F: FnMut(Pair<'i, R>) -> T,
    G: FnMut(T, Pair<'i, R>, T) -> T
其實也不難理解,它只是將上面的 precedence climbing 虛擬化為幾個函式:
pairs: P 是全部要走訪的 (term (op term)*) iterator。
primary: F 會吃一個 term 將它轉為剖析後的結果。
infix: G 為結合方式,拿到兩個剖析後的結果跟一個運算子,將兩個結合起來。

這裡的 primary 其實就是我們寫過的 build_factor:
fn build_factor(pair: Pair<Rule>) -> Box<Node> {
    match pair.as_rule() {
        Rule::variable => Node::variable(pair.into_span().as_str()),
        Rule::number => Node::number(pair.into_span().as_str().parse::<i64>().unwrap()),
        _ => unreachable!(),
    }
}
infix_rule 其實也只是把我們之前 build_expr 的東西給取出來:
fn infix_rule(lhs: Box<Node>, pair: Pair<Rule>, rhs: Box<Node>) -> Box<Node> {
    match pair.as_rule() {
        Rule::op_add => Node::add(lhs, rhs),
        Rule::op_mul => Node::multiply(lhs, rhs),
        Rule::op_lt => Node::lessthan(lhs, rhs),
        _ => unreachable!(),
    }
}

build_factor 會吃進 token,將它轉為我們 AST 的型態 Box<Node>;infix_rule
使用 climb ,當我們拿到一個 expression token,要做的就只剩下把它丟給 climb 去爬,into_inner 將 expression token 轉為下層的 token iterator;:
// pair.as_rule() == Rule::expr
pub fn climb(pair: Pair<Rule>) -> Box<Node> {
    PREC_CLIMBER.climb(pair.into_inner(), build_factor, infix_rule)
}
最後一小步,我們想要避免每次要 climb 的時候,還要重新產生 PREC_CLIMBER 這個物件,反正語法固定之前 PREC_CLIMBER 沒理由會變動,因此我們用了 lazy_static 這個套件,將它變成 static 的物件:
#[macro_use]
extern crate lazy_static;

lazy_static! {
    static ref PREC_CLIMBER: PrecClimber<Rule> = build_precedence_climber();
}
fn build_precedence_climber() -> PrecClimber<Rule> {
    PrecClimber::new(vec![
        Operator::new(Rule::op_lt,  Assoc::Left),
        Operator::new(Rule::op_add, Assoc::Left),
        Operator::new(Rule::op_mul, Assoc::Left)
    ])
}
這麼一來我們的 simple 剖析器就完成了,現在 1 * 2 + 3 * 4 會是正確的 14 了,可喜可賀可喜可賀。

2018年5月6日 星期日

使用 rust pest 實作簡單的 PEG simple 剖析器

上一篇我們看了 PEG 相關的內容,這篇我們就來介紹該如何用 PEG 寫一個簡單的剖析器,當初會開始這系列文章,是因為自己 computation book rust 實作中,並沒有像原作者的 ruby 實作,有用 treetop 這個 PEG parser 寫一個剖析器,剖析文法變成裡面的程式,例如 simple, regupar expression, pushdown automata, lambda calculus 等等,最近想說把這部分補上,結果在第一關 simple 上就研究了好一陣子。
本來預估一個星期寫完,根本太樂觀,回家晚上能自己寫 code 的時間估太多,到現在應該已經快一個多月了,才有初步的結果,當然我們也可以說原因是 rust pest 沒有 ruby treetop 這麼好用(炸。

要使用 rust pest,首先是透過 cargo 安裝,為了這點我一開始先花好一陣子,把整個 project改寫成 cargo 管理,詳見這篇文章,之後才開始相關的實作,整個完成的程式碼可以看這裡
接著就是安裝 pest,在 Cargo.toml 中加上:
[dependencies]
pest = "^1.0"
pest_derive = "^1.0"
pest_derive 為 pest 剖析器產生器,他會分析你指定的 PEG 文法,生成對應的剖析規則跟剖析器;pest 則是引入剖析後生成的資料結構,兩個都要引入。
接著在原始碼中加入:
#[cfg(debug_assertions)]
const _GRAMMAR: &'static str = include_str!("simple.pest");
#[derive(Parser)]
#[grammar = "the_meaning_of_programs/simple.pest"]
struct SimlpeParser;
_GRAMMAR 是用來提醒編譯器,在 simple.pest 檔案更新的時候,也要觸發重新編譯(不然就會發現改了文法,cargo build 不會重新編譯),該 pest 檔的路徑是相關於目前的原始碼檔案;grammar 後的路徑則是相對於 src 資料夾,我試過不能用 .. 的方式回到 src 上一層目錄,grammar 檔案內容就是PEG 的語法,在編譯的時候會被 pest 轉換成 parser 的實作儲存在 SimpleParser 裡面。

pest 的語法基本上跟 PEG 沒有太大差別,在文法檔案中,就是 rule = { rule content } 的方式去定義規則:
  • 匹配字串使用雙引號包住,用 ^ 設定 ASCII 為無關大小寫,例:op_add = { “+” }, const = { ^”const” }
  • 一定文字範圍的用單引號搭配 ..,例:number = { ‘0’..’9’ }
  • 選擇規則用 | ,例:alpha = { ‘a’..’z’ | ‘A’..’Z’ }
  • 連結規則用 ~,跟 PEG 定義用空白直接連接不同,空白在 pest 用做排版,例:stat_assign = { variable ~ “=” ~ expr ~ “;” }

定義規則中,可以用到其他規則,例:factor = { (variable | number) }。
另外有一些特別的規則,包括:
  • whitespace:whitespace 裡指定的字串,會自動在 ~ 連結的位置中插入 (whitespace)*,平常不需要特別指明處理 whitespace,例如上面的 stat_assign 就變得能夠剖析 ”foo = 123” 而不只是 “foo=123”。
  • comment:comment 會在規則和子規則間被執行,不需特別指明。
  • any:匹配任一字元,對應 PEG 中的 .。
  • soi, eoi:對應匹配內容的開始和結束,這兩個還滿重要的,以之前的 S = A, A = aAa | a 為例,如果直接寫 S = { A },那去匹配一個以上的 a 都會匹配成功,因為我們沒指定 S 之後要把整個字串匹配完,正確的寫法是:S = { A ~ eoi }。
  • push, pop, peek:分別 push/pop/peek 字串到 stack 上面,push(rule) 將 rule 匹配到的字串送到 stack 上; epop/peek 會用 stack 內容的字串去做匹配,但 pop 會消耗掉 stack 的內容;這個規則我還沒有實際用過,不確定哪裡會用到它。

由於 pest 的文法規則都會被轉成一個 rust enum ,所以 rule 的取名必須避開 rust 的關鍵字,我在這裡是加上一些前綴或後綴來迴避,例如 stat_while;規則在剖析過後會生成對應的 token,內含剖析到的字串,如果是直接實寫的文字就不會產生出結果,這部分等等會看到。
  • 用 // 在規則中寫註解。
  • PEG 中 ?+* 三個符號,也是直接加上,有需要特別分隔的地方,可用小括號分開,例:number = @ { (digit)+ }、stats = { (stat)* }
  • e{n},e{,n},e{m,},e{m,n}:分別是 n 個,至多 n 個,m個以上,m至n個匹配。
  • PEG 的 & 跟 ! predicate 也是直接使用(不過我沒用過XD)

每個規則前面可以加上四個 optional modifier,分別如下:
  • Silent _ :剖析的時候不產生這個規則對應的節點,例如我的 factor 是:factor = _{ (variable | number) },那在剖析完之後,會直接跳過 factor,產生 variable 或 number 的節點。
  • Atomic @:這跟上面的 whitespace 有關,像我的 variable 寫成 variable = { (alpha) ~ (alpha | digit)* } ,豈不是可以接受 “a 123” 這樣奇怪的變數名?這時候就用 @ 確保規則中不執行 whitespace 規則。
  • Compound-atomic $:這跟 atomic 一樣,只是規則的子規則,例如 expr = $ { “-” ~ term } ,則 term 仍然適用 whitespace。
  • Non-atomic !:因為一個 atomic 規則下所有規則都會是 atomic,可以用 ! 來停止這樣的效果。

我們可以把上面這些都綜合起來,寫出一個極簡的 simple language parser,當然這實在是太簡單了,簡單到會出一些問題:
alpha = { 'a'..'z' | 'A'..'Z' }
digit = { '0'..'9' }

whitespace = _{ " " | “\n” }

variable = @ { (alpha) ~ (alpha | digit)* }
number = @ { (digit)+ }

op_add = { "+" }
op_mul = { "*" }
op_lt  = { "<" }
op_binary = _ {op_add | op_mul | op_lt }

factor = _{ (variable | number) }
expr = { factor ~ (op_binary ~ factor)* }

stat_assign = { variable ~ "=" ~ expr ~ ";" }
stat_while = { "while" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}" }
stat_if = { ("if" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}" ~ "else" ~ "{" ~ stats ~ "}" ) |
            ("if" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}") }
stat = _{ ( stat_if | stat_while | stat_assign ) }
stats = { (stat)* }

simple = _{ soi ~ stats ~ eoi }
simple 就是整個剖析的進入點,在原始碼中呼叫 SimpleParser 的 parse 函式,對字串進行剖析,參數要代入想要剖析的規則和內容,這裡我們用 expression 來舉例,畢竟寫過 parser 就知道 expression 算是最難爬的東西之一,通常搞定 expression 其他都是小菜一碟:
let pair = SimpleParser::parse(Rule::expr, "1 * 2 + 3 * 4")
                .unwrap_or_else(|e| panic!("{}", e))
                .next().unwrap();
parse 之後會得到一個 Result<Pairs<R>, Error<R>>,表示是否成功,這裡如果不成功我們就直接 panic ,成功的話取出 Pairs,用 next unwrap 將第一個 Pair 取出來,也就是剖析完的 Expr Token,因為剖析失敗的話在剛剛的 Result 就會得到 Err 了,這裡我們都可以大膽的用 unwrap 取出結果。
Pair 有幾個函式可呼叫:

  • pair.as_rule() 會得到剖析的規則,此時的 pair.as_rule() 為 Rule::expr,這可以用來判斷剖析到什麼東西。
  • pair.into_span() 會取得 token 的範圍資訊。
  • pair.into_span().as_str() 會得到 token 匹配的字串內容,像在處理 assign的時候會用這個拿到變數名稱 。
  • pair.into_inner() 會拿到下一層的 Pairs,以 expr 來說,會對應到 { factor ~ (op_binary ~ factor)* },之前有提過字串並不會產生 token,上面的 stat_if, stat_while 就是例子,在 into_inner 的時候,括號、角括號等只是匹配,但不會有 token 產生。

在這裡我們把 expr 的 Pair 直接丟下去給另一個函式 build_expr,由它把 expression 剖析成 simple language 的 Node,它會先用 into_inner 叫出 expr 的內容物,然後依序取出左值、運算符跟右值並建成 Node Tree;可以從 op 的處理方式看到如何使用 as_rule() 來看看剖析到什麼。
fn build_expr(pair: Pair<Rule>) -> Box<Node> {
    let mut inner = pair.into_inner();
    let mut lhs = build_factor(inner.next().unwrap());
    loop {
        let op = inner.next();
        match op {
            Some(op) => {
                let rhs = build_factor(inner.next().unwrap());
                lhs = match op.as_rule() {
                    Rule::op_add => Node::add(lhs, rhs),
                    Rule::op_mul => Node::multiply(lhs, rhs),
                    Rule::op_lt  => Node::lessthan(lhs, rhs),
                    _ => unreachable!(),
                }
            },
            None => break,
        }
    }
    lhs
}

因為我們沒有處理運算符優先順序的問題,所以 1 * 2 + 3 * 4 的結果會是 20,如果要正確處理就需要實作 precedence climbing 之類的方法,不過這個留待下篇文章再來解決這個問題,至少我們已經能 parse 一個 simple program,自動轉成 Rust 的 simple AST 了(其實原作者的 treetop parser 也沒有考慮這個問題,所以其實我們可以裝傻當作沒這回事XD)。

以上大概就是 pest 的介紹,基本上使用 pest,一個規則用一個單獨的函式來處理,就能把每次修改的範圍縮到最小,熟練的話應該能在短時間內魯出一個基本的 parser 來用。

2018年5月1日 星期二

剖析表達文法 PEG 簡介

剖析表達文法 PEG 為 Parsing Expression Grammar 的縮寫,2004 年由 Bryan Ford 教授所提出,相對於一般在編譯器課上教 parsing 所用的 CFG (Context Free Grammar) ,已經被鑽研數十年之久,可說是相當年輕的形式化語言。

其實 PEG 和 CFG 在本體上幾乎沒有不同,從創作概念上來看,CFG 著重的是語法的產生和定義,PEG 則專注在剖析語法上,找資料時就有在中國的知乎論壇上看到這句:「CFG 作為產生式文法,很適合用來生成內容丰富多彩的垃圾郵件」不禁會心一笑,過去定義程式語言,都是先教 CFG,通常都會有這麼一句:「寫出 CFG 就定義了一個程式語言」
生成文法的切入點在<產生>,我們定義產生文法來定義語言,討論各種文法的強度,看看它們能產生什麼,不能產生什麼;用這套文法產生出來的東西,管它到底多亂多醜多長,都符合這個文法(有點回文),從 CFG 的觀點來看,先想好怎麼產生程式語言,接下來再來看怎麼剖析它,然後再討論 LL, LR 等等剖析方法。

PEG 則沒有這麼繞圈圈,PEG 本身即是 parser 的抽象定義,PEG 定義的 parser 會由一條一條規則組成,每條規則會去匹配輸入,如果成功則消耗輸入,失敗則不會消耗輸入。
PEG 的 terminal 規則如下,大致和 CFG 相同:
* 字串即匹配字面上的字串
* eps (ε) 匹配空集合,永遠成功且不消耗輸入
* . 匹配任意字元
* [abc] [a-z] 表示符合集合中任一字元

Non-terminal 的規則是跟 CFG 較多不同之處:
* PEG 同樣提供來自 regexp 的 ? + * 三個結合符號,也就是零或一個、一個或多個、零至多個,全部都是 greedy。
* e1 e2:依序剖析 e1,在剩餘的字串上剖析 e2,如果 e1, e2 任一剖析失敗則整個規則都失敗(記得如果規則失敗則不會消耗 input)。
* e1 / e2:嘗試 e1,失敗的話就換 e2,這是 PEG 跟 CFG 最大的不同之處,CFG 的接續規則是沒有先後次序的,雖然 CFG 的剖析器,通常為了方便會加入一些先後次序來處理歧義性的問題,例如對 dangling else 採用 shift over reduce ,把多的 else 先拉進來,但在 PEG 中這樣的歧義性可以很簡單的用 / 來消除。
S <- “if” C “then” S “else” S / “if” C “then” S
* 另外有兩個 And predicate &e 跟 Not predicate !e:可以向前看之後的內容是否匹配/不匹配 e,但無論成功或失敗,predicate 都不消耗輸入;理論上的 PEG predicate 可以擁有無限的 predicate 能力,但在實作上應該都有一定的限制。

下面可以舉一些跟 non-terminal 有關的例子:
a* a:永遠會失敗,e1 會吃光所有的 a,造成 e2 失敗。
!”_” .:匹配除底線外任意字元。
“>” / “>=”:是個錯誤的寫法,要不是失敗就是 e1 成功消耗 > 字元,第二個 >= 只是裝飾用的,在運算符的匹配上,應該要依序從長到短排序:>> / << / >= / <= / > / </ =。
另外我查 PEG 時也有遇到一些詭異的文法剖析結果,例如參考資料舉出的:
S -> A $
A -> "a" A "a" / "a"
PEG 會很見鬼的匹配 2^n-1 個 a,以 5 個 a 的狀況,後三個 a 會剖析為 A = aAa,但下一步合併失敗,導致第二個 a 被剖析為 A = a,最後只剖析了前三個字元:失敗。

PEG 的好處在於簡單漂亮,每個 PEG 都是無岐義的,實作上一條規則正好對應一條處理函式,類似 parser combinator,由上而下一跟呼叫:parseExpr -> parseTerm -> parseFactor -> identifier / number 這樣的剖析順序,可以把剖析器寫得漂亮好改;也因此一些語言都有開始支援 PEG parser generator:例如 rust 的 rust-peg, pest,haskell 的 peggy,Dlang 的 pegged 等等。
PEG 並不是單純 CFG 的超集或子集,事實上兩者的概念不太一樣,我建議不要把兩者混為一談,例如知名的 a{n} b{n} c{n} 這個 CSG(n個a 接 n個b 接 n個c,這用 CFG 是產生不出來的),卻可以用 PEG 來剖析;目前是否 CFG 產生出來的文法都能用 PEG 來剖析還是一個開放問題,就留給有興趣的人去挑戰了。

會寫這篇文章,因為最近正在試著用 rust pest 寫一個簡單的剖析器,發現有關 PEG 的中文討論相當的少,就先整理一篇,其實目前要查中文,用「解析表達文法」查到的比較多,但台灣的 parse 就是剖析,所以我標題還是下「剖析表達文法」; pest 的部分因為文件有點少還在卡關當中,下一篇應該會整理相關的用法,然後用它寫個超簡單剖析器。

參考資料:
https://github.com/PhilippeSigaud/Pegged/wiki
本文基礎,大部分的例子都是裡面來的 :P
http://qnighy.hatenablog.com/entry/2015/11/12/162424
神文大推(日文就是…),用了 haskell monad 實作了 CFG, PEG parser,兩者的差距只在 Maybe 跟 list 的差別,現在還在研究當中。
https://www.zhihu.com/question/28525605
一些 CFG 跟 PEG 的比較,算簡單易懂,可以看過去

附註:
S -> A $
A -> "a" A "a" / "a"
這個問題,後來我有想通了,先假設 k 個 a 的時候是可以匹配的;在輸入 n 個 a 的時候,每一個 a 都會率先匹配為 aAa 的前一個,最後 k 個 a 則會匹配為 A,但後面已經沒有 a 了,因此倒數 k+1 個 a 開始的 A = aAa 匹配失敗,匹配為 A = a,接著如果要匹配成功,就要前後都有 k 個 a 才行。
得到結論:k 個 a 匹配則下一個為 2 * k + 1。
Related Posts Plugin for WordPress, Blogger...