計算機(jī)科學(xué)分類-自動機(jī)理論

1ApplicationsofRegularExpressionsUnixRE’sTextProcessingLexicalAnalysis2SomeApplicationsRE’sappearinmanysystems,oftenprivatesoftwarethatneedsasimplelanguagetodescribesequencesofevents.We’lluseJungleeasanexample,thentalkabouttextprocessingandlexicalanalysis.3JungleeStartedinthemid-90’sbythreeofmystudents,AshishGupta,AnandRajaraman,andVenkyHarinarayan.GoalwastointegrateinformationfromWebpages.BoughtbyAmazonwhenYahoo!hiredthemtobuildacomparisonshopperforbooks.4IntegratingWantAdsJunglee’sfirstcontractwastointegrateon-linewantadsintoaqueryabletable.Eachcompanyorganizeditsemploymentpagesdifferently.Worse:theorganizationtypicallychangedweekly.5Junglee’sSolutionTheydevelopedaregular-expressionlanguagefornavigatingwithinapageandamongpages.Inputsymbolswere:Letters,forformingwordslike“salary”.HTMLtags,forfollowingstructureofpage.Links,tojumpbetweenpages.6Junglee’sSolution–(2)EngineerscouldthenwriteRE’stodescribehowtofindkeyinformationataWebsite.E.g.,positiontitle,salary,requirements,…Becausetheyhadalittlelanguage,theycouldincorporatenewsitesquickly,andtheycouldmodifytheirstrategywhenthesitechanged.7RE-BasedSoftwareArchitectureJungleeusedacommonformofarchitecture:UseRE’splusactions(arbitrarycode)asyourinputlanguage.CompileintoaDFAorsimulatedNFA.Eachacceptingstateisassociatedwithanaction,whichisexecutedwhenthatstateisentered.8UNIXRegularExpressionsUNIX,fromthebeginning,usedregularexpressionsinmanyplaces,includingthe“grep”command.Grep=“Global(searchfora)RegularExpressionandPrint.”MostUNIXcommandsuseanextendedREnotationthatstilldefinesonlyregularlanguages.9UNIXRENotation[a1a2…an]isshorthandfora1+a2+…+an.Rangesindicatedbyfirst-dash-lastandbrackets.OrderisASCII.Examples:[a-z]=“anylower-caseletter,”[a-zA-Z]=“anyletter.”Dot=“anycharacter.”10UNIXRENotation–(2)|isusedforunioninsteadof+.But+hasameaning:“oneormoreof.”E+=EE*.Example:[a-z]+=“oneormorelower-caseletters.?=“zerooroneof.”E?=E+ε.Example:[ab]?=“anoptionalaorb.”11Example:TextProcessingRememberourDFAforrecognizingstringsthatendin“ing”?Itwasrathertricky.ButtheREforsuchstringsiseasy:.*ingwherethedotistheUNIX“any”.EvenanNFAiseasy(nextslide).12NFAfor“Endsining”Startanying13LexicalAnalysisThefirstthingacompilerdoesisbreakaprogramintotokens=substringsthattogetherrepresentaunit.Examples:identifiers,reservedwordslike“if,”meaningfulsinglecharacterslike“;”or“+”,multicharacteroperatorslike“<=”.14LexicalAnalysis–(2)UsingatoollikeLexorFlex,onecanwritearegularexpressionforeachdifferentkindoftoken.Example:inUNIXnotation,identifiersaresomethinglike[A-Za-z][A-Za-z0-9]*.EachREhasanassociatedaction.Example:returnacodeforthetokenfound.15TricksforCombiningTokensTherearesomeambiguitiesthatneedtoberesolvedasweconvertRE’stoaDFA.Examples:“if”lookslikeanidentifier,butitisareservedword.<mightbeacomparisonoperator,butiffollowedby=,thenthetokenis<=.16Tricks–(2)ConverttheREforeachtokentoanε–NFA.Eachhasitsownfinalstate.Combinetheseallbyintroducinganewstartstatewithε-transitionstothestartstatesofeachε–NFA.ThenconverttoaDFA.17Tricks–(3)IfaDFAstatehasseveralfinalstatesamongitsmembers,givethempriority.Example:Giveallreservedwordspriorityoveridentifiers,soiftheDFAarrivesatastatethatcontainsfinalstatesforthe“if”ε–NFAaswellasfortheidentifierε–NFA,ifdeclares“if”,notidentifier.18Tricks–(4)It’sabitmorecomplicated,becausetheDFAhastohaveanadditionalpower.Itmustbeabletoreadaninputsymbolandthen,whenitaccepts,putthatsymbolbackontheinputtobereadlater.19Example:Put-BackSuppose“<”isthefirstinputsymbol.Readthenextinputsymbol.Ifitis“=”,acceptanddeclarethetokenis<=.Ifitisanythingelse,putitbackanddeclarethetokenis<.20Example:Put-Back–(2)Suppose“if”h