外文翻译 - 一种教学编译器的通用工具

外文资料ComputerandInformationScience;Vol.6,No.2;2013ISSN1913-8989E-ISSN1913-8997PublishedbyCanadianCenterofScienceandEducation134AGenericToolforTeachingCompilersRiadJabri11UniversityofJordan,Amman,JordanCorrespondence:RiadJabri,ComputerScienceDepartment,KingAbdullahIISchoolforInformationTechnology,UniversityofJordan,Amman11942,Jordan.E-mail:.joReceived:March11,2013Accepted:April24,2013OnlinePublished:April26,2013doi:10.5539/cis.v6n2p134URL:/10.5539/cis.v6n2p134AbstractInthispaper,weproposeatwo-foldgenerictoolforcompilerconstruction.First,itfacilitatesteachingcompilers.Second,itconstitutesanewapproachforcompilerconstruction.Inaddition,itenablesasmoothtransitionfromtheorytopracticeandintroducesaunifiedapproachfortheimplementationofthedifferentcompilerphases.Suchunificationisachievedbasedontherepresentationofthecompilerphasesasagenericdomainthatisthenmappedintoagenericautomaton.Thegenericautomatonsimulatesthebehavioroffiniteandshift-reduceautomata,annotatedbyrespectivetranslationschemes.Thus,thetoolactsasascanner,aparserorassyntaxdirectedtranslator.Withoutlossofgenerality,theproposedtoolisusedwithinacompiler-teachingframework.Comparisonswithsimilarandwell-knownapproacheshaveshownthatourapproachispedagogical,conceptuallysimpler,requireslessstudenteffortsandmorerelevanttocorecurriculum.Keywords:teachingframework,scanning,parsing,grammars,syntaxdirectedtranslation1.IntroductionInthispaper,weproposeagenerictoolforteachingcompilers.Usually,compilerconstructionistaughtasaone-semestercoursehavingasprerequisitescoursesinprogramminglanguages;datastructuresandcomputerorganization.Withintheframeworkofthecompilerconstructioncourse,thestudentsarerequestedtowriteacompilerfromagivenlanguagespecification,usingautomatedtoolssuchasLexandYacc(Mason&Brown,1990).However,suchteachingapproachloosely-couplesthetheoryofscanningandparsing.Inaddition,itconstitutesanambiguousshiftfromtheorytopractice,associatedbytheinherentdifficultiesandthetypicalerrorsofautomatedtools(Mallozzi,2005).Hence,inthispaperwesetanobjectivetotightlycouplescanning,parsingandtranslation,aswellastokeepaconnectionandasmoothtransitionbetweentheoryandpractice.Suchcouplingisbasedonaproposedgenerictoolfortheconstructionofscanners,parsers,andsyntaxdirectedtranslators.Theproposedtoolisusedasaunifyingtoolwithinthefollowingframeworkforteachingcompilers1)Introducecompilation,includingitsdifferentphases.2)Introduceregularexpressionsandcontext-freegrammars.Emphasizetheirrolesinspecifyingthelexicalandsyntacticlevelsofhighlevelprogramminglanguages.3)Introducescanningintermsoffiniteautomata.Emphasizetheroleofautomataasscannersoflanguagesspecifiedbyregularexpressions(definitions).4)Introduceparsingintermsofpushdownstorageautomata.Emphasizetheroleofautomataasparsersoflanguagesspecifiedbycontextfreegrammars.5)Introducetheconceptsofagenericgrammarthatcanbeinstantiatedeitherbyregularexpressionsandcontext-freegrammars.Emphasizeitsroleinconstructingagenericautomaton(scanner-parser).6)Constructthegenericautomatonasascanner.7)Constructthegenericautomatonasaparser.8)Introducetheconceptsofthesyntaxdirectedtranslation.Emphasizetheroleofthetranslationschemes.9)Considertheremainingcompilationphasesintheirsubsequentorder.Extendtheautomatonastype-checker,intermediatecodegeneratorandascodegenerator.TheoutlinedframeworkisconsistentwithACMsCurriculum2001.Itismotivatedbythestrategiesandtheteachingapproachessuggestedin(Aho,2008;Waite,2006).However,theproposedframeworkadoptsaunifiedapproachforteachingtheoryanditspracticalapplication.Suchunificationisachievedbyadoptingagenericgrammarthatcanbeeitherinstantiatedbycontext-freegrammarsorbyregulardefinitions.Suchgrammarisannotatedbyappropriatetranslationschemes.Assuch,theaugmentedgrammaristhentransformedintoanaugmentedgenericautomaton(AGA).ThestatesandthetransitionsofAGAaredefinedbasedoncombiningconceptsfromLRautomata,finiteautomata,withembeddedtranslationschemes(Ahoetal.,2007).Hence,theparsingbehaviorofAGAisgeneric.Itsimulatesfiniteautomata,shiftreduceautomataandsyntaxdirectedtranslator.However,AGAisanondeterministic.Itisefficientlytransformedintoareducedone,calledRAGA,usingaproposedsubsetconstructionapproach.Inaddition,thesubsetconstructionproducesparsingandtranslationtablesthatspecifytheRGAparsing/translationactions,respectiveagivenstateandeachoneoftheinputsymbols.Asimulatoristhenconstructedtosimulatetherun(scanner/parser/translator)ofRGAonstringsderivedfromagenericgrammar.Ourparsingapproachisbasedonpositionparsingautomata(PPA),asproposedin(Jabri,2009,2012).However,itextendsPPAtoactasascanner/parser/translatorandusesdifferentconstructionapproachthathandlesrecursionbyreducedstackactivitiesinawaysimilartothegeneralizedbottomupparsersandthereduction-incorporatedparsers,asproposedin(Ayock,2001;JohnstoneScott&Johnstone,2005)respectively.Inaddition,ithandlesnondeterminisminawaysimilartoSLRparsingasproposedin(Jabri,2012).Theremainderofthispaperisorganizedasfollows.Section2presentspreliminaries.Section3presentstheproposedgenerictoolandtherespectivealgorithmsforitsimplementation.Section4presentsexperimentalresults,followedbyadiscussionandaconclusionthataregiveninSection5andSection6respectively.2.PreliminariesForourfurtherdiscussions,weassumethefollowingdefinitionsbasedontheonesgivenbyAhoetal.(2007)andbyJabri(2012).Thesedefinitionsareusedtospecifythesubsequentphasesofacompilerasfollows:ThespecificationneededforlexicalanalysisandparsingarebasedonregulardefinitionandcontextfreegrammarsasgiveninDefinition1andDefinition2respectively.AunifieddefinitionforbothisbasedonagenericgrammarasgiveninDefinition3.Thespecificationneededfortheremainingcompilerphasesarebasedonsyntaxdirectedtranslationschemes(Ahoetal.,2007)whereprogramfragmentsareembeddedwithintheproductionsofthegenericgrammar.Thesefragmentsareenclosedbetweenbraces(.)anddenotedastranslationschemes.Definition1.Givenanalphabet,aregularexpression(RE)isdefinedasanotationtodescribealllanguagesthatcanbebuiltfromthesymbolsofbyapplyingtheoperations:union(|);concatenation(.)andexponentiation(*).REistheninductivelydefinedasfollows:ThesymbolisREandifxthenxisRE.Letx,ybeRE.ThenREisinductivelydefinedas:xyisRE;x|yisRE;x*isREand(X)isRE.Definition2.Givenanalphabet,aregulardefinition(RD)isasequenceofdefinitionsoftheform:RD1RE1,RD2RE2,RDnREn,whereRDiandREiisdefinedoverRD1,RD2,RDi-1.Definition3.AnAction-annotatedGenericGrammarisdefinedbythe5-tupleAGG=(,N,P,S,TS)thatiseitherinstantiatedbyacontextfreegrammar(CFG)orbyRD.Inaddition,itisannotatedbytranslationschemestospecifyaparticulartranslationasfollows:1)AGGisinstantiatedbyCFG,if:isanalphabetofterminalsymbols.Nisafinitesetofnonterminalsymbols,whereSNisastartingsymbol.Pisafinitesetofproductionsphavingtheformp:AV,whereANandV(N).TSissetoftranslationschemestospecifyparticulartranslationphase,wheretheindividualproductionsareannotatedbysuchschemesasinp:AV:translationscheme.2)AGGisinstantiatedbyRD,if:isanalphabetofsymbols.N=RD1,RD2,RDn,OP,whereRD1,RD2,RDn,isanorderedsetofnonterminalsymbols;SNisastartingsymbolandOParespecialnonterminalsrepresentingtheoperations:|,(),(.)and*.Pisafinitesetofproductionsphavingtheformp:AiREi,whereAiRD1,RD2,RDn,andREidefinedbyapplyingOPover(RD1,RD2,RDi-1).TSisasetoftranslationschemestospecifythetranslationoflexicalentitiesintoappropriatetokensasinp:AiREi:translationscheme.Subsequently,inourfurtherdiscussion,weuseastringasagenerictermtoeitherdenotesstrings,generatedbyRD,orsentencesgeneratedbyCFG.Thesestringsareannotatedbyappropriatetranslationschemes.Example1.LetG=(,N,P,S,TS)beAGGinstantiatedbyRD,where:(a-z,0-9,+,*),(Id,num,op,ws,token,tokenlst)N,P=lettera|b|z,digit0|9,wsblank,idletter(letter|digit)*,numdigit.digit*(.digit)*,op+|*,tokenid|num|op,tokenlsttokenlstwstokenandTSisasetoftranslationschemes.ExamplesforstringsgeneratedbyGare:xy2z,23.5and56.9.ApossibleannotationofGisasfollows:idletter(letter|digit)*:Return(ID),whereIDisanencodingofatokenoftypeid;numdigit.digit*(.digit)*:Return(NUM),whereNUMisanencodingofatokenoftypenumandop+|*:Return(OP),whereOPisanencodingofatokenoftypeop.Example2.LetG=(,N,P,S,TS)beAGGgrammar.ItisinstantiatedbyCFGasfollows:=id,+,*,N=E,T,F,P=EE+T|T,TT*F|F,FidandTSisasetoftranslationschemes.ExamplesforstringsgeneratedbyGare:id*id,id,andid+id*id.ApossibleannotationofGfortypecheckingisasfollows:Fid:Type.F=Type.idandEE+T:Type.E=f(Type.E,Type.T).3.TheProposedGenericToolLetG=(,N,P,S,TS)beanAGGgrammar.Theproposedgenerictool(GCT)isdefinedeitherasascanner,ifGisinstantiatedbyRD,orasaparser,ifGisinstantiatedbyCFG.Inaddition,GCTisdefinedinawaythatpermititstransformationtoatranslatorrespectivetothetranslationschemes(TS),annotatingtheindividualproductionsofG.Assuch,GCThasthestructureshowninFigure1,where:Figure1.ThestructureofGCTAGAisanondeterministicautomatondefinedandconstructedasgivenbyDefinition4andSection3.1.RGAisareducedautomatonobtainedasaresultofapplyingasubsetconstructiononAGAasgiveninSection3.2AsimulatorforRGAconstructedasgiveninSection3.3.Suchsimulatoractseitherasascanner/translatororaparser/translator.OnceastringisfedasaninputtoRGAsimulator,anoutputisthenproducedasconsistingofarespectivesequenceofAGGsproductionreductionsandtheresultsoftheexecutionofthetranslationschemesannotatingtheindividualAGGsproductions.Definition4.AnAugmentedGenericAutomaton(AGA)Let(,N,P,S,TS)beAGGgrammar.AGAisthendefinedbythe5-tuple(),Q,qin,qfin,TA),where:representsstringsgeneratedbytheAGGgrammar.EachgrammarsymbolV(N)isrepresentedbythepair(Vi,Vf)torepresentapredictionandanacceptanceofVinanassumedtranslation.Consequently,TheGCCTstatesrespectivetoeachV(N)aredefinedastheset(qi=Vi,qf=Vf),where:qiisaninitialstateinstantiatedbyViandactsasapredictor(scanner)forV.Thestateqfisafinalone,instantiatedbyVfandactsasitsrespectiveacceptor.InadditionandifVisassociatedwithatranslationscheme,thestateqfisaugmentedbysuchschemeasatranslationactiontobeexecutedupontransitiontoqf.Hence,thesetofAGAstatesisdefinedasQ=(qi=Vi,qf=Vf)|V(N)where,eachstateisinstantiatedbyarespectivegrammarsymbols.(qin=Si)and(qfin=Sf)aretheinitialandfinalstates,instantiatedbythesymbolsrespectivetothestartinggrammarsymboloftheAGGgrammar.TAisasetofthetranslationactionsofAGA.Itconsistsofparsingactionsannotatedbytranslationschemes.Theparsingactionsconsistofmovetransitionsandreductions.Upontransitionsandreductions,theactionspecifiedbysuchschemeisexecutedasanintegralpartoftheparsingaction.ThemoveparsingactionsaredefinedbythesetSPA=(qi,V)=(qj,):translationscheme,where(qi,V)=(qj,)specifiesasubsequentstateqjQforagivenstateqiQandagivengrammarsymbolVT.Upontransitions,aprogramfragmentisperformedasindicatedbytheannotatingtranslationscheme.ThereduceparsingactionsaredefinedbythesetRPA=(q,V)=reduce(r):translationscheme,where(q,V)=reduce(r)definesareductionrule(r),foreveryVN,qQsuchthatqhasbeeninstantiatedbyVfandVistheLHS(r).RPAperformstheindicatedtranslationscheme,Ifthereductionisassociatedwithsuchscheme.ThestatesandtheparsingactionsofAGAaredependentontheproductiontypes;thetypesofthegrammarsymbolsandtheirrespectivepositionsintheindividualproductionsofAGG,TheyareinductivelyconstructedasgiveninSectionAGAConstructionApproachLetG=(,N,P,S,TS)beanAGGgrammar,where:GiseitherinstantiatedbyCFGorRD.Respectively,thesetofproductionsPisgenericandiseitherinstantiatedbygrammarproductionsorregulardefinitions.TheproductionsofCFGareclassifiedintothreetypes:simpleproductions,productionshavingalternativesandproductionshavingembeddedrecursion.GivenpP,thegrammarsymbolsVinpareclassifiedintothefollowingtypes:terminals,rankedterminals,nonterminals,arecursive-head(VisLHS(p)andpisaproductionhavingembeddedrecursion)andarecursive-instance(VRHS(p)andVisLHS(p).Inaddition,eachnonterminalswithrepeatedoccurrencesinRHSofdifferentproductionsisclassifiedasrepeatedinstance.TherighthandsideofRDareregularexpressionsonwhichthefollowingoperationsareapplied:Concatenation;alternation;exponentiation.Consideringaparticularcompilationphase,respectivetranslationschemes(TS)aredefinedandusedtoannotatethesetP.Assumingthattherighthandsides(regularexpressions)ofRDaredecomposedintotheirconstituentsubexpressions,Algorithm1constructsAGAforRD(AGA(RD)aswellasforCFG(AGA(CFG).TheconstructionofAGA(RD)or(AGA(CFG)proceedsaccordingtothesamestepsfromwhichAlgorithm1iscomposed.However,theconstructionofAGA(RD)excludesthestepcoveringembeddedrecursions,whiletheconstructionofAGA(CFG)excludestheonecoveringexponentiation.Algorithm1:AGAConstructionAlgorithmInput:AnAGGgrammarG=(,N,P,S,TS).Output:GAdefinedbythe5-tuple(),Q,qin,qfin,TA)anditsrespectivetransitiongraph.Method:Initially,thestatesofAGAareconstructedasthesetasQ=(qi=Vi,qf=Vf)|V(N).AGAistheninductivelyconstructedasfollows:1)Basis:Let(qi,qf)Qbeanarbitrarystates,denotedasaninitialstateandafinalonerespectively,AGAforthegrammarsymbol(AGA()isthenconstructedasshowninFigure2.Figure2.AGA()Itconstitutesan-transition(qi,)=(qf,):translationscheme)betweenqiandqf,associatedwithatranslationscheme.LetV,AGA(V)isthenconstructedasconsistingoftwostates(Fig.3)withthefollowingtransitions(qi,V)=(qf):translationschemeFigure3.AGA(V)2)Induction:2.1LetpP:LHS(p)RHS(p)beeitherasimpleproductionoraconcatenationofsubexpressions;AGA(p)isthenconstructedasshowninFigure4.Figure4.AGA(p)where:qiistheinitialstateandqithefinalstateofAGA(p).AGA(RHS(p)isanaggregationofAGA1,andAGAnrespectivetotheindividualgrammarsymbolsfromwhichRHS(p)iscomposed.Hence,itisconstructedasshowninFigure5.Figure5.AGA(RHS(p)EachAGAihasqiiandqifasaninitialandfinalstatesrespectively.AGA(p)hasthefollowingtranslationactions:SPA:(qi,)=(q1i):translationscheme,whereq1iisaninitialstateofAGA(RHS(p).SPA:(qnf,)=(qf,):translationschemewhereqnf,isthefinalstateofAGA(RHS(p).SPA:(qif,)=(qi+1i,):translationscheme|i=1,n-1.RPA:(qf,LHS(p)=reduce(LHS(p):translationscheme.2.2LetpP:LHS(p)RHS1(p)|RHSn(p)beeitheraproductionwithalternativerighthandsidesoralternativesubexpressionsRHS1(p),RHS2(p),.,RHSn(p).AGA(p)isthenconstructedasshowninFigure6.Figure6.AGAforaproductionwithalternativesEachalternativeRHSi(p)hasarespectiveAGA(RHSi(p)withinitialandfinalstatesqiiandqifrespectively.TheinitialandthefinalstatesofAGA(p)areqiandqf.AGA(p)hastheactions:SPA:(qi,)=(qji,):translationscheme|j=1,.n,whereqjiistheinitialstateofAGAj.SPA:(qjf,)=(qf,):translationscheme|j=1,.n,whereqjfisthefinalstateofAGAj.RPA:(qf,LHS(p)=reduce(LHS(p):translationscheme.2.3LetpP:LHS(p)RHS(p)beaproductionhavingembeddedrecursion,whereLHS(p)RHS(p)atposition(i).AGAisconstructedasshowninFigure7.Figure7.AGAforaproductionwithembeddedrecursionAGA(p)consistsof:theinitialstateqi,thefinalstateqfandtheAGArespectiveto(RHS(p).AGA(RHS(p)hasthestatesq1i,qi-1f,qrii,qrif,qi+1i,qnf,whereq1iandqnfaretheinitialandfinalstates;qriiandqrifaretheinitialandfinalrespectivetotheembeddedrecursion.AGAactionsareasfollows:SPA:(qi,)=(q1i,):translationscheme:recursion-initialization1,whererecursion-initializationisaprogramsegment,executedduringparsing,thatcreatesastack(qi)initializedwiththesymbolatthetop.SPA:(qnf,)=(qf,):translationschemeSPA:(qi-1f,)=(qrii,):translationschemeSPA:(qrii,)=(qi):translationscheme:recursion-initialization2,whererecuersion-initialization2isaprogramsegment,executedduringparsing,thatinitializesarecursivepathwithareturnaddressqrif,pushedonthetopofstack(qi).RPA:(qf,LHS(p)=reduce(LHS(p):translationschemerecursion-termination,whererecursion-terminationisaprogramsegment,executedduringparsing,thatterminatesarecursivepathbyperformingan-transitiontotheaddressattopofstack(qi),iftop(stack(qi).SPA:(qrif,)=(qi+1i):translationscheme.2.4LetpP:LHS(p)RHS(p)beasetofproductionshaving(AN)RHS(p),whereAisclassifiedasrepeated-instance.AGA(A)isthenconstructedforaselectedinstance.AnAGAforeachoneoftheotherinstanceisconstructedfollowingthestepsforembeddedrecursion.2.5LetpP:LHS(p)RHS(p)beaproduction(regulardefinition)havingasubexpressionr*atposition(i),wherer*RHS(p)atposition(i).AGA(p)isconstructedasshowninFigure8.Figure8.AGAforregulardefinitionsAGA(p)consistsof:theinitialstateq0,thefinalstateqfandAGA(RHS(p)respectiveto(RHS(p).AGA(RHS(p)hasthestatesq1i,qi-1f,AGA(r*),qi+1i,qnf,where:qiiandqifaretheinitialandfinalstatesforAGA(r*);qriiandqrifaretheinitialandfinalrespectivetotheexponentiation.AGAactionsare:SPA:(q0,)=(q1i,):translationschemeSPA:(qnf,)=(qf,):translationschemeSPA:(qi-1f,)=(qrii,):translationschemeSPA:(qrii,)=(qii):translationschemeSPA:(qif,)=(qii):translationschemeSPA:(qif,)=(qrif):translationschemeSPA:(qrii,)=(qrif):translationschemeSPA:(qrif,)=(qi+1i):translationschemeRPA:(qf,LHS(p)=reduce(LHS(p):translationschemeExample3.LetG=(,N,P,S,TS)beGAAgrammarwithsimpleproductions.Where:(id,+,*),(E,T,F)NandP=EE+TT,TT*FF,Fid.AnondeterministicautomatonrepresentingAGArespectivetoGisshowninFigure9.Figure9.AGAforthegrammarofExample3Example4.LetG=(,N,P,S,TS)beGGAgrammarinstantiatedbyregulardefinitionsasgiveninExample1.Fig.10showsanondeterministicautomatonrepresentingAGArespectivetotheproductions:lettera|b|z;digit0|9,idletter(letter|digit)*;tokenid;andtokenlsttoken.Figure10.AGAforthegrammarofExample43.2RAGAConstructionApproachInthissection,weproposeaconstructionapproachforthereducedautomatonRAGAbasedonextensionofthesubsetconstructionalgorithmsgivenin(Ahoetal.,2007;Jabri,2012).Suchextensionisatwofold.First,itcoversawiderclassofgrammarsincludingRDandCFG.Second,ithasadeterministicbehaviorupontheRGAGreduceactions,aswellasuponreturnactionsasdeterminedbyrecursion-termination.Theconstructedautomatonin(Jabri,2012)hasmultipletransitionsandrespectivereductions.Incontrast,accordingtotheproposedapproach,thesetsoffollowsymbolsforthenontermi