Lex−ALexicalAnalyzerGenerator MM..EE..LLeesskkaannddEE..SScchhmmiiddtt AABBSSTTRRAACCTT Lexhelpswriteprogramswhosecontrolflowisdirectedbyinstancesofregularexpressionsin theinputstream.Itiswellsuitedforeditor-scripttypetransformationsandforsegmentinginputin preparationforaparsingroutine. Lexsourceisatableofregularexpressionsandcorrespondingprogramfragments.Thetableis translatedtoaprogramwhichreadsaninputstream,copyingittoanoutputstreamandpartitioning theinputintostringswhichmatchthegivenexpressions.Aseachsuchstringisrecognizedthecorrespondingprogramfragmentisexecuted.TherecognitionoftheexpressionsisperformedbyadeterministicfiniteautomatongeneratedbyLex.Theprogramfragmentswrittenbytheuserareexecuted intheorderinwhichthecorrespondingregularexpressionsoccurintheinputstream. ThelexicalanalysisprogramswrittenwithLexacceptambiguousspecificationsandchoosethe longestmatchpossibleateachinputpoint.Ifnecessary,substantiallookaheadisperformedonthe input,buttheinputstreamwillbebackeduptotheendofthecurrentpartition,sothattheuserhas generalfreedomtomanipulateit. LexcangenerateanalyzersineitherCorRatfor,alanguagewhichcanbetranslatedautomaticallytoportableFortran.ItisavailableonthePDP-11UNIX,HoneywellGCOS,andIBMOSsys-tems.Thismanual,however,willonlydiscussgeneratinganalyzersinContheUNIXsystem,which istheonlysupportedformofLexunderUNIXVersion7.Lexisdesignedtosimplifyinterfacingwith Yacc,forthosewithaccesstothiscompiler-compilersystem. July21,1975 Lex−ALexicalAnalyzerGenerator MM..EE..LLeesskkaannddEE..SScchhmmiiddtt TableofContents 1.Introduction.1 2.LexSource.3 3.LexRegularExpressions.3 4.LexActions.5 5.AmbiguousSourceRules.7 6.LexSourceDefinitions.8 7.Usage.8 8.LexandYacc.9 9.Examples.10 10.LeftContextSensitivity.11 11.CharacterSet.12 12.SummaryofSourceFormat.12 13.CaveatsandBugs.13 14.Acknowledgments.13 15.References.13 1.Introduction. Lexisaprogramgeneratordesignedforlexicalprocessingofcharacterinputstreams.It acceptsahigh-level,problemorientedspecification forcharacterstringmatching,andproducesaprograminageneralpurposelanguagewhichrecognizesregularexpressions.Theregularexpressions arespecifiedbytheuserinthesourcespecificationsgiventoLex.TheLexwrittencoderecognizestheseexpressionsinaninputstreamandpartitionstheinputstreamintostringsmatchingthe expressions.Attheboundariesbetweenstrings programsectionsprovidedbytheuserareexecuted.TheLexsourcefileassociatestheregular expressionsandtheprogramfragments.Aseach expressionappearsintheinputtotheprogram writtenbyLex,thecorrespondingfragmentisexecuted. Theusersuppliestheadditionalcode beyondexpressionmatchingneededtocomplete histasks,possiblyincludingcodewrittenbyother generators.Theprogramthatrecognizesthe expressionsisgeneratedinthegeneralpurpose programminglanguageemployedfortheuser’s programfragments.Thus,ahighlevelexpression languageisprovidedtowritethestringexpressionstobematchedwhiletheuser’sfreedomto writeactionsisunimpaired.Thisavoidsforcing theuserwhowishestouseastringmanipulation languageforinputanalysistowriteprocessing programsinthesameandofteninappropriate stringhandlinglanguage.

