先前曾經探討，像我們這種靠寫程式混吃的，最好備有兩把刷子，當發現其中一把刷子無法刷掉問題時，趕緊換上另一把刷刷看。通常一次只要用上一把，就可以把問題刷掉，偏偏有些問題比較棘手，要同時用上兩把刷子，左右開弓，才刷得乾淨！
這些要左右開弓的問題中，有個最典型的例子，那就是實作一個程式語言的編譯器（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
4 comments:
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上玩。
現代的FPGA開發，大多數人在處理狀態程序，會使用狀態機(State Machine)。我看了Automata後就在想，若是加入堆疊會做出人什麼樣的狀態機來。就理論來說，只不過多了指標暫存器及記憶體。不過好像可以實現Regular Expression的運算，這樣的系統在做資料比對應是很快。應該在串列通信上會很廣泛應用才是。
好熟悉的Context-Free Grammar.我大學時期曾經努力於寫一個簡單的數字型Compiler,類似計算機. 現在應該已經很少人會動手寫Compiler..
To harlan,
工作需要寫完整 Compiler 的機會不多，但要用到 Compiler 技術的機會則很多。
我就很常利用相關技術來作一些格式轉換，以達成自動化。例如 1) UI 描述檔和 C code 間的轉換 2) Verilog code 和 C code 間的轉換
Post a Comment