Yacc:YetAnotherCompiler-Compiler StephenC.Johnson ABSTRACT Computerprograminputgenerallyhassomestructure;infact,everycomputerprogramthatdoesinputcanbethoughtofasdefiningan‘‘inputlanguage’’ whichitaccepts.Aninputlanguagemaybeascomplexasaprogramminglanguage,orassimpleasasequenceofnumbers.Unfortunately,usualinputfacilitiesarelimited,difficulttouse,andoftenarelaxaboutcheckingtheirinputsfor validity. Yaccprovidesageneraltoolfordescribingtheinputtoacomputerprogram.TheYaccuserspecifiesthestructuresofhisinput,togetherwithcodeto beinvokedaseachsuchstructureisrecognized.Yaccturnssuchaspecification intoasubroutinethathandlestheinputprocess;frequently,itisconvenientand appropriatetohavemostoftheflowofcontrolintheuser’sapplicationhandled bythissubroutine. TheinputsubroutineproducedbyYacccallsauser-suppliedroutineto returnthenextbasicinputitem.Thus,theusercanspecifyhisinputintermsof individualinputcharacters,orintermsofhigherlevelconstructssuchasnames andnumbers.Theuser-suppliedroutinemayalsohandleidiomaticfeaturessuch ascommentandcontinuationconventions,whichtypicallydefyeasygrammatical specification. YacciswritteninportableC.Theclassofspecificationsacceptedisavery generalone:LALR(1)grammarswithdisambiguatingrules. InadditiontocompilersforC,APL,Pascal,RATFOR,etc.,Yacchasalso beenusedforlessconventionallanguages,includingaphototypesetterlanguage, severaldeskcalculatorlanguages,adocumentretrievalsystem,andaFortran debuggingsystem. July31,1978 Yacc:YetAnotherCompiler-Compiler StephenC.Johnson ComputerLanguages Compilers FormalLanguageTheory 0:Introduction Yaccprovidesageneraltoolforimposingstructureontheinputtoacomputerprogram. TheYaccuserpreparesaspecificationoftheinputprocess;thisincludesrulesdescribingthe inputstructure,codetobeinvokedwhentheserulesarerecognized,andalow-levelroutinetodo thebasicinput.Yaccthengeneratesafunctiontocontroltheinputprocess.Thisfunction, calledaparser,callstheuser-suppliedlow-levelinputroutine(thelexicalanalyzer)topickupthe basicitems(calledtokens)fromtheinputstream.Thesetokensareorganizedaccordingtothe inputstructurerules,calledgrammarrules;whenoneoftheseruleshasbeenrecognized,then usercodesuppliedforthisrule,anaction,isinvoked;actionshavetheabilitytoreturnvaluesand makeuseofthevaluesofotheractions. YacciswritteninaportabledialectofC1andtheactions,andoutputsubroutine,areinC aswell.Moreover,manyofthesyntacticconventionsofYaccfollowC. Theheartoftheinputspecificationisacollectionofgrammarrules.Eachruledescribesan allowablestructureandgivesitaname.Forexample,onegrammarrulemightbe date:monthnameday´ ,´ year; Here,date,monthname,day,andyearrepresentstructuresofinterestintheinputprocess;presumably,monthname,day,andyeararedefinedelsewhere.Thecomma‘‘,’’isenclosedinsingle quotes;thisimpliesthatthecommaistoappearliterallyintheinput.Thecolonandsemicolon merelyserveaspunctuationintherule,andhavenosignificanceincontrollingtheinput.Thus, withproperdefinitions,theinput July4,1776 mightbematchedbytheaboverule. Animportantpartoftheinputprocessiscarriedoutbythelexicalanalyzer.Thisuserroutinereadstheinputstream,recognizingthelowerlevelstructures,andcommunicatesthesetokens totheparser.Forhistoricalreasons,astructurerecognizedbythelexicalanalyzeriscalledaterminalsymbol,whilethestructurerecognizedbytheparseriscalledanonterminalsymbol.To avoidconfusion,terminalsymbolswillusuallybereferredtoastokens. Thereisconsiderableleewayindecidingwhethertorecognizestructuresusingthelexical analyzerorgrammarrules.Forexample,therules monthname:´ J´ ´ a´ ´ n´ ; monthname:´ F´ ´ e´ ´ b´ ; ... monthname:´ D´ ´ e´ ´ c´ ; mightbeusedintheaboveexample.Thelexicalanalyzerwouldonlyneedtorecognizeindividual letters,andmonthnamewouldbeanonterminalsymbol.Suchlow-levelrulestendtowastetime andspace,andmaycomplicatethespecificationbeyondYacc’sabilitytodealwithit.Usually, -2-thelexicalanalyzerwouldrecognizethemonthnames,andreturnanindicationthata monthnamewasseen;inthiscase,monthnamewouldbeatoken. Literalcharacterssuchas‘‘,’’mustalsobepassedthroughthelexicalanalyzer,andarealso consideredtokens. Specificationfilesareveryflexible.Itisrealivelyeasytoaddtotheaboveexampletherule date:month´ /´ day´ /´ year; allowing 7/4/1776 asasynonymfor July4,1776 Inmostcases,thisnewrulecouldbe‘‘slippedin’’toaworkingsystemwithminimaleffort,and littledangerofdisruptingexistinginput. Theinputbeingreadmaynotconformtothespecifications.Theseinputerrorsaredetected asearlyasistheoreticallypossiblewithaleft-to-rightscan;thus,notonlyisthechanceofreading andcomputingwithbadinputdatasubstantiallyreduced,butthebaddatacanusuallybe quicklyfound.Errorhandling,providedaspartoftheinputspecifications,permitsthereentryof baddata,orthecontinuationoftheinputprocessafterskippingoverthebaddata. Insomecases,Yaccfailstoproduceaparserwhengivenasetofspecifications.Forexample,thespecificationsmaybeselfcontradictory,ortheymayrequireamorepowerfulrecognition mechanismthanthatavailabletoYacc.Theformercasesrepresentdesignerrors;thelattercases canoftenbecorrectedbymakingthelexicalanalyzermorepowerful,orbyrewritingsomeofthe grammarrules.WhileYacccannothandleallpossiblespecifications,itspowercomparesfavorably withsimilarsystems;moreover,theconstructionswhicharedifficultforYacctohandlearealso frequentlydifficultforhumanbeingstohandle.Someusershavereportedthatthedisciplineof formulatingvalidYaccspecificationsfortheirinputrevealederrorsofconceptionordesignearly intheprogramdevelopment. ThetheoryunderlyingYacchasbeendescribedelsewhere.2,3,4Yacchasbeenextensively usedinnumerouspracticalapplications,includinglint,5thePortableCCompiler,6andasystem fortypesettingmathematics.7 ThenextseveralsectionsdescribethebasicprocessofpreparingaYaccspecification;Section1describesthepreparationofgrammarrules,Section2thepreparationoftheusersupplied actionsassociatedwiththeserules,andSection3thepreparationoflexicalanalyzers.Section4 describestheoperationoftheparser.Section5discussesvariousreasonswhyYaccmaybeunable toproduceaparserfromaspecification,andwhattodoaboutit.Section6describesasimple mechanismforhandlingoperatorprecedencesinarithmeticexpressions.Section7discusseserror detectionandrecovery.Section8discussestheoperatingenvironmentandspecialfeaturesofthe parsersYaccproduces.Section9givessomesuggestionswhichshouldimprovethestyleandefficiencyofthespecifications.Section10discussessomeadvancedtopics,andSection11gives acknowledgements.AppendixAhasabriefexample,andAppendixBgivesasummaryofthe Yaccinputsyntax.AppendixCgivesanexampleusingsomeofthemoreadvancedfeaturesof Yacc,and,finally,AppendixDdescribesmechanismsandsyntaxnolongeractivelysupported,but providedforhistoricalcontinuitywitholderversionsofYacc. 1:BasicSpecifications Namesrefertoeithertokensornonterminalsymbols.Yaccrequirestokennamestobe declaredassuch.Inaddition,forreasonsdiscussedinSection3,itisoftendesirabletoinclude thelexicalanalyzeraspartofthespecificationfile;itmaybeusefultoincludeotherprogramsas well.Thus,everyspecificationfileconsistsofthreesections:thedeclarations,(grammar)rules, andprograms.Thesectionsareseparatedbydoublepercent‘‘%%’’marks.(Thepercent‘‘%’’is -3-generallyusedinYaccspecificationsasanescapecharacter.) Inotherwords,afullspecificationfilelookslike declarations %% rules %% programs Thedeclarationsectionmaybeempty.Moreover,iftheprogramssectionisomitted,the second%%markmaybeomittedalso;thus,thesmallestlegalYaccspecificationis %% rules Blanks,tabs,andnewlinesareignoredexceptthattheymaynotappearinnamesormulticharacterreservedsymbols.Commentsmayappearwhereveranameislegal;theyareenclosedin /∗...∗/,asinCandPL/I. Therulessectionismadeupofoneormoregrammarrules.Agrammarrulehastheform: A:BODY; Arepresentsanonterminalname,andBODYrepresentsasequenceofzeroormorenamesandliterals.ThecolonandthesemicolonareYaccpunctuation. Namesmaybeofarbitrarylength,andmaybemadeupofletters,dot‘‘.’’,underscore‘‘’’, andnon-initialdigits.Upperandlowercaselettersaredistinct.Thenamesusedinthebodyofa grammarrulemayrepresenttokensornonterminalsymbols. Aliteralconsistsofacharacterenclosedinsinglequotes‘‘´ ’’.AsinC,thebackslash‘‘\’’is anescapecharacterwithinliterals,andalltheCescapesarerecognized.Thus ´ \n´ newline ´ \r´ return ´ \´ ´ singlequote‘‘´ ’’ ´ \\´ backslash‘‘\’’ ´ \t´ tab ´ \b´ backspace ´ \f´ formfeed ´ \xxx´ ‘‘xxx’’inoctal Foranumberoftechnicalreasons,theNULcharacter(´ \0´ or0)shouldneverbeusedingrammar rules. Ifthereareseveralgrammarruleswiththesamelefthandside,theverticalbar‘‘|’’canbe usedtoavoidrewritingthelefthandside.Inaddition,thesemicolonattheendofarulecanbe droppedbeforeaverticalbar.Thusthegrammarrules A:BCD; A:EF; A:G; canbegiventoYaccas A:BCD |EF |G ; Itisnotnecessarythatallgrammarruleswiththesameleftsideappeartogetherinthegrammar rulessection,althoughitmakestheinputmuchmorereadable,andeasiertochange.

