107 關務特考四等 資訊處理 程式語言概要 考古題詳解

核心觀念

本題測驗程式語言的語彙結構（Lexical Structure）、命名規範以及編譯器前端（語彙分析器 Scanner 與語法分析器 Parser）之運作機制：

1. 保留字（Reserved Words）與關鍵字（Keywords）的本質差異：

• 保留字：指語言規格中已被系統保留的字串，絕對禁止程式設計師將其用作「使用者自訂識別字」（User-Defined Identifiers，如變數名稱、常數名稱、函式名稱、標籤等）。
• 關鍵字：指在特定語法情境下具有特殊語法意義的字詞（例如代表控制結構、資料型態等）。
• 在現代程式語言中，多數關鍵字同時被設為保留字；但兩者在概念上並不等價（例如早期 PL/I 或 FORTRAN 擁有關鍵字但無保留字；Java 中的 goto 與 const 雖為保留字但不是現行關鍵字）。

2. 編譯器處理效能與複雜度：

• 編譯器在進行語彙分析（Lexical Analysis）與語法分析（Syntax Analysis / Parsing）時，必須判定各個語彙單元（Token）的角色。
• 若特定關鍵字未被設為保留字，語法分析器在辨識陳述句（Statement）類型時，將無法僅憑單一 Token 決定走向，必須依賴較長的前瞻預讀（Lookahead）甚至回溯（Backtracking），導致編譯器實作複雜且降低處理效率。

---

解題方法

本題分為兩個子題，切入點與推導邏輯如下：

1. 第一問：保留字之定義

• 從「語言規範對識別字命名的限制」切入。
• 清楚闡明：保留字不能被使用者作為任何自訂識別字（如變數、常數、函式、型態名稱）。
• 補充其目的：防止使用者命名與語言預設語法結構產生混淆，確保程式碼的可讀性，並降低語法分析的歧義性（Ambiguity）。

2. 第二問：設定 while 為保留字，編譯器處理哪些指令時會變簡單？

• 從「反向思考」切入：若 while 不是保留字，會發生什麼事？ 若 while 不是保留字，使用者可寫出如下指令：
• 指派指令：while = 10;
• 函式呼叫或陣列存取：while(x);
• 條件迴圈：while (x < 10) { ... }
• 分析編譯器前端在面臨非保留字時的困境： 當編譯器掃描到 while 時，無法立即判定當前指令是「迴圈指令」還是「以 while 為變數／函式名稱的表示式／指派指令」，必須往後讀取多個 Token（甚至要等看到後續的指派符號 = 或主體結構）才能做決策，大幅增加文法分析的預讀負擔（需採用 $k \ge 2$ 的 $LL(k)$ 或 $LR(k)$ 文法）。
• 因此，設定 while 為保留字時，編譯器處理以下指令顯著簡化：
• 迴圈控制指令（while 迴圈語句）：只要開頭讀取到 while 記號，可確定為迴圈結構起點，簡化預測剖析（Predictive Parsing）的 First 集合判定。
• 指派指令（Assignment Statements）與變數宣告指令（Declaration Statements）：不必將 while 視為合法左值（l-value）或識別字進行名稱解析，防止符號表（Symbol Table）檢索時的多義衝突。
• 表示式陳述句（Expression Statements）與函式呼叫指令：不必處理如 while(a + b); 到底是呼叫名為 while 的函式還是迴圈陳述句的語意歧義。

---

選項分析

註：本題為申論問答題，非選擇題。以下針對受 while 保留字影響之關鍵「指令類型」進行逐一結構剖析：

1. while 迴圈指令（Loop Statements）：

• 簡化效能：極高（正面確定）。
• 編譯器解析陳述句開頭時，利用 $LL(1)$ 或單一 Lookahead Token 即可命中 while 迴圈產生規則（Production Rule），不需延後決策，語法樹建構直截了當。

核心觀念

本題評量程式語言中的三大核心主題：

