Tag

2018年9月20日 星期四

黃禍

黃禍,作者是王力雄,ISBN:9789862138502

本書是小說,主要在描述中國由於一場水災,造成一系列的連鎖反應,總書記被暗殺、各地軍閥四起、中國內戰、美俄介入,最後以世界大戰作為終結。

我對<黃禍>的評價是最低的。
第一個畢竟這是 1996 年的小說,預測偏很多也不是很意外,書裡的台灣甚至還反攻中國,然後「毫無防備」的台北被丟原子彈……反攻中國?毫無防備?看到與其說是驚呆不如說噴笑。
第二個是主因:作者寫這本書更大的原因,反而是想宣傳他想出的新式民主:逐級遞選制;這本書也就不那麼純粹,轉變成為政治理念服務的小說。雖然說文以載道,但當宣道變成主要目的,文的價值就淡化甚至消失了。
作者在書裡想像了幾天就能成熟的「薯瓜」,可以在營養液裡快速成長,可以在行走中攜帶成長;最後三分之一(也就是下冊)開始描述中國人們在上述逐級遞選制的引導之下,離開中國到富裕國家尋求生存,北邊遷入西伯利亞;西邊走新疆一路到歐洲;南邊去澳洲;東邊跨海到美國。
單純的評論就是作者的一廂情願,也許是作者想像了一幅千萬人遷移的壯觀畫面,又或者作者只是想表達他的逐級遞選制才能成功帶領人群,即便在無秩序世界裡以最有效率的方式達成治理?無論作者所想是哪一個,總歸而言就只是本空想的小說,在一套空想的政治制度下,吃著空想的食物走一趟空想的旅程。

事實上我認為從中冊開始,有些人物就開始變成木偶,隨劇情需要做出各種不同的反應、出現在他該出現的地方、說他該說的話,至於他們到底怎麼做到、或者他們怎麼換腦的?反正作者寫了算。
反正作者的主軸就是讓中國崩潰順便傳個教,嚴格來說雖然中國崩潰看起來很政治不正確,但從字裡行間看來作者還是跳脫不出身為中國人的思考模式,就算中國崩潰了也要拖全世界下水,誰瞧不起中華民族我們就算死也要拉你一起;日本人表面和善可是背地捅刀;美國就是個人信仰,拿起槍背判政府想作亂就作亂……認真來看這本書問題一堆。
我不否認作者文以載道的努力,就如同他的另一部小說<大典>,闡述的是在全面監控的高科技之下,至高無上的威權,如何在「掌握監控科技」的人的手中傾頹,雖然也是小說,裡面的科技監控也過於匪夷所思;但從後記來看,作者想表達的也是他對於科技民主的期待,對照近期中國社會信用制度的上線,讓大典顯得不這麼空洞。

當年在撰寫黃禍時,作者對於逐級遞選制,也同樣有著他的期待,如果能看到作者這層思想,我想閱讀這本書也就值了,但畢竟是本過時的空想著作,值得看的部分其實不怎麼多。

總評:2.5/10
簡單評論:浪費時間 看看就好* 值得一看 非看不可

黑土

黑土,作者為:Timothy Snyder,ISBN:9789570851236
udn導讀

如果提到二戰對猶太人的大屠殺,大家腦中會浮現什麼?
我試著打一段大屠殺描述的文字,大家覺得其中「」標起來的關鍵字同意多少?
大屠殺:納粹德國在希特勒的意識型態下,由「德國人」開動德國之「國家機器」,有系統將「德國之猶太人」標籤、分類、運送往「德國奧斯威辛*」為代表的的「集中營」,以「毒氣室」對猶大人進行工業化的大屠殺。(*或譯奧許維茲集中營)

事實上,對於歷史上的大屠殺來說,上面幾個標籤都不太正確,這是黑土想要述說的論點,一個一個來看:
  • 德國人:部分正確,但真實的大屠殺發生地帶其實是從波蘭以東,進到白俄羅斯、烏克蘭、波羅的海三小國等地,進行煽動的或許是德國人,動手的卻未必,多數是在地的警隊跟居民。
  • 國家機器:正好相反,不是因為德國動員國家機器殺人,而是德國在東歐創造了大片無政府狀態的區域,使得大屠殺得以發生。
  • 德國之猶太人:同樣的,德國猶太人存活率顯著高於東歐地帶的猶太人*,只要能持有國家保護的身分,國家要動手也要瞻前顧後,還會受到官僚的綁手綁腳。
  • 德國奧斯威辛、集中營:事實上集中營大多在前述的佔領區,奧斯威辛在波蘭,德國想要殺人,得先把人遣送到無政府地帶才能動手。
  • 毒氣室:事實是集中營無論在重要性和時間上,在大屠殺中只能排第三,真正重要的大屠殺是東歐的大規模屍坑槍決跟毒氣車。