-4-Ifanonterminalsymbolmatchestheemptystring,thiscanbeindicatedintheobviousway: empty:; Namesrepresentingtokensmustbedeclared;thisismostsimplydonebywriting %tokenname1name2... inthedeclarationssection.(SeeSections3,5,and6formuchmorediscussion).Everynamenot definedinthedeclarationssectionisassumedtorepresentanonterminalsymbol.Everynonterminalsymbolmustappearontheleftsideofatleastonerule. Ofallthenonterminalsymbols,one,calledthestartsymbol,hasparticularimportance.The parserisdesignedtorecognizethestartsymbol;thus,thissymbolrepresentsthelargest,most generalstructuredescribedbythegrammarrules.Bydefault,thestartsymbolistakentobethe lefthandsideofthefirstgrammarruleintherulessection.Itispossible,andinfactdesirable,to declarethestartsymbolexplicitlyinthedeclarationssectionusingthe%startkeyword: %startsymbol Theendoftheinputtotheparserissignaledbyaspecialtoken,calledtheendmarker.If thetokensupto,butnotincluding,theendmarkerformastructurewhichmatchesthestartsymbol,theparserfunctionreturnstoitscalleraftertheendmarkerisseen;itacceptstheinput.If theendmarkerisseeninanyothercontext,itisanerror. Itisthejoboftheuser-suppliedlexicalanalyzertoreturntheendmarkerwhenappropriate; seesection3,below.UsuallytheendmarkerrepresentssomereasonablyobviousI/Ostatus,such as‘‘end-of-file’’or‘‘end-of-record’’. 2:Actions Witheachgrammarrule,theusermayassociateactionstobeperformedeachtimetherule isrecognizedintheinputprocess.Theseactionsmayreturnvalues,andmayobtainthevalues returnedbypreviousactions.Moreover,thelexicalanalyzercanreturnvaluesfortokens,if desired. AnactionisanarbitraryCstatement,andassuchcandoinputandoutput,callsubprograms,andalterexternalvectorsandvariables.Anactionisspecifiedbyoneormorestatements, enclosedincurlybraces‘‘{’’and‘‘}’’.Forexample, A:´ (´ B´ )´ {hello(1,"abc");} and XXX:YYYZZZ {printf("amessage\n"); flag=25;} aregrammarruleswithactions. Tofacilitateeasycommunicationbetweentheactionsandtheparser,theactionstatements arealteredslightly.Thesymbol‘‘dollarsign’’‘‘$’’isusedasasignaltoYaccinthiscontext. Toreturnavalue,theactionnormallysetsthepseudo-variable‘‘$$’’tosomevalue.For example,anactionthatdoesnothingbutreturnthevalue1is {$$=1;} Toobtainthevaluesreturnedbypreviousactionsandthelexicalanalyzer,theactionmay usethepseudo-variables$1,$2,...,whichrefertothevaluesreturnedbythecomponentsofthe rightsideofarule,readingfromlefttoright.Thus,iftheruleis -5-A:BCD; forexample,then$2hasthevaluereturnedbyC,and$3thevaluereturnedbyD. Asamoreconcreteexample,considertherule expr:´ (´ expr´ )´ ; Thevaluereturnedbythisruleisusuallythevalueoftheexprinparentheses.Thiscanbeindicatedby expr:´ (´ expr´ )´ {$$=$2;} Bydefault,thevalueofaruleisthevalueofthefirstelementinit($1).Thus,grammar rulesoftheform A:B; frequentlyneednothaveanexplicitaction. Intheexamplesabove,alltheactionscameattheendoftheirrules.Sometimes,itisdesirabletogetcontrolbeforearuleisfullyparsed.Yaccpermitsanactiontobewritteninthemiddleofaruleaswellasattheend.Thisruleisassumedtoreturnavalue,accessiblethroughthe usualmechanismbytheactionstotherightofit.Inturn,itmayaccessthevaluesreturnedby thesymbolstoitsleft.Thus,intherule A:B {$$=1;} C {x=$2;y=$3;} ; theeffectistosetxto1,andytothevaluereturnedbyC. ActionsthatdonotterminatearuleareactuallyhandledbyYaccbymanufacturinganew nonterminalsymbolname,andanewrulematchingthisnametotheemptystring.Theinterior actionistheactiontriggeredoffbyrecognizingthisaddedrule.Yaccactuallytreatstheabove exampleasifithadbeenwritten: $ACT:/∗empty∗/ {$$=1;} ; A:B$ACTC {x=$2;y=$3;} ; Inmanyapplications,outputisnotdonedirectlybytheactions;rather,adatastructure, suchasaparsetree,isconstructedinmemory,andtransformationsareappliedtoitbeforeoutput isgenerated.Parsetreesareparticularlyeasytoconstruct,givenroutinestobuildandmaintain thetreestructuredesired.Forexample,supposethereisaCfunctionnode,writtensothatthe call node(L,n1,n2) createsanodewithlabelL,anddescendantsn1andn2,andreturnstheindexofthenewlycreatednode.Thenparsetreecanbebuiltbysupplyingactionssuchas: expr:expr´ +´ expr {$$=node(´ +´ ,$1,$3);} inthespecification.

-6-Theusermaydefineothervariablestobeusedbytheactions.Declarationsanddefinitions canappearinthedeclarationssection,enclosedinthemarks‘‘%{’’and‘‘%}’’.Thesedeclarations anddefinitionshaveglobalscope,sotheyareknowntotheactionstatementsandthelexicalanalyzer.Forexample, %{intvariable=0;%} couldbeplacedinthedeclarationssection,makingvariableaccessibletoalloftheactions.The Yaccparserusesonlynamesbeginningin‘‘yy’’;theusershouldavoidsuchnames. Intheseexamples,allthevaluesareintegers:adiscussionofvaluesofothertypeswillbe foundinSection10. 3:LexicalAnalysis Theusermustsupplyalexicalanalyzertoreadtheinputstreamandcommunicatetokens (withvalues,ifdesired)totheparser.Thelexicalanalyzerisaninteger-valuedfunctioncalled yylex.Thefunctionreturnsaninteger,thetokennumber,representingthekindoftokenread.If thereisavalueassociatedwiththattoken,itshouldbeassignedtotheexternalvariableyylval. Theparserandthelexicalanalyzermustagreeonthesetokennumbersinorderforcommunicationbetweenthemtotakeplace.ThenumbersmaybechosenbyYacc,orchosenbytheuser. Ineithercase,the‘‘#define’’mechanismofCisusedtoallowthelexicalanalyzertoreturnthese numberssymbolically.Forexample,supposethatthetokennameDIGIThasbeendefinedinthe declarationssectionoftheYaccspecificationfile.Therelevantportionofthelexicalanalyzer mightlooklike: yylex(){ externintyylval; intc; ... c=getchar(); ... switch(c){ ... case´ 0´ : case´ 1´ : ... case´ 9´ : yylval=c−´ 0´ ; return(DIGIT); ... } ... TheintentistoreturnatokennumberofDIGIT,andavalueequaltothenumericalvalue ofthedigit.Providedthatthelexicalanalyzercodeisplacedintheprogramssectionofthespecificationfile,theidentifierDIGITwillbedefinedasthetokennumberassociatedwiththetoken DIGIT. Thismechanismleadstoclear,easilymodifiedlexicalanalyzers;theonlypitfallistheneed toavoidusinganytokennamesinthegrammarthatarereservedorsignificantinCortheparser; forexample,theuseoftokennamesiforwhilewillalmostcertainlycauseseveredifficultieswhen thelexicalanalyzeriscompiled.Thetokennameerrorisreservedforerrorhandling,andshould notbeusednaively(seeSection7). Asmentionedabove,thetokennumbersmaybechosenbyYaccorbytheuser.Inthe defaultsituation,thenumbersarechosenbyYacc.Thedefaulttokennumberforaliteralcharacteristhenumericalvalueofthecharacterinthelocalcharacterset.Othernamesareassigned tokennumbersstartingat257.

