編譯原理王生原第二章

1、編譯原理第二講第二講 Decaf / Mind 編譯實驗項目編譯實驗項目編譯原理 項目框架的總體結(jié)構(gòu)項目框架的總體結(jié)構(gòu) 實驗環(huán)境實驗環(huán)境 實驗內(nèi)容實驗內(nèi)容Decaf / Mind 編譯實驗項目編譯實驗項目 實驗安排實驗安排 項目回顧項目回顧 考核方案考核方案編譯原理項目回顧項目回顧 Decaf 語言語言- 一種強類型的、單繼承的一種強類型的、單繼承的簡單面向?qū)ο笳Z言簡單面向?qū)ο笳Z言- 許多大學用作許多大學用作教學語言教學語言 Stanford University Massachusetts Institute of Technology University of Tennessee Bro

2、wn University Texas A&M University Southern Adventist University 編譯原理項目回顧項目回顧 清華清華 Decaf / Mind 項目項目- 始于計算機系始于計算機系98級本科生級本科生編譯原理編譯原理課課- 基于基于 Stanford University 課程課程 CS143 /class/cs143/- 根據(jù)實際需要進行了一定的根據(jù)實際需要進行了一定的修改和簡化修改和簡化 如：適應如：適應 Windows 平臺平臺 增加目標代碼在增加目標代碼在 X86 上的執(zhí)行上的執(zhí)行 02

3、 級的級的 TOOL 項目項目- 03 級之后經(jīng)歷了級之后經(jīng)歷了3 3 次較大改動次較大改動編譯原理項目回顧項目回顧 清華清華 Decaf / Mind 項目項目- 03-04 級級 Decaf 項目項目 實驗框架中開發(fā)語言由實驗框架中開發(fā)語言由 C+ 改為改為 Java- 計計 50 班班 Mind 項目項目 實驗框架由原來的單遍組織改為實驗框架由原來的單遍組織改為多遍組織多遍組織 開發(fā)語言為開發(fā)語言為 C+C+，Decaf 語言有所精簡（語言有所精簡（Mind語言）語言） - 05 級至今級至今 Decaf / Mind 項目項目 以以 Mind 項目為基礎，開發(fā)語言由項目為基礎，開發(fā)語言

4、由 C+ 改為改為 Java編譯原理項目回顧項目回顧 清華清華 Decaf / Mind 項目項目- 參與項目開發(fā)的部分同學參與項目開發(fā)的部分同學 楊俊峰（楊俊峰（Stanford 助教）助教） 張迎輝（計張迎輝（計99-99-計計0000助教）助教） 毛雁華（計毛雁華（計00-00-計計0101助教，助教，X86后端）后端） 劉天淼（計劉天淼（計0101助教，助教，Windows環(huán)境）環(huán)境） 唐唐 碩（計碩（計0202助教，助教，TOOL） 梁英毅（計梁英毅（計03-03-計計0505助教，助教，Java 版，版，Mind，RA） 張張 鐸（計鐸（計05-05-計計0707助教，改助教，改

5、Mind 至至 Java 版）版） 蔣蔣 波（參與波（參與 Decaf 語言規(guī)范的翻譯語言規(guī)范的翻譯 ） （還有許多同學沒有一一列舉）（還有許多同學沒有一一列舉）編譯原理項目框架的總體結(jié)構(gòu)項目框架的總體結(jié)構(gòu) 當前項目中編譯器的邏輯結(jié)構(gòu)當前項目中編譯器的邏輯結(jié)構(gòu)編譯原理 當前項目中編譯器的邏輯結(jié)構(gòu)當前項目中編譯器的邏輯結(jié)構(gòu)項目框架的總體結(jié)構(gòu)項目框架的總體結(jié)構(gòu)編譯原理實驗內(nèi)容實驗內(nèi)容 四個階段四個階段編譯原理實驗內(nèi)容實驗內(nèi)容 四個階段四個階段- Phase 1Phase 1 詞法和語法分析詞法和語法分析 借助借助 Lex 和和 Yacc 實現(xiàn)詞法和語法分析實現(xiàn)詞法和語法分析 一遍掃描后產(chǎn)生一種高級

6、中間表示一遍掃描后產(chǎn)生一種高級中間表示 （實驗指定的抽象語法樹（實驗指定的抽象語法樹 AST）- Phase 2 Phase 2 語義分析語義分析 遍歷抽象語法樹構(gòu)造符號表、實現(xiàn)靜態(tài)語遍歷抽象語法樹構(gòu)造符號表、實現(xiàn)靜態(tài)語 義分析，產(chǎn)生帶標注的抽象語法樹義分析，產(chǎn)生帶標注的抽象語法樹 - Phase 3 Phase 3 生成生成三地址碼三地址碼 TAC- Phase 4 Phase 4 基于基于 TAC 實現(xiàn)一些簡單的數(shù)據(jù)流分析實現(xiàn)一些簡單的數(shù)據(jù)流分析編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 1Phase 1- 借助借助 Lex 和和 Yacc 實現(xiàn)詞法和語法分析實現(xiàn)詞法和語法分析生成一種高級中間表