Lexisnotacompletelanguage,butrathera generatorrepresentinganewlanguagefeature whichcanbeaddedtodifferentprogramminglanguages,called‘‘hostlanguages.’’Justasgeneral purposelanguagescanproducecodetorunondifferentcomputerhardware,Lexcanwritecodein differenthostlanguages.Thehostlanguageis usedfortheoutputcodegeneratedbyLexand alsofortheprogramfragmentsaddedbytheuser. Compatiblerun-timelibrariesforthedifferenthost languagesarealsoprovided.ThismakesLex adaptabletodifferentenvironmentsanddifferent users.Eachapplicationmaybedirectedtothe combinationofhardwareandhostlanguageappropriatetothetask,theuser’sbackground,andthe propertiesoflocalimplementations.Atpresent, theonlysupportedhostlanguageisC,although Fortran(intheformofRatfor[2]hasbeenavailableinthepast.LexitselfexistsonUNIX, GCOS,andOS/370;butthecodegeneratedby Lexmaybetakenanywheretheappropriatecompilersexist. Lexturnstheuser’sexpressionsandactions (calledssoouurrcceeinthismemo)intothehostgeneralpurposelanguage;thegeneratedprogramisnamed yyyylleexx..Theyyyylleexxprogramwillrecognizeexpressionsinastream(callediinnppuuttinthismemo)and performthespecifiedactionsforeachexpressionas itisdetected.SeeFigure1. Source→Lex→yylex LEX−2 Input→yylex→Output AnoverviewofLex Figure1 Foratrivialexample,consideraprogramto deletefromtheinputallblanksortabsattheends oflines. %% [\t]+$; isallthatisrequired.Theprogramcontainsa %%delimitertomarkthebeginningoftherules, andonerule.Thisrulecontainsaregularexpressionwhichmatchesoneormoreinstancesofthe charactersblankortab(written\tforvisibility,in accordancewiththeClanguageconvention)just priortotheendofaline.Thebracketsindicate thecharacterclassmadeofblankandtab;the+ indicates‘‘oneormore...’’;andthe$indicates ‘‘endofline,’’asinQED.Noactionisspecified, sotheprogramgeneratedbyLex(yylex)will ignorethesecharacters.Everythingelsewillbe copied.Tochangeanyremainingstringofblanks ortabstoasingleblank,addanotherrule: %% [\t]+$; [\t]+printf(""); Thefiniteautomatongeneratedforthissourcewill scanforbothrulesatonce,observingattheterminationofthestringofblanksortabswhetheror notthereisanewlinecharacter,andexecutingthe desiredruleaction.Thefirstrulematchesall stringsofblanksortabsattheendoflines,and thesecondruleallremainingstringsofblanksor tabs. Lexcanbeusedaloneforsimpletransformations,orforanalysisandstatisticsgatheringon alexicallevel.Lexcanalsobeusedwithaparser generatortoperformthelexicalanalysisphase;it isparticularlyeasytointerfaceLexandYacc[3]. Lexprogramsrecognizeonlyregularexpressions; Yaccwritesparsersthatacceptalargeclassof contextfreegrammars,butrequirealowerlevel analyzertorecognizeinputtokens.Thus,acombinationofLexandYaccisoftenappropriate. Whenusedasapreprocessorforalaterparser generator,Lexisusedtopartitiontheinput stream,andtheparsergeneratorassignsstructure totheresultingpieces.Theflowofcontrolinsuch acase(whichmightbethefirsthalfofacompiler, forexample)isshowninFigure2.Additionalprograms,writtenbyothergeneratorsorbyhand,can beaddedeasilytoprogramswrittenbyLex. lexicalgrammar rulesrules ↓↓ LexYacc ↓↓ Input→yylex→yyparse→Parsedinput LexwithYacc Figure2 Yaccuserswillrealizethatthenameyyyylleexxiswhat Yaccexpectsitslexicalanalyzertobenamed,so thattheuseofthisnamebyLexsimplifiesinterfacing. Lexgeneratesadeterministicfiniteautomatonfromtheregularexpressionsinthesource[4]. Theautomatonisinterpreted,ratherthancompiled,inordertosavespace.Theresultisstilla fastanalyzer.Inparticular,thetimetakenbya Lexprogramtorecognizeandpartitionaninput streamisproportionaltothelengthoftheinput. ThenumberofLexrulesorthecomplexityofthe rulesisnotimportantindeterminingspeed,unless ruleswhichincludeforwardcontextrequireasignificantamountofrescanning.Whatdoesincrease withthenumberandcomplexityofrulesisthe sizeofthefiniteautomaton,andthereforethesize oftheprogramgeneratedbyLex. IntheprogramwrittenbyLex,theuser’s fragments(representingtheaaccttiioonnsstobeperformedaseachregularexpressionisfound)are gatheredascasesofaswitch.Theautomaton interpreterdirectsthecontrolflow.Opportunityis providedfortheusertoinserteitherdeclarations oradditionalstatementsintheroutinecontaining theactions,ortoaddsubroutinesoutsidethis actionroutine. Lexisnotlimitedtosourcewhichcanbe interpretedonthebasisofonecharacterlookahead.Forexample,iftherearetworules,one lookingforaabbandanotherforaabbccddeeffgg,andthe inputstreamisaabbccddeeffhh,Lexwillrecognizeaabband leavetheinputpointerjustbeforeccdd......Such backupismorecostlythantheprocessingofsimplerlanguages.

LEX−3 2.LexSource. ThegeneralformatofLexsourceis: {definitions} %% {rules} %% {usersubroutines} wherethedefinitionsandtheusersubroutinesare oftenomitted.Thesecond%%%%isoptional,but thefirstisrequiredtomarkthebeginningofthe rules.TheabsoluteminimumLexprogramisthus %% (nodefinitions,norules)whichtranslatesintoa programwhichcopiestheinputtotheoutput unchanged. IntheoutlineofLexprogramsshownabove, therruulleessrepresenttheuser’scontroldecisions; theyareatable,inwhichtheleftcolumncontains rreegguullaarreexxpprreessssiioonnss(seesection3)andtheright columncontainsaaccttiioonnss,,programfragmentstobe executedwhentheexpressionsarerecognized. Thusanindividualrulemightappear integerprintf("foundkeywordINT"); tolookforthestringiinntteeggeerrintheinputstream andprintthemessage‘‘foundkeywordINT’’wheneveritappears.InthisexamplethehostprocedurallanguageisCandtheClibraryfunctionpprriinnttff isusedtoprintthestring.Theendoftheexpressionisindicatedbythefirstblankortabcharacter.IftheactionismerelyasingleCexpression, itcanjustbegivenontherightsideoftheline;if itiscompound,ortakesmorethanaline,it shouldbeenclosedinbraces.Asaslightlymore usefulexample,supposeitisdesiredtochangea numberofwordsfromBritishtoAmerican spelling.Lexrulessuchas colourprintf("color"); mechaniseprintf("mechanize"); petrolprintf("gas"); wouldbeastart.Theserulesarenotquite enough,sincethewordppeettrroolleeuummwouldbecome ggaasseeuumm;awayofdealingwiththiswillbe describedlater.

LEX−4 3.LexRegularExpressions. Thedefinitionsofregularexpressionsare verysimilartothoseinQED[5].Aregular expressionspecifiesasetofstringstobematched. Itcontainstextcharacters(whichmatchthecorrespondingcharactersinthestringsbeingcompared) andoperatorcharacters(whichspecifyrepetitions, choices,andotherfeatures).Thelettersofthe alphabetandthedigitsarealwaystextcharacters; thustheregularexpression integer matchesthestringiinntteeggeerrwhereveritappearsand theexpression a57D looksforthestringaa5577DD.. OOppeerraattoorrss..Theoperatorcharactersare "\[]ˆ −?.∗+|()$/{}%<> andiftheyaretobeusedastextcharacters,an escapeshouldbeused.Thequotationmarkoperator(")indicatesthatwhateveriscontained betweenapairofquotesistobetakenastext characters.Thus xyz"++" matchesthestringxxyyzz++++whenitappears.Note thatapartofastringmaybequoted.Itisharmlessbutunnecessarytoquoteanordinarytext character;theexpression "xyz++" isthesameastheoneabove.Thusbyquoting everynon-alphanumericcharacterbeingusedasa textcharacter,theusercanavoidrememberingthe listaboveofcurrentoperatorcharacters,andis safeshouldfurtherextensionstoLexlengthenthe list. Anoperatorcharactermayalsobeturned intoatextcharacterbyprecedingitwith\asin xyz\+\+ whichisanother,lessreadable,equivalentofthe aboveexpressions.Anotheruseofthequoting mechanismistogetablankintoanexpression; normally,asexplainedabove,blanksortabsenda rule.Anyblankcharacternotcontainedwithin[] (seebelow)mustbequoted.SeveralnormalC escapeswith\arerecognized:\nisnewline,\tis tab,and\bisbackspace.Toenter\itself,use\\. Sincenewlineisillegalinanexpression,\nmust beused;itisnotrequiredtoescapetaband backspace.Everycharacterbutblank,tab,newlineandthelistaboveisalwaysatextcharacter. CChhaarraacctteerrccllaasssseess..Classesofcharacterscan bespecifiedusingtheoperatorpair[].Theconstruction[[aabbcc]]matchesasinglecharacter,which maybeaa,bb,orcc.Withinsquarebrackets,most operatormeaningsareignored.Onlythreecharactersarespecial:theseare\−andˆ .The−characterindicatesranges.Forexample, [a−z0−9<>] indicatesthecharacterclasscontainingallthe lowercaseletters,thedigits,theanglebrackets, andunderline.Rangesmaybegivenineither order.Using−betweenanypairofcharacters whicharenotbothuppercaseletters,bothlower caseletters,orbothdigitsisimplementation dependentandwillgetawarningmessage.(E.g., [0−z]inASCIIismanymorecharactersthanitis inEBCDIC).Ifitisdesiredtoincludethecharacter−inacharacterclass,itshouldbefirstorlast; thus [−+0−9] matchesallthedigitsandthetwosigns. Incharacterclasses,theˆ operatormust appearasthefirstcharacteraftertheleftbracket; itindicatesthattheresultingstringistobecomplementedwithrespecttothecomputercharacter set.Thus [ˆ abc] matchesallcharactersexcepta,b,orc,including allspecialorcontrolcharacters;or [ˆ a−zA−Z] isanycharacterwhichisnotaletter.The\characterprovidestheusualescapeswithincharacter classbrackets. AArrbbiittrraarryycchhaarraacctteerr..Tomatchalmostany character,theoperatorcharacter . istheclassofallcharactersexceptnewline. Escapingintooctalispossiblealthoughnonportable: [\40−\176] matchesallprintablecharactersintheASCIIcharacterset,fromoctal40(blank)tooctal176 (tilde). OOppttiioonnaalleexxpprreessssiioonnss..Theoperator??indicatesanoptionalelementofanexpression.Thus ab?c matcheseitheraaccoraabbcc. RReeppeeaatteeddeexxpprreessssiioonnss..Repetitionsofclasses areindicatedbytheoperators∗∗and++. aa∗∗ isanynumberofconsecutiveaacharacters,includingzero;while a+ isoneormoreinstancesofaa..Forexample, [a−z]+ isallstringsoflowercaseletters.And [A−Za−z][A−Za−z0−9]∗ indicatesallalphanumericstringswithaleading alphabeticcharacter.Thisisatypicalexpression forrecognizingidentifiersincomputerlanguages. AAlltteerrnnaattiioonnaannddGGrroouuppiinngg..Theoperator| indicatesalternation: (ab|cd) matcheseitheraabborccdd..Notethatparenthesesare usedforgrouping,althoughtheyarenotnecessary ontheoutsidelevel; LEX−5 ab|cd wouldhavesufficed.Parenthesescanbeusedfor morecomplexexpressions: (ab|cd+)?(ef)∗ matchessuchstringsasaabbeeffeeff,eeffeeffeeff,ccddeeff,orccdddddd; butnotaabbcc,aabbccdd,oraabbccddeeff. CCoonntteexxttsseennssiittiivviittyy..Lexwillrecognizea smallamountofsurroundingcontext.Thetwo simplestoperatorsforthisareˆ ˆ and$$.Ifthefirst characterofanexpressionisˆ ˆ ,theexpressionwill onlybematchedatthebeginningofaline(aftera newlinecharacter,oratthebeginningoftheinput stream).Thiscanneverconflictwiththeother meaningofˆ ˆ ,complementationofcharacter classes,sincethatonlyapplieswithinthe[]operators.Iftheverylastcharacteris$$,theexpression willonlybematchedattheendofaline(when immediatelyfollowedbynewline).Thelatter operatorisaspecialcaseofthe//operatorcharacter,whichindicatestrailingcontext.Theexpression ab/cd matchesthestringaabb,butonlyiffollowedbyccdd.. Thus ab$ isthesameas ab/\n LeftcontextishandledinLexbyssttaarrttccoonnddiittiioonnss asexplainedinsection10.Ifaruleisonlytobe executedwhentheLexautomatoninterpreterisin startconditionxx,,theruleshouldbeprefixedby <x> usingtheanglebracketoperatorcharacters.Ifwe considered‘‘beingatthebeginningofaline’’tobe startconditionOONNEE,thentheˆ operatorwouldbe equivalentto <ONE> Startconditionsareexplainedmorefullylater. RReeppeettiittiioonnssaannddDDeefifinniittiioonnss..Theoperators {}specifyeitherrepetitions(iftheyenclosenumbers)ordefinitionexpansion(iftheyenclosea name).Forexample {digit} looksforapredefinedstringnamedddiiggiittand insertsitatthatpointintheexpression.ThedefinitionsaregiveninthefirstpartoftheLexinput, beforetherules.Incontrast, a{1,5} looksfor1to5occurrencesofaa. Finally,initial%%isspecial,beingtheseparatorforLexsourcesegments.