* 網路上找到以 Anne Frank 為名的紀念網站,雖然比例上有出入,但結論是類似的:大部分被屠殺的猶太人都非德國人。

本書的內容大約分成下面幾個部分:
  • 希特勒的世界觀,戰間期猶太人與波蘭間的競合
  • 德國入侵東歐摧毀國家後的屍坑大屠殺
  • 奧許維茲悖論,國家主權與猶太人存活的關係
  • 拯救猶太人的故事
  • 結語
作者在開頭很仔細的解釋了希特勒的世界觀與波蘭對猶太人的政策,隨後鉅細靡遺的介紹,在巴巴羅薩行動進佔東歐之後,發生在各地的大屠殺與手法;這段的重點在補足全書的脈絡,提醒讀者們大屠殺並不是集中營,而是發生在東歐更廣大的事件,二次世界大戰並不是連綿不絕的戰爭,而是一段極端行為變成日常的時間。
奧許維茲悖論是為本書的關鍵,對大屠殺來說,集中營這個符號跟標誌實在太過顯著,使得大家關注大屠殺只想到集中營,而忽略在奧許維茲真正開始運作之前,在廣袤的東歐土地上,德國已經在當地居民協助下殺害九成九的猶太人,更有甚者,當大部分猶太人被屠盡之後,身在集中營的勞動營 - 作為它本來的目的 - 的猶太人,反而是最後才遭到殺害的。
如果大屠殺在東歐確實發生,我們就要回答:是什麼讓人民互相殘殺?是什麼清除了管理社會的組織?是誰讓人變成獸?起初在東歐國家毀滅上,蘇聯其實也插了一腳,但隨著德國戰敗,蘇聯重新進佔東歐,某種程度上強調集中營正好非常理想的開脫了真正行刑者的責任,使得責任落在德國人與德國的頭上,輕易迴避了東歐民眾當時作為協力者的責任,以及大屠殺真正的關鍵因素:國家毀滅。

作者帶你走遍歐洲各國,看看猶太人何時被殺、為何被殺、被殺多少,發現都和國家主權息息相關,其效果甚至能壓過當地反猶的政治傾向,即便淪為德國的附庸、又是德國近鄰、本身又有強烈反猶政策的丹麥,仍有九成以上的猶太人能存活,只因為丹麥主權堪稱完整;甚至同為軸心國的義大利,猶太人死亡率反而低得出奇,大規模的遣送也要等到墨索里尼倒台,由德軍強力佔領義大利之後才開始行動。
國家不只是一個統治的主體,它同時給予人們身份和連結,在國家內的猶太人能夠求救於官僚、行政體系、朋友,而不致於被歸類為一個猶太人、一個猶太家庭,從社會被分離出來而被殺害,承平時期讓人惱怒的行政效率,反而是猶太人保命的關鍵;同時國家還能保持對外連結,一方面公民身分是國家統治的象徵,要維護國家地位,對於德國不會輕易的交出猶太人;到了二次世界大戰末期,軸心國開始失勢時,本來配合德國的國家也紛紛開始收手,轉而配合國際呼籲暫停國內的猶太遣送行動。

那些拯救猶太人的行動,國家主權再一次發揮力量,無論如何鳳山或日本的杉原千畝發放的簽證、亦或瑞典外交官發放的保護護照,只要能拿到簽證或護照,存活的機會就大大升高,每每以成千上萬的規模保護猶太人;透過國際合作進行的保護行動,也是透過流亡英國的波蘭政府四處奔才得以進行。
沒有國家保護的,就只能仰賴極為少數且力量有限的救援者,甚至就連救援者也受國家主權影響,位在西歐國家的救援者遠比東歐安全,庇護猶太人甚至不是能夠問罪的事情,例如庇護 Anne Frank 的 Miep Gies 即便被發現也能存活,在東歐的國家毀滅區卻會引來殺身之禍。

從黑土中給出來的訊息,在於國家存續的重要性。
對於國家人們有許多看法,但無論是合法壟斷暴力的實體,還是人民、領土、主權、政府綜合體,國家都代表一個授與、守護多數個人權利的主體,我們再怎麼小政府、大企業、開放資料、拆政府原地重建,國家、政府、主權仍然是一個強大、無可取代的組織(就如同七月的颱風,市政府一聲令下四點放假,大家四點就乖乖的去馬路上當停車場、到捷運站擠沙丁魚)。
失去國家的瞬間,所有國家所背書的一切文件、證照、證明都會失去效力,要在這樣的極端環境下,動物星球的極致:大屠殺才得以發生。