7、示（抽象語法樹生成一種高級中間表示（抽象語法樹 ASTAST）編譯原理實驗內(nèi)容實驗內(nèi)容生成一種高級中間表示（抽象語法樹生成一種高級中間表示（抽象語法樹 ASTAST） Phase 1Phase 1- 借助借助 Lex 和和 Yacc 實現(xiàn)詞法和語法分析實現(xiàn)詞法和語法分析編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 1Phase 1- 借助借助 Lex 和和 Yacc 實現(xiàn)詞法和語法分析實現(xiàn)詞法和語法分析定義定義 Decaf Decaf 語法的一個語法的一個可能的上下可能的上下文無關(guān)文法文無關(guān)文法GProgram GProgram （片斷）（片斷） 編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 1Phase 1

8、- 借助借助 Lex 和和 Yacc 實現(xiàn)詞法和語法分析實現(xiàn)詞法和語法分析比較比較: :語法分析結(jié)果語法分析結(jié)果（具體語法樹（具體語法樹 CSTCST）生成一種高級中間表示生成一種高級中間表示（抽象語法樹（抽象語法樹 ASTAST）編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 2Phase 2- 遍歷遍歷 AST 構(gòu)造符號表、實現(xiàn)靜態(tài)語義分析構(gòu)造符號表、實現(xiàn)靜態(tài)語義分析編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 2Phase 2- 遍歷遍歷 AST 構(gòu)造符號表、實現(xiàn)靜態(tài)語義分析構(gòu)造符號表、實現(xiàn)靜態(tài)語義分析編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 2Phase 2- 遍歷遍歷 AST 構(gòu)造符號表、實現(xiàn)靜態(tài)語義分析

9、構(gòu)造符號表、實現(xiàn)靜態(tài)語義分析編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 3Phase 3 - 由由帶標注的帶標注的 AST 生成生成三地址碼三地址碼 TAC 編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 3Phase 3 - 由由帶標注的帶標注的 AST 生成生成三地址碼三地址碼 TAC 每個每個 class 對對應一個應一個 vtable編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 3Phase 3 - 由由帶標注的帶標注的 AST 生成生成三地址碼三地址碼 TAC 編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 3Phase 3 - 由由帶標注的帶標注的 AST 生成生成三地址碼三地址碼 TAC 編譯原理實驗內(nèi)容實驗內(nèi)容

10、 Phase 3Phase 3 - 由由帶標注的帶標注的 AST 生成生成三地址碼三地址碼 TAC 編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 4Phase 4- 基于基于 TAC 實現(xiàn)簡單的數(shù)據(jù)流分析實現(xiàn)簡單的數(shù)據(jù)流分析劃分基本塊以及活躍變量數(shù)據(jù)流分析劃分基本塊以及活躍變量數(shù)據(jù)流分析編譯原理實驗內(nèi)容實驗內(nèi)容 Phase 5 Phase 5 （不在課程計劃內(nèi)）（不在課程計劃內(nèi)）- 由由 TAC 生成生成 MIPS 匯編代碼匯編代碼可選的工作如指可選的工作如指令選擇和寄存器令選擇和寄存器分配算法的改進分配算法的改進以及其它類優(yōu)化以及其它類優(yōu)化編譯原理實驗內(nèi)容實驗內(nèi)容 關(guān)于自行擴展實驗關(guān)于自行擴展實驗-

11、 完成完成 Phase 1-4 Phase 1-4 之后之后 2 周內(nèi)提交周內(nèi)提交 需要同時提交詳細的設計和測試文檔需要同時提交詳細的設計和測試文檔- 在已有實驗框架基礎上有意義的改進工作在已有實驗框架基礎上有意義的改進工作 函數(shù)式風格語句的實現(xiàn)函數(shù)式風格語句的實現(xiàn) 例外處理支持例外處理支持 垃圾回收機制垃圾回收機制 新的代碼生成機制新的代碼生成機制( (必要時增加新的低級表示必要時增加新的低級表示) ) 實現(xiàn)有意義的優(yōu)化算法實現(xiàn)有意義的優(yōu)化算法( (必要時增加新的中間表示必要時增加新的中間表示) ) 編譯原理實驗環(huán)境實驗環(huán)境 編程環(huán)境和相關(guān)工具編程環(huán)境和相關(guān)工具 Lex & YACC

12、 簡介簡介編譯原理編程環(huán)境和相關(guān)工具編程環(huán)境和相關(guān)工具 編程語言編程語言- Java ( (版本和操作系統(tǒng)信息參見實驗說明版本和操作系統(tǒng)信息參見實驗說明) ) Lex & YACC 工具工具- Jflex http:/jflex.de/- BYACC/J http:/ 其他輔助工具其他輔助工具- MIPS SPIM ( (Wisconsin大學大學 ) ) /larus/spim.html- Eclipse / 編譯原理 Lex 與與 YACC 工具工具Lex & YACC 簡介簡介編譯原理