LEX−6 4.LexActions. Whenanexpressionwrittenasaboveis matched,Lexexecutesthecorrespondingaction. ThissectiondescribessomefeaturesofLexwhich aidinwritingactions.Notethatthereisadefault action,whichconsistsofcopyingtheinputtothe output.Thisisperformedonallstringsnototherwisematched.ThustheLexuserwhowishesto absorbtheentireinput,withoutproducingany output,mustproviderulestomatcheverything. WhenLexisbeingusedwithYacc,thisisthenormalsituation.Onemayconsiderthatactionsare whatisdoneinsteadofcopyingtheinputtothe output;thus,ingeneral,arulewhichmerely copiescanbeomitted.Also,acharactercombinationwhichisomittedfromtherulesandwhich appearsasinputislikelytobeprintedontheoutput,thuscallingattentiontothegapintherules. Oneofthesimplestthingsthatcanbedone istoignoretheinput.SpecifyingaCnullstatement,;;asanactioncausesthisresult.Afrequent ruleis [\t\n]; whichcausesthethreespacingcharacters(blank, tab,andnewline)tobeignored. Anothereasywaytoavoidwritingactionsis theactioncharacter|,whichindicatesthatthe actionforthisruleistheactionforthenextrule. Thepreviousexamplecouldalsohavebeenwritten

""
"\t"
"\n"

