高考申論題
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
拿到形式語言的文法題，首先回想文法的四元組定義 G=(N, Σ, P, S)。大寫字母通常代表可進一步推導的非終結符號 (N)，最終字串的組成元素（如本題的括號）為終結符號 (Σ)，而文法規則的最左側起點即為起始符號 (S)。
小題 (二)
針對()()()字串，推導出 left-most derivation sequence。
思路引導 VIP
看到「最左推導（Left-most derivation）」，核心原則就是：在每一個推導步驟中，永遠只挑選字串中「最左邊」的非終結符號（此題為 S）進行展開。觀察目標字串為三個 () 組合，需善用 S -> SS 規則擴充符號數量，再逐一以 S -> () 替換。
小題 (三)
針對((( )))()字串，推導出 right-most derivation sequence。
思路引導 VIP
最右推導（Right-most derivation）的核心原則是：在每一步的推導過程中，永遠優先替換句型中『最右邊』的非終結符號（Non-terminal symbol）。觀察目標字串 ((( )))()，可先透過 S -> SS 切分為左右兩部分，接著嚴格由右至左逐步展開對應的括號結構。