資訊處理 104 年程式語言概要考古題

靜態類型程式語言需使用某種類型等價（type equivalence）方法以決定類型是否可 匹配（compatible），最常見的是名稱等價和結構等價，請說明這兩種方法。考慮 下列程式碼（X : T 表示變數X 之類型為T），在這兩種類型等價方法下，請分別 說明其中那些變數的類型為可匹配。（20 分） type T = array [1..10] of float X : T Y : T Z : array [1..10] of integer

物件導向語言中，對宣告之實體（如屬性、方法）的可見性（visibility）有那三 種常見的限制？請用你熟悉的語言舉一個簡單的例子解釋這三種限制造成的不同 可見性。（20 分）

請用上下文無關文法（context-free grammar）寫出一套文法規則，以產生與正規表 示式（regular expression），a*(ba*ba*)*，完全相同的語言（*符號代表可重複零到 無數次）。再用你所寫的文法規則，用最右推導（rightmost derivation），推導出 babaaabb 一句。（20 分）

下列的C 程式碼有何問題？如果忽略警告而逕行執行程式，在許多系統上，該程式 將顯示重複的行為，列印出0 1 2 3 4 5 6 7 8 9，為什麼？也請解釋為什麼在其他的 系統上，該程式的執行結果可能會有所不同，甚至結果是無法確定的。（20 分） void foo() { int i; printf("%d ", i++); } int main() { int j; for (j = 1; j <= 10; j++) foo(); }

假設你要寫一段程式碼，來管理數個並行執行緒（thread）之間共享的一雜湊表 （hash table），而雜湊表的操作必須符合原子性（atomicity）。你可以使用一個互 斥鎖（mutual exclusion lock）來保護整個表，你也可以用一個鎖分別保護每個雜湊 表的桶（bucket）。請分別說明這兩種做法的優點和缺點。（20 分）