1. 遞迴呼叫（Recursion）與執行流程：理解遞迴的「基底條件（Base Case）」與「遞迴條件（Recursive Case）」，以及算式求值時的「由左至右」先深後廣（Depth-First Search, DFS）呼叫順序。
2. 記憶體管理與執行期堆疊（Call Stack）：每次函式呼叫均需在呼叫堆疊上配置「活動紀錄（Activation Record / Stack Frame）」，用於保存區域變數、參數與返回位址（Return Address）。遞迴深度過大會引發堆疊溢位（Stack Overflow）。
3. 演算法複雜度與重疊子問題（Overlapping Subproblems）：樸素樹狀遞迴缺乏快取機制，會對相同的子問題重複計算，導致時間複雜度呈指數級成長（$O(2^n)$ 或精確的 $O(\phi^n)$，其中 $\phi \approx 1.618$ 為黃金比例）。

---

解題方法

(一) $fib(4)$ 的呼叫過程與結果

在多數主流高階語言（如 Python、C、Java）中，算術運算子 + 的運算元依循「由左至右」的求值順序。因此，fib(n-1) + fib(n-2) 會先完整展開左側的 fib(n-1)，待其返回具體數值後，才呼叫右側的 fib(n-2)。

1. 遞迴呼叫樹狀結構（Call Tree）

 fib(4)
 / \
 fib(3) fib(2)
 / \ / \
 fib(2) fib(1) fib(1) fib(0)
 / \
 fib(1) fib(0)

2. 逐步追蹤歷程（Trace）

1. 呼叫 $fib(4)$：

• 不符合基底條件，需計算 $fib(3) + fib(2)$。
• 先遞迴呼叫左子樹 $fib(3)$。

2. 呼叫 $fib(3)$：

• 不符合基底條件，需計算 $fib(2) + fib(1)$。
• 先遞迴呼叫左子樹 $fib(2)$。

3. 呼叫 $fib(2)$：

• 不符合基底條件，需計算 $fib(1) + fib(0)$。
• 先遞迴呼叫左側 $fib(1)$。

4. 呼叫 $fib(1)$：

• 符合條件 $n == 1$，直接返回 $1$。

5. 呼叫 $fib(0)$：

• 計算 $fib(2)$ 的右側，符合條件 $n == 0$，直接返回 $0$。

6. $fib(2)$ 結算：

• 取得 $1 + 0 = 1$，返回 $1$ 至 $fib(3)$。

7. 呼叫 $fib(3)$ 的右側 $fib(1)$：

• 符合條件 $n == 1$，直接返回 $1$。

8. $fib(3)$ 結算：

• 取得 $fib(2) + fib(1) = 1 + 1 = 2$，返回 $2$ 至 $fib(4)$。

9. 呼叫 $fib(4)$ 的右側 $fib(2)$：

• 重新呼叫 $fib(2)$，內部再度呼叫：
• $fib(1) \Rightarrow$ 返回 $1$
• $fib(0) \Rightarrow$ 返回 $0$
• 此處 $fib(2)$ 結算為 $1 + 0 = 1$，返回 $1$ 至 $fib(4)$。

10. $fib(4)$ 結算：

• 取得 $fib(3) + fib(2) = 2 + 1 = 3$，最終返回結果為 $3$。

• 呼叫總次數統計：共呼叫 $9$ 次函式（$fib(4) \times 1$、$fib(3) \times 1$、$fib(2) \times 2$、$fib(1) \times 3$、$fib(0) \times 2$）。

---

(二) $n$ 很大時在記憶體安排與效率上的問題

當輸入參數 $n$ 數值很大時，此程式會面臨以下嚴重缺陷：

1. 記憶體安排問題（Memory / Call Stack）

• 呼叫堆疊溢位（Stack Overflow）： 每次函式呼叫時，系統必須在呼叫堆疊（Call Stack）配置一個活動紀錄（Stack Frame），用以保存區域變數、參數及返回位址。

核心觀念

本題評量程式語言處理系統中編譯器（Compiler）​與解譯器（Interpreter）​的核心工作原理、內部架構、人機互動能力以及效能權衡（Trade-off）。

1. 編譯器（Compiler）：屬於「兩階段處理（Two-Stage Processing）」。將高階語言原始碼（Source Code）完整翻譯成目標機器語言的目的碼（Object Code）或可執行檔（Executable File）。翻譯完成後，執行階段完全脫離編譯器，由作業系統載入 CPU 原生執行。
2. 解譯器（Interpreter）：屬於「單階段處理（Single-Stage Processing）」。不產生獨立的目的碼檔案，而是將原始程式碼逐行（或逐句、逐指令區塊）讀入，即時進行語法分析並立即模擬執行該指令，翻譯與執行交替進行。
3. 效能權衡指標：

