Skip to content

week4 0309

Jump to bottom
Uriel58 edited this page Jun 11, 2022 · 3 revisions

八

編譯器

  • 將高階語言轉換成組合語言(或機器碼)的工具

C0語言

  • 代表C語言第0版的意思.就是小型的C語言。

  • 只包含for迴圈與基本計算

EBNF語法

  1. 星號代表重複零次以上

  2. 加號+代表重複一次以上

  3. 問號?代表重複0或1次

編譯器的六大階段

  1. 詞彙掃描(Scan或Lexical Analysis)

    • 將整個程式分成一個一個的基本詞彙(token)
    • 以正規表達式進行
      1. 整數
        • number = [0-9]+
      2. 名稱
        • id = [ A-Za-z_ ] [A-Za-z0-9_]

  2. 語法剖析(Parsing或Syntax Analysis)

    • 剖析器利用語法規則進行比對,以逐步建立語法樹
    • 剖析器
      • 由上而下的剖析法 (遞逗下降法、LL法)
      • 由下而上的剖析法(運算子優先矩陣法、LR法)

  3. 語意分析(Semantic Analysis)

    • 為語法樹加註節點型態,並檢查型態是否相容,然後輸出語意樹
    • 執行時機
      • 當語法樹建立完成後,緊接著通常會進行語意分析的動作。
    • 執行動作
      • 語意分析必須確定每個節點的型態,並且檢查這些型態是否可以相容,然後才輸出具有標記的語法樹,也就是語意樹。

  4. 中間碼產生(Pcode Generator)

    • 語意樹被轉換成中間碼

    • 演算法

      • 規則:STMT =id '=' EXP

      • 範例:sum=sum+i

        1. 呼叫 generate(exp):其中的exp為sum + i

        2. pcode 一行會產生=T0 sum

        3. 傳回T0作為sum=sum+i運算式的值

    • 使用時機

      • 一旦語意樹建立完成,我們就可以利用程式將樹中的每個節點,展開為中間碼

    • 方法

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

  5. 最佳化(Optimization)

    • 考慮暫存器的配置問題,降低指令數量,增加效率

  6. 組合語言產生(Assembly Code Generator)

    • 將中間碼轉換為組合語言輸出

組合語言產生

  • 時機

    • 一旦中間碼產生完畢,程式就可以輕易的將中間碼轉換成組合語言。

  • 方法

    • 將中間碼指令轉為組合語言指令
    • 必須考慮佔存器的載入與儲存

  • 範例:

    sum i T0

    ⇩

    LD R1 sum

    LD R2 i

    ADD R3 R1 R2

    ST R3 T0

指令的改寫

  • 對常數值的載入指令改寫為LDI

gcc編譯器

  • C語言→(剖析)→generic法樹→(產生)→gimple中間碼→(語意分析)RTL中間碼→(最佳化)→(組合語言產生)→組合語言
  • 高階語言→(掃描)→詞彙串列→(剖析)→語法樹→(語意分析)→語意樹→(中間碼產生)→中間碼→(組合語言產生)→組合語言→(組譯器)→目的檔「機器碼」

要求gcc譯器輸出rtl中間碼

  • 指令:加上-dr參數,可gcc輸出rtl中間碼

image

終端機輸入

  • gcc exp0var.c

  • ./a.out '(x+3)-y'

ASSIGN = id '=' E;

  • 判斷=就吃掉

指令 意義
OPEN open
READ read
CLOS close
PRTF printf
MALC malloc
FREE free
MSET memset
MCMP memcmp
指令 意義  
LEA load local address 載入區域變數
IMM load global addressor immediate 載入全域數或立即值
JMP jump 躍躍指令
JSR jump to subroutine 跳到副程式
BZ branch if zero if (a==0) goto m[pc]
BNZ branch if not zero if (a!=0) goto m[pc]
ENT enter subroutine 進入副程式
ADJ stack adjust 調整堆疊
LEV leave subroutine 離開副程式
LI load int 載入整數
LC load char 載入字元
SI store int 儲存整數
SC store char 儲存字元
PSH push 推入堆疊
OR a = a OR pop pop代表從中取出一個元素
XOR a = a XOR pop  
AND a = a AND pop  
EQ a = a EQ pop  
NE a = a NE pop  
LT a = a LT pop  
GT a = a GT pop  
LE a = a LE pop  
GE a = a GE pop  
SHL a = a SHL pop  
SHR a = a SHR pop  
ADD a = a ADD pop  
SUB a = a SUB pop  
MUL a = a MUL pop  
DIV a = a DIV pop  
MOD a = a MOD pop  
EXIT 終止離開
Clone this wiki locally