13、 Lex 源程序式樣源程序式樣 % 定義節(jié)定義節(jié) /* 可選，包含頭文件、宏定義或全局可選，包含頭文件、宏定義或全局 C 代碼代碼*/ % 輔助定義節(jié)輔助定義節(jié) / /* *可選，在此可以為正規(guī)式定義宏名字可選，在此可以為正規(guī)式定義宏名字* */ / % 規(guī)則節(jié)規(guī)則節(jié) /* 源程序的主體，不可或缺，由模式源程序的主體，不可或缺，由模式 （Lex 正規(guī)表達式）和動作（正規(guī)表達式）和動作（ C 語句或語句或 一段一段 C 程序）組成程序）組成 */ % C 語言用戶子程序節(jié)語言用戶子程序節(jié) /* 可選，包含規(guī)則節(jié)用到的可選，包含規(guī)則節(jié)用到的 局部局部 C 函數(shù)函數(shù)*/Lex & YACC

14、簡介簡介編譯原理%#include int num_lines = 0, num_chars = 0;%n +num_lines; +num_chars;. +num_chars;%Int main() yylex(); printf( “num of lines = %d, num of chars = %dn, num_lines, num_chars ); return 0; Lex 源程序舉例源程序舉例 count.l Lex & YACC 簡介簡介編譯原理$ lex count.l$ gcc -o count lex.yy.c -ll /*對于 flex 用-lfl */$

15、./count count.l $ count.l build runLex & YACC 簡介簡介編譯原理Lex 可單獨作為文本處理工具來使用，例如可單獨作為文本處理工具來使用，例如 toupper.l 源程序源程序 % #include % % a-z Printf(%c,yytext0+A-a) %Build & Run $ lex toupper.l $ gcc -o toupper lex.yy.c -ll $ ./toupper count.l Lex 源程序舉例源程序舉例 toupper.l Lex & YACC 簡介簡介編譯原理和和 YACC 聯(lián)用時的聯(lián)

16、用時的Lex 源程序源程序 例例 exp.l % #include “y.tab.h” % % 0| 1-90-9 * yylval = atoi(yytext); return INTEGER; +*()n return yytext0; . /*do nothing*/ % Lex 源程序舉例源程序舉例Lex & YACC 簡介簡介編譯原理- YACC 源程序式樣源程序式樣 % 聲明節(jié)聲明節(jié) / /* * 將被原樣拷貝將被原樣拷貝, ,可選可選* */ / % 輔助定義節(jié)輔助定義節(jié) /* 定義文法相關(guān)的名稱和屬性定義文法相關(guān)的名稱和屬性,可選可選*/ % 語法規(guī)則節(jié)語法規(guī)則節(jié) /*

17、 定義語法規(guī)則及語義動作定義語法規(guī)則及語義動作. Yacc中的產(chǎn)生式中的產(chǎn)生式 格式為格式為 非終結(jié)符非終結(jié)符: 右端右端 C語句表示的語義動作語句表示的語義動作 */ % 支撐函數(shù)節(jié)支撐函數(shù)節(jié) /* 規(guī)則節(jié)用到的局部規(guī)則節(jié)用到的局部 C 函數(shù)定義函數(shù)定義, 可選可選*/ YACC (Yet Another Compiler-Compiler)Lex & YACC 簡介簡介編譯原理 YACC 源程序舉例源程序舉例 exp.y/* 用用YACC實現(xiàn)的一個簡單的計算器實現(xiàn)的一個簡單的計算器 */% #include % /* 終結(jié)符終結(jié)符 */%token INTEGER/* 優(yōu)先級和結(jié)合

18、性優(yōu)先級和結(jié)合性 */%left +%left *Lex & YACC 簡介簡介編譯原理 YACC 源程序舉例源程序舉例 （續(xù)）（續(xù)）% input: /* empty string */ | input line ;line: n | exp n printf (t%dn, $1); | error n ;exp: INTEGER $ = $1; | exp + exp $ = $1 + $3; | exp * exp $ = $1 * $3; | ( exp ) $ = $2; ;%Lex & YACC 簡介簡介編譯原理/* 用戶子程序用戶子程序 */main () yyp

19、arse (); int yylex() /* 自行編寫或從自行編寫或從 Lex 得到得到, 隨后介紹隨后介紹 Lex和和YACC 的聯(lián)用，需刪去這里的的聯(lián)用，需刪去這里的 yylex()定義定義 */yyerror (char *s) printf (%sn, s); YACC 源程序舉例源程序舉例 （續(xù)）（續(xù)）Lex & YACC 簡介簡介編譯原理- 設設 exp.l 和和exp.y 分別為前述的分別為前述的Lex 和和YACC 源程序文件源程序文件 可如下實現(xiàn)可如下實現(xiàn)Lex 和和YACC的聯(lián)編：的聯(lián)編： lex exp.l /* 產(chǎn)生產(chǎn)生lex.yy.c，其中包含，其中包含 yylex() */ yacc -d exp.y /* 產(chǎn)生產(chǎn)生y.tab.c （其中