Sunday, April 13, 2008

Phases of a Compiler

先前曾經探討,像我們這種靠寫程式混吃的,最好備有兩把刷子,當發現其中一把刷子無法刷掉問題時,趕緊換上另一把刷刷看。通常一次只要用上一把,就可以把問題刷掉,偏偏有些問題比較棘手,要同時用上兩把刷子,左右開弓,才刷得乾淨!

這些要左右開弓的問題中,有個最典型的例子,那就是實作一個程式語言的編譯器(Compiler),它運作時恰好要經歷「分析」及「合成」兩個階段,這實在太妙了,所以我將它整理整理,簡述如下:

  • Analysis Phases
    • Linear Analysis
      • alias: scanning, lexical analysis
      • output: token stream
      • language: Regular Expression
    • Hierarchical Analysis
      • alias: parsing, syntax analysis
      • output: syntax tree
      • language: Context Free Grammar
    • Semantic Analysis
      • e.g. type checking
      • output: syntax tree
      • language:
        • Syntax Directed Definitions
          • 為每個 syntax production rule ,以 CFG 撰寫對應的 semantic rule
        • Translation Schemes
          • 將 semantic actions 嵌入既有的 syntax production rules 中
          • parser generator 常用的方法
  • Synthesis Phases
    • Intermediate Code Generation
      • built after the analysis phase
      • output: intermediate representation
        • e.g. three-address code
    • Machine-Independent Code Optimization
      • output: intermediate representation
    • Code Generation
      • output: target-machine code
    • Machine-Dependent Code Optimization
      • output: target-machine code
Tags: [] []

4 comments:

Wallace said...

Compiler的議題都沒有貼回覆,看來會的人不多。
我是電子出身的(含化學),軟體全部自學而來。老實說,第一次自學Compiler的書,真的就是天書。
後來找到自動機(Automata)的書,才開始了解Regular Expressions、Context-Free Grammars,再來才看得下Compiler的書。了解了之後才發現原來CPU及Compiler是出自於同一個理論,之後又發覺Automata已不再用,現在稱為Computer Theory。
剛好看懂時正在學FPGA,很快的就明瞭如何用FPGA做soft CPU。不過只有CPU是不能成大事,沒有Compiler根本做不了事。果然過了幾年,只剩下有C compiler的soft CPU才能存活。
至於我對Compiler的應用,仍停在Bison上玩。

Wallace said...

現代的FPGA開發,大多數人在處理狀態程序,會使用狀態機(State Machine)。我看了Automata後就在想,若是加入堆疊會做出人什麼樣的狀態機來。就理論來說,只不過多了指標暫存器及記憶體。不過好像可以實現Regular Expression的運算,這樣的系統在做資料比對應是很快。應該在串列通信上會很廣泛應用才是。

harlan said...

好熟悉的Context-Free Grammar.我大學時期曾經努力於寫一個簡單的數字型Compiler,類似計算機. 現在應該已經很少人會動手寫Compiler..

York said...

To harlan,

工作需要寫完整 Compiler 的機會不多,但要用到 Compiler 技術的機會則很多。

我就很常利用相關技術來作一些格式轉換,以達成自動化。例如 1) UI 描述檔和 C code 間的轉換 2) Verilog code 和 C code 間的轉換