BISON.TEX 166 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545
  1. \input texinfo @c -*-texinfo-*-
  2. @c tex
  3. @c special{twoside}
  4. @c end tex
  5. @comment %**start of header
  6. @setfilename bison.info
  7. @settitle Bison Reference Manual
  8. @setchapternewpage odd
  9. @c SMALL BOOK version
  10. @c This edition has been formatted so that you can format and print it in
  11. @c the smallbook format. The intent is to publish it in smallbook format
  12. @c when the manual becomes stable, which may happen after the POSIX
  13. @c standards committee agrees to a standard.
  14. @c smallbook
  15. @iftex
  16. @syncodeindex fn cp
  17. @syncodeindex vr cp
  18. @end iftex
  19. @ifinfo
  20. @synindex fn cp
  21. @synindex vr cp
  22. @end ifinfo
  23. @comment %**end of header
  24. @ifinfo
  25. This file documents the Bison parser generator.
  26. Copyright (C) 1988, 1989, 1990 Free Software Foundation, Inc.
  27. Permission is granted to make and distribute verbatim copies of
  28. this manual provided the copyright notice and this permission notice
  29. are preserved on all copies.
  30. @ignore
  31. Permission is granted to process this file through Tex and print the
  32. results, provided the printed document carries copying permission
  33. notice identical to this one except for the removal of this paragraph
  34. (this paragraph not being relevant to the printed manual).
  35. @end ignore
  36. Permission is granted to copy and distribute modified versions of this
  37. manual under the conditions for verbatim copying, provided also that the
  38. sections entitled ``GNU General Public License'' and ``Conditions for
  39. Using Bison'' are included exactly as in the original, and provided that
  40. the entire resulting derived work is distributed under the terms of a
  41. permission notice identical to this one.
  42. Permission is granted to copy and distribute translations of this manual
  43. into another language, under the above conditions for modified versions,
  44. except that the sections entitled ``GNU General Public License'',
  45. ``Conditions for Using Bison'' and this permission notice may be
  46. included in translations approved by the Free Software Foundation
  47. instead of in the original English.
  48. @end ifinfo
  49. @titlepage
  50. @title BISON
  51. @subtitle The YACC-compatible Parser Generator
  52. @subtitle June 1990
  53. @author by Charles Donnelly and Richard Stallman
  54. @page
  55. @vskip 0pt plus 1filll
  56. Copyright @copyright{} 1988, 1989, 1990 Free Software Foundation
  57. Permission is granted to make and distribute verbatim copies of
  58. this manual provided the copyright notice and this permission notice
  59. are preserved on all copies.
  60. @ignore
  61. Permission is granted to process this file through TeX and print the
  62. results, provided the printed document carries copying permission
  63. notice identical to this one except for the removal of this paragraph
  64. (this paragraph not being relevant to the printed manual).
  65. @end ignore
  66. Permission is granted to copy and distribute modified versions of this
  67. manual under the conditions for verbatim copying, provided also that the
  68. sections entitled ``GNU General Public License'' and ``Conditions for
  69. Using Bison'' are included exactly as in the original, and provided that
  70. the entire resulting derived work is distributed under the terms of a
  71. permission notice identical to this one.
  72. Permission is granted to copy and distribute translations of this manual
  73. into another language, under the above conditions for modified versions,
  74. except that the sections entitled ``GNU General Public License'',
  75. ``Conditions for Using Bison'' and this permission notice may be
  76. included in translations approved by the Free Software Foundation
  77. instead of in the original English.
  78. @space 2
  79. Cover art by Etienne Suvasa.
  80. @end titlepage
  81. @page
  82. @node Top, Introduction, (DIR), (DIR)
  83. @menu
  84. * Introduction::
  85. * Conditions::
  86. * Copying:: The GNU General Public License says
  87. how you can copy and share Bison
  88. Tutorial sections:
  89. * Concepts:: Basic concepts for understanding Bison.
  90. * Examples:: Three simple explained examples of using Bison.
  91. Reference sections:
  92. * Grammar File:: Writing Bison declarations and rules.
  93. * Interface:: C-language interface to the parser function @code{yyparse}.
  94. * Algorithm:: How the Bison parser works at run-time.
  95. * Error Recovery:: Writing rules for error recovery.
  96. * Context Dependency::What to do if your language syntax is too
  97. messy for Bison to handle straightforwardly.
  98. * Debugging:: Debugging Bison parsers that parse wrong.
  99. * Invocation:: How to run Bison (to produce the parser source file).
  100. * Table of Symbols:: All the keywords of the Bison language are explained.
  101. * Glossary:: Basic concepts are explained.
  102. * Index:: Cross-references to the text.
  103. @end menu
  104. @node Introduction, Conditions, Top, Top
  105. @unnumbered Introduction
  106. @cindex introduction
  107. @dfn{Bison} is a general-purpose parser generator that converts a
  108. grammar description for an LALR(1) context-free grammar into a C
  109. program to parse that grammar. Once you are proficient with Bison,
  110. you may use it to develop a wide range of language parsers, from those
  111. used in simple desk calculators to complex programming languages.
  112. Bison is upward compatible with Yacc: all properly-written Yacc grammars
  113. ought to work with Bison with no change. Anyone familiar with Yacc
  114. should be able to use Bison with little trouble. You need to be fluent in
  115. C programming in order to use Bison or to understand this manual.
  116. We begin with tutorial chapters that explain the basic concepts of using
  117. Bison and show three explained examples, each building on the last. If you
  118. don't know Bison or Yacc, start by reading these chapters. Reference
  119. chapters follow which describe specific aspects of Bison in detail.
  120. Bison was written primarily by Robert Corbett; Richard Stallman made
  121. it Yacc-compatible. This edition corresponds to version 1.10 of Bison.
  122. @node Conditions, Copying, Introduction, Top
  123. @unnumbered Conditions for Using Bison
  124. Bison grammars can be used only in programs that are free software. This
  125. is in contrast to what happens with the GNU C compiler and the other
  126. GNU programming tools.
  127. The reason Bison is special is that the output of the Bison utility---the
  128. Bison parser file---contains a verbatim copy of a sizable piece of Bison,
  129. which is the code for the @code{yyparse} function. (The actions from your
  130. grammar are inserted into this function at one point, but the rest of the
  131. function is not changed.)
  132. As a result, the Bison parser file is covered by the same copying
  133. conditions that cover Bison itself and the rest of the GNU system: any
  134. program containing it has to be distributed under the standard GNU copying
  135. conditions.
  136. Occasionally people who would like to use Bison to develop proprietary
  137. programs complain about this.
  138. We don't particularly sympathize with their complaints. The purpose of the
  139. GNU project is to promote the right to share software and the practice of
  140. sharing software; it is a means of changing society. The people who
  141. complain are planning to be uncooperative toward the rest of the world; why
  142. should they deserve our help in doing so?
  143. However, it's possible that a change in these conditions might encourage
  144. computer companies to use and distribute the GNU system. If so, then we
  145. might decide to change the terms on @code{yyparse} as a matter of the
  146. strategy of promoting the right to share. Such a change would be
  147. irrevocable. Since we stand by the copying permissions we have announced,
  148. we cannot withdraw them once given.
  149. We mustn't make an irrevocable change hastily. We have to wait until there
  150. is a complete GNU system and there has been time to learn how this issue
  151. affects its reception.
  152. @node Copying, Concepts, Conditions, Top
  153. @unnumbered GNU General Public License
  154. @center Version 1, February 1989
  155. @display
  156. Copyright @copyright{} 1989 Free Software Foundation, Inc.
  157. 675 Mass Ave, Cambridge, MA 02139, USA
  158. Everyone is permitted to copy and distribute verbatim copies
  159. of this license document, but changing it is not allowed.
  160. @end display
  161. @unnumberedsec Preamble
  162. The license agreements of most software companies try to keep users
  163. at the mercy of those companies. By contrast, our General Public
  164. License is intended to guarantee your freedom to share and change free
  165. software---to make sure the software is free for all its users. The
  166. General Public License applies to the Free Software Foundation's
  167. software and to any other program whose authors commit to using it.
  168. You can use it for your programs, too.
  169. When we speak of free software, we are referring to freedom, not
  170. price. Specifically, the General Public License is designed to make
  171. sure that you have the freedom to give away or sell copies of free
  172. software, that you receive source code or can get it if you want it,
  173. that you can change the software or use pieces of it in new free
  174. programs; and that you know you can do these things.
  175. To protect your rights, we need to make restrictions that forbid
  176. anyone to deny you these rights or to ask you to surrender the rights.
  177. These restrictions translate to certain responsibilities for you if you
  178. distribute copies of the software, or if you modify it.
  179. For example, if you distribute copies of a such a program, whether
  180. gratis or for a fee, you must give the recipients all the rights that
  181. you have. You must make sure that they, too, receive or can get the
  182. source code. And you must tell them their rights.
  183. We protect your rights with two steps: (1) copyright the software, and
  184. (2) offer you this license which gives you legal permission to copy,
  185. distribute and/or modify the software.
  186. Also, for each author's protection and ours, we want to make certain
  187. that everyone understands that there is no warranty for this free
  188. software. If the software is modified by someone else and passed on, we
  189. want its recipients to know that what they have is not the original, so
  190. that any problems introduced by others will not reflect on the original
  191. authors' reputations.
  192. The precise terms and conditions for copying, distribution and
  193. modification follow.
  194. @iftex
  195. @unnumberedsec TERMS AND CONDITIONS
  196. @end iftex
  197. @ifinfo
  198. @center TERMS AND CONDITIONS
  199. @end ifinfo
  200. @enumerate
  201. @item
  202. This License Agreement applies to any program or other work which
  203. contains a notice placed by the copyright holder saying it may be
  204. distributed under the terms of this General Public License. The
  205. ``Program'', below, refers to any such program or work, and a ``work based
  206. on the Program'' means either the Program or any work containing the
  207. Program or a portion of it, either verbatim or with modifications. Each
  208. licensee is addressed as ``you''.
  209. @item
  210. You may copy and distribute verbatim copies of the Program's source
  211. code as you receive it, in any medium, provided that you conspicuously and
  212. appropriately publish on each copy an appropriate copyright notice and
  213. disclaimer of warranty; keep intact all the notices that refer to this
  214. General Public License and to the absence of any warranty; and give any
  215. other recipients of the Program a copy of this General Public License
  216. along with the Program. You may charge a fee for the physical act of
  217. transferring a copy.
  218. @item
  219. You may modify your copy or copies of the Program or any portion of
  220. it, and copy and distribute such modifications under the terms of Paragraph
  221. 1 above, provided that you also do the following:
  222. @itemize @bullet
  223. @item
  224. cause the modified files to carry prominent notices stating that
  225. you changed the files and the date of any change; and
  226. @item
  227. cause the whole of any work that you distribute or publish, that
  228. in whole or in part contains the Program or any part thereof, either
  229. with or without modifications, to be licensed at no charge to all
  230. third parties under the terms of this General Public License (except
  231. that you may choose to grant warranty protection to some or all
  232. third parties, at your option).
  233. @item
  234. If the modified program normally reads commands interactively when
  235. run, you must cause it, when started running for such interactive use
  236. in the simplest and most usual way, to print or display an
  237. announcement including an appropriate copyright notice and a notice
  238. that there is no warranty (or else, saying that you provide a
  239. warranty) and that users may redistribute the program under these
  240. conditions, and telling the user how to view a copy of this General
  241. Public License.
  242. @item
  243. You may charge a fee for the physical act of transferring a
  244. copy, and you may at your option offer warranty protection in
  245. exchange for a fee.
  246. @end itemize
  247. Mere aggregation of another independent work with the Program (or its
  248. derivative) on a volume of a storage or distribution medium does not bring
  249. the other work under the scope of these terms.
  250. @item
  251. You may copy and distribute the Program (or a portion or derivative of
  252. it, under Paragraph 2) in object code or executable form under the terms of
  253. Paragraphs 1 and 2 above provided that you also do one of the following:
  254. @itemize @bullet
  255. @item
  256. accompany it with the complete corresponding machine-readable
  257. source code, which must be distributed under the terms of
  258. Paragraphs 1 and 2 above; or,
  259. @item
  260. accompany it with a written offer, valid for at least three
  261. years, to give any third party free (except for a nominal charge
  262. for the cost of distribution) a complete machine-readable copy of the
  263. corresponding source code, to be distributed under the terms of
  264. Paragraphs 1 and 2 above; or,
  265. @item
  266. accompany it with the information you received as to where the
  267. corresponding source code may be obtained. (This alternative is
  268. allowed only for noncommercial distribution and only if you
  269. received the program in object code or executable form alone.)
  270. @end itemize
  271. Source code for a work means the preferred form of the work for making
  272. modifications to it. For an executable file, complete source code means
  273. all the source code for all modules it contains; but, as a special
  274. exception, it need not include source code for modules which are standard
  275. libraries that accompany the operating system on which the executable
  276. file runs, or for standard header files or definitions files that
  277. accompany that operating system.
  278. @item
  279. You may not copy, modify, sublicense, distribute or transfer the
  280. Program except as expressly provided under this General Public License.
  281. Any attempt otherwise to copy, modify, sublicense, distribute or transfer
  282. the Program is void, and will automatically terminate your rights to use
  283. the Program under this License. However, parties who have received
  284. copies, or rights to use copies, from you under this General Public
  285. License will not have their licenses terminated so long as such parties
  286. remain in full compliance.
  287. @item
  288. By copying, distributing or modifying the Program (or any work based
  289. on the Program) you indicate your acceptance of this license to do so,
  290. and all its terms and conditions.
  291. @item
  292. Each time you redistribute the Program (or any work based on the
  293. Program), the recipient automatically receives a license from the original
  294. licensor to copy, distribute or modify the Program subject to these
  295. terms and conditions. You may not impose any further restrictions on the
  296. recipients' exercise of the rights granted herein.
  297. @item
  298. The Free Software Foundation may publish revised and/or new versions
  299. of the General Public License from time to time. Such new versions will
  300. be similar in spirit to the present version, but may differ in detail to
  301. address new problems or concerns.
  302. Each version is given a distinguishing version number. If the Program
  303. specifies a version number of the license which applies to it and ``any
  304. later version'', you have the option of following the terms and conditions
  305. either of that version or of any later version published by the Free
  306. Software Foundation. If the Program does not specify a version number of
  307. the license, you may choose any version ever published by the Free Software
  308. Foundation.
  309. @item
  310. If you wish to incorporate parts of the Program into other free
  311. programs whose distribution conditions are different, write to the author
  312. to ask for permission. For software which is copyrighted by the Free
  313. Software Foundation, write to the Free Software Foundation; we sometimes
  314. make exceptions for this. Our decision will be guided by the two goals
  315. of preserving the free status of all derivatives of our free software and
  316. of promoting the sharing and reuse of software generally.
  317. @iftex
  318. @heading NO WARRANTY
  319. @end iftex
  320. @ifinfo
  321. @center NO WARRANTY
  322. @end ifinfo
  323. @item
  324. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
  325. FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
  326. OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
  327. PROVIDE THE PROGRAM ``AS IS'' WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
  328. OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  329. MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
  330. TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
  331. PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
  332. REPAIR OR CORRECTION.
  333. @item
  334. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL
  335. ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
  336. REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
  337. INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES
  338. ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT
  339. LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES
  340. SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE
  341. WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN
  342. ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
  343. @end enumerate
  344. @iftex
  345. @heading END OF TERMS AND CONDITIONS
  346. @end iftex
  347. @ifinfo
  348. @center END OF TERMS AND CONDITIONS
  349. @end ifinfo
  350. @page
  351. @unnumberedsec Appendix: How to Apply These Terms
  352. If you develop a new program, and you want it to be of the greatest
  353. possible use to humanity, the best way to achieve this is to make it
  354. free software which everyone can redistribute and change under these
  355. terms.
  356. To do so, attach the following notices to the program. It is safest to
  357. attach them to the start of each source file to most effectively convey
  358. the exclusion of warranty; and each file should have at least the
  359. ``copyright'' line and a pointer to where the full notice is found.
  360. @smallexample
  361. @var{one line to give the program's name and a brief idea of what it does.}
  362. Copyright (C) 19@var{yy} @var{name of author}
  363. This program is free software; you can redistribute it and/or modify
  364. it under the terms of the GNU General Public License as published by
  365. the Free Software Foundation; either version 1, or (at your option)
  366. any later version.
  367. This program is distributed in the hope that it will be useful,
  368. but WITHOUT ANY WARRANTY; without even the implied warranty of
  369. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  370. GNU General Public License for more details.
  371. You should have received a copy of the GNU General Public License
  372. along with this program; if not, write to the Free Software
  373. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  374. @end smallexample
  375. Also add information on how to contact you by electronic and paper mail.
  376. If the program is interactive, make it output a short notice like this
  377. when it starts in an interactive mode:
  378. @smallexample
  379. Gnomovision version 69, Copyright (C) 19@var{yy} @var{name of author}
  380. Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
  381. This is free software, and you are welcome to redistribute it
  382. under certain conditions; type `show c' for details.
  383. @end smallexample
  384. The hypothetical commands `show w' and `show c' should show the
  385. appropriate parts of the General Public License. Of course, the
  386. commands you use may be called something other than `show w' and `show
  387. c'; they could even be mouse-clicks or menu items---whatever suits your
  388. program.
  389. You should also get your employer (if you work as a programmer) or your
  390. school, if any, to sign a ``copyright disclaimer'' for the program, if
  391. necessary. Here a sample; alter the names:
  392. @smallexample
  393. Yoyodyne, Inc., hereby disclaims all copyright interest in the program
  394. `Gnomovision' (a program to direct compilers to make passes at
  395. assemblers) written by James Hacker.
  396. @var{signature of Ty Coon}, 1 April 1989
  397. Ty Coon, President of Vice
  398. @end smallexample
  399. That's all there is to it!
  400. @node Concepts, Examples, Copying, Top
  401. @chapter The Concepts of Bison
  402. This chapter introduces many of the basic concepts without which the
  403. details of Bison will not make sense. If you do not already know how to
  404. use Bison or Yacc, we suggest you start by reading this chapter carefully.
  405. @menu
  406. * Language and Grammar:: Languages and context-free grammars,
  407. as mathematical ideas.
  408. * Grammar in Bison:: How we represent grammars for Bison's sake.
  409. * Semantic Values:: Each token or syntactic grouping can have
  410. a semantic value (the value of an integer,
  411. the name of an identifier, etc.).
  412. * Semantic Actions:: Each rule can have an action containing C code.
  413. * Bison Parser:: What are Bison's input and output,
  414. how is the output used?
  415. * Stages:: Stages in writing and running Bison grammars.
  416. * Grammar Layout:: Overall structure of a Bison grammar file.
  417. @end menu
  418. @node Language and Grammar, Grammar in Bison, Concepts, Concepts
  419. @section Languages and Context-Free Grammars
  420. @cindex context-free grammar
  421. @cindex grammar, context-free
  422. In order for Bison to parse a language, it must be described by a
  423. @dfn{context-free grammar}. This means that you specify one or more
  424. @dfn{syntactic groupings} and give rules for constructing them from their
  425. parts. For example, in the C language, one kind of grouping is called an
  426. `expression'. One rule for making an expression might be, ``An expression
  427. can be made of a minus sign and another expression''. Another would be,
  428. ``An expression can be an integer''. As you can see, rules are often
  429. recursive, but there must be at least one rule which leads out of the
  430. recursion.
  431. @cindex BNF
  432. @cindex Backus-Naur form
  433. The most common formal system for presenting such rules for humans to read
  434. is @dfn{Backus-Naur Form} or ``BNF'', which was developed in order to
  435. specify the language Algol 60. Any grammar expressed in BNF is a
  436. context-free grammar. The input to Bison is essentially machine-readable
  437. BNF.
  438. Not all context-free languages can be handled by Bison, only those
  439. that are LALR(1). In brief, this means that it must be possibly to
  440. tell how to parse any portion of an input string with just a single
  441. token of look-ahead. Strictly speaking, that is a description of an
  442. LR(1) grammar, and LALR(1) involves additional restrictions that are
  443. hard to explain simply; but it is rare in actual practice to find an
  444. LR(1) grammar that fails to be LALR(1). @xref{Mystery Conflicts, ,
  445. Mysterious Reduce/Reduce Conflicts}, for more information on this.
  446. @cindex symbols (abstract)
  447. @cindex token
  448. @cindex syntactic grouping
  449. @cindex grouping, syntactic
  450. In the formal grammatical rules for a language, each kind of syntactic unit
  451. or grouping is named by a @dfn{symbol}. Those which are built by grouping
  452. smaller constructs according to grammatical rules are called
  453. @dfn{nonterminal symbols}; those which can't be subdivided are called
  454. @dfn{terminal symbols} or @dfn{token types}. We call a piece of input
  455. corresponding to a single terminal symbol a @dfn{token}, and a piece
  456. corresponding to a single nonterminal symbol a @dfn{grouping}.@refill
  457. We can use the C language as an example of what symbols, terminal and
  458. nonterminal, mean. The tokens of C are identifiers, constants (numeric and
  459. string), and the various keywords, arithmetic operators and punctuation
  460. marks. So the terminal symbols of a grammar for C include `identifier',
  461. `number', `string', plus one symbol for each keyword, operator or
  462. punctuation mark: `if', `return', `const', `static', `int', `char',
  463. `plus-sign', `open-brace', `close-brace', `comma' and many more. (These
  464. tokens can be subdivided into characters, but that is a matter of
  465. lexicography, not grammar.)
  466. Here is a simple C function subdivided into tokens:
  467. @example
  468. int /* @r{keyword `int'} */
  469. square (x) /* @r{identifier, open-paren,} */
  470. /* @r{identifier, close-paren} */
  471. int x; /* @r{keyword `int', identifier, semicolon} */
  472. @{ /* @r{open-brace} */
  473. return x * x; /* @r{keyword `return', identifier,} */
  474. /* @r{asterisk, identifier, semicolon} */
  475. @} /* @r{close-brace} */
  476. @end example
  477. The syntactic groupings of C include the expression, the statement, the
  478. declaration, and the function definition. These are represented in the
  479. grammar of C by nonterminal symbols `expression', `statement',
  480. `declaration' and `function definition'. The full grammar uses dozens of
  481. additional language constructs, each with its own nonterminal symbol, in
  482. order to express the meanings of these four. The example above is a
  483. function definition; it contains one declaration, and one statement. In
  484. the statement, each @samp{x} is an expression and so is @samp{x * x}.
  485. Each nonterminal symbol must have grammatical rules showing how it is made
  486. out of simpler constructs. For example, one kind of C statement is the
  487. @code{return} statement; this would be described with a grammar rule which
  488. reads informally as follows:
  489. @quotation
  490. A `statement' can be made of a `return' keyword, an `expression' and a
  491. `semicolon'.
  492. @end quotation
  493. @noindent
  494. There would be many other rules for `statement', one for each kind of
  495. statement in C.
  496. @cindex start symbol
  497. One nonterminal symbol must be distinguished as the special one which
  498. defines a complete utterance in the language. It is called the @dfn{start
  499. symbol}. In a compiler, this means a complete input program. In the C
  500. language, the nonterminal symbol `sequence of definitions and declarations'
  501. plays this role.
  502. For example, @samp{1 + 2} is a valid C expression---a valid part of a C
  503. program---but it is not valid as an @emph{entire} C program. In the
  504. context-free grammar of C, this follows from the fact that `expression' is
  505. not the start symbol.
  506. The Bison parser reads a sequence of tokens as its input, and groups the
  507. tokens using the grammar rules. If the input is valid, the end result is
  508. that the entire token sequence reduces to a single grouping whose symbol is
  509. the grammar's start symbol. If we use a grammar for C, the entire input
  510. must be a `sequence of definitions and declarations'. If not, the parser
  511. reports a syntax error.
  512. @node Grammar in Bison, Semantic Values, Language and Grammar, Concepts
  513. @section From Formal Rules to Bison Input
  514. @cindex Bison grammar
  515. @cindex grammar, Bison
  516. @cindex formal grammar
  517. A formal grammar is a mathematical construct. To define the language
  518. for Bison, you must write a file expressing the grammar in Bison syntax:
  519. a @dfn{Bison grammar} file. @xref{Grammar File}.
  520. A nonterminal symbol in the formal grammar is represented in Bison input
  521. as an identifier, like an identifier in C. By convention, it should be
  522. in lower case, such as @code{expr}, @code{stmt} or @code{declaration}.
  523. The Bison representation for a terminal symbol is also called a @dfn{token
  524. type}. Token types as well can be represented as C-like identifiers. By
  525. convention, these identifiers should be upper case to distinguish them from
  526. nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or
  527. @code{RETURN}. A terminal symbol that stands for a particular keyword in
  528. the language should be named after that keyword converted to upper case.
  529. The terminal symbol @code{error} is reserved for error recovery.
  530. @xref{Symbols}.@refill
  531. A terminal symbol can also be represented as a character literal, just like
  532. a C character constant. You should do this whenever a token is just a
  533. single character (parenthesis, plus-sign, etc.): use that same character in
  534. a literal as the terminal symbol for that token.
  535. The grammar rules also have an expression in Bison syntax. For example,
  536. here is the Bison rule for a C @code{return} statement. The semicolon in
  537. quotes is a literal character token, representing part of the C syntax for
  538. the statement; the naked semicolon, and the colon, are Bison punctuation
  539. used in every rule.
  540. @example
  541. stmt: RETURN expr ';'
  542. ;
  543. @end example
  544. @noindent
  545. @xref{Rules}.
  546. @node Semantic Values, Semantic Actions, Grammar in Bison, Concepts
  547. @section Semantic Values
  548. @cindex semantic value
  549. @cindex value, semantic
  550. A formal grammar selects tokens only by their classifications: for example,
  551. if a rule mentions the terminal symbol `integer constant', it means that
  552. @emph{any} integer constant is grammatically valid in that position. The
  553. precise value of the constant is irrelevant to how to parse the input: if
  554. @samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally
  555. grammatical.@refill
  556. But the precise value is very important for what the input means once it is
  557. parsed. A compiler is useless if it fails to distinguish between 4, 1 and
  558. 3989 as constants in the program! Therefore, each token in a Bison grammar
  559. has both a token type and a @dfn{semantic value}. @xref{Semantics},
  560. for details.
  561. The token type is a terminal symbol defined in the grammar, such as
  562. @code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything
  563. you need to know to decide where the token may validly appear and how to
  564. group it with other tokens. The grammar rules know nothing about tokens
  565. except their types.@refill
  566. The semantic value has all the rest of the information about the
  567. meaning of the token, such as the value of an integer, or the name of an
  568. identifier. (A token such as @code{','} which is just punctuation doesn't
  569. need to have any semantic value.)
  570. For example, an input token might be classified as token type
  571. @code{INTEGER} and have the semantic value 4. Another input token might
  572. have the same token type @code{INTEGER} but value 3989. When a grammar
  573. rule says that @code{INTEGER} is allowed, either of these tokens is
  574. acceptable because each is an @code{INTEGER}. When the parser accepts the
  575. token, it keeps track of the token's semantic value.
  576. Each grouping can also have a semantic value as well as its nonterminal
  577. symbol. For example, in a calculator, an expression typically has a
  578. semantic value that is a number. In a compiler for a programming
  579. language, an expression typically has a semantic value that is a tree
  580. structure describing the meaning of the expression.
  581. @node Semantic Actions, Bison Parser, Semantic Values, Concepts
  582. @section Semantic Actions
  583. @cindex semantic actions
  584. @cindex actions, semantic
  585. In order to be useful, a program must do more than parse input; it must
  586. also produce some output based on the input. In a Bison grammar, a grammar
  587. rule can have an @dfn{action} made up of C statements. Each time the
  588. parser recognizes a match for that rule, the action is executed.
  589. @xref{Actions}.
  590. Most of the time, the purpose of an action is to compute the semantic value
  591. of the whole construct from the semantic values of its parts. For example,
  592. suppose we have a rule which says an expression can be the sum of two
  593. expressions. When the parser recognizes such a sum, each of the
  594. subexpressions has a semantic value which describes how it was built up.
  595. The action for this rule should create a similar sort of value for the
  596. newly recognized larger expression.
  597. For example, here is a rule that says an expression can be the sum of
  598. two subexpressions:
  599. @example
  600. expr: expr '+' expr @{ $$ = $1 + $3; @}
  601. ;
  602. @end example
  603. @noindent
  604. The action says how to produce the semantic value of the sum expression
  605. from the values of the two subexpressions.
  606. @node Bison Parser, Stages, Semantic Actions, Concepts
  607. @section Bison Output: the Parser File
  608. @cindex Bison parser
  609. @cindex Bison utility
  610. @cindex lexical analyzer, purpose
  611. @cindex parser
  612. When you run Bison, you give it a Bison grammar file as input. The output
  613. is a C source file that parses the language described by the grammar.
  614. This file is called a @dfn{Bison parser}. Keep in mind that the Bison
  615. utility and the Bison parser are two distinct programs: the Bison utility
  616. is a program whose output is the Bison parser that becomes part of your
  617. program.
  618. The job of the Bison parser is to group tokens into groupings according to
  619. the grammar rules---for example, to build identifiers and operators into
  620. expressions. As it does this, it runs the actions for the grammar rules it
  621. uses.
  622. The tokens come from a function called the @dfn{lexical analyzer} that you
  623. must supply in some fashion (such as by writing it in C). The Bison parser
  624. calls the lexical analyzer each time it wants a new token. It doesn't know
  625. what is ``inside'' the tokens (though their semantic values may reflect
  626. this). Typically the lexical analyzer makes the tokens by parsing
  627. characters of text, but Bison does not depend on this. @xref{Lexical}.
  628. The Bison parser file is C code which defines a function named
  629. @code{yyparse} which implements that grammar. This function does not make
  630. a complete C program: you must supply some additional functions. One is
  631. the lexical analyzer. Another is an error-reporting function which the
  632. parser calls to report an error. In addition, a complete C program must
  633. start with a function called @code{main}; you have to provide this, and
  634. arrange for it to call @code{yyparse} or the parser will never run.
  635. @xref{Interface}.
  636. Aside from the token type names and the symbols in the actions you
  637. write, all variable and function names used in the Bison parser file
  638. begin with @samp{yy} or @samp{YY}. This includes interface functions
  639. such as the lexical analyzer function @code{yylex}, the error reporting
  640. function @code{yyerror} and the parser function @code{yyparse} itself.
  641. This also includes numerous identifiers used for internal purposes.
  642. Therefore, you should avoid using C identifiers starting with @samp{yy}
  643. or @samp{YY} in the Bison grammar file except for the ones defined in
  644. this manual.
  645. @node Stages, Grammar Layout, Bison Parser, Concepts
  646. @section Stages in Using Bison
  647. @cindex stages in using Bison
  648. @cindex using Bison
  649. The actual language-design process using Bison, from grammar specification
  650. to a working compiler or interpreter, has these parts:
  651. @enumerate
  652. @item
  653. Formally specify the grammar in a form recognized by Bison
  654. (@pxref{Grammar File}). For each grammatical rule in the language,
  655. describe the action that is to be taken when an instance of that rule
  656. is recognized. The action is described by a sequence of C statements.
  657. @item
  658. Write a lexical analyzer to process input and pass tokens to the
  659. parser. The lexical analyzer may be written by hand in C
  660. (@pxref{Lexical}). It could also be produced using Lex, but the use
  661. of Lex is not discussed in this manual.
  662. @item
  663. Write a controlling function that calls the Bison-produced parser.
  664. @item
  665. Write error-reporting routines.
  666. @end enumerate
  667. To turn this source code as written into a runnable program, you
  668. must follow these steps:
  669. @enumerate
  670. @item
  671. Run Bison on the grammar to produce the parser.
  672. @item
  673. Compile the code output by Bison, as well as any other source files.
  674. @item
  675. Link the object files to produce the finished product.
  676. @end enumerate
  677. @node Grammar Layout,, Stages, Concepts
  678. @section The Overall Layout of a Bison Grammar
  679. @cindex grammar file
  680. @cindex file format
  681. @cindex format of grammar file
  682. @cindex layout of Bison grammar
  683. The input file for the Bison utility is a @dfn{Bison grammar file}. The
  684. general form of a Bison grammar file is as follows:
  685. @example
  686. %@{
  687. @var{C declarations}
  688. %@}
  689. @var{Bison declarations}
  690. %%
  691. @var{Grammar rules}
  692. %%
  693. @var{Additional C code}
  694. @end example
  695. @noindent
  696. The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears
  697. in every Bison grammar file to separate the sections.
  698. The C declarations may define types and variables used in the actions.
  699. You can also use preprocessor commands to define macros used there, and use
  700. @code{#include} to include header files that do any of these things.
  701. The Bison declarations declare the names of the terminal and nonterminal
  702. symbols, and may also describe operator precedence and the data types of
  703. semantic values of various symbols.
  704. The grammar rules define how to construct each nonterminal symbol from its
  705. parts.
  706. The additional C code can contain any C code you want to use. Often the
  707. definition of the lexical analyzer @code{yylex} goes here, plus subroutines
  708. called by the actions in the grammar rules. In a simple program, all the
  709. rest of the program can go here.
  710. @node Examples, Grammar File, Concepts, Top
  711. @chapter Examples
  712. @cindex simple examples
  713. @cindex examples, simple
  714. Now we show and explain three sample programs written using Bison: a
  715. reverse polish notation calculator, an algebraic (infix) notation
  716. calculator, and a multi-function calculator. All three have been tested
  717. under BSD Unix 4.3; each produces a usable, though limited, interactive
  718. desk-top calculator.
  719. These examples are simple, but Bison grammars for real programming
  720. languages are written the same way.
  721. @ifinfo
  722. You can copy these examples out of the Info file and into a source file
  723. to try them.
  724. @end ifinfo
  725. @menu
  726. * RPN Calc:: Reverse polish notation calculator;
  727. a first example with no operator precedence.
  728. * Infix Calc:: Infix (algebraic) notation calculator.
  729. Operator precedence is introduced.
  730. * Simple Error Recovery:: Continuing after syntax errors.
  731. * Multi-function Calc:: Calculator with memory and trig functions.
  732. It uses multiple data-types for semantic values.
  733. * Exercises:: Ideas for improving the multi-function calculator.
  734. @end menu
  735. @node RPN Calc, Infix Calc, Examples, Examples
  736. @section Reverse Polish Notation Calculator
  737. @cindex reverse polish notation
  738. @cindex polish notation calculator
  739. @cindex @code{rpcalc}
  740. @cindex calculator, simple
  741. The first example is that of a simple double-precision @dfn{reverse polish
  742. notation} calculator (a calculator using postfix operators). This example
  743. provides a good starting point, since operator precedence is not an issue.
  744. The second example will illustrate how operator precedence is handled.
  745. The source code for this calculator is named @file{rpcalc.y}. The
  746. @samp{.y} extension is a convention used for Bison input files.
  747. @menu
  748. * Decls: Rpcalc Decls. Bison and C declarations for rpcalc.
  749. * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
  750. * Input: Rpcalc Input. Explaining the rules for @code{input}.
  751. * Line: Rpcalc Line. Explaining the rules for @code{line}.
  752. * Expr: Rpcalc Expr. Explaining the rules for @code{expr}.
  753. * Lexer: Rpcalc Lexer. The lexical analyzer.
  754. * Main: Rpcalc Main. The controlling function.
  755. * Error: Rpcalc Error. The error reporting function.
  756. * Gen: Rpcalc Gen. Running Bison on the grammar file.
  757. * Comp: Rpcalc Compile. Run the C compiler on the output code.
  758. @end menu
  759. @node Rpcalc Decls, Rpcalc Rules, RPN calc, RPN calc
  760. @subsection Declarations for @code{rpcalc}
  761. Here are the C and Bison declarations for the reverse polish notation
  762. calculator. As in C, comments are placed between @samp{/*@dots{}*/}.
  763. @example
  764. /* Reverse polish notation calculator. */
  765. %@{
  766. #define YYSTYPE double
  767. #include <math.h>
  768. %@}
  769. %token NUM
  770. %% /* Grammar rules and actions follow */
  771. @end example
  772. The C declarations section (@pxref{C Declarations}) contains two
  773. preprocessor directives.
  774. The @code{#define} directive defines the macro @code{YYSTYPE}, thus
  775. specifying the C data type for semantic values of both tokens and groupings
  776. (@pxref{Value Type}). The Bison parser will use whatever type
  777. @code{YYSTYPE} is defined as; if you don't define it, @code{int} is the
  778. default. Because we specify @code{double}, each token and each expression
  779. has an associated value, which is a floating point number.
  780. The @code{#include} directive is used to declare the exponentiation
  781. function @code{pow}.
  782. The second section, Bison declarations, provides information to Bison about
  783. the token types (@pxref{Bison Declarations}). Each terminal symbol that is
  784. not a single-character literal must be declared here. (Single-character
  785. literals normally don't need to be declared.) In this example, all the
  786. arithmetic operators are designated by single-character literals, so the
  787. only terminal symbol that needs to be declared is @code{NUM}, the token
  788. type for numeric constants.
  789. @node Rpcalc Rules, Rpcalc Input, Rpcalc Decls, RPN Calc
  790. @subsection Grammar Rules for @code{rpcalc}
  791. Here are the grammar rules for the reverse polish notation calculator.
  792. @example
  793. input: /* empty */
  794. | input line
  795. ;
  796. line: '\n'
  797. | exp '\n' @{ printf ("\t%.10g\n", $1); @}
  798. ;
  799. exp: NUM @{ $$ = $1; @}
  800. | exp exp '+' @{ $$ = $1 + $2; @}
  801. | exp exp '-' @{ $$ = $1 - $2; @}
  802. | exp exp '*' @{ $$ = $1 * $2; @}
  803. | exp exp '/' @{ $$ = $1 / $2; @}
  804. /* Exponentiation */
  805. | exp exp '^' @{ $$ = pow ($1, $2); @}
  806. /* Unary minus */
  807. | exp 'n' @{ $$ = -$1; @}
  808. ;
  809. %%
  810. @end example
  811. The groupings of the rpcalc ``language'' defined here are the expression
  812. (given the name @code{exp}), the line of input (@code{line}), and the
  813. complete input transcript (@code{input}). Each of these nonterminal
  814. symbols has several alternate rules, joined by the @samp{|} punctuator
  815. which is read as ``or''. The following sections explain what these rules
  816. mean.
  817. The semantics of the language is determined by the actions taken when a
  818. grouping is recognized. The actions are the C code that appears inside
  819. braces. @xref{Actions}.
  820. You must specify these actions in C, but Bison provides the means for
  821. passing semantic values between the rules. In each action, the
  822. pseudo-variable @code{$$} stands for the semantic value for the grouping
  823. that the rule is going to construct. Assigning a value to @code{$$} is the
  824. main job of most actions. The semantic values of the components of the
  825. rule are referred to as @code{$1}, @code{$2}, and so on.
  826. @node Rpcalc Input, Rpcalc Line, Rpcalc Rules, RPN Calc
  827. @subsubsection Explanation of @code{input}
  828. Consider the definition of @code{input}:
  829. @example
  830. input: /* empty */
  831. | input line
  832. ;
  833. @end example
  834. This definition reads as follows: ``A complete input is either an empty
  835. string, or a complete input followed by an input line''. Notice that
  836. ``complete input'' is defined in terms of itself. This definition is said
  837. to be @dfn{left recursive} since @code{input} appears always as the
  838. leftmost symbol in the sequence. @xref{Recursion}.
  839. The first alternative is empty because there are no symbols between the
  840. colon and the first @samp{|}; this means that @code{input} can match an
  841. empty string of input (no tokens). We write the rules this way because it
  842. is legitimate to type @kbd{Ctrl-d} right after you start the calculator.
  843. It's conventional to put an empty alternative first and write the comment
  844. @samp{/* empty */} in it.
  845. The second alternate rule (@code{input line}) handles all nontrivial input.
  846. It means, ``After reading any number of lines, read one more line if
  847. possible.'' The left recursion makes this rule into a loop. Since the
  848. first alternative matches empty input, the loop can be executed zero or
  849. more times.
  850. The parser function @code{yyparse} continues to process input until a
  851. grammatical error is seen or the lexical analyzer says there are no more
  852. input tokens; we will arrange for the latter to happen at end of file.
  853. @node Rpcalc Line, Rpcalc Expr, Rpcalc Input, RPN Calc
  854. @subsubsection Explanation of @code{line}
  855. Now consider the definition of @code{line}:
  856. @example
  857. line: '\n'
  858. | exp '\n' @{ printf ("\t%.10g\n", $1); @}
  859. ;
  860. @end example
  861. The first alternative is a token which is a newline character; this means
  862. that rpcalc accepts a blank line (and ignores it, since there is no
  863. action). The second alternative is an expression followed by a newline.
  864. This is the alternative that makes rpcalc useful. The semantic value of
  865. the @code{exp} grouping is the value of @code{$1} because the @code{exp} in
  866. question is the first symbol in the alternative. The action prints this
  867. value, which is the result of the computation the user asked for.
  868. This action is unusual because it does not assign a value to @code{$$}. As
  869. a consequence, the semantic value associated with the @code{line} is
  870. uninitialized (its value will be unpredictable). This would be a bug if
  871. that value were ever used, but we don't use it: once rpcalc has printed the
  872. value of the user's input line, that value is no longer needed.
  873. @node Rpcalc Expr, Rpcalc Lexer, Rpcalc Line, RPN Calc
  874. @subsubsection Explanation of @code{expr}
  875. The @code{exp} grouping has several rules, one for each kind of expression.
  876. The first rule handles the simplest expressions: those that are just numbers.
  877. The second handles an addition-expression, which looks like two expressions
  878. followed by a plus-sign. The third handles subtraction, and so on.
  879. @example
  880. exp: NUM
  881. | exp exp '+' @{ $$ = $1 + $2; @}
  882. | exp exp '-' @{ $$ = $1 - $2; @}
  883. @dots{}
  884. ;
  885. @end example
  886. We have used @samp{|} to join all the rules for @code{exp}, but we could
  887. equally well have written them separately:
  888. @example
  889. exp: NUM ;
  890. exp: exp exp '+' @{ $$ = $1 + $2; @} ;
  891. exp: exp exp '-' @{ $$ = $1 - $2; @} ;
  892. @dots{}
  893. @end example
  894. Most of the rules have actions that compute the value of the expression in
  895. terms of the value of its parts. For example, in the rule for addition,
  896. @code{$1} refers to the first component @code{exp} and @code{$2} refers to
  897. the second one. The third component, @code{'+'}, has no meaningful
  898. associated semantic value, but if it had one you could refer to it as
  899. @code{$3}. When @code{yyparse} recognizes a sum expression using this
  900. rule, the sum of the two subexpressions' values is produced as the value of
  901. the entire expression. @xref{Actions}.
  902. You don't have to give an action for every rule. When a rule has no
  903. action, Bison by default copies the value of @code{$1} into @code{$$}.
  904. This is what happens in the first rule (the one that uses @code{NUM}).
  905. The formatting shown here is the recommended convention, but Bison does
  906. not require it. You can add or change whitespace as much as you wish.
  907. For example, this:
  908. @example
  909. exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{}
  910. @end example
  911. @noindent
  912. means the same thing as this:
  913. @example
  914. exp: NUM
  915. | exp exp '+' @{ $$ = $1 + $2; @}
  916. | @dots{}
  917. @end example
  918. @noindent
  919. The latter, however, is much more readable.
  920. @node Rpcalc Lexer, Rpcalc Main, Rpcalc Expr, RPN Calc
  921. @subsection The @code{rpcalc} Lexical Analyzer
  922. @cindex writing a lexical analyzer
  923. @cindex lexical analyzer, writing
  924. The lexical analyzer's job is low-level parsing: converting characters or
  925. sequences of characters into tokens. The Bison parser gets its tokens by
  926. calling the lexical analyzer. @xref{Lexical}.
  927. Only a simple lexical analyzer is needed for the RPN calculator. This
  928. lexical analyzer skips blanks and tabs, then reads in numbers as
  929. @code{double} and returns them as @code{NUM} tokens. Any other character
  930. that isn't part of a number is a separate token. Note that the token-code
  931. for such a single-character token is the character itself.
  932. The return value of the lexical analyzer function is a numeric code which
  933. represents a token type. The same text used in Bison rules to stand for
  934. this token type is also a C expression for the numeric code for the type.
  935. This works in two ways. If the token type is a character literal, then its
  936. numeric code is the ASCII code for that character; you can use the same
  937. character literal in the lexical analyzer to express the number. If the
  938. token type is an identifier, that identifier is defined by Bison as a C
  939. macro whose definition is the appropriate number. In this example,
  940. therefore, @code{NUM} becomes a macro for @code{yylex} to use.
  941. The semantic value of the token (if it has one) is stored into the global
  942. variable @code{yylval}, which is where the Bison parser will look for it.
  943. (The C data type of @code{yylval} is @code{YYSTYPE}, which was defined
  944. at the beginning of the grammar; @pxref{Rpcalc Decls}.)
  945. A token type code of zero is returned if the end-of-file is encountered.
  946. (Bison recognizes any nonpositive value as indicating the end of the
  947. input.)
  948. Here is the code for the lexical analyzer:
  949. @example
  950. /* Lexical analyzer returns a double floating point
  951. number on the stack and the token NUM, or the ASCII
  952. character read if not a number. Skips all blanks
  953. and tabs, returns 0 for EOF. */
  954. #include <ctype.h>
  955. yylex ()
  956. @{
  957. int c;
  958. /* skip white space */
  959. while ((c = getchar ()) == ' ' || c == '\t')
  960. ;
  961. /* process numbers */
  962. if (c == '.' || isdigit (c))
  963. @{
  964. ungetc (c, stdin);
  965. scanf ("%lf", &yylval);
  966. return NUM;
  967. @}
  968. /* return end-of-file */
  969. if (c == EOF)
  970. return 0;
  971. /* return single chars */
  972. return c;
  973. @}
  974. @end example
  975. @node Rpcalc Main, Rpcalc Error, Rpcalc Lexer, RPN Calc
  976. @subsection The Controlling Function
  977. @cindex controlling function
  978. @cindex main function in simple example
  979. In keeping with the spirit of this example, the controlling function is
  980. kept to the bare minimum. The only requirement is that it call
  981. @code{yyparse} to start the process of parsing.
  982. @example
  983. main ()
  984. @{
  985. yyparse ();
  986. @}
  987. @end example
  988. @node Rpcalc Error, Rpcalc Gen, Rpcalc Main, RPN Calc
  989. @subsection The Error Reporting Routine
  990. @cindex error reporting routine
  991. When @code{yyparse} detects a syntax error, it calls the error reporting
  992. function @code{yyerror} to print an error message (usually but not always
  993. @code{"parse error"}). It is up to the programmer to supply @code{yyerror}
  994. (@pxref{Interface}), so here is the definition we will use:
  995. @example
  996. #include <stdio.h>
  997. yyerror (s) /* Called by yyparse on error */
  998. char *s;
  999. @{
  1000. printf ("%s\n", s);
  1001. @}
  1002. @end example
  1003. After @code{yyerror} returns, the Bison parser may recover from the error
  1004. and continue parsing if the grammar contains a suitable error rule
  1005. (@pxref{Error Recovery}). Otherwise, @code{yyparse} returns nonzero. We
  1006. have not written any error rules in this example, so any invalid input will
  1007. cause the calculator program to exit. This is not clean behavior for a
  1008. real calculator, but it is adequate in the first example.
  1009. @node Rpcalc Gen, Rpcalc Compile, Rpcalc Error, RPN Calc
  1010. @subsection Running Bison to Make the Parser
  1011. @cindex running Bison (introduction)
  1012. Before running Bison to produce a parser, we need to decide how to arrange
  1013. all the source code in one or more source files. For such a simple example,
  1014. the easiest thing is to put everything in one file. The definitions of
  1015. @code{yylex}, @code{yyerror} and @code{main} go at the end, in the
  1016. ``additional C code'' section of the file (@pxref{Grammar Layout}).
  1017. For a large project, you would probably have several source files, and use
  1018. @code{make} to arrange to recompile them.
  1019. With all the source in a single file, you use the following command to
  1020. convert it into a parser file:
  1021. @example
  1022. bison @var{file_name}.y
  1023. @end example
  1024. @noindent
  1025. In this example the file was called @file{rpcalc.y} (for ``Reverse Polish
  1026. CALCulator''). Bison produces a file named @file{@var{file_name}.tab.c},
  1027. removing the @samp{.y} from the original file name. The file output by
  1028. Bison contains the source code for @code{yyparse}. The additional
  1029. functions in the input file (@code{yylex}, @code{yyerror} and @code{main})
  1030. are copied verbatim to the output.
  1031. @node Rpcalc Compile,, Rpcalc Gen, RPN Calc
  1032. @subsection Compiling the Parser File
  1033. @cindex compiling the parser
  1034. Here is how to compile and run the parser file:
  1035. @example
  1036. # @r{List files in current directory.}
  1037. % ls
  1038. rpcalc.tab.c rpcalc.y
  1039. # @r{Compile the Bison parser.}
  1040. # @r{@samp{-lm} tells compiler to search math library for @code{pow}.}
  1041. % cc rpcalc.tab.c -lm -o rpcalc
  1042. # @r{List files again.}
  1043. % ls
  1044. rpcalc rpcalc.tab.c rpcalc.y
  1045. @end example
  1046. The file @file{rpcalc} now contains the executable code. Here is an
  1047. example session using @code{rpcalc}.
  1048. @example
  1049. % rpcalc
  1050. 4 9 +
  1051. 13
  1052. 3 7 + 3 4 5 *+-
  1053. -13
  1054. 3 7 + 3 4 5 * + - n @r{Note the unary minus, @samp{n}}
  1055. 13
  1056. 5 6 / 4 n +
  1057. -3.166666667
  1058. 3 4 ^ @r{Exponentiation}
  1059. 81
  1060. ^D @r{End-of-file indicator}
  1061. %
  1062. @end example
  1063. @node Infix Calc, Simple Error Recovery, RPN Calc, Examples
  1064. @section Infix Notation Calculator: @code{calc}
  1065. @cindex infix notation calculator
  1066. @cindex @code{calc}
  1067. @cindex calculator, infix notation
  1068. We now modify rpcalc to handle infix operators instead of postfix. Infix
  1069. notation involves the concept of operator precedence and the need for
  1070. parentheses nested to arbitrary depth. Here is the Bison code for
  1071. @file{calc.y}, an infix desk-top calculator.
  1072. @example
  1073. /* Infix notation calculator--calc */
  1074. %@{
  1075. #define YYSTYPE double
  1076. #include <math.h>
  1077. %@}
  1078. /* BISON Declarations */
  1079. %token NUM
  1080. %left '-' '+'
  1081. %left '*' '/'
  1082. %left NEG /* negation--unary minus */
  1083. %right '^' /* exponentiation */
  1084. /* Grammar follows */
  1085. %%
  1086. input: /* empty string */
  1087. | input line
  1088. ;
  1089. line: '\n'
  1090. | exp '\n' @{ printf("\t%.10g\n", $1); @}
  1091. ;
  1092. exp: NUM @{ $$ = $1; @}
  1093. | exp '+' exp @{ $$ = $1 + $3; @}
  1094. | exp '-' exp @{ $$ = $1 - $3; @}
  1095. | exp '*' exp @{ $$ = $1 * $3; @}
  1096. | exp '/' exp @{ $$ = $1 / $3; @}
  1097. | '-' exp %prec NEG @{ $$ = -$2; @}
  1098. | exp '^' exp @{ $$ = pow ($1, $3); @}
  1099. | '(' exp ')' @{ $$ = $2; @}
  1100. ;
  1101. %%
  1102. @end example
  1103. @noindent
  1104. The functions @code{yylex}, @code{yyerror} and @code{main} can be the same
  1105. as before.
  1106. There are two important new features shown in this code.
  1107. In the second section (Bison declarations), @code{%left} declares token
  1108. types and says they are left-associative operators. The declarations
  1109. @code{%left} and @code{%right} (right associativity) take the place of
  1110. @code{%token} which is used to declare a token type name without
  1111. associativity. (These tokens are single-character literals, which
  1112. ordinarily don't need to be declared. We declare them here to specify
  1113. the associativity.)
  1114. Operator precedence is determined by the line ordering of the
  1115. declarations; the higher the line number of the declaration (lower on
  1116. the page or screen), the higher the precedence. Hence, exponentiation
  1117. has the highest precedence, unary minus (@code{NEG}) is next, followed
  1118. by @samp{*} and @samp{/}, and so on. @xref{Precedence}.
  1119. The other important new feature is the @code{%prec} in the grammar section
  1120. for the unary minus operator. The @code{%prec} simply instructs Bison that
  1121. the rule @samp{| '-' exp} has the same precedence as @code{NEG}---in this
  1122. case the next-to-highest. @xref{Contextual Precedence}.
  1123. Here is a sample run of @file{calc.y}:
  1124. @need 500
  1125. @example
  1126. % calc
  1127. 4 + 4.5 - (34/(8*3+-3))
  1128. 6.880952381
  1129. -56 + 2
  1130. -54
  1131. 3 ^ 2
  1132. 9
  1133. @end example
  1134. @node Simple Error Recovery, Multi-function Calc, Infix Calc, Examples
  1135. @section Simple Error Recovery
  1136. @cindex error recovery, simple
  1137. Up to this point, this manual has not addressed the issue of @dfn{error
  1138. recovery}---how to continue parsing after the parser detects a syntax
  1139. error. All we have handled is error reporting with @code{yyerror}. Recall
  1140. that by default @code{yyparse} returns after calling @code{yyerror}. This
  1141. means that an erroneous input line causes the calculator program to exit.
  1142. Now we show how to rectify this deficiency.
  1143. The Bison language itself includes the reserved word @code{error}, which
  1144. may be included in the grammar rules. In the example below it has
  1145. been added to one of the alternatives for @code{line}:
  1146. @example
  1147. line: '\n'
  1148. | exp '\n' @{ printf("\t%.10g\n", $1); @}
  1149. | error '\n' @{ yyerrok; @}
  1150. ;
  1151. @end example
  1152. This addition to the grammar allows for simple error recovery in the event
  1153. of a parse error. If an expression that cannot be evaluated is read, the
  1154. error will be recognized by the third rule for @code{line}, and parsing
  1155. will continue. (The @code{yyerror} function is still called upon to print
  1156. its message as well.) The action executes the statement @code{yyerrok}, a
  1157. macro defined automatically by Bison; its meaning is that error recovery is
  1158. complete (@pxref{Error Recovery}). Note the difference between
  1159. @code{yyerrok} and @code{yyerror}; neither one is a misprint.@refill
  1160. This form of error recovery deals with syntax errors. There are other
  1161. kinds of errors; for example, division by zero, which raises an exception
  1162. signal that is normally fatal. A real calculator program must handle this
  1163. signal and use @code{longjmp} to return to @code{main} and resume parsing
  1164. input lines; it would also have to discard the rest of the current line of
  1165. input. We won't discuss this issue further because it is not specific to
  1166. Bison programs.
  1167. @node Multi-function Calc, Exercises, Simple Error Recovery, Examples
  1168. @section Multi-Function Calculator: @code{mfcalc}
  1169. @cindex multi-function calculator
  1170. @cindex @code{mfcalc}
  1171. @cindex calculator, multi-function
  1172. Now that the basics of Bison have been discussed, it is time to move on to
  1173. a more advanced problem. The above calculators provided only five
  1174. functions, @samp{+}, @samp{-}, @samp{*}, @samp{/} and @samp{^}. It would
  1175. be nice to have a calculator that provides other mathematical functions such
  1176. as @code{sin}, @code{cos}, etc.
  1177. It is easy to add new operators to the infix calculator as long as they are
  1178. only single-character literals. The lexical analyzer @code{yylex} passes
  1179. back all non-number characters as tokens, so new grammar rules suffice for
  1180. adding a new operator. But we want something more flexible: built-in
  1181. functions whose syntax has this form:
  1182. @example
  1183. @var{function_name} (@var{argument})
  1184. @end example
  1185. @noindent
  1186. At the same time, we will add memory to the calculator, by allowing you
  1187. to create named variables, store values in them, and use them later.
  1188. Here is a sample session with the multi-function calculator:
  1189. @example
  1190. % acalc
  1191. pi = 3.141592653589
  1192. 3.1415926536
  1193. sin(pi)
  1194. 0.0000000000
  1195. alpha = beta1 = 2.3
  1196. 2.3000000000
  1197. alpha
  1198. 2.3000000000
  1199. ln(alpha)
  1200. 0.8329091229
  1201. exp(ln(beta1))
  1202. 2.3000000000
  1203. %
  1204. @end example
  1205. Note that multiple assignment and nested function calls are permitted.
  1206. @menu
  1207. * Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
  1208. * Rules: Mfcalc Rules. Grammar rules for the calculator.
  1209. * Symtab: Mfcalc Symtab. Symbol table management subroutines.
  1210. @end menu
  1211. @node Mfcalc Decl, Mfcalc Rules, Multi-function Calc, Multi-function Calc
  1212. @subsection Declarations for @code{mfcalc}
  1213. Here are the C and Bison declarations for the multi-function calculator.
  1214. @smallexample
  1215. %@{
  1216. #include <math.h> /* For math functions, cos(), sin(), etc. */
  1217. #include "calc.h" /* Contains definition of `symrec' */
  1218. %@}
  1219. %union @{
  1220. double val; /* For returning numbers. */
  1221. symrec *tptr; /* For returning symbol-table pointers */
  1222. @}
  1223. %token <val> NUM /* Simple double precision number */
  1224. %token <tptr> VAR FNCT /* Variable and Function */
  1225. %type <val> exp
  1226. %right '='
  1227. %left '-' '+'
  1228. %left '*' '/'
  1229. %left NEG /* Negation--unary minus */
  1230. %right '^' /* Exponentiation */
  1231. /* Grammar follows */
  1232. %%
  1233. @end smallexample
  1234. The above grammar introduces only two new features of the Bison language.
  1235. These features allow semantic values to have various data types
  1236. (@pxref{Multiple Types}).
  1237. The @code{%union} declaration specifies the entire list of possible types;
  1238. this is instead of defining @code{YYSTYPE}. The allowable types are now
  1239. double-floats (for @code{exp} and @code{NUM}) and pointers to entries in
  1240. the symbol table. @xref{Union Decl}.
  1241. Since values can now have various types, it is necessary to associate a
  1242. type with each grammar symbol whose semantic value is used. These symbols
  1243. are @code{NUM}, @code{VAR}, @code{FNCT}, and @code{exp}. Their
  1244. declarations are augmented with information about their data type (placed
  1245. between angle brackets).
  1246. The Bison construct @code{%type} is used for declaring nonterminal symbols,
  1247. just as @code{%token} is used for declaring token types. We have not used
  1248. @code{%type} before because nonterminal symbols are normally declared
  1249. implicitly by the rules that define them. But @code{exp} must be declared
  1250. explicitly so we can specify its value type. @xref{Type Decl}.
  1251. @node Mfcalc Rules, Mfcalc Symtab, Mfcalc Decl, Multi-function Calc
  1252. @subsection Grammar Rules for @code{mfcalc}
  1253. Here are the grammar rules for the multi-function calculator.
  1254. Most of them are copied directly from @code{calc}; three rules,
  1255. those which mention @code{VAR} or @code{FNCT}, are new.
  1256. @smallexample
  1257. input: /* empty */
  1258. | input line
  1259. ;
  1260. line:
  1261. '\n'
  1262. | exp '\n' @{ printf ("\t%.10g\n", $1); @}
  1263. | error '\n' @{ yyerrok; @}
  1264. ;
  1265. exp: NUM @{ $$ = $1; @}
  1266. | VAR @{ $$ = $1->value.var; @}
  1267. | VAR '=' exp @{ $$ = $3; $1->value.var = $3; @}
  1268. | FNCT '(' exp ')' @{ $$ = (*($1->value.fnctptr))($3); @}
  1269. | exp '+' exp @{ $$ = $1 + $3; @}
  1270. | exp '-' exp @{ $$ = $1 - $3; @}
  1271. | exp '*' exp @{ $$ = $1 * $3; @}
  1272. | exp '/' exp @{ $$ = $1 / $3; @}
  1273. | '-' exp %prec NEG @{ $$ = -$2; @}
  1274. | exp '^' exp @{ $$ = pow ($1, $3); @}
  1275. | '(' exp ')' @{ $$ = $2; @}
  1276. ;
  1277. /* End of grammar */
  1278. %%
  1279. @end smallexample
  1280. @node Mfcalc Symtab,, Mfcalc Rules, Multi-function Calc
  1281. @subsection The @code{mfcalc} Symbol Table
  1282. @cindex symbol table example
  1283. The multi-function calculator requires a symbol table to keep track of the
  1284. names and meanings of variables and functions. This doesn't affect the
  1285. grammar rules (except for the actions) or the Bison declarations, but it
  1286. requires some additional C functions for support.
  1287. The symbol table itself consists of a linked list of records. Its
  1288. definition, which is kept in the header @file{calc.h}, is as follows. It
  1289. provides for either functions or variables to be placed in the table.
  1290. @example
  1291. /* Data type for links in the chain of symbols. */
  1292. struct symrec
  1293. @{
  1294. char *name; /* name of symbol */
  1295. int type; /* type of symbol: either VAR or FNCT */
  1296. union @{
  1297. double var; /* value of a VAR */
  1298. double (*fnctptr)(); /* value of a FNCT */
  1299. @} value;
  1300. struct symrec *next; /* link field */
  1301. @};
  1302. typedef struct symrec symrec;
  1303. /* The symbol table: a chain of `struct symrec'. */
  1304. extern symrec *sym_table;
  1305. symrec *putsym ();
  1306. symrec *getsym ();
  1307. @end example
  1308. The new version of @code{main} includes a call to @code{init_table}, a
  1309. function that initializes the symbol table. Here it is, and
  1310. @code{init_table} as well:
  1311. @example
  1312. #include <stdio.h>
  1313. main()
  1314. @{
  1315. init_table ();
  1316. yyparse ();
  1317. @}
  1318. yyerror (s) /* Called by yyparse on error */
  1319. char *s;
  1320. @{
  1321. printf ("%s\n", s);
  1322. @}
  1323. struct init
  1324. @{
  1325. char *fname;
  1326. double (*fnct)();
  1327. @};
  1328. struct init arith_fncts[]
  1329. = @{
  1330. "sin", sin,
  1331. "cos", cos,
  1332. "atan", atan,
  1333. "ln", log,
  1334. "exp", exp,
  1335. "sqrt", sqrt,
  1336. 0, 0
  1337. @};
  1338. /* The symbol table: a chain of `struct symrec'. */
  1339. symrec *sym_table = (symrec *)0;
  1340. init_table () /* puts arithmetic functions in table. */
  1341. @{
  1342. int i;
  1343. symrec *ptr;
  1344. for (i = 0; arith_fncts[i].fname != 0; i++)
  1345. @{
  1346. ptr = putsym (arith_fncts[i].fname, FNCT);
  1347. ptr->value.fnctptr = arith_fncts[i].fnct;
  1348. @}
  1349. @}
  1350. @end example
  1351. By simply editing the initialization list and adding the necessary include
  1352. files, you can add additional functions to the calculator.
  1353. Two important functions allow look-up and installation of symbols in the
  1354. symbol table. The function @code{putsym} is passed a name and the type
  1355. (@code{VAR} or @code{FNCT}) of the object to be installed. The object is
  1356. linked to the front of the list, and a pointer to the object is returned.
  1357. The function @code{getsym} is passed the name of the symbol to look up. If
  1358. found, a pointer to that symbol is returned; otherwise zero is returned.
  1359. @example
  1360. symrec *
  1361. putsym (sym_name,sym_type)
  1362. char *sym_name;
  1363. int sym_type;
  1364. @{
  1365. symrec *ptr;
  1366. ptr = (symrec *) malloc (sizeof(symrec));
  1367. ptr->name = (char *) malloc (strlen(sym_name)+1);
  1368. strcpy (ptr->name,sym_name);
  1369. ptr->type = sym_type;
  1370. ptr->value.var = 0; /* set value to 0 even if fctn. */
  1371. ptr->next = (struct symrec *)sym_table;
  1372. sym_table = ptr;
  1373. return ptr;
  1374. @}
  1375. symrec *
  1376. getsym (sym_name)
  1377. char *sym_name;
  1378. @{
  1379. symrec *ptr;
  1380. for (ptr = sym_table; ptr != (symrec *) 0;
  1381. ptr = (symrec *)ptr->next)
  1382. if (strcmp (ptr->name,sym_name) == 0)
  1383. return ptr;
  1384. return 0;
  1385. @}
  1386. @end example
  1387. The function @code{yylex} must now recognize variables, numeric values, and
  1388. the single-character arithmetic operators. Strings of alphanumeric
  1389. characters with a leading nondigit are recognized as either variables or
  1390. functions depending on what the symbol table says about them.
  1391. The string is passed to @code{getsym} for look up in the symbol table. If
  1392. the name appears in the table, a pointer to its location and its type
  1393. (@code{VAR} or @code{FNCT}) is returned to @code{yyparse}. If it is not
  1394. already in the table, then it is installed as a @code{VAR} using
  1395. @code{putsym}. Again, a pointer and its type (which must be @code{VAR}) is
  1396. returned to @code{yyparse}.@refill
  1397. No change is needed in the handling of numeric values and arithmetic
  1398. operators in @code{yylex}.
  1399. @example
  1400. #include <ctype.h>
  1401. yylex()
  1402. @{
  1403. int c;
  1404. /* Ignore whitespace, get first nonwhite character. */
  1405. while ((c = getchar ()) == ' ' || c == '\t');
  1406. if (c == EOF)
  1407. return 0;
  1408. /* Char starts a number => parse the number. */
  1409. if (c == '.' || isdigit (c))
  1410. @{
  1411. ungetc (c, stdin);
  1412. scanf ("%lf", &yylval.val);
  1413. return NUM;
  1414. @}
  1415. /* Char starts an identifier => read the name. */
  1416. if (isalpha (c))
  1417. @{
  1418. symrec *s;
  1419. static char *symbuf = 0;
  1420. static int length = 0;
  1421. int i;
  1422. /* Initially make the buffer long enough
  1423. for a 40-character symbol name. */
  1424. if (length == 0)
  1425. length = 40, symbuf = (char *)malloc (length + 1);
  1426. i = 0;
  1427. do
  1428. @{
  1429. /* If buffer is full, make it bigger. */
  1430. if (i == length)
  1431. @{
  1432. length *= 2;
  1433. symbuf = (char *)realloc (symbuf, length + 1);
  1434. @}
  1435. /* Add this character to the buffer. */
  1436. symbuf[i++] = c;
  1437. /* Get another character. */
  1438. c = getchar ();
  1439. @}
  1440. while (c != EOF && isalnum (c));
  1441. ungetc (c, stdin);
  1442. symbuf[i] = '\0';
  1443. s = getsym (symbuf);
  1444. if (s == 0)
  1445. s = putsym (symbuf, VAR);
  1446. yylval.tptr = s;
  1447. return s->type;
  1448. @}
  1449. /* Any other character is a token by itself. */
  1450. return c;
  1451. @}
  1452. @end example
  1453. This program is both powerful and flexible. You may easily add new
  1454. functions, and it is a simple job to modify this code to install predefined
  1455. variables such as @code{pi} or @code{e} as well.
  1456. @node Exercises,, Multi-function calc, Examples
  1457. @section Exercises
  1458. @cindex exercises
  1459. @enumerate
  1460. @item
  1461. Add some new functions from @file{math.h} to the initialization list.
  1462. @item
  1463. Add another array that contains constants and their values. Then
  1464. modify @code{init_table} to add these constants to the symbol table.
  1465. It will be easiest to give the constants type @code{VAR}.
  1466. @item
  1467. Make the program report an error if the user refers to an
  1468. uninitialized variable in any way except to store a value in it.
  1469. @end enumerate
  1470. @node Grammar File, Interface, Examples, Top
  1471. @chapter Bison Grammar Files
  1472. Bison takes as input a context-free grammar specification and produces a
  1473. C-language function that recognizes correct instances of the grammar.
  1474. The Bison grammar input file conventionally has a name ending in @samp{.y}.
  1475. @menu
  1476. * Grammar Outline:: Overall layout of the grammar file.
  1477. * Symbols:: Terminal and nonterminal symbols.
  1478. * Rules:: How to write grammar rules.
  1479. * Recursion:: Writing recursive rules.
  1480. * Semantics:: Semantic values and actions.
  1481. * Declarations:: All kinds of Bison declarations are described here.
  1482. * Multiple Parsers:: Putting more than one Bison parser in one program.
  1483. @end menu
  1484. @node Grammar Outline, Symbols, Grammar File, Grammar File
  1485. @section Outline of a Bison Grammar
  1486. A Bison grammar file has four main sections, shown here with the
  1487. appropriate delimiters:
  1488. @example
  1489. %@{
  1490. @var{C declarations}
  1491. %@}
  1492. @var{Bison declarations}
  1493. %%
  1494. @var{Grammar rules}
  1495. %%
  1496. @var{Additional C code}
  1497. @end example
  1498. Comments enclosed in @samp{/* @dots{} */} may appear in any of the sections.
  1499. @menu
  1500. * C Declarations:: Syntax and usage of the C declarations section.
  1501. * Bison Declarations:: Syntax and usage of the Bison declarations section.
  1502. * Grammar Rules:: Syntax and usage of the grammar rules section.
  1503. * C Code:: Syntax and usage of the additional C code section.
  1504. @end menu
  1505. @node C Declarations, Bison Declarations, Grammar Outline, Grammar Outline
  1506. @subsection The C Declarations Section
  1507. @cindex C declarations section
  1508. @cindex declarations, C
  1509. The @var{C declarations} section contains macro definitions and
  1510. declarations of functions and variables that are used in the actions in the
  1511. grammar rules. These are copied to the beginning of the parser file so
  1512. that they precede the definition of @code{yylex}. You can use
  1513. @samp{#include} to get the declarations from a header file. If you don't
  1514. need any C declarations, you may omit the @samp{%@{} and @samp{%@}}
  1515. delimiters that bracket this section.
  1516. @node Bison Declarations, Grammar Rules, C Declarations, Grammar Outline
  1517. @subsection The Bison Declarations Section
  1518. @cindex Bison declarations (introduction)
  1519. @cindex declarations, Bison (introduction)
  1520. The @var{Bison declarations} section contains declarations that define
  1521. terminal and nonterminal symbols, specify precedence, and so on.
  1522. In some simple grammars you may not need any declarations.
  1523. @xref{Declarations}.
  1524. @node Grammar Rules,C Code, Bison Declarations, Grammar Outline
  1525. @subsection The Grammar Rules Section
  1526. @cindex grammar rules section
  1527. @cindex rules section for grammar
  1528. The @dfn{grammar rules} section contains one or more Bison grammar
  1529. rules, and nothing else. @xref{Rules}.
  1530. There must always be at least one grammar rule, and the first
  1531. @samp{%%} (which precedes the grammar rules) may never be omitted even
  1532. if it is the first thing in the file.
  1533. @node C Code,, Grammar Rules, Grammar Outline
  1534. @subsection The Additional C Code Section
  1535. @cindex additional C code section
  1536. @cindex C code, section for additional
  1537. The @var{additional C code} section is copied verbatim to the end of
  1538. the parser file, just as the @var{C declarations} section is copied to
  1539. the beginning. This is the most convenient place to put anything
  1540. that you want to have in the parser file but which need not come before
  1541. the definition of @code{yylex}. For example, the definitions of
  1542. @code{yylex} and @code{yyerror} often go here. @xref{Interface}.
  1543. If the last section is empty, you may omit the @samp{%%} that separates it
  1544. from the grammar rules.
  1545. The Bison parser itself contains many static variables whose names start
  1546. with @samp{yy} and many macros whose names start with @samp{YY}. It is a
  1547. good idea to avoid using any such names (except those documented in this
  1548. manual) in the additional C code section of the grammar file.
  1549. @node Symbols, Rules, Grammar Outline, Grammar File
  1550. @section Symbols, Terminal and Nonterminal
  1551. @cindex nonterminal symbol
  1552. @cindex terminal symbol
  1553. @cindex token type
  1554. @cindex symbol
  1555. @dfn{Symbols} in Bison grammars represent the grammatical classifications
  1556. of the language.
  1557. A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a
  1558. class of syntactically equivalent tokens. You use the symbol in grammar
  1559. rules to mean that a token in that class is allowed. The symbol is
  1560. represented in the Bison parser by a numeric code, and the @code{yylex}
  1561. function returns a token type code to indicate what kind of token has been
  1562. read. You don't need to know what the code value is; you can use the
  1563. symbol to stand for it.
  1564. A @dfn{nonterminal symbol} stands for a class of syntactically equivalent
  1565. groupings. The symbol name is used in writing grammar rules. By convention,
  1566. it should be all lower case.
  1567. Symbol names can contain letters, digits (not at the beginning),
  1568. underscores and periods. Periods make sense only in nonterminals.
  1569. There are two ways of writing terminal symbols in the grammar:
  1570. @itemize @bullet
  1571. @item
  1572. A @dfn{named token type} is written with an identifier, like an
  1573. identifier in C. By convention, it should be all upper case. Each
  1574. such name must be defined with a Bison declaration such as
  1575. @code{%token}. @xref{Token Decl}.
  1576. @item
  1577. @cindex character token
  1578. @cindex literal token
  1579. @cindex single-character literal
  1580. A @dfn{character token type} (or @dfn{literal token}) is written in
  1581. the grammar using the same syntax used in C for character constants;
  1582. for example, @code{'+'} is a character token type. A character token
  1583. type doesn't need to be declared unless you need to specify its
  1584. semantic value data type (@pxref{Value Type}), associativity, or
  1585. precedence (@pxref{Precedence}).
  1586. By convention, a character token type is used only to represent a
  1587. token that consists of that particular character. Thus, the token
  1588. type @code{'+'} is used to represent the character @samp{+} as a
  1589. token. Nothing enforces this convention, but if you depart from it,
  1590. your program will confuse other readers.
  1591. All the usual escape sequences used in character literals in C can be
  1592. used in Bison as well, but you must not use the null character as a
  1593. character literal because its ASCII code, zero, is the code
  1594. @code{yylex} returns for end-of-input (@pxref{Calling Convention}).
  1595. @end itemize
  1596. How you choose to write a terminal symbol has no effect on its
  1597. grammatical meaning. That depends only on where it appears in rules and
  1598. on when the parser function returns that symbol.
  1599. The value returned by @code{yylex} is always one of the terminal symbols
  1600. (or 0 for end-of-input). Whichever way you write the token type in the
  1601. grammar rules, you write it the same way in the definition of @code{yylex}.
  1602. The numeric code for a character token type is simply the ASCII code for
  1603. the character, so @code{yylex} can use the identical character constant to
  1604. generate the requisite code. Each named token type becomes a C macro in
  1605. the parser file, so @code{yylex} can use the name to stand for the code.
  1606. (This is why periods don't make sense in terminal symbols.) @xref{Calling
  1607. Convention}.
  1608. If @code{yylex} is defined in a separate file, you need to arrange for the
  1609. token-type macro definitions to be available there. Use the @samp{-d}
  1610. option when you run Bison, so that it will write these macro definitions
  1611. into a separate header file @file{@var{name}.tab.h} which you can include
  1612. in the other source files that need it. @xref{Invocation}.
  1613. The symbol @code{error} is a terminal symbol reserved for error recovery
  1614. (@pxref{Error Recovery}); you shouldn't use it for any other purpose.
  1615. In particular, @code{yylex} should never return this value.
  1616. @node Rules, Recursion, Symbols, Grammar File
  1617. @section Syntax of Grammar Rules
  1618. @cindex rule syntax
  1619. @cindex grammar rule syntax
  1620. @cindex syntax of grammar rules
  1621. A Bison grammar rule has the following general form:
  1622. @example
  1623. @var{result}: @var{components}@dots{}
  1624. ;
  1625. @end example
  1626. @noindent
  1627. where @var{result} is the nonterminal symbol that this rule describes
  1628. and @var{components} are various terminal and nonterminal symbols that
  1629. are put together by this rule (@pxref{Symbols}). For example,
  1630. @example
  1631. exp: exp '+' exp
  1632. ;
  1633. @end example
  1634. @noindent
  1635. says that two groupings of type @code{exp}, with a @samp{+} token in between,
  1636. can be combined into a larger grouping of type @code{exp}.
  1637. Whitespace in rules is significant only to separate symbols. You can add
  1638. extra whitespace as you wish.
  1639. Scattered among the components can be @var{actions} that determine
  1640. the semantics of the rule. An action looks like this:
  1641. @example
  1642. @{@var{C statements}@}
  1643. @end example
  1644. @noindent
  1645. Usually there is only one action and it follows the components.
  1646. @xref{Actions}.
  1647. @findex |
  1648. Multiple rules for the same @var{result} can be written separately or can
  1649. be joined with the vertical-bar character @samp{|} as follows:
  1650. @ifinfo
  1651. @example
  1652. @var{result}: @var{rule1-components}@dots{}
  1653. | @var{rule2-components}@dots{}
  1654. @dots{}
  1655. ;
  1656. @end example
  1657. @end ifinfo
  1658. @iftex
  1659. @example
  1660. @var{result}: @var{rule1-components}@dots{}
  1661. | @var{rule2-components}@dots{}
  1662. @dots{}
  1663. ;
  1664. @end example
  1665. @end iftex
  1666. @noindent
  1667. They are still considered distinct rules even when joined in this way.
  1668. If @var{components} in a rule is empty, it means that @var{result} can
  1669. match the empty string. For example, here is how to define a
  1670. comma-separated sequence of zero or more @code{exp} groupings:
  1671. @example
  1672. expseq: /* empty */
  1673. | expseq1
  1674. ;
  1675. expseq1: exp
  1676. | expseq1 ',' exp
  1677. ;
  1678. @end example
  1679. @noindent
  1680. It is customary to write a comment @samp{/* empty */} in each rule
  1681. with no components.
  1682. @node Recursion, Semantics, Rules, Grammar File
  1683. @section Recursive Rules
  1684. @cindex recursive rule
  1685. A rule is called @dfn{recursive} when its @var{result} nonterminal appears
  1686. also on its right hand side. Nearly all Bison grammars need to use
  1687. recursion, because that is the only way to define a sequence of any number
  1688. of somethings. Consider this recursive definition of a comma-separated
  1689. sequence of one or more expressions:
  1690. @example
  1691. expseq1: exp
  1692. | expseq1 ',' exp
  1693. ;
  1694. @end example
  1695. @cindex left recursion
  1696. @cindex right recursion
  1697. @noindent
  1698. Since the recursive use of @code{expseq1} is the leftmost symbol in the
  1699. right hand side, we call this @dfn{left recursion}. By contrast, here
  1700. the same construct is defined using @dfn{right recursion}:
  1701. @example
  1702. expseq1: exp
  1703. | exp ',' expseq1
  1704. ;
  1705. @end example
  1706. @noindent
  1707. Any kind of sequence can be defined using either left recursion or
  1708. right recursion, but you should always use left recursion, because it
  1709. can parse a sequence of any number of elements with bounded stack
  1710. space. Right recursion uses up space on the Bison stack in proportion
  1711. to the number of elements in the sequence, because all the elements
  1712. must be shifted onto the stack before the rule can be applied even
  1713. once. @xref{Algorithm, , The Algorithm of the Bison Parser}, for
  1714. further explanation of this.
  1715. @cindex mutual recursion
  1716. @dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the
  1717. rule does not appear directly on its right hand side, but does appear
  1718. in rules for other nonterminals which do appear on its right hand
  1719. side. For example:
  1720. @example
  1721. expr: primary
  1722. | primary '+' primary
  1723. ;
  1724. primary: constant
  1725. | '(' expr ')'
  1726. ;
  1727. @end example
  1728. @noindent
  1729. defines two mutually-recursive nonterminals, since each refers to the
  1730. other.
  1731. @node Semantics, Declarations, Recursion, Grammar File
  1732. @section Defining Language Semantics
  1733. @cindex defining language semantics
  1734. @cindex language semantics, defining
  1735. The grammar rules for a language determine only the syntax. The semantics
  1736. are determined by the semantic values associated with various tokens and
  1737. groupings, and by the actions taken when various groupings are recognized.
  1738. For example, the calculator calculates properly because the value
  1739. associated with each expression is the proper number; it adds properly
  1740. because the action for the grouping @w{@samp{@var{x} + @var{y}}} is to add
  1741. the numbers associated with @var{x} and @var{y}.
  1742. @menu
  1743. * Value Type:: Specifying one data type for all semantic values.
  1744. * Multiple Types:: Specifying several alternative data types.
  1745. * Actions:: An action is the semantic definition of a grammar rule.
  1746. * Action Types:: Specifying data types for actions to operate on.
  1747. * Mid-Rule Actions:: Most actions go at the end of a rule.
  1748. This says when, why and how to use the exceptional
  1749. action in the middle of a rule.
  1750. @end menu
  1751. @node Value Type, Multiple Types, Semantics, Semantics
  1752. @subsection Data Types of Semantic Values
  1753. @cindex semantic value type
  1754. @cindex value type, semantic
  1755. @cindex data types of semantic values
  1756. In a simple program it may be sufficient to use the same data type for
  1757. the semantic values of all language constructs. This was true in the
  1758. RPN and infix calculator examples (@pxref{RPN Calc}).
  1759. Bison's default is to use type @code{int} for all semantic values. To
  1760. specify some other type, define @code{YYSTYPE} as a macro, like this:
  1761. @example
  1762. #define YYSTYPE double
  1763. @end example
  1764. @noindent
  1765. This macro definition must go in the C declarations section of the grammar
  1766. file (@pxref{Grammar Outline}).
  1767. @node Multiple Types, Actions, Value Type, Semantics
  1768. @subsection More Than One Value Type
  1769. In most programs, you will need different data types for different kinds
  1770. of tokens and groupings. For example, a numeric constant may need type
  1771. @code{int} or @code{long}, while a string constant needs type @code{char *},
  1772. and an identifier might need a pointer to an entry in the symbol table.
  1773. To use more than one data type for semantic values in one parser, Bison
  1774. requires you to do two things:
  1775. @itemize @bullet
  1776. @item
  1777. Specify the entire collection of possible data types, with the
  1778. @code{%union} Bison declaration (@pxref{Union Decl}).
  1779. @item
  1780. Choose one of those types for each symbol (terminal or nonterminal)
  1781. for which semantic values are used. This is done for tokens with the
  1782. @code{%token} Bison declaration (@pxref{Token Decl}) and for groupings
  1783. with the @code{%type} Bison declaration (@pxref{Type Decl}).
  1784. @end itemize
  1785. @node Actions, Action Types, Multiple Types, Semantics
  1786. @subsection Actions
  1787. @cindex action
  1788. @vindex $$
  1789. @vindex $@var{n}
  1790. An action accompanies a syntactic rule and contains C code to be executed
  1791. each time an instance of that rule is recognized. The task of most actions
  1792. is to compute a semantic value for the grouping built by the rule from the
  1793. semantic values associated with tokens or smaller groupings.
  1794. An action consists of C statements surrounded by braces, much like a
  1795. compound statement in C. It can be placed at any position in the rule; it
  1796. is executed at that position. Most rules have just one action at the end
  1797. of the rule, following all the components. Actions in the middle of a rule
  1798. are tricky and used only for special purposes (@pxref{Mid-Rule Actions}).
  1799. The C code in an action can refer to the semantic values of the components
  1800. matched by the rule with the construct @code{$@var{n}}, which stands for
  1801. the value of the @var{n}th component. The semantic value for the grouping
  1802. being constructed is @code{$$}. (Bison translates both of these constructs
  1803. into array element references when it copies the actions into the parser
  1804. file.)
  1805. Here is a typical example:
  1806. @example
  1807. exp: @dots{}
  1808. | exp '+' exp
  1809. @{ $$ = $1 + $3; @}
  1810. @end example
  1811. @noindent
  1812. This rule constructs an @code{exp} from two smaller @code{exp} groupings
  1813. connected by a plus-sign token. In the action, @code{$1} and @code{$3}
  1814. refer to the semantic values of the two component @code{exp} groupings,
  1815. which are the first and third symbols on the right hand side of the rule.
  1816. The sum is stored into @code{$$} so that it becomes the semantic value of
  1817. the addition-expression just recognized by the rule. If there were a
  1818. useful semantic value associated with the @samp{+} token, it could be
  1819. referred to as @code{$2}.@refill
  1820. @code{$@var{n}} with @var{n} zero or negative is allowed for reference
  1821. to tokens and groupings on the stack @emph{before} those that match the
  1822. current rule. This is a very risky practice, and to use it reliably
  1823. you must be certain of the context in which the rule is applied. Here
  1824. is a case in which you can use this reliably:
  1825. @example
  1826. foo: expr bar '+' expr @{ @dots{} @}
  1827. | expr bar '-' expr @{ @dots{} @}
  1828. ;
  1829. bar: /* empty */
  1830. @{ previous_expr = $0; @}
  1831. ;
  1832. @end example
  1833. As long as @code{bar} is used only in the fashion shown here, @code{$0}
  1834. always refers to the @code{expr} which precedes @code{bar} in the
  1835. definition of @code{foo}.
  1836. @node Action Types, Mid-Rule Actions, Actions, Semantics
  1837. @subsection Data Types of Values in Actions
  1838. @cindex action data types
  1839. @cindex data types in actions
  1840. If you have chosen a single data type for semantic values, the @code{$$}
  1841. and @code{$@var{n}} constructs always have that data type.
  1842. If you have used @code{%union} to specify a variety of data types, then you
  1843. must declare a choice among these types for each terminal or nonterminal
  1844. symbol that can have a semantic value. Then each time you use @code{$$} or
  1845. @code{$@var{n}}, its data type is determined by which symbol it refers to
  1846. in the rule. In this example,@refill
  1847. @example
  1848. exp: @dots{}
  1849. | exp '+' exp
  1850. @{ $$ = $1 + $3; @}
  1851. @end example
  1852. @noindent
  1853. @code{$1} and @code{$3} refer to instances of @code{exp}, so they all
  1854. have the data type declared for the nonterminal symbol @code{exp}. If
  1855. @code{$2} were used, it would have the data type declared for the
  1856. terminal symbol @code{'+'}, whatever that might be.@refill
  1857. Alternatively, you can specify the data type when you refer to the value,
  1858. by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the
  1859. reference. For example, if you have defined types as shown here:
  1860. @example
  1861. %union @{
  1862. int itype;
  1863. double dtype;
  1864. @}
  1865. @end example
  1866. @noindent
  1867. then you can write @code{$<itype>1} to refer to the first subunit of the
  1868. rule as an integer, or @code{$<dtype>1} to refer to it as a double.
  1869. @node Mid-Rule Actions,, Action Types, Semantics
  1870. @subsection Actions in Mid-Rule
  1871. @cindex actions in mid-rule
  1872. @cindex mid-rule actions
  1873. Occasionally it is useful to put an action in the middle of a rule.
  1874. These actions are written just like usual end-of-rule actions, but they
  1875. are executed before the parser even recognizes the following components.
  1876. A mid-rule action may refer to the components preceding it using
  1877. @code{$@var{n}}, but it may not refer to subsequent components because
  1878. it is run before they are parsed.
  1879. The mid-rule action itself counts as one of the components of the rule.
  1880. This makes a difference when there is another action later in the same rule
  1881. (and usually there is another at the end): you have to count the actions
  1882. along with the symbols when working out which number @var{n} to use in
  1883. @code{$@var{n}}.
  1884. The mid-rule action can also have a semantic value. This can be set within
  1885. that action by an assignment to @code{$$}, and can referred to by later
  1886. actions using @code{$@var{n}}. Since there is no symbol to name the
  1887. action, there is no way to declare a data type for the value in advance, so
  1888. you must use the @samp{$<@dots{}>} construct to specify a data type each
  1889. time you refer to this value.
  1890. Here is an example from a hypothetical compiler, handling a @code{let}
  1891. statement that looks like @samp{let (@var{variable}) @var{statement}} and
  1892. serves to create a variable named @var{variable} temporarily for the
  1893. duration of @var{statement}. To parse this construct, we must put
  1894. @var{variable} into the symbol table while @var{statement} is parsed, then
  1895. remove it afterward. Here is how it is done:
  1896. @example
  1897. stmt: LET '(' var ')'
  1898. @{ $<context>$ = push_context ();
  1899. declare_variable ($3); @}
  1900. stmt @{ $$ = $6;
  1901. pop_context ($<context>5); @}
  1902. @end example
  1903. @noindent
  1904. As soon as @samp{let (@var{variable})} has been recognized, the first
  1905. action is run. It saves a copy of the current semantic context (the
  1906. list of accessible variables) as its semantic value, using alternative
  1907. @code{context} in the data-type union. Then it calls
  1908. @code{declare_variable} to add the new variable to that list. Once the
  1909. first action is finished, the embedded statement @code{stmt} can be
  1910. parsed. Note that the mid-rule action is component number 5, so the
  1911. @samp{stmt} is component number 6.
  1912. After the embedded statement is parsed, its semantic value becomes the
  1913. value of the entire @code{let}-statement. Then the semantic value from the
  1914. earlier action is used to restore the prior list of variables. This
  1915. removes the temporary @code{let}-variable from the list so that it won't
  1916. appear to exist while the rest of the program is parsed.
  1917. Taking action before a rule is completely recognized often leads to
  1918. conflicts since the parser must commit to a parse in order to execute the
  1919. action. For example, the following two rules, without mid-rule actions,
  1920. can coexist in a working parser because the parser can shift the open-brace
  1921. token and look at what follows before deciding whether there is a
  1922. declaration or not:
  1923. @example
  1924. compound: '@{' declarations statements '@}'
  1925. | '@{' statements '@}'
  1926. ;
  1927. @end example
  1928. @noindent
  1929. But when we add a mid-rule action as follows, the rules become nonfunctional:
  1930. @example
  1931. compound: @{ prepare_for_local_variables (); @}
  1932. '@{' declarations statements '@}'
  1933. @group
  1934. | '@{' statements '@}'
  1935. ;
  1936. @end group
  1937. @end example
  1938. @noindent
  1939. Now the parser is forced to decide whether to run the mid-rule action
  1940. when it has read no farther than the open-brace. In other words, it
  1941. must commit to using one rule or the other, without sufficient
  1942. information to do it correctly. (The open-brace token is what is called
  1943. the @dfn{look-ahead} token at this time, since the parser is still
  1944. deciding what to do about it. @xref{Look-Ahead}.)
  1945. You might think that you could correct the problem by putting identical
  1946. actions into the two rules, like this:
  1947. @example
  1948. compound: @{ prepare_for_local_variables (); @}
  1949. '@{' declarations statements '@}'
  1950. | @{ prepare_for_local_variables (); @}
  1951. '@{' statements '@}'
  1952. ;
  1953. @end example
  1954. @noindent
  1955. But this does not help, because Bison does not realize that the two actions
  1956. are identical. (Bison never tries to understand the C code in an action.)
  1957. If the grammar is such that a declaration can be distinguished from a
  1958. statement by the first token (which is true in C), then one solution which
  1959. does work is to put the action after the open-brace, like this:
  1960. @example
  1961. compound: '@{' @{ prepare_for_local_variables (); @}
  1962. declarations statements '@}'
  1963. | '@{' statements '@}'
  1964. ;
  1965. @end example
  1966. @noindent
  1967. Now the first token of the following declaration or statement,
  1968. which would in any case tell Bison which rule to use, can still do so.
  1969. Another solution is to bury the action inside a nonterminal symbol which
  1970. serves as a subroutine:
  1971. @example
  1972. subroutine: /* empty */
  1973. @{ prepare_for_local_variables (); @}
  1974. ;
  1975. compound: subroutine
  1976. '@{' declarations statements '@}'
  1977. | subroutine
  1978. '@{' statements '@}'
  1979. ;
  1980. @end example
  1981. @noindent
  1982. Now Bison can execute the action in the rule for @code{subroutine} without
  1983. deciding which rule for @code{compound} it will eventually use. Note that
  1984. the action is now at the end of its rule. Any mid-rule action can be
  1985. converted to an end-of-rule action in this way, and this is what Bison
  1986. actually does to implement mid-rule actions.
  1987. @node Declarations, Multiple Parsers, Semantics, Grammar File
  1988. @section Bison Declarations
  1989. @cindex declarations, Bison
  1990. @cindex Bison declarations
  1991. The @dfn{Bison declarations} section of a Bison grammar defines the symbols
  1992. used in formulating the grammar and the data types of semantic values.
  1993. @xref{Symbols}.
  1994. All token type names (but not single-character literal tokens such as
  1995. @code{'+'} and @code{'*'}) must be declared. Nonterminal symbols must be
  1996. declared if you need to specify which data type to use for the semantic
  1997. value (@pxref{Multiple Types}).
  1998. The first rule in the file also specifies the start symbol, by default.
  1999. If you want some other symbol to be the start symbol, you must declare
  2000. it explicitly (@pxref{Language and Grammar}).
  2001. @menu
  2002. * Token Decl:: Declaring terminal symbols.
  2003. * Precedence Decl:: Declaring terminals with precedence and associativity.
  2004. * Union Decl:: Declaring the set of all semantic value types.
  2005. * Type Decl:: Declaring the choice of type for a nonterminal symbol.
  2006. * Expect Decl:: Suppressing warnings about shift/reduce conflicts.
  2007. * Start Decl:: Specifying the start symbol.
  2008. * Pure Decl:: Requesting a reentrant parser.
  2009. * Decl Summary:: Table of all Bison declarations.
  2010. @end menu
  2011. @node Token Decl, Precedence Decl, Declarations, Declarations
  2012. @subsection Token Type Names
  2013. @cindex declaring token type names
  2014. @cindex token type names, declaring
  2015. @findex %token
  2016. The basic way to declare a token type name (terminal symbol) is as follows:
  2017. @example
  2018. %token @var{name}
  2019. @end example
  2020. Bison will convert this into a @code{#define} directive in
  2021. the parser, so that the function @code{yylex} (if it is in this file)
  2022. can use the name @var{name} to stand for this token type's code.
  2023. Alternatively you can use @code{%left}, @code{%right}, or @code{%nonassoc}
  2024. instead of @code{%token}, if you wish to specify precedence.
  2025. @xref{Precedence Decl}.
  2026. You can explicitly specify the numeric code for a token type by appending
  2027. an integer value in the field immediately following the token name:
  2028. @example
  2029. %token NUM 300
  2030. @end example
  2031. @noindent
  2032. It is generally best, however, to let Bison choose the numeric codes for
  2033. all token types. Bison will automatically select codes that don't conflict
  2034. with each other or with ASCII characters.
  2035. In the event that the stack type is a union, you must augment the
  2036. @code{%token} or other token declaration to include the data type
  2037. alternative delimited by angle-brackets (@pxref{Multiple Types}). For
  2038. example:
  2039. @example
  2040. %union @{ /* define stack type */
  2041. double val;
  2042. symrec *tptr;
  2043. @}
  2044. %token <val> NUM /* define token NUM and its type */
  2045. @end example
  2046. @node Precedence Decl, Union Decl, Token Decl, Declarations
  2047. @subsection Operator Precedence
  2048. @cindex precedence declarations
  2049. @cindex declaring operator precedence
  2050. @cindex operator precedence, declaring
  2051. Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to
  2052. declare a token and specify its precedence and associativity, all at
  2053. once. These are called @dfn{precedence declarations}.
  2054. @xref{Precedence}, for general information on operator precedence.
  2055. The syntax of a precedence declaration is the same as that of
  2056. @code{%token}: either
  2057. @example
  2058. %left @var{symbols}@dots{}
  2059. @end example
  2060. @noindent
  2061. or
  2062. @example
  2063. %left <@var{type}> @var{symbols}@dots{}
  2064. @end example
  2065. And indeed any of these declarations serves the purposes of @code{%token}.
  2066. But in addition, they specify the associativity and relative precedence for
  2067. all the @var{symbols}:
  2068. @itemize @bullet
  2069. @item
  2070. The associativity of an operator @var{op} determines how repeated uses
  2071. of the operator nest: whether @samp{@var{x} @var{op} @var{y} @var{op}
  2072. @var{z}} is parsed by grouping @var{x} with @var{y} first or by
  2073. grouping @var{y} with @var{z} first. @code{%left} specifies
  2074. left-associativity (grouping @var{x} with @var{y} first) and
  2075. @code{%right} specifies right-associativity (grouping @var{y} with
  2076. @var{z} first). @code{%nonassoc} specifies no associativity, which
  2077. means that @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is
  2078. considered a syntax error.
  2079. @item
  2080. The precedence of an operator determines how it nests with other operators.
  2081. All the tokens declared in a single precedence declaration have equal
  2082. precedence and nest together according to their associativity.
  2083. When two tokens declared in different precedence declarations associate,
  2084. the one declared later has the higher precedence and is grouped first.
  2085. @end itemize
  2086. @node Union Decl, Type Decl, Precedence Decl, Declarations
  2087. @subsection The Collection of Value Types
  2088. @cindex declaring value types
  2089. @cindex value types, declaring
  2090. @findex %union
  2091. The @code{%union} declaration specifies the entire collection of possible
  2092. data types for semantic values. The keyword @code{%union} is followed by a
  2093. pair of braces containing the same thing that goes inside a @code{union} in
  2094. C. For example:
  2095. @example
  2096. %union @{
  2097. double val;
  2098. symrec *tptr;
  2099. @}
  2100. @end example
  2101. @noindent
  2102. This says that the two alternative types are @code{double} and @code{symrec
  2103. *}. They are given names @code{val} and @code{tptr}; these names are used
  2104. in the @code{%token} and @code{%type} declarations to pick one of the types
  2105. for a terminal or nonterminal symbol (@pxref{Type Decl}).
  2106. Note that, unlike making a @code{union} declaration in C, you do not write
  2107. a semicolon after the closing brace.
  2108. @node Type Decl, Expect Decl, Union Decl, Declarations
  2109. @subsection Nonterminal Symbols
  2110. @cindex declaring value types, nonterminals
  2111. @cindex value types, nonterminals, declaring
  2112. @findex %type
  2113. @noindent
  2114. When you use @code{%union} to specify multiple value types, you must
  2115. declare the value type of each nonterminal symbol for which values are
  2116. used. This is done with a @code{%type} declaration, like this:
  2117. @example
  2118. %type <@var{type}> @var{nonterminal}@dots{}
  2119. @end example
  2120. @noindent
  2121. Here @var{nonterminal} is the name of a nonterminal symbol, and @var{type}
  2122. is the name given in the @code{%union} to the alternative that you want
  2123. (@pxref{Union Decl}). You can give any number of nonterminal symbols in
  2124. the same @code{%type} declaration, if they have the same value type. Use
  2125. spaces to separate the symbol names.
  2126. @node Expect Decl, Start Decl, Type Decl, Declarations
  2127. @subsection Suppressing Conflict Warnings
  2128. @cindex suppressing conflict warnings
  2129. @cindex preventing warnings about conflicts
  2130. @cindex warnings, preventing
  2131. @cindex conflicts, suppressing warnings of
  2132. @findex %expect
  2133. Bison normally warns if there are any conflicts in the grammar
  2134. (@pxref{Shift/Reduce}), but most real grammars have harmless shift/reduce
  2135. conflicts which are resolved in a predictable way and would be difficult to
  2136. eliminate. It is desirable to suppress the warning about these conflicts
  2137. unless the number of conflicts changes. You can do this with the
  2138. @code{%expect} declaration.
  2139. The declaration looks like this:
  2140. @example
  2141. %expect @var{n}
  2142. @end example
  2143. Here @var{n} is a decimal integer. The declaration says there should be no
  2144. warning if there are @var{n} shift/reduce conflicts and no reduce/reduce
  2145. conflicts. The usual warning is given if there are either more or fewer
  2146. conflicts, or if there are any reduce/reduce conflicts.
  2147. In general, using @code{%expect} involves these steps:
  2148. @itemize @bullet
  2149. @item
  2150. Compile your grammar without @code{%expect}. Use the @samp{-v} option
  2151. to get a verbose list of where the conflicts occur. Bison will also
  2152. print the number of conflicts.
  2153. @item
  2154. Check each of the conflicts to make sure that Bison's default
  2155. resolution is what you really want. If not, rewrite the grammar and
  2156. go back to the beginning.
  2157. @item
  2158. Add an @code{%expect} declaration, copying the number @var{n} from the
  2159. number which Bison printed.
  2160. @end itemize
  2161. Now Bison will stop annoying you about the conflicts you have checked, but
  2162. it will warn you again if changes in the grammer result in additional
  2163. conflicts.
  2164. @node Start Decl, Pure Decl, Expect Decl, Declarations
  2165. @subsection The Start-Symbol
  2166. @cindex declaring the start symbol
  2167. @cindex start symbol, declaring
  2168. @findex %start
  2169. Bison assumes by default that the start symbol for the grammar is the first
  2170. nonterminal specified in the grammar specification section. The programmer
  2171. may override this restriction with the @code{%start} declaration as follows:
  2172. @example
  2173. %start @var{symbol}
  2174. @end example
  2175. @node Pure Decl, Decl Summary, Start Decl, Declarations
  2176. @subsection A Pure (Reentrant) Parser
  2177. @cindex reentrant parser
  2178. @cindex pure parser
  2179. @findex %pure_parser
  2180. A @dfn{reentrant} program is one which does not alter in the course of
  2181. execution; in other words, it consists entirely of @dfn{pure} (read-only)
  2182. code. Reentrancy is important whenever asynchronous execution is possible;
  2183. for example, a nonreentrant program may not be safe to call from a signal
  2184. handler. In systems with multiple threads of control, a nonreentrant
  2185. program must be called only within interlocks.
  2186. The Bison parser is not normally a reentrant program, because it uses
  2187. statically allocated variables for communication with @code{yylex}. These
  2188. variables include @code{yylval} and @code{yylloc}.
  2189. The Bison declaration @code{%pure_parser} says that you want the parser
  2190. to be reentrant. It looks like this:
  2191. @example
  2192. %pure_parser
  2193. @end example
  2194. The effect is that the two communication variables become local
  2195. variables in @code{yyparse}, and a different calling convention is used for
  2196. the lexical analyzer function @code{yylex}. @xref{Pure Calling}, for the
  2197. details of this. The variable @code{yynerrs} also becomes local in
  2198. @code{yyparse} (@pxref{Error Reporting}). The convention for calling
  2199. @code{yyparse} itself is unchanged.
  2200. @node Decl Summary,, Pure Decl, Declarations
  2201. @subsection Bison Declaration Summary
  2202. @cindex Bison declaration summary
  2203. @cindex declaration summary
  2204. @cindex summary, Bison declaration
  2205. Here is a summary of all Bison declarations:
  2206. @table @code
  2207. @item %union
  2208. Declare the collection of data types that semantic values may have
  2209. (@pxref{Union Decl}).
  2210. @item %token
  2211. Declare a terminal symbol (token type name) with no precedence
  2212. or associativity specified (@pxref{Token Decl}).
  2213. @item %right
  2214. Declare a terminal symbol (token type name) that is right-associative
  2215. (@pxref{Precedence Decl}).
  2216. @item %left
  2217. Declare a terminal symbol (token type name) that is left-associative
  2218. (@pxref{Precedence Decl}).
  2219. @item %nonassoc
  2220. Declare a terminal symbol (token type name) that is nonassociative
  2221. (using it in a way that would be associative is a syntax error)
  2222. (@pxref{Precedence Decl}).
  2223. @item %type
  2224. Declare the type of semantic values for a nonterminal symbol
  2225. (@pxref{Type Decl}).
  2226. @item %start
  2227. Specify the grammar's start symbol (@pxref{Start Decl}).
  2228. @item %expect
  2229. Declare the expected number of shift-reduce conflicts
  2230. (@pxref{Expect Decl}).
  2231. @item %pure_parser
  2232. Request a pure (reentrant) parser program (@pxref{Pure Decl}).
  2233. @end table
  2234. @node Multiple Parsers,, Declarations, Grammar File
  2235. @section Multiple Parsers in the Same Program
  2236. Most programs that use Bison parse only one language and therefore contain
  2237. only one Bison parser. But what if you want to parse more than one
  2238. language with the same program? Here is what you must do:
  2239. @itemize @bullet
  2240. @item
  2241. Make each parser a pure parser (@pxref{Pure Decl}). This gets rid of
  2242. global variables such as @code{yylval} which would otherwise conflict
  2243. between the various parsers, but it requires an alternate calling
  2244. convention for @code{yylex} (@pxref{Pure Calling}).
  2245. @item
  2246. In each grammar file, define @code{yyparse} as a macro, expanding
  2247. into the name you want for that parser. Put this definition in
  2248. the C declarations section (@pxref{C Declarations}). For example:
  2249. @example
  2250. %@{
  2251. #define yyparse parse_algol
  2252. %@}
  2253. @end example
  2254. @noindent
  2255. Then use the expanded name @code{parse_algol} in other source files to
  2256. call this parser.
  2257. @item
  2258. If you want different lexical analyzers for each grammar, you can
  2259. define @code{yylex} as a macro, just like @code{yyparse}. Use
  2260. the expanded name when you define @code{yylex} in another source
  2261. file.
  2262. If you define @code{yylex} in the grammar file itself, simply
  2263. make it static, like this:
  2264. @example
  2265. %@{
  2266. static int yylex ();
  2267. %@}
  2268. %%
  2269. @dots{} @var{grammar rules} @dots{}
  2270. %%
  2271. static int
  2272. yylex (yylvalp, yyllocp)
  2273. YYSTYPE *yylvalp;
  2274. YYLTYPE *yyllocp;
  2275. @{ @dots{} @}
  2276. @end example
  2277. @item
  2278. If you want a different @code{yyerror} function for each grammar,
  2279. you can use the same methods that work for @code{yylex}.
  2280. @end itemize
  2281. @node Interface, Algorithm, Grammar File, Top
  2282. @chapter Parser C-Language Interface
  2283. @cindex C-language interface
  2284. @cindex interface
  2285. The Bison parser is actually a C function named @code{yyparse}. Here we
  2286. describe the interface conventions of @code{yyparse} and the other
  2287. functions that it needs to use.
  2288. Keep in mind that the parser uses many C identifiers starting with
  2289. @samp{yy} and @samp{YY} for internal purposes. If you use such an
  2290. identifier (aside from those in this manual) in an action or in additional
  2291. C code in the grammar file, you are likely to run into trouble.
  2292. @menu
  2293. * Parser Function:: How to call @code{yyparse} and what it returns.
  2294. * Lexical:: You must supply a function @code{yylex} which reads tokens.
  2295. * Error Reporting:: You must supply a function @code{yyerror}.
  2296. * Action Features:: Special features for use in actions.
  2297. @end menu
  2298. @node Parser Function, Lexical, Interface, Interface
  2299. @section The Parser Function @code{yyparse}
  2300. @findex yyparse
  2301. You call the function @code{yyparse} to cause parsing to occur. This
  2302. function reads tokens, executes actions, and ultimately returns when it
  2303. encounters end-of-input or an unrecoverable syntax error. You can also
  2304. write an action which directs @code{yyparse} to return immediately without
  2305. reading further.
  2306. The value returned by @code{yyparse} is 0 if parsing was successful (return
  2307. is due to end-of-input).
  2308. The value is 1 if parsing failed (return is due to a syntax error).
  2309. In an action, you can cause immediate return from @code{yyparse} by using
  2310. these macros:
  2311. @table @code
  2312. @item YYACCEPT
  2313. @findex YYACCEPT
  2314. Return immediately with value 0 (to report success).
  2315. @item YYABORT
  2316. @findex YYABORT
  2317. Return immediately with value 1 (to report failure).
  2318. @end table
  2319. @node Lexical, Error Reporting, Parser Function, Interface
  2320. @section The Lexical Analyzer Function @code{yylex}
  2321. @findex yylex
  2322. @cindex lexical analyzer
  2323. The @dfn{lexical analyzer} function, @code{yylex}, recognizes tokens from
  2324. the input stream and returns them to the parser. Bison does not create
  2325. this function automatically; you must write it so that @code{yyparse} can
  2326. call it. The function is sometimes referred to as a lexical scanner.
  2327. In simple programs, @code{yylex} is often defined at the end of the Bison
  2328. grammar file. If @code{yylex} is defined in a separate source file, you
  2329. need to arrange for the token-type macro definitions to be available there.
  2330. To do this, use the @samp{-d} option when you run Bison, so that it will
  2331. write these macro definitions into a separate header file
  2332. @file{@var{name}.tab.h} which you can include in the other source files
  2333. that need it. @xref{Invocation}.@refill
  2334. @menu
  2335. * Calling Convention:: How @code{yyparse} calls @code{yylex}.
  2336. * Token Values:: How @code{yylex} must return the semantic value
  2337. of the token it has read.
  2338. * Token Positions:: How @code{yylex} must return the text position
  2339. (line number, etc.) of the token, if the
  2340. actions want that.
  2341. * Pure Calling:: How the calling convention differs
  2342. in a pure parser (@pxref{Pure Decl}).
  2343. @end menu
  2344. @node Calling Convention, Token Values, Lexical, Lexical
  2345. @subsection Calling Convention for @code{yylex}
  2346. The value that @code{yylex} returns must be the numeric code for the type
  2347. of token it has just found, or 0 for end-of-input.
  2348. When a token is referred to in the grammar rules by a name, that name
  2349. in the parser file becomes a C macro whose definition is the proper
  2350. numeric code for that token type. So @code{yylex} can use the name
  2351. to indicate that type. @xref{Symbols}.
  2352. When a token is referred to in the grammar rules by a character literal,
  2353. the numeric code for that character is also the code for the token type.
  2354. So @code{yylex} can simply return that character code. The null character
  2355. must not be used this way, because its code is zero and that is what
  2356. signifies end-of-input.
  2357. Here is an example showing these things:
  2358. @example
  2359. yylex()
  2360. @{
  2361. @dots{}
  2362. if (c == EOF) /* Detect end of file. */
  2363. return 0;
  2364. @dots{}
  2365. if (c == '+' || c == '-')
  2366. return c; /* Assume token type for `+' is '+'. */
  2367. @dots{}
  2368. return INT; /* Return the type of the token. */
  2369. @dots{}
  2370. @}
  2371. @end example
  2372. @noindent
  2373. This interface has been designed so that the output from the @code{lex}
  2374. utility can be used without change as the definition of @code{yylex}.
  2375. @node Token Values, Token Positions, Calling Convention, Lexical
  2376. @subsection Semantic Values of Tokens
  2377. @vindex yylval
  2378. In an ordinary (nonreentrant) parser, the semantic value of the token must
  2379. be stored into the global variable @code{yylval}. When you are using
  2380. just one data type for semantic values, @code{yylval} has that type.
  2381. Thus, if the type is @code{int} (the default), you might write this in
  2382. @code{yylex}:
  2383. @example
  2384. @dots{}
  2385. yylval = value; /* Put value onto Bison stack. */
  2386. return INT; /* Return the type of the token. */
  2387. @dots{}
  2388. @end example
  2389. When you are using multiple data types, @code{yylval}'s type is a union
  2390. made from the @code{%union} declaration (@pxref{Union Decl}). So when
  2391. you store a token's value, you must use the proper member of the union.
  2392. If the @code{%union} declaration looks like this:
  2393. @example
  2394. %union @{
  2395. int intval;
  2396. double val;
  2397. symrec *tptr;
  2398. @}
  2399. @end example
  2400. @noindent
  2401. then the code in @code{yylex} might look like this:
  2402. @example
  2403. @dots{}
  2404. yylval.intval = value; /* Put value onto Bison stack. */
  2405. return INT; /* Return the type of the token. */
  2406. @dots{}
  2407. @end example
  2408. @node Token Positions, Pure Calling, Token Values, Lexical
  2409. @subsection Textual Positions of Tokens
  2410. @vindex yylloc
  2411. If you are using the @samp{@@@var{n}}-feature (@pxref{Action Features}) in
  2412. actions to keep track of the textual locations of tokens and groupings,
  2413. then you must provide this information in @code{yylex}. The function
  2414. @code{yyparse} expects to find the textual location of a token just parsed
  2415. in the global variable @code{yylloc}. So @code{yylex} must store the
  2416. proper data in that variable. The value of @code{yylloc} is a structure
  2417. and you need only initialize the members that are going to be used by the
  2418. actions. The four members are called @code{first_line},
  2419. @code{first_column}, @code{last_line} and @code{last_column}. Note that
  2420. the use of this feature makes the parser noticeably slower.
  2421. @tindex YYLTYPE
  2422. The data type of @code{yylloc} has the name @code{YYLTYPE}.
  2423. @node Pure Calling,, Token Positions, Lexical
  2424. @subsection Calling for Pure Parsers
  2425. When you use the Bison declaration @code{%pure_parser} to request a pure,
  2426. reentrant parser, the global communication variables @code{yylval} and
  2427. @code{yylloc} cannot be used. (@xref{Pure Decl}.) In such parsers the
  2428. two global variables are replaced by pointers passed as arguments to
  2429. @code{yylex}. You must declare them as shown here, and pass the
  2430. information back by storing it through those pointers.
  2431. @example
  2432. yylex (lvalp, llocp)
  2433. YYSTYPE *lvalp;
  2434. YYLTYPE *llocp;
  2435. @{
  2436. @dots{}
  2437. *lvalp = value; /* Put value onto Bison stack. */
  2438. return INT; /* Return the type of the token. */
  2439. @dots{}
  2440. @}
  2441. @end example
  2442. @node Error Reporting, Action Features, Lexical, Interface
  2443. @section The Error Reporting Function @code{yyerror}
  2444. @cindex error reporting function
  2445. @findex yyerror
  2446. @cindex parse error
  2447. @cindex syntax error
  2448. The Bison parser detects a @dfn{parse error} or @dfn{syntax error}
  2449. whenever it reads a token which cannot satisfy any syntax rule. A
  2450. action in the grammar can also explicitly proclaim an error, using the
  2451. macro @code{YYERROR} (@pxref{Action Features}).
  2452. The Bison parser expects to report the error by calling an error
  2453. reporting function named @code{yyerror}, which you must supply. It is
  2454. called by @code{yyparse} whenever a syntax error is found, and it
  2455. receives one argument. For a parse error, the string is always
  2456. @w{@code{"parse error"}}.
  2457. The parser can detect one other kind of error: stack overflow. This
  2458. happens when the input contains constructions that are very deeply
  2459. nested. It isn't likely you will encounter this, since the Bison
  2460. parser extends its stack automatically up to a very large limit. But
  2461. if overflow happens, @code{yyparse} calls @code{yyerror} in the usual
  2462. fashion, except that the argument string is @w{@code{"parser stack
  2463. overflow"}}.
  2464. The following definition suffices in simple programs:
  2465. @example
  2466. yyerror (s)
  2467. char *s;
  2468. @{
  2469. @group
  2470. fprintf (stderr, "%s\n", s);
  2471. @}
  2472. @end group
  2473. @end example
  2474. After @code{yyerror} returns to @code{yyparse}, the latter will attempt
  2475. error recovery if you have written suitable error recovery grammar rules
  2476. (@pxref{Error Recovery}). If recovery is impossible, @code{yyparse} will
  2477. immediately return 1.
  2478. @vindex yynerrs
  2479. The variable @code{yynerrs} contains the number of syntax errors
  2480. encountered so far. Normally this variable is global; but if you
  2481. request a pure parser (@pxref{Pure Decl}) then it is a local variable
  2482. which only the actions can access.
  2483. @node Action Features,, Error Reporting, Interface
  2484. @section Special Features for Use in Actions
  2485. @cindex summary, action features
  2486. @cindex action features summary
  2487. Here is a table of Bison constructs, variables and macros that
  2488. are useful in actions.
  2489. @table @samp
  2490. @item $$
  2491. Acts like a variable that contains the semantic value for the
  2492. grouping made by the current rule. @xref{Actions}.
  2493. @item $@var{n}
  2494. Acts like a variable that contains the semantic value for the
  2495. @var{n}th component of the current rule. @xref{Actions}.
  2496. @item $<@var{typealt}>$
  2497. Like @code{$$} but specifies alternative @var{typealt} in the union
  2498. specified by the @code{%union} declaration. @xref{Action Types}.
  2499. @item $<@var{typealt}>@var{n}
  2500. Like @code{$@var{n}} but specifies alternative @var{typealt} in the
  2501. union specified by the @code{%union} declaration. @xref{Action
  2502. Types}.@refill
  2503. @item YYABORT;
  2504. Return immediately from @code{yyparse}, indicating failure.
  2505. @xref{Parser Function}.
  2506. @item YYACCEPT;
  2507. Return immediately from @code{yyparse}, indicating success.
  2508. @xref{Parser Function}.
  2509. @item YYBACKUP (@var{token}, @var{value});
  2510. @findex YYBACKUP
  2511. Unshift a token. This macro is allowed only for rules that reduce
  2512. a single value, and only when there is no look-ahead token.
  2513. It installs a look-ahead token with token type @var{token} and
  2514. semantic value @var{value}; then it discards the value that was
  2515. going to be reduced by this rule.
  2516. If the macro is used when it is not valid, such as when there is
  2517. a look-ahead token already, then it reports a syntax error with
  2518. a message @samp{cannot back up} and performs ordinary error
  2519. recovery.
  2520. In either case, the rest of the action is not executed.
  2521. @item YYEMPTY
  2522. @vindex YYEMPTY
  2523. Value stored in @code{yychar} when there is no look-ahead token.
  2524. @item YYERROR;
  2525. @findex YYERROR
  2526. Cause an immediate syntax error. This statement initiates error
  2527. recovery just as if the parser itself had detected an error; however, it
  2528. does not call @code{yyerror}, and does not print any message. If you
  2529. want to print an error message, call @code{yyerror} explicitly before
  2530. the @samp{YYERROR;} statement. @xref{Error Recovery}.
  2531. @item YYRECOVERING
  2532. This macro stands for an expression that has the value 1 when the parser
  2533. is recovering from a syntax error, and 0 the rest of the time.
  2534. @xref{Error Recovery}.
  2535. @item yychar
  2536. Variable containing the current look-ahead token. (In a pure parser,
  2537. this is actually a local variable within @code{yyparse}.) When there is
  2538. no look-ahead token, the value @code{YYEMPTY} is stored in the variable.
  2539. @xref{Look-Ahead}.
  2540. @item yyclearin;
  2541. Discard the current look-ahead token. This is useful primarily in
  2542. error rules. @xref{Error Recovery}.
  2543. @item yyerrok;
  2544. Resume generating error messages immediately for subsequent syntax
  2545. errors. This is useful primarily in error rules. @xref{Error
  2546. Recovery}.
  2547. @item @@@var{n}
  2548. @findex @@@var{n}
  2549. Acts like a structure variable containing information on the line
  2550. numbers and column numbers of the @var{n}th component of the current
  2551. rule. The structure has four members, like this:
  2552. @example
  2553. struct @{
  2554. int first_line, last_line;
  2555. int first_column, last_column;
  2556. @};
  2557. @end example
  2558. Thus, to get the starting line number of the third component, use
  2559. @samp{@@3.first_line}.
  2560. In order for the members of this structure to contain valid information,
  2561. you must make @code{yylex} supply this information about each token.
  2562. If you need only certain members, then @code{yylex} need only fill in
  2563. those members.
  2564. The use of this feature makes the parser noticeably slower.
  2565. @end table
  2566. @node Algorithm, Error Recovery, Interface, Top
  2567. @chapter The Bison Parser Algorithm
  2568. @cindex Bison parser algorithm
  2569. @cindex algorithm of parser
  2570. @cindex shifting
  2571. @cindex reduction
  2572. @cindex parser stack
  2573. @cindex stack, parser
  2574. As Bison reads tokens, it pushes them onto a stack along with their
  2575. semantic values. The stack is called the @dfn{parser stack}. Pushing a
  2576. token is traditionally called @dfn{shifting}.
  2577. For example, suppose the infix calculator has read @samp{1 + 5 *}, with a
  2578. @samp{3} to come. The stack will have four elements, one for each token
  2579. that was shifted.
  2580. But the stack does not always have an element for each token read. When
  2581. the last @var{n} tokens and groupings shifted match the components of a
  2582. grammar rule, they can be combined according to that rule. This is called
  2583. @dfn{reduction}. Those tokens and groupings are replaced on the stack by a
  2584. single grouping whose symbol is the result (left hand side) of that rule.
  2585. Running the rule's action is part of the process of reduction, because this
  2586. is what computes the semantic value of the resulting grouping.
  2587. For example, if the infix calculator's parser stack contains this:
  2588. @example
  2589. 1 + 5 * 3
  2590. @end example
  2591. @noindent
  2592. and the next input token is a newline character, then the last three
  2593. elements can be reduced to 15 via the rule:
  2594. @example
  2595. expr: expr '*' expr;
  2596. @end example
  2597. @noindent
  2598. Then the stack contains just these three elements:
  2599. @example
  2600. 1 + 15
  2601. @end example
  2602. @noindent
  2603. At this point, another reduction can be made, resulting in the single value
  2604. 16. Then the newline token can be shifted.
  2605. The parser tries, by shifts and reductions, to reduce the entire input down
  2606. to a single grouping whose symbol is the grammar's start-symbol
  2607. (@pxref{Language and Grammar}).
  2608. This kind of parser is known in the literature as a bottom-up parser.
  2609. @menu
  2610. * Look-Ahead:: Parser looks one token ahead when deciding what to do.
  2611. * Shift/Reduce:: Conflicts: when either shifting or reduction is valid.
  2612. * Precedence:: Operator precedence works by resolving conflicts.
  2613. * Contextual Precedence:: When an operator's precedence depends on context.
  2614. * Parser States:: The parser is a finite-state-machine with stack.
  2615. * Reduce/Reduce:: When two rules are applicable in the same situation.
  2616. * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified.
  2617. * Stack Overflow:: What happens when stack gets full. How to avoid it.
  2618. @end menu
  2619. @node Look-Ahead, Shift/Reduce, Algorithm, Algorithm
  2620. @section Look-Ahead Tokens
  2621. @cindex look-ahead token
  2622. The Bison parser does @emph{not} always reduce immediately as soon as the
  2623. last @var{n} tokens and groupings match a rule. This is because such a
  2624. simple strategy is inadequate to handle most languages. Instead, when a
  2625. reduction is possible, the parser sometimes ``looks ahead'' at the next
  2626. token in order to decide what to do.
  2627. When a token is read, it is not immediately shifted; first it becomes the
  2628. @dfn{look-ahead token}, which is not on the stack. Now the parser can
  2629. perform one or more reductions of tokens and groupings on the stack, while
  2630. the look-ahead token remains off to the side. When no more reductions
  2631. should take place, the look-ahead token is shifted onto the stack. This
  2632. does not mean that all possible reductions have been done; depending on the
  2633. token type of the look-ahead token, some rules may choose to delay their
  2634. application.
  2635. Here is a simple case where look-ahead is needed. These three rules define
  2636. expressions which contain binary addition operators and postfix unary
  2637. factorial operators (@samp{!}), and allow parentheses for grouping.
  2638. @example
  2639. expr: term '+' expr
  2640. | term
  2641. ;
  2642. term: '(' expr ')'
  2643. | term '!'
  2644. | NUMBER
  2645. ;
  2646. @end example
  2647. Suppose that the tokens @w{@samp{1 + 2}} have been read and shifted; what
  2648. should be done? If the following token is @samp{)}, then the first three
  2649. tokens must be reduced to form an @code{expr}. This is the only valid
  2650. course, because shifting the @samp{)} would produce a sequence of symbols
  2651. @w{@code{term ')'}}, and no rule allows this.
  2652. If the following token is @samp{!}, then it must be shifted immediately so
  2653. that @w{@samp{2 !}} can be reduced to make a @code{term}. If instead the
  2654. parser were to reduce before shifting, @w{@samp{1 + 2}} would become an
  2655. @code{expr}. It would then be impossible to shift the @samp{!} because
  2656. doing so would produce on the stack the sequence of symbols @code{expr
  2657. '!'}. No rule allows that sequence.
  2658. @vindex yychar
  2659. The current look-ahead token is stored in the variable @code{yychar}.
  2660. @xref{Action Features}.
  2661. @node Shift/Reduce, Precedence, Look-Ahead, Algorithm
  2662. @section Shift/Reduce Conflicts
  2663. @cindex conflicts
  2664. @cindex shift/reduce conflicts
  2665. @cindex dangling @code{else}
  2666. @cindex @code{else}, dangling
  2667. Suppose we are parsing a language which has if-then and if-then-else
  2668. statements, with a pair of rules like this:
  2669. @example
  2670. if_stmt:
  2671. IF expr THEN stmt
  2672. | IF expr THEN stmt ELSE stmt
  2673. ;
  2674. @end example
  2675. @noindent
  2676. (Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are
  2677. terminal symbols for specific keyword tokens.)
  2678. When the @code{ELSE} token is read and becomes the look-ahead token, the
  2679. contents of the stack (assuming the input is valid) are just right for
  2680. reduction by the first rule. But it is also legitimate to shift the
  2681. @code{ELSE}, because that would lead to eventual reduction by the second
  2682. rule.
  2683. This situation, where either a shift or a reduction would be valid, is
  2684. called a @dfn{shift/reduce conflict}. Bison is designed to resolve these
  2685. conflicts by choosing to shift, unless otherwise directed by operator
  2686. precedence declarations. To see the reason for this, let's contrast
  2687. it with the other alternative.
  2688. Since the parser prefers to shift the @code{ELSE}, the result is to attach
  2689. the else-clause to the innermost if-statement, making these two inputs
  2690. equivalent:
  2691. @example
  2692. if x then if y then win(); else lose;
  2693. if x then do; if y then win(); else lose; end;
  2694. @end example
  2695. But if the parser chose to reduce when possible rather than shift, the
  2696. result would be to attach the else-clause to the outermost if-statement,
  2697. making these two inputs equivalent:
  2698. @example
  2699. if x then if y then win(); else lose;
  2700. if x then do; if y then win(); end; else lose;
  2701. @end example
  2702. The conflict exists because the grammar as written is ambiguous: either
  2703. parsing of the simple nested if-statement is legitimate. The established
  2704. convention is that these ambiguities are resolved by attaching the
  2705. else-clause to the innermost if-statement; this is what Bison accomplishes
  2706. by choosing to shift rather than reduce. (It would ideally be cleaner to
  2707. write an unambiguous grammar, but that is very hard to do in this case.)
  2708. This particular ambiguity was first encountered in the specifications of
  2709. Algol 60 and is called the ``dangling @code{else}'' ambiguity.
  2710. To avoid warnings from Bison about predictable, legitimate shift/reduce
  2711. conflicts, use the @code{%expect @var{n}} declaration. There will be no
  2712. warning as long as the number of shift/reduce conflicts is exactly @var{n}.
  2713. @xref{Expect Decl}.
  2714. @node Precedence, Contextual Precedence, Shift/Reduce, Algorithm
  2715. @section Operator Precedence
  2716. @cindex operator precedence
  2717. @cindex precedence of operators
  2718. Another situation where shift/reduce conflicts appear is in arithmetic
  2719. expressions. Here shifting is not always the preferred resolution; the
  2720. Bison declarations for operator precedence allow you to specify when to
  2721. shift and when to reduce.
  2722. @menu
  2723. * Why Precedence:: An example showing why precedence is needed.
  2724. * Using Precedence:: How to specify precedence in Bison grammars.
  2725. * Precedence Examples:: How these features are used in the previous example.
  2726. * How Precedence:: How they work.
  2727. @end menu
  2728. @node Why Precedence, Using Precedence, Precedence, Precedence
  2729. @subsection When Precedence is Needed
  2730. Consider the following ambiguous grammar fragment (ambiguous because the
  2731. input @w{@samp{1 - 2 * 3}} can be parsed in two different ways):
  2732. @example
  2733. expr: expr '-' expr
  2734. | expr '*' expr
  2735. | expr '<' expr
  2736. | '(' expr ')'
  2737. @dots{}
  2738. ;
  2739. @end example
  2740. @noindent
  2741. Suppose the parser has seen the tokens @samp{1}, @samp{-} and @samp{2};
  2742. should it reduce them via the rule for the addition operator? It depends
  2743. on the next token. Of course, if the next token is @samp{)}, we must
  2744. reduce; shifting is invalid because no single rule can reduce the token
  2745. sequence @w{@samp{- 2 )}} or anything starting with that. But if the next
  2746. token is @samp{*} or @samp{<}, we have a choice: either shifting or
  2747. reduction would allow the parse to complete, but with different
  2748. results.
  2749. To decide which one Bison should do, we must consider the
  2750. results. If the next operator token @var{op} is shifted, then it
  2751. must be reduced first in order to permit another opportunity to
  2752. reduce the sum. The result is (in effect) @w{@samp{1 - (2
  2753. @var{op} 3)}}. On the other hand, if the subtraction is reduced
  2754. before shifting @var{op}, the result is @w{@samp{(1 - 2) @var{op}
  2755. 3}}. Clearly, then, the choice of shift or reduce should depend
  2756. on the relative precedence of the operators @samp{-} and
  2757. @var{op}: @samp{*} should be shifted first, but not @samp{<}.
  2758. @cindex associativity
  2759. What about input such as @w{@samp{1 - 2 - 5}}; should this be
  2760. @w{@samp{(1 - 2) - 5}} or should it be @w{@samp{1 - (2 - 5)}}? For
  2761. most operators we prefer the former, which is called @dfn{left
  2762. association}. The latter alternative, @dfn{right association}, is
  2763. desirable for assignment operators. The choice of left or right
  2764. association is a matter of whether the parser chooses to shift or
  2765. reduce when the stack contains @w{@samp{1 - 2}} and the look-ahead
  2766. token is @samp{-}: shifting makes right-associativity.
  2767. @node Using Precedence, Precedence Examples, Why Precedence, Precedence
  2768. @subsection Specifying Operator Precedence
  2769. @findex %left
  2770. @findex %right
  2771. @findex %nonassoc
  2772. Bison allows you to specify these choices with the operator precedence
  2773. declarations @code{%left} and @code{%right}. Each such declaration
  2774. contains a list of tokens, which are operators whose precedence and
  2775. associativity is being declared. The @code{%left} declaration makes all
  2776. those operators left-associative and the @code{%right} declaration makes
  2777. them right-associative. A third alternative is @code{%nonassoc}, which
  2778. declares that it is a syntax error to find the same operator twice ``in a
  2779. row''.
  2780. The relative precedence of different operators is controlled by the
  2781. order in which they are declared. The first @code{%left} or
  2782. @code{%right} declaration in the file declares the operators whose
  2783. precedence is lowest, the next such declaration declares the operators
  2784. whose precedence is a little higher, and so on.
  2785. @node Precedence Examples, How Precedence, Using Precedence, Precedence
  2786. @subsection Precedence Examples
  2787. In our example, we would want the following declarations:
  2788. @example
  2789. %left '<'
  2790. %left '-'
  2791. %left '*'
  2792. @end example
  2793. In a more complete example, which supports other operators as well, we
  2794. would declare them in groups of equal precedence. For example, @code{'+'} is
  2795. declared with @code{'-'}:
  2796. @example
  2797. %left '<' '>' '=' NE LE GE
  2798. %left '+' '-'
  2799. %left '*' '/'
  2800. @end example
  2801. @noindent
  2802. (Here @code{NE} and so on stand for the operators for ``not equal''
  2803. and so on. We assume that these tokens are more than one character long
  2804. and therefore are represented by names, not character literals.)
  2805. @node How Precedence,, Precedence Examples, Precedence
  2806. @subsection How Precedence Works
  2807. The first effect of the precedence declarations is to assign precedence
  2808. levels to the terminal symbols declared. The second effect is to assign
  2809. precedence levels to certain rules: each rule gets its precedence from the
  2810. last terminal symbol mentioned in the components. (You can also specify
  2811. explicitly the precedence of a rule. @xref{Contextual Precedence}.)
  2812. Finally, the resolution of conflicts works by comparing the
  2813. precedence of the rule being considered with that of the
  2814. look-ahead token. If the token's precedence is higher, the
  2815. choice is to shift. If the rule's precedence is higher, the
  2816. choice is to reduce. If they have equal precedence, the choice
  2817. is made based on the associativity of that precedence level. The
  2818. verbose output file made by @samp{-v} (@pxref{Invocation}) says
  2819. how each conflict was resolved.
  2820. Not all rules and not all tokens have precedence. If either the rule or
  2821. the look-ahead token has no precedence, then the default is to shift.
  2822. @node Contextual Precedence, Parser States, Precedence, Algorithm
  2823. @section Context-Dependent Precedence
  2824. @cindex context-dependent precedence
  2825. @cindex unary operator precedence
  2826. @cindex precedence, context-dependent
  2827. @cindex precedence, unary operator
  2828. @findex %prec
  2829. Often the precedence of an operator depends on the context. This sounds
  2830. outlandish at first, but it is really very common. For example, a minus
  2831. sign typically has a very high precedence as a unary operator, and a
  2832. somewhat lower precedence (lower than multiplication) as a binary operator.
  2833. The Bison precedence declarations, @code{%left}, @code{%right} and
  2834. @code{%nonassoc}, can only be used once for a given token; so a token has
  2835. only one precedence declared in this way. For context-dependent
  2836. precedence, you need to use an additional mechanism: the @code{%prec}
  2837. modifier for rules.@refill
  2838. The @code{%prec} modifier declares the precedence of a particular rule by
  2839. specifying a terminal symbol whose predecence should be used for that rule.
  2840. It's not necessary for that symbol to appear otherwise in the rule. The
  2841. modifier's syntax is:
  2842. @example
  2843. %prec @var{terminal-symbol}
  2844. @end example
  2845. @noindent
  2846. and it is written after the components of the rule. Its effect is to
  2847. assign the rule the precedence of @var{terminal-symbol}, overriding
  2848. the precedence that would be deduced for it in the ordinary way. The
  2849. altered rule precedence then affects how conflicts involving that rule
  2850. are resolved (@pxref{Precedence}).
  2851. Here is how @code{%prec} solves the problem of unary minus. First, declare
  2852. a precedence for a fictitious terminal symbol named @code{UMINUS}. There
  2853. are no tokens of this type, but the symbol serves to stand for its
  2854. precedence:
  2855. @example
  2856. @dots{}
  2857. %left '+' '-'
  2858. %left '*'
  2859. %left UMINUS
  2860. @end example
  2861. Now the precedence of @code{UMINUS} can be used in specific rules:
  2862. @example
  2863. exp: @dots{}
  2864. | exp '-' exp
  2865. @dots{}
  2866. | '-' exp %prec UMINUS
  2867. @end example
  2868. @node Parser States, Reduce/Reduce, Contextual Precedence, Algorithm
  2869. @section Parser States
  2870. @cindex finite-state machine
  2871. @cindex parser state
  2872. @cindex state (of parser)
  2873. The function @code{yyparse} is implemented using a finite-state machine.
  2874. The values pushed on the parser stack are not simply token type codes; they
  2875. represent the entire sequence of terminal and nonterminal symbols at or
  2876. near the top of the stack. The current state collects all the information
  2877. about previous input which is relevant to deciding what to do next.
  2878. Each time a look-ahead token is read, the current parser state together
  2879. with the type of look-ahead token are looked up in a table. This table
  2880. entry can say, ``Shift the look-ahead token.'' In this case, it also
  2881. specifies the new parser state, which is pushed onto the top of the
  2882. parser stack. Or it can say, ``Reduce using rule number @var{n}.''
  2883. This means that a certain of tokens or groupings are taken off the top
  2884. of the stack, and replaced by one grouping. In other words, that number
  2885. of states are popped from the stack, and one new state is pushed.
  2886. There is one other alternative: the table can say that the look-ahead token
  2887. is erroneous in the current state. This causes error processing to begin
  2888. (@pxref{Error Recovery}).
  2889. @node Reduce/Reduce, Mystery Conflicts, Parser States, Algorithm
  2890. @section Reduce/Reduce Conflicts
  2891. @cindex reduce/reduce conflict
  2892. @cindex conflicts, reduce/reduce
  2893. A reduce/reduce conflict occurs if there are two or more rules that apply
  2894. to the same sequence of input. This usually indicates a serious error
  2895. in the grammar.
  2896. For example, here is an erroneous attempt to define a sequence
  2897. of zero or more @code{word} groupings.
  2898. @example
  2899. sequence: /* empty */
  2900. @{ printf ("empty sequence\n"); @}
  2901. | word
  2902. @{ printf ("single word %s\n", $1); @}
  2903. | sequence word
  2904. @{ printf ("added word %s\n", $2); @}
  2905. ;
  2906. @end example
  2907. @noindent
  2908. The error is an ambiguity: there is more than one way to parse a single
  2909. @code{word} into a @code{sequence}. It could be reduced directly via the
  2910. second rule. Alternatively, nothing-at-all could be reduced into a
  2911. @code{sequence} via the first rule, and this could be combined with the
  2912. @code{word} using the third rule.
  2913. You might think that this is a distinction without a difference, because it
  2914. does not change whether any particular input is valid or not. But it does
  2915. affect which actions are run. One parsing order runs the second rule's
  2916. action; the other runs the first rule's action and the third rule's action.
  2917. In this example, the output of the program changes.
  2918. Bison resolves a reduce/reduce conflict by choosing to use the rule that
  2919. appears first in the grammar, but it is very risky to rely on this. Every
  2920. reduce/reduce conflict must be studied and usually eliminated. Here is the
  2921. proper way to define @code{sequence}:
  2922. @example
  2923. sequence: /* empty */
  2924. @{ printf ("empty sequence\n"); @}
  2925. | sequence word
  2926. @{ printf ("added word %s\n", $2); @}
  2927. ;
  2928. @end example
  2929. Here is another common error that yields a reduce/reduce conflict:
  2930. @example
  2931. sequence: /* empty */
  2932. | sequence words
  2933. | sequence redirects
  2934. ;
  2935. words: /* empty */
  2936. | words word
  2937. ;
  2938. redirects:/* empty */
  2939. | redirects redirect
  2940. ;
  2941. @end example
  2942. @noindent
  2943. The intention here is to define a sequence which can contain either
  2944. @code{word} or @code{redirect} groupings. The individual definitions of
  2945. @code{sequence}, @code{words} and @code{redirects} are error-free, but the
  2946. three together make a subtle ambiguity: even an empty input can be parsed
  2947. in infinitely many ways!
  2948. Consider: nothing-at-all could be a @code{words}. Or it could be two
  2949. @code{words} in a row, or three, or any number. It could equally well be a
  2950. @code{redirects}, or two, or any number. Or it could be a @code{words}
  2951. followed by three @code{redirects} and another @code{words}. And so on.
  2952. Here are two ways to correct these rules. First, to make it a single level
  2953. of sequence:
  2954. @example
  2955. sequence: /* empty */
  2956. | sequence word
  2957. | sequence redirect
  2958. ;
  2959. @end example
  2960. Second, to prevent either a @code{words} or a @code{redirects}
  2961. from being empty:
  2962. @example
  2963. sequence: /* empty */
  2964. | sequence words
  2965. | sequence redirects
  2966. ;
  2967. words: word
  2968. | words word
  2969. ;
  2970. redirects:redirect
  2971. | redirects redirect
  2972. ;
  2973. @end example
  2974. @node Mystery Conflicts, Stack Overflow, Reduce/Reduce, Algorithm
  2975. @section Mysterious Reduce/Reduce Conflicts
  2976. Sometimes reduce/reduce conflicts can occur that don't look warranted.
  2977. Here is an example:
  2978. @example
  2979. %token ID
  2980. %%
  2981. def: param_spec return_spec ','
  2982. ;
  2983. param_spec:
  2984. type
  2985. | name_list ':' type
  2986. ;
  2987. return_spec:
  2988. type
  2989. | name ':' type
  2990. ;
  2991. type: ID
  2992. ;
  2993. name: ID
  2994. ;
  2995. name_list:
  2996. name
  2997. | name ',' name_list
  2998. ;
  2999. @end example
  3000. It would seem that this grammar can be parsed with only a single token
  3001. of look-ahead: when a @code{param_spec} is being read, an @code{ID} is
  3002. a @code{name} if a comma or colon follows, or a @code{type} if another
  3003. @code{ID} follows. In other words, this grammar is LR(1).
  3004. @cindex LR(1)
  3005. @cindex LALR(1)
  3006. However, Bison, like most parser generators, cannot actually handle all
  3007. LR(1) grammars. In this grammar, two contexts, that after an @code{ID}
  3008. at the beginning of a @code{param_spec} and likewise at the beginning of
  3009. a @code{return_spec}, are similar enough that Bison assumes they are the
  3010. same. They appear similar because the same set of rules would be
  3011. active---the rule for reducing to a @code{name} and that for reducing to
  3012. a @code{type}. Bison is unable to determine at that stage of processing
  3013. that the rules would require different look-ahead tokens in the two
  3014. contexts, so it makes a single parser state for them both. Combining
  3015. the two contexts causes a conflict later. In parser terminology, this
  3016. occurrence means that the grammar is not LALR(1).
  3017. In general, it is better to fix deficiencies than to document them. But
  3018. this particular deficiency is intrinsically hard to fix; parser
  3019. generators that can handle LR(1) grammars are hard to write and tend to
  3020. produce parsers that are very large. In practice, Bison is more useful
  3021. as it is now.
  3022. When the problem arises, you can often fix it by identifying the two
  3023. parser states that are being confused, and adding something to make them
  3024. look distinct. In the above example, adding one rule to
  3025. @code{return_spec} as follows makes the problem go away:
  3026. @example
  3027. %token BOGUS
  3028. @dots{}
  3029. %%
  3030. @dots{}
  3031. return_spec:
  3032. type
  3033. | name ':' type
  3034. /* This rule is never used. */
  3035. | ID BOGUS
  3036. ;
  3037. @end example
  3038. This corrects the problem because it introduces the possibility of an
  3039. additional active rule in the context after the @code{ID} at the beginning of
  3040. @code{return_spec}. This rule is not active in the corresponding context
  3041. in a @code{param_spec}, so the two contexts receive distinct parser states.
  3042. As long as the token @code{BOGUS} is never generated by @code{yylex},
  3043. the added rule cannot alter the way actual input is parsed.
  3044. In this particular example, there is another way to solve the problem:
  3045. rewrite the rule for @code{return_spec} to use @code{ID} directly
  3046. instead of via @code{name}. This also causes the two confusing
  3047. contexts to have different sets of active rules, because the one for
  3048. @code{return_spec} activates the altered rule for @code{return_spec}
  3049. rather than the one for @code{name}.
  3050. @example
  3051. param_spec:
  3052. type
  3053. | name_list ':' type
  3054. ;
  3055. return_spec:
  3056. type
  3057. | ID ':' type
  3058. ;
  3059. @end example
  3060. @node Stack Overflow,, Mystery Conflicts, Algorithm
  3061. @section Stack Overflow, and How to Avoid It
  3062. @cindex stack overflow
  3063. @cindex parser stack overflow
  3064. @cindex overflow of parser stack
  3065. The Bison parser stack can overflow if too many tokens are shifted and
  3066. not reduced. When this happens, the parser function @code{yyparse}
  3067. returns a nonzero value, pausing only to call @code{yyerror} to report
  3068. the overflow.
  3069. @vindex YYMAXDEPTH
  3070. By defining the macro @code{YYMAXDEPTH}, you can control how deep the
  3071. parser stack can become before a stack overflow occurs. Define the
  3072. macro with a value that is an integer. This value is the maximum number
  3073. of tokens that can be shifted (and not reduced) before overflow.
  3074. It must be a constant expression whose value is known at compile time.
  3075. The stack space allowed is not necessarily allocated. If you specify a
  3076. large value for @code{YYMAXDEPTH}, the parser actually allocates a small
  3077. stack at first, and then makes it bigger by stages as needed. This
  3078. increasing allocation happens automatically and silently. Therefore,
  3079. you do not need to make @code{YYMAXDEPTH} painfully small merely to save
  3080. space for ordinary inputs that do not need much stack.
  3081. The default value of @code{YYMAXDEPTH}, if you do not define it, is
  3082. 10000.
  3083. @vindex YYINITDEPTH
  3084. You can control how much stack is allocated initially by defining the
  3085. macro @code{YYINITDEPTH}. This value too must be a compile-time
  3086. constant integer. The default is 200.
  3087. @node Error Recovery, Context Dependency, Algorithm, Top
  3088. @chapter Error Recovery
  3089. @cindex error recovery
  3090. @cindex recovery from errors
  3091. It is not usually acceptable to have a program terminate on a parse
  3092. error. For example, a compiler should recover sufficiently to parse the
  3093. rest of the input file and check it for errors; a calculator should accept
  3094. another expression.
  3095. In a simple interactive command parser where each input is one line, it may
  3096. be sufficient to allow @code{yyparse} to return 1 on error and have the
  3097. caller ignore the rest of the input line when that happens (and then call
  3098. @code{yyparse} again). But this is inadequate for a compiler, because it
  3099. forgets all the syntactic context leading up to the error. A syntax error
  3100. deep within a function in the compiler input should not cause the compiler
  3101. to treat the following line like the beginning of a source file.
  3102. @findex error
  3103. You can define how to recover from a syntax error by writing rules to
  3104. recognize the special token @code{error}. This is a terminal symbol that
  3105. is always defined (you need not declare it) and reserved for error
  3106. handling. The Bison parser generates an @code{error} token whenever a
  3107. syntax error happens; if you have provided a rule to recognize this token
  3108. in the current context, the parse can continue. For example:
  3109. @example
  3110. stmnts: /* empty string */
  3111. | stmnts '\n'
  3112. | stmnts exp '\n'
  3113. | stmnts error '\n'
  3114. @end example
  3115. The fourth rule in this example says that an error followed by a newline
  3116. makes a valid addition to any @code{stmnts}.
  3117. What happens if a syntax error occurs in the middle of an @code{exp}? The
  3118. error recovery rule, interpreted strictly, applies to the precise sequence
  3119. of a @code{stmnts}, an @code{error} and a newline. If an error occurs in
  3120. the middle of an @code{exp}, there will probably be some additional tokens
  3121. and subexpressions on the stack after the last @code{stmnts}, and there
  3122. will be tokens to read before the next newline. So the rule is not
  3123. applicable in the ordinary way.
  3124. But Bison can force the situation to fit the rule, by discarding part of
  3125. the semantic context and part of the input. First it discards states and
  3126. objects from the stack until it gets back to a state in which the
  3127. @code{error} token is acceptable. (This means that the subexpressions
  3128. already parsed are discarded, back to the last complete @code{stmnts}.) At
  3129. this point the @code{error} token can be shifted. Then, if the old
  3130. look-ahead token is not acceptable to be shifted next, the parser reads
  3131. tokens and discards them until it finds a token which is acceptable. In
  3132. this example, Bison reads and discards input until the next newline
  3133. so that the fourth rule can apply.
  3134. The choice of error rules in the grammar is a choice of strategies for
  3135. error recovery. A simple and useful strategy is simply to skip the rest of
  3136. the current input line or current statement if an error is detected:
  3137. @example
  3138. stmnt: error ';' /* on error, skip until ';' is read */
  3139. @end example
  3140. It is also useful to recover to the matching close-delimiter of an
  3141. opening-delimiter that has already been parsed. Otherwise the
  3142. close-delimiter will probably appear to be unmatched, and generate another,
  3143. spurious error message:
  3144. @example
  3145. primary: '(' expr ')'
  3146. | '(' error ')'
  3147. @dots{}
  3148. ;
  3149. @end example
  3150. Error recovery strategies are necessarily guesses. When they guess wrong,
  3151. one syntax error often leads to another. In the above example, the error
  3152. recovery rule guesses that an error is due to bad input within one
  3153. @code{stmnt}. Suppose that instead a spurious semicolon is inserted in the
  3154. middle of a valid @code{stmnt}. After the error recovery rule recovers
  3155. from the first error, another syntax error will be found straightaway,
  3156. since the text following the spurious semicolon is also an invalid
  3157. @code{stmnt}.
  3158. To prevent an outpouring of error messages, the parser will output no error
  3159. message for another syntax error that happens shortly after the first; only
  3160. after three consecutive input tokens have been successfully shifted will
  3161. error messages resume.
  3162. Note that rules which accept the @code{error} token may have actions, just
  3163. as any other rules can.
  3164. @findex yyerrok
  3165. You can make error messages resume immediately by using the macro
  3166. @code{yyerrok} in an action. If you do this in the error rule's action, no
  3167. error messages will be suppressed. This macro requires no arguments;
  3168. @samp{yyerrok;} is a valid C statement.
  3169. @findex yyclearin
  3170. The previous look-ahead token is reanalyzed immediately after an error. If
  3171. this is unacceptable, then the macro @code{yyclearin} may be used to clear
  3172. this token. Write the statement @samp{yyclearin;} in the error rule's
  3173. action.
  3174. For example, suppose that on a parse error, an error handling routine is
  3175. called that advances the input stream to some point where parsing should
  3176. once again commence. The next symbol returned by the lexical scanner is
  3177. probably correct. The previous look-ahead token ought to be discarded
  3178. with @samp{yyclearin;}.
  3179. @vindex YYRECOVERING
  3180. The macro @code{YYRECOVERING} stands for an expression that has the
  3181. value 1 when the parser is recovering from a syntax error, and 0 the
  3182. rest of the time. A value of 1 indicates that error messages are
  3183. currently suppressed for new syntax errors.
  3184. @node Context Dependency, Debugging, Error Recovery, Top
  3185. @chapter Handling Context Dependencies
  3186. The Bison paradigm is to parse tokens first, then group them into larger
  3187. syntactic units. In many languages, the meaning of a token is affected by
  3188. its context. Although this violates the Bison paradigm, certain techniques
  3189. (known as @dfn{kludges}) may enable you to write Bison parsers for such
  3190. languages.
  3191. @menu
  3192. * Semantic Tokens:: Token parsing can depend on the semantic context.
  3193. * Lexical Tie-ins:: Token parsing can depend on the syntactic context.
  3194. * Tie-in Recovery:: Lexical tie-ins have implications for how
  3195. error recovery rules must be written.
  3196. @end menu
  3197. (Actually, ``kludge'' means any technique that gets its job done but is
  3198. neither clean nor robust.)
  3199. @node Semantic Tokens, Lexical Tie-ins, Context Dependency, Context Dependency
  3200. @section Semantic Info in Token Types
  3201. The C language has a context dependency: the way an identifier is used
  3202. depends on what its current meaning is. For example, consider this:
  3203. @example
  3204. foo (x);
  3205. @end example
  3206. This looks like a function call statement, but if @code{foo} is a typedef
  3207. name, then this is actually a declaration of @code{x}. How can a Bison
  3208. parser for C decide how to parse this input?
  3209. The method used in GNU C is to have two different token types,
  3210. @code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an
  3211. identifier, it looks up the current declaration of the identifier in order
  3212. to decide which token type to return: @code{TYPENAME} if the identifier is
  3213. declared as a typedef, @code{IDENTIFIER} otherwise.
  3214. The grammar rules can then express the context dependency by the choice of
  3215. token type to recognize. @code{IDENTIFIER} is accepted as an expression,
  3216. but @code{TYPENAME} is not. @code{TYPENAME} can start a declaration, but
  3217. @code{IDENTIFIER} cannot. In contexts where the meaning of the identifier
  3218. is @emph{not} significant, such as in declarations that can shadow a
  3219. typedef name, either @code{TYPENAME} or @code{IDENTIFIER} is
  3220. accepted---there is one rule for each of the two token types.
  3221. This technique is simple to use if the decision of which kinds of
  3222. identifiers to allow is made at a place close to where the identifier is
  3223. parsed. But in C this is not always so: C allows a declaration to
  3224. redeclare a typedef name provided an explicit type has been specified
  3225. earlier:
  3226. @example
  3227. typedef int foo, bar, lose;
  3228. static foo (bar); /* @r{redeclare @code{bar} as static variable} */
  3229. static int foo (lose); /* @r{redeclare @code{foo} as function} */
  3230. @end example
  3231. Unfortunately, the name being declared is separated from the declaration
  3232. construct itself by a complicated syntactic structure---the ``declarator''.
  3233. As a result, the part of Bison parser for C needs to be duplicated, with
  3234. all the nonterminal names changed: once for parsing a declaration in which
  3235. a typedef name can be redefined, and once for parsing a declaration in
  3236. which that can't be done. Here is a part of the duplication, with actions
  3237. omitted for brevity:
  3238. @example
  3239. initdcl:
  3240. declarator maybeasm '='
  3241. init
  3242. | declarator maybeasm
  3243. ;
  3244. notype_initdcl:
  3245. notype_declarator maybeasm '='
  3246. init
  3247. | notype_declarator maybeasm
  3248. ;
  3249. @end example
  3250. @noindent
  3251. Here @code{initdcl} can redeclare a typedef name, but @code{notype_initdcl}
  3252. cannot. The distinction between @code{declarator} and
  3253. @code{notype_declarator} is the same sort of thing.
  3254. There is some similarity between this technique and a lexical tie-in
  3255. (described next), in that information which alters the lexical analysis is
  3256. changed during parsing by other parts of the program. The difference is
  3257. here the information is global, and is used for other purposes in the
  3258. program. A true lexical tie-in has a special-purpose flag controlled by
  3259. the syntactic context.
  3260. @node Lexical Tie-ins, Tie-in Recovery, Semantic Tokens, Context Dependency
  3261. @section Lexical Tie-ins
  3262. @cindex lexical tie-in
  3263. One way to handle context-dependency is the @dfn{lexical tie-in}: a flag
  3264. which is set by Bison actions, whose purpose is to alter the way tokens are
  3265. parsed.
  3266. For example, suppose we have a language vaguely like C, but with a special
  3267. construct @samp{hex (@var{hex-expr})}. After the keyword @code{hex} comes
  3268. an expression in parentheses in which all integers are hexadecimal. In
  3269. particular, the token @samp{a1b} must be treated as an integer rather than
  3270. as an identifier if it appears in that context. Here is how you can do it:
  3271. @example
  3272. %@{
  3273. int hexflag;
  3274. %@}
  3275. %%
  3276. @dots{}
  3277. expr: IDENTIFIER
  3278. | constant
  3279. | HEX '('
  3280. @{ hexflag = 1; @}
  3281. expr ')'
  3282. @{ hexflag = 0;
  3283. $$ = $4; @}
  3284. | expr '+' expr
  3285. @{ $$ = make_sum ($1, $3); @}
  3286. @dots{}
  3287. ;
  3288. constant:
  3289. INTEGER
  3290. | STRING
  3291. ;
  3292. @end example
  3293. @noindent
  3294. Here we assume that @code{yylex} looks at the value of @code{hexflag}; when
  3295. it is nonzero, all integers are parsed in hexadecimal, and tokens starting
  3296. with letters are parsed as integers if possible.
  3297. The declaration of @code{hexflag} shown in the C declarations section of
  3298. the parser file is needed to make it accessible to the actions (@pxref{C
  3299. Declarations}). You must also write the code in @code{yylex} to obey the
  3300. flag.
  3301. @node Tie-in Recovery,, Lexical Tie-ins, Context Dependency
  3302. @section Lexical Tie-ins and Error Recovery
  3303. Lexical tie-ins make strict demands on any error recovery rules you have.
  3304. @xref{Error Recovery}.
  3305. The reason for this is that the purpose of an error recovery rule is to
  3306. abort the parsing of one construct and resume in some larger construct.
  3307. For example, in C-like languages, a typical error recovery rule is to skip
  3308. tokens until the next semicolon, and then start a new statement, like this:
  3309. @example
  3310. stmt: expr ';'
  3311. | IF '(' expr ')' stmt @{ @dots{} @}
  3312. @dots{}
  3313. error ';'
  3314. @{ hexflag = 0; @}
  3315. ;
  3316. @end example
  3317. If there is a syntax error in the middle of a @samp{hex (@var{expr})}
  3318. construct, this error rule will apply, and then the action for the
  3319. completed @samp{hex (@var{expr})} will never run. So @code{hexflag} would
  3320. remain set for the entire rest of the input, or until the next @code{hex}
  3321. keyword, causing identifiers to be misinterpreted as integers.
  3322. To avoid this problem the error recovery rule itself clears @code{hexflag}.
  3323. There may also be an error recovery rule that works within expressions.
  3324. For example, there could be a rule which applies within parentheses
  3325. and skips to the close-parenthesis:
  3326. @example
  3327. expr: @dots{}
  3328. | '(' expr ')'
  3329. @{ $$ = $2; @}
  3330. | '(' error ')'
  3331. @dots{}
  3332. @end example
  3333. If this rule acts within the @code{hex} construct, it is not going to abort
  3334. that construct (since it applies to an inner level of parentheses within
  3335. the construct). Therefore, it should not clear the flag: the rest of
  3336. the @code{hex} construct should be parsed with the flag still in effect.
  3337. What if there is an error recovery rule which might abort out of the
  3338. @code{hex} construct or might not, depending on circumstances? There is no
  3339. way you can write the action to determine whether a @code{hex} construct is
  3340. being aborted or not. So if you are using a lexical tie-in, you had better
  3341. make sure your error recovery rules are not of this kind. Each rule must
  3342. be such that you can be sure that it always will, or always won't, have to
  3343. clear the flag.
  3344. @node Debugging, Invocation, Context Dependency, Top
  3345. @chapter Debugging Your Parser
  3346. @findex YYDEBUG
  3347. @findex yydebug
  3348. @cindex debugging
  3349. @cindex tracing the parser
  3350. If a Bison grammar compiles properly but doesn't do what you want when it
  3351. runs, the @code{yydebug} parser-trace feature can help you figure out why.
  3352. To enable compilation of trace facilities, you must define the macro
  3353. @code{YYDEBUG} when you compile the parser. You could use
  3354. @samp{-DYYDEBUG=1} as a compiler option or you could put @samp{#define
  3355. YYDEBUG 1} in the C declarations section of the grammar file (@pxref{C
  3356. Declarations}). Alternatively, use the @samp{-t} option when you run
  3357. Bison (@pxref{Invocation}). We always define @code{YYDEBUG} so that
  3358. debugging is always possible.
  3359. The trace facility uses @code{stderr}, so you must add @w{@code{#include
  3360. <stdio.h>}} to the C declarations section unless it is already there.
  3361. Once you have compiled the program with trace facilities, the way to
  3362. request a trace is to store a nonzero value in the variable @code{yydebug}.
  3363. You can do this by making the C code do it (in @code{main}, perhaps), or
  3364. you can alter the value with a C debugger.
  3365. Each step taken by the parser when @code{yydebug} is nonzero produces a
  3366. line or two of trace information, written on @code{stderr}. The trace
  3367. messages tell you these things:
  3368. @itemize @bullet
  3369. @item
  3370. Each time the parser calls @code{yylex}, what kind of token was read.
  3371. @item
  3372. Each time a token is shifted, the depth and complete contents of the
  3373. state stack (@pxref{Parser States}).
  3374. @item
  3375. Each time a rule is reduced, which rule it is, and the complete contents
  3376. of the state stack afterward.
  3377. @end itemize
  3378. To make sense of this information, it helps to refer to the listing file
  3379. produced by the Bison @samp{-v} option (@pxref{Invocation}). This file
  3380. shows the meaning of each state in terms of positions in various rules, and
  3381. also what each state will do with each possible input token. As you read
  3382. the successive trace messages, you can see that the parser is functioning
  3383. according to its specification in the listing file. Eventually you will
  3384. arrive at the place where something undesirable happens, and you will see
  3385. which parts of the grammar are to blame.
  3386. The parser file is a C program and you can use C debuggers on it, but it's
  3387. not easy to interpret what it is doing. The parser function is a
  3388. finite-state machine interpreter, and aside from the actions it executes
  3389. the same code over and over. Only the values of variables show where in
  3390. the grammar it is working.
  3391. @node Invocation, Table of Symbols, Debugging, Top
  3392. @chapter Invoking Bison
  3393. @cindex invoking Bison
  3394. @cindex Bison invocation
  3395. @cindex options for Bison invocation
  3396. The usual way to invoke Bison is as follows:
  3397. @example
  3398. bison @var{infile}
  3399. @end example
  3400. Here @var{infile} is the grammar file name, which usually ends in
  3401. @samp{.y}. The parser file's name is made by replacing the @samp{.y}
  3402. with @samp{.tab.c}. Thus, the @samp{bison foo.y} filename yields
  3403. @file{foo.tab.c}, and the @samp{bison hack/foo.y} filename yields
  3404. @file{hack/foo.tab.c}.@refill
  3405. These options can be used with Bison:
  3406. @table @samp
  3407. @item -d
  3408. Write an extra output file containing macro definitions for the token
  3409. type names defined in the grammar and the semantic value type
  3410. @code{YYSTYPE}, as well as a few @code{extern} variable declarations.
  3411. If the parser output file is named @file{@var{name}.c} then this file
  3412. is named @file{@var{name}.h}.@refill
  3413. This output file is essential if you wish to put the definition of
  3414. @code{yylex} in a separate source file, because @code{yylex} needs to
  3415. be able to refer to token type codes and the variable
  3416. @code{yylval}. @xref{Token Values}.@refill
  3417. @item -l
  3418. Don't put any @code{#line} preprocessor commands in the parser file.
  3419. Ordinarily Bison puts them in the parser file so that the C compiler
  3420. and debuggers will associate errors with your source file, the
  3421. grammar file. This option causes them to associate errors with the
  3422. parser file, treating it an independent source file in its own right.
  3423. @item -o @var{outfile}
  3424. Specify the name @var{outfile} for the parser file.
  3425. The other output files' names are constructed from @var{outfile}
  3426. as described under the @samp{-v} and @samp{-d} switches.
  3427. @item -t
  3428. Output a definition of the macro @code{YYDEBUG} into the parser file,
  3429. so that the debugging facilities are compiled. @xref{Debugging}.
  3430. @item -v
  3431. Write an extra output file containing verbose descriptions of the
  3432. parser states and what is done for each type of look-ahead token in
  3433. that state.
  3434. This file also describes all the conflicts, both those resolved by
  3435. operator precedence and the unresolved ones.
  3436. The file's name is made by removing @samp{.tab.c} or @samp{.c} from
  3437. the parser output file name, and adding @samp{.output} instead.@refill
  3438. Therefore, if the input file is @file{foo.y}, then the parser file is
  3439. called @file{foo.tab.c} by default. As a consequence, the verbose
  3440. output file is called @file{foo.output}.@refill
  3441. @item -y
  3442. Equivalent to @samp{-o y.tab.c}; the parser output file is called
  3443. @file{y.tab.c}, and the other outputs are called @file{y.output} and
  3444. @file{y.tab.h}. The purpose of this switch is to imitate Yacc's output
  3445. file name conventions. Thus, the following shell script can substitute
  3446. for Yacc:@refill
  3447. @example
  3448. bison -y $*
  3449. @end example
  3450. @end table
  3451. @node Table of Symbols, Glossary, Invocation, Top
  3452. @appendix Bison Symbols
  3453. @cindex Bison symbols, table of
  3454. @cindex symbols in Bison, table of
  3455. @table @code
  3456. @item error
  3457. A token name reserved for error recovery. This token may be used in
  3458. grammar rules so as to allow the Bison parser to recognize an error in
  3459. the grammar without halting the process. In effect, a sentence
  3460. containing an error may be recognized as valid. On a parse error, the
  3461. token @code{error} becomes the current look-ahead token. Actions
  3462. corresponding to @code{error} are then executed, and the look-ahead
  3463. token is reset to the token that originally caused the violation.
  3464. @xref{Error Recovery}.
  3465. @item YYABORT
  3466. Macro to pretend that an unrecoverable syntax error has occurred, by
  3467. making @code{yyparse} return 1 immediately. The error reporting
  3468. function @code{yyerror} is not called. @xref{Parser Function}.
  3469. @item YYACCEPT
  3470. Macro to pretend that a complete utterance of the language has been
  3471. read, by making @code{yyparse} return 0 immediately. @xref{Parser
  3472. Function}.
  3473. @item YYBACKUP
  3474. Macro to discard a value from the parser stack and fake a look-ahead
  3475. token. @xref{Action Features}.
  3476. @item YYERROR
  3477. Macro to pretend that a syntax error has just been detected: call
  3478. @code{yyerror} and then perform normal error recovery if possible
  3479. (@pxref{Error Recovery}), or (if recovery is impossible) make
  3480. @code{yyparse} return 1. @xref{Error Recovery}.
  3481. @item YYINITDEPTH
  3482. Macro for specifying the initial size of the parser stack.
  3483. @xref{Stack Overflow}.
  3484. @item YYLTYPE
  3485. Macro for the data type of @code{yylloc}; a structure with four
  3486. members. @xref{Token Positions}.
  3487. @item YYMAXDEPTH
  3488. Macro for specifying the maximum size of the parser stack.
  3489. @xref{Stack Overflow}.
  3490. @item YYRECOVERING
  3491. Macro whose value indicates whether the parser is recovering from a
  3492. syntax error. @xref{Action Features}.
  3493. @item YYSTYPE
  3494. Macro for the data type of semantic values; @code{int} by default.
  3495. @xref{Value Type}.
  3496. @item yychar
  3497. External integer variable that contains the integer value of the
  3498. current look-ahead token. (In a pure parser, it is a local variable
  3499. within @code{yyparse}.) Error-recovery rule actions may examine this
  3500. variable. @xref{Action Features}.
  3501. @item yyclearin
  3502. Macro used in error-recovery rule actions. It clears the previous
  3503. look-ahead token. @xref{Error Recovery}.
  3504. @item yydebug
  3505. External integer variable set to zero by default. If @code{yydebug}
  3506. is given a nonzero value, the parser will output information on input
  3507. symbols and parser action. @xref{Debugging}.
  3508. @item yyerrok
  3509. Macro to cause parser to recover immediately to its normal mode
  3510. after a parse error. @xref{Error Recovery}.
  3511. @item yyerror
  3512. User-supplied function to be called by @code{yyparse} on error. The
  3513. function receives one argument, a pointer to a character string
  3514. containing an error message. @xref{Error Reporting}.
  3515. @item yylex
  3516. User-supplied lexical analyzer function, called with no arguments
  3517. to get the next token. @xref{Lexical}.
  3518. @item yylval
  3519. External variable in which @code{yylex} should place the semantic
  3520. value associated with a token. (In a pure parser, it is a local
  3521. variable within @code{yyparse}, and its address is passed to
  3522. @code{yylex}.) @xref{Token Values}.
  3523. @item yylloc
  3524. External variable in which @code{yylex} should place the line and
  3525. column numbers associated with a token. (In a pure parser, it is a
  3526. local variable within @code{yyparse}, and its address is passed to
  3527. @code{yylex}.) You can ignore this variable if you don't use the
  3528. @samp{@@} feature in the grammar actions. @xref{Token Positions}.
  3529. @item yynerrs
  3530. Global variable which Bison increments each time there is a parse
  3531. error. (In a pure parser, it is a local variable within
  3532. @code{yyparse}.) @xref{Error Reporting}.
  3533. @item yyparse
  3534. The parser function produced by Bison; call this function to start
  3535. parsing. @xref{Parser Function}.
  3536. @item %left
  3537. Bison declaration to assign left associativity to token(s).
  3538. @xref{Precedence Decl}.
  3539. @item %nonassoc
  3540. Bison declaration to assign nonassociativity to token(s).
  3541. @xref{Precedence Decl}.
  3542. @item %prec
  3543. Bison declaration to assign a precedence to a specific rule.
  3544. @xref{Contextual Precedence}.
  3545. @item %pure_parser
  3546. Bison declaration to request a pure (reentrant) parser.
  3547. @xref{Pure Decl}.
  3548. @item %right
  3549. Bison declaration to assign right associativity to token(s).
  3550. @xref{Precedence Decl}.
  3551. @item %start
  3552. Bison declaration to specify the start symbol. @xref{Start Decl}.
  3553. @item %token
  3554. Bison declaration to declare token(s) without specifying precedence.
  3555. @xref{Token Decl}.
  3556. @item %type
  3557. Bison declaration to declare nonterminals. @xref{Type Decl}.
  3558. @item %union
  3559. Bison declaration to specify several possible data types for semantic
  3560. values. @xref{Union Decl}.
  3561. @end table
  3562. These are the punctuation and delimiters used in Bison input:
  3563. @table @samp
  3564. @item %%
  3565. Delimiter used to separate the grammar rule section from the
  3566. Bison declarations section or the additional C code section.
  3567. @xref{Grammar Layout}.
  3568. @item %@{ %@}
  3569. All code listed between @samp{%@{} and @samp{%@}} is copied directly
  3570. to the output file uninterpreted. Such code forms the ``C
  3571. declarations'' section of the input file. @xref{Grammar Outline}.
  3572. @item /*@dots{}*/
  3573. Comment delimiters, as in C.
  3574. @item :
  3575. Separates a rule's result from its components. @xref{Rules}.
  3576. @item ;
  3577. Terminates a rule. @xref{Rules}.
  3578. @item |
  3579. Separates alternate rules for the same result nonterminal.
  3580. @xref{Rules}.
  3581. @end table
  3582. @node Glossary, Index, Table of Symbols, top
  3583. @appendix Glossary
  3584. @cindex glossary
  3585. @table @asis
  3586. @item Backus-Naur Form (BNF)
  3587. Formal method of specifying context-free grammars. BNF was first used
  3588. in the @cite{ALGOL-60} report, 1963. @xref{Language and Grammar}.
  3589. @item Context-free grammars
  3590. Grammars specified as rules that can be applied regardless of context.
  3591. Thus, if there is a rule which says that an integer can be used as an
  3592. expression, integers are allowed @emph{anywhere} an expression is
  3593. permitted. @xref{Language and Grammar}.
  3594. @item Dynamic allocation
  3595. Allocation of memory that occurs during execution, rather than at
  3596. compile time or on entry to a function.
  3597. @item Empty string
  3598. Analogous to the empty set in set theory, the empty string is a
  3599. character string of length zero.
  3600. @item Finite-state stack machine
  3601. A ``machine'' that has discrete states in which it is said to exist at
  3602. each instant in time. As input to the machine is processed, the
  3603. machine moves from state to state as specified by the logic of the
  3604. machine. In the case of the parser, the input is the language being
  3605. parsed, and the states correspond to various stages in the grammar
  3606. rules. @xref{Algorithm}.
  3607. @item Grouping
  3608. A language construct that is (in general) grammatically divisible;
  3609. for example, `expression' or `declaration' in C. @xref{Language and
  3610. Grammar}.
  3611. @item Infix operator
  3612. An arithmetic operator that is placed between the operands on which it
  3613. performs some operation.
  3614. @item Input stream
  3615. A continuous flow of data between devices or programs.
  3616. @item Language construct
  3617. One of the typical usage schemas of the language. For example, one of
  3618. the constructs of the C language is the @code{if} statement.
  3619. @xref{Language and Grammar}.
  3620. @item Left associativity
  3621. Operators having left associativity are analyzed from left to right:
  3622. @samp{a+b+c} first computes @samp{a+b} and then combines with
  3623. @samp{c}. @xref{Precedence}.
  3624. @item Left recursion
  3625. A rule whose result symbol is also its first component symbol;
  3626. for example, @samp{expseq1 : expseq1 ',' exp;}. @xref{Recursion}.
  3627. @item Left-to-right parsing
  3628. Parsing a sentence of a language by analyzing it token by token from
  3629. left to right. @xref{Algorithm}.
  3630. @item Lexical analyzer (scanner)
  3631. A function that reads an input stream and returns tokens one by one.
  3632. @xref{Lexical}.
  3633. @item Lexical tie-in
  3634. A flag, set by actions in the grammar rules, which alters the way
  3635. tokens are parsed. @xref{Lexical Tie-ins}.
  3636. @item Look-ahead token
  3637. A token already read but not yet shifted. @xref{Look-Ahead}.
  3638. @item LALR(1)
  3639. The class of context-free grammars that Bison (like most other parser
  3640. generators) can handle; a subset of LR(1). @xref{Mystery Conflicts, ,
  3641. Mysterious Reduce/Reduce Conflicts}.
  3642. @item LR(1)
  3643. The class of context-free grammars in which at most one token of
  3644. look-ahead is needed to disambiguate the parsing of any piece of input.
  3645. @item Nonterminal symbol
  3646. A grammar symbol standing for a grammatical construct that can
  3647. be expressed through rules in terms of smaller constructs; in other
  3648. words, a construct that is not a token. @xref{Symbols}.
  3649. @item Parse error
  3650. An error encountered during parsing of an input stream due to invalid
  3651. syntax. @xref{Error Recovery}.
  3652. @item Parser
  3653. A function that recognizes valid sentences of a language by analyzing
  3654. the syntax structure of a set of tokens passed to it from a lexical
  3655. analyzer.
  3656. @item Postfix operator
  3657. An arithmetic operator that is placed after the operands upon which it
  3658. performs some operation.
  3659. @item Reduction
  3660. Replacing a string of nonterminals and/or terminals with a single
  3661. nonterminal, according to a grammar rule. @xref{Algorithm}.
  3662. @item Reentrant
  3663. A reentrant subprogram is a subprogram which can be in invoked any
  3664. number of times in parallel, without interference between the various
  3665. invocations. @xref{Pure Decl}.
  3666. @item Reverse polish notation
  3667. A language in which all operators are postfix operators.
  3668. @item Right recursion
  3669. A rule whose result symbol is also its last component symbol;
  3670. for example, @samp{expseq1: exp ',' expseq1;}. @xref{Recursion}.
  3671. @item Semantics
  3672. In computer languages, the semantics are specified by the actions
  3673. taken for each instance of the language, i.e., the meaning of
  3674. each statement. @xref{Semantics}.
  3675. @item Shift
  3676. A parser is said to shift when it makes the choice of analyzing
  3677. further input from the stream rather than reducing immediately some
  3678. already-recognized rule. @xref{Algorithm}.
  3679. @item Single-character literal
  3680. A single character that is recognized and interpreted as is.
  3681. @xref{Grammar in Bison}.
  3682. @item Start symbol
  3683. The nonterminal symbol that stands for a complete valid utterance in
  3684. the language being parsed. The start symbol is usually listed as the
  3685. first nonterminal symbol in a language specification. @xref{Start
  3686. Decl}.
  3687. @item Symbol table
  3688. A data structure where symbol names and associated data are stored
  3689. during parsing to allow for recognition and use of existing
  3690. information in repeated uses of a symbol. @xref{Multi-function Calc}.
  3691. @item Token
  3692. A basic, grammatically indivisible unit of a language. The symbol
  3693. that describes a token in the grammar is a terminal symbol.
  3694. The input of the Bison parser is a stream of tokens which comes from
  3695. the lexical analyzer. @xref{Symbols}.
  3696. @item Terminal symbol
  3697. A grammar symbol that has no rules in the grammar and therefore
  3698. is grammatically indivisible. The piece of text it represents
  3699. is a token. @xref{Language and Grammar}.
  3700. @end table
  3701. @node Index, , Glossary, top
  3702. @unnumbered Index
  3703. @printindex cp
  3704. @contents
  3705. @bye