國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

第一章 程式語言導論

1-1程式語言基本概念

一、定義

程式 = 演算法+資料結構

是人類與電腦溝通的工具，能描述問題的演算法及其資料結構的概念。每種程式語言都有其特定的撰寫規則 (語法)，只要依其規則撰寫，即可命令電腦完成某些特定的工作。

※圖靈機(Turing Machine)：

[杜林機(Turing machine)] 2 | 94, 104

96交員晉高、104地三

1.又稱確定型圖靈機，是英國數學家艾倫·圖靈於1936年提出的一種抽象計算模型，其更抽象的意義為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。

2.用機器來模擬人們用紙筆進行數學運算的過程，這樣的過程看作下列兩種簡單的動作：

(1)在紙上寫上或擦除某個符號。

(2)把注意力從紙的一個位置移動到另一個位置。

而在每個階段，人要決定下一步的動作，依賴於(1)此人當前所關注的紙上某個位置的符號和(2)此人當前思維的狀態。

3.使用一個無限長的磁帶當作記憶體，磁帶頭有讀與寫的功能，而且可以在磁帶上左右移動。

4.Turing Machine工作的情況就好像無法記得那麼長的資料，但是可以前後瀏覽，作記號並且比對。

※參考資料：

1.http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/05ct/chp08.pdf

2.https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA

二、程式語言的分類

[程式語言分類] 3 | 93,103,104

93專檢、103檢三、104高三

(一)第一代程式語言－機器語言(machine language)

1.是由0與1組成的二進位碼所構成，不同類型的計算機擁有不同的指令群，對應的二進位碼亦不相同，因此是一種與機器相關的語言。

2.撰寫及維護都極為困難，例如麥金塔電腦與 IBM 個人電腦的機器語言不相容。

(二)第二代程式語言－組合語言(assembly language)

1.又稱為低階語言 (low-level language)。將每一條機器語言指令用一個助記憶符號 (memonic symbol) 來取代。

2.組合語言指令與機器語言指令具有一對一的對應關係，因此屬於與機器相關的語言。

(三)第三代程式語言－高階語言(high-level language)：如何做(how) / 師傅

1.又稱為程序導向語言 (procedure oriented language)，告訴電腦如何做。

2.與機器無關，具有移植性，不須要因為電腦設備的不同而修改大量程式指令。

3.例如 Pascal、C、C++、Basic、Fortran 與 Cobol。

(四)第四代程式語言－超高階語言(very high level language)：做什麼(what) / 老闆

1.通常稱為 4GL (fourth generation language)。是問題導向語言 (problem oriented language) 或非程序導向語言 (non-procedure language)，告訴電腦做什麼。

2.例如 SQL (Structured Query Language)。

(五)第五代程式語言－自然語言(nature language)

1.利用人工智慧技術，使其接近人類使用的自然語言 (如英語)，讓電腦讀懂人類的語言。

2.目前人工智慧語言仍處於發展中的階段，現今開發的產品則多是以 Lisp 或 Prolog 語言為基礎，專為特定領域設計的知識庫系統 (如醫療、財經)。

※參考資料：

http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E8%AF%AD%E8%A8%80%E5%A4%84%E7%90%86

三、為何要學習程式語言

增進對所使用程式語言的了解、可以改進程式的架構、有助於選擇合適的程式語言、比較容易學習新的程式語言、較容易設計出一種新的程式語言。

四、電腦的應用領域及相關的程式語言

(一)科學應用：Fortran。

(二)商業應用：COBOL。

(三)人工智慧：LISP、Prolog。

(四)系統程式：發展 UNIX 所用的 C 語言。

(五)超高階語言

UNIX 上面的各種腳本語言 (scripting languages)，例如 shell、ksh、awk、perl。

(六)特殊目的語言(問題導向語言)

例如用於產生商業報表的 RPG (Report Program Generator)。

※參考資料：http://en.wikibooks.org/wiki/Fortran/Fortran_examples

