※ 引述《bnm51315 (La-La)》之銘言： : 最近看書看到"程式語言"這章 : 其中有提到代數運算式語法圖和語法圖所建的字串剖析樹 ^^^^^^^^^^ ^^^^^^^^^^ expression(expr.) parse tree : 但是看了半天 : 書上沒有解釋剖析樹要怎麼轉換、怎麼看 : 所以想請問各位 : 這種東西要怎麼去做轉換以及怎麼去解析... 先說，我對這個也不是很瞭解，有講錯的地方麻煩板上高手更正。 簡單來說， 就是像在實做編譯器等需要「解析語法」的地方， 他內部會有一個判別的語法(grammar), 若是可以依據這個 grammar 的推展來得到最後的 expr.， 就可判斷此 expr. 為合乎語法 e.g. a + b * c - d / e 合乎語法 a + b c - d 不合乎語法 舉一個簡單的 grammar 可能長這樣: <expr> -> <expr> + <term> | <expr> - <term> | <term> (1.1 - 1.3) <term> -> <term> * <fact> | <term> / <fact> | <fact> (2.1 - 2.3) <fact> -> <nums> | (<expr>) (3.1, 3.2) <nums> -> 0 | 1 | 2 | ... | 8 | 9 (4.1 - 4.10) 每一個用 < > 括起來的都是 variable(non-terminal)，意思就是還可以再轉換 最後的 0, 1, ... , 9, +, -, *, / 是 terminal 上面每一條 grammar 代表 [左邊的 valuable] 可以轉換成 [右邊的表示式] 而 | 就是 「或」 的意思，表示從中選一個， 因此我把上面每一種轉換的可能都編上號碼(1.1 - 4.10)，方便說明 假設現在我要判斷 5 * (6 - 1) 是不是一個 expr. 那麼可以試著推推看： <expr> = <term> 1.3 = <term> * <fact> 2.1 = <fact> * <fact> 2.3 = <nums> * <fact> 3.1 = 5 * <fact> 4.6 = 5 * (<expr>) 3.2 = 5 * (<expr> - <term>) 1.2 = 5 * (<term> - <term>) 1.3 = 5 * (<fact> - <term>) 2.3 = 5 * (<nums> - <term>) 3.1 = 5 * ( 6 - <term>) 4.7 = 5 * ( 6 - <fact>) 2.3 = 5 * ( 6 - <nums>) 3.1 = 5 * ( 6 - 1 ) 4.2 至於 paser tree 就是上面用式子推導的過程，改用 tree 的型態來表示，換湯不換藥 <expr> | <term> 1.3 / | \ <term> * <fact> 2.1 | | | <fact> * <fact> 2.3 | | | <nums> * <fact> 3.1 | | \ 5 * <fact> 4.6 | | \ 5 * (<expr>) 3.2 | | / | \ 5 * (<expr> - <term>) 1.2 | | | | | 5 * (<term> - <term>) 1.3 | | | | | 5 * (<fact> - <term>) 2.3 | | | | | 5 * (<nums> - <term>) 3.1 | | | | | 5 * ( 6 - <term>) 4.7 | | | | | 5 * ( 6 - <fact>) 2.3 | | | | | 5 * ( 6 - <nums>) 3.1 | | | | | 5 * ( 6 - 1 ) 4.2 因此，不管從式子推導，或是 parse tree， 我們都可知 5 * (6 - 1) 合乎我們上面所給定那個 grammar 然而你可以發現像是 2(4 * 7 / 3) 這樣是推導不出來的， 它並不屬於我所給的這個 grammar 所定義的語言(language) （但是仍有可能有另外一個 grammar 能夠解析它） -- 我印象中去年不管考試還是寫考古題， 好像都沒碰過這種問題啊。 建議有個大致的認識就好，不用太鑽研 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.2.239 ※ 編輯: rainphiz 來自: 220.133.2.239 (03/31 14:00)