withthesameresult,althoughindifferentstyle. Thequotesaround\nand\tarenotrequired. Inmorecomplexactions,theuserwilloften wanttoknowtheactualtextthatmatchedsome expressionlike[[aa−−zz]]++.Lexleavesthistextinan externalcharacterarraynamedyyyytteexxtt..Thus,to printthenamefound,arulelike [a−z]+printf("%s",yytext); willprintthestringinyyyytteexxtt..TheCfunction pprriinnttffacceptsaformatargumentanddatatobe printed;inthiscase,theformatis‘‘printstring’’ (%indicatingdataconversion,andssindicating stringtype),andthedataarethecharactersin yyyytteexxtt..Sothisjustplacesthematchedstringon theoutput.Thisactionissocommonthatitmay bewrittenasECHO: [a−z]+ECHO; isthesameastheabove.Sincethedefaultaction isjusttoprintthecharactersfound,onemightask whygivearule,likethisone,whichmerelyspecifiesthedefaultaction?Suchrulesareoften requiredtoavoidmatchingsomeotherrulewhich isnotdesired.Forexample,ifthereisarule whichmatchesrreeaadditwillnormallymatchthe instancesofrreeaaddcontainedinbbrreeaaddorrreeaaddjjuusstt;to avoidthis,aruleoftheform[[aa−−zz]]++isneeded.

Thisisexplainedfurtherbelow. Sometimesitismoreconvenienttoknowthe endofwhathasbeenfound;henceLexalsoprovidesacountyyyylleennggofthenumberofcharacters matched.Tocountboththenumberofwordsand thenumberofcharactersinwordsintheinput, theusermightwrite [a−zA−Z]+{words++;chars+=yyleng;} whichaccumulatesincchhaarrssthenumberofcharactersinthewordsrecognized.Thelastcharacterin thestringmatchedcanbeaccessedby yytext[yyleng−1] Occasionally,aLexactionmaydecidethata rulehasnotrecognizedthecorrectspanofcharacters.Tworoutinesareprovidedtoaidwiththis situation.First,yyyymmoorree(())canbecalledtoindicatethatthenextinputexpressionrecognizedis tobetackedontotheendofthisinput.Normally,thenextinputstringwouldoverwritethe currententryinyyyytteexxtt..Second,yyyylleessss((nn))maybe calledtoindicatethatnotallthecharacters matchedbythecurrentlysuccessfulexpressionare wantedrightnow.Theargumentnnindicatesthe numberofcharactersinyyyytteexxtttoberetained. Furthercharacterspreviouslymatchedare returnedtotheinput.Thisprovidesthesamesort oflookaheadofferedbythe/operator,butina differentform. EExxaammppllee::Consideralanguagewhichdefines astringasasetofcharactersbetweenquotation (")marks,andprovidesthattoincludea"ina stringitmustbeprecededbya\.Theregular expressionwhichmatchesthatissomewhatconfusing,sothatitmightbepreferabletowrite \"[ˆ "]∗{ if(yytext[yyleng−1]==′\\′) yymore(); else ...normaluserprocessing } whichwill,whenfacedwithastringsuchas ""aabbcc\\""ddeeff""firstmatchthefivecharacters""aabbcc\\; thenthecalltoyyyymmoorree(())willcausethenextpart ofthestring,""ddeeff,tobetackedontheend.Note thatthefinalquoteterminatingthestringshould bepickedupinthecodelabeled‘‘normalprocessing’’. Thefunctionyyyylleessss(())mightbeusedto reprocesstextinvariouscircumstances.Consider theCproblemofdistinguishingtheambiguityof ‘‘=−a’’.Supposeitisdesiredtotreatthisas‘‘=− a’’butprintamessage.Arulemightbe =−[a−zA−Z]{ printf("Operator(=−)ambiguous\n"); yyless(yyleng−1); ...actionfor=−... } whichprintsamessage,returnstheletterafterthe LEX−7 operatortotheinputstream,andtreatstheoperatoras‘‘=−’’.Alternativelyitmightbedesiredto treatthisas‘‘=−a’’.Todothis,justreturnthe minussignaswellasthelettertotheinput: =−[a−zA−Z]{ printf("Operator(=−)ambiguous\n"); yyless(yyleng−2); ...actionfor=... } willperformtheotherinterpretation.Notethat theexpressionsforthetwocasesmightmoreeasily bewritten =−/[A−Za−z] inthefirstcaseand =/−[A−Za−z] inthesecond;nobackupwouldberequiredinthe ruleaction.Itisnotnecessarytorecognizethe wholeidentifiertoobservetheambiguity.The possibilityof‘‘=−3’’,however,makes =−/[ˆ \t\n] astillbetterrule. Inadditiontotheseroutines,LexalsopermitsaccesstotheI/Oroutinesituses.Theyare: 1)iinnppuutt(())whichreturnsthenextinputcharacter; 2)oouuttppuutt((cc))whichwritesthecharacterccon theoutput;and 3)uunnppuutt((cc))pushesthecharacterccbackonto theinputstreamtobereadlaterbyiinnppuutt(()).. Bydefaulttheseroutinesareprovidedasmacro definitions,buttheusercanoverridethemand supplyprivateversions.Theseroutinesdefinethe relationshipbetweenexternalfilesandinternal characters,andmustallberetainedormodified consistently.Theymayberedefined,tocause inputoroutputtobetransmittedtoorfrom strangeplaces,includingotherprogramsorinternalmemory;butthecharactersetusedmustbe consistentinallroutines;avalueofzeroreturned byiinnppuuttmustmeanendoffile;andtherelationshipbetweenuunnppuuttandiinnppuuttmustberetainedor theLexlookaheadwillnotwork.Lexdoesnot lookaheadatallifitdoesnothaveto,butevery ruleendingin++∗∗??or$$orcontaining//implies lookahead.Lookaheadisalsonecessarytomatch anexpressionthatisaprefixofanotherexpression.Seebelowforadiscussionofthecharacter setusedbyLex.ThestandardLexlibrary imposesa100characterlimitonbackup. AnotherLexlibraryroutinethattheuser willsometimeswanttoredefineisyyyywwrraapp(())which iscalledwheneverLexreachesanend-of-file.If yyyywwrraappreturnsa1,Lexcontinueswiththenormal wrapuponendofinput.Sometimes,however,itis convenienttoarrangeformoreinputtoarrive fromanewsource.Inthiscase,theusershould provideayyyywwrraappwhicharrangesfornewinput andreturns0.ThisinstructsLextocontinueprocessing.Thedefaultyyyywwrraappalwaysreturns1. Thisroutineisalsoaconvenientplaceto printtables,summaries,etc.attheendofaprogram.Notethatitisnotpossibletowriteanormalrulewhichrecognizesend-of-file;theonly accesstothisconditionisthroughyyyywwrraapp..In fact,unlessaprivateversionofiinnppuutt(())issupplied afilecontainingnullscannotbehandled,sincea valueof0returnedbyiinnppuuttistakentobeend-of-file.

