外文翻译-让我们来做一个编译器

外文原文LETSBUILDACOMPILERByJackW.Crenshaw,Ph.D.PartVII:LEXICALSCANNINGINTRODUCTIONInthelastinstallment,IleftyouwithacompilerthatwouldALMOSTwork,exceptthatwewerestilllimitedtosingle-charactertokens.Thepurposeofthissessionistogetridofthatrestriction,onceandforall.Thismeansthatwemustdealwiththeconceptofthelexicalscanner.MaybeIshouldmentionwhyweneedalexicalscanneratall.afterall,wevebeenabletomanageallrightwithoutone,uptillnow,evenwhenweprovidedformulti-charactertokens.TheONLYreason,really,hastodowithkeywords.Itsafactofcomputerlifethatthesyntaxforakeywordhasthesameformasthatforanyotheridentifier.WecanttelluntilwegetthecompletewordwhetherornotitISakeyword.Forexample,thevariableIFILEandthekeywordIFlookjustalike,untilyougettothethirdcharacter.Intheexamplestodate,wewerealwaysabletomakeadecisionbaseduponthefirstcharacterofthetoken,butthatsnolongerpossiblewhenkeywordsarepresent.WeneedtoknowthatagivenstringisakeywordBEFOREwebegintoprocessit.Andthatswhyweneedascanner.Inthelastsession,Ialsopromisedthatwewouldbeabletoprovidefornormaltokenswithoutmakingwholesalechangestowhatwehavealreadydone.Ididntlie.wecan,asyouwillseelater.ButeverytimeIsetouttoinstalltheseelementsofthesoftwareintotheparserwehavealreadybuilt,Ihadbadfeelingsaboutit.Thewholethingfeltentirelytoomuchlikeaband-aid.Ifinallyfiguredoutwhatwascausingtheproblem:Iwasinstallinglexicalscanningsoftwarewithoutfirstexplainingtoyouwhatscanningisallabout,andwhatthealternativesare.Uptillnow,Ihavestudiouslyavoidedgivingyoualotoftheory,andcertainlynotalternatives.Igenerallydontrespondwelltothetextbooksthatgiveyoutwenty-fivedifferentwaystodosomething,butnoclueastowhichwaybestfitsyourneeds.IvetriedtoavoidthatpitfallbyjustshowingyouONEmethod,thatWORKS.Butthisisanimportantarea.Whilethelexicalscannerishardlythemostexcitingpartofacompiler,itoftenhasthemostprofoundeffectonthegenerallook&feelofthelanguage,sinceafterallitsthepartclosesttotheuser.IhaveaparticularstructureinmindforthescannertobeusedwithKISS.Itfitsthelook&feelthatIwantforthatlanguage.ButitmaynotworkatallforthelanguageYOUREcookingup,sointhisonecaseIfeelthatitsimportantforyoutoknowyouroptions.SoImgoingtodepart,again,frommyusualformat.Inthissessionwellbegettingmuchdeeperthanusualintothebasictheoryoflanguagesandgrammars.IllalsobetalkingaboutareasOTHERthancompilersinwhichlexicalscanningplaysanimportantrole.Finally,Iwillshowyousomealternativesforthestructureofthelexicalscanner.Then,andonlythen,willwegetbacktoourparserfromthelastinstallment.Bearwithme.Ithinkyoullfinditsworththewait.Infact,sincescannershavemanyapplicationsoutsideofcompilers,youmaywellfindthistobethemostusefulsessionforyou.LEXICALSCANNINGLexicalscanningistheprocessofscanningthestreamofinputcharactersandseparatingitintostringscalledtokens.Mostcompilertextsstarthere,anddevoteseveralchapterstodiscussingvariouswaystobuildscanners.Thisapproachhasitsplace,butasyouhavealreadyseen,thereisalotyoucandowithouteverevenaddressingtheissue,andinfactthescannerwellendupwithherewontlookmuchlikewhatthetextsdescribe.Thereason?Compilertheoryand,consequently,theprogramsresultingfromit,mustdealwiththemostgeneralkindofparsingrules.Wedont.Intherealworld,itispossibletospecifythelanguagesyntaxinsuchawaythataprettysimplescannerwillsuffice.Andasalways,KISSisourmotto.Typically,lexicalscanningisdoneinaseparatepartofthecompiler,sothattheparserperseseesonlyastreamofinputtokens.Now,theoreticallyitisnotnecessarytoseparatethisfunctionfromtherestoftheparser.Thereisonlyonesetofsyntaxequationsthatdefinethewholelanguage,sointheorywecouldwritethewholeparserinonemodule.Whytheseparation?Theanswerhasbothpracticalandtheoreticalbases.In1956,NoamChomskydefinedtheChomskyHierarchyofgrammars.Theyare:Type0:Unrestricted(e.g.,English)Type1:Context-SensitiveType2:Context-FreeType3:RegularAfewfeaturesofthetypicalprogramminglanguage(particularlytheolderones,suchasFORTRAN)areType1,butforthemostpartallmodernlanguagescanbedescribedusingonlythelasttwotypes,andthoseareallwellbedealingwithhere.Theneatpartaboutthesetwotypesisthatthereareveryspecificwaystoparsethem.Ithasbeenshownthatanyregulargrammarcanbeparsedusingaparticularformofabstractmachinecalledthestatemachine(finiteautomaton).Wehavealreadyimplementedstatemachinesinsomeofourrecognizers.Similarly,Type2(context-free)grammarscanalwaysbeparsedusingapush-downautomaton(astatemachineaugmentedbyastack).Wehavealsoimplementedthesemachines.Insteadofimplementingaliteralstack,wehavereliedonthebuilt-instackassociatedwithrecursivecodingtodothejob,andthatinfactisthepreferredapproachfortop-downparsing.Now,ithappensthatinreal,practicalgrammars,thepartsthatqualifyasregularexpressionstendtobethelower-levelparts,suchasthedefinitionofanidentifier:=|*Sinceittakesadifferentkindofabstractmachinetoparsethetwotypesofgrammars,itmakessensetoseparatetheselower-levelfunctionsintoaseparatemodule,thelexicalscanner,whichisbuiltaroundtheideaofastatemachine.Theideaistousethesimplestparsingtechniqueneededforthejob.Thereisanother,morepracticalreasonforseparatingscannerfromparser.Weliketothinkoftheinputsourcefileasastreamofcharacters,whichweprocessrighttoleftwithoutbacktracking.Inpracticethatisntpossible.AlmosteverylanguagehascertainkeywordssuchasIF,WHILE,andEND.AsImentionedearlier,wecantreallyknowwhetheragivencharacterstringisakeyword,untilwevereachedtheendofit,asdefinedbyaspaceorotherdelimiter.Sointhatsense,weMUSTsavethestringlongenoughtofindoutwhetherwehaveakeywordornot.Thatsalimitedformofbacktracking.Sothestructureofaconventionalcompilerinvolvessplittingupthefunctionsofthelower-levelandhigher-levelparsing.Thelexicalscannerdealswiththingsatthecharacterlevel,collectingcharactersintostrings,etc.,andpassingthemalongtotheparserproperasindivisibletokens.Itsalsoconsiderednormaltoletthescannerhavethejobofidentifyingkeywords.STATEMACHINESANDALTERNATIVESImentionedthattheregularexpressionscanbeparsedusingastatemachine.Inmostcompilertexts,andindeedinmostcompilersaswell,youwillfindthistakenliterally.Thereistypicallyarealimplementationofthestatemachine,withintegersusedtodefinethecurrentstate,andatableofactionstotakeforeachcombinationofcurrentstateandinputcharacter.IfyouwriteacompilerfrontendusingthepopularUnixtoolsLEXandYACC,thatswhatyoullget.TheoutputofLEXisastatemachineimplementedinC,plusatableofactionscorrespondingtotheinputgrammargiventoLEX.TheYACCoutputissimilar.acannedtable-drivenparser,plusthetablecorrespondingtothelanguagesyntax.Thatisnottheonlychoice,though.Inourpreviousinstallments,youhaveseenoverandoverthatitispossibletoimplementparserswithoutdealingspecificallywithtables,stacks,orstatevariables.Infact,inInstallmentVIwarnedyouthatifyoufindyourselfneedingthesethingsyoumightbedoingsomethingwrong,andnottakingadvantageofthepowerofPascal.Therearebasicallytwowaystodefineastatemachinesstate:explicitly,withastatenumberorcode,andimplicitly,simplybyvirtueofthefactthatImatacertainplaceinthecode(ifitsTuesday,thismustbeBelgium).Wevereliedheavilyontheimplicitapproachesbefore,andIthinkyoullfindthattheyworkwellhere,too.Inpractice,itmaynotevenbenecessarytoHAVEawell-definedlexicalscanner.Thisisntourfirstexperienceatdealingwithmulti-charactertokens.InInstallmentIII,weextendedourparsertoprovideforthem,andwedidntevenNEEDalexicalscanner.Thatwasbecauseinthatnarrowcontext,wecouldalwaystell,justbylookingatthesinglelookaheadcharacter,whetherweweredealingwithanumber,avariable,oranoperator.Ineffect,webuiltadistributedlexicalscanner,usingproceduresGetNameandGetNum.Withkeywordspresent,wecantknowanymorewhatweredealingwith,untiltheentiretokenisread.Thisleadsustoamorelocalizedscanner;although,asyouwillsee,theideaofadistributedscannerstillhasitsmerits.SOMEEXPERIMENTSINSCANNINGBeforegettingbacktoourcompiler,itwillbeusefultoexperimentabitwiththegeneralconcepts.Letsbeginwiththetwodefinitionsmostoftenseeninrealprogramminglanguages:=|*+(Remember,the*indicateszeroormoreoccurencesofthetermsinbrackets,andthe+,oneormore.)WehavealreadydealtwithsimilaritemsinInstallmentIII.Letsbegin(asusual)withabarecradle.Notsurprisingly,wearegoingtoneedanewrecognizer:RecognizeanAlphanumericCharacterfunctionIsAlNum(c:char):boolean;beginIsAlNum:=IsAlpha(c)orIsDigit(c);end;YoucaneasilyverifythattheseroutinesworkbycallingthemfromthemainprogramWriteLn(GetName);Thisprogramwillprintanylegalnametypedin(maximumeightcharacters,sincethatswhatwetoldGetName).Itwillrejectanythingelse.Testtheotherroutinesimilarly.WHITESPACEWealsohavedealtwithembeddedwhitespacebefore,usingthetworoutinesIsWhiteandSkipWhite.Makesurethattheseroutinesareinyourcurrentversionofthecradle,andaddthethelineSkipWhite;attheendofbothGetNameandGetNum.Now,letsdefinethenewprocedure:-LexicalScannerFunctionScan:string;beginifIsAlpha(Look)thenScan:=GetNameelseifIsDigit(Look)thenScan:=GetNumelsebeginScan:=Look;GetChar;end;SkipWhite;end;-(YouwillhavetoaddthedeclarationofthestringTokenatthebeginningoftheprogram.Makeitanyconvenientlength,say16characters.)Now,runtheprogram.Notehowtheinputstringis,indeed,separatedintodistincttokens.STATEMACHINESFortherecord,aparseroutinelikeGetNamedoesindeedimplementastatemachine.Thestateisimplicitinthecurrentpositioninthecode.Averyusefultrickforvisualizingwhatsgoingonisthesyntaxdiagram,orrailroad-trackdiagram.Itsalittledifficulttodrawoneinthismedium,soIllusethemverysparingly,butthefigurebelowshouldgiveyoutheidea:|-Other-Error|Start-Letter-Other-Finish|=,and,buttheycouldbedealtwithasspecialcases.Still,otherlanguageshavemulti-characteroperators,suchasthe:=ofPascalorthe+andofC.Sowhilewemaynotneedmulti-characteroperators,itsnicetoknowhowtogetthemifnecessary.Needlesstosay,wecanhandleoperatorsverymuchthesamewayastheothertokens.Letsstartwitharecognizer:-RecognizeAnyOperatorfunctionIsOp(c:char):boolean;beginIsOp:=cin+,-,*,/,:,=;end;-ItsimportanttonotethatweDONThavetoincludeeverypossibleoperatorinthislist.Forexample,theparethesesarentincluded,noristheterminatingperiod.ThecurrentversionofScanhandlessingle-characteroperatorsjustfineasitis.Thelistaboveincludesonlythosecharactersthatcanappearinmulti-characteroperators.(Forspecificlanguages,ofcourse,thelistcanalwaysbeedited.)Now,letsmodifyScantoread:-LexicalScannerFunctionScan:string;beginwhileLook=CRdoFin;ifIsAlpha(Look)thenScan:=GetNameelseifIsDigit(Look)thenScan:=GetNumelseifIsOp(Look)thenScan:=GetOpelsebeginScan:=Look;GetChar;end;SkipWhite;end;-Trytheprogramnow.Youwillfindthatanycodefragmentsyoucaretothrowatitwillbeneatlybrokenupintoindividualtokens.LISTS,COMMASANDCOMMANDLINESBeforegettingbacktothemainthrustofourstudy,Idliketogetonmysoapboxforamoment.Howmanytimeshaveyouworkedwithaprogramoroperatingsystemthathadrigidrulesabouthowyoumustseparateitemsinalist?(Try,thelasttimeyouusedMSDOS!)Someprogramsrequirespacesasdelimiters,andsomerequirecommas.Worstofall,somerequireboth,indifferentplaces.Mostareprettyunforgivingaboutviolationsoftheirrules.Ithinkthisisinexcusable.Itstooeasytowriteaparserthatwillhandlebothspacesandcommasinaflexibleway.Considerthefollowingprocedure:-SkipOveraCommaprocedureSkipComma;beginSkipWhite;ifLook=,thenbeginGetChar;SkipWhite;end;end;-Thiseight-lineprocedurewillskipoveradelimiterconsistingofanynumber(includingzero)ofspaces,withzerooronecommaembeddedinthestring.TEMPORARILY,changethecalltoSkipWhiteinScantoacalltoSkipComma,andtryinputtingsomelists.Worksnicely,eh?DontyouwishmoresoftwareauthorsknewaboutSkipComma?Fortherecord,IfoundthataddingtheequivalentofSkipCommatomyZ80assembler-languageprogramstookallof6(six)extrabytesofcode.Evenina64Kmachine,thatsnotaveryhighpricetopayforuser-friendliness!IthinkyoucanseewhereImgoinghere.Evenifyouneverwritealineofacompilercodeinyourlife,thereareplacesineveryprogramwhereyoucanusetheconceptsofparsing.Anyprogramthatprocessesacommandlineneedsthem.Infact,ifyouthinkaboutitforabit,youllhavetoconcludethatanytimeyouwriteaprogramthatprocessesuserinputs,youredefiningalanguage.Peoplecommunicatewithlanguages,andthesyntaximplicitinyourprogramdefinesthatlanguage.Therealquestionis:areyougoingtodefineitdeliberatelyandexplicitly,orjustletitturnouttobewhatevertheprogramendsupparsing?Iclaimthatyoullhaveabetter,moreuser-friendlyprogramifyoulltakethetimetodefinethesyntaxexplicitly.Writedownthesyntaxequationsordrawtherailroad-trackdiagrams,andcodetheparserusingthetechniquesIveshownyouhere.Youllendupwithabetterprogram,anditwillbeeasiertowrite,toboot.GETTINGFANCYOK,atthispointwehaveaprettynicelexicalscannerthatwillbreakaninputstreamupintotokens.Wecoulduseitasitstandsandhaveaservicablecompiler.Buttherearesomeotheraspectsoflexicalscanningthatweneedtocover.Themainconsiderationisefficiency.Rememberwhenweweredealingwithsingle-charactertokens,everytestwasacomparisonofasinglecharacter,Look,withabyteconstant.WealsousedtheCasestatementheavily.Withthemulti-charactertokensbeingreturnedbyScan,allthosetestsnowbecomestringcomparisons.Muchslower.Andnotonlyslower,butmoreawkward,sincethereisnostringequivalentoftheCasestatementinPascal.Itseemsespeciallywastefultotestforwhatusedtobesinglecharacters.the=,+,andotheroperators.usingstringcomparisons.Usingstringcomparisonisnotimpossible.RonCainusedjustthatapproachinwritingSmallC.SincewerestickingtotheKISSprinciplehere,wewouldbetrulyjustifiedinsettlingforthisapproach.ButthenIwouldhavefailedtotellyouaboutoneofthekeyapproachesusedinrealcompilers.Youhavetoremember:thelexicalscannerisgoingtobecalleda_LOT_!Onceforeverytokeninthewholesourceprogram,infact.Experimentshaveindicatedthattheaveragecompilerspendsanywherefrom20%to40%ofitstimeinthescannerroutines.Iftherewereeveraplacewhereefficiencydeservesrealconsideration,thisisit.Forthisreason,mostcompilerwritersaskthelexicalscannertodoalittlemorework,bytokenizingtheinputstream.Theideaistomatcheverytokenagainstalistofacceptablekeywordsandoperators,andreturnuniquecodesforeachonerecognized.Inthecaseofordinaryvariablenamesornumbers,wejustreturnacodethatsayswhatkindoftokentheyare,andsavetheactualstringsomewhereelse.Oneofthefirstthingsweregoingtoneedisawaytoidentifykeywords.WecanalwaysdoitwithsuccessiveIFtests,butitsurelywouldbeniceifwehadageneral-purposeroutinethatcouldcompareagivenstringwithatableofkeywords.(Bytheway,werealsogoingtoneedsucharoutinelater,fordealingwithsymboltables.)ThisusuallypresentsaprobleminPascal,becausestandardPascaldoesntallowforarraysofvariablelengths.Itsarealbothertohavetodeclareadifferentsearchroutineforeverytable.StandardPascalalsodoesntallowforinitializingarrays,soyoutendtoseecodelikeTable1:=IF;Table2:=ELSE;Tablen:=END;whichcangetprettyoldiftherearemanykeywords.Fortunately,TurboPascal4.0hasextensionsthateliminatebothoftheseproblems.ConstantarrayscanbedeclaredusingTPstypedconstantfacility,andthevariabledimensionscanbehandledwithitsC-likeextensionsforpointers.First,modifyyourdeclarationslikethis:-TypeDeclarationstypeSymbol=string8;SymTab=array1.1000ofSymbol;TabPtr=SymTab;-(ThedimensionusedinSymTabisnotreal.nostorageisallocatedbythedeclarationitself,andthenumberneedonlybebigenough.)Now,justbeneaththosedeclarations,addthefollowing:-DefinitionofKeywordsandTokenTypesconstKWlist:array1.4ofSymbol=(IF,ELSE,ENDIF,END);-Next,insertthefollowingnewfunction:-TableLookupIftheinputstringmatchesatableentry,returntheentryindex.Ifnot,returnazero.functionLookup(T:TabPtr;s:string;n:integer):integer;vari:integer;found:boolean;beginfound:=false;i:=n;while(i0)andnotfounddoifs=Tithenfound:=trueelsedec(i);Lookup:=i;end;-Totestit,youcantemporarilychangethemainprogramasfollows:-MainProgrambeginReadLn(Token);WriteLn(Lookup(Addr(KWList),Token,4);end.-NoticehowLookupiscalled:TheAddrfunctionsetsupapointertoKWList,whichgetspassedtoLookup.OK,givethisatry.SincewerebypassingScanhere,youllhavetotypethekeywordsinuppercasetogetanymatches.Nowthatwecanrecognizekeywords,thenextthingistoarrangetoreturncodesforthem.Sowhatkindofcodeshouldwereturn?Therearereallyonlytworeasonablechoices.ThisseemslikeanidealapplicationforthePascalenumeratedtype.Forexample,youcandefinesomethinglikeSymType=(IfSym,ElseSym,EndifSym,EndSym,Ident,Number,Operator);andarrangetoreturnavariableofthistype.Letsgiveitatry.Insertthelineaboveintoyourtypedefinitions.Now,addthetwovariabledeclarations:Token:Symtype;CurrentTokenValue:String16;StringTokenofLookModifythescannertoread:-LexicalScannerprocedureScan;vark:integer;beginwhileLook=CRdoFin;ifIsAlpha(Look)thenbeginValue:=GetName;k:=Lookup(Addr(KWlist),Value,4);ifk=0thenToken:=IdentelseToken:=SymType(k-1);endelseifIsDigit(Look)thenbeginValue:=GetNum;Token:=Number;endelseifIsOp(Look)thenbeginValue:=GetOp;Token:=Operator;endelsebeginValue:=Look;Token:=Operator;GetChar;end;SkipWhite;end;-(NoticethatScanisnowaprocedure,notafunction.)Finally,modifythemainprogramtoread:-M