第一章 程式語言導論
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年專門職業及技術人員檢覈程式語言
|
四、我們通常將程式語言分為五代。 (一)請問第一代程式語言所指為何？（5分） (二)第二代程式語言一般指的是「高階語言」，又稱為「程序導向語言」，請說明程序導向語言解決問題的方式為何？（5分） (三)第四代程式語言一般指的是「問題導向語言」(problem oriented language)，例如 SQL，請說明 SQL 解決問題的方式為何？（5分） (四)第五代程式語言一般指的是「自然語言」(nature language)，又稱為「知識庫語言」，請說明此類語言解決問題的方式為何？（5分） |
答：
略
103年檢察事務官三等程式語言
|
一、何謂程式語言 (programming language)？又有那些分類？（17分） |
答：
略
104年高考三級程式語言
|
一、請就解譯方式 (組譯、直譯、編譯)、程式結構 (程序導向、物件導向)、標記文字 (是、否) 等特性，分類說明程式語言 C, CSS, C#, HTML, Java, PHP, Python, SQL 的特性。請繪製表格作答。（25分） |
答：
|
|
解譯方式 |
程式結構 |
標記文字 |
|
C |
編譯 |
程序導向 |
否 |
|
CSS |
直譯 |
非程序導向 (宣告方式) |
是 (樣式可以嵌入於 HTML 文件中) |
|
C# |
編譯 |
物件導向 |
否 |
|
HTML |
直譯 |
非程序導向 (超文件標記語言) |
是 |
|
Java |
編譯 (編譯後再直譯) |
物件導向 |
否 |
|
PHP |
直譯 |
物件導向 |
是 (程式碼必須在<?php ?> 標籤中) |
|
Python |
直譯 |
物件導向 |
否 |
|
SQL |
直譯 |
非程序導向 (查詢語言) |
否 |
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 是無法相乘的，因而輸出錯誤訊息。
|
C語言程式 |
語義分析的結果 |
|
int a = 5, c; char b[10]; c = a*b; |
a, c 是整數 b 是字元陣列 c (錯誤？) = 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.範例：
|
C語言程式 |
中間碼 |
說明 |
|
sum = 0; for(i = 1; i <= 10; i++) { sum = sum+i; } return sum; |
= 0 sum = 1 i FOR0: CMP i 10 J > _FOR0 + sum i T0 = T0 sum + i 1 i J FOR0 _FOR0: RET sum |
設定 sum 為0 設定 i 為1 for 迴圈的起始點 i >=< 10 ? if (i>10) goto FOR1 T0 = sum+i sum = T0 i = i+1
傳回 sum |
※指定述句的翻譯：
<圖3>pic3
※參考資料：趙建華-編譯系統設計.pdf
※程式編譯器：
先用編譯再組譯。
※編譯(Compiler)：
將高階語言轉成組合語言。
※組譯(Assembling)：
將組合語言轉成機器語言。
※編譯器的步驟：
|
步驟 |
內容 |
|
1.詞彙分析(Lexical Analysis) |
將整個程式分成一個一個的基本詞彙 (token) |
|
2.語法分析(Parsing或Syntax Analysis) |
剖析器利用語法規則進行比對，建立語法剖析樹 |
|
3.語意分析(Semantic Analysis) |
為剖析樹加註節點型態，並檢查型態相容性，輸出語意樹 |
|
4.中間碼產生(Pcode Generator) |
將語意樹轉換成中間碼 |
|
5.最佳化(Optimization) |
考慮暫存器配置問題，降低指令數量，增加效率 |
|
6.組合語言產生(Assembly Code Generator) |
將中間碼轉換為組合語言輸出 |
|
7.編譯組譯(Compilation Assembly) |
將中間碼碼產生的組合語言轉換成機器語言及載入程式所需的資訊 |
※參考資料：
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 檔。可以條件式編譯，例如要在測試時將除錯用的程式碼放進來，然後在正式發行時予以刪除。如下：
|
#include < stdio.h > #define value 99 void main(void) { #if value < 100 printf("value < 100"); #else printf("value >= 100"); #endif } |
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
※編譯程式與直譯程式的差異：
|
|
編譯程式 |
直譯程式 |
|
原始程式的處理方式 |
產生目的程式 (機器語言) 卻不執行，可以透過連結過程產生執行檔 |
按照輸入程式執行時敘述的邏輯順序逐一地分析解碼並且執行 |
|
敘述的處理順序 |
依照程式實體上敘述的輸入順序進行處理 (撰寫順序) |
依照程式執行時敘述的邏輯順序進行處理 |
|
敘述的處理次數 |
程式中每個敘述都只處理一次 |
依照執行時敘述的邏輯順序進行處理，可能發生某些敘述被重複處理許多次 (迴圈)，而某些敘述沒有被處理 (當錯誤發生時才執行的程式片斷可能不會被執行) |
※編譯程式與直譯程式的優缺點：
|
|
優點 |
缺點 |
留言列表
國考資訊處理解答 (7)