-7-Toassignatokennumbertoatoken(includingliterals),thefirstappearanceofthetoken nameorliteralinthedeclarationssectioncanbeimmediatelyfollowedbyanonnegativeinteger. Thisintegeristakentobethetokennumberofthenameorliteral.Namesandliteralsnot definedbythismechanismretaintheirdefaultdefinition.Itisimportantthatalltokennumbers bedistinct. Forhistoricalreasons,theendmarkermusthavetokennumber0ornegative.Thistoken numbercannotberedefinedbytheuser;thus,alllexicalanalyzersshouldbepreparedtoreturn0 ornegativeasatokennumberuponreachingtheendoftheirinput. AveryusefultoolforconstructinglexicalanalyzersistheLexprogramdevelopedbyMike Lesk.8TheselexicalanalyzersaredesignedtoworkincloseharmonywithYaccparsers.The specificationsfortheselexicalanalyzersuseregularexpressionsinsteadofgrammarrules.Lexcan beeasilyusedtoproducequitecomplicatedlexicalanalyzers,butthereremainsomelanguages (suchasFORTRAN)whichdonotfitanytheoreticalframework,andwhoselexicalanalyzers mustbecraftedbyhand. 4:HowtheParserWorks YaccturnsthespecificationfileintoaCprogram,whichparsestheinputaccordingtothe specificationgiven.Thealgorithmusedtogofromthespecificationtotheparseriscomplex,and willnotbediscussedhere(seethereferencesformoreinformation).Theparseritself,however,is relativelysimple,andunderstandinghowitworks,whilenotstrictlynecessary,willnevertheless maketreatmentoferrorrecoveryandambiguitiesmuchmorecomprehensible. TheparserproducedbyYaccconsistsofafinitestatemachinewithastack.Theparseris alsocapableofreadingandrememberingthenextinputtoken(calledthelookaheadtoken).The currentstateisalwaystheoneonthetopofthestack.Thestatesofthefinitestatemachineare givensmallintegerlabels;initially,themachineisinstate0,thestackcontainsonlystate0,and nolookaheadtokenhasbeenread. Themachinehasonlyfouractionsavailabletoit,calledshift,reduce,accept,anderror.A moveoftheparserisdoneasfollows: 1.Basedonitscurrentstate,theparserdecideswhetheritneedsalookaheadtokentodecide whatactionshouldbedone;ifitneedsone,anddoesnothaveone,itcallsyylextoobtain thenexttoken. 2.Usingthecurrentstate,andthelookaheadtokenifneeded,theparserdecidesonitsnext action,andcarriesitout.Thismayresultinstatesbeingpushedontothestack,orpopped offofthestack,andinthelookaheadtokenbeingprocessedorleftalone. Theshiftactionisthemostcommonactiontheparsertakes.Wheneverashiftactionis taken,thereisalwaysalookaheadtoken.Forexample,instate56theremaybeanaction: IFshift34 whichsays,instate56,ifthelookaheadtokenisIF,thecurrentstate(56)ispusheddownonthe stack,andstate34becomesthecurrentstate(onthetopofthestack).Thelookaheadtokenis cleared. Thereduceactionkeepsthestackfromgrowingwithoutbounds.Reduceactionsareappropriatewhentheparserhasseentherighthandsideofagrammarrule,andispreparedto announcethatithasseenaninstanceoftherule,replacingtherighthandsidebythelefthand side.Itmaybenecessarytoconsultthelookaheadtokentodecidewhethertoreduce,butusually itisnot;infact,thedefaultaction(representedbya‘‘.’’)isoftenareduceaction. Reduceactionsareassociatedwithindividualgrammarrules.Grammarrulesarealsogiven smallintegernumbers,leadingtosomeconfusion.Theaction .reduce18 referstogrammarrule18,whiletheaction -8-IFshift34 referstostate34. Supposetherulebeingreducedis A:xyz; Thereduceactiondependsonthelefthandsymbol(Ainthiscase),andthenumberofsymbols ontherighthandside(threeinthiscase).Toreduce,firstpopoffthetopthreestatesfromthe stack(Ingeneral,thenumberofstatespoppedequalsthenumberofsymbolsontherightsideof therule).Ineffect,thesestatesweretheonesputonthestackwhilerecognizingx,y,andz,and nolongerserveanyusefulpurpose.Afterpoppingthesestates,astateisuncoveredwhichwasthe statetheparserwasinbeforebeginningtoprocesstherule.Usingthisuncoveredstate,andthe symbolontheleftsideoftherule,performwhatisineffectashiftofA.Anewstateisobtained, pushedontothestack,andparsingcontinues.Therearesignificantdifferencesbetweentheprocessingofthelefthandsymbolandanordinaryshiftofatoken,however,sothisactioniscalleda gotoaction.Inparticular,thelookaheadtokenisclearedbyashift,andisnotaffectedbyagoto. Inanycase,theuncoveredstatecontainsanentrysuchas: Agoto20 causingstate20tobepushedontothestack,andbecomethecurrentstate. Ineffect,thereduceaction‘‘turnsbacktheclock’’intheparse,poppingthestatesoffthe stacktogobacktothestatewheretherighthandsideoftherulewasfirstseen.Theparserthen behavesasifithadseentheleftsideatthattime.Iftherighthandsideoftheruleisempty,no statesarepoppedoffofthestack:theuncoveredstateisinfactthecurrentstate. Thereduceactionisalsoimportantinthetreatmentofuser-suppliedactionsandvalues. Whenaruleisreduced,thecodesuppliedwiththeruleisexecutedbeforethestackisadjusted. Inadditiontothestackholdingthestates,anotherstack,runninginparallelwithit,holdsthe valuesreturnedfromthelexicalanalyzerandtheactions.Whenashifttakesplace,theexternal variableyylvaliscopiedontothevaluestack.Afterthereturnfromtheusercode,thereduction iscarriedout.Whenthegotoactionisdone,theexternalvariableyyvaliscopiedontothevalue stack.Thepseudo-variables$1,$2,etc.,refertothevaluestack. Theothertwoparseractionsareconceptuallymuchsimpler.Theacceptactionindicates thattheentireinputhasbeenseenandthatitmatchesthespecification.Thisactionappears onlywhenthelookaheadtokenistheendmarker,andindicatesthattheparserhassuccessfully doneitsjob.Theerroraction,ontheotherhand,representsaplacewheretheparsercanno longercontinueparsingaccordingtothespecification.Theinputtokensithasseen,togetherwith thelookaheadtoken,cannotbefollowedbyanythingthatwouldresultinalegalinput.The parserreportsanerror,andattemptstorecoverthesituationandresumeparsing:theerrorrecovery(asopposedtothedetectionoferror)willbecoveredinSection7. Itistimeforanexample!Considerthespecification %tokenDINGDONGDELL %% rhyme:soundplace ; sound:DINGDONG ; place:DELL ; WhenYaccisinvokedwiththe−voption,afilecalledy.outputisproduced,withahumanreadabledescriptionoftheparser.They.outputfilecorrespondingtotheabovegrammar(with somestatisticsstrippedofftheend)is:

-9-state0 $accept:rhyme$end DINGshift3 .error rhymegoto1 soundgoto2 state1 $accept:rhyme$end $endaccept .error state2 rhyme:soundplace DELLshift5 .error placegoto4 state3 sound:DINGDONG DONGshift6 .error state4 rhyme:soundplace(1) .reduce1 state5 place:DELL(3) .reduce3 state6 sound:DINGDONG(2) .reduce2 Noticethat,inadditiontotheactionsforeachstate,thereisadescriptionoftheparsingrules beingprocessedineachstate.Thecharacterisusedtoindicatewhathasbeenseen,andwhat isyettocome,ineachrule.Supposetheinputis DINGDONGDELL Itisinstructivetofollowthestepsoftheparserwhileprocessingthisinput. Initially,thecurrentstateisstate0.Theparserneedstorefertotheinputinorderto decidebetweentheactionsavailableinstate0,sothefirsttoken,DING,isread,becomingthe lookaheadtoken.Theactioninstate0onDINGisis‘‘shift3’’,sostate3ispushedontothe stack,andthelookaheadtokeniscleared.State3becomesthecurrentstate.Thenexttoken, DONG,isread,becomingthelookaheadtoken.Theactioninstate3onthetokenDONGis -10- ‘‘shift6’’,sostate6ispushedontothestack,andthelookaheadiscleared.Thestacknowcontains0,3,and6.Instate6,withoutevenconsultingthelookahead,theparserreducesbyrule2. sound:DINGDONG Thisrulehastwosymbolsontherighthandside,sotwostates,6and3,arepoppedoffofthe stack,uncoveringstate0.Consultingthedescriptionofstate0,lookingforagotoonsound, soundgoto2 isobtained;thusstate2ispushedontothestack,becomingthecurrentstate. Instate2,thenexttoken,DELL,mustberead.Theactionis‘‘shift5’’,sostate5ispushed ontothestack,whichnowhas0,2,and5onit,andthelookaheadtokeniscleared.Instate5, theonlyactionistoreducebyrule3.Thishasonesymbolontherighthandside,soonestate,5, ispoppedoff,andstate2isuncovered.Thegotoinstate2onplace,theleftsideofrule3,is state4.Now,thestackcontains0,2,and4.Instate4,theonlyactionistoreducebyrule1. Therearetwosymbolsontheright,sothetoptwostatesarepoppedoff,uncoveringstate0 again.Instate0,thereisagotoonrhymecausingtheparsertoenterstate1.Instate1,the inputisread;theendmarkerisobtained,indicatedby‘‘$end’’inthey.outputfile.Theactionin state1whentheendmarkerisseenistoaccept,successfullyendingtheparse. Thereaderisurgedtoconsiderhowtheparserworkswhenconfrontedwithsuchincorrect stringsasDINGDONGDONG,DINGDONG,DINGDONGDELLDELL,etc.Afewminutes spendwiththisandothersimpleexampleswillprobablyberepaidwhenproblemsariseinmore complicatedcontexts. 5:AmbiguityandConflicts Asetofgrammarrulesisambiguousifthereissomeinputstringthatcanbestructuredin twoormoredifferentways.Forexample,thegrammarrule expr:expr´ −´ expr isanaturalwayofexpressingthefactthatonewayofforminganarithmeticexpressionistoput twootherexpressionstogetherwithaminussignbetweenthem.Unfortunately,thisgrammarrule doesnotcompletelyspecifythewaythatallcomplexinputsshouldbestructured.Forexample,if theinputis expr−expr−expr theruleallowsthisinputtobestructuredaseither (expr−expr)−expr oras expr−(expr−expr) (Thefirstiscalledleftassociation,thesecondrightassociation). Yaccdetectssuchambiguitieswhenitisattemptingtobuildtheparser.Itisinstructiveto considertheproblemthatconfrontstheparserwhenitisgivenaninputsuchas expr−expr−expr Whentheparserhasreadthesecondexpr,theinputthatithasseen: expr−expr matchestherightsideofthegrammarruleabove.Theparsercouldreducetheinputbyapplying thisrule;afterapplyingtherule;theinputisreducedtoexpr(theleftsideoftherule).Theparser wouldthenreadthefinalpartoftheinput: −expr -11-andagainreduce.Theeffectofthisistotaketheleftassociativeinterpretation. Alternatively,whentheparserhasseen expr−expr itcoulddefertheimmediateapplicationoftherule,andcontinuereadingtheinputuntilithad seen expr−expr−expr Itcouldthenapplytheruletotherightmostthreesymbols,reducingthemtoexprandleaving expr−expr Nowtherulecanbereducedoncemore;theeffectistotaketherightassociativeinterpretation. Thus,havingread expr−expr theparsercandotwolegalthings,ashiftorareduction,andhasnowayofdecidingbetween them.Thisiscalledashift/reduceconflict.Itmayalsohappenthattheparserhasachoiceof twolegalreductions;thisiscalledareduce/reduceconflict.Notethatthereareneverany ‘‘Shift/shift’’conflicts. Whenthereareshift/reduceorreduce/reduceconflicts,Yaccstillproducesaparser.Itdoes thisbyselectingoneofthevalidstepswhereverithasachoice.Aruledescribingwhichchoiceto makeinagivensituationiscalledadisambiguatingrule. Yaccinvokestwodisambiguatingrulesbydefault: 1.Inashift/reduceconflict,thedefaultistodotheshift. 2.Inareduce/reduceconflict,thedefaultistoreducebytheearliergrammarrule(inthe inputsequence). Rule1impliesthatreductionsaredeferredwheneverthereisachoice,infavorofshifts. Rule2givestheuserrathercrudecontroloverthebehavioroftheparserinthissituation,but reduce/reduceconflictsshouldbeavoidedwheneverpossible. Conflictsmayarisebecauseofmistakesininputorlogic,orbecausethegrammarrules, whileconsistent,requireamorecomplexparserthanYacccanconstruct.Theuseofactions withinrulescanalsocauseconflicts,iftheactionmustbedonebeforetheparsercanbesure whichruleisbeingrecognized.Inthesecases,theapplicationofdisambiguatingrulesisinappropriate,andleadstoanincorrectparser.Forthisreason,Yaccalwaysreportsthenumberof shift/reduceandreduce/reduceconflictsresolvedbyRule1andRule2. Ingeneral,wheneveritispossibletoapplydisambiguatingrulestoproduceacorrectparser, itisalsopossibletorewritethegrammarrulessothatthesameinputsarereadbutthereareno conflicts.Forthisreason,mostpreviousparsergeneratorshaveconsideredconflictstobefatal errors.Ourexperiencehassuggestedthatthisrewritingissomewhatunnatural,andproduces slowerparsers;thus,Yaccwillproduceparserseveninthepresenceofconflicts. Asanexampleofthepowerofdisambiguatingrules,considerafragmentfromaprogramminglanguageinvolvingan‘‘if-then-else’’construction: stat:IF´ (´ cond´ )´ stat |IF´ (´ cond´ )´ statELSEstat ; Intheserules,IFandELSEaretokens,condisanonterminalsymboldescribingconditional(logical)expressions,andstatisanonterminalsymboldescribingstatements.Thefirstrulewillbe calledthesimple-ifrule,andthesecondtheif-elserule. Thesetworulesformanambiguousconstruction,sinceinputoftheform -12-IF(C1)IF(C2)S1ELSES2 canbestructuredaccordingtotheserulesintwoways: IF(C1){ IF(C2)S1 } ELSES2 or IF(C1){ IF(C2)S1 ELSES2 } Thesecondinterpretationistheonegiveninmostprogramminglanguageshavingthisconstruct. EachELSEisassociatedwiththelastpreceding‘‘un-ELSE’d’’IF.Inthisexample,considerthe situationwheretheparserhasseen IF(C1)IF(C2)S1 andislookingattheELSE.Itcanimmediatelyreducebythesimple-ifruletoget IF(C1)stat andthenreadtheremaininginput, ELSES2 andreduce IF(C1)statELSES2 bytheif-elserule.Thisleadstothefirstoftheabovegroupingsoftheinput. Ontheotherhand,theELSEmaybeshifted,S2read,andthentherighthandportionof IF(C1)IF(C2)S1ELSES2 canbereducedbytheif-elseruletoget IF(C1)stat whichcanbereducedbythesimple-ifrule.Thisleadstothesecondoftheabovegroupingsofthe input,whichisusuallydesired. Onceagaintheparsercandotwovalidthings−thereisashift/reduceconflict.Theapplicationofdisambiguatingrule1tellstheparsertoshiftinthiscase,whichleadstothedesired grouping. Thisshift/reduceconflictarisesonlywhenthereisaparticularcurrentinputsymbol,ELSE, andparticularinputsalreadyseen,suchas IF(C1)IF(C2)S1 Ingeneral,theremaybemanyconflicts,andeachonewillbeassociatedwithaninputsymboland asetofpreviouslyreadinputs.Thepreviouslyreadinputsarecharacterizedbythestateofthe parser. TheconflictmessagesofYaccarebestunderstoodbyexaminingtheverbose(−v)option outputfile.Forexample,theoutputcorrespondingtotheaboveconflictstatemightbe:

-13-23:shift/reduceconflict(shift45,reduce18)onELSE state23 stat:IF(cond)stat(18) stat:IF(cond)statELSEstat ELSEshift45 .reduce18 Thefirstlinedescribestheconflict,givingthestateandtheinputsymbol.Theordinarystate descriptionfollows,givingthegrammarrulesactiveinthestate,andtheparseractions.Recall thattheunderlinemarkstheportionofthegrammarruleswhichhasbeenseen.Thusinthe example,instate23theparserhasseeninputcorrespondingto IF(cond)stat andthetwogrammarrulesshownareactiveatthistime.Theparsercandotwopossiblethings. IftheinputsymbolisELSE,itispossibletoshiftintostate45.State45willhave,aspartofits description,theline stat:IF(cond)statELSEstat sincetheELSEwillhavebeenshiftedinthisstate.Backinstate23,thealternativeaction, describedby‘‘.’’,istobedoneiftheinputsymbolisnotmentionedexplicitlyintheabove actions;thus,inthiscase,iftheinputsymbolisnotELSE,theparserreducesbygrammarrule 18: stat:IF´ (´ cond´ )´ stat Onceagain,noticethatthenumbersfollowing‘‘shift’’commandsrefertootherstates,whilethe numbersfollowing‘‘reduce’’commandsrefertogrammarrulenumbers.Inthey.outputfile,the rulenumbersareprintedafterthoseruleswhichcanbereduced.Inmostonestates,therewillbe atmostreduceactionpossibleinthestate,andthiswillbethedefaultcommand.Theuserwho encountersunexpectedshift/reduceconflictswillprobablywanttolookattheverboseoutputto decidewhetherthedefaultactionsareappropriate.Inreallytoughcases,theusermightneedto knowmoreaboutthebehaviorandconstructionoftheparserthancanbecoveredhere.Inthis case,oneofthetheoreticalreferences9,10,11mightbeconsulted;theservicesofalocalgurumight alsobeappropriate. 6:Precedence Thereisonecommonsituationwheretherulesgivenaboveforresolvingconflictsarenot sufficient;thisisintheparsingofarithmeticexpressions.Mostofthecommonlyusedconstructionsforarithmeticexpressionscanbenaturallydescribedbythenotionofprecedencelevelsfor operators,togetherwithinformationaboutleftorrightassociativity.Itturnsoutthatambiguous grammarswithappropriatedisambiguatingrulescanbeusedtocreateparsersthatarefasterand easiertowritethanparsersconstructedfromunambiguousgrammars.Thebasicnotionisto writegrammarrulesoftheform expr:exprOPexpr and expr:UNARYexpr forallbinaryandunaryoperatorsdesired.Thiscreatesaveryambiguousgrammar,withmany parsingconflicts.Asdisambiguatingrules,theuserspecifiestheprecedence,orbindingstrength, ofalltheoperators,andtheassociativityofthebinaryoperators.Thisinformationissufficientto allowYacctoresolvetheparsingconflictsinaccordancewiththeserules,andconstructaparser -14-thatrealizesthedesiredprecedencesandassociativities. Theprecedencesandassociativitiesareattachedtotokensinthedeclarationssection.This isdonebyaseriesoflinesbeginningwithaYacckeyword:%left,%right,or%nonassoc,followed byalistoftokens.Allofthetokensonthesamelineareassumedtohavethesameprecedence levelandassociativity;thelinesarelistedinorderofincreasingprecedenceorbindingstrength. Thus, %left´ +´ ´ −´ %left´ ∗´ ´ /´ describestheprecedenceandassociativityofthefourarithmeticoperators.Plusandminusare leftassociative,andhavelowerprecedencethanstarandslash,whicharealsoleftassociative. Thekeyword%rightisusedtodescriberightassociativeoperators,andthekeyword%nonassocis usedtodescribeoperators,liketheoperator.LT.inFortran,thatmaynotassociatewiththemselves;thus, A.LT.B.LT.C isillegalinFortran,andsuchanoperatorwouldbedescribedwiththekeyword%nonassocin Yacc.Asanexampleofthebehaviorofthesedeclarations,thedescription %right´ =´ %left´ +´ ´ −´ %left´ ∗´ ´ /´ %% expr:expr´ =´ expr |expr´ +´ expr |expr´ −´ expr |expr´ ∗´ expr |expr´ /´ expr |NAME ; mightbeusedtostructuretheinput a=b=c∗d−e−f∗g asfollows: a=(b=(((c∗d)−e)−(f∗g))) Whenthismechanismisused,unaryoperatorsmust,ingeneral,begivenaprecedence.Sometimesaunaryoperatorandabinaryoperatorhavethesamesymbolicrepresentation,butdifferent precedences.Anexampleisunaryandbinary´ −´ ;unaryminusmaybegiventhesamestrength asmultiplication,orevenhigher,whilebinaryminushasalowerstrengththanmultiplication. Thekeyword,%prec,changestheprecedencelevelassociatedwithaparticulargrammarrule. %precappearsimmediatelyafterthebodyofthegrammarrule,beforetheactionorclosingsemicolon,andisfollowedbyatokennameorliteral.Itcausestheprecedenceofthegrammarruleto becomethatofthefollowingtokennameorliteral.Forexample,tomakeunaryminushavethe sameprecedenceasmultiplicationtherulesmightresemble:

-15- %left´ +´ ´ −´ %left´ ∗´ ´ /´ %% expr:expr´ +´ expr |expr´ −´ expr |expr´ ∗´ expr |expr´ /´ expr |´ −´ expr%prec´ ∗´ |NAME ; Atokendeclaredby%left,%right,and%nonassocneednotbe,butmaybe,declaredby %tokenaswell. TheprecedencesandassociativitiesareusedbyYacctoresolveparsingconflicts;theygive risetodisambiguatingrules.Formally,therulesworkasfollows: 1.Theprecedencesandassociativitiesarerecordedforthosetokensandliteralsthathave them. 2.Aprecedenceandassociativityisassociatedwitheachgrammarrule;itistheprecedence andassociativityofthelasttokenorliteralinthebodyoftherule.Ifthe%precconstructionisused,itoverridesthisdefault.Somegrammarrulesmayhavenoprecedenceand associativityassociatedwiththem. 3.Whenthereisareduce/reduceconflict,orthereisashift/reduceconflictandeitherthe inputsymbolorthegrammarrulehasnoprecedenceandassociativity,thenthetwodisambiguatingrulesgivenatthebeginningofthesectionareused,andtheconflictsarereported. 4.Ifthereisashift/reduceconflict,andboththegrammarruleandtheinputcharacterhave precedenceandassociativityassociatedwiththem,thentheconflictisresolvedinfavorof theaction(shiftorreduce)associatedwiththehigherprecedence.Iftheprecedencesare thesame,thentheassociativityisused;leftassociativeimpliesreduce,rightassociative impliesshift,andnonassociatingimplieserror. Conflictsresolvedbyprecedencearenotcountedinthenumberofshift/reduceand reduce/reduceconflictsreportedbyYacc.Thismeansthatmistakesinthespecificationofprecedencesmaydisguiseerrorsintheinputgrammar;itisagoodideatobesparingwithprecedences, andusetheminanessentially‘‘cookbook’’fashion,untilsomeexperiencehasbeengained.The y.outputfileisveryusefulindecidingwhethertheparserisactuallydoingwhatwasintended. 7:ErrorHandling Errorhandlingisanextremelydifficultarea,andmanyoftheproblemsaresemanticones. Whenanerrorisfound,forexample,itmaybenecessarytoreclaimparsetreestorage,deleteor altersymboltableentries,and,typically,setswitchestoavoidgeneratinganyfurtheroutput. Itisseldomacceptabletostopallprocessingwhenanerrorisfound;itismoreusefulto continuescanningtheinputtofindfurthersyntaxerrors.Thisleadstotheproblemofgettingthe parser‘‘restarted’’afteranerror.Ageneralclassofalgorithmstodothisinvolvesdiscardinga numberoftokensfromtheinputstring,andattemptingtoadjusttheparsersothatinputcan continue. Toallowtheusersomecontroloverthisprocess,Yaccprovidesasimple,butreasonablygeneral,feature.Thetokenname‘‘error’’isreservedforerrorhandling.Thisnamecanbeusedin grammarrules;ineffect,itsuggestsplaceswhereerrorsareexpected,andrecoverymighttake place.Theparserpopsitsstackuntilitentersastatewherethetoken‘‘error’’islegal.Itthen behavesasifthetoken‘‘error’’werethecurrentlookaheadtoken,andperformstheactionencountered.Thelookaheadtokenisthenresettothetokenthatcausedtheerror.Ifnospecialerror -16-ruleshavebeenspecified,theprocessinghaltswhenanerrorisdetected. Inordertopreventacascadeoferrormessages,theparser,afterdetectinganerror,remains inerrorstateuntilthreetokenshavebeensuccessfullyreadandshifted.Ifanerrorisdetected whentheparserisalreadyinerrorstate,nomessageisgiven,andtheinputtokenisquietly deleted. Asanexample,aruleoftheform stat:error would,ineffect,meanthatonasyntaxerrortheparserwouldattempttoskipoverthestatement inwhichtheerrorwasseen.Moreprecisely,theparserwillscanahead,lookingforthreetokens thatmightlegallyfollowastatement,andstartprocessingatthefirstofthese;ifthebeginnings ofstatementsarenotsufficientlydistinctive,itmaymakeafalsestartinthemiddleofastatement,andendupreportingaseconderrorwherethereisinfactnoerror. Actionsmaybeusedwiththesespecialerrorrules.Theseactionsmightattempttoreinitializetables,reclaimsymboltablespace,etc. Errorrulessuchastheaboveareverygeneral,butdifficulttocontrol.Somewhateasierare rulessuchas stat:error´ ;´ Here,whenthereisanerror,theparserattemptstoskipoverthestatement,butwilldosoby skippingtothenext´ ;´ .Alltokensaftertheerrorandbeforethenext´ ;´ cannotbeshifted,and arediscarded.Whenthe´ ;´ isseen,thisrulewillbereduced,andany‘‘cleanup’’actionassociatedwithitperformed. Anotherformoferrorrulearisesininteractiveapplications,whereitmaybedesirableto permitalinetobereenteredafteranerror.Apossibleerrorrulemightbe input:error´ \n´ {printf("Reenterlastline:");}input {$$=$4;} Thereisonepotentialdifficultywiththisapproach;theparsermustcorrectlyprocessthreeinput tokensbeforeitadmitsthatithascorrectlyresynchronizedaftertheerror.Ifthereenteredline containsanerrorinthefirsttwotokens,theparserdeletestheoffendingtokens,andgivesnomessage;thisisclearlyunacceptable.Forthisreason,thereisamechanismthatcanbeusedtoforce theparsertobelievethatanerrorhasbeenfullyrecoveredfrom.Thestatement yyerrok; inanactionresetstheparsertoitsnormalmode.Thelastexampleisbetterwritten input:error´ \n´ {yyerrok; printf("Reenterlastline:");} input {$$=$4;} ; Asmentionedabove,thetokenseenimmediatelyafterthe‘‘error’’symbolistheinputtoken atwhichtheerrorwasdiscovered.Sometimes,thisisinappropriate;forexample,anerrorrecoveryactionmighttakeuponitselfthejoboffindingthecorrectplacetoresumeinput.Inthiscase, thepreviouslookaheadtokenmustbecleared.Thestatement yyclearin; inanactionwillhavethiseffect.Forexample,supposetheactionaftererrorweretocallsome sophisticatedresynchronizationroutine,suppliedbytheuser,thatattemptedtoadvancetheinput tothebeginningofthenextvalidstatement.Afterthisroutinewascalled,thenexttoken returnedbyyylexwouldpresumablybethefirsttokeninalegalstatement;theold,illegaltoken -17-mustbediscarded,andtheerrorstatereset.Thiscouldbedonebyarulelike stat:error {resynch(); yyerrok; yyclearin;} ; Thesemechanismsareadmittedlycrude,butdoallowforasimple,fairlyeffectiverecovery oftheparserfrommanyerrors;moreover,theusercangetcontroltodealwiththeerroractions requiredbyotherportionsoftheprogram. 8:TheYaccEnvironment WhentheuserinputsaspecificationtoYacc,theoutputisafileofCprograms,called y.tab.conmostsystems(duetolocalfilesystemconventions,thenamesmaydifferfrominstallationtoinstallation).ThefunctionproducedbyYacciscalledyyparse;itisanintegervalued function.Whenitiscalled,itinturnrepeatedlycallsyylex,thelexicalanalyzersuppliedbythe user(seeSection3)toobtaininputtokens.Eventually,eitheranerrorisdetected,inwhichcase (ifnoerrorrecoveryispossible)yyparsereturnsthevalue1,orthelexicalanalyzerreturnsthe endmarkertokenandtheparseraccepts.Inthiscase,yyparsereturnsthevalue0. Theusermustprovideacertainamountofenvironmentforthisparserinordertoobtaina workingprogram.Forexample,aswitheveryCprogram,aprogramcalledmainmustbedefined, thateventuallycallsyyparse.Inaddition,aroutinecalledyyerrorprintsamessagewhenasyntax errorisdetected. Thesetworoutinesmustbesuppliedinoneformoranotherbytheuser.Toeasetheinitial effortofusingYacc,alibraryhasbeenprovidedwithdefaultversionsofmainandyyerror.The nameofthislibraryissystemdependent;onmanysystemsthelibraryisaccessedbya−lyargumenttotheloader.Toshowthetrivialityofthesedefaultprograms,thesourceisgivenbelow: main(){ return(yyparse()); } and #include<stdio.h> yyerror(s)char∗s;{ fprintf(stderr,"%s\n",s); } Theargumenttoyyerrorisastringcontaininganerrormessage,usuallythestring‘‘syntaxerror’’. Theaverageapplicationwillwanttodobetterthanthis.Ordinarily,theprogramshouldkeep trackoftheinputlinenumber,andprintitalongwiththemessagewhenasyntaxerroris detected.Theexternalintegervariableyycharcontainsthelookaheadtokennumberatthetime theerrorwasdetected;thismaybeofsomeinterestingivingbetterdiagnostics.Sincethemain programisprobablysuppliedbytheuser(toreadarguments,etc.)theYacclibraryisusefulonly insmallprojects,orintheearlieststagesoflargerones. Theexternalintegervariableyydebugisnormallysetto0.Ifitissettoanonzerovalue,the parserwilloutputaverbosedescriptionofitsactions,includingadiscussionofwhichinputsymbolshavebeenread,andwhattheparseractionsare.Dependingontheoperatingenvironment, itmaybepossibletosetthisvariablebyusingadebuggingsystem. 9:HintsforPreparingSpecifications Thissectioncontainsmiscellaneoushintsonpreparingefficient,easytochange,andclear specifications.Theindividualsubsectionsaremoreorlessindependent.