LEX−8 5.AmbiguousSourceRules. Lexcanhandleambiguousspecifications. Whenmorethanoneexpressioncanmatchthe currentinput,Lexchoosesasfollows: 1)Thelongestmatchispreferred. 2)Amongruleswhichmatchedthesame numberofcharacters,therulegivenfirstis preferred. Thus,supposetherules integerkeywordaction...; [a−z]+identifieraction...; tobegiveninthatorder.Iftheinputisiinntteeggeerrss, itistakenasanidentifier,because[[aa−−zz]]++matches 8characterswhileiinntteeggeerrmatchesonly7.Ifthe inputisiinntteeggeerr,bothrulesmatch7characters, andthekeywordruleisselectedbecauseitwas givenfirst.Anythingshorter(e.g.iinntt)willnot matchtheexpressioniinntteeggeerrandsotheidentifier interpretationisused. Theprincipleofpreferringthelongest matchmakesrulescontainingexpressionslike..∗∗ dangerous.Forexample, ′.∗′ mightseemagoodwayofrecognizingastringin singlequotes.Butitisaninvitationfortheprogramtoreadfarahead,lookingforadistantsingle quote.Presentedwiththeinput ′first′quotedstringhere,′second′here theaboveexpressionwillmatch ′first′quotedstringhere,′second′ whichisprobablynotwhatwaswanted.Abetter ruleisoftheform ′[ˆ ′\n]∗′ which,ontheaboveinput,willstopafter′′fifirrsstt′′. Theconsequencesoferrorslikethisaremitigated bythefactthatthe..operatorwillnotmatch newline.Thusexpressionslike..∗∗stoponthecurrentline.Don’ttrytodefeatthiswithexpressions like[[..\\nn]]++orequivalents;theLexgeneratedprogramwilltrytoreadtheentireinputfile,causing internalbufferoverflows. NotethatLexisnormallypartitioningthe inputstream,notsearchingforallpossible matchesofeachexpression.Thismeansthateach characterisaccountedforonceandonlyonce.For example,supposeitisdesiredtocountoccurrences ofbothsshheeandhheeinaninputtext.SomeLex rulestodothismightbe shes++; heh++; \n| .; wherethelasttworulesignoreeverythingbesides hheeandsshhee.Rememberthat.doesnotinclude newline.Sincesshheeincludeshhee,Lexwillnormally nnoottrecognizetheinstancesofhheeincludedinsshhee, sinceonceithaspassedasshheethosecharactersare gone. Sometimestheuserwouldliketooverride thischoice.TheactionREJECTmeans‘‘godo thenextalternative.’’Itcauseswhateverrulewas secondchoiceafterthecurrentruletobeexecuted. Thepositionoftheinputpointerisadjusted accordingly.Supposetheuserreallywantsto counttheincludedinstancesofhhee: she{s++;REJECT;} he{h++;REJECT;} \n| .; theserulesareonewayofchangingtheprevious exampletodojustthat.Aftercountingeach expression,itisrejected;wheneverappropriate, theotherexpressionwillthenbecounted.Inthis example,ofcourse,theusercouldnotethatsshhee includeshheebutnotviceversa,andomitthe REJECTactiononhhee;inothercases,however,it wouldnotbepossibleaprioritotellwhichinput characterswereinbothclasses. Considerthetworules a[bc]+{...;REJECT;} a[cd]+{...;REJECT;} Iftheinputisaabb,onlythefirstrulematches,and onaaddonlythesecondmatches.Theinputstring aaccccbbmatchesthefirstruleforfourcharactersand thenthesecondruleforthreecharacters.Incontrast,theinputaaccccddagreeswiththesecondrule forfourcharactersandthenthefirstruleforthree. Ingeneral,REJECTisusefulwheneverthe purposeofLexisnottopartitiontheinputstream buttodetectallexamplesofsomeitemsinthe input,andtheinstancesoftheseitemsmayoverlaporincludeeachother.Supposeadigramtable oftheinputisdesired;normallythedigramsoverlap,thatisthewordtthheeisconsideredtocontain bothtthhandhhee.Assumingatwo-dimensional arraynamedddiiggrraammtobeincremented,theappropriatesourceis %% [a−z][a−z]{digram[yytext[0]][yytext[1]]++;REJECT;} \n; wheretheREJECTisnecessarytopickupaletter pairbeginningateverycharacter,ratherthanat everyothercharacter.

LEX−9 6.LexSourceDefinitions. RemembertheformatoftheLexsource: {definitions} %% {rules} %% {userroutines} Sofaronlytheruleshavebeendescribed.The userneedsadditionaloptions,though,todefine variablesforuseinhisprogramandforuseby Lex.Thesecangoeitherinthedefinitionssection orintherulessection. RememberthatLexisturningtherulesinto aprogram.AnysourcenotinterceptedbyLexis copiedintothegeneratedprogram.Thereare threeclassesofsuchthings. 1)AnylinewhichisnotpartofaLexruleor actionwhichbeginswithablankortabis copiedintotheLexgeneratedprogram. Suchsourceinputpriortothefirst%% delimiterwillbeexternaltoanyfunctionin thecode;ifitappearsimmediatelyafterthe first%%,itappearsinanappropriateplace fordeclarationsinthefunctionwrittenby Lexwhichcontainstheactions.Thismaterialmustlooklikeprogramfragments,and shouldprecedethefirstLexrule. Asasideeffectoftheabove,lineswhich beginwithablankortab,andwhichcontainacomment,arepassedthroughtothe generatedprogram.Thiscanbeusedto includecommentsineithertheLexsource orthegeneratedcode.Thecomments shouldfollowthehostlanguageconvention. 2)Anythingincludedbetweenlinescontaining only%%{{and%%}}iscopiedoutasabove. Thedelimitersarediscarded.Thisformat permitsenteringtextlikepreprocessorstatementsthatmustbeginincolumn1,orcopyinglinesthatdonotlooklikeprograms. 3)Anythingafterthethird%%delimiter, regardlessofformats,etc.,iscopiedout aftertheLexoutput. DefinitionsintendedforLexaregivenbefore thefirst%%delimiter.Anylineinthissection notcontainedbetween%{and%},andbegining incolumn1,isassumedtodefineLexsubstitution strings.Theformatofsuchlinesis nametranslation anditcausesthestringgivenasatranslationto beassociatedwiththename.Thenameand translationmustbeseparatedbyatleastone blankortab,andthenamemustbeginwithaletter.Thetranslationcanthenbecalledoutbythe {name}syntaxinarule.Using{D}forthedigits and{E}foranexponentfield,forexample,might abbreviaterulestorecognizenumbers:

