編譯原理：實(shí)驗(yàn)介紹-編譯原理

TINY語言及其編譯器的實(shí)現(xiàn)1TINY語言及其編譯器概述[more]2TINY語言詞法分析器的實(shí)現(xiàn)[more]3TINY語言的語法定義[more]4TINY語言的遞歸下降語法分析器的構(gòu)造[more]5TINY語言的語義分析器[more]6TINY語言的運(yùn)行時(shí)環(huán)境[more]7TINY語言的代碼生成器的構(gòu)造[more]1TINY語言及其編譯器概述TINY編譯器TINY語言編譯器的構(gòu)造直觀的展示了如何將各章的理論技術(shù)組合在一起，以構(gòu)造一個(gè)完整的編譯器用實(shí)驗(yàn)語言TINY作為源語言用TM（為TINY語言構(gòu)造的虛擬機(jī)的匯編語言）作為目標(biāo)語言TINY編譯器用C語言構(gòu)造要為一個(gè)具體的語言構(gòu)造編譯器，必須：熟悉源語言（詞法、語法、語義規(guī)定）熟悉目標(biāo)語言（尋址方式，寄存器個(gè)數(shù)，數(shù)據(jù)表示等）確定編譯器的結(jié)構(gòu)1.1TINY語言的定義TINY語言程序是用分號(hào)分隔的語句序列聲明 沒有過程定義以及聲明數(shù)據(jù)類型 所有的變量都是整型變量，為變量賦值就認(rèn)為已聲明了該變量語句 兩種控制語句：if語句和repeat語句；賦值語句，read和write語句表達(dá)式 布爾表達(dá)式（用<，=）以及整型算術(shù)表達(dá)式（+，-，*，/，括號(hào)，常量，變量）。布爾表達(dá)式只用在控制語句中作為條件判斷注釋 注釋的內(nèi)容被放在花括號(hào){}中，注釋不允許嵌套定義{sampleprograminTINYlanguage-computesfactorial}readx;{inputaninteger}if0<xthen{don’tcomputeifx<=0} fact:=1; repeat fact:=fact*x; x:=x-1 untilx=0; writefact{outputfactorialofx}endTINY示例程序1.2TINY的編譯器TINY編譯器的組成包括如下部分：詞法分析器，語法分析器，語義分析器，代碼生成器，以及一個(gè)符號(hào)表不包括以下部分： 優(yōu)化階段，單獨(dú)的錯(cuò)誤處理程序和常量表TINY編譯器的結(jié)構(gòu) 四遍編譯器第一遍進(jìn)行詞法分析和語法分析，構(gòu)造語法樹；第二遍和第三遍進(jìn)行語義分析第二遍構(gòu)造符號(hào)表第三遍執(zhí)行類型檢查第四遍完成代碼生成驅(qū)動(dòng)這些遍（pass）的TINY編譯器程序代碼如下： syntaxTree=parse(); buildSymtab(syntaxTree); typeCheck(syntaxTree); codeGen(syntaxTree,codefile);RET2.TINY詞法分析器的實(shí)現(xiàn)2.1實(shí)現(xiàn)TINY語言的詞法分析器TINY語言的詞法結(jié)構(gòu)保留字特殊符號(hào)其他ifthenelseendrepeatuntilreadwrite+-*/=<();:=numberidentifier識(shí)別TINY語言單詞的DFA+-returnPLUSreturnSEMI;識(shí)別除了賦值號(hào)以外的所有特殊符號(hào)的DFA定義如下：與識(shí)別數(shù)字和標(biāo)識(shí)符的DFA合并STARTdigitINIDINNUMdigitletterletterDONE[other][other]+-*/=<();擴(kuò)展DFA，增加對(duì)注釋、空白以及賦值號(hào)的識(shí)別STARTdigitINIDINNUMdigitletterletter[other][other]INASSIGN:whitespaceother=DONEINCOMMENT}{[other]other說明：所有接受狀態(tài)被合并為一個(gè)“DONE”狀態(tài)，不同接受狀態(tài)所識(shí)別的不同單詞被存放在一個(gè)變量中。為保留字構(gòu)造一張保留字表，當(dāng)一個(gè)標(biāo)識(shí)符被識(shí)別后，查找保留字表以確定是否為保留字。DFA的實(shí)現(xiàn)用在一個(gè)loop循環(huán)中定義兩層嵌套的case語句的方法。對(duì)實(shí)現(xiàn)DFA的部分代碼的解釋Scan.handScan.c主要過程：getToken

讀取輸入字符，返回根據(jù)DFA識(shí)別到的下一個(gè)單詞；該程序使用了兩層嵌套的case語句的方式實(shí)現(xiàn)外層case語句依據(jù)所處的不同狀態(tài)，內(nèi)層case語句依據(jù)不同的輸入符號(hào)對(duì)實(shí)現(xiàn)DFA的部分代碼的解釋Scan.handScan.ctokens在文件globals.h中被定義為一個(gè)枚舉類型包括以上所列的所有單詞，以及特殊用途的單詞endfile（當(dāng)?shù)竭_(dá)文件的結(jié)尾）以及ERROR（當(dāng)識(shí)別到一個(gè)錯(cuò)誤的單詞）詞法分析器的狀態(tài)被定義為一個(gè)枚舉類型，但定義在詞法分析器程序內(nèi)。對(duì)實(shí)現(xiàn)DFA的部分代碼的解釋Scan.handScan.c所識(shí)別的單詞的字符串值被存放在變量tokenString中變量tokenString以及getToken函數(shù)是詞法分析程序提供給編譯器其他部分的唯一接口他們的定義在頭文件scan.h中

