地特三等申論題
105年
[資訊處理] 程式語言
第 一 題
📖 題組：
考慮下列文法：S -> SS |(S)|()（每小題 4 分，共 12 分） (一) 請指出此文法的 terminal symbol、non-terminal symbol 及 start symbol。 (二) 針對()()()字串，推導出 left-most derivation sequence。 (三) 針對((( )))()字串，推導出 right-most derivation sequence。
考慮下列文法：S -> SS |(S)|()（每小題 4 分，共 12 分） (一) 請指出此文法的 terminal symbol、non-terminal symbol 及 start symbol。 (二) 針對()()()字串，推導出 left-most derivation sequence。 (三) 針對((( )))()字串，推導出 right-most derivation sequence。
📝 此題為申論題，共 3 小題
小題 (一)
請指出此文法的 terminal symbol、non-terminal symbol 及 start symbol。
思路引導 VIP
遇到文法組成問題，首先觀察產生式（production rules）。出現在箭頭左側且可被替換的大寫字母通常為 non-terminal symbol；出現在右側且無法進一步展開的具體字元或符號為 terminal symbol；而代表文法推導第一步起點的符號即為 start symbol。
小題 (二)
針對()()()字串，推導出 left-most derivation sequence。
思路引導 VIP
看到「最左推導（left-most derivation）」，應立刻想到在推導字串的每一步驟中，都必須優先選擇「最左邊的非終結符號（non-terminal symbol）」進行展開。同時注意此文法具備模糊性（ambiguity），因此可能存在一種以上的正確推導路徑，只要列出其中一種合法的最左推導即可。
小題 (三)
針對((( )))()字串，推導出 right-most derivation sequence。
思路引導 VIP
本題測驗「最右推導（Right-most derivation）」的概念。解題時需先觀察目標字串的結構將其拆解為左、右兩部分，並在每一步推導過程中，嚴格挑選當時句型「最右邊」的非終結符號（Non-terminal symbol）進行規則替換。