D[0−9] E[DEde][−+]?{D}+ %% {D}+printf("integer"); {D}+"."{D}∗({E})?| {D}∗"."{D}+({E})?| {D}+{E} Notethefirsttworulesforrealnumbers;both requireadecimalpointandcontainanoptional exponentfield,butthefirstrequiresatleastone digitbeforethedecimalpointandthesecond requiresatleastonedigitafterthedecimalpoint. TocorrectlyhandletheproblemposedbyaFortranexpressionsuchas3355..EEQQ..II,whichdoesnot containarealnumber,acontext-sensitiverule suchas [0−9]+/"."EQprintf("integer"); couldbeusedinadditiontothenormalrulefor integers. Thedefinitionssectionmayalsocontain othercommands,includingtheselectionofahost language,acharactersettable,alistofstartconditions,oradjustmentstothedefaultsizeofarrays withinLexitselfforlargersourceprograms.These possibilitiesarediscussedbelowunder‘‘Summary ofSourceFormat,’’section12.

LEX−10 7.Usage. TherearetwostepsincompilingaLex sourceprogram.First,theLexsourcemustbe turnedintoageneratedprograminthehostgeneralpurposelanguage.Thenthisprogrammust becompiledandloaded,usuallywithalibraryof Lexsubroutines.Thegeneratedprogramisona filenamedlleexx..yyyy..cc.TheI/Olibraryisdefinedin termsoftheCstandardlibrary[6]. TheCprogramsgeneratedbyLexare slightlydifferentonOS/370,becausetheOScompilerislesspowerfulthantheUNIXorGCOS compilers,anddoeslessatcompiletime.CprogramsgeneratedonGCOSandUNIXarethe same. UUNNIIXX..Thelibraryisaccessedbytheloader flag−−llll.Soanappropriatesetofcommandsis lexsourcecclex.yy.c−ll Theresultingprogramisplacedontheusualfile aa..oouuttforlaterexecution.TouseLexwithYacc seebelow.AlthoughthedefaultLexI/Oroutines usetheCstandardlibrary,theLexautomata themselvesdonotdoso;ifprivateversionsof iinnppuutt,,oouuttppuuttanduunnppuuttaregiven,thelibrarycan beavoided.

LEX−11 8.LexandYacc. IfyouwanttouseLexwithYacc,notethat whatLexwritesisaprogramnamedyyyylleexx(()),,the namerequiredbyYaccforitsanalyzer.Normally, thedefaultmainprogramontheLexlibrarycalls thisroutine,butifYaccisloaded,anditsmain programisused,Yaccwillcallyyyylleexx(())..Inthis caseeachLexruleshouldendwith return(token); wheretheappropriatetokenvalueisreturned.An easywaytogetaccesstoYacc’snamesfortokens istocompiletheLexoutputfileaspartofthe Yaccoutputfilebyplacingtheline #include"lex.yy.c" inthelastsectionofYaccinput.Supposingthe grammartobenamed‘‘good’’andthelexicalrules tobenamed‘‘better’’theUNIXcommand sequencecanjustbe: yaccgood lexbetter ccy.tab.c−ly−ll TheYacclibrary(−ly)shouldbeloadedbefore theLexlibrary,toobtainamainprogramwhich invokestheYaccparser.ThegenerationsofLex andYaccprogramscanbedoneineitherorder.

