华南理工大学《编译原理》实验报告.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
升级会员 