107 司法特考三等 檢察事務官電子資訊組 程式語言 考古題詳解

核心觀念

本題評量程式語言與編譯器前端設計之核心理論——「形式語言與語法剖析（Syntax Analysis）」。

1. 上下文無關文法（Context-Free Grammar, CFG）： 定義為四元組 $G = (V_N, V_T, P, S)$，其中 $V_N$ 為非終端符號集合（Non-terminals）、$V_T$ 為終端符號集合（Terminals）、$P$ 為產生規則集合（Production Rules）、$S \in V_N$ 為起始符號（Start Symbol）。
2. 混淆文法（Ambiguous Grammar）的形式定義： 若文法 $G$ 所產生的語言 $L(G)$ 中，存在至少一個字串 $w \in L(G)$，能導出下列任一等價條件，則稱文法 $G$ 為混淆文法：

• 該字串擁有兩棵（含）以上結構相異的語法剖析樹（Parse Tree）。
• 該字串擁有兩條（含）以上相異的最左導證（Leftmost Derivation）。
• 該字串擁有兩條（含）以上相異的最右導證（Rightmost Derivation）。

3. 語意衝擊： 語法剖析樹直接決定運算式或語句的語意（Semantics）及求值順序。文法混淆會導致編譯器無法唯一確定程式碼的抽象語法結構，產生語意不確定性。

解題方法

解答申論題宜採「定義闡述 $\to$ 典型範例建立 $\to$ 雙重導證與剖析樹對比 $\to$ 消除混淆之重寫技術」的四段論證結構：

1. 舉例：二元算術運算式文法

考慮一包含加法與乘法的簡易算術運算式文法 $G_1$： $E \to E + E \mid E \times E \mid \text{id}$ 其中 $E$ 為非終端符號（代表運算式 Expression），$+$、$\times$、$\text{id}$ 為終端符號。

考慮目標字串： $w = \text{id} + \text{id} \times \text{id}$

2. 說明與證明（以最左導證為例）

對同一字串 $w$，文法 $G_1$ 存在兩種相異的最左導證（每次皆替換最左側之非終端符號 $E$）：

• 最左導證 A（乘法優先）： $E \Rightarrow E + E \Rightarrow \text{id} + E \Rightarrow \text{id} + E \times E \Rightarrow \text{id} + \text{id} \times E \Rightarrow \text{id} + \text{id} \times \text{id}$ 對應之語法剖析樹：

E
/|\
E + E
| /|\
id E * E
| |
id id

語意解讀：$\text{id} \times \text{id}$ 為子樹，先被計算，再與最左側的 $\text{id}$ 相加。符合數學常規之乘除先於加減。

• 最左導證 B（加法優先）： $E \Rightarrow E \times E \Rightarrow E + E \times E \Rightarrow \text{id} + E \times E \Rightarrow \text{id} + \text{id} \times E \Rightarrow \text{id} + \text{id} \times \text{id}$ 對應之語法剖析樹：

E
/|\
E * E
/|\ |
E + E id
| |
id id

語意解讀：$\text{id} + \text{id}$ 為子樹，先被計算，再與最右側的 $\text{id}$ 相乘。違反常規運算順序。

因字串 $\text{id} + \text{id} \times \text{id}$ 存在兩棵相異的剖析樹，故文法 $G_1$ 為混淆文法。

3. 解決方案（消除混淆）

透過引入額外的非終端符號分層（Stratification），強制明定運算子優先權（Precedence）​與結合律（Associativity），可將 $G_1$ 改寫為等價且無混淆的文法 $G_2$：

核心觀念

本題旨在測驗程式語言（Programming Languages）中副程式（Subprogram）呼叫時的參數傳遞機制（Parameter Passing Modes）​及其語意模型。核心概念涵蓋形式參數（Formal Parameter）與實際引數（Actual Argument）之繫結時機（Binding Time）、求值策略（Evaluation Strategy）、資料傳遞方向（In / Out / In-Out Mode）以及記憶體共用所引發的副作用（Side Effects）與別名現象（Aliasing）。

主要的參數傳遞方法包含以下四種：

