华南理工大学《编译原理》实验报告.docx
《华南理工大学《编译原理》实验报告.docx》由会员分享,可在线阅读,更多相关《华南理工大学《编译原理》实验报告.docx(24页珍藏版)》请在冰点文库上搜索。
华南理工大学《编译原理》实验报告
华南理工大学
编译原理课程实验报告
实验题目:
Implementparser,analyzer,codegeneratorforTINY+
姓名:
黄炜杰学号:
201230590051
班级:
12计创组别:
无
合作者:
无
指导教师:
刘欣欣
实验概述
【实验目的及要求】
Purpose:
Implementtheparser,semanticanalyzerandcodegeneratorparttoconstructthewholecomplier.
Requirement:
Completearecursive–descentparserforTINY+.Parsergivessyntaxanalysistothetokensgeneratedbythescanner.Outputoftheparserisanabstractsyntaxtree.TheparsershouldfollowthetheseEBNFgrammarrules:
program->declarationsstmt-sequence
declarations->decl;declarations|ε
decl->type-specifiervarlist
type-specifier->int|bool|char
varlist->identifier{,identifier}
stmt-sequence->statement{;statement}
statement->if-stmt|repeat-stmt|assign-stmt|read-stmt|write-stmt|while-stmt
while-stmt->whilebool-expdostmt-sequenceend
bool-exp->bterm{orbterm}
bterm->bfactor{andbfactor}
bfactor->comparison-exp
comparison-exp->arithmetic-expcomparison-oparithmetic-exp
comparison-op-><|=|>|>=|<=
arithmetic-exp->term{addopterm}
term->factor{mulopfactor}
factor->(arithmetic-exp)|number|identifier
if-stmt->ifbool-expthenstmt-sequence[elsestmt-sequence]end
repeat-stmt->repeatstmt-sequenceuntilbool-exp
assign-stmt->identifier:
=exp
read-stmt->readidentifier
write-stmt->writeexp
exp->arithmetic-exp|bool-exp|string-exp
addop->+|-
mulop->*|/
string-exp->string
Buildsthesymboltableandchecksemanticerrors.Thefollowingsyntaxerrorsandsemanticerrorsshouldbedetected:
Syntaxerrors
Startsymbolandfollowingsymbolerror.
Identifierserror,suchasintisnotfollowedbyanidentifier.
Parenthesismatchingerror,suchas(and)donotmatch.
Symbolerror,suchasinassignmentthesymbolshouldbe‘:
=’,whileincompareexpressionsthesymbolshouldbe‘=’.
Semanticerrors
Anidentifierisusedbeforethedeclarationsofitandanidentifierisdeclaredmorethanonce.
Thetypeofaconditionexpressionisnotbool.
Thetypesofoperandsarenotequal.
Thetypesoftheleftandrighthandsideofassignmentarenotequal.
Intermediatecodeofcontrolstatementsshouldfollowtheseattributegrammar:
Seq->S;Seq1
{S.next=newlabel;Seq1.next=Seq.next;
Seq.code=S.code||LabelS.next||Seq1.code}
Seq->S
{S.next=Seq.next;Seq.code=S.code}
S->repeatSequntilE
{S.begin=newlabel;Seq.next=newlabel;
E.true=S.next;E.false=S.begin;
S.code=LabelS.begin||Seq.code||LabelSeq.next||E.code}
S->whileEdoSeqend
{S.begin=newlabelSeq.next=S.begin
E.true=newlabelE.false=S.next
S.code=LabelS.begin||E.code||LabelE.true||Seq.code||gotoS.begin}
S->ifEthenSeqend
{E.true=newlabel;E.false=S.next;Seq.next=S.next
S.code=E.code||Label.E.ture||Seq.code}
S->ifEthenSeq1elseSeq2end
{E.ture=newlabel;E.false=newlabel;
Seq1.next=S.next;Seq2.next=S.next;
S.code=E.code||LabelE.true||Seq1.code||gotoS.next||LabelE.fasle||Seq2.code}
【实验原理】
Scannerdolexicalconversionbyscanningeverycharactersandchangeitsstate,thenindicatethetypeoftokens.
Parserusethetokensformthescannertobuildaparseorsyntaxtree.Parserrecognizeeachtokenssequentially,anddeterminewhichshoulddonext,namelyshiftorreduction,bytheEBNFgrammarrules.WecannotmakesurewhetherthegrammarisLL
(1)ornot,soeliminateleftrecursionandleftfactorshouldbeconsidered.
Analyzercheckthesemanticandsyntaxerrorforthetreegeneratedfromparser,postordertraversalofthetreegiveeverynodeanattributestructures,whichincludenameorvalueofthenode.Bycheckingtheattributeofnodesandtheirchildren,errorscanbedetected.Also,bythetraversalofthetree,wecanaddeverydeclaredvariableintoahashtable,andthenconstructasymboltablefromthishashtable.
Codegeneratorisimplementedbytraversalthesyntaxorparsertreeagain.Thethreeaddresscodeisgenerateduringthetraversalprocess.EachstatementofEBNFgrammararetranslatebyspecialintermediatecodegrammarrule.Thereprocessisaconversionformtreestructuretosequentialcodestructure.
【实验环境】
IDE:
MicrosoftVisualStudio2013.
Project:
Win32consolecontrolapplication
Language:
Clanguage.
实验内容
【实验方案设计】
Therearesomanyproductioninthispart,soIjustillustratetherepresentativepartofthem.
Tobuildatree,itisnodoubtthatweshouldinsertmanynodeintothetree.So,manyproductionneedaspecificnodekindtoberepresented.Ideclarethefollowingnodekind,andtheywillbeexplainedlaterinthisreport:
typedefenum{StmtK,ExpK,DeclK}NodeKind;
typedefenum{tempK,StartK,DeclaK,TypespeK,WhileK,IfK,RepeatK,AssignK,ReadK,WriteK}StmtKind;
typedefenum{OpK,ConstK,IdK,StringK}ExpKind;
typedefenum{IntK,BoolK,CharK}DeclKind;
Thefirstruleisprogram->declarationsstmt-sequence
Thisruleseparatetheprogramintotwopart,oneisvariabledeclaration,theotherissequenceofstatements.Itshouldbetherootofthetree,soitisnecessarytoaddanodetothispoint.Asillustrateintherequirementinanalyzer,aprogramshouldcontainbothofthistwopart,soIdeclarethetopofthetreeasfollow:
Codeforthisstructureissimple.Nodeforstartpointis‘StartK’,ithastwochildren.
TreeNode*program(void)
{
TreeNode*t=newStmtNode(StartK);
if(t!
=NULL)
{
t->child[0]=declaration();
t->child[1]=stmt_sequence();
}
returnt;
}
Considertherule:
declarations->decl;declarations|ε
Theremaybeoneormoredeclsindelclaration.Wedon’sallocatenodefordelclarationsoastosavememory,sothestructureofdelclarationisdesignedasfollow:
Theamountofdeclsisundefined,soweneedtojudgebymyself.Bycomputation,IgetthatthefirstsetofdeclisINT,CHARorBOOL,soIcomparethenexttokenwithfirstsettodeterminetheendofdecls.
Codeforthiskindofnodeisalsosimple:
TreeNode*declaration(void)
{
TreeNode*t=decls();
TreeNode*p=t;
if(t==NULL)returnt;
match(SEMI);
while(token==INT||token==BOOL||token==CHAR)
{
TreeNode*q=newStmtNode(DeclaK);
q=decls();
match(SEMI);
p->sibling=q;
p=p->sibling;
}
returnt;
}
Theruletype-specifier->int|bool|charisatypicalexampleofleavenode.Fortheseleavenodes,weonlyneedtousethecurrenttokentodeterminewhichkinditis.
TreeNode*type_specifier(void)
{
TreeNode*t=newStmtNode(TypespeK);
switch(token){
caseINT:
t->child[0]=newDeclNode(IntK);
match(INT);
break;
caseCHAR:
t->child[0]=newDeclNode(CharK);
match(CHAR);
break;
caseBOOL:
t->child[0]=newDeclNode(BoolK);
match(BOOL);
break;
default:
syntaxError("unexpectedtoken->");
printToken(token,tokenString);
token=getToken();
break;
}
returnt;
}
Theabovesituationsnearlycoverallthetechniqueusedinparser.Butweshouldnotethat,thisgrammarisnotaLL
(1)grammar,wecannotbuildasyntaxtreeofparsertreebythisgrammar.Seethegrammerrule:
exp->arithmetic-exp|bool-exp|string-exp
Weshouldfocusonthearithmetic-exp|bool-exp,seetheirproductionrule:
arithmetic-exp->term{addopterm}
term->factor{mulopfactor}
factor->(arithmetic-exp)|number|identifier
bool-exp->bterm{orbterm}
bterm->bfactor{andbfactor}
bfactor->comparison-exp
comparison-exp->arithmetic-expcomparison-oparithmetic-exp
comparison-op-><|=|>|>=|<=
Whenweparsetheexprule,ifthenexttokenisidentifierofnumber,wecannotdeterminewhethertochosearithmetic_expofbool_exp,since
{identifier,num}∈First(arithmetic_exp)∩First(bool_exp).
Tosolvethisproblem,weshouldusetheleftfactoringtechnique.Thegrammarcanbemodifiedasfollow:
exp->bool-exp|string-exp
bool-exp->or-exp
Or-exp->Andexp{orAndexp}
Andexp->Notexp{andNotexp}
Not-exp->notexp|true|false|compare-exp
compare-exp->arithmetic-expcompare-oparithmetic-exp
comapre-op->>|<|=|>=|<=
arithmetic-exp->term{addopterm}
addop->+|-
term->factor{mulopfactor}
mulop->*|/
factor->(arithmetic-exp)|number|identifier
Withthenewgrammarrule,thenexttimegettheidentifierornumbertokenfortheexp()rules,it’seasytodeterminewhichproductiontouse.
Thereisnosuchinformationof“kind”inthetree.Soweneedtopostordertraversethetreetoassigntheirkindofthem.
Fortheleavenode,wedirectlyassignthetypeforthembytheirattribute,forexample
caseDeclK:
/*strcpy(treeNode_type,t->attr.name);
if(check_id(treeNode_type)==1)
typeError(t,"varible");*/
switch(t->kind.decl)
{
caseIntK:
type="int";
break;
caseBoolK:
type="bool";
break;
caseCharK:
type="char";
break;
default:
break;
}
default:
break;
Fortheinternalnode,wepassthetypeoftheirchildrenandassignatypeofthembythetypesofchildrenanditsattribute,forexample:
caseEQ:
if(t->child[0]->type!
=t->child[1]->type)
typeError(t,"Comparisionoperation=appliedtodifferenttype");
else
t->type=Boolean;
break;
Nowwehavegetthetypeofeverynodeofthetree,it’stimeforerrorchecking.Thetechniqueissimple,wejustneedtocomparethetypeofchildrenandthenodeitself,forexample:
caseEQ:
if(t->child[0]->type!
=t->child[1]->type)
typeError(t,"Comparisionoperation=appliedtodifferenttype");
else
t->type=Boolean;
break;
Thiscodecheckwhetherthetwooperandsofequaloperationisthesame.
Tocheckwhetheravariableisdefinedbeforeusedor