以上的情境,我相信身為台灣人的我們其實並不陌生,無論是 1895 年日本政府殖民、或 1949 年中國政權殖民台灣,台灣都在那一瞬間面臨國家的毀滅,接下來就是全國範圍的大清洗,把所有高知識份子跟具有號召能力的人全部洗掉,這一切在波蘭都曾經發生過。
眼下最為危險的,正如同二次大戰前德國所宣稱:波蘭並非國家而且始終不曾存在主權,因為不曾存在,所以所有主權證明都視為無效、所有的法律規定也不曾存在。同樣如此宣稱的,正是海峽對岸的中國政權,堅稱台灣政府不曾擁有主權,本身就是一個危險的信號,可以想見一但台灣政府垮台,等待台灣人民的,只可能是 1895, 1939, 1949 年大屠殺的重演,沒有其他;所有代表政府曾經運作,以及可以維持主權機能的人:軍人、警察、公務人員、高知識份子、社會領袖,絕對會被清掃乾淨,別無例外。
所謂「人之所以異於禽獸者,幾希」,差別在於人類組成國家社會,將人類社會一步步複雜化,用種種規約、法律、習俗,將人身上的動物性給壓制下來,在一個多樣化充滿連結的社會,每條關係都彼此牽制,將我們禽獸的一面給壓制住。

另外一個訊息則是耐心,社會、國家是一個變動遲緩的巨型生物,對一般人來說每分每秒的生活之中,我們幾乎感受不到以數年計量的社會漂移。
但所有的行動,都不可能一蹴可及,就如同今年年底的同婚公投,如果沒過會如何?很可能同婚合法化會等到 10 年之後,說來殘酷,但那又如何?社會本來就是緩慢的,不可能明天起床,所有人都被洗腦成你的觀點,但每天說服一個人、一個就好你願意嗎?
曾經看過一句話:人們都會高估一年能做什麼,卻會低估十年能做什麼。

人們需要知道特效電影如 Avenger ,那樣的超級災難和超級英雄是不切實際的,改變社會和未來是一項大工程,枯燥而且乏味,但卻是唯一預防任何激進行動的唯一方式,如同書名隱喻的,在烏克蘭的肥沃黑土對二戰的德國意味著確保生存的解決方案,德國需要殖民烏克蘭,用黑土確保德國的糧食供應。
這可以套用在任一個國家,面對溫暖化、糧食危機的當今世界,面對風吹草動的危機,黑土意味某種快速、簡單、直覺思考、快問快答的解決方式,如同希特勒將日後餵飽全世界的綠色革命棄若敝屣,轉而訴諸簡單的陰謀論:一切都是猶太人在背後搞鬼,以及快速的解決方案:進佔東歐、殺光住民、殖民確保糧食來源;當陷於快速簡單的解決方案,人們也就失去自省,以及任何替代思考的可能性。
正如一戰未曾結束,希望在巴黎畫畫地圖就能讓歐洲永久和平,只會換得一紙 20 年的停戰協定。科學不會有陰謀論吸引人;枯燥的論述不若網紅的激進發言刺激;冗長的討論也不會比一來一往的網路留言有趣,但我們需要耐心才能真實解決問題,如果我們只想著某種快速的解決方案,我們就更朝希特勒的世界前進一步。


本書最大的問題體現在翻譯上,偶爾會出現一些超級長、夾帶兩層甚至三層意思的句子,像是:「希特勒與那種認為人類之所以異於自然是因為人類有能力想像並創造新的合作形式的政治思想之間有著斷裂」,或者有些明明可以斷句卻又沒斷,感覺就像是全書曾經先用過機器翻譯,之後的校稿潤稿又沒有好好做的結果,不得不說很妨礙閱讀。

總評:6.5/10
簡單評論:浪費時間 看看就好 值得一看* 非看不可
我認為全書內容可以到 7.5 - 8,不過翻譯問題實在太過嚴重,因此稍微扣了點分。

不曾結束的一戰

不曾結束的一戰:作者為 Robert Gerwarth,ISBN:9789571374338
udn導讀