1. 傳值呼叫（Call-by-Value / Pass-by-Value）：單向傳入（In-mode）。將實引數的數值複製一份給形參，形參與實引數佔用各自獨立的記憶體位址，函式內部對形參的修改完全不影響呼叫端的實引數。
2. 傳址呼叫／傳參考呼叫（Call-by-Reference / Pass-by-Reference）：雙向傳遞（In/Out-mode）。將實引數的記憶體位址（L-value）繫結至形參，形參與實引數共用同一記憶體位址（即形參成為實引數的別名 Alias），函式內修改形參會即時反應至呼叫端實引數。
3. 傳名呼叫（Call-by-Name）：晚期求值／延遲求值（Late / Lazy Evaluation，源於 Algol 60）。形參在語意上等同於實引數運算式的「文字替換」，每次函式中讀取或修改形參時，均會在呼叫端的環境中重新求值（Re-evaluation）。
4. 傳值回傳呼叫（Call-by-Value-Result / Copy-in Copy-out）：雙向傳遞（In/Out-mode）。呼叫函式時先複製實引數的值給形參（Copy-in），函式執行結束返回呼叫端前，再將形參的最新數值複製寫回實引數的位址（Copy-out）。

解題方法

為了清楚展示至少三種（此處列出最經典之四種）參數傳遞方式在執行上的根本差異，採用單一統一的程式碼範例進行變數追蹤（Trace）。範例程式特意設計了包含「陣列索引相依」與「數值遞增副作用」的語法結構，以突顯計算時機與位址繫結的本質區別。

統一範例程式碼（C-like 虛擬碼）

int i = 1;
int a[3] = {0, 10, 20}; // a[1] = 10, a[2] = 20

void sub(int x, int y) {
 x = x + 1;
 y = y + 2;
}

int main {
 sub(i, a[i]);
 // 輸出 i, a[1], a[2]
}

各傳遞方法之執行推導與結果分析

1. 傳值呼叫（Call-by-Value）

• 進入函式：計算實引數數值並複製給區域變數 $x$ 與 $y$。此時 $x = i = 1$，$y = a[1] = 10$。
• 函式執行：
• $x = x + 1 = 1 + 1 = 2$
• $y = y + 2 = 10 + 2 = 12$
• 離開函式：區域變數 $x, y$ 釋放，全域變數 $i, a[1], a[2]$ 完全不受影響。
• 執行結果：$i = 1,\ a[1] = 10,\ a[2] = 20$。

2. 傳址呼叫（Call-by-Reference）

• 進入函式：求出實引數之位址並傳入。$x$ 繫結至 $i$ 的位址；$y$ 繫結至 $a[i]$ 的位址（此時 $i=1$，故繫結至 $a[1]$）。
• 函式執行：
• $x = x + 1$：直接寫入 $i$ 的位址，使 $i$ 變為 $1 + 1 = 2$。
• $y = y + 2$：直接寫入 $a[1]$ 的位址，使 $a[1]$ 變為 $10 + 2 = 12$。
• 離開函式：實引數隨時處於即時同步狀態。
• 執行結果：$i = 2,\ a[1] = 12,\ a[2] = 20$。

3. 傳名呼叫（Call-by-Name）

• 進入函式：不預先計算引數值，而是將形參進行文字代換：$x \to i$，$y \to a[i]$。
• 函式執行：
• $x = x + 1 \implies i = i + 1$：求值並寫入 $i$，使 $i$ 變為 $1 + 1 = 2$。
• $y = y + 2 \implies a[i] = a[i] + 2$：此時 $i$ 已為 $2$，故重新求值時存取的是 $a[2]$，即 $a[2] = a[2] + 2 = 20 + 2 = 22$。
• 離開函式：$a[1]$ 未被觸及，$a[2]$ 被修改。
• 執行結果：$i = 2,\ a[1] = 10,\ a[2] = 22$。

4. 傳值回傳呼叫（Call-by-Value-Result）

核心觀念

本題評量程式語言（Programming Languages）中變數的領域規則（Scoping Rules）​與非區域變數名稱解析（Non-local Name Resolution）​機制：

1. 領域（Scope / 作用域）：程式中識別字（Identifier，如變數名稱）與其實體（Entity / Memory Location）繫結（Binding）的有效可視範圍。
2. 靜態領域（Static Scoping，又稱語法領域 Lexical Scoping）：變數的有效範圍由程式碼的空間文本結構（語法定義的巢狀區塊階層）​決定。名稱解析在編譯期（Compile-time）即可完成。
3. 動態領域（Dynamic Scoping）：變數的有效範圍由程式執行時的時間呼叫順序（呼叫鏈 Call Chain / 執行堆疊 Call Stack）​決定。名稱解析必須在執行期（Run-time）動態尋找。