tokenString被聲明為固定的長度41，所以標(biāo)識(shí)符的長度不能超過40個(gè)字符（包括字符串結(jié)束符）。對(duì)實(shí)現(xiàn)DFA的部分代碼的解釋Scan.handScan.c詞法分析程序使用了3個(gè)全局變量：存放源程序文件的變量source和listing，在globals.h中聲明，在main.c中初始化的整型變量lineno。對(duì)實(shí)現(xiàn)DFA的部分代碼的解釋Scan.handScan.c保留字表reservedWords以及表查找函數(shù)reservedLookup當(dāng)函數(shù)getToken識(shí)別了一個(gè)標(biāo)識(shí)符后，執(zhí)行保留字表的查表操作

如果在保留字表中，變量currentToken的值將相應(yīng)的改變標(biāo)記變量save用來標(biāo)記一個(gè)字符的值是否需要被增加到變量tokenString中。對(duì)實(shí)現(xiàn)DFA的部分代碼的解釋Scan.handScan.cgetNextChar函數(shù)為詞法分析程序提供輸入字符,從lineBuf中提取字符，其中l(wèi)ineBuf是詞法分析程序內(nèi)部一個(gè)256個(gè)字符的緩沖區(qū)如果lineBuf緩沖區(qū)的字符被取完，getNextChar函數(shù)將調(diào)用標(biāo)準(zhǔn)C函數(shù)fgets從源程序中提取字符到緩沖區(qū)假定每次提取源程序的一行，增加變量lineno的值雖然這種假定使編程變得簡單，但如果TINY源程序的某行多于255個(gè)字符，詞法分析程序的處理將不正確。對(duì)實(shí)現(xiàn)DFA的部分代碼的解釋Scan.handScan.c函數(shù)ungetNextChar在輸入緩沖區(qū)中倒退一個(gè)字符。TINY語言的示例程序{sampleprogramInTINYlanguage-Computesfactorial}readx;{inputoninteger}if0<xthen{don'tcomputeifx<=0}fact:=1;repeatfact:=fact*x;x:=x-1untilx=0;writefact{outputfactorialofx}end詞法分析器的輸出TINYCOMPILATION:sample.tny1:{Sampleprogram2:inTINYlanguage–3:computesfactorial4:}5:readx;{inputaninteger}5:reservedword:read5:id,name=x5:;6:

if0<xthen{don'tcomputeifx<=0}6:reservedword:if6:mum,val=06:<6:id,name=x6:reservedword:then7:fact:=1;7:id,name=fact7::=7:num,val=17:;8:repeat8:reservedword:repeat9:fact:=fact*x;9:id,name=fact9::=9:id,name=fact9:*9:id,name=x9:;10:x:=x-110:id,name=x10::=10:id,name=x10:-10:mum,val=111:untilx=0;11:reservedword:until11:id,name=x11:=11:mum,val=011:;12:writefact{outputfactorialofx}12:reservedwords:write12:id,name=fact13:end13:reservedword:end14:EOFRET3TINY語言的語法定義3.1TINY語言的上下文無關(guān)文法TINY語言的BNF文法定義(1)programstmt-sequencestmt-sequencestmt-sequence;statement|statementstatement

if-stmt|repeat-stmt|assign-stmt|read-stmt|write-stmtif-stmt

ifexpthenstmt-sequenceend |ifexpthenstmt-sequenceelsestmt-sequenceendrepeat-stmt

repeatstmt-sequenceuntilexpassign-stmtidentifier:=expread-stmt

readidentifierwrite-stmt

writeexpTINY語言的BNF文法定義(2)expsimple-expcomparison-opsimple-exp|simple-expcomparison-op

<|=simple-expsimple-expaddopterm|termaddop

+|-termtermmulopfactorfactor|factormulop*|/factor

(exp)|number|identifier3.2TINY編譯器的語法樹結(jié)構(gòu)基本的語法樹結(jié)構(gòu)1語句序列：s;s;sseqsss存在問題&解決方法當(dāng)樹的兒子節(jié)點(diǎn)個(gè)數(shù)不確定時(shí)，標(biāo)準(zhǔn)的表示方法是leftmost-childright-sibling，語句序列的表示采用了該方法從父親節(jié)點(diǎn)到兒子節(jié)點(diǎn)唯一的連接是到連接到最左邊的兒子節(jié)點(diǎn)所有的兒子節(jié)點(diǎn)從左到右按標(biāo)準(zhǔn)的列表的方式連接在一起，它們之間是兄弟節(jié)點(diǎn)的關(guān)系。存在問題&解決方法用leftmost-childright-sibling方式組織的語句序列對(duì)應(yīng)的語法樹:

seq

sss可進(jìn)一步去除seq節(jié)點(diǎn)，于是語法樹可簡化為：

sss1語句系列2if語句基本的語法樹的結(jié)構(gòu)3repeat語句4賦值語句5write語句6一個(gè)操作符的表達(dá)式{sampleprograminTINYlanguage-computesfactorial}readx;{inputaninteger}if0<xthen{don’tcomputeifx<=0} fact:=1; repeat fact:=fact*x; x:=x-1 untilx=0; writefact{outputfactorialofx}end語法樹的實(shí)現(xiàn)語法分析器生成的語法樹是標(biāo)準(zhǔn)的基于指針類型的結(jié)構(gòu)語法樹的每個(gè)節(jié)點(diǎn)包含語法分析器及其后續(xù)階段收集的信息，存放這些信息所需的空間可動(dòng)態(tài)分配，也可將這些信息存放在符號(hào)表中語法結(jié)構(gòu)的種類不同，對(duì)應(yīng)的語法樹節(jié)點(diǎn)需要保存的屬性也不同，因此可將語法樹節(jié)點(diǎn)定義為一個(gè)可變結(jié)構(gòu)體TINY語法樹的定義

typedefenum{StmtK,ExpK}NodeKind; typedefenum{IfK,RepeatK,AssignK,ReadK,WriteK}StmtKind; typedefenum{OpK,ConstK,IdK}ExpKind;#defineMAXCHILDREN3typedefstructtreeNode{ structtreeNode*child[MAXCHILDREN];structtreeNode*sibling;intlineno; NodeKindnodekind;union{StmtKindstmt;ExpKindexp;}kind;union{TokenTypeop;Intval;char*name;}attr;ExpTypetype;}TreeNode;RET4TINY的遞歸下降語法分析器TINY的語法分析器代碼TINY語法分析器包含兩個(gè)代碼文件：parse.handparse.c主要函數(shù)parse返回一個(gè)指向語法樹的指針 TreeNode*parse(void)用EBNF表示的TINY文法…stmt->seq->stmt{;stmt}exp ->simp-exp[copsimp-exp]simp-exp ->term{addopterm}term ->factor{mulopfactor}……TINY的語法分析器代碼包括11個(gè)遞歸子程序，每個(gè)對(duì)應(yīng)EBNF表示中的一個(gè)非終結(jié)符操作符在文法定義中是非終結(jié)符，但對(duì)它們的識(shí)別在相應(yīng)的表達(dá)式中進(jìn)行，沒有構(gòu)造單獨(dú)的識(shí)別子程序除了語句序列對(duì)應(yīng)的子程序，其他每個(gè)遞歸子程序的內(nèi)容完全是根據(jù)語法規(guī)則的定義構(gòu)造的stmt->seq->stmt{;stmt}TreeNode*stmt_sequence(void){TreeNode*t=statement();TreeNode*p=t;

while((token!=ENDFILE)&&(token!=END)&&(token!=ELSE)&&(token!=UNTIL)){TreeNode*q;

match(SEMI);q=statement();if(q!=NULL){if(t==NULL)t=p=q;else/*nowpcannotbeNULLeither*/{p->sibling=q;p=q;}}}returnt;}programstmt-sequenceif-stmt

ifexpthenstmt-sequence [elsestmt-sequence]endrepeat-stmt

repeatstmt-sequenceuntilexp遞歸下降語法分析程序用到的一些有用的函數(shù)被定義在文件util.c中：NewStmtNode(line405-421)：取語句的種類作為參數(shù)，創(chuàng)建一個(gè)相應(yīng)類型的語句節(jié)點(diǎn);NewExpNode(line423-440)：取exp的類型作為參數(shù)，創(chuàng)建一個(gè)相應(yīng)類型的表達(dá)式節(jié)點(diǎn)；PrintTree(linge473-506)：輸出語法樹，但語法樹僅被打印為一種線性的表示RET5TINY的語義分析器TINY的語義分析器包括兩個(gè)部分的主要工作：符號(hào)表的結(jié)構(gòu)設(shè)計(jì)以及符號(hào)表的相應(yīng)的操作語義分析程序本身的操作，包括符號(hào)表的構(gòu)建以及類型檢查5.1TINY編譯器的符號(hào)表TINY語言的符號(hào)表需要保存的信息包括：不需要包含作用域信息，以及數(shù)據(jù)類型信息為了目標(biāo)代碼生成的需要，包含了變量的地址信息包含了一個(gè)變量的引用列表，即一個(gè)關(guān)于變量在程序中被訪問的行號(hào)的列表例如：5: readx;6: ifx>0then7: fact:=1;8: repeat9: fact:=fact*x;10: x:=x-111: untilx=0;12: writefact13:end上述程序?qū)?yīng)的符號(hào)表信息為：VariableNameLocationLinenumbersx05,6,9,10,10,11fact17,9,9,125.2TINY的語義分析程序符號(hào)表是一種繼承屬性，而表達(dá)式的數(shù)據(jù)類型是一種綜合屬性于是，符號(hào)表的構(gòu)建可以通過對(duì)語法樹進(jìn)行先根遍歷，而類型檢查的執(zhí)行可以通過對(duì)語法樹的后根遍歷分別對(duì)語法樹進(jìn)行一次單獨(dú)的遍歷RET6TINY語言的運(yùn)行時(shí)環(huán)境TINY程序沒有過程定義，所有的變量都是全局變量，因此不需要過程活動(dòng)記錄棧唯一的動(dòng)態(tài)存儲(chǔ)需求是存儲(chǔ)表達(dá)式計(jì)算時(shí)生成的臨時(shí)變量TINY語言運(yùn)行時(shí)環(huán)境的結(jié)構(gòu)如下：在程序內(nèi)存的底部，為所有的變量分配絕對(duì)地址在程序內(nèi)存的頂部，分配存儲(chǔ)臨時(shí)變量的棧（表達(dá)式計(jì)算時(shí)產(chǎn)生的動(dòng)態(tài)存儲(chǔ)）假設(shè)某程序使用了4個(gè)變量x,y,z和w，這些變量將獲得內(nèi)存底部從0到3的絕對(duì)地址假定在該程序執(zhí)行過程中的某一時(shí)刻，有3個(gè)臨時(shí)變量被存儲(chǔ)運(yùn)行時(shí)環(huán)境如下所示：temp1temp2temp3freememorywzyxbottomofmemorytopofmemorytopoftempstack0123TINY的運(yùn)行時(shí)環(huán)境RET7Tiny的目標(biāo)代碼生成器TM：一個(gè)簡單的目標(biāo)機(jī)TINY編譯器生成一個(gè)非常簡單的虛擬機(jī)上的目標(biāo)代碼該虛擬機(jī)被稱為TM(TinyMachine)TINY的目標(biāo)代碼生成器要用到的TM的信息被存放在文件code.h和code.c中TINY語言的目標(biāo)代碼生成器TINY目標(biāo)代碼生成器的實(shí)現(xiàn)在文件cgen.c和cgen.h中，為TINY編譯器提供的唯一接口是函數(shù)codeGenvoidcodeGen(TreeNode*syntaxTree,char*codefile);函數(shù)codeGen的主要功能是:函數(shù)的開始，產(chǎn)生一些注釋以及建立運(yùn)行時(shí)環(huán)境的指令；然后，對(duì)語法樹調(diào)用cGen函數(shù)；最后，生成HALT指令，結(jié)束目標(biāo)代碼的生成。TINY語法樹的定義如下：typedefenum{StmtK,ExpK}NodeKind;typedefenum{IfK,RepeatK,AssignK,ReadK,WriteK}StmtKind;typedefenum{OpK,ConstK,IdK}ExpKind;#defineMAXCHILDREN3typedefstructtreeNo