地特三等申論題
106年
[電力工程] 計算機概論
第 二 題
📖 題組：
四、下列為某一語言之 BNF（Backus-Naur Form）表示法： ::= =
::= + | – | * |
::= A | B | C | D | E
::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
四、下列為某一語言之 BNF（Backus-Naur Form）表示法：
📝 此題為申論題，共 2 小題
小題 (二)
請問此語法是否為混淆的（ambiguous）？請詳細解釋理由。（10 分）
思路引導 VIP
遇到判斷文法是否為混淆（ambiguous）的問題，首要關鍵是回憶其定義：『若一個文法能為同一個字串產生兩棵以上的剖析樹（或兩種以上不同的最左推導），則該文法即為混淆的』。解題策略是直接構造一個包含多個運算子的簡單字串（如 A = 1 + 2 * 3），並實際寫出兩種不同的推導過程來作為嚴謹的證明。
小題 (一)
C = 8 + 3 * 2 – 5 是否合乎此語法？請詳細說明理由。（10 分）
思路引導 VIP
看到 BNF 語法判斷題，首先找出起始符號（通常為第一條規則左側的非終結符），並嘗試透過逐步推導（Derivation）或建構剖析樹（Parse Tree）來生成目標字串。若能成功推導出該字串，即代表合乎語法；反之則否。
BNF 文法混淆性判定
💡 單一合法字串具備多種剖析路徑或剖析樹即為混淆文法。
🔗 文法混淆性驗證標準流程
- 1 選取測試字串 — 挑選含多個不同運算子的字串，如 1+2*3
- 2 執行推導 A — 依某一結合順序展示最左推導過程
- 3 執行推導 B — 更換運算子優先順序，展示第二種推導
- 4 判定混淆 — 證明一個字串對應多條路徑，結論為混淆
↓
↓
↓
🔄 延伸學習：進階延伸：學習如何透過增加非終端符號層級來改寫文法，消除歧義。