解題方法

本題為經典問答題，答題架構應包含三大核心部分：

1. 觀念與機制對比：以「判定依據」、「解析時機」與「代表語言」切入，建立兩者的本質差異。
2. 具體程式範例：使用最精簡且對比鮮明的虛擬碼，展示同一段程式碼在兩種領域規則下產生不同的輸出結果，並詳細推導解析過程。
3. 優缺點系統化分析：由「軟體工程（可讀性、維護性、模組化）」、「系統效能（編譯檢查、執行開銷）」及「使用彈性」三個維度全面剖析。

一、靜態領域與動態領域的本質差異

二、具體程式範例與推導

設計以下虛擬碼（Pseudo-code）結構：

int x = 10; // 全域變數

void sub1 {
 print(x);
}

void sub2 {
 int x = 20; // sub2 之區域變數
 sub1;
}

void main {
 sub2;
}

1. 靜態領域（Static Scoping）下的執行推導：

• sub1 中參考了變數 x，但 sub1 本身未宣告區域變數 x。
• 依據語法結構，向外層語法區塊（Lexical Parent）尋找，其外層為全域環境。
• 找到全域變數 int x = 10。
• 輸出結果：10

2. 動態領域（Dynamic Scoping）下的執行推導：

• 程式進入 main $\rightarrow$ 呼叫 sub2 $\rightarrow$ sub2 呼叫 sub1。
• 當 sub1 執行 print(x) 時，沿著當前執行期的呼叫堆疊（Call Stack）向上搜尋最近的呼叫者。
• sub1 的直接呼叫者為 sub2，而 sub2 內部宣告並活化了區域變數 x = 20。
• sub1 繫結至 sub2 中的 x。

核心觀念

本題旨在評量考生對物件導向程式設計（Object-Oriented Programming, OOP）中多型（Polymorphism）​實作機制的掌握程度。其核心理論涵蓋：

1. 多載（Overloading）：屬於特設多型（Ad-hoc Polymorphism），採用靜態繫結（Static Binding / Early Binding）。編譯器在編譯時期依據「方法名稱」與「參數特徵標記（Parameter Signature）」決定呼叫的具體方法。
2. 覆寫（Overriding）：屬於子型態多型（Subtyping Polymorphism），採用動態繫結（Dynamic Binding / Late Binding）。在具備繼承關係的前提下，子類別重新定義父類別已存在的方法，執行時期（Runtime）依據「物件實體的實際型態（Actual Type）」動態分派（Dynamic Dispatch）至對應實作。

解題方法

解答本題需從「概念定義」、「語法規則與特徵標記」、「繫結與執行時機」、「繼承相依性」四大維度進行結構化對比，並搭配一段簡明且具備兩者特性的程式碼範例（以考科最通用的 Java 語言為例）具體說明。

一、覆寫與多載的本質差異

1. 定義與目的

• 多載（Overloading）：在同一類別內（或繼承架構中），定義多個「方法名稱相同但參數串列不同」的方法，目的是提高介面的彈性與程式碼可讀性，免除為相似功能取不同名稱的繁瑣。
• 覆寫（Overriding）：子類別重新實作父類別中「方法名稱與參數特徵完全相同」的方法，目的是讓子類別能依自身需求特化行為，實現執行期多型。

2. 方法特徵標記（Method Signature）之約束

• 多載：
• 方法名稱必須相同。
• 參數列（參數型態、數量或排列順序）必須不同。
• 回傳型態、存取修飾詞（Access Modifier）及拋出之例外（Exceptions）可相同或不同，但不能僅憑回傳型態不同而構成多載。
• 覆寫：
• 方法名稱、參數型態、數量與順序必須完全一致。
• 回傳型態必須相同或相容（允許協變回傳型態 Covariant Return Type，即子類別回傳型態為父類別回傳型態的衍生子類別）。
• 子類別覆寫方法的存取權限不得嚴格於父類別（例如父類別為 protected，子類別覆寫時只能為 protected 或 public）。
• 子類別拋出的受檢例外（Checked Exception）範圍不得廣於或多於父類別方法宣告的例外。

3. 繫結機制與執行效能

