Re: [問題] 計概觀念問題
※ 引述《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)
推
03/31 18:44, , 1F
03/31 18:44, 1F
→
03/31 18:44, , 2F
03/31 18:44, 2F
推
03/31 18:53, , 3F
03/31 18:53, 3F
推
03/31 23:43, , 4F
03/31 23:43, 4F
→
03/31 23:43, , 5F
03/31 23:43, 5F
→
03/31 23:44, , 6F
03/31 23:44, 6F