• 編譯開銷（Compile-time Overhead）：編譯前期的語彙、語法、最佳化及目標碼生成耗時。
• 解譯開銷（Interpretation Overhead）：執行時逐行剖析與動態分派（Dynamic Dispatching）所產生的額外負擔。
• 總周轉時間（Total Turnaround Time）：$\text{總時間} = \text{翻譯時間} + \text{執行時間}$。

---

解題方法

本題為標準的公職資訊處理類科申論問答題，評分標準重在「架構條理」與「對比鮮明」。解題切入點如下：

1. 第 (一) 子題（製作方式，佔 15 分）：

• 採「管線化處理階段（Compilation/Interpretation Phases）」為架構切入。
• 編譯器：依前端（Front-end，機器無關）與後端（Back-end，機器相依）劃分六大經典階段（詞彙分析、語法分析、語意分析、中間碼產生、程式碼最佳化、目標碼產生），並說明符號表（Symbol Table）與錯誤處理（Error Handling）之角色。
• 解譯器：說明其解析原始碼並直接由解譯引擎（Execution Engine/Virtual Machine）逐行取指、分析、模擬執行的運作機制。
• 繪製流程對比圖，強化閱卷委員的視覺評分印象。

2. 第 (二) 子題（互動式操作，佔 5 分）：

• 從「REPL（Read-Eval-Print Loop，讀取-求值-輸出迴圈）」機制切入，論述何者能支援即時回饋，並說明編譯器因需完整原始碼、宣告與鏈結（Linking）而無法單行即時互動之原因。

3. 第 (三) 子題（執行次數之效能比較，佔 5 分）：

• 區分「執行一次」與「執行多次（含迴圈重複執行）」兩種情境，分別計算 $\text{翻譯成本}$ 與 $\text{執行成本}$ 的佔比，給出明確結論。

---

題意解析與試題詳解

(一) 編譯器與解譯器之製作方式

編譯器與解譯器的核心差異在於「原始碼轉換為機器動作的時機與管道」：

1. 編譯器（Compiler）的製作方式

編譯器通常採用多階段的管線化流程（Pipeline）製作，分為「前端（Front-End）」與「後端（Back-End）」：

• 詞彙分析（Lexical Analysis / Scanner）：讀入字元串流原始碼，去除空白與註解，根據正規表示式（Regular Expression）切割並辨識出有意義的記號（Tokens）。
• 語法分析（Syntax Analysis / Parser）：依據上下文無關文法（Context-Free Grammar, CFG），將 Tokens 組成抽象語法樹（Abstract Syntax Tree, AST），驗證程式結構是否合乎語法規則。
• 語意分析（Semantic Analysis）：檢查靜態語意，例如型態檢查（Type Checking）、變數是否先宣告後使用、作用域（Scope）檢查，並在語法樹上標註屬性。
• 中間碼產生（Intermediate Code Generation, IR）：將語法樹轉換成與特定硬體架構無關的低階表示法（如三位址碼 Three-Address Code 或 Bytecode）。
• 程式碼最佳化（Code Optimization）：重構中間碼以提升執行效率或降低空間消耗（例如：死碼消除 Dead Code Elimination、常數摺疊 Constant Folding、迴圈不變量外提 Loop-Invariant Code Motion）。
• 目標碼產生（Target Code Generation）：將最佳化後的中間碼轉譯為特定 CPU 架構的機器碼（Machine Code）或組合語言，並分派硬體暫存器。
• 全域元件支援：符號表管理員（Symbol Table Management）儲存識別字屬性與位址資訊；錯誤處理器（Error Handler）回報各階段之錯誤資訊。

[原始碼] → 詞彙分析 → 語法分析 → 語意分析 → 中間碼產生 → 最佳化 → 目標碼產生 → [目的碼/執行檔]
 ↑ ↑ ↑ ↑ ↑ ↑
 └──────────┴───── 符號表管理與錯誤處理 ─────┴──────────┴──────┘

2. 解譯器（Interpreter）的製作方式

解譯器不產生獨立的二進位目標檔，其製作著重於「動態解析與即時執行模擬」：

