4 系統程式 (System Program)

Software License

Software Licence Def licence Open source code Ex
Trial software 試用一段時間, 若欲長期使用需付費 Yes No ACDSee
Shareware 同上, 但限制較寬鬆 Yes No WinRAR
Freeware free Yes No IE, MSN
Public domain free No No X
Open software free No Yes Redhat, Open Office

Open Source Software

Def:

  • 指沒有 licence 限制, 可 free 使用, 且可拿到程式碼
  • 從 Open source 取得的程式, 修改後亦無 licence 所屬也為 Open source

System Program

Assembler (組譯器)

  • Def: 將組合語言轉成 object code (目的碼, 為機器可識別之程式), 以便系統執行之
  • 圖：

Linker/Loader (鏈結器/載入器) => linking loader

  • 欲將 object code 載入 memory 中, 過程需
    1. linking (連結): 將 object code 中的外部參考之宣告, 正式跟外部函式庫鏈結
    2. relocation (重定址): 將程式中參考位址依實際 memory 所在重新計算其實際的位址
    3. loading (載入): 正式將上述完成之 object code 載入 memory 中

Compiler (編譯器)

  • Def: 將高階語言 (c, c++) 轉成低階的 object code
  • 圖：
  • Compiler 過程：
    1. Lexical Analysis
    2. Syntax Analysis
    3. Semantic Analysis
    4. Intermediate Code Optimization
    5. Machine Dependent Code Generation and Optimization
    6. Generate the Object Code
      1.~ 4. => Machine Independent
      5.~ 6. => Machine Dependent
  • Lexical Analysis 語彙分析
    • Scan the program and find out the token (語彙單元)
      1. Terminal Symbol (終端符號) => keyword, 保留字
      2. Identifier (識別字) => 變數
      3. Liferal (常數) => 文, 數字
      • Ex: int(1) x(2) = (1) 20(3);(1)
    • 圖：
  • Syntax Analysis 語法分析
    • Def: 判別程式敘述是否合乎文法 (Grammer)
      • 合乎：建立出 parsing tree 或 syntax tree
      • 不合乎：output syntax tree
    • 圖：
    • 文法 (Grammer)
      • Note: 剖析工具: parser (剖析器)
      • Def: G = <N, T, P, S>
        • N: Non-terminal symbol set (非終端)
        • T: Terminal symbol set (終端)
        • P: Production rules (推衍規則)
        • S: Start symbol (S ∈ N) (起始)
      • Ex:
        G = <N, T, P, S>, N = {s, A, B}, T = {a, b},
        P = {S -> A|B; A -> aA|a; B -> bB|b;} (-> 為推衍符號),
        S = s ∈ N (S 為起始符號, s 為起始符號的名稱), 問 abaa, aaa 是否合乎文法？
        Sol:
        1. S -> A -> aA -> 此無法推出 b, 故不合乎文法
        2. S -> A -> aA -> aaA -> aaa, 可推論出, 故合乎文法
    • Parsing tree 剖析樹
      • Def: 剖析文法敘述所建立之樹
      • 作法:
        • N 必為 Tree 中的非終端節點 (degree ≥ 1)
        • T 必為 Tree 中的終端節點 (degree = 0)
      • Ex:
        G = <N, T, P, S>, N = {E, T, F}, T = {+, -, *, /, id (,)},
        P = {E -> E+T|E-T|T; T -> T*F|T/F|F; F -> id|(E);}, S = E ∈ N,
        問
        1. id + id * id 合法建立剖析樹
        2. id * (id - id / id)?
        • Note: 括號 “()”, 不可以被分割於 2 不同區塊之中
          Sol:
    • Syntax tree 語法樹
      • 目的：
        • 簡化剖析樹
        • 只保留 Terminal symbol
        • 利用中序追蹤可還原運算式
      • Note: 括號不需考慮 (因為已有 priority 之考量)
    • 文法種類
      Note Type 別名 自動機
      自由度最大 0 Unrestricted (不受限) grammer (AI) Turing Machine (杜林機)
      如變數的宣告 1 Context-sensitive (上下文相關) grammer
      高階語法 2 Context-free (上下文無關) grammer
      3 Regular grammer
  • Semantic Analysis 語意分析
    • 目的：依剖析結果, 呼叫對應的 semantic routine 或 action routine 以產生 intermediate code (中間碼) (類似目的碼一樣由 0, 1 組成, 但和機器獨立謂之)
    • 圖：
  • Intermediate Code Optimization 中間碼最佳化
    • 目的：
      1. 精簡中間碼
      2. 所佔用 space 下降
      3. 效益提高
    • 常用技巧：
      1. 刪除共通運算式
        A = B + C * D + 2
        F = 5 + (B + C + D) / 3
        令 B, C, D 皆不變
        α = B + C * D
      2. 先求出常數運算
        Ex: A = 3.14 * 2.56 / 3.2 + 8 - E
        求 α = 3.14 * 2.56 / 3.2 + 8
      3. 布林運算式最佳化
        • Ex1: if (A and B), A B 皆為 Condition (條件式)
          若 A = false, B 不做 => 結果必為 false
        • Ex2: if (A or B), 若 A = true, B 不做 => 結果必為 True
        • Note: 此概念為：
          • 短路：short-circuit
          • 又稱 “捷徑運算”
  • 程式中常見的 error

Interpreter (直譯器)

  • Def:
    • 不事先將 source code 轉成 object code
    • 直接拿 source code 執行, 依原始程式 logical 順序進行
    • 執行期間 interpreter 須留在 memory 之中
  • 圖：

Compare Compiler vs Interpreter

Compiler Interpreter
執行不需於 memory 中 需要
會事先產生 object code (有最佳化, 故效益佳) 不會, 直接依 logical 執行, 產生結果
全部 scan, 故比較沒有漏洞 較易有漏洞
修改 => recompile (彈性差) 不需 recompile (彈性佳)
開發時期較不適用 適用
找 bug 較不易 較易找到 bug 所在
初學者較不易 初學者較易上手

Macro 巨集

  • Def: 開放式副程式 (Open subroutine)
    將一連串的指令定義為巨集指令, 當 source code 轉換時, 遇到巨集呼叫, 就將對應的連串指令插入於呼叫處
  • 圖：
  • 特性：
    1. 巨集呼叫於程式轉換期間, 而非 runtime
    2. 呼叫 Ｎ 次, 需插入巨集本文 N 次 => 浪費空間
    3. 執行階段, 不需做控制移轉 => 快
    4. 多此使用一單獨定義的常式 (定義一次, 可使用多次)

Subroutine 副程式 => 又稱 close subroutine

  • Def: 於執行中, 當 subroutine 被呼叫才動態的去呼叫之, 並將資料及控制權移轉給他, 待完成, 再移轉回來
  • 優點：只佔用一份 memory => 省 space
  • 缺點：需做控制權移轉 => speed 下降

Compare Macro vs Subroutine

MACRO Subroutine
Speed 快 Speed 慢
以空間換時間 以時間換空間
space 浪費 space 省

Summary