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

第一章 程式語言導論

1-1程式語言基本概念

一、定義

程式 = 演算法+資料結構

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

※Turing Machine：

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

96交員晉高、104地三

使用一個無限長的磁帶當作記憶體，磁帶頭有讀與寫的功能，而且可以在磁帶上左右移動。Turing Machine工作的情況就好像無法記得那麼長的資料，但是可以前後瀏覽，作記號並且比對。

※參考資料：http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/05ct/chp08.pdf

二、程式語言的分類

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

93專檢、103檢三、104高三

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

是由0與1組成的二進位碼所構成，不同類型的計算機擁有不同的指令群，對應的二進位碼亦不相同，因此是一種與機器相關的語言。撰寫及維護都極為困難。例如麥金塔電腦與 IBM 個人電腦的機器語言不相容。

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

又稱為低階語言 (low-level language)。將每一條機器語言指令用一個助記憶符號 (memonic symbol) 來取代。組合語言指令與機器語言指令具有一對一的對應關係，因此屬於與機器相關的語言。

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

又稱為程序導向語言 (procedure oriented language)，告訴電腦如何做。與機器無關，具有移植性，不須要因為電腦設備的不同而修改大量程式指令。例如 Pascal、C、C++、Basic、Fortran 與 Cobol。

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

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

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

利用人工智慧技術，使其接近人類使用的自然語言 (如英語)，讓電腦讀懂人類的語言。目前人工智慧語言仍處於發展中的階段，現今開發的產品則多是以 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年檢察事務官三等程式語言

答：

略

104年高考三級程式語言

答：

1-2 高階程式語言

一、高階語言的優點

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

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

(三)與機器無關

(四)程式的除錯較容易

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

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

二、高階語言的實作

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

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

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

1.定義：是一種系統程式，將高階語言的原始碼轉換成機器語言程式 (目的程式)。

2.編譯的作法：

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

3.編譯的流程：

※參考資料：

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

※語彙分析(Lexical Analysis)：

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

※語法分析(Syntax Analysis)：

將程式符號轉換成階層式的語法樹 (Syntax Tree) 符號。在語法樹中，階層最高的節點 (Node) 為 assign 的符號，其餘的節點為其他的運算元符號，而葉子 (Leaf) 就都是變數的標記 (Token)。

※語意分析(Semantic Analysis)：

1.定義：

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

2.範例：

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

※LR parser：

104地三

是一種由下而上 (bottom-up) 的上下文無關語法剖析器。LR 意指由左至右處理輸入字串，並以最右邊優先衍生 (Right derivation) 的推導順序建構語法樹。由於 LR 剖析器 (LR parser) 由剖析樹的葉節點開始，然後透過文法規則逐步向上層化簡，最後化簡到樹的根部 (起始符號)，所以是一種由下而上的剖析方法。

※參考資料：

https://zh.wikipedia.org/wiki/LR%E5%89%96%E6%9E%90%E5%99%A8

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

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

2.方法：

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

3.範例：

※指定述句的翻譯：

<圖3>pic3

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

※程式編譯器：

先用編譯再組譯。

※編譯(Compiler)：

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

※組譯(Assembling)：

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

※編譯器的步驟：

※參考資料：

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

※程式編譯器的過程：

Dev-C++ 主要工作為預先處理 (Preprocess)、編譯 (Compile) 和組譯(Assemble)。預先處理是做一些在編譯前要做的工作，之後就進行編譯。在編譯過程中，會檢查程式有沒有錯誤，而錯誤主要有語法錯誤 (Syntax Error) 和語義錯誤 (Semantic Error) 兩類。如果有上述錯誤，編譯器會通知，而且停止編譯過程，這時候要修正程式內的錯誤，修改後重新開始編譯。當沒有任何錯誤後，編譯器會把程式內每個句子轉成更低階的方式，一般是轉成組合語言 (Assembly)。轉成組合語言後，組譯時 (通常編譯器都內置了組譯器) 就會把每個組合語言句子轉成機械語言 (Machine Code)，也稱為目的碼 (Object Code)，產生另一個檔案 “file.obj”。最後到了連結 (Link) 過程，就會把程式、有關的程式和程式庫所產生出來的 *.lib，轉成可以在電腦上執行的方式，產生另一個檔 “file.exe”，這個檔案就可以執行了。

※參考資料：http://www2.lssh.tp.edu.tw/~hlf/class-1/lang-c/compile.htm

※預先處理(Preprocess)：

1.#define巨集的宣告與使用：

巨集指令 #define 宣告的格式如下

#define macroname string

假設有一 C 程式檔 file.c 其內容為：

  #define MAXSIZE 100

  main( ) {

      int A[MAXSIZE];

}