• 原始碼載入與即時剖析：解譯器同樣包含簡化的前端（詞彙分析與語法分析），讀取一行或一小段敘述後，立即建立對應的內部資料結構（如語法樹節點或內部運算碼 Opcode）。
• 解譯執行引擎（Execution Engine / Virtual Machine）：
• 內部維護一個虛擬的環境狀態（包含記憶體空間、全域/區域變數環境映射表、呼叫堆疊 Call Stack）。
• 核心採用​「Fetch-Decode-Execute」迴圈：逐行讀取指令、解碼其運算意圖，並直接調用解譯器內建的原生函式庫完成對應運算。

核心觀念 本題旨在評量考生對「程式語言設計範式」（Programming Paradigms）的分類與特性的理解程度。核心在於區分以下三種控制流程與抽象化機制：

1. 物件導向範式（Object-Oriented Paradigm）：以「狀態與行為的封裝」為核心，運用類別（Class）、物件（Object）及三大特性（封裝、繼承、多型）來模擬實體世界問題。
2. 函數式範式（Functional Paradigm）：植基於數學上的 $\lambda$-演算（Lambda Calculus），強調「純函數」（Pure Functions）、「不可變性」（Immutability）及「無副作用」（No Side Effects），將運算視為數學運算式的求值。
3. 事件驅動範式（Event-Driven Paradigm）：控制流程並非由固定的線性指令流決定，而是依賴「事件迴圈」（Event Loop）監聽外部訊號（如使用者操作、計時器、硬體中斷），並觸發相應的「事件處理常式」（Event Handler）。

---

解題方法 本題為公職考試常見的標準申論題，配分比重明確（10 分、10 分、5 分，共 25 分）。作答策略如下：

1. 結構對稱化：每個子題嚴格依照題目要求的「基本概念」、「優點」、「適用情形」三等分作答，綱舉目張，方便閱卷委員快速比對給分點。
2. 緊扣代表語言：回答時適時帶入題目提示的代表語言（Java/C++、Scheme、Visual Basic），以實例印證理論，提升作答說服力。
3. 區隔概念差異：

• 物件導向要點出「狀態封裝與代碼重複使用」；
• 函數式要強調「一級公民函數」與「並行運算（Concurrency）安全性」；
• 事件驅動要點出「非同步反應性」與「以事件監聽／回呼函式為核心」。

---

選項分析 本題為申論問答題，無選擇題選項。評分關鍵在於能否精準寫出各範式的「核心專有名詞」與「軟體工程特性」，若僅以一般白話描述而未提及技術術語（如：參照透明性、多型、事件迴圈），將無法取得高分段分數。

---

解題技巧

1. 關鍵字精準打擊：

• 物件導向：封裝（Encapsulation）、繼承（Inheritance）、多型（Polymorphism）、抽象（Abstraction）、動態繫結（Dynamic Binding）。
• 函數式：一級公民（First-class Function）、高階函數（Higher-order Function）、純函數（Pure Function）、參照透明性（Referential Transparency）、無副作用（Side-effect Free）。
• 事件驅動：事件迴圈（Event Loop）、事件傾聽器（Event Listener）、回呼常式（Callback/Handler）、非同步（Asynchronous）、人機介面（GUI）。

2. 避開常見陷阱：

• 誤將「函數式語言」寫成 C 語言那種「程序導向（Procedural）的副程式呼叫」。函數式語言的「函數」是數學映射，不可包含改變外部狀態的副作用。
• 忽略配分比重。第 (一)、(二) 小題各占 10 分，論述深度需充足；第 (三) 小題占 5 分，文字宜精煉扼要，避免頭重腳輕或分配時間不均。

---

【答案】

(一) 物件導向程式語言（如 Java、C++）（10 分）

1. 基本概念：

• 核心哲學：以「物件」（Object）作為系統建構的基本單元，將「資料（屬性／Attribute）」與「操作資料的邏輯（方法／Method）」綁定在一起。
• 核心支柱：
• 封裝（Encapsulation）：隱藏內部實作細節，僅透過公開介面與外界互動，實現資訊隱藏（Information Hiding）。
• 繼承（Inheritance）：子類別可繼承父類別的特性與行為，建立層級分類架構，達到程式碼重複使用。
• 多型（Polymorphism）：同一介面或方法名稱在不同物件實體上具備不同的實作行為，透過「動態繫結」（Dynamic Binding）在執行時期決定呼叫對象。