身心障礙人員考試身障四等-資訊處理類科計算機概要105 年第 22 題單選題
若某一語法以 BNF(Backus-Naur Form)記述如下:
$$
\begin{array}{l} \langle \mathrm{str} \rangle : := \langle \mathrm{A} \rangle \mathrm{x} \langle \mathrm{B} \rangle \\ < \mathrm{A} >: := < \mathrm{A} > \mathrm{y} | \mathrm{y} \\ < \mathrm{B} >: := \mathrm{x} < \mathrm{B} > | \mathrm{x} \\ \end{array}
$$
則下列那一字串不符合此語法規則?
Ayyxxx
Byyxx
Cyyyxx
Dyyx正確答案
D正確答案
BNF 語法推導題,<str> 結構固定為 <A>x<B>,且 <B> 至少產生一個 x,故字串結尾至少需兩個 x。
為什麼答案是 D
題目問「不符合」者。<str> 結構為 <A>x<B>,其中 <B> 定義為 x<B>|x,代表 <B> 產生的字串必以 x 開頭且至少含一個 x。因此 <str> 中間的 x 加上 <B> 的首個 x,結尾至少要有連續兩個 x。yyx 結尾僅一個 x,違反規則。
載入中…
完整詳解
Pro · 無限重點 BNF 語法推導題,<str> 結構固定為 <A>x<B>,且 <B> 至少產生一個 x,故字串結尾至少需兩個 x。
觀察 <B> ::= x<B> | x,無論如何推導 <B> 必以 x 開頭且至少含一個 x。加上中間固定的 x,合法字串結尾至少是 xx。選項 D 結尾僅單個 x,直接排除。
逐選項分析
A✕
<A> 推導為 yy(y+y),中間固定 x,<B> 推導為 xx(x+x)。組合為 yyxxx,符合 <A>x<B> 結構且 <B> 合法,為正確字串。
B✕
<A> 推導為 yy,中間固定 x,<B> 推導為 x(終止條件)。組合為 yyxx,符合語法規則。<B> 最少就是一個 x,此選項剛好是最短合法形式之一。
C✕
<A> 推導為 yyy(三次遞迴),中間固定 x,<B> 推導為 xx。組合為 yyyxx,完全符合語法。<A> 與 <B> 的長度可獨立變化,不影響合法性。
D✓ 正確
題目問「不符合」者。<str> 結構為 <A>x<B>,其中 <B> 定義為 x<B>|x,代表 <B> 產生的字串必以 x 開頭且至少含一個 x。因此 <str> 中間的 x 加上 <B> 的首個 x,結尾至少要有連續兩個 x。yyx 結尾僅一個 x,違反規則。
BNF 符號與推導規則對照
| 符號 | 意義 | 本題對應 | 解題關鍵 |
|---|
| ::= | 定義為 | <str> ::= <A>x<B> | 左側被右側取代 |
| | | 或(選擇) | <A>y | y | 二選一進行推導 |
| < > | 非終端符號 | <A>, <B>, <str> | 必須繼續展開直到消除 |
| x, y | 終端符號 | 最終字串的組成元素 | 不可再展開,即答案字符 |
考生易忽略 <str> 中間有一個「固定的終端符號 x」,誤以為整個字串的 x 都來自 <B>。實際上 <str> = <A> + 'x' + <B>,而 <B> 又至少貢獻一個 x,所以合法字串中 x 的總數至少為 2,且最後兩個字符必為 xx。選項 D 的 yyx 看似有 x,但數量不足。