LEX−12 9.Examples. Asatrivialproblem,considercopyingan inputfilewhileadding3toeverypositivenumber divisibleby7.HereisasuitableLexsourceprogram %% intk; [0−9]+{ k=atoi(yytext); if(k%7==0) printf("%d",k+3); else printf("%d",k); } todojustthat.Therule[0−9]+recognizes stringsofdigits;aattooiiconvertsthedigitstobinary andstorestheresultinkk..Theoperator% (remainder)isusedtocheckwhetherkkisdivisible by7;ifitis,itisincrementedby3asitiswritten out.Itmaybeobjectedthatthisprogramwill altersuchinputitemsas4499..6633orXX77.Furthermore,itincrementstheabsolutevalueofallnegativenumbersdivisibleby7.Toavoidthis,just addafewmorerulesaftertheactiveone,ashere: %% intk; −?[0−9]+{ k=atoi(yytext); printf("%d",k%7==0?k+3:k); } −?[0−9.]+ECHO; [A-Za-z][A-Za-z0-9]+ECHO; Numericalstringscontaininga‘‘.’’orprecededby aletterwillbepickedupbyoneofthelasttwo rules,andnotchanged.Theiiff−−eellsseehasbeen replacedbyaCconditionalexpressiontosave space;theformaa??bb::ccmeans‘‘ifaathenbbelsecc’’. Foranexampleofstatisticsgathering,here isaprogramwhichhistogramsthelengthsof words,whereawordisdefinedasastringofletters. intlengs[100]; %% [a−z]+lengs[yyleng]++; .| \n; %% yywrap() { inti; printf("LengthNo.words\n"); for(i=0;i<100;i++) if(lengs[i]>0) printf("%5d%10d\n",i,lengs[i]); return(1); } Thisprogramaccumulatesthehistogram,while producingnooutput.Attheendoftheinputit printsthetable.Thefinalstatementrreettuurrnn((11));; indicatesthatLexistoperformwrapup.If yyyywwrraappreturnszero(false)itimpliesthatfurther inputisavailableandtheprogramistocontinue readingandprocessing.Toprovideayyyywwrraappthat neverreturnstruecausesaninfiniteloop. Asalargerexample,herearesomepartsof aprogramwrittenbyN.L.Schryertoconvert doubleprecisionFortrantosingleprecisionFortran.BecauseFortrandoesnotdistinguishupper andlowercaseletters,thisroutinebeginsbydefiningasetofclassesincludingbothcasesofeachletter: a[aA] b[bB] c[cC] ... z[zZ] Anadditionalclassrecognizeswhitespace: W[\t]∗ Thefirstrulechanges‘‘doubleprecision’’to‘‘real’’, or‘‘DOUBLEPRECISION’’to‘‘REAL’’. {d}{o}{u}{b}{l}{e}{W}{p}{r}{e}{c}{i}{s}{i}{o}{n}{ printf(yytext[0]==′d′?"real":"REAL"); } Careistakenthroughoutthisprogramtopreserve thecase(upperorlower)oftheoriginalprogram. Theconditionaloperatorisusedtoselectthe properformofthekeyword.Thenextrulecopies continuationcardindicationstoavoidconfusing themwithconstants: ˆ ""[ˆ 0]ECHO; Intheregularexpression,thequotessurroundthe blanks.Itisinterpretedas‘‘beginningofline, thenfiveblanks,thenanythingbutblankorzero.’’ Notethetwodifferentmeaningsofˆ ˆ .Therefollow somerulestochangedoubleprecisionconstantsto ordinaryfloatingconstants. [0−9]+{W}{d}{W}[+−]?{W}[0−9]+| [0−9]+{W}"."{W}{d}{W}[+−]?{W}[0−9]+| "."{W}[0−9]+{W}{d}{W}[+−]?{W}[0−9]+{ /∗convertconstants∗/ for(p=yytext;∗p!=0;p++) { if(∗p==′d′||∗p==′D′) ∗p=+′e′−′d′; ECHO; } Afterthefloatingpointconstantisrecognized,itis scannedbytheffoorrlooptofindtheletterddorDD. Theprogramthanadds′′ee′′−−′′dd′′,whichconvertsit tothenextletterofthealphabet.Themodified constant,nowsingle-precision,iswrittenout again.Therefollowaseriesofnameswhichmust berespelledtoremovetheirinitialdd.Byusingthe arrayyyyytteexxttthesameactionsufficesforallthe names(onlyasampleofaratherlonglistisgiven here). {d}{s}{i}{n}| LEX−13 {d}{c}{o}{s}| {d}{s}{q}{r}{t}| {d}{a}{t}{a}{n}| ... {d}{f}{l}{o}{a}{t}printf("%s",yytext+1); Anotherlistofnamesmusthaveinitialddchanged toinitialaa: {d}{l}{o}{g}| {d}{l}{o}{g}10| {d}{m}{i}{n}1| {d}{m}{a}{x}1{ yytext[0]=+′a′−′d′; ECHO; } Andoneroutinemusthaveinitialddchangedto initialrr: {d}1{m}{a}{c}{h}{yytext[0]=+′r′−′d′; Toavoidsuchnamesasddssiinnxxbeingdetectedas instancesofddssiinn,somefinalrulespickuplonger wordsasidentifiersandcopysomesurvivingcharacters: [A−Za−z][A−Za−z0−9]∗| [0−9]+| \n| . ECHO; Notethatthisprogramisnotcomplete;itdoes notdealwiththespacingproblemsinFortranor withtheuseofkeywordsasidentifiers.

LEX−14 10.LeftContextSensitivity. Sometimesitisdesirabletohaveseveralsets oflexicalrulestobeappliedatdifferenttimesin theinput.Forexample,acompilerpreprocessor mightdistinguishpreprocessorstatementsand analyzethemdifferentlyfromordinarystatements. Thisrequiressensitivitytopriorcontext,andthere areseveralwaysofhandlingsuchproblems.Theˆ ˆ operator,forexample,isapriorcontextoperator, recognizingimmediatelyprecedingleftcontextjust as$$recognizesimmediatelyfollowingrightcontext.Adjacentleftcontextcouldbeextended,to produceafacilitysimilartothatforadjacentright context,butitisunlikelytobeasuseful,since oftentherelevantleftcontextappearedsometime earlier,suchasatthebeginningofaline. Thissectiondescribesthreemeansofdealingwithdifferentenvironments:asimpleuseof flags,whenonlyafewruleschangefromoneenvironmenttoanother,theuseofssttaarrttccoonnddiittiioonnsson rules,andthepossibilityofmakingmultiplelexical analyzersallruntogether.Ineachcase,thereare ruleswhichrecognizetheneedtochangetheenvironmentinwhichthefollowinginputtextisanalyzed,andsetsomeparametertoreflectthe change.Thismaybeaflagexplicitlytestedby theuser’sactioncode;suchaflagisthesimplest wayofdealingwiththeproblem,sinceLexisnot involvedatall.Itmaybemoreconvenient,however,tohaveLexremembertheflagsasinitialconditionsontherules.Anyrulemaybeassociated withastartcondition.Itwillonlyberecognized whenLexisinthatstartcondition.Thecurrent startconditionmaybechangedatanytime. Finally,ifthesetsofrulesforthedifferentenvironmentsareverydissimilar,claritymaybebest achievedbywritingseveraldistinctlexicalanalyzers,andswitchingfromonetoanotherasdesired. Considerthefollowingproblem:copythe inputtotheoutput,changingthewordmmaaggiiccto fifirrssttoneverylinewhichbeganwiththeletteraa, changingmmaaggiicctosseeccoonnddoneverylinewhich beganwiththeletterbb,andchangingmmaaggiiccto tthhiirrddoneverylinewhichbeganwiththelettercc. Allotherwordsandallotherlinesareleft unchanged. Theserulesaresosimplethattheeasiest waytodothisjobiswithaflag: intflag; %% ˆ a{flag=′a′;ECHO;} ˆ b{flag=′b′;ECHO;} ˆ c{flag=′c′;ECHO;} \n{flag=0;ECHO;} magic{ switch(flag) { case′a′:printf("first");break; case′b′:printf("second");break; case′c′:printf("third");break; default:ECHO;break; } } shouldbeadequate. Tohandlethesameproblemwithstartconditions,eachstartconditionmustbeintroducedto Lexinthedefinitionssectionwithalinereading %Startname1name2... wheretheconditionsmaybenamedinanyorder. ThewordSSttaarrttmaybeabbreviatedtossorSS.The conditionsmaybereferencedattheheadofarule withthe<>brackets: <name1>expression isarulewhichisonlyrecognizedwhenLexisin thestartconditionnnaammee11.Toenterastartcondition,executetheactionstatement BEGINname1; whichchangesthestartconditiontonnaammee11.To resumethenormalstate, BEGIN0; resetstheinitialconditionoftheLexautomaton interpreter.Arulemaybeactiveinseveralstart conditions: <name1,name2,name3> isalegalprefix.Anyrulenotbeginningwiththe <>prefixoperatorisalwaysactive. Thesameexampleasbeforecanbewritten: %STARTAABBCC %% ˆ a{ECHO;BEGINAA;} ˆ b{ECHO;BEGINBB;} ˆ c{ECHO;BEGINCC;} \n{ECHO;BEGIN0;} <AA>magicprintf("first"); <BB>magicprintf("second"); <CC>magicprintf("third"); wherethelogicisexactlythesameasinthepreviousmethodofhandlingtheproblem,butLexdoes theworkratherthantheuser’scode.

LEX−15 11.CharacterSet. TheprogramsgeneratedbyLexhandle characterI/Oonlythroughtheroutinesiinnppuutt,, oouuttppuutt,,anduunnppuutt..ThusthecharacterrepresentationprovidedintheseroutinesisacceptedbyLex andemployedtoreturnvaluesinyyyytteexxtt..For internaluseacharacterisrepresentedasasmall integerwhich,ifthestandardlibraryisused,hasa valueequaltotheintegervalueofthebitpattern representingthecharacteronthehostcomputer. Normally,theletteraaisrepresentedasthesame formasthecharacterconstant′′aa′′.Ifthisinterpretationischanged,byprovidingI/Oroutineswhich translatethecharacters,Lexmustbetoldabout it,bygivingatranslationtable.Thistablemust beinthedefinitionssection,andmustbebracketedbylinescontainingonly‘‘%T’’.Thetable containslinesoftheform {integer}{characterstring} whichindicatethevalueassociatedwitheachcharacter.Thusthenextexample %T 1Aa 2Bb ... 26Zz 27\n 28+ 29− 300 311 ... 399 %T Samplecharactertable. mapstheloweranduppercaseletterstogether intotheintegers1through26,newlineinto27,+ and−into28and29,andthedigitsinto30 through39.Notetheescapefornewline.Ifa tableissupplied,everycharacterthatistoappear eitherintherulesorinanyvalidinputmustbe includedinthetable.Nocharactermaybe assignedthenumber0,andnocharactermaybe assignedabiggernumberthanthesizeofthe hardwarecharacterset.

LEX−16 12.SummaryofSourceFormat. ThegeneralformofaLexsourcefileis: {definitions} %% {rules} %% {usersubroutines} Thedefinitionssectioncontainsacombinationof 1)Definitions,intheform‘‘namespacetranslation’’. 2)Includedcode,intheform‘‘spacecode’’. 3)Includedcode,intheform %{ code %} 4)Startconditions,givenintheform %Sname1name2... 5)Charactersettables,intheform %T numberspacecharacter-string ... %T 6)Changestointernalarraysizes,intheform %xxnnnnnn wherennnnnnisadecimalintegerrepresenting anarraysizeandxxselectstheparameteras follows: LetterParameter ppositions nstates etreenodes atransitions kpackedcharacterclasses ooutputarraysize Linesintherulessectionhavetheform‘‘expressionaction’’wheretheactionmaybecontinued onsucceedinglinesbyusingbracestodelimitit. RegularexpressionsinLexusethefollowing operators: xthecharacter"x" "x"an"x",evenifxisanoperator. \xan"x",evenifxisanoperator. [xy]thecharacterxory. [x−z]thecharactersx,yorz. [ˆ x]anycharacterbutx. .anycharacterbutnewline. ˆ xanxatthebeginningofaline. <y>xanxwhenLexisinstartconditiony. x$anxattheendofaline. x?anoptionalx. x∗0,1,2,...instancesofx. x+1,2,3,...instancesofx. x|yanxoray. (x)anx. x/yanxbutonlyiffollowedbyy. {xx}thetranslationofxxfromthedefinitionssection. x{m,n}mmthroughnnoccurrencesofx 13.CaveatsandBugs. Therearepathologicalexpressionswhich produceexponentialgrowthofthetableswhen convertedtodeterministicmachines;fortunately, theyarerare. REJECTdoesnotrescantheinput;instead itrememberstheresultsofthepreviousscan. Thismeansthatifarulewithtrailingcontextis found,andREJECTexecuted,theusermustnot haveuseduunnppuutttochangethecharactersforthcomingfromtheinputstream.Thisistheonly restrictionontheuser’sabilitytomanipulatethe not-yet-processedinput.