• 多載：在編譯時期（Compile-time）​依據呼叫端傳入之引數靜態型態（Declared/Static Type）完成方法簽章的解析與繫結，無執行期額外查找開銷。
• 覆寫：在執行時期（Runtime）​透過虛擬方法表（Virtual Method Table, vtable）動態解析，依據底層物件實際型態決定呼叫版本。

4. 繼承關係相依性

• 多載：不以繼承為必要條件，通常定義於同一個類別內部。
• 覆寫：必須存在於具備階層關係的類別之間（父子繼承或介面實作）。

二、程式碼舉例說明

以下使用 Java 程式碼同時示範多載與覆寫的運作：

核心觀念

本題評量邏輯程式語言（Logic Programming）​中 Prolog 的核心運作機制，主要涵蓋以下觀念：

1. 串列結構與模式匹配（Pattern Matching）：

• Prolog 串列的基本結構為 [Head | Tail]，其中 Head 代表串列的第一個元素，Tail 代表其餘元素所構成的子串列（若無剩餘元素則為空串列 []）。
• 語法 [X, X | Z] 表示新串列的頭部連續由兩個相同元素 $X$ 組成，其後續的尾部串列為 $Z$。

2. 單一化（Unification）：

• Prolog 在執行時透過單一化演算法比對目標（Goal）與子句頭部（Clause Head），使對應的變數進行繫結（Binding/Instantiation）。

3. 遞迴推論（Recursive Resolution）：

• 邏輯程式透過「事實（Fact）」建立遞迴基底條件（Base Case），透過「規則（Rule）」建立歸納推導步驟。

4. 追蹤模型（Tracing Model / 4-Port Model）：

• Prolog 查詢的執行過程包含呼叫（Call）、成功離開（Exit）、重試（Redo）與失敗（Fail）。進行追蹤時，必須完整展現子目標的產生、變數單一化以及回代（Back-substitution）過程。

解題方法

(一) 函式 $mystery$ 的功能解析

分析題目給定的兩條子句（Clauses）：

1. 基底條件（Fact）：

mystery([], []).

當輸入為空串列 [] 時，輸出亦為空串列 []，作為遞迴終止條件。

2. 遞迴規則（Rule）：

mystery([X|Y], [X, X|Z]) :- mystery(Y, Z).

• 若第一個引數（輸入串列）非空，則拆分為首元素 $X$ 與尾串列 $Y$。
• 規則體（Rule Body）以原尾串列 $Y$ 作為輸入進行遞迴查詢，求得輸出串列 $Z$。
• 規則頭（Rule Head）將原首元素 $X$ 連續複製兩次放入輸出串列的前端，組合成新串列 [X, X | Z]。

結論： $mystery/2$ 述詞的功能是將輸入串列中的每一個元素複製兩次（連續重複出現兩次），並維持原有的相對順序，產生長度為原串列兩倍的新串列（即串列元素的雙重倍增，Duplication of elements）。

(二) 目標 mystery([1, 2, 3], X). 的執行與跟蹤步驟（Tracing Steps）

依據 Prolog 標準推論順序，列出每一步驟的單一化、產生的子目標及回代推導：

• 步驟 1（Call 第 1 層目標）：

• 呼叫目標：mystery([1, 2, 3], X)

• 與規則 2 mystery([X1|Y1], [X1, X1|Z1]) :- mystery(Y1, Z1). 進行單一化： $X_1 = 1,\quad Y_1 = [2, 3],\quad X = [1, 1 \mid Z_1]$

• 產生子目標：mystery([2, 3], Z1)

• 步驟 2（Call 第 2 層遞迴）：

• 呼叫目標：mystery([2, 3], Z1)

• 與規則 2 mystery([X2|Y2], [X2, X2|Z2]) :- mystery(Y2, Z2). 進行單一化： $X_2 = 2,\quad Y_2 = [3],\quad Z_1 = [2, 2 \mid Z_2]$

• 產生子目標：mystery([3], Z2)

• 步驟 3（Call 第 3 層遞迴）：

• 呼叫目標：mystery([3], Z2)

• 與規則 2 mystery([X3|Y3], [X3, X3|Z3]) :- mystery(Y3, Z3). 進行單一化： $X_3 = 3,\quad Y_3 = [],\quad Z_2 = [3, 3 \mid Z_3]$

• 產生子目標：mystery([], Z3)