-18-InputStyle Itisdifficulttoprovideruleswithsubstantialactionsandstillhaveareadablespecification file.ThefollowingstylehintsowemuchtoBrianKernighan. a.Useallcapitallettersfortokennames,alllowercaselettersfornonterminalnames.This rulecomesundertheheadingof‘‘knowingwhotoblamewhenthingsgowrong.’’ b.Putgrammarrulesandactionsonseparatelines.Thisallowseithertobechangedwithout anautomaticneedtochangetheother. c.Putallruleswiththesamelefthandsidetogether.Putthelefthandsideinonlyonce,and letallfollowingrulesbeginwithaverticalbar. d.Putasemicolononlyafterthelastrulewithagivenlefthandside,andputthesemicolon onaseparateline.Thisallowsnewrulestobeeasilyadded. e.Indentrulebodiesbytwotabstops,andactionbodiesbythreetabstops. TheexampleinAppendixAiswrittenfollowingthisstyle,asaretheexamplesinthetextof thispaper(wherespacepermits).Theusermustmakeuphisownmindaboutthesestylistic questions;thecentralproblem,however,istomaketherulesvisiblethroughthemorassofaction code. LeftRecursion ThealgorithmusedbytheYaccparserencouragessocalled‘‘leftrecursive’’grammarrules: rulesoftheform name:namerestofrule; Theserulesfrequentlyarisewhenwritingspecificationsofsequencesandlists: list:item |list´ ,´ item ; and seq:item |seqitem ; Ineachofthesecases,thefirstrulewillbereducedforthefirstitemonly,andthesecondrulewill bereducedforthesecondandallsucceedingitems. Withrightrecursiverules,suchas seq:item |itemseq ; theparserwouldbeabitbigger,andtheitemswouldbeseen,andreduced,fromrighttoleft. Moreseriously,aninternalstackintheparserwouldbeindangerofoverflowingifaverylong sequencewereread.Thus,theusershoulduseleftrecursionwhereverreasonable. Itisworthconsideringwhetherasequencewithzeroelementshasanymeaning,andifso, considerwritingthesequencespecificationwithanemptyrule: seq:/∗empty∗/ |seqitem ; Onceagain,thefirstrulewouldalwaysbereducedexactlyonce,beforethefirstitemwasread, andthenthesecondrulewouldbereducedonceforeachitemread.Permittingemptysequences oftenleadstoincreasedgenerality.However,conflictsmightariseifYaccisaskedtodecidewhich emptysequenceithasseen,whenithasn’tseenenoughtoknow!

-19-LexicalTie-ins Somelexicaldecisionsdependoncontext.Forexample,thelexicalanalyzermightwantto deleteblanksnormally,butnotwithinquotedstrings.Ornamesmightbeenteredintoasymbol tableindeclarations,butnotinexpressions. Onewayofhandlingthissituationistocreateaglobalflagthatisexaminedbythelexical analyzer,andsetbyactions.Forexample,supposeaprogramconsistsof0ormoredeclarations, followedby0ormorestatements.Consider: %{ intdflag; %} ...otherdeclarations... %% prog:declsstats ; decls:/∗empty∗/ {dflag=1;} |declsdeclaration ; stats:/∗empty∗/ {dflag=0;} |statsstatement ; ...otherrules... Theflagdflagisnow0whenreadingstatements,and1whenreadingdeclarations,exceptforthe firsttokeninthefirststatement.Thistokenmustbeseenbytheparserbeforeitcantellthatthe declarationsectionhasendedandthestatementshavebegun.Inmanycases,thissingletoken exceptiondoesnotaffectthelexicalscan. Thiskindof‘‘backdoor’’approachcanbeelaboratedtoanoxiousdegree.Nevertheless,it representsawayofdoingsomethingsthataredifficult,ifnotimpossible,todootherwise. ReservedWords Someprogramminglanguagespermittheusertousewordslike‘‘if’’,whicharenormally reserved,aslabelorvariablenames,providedthatsuchusedoesnotconflictwiththelegaluseof thesenamesintheprogramminglanguage.Thisisextremelyhardtodointheframeworkof Yacc;itisdifficulttopassinformationtothelexicalanalyzertellingit‘‘thisinstanceof‘if’isa keyword,andthatinstanceisavariable’’.Theusercanmakeastabatit,usingthemechanism describedinthelastsubsection,butitisdifficult. Anumberofwaysofmakingthiseasierareunderadvisement.Untilthen,itisbetterthat thekeywordsbereserved;thatis,beforbiddenforuseasvariablenames.Therearepowerful stylisticreasonsforpreferringthis,anyway. 10:AdvancedTopics ThissectiondiscussesanumberofadvancedfeaturesofYacc.

-20-SimulatingErrorandAcceptinActions Theparsingactionsoferrorandacceptcanbesimulatedinanactionbyuseofmacros YYACCEPTandYYERROR.YYACCEPTcausesyyparsetoreturnthevalue0;YYERROR causestheparsertobehaveasifthecurrentinputsymbolhadbeenasyntaxerror;yyerroris called,anderrorrecoverytakesplace.Thesemechanismscanbeusedtosimulateparserswith multipleendmarkersorcontext-sensitivesyntaxchecking. AccessingValuesinEnclosingRules. Anactionmayrefertovaluesreturnedbyactionstotheleftofthecurrentrule.Themechanismissimplythesameaswithordinaryactions,adollarsignfollowedbyadigit,butinthis casethedigitmaybe0ornegative.Consider sent:adjnounverbadjnoun {lookatthesentence...} ; adj:THE{$$=THE;} |YOUNG{$$=YOUNG;} ... ; noun:DOG {$$=DOG;} |CRONE {if($0==YOUNG){ printf("what?\n"); } $$=CRONE; } ; ... IntheactionfollowingthewordCRONE,acheckismadethattheprecedingtokenshiftedwas notYOUNG.Obviously,thisisonlypossiblewhenagreatdealisknownaboutwhatmightprecedethesymbolnounintheinput.Thereisalsoadistinctlyunstructuredflavoraboutthis. Nevertheless,attimesthismechanismwillsaveagreatdealoftrouble,especiallywhenafewcombinationsaretobeexcludedfromanotherwiseregularstructure. SupportforArbitraryValueTypes Bydefault,thevaluesreturnedbyactionsandthelexicalanalyzerareintegers.Yacccan alsosupportvaluesofothertypes,includingstructures.Inaddition,Yacckeepstrackofthe types,andinsertsappropriateunionmembernamessothattheresultingparserwillbestrictly typechecked.TheYaccvaluestack(seeSection4)isdeclaredtobeaunionofthevarioustypes ofvaluesdesired.Theuserdeclarestheunion,andassociatesunionmembernamestoeachtoken andnonterminalsymbolhavingavalue.Whenthevalueisreferencedthrougha$$or$nconstruction,Yaccwillautomaticallyinserttheappropriateunionname,sothatnounwantedconversionswilltakeplace.Inaddition,typecheckingcommandssuchasLint12willbefarmoresilent. Therearethreemechanismsusedtoprovideforthistyping.First,thereisawayofdefining theunion;thismustbedonebytheusersinceotherprograms,notablythelexicalanalyzer,must knowabouttheunionmembernames.Second,thereisawayofassociatingaunionmember namewithtokensandnonterminals.Finally,thereisamechanismfordescribingthetypeof thosefewvalueswhereYacccannoteasilydeterminethetype. Todeclaretheunion,theuserincludesinthedeclarationsection:

-21- %union{ bodyofunion... } ThisdeclarestheYaccvaluestack,andtheexternalvariablesyylvalandyyval,tohavetypeequal tothisunion.IfYaccwasinvokedwiththe−doption,theuniondeclarationiscopiedontothe y.tab.hfile.Alternatively,theunionmaybedeclaredinaheaderfile,andatypedefusedtodefine thevariableYYSTYPEtorepresentthisunion.Thus,theheaderfilemightalsohavesaid: typedefunion{ bodyofunion... }YYSTYPE; Theheaderfilemustbeincludedinthedeclarationssection,byuseof%{and%}. OnceYYSTYPEisdefined,theunionmembernamesmustbeassociatedwiththevarious terminalandnonterminalnames.Theconstruction <name> isusedtoindicateaunionmembername.Ifthisfollowsoneofthekeywords%token,%left, %right,and%nonassoc,theunionmembernameisassociatedwiththetokenslisted.Thus,saying %left<optype>´ +´ ´ −´ willcauseanyreferencetovaluesreturnedbythesetwotokenstobetaggedwiththeunionmembernameoptype.Anotherkeyword,%type,isusedsimilarlytoassociateunionmembernames withnonterminals.Thus,onemightsay %type<nodetype>exprstat Thereremainacoupleofcaseswherethesemechanismsareinsufficient.Ifthereisanaction withinarule,thevaluereturnedbythisactionhasnoaprioritype.Similarly,referencetoleft contextvalues(suchas$0−seetheprevioussubsection)leavesYaccwithnoeasywayofknowingthetype.Inthiscase,atypecanbeimposedonthereferencebyinsertingaunionmember name,between<and>,immediatelyafterthefirst$.Anexampleofthisusageis rule:aaa{$<intval>$=3;}bbb {fun($<intval>2,$<other>0);} ; Thissyntaxhaslittletorecommendit,butthesituationarisesrarely. AsamplespecificationisgiveninAppendixC.Thefacilitiesinthissubsectionarenottriggereduntiltheyareused:inparticular,theuseof%typewillturnonthesemechanisms.When theyareused,thereisafairlystrictlevelofchecking.Forexample,useof$nor$$toreferto somethingwithnodefinedtypeisdiagnosed.Ifthesefacilitiesarenottriggered,theYaccvalue stackisusedtoholdint’s,aswastruehistorically. 11:Acknowledgements Yaccowesmuchtoamoststimulatingcollectionofusers,whohavegoadedmebeyondmy inclination,andfrequentlybeyondmyability,intheirendlesssearchfor‘‘onemorefeature’’. Theirirritatingunwillingnesstolearnhowtodothingsmywayhasusuallyledtomydoingthings theirway;mostofthetime,theyhavebeenright.B.W.Kernighan,P.J.Plauger,S.I.Feldman, C.Imagna,M.E.Lesk,andA.Snyderwillrecognizesomeoftheirideasinthecurrentversionof Yacc.C.B.Haleycontributedtotheerrorrecoveryalgorithm.D.M.Ritchie,B.W.Kernighan, andM.O.HarrishelpedtranslatethisdocumentintoEnglish.AlAhoalsodeservesspecialcredit forbringingthemountaintoMohammed,andotherfavors.

-22-References 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