歷史學家或者歷史教育通常喜歡用一個個事件來描述歷史,箇中原因在於,每個人的一生會被無數事件交錯纏繞,人物誌會讓人看不出事情的全貌,編年史會讓事件被時間切成碎片,用事件可以把其中各造都拉進來,綜合編年史和人物誌的優點,完整呈現事件各方立場和時間順序。
有利必有弊,事件史的缺點可以說是歷史的片段化,一個全面的歷史會是任何時間、任何地點都在發生事件的組合,但這遠超過一般人能理解的程度,也因此一些重大事件通常就成為標誌,其開始和結束常被當作歷史的中斷點,一個世界都為之暫停的斷點,但事實上通常不是這樣。

一次世界大戰就是一個例子,由於西線的壕溝戰、毒氣戰、機槍、坦克打造的絞肉機太過引人注目,幾乎都能聽到書寫歷史新頁的沙沙聲,於是大家的目光都集中在西線,第一次世界大戰結束的 1918 年 11 月 11 日,正是西戰線停戰的日子。
普遍的印象,在一次世界大戰結束之後,歐洲進入了所謂的戰間期,普遍印象歐洲也進入一段和平歲月,直到 1939 年德國打響二次世界大戰,事實上,只要稍加涉獵,就知道蘇聯在戰間期時,曾有過紅白兩軍的內戰,跟和平其實相差甚遠。
不曾結束的一戰,寫作目的正是要打破以上的印象,本書從1917年的俄羅斯革命開始,到 1922 年的希土戰爭終局的士麥那大屠殺,從三個面向完整介紹這段時間:1. 戰敗國的下場;2. 橫跨戰勝國與戰敗國的革命與反革命;3. 巴黎和會與帝國解體。
對戰後發生在東歐、中歐、南歐,遍及土耳其帝國、奧匈帝國和俄羅斯帝國的一連串事件,作了清晰完整的介紹。

一戰之後,帝國或因為革命、或因為不堪戰爭拖累、或因為凡爾賽條約,相繼在一戰後瓦解,但隨後而來卻非期盼已久的和平,而是一連串更長久的紛爭,帝國雖然專制,實際上卻對境內各民族都提供一視同仁的權利保障,隨著戰後威爾遜民族自決的風潮,帝國瓦解後的新生民族國家,如波蘭、捷克、匈牙利等國,對國內少數民族的保障更形欠缺,本來相安無事的多民族區域,在「民族」國家這個旗號的擠壓下,緩衝的空間都失去了,於是發源於民族的暴力衝突反而更多;對於多民族區域的歸屬,更引發多國間的競爭角力,甚至於強制性的地區人口交換。作為無根蘭花的猶太人,則變得四處不是人,在各國都被從國家保護中分離出去,最後淪為各國都亟卻清除的對象。
此外凡爾賽條約淪為戰勝國爭利益的場所,有些戰勝國如義大利、希臘無法滿足於條約結果,引爆國內極端主義或再次對外用兵;戰敗國視條約為奇恥大辱,無不謀求以各種方式打破條約;條約又無力調解新生國家地域衝突和民族衝突,以為戰勝就能在地圖上用畫筆訂下新國界;威爾遜的民族自決又有種族限定,以致無法適用的國家同樣無法信任新生的國際聯盟。
凡此種種都為 20 年後的亂局打下根基。

同時,一戰後的革命與反革命為進階化的暴力打開窗口,平民跟戰鬥員的界線首次抹去,頭一回的總體戰,平民成為需要為國家敗戰負起責任的一部分,導致隨之而來的二次世界大戰,目標不再是擊敗對手,而是為了完全消滅國家、消滅人民、謀求「優等」人民的生存空間。
一戰用一個全新民族國家的體制,取代視為落後的專制帝國,卻也因此種下更長遠的暴力。今年正好是標誌上的一次世界大戰結束100週年,正好透過本書,用全新的視角看待一次世界大戰,事實上正如作者所言,即使到了今日,從敘利亞內戰、庫德族等事件,亦或是最近塞爾維亞與科索沃互換領土的爭端(),見證一次世界大戰結束後,當年鑄下的苦果現在為人們所承受著。
有感於大家的歷史常識通常忽略了戰間期,這個重新塑造歐洲,為二次大戰種下遠因的時期,許多重大事件如俄羅期內戰、芬蘭獨立戰爭、希土戰爭,通常不在大家的關注範圍,本書是補助戰間期一本極佳的著作。

相對來說,本書最大的問題是缺乏地圖,由於全文出現許多地名,多是東歐、西亞等不常出現的區域,缺乏地圖讓本書在空間感上略顯薄弱,是個可以改進的方向。

總評:8/10
簡單評論:浪費時間 看看就好 值得一看 非看不可*

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

Related Posts Plugin for WordPress, Blogger...