[編譯器的研究]parser grammar

這次有找到新的參考，是國內大學(註1)的講義，因此把一些英文名詞換成中文來寫。
文章也比較順眼一點。
parser 的工作是語法分析(syntactic analysis)，要完成這項工作，
需要兩個先決條件，一個是字彙分析(lexical analysis)的結果，
一個是文法(grammer)已經設計完畢。文法是由一組推導(derivation)所形成。
用白話一點的方式來說，parser的工作就是
找出字彙分析(lexical analysis)的結果是由哪些推導、依據什麼順序產生的。
找出這些推導及順序，記錄下來這些推導及順序，
就是所謂的建立 parse tree 了。

字彙分析(lexical analysis)的結果，之前已經有提過。
所以現在要來看一下文法的表示方式。
在一般的編譯器課程裡，大多使用的是 BNF 的表示方式(註2)。
之前的課本提到的方式則是CNF(註3)。

BNF 的表示方式的元素有(1)終端符號、(2)非終端符號、(3)指定符號、(4)選擇符號。
一個推導(derivation)規則，可以表示成

<符號> ::= __expression__

其中，<符號> 這是指非終端符號，所有的非終端符號都用 < > 括起來。
::= 這是指定符號，用來將表示式分成左邊跟右邊。
| 這個是選擇符號。
其他出現的符號，都算是終端符號。
在指定符號的左邊，只能出現非終端符號，
在指定符號的右邊，叫做 expression，因為他可以是所有符號的組合。
一個推導規則表示，在左邊的非終端符號，可以被替換右邊的 expression。
因為這個操作規則，只出現在右邊的符號，永遠不能被替換，
不能再被推導的符號叫做終端符號。
選擇符號是用來分隔不同的選擇。
一個綜合範例：

<A> ::= <B> | <C> + <D>

<A> <B> <C> <D> 是四個終端符號
+ 是終端符號
| 是分隔符號
這個規則，就是表示<A> 可以被替換成 <B> 或著是 <C> + <D>
一般而言，一組推導之中，列在最上面的那一個與別人不太一樣。
因為推導過程需要開始，而最開始的非終端符號就需要寫在最上面。

有了文法，就需要有尋找推導規則的方法，這個方法叫做剖析方法(parse)
有分成LL及LR兩大類。
LL = parse from left construct leftmost derivation
LR = parse from left construct rightmost derivation
因為文法的表示方式，可以表達到 context-free 語言，
而單純的 LL 及 LR 的尋找方法無法涵蓋整個 context-free 語言。
因此，大多的實作上，都要使用到LL(1) 或 LALR 來滿足實際需求。
選擇 LL 或是 LR 對於文法的設計，也會有一點點的影響。
例如使用 LL 方法的時候會遇到的 left recursion 的問題，
就要在設計文法的時候避開。

簡單講完文法設計的原則，就來試試設計自己的文法。
字彙分析(lexical analysis)的結果要回頭看一下 scanner 那篇的最後。
我設計文法如下：

<msg> ::= timestamp <desc> secs_comment <secs_msg> | timestamp eap_log_1 xml_transaction | timestamp eap_log_1
<desc> ::= <secs_msg_name> colon secs_SxFy <secs_w_bit> | <secs_msg_name> colon secs_SxFy
<secs_msg_name> ::= normal_word
<secs_w_bit> ::= normal_word
<secs_msg> ::= <secs_msg_body> secs_end | secs_end
<secs_msg_body> ::= <secs_msg_item> secs_comment | <secs_msg_item>
<secs_msg_item> ::= secs_item_a | secs_item_u | secs_item_b | secs_item_bool | secs_item_f | secs_item_i  | secs_list_start secs_comment <secs_msg_item> secs_list_end | secs_list_start <secs_msg_item> secs_list_end | secs_list_start secs_comment secs_list_end | secs_list_start secs_list_end

接下來挑選最符合人的思考的剖析方法叫做遞迴-下降方法，屬於LL類型。
因為這個方法想法直接，用程式來實作時非常直覺，
據說 c# 的 parser 也是用這種方法寫的。
在設計文法的時候儘量把同一個非終端符號寫在一行，
接下來檢查幾個項目，減少實作上的問題：
(1)檢查一下有無 left recursion 問題。
left recursion 的問題是就文法中，左邊的符號跟右邊的第一個符號一樣，
例如：
<a> ::= <a> + <b>
或是
<a> ::= <a> + c

(2)檢查文法中，有無需要「選擇」，
例如以下的文法，不先偷看一下，沒辦法知道選哪一個推導：

<desc> ::= <secs_msg_name> colon secs_SxFy <secs_w_bit> | <secs_msg_name> colon secs_SxFy

所以LL(0)是不太可能的。
如果希望LL(1)就能夠剖析，還是需要再改寫
<desc> 可以有兩個選擇，這兩個選擇前面都一樣，只差在尾巴，
一個有<secs_w_bit>，一個沒有。要先偷看的話，是要看到 4 個之後。
所以改寫成
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
<secs_SxFy_sym> ::= secs_SxFy | secs_SxFy <secs_w_bit>
同理：
<msg> ::= timestamp <secs_type_msg>| timestamp <host_type_msg>
<secs_type_msg> ::= <desc> secs_comment <secs_msg>
<host_type_msg> ::= eap_log_1 | eap_log_1 xml_transaction

(3)把「出現0次或1次」、「出現0次或多次」、「出現1次或多次」的關係整理一下。
這一步需要用到多一點的BNF變種，{ 出現0次或多次 }、[出現0次或1次]，
這樣寫在實作時也方便參考。
例如：

<secs_msg> ::= <secs_msg_body> secs_end | secs_end

改成

<secs_msg> ::= {<secs_msg_body>} secs_end

整理完的文法如下：

<msg> ::= timestamp <secs_type_msg>
          | timestamp <host_type_msg>
<secs_type_msg> ::= <desc> secs_comment <secs_msg>
<host_type_msg> ::= eap_log_1 {xml_transaction}
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
          | normal_word {normal_word}
<secs_SxFy_sym> ::= secs_SxFy {<secs_w_bit>}
<secs_msg_name> ::= normal_word
<secs_w_bit> ::= normal_word
<secs_msg> ::= {<secs_msg_body>} secs_end
<secs_msg_body> ::= <secs_msg_item> {secs_comment }
<secs_msg_item> ::= secs_item_a {secs_comment}
                    | secs_item_u {secs_comment}
                    | secs_item_b {secs_comment}
                    | secs_item_bool {secs_comment}
                    | secs_item_f {secs_comment}
                    | secs_item_i {secs_comment}
                    | secs_list_start {secs_comment} {<secs_msg_item>} secs_list_end

接下來就可以開始把 parser 的程式寫出來

(註1)：http://www.nhu.edu.tw/~ycliaw/Teaching/9901/SP/05_Compiler.pdf
(註2)：http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form
(註3)：http://en.wikipedia.org/wiki/Chomsky_normal_form