2022年編譯原理課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

編譯原理課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康模哼@個(gè)實(shí)驗(yàn)的目的是構(gòu)造Cminus語言的編譯器，要求能夠編譯Cminus語言的程序并且生成中間代碼。在實(shí)驗(yàn)的過程中，學(xué)會使用flex/bison這兩個(gè)重要的工具。實(shí)驗(yàn)內(nèi)容：參見教材p491appendixA.設(shè)計(jì)一cminus語言編譯器語言介紹。Decaf（cminus）語言的關(guān)鍵字：

intwhileifelsereturnvoid運(yùn)算符：+-*/><=,.!={}[]<=>===()Cminus語言的限制。數(shù)字：支持10進(jìn)制整數(shù)。小數(shù)可以采用科學(xué)記數(shù)法，如1E3也是合法的。字符串：字符串內(nèi)部不允許出現(xiàn)換行，即字符串變量必須在同一行內(nèi)。注釋：Cminus語言允許采用/*…*/注釋，并且注釋不可以嵌套，即下面的注釋是不合法的：/*Thisis/*avalid*/comment*/程序流程圖開始開始詞法分析語法分析建立符號表類型檢查代碼生成結(jié)束語法樹符號表程序的流程參照了書本TINY編譯器的實(shí)例程序：語法分析器(Parser)調(diào)用詞法分析器得到符合詞法的字，建立語法樹；符號表通過對語法樹的分析，建立符號表，同時(shí)檢查變量未定義等錯(cuò)誤；類型檢查包括檢查表達(dá)式兩邊是否匹配，函數(shù)參數(shù)是否匹配等等；經(jīng)由上述步驟而未出錯(cuò)的源程序被認(rèn)為是合法程序，然后代碼生成通過語法樹和符號表生成PCode中間代碼，并將變量地址存入符號表。其中類型檢查和代碼生成不要求實(shí)現(xiàn)。本次實(shí)驗(yàn)要求分組，一組五人，一人完成一個(gè)部分。本組實(shí)驗(yàn)分組成員以及分工介紹：汪晨風(fēng)：（設(shè)計(jì)并實(shí)現(xiàn)cminus符號表）；E02620105蔡其星：（編寫cminus.l文件，并用lex工具生成c代碼）；E02620107趙婷：（設(shè)計(jì)cminus語法樹結(jié)構(gòu)）；E02620106馬培良：編寫cminus.y文件，并用yacc工具生成可執(zhí)行代碼）；E02620121丘廷：（進(jìn)行程序的測試）以下為具體實(shí)驗(yàn)分步報(bào)告以及過程：第一部分：設(shè)計(jì)cminus符號表符號表是編譯器中的主要繼承屬性，并且在語法樹之后，形成了主要的數(shù)據(jù)結(jié)構(gòu)。符號表主要的操作有插入、查找和刪除。雜湊表（hash表）通常為符號表的實(shí)現(xiàn)提供了最好的選擇，因?yàn)樗?種操作都能在幾乎恒定的時(shí)間內(nèi)完成，在實(shí)踐中也是最常使用。該課程設(shè)計(jì)所用的C-符號表采用建立雜湊表的方法。雜湊表是一個(gè)入口數(shù)組，稱作“桶(bucket)”，使用一個(gè)整數(shù)范圍的索引，通常從0到表的尺寸減1。雜湊函數(shù)(hashfuction)把索引鍵(在這種情況下是標(biāo)識符名，組成一個(gè)字符串)轉(zhuǎn)換成索引范圍內(nèi)的一個(gè)整數(shù)的雜湊值，對應(yīng)于索引鍵的項(xiàng)存儲在這個(gè)索引的“桶”中。每個(gè)“桶”實(shí)際上又是一個(gè)線性表，通過把新的項(xiàng)插入到“桶”表中來解決沖突在任何情況下，“桶”數(shù)組的實(shí)際大小要選擇一個(gè)素?cái)?shù)，因?yàn)檫@將使一般的雜湊函數(shù)運(yùn)行得更好。雜湊函數(shù)。在符號表實(shí)現(xiàn)中使用的雜湊函數(shù)將字符串(標(biāo)識符名)轉(zhuǎn)換成0...size-1范圍內(nèi)的一個(gè)整數(shù)。一般這通過3步來進(jìn)行。首先，字符串中的每個(gè)字符轉(zhuǎn)換成一個(gè)非負(fù)整數(shù)。然后，這些整數(shù)用一定的方法組合形成一個(gè)整數(shù)。最后，把結(jié)果整數(shù)調(diào)整到0...size-1范圍內(nèi)。沖突的一個(gè)好的解決辦法是，當(dāng)加上下一個(gè)字符的值時(shí)，重復(fù)地使用一個(gè)常量作為乘法因子。因此，如果ci是第i個(gè)字符的數(shù)字值，hi是在第i步計(jì)算的部分雜湊值，那么hi根據(jù)下面的遞歸公式計(jì)算，h0=0，hi－1=ahi－ci，最后的雜湊值用h=hnmodsize計(jì)算。這里n是雜湊的名字中字符的個(gè)數(shù)。這等價(jià)于下列公式當(dāng)然，在這個(gè)公式中a的選擇對輸出結(jié)果有重要影響。a的一種合理的選擇是2的冪，如16或128，這樣乘法可以通過移位來完成。該程序a選16，size取211。由于在數(shù)據(jù)結(jié)構(gòu)方面為了實(shí)現(xiàn)很方便的進(jìn)行查找，插入，刪除等操作。我們把它的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)成一哈稀表結(jié)構(gòu)，哈稀表的查找，插入等操作是飛快的。我們所設(shè)計(jì)的哈稀結(jié)構(gòu)符號表是參考教科書上P295它的結(jié)構(gòu)如下：符號表的雜湊函數(shù)#defineSIZE211#defineSHIFT4inthash(char*key){inttemp=0;inti=0;while(key[i]!='\0'){temp=((temp<<SHIFT)+key[i])%SIZE;++i;}returntemp;}該符號表完成了插入[voidst_insert(char*name,intlineno,intloc)]、查找[intst_lookup(char*name)]工作源程序：symtab.c#include<stdio.h>#include<stdlib.h>#include<string.h>#include"symtab.h"/*定義哈稀表的最大值*/#defineSIZE211/*SHIFTisthepoweroftwousedasmultiplierinhashfunction*/#defineSHIFT4/*哈稀函數(shù)結(jié)構(gòu)*/staticinthash(char*key){inttemp=0;inti=0;while(key[i]!='\0'){temp=((temp<<SHIFT)+key[i])%SIZE;++i;}returntemp;}typedefstructLineListRec{intlineno;structLineListRec*next;}*LineList;typedefstructBucketListRec{char*name;LineListlines;intmemloc;/*memorylocationforvariable*/structBucketListRec*next;}*BucketList;/*哈稀表*/staticBucketListhashTable[SIZE];voidst_insert(char*name,intlineno,intloc){inth=hash(name);BucketListl=hashTable[h];while((l!=NULL)&&(strcmp(name,l->name)!=0))l=l->next;if(l==NULL)/*variablenotyetintable*/{l=(BucketList)malloc(sizeof(structBucketListRec));l->name=name;l->lines=(LineList)malloc(sizeof(structLineListRec));l->lines->lineno=lineno;l->memloc=loc;l->lines->next=NULL;l->next=hashTable[h];hashTable[h]=l;}else/*foundintable,sojustaddlinenumber*/{LineListt=l->lines;while(t->next!=NULL)t=t->next;t->next=(LineList)malloc(sizeof(structLineListRec));t->next->lineno=lineno;t->next->next=NULL;}}intst_lookup(char*name){inth=hash(name);BucketListl=hashTable[h];while((l!=NULL)&&(strcmp(name,l->name)!=0))l=l->next;if(l==NULL)return-1;elsereturnl->memloc;}voidprintSymTab(FILE*listing){inti;fprintf(listing,"VariableNameLocationLineNumbers\n");fprintf(listing,"---------------------------------\n");for(i=0;i<SIZE;++i){if(hashTable[i]!=NULL){BucketListl=hashTable[i];while(l!=NULL){LineListt=l->lines;fprintf(listing,"%-14s",l->name);fprintf(listing,"%-8d",l->memloc);while(t!=NULL){fprintf(listing,"%4d",t->lineno);t=t->next;}fprintf(listing,"\n");l=l->next;}}}}/*printSymTab*/symtab.h#ifndef_SYMTAB_H_#define_SYMTAB_H_voidst_insert(char*name,intlineno,intloc);/*插入函數(shù)*/intst_lookup(char*name);/*查找函數(shù)*/voidprintSymTab(FILE*listing);/*用來打印哈稀表內(nèi)容*/#endif符號表設(shè)計(jì)的好壞直接影響到整個(gè)程序運(yùn)行的速度，效率以及準(zhǔn)確度。因?yàn)榻酉聛淼膒arse工作是基于符號表的，是從符號表里提取token進(jìn)行語法分析的。為了提高程序運(yùn)行的的效率，我們把scan直接通過parse來調(diào)用。具體的來講就是，程序運(yùn)行時(shí)，首先進(jìn)入parse部分，當(dāng)parse要用到token時(shí)，調(diào)用scan部分掃描原文件生成token儲存在符號表中，并同時(shí)提供給parse進(jìn)行語法分析。這樣就可以一遍完成整個(gè)原文件的掃描。第二部分：運(yùn)用LEX實(shí)現(xiàn)cminus詞法分析程序。這一部比較關(guān)鍵，設(shè)計(jì)的正確與否直接影響到在scan過程中token的產(chǎn)生。以及整個(gè)程序運(yùn)行的結(jié)果的正確與否。在這里主要定義cminus的基本語法規(guī)則，以及token類型，運(yùn)算符類型，并且定義cminus關(guān)鍵字，便于在程序運(yùn)行時(shí)能對其進(jìn)行識別。一下為cminus.l文件原代碼：/*定義全局變量、函數(shù)及包含文件說明：*/%{#include"globals.h"#include"util.h"#include"scan.h"#defineMAXTOKENLEN40chartokenString[40];intlineno=0;%}有關(guān)語法規(guī)則以及token的定義:digit[0-9]number{digit}+letter[a-zA-Z]identifier{letter}+newline\nwhitespace[\t]+%%/*以下為關(guān)鍵字定義:*/"if"{returnIF;}"else"{returnELSE;}"int"{returnINT;}"void"{returnVOID;}"return"{returnRETURN;}"while"{returnWHILE;}以下為運(yùn)算符號定義:*/"="{returnASSIGN;}"<="{returnLTEQ;}">="{returnGTEQ;}"<"{returnLT;}">"{returnGT;}"=="{returnEQ;}"!="{returnNOTEQ;}"+"{returnPLUS;}"-"{returnMINUS;}"*"{returnTIMES;}"/"{returnOVER;}"("{returnLPAREN;}")"{returnRPAREN;}"["{returnLBRACK;}"]"{returnRBRACK;}"{"{returnLCURL;}"}"{returnRCURL;}";"{returnSEMI;}","{returnCOMMA;}終結(jié)符及注釋符號*/{number}{returnNUM;}{identifier}{returnID;}{newline}{lineno++;}{whitespace}{/*skipwhitespace*/}"/*"{charc;chard;c=input();if(c!=EOF){do{d=c;c=input();if(c==EOF)break;if(c=='\n')lineno++;}while(!(d=='*'&&c=='/'));}}.{returnERROR;}%%定義getToken()函數(shù)體:TokenTypegetToken(void){staticintfirstTime=TRUE;TokenTypecurrentToken;if(firstTime){firstTime=FALSE;lineno++;yyin=source;yyout=listing;}currentToken=yylex();strncpy(tokenString,yytext,MAXTOKENLEN);if(TraceScan){fprintf(listing,"\t%d:",lineno);printToken(currentToken,tokenString);}returncurrentToken;}說明：以上代碼已經(jīng)能通過lex工具產(chǎn)生c代碼。cminus.l的設(shè)計(jì)基本結(jié)構(gòu)是參考tiny.l的結(jié)構(gòu)設(shè)計(jì)而成，但要注意的是，由于在接下來的cnimus.y中所定義的語法規(guī)則不同，這里的也要稍做修改。比如在這里的getToken函數(shù)，要于cminus.y文件里的設(shè)計(jì)的返回參數(shù)要一一對應(yīng)，否則在編譯的過程中會出現(xiàn)類型不匹配等等的錯(cuò)誤，修改起來比較麻煩。第三部分：為C-設(shè)計(jì)語法樹結(jié)構(gòu)，使之適用于分析器產(chǎn)生語法樹是LALR分析的前提。因此在進(jìn)行語法分析之前，必須設(shè)計(jì)語法樹結(jié)構(gòu)，使接下來的語法分析有一個(gè)具體的數(shù)據(jù)結(jié)構(gòu)。其代碼段如下：#defineMAXTOKENSIZE50typedefintTokenType;/*定義語法樹結(jié)構(gòu)*/typedefstruct{TokenTypetok;char*tokString;}TokenStruct;typedefenum{IfK,WhileK,AssignK,ReturnK,CallK,VarDeclK,FunDeclK,OpK,ConstK,IdK}NodeKind;/*枚舉結(jié)點(diǎn)類型*/typedefenum{Void,Integer,Boolean}ExpType;/*枚舉返回變量類型*/#defineMAXCHILDREN3/*聲明一個(gè)結(jié)點(diǎn)最多有三個(gè)子結(jié)點(diǎn)*/typedefstructtreeNode/*定義語法樹結(jié)點(diǎn)結(jié)構(gòu)*/{structtreeNode*child[MAXCHILDREN];structtreeNode*sibling;intlineno;NodeKindkind;union{TokenTypeop;intval;char*name;}attr;ExpTypetype;}TreeNode;說明：在這里當(dāng)當(dāng)只是設(shè)計(jì)的語法樹的基本數(shù)據(jù)結(jié)構(gòu)，至于要用到parse過程中還要進(jìn)行具體的修改，調(diào)試。這些工作都已經(jīng)在程序原代碼調(diào)試過程中做好。第四部分：LALR分析。（使用yacc工具）這一部分完成了整個(gè)編譯過程中的語法分析，二異性沖突處理，lese懸掛問題的處理，運(yùn)算符優(yōu)先級處理以及錯(cuò)誤報(bào)告。參考課本P49229條cminusBNF。并且通過細(xì)心理解體會，寫出了cminus.y文件，并能通過yacc生成c代碼。Cnimus.y代碼以及一些具體功能如下所述：YACC源程序的結(jié)構(gòu)說明部分的內(nèi)容如下：％{ 頭文件 宏定義 數(shù)據(jù)類型定義 全局變量定義 ％} 語法開始符定義 語義值類型定義 終結(jié)符定義 運(yùn)算符優(yōu)先級及結(jié)合性定義%{#defineYYPARSER/*distinguishesYaccoutputfromothercodefiles*/#include"globals.h"#include"util.h"#include"scan.h"#include"parse.h"TreeNode*parseTree;/*storessyntaxtreeforlaterreturn*/voidyyerror(constchar*s);%}語法開始符號的定義％start非終結(jié)符注：若沒有上述說明，YACC自動(dòng)將第一條語法規(guī)則左部的非終結(jié)符作為語法開始符。語義值類型的定義%union定義語義值的類型;%union{TreeNode*tnode;TokenTypetok;}%type定義文法符號的語義值類型;%type<tnode>programdeclaration_listdeclarationvar_declaration%type<tnode>fun_declarationparamsparam_listparamcompound_stmt%type<tnode>local_declarationsstatement_liststatement%type<tnode>expression_stmtselection_stmtiteration_stmt%type<tnode>return_stmtexpressionvarsimple_expression%type<tnode>additive_expressiontermfactorcallargsarg_list%type<tok>type_specifierrelopaddopmulop%token在定義終結(jié)符號時(shí)也可以定義語義值類型。終結(jié)符的定義%token<語義值類型>終結(jié)符名編號%tokenDIGITLETTER%tokenBEGIN100注：1.非終結(jié)符不需要特別說明，如果需要說明語義值類型則用％type語句；2.文字字符終結(jié)符不需要特別說明，它們的編號取其在字符集中的值；3.在規(guī)則中出現(xiàn)文字字符時(shí)用單引號括起來。%tokenENDFILE,ERROR,%tokenIF,ELSE,INT,RETURN,VOID,WHILE,%tokenID,NUM,%tokenASSIGN,%tokenEQ,NOTEQ,LTEQ,GTEQ,LT,GT,%tokenPLUS,MINUS,TIMES,OVER,%tokenLPAREN,RPAREN,LBRACK,RBRACK,LCURL,RCURL,%tokenSEMI,COMMA運(yùn)算符優(yōu)先級和結(jié)合性的定義以％left和％right定義結(jié)合性；以排列順序定義優(yōu)先級；在語法規(guī)則中，以％prec輔助定義優(yōu)先級消除二義性的兩條規(guī)則：1.出現(xiàn)移進(jìn)/歸約沖突時(shí)，進(jìn)行移進(jìn)；2.出現(xiàn)歸約/歸約沖突時(shí)，用先出現(xiàn)的規(guī)則進(jìn)行歸約；stat: IFbexpTHENstatIFbexpTHENstatELSEstat;用結(jié)合性和優(yōu)先級解決沖突；規(guī)則的結(jié)合性就是規(guī)則右部最后一個(gè)非終結(jié)符的優(yōu)先級和結(jié)合性；如果使用了％prec子句，則優(yōu)先級和結(jié)合性由％prec子句決定；對于無優(yōu)先級和結(jié)合性的規(guī)則，用規(guī)則1、2解決；對于有優(yōu)先級和結(jié)合行的規(guī)則，用如下的規(guī)則解決：出現(xiàn)移進(jìn)/歸約沖突時(shí)，輸入符號的優(yōu)先級大于規(guī)則的優(yōu)先級則移進(jìn)，若輸入符號的優(yōu)先級小于規(guī)則的優(yōu)先級則歸約，若二者的優(yōu)先級相同，左結(jié)合則歸約，右結(jié)合則移進(jìn)，無結(jié)合則出錯(cuò)。語法規(guī)則program :declaration_list {parseTree=$1; YYACCEPT; } ;declaration_list :declaration_listdeclaration {TreeNode*t=$1;if(t!=NULL){ while(t->sibling!=NULL) t=(TreeNode*)t->sibling;t->sibling=$2;$$=$1; }else$$=$2; } |declaration {$$=$1;} ;declaration :var_declaration {$$=$1;} |fun_declaration {$$=$1;} ;程序由聲明的列表(或序列)組成，聲明可以是函數(shù)或變量聲明，順序是任意的。至少必須有一個(gè)聲明。接下來是語義限制(這些在C中不會出現(xiàn))。所有的變量和函數(shù)在使用前必須聲明(這避免了向后backpatching引用)。程序中最后的聲明必須是一個(gè)函數(shù)聲明，名字為main。var_declaration :type_specifierIDSEMI {$$=(TreeNode*)newNode(VarDeclK); $$->attr.op=$1; $$->child[0]=(TreeNode*)newNode(IdK); $$->child[0]->=(char*)copyString(lastid); //addtosymboltable } |type_specifierIDLBRACKNUM {$<tnode>$=(TreeNode*)newNode(VarDeclK); $<tnode>$->attr.op=$1; $<tnode>$->child[0]=(TreeNode*)newNode(IdK); $<tnode>$->child[0]->=(char*)copyString(lastid); $<tnode>$->child[0]=(TreeNode*)newNode(ConstK); $<tnode>$->child[0]->attr.val=atoi(curToken.tokString); //addtosymboltable } RBRACKSEMI { $$=$<tnode>5; } ;type_specifier :INT {$$=INT;} |VOID {$$=VOID;} ;變量聲明或者聲明了簡單的整數(shù)類型變量，或者是基類型為整數(shù)的數(shù)組變量，索引范圍從0到NUM-1。注意，在C－中僅有的基本類型是整型和空類型。在一個(gè)變量聲明中，只能使用類型指示符int。void用于函數(shù)聲明(參見下面)。也要注意，每個(gè)聲明只能聲明一個(gè)變量。fun_declaration :type_specifierID {$<tnode>$=(TreeNode*)newNode(FunDeclK); $<tnode>$->attr.op=$1; $<tnode>$->child[0]=(TreeNode*)newNode(IdK); $<tnode>$->child[0]->=(char*)copyString(lastid); } LPARENparamsRPARENcompound_stmt {$$=$<tnode>3; $$->child[1]=$5; $$->child[2]=$7; } ;params :param_list {$$=$1;} |VOID {$$=NULL;} ;param_list :param_listCOMMAparam {TreeNode*t=$1;if(t!=NULL){ while(t->sibling!=NULL) t=(TreeNode*)t->sibling;t->sibling=$3;$$=$1; }else$$=$3; } |param {$$=$1;} ;param :type_specifierID {$$=(TreeNode*)newNode(VarDeclK); $$->attr.op=$1; $$->child[0]=(TreeNode*)newNode(IdK); $$->child[0]->=(char*)copyString(lastid); //addtosymboltable } |type_specifierID {$<tnode>$=(TreeNode*)newNode(VarDeclK); $<tnode>$->attr.op=$1; $<tnode>$->child[0]=(TreeNode*)newNode(IdK); $<tnode>$->child[0]->=(char*)copyString(lastid); //addtosymboltable } LBRACKRBRACK {$$=$<tnode>3;} ;函數(shù)聲明由返回類型指示符、標(biāo)識符以及在圓括號內(nèi)的用逗號分開的參數(shù)列表組成，后面跟著一個(gè)復(fù)合語句，是函數(shù)的代碼。如果函數(shù)的返回類型是void，那么函數(shù)不返回任何值(即是一個(gè)過程)。函數(shù)的參數(shù)可以是void(即沒有參數(shù))，或者一列描述函數(shù)的參數(shù)。參數(shù)后面跟著方括號是數(shù)組參數(shù)，其大小是可變的。簡單的整型參數(shù)由值傳遞。數(shù)組參數(shù)由引用來傳遞(也就是指針)，在調(diào)用時(shí)必須通過數(shù)組變量來匹配。注意，類型“函數(shù)”沒有參數(shù)。一個(gè)函數(shù)參數(shù)的作用域等于函數(shù)聲明的復(fù)合語句，函數(shù)的每次請求都有一個(gè)獨(dú)立的參數(shù)集。函數(shù)可以是遞歸的(對于使用聲明允許的范圍)。compound_stmt :LCURLlocal_declarationsstatement_listRCURL {TreeNode*t=$2;if(t!=NULL){ while(t->sibling!=NULL) t=(TreeNode*)t->sibling;t->sibling=$3;$$=$2; }else$$=$3; } ;復(fù)合語句由用花括號圍起來的一組聲明和語句組成。復(fù)合語句通過用給定的順序執(zhí)行語句序列來執(zhí)行。局部聲明的作用域等于復(fù)合語句的語句列表，并代替任何全局聲明。local_declarations :local_declarationsvar_declaration {TreeNode*t=$1;if(t!=NULL){ while(t->sibling!=NULL) t=(TreeNode*)t->sibling;t->sibling=$2;$$=$1; }else$$=$2; } | {$$=NULL;} ;statement_list :statement_liststatement {TreeNode*t=$1;if(t!=NULL){ while(t->sibling!=NULL) t=(TreeNode*)t->sibling;t->sibling=$2;$$=$1; }else$$=$2; } | {$$=NULL;} ;注意聲明和語句列表都可以是空的(非終結(jié)符empty表示空字符串，有時(shí)寫作)statement :expression_stmt {$$=$1;} |compound_stmt {$$=$1;} |selection_stmt {$$=$1;} |iteration_stmt {$$=$1;} |return_stmt {$$=$1;} ;expression_stmt :expressionSEMI {$$=$1;} |SEMI {$$=NULL;} ;表達(dá)式語句有一個(gè)可選的且后面跟著分號的表達(dá)式。這樣的表達(dá)式通常求出它們一方的結(jié)果。因此，這個(gè)語句用于賦值和函數(shù)調(diào)用。selection_stmt :IFLPARENexpressionRPARENstatement {$$=(TreeNode*)newNode(IfK); $$->child[0]=$3; $$->child[1]=$5; } |IFLPARENexpressionRPARENstatementELSEstatement {$$=(TreeNode*)newNode(IfK); $$->child[0]=$3; $$->child[1]=$5; $$->child[2]=$7; } ;if語句有通常的語義：表達(dá)式進(jìn)行計(jì)算；非0值引起第一條語句的執(zhí)行；0值引起第二條語句的執(zhí)行，如果它存在的話。這個(gè)規(guī)則導(dǎo)致了典型的懸掛else二義性，可以用一種標(biāo)準(zhǔn)的方法解決：else部分通常作為當(dāng)前if的一個(gè)子結(jié)構(gòu)立即分析(“最近嵌套”非二義性規(guī)則)。iteration_stmt :WHILELPARENexpressionRPARENstatement {$$=(TreeNode*)newNode(WhileK); $$->child[0]=$3; $$->child[1]=$5; } ;while語句是C－中唯一的重復(fù)語句。它重復(fù)執(zhí)行表達(dá)式，并且如果表達(dá)式的求值為非0，則執(zhí)行語句，當(dāng)表達(dá)式的值為0時(shí)結(jié)束。return_stmt :RETURNSEMI {$$=(TreeNode*)newNode(ReturnK);} |RETURNexpressionSEMI {$$=(TreeNode*)newNode(ReturnK); $$->child[0]=$2; } ;返回語句可以返回一個(gè)值也可無值返回。函數(shù)沒有說明為void就必須返回一個(gè)值。函數(shù)聲明為void就沒有返回值。return引起控制返回調(diào)用者(如果它在main中，則程序結(jié)束)。expression :varASSIGNexpression {$$=(TreeNode*)newNode(AssignK); $$->child[0]=$1; $$->child[1]=$3; } |simple_expression {$$=$1;} ;var :ID {$$=(TreeNode*)newNode(IdK); $$->=(char*)copyString(lastid); } |ID {$<tnode>$=(TreeNode*)newNode(IdK); $<tnode>$->=(char*)copyString(lastid); } LBRACKexpressionRBRACK {$$=$<tnode>2; $$->child[0]=$4; } ;表達(dá)式是一個(gè)變量引用，后面跟著賦值符號(等號)和一個(gè)表達(dá)式，或者就是一個(gè)簡單的表達(dá)式。賦值有通常的存儲語義：找到由var表示的變量的地址，然后由賦值符右邊的子表達(dá)式進(jìn)行求值，子表達(dá)式的值存儲到給定的地址。這個(gè)值也作為整個(gè)表達(dá)式的值返回。var是簡單的(整型)變量或下標(biāo)數(shù)組變量。負(fù)的下標(biāo)將引起程序停止(與C不同)。然而，不進(jìn)行下標(biāo)越界檢查。simple_expression :additive_expressionrelopadditive_expression {$$=(TreeNode*)newNode(OpK); $$->attr.op=$2; $$->child[0]=$1; $$->child[1]=$3; } |additive_expression {$$=$1;} ;relop :EQ {$$=EQ;} |NOTEQ {$$=NOTEQ;} |LTEQ {$$=LTEQ;} |GTEQ {$$=GTEQ;} |LT {$$=LT;} |GT {$$=GT;} ;簡單表達(dá)式由無結(jié)合的關(guān)系操作符組成(即無括號的表達(dá)式僅有一個(gè)關(guān)系操作符)。簡單表達(dá)式在它不包含關(guān)系操作符時(shí)，其值是加法表達(dá)式的值，或者如果關(guān)系算式求值為ture，其值為1，求值為false時(shí)值為0。additive_expression :additive_expressionaddopterm {$$=(TreeNode*)newNode(OpK); $$->attr.op=$2; $$->child[0]=$1; $$->child[2]=$3; } |term {$$=$1;} ;addop :PLUS {$$=PLUS;} |MINUS {$$=MINUS;} ;term :termmulopfactor {$$=(TreeNode*)newNode(OpK); $$->attr.op=$2; $$->child[0]=$1; $$->child[2]=$3; } |factor {$$=$1;} ;mulop :TIMES {$$=TIMES;} |OVER {$$=OVER;} ;加法表達(dá)式和項(xiàng)表示了算術(shù)操作符的結(jié)合性和優(yōu)先級。符號表示整數(shù)除；即任何余數(shù)都被截去。factor :LPARENexpressionRPAREN {$$=$2;} |var {$$=$1;} |call {$$=$1;} |NUM {$$=(TreeNode*)newNode(ConstK); $$->attr.val=atoi(curToken.tokString); } ;因子是圍在括號內(nèi)的表達(dá)式；或一個(gè)變量，求出其變量的值；或者一個(gè)函數(shù)調(diào)用，求出函數(shù)的返回值；或者一個(gè)NUM，其值由掃描器計(jì)算。數(shù)組變量必須是下標(biāo)變量，除非表達(dá)式由單個(gè)ID組成，并且以數(shù)組為參數(shù)在函數(shù)調(diào)用中使用(如下所示)。call :ID {$<tnode>$=(TreeNode*)newNode(CallK); $<tnode>$->child[0]=(TreeNode*)newNode(IdK); $<tnode>$->child[0]->=(char*)copyString(lastid); } LPARENargsRPAREN {$$=$<tnode>2; $$->child[1]=$4; } ;args :arg_list {$$=$1;} | {$$=NULL;} ;arg_list :arg_listCOMMAexpression {TreeNode*t=$1;if(t!=NULL){ while(t->sibling!=NULL) t=(TreeNode*)t->sibling;t->sibling=$3;$$=$1; }else$$=$3; } |expression {$$=$1;} ;函數(shù)調(diào)用的組成是一個(gè)ID(函數(shù)名)，后面是用括號圍起來的參數(shù)。參數(shù)或者為空，或者由逗號分割的表達(dá)式列表組成，表示在一次調(diào)用期間分配的參數(shù)的值。函數(shù)在調(diào)用之前必須聲明，聲明中參數(shù)的數(shù)目必須等于調(diào)用中參數(shù)的數(shù)目。函數(shù)聲明中的數(shù)組參數(shù)必須和一個(gè)表達(dá)式匹配，這個(gè)表達(dá)式由一個(gè)標(biāo)識符組成表示一個(gè)數(shù)組變量。%%出錯(cuò)處理遇到錯(cuò)誤就終止語法分析；voidyyerror(char*message){printf("Erroratline%d:%s\n",lineno,message);}說明：.L文件.Y文件是是整個(gè)程序的主題部分，直接決定了該程序的功能如何。因此在設(shè)計(jì)這兩個(gè)部分的時(shí)候要細(xì)心耐心調(diào)試。難點(diǎn)主要是在語法規(guī)則的定義，已經(jīng)函數(shù)間的銜接。通過長時(shí)間的調(diào)試，并且參考tiny編譯器，對它的一些工具函數(shù)進(jìn)行修改（原程序的util.c文件）并使子之能適用于cminus編譯器。第五部分：程序測試測試工作在任何一個(gè)程序設(shè)計(jì)或者軟件設(shè)計(jì)當(dāng)中是一項(xiàng)必不可少的工序，而且是一項(xiàng)非常重要的工作。測試做的好壞，直接可以決定該軟件的好壞。在測試當(dāng)中可以發(fā)現(xiàn)軟件的漏洞，這樣就可以對其進(jìn)行修改，使之完善。在本程序測試過程中，可以自己編寫cminus語句或者程序，用該編譯器來進(jìn)行掃描，語法分析。并且輸出語法樹，如果cnimus語句有錯(cuò)，編譯器會報(bào)錯(cuò)。基于這樣的目的我們做了以下的測試：首先利用課本496頁的測試程序?qū)ζ溥M(jìn)行測試：sample.decaf/*Aprogram