-23-AppendixA:ASimpleExample ThisexamplegivesthecompleteYaccspecificationforasmalldeskcalculator;thedeskcalculatorhas26registers,labeled‘‘a’’through‘‘z’’,andacceptsarithmeticexpressionsmadeupof theoperators+,−,∗,/,%(modoperator),&(bitwiseand),|(bitwiseor),andassignment.Ifan expressionatthetoplevelisanassignment,thevalueisnotprinted;otherwiseitis.AsinC,an integerthatbeginswith0(zero)isassumedtobeoctal;otherwise,itisassumedtobedecimal. AsanexampleofaYaccspecification,thedeskcalculatordoesareasonablejobofshowing howprecedencesandambiguitiesareused,anddemonstratingsimpleerrorrecovery.Themajor oversimplificationsarethatthelexicalanalysisphaseismuchsimplerthanformostapplications, andtheoutputisproducedimmediately,linebyline.Notethewaythatdecimalandoctalintegersarereadinbythegrammarrules;Thisjobisprobablybetterdonebythelexicalanalyzer. %{ #include<stdio.h> #include<ctype.h> intregs[26]; intbase; %} %startlist %tokenDIGITLETTER %left´ |´ %left´ &´ %left´ +´ ´ −´ %left´ ∗´ ´ /´ ´ %´ %leftUMINUS/∗suppliesprecedenceforunaryminus∗/ %%/∗beginningofrulessection∗/ list:/∗empty∗/ |liststat´ \n´ |listerror´ \n´ {yyerrok;} ; stat:expr {printf("%d\n",$1);} |LETTER´ =´ expr {regs[$1]=$3;} ; expr:´ (´ expr´ )´ {$$=$2;} |expr´ +´ expr {$$=$1+$3;} |expr´ −´ expr {$$=$1−$3;} |expr´ ∗´ expr {$$=$1∗$3;} -24- |expr´ /´ expr {$$=$1/$3;} |expr´ %´ expr {$$=$1%$3;} |expr´ &´ expr {$$=$1&$3;} |expr´ |´ expr {$$=$1|$3;} |´ −´ expr%precUMINUS {$$=−$2;} |LETTER {$$=regs[$1];} |number ; number:DIGIT {$$=$1;base=($1==0)?8:10;} |numberDIGIT {$$=base∗$1+$2;} ; %%/∗startofprograms∗/ yylex(){/∗lexicalanalysisroutine∗/ /∗returnsLETTERforalowercaseletter,yylval=0through25∗/ /∗returnDIGITforadigit,yylval=0through9∗/ /∗allothercharactersarereturnedimmediately∗/ intc; while((c=getchar())==´ ´ ){/∗skipblanks∗/} /∗cisnownonblank∗/ if(islower(c)){ yylval=c−´ a´ ; return(LETTER); } if(isdigit(c)){ yylval=c−´ 0´ ; return(DIGIT); } return(c); } -25-AppendixB:YaccInputSyntax ThisAppendixhasadescriptionoftheYaccinputsyntax,asaYaccspecification.Context dependencies,etc.,arenotconsidered.Ironically,theYaccinputspecificationlanguageismost naturallyspecifiedasanLR(2)grammar;thestickypartcomeswhenanidentifierisseenina rule,immediatelyfollowinganaction.Ifthisidentifierisfollowedbyacolon,itisthestartofthe nextrule;otherwiseitisacontinuationofthecurrentrule,whichjusthappenstohaveanaction embeddedinit.Asimplemented,thelexicalanalyzerlooksaheadafterseeinganidentifier,and decidewhetherthenexttoken(skippingblanks,newlines,comments,etc.)isacolon.Ifso,it returnsthetokenCIDENTIFIER.Otherwise,itreturnsIDENTIFIER.Literals(quotedstrings) arealsoreturnedasIDENTIFIERS,butneveraspartofCIDENTIFIERs. /∗grammarfortheinputtoYacc∗/ /∗basicentities∗/ %tokenIDENTIFIER/∗includesidentifiersandliterals∗/ %tokenCIDENTIFIER/∗identifier(butnotliteral)followedbycolon∗/ %tokenNUMBER/∗[0-9]+∗/ /∗reservedwords:%type=>TYPE,%left=>LEFT,etc.∗/ %tokenLEFTRIGHTNONASSOCTOKENPRECTYPESTARTUNION %tokenMARK/∗the%%mark∗/ %tokenLCURL/∗the%{mark∗/ %tokenRCURL/∗the%}mark∗/ /∗asciicharacterliteralsstandforthemselves∗/ %startspec %% spec:defsMARKrulestail ; tail:MARK{Inthisaction,eatuptherestofthefile} |/∗empty:thesecondMARKisoptional∗/ ; defs:/∗empty∗/ |defsdef ; def:STARTIDENTIFIER |UNION{Copyuniondefinitiontooutput} |LCURL{CopyCcodetooutputfile}RCURL |ndefsrwordtagnlist ; rword:TOKEN |LEFT |RIGHT |NONASSOC -26- |TYPE ; tag:/∗empty:uniontagisoptional∗/ |´ <´ IDENTIFIER´ >´ ; nlist:nmno |nlistnmno |nlist´ ,´ nmno ; nmno:IDENTIFIER/∗NOTE:literalillegalwith%type∗/ |IDENTIFIERNUMBER/∗NOTE:illegalwith%type∗/ ; /∗rulessection∗/ rules:CIDENTIFIERrbodyprec |rulesrule ; rule:CIDENTIFIERrbodyprec |’|’rbodyprec ; rbody:/∗empty∗/ |rbodyIDENTIFIER |rbodyact ; act:´ {´ {Copyaction,translate$$,etc.}´ }´ ; prec:/∗empty∗/ |PRECIDENTIFIER |PRECIDENTIFIERact |prec´ ;´ ; -27-AppendixC:AnAdvancedExample ThisAppendixgivesanexampleofagrammarusingsomeoftheadvancedfeaturesdiscussedinSection10.ThedeskcalculatorexampleinAppendixAismodifiedtoprovideadesk calculatorthatdoesfloatingpointintervalarithmetic.Thecalculatorunderstandsfloatingpoint constants,thearithmeticoperations+,−,∗,/,unary−,and=(assignment),andhas26floating pointvariables,‘‘a’’through‘‘z’’.Moreover,italsounderstandsintervals,written (x,y) wherexislessthanorequaltoy.Thereare26intervalvaluedvariables‘‘A’’through‘‘Z’’that mayalsobeused.TheusageissimilartothatinAppendixA;assignmentsreturnnovalue,and printnothing,whileexpressionsprintthe(floatingorinterval)value. ThisexampleexploresanumberofinterestingfeaturesofYaccandC.Intervalsarerepresentedbyastructure,consistingoftheleftandrightendpointvalues,storedasdouble’s.This structureisgivenatypename,INTERVAL,byusingtypedef.TheYaccvaluestackcanalsocontainfloatingpointscalars,andintegers(usedtoindexintothearraysholdingthevariablevalues). Noticethatthisentirestrategydependsstronglyonbeingabletoassignstructuresandunionsin C.Infact,manyoftheactionscallfunctionsthatreturnstructuresaswell. ItisalsoworthnotingtheuseofYYERRORtohandleerrorconditions:divisionbyan intervalcontaining0,andanintervalpresentedinthewrongorder.Ineffect,theerrorrecovery mechanismofYaccisusedtothrowawaytherestoftheoffendingline. Inadditiontothemixingoftypesonthevaluestack,thisgrammaralsodemonstratesan interestinguseofsyntaxtokeeptrackofthetype(e.g.scalarorinterval)ofintermediateexpressions.Notethatascalarcanbeautomaticallypromotedtoanintervalifthecontextdemandsan intervalvalue.ThiscausesalargenumberofconflictswhenthegrammarisrunthroughYacc:18 Shift/Reduceand26Reduce/Reduce.Theproblemcanbeseenbylookingatthetwoinputlines: 2.5+(3.5−4.) and 2.5+(3.5,4.) Noticethatthe2.5istobeusedinanintervalvaluedexpressioninthesecondexample,butthis factisnotknownuntilthe‘‘,’’isread;bythistime,2.5isfinished,andtheparsercannotgoback andchangeitsmind.Moregenerally,itmightbenecessarytolookaheadanarbitrarynumberof tokenstodecidewhethertoconvertascalartoaninterval.Thisproblemisevadedbyhavingtwo rulesforeachbinaryintervalvaluedoperator:onewhentheleftoperandisascalar,andonewhen theleftoperandisaninterval.Inthesecondcase,therightoperandmustbeaninterval,sothe conversionwillbeappliedautomatically.Despitethisevasion,therearestillmanycaseswhere theconversionmaybeappliedornot,leadingtotheaboveconflicts.Theyareresolvedbylisting therulesthatyieldscalarsfirstinthespecificationfile;inthisway,theconflictswillberesolvedin thedirectionofkeepingscalarvaluedexpressionsscalarvalueduntiltheyareforcedtobecome intervals. Thiswayofhandlingmultipletypesisveryinstructive,butnotverygeneral.Iftherewere manykindsofexpressiontypes,insteadofjusttwo,thenumberofrulesneededwouldincrease dramatically,andtheconflictsevenmoredramatically.Thus,whilethisexampleisinstructive,it isbetterpracticeinamorenormalprogramminglanguageenvironmenttokeepthetypeinformationaspartofthevalue,andnotaspartofthegrammar. Finally,awordaboutthelexicalanalysis.Theonlyunusualfeatureisthetreatmentof floatingpointconstants.TheClibraryroutineatofisusedtodotheactualconversionfroma characterstringtoadoubleprecisionvalue.Ifthelexicalanalyzerdetectsanerror,itresponds byreturningatokenthatisillegalinthegrammar,provokingasyntaxerrorintheparser,and thenceerrorrecovery.

-28- %{ #include<stdio.h> #include<ctype.h> typedefstructinterval{ doublelo,hi; }INTERVAL; INTERVALvmul(),vdiv(); doubleatof(); doubledreg[26]; INTERVALvreg[26]; %} %startlines %union{ intival; doubledval; INTERVALvval; } %token<ival>DREGVREG/∗indicesintodreg,vregarrays∗/ %token<dval>CONST/∗floatingpointconstant∗/ %type<dval>dexp/∗expression∗/ %type<vval>vexp/∗intervalexpression∗/ /∗precedenceinformationabouttheoperators∗/ %left´ +´ ´ −´ %left´ ∗´ ´ /´ %leftUMINUS/∗precedenceforunaryminus∗/ %% lines:/∗empty∗/ |linesline ; line:dexp´ \n´ {printf("%15.8f\n",$1);} |vexp´ \n´ {printf("(%15.8f,%15.8f)\n",$1.lo,$1.hi);} |DREG´ =´ dexp´ \n´ {dreg[$1]=$3;} |VREG´ =´ vexp´ \n´ {vreg[$1]=$3;} -29- |error´ \n´ {yyerrok;} ; dexp:CONST |DREG {$$=dreg[$1];} |dexp´ +´ dexp {$$=$1+$3;} |dexp´ −´ dexp {$$=$1−$3;} |dexp´ ∗´ dexp {$$=$1∗$3;} |dexp´ /´ dexp {$$=$1/$3;} |´ −´ dexp%precUMINUS {$$=−$2;} |´ (´ dexp´ )´ {$$=$2;} ; vexp:dexp {$$.hi=$$.lo=$1;} |´ (´ dexp´ ,´ dexp´ )´ { $$.lo=$2; $$.hi=$4; if($$.lo>$$.hi){ printf("intervaloutoforder\n"); YYERROR; } } |VREG {$$=vreg[$1];} |vexp´ +´ vexp {$$.hi=$1.hi+$3.hi; $$.lo=$1.lo+$3.lo;} |dexp´ +´ vexp {$$.hi=$1+$3.hi; $$.lo=$1+$3.lo;} |vexp´ −´ vexp {$$.hi=$1.hi−$3.lo; $$.lo=$1.lo−$3.hi;} |dexp´ −´ vexp {$$.hi=$1−$3.lo; $$.lo=$1−$3.hi;} |vexp´ ∗´ vexp {$$=vmul($1.lo,$1.hi,$3);} |dexp´ ∗´ vexp {$$=vmul($1,$1,$3);} |vexp´ /´ vexp {if(dcheck($3))YYERROR; $$=vdiv($1.lo,$1.hi,$3);} |dexp´ /´ vexp -30- {if(dcheck($3))YYERROR; $$=vdiv($1,$1,$3);} |´ −´ vexp%precUMINUS {$$.hi=−$2.lo;$$.lo=−$2.hi;} |´ (´ vexp´ )´ {$$=$2;} ; %% #defineBSZ50/∗buffersizeforfloatingpointnumbers∗/ /∗lexicalanalysis∗/ yylex(){ registerc; while((c=getchar())==´ ´ ){/∗skipoverblanks∗/} if(isupper(c)){ yylval.ival=c−´ A´ ; return(VREG); } if(islower(c)){ yylval.ival=c−´ a´ ; return(DREG); } if(isdigit(c)||c==´ .´ ){ /∗gobbleupdigits,points,exponents∗/ charbuf[BSZ+1],∗cp=buf; intdot=0,exp=0; for(;(cp−buf)<BSZ;++cp,c=getchar()){ ∗cp=c; if(isdigit(c))continue; if(c==´ .´ ){ if(dot++||exp)return(´ .´ );/∗willcausesyntaxerror∗/ continue; } if(c==´ e´ ){ if(exp++)return(´ e´ );/∗willcausesyntaxerror∗/ continue; } /∗endofnumber∗/ break; } ∗cp=´ \0´ ; if((cp−buf)>=BSZ)printf("constanttoolong:truncated\n"); elseungetc(c,stdin);/∗pushbacklastcharread∗/ -31-yylval.dval=atof(buf); return(CONST); } return(c); } INTERVALhilo(a,b,c,d)doublea,b,c,d;{ /∗returnsthesmallestintervalcontaininga,b,c,andd∗/ /∗usedby∗,/routines∗/ INTERVALv; if(a>b){v.hi=a;v.lo=b;} else{v.hi=b;v.lo=a;} if(c>d){ if(c>v.hi)v.hi=c; if(d<v.lo)v.lo=d; } else{ if(d>v.hi)v.hi=d; if(c<v.lo)v.lo=c; } return(v); } INTERVALvmul(a,b,v)doublea,b;INTERVALv;{ return(hilo(a∗v.hi,a∗v.lo,b∗v.hi,b∗v.lo)); } dcheck(v)INTERVALv;{ if(v.hi>=0.&&v.lo<=0.){ printf("divisorintervalcontains0.\n"); return(1); } return(0); } INTERVALvdiv(a,b,v)doublea,b;INTERVALv;{ return(hilo(a/v.hi,a/v.lo,b/v.hi,b/v.lo)); } -32-AppendixD:OldFeaturesSupportedbutnotEncouraged ThisAppendixmentionssynonymsandfeatureswhicharesupportedforhistoricalcontinuity,but,forvariousreasons,arenotencouraged. 1.Literalsmayalsobedelimitedbydoublequotes‘‘"’’. 2.Literalsmaybemorethanonecharacterlong.Ifallthecharactersarealphabetic,numeric, or,thetypenumberoftheliteralisdefined,justasiftheliteraldidnothavethequotes aroundit.Otherwise,itisdifficulttofindthevalueforsuchliterals. Theuseofmulti-characterliteralsislikelytomisleadthoseunfamiliarwithYacc,sinceit suggeststhatYaccisdoingajobwhichmustbeactuallydonebythelexicalanalyzer. 3.Mostplaceswhere%islegal,backslash‘‘\’’maybeused.Inparticular,\\isthesameas %%,\leftthesameas%left,etc. 4.Thereareanumberofothersynonyms: %<isthesameas%left %>isthesameas%right %binaryand%2arethesameas%nonassoc %0and%termarethesameas%token %=isthesameas%prec 5.Actionsmayalsohavetheform ={...} andthecurlybracescanbedroppediftheactionisasingleCstatement. 6.Ccodebetween%{and%}usedtobepermittedattheheadoftherulessection,aswellas inthedeclarationsection.