第 一 題

遇到 BNF 推導剖析樹的題目，首先觀察目標字串 aba 的結構，並尋找對應的替換規則。此文法為模糊文法（Ambiguous grammar），因此會有多種合法的剖析樹。建議採取由上而下（Top-down）的方式，以中間字元 b 為切入點使用 S -> SbS 展開，再將左右兩側的 S 分別展開為 SaS，最後將剩餘的非終結符號 S 替換為空字串 ε，這樣能畫出結構最對稱且直觀的樹狀圖。

面對 BNF 語法題，首先回想「不明確語法（Ambiguous Grammar）」的定義：是否能找尋到一個句子，存在兩棵以上的剖析樹（或兩個以上的極左/極右推導）。接著，嘗試用最短的終結符號組合（例如字串 'aa'）帶入推導，若能產生不同的推導路徑，即證明其為不明確。最後，分析原語法同時具備左、右遞迴導致結合律不清的缺陷，並透過改寫為單純的右遞迴或左遞迴來提供解決方案。