LEX−17 14.Acknowledgments. Asshouldbeobviousfromtheabove,the outsideofLexispatternedonYaccandtheinside onAho’sstringmatchingroutines.Therefore, bothS.C.JohnsonandA.V.AhoarereallyoriginatorsofmuchofLex,aswellasdebuggersofit. Manythanksareduetoboth. ThecodeofthecurrentversionofLexwas designed,written,anddebuggedbyEricSchmidt.

LEX−18 15.References. 1.B.W.KernighanandD.M.Ritchie,TThheeCC PPrrooggrraammmmiinnggLLaanngguuaaggee,,Prentice-Hall,N.J. (1978). 2.B.W.Kernighan,RRaattffoorr::AAPPrreepprroocceessssoorr ffoorraaRRaattiioonnaallFFoorrttrraann,,Software−Practice andExperience,5,pp.395-496(1975). 3.S.C.Johnson,YYaacccc::YYeettAAnnootthheerrCCoommppiilleerr CCoommppiilleerr,,ComputingScienceTechnical ReportNo.32,1975,BellLaboratories, MurrayHill,NJ07974. 4.A.V.AhoandM.J.Corasick,EEffifficciieenntt SSttrriinnggMMaattcchhiinngg::AAnnAAiiddttooBBiibblliiooggrraapphhiicc SSeeaarrcchh,,Comm.ACM18,333-340(1975). 5.B.W.Kernighan,D.M.RitchieandK.L. Thompson,QQEEDDTTeexxttEEddiittoorr,,Computing ScienceTechnicalReportNo.5,1972,Bell Laboratories,MurrayHill,NJ07974. 6.D.M.Ritchie,privatecommunication.See alsoM.E.Lesk,TThheePPoorrttaabblleeCCLLiibbrraarryy,, ComputingScienceTechnicalReportNo.31, BellLaboratories,MurrayHill,NJ07974.