於編譯時經過前置處理後，該程式變成

  main( ) {

int A[100];

}

其中所有的 #define 指令都不見了，MAXSIZE 也都變成了100。

2.#include的使用：

C 程式的設計，不僅可以用模組化的方式，以函數來表現，亦可將程式碼依其不同的目的與功能，呈現在不同的檔案中。為了程式碼的一致性，例如常數、巨集指令和全域 (global) 變數宣告一些函數 (僅列出函數的標題 heading) 等，都放在一檔頭檔 .h，當然不見的是要以 .h 當作副檔名，不過，一般都是以 .h 來當作 include 檔的副檔名，再以指令 #include 方式將該檔 加入即可。指令 #include 的宣告方式如下：

#include <filename>

或

#include "filename"

經過編譯器前置處理後，含指令 #include 這行則由該檔 filename 來代替，如果 filename 是由 < > 所含，則編譯器會到 include 目錄下去找該檔或至預設的目錄去找。" " 常用來引用自定義的頭文件。

假設檔案 file1.h 的內容如下：

#define MAXSIZE 100

  extern int size;

  int f(int x);

假設檔案 file2.c 的內容如下：

#include "file1.h"

main( ) {

int A[MAXSIZE], i, sum;

for(i = 0; i < size; i++)

          sum = sum+f(i);

}

假設 file1.h 與 file2.c 都在同一目錄，經過前置處理，file2.c 就先變成：

  #define MAXSIZE 100

  extern int size;

  int f(int x);

  main( ) {

int A[MAXSIZE], i, sum;

      for(i = 0; i < size; i++)

          sum = sum+f(i);

}

經過前置處理完成後，file2.c 就變成：

extern int size;

int f(int x);

main( ) {

int A[100], i, sum;

for(i = 0;i < size; i++)

sum = sum+f(x);

}

3.#if、#ifdef等的使用：

如果在一檔案欲 include 一檔頭檔 file1.h，又想避免在同一檔案宣告兩次相同的東西，例如：

檔案 file1.h 含 extern int size

檔案 file2.h 含 #include "file1.h"

檔案 file3.h 含 #include "file1.h"

檔案 file.c 含 #include "file2.h" 及 #include "file3.h"

則在檔案 file.c 內，變數 size 重複宣告了兩次而產生錯誤。

欲避免這種情況發生，每個 #include "file1.h" 指令，可以改變為如下指令：

  #if !define(FILE1) // 如果沒有定義一個 file1.h 標頭檔，就執行底下所有操作

  #define FILE1 "file1.h" // 定義一個符號

  #include FILE1// 在程序中包含頭文件

  #endif // 結束

或是

  #ifndef FILE1

  #define FILE1 "file1.h"

  #include FILE1

  #endif

如果一個辨識名稱 X 沒有被 define 過，則 define(X) 的值為0，或者 ifndef X 為真值。當 file2.h 與 file3.h 都含上述指令，如此一來 file1.h 僅能一次被加入 file.c 而不致於產生衝突。

※參考資料：http://nknucc.nknu.edu.tw/~jwu/c/cpgch8.htm#third

※C語言前置處理器：

1.定義：

是一種特殊的文字編輯器，語法和 C 語言完全不同，能處理常數、巨集及 include 檔。可以條件式編譯，例如要在測試時將除錯用的程式碼放進來，然後在正式發行時予以刪除。如下：

2.原理：

(1)前置處理程式將原始檔中的 # 開頭的指令全部轉換為 C 指令。例如 #include <stdio.h>，將 stdio.h 內容展開。

(2)編譯程式將純 C 檔案轉為對應的機器語言 (目的檔案)。

(3)連結程式將所用到的 C 函數由函式庫連結到目的檔案後形成執行檔。

(4)執行檔 .exe 才是真正可執行的檔案。

(二)直譯程式(interpretation)

1.定義：

是一種系統程式，按照高階語言所寫的原始程式執行時敘述的邏輯順序，逐一將指令轉換為機器語言並且執行它。直譯器不會一次把整個程式轉譯出來，只像一位「中間人」，每次執行程式時都要先轉成另一種語言再作執行，因此直譯器的程式運行速度比較緩慢。每轉譯一行程式敘述就立刻執行，然後再轉譯下一行，再執行，如此不停地進行下去。可以使用語彙分析器 (lexical analyzer) 和語法分析器 (parser)，然後轉譯產生出來的抽象語法樹 (abstract syntax tree)。

2.直譯的作法：原始程式→直譯程式 (原始程式轉成機器語言)→執行結果。

※參考資料：

http://zh.wikipedia.org/wiki/%E7%9B%B4%E8%AD%AF%E5%99%A8

※編譯程式與直譯程式的差異：

※編譯程式與直譯程式的優缺點：