Re: [問題] BNF文法問題

看板Programming作者yauhh (喲)時間14年前 (2011/05/11 20:47)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串6/6 (看更多)

※ 引述《killermomo (殺Mo)》之銘言： : ※ 引述《yauhh (喲)》之銘言： : : 2*3+4*5 由 E 規則可能有 <E,2>*<T,3+4*5> 或 <E,2*3+4>*<T,5> 而前者一下子 ^^^^^^^^^^^^^^^ : : 就會推到盡頭得不到解答. 然後可以看後者: : 延續y大的答案而產生的問題... : 該如何判斷一個文法如何拆解呢? : : 不太懂這句 : 而前者一下子就會推到盡頭得不到解答 : 因為我推導出來E * T之後 : T再推導下去,感覺就推不出來了... : 真令人緊張,不知道之前有弄錯什麼. : 是因為這樣才不考慮這個解答嗎? 前一項是 E 2 + T 3+4*5, 看那個 T 只能解成 T 3+4, F 5. 於是,在此已經看不到 T 3+4 該怎麼拆了,遇到盡頭. 這樣就是 parse 失敗. : 另外一問... : E→E + T | T : T→T * F | F : F→(E) | id (E)可視為E嗎?如不行,這題則不為模糊?對嗎? : 這個文法是模糊文法嗎? : 我的判斷為是模糊文法?對嗎? : ※ 編輯: killermomo 來自: 112.105.171.107 (05/10 00:38) 這種精簡的表達法,每個符號都重要, (E) 當然跟 E 完全不同. http://en.wikipedia.org/wiki/Ambiguous_grammar 文章中談到, 沒有演算法方便來判斷文法有沒有模糊. 雖然演算法理論上說,並沒有足夠的工具判斷模糊,但用人聰明的腦袋好像可以判斷. 像 E -> 是說,如果式子有 + 號, + 號左邊也是 E, 而右邊是 T. 不然全都看成 T. 再往下看,很顯然列為 T 的式子,只有被括弧包著的才可能有 + 號. 所以一條式子同一層如果有好幾個 + 號, 一定是右邊先算. (先解的符號較後算.) 然後看 T ->, 如果式子有 * 號, * 號左邊也算成 T, 右邊是 F, 要不然全是 F. 所以同一層好幾個 * 號也是右邊先算. 結果這個式子可以說是括弧特別優先計算, 同一層級從右邊先算, 先乘除後加減. 有蠻清楚的理由可說是不模糊. -- /yau -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.112.231.115