93年專門職業及技術人員檢覈程式語言

答：

略

103年檢察事務官三等程式語言

答：

略

1-2 高階程式語言

一、高階語言的優點

(一)學習容易，學習時間較短

(二)生產力較高，對於人力及管理的需求較少

(三)與機器無關

(四)程式的除錯較容易

(五)編寫較大的應用程式時，不至因瑣碎的程式細節而影響設計的進行

(六)高階語言的結構本身就具有卓越的文件說明能力

二、高階語言的實作

[編譯(compilation)] 18 | 82,86,91,94(2),95(3),96,97(2),98(2),99,100,104,107(2)

82地三、86高三、91地三、94高三(2)、95身三、95港員晉高、95地三、96地三、97高三、97地三、98關薦、98檢三、99高三、100關四、104地三、107關四、107鐵高

(一)編譯程式(Compiler)：程式編譯器

1.定義：是一種系統程式，將高階語言的原始碼轉換成「可執行檔」 (目的程式)。

2.編譯的作法：

原始程式→編譯器 (高階語言轉成組合語言)→組譯器 (組合語言轉成機器語言)→目的程式。

3.編譯的流程：

※參考資料：

http://digital.cs.usu.edu/~cdyreson/teaching/languages/142/lectures/printintroduction.htm

※編譯器的六大階段：

※參考資料：陳鍾誠-系統程式-第8章編譯器.ppt

※語彙分析(Lexical Analysis)：詞彙分析 / 詞法分析

1.定義：

將敘述句拆成組成語法的基本單元，例如保留字、關鍵字、識別字、運算子等。

2.範例：

sum = sum+i

※參考資料：陳鍾誠-系統程式-第8章編譯器.ppt

※語法分析(Syntax Analysis)：

1.將程式符號轉換成階層式的語法樹 (Syntax Tree) 符號。

2.在語法樹中，階層最高的節點 (Node) 為 assign 的符號，其餘的節點為其他的運算元符號，而葉子 (Leaf) 就都是變數的標記 (Token)。

※語意分析(Semantic Analysis)：

1.定義：

藉由語法樹來分析程式的邏輯與語法是否符合規定。主要是為語法樹加註節點的資料型態，並且檢查資料型態是否相容，然後輸出語意樹。

2.範例：

語意分析器將會發現到 a 與 b 是無法相乘的，因而輸出錯誤訊息。

※參考資料：陳鍾誠-系統程式-第8章編譯器.ppt

※中間碼產生：語意樹→中間碼

1.使用時機：語意樹建立完成後，就可以將語意樹中的每個節點展開為中間碼。

2.方法：

利用遞迴的方式，從根節點開始，遞迴展開每個子節點，直到所有節點的中間碼都產生完畢為止。

3.範例：

※參考資料：陳鍾誠-系統程式-第8章編譯器.ppt

※指定述句的翻譯：

註：

01 LDF R2, id3

02 MULF R2, R2, #60.0

03 LDF R1, id2

04 ADDF R1, R1, R2

05 STF id1, R1

1.每個指令的第一個運算元指定了目的位址。各個指令中的 F 告知所它處理的是浮點數。

2.第一個指令：把程式碼把位址 id3 中的內容載入暫存器 R2。

3.第二個指令：把將其與浮點常數60.0相乘，“#”表示60.0應該視為直接常數。

4.第三個指令：把 id2 移到暫存器 R1。

5.第四個指令：把前面計算並存放在 R2 的值加到 R1。

6.第五個指令：把暫存器 R1 的值存放到 id1 的位址。

※參考資料：趙建華-編譯系統設計.pdf

※程式編譯器：

先用編譯再組譯。

※編譯(Compiler)：

將高階語言轉成組合語言。

※組譯(Assembling)：

將組合語言轉成機器語言。

※編譯器的步驟：

※參考資料：

http://www2.nuu.edu.tw/~elearning/nuuopencourse/93open/93004/html/contents.htm