]>
Commit | Line | Data |
---|---|---|
1 | \input texinfo @c -*-texinfo-*- | |
2 | @comment %**start of header | |
3 | @setfilename bison.info | |
4 | @settitle Bison 1.25 | |
5 | @setchapternewpage odd | |
6 | ||
7 | @iftex | |
8 | @finalout | |
9 | @end iftex | |
10 | ||
11 | @c SMALL BOOK version | |
12 | @c This edition has been formatted so that you can format and print it in | |
13 | @c the smallbook format. | |
14 | @c @smallbook | |
15 | ||
16 | @c next time, consider using @set for edition number, etc... | |
17 | ||
18 | @c Set following if you have the new `shorttitlepage' command | |
19 | @c @clear shorttitlepage-enabled | |
20 | @c @set shorttitlepage-enabled | |
21 | ||
22 | @c ISPELL CHECK: done, 14 Jan 1993 --bob | |
23 | ||
24 | @c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo | |
25 | @c titlepage; should NOT be changed in the GPL. --mew | |
26 | ||
27 | @iftex | |
28 | @syncodeindex fn cp | |
29 | @syncodeindex vr cp | |
30 | @syncodeindex tp cp | |
31 | @end iftex | |
32 | @ifinfo | |
33 | @synindex fn cp | |
34 | @synindex vr cp | |
35 | @synindex tp cp | |
36 | @end ifinfo | |
37 | @comment %**end of header | |
38 | ||
39 | @ifinfo | |
40 | This file documents the Bison parser generator. | |
41 | ||
42 | Copyright (C) 1988, 89, 90, 91, 92, 93, 1995 Free Software Foundation, Inc. | |
43 | ||
44 | Permission is granted to make and distribute verbatim copies of | |
45 | this manual provided the copyright notice and this permission notice | |
46 | are preserved on all copies. | |
47 | ||
48 | @ignore | |
49 | Permission is granted to process this file through Tex and print the | |
50 | results, provided the printed document carries copying permission | |
51 | notice identical to this one except for the removal of this paragraph | |
52 | (this paragraph not being relevant to the printed manual). | |
53 | ||
54 | @end ignore | |
55 | Permission is granted to copy and distribute modified versions of this | |
56 | manual under the conditions for verbatim copying, provided also that the | |
57 | sections entitled ``GNU General Public License'' and ``Conditions for | |
58 | Using Bison'' are included exactly as in the original, and provided that | |
59 | the entire resulting derived work is distributed under the terms of a | |
60 | permission notice identical to this one. | |
61 | ||
62 | Permission is granted to copy and distribute translations of this manual | |
63 | into another language, under the above conditions for modified versions, | |
64 | except that the sections entitled ``GNU General Public License'', | |
65 | ``Conditions for Using Bison'' and this permission notice may be | |
66 | included in translations approved by the Free Software Foundation | |
67 | instead of in the original English. | |
68 | @end ifinfo | |
69 | ||
70 | @ifset shorttitlepage-enabled | |
71 | @shorttitlepage Bison | |
72 | @end ifset | |
73 | @titlepage | |
74 | @title Bison | |
75 | @subtitle The YACC-compatible Parser Generator | |
76 | @subtitle November 1995, Bison Version 1.25 | |
77 | ||
78 | @author by Charles Donnelly and Richard Stallman | |
79 | ||
80 | @page | |
81 | @vskip 0pt plus 1filll | |
82 | Copyright @copyright{} 1988, 89, 90, 91, 92, 93, 1995 Free Software | |
83 | Foundation | |
84 | ||
85 | @sp 2 | |
86 | Published by the Free Software Foundation @* | |
87 | 59 Temple Place, Suite 330 @* | |
88 | Boston, MA 02111-1307 USA @* | |
89 | Printed copies are available for $15 each.@* | |
90 | ISBN 1-882114-45-0 | |
91 | ||
92 | Permission is granted to make and distribute verbatim copies of | |
93 | this manual provided the copyright notice and this permission notice | |
94 | are preserved on all copies. | |
95 | ||
96 | @ignore | |
97 | Permission is granted to process this file through TeX and print the | |
98 | results, provided the printed document carries copying permission | |
99 | notice identical to this one except for the removal of this paragraph | |
100 | (this paragraph not being relevant to the printed manual). | |
101 | ||
102 | @end ignore | |
103 | Permission is granted to copy and distribute modified versions of this | |
104 | manual under the conditions for verbatim copying, provided also that the | |
105 | sections entitled ``GNU General Public License'' and ``Conditions for | |
106 | Using Bison'' are included exactly as in the original, and provided that | |
107 | the entire resulting derived work is distributed under the terms of a | |
108 | permission notice identical to this one. | |
109 | ||
110 | Permission is granted to copy and distribute translations of this manual | |
111 | into another language, under the above conditions for modified versions, | |
112 | except that the sections entitled ``GNU General Public License'', | |
113 | ``Conditions for Using Bison'' and this permission notice may be | |
114 | included in translations approved by the Free Software Foundation | |
115 | instead of in the original English. | |
116 | @sp 2 | |
117 | Cover art by Etienne Suvasa. | |
118 | @end titlepage | |
119 | @page | |
120 | ||
121 | @node Top, Introduction, (dir), (dir) | |
122 | ||
123 | @ifinfo | |
124 | This manual documents version 1.25 of Bison. | |
125 | @end ifinfo | |
126 | ||
127 | @menu | |
128 | * Introduction:: | |
129 | * Conditions:: | |
130 | * Copying:: The GNU General Public License says | |
131 | how you can copy and share Bison | |
132 | ||
133 | Tutorial sections: | |
134 | * Concepts:: Basic concepts for understanding Bison. | |
135 | * Examples:: Three simple explained examples of using Bison. | |
136 | ||
137 | Reference sections: | |
138 | * Grammar File:: Writing Bison declarations and rules. | |
139 | * Interface:: C-language interface to the parser function @code{yyparse}. | |
140 | * Algorithm:: How the Bison parser works at run-time. | |
141 | * Error Recovery:: Writing rules for error recovery. | |
142 | * Context Dependency:: What to do if your language syntax is too | |
143 | messy for Bison to handle straightforwardly. | |
144 | * Debugging:: Debugging Bison parsers that parse wrong. | |
145 | * Invocation:: How to run Bison (to produce the parser source file). | |
146 | * Table of Symbols:: All the keywords of the Bison language are explained. | |
147 | * Glossary:: Basic concepts are explained. | |
148 | * Index:: Cross-references to the text. | |
149 | ||
150 | --- The Detailed Node Listing --- | |
151 | ||
152 | The Concepts of Bison | |
153 | ||
154 | * Language and Grammar:: Languages and context-free grammars, | |
155 | as mathematical ideas. | |
156 | * Grammar in Bison:: How we represent grammars for Bison's sake. | |
157 | * Semantic Values:: Each token or syntactic grouping can have | |
158 | a semantic value (the value of an integer, | |
159 | the name of an identifier, etc.). | |
160 | * Semantic Actions:: Each rule can have an action containing C code. | |
161 | * Bison Parser:: What are Bison's input and output, | |
162 | how is the output used? | |
163 | * Stages:: Stages in writing and running Bison grammars. | |
164 | * Grammar Layout:: Overall structure of a Bison grammar file. | |
165 | ||
166 | Examples | |
167 | ||
168 | * RPN Calc:: Reverse polish notation calculator; | |
169 | a first example with no operator precedence. | |
170 | * Infix Calc:: Infix (algebraic) notation calculator. | |
171 | Operator precedence is introduced. | |
172 | * Simple Error Recovery:: Continuing after syntax errors. | |
173 | * Multi-function Calc:: Calculator with memory and trig functions. | |
174 | It uses multiple data-types for semantic values. | |
175 | * Exercises:: Ideas for improving the multi-function calculator. | |
176 | ||
177 | Reverse Polish Notation Calculator | |
178 | ||
179 | * Decls: Rpcalc Decls. Bison and C declarations for rpcalc. | |
180 | * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation. | |
181 | * Lexer: Rpcalc Lexer. The lexical analyzer. | |
182 | * Main: Rpcalc Main. The controlling function. | |
183 | * Error: Rpcalc Error. The error reporting function. | |
184 | * Gen: Rpcalc Gen. Running Bison on the grammar file. | |
185 | * Comp: Rpcalc Compile. Run the C compiler on the output code. | |
186 | ||
187 | Grammar Rules for @code{rpcalc} | |
188 | ||
189 | * Rpcalc Input:: | |
190 | * Rpcalc Line:: | |
191 | * Rpcalc Expr:: | |
192 | ||
193 | Multi-Function Calculator: @code{mfcalc} | |
194 | ||
195 | * Decl: Mfcalc Decl. Bison declarations for multi-function calculator. | |
196 | * Rules: Mfcalc Rules. Grammar rules for the calculator. | |
197 | * Symtab: Mfcalc Symtab. Symbol table management subroutines. | |
198 | ||
199 | Bison Grammar Files | |
200 | ||
201 | * Grammar Outline:: Overall layout of the grammar file. | |
202 | * Symbols:: Terminal and nonterminal symbols. | |
203 | * Rules:: How to write grammar rules. | |
204 | * Recursion:: Writing recursive rules. | |
205 | * Semantics:: Semantic values and actions. | |
206 | * Declarations:: All kinds of Bison declarations are described here. | |
207 | * Multiple Parsers:: Putting more than one Bison parser in one program. | |
208 | ||
209 | Outline of a Bison Grammar | |
210 | ||
211 | * C Declarations:: Syntax and usage of the C declarations section. | |
212 | * Bison Declarations:: Syntax and usage of the Bison declarations section. | |
213 | * Grammar Rules:: Syntax and usage of the grammar rules section. | |
214 | * C Code:: Syntax and usage of the additional C code section. | |
215 | ||
216 | Defining Language Semantics | |
217 | ||
218 | * Value Type:: Specifying one data type for all semantic values. | |
219 | * Multiple Types:: Specifying several alternative data types. | |
220 | * Actions:: An action is the semantic definition of a grammar rule. | |
221 | * Action Types:: Specifying data types for actions to operate on. | |
222 | * Mid-Rule Actions:: Most actions go at the end of a rule. | |
223 | This says when, why and how to use the exceptional | |
224 | action in the middle of a rule. | |
225 | ||
226 | Bison Declarations | |
227 | ||
228 | * Token Decl:: Declaring terminal symbols. | |
229 | * Precedence Decl:: Declaring terminals with precedence and associativity. | |
230 | * Union Decl:: Declaring the set of all semantic value types. | |
231 | * Type Decl:: Declaring the choice of type for a nonterminal symbol. | |
232 | * Expect Decl:: Suppressing warnings about shift/reduce conflicts. | |
233 | * Start Decl:: Specifying the start symbol. | |
234 | * Pure Decl:: Requesting a reentrant parser. | |
235 | * Decl Summary:: Table of all Bison declarations. | |
236 | ||
237 | Parser C-Language Interface | |
238 | ||
239 | * Parser Function:: How to call @code{yyparse} and what it returns. | |
240 | * Lexical:: You must supply a function @code{yylex} | |
241 | which reads tokens. | |
242 | * Error Reporting:: You must supply a function @code{yyerror}. | |
243 | * Action Features:: Special features for use in actions. | |
244 | ||
245 | The Lexical Analyzer Function @code{yylex} | |
246 | ||
247 | * Calling Convention:: How @code{yyparse} calls @code{yylex}. | |
248 | * Token Values:: How @code{yylex} must return the semantic value | |
249 | of the token it has read. | |
250 | * Token Positions:: How @code{yylex} must return the text position | |
251 | (line number, etc.) of the token, if the | |
252 | actions want that. | |
253 | * Pure Calling:: How the calling convention differs | |
254 | in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}). | |
255 | ||
256 | The Bison Parser Algorithm | |
257 | ||
258 | * Look-Ahead:: Parser looks one token ahead when deciding what to do. | |
259 | * Shift/Reduce:: Conflicts: when either shifting or reduction is valid. | |
260 | * Precedence:: Operator precedence works by resolving conflicts. | |
261 | * Contextual Precedence:: When an operator's precedence depends on context. | |
262 | * Parser States:: The parser is a finite-state-machine with stack. | |
263 | * Reduce/Reduce:: When two rules are applicable in the same situation. | |
264 | * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified. | |
265 | * Stack Overflow:: What happens when stack gets full. How to avoid it. | |
266 | ||
267 | Operator Precedence | |
268 | ||
269 | * Why Precedence:: An example showing why precedence is needed. | |
270 | * Using Precedence:: How to specify precedence in Bison grammars. | |
271 | * Precedence Examples:: How these features are used in the previous example. | |
272 | * How Precedence:: How they work. | |
273 | ||
274 | Handling Context Dependencies | |
275 | ||
276 | * Semantic Tokens:: Token parsing can depend on the semantic context. | |
277 | * Lexical Tie-ins:: Token parsing can depend on the syntactic context. | |
278 | * Tie-in Recovery:: Lexical tie-ins have implications for how | |
279 | error recovery rules must be written. | |
280 | ||
281 | Invoking Bison | |
282 | ||
283 | * Bison Options:: All the options described in detail, | |
284 | in alphabetical order by short options. | |
285 | * Option Cross Key:: Alphabetical list of long options. | |
286 | * VMS Invocation:: Bison command syntax on VMS. | |
287 | @end menu | |
288 | ||
289 | @node Introduction, Conditions, Top, Top | |
290 | @unnumbered Introduction | |
291 | @cindex introduction | |
292 | ||
293 | @dfn{Bison} is a general-purpose parser generator that converts a | |
294 | grammar description for an LALR(1) context-free grammar into a C | |
295 | program to parse that grammar. Once you are proficient with Bison, | |
296 | you may use it to develop a wide range of language parsers, from those | |
297 | used in simple desk calculators to complex programming languages. | |
298 | ||
299 | Bison is upward compatible with Yacc: all properly-written Yacc grammars | |
300 | ought to work with Bison with no change. Anyone familiar with Yacc | |
301 | should be able to use Bison with little trouble. You need to be fluent in | |
302 | C programming in order to use Bison or to understand this manual. | |
303 | ||
304 | We begin with tutorial chapters that explain the basic concepts of using | |
305 | Bison and show three explained examples, each building on the last. If you | |
306 | don't know Bison or Yacc, start by reading these chapters. Reference | |
307 | chapters follow which describe specific aspects of Bison in detail. | |
308 | ||
309 | Bison was written primarily by Robert Corbett; Richard Stallman made it | |
310 | Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added | |
311 | multicharacter string literals and other features. | |
312 | ||
313 | This edition corresponds to version 1.25 of Bison. | |
314 | ||
315 | @node Conditions, Copying, Introduction, Top | |
316 | @unnumbered Conditions for Using Bison | |
317 | ||
318 | As of Bison version 1.24, we have changed the distribution terms for | |
319 | @code{yyparse} to permit using Bison's output in non-free programs. | |
320 | Formerly, Bison parsers could be used only in programs that were free | |
321 | software. | |
322 | ||
323 | The other GNU programming tools, such as the GNU C compiler, have never | |
324 | had such a requirement. They could always be used for non-free | |
325 | software. The reason Bison was different was not due to a special | |
326 | policy decision; it resulted from applying the usual General Public | |
327 | License to all of the Bison source code. | |
328 | ||
329 | The output of the Bison utility---the Bison parser file---contains a | |
330 | verbatim copy of a sizable piece of Bison, which is the code for the | |
331 | @code{yyparse} function. (The actions from your grammar are inserted | |
332 | into this function at one point, but the rest of the function is not | |
333 | changed.) When we applied the GPL terms to the code for @code{yyparse}, | |
334 | the effect was to restrict the use of Bison output to free software. | |
335 | ||
336 | We didn't change the terms because of sympathy for people who want to | |
337 | make software proprietary. @strong{Software should be free.} But we | |
338 | concluded that limiting Bison's use to free software was doing little to | |
339 | encourage people to make other software free. So we decided to make the | |
340 | practical conditions for using Bison match the practical conditions for | |
341 | using the other GNU tools. | |
342 | ||
343 | @node Copying, Concepts, Conditions, Top | |
344 | @unnumbered GNU GENERAL PUBLIC LICENSE | |
345 | @center Version 2, June 1991 | |
346 | ||
347 | @display | |
348 | Copyright @copyright{} 1989, 1991 Free Software Foundation, Inc. | |
349 | 675 Mass Ave, Cambridge, MA 02139, USA | |
350 | ||
351 | Everyone is permitted to copy and distribute verbatim copies | |
352 | of this license document, but changing it is not allowed. | |
353 | @end display | |
354 | ||
355 | @unnumberedsec Preamble | |
356 | ||
357 | The licenses for most software are designed to take away your | |
358 | freedom to share and change it. By contrast, the GNU General Public | |
359 | License is intended to guarantee your freedom to share and change free | |
360 | software---to make sure the software is free for all its users. This | |
361 | General Public License applies to most of the Free Software | |
362 | Foundation's software and to any other program whose authors commit to | |
363 | using it. (Some other Free Software Foundation software is covered by | |
364 | the GNU Library General Public License instead.) You can apply it to | |
365 | your programs, too. | |
366 | ||
367 | When we speak of free software, we are referring to freedom, not | |
368 | price. Our General Public Licenses are designed to make sure that you | |
369 | have the freedom to distribute copies of free software (and charge for | |
370 | this service if you wish), that you receive source code or can get it | |
371 | if you want it, that you can change the software or use pieces of it | |
372 | in new free programs; and that you know you can do these things. | |
373 | ||
374 | To protect your rights, we need to make restrictions that forbid | |
375 | anyone to deny you these rights or to ask you to surrender the rights. | |
376 | These restrictions translate to certain responsibilities for you if you | |
377 | distribute copies of the software, or if you modify it. | |
378 | ||
379 | For example, if you distribute copies of such a program, whether | |
380 | gratis or for a fee, you must give the recipients all the rights that | |
381 | you have. You must make sure that they, too, receive or can get the | |
382 | source code. And you must show them these terms so they know their | |
383 | rights. | |
384 | ||
385 | We protect your rights with two steps: (1) copyright the software, and | |
386 | (2) offer you this license which gives you legal permission to copy, | |
387 | distribute and/or modify the software. | |
388 | ||
389 | Also, for each author's protection and ours, we want to make certain | |
390 | that everyone understands that there is no warranty for this free | |
391 | software. If the software is modified by someone else and passed on, we | |
392 | want its recipients to know that what they have is not the original, so | |
393 | that any problems introduced by others will not reflect on the original | |
394 | authors' reputations. | |
395 | ||
396 | Finally, any free program is threatened constantly by software | |
397 | patents. We wish to avoid the danger that redistributors of a free | |
398 | program will individually obtain patent licenses, in effect making the | |
399 | program proprietary. To prevent this, we have made it clear that any | |
400 | patent must be licensed for everyone's free use or not licensed at all. | |
401 | ||
402 | The precise terms and conditions for copying, distribution and | |
403 | modification follow. | |
404 | ||
405 | @iftex | |
406 | @unnumberedsec TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
407 | @end iftex | |
408 | @ifinfo | |
409 | @center TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
410 | @end ifinfo | |
411 | ||
412 | @enumerate 0 | |
413 | @item | |
414 | This License applies to any program or other work which contains | |
415 | a notice placed by the copyright holder saying it may be distributed | |
416 | under the terms of this General Public License. The ``Program'', below, | |
417 | refers to any such program or work, and a ``work based on the Program'' | |
418 | means either the Program or any derivative work under copyright law: | |
419 | that is to say, a work containing the Program or a portion of it, | |
420 | either verbatim or with modifications and/or translated into another | |
421 | language. (Hereinafter, translation is included without limitation in | |
422 | the term ``modification''.) Each licensee is addressed as ``you''. | |
423 | ||
424 | Activities other than copying, distribution and modification are not | |
425 | covered by this License; they are outside its scope. The act of | |
426 | running the Program is not restricted, and the output from the Program | |
427 | is covered only if its contents constitute a work based on the | |
428 | Program (independent of having been made by running the Program). | |
429 | Whether that is true depends on what the Program does. | |
430 | ||
431 | @item | |
432 | You may copy and distribute verbatim copies of the Program's | |
433 | source code as you receive it, in any medium, provided that you | |
434 | conspicuously and appropriately publish on each copy an appropriate | |
435 | copyright notice and disclaimer of warranty; keep intact all the | |
436 | notices that refer to this License and to the absence of any warranty; | |
437 | and give any other recipients of the Program a copy of this License | |
438 | along with the Program. | |
439 | ||
440 | You may charge a fee for the physical act of transferring a copy, and | |
441 | you may at your option offer warranty protection in exchange for a fee. | |
442 | ||
443 | @item | |
444 | You may modify your copy or copies of the Program or any portion | |
445 | of it, thus forming a work based on the Program, and copy and | |
446 | distribute such modifications or work under the terms of Section 1 | |
447 | above, provided that you also meet all of these conditions: | |
448 | ||
449 | @enumerate a | |
450 | @item | |
451 | You must cause the modified files to carry prominent notices | |
452 | stating that you changed the files and the date of any change. | |
453 | ||
454 | @item | |
455 | You must cause any work that you distribute or publish, that in | |
456 | whole or in part contains or is derived from the Program or any | |
457 | part thereof, to be licensed as a whole at no charge to all third | |
458 | parties under the terms of this License. | |
459 | ||
460 | @item | |
461 | If the modified program normally reads commands interactively | |
462 | when run, you must cause it, when started running for such | |
463 | interactive use in the most ordinary way, to print or display an | |
464 | announcement including an appropriate copyright notice and a | |
465 | notice that there is no warranty (or else, saying that you provide | |
466 | a warranty) and that users may redistribute the program under | |
467 | these conditions, and telling the user how to view a copy of this | |
468 | License. (Exception: if the Program itself is interactive but | |
469 | does not normally print such an announcement, your work based on | |
470 | the Program is not required to print an announcement.) | |
471 | @end enumerate | |
472 | ||
473 | These requirements apply to the modified work as a whole. If | |
474 | identifiable sections of that work are not derived from the Program, | |
475 | and can be reasonably considered independent and separate works in | |
476 | themselves, then this License, and its terms, do not apply to those | |
477 | sections when you distribute them as separate works. But when you | |
478 | distribute the same sections as part of a whole which is a work based | |
479 | on the Program, the distribution of the whole must be on the terms of | |
480 | this License, whose permissions for other licensees extend to the | |
481 | entire whole, and thus to each and every part regardless of who wrote it. | |
482 | ||
483 | Thus, it is not the intent of this section to claim rights or contest | |
484 | your rights to work written entirely by you; rather, the intent is to | |
485 | exercise the right to control the distribution of derivative or | |
486 | collective works based on the Program. | |
487 | ||
488 | In addition, mere aggregation of another work not based on the Program | |
489 | with the Program (or with a work based on the Program) on a volume of | |
490 | a storage or distribution medium does not bring the other work under | |
491 | the scope of this License. | |
492 | ||
493 | @item | |
494 | You may copy and distribute the Program (or a work based on it, | |
495 | under Section 2) in object code or executable form under the terms of | |
496 | Sections 1 and 2 above provided that you also do one of the following: | |
497 | ||
498 | @enumerate a | |
499 | @item | |
500 | Accompany it with the complete corresponding machine-readable | |
501 | source code, which must be distributed under the terms of Sections | |
502 | 1 and 2 above on a medium customarily used for software interchange; or, | |
503 | ||
504 | @item | |
505 | Accompany it with a written offer, valid for at least three | |
506 | years, to give any third party, for a charge no more than your | |
507 | cost of physically performing source distribution, a complete | |
508 | machine-readable copy of the corresponding source code, to be | |
509 | distributed under the terms of Sections 1 and 2 above on a medium | |
510 | customarily used for software interchange; or, | |
511 | ||
512 | @item | |
513 | Accompany it with the information you received as to the offer | |
514 | to distribute corresponding source code. (This alternative is | |
515 | allowed only for noncommercial distribution and only if you | |
516 | received the program in object code or executable form with such | |
517 | an offer, in accord with Subsection b above.) | |
518 | @end enumerate | |
519 | ||
520 | The source code for a work means the preferred form of the work for | |
521 | making modifications to it. For an executable work, complete source | |
522 | code means all the source code for all modules it contains, plus any | |
523 | associated interface definition files, plus the scripts used to | |
524 | control compilation and installation of the executable. However, as a | |
525 | special exception, the source code distributed need not include | |
526 | anything that is normally distributed (in either source or binary | |
527 | form) with the major components (compiler, kernel, and so on) of the | |
528 | operating system on which the executable runs, unless that component | |
529 | itself accompanies the executable. | |
530 | ||
531 | If distribution of executable or object code is made by offering | |
532 | access to copy from a designated place, then offering equivalent | |
533 | access to copy the source code from the same place counts as | |
534 | distribution of the source code, even though third parties are not | |
535 | compelled to copy the source along with the object code. | |
536 | ||
537 | @item | |
538 | You may not copy, modify, sublicense, or distribute the Program | |
539 | except as expressly provided under this License. Any attempt | |
540 | otherwise to copy, modify, sublicense or distribute the Program is | |
541 | void, and will automatically terminate your rights under this License. | |
542 | However, parties who have received copies, or rights, from you under | |
543 | this License will not have their licenses terminated so long as such | |
544 | parties remain in full compliance. | |
545 | ||
546 | @item | |
547 | You are not required to accept this License, since you have not | |
548 | signed it. However, nothing else grants you permission to modify or | |
549 | distribute the Program or its derivative works. These actions are | |
550 | prohibited by law if you do not accept this License. Therefore, by | |
551 | modifying or distributing the Program (or any work based on the | |
552 | Program), you indicate your acceptance of this License to do so, and | |
553 | all its terms and conditions for copying, distributing or modifying | |
554 | the Program or works based on it. | |
555 | ||
556 | @item | |
557 | Each time you redistribute the Program (or any work based on the | |
558 | Program), the recipient automatically receives a license from the | |
559 | original licensor to copy, distribute or modify the Program subject to | |
560 | these terms and conditions. You may not impose any further | |
561 | restrictions on the recipients' exercise of the rights granted herein. | |
562 | You are not responsible for enforcing compliance by third parties to | |
563 | this License. | |
564 | ||
565 | @item | |
566 | If, as a consequence of a court judgment or allegation of patent | |
567 | infringement or for any other reason (not limited to patent issues), | |
568 | conditions are imposed on you (whether by court order, agreement or | |
569 | otherwise) that contradict the conditions of this License, they do not | |
570 | excuse you from the conditions of this License. If you cannot | |
571 | distribute so as to satisfy simultaneously your obligations under this | |
572 | License and any other pertinent obligations, then as a consequence you | |
573 | may not distribute the Program at all. For example, if a patent | |
574 | license would not permit royalty-free redistribution of the Program by | |
575 | all those who receive copies directly or indirectly through you, then | |
576 | the only way you could satisfy both it and this License would be to | |
577 | refrain entirely from distribution of the Program. | |
578 | ||
579 | If any portion of this section is held invalid or unenforceable under | |
580 | any particular circumstance, the balance of the section is intended to | |
581 | apply and the section as a whole is intended to apply in other | |
582 | circumstances. | |
583 | ||
584 | It is not the purpose of this section to induce you to infringe any | |
585 | patents or other property right claims or to contest validity of any | |
586 | such claims; this section has the sole purpose of protecting the | |
587 | integrity of the free software distribution system, which is | |
588 | implemented by public license practices. Many people have made | |
589 | generous contributions to the wide range of software distributed | |
590 | through that system in reliance on consistent application of that | |
591 | system; it is up to the author/donor to decide if he or she is willing | |
592 | to distribute software through any other system and a licensee cannot | |
593 | impose that choice. | |
594 | ||
595 | This section is intended to make thoroughly clear what is believed to | |
596 | be a consequence of the rest of this License. | |
597 | ||
598 | @item | |
599 | If the distribution and/or use of the Program is restricted in | |
600 | certain countries either by patents or by copyrighted interfaces, the | |
601 | original copyright holder who places the Program under this License | |
602 | may add an explicit geographical distribution limitation excluding | |
603 | those countries, so that distribution is permitted only in or among | |
604 | countries not thus excluded. In such case, this License incorporates | |
605 | the limitation as if written in the body of this License. | |
606 | ||
607 | @item | |
608 | The Free Software Foundation may publish revised and/or new versions | |
609 | of the General Public License from time to time. Such new versions will | |
610 | be similar in spirit to the present version, but may differ in detail to | |
611 | address new problems or concerns. | |
612 | ||
613 | Each version is given a distinguishing version number. If the Program | |
614 | specifies a version number of this License which applies to it and ``any | |
615 | later version'', you have the option of following the terms and conditions | |
616 | either of that version or of any later version published by the Free | |
617 | Software Foundation. If the Program does not specify a version number of | |
618 | this License, you may choose any version ever published by the Free Software | |
619 | Foundation. | |
620 | ||
621 | @item | |
622 | If you wish to incorporate parts of the Program into other free | |
623 | programs whose distribution conditions are different, write to the author | |
624 | to ask for permission. For software which is copyrighted by the Free | |
625 | Software Foundation, write to the Free Software Foundation; we sometimes | |
626 | make exceptions for this. Our decision will be guided by the two goals | |
627 | of preserving the free status of all derivatives of our free software and | |
628 | of promoting the sharing and reuse of software generally. | |
629 | ||
630 | @iftex | |
631 | @heading NO WARRANTY | |
632 | @end iftex | |
633 | @ifinfo | |
634 | @center NO WARRANTY | |
635 | @end ifinfo | |
636 | ||
637 | @item | |
638 | BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY | |
639 | FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN | |
640 | OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES | |
641 | PROVIDE THE PROGRAM ``AS IS'' WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED | |
642 | OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF | |
643 | MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS | |
644 | TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE | |
645 | PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, | |
646 | REPAIR OR CORRECTION. | |
647 | ||
648 | @item | |
649 | IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING | |
650 | WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR | |
651 | REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, | |
652 | INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING | |
653 | OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED | |
654 | TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY | |
655 | YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER | |
656 | PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE | |
657 | POSSIBILITY OF SUCH DAMAGES. | |
658 | @end enumerate | |
659 | ||
660 | @iftex | |
661 | @heading END OF TERMS AND CONDITIONS | |
662 | @end iftex | |
663 | @ifinfo | |
664 | @center END OF TERMS AND CONDITIONS | |
665 | @end ifinfo | |
666 | ||
667 | @page | |
668 | @unnumberedsec How to Apply These Terms to Your New Programs | |
669 | ||
670 | If you develop a new program, and you want it to be of the greatest | |
671 | possible use to the public, the best way to achieve this is to make it | |
672 | free software which everyone can redistribute and change under these terms. | |
673 | ||
674 | To do so, attach the following notices to the program. It is safest | |
675 | to attach them to the start of each source file to most effectively | |
676 | convey the exclusion of warranty; and each file should have at least | |
677 | the ``copyright'' line and a pointer to where the full notice is found. | |
678 | ||
679 | @smallexample | |
680 | @var{one line to give the program's name and a brief idea of what it does.} | |
681 | Copyright (C) 19@var{yy} @var{name of author} | |
682 | ||
683 | This program is free software; you can redistribute it and/or modify | |
684 | it under the terms of the GNU General Public License as published by | |
685 | the Free Software Foundation; either version 2 of the License, or | |
686 | (at your option) any later version. | |
687 | ||
688 | This program is distributed in the hope that it will be useful, | |
689 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
690 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
691 | GNU General Public License for more details. | |
692 | ||
693 | You should have received a copy of the GNU General Public License | |
694 | along with this program; if not, write to the Free Software | |
695 | Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
696 | @end smallexample | |
697 | ||
698 | Also add information on how to contact you by electronic and paper mail. | |
699 | ||
700 | If the program is interactive, make it output a short notice like this | |
701 | when it starts in an interactive mode: | |
702 | ||
703 | @smallexample | |
704 | Gnomovision version 69, Copyright (C) 19@var{yy} @var{name of author} | |
705 | Gnomovision comes with ABSOLUTELY NO WARRANTY; for details | |
706 | type `show w'. | |
707 | This is free software, and you are welcome to redistribute it | |
708 | under certain conditions; type `show c' for details. | |
709 | @end smallexample | |
710 | ||
711 | The hypothetical commands @samp{show w} and @samp{show c} should show | |
712 | the appropriate parts of the General Public License. Of course, the | |
713 | commands you use may be called something other than @samp{show w} and | |
714 | @samp{show c}; they could even be mouse-clicks or menu items---whatever | |
715 | suits your program. | |
716 | ||
717 | You should also get your employer (if you work as a programmer) or your | |
718 | school, if any, to sign a ``copyright disclaimer'' for the program, if | |
719 | necessary. Here is a sample; alter the names: | |
720 | ||
721 | @smallexample | |
722 | Yoyodyne, Inc., hereby disclaims all copyright interest in the program | |
723 | `Gnomovision' (which makes passes at compilers) written by James Hacker. | |
724 | ||
725 | @var{signature of Ty Coon}, 1 April 1989 | |
726 | Ty Coon, President of Vice | |
727 | @end smallexample | |
728 | ||
729 | This General Public License does not permit incorporating your program into | |
730 | proprietary programs. If your program is a subroutine library, you may | |
731 | consider it more useful to permit linking proprietary applications with the | |
732 | library. If this is what you want to do, use the GNU Library General | |
733 | Public License instead of this License. | |
734 | ||
735 | @node Concepts, Examples, Copying, Top | |
736 | @chapter The Concepts of Bison | |
737 | ||
738 | This chapter introduces many of the basic concepts without which the | |
739 | details of Bison will not make sense. If you do not already know how to | |
740 | use Bison or Yacc, we suggest you start by reading this chapter carefully. | |
741 | ||
742 | @menu | |
743 | * Language and Grammar:: Languages and context-free grammars, | |
744 | as mathematical ideas. | |
745 | * Grammar in Bison:: How we represent grammars for Bison's sake. | |
746 | * Semantic Values:: Each token or syntactic grouping can have | |
747 | a semantic value (the value of an integer, | |
748 | the name of an identifier, etc.). | |
749 | * Semantic Actions:: Each rule can have an action containing C code. | |
750 | * Bison Parser:: What are Bison's input and output, | |
751 | how is the output used? | |
752 | * Stages:: Stages in writing and running Bison grammars. | |
753 | * Grammar Layout:: Overall structure of a Bison grammar file. | |
754 | @end menu | |
755 | ||
756 | @node Language and Grammar, Grammar in Bison, , Concepts | |
757 | @section Languages and Context-Free Grammars | |
758 | ||
759 | @cindex context-free grammar | |
760 | @cindex grammar, context-free | |
761 | In order for Bison to parse a language, it must be described by a | |
762 | @dfn{context-free grammar}. This means that you specify one or more | |
763 | @dfn{syntactic groupings} and give rules for constructing them from their | |
764 | parts. For example, in the C language, one kind of grouping is called an | |
765 | `expression'. One rule for making an expression might be, ``An expression | |
766 | can be made of a minus sign and another expression''. Another would be, | |
767 | ``An expression can be an integer''. As you can see, rules are often | |
768 | recursive, but there must be at least one rule which leads out of the | |
769 | recursion. | |
770 | ||
771 | @cindex BNF | |
772 | @cindex Backus-Naur form | |
773 | The most common formal system for presenting such rules for humans to read | |
774 | is @dfn{Backus-Naur Form} or ``BNF'', which was developed in order to | |
775 | specify the language Algol 60. Any grammar expressed in BNF is a | |
776 | context-free grammar. The input to Bison is essentially machine-readable | |
777 | BNF. | |
778 | ||
779 | Not all context-free languages can be handled by Bison, only those | |
780 | that are LALR(1). In brief, this means that it must be possible to | |
781 | tell how to parse any portion of an input string with just a single | |
782 | token of look-ahead. Strictly speaking, that is a description of an | |
783 | LR(1) grammar, and LALR(1) involves additional restrictions that are | |
784 | hard to explain simply; but it is rare in actual practice to find an | |
785 | LR(1) grammar that fails to be LALR(1). @xref{Mystery Conflicts, , | |
786 | Mysterious Reduce/Reduce Conflicts}, for more information on this. | |
787 | ||
788 | @cindex symbols (abstract) | |
789 | @cindex token | |
790 | @cindex syntactic grouping | |
791 | @cindex grouping, syntactic | |
792 | In the formal grammatical rules for a language, each kind of syntactic unit | |
793 | or grouping is named by a @dfn{symbol}. Those which are built by grouping | |
794 | smaller constructs according to grammatical rules are called | |
795 | @dfn{nonterminal symbols}; those which can't be subdivided are called | |
796 | @dfn{terminal symbols} or @dfn{token types}. We call a piece of input | |
797 | corresponding to a single terminal symbol a @dfn{token}, and a piece | |
798 | corresponding to a single nonterminal symbol a @dfn{grouping}.@refill | |
799 | ||
800 | We can use the C language as an example of what symbols, terminal and | |
801 | nonterminal, mean. The tokens of C are identifiers, constants (numeric and | |
802 | string), and the various keywords, arithmetic operators and punctuation | |
803 | marks. So the terminal symbols of a grammar for C include `identifier', | |
804 | `number', `string', plus one symbol for each keyword, operator or | |
805 | punctuation mark: `if', `return', `const', `static', `int', `char', | |
806 | `plus-sign', `open-brace', `close-brace', `comma' and many more. (These | |
807 | tokens can be subdivided into characters, but that is a matter of | |
808 | lexicography, not grammar.) | |
809 | ||
810 | Here is a simple C function subdivided into tokens: | |
811 | ||
812 | @example | |
813 | int /* @r{keyword `int'} */ | |
814 | square (x) /* @r{identifier, open-paren,} */ | |
815 | /* @r{identifier, close-paren} */ | |
816 | int x; /* @r{keyword `int', identifier, semicolon} */ | |
817 | @{ /* @r{open-brace} */ | |
818 | return x * x; /* @r{keyword `return', identifier,} */ | |
819 | /* @r{asterisk, identifier, semicolon} */ | |
820 | @} /* @r{close-brace} */ | |
821 | @end example | |
822 | ||
823 | The syntactic groupings of C include the expression, the statement, the | |
824 | declaration, and the function definition. These are represented in the | |
825 | grammar of C by nonterminal symbols `expression', `statement', | |
826 | `declaration' and `function definition'. The full grammar uses dozens of | |
827 | additional language constructs, each with its own nonterminal symbol, in | |
828 | order to express the meanings of these four. The example above is a | |
829 | function definition; it contains one declaration, and one statement. In | |
830 | the statement, each @samp{x} is an expression and so is @samp{x * x}. | |
831 | ||
832 | Each nonterminal symbol must have grammatical rules showing how it is made | |
833 | out of simpler constructs. For example, one kind of C statement is the | |
834 | @code{return} statement; this would be described with a grammar rule which | |
835 | reads informally as follows: | |
836 | ||
837 | @quotation | |
838 | A `statement' can be made of a `return' keyword, an `expression' and a | |
839 | `semicolon'. | |
840 | @end quotation | |
841 | ||
842 | @noindent | |
843 | There would be many other rules for `statement', one for each kind of | |
844 | statement in C. | |
845 | ||
846 | @cindex start symbol | |
847 | One nonterminal symbol must be distinguished as the special one which | |
848 | defines a complete utterance in the language. It is called the @dfn{start | |
849 | symbol}. In a compiler, this means a complete input program. In the C | |
850 | language, the nonterminal symbol `sequence of definitions and declarations' | |
851 | plays this role. | |
852 | ||
853 | For example, @samp{1 + 2} is a valid C expression---a valid part of a C | |
854 | program---but it is not valid as an @emph{entire} C program. In the | |
855 | context-free grammar of C, this follows from the fact that `expression' is | |
856 | not the start symbol. | |
857 | ||
858 | The Bison parser reads a sequence of tokens as its input, and groups the | |
859 | tokens using the grammar rules. If the input is valid, the end result is | |
860 | that the entire token sequence reduces to a single grouping whose symbol is | |
861 | the grammar's start symbol. If we use a grammar for C, the entire input | |
862 | must be a `sequence of definitions and declarations'. If not, the parser | |
863 | reports a syntax error. | |
864 | ||
865 | @node Grammar in Bison, Semantic Values, Language and Grammar, Concepts | |
866 | @section From Formal Rules to Bison Input | |
867 | @cindex Bison grammar | |
868 | @cindex grammar, Bison | |
869 | @cindex formal grammar | |
870 | ||
871 | A formal grammar is a mathematical construct. To define the language | |
872 | for Bison, you must write a file expressing the grammar in Bison syntax: | |
873 | a @dfn{Bison grammar} file. @xref{Grammar File, ,Bison Grammar Files}. | |
874 | ||
875 | A nonterminal symbol in the formal grammar is represented in Bison input | |
876 | as an identifier, like an identifier in C. By convention, it should be | |
877 | in lower case, such as @code{expr}, @code{stmt} or @code{declaration}. | |
878 | ||
879 | The Bison representation for a terminal symbol is also called a @dfn{token | |
880 | type}. Token types as well can be represented as C-like identifiers. By | |
881 | convention, these identifiers should be upper case to distinguish them from | |
882 | nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or | |
883 | @code{RETURN}. A terminal symbol that stands for a particular keyword in | |
884 | the language should be named after that keyword converted to upper case. | |
885 | The terminal symbol @code{error} is reserved for error recovery. | |
886 | @xref{Symbols}. | |
887 | ||
888 | A terminal symbol can also be represented as a character literal, just like | |
889 | a C character constant. You should do this whenever a token is just a | |
890 | single character (parenthesis, plus-sign, etc.): use that same character in | |
891 | a literal as the terminal symbol for that token. | |
892 | ||
893 | A third way to represent a terminal symbol is with a C string constant | |
894 | containing several characters. @xref{Symbols}, for more information. | |
895 | ||
896 | The grammar rules also have an expression in Bison syntax. For example, | |
897 | here is the Bison rule for a C @code{return} statement. The semicolon in | |
898 | quotes is a literal character token, representing part of the C syntax for | |
899 | the statement; the naked semicolon, and the colon, are Bison punctuation | |
900 | used in every rule. | |
901 | ||
902 | @example | |
903 | stmt: RETURN expr ';' | |
904 | ; | |
905 | @end example | |
906 | ||
907 | @noindent | |
908 | @xref{Rules, ,Syntax of Grammar Rules}. | |
909 | ||
910 | @node Semantic Values, Semantic Actions, Grammar in Bison, Concepts | |
911 | @section Semantic Values | |
912 | @cindex semantic value | |
913 | @cindex value, semantic | |
914 | ||
915 | A formal grammar selects tokens only by their classifications: for example, | |
916 | if a rule mentions the terminal symbol `integer constant', it means that | |
917 | @emph{any} integer constant is grammatically valid in that position. The | |
918 | precise value of the constant is irrelevant to how to parse the input: if | |
919 | @samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally | |
920 | grammatical.@refill | |
921 | ||
922 | But the precise value is very important for what the input means once it is | |
923 | parsed. A compiler is useless if it fails to distinguish between 4, 1 and | |
924 | 3989 as constants in the program! Therefore, each token in a Bison grammar | |
925 | has both a token type and a @dfn{semantic value}. @xref{Semantics, ,Defining Language Semantics}, | |
926 | for details. | |
927 | ||
928 | The token type is a terminal symbol defined in the grammar, such as | |
929 | @code{INTEGER}, @code{IDENTIFIER} or @code{','}. It tells everything | |
930 | you need to know to decide where the token may validly appear and how to | |
931 | group it with other tokens. The grammar rules know nothing about tokens | |
932 | except their types.@refill | |
933 | ||
934 | The semantic value has all the rest of the information about the | |
935 | meaning of the token, such as the value of an integer, or the name of an | |
936 | identifier. (A token such as @code{','} which is just punctuation doesn't | |
937 | need to have any semantic value.) | |
938 | ||
939 | For example, an input token might be classified as token type | |
940 | @code{INTEGER} and have the semantic value 4. Another input token might | |
941 | have the same token type @code{INTEGER} but value 3989. When a grammar | |
942 | rule says that @code{INTEGER} is allowed, either of these tokens is | |
943 | acceptable because each is an @code{INTEGER}. When the parser accepts the | |
944 | token, it keeps track of the token's semantic value. | |
945 | ||
946 | Each grouping can also have a semantic value as well as its nonterminal | |
947 | symbol. For example, in a calculator, an expression typically has a | |
948 | semantic value that is a number. In a compiler for a programming | |
949 | language, an expression typically has a semantic value that is a tree | |
950 | structure describing the meaning of the expression. | |
951 | ||
952 | @node Semantic Actions, Bison Parser, Semantic Values, Concepts | |
953 | @section Semantic Actions | |
954 | @cindex semantic actions | |
955 | @cindex actions, semantic | |
956 | ||
957 | In order to be useful, a program must do more than parse input; it must | |
958 | also produce some output based on the input. In a Bison grammar, a grammar | |
959 | rule can have an @dfn{action} made up of C statements. Each time the | |
960 | parser recognizes a match for that rule, the action is executed. | |
961 | @xref{Actions}. | |
962 | ||
963 | Most of the time, the purpose of an action is to compute the semantic value | |
964 | of the whole construct from the semantic values of its parts. For example, | |
965 | suppose we have a rule which says an expression can be the sum of two | |
966 | expressions. When the parser recognizes such a sum, each of the | |
967 | subexpressions has a semantic value which describes how it was built up. | |
968 | The action for this rule should create a similar sort of value for the | |
969 | newly recognized larger expression. | |
970 | ||
971 | For example, here is a rule that says an expression can be the sum of | |
972 | two subexpressions: | |
973 | ||
974 | @example | |
975 | expr: expr '+' expr @{ $$ = $1 + $3; @} | |
976 | ; | |
977 | @end example | |
978 | ||
979 | @noindent | |
980 | The action says how to produce the semantic value of the sum expression | |
981 | from the values of the two subexpressions. | |
982 | ||
983 | @node Bison Parser, Stages, Semantic Actions, Concepts | |
984 | @section Bison Output: the Parser File | |
985 | @cindex Bison parser | |
986 | @cindex Bison utility | |
987 | @cindex lexical analyzer, purpose | |
988 | @cindex parser | |
989 | ||
990 | When you run Bison, you give it a Bison grammar file as input. The output | |
991 | is a C source file that parses the language described by the grammar. | |
992 | This file is called a @dfn{Bison parser}. Keep in mind that the Bison | |
993 | utility and the Bison parser are two distinct programs: the Bison utility | |
994 | is a program whose output is the Bison parser that becomes part of your | |
995 | program. | |
996 | ||
997 | The job of the Bison parser is to group tokens into groupings according to | |
998 | the grammar rules---for example, to build identifiers and operators into | |
999 | expressions. As it does this, it runs the actions for the grammar rules it | |
1000 | uses. | |
1001 | ||
1002 | The tokens come from a function called the @dfn{lexical analyzer} that you | |
1003 | must supply in some fashion (such as by writing it in C). The Bison parser | |
1004 | calls the lexical analyzer each time it wants a new token. It doesn't know | |
1005 | what is ``inside'' the tokens (though their semantic values may reflect | |
1006 | this). Typically the lexical analyzer makes the tokens by parsing | |
1007 | characters of text, but Bison does not depend on this. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}. | |
1008 | ||
1009 | The Bison parser file is C code which defines a function named | |
1010 | @code{yyparse} which implements that grammar. This function does not make | |
1011 | a complete C program: you must supply some additional functions. One is | |
1012 | the lexical analyzer. Another is an error-reporting function which the | |
1013 | parser calls to report an error. In addition, a complete C program must | |
1014 | start with a function called @code{main}; you have to provide this, and | |
1015 | arrange for it to call @code{yyparse} or the parser will never run. | |
1016 | @xref{Interface, ,Parser C-Language Interface}. | |
1017 | ||
1018 | Aside from the token type names and the symbols in the actions you | |
1019 | write, all variable and function names used in the Bison parser file | |
1020 | begin with @samp{yy} or @samp{YY}. This includes interface functions | |
1021 | such as the lexical analyzer function @code{yylex}, the error reporting | |
1022 | function @code{yyerror} and the parser function @code{yyparse} itself. | |
1023 | This also includes numerous identifiers used for internal purposes. | |
1024 | Therefore, you should avoid using C identifiers starting with @samp{yy} | |
1025 | or @samp{YY} in the Bison grammar file except for the ones defined in | |
1026 | this manual. | |
1027 | ||
1028 | @node Stages, Grammar Layout, Bison Parser, Concepts | |
1029 | @section Stages in Using Bison | |
1030 | @cindex stages in using Bison | |
1031 | @cindex using Bison | |
1032 | ||
1033 | The actual language-design process using Bison, from grammar specification | |
1034 | to a working compiler or interpreter, has these parts: | |
1035 | ||
1036 | @enumerate | |
1037 | @item | |
1038 | Formally specify the grammar in a form recognized by Bison | |
1039 | (@pxref{Grammar File, ,Bison Grammar Files}). For each grammatical rule in the language, | |
1040 | describe the action that is to be taken when an instance of that rule | |
1041 | is recognized. The action is described by a sequence of C statements. | |
1042 | ||
1043 | @item | |
1044 | Write a lexical analyzer to process input and pass tokens to the | |
1045 | parser. The lexical analyzer may be written by hand in C | |
1046 | (@pxref{Lexical, ,The Lexical Analyzer Function @code{yylex}}). It could also be produced using Lex, but the use | |
1047 | of Lex is not discussed in this manual. | |
1048 | ||
1049 | @item | |
1050 | Write a controlling function that calls the Bison-produced parser. | |
1051 | ||
1052 | @item | |
1053 | Write error-reporting routines. | |
1054 | @end enumerate | |
1055 | ||
1056 | To turn this source code as written into a runnable program, you | |
1057 | must follow these steps: | |
1058 | ||
1059 | @enumerate | |
1060 | @item | |
1061 | Run Bison on the grammar to produce the parser. | |
1062 | ||
1063 | @item | |
1064 | Compile the code output by Bison, as well as any other source files. | |
1065 | ||
1066 | @item | |
1067 | Link the object files to produce the finished product. | |
1068 | @end enumerate | |
1069 | ||
1070 | @node Grammar Layout, , Stages, Concepts | |
1071 | @section The Overall Layout of a Bison Grammar | |
1072 | @cindex grammar file | |
1073 | @cindex file format | |
1074 | @cindex format of grammar file | |
1075 | @cindex layout of Bison grammar | |
1076 | ||
1077 | The input file for the Bison utility is a @dfn{Bison grammar file}. The | |
1078 | general form of a Bison grammar file is as follows: | |
1079 | ||
1080 | @example | |
1081 | %@{ | |
1082 | @var{C declarations} | |
1083 | %@} | |
1084 | ||
1085 | @var{Bison declarations} | |
1086 | ||
1087 | %% | |
1088 | @var{Grammar rules} | |
1089 | %% | |
1090 | @var{Additional C code} | |
1091 | @end example | |
1092 | ||
1093 | @noindent | |
1094 | The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears | |
1095 | in every Bison grammar file to separate the sections. | |
1096 | ||
1097 | The C declarations may define types and variables used in the actions. | |
1098 | You can also use preprocessor commands to define macros used there, and use | |
1099 | @code{#include} to include header files that do any of these things. | |
1100 | ||
1101 | The Bison declarations declare the names of the terminal and nonterminal | |
1102 | symbols, and may also describe operator precedence and the data types of | |
1103 | semantic values of various symbols. | |
1104 | ||
1105 | The grammar rules define how to construct each nonterminal symbol from its | |
1106 | parts. | |
1107 | ||
1108 | The additional C code can contain any C code you want to use. Often the | |
1109 | definition of the lexical analyzer @code{yylex} goes here, plus subroutines | |
1110 | called by the actions in the grammar rules. In a simple program, all the | |
1111 | rest of the program can go here. | |
1112 | ||
1113 | @node Examples, Grammar File, Concepts, Top | |
1114 | @chapter Examples | |
1115 | @cindex simple examples | |
1116 | @cindex examples, simple | |
1117 | ||
1118 | Now we show and explain three sample programs written using Bison: a | |
1119 | reverse polish notation calculator, an algebraic (infix) notation | |
1120 | calculator, and a multi-function calculator. All three have been tested | |
1121 | under BSD Unix 4.3; each produces a usable, though limited, interactive | |
1122 | desk-top calculator. | |
1123 | ||
1124 | These examples are simple, but Bison grammars for real programming | |
1125 | languages are written the same way. | |
1126 | @ifinfo | |
1127 | You can copy these examples out of the Info file and into a source file | |
1128 | to try them. | |
1129 | @end ifinfo | |
1130 | ||
1131 | @menu | |
1132 | * RPN Calc:: Reverse polish notation calculator; | |
1133 | a first example with no operator precedence. | |
1134 | * Infix Calc:: Infix (algebraic) notation calculator. | |
1135 | Operator precedence is introduced. | |
1136 | * Simple Error Recovery:: Continuing after syntax errors. | |
1137 | * Multi-function Calc:: Calculator with memory and trig functions. | |
1138 | It uses multiple data-types for semantic values. | |
1139 | * Exercises:: Ideas for improving the multi-function calculator. | |
1140 | @end menu | |
1141 | ||
1142 | @node RPN Calc, Infix Calc, , Examples | |
1143 | @section Reverse Polish Notation Calculator | |
1144 | @cindex reverse polish notation | |
1145 | @cindex polish notation calculator | |
1146 | @cindex @code{rpcalc} | |
1147 | @cindex calculator, simple | |
1148 | ||
1149 | The first example is that of a simple double-precision @dfn{reverse polish | |
1150 | notation} calculator (a calculator using postfix operators). This example | |
1151 | provides a good starting point, since operator precedence is not an issue. | |
1152 | The second example will illustrate how operator precedence is handled. | |
1153 | ||
1154 | The source code for this calculator is named @file{rpcalc.y}. The | |
1155 | @samp{.y} extension is a convention used for Bison input files. | |
1156 | ||
1157 | @menu | |
1158 | * Decls: Rpcalc Decls. Bison and C declarations for rpcalc. | |
1159 | * Rules: Rpcalc Rules. Grammar Rules for rpcalc, with explanation. | |
1160 | * Lexer: Rpcalc Lexer. The lexical analyzer. | |
1161 | * Main: Rpcalc Main. The controlling function. | |
1162 | * Error: Rpcalc Error. The error reporting function. | |
1163 | * Gen: Rpcalc Gen. Running Bison on the grammar file. | |
1164 | * Comp: Rpcalc Compile. Run the C compiler on the output code. | |
1165 | @end menu | |
1166 | ||
1167 | @node Rpcalc Decls, Rpcalc Rules, , RPN Calc | |
1168 | @subsection Declarations for @code{rpcalc} | |
1169 | ||
1170 | Here are the C and Bison declarations for the reverse polish notation | |
1171 | calculator. As in C, comments are placed between @samp{/*@dots{}*/}. | |
1172 | ||
1173 | @example | |
1174 | /* Reverse polish notation calculator. */ | |
1175 | ||
1176 | %@{ | |
1177 | #define YYSTYPE double | |
1178 | #include <math.h> | |
1179 | %@} | |
1180 | ||
1181 | %token NUM | |
1182 | ||
1183 | %% /* Grammar rules and actions follow */ | |
1184 | @end example | |
1185 | ||
1186 | The C declarations section (@pxref{C Declarations, ,The C Declarations Section}) contains two | |
1187 | preprocessor directives. | |
1188 | ||
1189 | The @code{#define} directive defines the macro @code{YYSTYPE}, thus | |
1190 | specifying the C data type for semantic values of both tokens and groupings | |
1191 | (@pxref{Value Type, ,Data Types of Semantic Values}). The Bison parser will use whatever type | |
1192 | @code{YYSTYPE} is defined as; if you don't define it, @code{int} is the | |
1193 | default. Because we specify @code{double}, each token and each expression | |
1194 | has an associated value, which is a floating point number. | |
1195 | ||
1196 | The @code{#include} directive is used to declare the exponentiation | |
1197 | function @code{pow}. | |
1198 | ||
1199 | The second section, Bison declarations, provides information to Bison about | |
1200 | the token types (@pxref{Bison Declarations, ,The Bison Declarations Section}). Each terminal symbol that is | |
1201 | not a single-character literal must be declared here. (Single-character | |
1202 | literals normally don't need to be declared.) In this example, all the | |
1203 | arithmetic operators are designated by single-character literals, so the | |
1204 | only terminal symbol that needs to be declared is @code{NUM}, the token | |
1205 | type for numeric constants. | |
1206 | ||
1207 | @node Rpcalc Rules, Rpcalc Lexer, Rpcalc Decls, RPN Calc | |
1208 | @subsection Grammar Rules for @code{rpcalc} | |
1209 | ||
1210 | Here are the grammar rules for the reverse polish notation calculator. | |
1211 | ||
1212 | @example | |
1213 | input: /* empty */ | |
1214 | | input line | |
1215 | ; | |
1216 | ||
1217 | line: '\n' | |
1218 | | exp '\n' @{ printf ("\t%.10g\n", $1); @} | |
1219 | ; | |
1220 | ||
1221 | exp: NUM @{ $$ = $1; @} | |
1222 | | exp exp '+' @{ $$ = $1 + $2; @} | |
1223 | | exp exp '-' @{ $$ = $1 - $2; @} | |
1224 | | exp exp '*' @{ $$ = $1 * $2; @} | |
1225 | | exp exp '/' @{ $$ = $1 / $2; @} | |
1226 | /* Exponentiation */ | |
1227 | | exp exp '^' @{ $$ = pow ($1, $2); @} | |
1228 | /* Unary minus */ | |
1229 | | exp 'n' @{ $$ = -$1; @} | |
1230 | ; | |
1231 | %% | |
1232 | @end example | |
1233 | ||
1234 | The groupings of the rpcalc ``language'' defined here are the expression | |
1235 | (given the name @code{exp}), the line of input (@code{line}), and the | |
1236 | complete input transcript (@code{input}). Each of these nonterminal | |
1237 | symbols has several alternate rules, joined by the @samp{|} punctuator | |
1238 | which is read as ``or''. The following sections explain what these rules | |
1239 | mean. | |
1240 | ||
1241 | The semantics of the language is determined by the actions taken when a | |
1242 | grouping is recognized. The actions are the C code that appears inside | |
1243 | braces. @xref{Actions}. | |
1244 | ||
1245 | You must specify these actions in C, but Bison provides the means for | |
1246 | passing semantic values between the rules. In each action, the | |
1247 | pseudo-variable @code{$$} stands for the semantic value for the grouping | |
1248 | that the rule is going to construct. Assigning a value to @code{$$} is the | |
1249 | main job of most actions. The semantic values of the components of the | |
1250 | rule are referred to as @code{$1}, @code{$2}, and so on. | |
1251 | ||
1252 | @menu | |
1253 | * Rpcalc Input:: | |
1254 | * Rpcalc Line:: | |
1255 | * Rpcalc Expr:: | |
1256 | @end menu | |
1257 | ||
1258 | @node Rpcalc Input, Rpcalc Line, , Rpcalc Rules | |
1259 | @subsubsection Explanation of @code{input} | |
1260 | ||
1261 | Consider the definition of @code{input}: | |
1262 | ||
1263 | @example | |
1264 | input: /* empty */ | |
1265 | | input line | |
1266 | ; | |
1267 | @end example | |
1268 | ||
1269 | This definition reads as follows: ``A complete input is either an empty | |
1270 | string, or a complete input followed by an input line''. Notice that | |
1271 | ``complete input'' is defined in terms of itself. This definition is said | |
1272 | to be @dfn{left recursive} since @code{input} appears always as the | |
1273 | leftmost symbol in the sequence. @xref{Recursion, ,Recursive Rules}. | |
1274 | ||
1275 | The first alternative is empty because there are no symbols between the | |
1276 | colon and the first @samp{|}; this means that @code{input} can match an | |
1277 | empty string of input (no tokens). We write the rules this way because it | |
1278 | is legitimate to type @kbd{Ctrl-d} right after you start the calculator. | |
1279 | It's conventional to put an empty alternative first and write the comment | |
1280 | @samp{/* empty */} in it. | |
1281 | ||
1282 | The second alternate rule (@code{input line}) handles all nontrivial input. | |
1283 | It means, ``After reading any number of lines, read one more line if | |
1284 | possible.'' The left recursion makes this rule into a loop. Since the | |
1285 | first alternative matches empty input, the loop can be executed zero or | |
1286 | more times. | |
1287 | ||
1288 | The parser function @code{yyparse} continues to process input until a | |
1289 | grammatical error is seen or the lexical analyzer says there are no more | |
1290 | input tokens; we will arrange for the latter to happen at end of file. | |
1291 | ||
1292 | @node Rpcalc Line, Rpcalc Expr, Rpcalc Input, Rpcalc Rules | |
1293 | @subsubsection Explanation of @code{line} | |
1294 | ||
1295 | Now consider the definition of @code{line}: | |
1296 | ||
1297 | @example | |
1298 | line: '\n' | |
1299 | | exp '\n' @{ printf ("\t%.10g\n", $1); @} | |
1300 | ; | |
1301 | @end example | |
1302 | ||
1303 | The first alternative is a token which is a newline character; this means | |
1304 | that rpcalc accepts a blank line (and ignores it, since there is no | |
1305 | action). The second alternative is an expression followed by a newline. | |
1306 | This is the alternative that makes rpcalc useful. The semantic value of | |
1307 | the @code{exp} grouping is the value of @code{$1} because the @code{exp} in | |
1308 | question is the first symbol in the alternative. The action prints this | |
1309 | value, which is the result of the computation the user asked for. | |
1310 | ||
1311 | This action is unusual because it does not assign a value to @code{$$}. As | |
1312 | a consequence, the semantic value associated with the @code{line} is | |
1313 | uninitialized (its value will be unpredictable). This would be a bug if | |
1314 | that value were ever used, but we don't use it: once rpcalc has printed the | |
1315 | value of the user's input line, that value is no longer needed. | |
1316 | ||
1317 | @node Rpcalc Expr, , Rpcalc Line, Rpcalc Rules | |
1318 | @subsubsection Explanation of @code{expr} | |
1319 | ||
1320 | The @code{exp} grouping has several rules, one for each kind of expression. | |
1321 | The first rule handles the simplest expressions: those that are just numbers. | |
1322 | The second handles an addition-expression, which looks like two expressions | |
1323 | followed by a plus-sign. The third handles subtraction, and so on. | |
1324 | ||
1325 | @example | |
1326 | exp: NUM | |
1327 | | exp exp '+' @{ $$ = $1 + $2; @} | |
1328 | | exp exp '-' @{ $$ = $1 - $2; @} | |
1329 | @dots{} | |
1330 | ; | |
1331 | @end example | |
1332 | ||
1333 | We have used @samp{|} to join all the rules for @code{exp}, but we could | |
1334 | equally well have written them separately: | |
1335 | ||
1336 | @example | |
1337 | exp: NUM ; | |
1338 | exp: exp exp '+' @{ $$ = $1 + $2; @} ; | |
1339 | exp: exp exp '-' @{ $$ = $1 - $2; @} ; | |
1340 | @dots{} | |
1341 | @end example | |
1342 | ||
1343 | Most of the rules have actions that compute the value of the expression in | |
1344 | terms of the value of its parts. For example, in the rule for addition, | |
1345 | @code{$1} refers to the first component @code{exp} and @code{$2} refers to | |
1346 | the second one. The third component, @code{'+'}, has no meaningful | |
1347 | associated semantic value, but if it had one you could refer to it as | |
1348 | @code{$3}. When @code{yyparse} recognizes a sum expression using this | |
1349 | rule, the sum of the two subexpressions' values is produced as the value of | |
1350 | the entire expression. @xref{Actions}. | |
1351 | ||
1352 | You don't have to give an action for every rule. When a rule has no | |
1353 | action, Bison by default copies the value of @code{$1} into @code{$$}. | |
1354 | This is what happens in the first rule (the one that uses @code{NUM}). | |
1355 | ||
1356 | The formatting shown here is the recommended convention, but Bison does | |
1357 | not require it. You can add or change whitespace as much as you wish. | |
1358 | For example, this: | |
1359 | ||
1360 | @example | |
1361 | exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{} | |
1362 | @end example | |
1363 | ||
1364 | @noindent | |
1365 | means the same thing as this: | |
1366 | ||
1367 | @example | |
1368 | exp: NUM | |
1369 | | exp exp '+' @{ $$ = $1 + $2; @} | |
1370 | | @dots{} | |
1371 | @end example | |
1372 | ||
1373 | @noindent | |
1374 | The latter, however, is much more readable. | |
1375 | ||
1376 | @node Rpcalc Lexer, Rpcalc Main, Rpcalc Rules, RPN Calc | |
1377 | @subsection The @code{rpcalc} Lexical Analyzer | |
1378 | @cindex writing a lexical analyzer | |
1379 | @cindex lexical analyzer, writing | |
1380 | ||
1381 | The lexical analyzer's job is low-level parsing: converting characters or | |
1382 | sequences of characters into tokens. The Bison parser gets its tokens by | |
1383 | calling the lexical analyzer. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}. | |
1384 | ||
1385 | Only a simple lexical analyzer is needed for the RPN calculator. This | |
1386 | lexical analyzer skips blanks and tabs, then reads in numbers as | |
1387 | @code{double} and returns them as @code{NUM} tokens. Any other character | |
1388 | that isn't part of a number is a separate token. Note that the token-code | |
1389 | for such a single-character token is the character itself. | |
1390 | ||
1391 | The return value of the lexical analyzer function is a numeric code which | |
1392 | represents a token type. The same text used in Bison rules to stand for | |
1393 | this token type is also a C expression for the numeric code for the type. | |
1394 | This works in two ways. If the token type is a character literal, then its | |
1395 | numeric code is the ASCII code for that character; you can use the same | |
1396 | character literal in the lexical analyzer to express the number. If the | |
1397 | token type is an identifier, that identifier is defined by Bison as a C | |
1398 | macro whose definition is the appropriate number. In this example, | |
1399 | therefore, @code{NUM} becomes a macro for @code{yylex} to use. | |
1400 | ||
1401 | The semantic value of the token (if it has one) is stored into the global | |
1402 | variable @code{yylval}, which is where the Bison parser will look for it. | |
1403 | (The C data type of @code{yylval} is @code{YYSTYPE}, which was defined | |
1404 | at the beginning of the grammar; @pxref{Rpcalc Decls, ,Declarations for @code{rpcalc}}.) | |
1405 | ||
1406 | A token type code of zero is returned if the end-of-file is encountered. | |
1407 | (Bison recognizes any nonpositive value as indicating the end of the | |
1408 | input.) | |
1409 | ||
1410 | Here is the code for the lexical analyzer: | |
1411 | ||
1412 | @example | |
1413 | @group | |
1414 | /* Lexical analyzer returns a double floating point | |
1415 | number on the stack and the token NUM, or the ASCII | |
1416 | character read if not a number. Skips all blanks | |
1417 | and tabs, returns 0 for EOF. */ | |
1418 | ||
1419 | #include <ctype.h> | |
1420 | @end group | |
1421 | ||
1422 | @group | |
1423 | yylex () | |
1424 | @{ | |
1425 | int c; | |
1426 | ||
1427 | /* skip white space */ | |
1428 | while ((c = getchar ()) == ' ' || c == '\t') | |
1429 | ; | |
1430 | @end group | |
1431 | @group | |
1432 | /* process numbers */ | |
1433 | if (c == '.' || isdigit (c)) | |
1434 | @{ | |
1435 | ungetc (c, stdin); | |
1436 | scanf ("%lf", &yylval); | |
1437 | return NUM; | |
1438 | @} | |
1439 | @end group | |
1440 | @group | |
1441 | /* return end-of-file */ | |
1442 | if (c == EOF) | |
1443 | return 0; | |
1444 | /* return single chars */ | |
1445 | return c; | |
1446 | @} | |
1447 | @end group | |
1448 | @end example | |
1449 | ||
1450 | @node Rpcalc Main, Rpcalc Error, Rpcalc Lexer, RPN Calc | |
1451 | @subsection The Controlling Function | |
1452 | @cindex controlling function | |
1453 | @cindex main function in simple example | |
1454 | ||
1455 | In keeping with the spirit of this example, the controlling function is | |
1456 | kept to the bare minimum. The only requirement is that it call | |
1457 | @code{yyparse} to start the process of parsing. | |
1458 | ||
1459 | @example | |
1460 | @group | |
1461 | main () | |
1462 | @{ | |
1463 | yyparse (); | |
1464 | @} | |
1465 | @end group | |
1466 | @end example | |
1467 | ||
1468 | @node Rpcalc Error, Rpcalc Gen, Rpcalc Main, RPN Calc | |
1469 | @subsection The Error Reporting Routine | |
1470 | @cindex error reporting routine | |
1471 | ||
1472 | When @code{yyparse} detects a syntax error, it calls the error reporting | |
1473 | function @code{yyerror} to print an error message (usually but not always | |
1474 | @code{"parse error"}). It is up to the programmer to supply @code{yyerror} | |
1475 | (@pxref{Interface, ,Parser C-Language Interface}), so here is the definition we will use: | |
1476 | ||
1477 | @example | |
1478 | @group | |
1479 | #include <stdio.h> | |
1480 | ||
1481 | yyerror (s) /* Called by yyparse on error */ | |
1482 | char *s; | |
1483 | @{ | |
1484 | printf ("%s\n", s); | |
1485 | @} | |
1486 | @end group | |
1487 | @end example | |
1488 | ||
1489 | After @code{yyerror} returns, the Bison parser may recover from the error | |
1490 | and continue parsing if the grammar contains a suitable error rule | |
1491 | (@pxref{Error Recovery}). Otherwise, @code{yyparse} returns nonzero. We | |
1492 | have not written any error rules in this example, so any invalid input will | |
1493 | cause the calculator program to exit. This is not clean behavior for a | |
1494 | real calculator, but it is adequate in the first example. | |
1495 | ||
1496 | @node Rpcalc Gen, Rpcalc Compile, Rpcalc Error, RPN Calc | |
1497 | @subsection Running Bison to Make the Parser | |
1498 | @cindex running Bison (introduction) | |
1499 | ||
1500 | Before running Bison to produce a parser, we need to decide how to arrange | |
1501 | all the source code in one or more source files. For such a simple example, | |
1502 | the easiest thing is to put everything in one file. The definitions of | |
1503 | @code{yylex}, @code{yyerror} and @code{main} go at the end, in the | |
1504 | ``additional C code'' section of the file (@pxref{Grammar Layout, ,The Overall Layout of a Bison Grammar}). | |
1505 | ||
1506 | For a large project, you would probably have several source files, and use | |
1507 | @code{make} to arrange to recompile them. | |
1508 | ||
1509 | With all the source in a single file, you use the following command to | |
1510 | convert it into a parser file: | |
1511 | ||
1512 | @example | |
1513 | bison @var{file_name}.y | |
1514 | @end example | |
1515 | ||
1516 | @noindent | |
1517 | In this example the file was called @file{rpcalc.y} (for ``Reverse Polish | |
1518 | CALCulator''). Bison produces a file named @file{@var{file_name}.tab.c}, | |
1519 | removing the @samp{.y} from the original file name. The file output by | |
1520 | Bison contains the source code for @code{yyparse}. The additional | |
1521 | functions in the input file (@code{yylex}, @code{yyerror} and @code{main}) | |
1522 | are copied verbatim to the output. | |
1523 | ||
1524 | @node Rpcalc Compile, , Rpcalc Gen, RPN Calc | |
1525 | @subsection Compiling the Parser File | |
1526 | @cindex compiling the parser | |
1527 | ||
1528 | Here is how to compile and run the parser file: | |
1529 | ||
1530 | @example | |
1531 | @group | |
1532 | # @r{List files in current directory.} | |
1533 | % ls | |
1534 | rpcalc.tab.c rpcalc.y | |
1535 | @end group | |
1536 | ||
1537 | @group | |
1538 | # @r{Compile the Bison parser.} | |
1539 | # @r{@samp{-lm} tells compiler to search math library for @code{pow}.} | |
1540 | % cc rpcalc.tab.c -lm -o rpcalc | |
1541 | @end group | |
1542 | ||
1543 | @group | |
1544 | # @r{List files again.} | |
1545 | % ls | |
1546 | rpcalc rpcalc.tab.c rpcalc.y | |
1547 | @end group | |
1548 | @end example | |
1549 | ||
1550 | The file @file{rpcalc} now contains the executable code. Here is an | |
1551 | example session using @code{rpcalc}. | |
1552 | ||
1553 | @example | |
1554 | % rpcalc | |
1555 | 4 9 + | |
1556 | 13 | |
1557 | 3 7 + 3 4 5 *+- | |
1558 | -13 | |
1559 | 3 7 + 3 4 5 * + - n @r{Note the unary minus, @samp{n}} | |
1560 | 13 | |
1561 | 5 6 / 4 n + | |
1562 | -3.166666667 | |
1563 | 3 4 ^ @r{Exponentiation} | |
1564 | 81 | |
1565 | ^D @r{End-of-file indicator} | |
1566 | % | |
1567 | @end example | |
1568 | ||
1569 | @node Infix Calc, Simple Error Recovery, RPN Calc, Examples | |
1570 | @section Infix Notation Calculator: @code{calc} | |
1571 | @cindex infix notation calculator | |
1572 | @cindex @code{calc} | |
1573 | @cindex calculator, infix notation | |
1574 | ||
1575 | We now modify rpcalc to handle infix operators instead of postfix. Infix | |
1576 | notation involves the concept of operator precedence and the need for | |
1577 | parentheses nested to arbitrary depth. Here is the Bison code for | |
1578 | @file{calc.y}, an infix desk-top calculator. | |
1579 | ||
1580 | @example | |
1581 | /* Infix notation calculator--calc */ | |
1582 | ||
1583 | %@{ | |
1584 | #define YYSTYPE double | |
1585 | #include <math.h> | |
1586 | %@} | |
1587 | ||
1588 | /* BISON Declarations */ | |
1589 | %token NUM | |
1590 | %left '-' '+' | |
1591 | %left '*' '/' | |
1592 | %left NEG /* negation--unary minus */ | |
1593 | %right '^' /* exponentiation */ | |
1594 | ||
1595 | /* Grammar follows */ | |
1596 | %% | |
1597 | input: /* empty string */ | |
1598 | | input line | |
1599 | ; | |
1600 | ||
1601 | line: '\n' | |
1602 | | exp '\n' @{ printf ("\t%.10g\n", $1); @} | |
1603 | ; | |
1604 | ||
1605 | exp: NUM @{ $$ = $1; @} | |
1606 | | exp '+' exp @{ $$ = $1 + $3; @} | |
1607 | | exp '-' exp @{ $$ = $1 - $3; @} | |
1608 | | exp '*' exp @{ $$ = $1 * $3; @} | |
1609 | | exp '/' exp @{ $$ = $1 / $3; @} | |
1610 | | '-' exp %prec NEG @{ $$ = -$2; @} | |
1611 | | exp '^' exp @{ $$ = pow ($1, $3); @} | |
1612 | | '(' exp ')' @{ $$ = $2; @} | |
1613 | ; | |
1614 | %% | |
1615 | @end example | |
1616 | ||
1617 | @noindent | |
1618 | The functions @code{yylex}, @code{yyerror} and @code{main} can be the same | |
1619 | as before. | |
1620 | ||
1621 | There are two important new features shown in this code. | |
1622 | ||
1623 | In the second section (Bison declarations), @code{%left} declares token | |
1624 | types and says they are left-associative operators. The declarations | |
1625 | @code{%left} and @code{%right} (right associativity) take the place of | |
1626 | @code{%token} which is used to declare a token type name without | |
1627 | associativity. (These tokens are single-character literals, which | |
1628 | ordinarily don't need to be declared. We declare them here to specify | |
1629 | the associativity.) | |
1630 | ||
1631 | Operator precedence is determined by the line ordering of the | |
1632 | declarations; the higher the line number of the declaration (lower on | |
1633 | the page or screen), the higher the precedence. Hence, exponentiation | |
1634 | has the highest precedence, unary minus (@code{NEG}) is next, followed | |
1635 | by @samp{*} and @samp{/}, and so on. @xref{Precedence, ,Operator Precedence}. | |
1636 | ||
1637 | The other important new feature is the @code{%prec} in the grammar section | |
1638 | for the unary minus operator. The @code{%prec} simply instructs Bison that | |
1639 | the rule @samp{| '-' exp} has the same precedence as @code{NEG}---in this | |
1640 | case the next-to-highest. @xref{Contextual Precedence, ,Context-Dependent Precedence}. | |
1641 | ||
1642 | Here is a sample run of @file{calc.y}: | |
1643 | ||
1644 | @need 500 | |
1645 | @example | |
1646 | % calc | |
1647 | 4 + 4.5 - (34/(8*3+-3)) | |
1648 | 6.880952381 | |
1649 | -56 + 2 | |
1650 | -54 | |
1651 | 3 ^ 2 | |
1652 | 9 | |
1653 | @end example | |
1654 | ||
1655 | @node Simple Error Recovery, Multi-function Calc, Infix Calc, Examples | |
1656 | @section Simple Error Recovery | |
1657 | @cindex error recovery, simple | |
1658 | ||
1659 | Up to this point, this manual has not addressed the issue of @dfn{error | |
1660 | recovery}---how to continue parsing after the parser detects a syntax | |
1661 | error. All we have handled is error reporting with @code{yyerror}. Recall | |
1662 | that by default @code{yyparse} returns after calling @code{yyerror}. This | |
1663 | means that an erroneous input line causes the calculator program to exit. | |
1664 | Now we show how to rectify this deficiency. | |
1665 | ||
1666 | The Bison language itself includes the reserved word @code{error}, which | |
1667 | may be included in the grammar rules. In the example below it has | |
1668 | been added to one of the alternatives for @code{line}: | |
1669 | ||
1670 | @example | |
1671 | @group | |
1672 | line: '\n' | |
1673 | | exp '\n' @{ printf ("\t%.10g\n", $1); @} | |
1674 | | error '\n' @{ yyerrok; @} | |
1675 | ; | |
1676 | @end group | |
1677 | @end example | |
1678 | ||
1679 | This addition to the grammar allows for simple error recovery in the event | |
1680 | of a parse error. If an expression that cannot be evaluated is read, the | |
1681 | error will be recognized by the third rule for @code{line}, and parsing | |
1682 | will continue. (The @code{yyerror} function is still called upon to print | |
1683 | its message as well.) The action executes the statement @code{yyerrok}, a | |
1684 | macro defined automatically by Bison; its meaning is that error recovery is | |
1685 | complete (@pxref{Error Recovery}). Note the difference between | |
1686 | @code{yyerrok} and @code{yyerror}; neither one is a misprint.@refill | |
1687 | ||
1688 | This form of error recovery deals with syntax errors. There are other | |
1689 | kinds of errors; for example, division by zero, which raises an exception | |
1690 | signal that is normally fatal. A real calculator program must handle this | |
1691 | signal and use @code{longjmp} to return to @code{main} and resume parsing | |
1692 | input lines; it would also have to discard the rest of the current line of | |
1693 | input. We won't discuss this issue further because it is not specific to | |
1694 | Bison programs. | |
1695 | ||
1696 | @node Multi-function Calc, Exercises, Simple Error Recovery, Examples | |
1697 | @section Multi-Function Calculator: @code{mfcalc} | |
1698 | @cindex multi-function calculator | |
1699 | @cindex @code{mfcalc} | |
1700 | @cindex calculator, multi-function | |
1701 | ||
1702 | Now that the basics of Bison have been discussed, it is time to move on to | |
1703 | a more advanced problem. The above calculators provided only five | |
1704 | functions, @samp{+}, @samp{-}, @samp{*}, @samp{/} and @samp{^}. It would | |
1705 | be nice to have a calculator that provides other mathematical functions such | |
1706 | as @code{sin}, @code{cos}, etc. | |
1707 | ||
1708 | It is easy to add new operators to the infix calculator as long as they are | |
1709 | only single-character literals. The lexical analyzer @code{yylex} passes | |
1710 | back all non-number characters as tokens, so new grammar rules suffice for | |
1711 | adding a new operator. But we want something more flexible: built-in | |
1712 | functions whose syntax has this form: | |
1713 | ||
1714 | @example | |
1715 | @var{function_name} (@var{argument}) | |
1716 | @end example | |
1717 | ||
1718 | @noindent | |
1719 | At the same time, we will add memory to the calculator, by allowing you | |
1720 | to create named variables, store values in them, and use them later. | |
1721 | Here is a sample session with the multi-function calculator: | |
1722 | ||
1723 | @example | |
1724 | % mfcalc | |
1725 | pi = 3.141592653589 | |
1726 | 3.1415926536 | |
1727 | sin(pi) | |
1728 | 0.0000000000 | |
1729 | alpha = beta1 = 2.3 | |
1730 | 2.3000000000 | |
1731 | alpha | |
1732 | 2.3000000000 | |
1733 | ln(alpha) | |
1734 | 0.8329091229 | |
1735 | exp(ln(beta1)) | |
1736 | 2.3000000000 | |
1737 | % | |
1738 | @end example | |
1739 | ||
1740 | Note that multiple assignment and nested function calls are permitted. | |
1741 | ||
1742 | @menu | |
1743 | * Decl: Mfcalc Decl. Bison declarations for multi-function calculator. | |
1744 | * Rules: Mfcalc Rules. Grammar rules for the calculator. | |
1745 | * Symtab: Mfcalc Symtab. Symbol table management subroutines. | |
1746 | @end menu | |
1747 | ||
1748 | @node Mfcalc Decl, Mfcalc Rules, , Multi-function Calc | |
1749 | @subsection Declarations for @code{mfcalc} | |
1750 | ||
1751 | Here are the C and Bison declarations for the multi-function calculator. | |
1752 | ||
1753 | @smallexample | |
1754 | %@{ | |
1755 | #include <math.h> /* For math functions, cos(), sin(), etc. */ | |
1756 | #include "calc.h" /* Contains definition of `symrec' */ | |
1757 | %@} | |
1758 | %union @{ | |
1759 | double val; /* For returning numbers. */ | |
1760 | symrec *tptr; /* For returning symbol-table pointers */ | |
1761 | @} | |
1762 | ||
1763 | %token <val> NUM /* Simple double precision number */ | |
1764 | %token <tptr> VAR FNCT /* Variable and Function */ | |
1765 | %type <val> exp | |
1766 | ||
1767 | %right '=' | |
1768 | %left '-' '+' | |
1769 | %left '*' '/' | |
1770 | %left NEG /* Negation--unary minus */ | |
1771 | %right '^' /* Exponentiation */ | |
1772 | ||
1773 | /* Grammar follows */ | |
1774 | ||
1775 | %% | |
1776 | @end smallexample | |
1777 | ||
1778 | The above grammar introduces only two new features of the Bison language. | |
1779 | These features allow semantic values to have various data types | |
1780 | (@pxref{Multiple Types, ,More Than One Value Type}). | |
1781 | ||
1782 | The @code{%union} declaration specifies the entire list of possible types; | |
1783 | this is instead of defining @code{YYSTYPE}. The allowable types are now | |
1784 | double-floats (for @code{exp} and @code{NUM}) and pointers to entries in | |
1785 | the symbol table. @xref{Union Decl, ,The Collection of Value Types}. | |
1786 | ||
1787 | Since values can now have various types, it is necessary to associate a | |
1788 | type with each grammar symbol whose semantic value is used. These symbols | |
1789 | are @code{NUM}, @code{VAR}, @code{FNCT}, and @code{exp}. Their | |
1790 | declarations are augmented with information about their data type (placed | |
1791 | between angle brackets). | |
1792 | ||
1793 | The Bison construct @code{%type} is used for declaring nonterminal symbols, | |
1794 | just as @code{%token} is used for declaring token types. We have not used | |
1795 | @code{%type} before because nonterminal symbols are normally declared | |
1796 | implicitly by the rules that define them. But @code{exp} must be declared | |
1797 | explicitly so we can specify its value type. @xref{Type Decl, ,Nonterminal Symbols}. | |
1798 | ||
1799 | @node Mfcalc Rules, Mfcalc Symtab, Mfcalc Decl, Multi-function Calc | |
1800 | @subsection Grammar Rules for @code{mfcalc} | |
1801 | ||
1802 | Here are the grammar rules for the multi-function calculator. | |
1803 | Most of them are copied directly from @code{calc}; three rules, | |
1804 | those which mention @code{VAR} or @code{FNCT}, are new. | |
1805 | ||
1806 | @smallexample | |
1807 | input: /* empty */ | |
1808 | | input line | |
1809 | ; | |
1810 | ||
1811 | line: | |
1812 | '\n' | |
1813 | | exp '\n' @{ printf ("\t%.10g\n", $1); @} | |
1814 | | error '\n' @{ yyerrok; @} | |
1815 | ; | |
1816 | ||
1817 | exp: NUM @{ $$ = $1; @} | |
1818 | | VAR @{ $$ = $1->value.var; @} | |
1819 | | VAR '=' exp @{ $$ = $3; $1->value.var = $3; @} | |
1820 | | FNCT '(' exp ')' @{ $$ = (*($1->value.fnctptr))($3); @} | |
1821 | | exp '+' exp @{ $$ = $1 + $3; @} | |
1822 | | exp '-' exp @{ $$ = $1 - $3; @} | |
1823 | | exp '*' exp @{ $$ = $1 * $3; @} | |
1824 | | exp '/' exp @{ $$ = $1 / $3; @} | |
1825 | | '-' exp %prec NEG @{ $$ = -$2; @} | |
1826 | | exp '^' exp @{ $$ = pow ($1, $3); @} | |
1827 | | '(' exp ')' @{ $$ = $2; @} | |
1828 | ; | |
1829 | /* End of grammar */ | |
1830 | %% | |
1831 | @end smallexample | |
1832 | ||
1833 | @node Mfcalc Symtab, , Mfcalc Rules, Multi-function Calc | |
1834 | @subsection The @code{mfcalc} Symbol Table | |
1835 | @cindex symbol table example | |
1836 | ||
1837 | The multi-function calculator requires a symbol table to keep track of the | |
1838 | names and meanings of variables and functions. This doesn't affect the | |
1839 | grammar rules (except for the actions) or the Bison declarations, but it | |
1840 | requires some additional C functions for support. | |
1841 | ||
1842 | The symbol table itself consists of a linked list of records. Its | |
1843 | definition, which is kept in the header @file{calc.h}, is as follows. It | |
1844 | provides for either functions or variables to be placed in the table. | |
1845 | ||
1846 | @smallexample | |
1847 | @group | |
1848 | /* Data type for links in the chain of symbols. */ | |
1849 | struct symrec | |
1850 | @{ | |
1851 | char *name; /* name of symbol */ | |
1852 | int type; /* type of symbol: either VAR or FNCT */ | |
1853 | union @{ | |
1854 | double var; /* value of a VAR */ | |
1855 | double (*fnctptr)(); /* value of a FNCT */ | |
1856 | @} value; | |
1857 | struct symrec *next; /* link field */ | |
1858 | @}; | |
1859 | @end group | |
1860 | ||
1861 | @group | |
1862 | typedef struct symrec symrec; | |
1863 | ||
1864 | /* The symbol table: a chain of `struct symrec'. */ | |
1865 | extern symrec *sym_table; | |
1866 | ||
1867 | symrec *putsym (); | |
1868 | symrec *getsym (); | |
1869 | @end group | |
1870 | @end smallexample | |
1871 | ||
1872 | The new version of @code{main} includes a call to @code{init_table}, a | |
1873 | function that initializes the symbol table. Here it is, and | |
1874 | @code{init_table} as well: | |
1875 | ||
1876 | @smallexample | |
1877 | @group | |
1878 | #include <stdio.h> | |
1879 | ||
1880 | main () | |
1881 | @{ | |
1882 | init_table (); | |
1883 | yyparse (); | |
1884 | @} | |
1885 | @end group | |
1886 | ||
1887 | @group | |
1888 | yyerror (s) /* Called by yyparse on error */ | |
1889 | char *s; | |
1890 | @{ | |
1891 | printf ("%s\n", s); | |
1892 | @} | |
1893 | ||
1894 | struct init | |
1895 | @{ | |
1896 | char *fname; | |
1897 | double (*fnct)(); | |
1898 | @}; | |
1899 | @end group | |
1900 | ||
1901 | @group | |
1902 | struct init arith_fncts[] | |
1903 | = @{ | |
1904 | "sin", sin, | |
1905 | "cos", cos, | |
1906 | "atan", atan, | |
1907 | "ln", log, | |
1908 | "exp", exp, | |
1909 | "sqrt", sqrt, | |
1910 | 0, 0 | |
1911 | @}; | |
1912 | ||
1913 | /* The symbol table: a chain of `struct symrec'. */ | |
1914 | symrec *sym_table = (symrec *)0; | |
1915 | @end group | |
1916 | ||
1917 | @group | |
1918 | init_table () /* puts arithmetic functions in table. */ | |
1919 | @{ | |
1920 | int i; | |
1921 | symrec *ptr; | |
1922 | for (i = 0; arith_fncts[i].fname != 0; i++) | |
1923 | @{ | |
1924 | ptr = putsym (arith_fncts[i].fname, FNCT); | |
1925 | ptr->value.fnctptr = arith_fncts[i].fnct; | |
1926 | @} | |
1927 | @} | |
1928 | @end group | |
1929 | @end smallexample | |
1930 | ||
1931 | By simply editing the initialization list and adding the necessary include | |
1932 | files, you can add additional functions to the calculator. | |
1933 | ||
1934 | Two important functions allow look-up and installation of symbols in the | |
1935 | symbol table. The function @code{putsym} is passed a name and the type | |
1936 | (@code{VAR} or @code{FNCT}) of the object to be installed. The object is | |
1937 | linked to the front of the list, and a pointer to the object is returned. | |
1938 | The function @code{getsym} is passed the name of the symbol to look up. If | |
1939 | found, a pointer to that symbol is returned; otherwise zero is returned. | |
1940 | ||
1941 | @smallexample | |
1942 | symrec * | |
1943 | putsym (sym_name,sym_type) | |
1944 | char *sym_name; | |
1945 | int sym_type; | |
1946 | @{ | |
1947 | symrec *ptr; | |
1948 | ptr = (symrec *) malloc (sizeof (symrec)); | |
1949 | ptr->name = (char *) malloc (strlen (sym_name) + 1); | |
1950 | strcpy (ptr->name,sym_name); | |
1951 | ptr->type = sym_type; | |
1952 | ptr->value.var = 0; /* set value to 0 even if fctn. */ | |
1953 | ptr->next = (struct symrec *)sym_table; | |
1954 | sym_table = ptr; | |
1955 | return ptr; | |
1956 | @} | |
1957 | ||
1958 | symrec * | |
1959 | getsym (sym_name) | |
1960 | char *sym_name; | |
1961 | @{ | |
1962 | symrec *ptr; | |
1963 | for (ptr = sym_table; ptr != (symrec *) 0; | |
1964 | ptr = (symrec *)ptr->next) | |
1965 | if (strcmp (ptr->name,sym_name) == 0) | |
1966 | return ptr; | |
1967 | return 0; | |
1968 | @} | |
1969 | @end smallexample | |
1970 | ||
1971 | The function @code{yylex} must now recognize variables, numeric values, and | |
1972 | the single-character arithmetic operators. Strings of alphanumeric | |
1973 | characters with a leading nondigit are recognized as either variables or | |
1974 | functions depending on what the symbol table says about them. | |
1975 | ||
1976 | The string is passed to @code{getsym} for look up in the symbol table. If | |
1977 | the name appears in the table, a pointer to its location and its type | |
1978 | (@code{VAR} or @code{FNCT}) is returned to @code{yyparse}. If it is not | |
1979 | already in the table, then it is installed as a @code{VAR} using | |
1980 | @code{putsym}. Again, a pointer and its type (which must be @code{VAR}) is | |
1981 | returned to @code{yyparse}.@refill | |
1982 | ||
1983 | No change is needed in the handling of numeric values and arithmetic | |
1984 | operators in @code{yylex}. | |
1985 | ||
1986 | @smallexample | |
1987 | @group | |
1988 | #include <ctype.h> | |
1989 | yylex () | |
1990 | @{ | |
1991 | int c; | |
1992 | ||
1993 | /* Ignore whitespace, get first nonwhite character. */ | |
1994 | while ((c = getchar ()) == ' ' || c == '\t'); | |
1995 | ||
1996 | if (c == EOF) | |
1997 | return 0; | |
1998 | @end group | |
1999 | ||
2000 | @group | |
2001 | /* Char starts a number => parse the number. */ | |
2002 | if (c == '.' || isdigit (c)) | |
2003 | @{ | |
2004 | ungetc (c, stdin); | |
2005 | scanf ("%lf", &yylval.val); | |
2006 | return NUM; | |
2007 | @} | |
2008 | @end group | |
2009 | ||
2010 | @group | |
2011 | /* Char starts an identifier => read the name. */ | |
2012 | if (isalpha (c)) | |
2013 | @{ | |
2014 | symrec *s; | |
2015 | static char *symbuf = 0; | |
2016 | static int length = 0; | |
2017 | int i; | |
2018 | @end group | |
2019 | ||
2020 | @group | |
2021 | /* Initially make the buffer long enough | |
2022 | for a 40-character symbol name. */ | |
2023 | if (length == 0) | |
2024 | length = 40, symbuf = (char *)malloc (length + 1); | |
2025 | ||
2026 | i = 0; | |
2027 | do | |
2028 | @end group | |
2029 | @group | |
2030 | @{ | |
2031 | /* If buffer is full, make it bigger. */ | |
2032 | if (i == length) | |
2033 | @{ | |
2034 | length *= 2; | |
2035 | symbuf = (char *)realloc (symbuf, length + 1); | |
2036 | @} | |
2037 | /* Add this character to the buffer. */ | |
2038 | symbuf[i++] = c; | |
2039 | /* Get another character. */ | |
2040 | c = getchar (); | |
2041 | @} | |
2042 | @end group | |
2043 | @group | |
2044 | while (c != EOF && isalnum (c)); | |
2045 | ||
2046 | ungetc (c, stdin); | |
2047 | symbuf[i] = '\0'; | |
2048 | @end group | |
2049 | ||
2050 | @group | |
2051 | s = getsym (symbuf); | |
2052 | if (s == 0) | |
2053 | s = putsym (symbuf, VAR); | |
2054 | yylval.tptr = s; | |
2055 | return s->type; | |
2056 | @} | |
2057 | ||
2058 | /* Any other character is a token by itself. */ | |
2059 | return c; | |
2060 | @} | |
2061 | @end group | |
2062 | @end smallexample | |
2063 | ||
2064 | This program is both powerful and flexible. You may easily add new | |
2065 | functions, and it is a simple job to modify this code to install predefined | |
2066 | variables such as @code{pi} or @code{e} as well. | |
2067 | ||
2068 | @node Exercises, , Multi-function Calc, Examples | |
2069 | @section Exercises | |
2070 | @cindex exercises | |
2071 | ||
2072 | @enumerate | |
2073 | @item | |
2074 | Add some new functions from @file{math.h} to the initialization list. | |
2075 | ||
2076 | @item | |
2077 | Add another array that contains constants and their values. Then | |
2078 | modify @code{init_table} to add these constants to the symbol table. | |
2079 | It will be easiest to give the constants type @code{VAR}. | |
2080 | ||
2081 | @item | |
2082 | Make the program report an error if the user refers to an | |
2083 | uninitialized variable in any way except to store a value in it. | |
2084 | @end enumerate | |
2085 | ||
2086 | @node Grammar File, Interface, Examples, Top | |
2087 | @chapter Bison Grammar Files | |
2088 | ||
2089 | Bison takes as input a context-free grammar specification and produces a | |
2090 | C-language function that recognizes correct instances of the grammar. | |
2091 | ||
2092 | The Bison grammar input file conventionally has a name ending in @samp{.y}. | |
2093 | ||
2094 | @menu | |
2095 | * Grammar Outline:: Overall layout of the grammar file. | |
2096 | * Symbols:: Terminal and nonterminal symbols. | |
2097 | * Rules:: How to write grammar rules. | |
2098 | * Recursion:: Writing recursive rules. | |
2099 | * Semantics:: Semantic values and actions. | |
2100 | * Declarations:: All kinds of Bison declarations are described here. | |
2101 | * Multiple Parsers:: Putting more than one Bison parser in one program. | |
2102 | @end menu | |
2103 | ||
2104 | @node Grammar Outline, Symbols, , Grammar File | |
2105 | @section Outline of a Bison Grammar | |
2106 | ||
2107 | A Bison grammar file has four main sections, shown here with the | |
2108 | appropriate delimiters: | |
2109 | ||
2110 | @example | |
2111 | %@{ | |
2112 | @var{C declarations} | |
2113 | %@} | |
2114 | ||
2115 | @var{Bison declarations} | |
2116 | ||
2117 | %% | |
2118 | @var{Grammar rules} | |
2119 | %% | |
2120 | ||
2121 | @var{Additional C code} | |
2122 | @end example | |
2123 | ||
2124 | Comments enclosed in @samp{/* @dots{} */} may appear in any of the sections. | |
2125 | ||
2126 | @menu | |
2127 | * C Declarations:: Syntax and usage of the C declarations section. | |
2128 | * Bison Declarations:: Syntax and usage of the Bison declarations section. | |
2129 | * Grammar Rules:: Syntax and usage of the grammar rules section. | |
2130 | * C Code:: Syntax and usage of the additional C code section. | |
2131 | @end menu | |
2132 | ||
2133 | @node C Declarations, Bison Declarations, , Grammar Outline | |
2134 | @subsection The C Declarations Section | |
2135 | @cindex C declarations section | |
2136 | @cindex declarations, C | |
2137 | ||
2138 | The @var{C declarations} section contains macro definitions and | |
2139 | declarations of functions and variables that are used in the actions in the | |
2140 | grammar rules. These are copied to the beginning of the parser file so | |
2141 | that they precede the definition of @code{yyparse}. You can use | |
2142 | @samp{#include} to get the declarations from a header file. If you don't | |
2143 | need any C declarations, you may omit the @samp{%@{} and @samp{%@}} | |
2144 | delimiters that bracket this section. | |
2145 | ||
2146 | @node Bison Declarations, Grammar Rules, C Declarations, Grammar Outline | |
2147 | @subsection The Bison Declarations Section | |
2148 | @cindex Bison declarations (introduction) | |
2149 | @cindex declarations, Bison (introduction) | |
2150 | ||
2151 | The @var{Bison declarations} section contains declarations that define | |
2152 | terminal and nonterminal symbols, specify precedence, and so on. | |
2153 | In some simple grammars you may not need any declarations. | |
2154 | @xref{Declarations, ,Bison Declarations}. | |
2155 | ||
2156 | @node Grammar Rules, C Code, Bison Declarations, Grammar Outline | |
2157 | @subsection The Grammar Rules Section | |
2158 | @cindex grammar rules section | |
2159 | @cindex rules section for grammar | |
2160 | ||
2161 | The @dfn{grammar rules} section contains one or more Bison grammar | |
2162 | rules, and nothing else. @xref{Rules, ,Syntax of Grammar Rules}. | |
2163 | ||
2164 | There must always be at least one grammar rule, and the first | |
2165 | @samp{%%} (which precedes the grammar rules) may never be omitted even | |
2166 | if it is the first thing in the file. | |
2167 | ||
2168 | @node C Code, , Grammar Rules, Grammar Outline | |
2169 | @subsection The Additional C Code Section | |
2170 | @cindex additional C code section | |
2171 | @cindex C code, section for additional | |
2172 | ||
2173 | The @var{additional C code} section is copied verbatim to the end of | |
2174 | the parser file, just as the @var{C declarations} section is copied to | |
2175 | the beginning. This is the most convenient place to put anything | |
2176 | that you want to have in the parser file but which need not come before | |
2177 | the definition of @code{yyparse}. For example, the definitions of | |
2178 | @code{yylex} and @code{yyerror} often go here. @xref{Interface, ,Parser C-Language Interface}. | |
2179 | ||
2180 | If the last section is empty, you may omit the @samp{%%} that separates it | |
2181 | from the grammar rules. | |
2182 | ||
2183 | The Bison parser itself contains many static variables whose names start | |
2184 | with @samp{yy} and many macros whose names start with @samp{YY}. It is a | |
2185 | good idea to avoid using any such names (except those documented in this | |
2186 | manual) in the additional C code section of the grammar file. | |
2187 | ||
2188 | @node Symbols, Rules, Grammar Outline, Grammar File | |
2189 | @section Symbols, Terminal and Nonterminal | |
2190 | @cindex nonterminal symbol | |
2191 | @cindex terminal symbol | |
2192 | @cindex token type | |
2193 | @cindex symbol | |
2194 | ||
2195 | @dfn{Symbols} in Bison grammars represent the grammatical classifications | |
2196 | of the language. | |
2197 | ||
2198 | A @dfn{terminal symbol} (also known as a @dfn{token type}) represents a | |
2199 | class of syntactically equivalent tokens. You use the symbol in grammar | |
2200 | rules to mean that a token in that class is allowed. The symbol is | |
2201 | represented in the Bison parser by a numeric code, and the @code{yylex} | |
2202 | function returns a token type code to indicate what kind of token has been | |
2203 | read. You don't need to know what the code value is; you can use the | |
2204 | symbol to stand for it. | |
2205 | ||
2206 | A @dfn{nonterminal symbol} stands for a class of syntactically equivalent | |
2207 | groupings. The symbol name is used in writing grammar rules. By convention, | |
2208 | it should be all lower case. | |
2209 | ||
2210 | Symbol names can contain letters, digits (not at the beginning), | |
2211 | underscores and periods. Periods make sense only in nonterminals. | |
2212 | ||
2213 | There are three ways of writing terminal symbols in the grammar: | |
2214 | ||
2215 | @itemize @bullet | |
2216 | @item | |
2217 | A @dfn{named token type} is written with an identifier, like an | |
2218 | identifier in C. By convention, it should be all upper case. Each | |
2219 | such name must be defined with a Bison declaration such as | |
2220 | @code{%token}. @xref{Token Decl, ,Token Type Names}. | |
2221 | ||
2222 | @item | |
2223 | @cindex character token | |
2224 | @cindex literal token | |
2225 | @cindex single-character literal | |
2226 | A @dfn{character token type} (or @dfn{literal character token}) is | |
2227 | written in the grammar using the same syntax used in C for character | |
2228 | constants; for example, @code{'+'} is a character token type. A | |
2229 | character token type doesn't need to be declared unless you need to | |
2230 | specify its semantic value data type (@pxref{Value Type, ,Data Types of | |
2231 | Semantic Values}), associativity, or precedence (@pxref{Precedence, | |
2232 | ,Operator Precedence}). | |
2233 | ||
2234 | By convention, a character token type is used only to represent a | |
2235 | token that consists of that particular character. Thus, the token | |
2236 | type @code{'+'} is used to represent the character @samp{+} as a | |
2237 | token. Nothing enforces this convention, but if you depart from it, | |
2238 | your program will confuse other readers. | |
2239 | ||
2240 | All the usual escape sequences used in character literals in C can be | |
2241 | used in Bison as well, but you must not use the null character as a | |
2242 | character literal because its ASCII code, zero, is the code @code{yylex} | |
2243 | returns for end-of-input (@pxref{Calling Convention, ,Calling Convention | |
2244 | for @code{yylex}}). | |
2245 | ||
2246 | @item | |
2247 | @cindex string token | |
2248 | @cindex literal string token | |
2249 | @cindex multi-character literal | |
2250 | A @dfn{literal string token} is written like a C string constant; for | |
2251 | example, @code{"<="} is a literal string token. A literal string token | |
2252 | doesn't need to be declared unless you need to specify its semantic | |
2253 | value data type (@pxref{Value Type}), associativity, precedence | |
2254 | (@pxref{Precedence}). | |
2255 | ||
2256 | You can associate the literal string token with a symbolic name as an | |
2257 | alias, using the @code{%token} declaration (@pxref{Token Decl, ,Token | |
2258 | Declarations}). If you don't do that, the lexical analyzer has to | |
2259 | retrieve the token number for the literal string token from the | |
2260 | @code{yytname} table (@pxref{Calling Convention}). | |
2261 | ||
2262 | @strong{WARNING}: literal string tokens do not work in Yacc. | |
2263 | ||
2264 | By convention, a literal string token is used only to represent a token | |
2265 | that consists of that particular string. Thus, you should use the token | |
2266 | type @code{"<="} to represent the string @samp{<=} as a token. Bison | |
2267 | does not enforces this convention, but if you depart from it, people who | |
2268 | read your program will be confused. | |
2269 | ||
2270 | All the escape sequences used in string literals in C can be used in | |
2271 | Bison as well. A literal string token must contain two or more | |
2272 | characters; for a token containing just one character, use a character | |
2273 | token (see above). | |
2274 | @end itemize | |
2275 | ||
2276 | How you choose to write a terminal symbol has no effect on its | |
2277 | grammatical meaning. That depends only on where it appears in rules and | |
2278 | on when the parser function returns that symbol. | |
2279 | ||
2280 | The value returned by @code{yylex} is always one of the terminal symbols | |
2281 | (or 0 for end-of-input). Whichever way you write the token type in the | |
2282 | grammar rules, you write it the same way in the definition of @code{yylex}. | |
2283 | The numeric code for a character token type is simply the ASCII code for | |
2284 | the character, so @code{yylex} can use the identical character constant to | |
2285 | generate the requisite code. Each named token type becomes a C macro in | |
2286 | the parser file, so @code{yylex} can use the name to stand for the code. | |
2287 | (This is why periods don't make sense in terminal symbols.) | |
2288 | @xref{Calling Convention, ,Calling Convention for @code{yylex}}. | |
2289 | ||
2290 | If @code{yylex} is defined in a separate file, you need to arrange for the | |
2291 | token-type macro definitions to be available there. Use the @samp{-d} | |
2292 | option when you run Bison, so that it will write these macro definitions | |
2293 | into a separate header file @file{@var{name}.tab.h} which you can include | |
2294 | in the other source files that need it. @xref{Invocation, ,Invoking Bison}. | |
2295 | ||
2296 | The symbol @code{error} is a terminal symbol reserved for error recovery | |
2297 | (@pxref{Error Recovery}); you shouldn't use it for any other purpose. | |
2298 | In particular, @code{yylex} should never return this value. | |
2299 | ||
2300 | @node Rules, Recursion, Symbols, Grammar File | |
2301 | @section Syntax of Grammar Rules | |
2302 | @cindex rule syntax | |
2303 | @cindex grammar rule syntax | |
2304 | @cindex syntax of grammar rules | |
2305 | ||
2306 | A Bison grammar rule has the following general form: | |
2307 | ||
2308 | @example | |
2309 | @group | |
2310 | @var{result}: @var{components}@dots{} | |
2311 | ; | |
2312 | @end group | |
2313 | @end example | |
2314 | ||
2315 | @noindent | |
2316 | where @var{result} is the nonterminal symbol that this rule describes | |
2317 | and @var{components} are various terminal and nonterminal symbols that | |
2318 | are put together by this rule (@pxref{Symbols}). | |
2319 | ||
2320 | For example, | |
2321 | ||
2322 | @example | |
2323 | @group | |
2324 | exp: exp '+' exp | |
2325 | ; | |
2326 | @end group | |
2327 | @end example | |
2328 | ||
2329 | @noindent | |
2330 | says that two groupings of type @code{exp}, with a @samp{+} token in between, | |
2331 | can be combined into a larger grouping of type @code{exp}. | |
2332 | ||
2333 | Whitespace in rules is significant only to separate symbols. You can add | |
2334 | extra whitespace as you wish. | |
2335 | ||
2336 | Scattered among the components can be @var{actions} that determine | |
2337 | the semantics of the rule. An action looks like this: | |
2338 | ||
2339 | @example | |
2340 | @{@var{C statements}@} | |
2341 | @end example | |
2342 | ||
2343 | @noindent | |
2344 | Usually there is only one action and it follows the components. | |
2345 | @xref{Actions}. | |
2346 | ||
2347 | @findex | | |
2348 | Multiple rules for the same @var{result} can be written separately or can | |
2349 | be joined with the vertical-bar character @samp{|} as follows: | |
2350 | ||
2351 | @ifinfo | |
2352 | @example | |
2353 | @var{result}: @var{rule1-components}@dots{} | |
2354 | | @var{rule2-components}@dots{} | |
2355 | @dots{} | |
2356 | ; | |
2357 | @end example | |
2358 | @end ifinfo | |
2359 | @iftex | |
2360 | @example | |
2361 | @group | |
2362 | @var{result}: @var{rule1-components}@dots{} | |
2363 | | @var{rule2-components}@dots{} | |
2364 | @dots{} | |
2365 | ; | |
2366 | @end group | |
2367 | @end example | |
2368 | @end iftex | |
2369 | ||
2370 | @noindent | |
2371 | They are still considered distinct rules even when joined in this way. | |
2372 | ||
2373 | If @var{components} in a rule is empty, it means that @var{result} can | |
2374 | match the empty string. For example, here is how to define a | |
2375 | comma-separated sequence of zero or more @code{exp} groupings: | |
2376 | ||
2377 | @example | |
2378 | @group | |
2379 | expseq: /* empty */ | |
2380 | | expseq1 | |
2381 | ; | |
2382 | @end group | |
2383 | ||
2384 | @group | |
2385 | expseq1: exp | |
2386 | | expseq1 ',' exp | |
2387 | ; | |
2388 | @end group | |
2389 | @end example | |
2390 | ||
2391 | @noindent | |
2392 | It is customary to write a comment @samp{/* empty */} in each rule | |
2393 | with no components. | |
2394 | ||
2395 | @node Recursion, Semantics, Rules, Grammar File | |
2396 | @section Recursive Rules | |
2397 | @cindex recursive rule | |
2398 | ||
2399 | A rule is called @dfn{recursive} when its @var{result} nonterminal appears | |
2400 | also on its right hand side. Nearly all Bison grammars need to use | |
2401 | recursion, because that is the only way to define a sequence of any number | |
2402 | of somethings. Consider this recursive definition of a comma-separated | |
2403 | sequence of one or more expressions: | |
2404 | ||
2405 | @example | |
2406 | @group | |
2407 | expseq1: exp | |
2408 | | expseq1 ',' exp | |
2409 | ; | |
2410 | @end group | |
2411 | @end example | |
2412 | ||
2413 | @cindex left recursion | |
2414 | @cindex right recursion | |
2415 | @noindent | |
2416 | Since the recursive use of @code{expseq1} is the leftmost symbol in the | |
2417 | right hand side, we call this @dfn{left recursion}. By contrast, here | |
2418 | the same construct is defined using @dfn{right recursion}: | |
2419 | ||
2420 | @example | |
2421 | @group | |
2422 | expseq1: exp | |
2423 | | exp ',' expseq1 | |
2424 | ; | |
2425 | @end group | |
2426 | @end example | |
2427 | ||
2428 | @noindent | |
2429 | Any kind of sequence can be defined using either left recursion or | |
2430 | right recursion, but you should always use left recursion, because it | |
2431 | can parse a sequence of any number of elements with bounded stack | |
2432 | space. Right recursion uses up space on the Bison stack in proportion | |
2433 | to the number of elements in the sequence, because all the elements | |
2434 | must be shifted onto the stack before the rule can be applied even | |
2435 | once. @xref{Algorithm, ,The Bison Parser Algorithm }, for | |
2436 | further explanation of this. | |
2437 | ||
2438 | @cindex mutual recursion | |
2439 | @dfn{Indirect} or @dfn{mutual} recursion occurs when the result of the | |
2440 | rule does not appear directly on its right hand side, but does appear | |
2441 | in rules for other nonterminals which do appear on its right hand | |
2442 | side. | |
2443 | ||
2444 | For example: | |
2445 | ||
2446 | @example | |
2447 | @group | |
2448 | expr: primary | |
2449 | | primary '+' primary | |
2450 | ; | |
2451 | @end group | |
2452 | ||
2453 | @group | |
2454 | primary: constant | |
2455 | | '(' expr ')' | |
2456 | ; | |
2457 | @end group | |
2458 | @end example | |
2459 | ||
2460 | @noindent | |
2461 | defines two mutually-recursive nonterminals, since each refers to the | |
2462 | other. | |
2463 | ||
2464 | @node Semantics, Declarations, Recursion, Grammar File | |
2465 | @section Defining Language Semantics | |
2466 | @cindex defining language semantics | |
2467 | @cindex language semantics, defining | |
2468 | ||
2469 | The grammar rules for a language determine only the syntax. The semantics | |
2470 | are determined by the semantic values associated with various tokens and | |
2471 | groupings, and by the actions taken when various groupings are recognized. | |
2472 | ||
2473 | For example, the calculator calculates properly because the value | |
2474 | associated with each expression is the proper number; it adds properly | |
2475 | because the action for the grouping @w{@samp{@var{x} + @var{y}}} is to add | |
2476 | the numbers associated with @var{x} and @var{y}. | |
2477 | ||
2478 | @menu | |
2479 | * Value Type:: Specifying one data type for all semantic values. | |
2480 | * Multiple Types:: Specifying several alternative data types. | |
2481 | * Actions:: An action is the semantic definition of a grammar rule. | |
2482 | * Action Types:: Specifying data types for actions to operate on. | |
2483 | * Mid-Rule Actions:: Most actions go at the end of a rule. | |
2484 | This says when, why and how to use the exceptional | |
2485 | action in the middle of a rule. | |
2486 | @end menu | |
2487 | ||
2488 | @node Value Type, Multiple Types, , Semantics | |
2489 | @subsection Data Types of Semantic Values | |
2490 | @cindex semantic value type | |
2491 | @cindex value type, semantic | |
2492 | @cindex data types of semantic values | |
2493 | @cindex default data type | |
2494 | ||
2495 | In a simple program it may be sufficient to use the same data type for | |
2496 | the semantic values of all language constructs. This was true in the | |
2497 | RPN and infix calculator examples (@pxref{RPN Calc, ,Reverse Polish Notation Calculator}). | |
2498 | ||
2499 | Bison's default is to use type @code{int} for all semantic values. To | |
2500 | specify some other type, define @code{YYSTYPE} as a macro, like this: | |
2501 | ||
2502 | @example | |
2503 | #define YYSTYPE double | |
2504 | @end example | |
2505 | ||
2506 | @noindent | |
2507 | This macro definition must go in the C declarations section of the grammar | |
2508 | file (@pxref{Grammar Outline, ,Outline of a Bison Grammar}). | |
2509 | ||
2510 | @node Multiple Types, Actions, Value Type, Semantics | |
2511 | @subsection More Than One Value Type | |
2512 | ||
2513 | In most programs, you will need different data types for different kinds | |
2514 | of tokens and groupings. For example, a numeric constant may need type | |
2515 | @code{int} or @code{long}, while a string constant needs type @code{char *}, | |
2516 | and an identifier might need a pointer to an entry in the symbol table. | |
2517 | ||
2518 | To use more than one data type for semantic values in one parser, Bison | |
2519 | requires you to do two things: | |
2520 | ||
2521 | @itemize @bullet | |
2522 | @item | |
2523 | Specify the entire collection of possible data types, with the | |
2524 | @code{%union} Bison declaration (@pxref{Union Decl, ,The Collection of Value Types}). | |
2525 | ||
2526 | @item | |
2527 | Choose one of those types for each symbol (terminal or nonterminal) | |
2528 | for which semantic values are used. This is done for tokens with the | |
2529 | @code{%token} Bison declaration (@pxref{Token Decl, ,Token Type Names}) and for groupings | |
2530 | with the @code{%type} Bison declaration (@pxref{Type Decl, ,Nonterminal Symbols}). | |
2531 | @end itemize | |
2532 | ||
2533 | @node Actions, Action Types, Multiple Types, Semantics | |
2534 | @subsection Actions | |
2535 | @cindex action | |
2536 | @vindex $$ | |
2537 | @vindex $@var{n} | |
2538 | ||
2539 | An action accompanies a syntactic rule and contains C code to be executed | |
2540 | each time an instance of that rule is recognized. The task of most actions | |
2541 | is to compute a semantic value for the grouping built by the rule from the | |
2542 | semantic values associated with tokens or smaller groupings. | |
2543 | ||
2544 | An action consists of C statements surrounded by braces, much like a | |
2545 | compound statement in C. It can be placed at any position in the rule; it | |
2546 | is executed at that position. Most rules have just one action at the end | |
2547 | of the rule, following all the components. Actions in the middle of a rule | |
2548 | are tricky and used only for special purposes (@pxref{Mid-Rule Actions, ,Actions in Mid-Rule}). | |
2549 | ||
2550 | The C code in an action can refer to the semantic values of the components | |
2551 | matched by the rule with the construct @code{$@var{n}}, which stands for | |
2552 | the value of the @var{n}th component. The semantic value for the grouping | |
2553 | being constructed is @code{$$}. (Bison translates both of these constructs | |
2554 | into array element references when it copies the actions into the parser | |
2555 | file.) | |
2556 | ||
2557 | Here is a typical example: | |
2558 | ||
2559 | @example | |
2560 | @group | |
2561 | exp: @dots{} | |
2562 | | exp '+' exp | |
2563 | @{ $$ = $1 + $3; @} | |
2564 | @end group | |
2565 | @end example | |
2566 | ||
2567 | @noindent | |
2568 | This rule constructs an @code{exp} from two smaller @code{exp} groupings | |
2569 | connected by a plus-sign token. In the action, @code{$1} and @code{$3} | |
2570 | refer to the semantic values of the two component @code{exp} groupings, | |
2571 | which are the first and third symbols on the right hand side of the rule. | |
2572 | The sum is stored into @code{$$} so that it becomes the semantic value of | |
2573 | the addition-expression just recognized by the rule. If there were a | |
2574 | useful semantic value associated with the @samp{+} token, it could be | |
2575 | referred to as @code{$2}.@refill | |
2576 | ||
2577 | @cindex default action | |
2578 | If you don't specify an action for a rule, Bison supplies a default: | |
2579 | @w{@code{$$ = $1}.} Thus, the value of the first symbol in the rule becomes | |
2580 | the value of the whole rule. Of course, the default rule is valid only | |
2581 | if the two data types match. There is no meaningful default action for | |
2582 | an empty rule; every empty rule must have an explicit action unless the | |
2583 | rule's value does not matter. | |
2584 | ||
2585 | @code{$@var{n}} with @var{n} zero or negative is allowed for reference | |
2586 | to tokens and groupings on the stack @emph{before} those that match the | |
2587 | current rule. This is a very risky practice, and to use it reliably | |
2588 | you must be certain of the context in which the rule is applied. Here | |
2589 | is a case in which you can use this reliably: | |
2590 | ||
2591 | @example | |
2592 | @group | |
2593 | foo: expr bar '+' expr @{ @dots{} @} | |
2594 | | expr bar '-' expr @{ @dots{} @} | |
2595 | ; | |
2596 | @end group | |
2597 | ||
2598 | @group | |
2599 | bar: /* empty */ | |
2600 | @{ previous_expr = $0; @} | |
2601 | ; | |
2602 | @end group | |
2603 | @end example | |
2604 | ||
2605 | As long as @code{bar} is used only in the fashion shown here, @code{$0} | |
2606 | always refers to the @code{expr} which precedes @code{bar} in the | |
2607 | definition of @code{foo}. | |
2608 | ||
2609 | @node Action Types, Mid-Rule Actions, Actions, Semantics | |
2610 | @subsection Data Types of Values in Actions | |
2611 | @cindex action data types | |
2612 | @cindex data types in actions | |
2613 | ||
2614 | If you have chosen a single data type for semantic values, the @code{$$} | |
2615 | and @code{$@var{n}} constructs always have that data type. | |
2616 | ||
2617 | If you have used @code{%union} to specify a variety of data types, then you | |
2618 | must declare a choice among these types for each terminal or nonterminal | |
2619 | symbol that can have a semantic value. Then each time you use @code{$$} or | |
2620 | @code{$@var{n}}, its data type is determined by which symbol it refers to | |
2621 | in the rule. In this example,@refill | |
2622 | ||
2623 | @example | |
2624 | @group | |
2625 | exp: @dots{} | |
2626 | | exp '+' exp | |
2627 | @{ $$ = $1 + $3; @} | |
2628 | @end group | |
2629 | @end example | |
2630 | ||
2631 | @noindent | |
2632 | @code{$1} and @code{$3} refer to instances of @code{exp}, so they all | |
2633 | have the data type declared for the nonterminal symbol @code{exp}. If | |
2634 | @code{$2} were used, it would have the data type declared for the | |
2635 | terminal symbol @code{'+'}, whatever that might be.@refill | |
2636 | ||
2637 | Alternatively, you can specify the data type when you refer to the value, | |
2638 | by inserting @samp{<@var{type}>} after the @samp{$} at the beginning of the | |
2639 | reference. For example, if you have defined types as shown here: | |
2640 | ||
2641 | @example | |
2642 | @group | |
2643 | %union @{ | |
2644 | int itype; | |
2645 | double dtype; | |
2646 | @} | |
2647 | @end group | |
2648 | @end example | |
2649 | ||
2650 | @noindent | |
2651 | then you can write @code{$<itype>1} to refer to the first subunit of the | |
2652 | rule as an integer, or @code{$<dtype>1} to refer to it as a double. | |
2653 | ||
2654 | @node Mid-Rule Actions, , Action Types, Semantics | |
2655 | @subsection Actions in Mid-Rule | |
2656 | @cindex actions in mid-rule | |
2657 | @cindex mid-rule actions | |
2658 | ||
2659 | Occasionally it is useful to put an action in the middle of a rule. | |
2660 | These actions are written just like usual end-of-rule actions, but they | |
2661 | are executed before the parser even recognizes the following components. | |
2662 | ||
2663 | A mid-rule action may refer to the components preceding it using | |
2664 | @code{$@var{n}}, but it may not refer to subsequent components because | |
2665 | it is run before they are parsed. | |
2666 | ||
2667 | The mid-rule action itself counts as one of the components of the rule. | |
2668 | This makes a difference when there is another action later in the same rule | |
2669 | (and usually there is another at the end): you have to count the actions | |
2670 | along with the symbols when working out which number @var{n} to use in | |
2671 | @code{$@var{n}}. | |
2672 | ||
2673 | The mid-rule action can also have a semantic value. The action can set | |
2674 | its value with an assignment to @code{$$}, and actions later in the rule | |
2675 | can refer to the value using @code{$@var{n}}. Since there is no symbol | |
2676 | to name the action, there is no way to declare a data type for the value | |
2677 | in advance, so you must use the @samp{$<@dots{}>} construct to specify a | |
2678 | data type each time you refer to this value. | |
2679 | ||
2680 | There is no way to set the value of the entire rule with a mid-rule | |
2681 | action, because assignments to @code{$$} do not have that effect. The | |
2682 | only way to set the value for the entire rule is with an ordinary action | |
2683 | at the end of the rule. | |
2684 | ||
2685 | Here is an example from a hypothetical compiler, handling a @code{let} | |
2686 | statement that looks like @samp{let (@var{variable}) @var{statement}} and | |
2687 | serves to create a variable named @var{variable} temporarily for the | |
2688 | duration of @var{statement}. To parse this construct, we must put | |
2689 | @var{variable} into the symbol table while @var{statement} is parsed, then | |
2690 | remove it afterward. Here is how it is done: | |
2691 | ||
2692 | @example | |
2693 | @group | |
2694 | stmt: LET '(' var ')' | |
2695 | @{ $<context>$ = push_context (); | |
2696 | declare_variable ($3); @} | |
2697 | stmt @{ $$ = $6; | |
2698 | pop_context ($<context>5); @} | |
2699 | @end group | |
2700 | @end example | |
2701 | ||
2702 | @noindent | |
2703 | As soon as @samp{let (@var{variable})} has been recognized, the first | |
2704 | action is run. It saves a copy of the current semantic context (the | |
2705 | list of accessible variables) as its semantic value, using alternative | |
2706 | @code{context} in the data-type union. Then it calls | |
2707 | @code{declare_variable} to add the new variable to that list. Once the | |
2708 | first action is finished, the embedded statement @code{stmt} can be | |
2709 | parsed. Note that the mid-rule action is component number 5, so the | |
2710 | @samp{stmt} is component number 6. | |
2711 | ||
2712 | After the embedded statement is parsed, its semantic value becomes the | |
2713 | value of the entire @code{let}-statement. Then the semantic value from the | |
2714 | earlier action is used to restore the prior list of variables. This | |
2715 | removes the temporary @code{let}-variable from the list so that it won't | |
2716 | appear to exist while the rest of the program is parsed. | |
2717 | ||
2718 | Taking action before a rule is completely recognized often leads to | |
2719 | conflicts since the parser must commit to a parse in order to execute the | |
2720 | action. For example, the following two rules, without mid-rule actions, | |
2721 | can coexist in a working parser because the parser can shift the open-brace | |
2722 | token and look at what follows before deciding whether there is a | |
2723 | declaration or not: | |
2724 | ||
2725 | @example | |
2726 | @group | |
2727 | compound: '@{' declarations statements '@}' | |
2728 | | '@{' statements '@}' | |
2729 | ; | |
2730 | @end group | |
2731 | @end example | |
2732 | ||
2733 | @noindent | |
2734 | But when we add a mid-rule action as follows, the rules become nonfunctional: | |
2735 | ||
2736 | @example | |
2737 | @group | |
2738 | compound: @{ prepare_for_local_variables (); @} | |
2739 | '@{' declarations statements '@}' | |
2740 | @end group | |
2741 | @group | |
2742 | | '@{' statements '@}' | |
2743 | ; | |
2744 | @end group | |
2745 | @end example | |
2746 | ||
2747 | @noindent | |
2748 | Now the parser is forced to decide whether to run the mid-rule action | |
2749 | when it has read no farther than the open-brace. In other words, it | |
2750 | must commit to using one rule or the other, without sufficient | |
2751 | information to do it correctly. (The open-brace token is what is called | |
2752 | the @dfn{look-ahead} token at this time, since the parser is still | |
2753 | deciding what to do about it. @xref{Look-Ahead, ,Look-Ahead Tokens}.) | |
2754 | ||
2755 | You might think that you could correct the problem by putting identical | |
2756 | actions into the two rules, like this: | |
2757 | ||
2758 | @example | |
2759 | @group | |
2760 | compound: @{ prepare_for_local_variables (); @} | |
2761 | '@{' declarations statements '@}' | |
2762 | | @{ prepare_for_local_variables (); @} | |
2763 | '@{' statements '@}' | |
2764 | ; | |
2765 | @end group | |
2766 | @end example | |
2767 | ||
2768 | @noindent | |
2769 | But this does not help, because Bison does not realize that the two actions | |
2770 | are identical. (Bison never tries to understand the C code in an action.) | |
2771 | ||
2772 | If the grammar is such that a declaration can be distinguished from a | |
2773 | statement by the first token (which is true in C), then one solution which | |
2774 | does work is to put the action after the open-brace, like this: | |
2775 | ||
2776 | @example | |
2777 | @group | |
2778 | compound: '@{' @{ prepare_for_local_variables (); @} | |
2779 | declarations statements '@}' | |
2780 | | '@{' statements '@}' | |
2781 | ; | |
2782 | @end group | |
2783 | @end example | |
2784 | ||
2785 | @noindent | |
2786 | Now the first token of the following declaration or statement, | |
2787 | which would in any case tell Bison which rule to use, can still do so. | |
2788 | ||
2789 | Another solution is to bury the action inside a nonterminal symbol which | |
2790 | serves as a subroutine: | |
2791 | ||
2792 | @example | |
2793 | @group | |
2794 | subroutine: /* empty */ | |
2795 | @{ prepare_for_local_variables (); @} | |
2796 | ; | |
2797 | ||
2798 | @end group | |
2799 | ||
2800 | @group | |
2801 | compound: subroutine | |
2802 | '@{' declarations statements '@}' | |
2803 | | subroutine | |
2804 | '@{' statements '@}' | |
2805 | ; | |
2806 | @end group | |
2807 | @end example | |
2808 | ||
2809 | @noindent | |
2810 | Now Bison can execute the action in the rule for @code{subroutine} without | |
2811 | deciding which rule for @code{compound} it will eventually use. Note that | |
2812 | the action is now at the end of its rule. Any mid-rule action can be | |
2813 | converted to an end-of-rule action in this way, and this is what Bison | |
2814 | actually does to implement mid-rule actions. | |
2815 | ||
2816 | @node Declarations, Multiple Parsers, Semantics, Grammar File | |
2817 | @section Bison Declarations | |
2818 | @cindex declarations, Bison | |
2819 | @cindex Bison declarations | |
2820 | ||
2821 | The @dfn{Bison declarations} section of a Bison grammar defines the symbols | |
2822 | used in formulating the grammar and the data types of semantic values. | |
2823 | @xref{Symbols}. | |
2824 | ||
2825 | All token type names (but not single-character literal tokens such as | |
2826 | @code{'+'} and @code{'*'}) must be declared. Nonterminal symbols must be | |
2827 | declared if you need to specify which data type to use for the semantic | |
2828 | value (@pxref{Multiple Types, ,More Than One Value Type}). | |
2829 | ||
2830 | The first rule in the file also specifies the start symbol, by default. | |
2831 | If you want some other symbol to be the start symbol, you must declare | |
2832 | it explicitly (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}). | |
2833 | ||
2834 | @menu | |
2835 | * Token Decl:: Declaring terminal symbols. | |
2836 | * Precedence Decl:: Declaring terminals with precedence and associativity. | |
2837 | * Union Decl:: Declaring the set of all semantic value types. | |
2838 | * Type Decl:: Declaring the choice of type for a nonterminal symbol. | |
2839 | * Expect Decl:: Suppressing warnings about shift/reduce conflicts. | |
2840 | * Start Decl:: Specifying the start symbol. | |
2841 | * Pure Decl:: Requesting a reentrant parser. | |
2842 | * Decl Summary:: Table of all Bison declarations. | |
2843 | @end menu | |
2844 | ||
2845 | @node Token Decl, Precedence Decl, , Declarations | |
2846 | @subsection Token Type Names | |
2847 | @cindex declaring token type names | |
2848 | @cindex token type names, declaring | |
2849 | @cindex declaring literal string tokens | |
2850 | @findex %token | |
2851 | ||
2852 | The basic way to declare a token type name (terminal symbol) is as follows: | |
2853 | ||
2854 | @example | |
2855 | %token @var{name} | |
2856 | @end example | |
2857 | ||
2858 | Bison will convert this into a @code{#define} directive in | |
2859 | the parser, so that the function @code{yylex} (if it is in this file) | |
2860 | can use the name @var{name} to stand for this token type's code. | |
2861 | ||
2862 | Alternatively, you can use @code{%left}, @code{%right}, or @code{%nonassoc} | |
2863 | instead of @code{%token}, if you wish to specify precedence. | |
2864 | @xref{Precedence Decl, ,Operator Precedence}. | |
2865 | ||
2866 | You can explicitly specify the numeric code for a token type by appending | |
2867 | an integer value in the field immediately following the token name: | |
2868 | ||
2869 | @example | |
2870 | %token NUM 300 | |
2871 | @end example | |
2872 | ||
2873 | @noindent | |
2874 | It is generally best, however, to let Bison choose the numeric codes for | |
2875 | all token types. Bison will automatically select codes that don't conflict | |
2876 | with each other or with ASCII characters. | |
2877 | ||
2878 | In the event that the stack type is a union, you must augment the | |
2879 | @code{%token} or other token declaration to include the data type | |
2880 | alternative delimited by angle-brackets (@pxref{Multiple Types, ,More Than One Value Type}). | |
2881 | ||
2882 | For example: | |
2883 | ||
2884 | @example | |
2885 | @group | |
2886 | %union @{ /* define stack type */ | |
2887 | double val; | |
2888 | symrec *tptr; | |
2889 | @} | |
2890 | %token <val> NUM /* define token NUM and its type */ | |
2891 | @end group | |
2892 | @end example | |
2893 | ||
2894 | You can associate a literal string token with a token type name by | |
2895 | writing the literal string at the end of a @code{%token} | |
2896 | declaration which declares the name. For example: | |
2897 | ||
2898 | @example | |
2899 | %token arrow "=>" | |
2900 | @end example | |
2901 | ||
2902 | @noindent | |
2903 | For example, a grammar for the C language might specify these names with | |
2904 | equivalent literal string tokens: | |
2905 | ||
2906 | @example | |
2907 | %token <operator> OR "||" | |
2908 | %token <operator> LE 134 "<=" | |
2909 | %left OR "<=" | |
2910 | @end example | |
2911 | ||
2912 | @noindent | |
2913 | Once you equate the literal string and the token name, you can use them | |
2914 | interchangeably in further declarations or the grammar rules. The | |
2915 | @code{yylex} function can use the token name or the literal string to | |
2916 | obtain the token type code number (@pxref{Calling Convention}). | |
2917 | ||
2918 | @node Precedence Decl, Union Decl, Token Decl, Declarations | |
2919 | @subsection Operator Precedence | |
2920 | @cindex precedence declarations | |
2921 | @cindex declaring operator precedence | |
2922 | @cindex operator precedence, declaring | |
2923 | ||
2924 | Use the @code{%left}, @code{%right} or @code{%nonassoc} declaration to | |
2925 | declare a token and specify its precedence and associativity, all at | |
2926 | once. These are called @dfn{precedence declarations}. | |
2927 | @xref{Precedence, ,Operator Precedence}, for general information on operator precedence. | |
2928 | ||
2929 | The syntax of a precedence declaration is the same as that of | |
2930 | @code{%token}: either | |
2931 | ||
2932 | @example | |
2933 | %left @var{symbols}@dots{} | |
2934 | @end example | |
2935 | ||
2936 | @noindent | |
2937 | or | |
2938 | ||
2939 | @example | |
2940 | %left <@var{type}> @var{symbols}@dots{} | |
2941 | @end example | |
2942 | ||
2943 | And indeed any of these declarations serves the purposes of @code{%token}. | |
2944 | But in addition, they specify the associativity and relative precedence for | |
2945 | all the @var{symbols}: | |
2946 | ||
2947 | @itemize @bullet | |
2948 | @item | |
2949 | The associativity of an operator @var{op} determines how repeated uses | |
2950 | of the operator nest: whether @samp{@var{x} @var{op} @var{y} @var{op} | |
2951 | @var{z}} is parsed by grouping @var{x} with @var{y} first or by | |
2952 | grouping @var{y} with @var{z} first. @code{%left} specifies | |
2953 | left-associativity (grouping @var{x} with @var{y} first) and | |
2954 | @code{%right} specifies right-associativity (grouping @var{y} with | |
2955 | @var{z} first). @code{%nonassoc} specifies no associativity, which | |
2956 | means that @samp{@var{x} @var{op} @var{y} @var{op} @var{z}} is | |
2957 | considered a syntax error. | |
2958 | ||
2959 | @item | |
2960 | The precedence of an operator determines how it nests with other operators. | |
2961 | All the tokens declared in a single precedence declaration have equal | |
2962 | precedence and nest together according to their associativity. | |
2963 | When two tokens declared in different precedence declarations associate, | |
2964 | the one declared later has the higher precedence and is grouped first. | |
2965 | @end itemize | |
2966 | ||
2967 | @node Union Decl, Type Decl, Precedence Decl, Declarations | |
2968 | @subsection The Collection of Value Types | |
2969 | @cindex declaring value types | |
2970 | @cindex value types, declaring | |
2971 | @findex %union | |
2972 | ||
2973 | The @code{%union} declaration specifies the entire collection of possible | |
2974 | data types for semantic values. The keyword @code{%union} is followed by a | |
2975 | pair of braces containing the same thing that goes inside a @code{union} in | |
2976 | C. | |
2977 | ||
2978 | For example: | |
2979 | ||
2980 | @example | |
2981 | @group | |
2982 | %union @{ | |
2983 | double val; | |
2984 | symrec *tptr; | |
2985 | @} | |
2986 | @end group | |
2987 | @end example | |
2988 | ||
2989 | @noindent | |
2990 | This says that the two alternative types are @code{double} and @code{symrec | |
2991 | *}. They are given names @code{val} and @code{tptr}; these names are used | |
2992 | in the @code{%token} and @code{%type} declarations to pick one of the types | |
2993 | for a terminal or nonterminal symbol (@pxref{Type Decl, ,Nonterminal Symbols}). | |
2994 | ||
2995 | Note that, unlike making a @code{union} declaration in C, you do not write | |
2996 | a semicolon after the closing brace. | |
2997 | ||
2998 | @node Type Decl, Expect Decl, Union Decl, Declarations | |
2999 | @subsection Nonterminal Symbols | |
3000 | @cindex declaring value types, nonterminals | |
3001 | @cindex value types, nonterminals, declaring | |
3002 | @findex %type | |
3003 | ||
3004 | @noindent | |
3005 | When you use @code{%union} to specify multiple value types, you must | |
3006 | declare the value type of each nonterminal symbol for which values are | |
3007 | used. This is done with a @code{%type} declaration, like this: | |
3008 | ||
3009 | @example | |
3010 | %type <@var{type}> @var{nonterminal}@dots{} | |
3011 | @end example | |
3012 | ||
3013 | @noindent | |
3014 | Here @var{nonterminal} is the name of a nonterminal symbol, and @var{type} | |
3015 | is the name given in the @code{%union} to the alternative that you want | |
3016 | (@pxref{Union Decl, ,The Collection of Value Types}). You can give any number of nonterminal symbols in | |
3017 | the same @code{%type} declaration, if they have the same value type. Use | |
3018 | spaces to separate the symbol names. | |
3019 | ||
3020 | You can also declare the value type of a terminal symbol. To do this, | |
3021 | use the same @code{<@var{type}>} construction in a declaration for the | |
3022 | terminal symbol. All kinds of token declarations allow | |
3023 | @code{<@var{type}>}. | |
3024 | ||
3025 | @node Expect Decl, Start Decl, Type Decl, Declarations | |
3026 | @subsection Suppressing Conflict Warnings | |
3027 | @cindex suppressing conflict warnings | |
3028 | @cindex preventing warnings about conflicts | |
3029 | @cindex warnings, preventing | |
3030 | @cindex conflicts, suppressing warnings of | |
3031 | @findex %expect | |
3032 | ||
3033 | Bison normally warns if there are any conflicts in the grammar | |
3034 | (@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars have harmless shift/reduce | |
3035 | conflicts which are resolved in a predictable way and would be difficult to | |
3036 | eliminate. It is desirable to suppress the warning about these conflicts | |
3037 | unless the number of conflicts changes. You can do this with the | |
3038 | @code{%expect} declaration. | |
3039 | ||
3040 | The declaration looks like this: | |
3041 | ||
3042 | @example | |
3043 | %expect @var{n} | |
3044 | @end example | |
3045 | ||
3046 | Here @var{n} is a decimal integer. The declaration says there should be no | |
3047 | warning if there are @var{n} shift/reduce conflicts and no reduce/reduce | |
3048 | conflicts. The usual warning is given if there are either more or fewer | |
3049 | conflicts, or if there are any reduce/reduce conflicts. | |
3050 | ||
3051 | In general, using @code{%expect} involves these steps: | |
3052 | ||
3053 | @itemize @bullet | |
3054 | @item | |
3055 | Compile your grammar without @code{%expect}. Use the @samp{-v} option | |
3056 | to get a verbose list of where the conflicts occur. Bison will also | |
3057 | print the number of conflicts. | |
3058 | ||
3059 | @item | |
3060 | Check each of the conflicts to make sure that Bison's default | |
3061 | resolution is what you really want. If not, rewrite the grammar and | |
3062 | go back to the beginning. | |
3063 | ||
3064 | @item | |
3065 | Add an @code{%expect} declaration, copying the number @var{n} from the | |
3066 | number which Bison printed. | |
3067 | @end itemize | |
3068 | ||
3069 | Now Bison will stop annoying you about the conflicts you have checked, but | |
3070 | it will warn you again if changes in the grammar result in additional | |
3071 | conflicts. | |
3072 | ||
3073 | @node Start Decl, Pure Decl, Expect Decl, Declarations | |
3074 | @subsection The Start-Symbol | |
3075 | @cindex declaring the start symbol | |
3076 | @cindex start symbol, declaring | |
3077 | @cindex default start symbol | |
3078 | @findex %start | |
3079 | ||
3080 | Bison assumes by default that the start symbol for the grammar is the first | |
3081 | nonterminal specified in the grammar specification section. The programmer | |
3082 | may override this restriction with the @code{%start} declaration as follows: | |
3083 | ||
3084 | @example | |
3085 | %start @var{symbol} | |
3086 | @end example | |
3087 | ||
3088 | @node Pure Decl, Decl Summary, Start Decl, Declarations | |
3089 | @subsection A Pure (Reentrant) Parser | |
3090 | @cindex reentrant parser | |
3091 | @cindex pure parser | |
3092 | @findex %pure_parser | |
3093 | ||
3094 | A @dfn{reentrant} program is one which does not alter in the course of | |
3095 | execution; in other words, it consists entirely of @dfn{pure} (read-only) | |
3096 | code. Reentrancy is important whenever asynchronous execution is possible; | |
3097 | for example, a nonreentrant program may not be safe to call from a signal | |
3098 | handler. In systems with multiple threads of control, a nonreentrant | |
3099 | program must be called only within interlocks. | |
3100 | ||
3101 | The Bison parser is not normally a reentrant program, because it uses | |
3102 | statically allocated variables for communication with @code{yylex}. These | |
3103 | variables include @code{yylval} and @code{yylloc}. | |
3104 | ||
3105 | The Bison declaration @code{%pure_parser} says that you want the parser | |
3106 | to be reentrant. It looks like this: | |
3107 | ||
3108 | @example | |
3109 | %pure_parser | |
3110 | @end example | |
3111 | ||
3112 | The effect is that the two communication variables become local | |
3113 | variables in @code{yyparse}, and a different calling convention is used | |
3114 | for the lexical analyzer function @code{yylex}. @xref{Pure Calling, | |
3115 | ,Calling Conventions for Pure Parsers}, for the details of this. The | |
3116 | variable @code{yynerrs} also becomes local in @code{yyparse} | |
3117 | (@pxref{Error Reporting, ,The Error Reporting Function @code{yyerror}}). | |
3118 | The convention for calling @code{yyparse} itself is unchanged. | |
3119 | ||
3120 | @node Decl Summary, , Pure Decl, Declarations | |
3121 | @subsection Bison Declaration Summary | |
3122 | @cindex Bison declaration summary | |
3123 | @cindex declaration summary | |
3124 | @cindex summary, Bison declaration | |
3125 | ||
3126 | Here is a summary of all Bison declarations: | |
3127 | ||
3128 | @table @code | |
3129 | @item %union | |
3130 | Declare the collection of data types that semantic values may have | |
3131 | (@pxref{Union Decl, ,The Collection of Value Types}). | |
3132 | ||
3133 | @item %token | |
3134 | Declare a terminal symbol (token type name) with no precedence | |
3135 | or associativity specified (@pxref{Token Decl, ,Token Type Names}). | |
3136 | ||
3137 | @item %right | |
3138 | Declare a terminal symbol (token type name) that is right-associative | |
3139 | (@pxref{Precedence Decl, ,Operator Precedence}). | |
3140 | ||
3141 | @item %left | |
3142 | Declare a terminal symbol (token type name) that is left-associative | |
3143 | (@pxref{Precedence Decl, ,Operator Precedence}). | |
3144 | ||
3145 | @item %nonassoc | |
3146 | Declare a terminal symbol (token type name) that is nonassociative | |
3147 | (using it in a way that would be associative is a syntax error) | |
3148 | (@pxref{Precedence Decl, ,Operator Precedence}). | |
3149 | ||
3150 | @item %type | |
3151 | Declare the type of semantic values for a nonterminal symbol | |
3152 | (@pxref{Type Decl, ,Nonterminal Symbols}). | |
3153 | ||
3154 | @item %start | |
3155 | Specify the grammar's start symbol (@pxref{Start Decl, ,The Start-Symbol}). | |
3156 | ||
3157 | @item %expect | |
3158 | Declare the expected number of shift-reduce conflicts | |
3159 | (@pxref{Expect Decl, ,Suppressing Conflict Warnings}). | |
3160 | ||
3161 | @item %pure_parser | |
3162 | Request a pure (reentrant) parser program (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}). | |
3163 | ||
3164 | @item %no_lines | |
3165 | Don't generate any @code{#line} preprocessor commands in the parser | |
3166 | file. Ordinarily Bison writes these commands in the parser file so that | |
3167 | the C compiler and debuggers will associate errors and object code with | |
3168 | your source file (the grammar file). This directive causes them to | |
3169 | associate errors with the parser file, treating it an independent source | |
3170 | file in its own right. | |
3171 | ||
3172 | @item %raw | |
3173 | The output file @file{@var{name}.h} normally defines the tokens with | |
3174 | Yacc-compatible token numbers. If this option is specified, the | |
3175 | internal Bison numbers are used instead. (Yacc-compatible numbers start | |
3176 | at 257 except for single character tokens; Bison assigns token numbers | |
3177 | sequentially for all tokens starting at 3.) | |
3178 | ||
3179 | @item %token_table | |
3180 | Generate an array of token names in the parser file. The name of the | |
3181 | array is @code{yytname}; @code{yytname[@var{i}]} is the name of the | |
3182 | token whose internal Bison token code number is @var{i}. The first three | |
3183 | elements of @code{yytname} are always @code{"$"}, @code{"error"}, and | |
3184 | @code{"$illegal"}; after these come the symbols defined in the grammar | |
3185 | file. | |
3186 | ||
3187 | For single-character literal tokens and literal string tokens, the name | |
3188 | in the table includes the single-quote or double-quote characters: for | |
3189 | example, @code{"'+'"} is a single-character literal and @code{"\"<=\""} | |
3190 | is a literal string token. All the characters of the literal string | |
3191 | token appear verbatim in the string found in the table; even | |
3192 | double-quote characters are not escaped. For example, if the token | |
3193 | consists of three characters @samp{*"*}, its string in @code{yytname} | |
3194 | contains @samp{"*"*"}. (In C, that would be written as | |
3195 | @code{"\"*\"*\""}). | |
3196 | ||
3197 | When you specify @code{%token_table}, Bison also generates macro | |
3198 | definitions for macros @code{YYNTOKENS}, @code{YYNNTS}, and | |
3199 | @code{YYNRULES}, and @code{YYNSTATES}: | |
3200 | ||
3201 | @table @code | |
3202 | @item YYNTOKENS | |
3203 | The highest token number, plus one. | |
3204 | @item YYNNTS | |
3205 | The number of non-terminal symbols. | |
3206 | @item YYNRULES | |
3207 | The number of grammar rules, | |
3208 | @item YYNSTATES | |
3209 | The number of parser states (@pxref{Parser States}). | |
3210 | @end table | |
3211 | @end table | |
3212 | ||
3213 | @node Multiple Parsers,, Declarations, Grammar File | |
3214 | @section Multiple Parsers in the Same Program | |
3215 | ||
3216 | Most programs that use Bison parse only one language and therefore contain | |
3217 | only one Bison parser. But what if you want to parse more than one | |
3218 | language with the same program? Then you need to avoid a name conflict | |
3219 | between different definitions of @code{yyparse}, @code{yylval}, and so on. | |
3220 | ||
3221 | The easy way to do this is to use the option @samp{-p @var{prefix}} | |
3222 | (@pxref{Invocation, ,Invoking Bison}). This renames the interface functions and | |
3223 | variables of the Bison parser to start with @var{prefix} instead of | |
3224 | @samp{yy}. You can use this to give each parser distinct names that do | |
3225 | not conflict. | |
3226 | ||
3227 | The precise list of symbols renamed is @code{yyparse}, @code{yylex}, | |
3228 | @code{yyerror}, @code{yynerrs}, @code{yylval}, @code{yychar} and | |
3229 | @code{yydebug}. For example, if you use @samp{-p c}, the names become | |
3230 | @code{cparse}, @code{clex}, and so on. | |
3231 | ||
3232 | @strong{All the other variables and macros associated with Bison are not | |
3233 | renamed.} These others are not global; there is no conflict if the same | |
3234 | name is used in different parsers. For example, @code{YYSTYPE} is not | |
3235 | renamed, but defining this in different ways in different parsers causes | |
3236 | no trouble (@pxref{Value Type, ,Data Types of Semantic Values}). | |
3237 | ||
3238 | The @samp{-p} option works by adding macro definitions to the beginning | |
3239 | of the parser source file, defining @code{yyparse} as | |
3240 | @code{@var{prefix}parse}, and so on. This effectively substitutes one | |
3241 | name for the other in the entire parser file. | |
3242 | ||
3243 | @node Interface, Algorithm, Grammar File, Top | |
3244 | @chapter Parser C-Language Interface | |
3245 | @cindex C-language interface | |
3246 | @cindex interface | |
3247 | ||
3248 | The Bison parser is actually a C function named @code{yyparse}. Here we | |
3249 | describe the interface conventions of @code{yyparse} and the other | |
3250 | functions that it needs to use. | |
3251 | ||
3252 | Keep in mind that the parser uses many C identifiers starting with | |
3253 | @samp{yy} and @samp{YY} for internal purposes. If you use such an | |
3254 | identifier (aside from those in this manual) in an action or in additional | |
3255 | C code in the grammar file, you are likely to run into trouble. | |
3256 | ||
3257 | @menu | |
3258 | * Parser Function:: How to call @code{yyparse} and what it returns. | |
3259 | * Lexical:: You must supply a function @code{yylex} | |
3260 | which reads tokens. | |
3261 | * Error Reporting:: You must supply a function @code{yyerror}. | |
3262 | * Action Features:: Special features for use in actions. | |
3263 | @end menu | |
3264 | ||
3265 | @node Parser Function, Lexical, , Interface | |
3266 | @section The Parser Function @code{yyparse} | |
3267 | @findex yyparse | |
3268 | ||
3269 | You call the function @code{yyparse} to cause parsing to occur. This | |
3270 | function reads tokens, executes actions, and ultimately returns when it | |
3271 | encounters end-of-input or an unrecoverable syntax error. You can also | |
3272 | write an action which directs @code{yyparse} to return immediately without | |
3273 | reading further. | |
3274 | ||
3275 | The value returned by @code{yyparse} is 0 if parsing was successful (return | |
3276 | is due to end-of-input). | |
3277 | ||
3278 | The value is 1 if parsing failed (return is due to a syntax error). | |
3279 | ||
3280 | In an action, you can cause immediate return from @code{yyparse} by using | |
3281 | these macros: | |
3282 | ||
3283 | @table @code | |
3284 | @item YYACCEPT | |
3285 | @findex YYACCEPT | |
3286 | Return immediately with value 0 (to report success). | |
3287 | ||
3288 | @item YYABORT | |
3289 | @findex YYABORT | |
3290 | Return immediately with value 1 (to report failure). | |
3291 | @end table | |
3292 | ||
3293 | @node Lexical, Error Reporting, Parser Function, Interface | |
3294 | @section The Lexical Analyzer Function @code{yylex} | |
3295 | @findex yylex | |
3296 | @cindex lexical analyzer | |
3297 | ||
3298 | The @dfn{lexical analyzer} function, @code{yylex}, recognizes tokens from | |
3299 | the input stream and returns them to the parser. Bison does not create | |
3300 | this function automatically; you must write it so that @code{yyparse} can | |
3301 | call it. The function is sometimes referred to as a lexical scanner. | |
3302 | ||
3303 | In simple programs, @code{yylex} is often defined at the end of the Bison | |
3304 | grammar file. If @code{yylex} is defined in a separate source file, you | |
3305 | need to arrange for the token-type macro definitions to be available there. | |
3306 | To do this, use the @samp{-d} option when you run Bison, so that it will | |
3307 | write these macro definitions into a separate header file | |
3308 | @file{@var{name}.tab.h} which you can include in the other source files | |
3309 | that need it. @xref{Invocation, ,Invoking Bison}.@refill | |
3310 | ||
3311 | @menu | |
3312 | * Calling Convention:: How @code{yyparse} calls @code{yylex}. | |
3313 | * Token Values:: How @code{yylex} must return the semantic value | |
3314 | of the token it has read. | |
3315 | * Token Positions:: How @code{yylex} must return the text position | |
3316 | (line number, etc.) of the token, if the | |
3317 | actions want that. | |
3318 | * Pure Calling:: How the calling convention differs | |
3319 | in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}). | |
3320 | @end menu | |
3321 | ||
3322 | @node Calling Convention, Token Values, , Lexical | |
3323 | @subsection Calling Convention for @code{yylex} | |
3324 | ||
3325 | The value that @code{yylex} returns must be the numeric code for the type | |
3326 | of token it has just found, or 0 for end-of-input. | |
3327 | ||
3328 | When a token is referred to in the grammar rules by a name, that name | |
3329 | in the parser file becomes a C macro whose definition is the proper | |
3330 | numeric code for that token type. So @code{yylex} can use the name | |
3331 | to indicate that type. @xref{Symbols}. | |
3332 | ||
3333 | When a token is referred to in the grammar rules by a character literal, | |
3334 | the numeric code for that character is also the code for the token type. | |
3335 | So @code{yylex} can simply return that character code. The null character | |
3336 | must not be used this way, because its code is zero and that is what | |
3337 | signifies end-of-input. | |
3338 | ||
3339 | Here is an example showing these things: | |
3340 | ||
3341 | @example | |
3342 | yylex () | |
3343 | @{ | |
3344 | @dots{} | |
3345 | if (c == EOF) /* Detect end of file. */ | |
3346 | return 0; | |
3347 | @dots{} | |
3348 | if (c == '+' || c == '-') | |
3349 | return c; /* Assume token type for `+' is '+'. */ | |
3350 | @dots{} | |
3351 | return INT; /* Return the type of the token. */ | |
3352 | @dots{} | |
3353 | @} | |
3354 | @end example | |
3355 | ||
3356 | @noindent | |
3357 | This interface has been designed so that the output from the @code{lex} | |
3358 | utility can be used without change as the definition of @code{yylex}. | |
3359 | ||
3360 | If the grammar uses literal string tokens, there are two ways that | |
3361 | @code{yylex} can determine the token type codes for them: | |
3362 | ||
3363 | @itemize @bullet | |
3364 | @item | |
3365 | If the grammar defines symbolic token names as aliases for the | |
3366 | literal string tokens, @code{yylex} can use these symbolic names like | |
3367 | all others. In this case, the use of the literal string tokens in | |
3368 | the grammar file has no effect on @code{yylex}. | |
3369 | ||
3370 | @item | |
3371 | @code{yylex} can find the multi-character token in the @code{yytname} | |
3372 | table. The index of the token in the table is the token type's code. | |
3373 | The name of a multi-character token is recorded in @code{yytname} with a | |
3374 | double-quote, the token's characters, and another double-quote. The | |
3375 | token's characters are not escaped in any way; they appear verbatim in | |
3376 | the contents of the string in the table. | |
3377 | ||
3378 | Here's code for looking up a token in @code{yytname}, assuming that the | |
3379 | characters of the token are stored in @code{token_buffer}. | |
3380 | ||
3381 | @smallexample | |
3382 | for (i = 0; i < YYNTOKENS; i++) | |
3383 | @{ | |
3384 | if (yytname[i] != 0 | |
3385 | && yytname[i][0] == '"' | |
3386 | && strncmp (yytname[i] + 1, token_buffer, strlen (token_buffer)) | |
3387 | && yytname[i][strlen (token_buffer) + 1] == '"' | |
3388 | && yytname[i][strlen (token_buffer) + 2] == 0) | |
3389 | break; | |
3390 | @} | |
3391 | @end smallexample | |
3392 | ||
3393 | The @code{yytname} table is generated only if you use the | |
3394 | @code{%token_table} declaration. @xref{Decl Summary}. | |
3395 | @end itemize | |
3396 | ||
3397 | @node Token Values, Token Positions, Calling Convention, Lexical | |
3398 | @subsection Semantic Values of Tokens | |
3399 | ||
3400 | @vindex yylval | |
3401 | In an ordinary (nonreentrant) parser, the semantic value of the token must | |
3402 | be stored into the global variable @code{yylval}. When you are using | |
3403 | just one data type for semantic values, @code{yylval} has that type. | |
3404 | Thus, if the type is @code{int} (the default), you might write this in | |
3405 | @code{yylex}: | |
3406 | ||
3407 | @example | |
3408 | @group | |
3409 | @dots{} | |
3410 | yylval = value; /* Put value onto Bison stack. */ | |
3411 | return INT; /* Return the type of the token. */ | |
3412 | @dots{} | |
3413 | @end group | |
3414 | @end example | |
3415 | ||
3416 | When you are using multiple data types, @code{yylval}'s type is a union | |
3417 | made from the @code{%union} declaration (@pxref{Union Decl, ,The Collection of Value Types}). So when | |
3418 | you store a token's value, you must use the proper member of the union. | |
3419 | If the @code{%union} declaration looks like this: | |
3420 | ||
3421 | @example | |
3422 | @group | |
3423 | %union @{ | |
3424 | int intval; | |
3425 | double val; | |
3426 | symrec *tptr; | |
3427 | @} | |
3428 | @end group | |
3429 | @end example | |
3430 | ||
3431 | @noindent | |
3432 | then the code in @code{yylex} might look like this: | |
3433 | ||
3434 | @example | |
3435 | @group | |
3436 | @dots{} | |
3437 | yylval.intval = value; /* Put value onto Bison stack. */ | |
3438 | return INT; /* Return the type of the token. */ | |
3439 | @dots{} | |
3440 | @end group | |
3441 | @end example | |
3442 | ||
3443 | @node Token Positions, Pure Calling, Token Values, Lexical | |
3444 | @subsection Textual Positions of Tokens | |
3445 | ||
3446 | @vindex yylloc | |
3447 | If you are using the @samp{@@@var{n}}-feature (@pxref{Action Features, ,Special Features for Use in Actions}) in | |
3448 | actions to keep track of the textual locations of tokens and groupings, | |
3449 | then you must provide this information in @code{yylex}. The function | |
3450 | @code{yyparse} expects to find the textual location of a token just parsed | |
3451 | in the global variable @code{yylloc}. So @code{yylex} must store the | |
3452 | proper data in that variable. The value of @code{yylloc} is a structure | |
3453 | and you need only initialize the members that are going to be used by the | |
3454 | actions. The four members are called @code{first_line}, | |
3455 | @code{first_column}, @code{last_line} and @code{last_column}. Note that | |
3456 | the use of this feature makes the parser noticeably slower. | |
3457 | ||
3458 | @tindex YYLTYPE | |
3459 | The data type of @code{yylloc} has the name @code{YYLTYPE}. | |
3460 | ||
3461 | @node Pure Calling, , Token Positions, Lexical | |
3462 | @subsection Calling Conventions for Pure Parsers | |
3463 | ||
3464 | When you use the Bison declaration @code{%pure_parser} to request a | |
3465 | pure, reentrant parser, the global communication variables @code{yylval} | |
3466 | and @code{yylloc} cannot be used. (@xref{Pure Decl, ,A Pure (Reentrant) | |
3467 | Parser}.) In such parsers the two global variables are replaced by | |
3468 | pointers passed as arguments to @code{yylex}. You must declare them as | |
3469 | shown here, and pass the information back by storing it through those | |
3470 | pointers. | |
3471 | ||
3472 | @example | |
3473 | yylex (lvalp, llocp) | |
3474 | YYSTYPE *lvalp; | |
3475 | YYLTYPE *llocp; | |
3476 | @{ | |
3477 | @dots{} | |
3478 | *lvalp = value; /* Put value onto Bison stack. */ | |
3479 | return INT; /* Return the type of the token. */ | |
3480 | @dots{} | |
3481 | @} | |
3482 | @end example | |
3483 | ||
3484 | If the grammar file does not use the @samp{@@} constructs to refer to | |
3485 | textual positions, then the type @code{YYLTYPE} will not be defined. In | |
3486 | this case, omit the second argument; @code{yylex} will be called with | |
3487 | only one argument. | |
3488 | ||
3489 | @vindex YYPARSE_PARAM | |
3490 | If you use a reentrant parser, you can optionally pass additional | |
3491 | parameter information to it in a reentrant way. To do so, define the | |
3492 | macro @code{YYPARSE_PARAM} as a variable name. This modifies the | |
3493 | @code{yyparse} function to accept one argument, of type @code{void *}, | |
3494 | with that name. | |
3495 | ||
3496 | When you call @code{yyparse}, pass the address of an object, casting the | |
3497 | address to @code{void *}. The grammar actions can refer to the contents | |
3498 | of the object by casting the pointer value back to its proper type and | |
3499 | then dereferencing it. Here's an example. Write this in the parser: | |
3500 | ||
3501 | @example | |
3502 | %@{ | |
3503 | struct parser_control | |
3504 | @{ | |
3505 | int nastiness; | |
3506 | int randomness; | |
3507 | @}; | |
3508 | ||
3509 | #define YYPARSE_PARAM parm | |
3510 | %@} | |
3511 | @end example | |
3512 | ||
3513 | @noindent | |
3514 | Then call the parser like this: | |
3515 | ||
3516 | @example | |
3517 | struct parser_control | |
3518 | @{ | |
3519 | int nastiness; | |
3520 | int randomness; | |
3521 | @}; | |
3522 | ||
3523 | @dots{} | |
3524 | ||
3525 | @{ | |
3526 | struct parser_control foo; | |
3527 | @dots{} /* @r{Store proper data in @code{foo}.} */ | |
3528 | value = yyparse ((void *) &foo); | |
3529 | @dots{} | |
3530 | @} | |
3531 | @end example | |
3532 | ||
3533 | @noindent | |
3534 | In the grammar actions, use expressions like this to refer to the data: | |
3535 | ||
3536 | @example | |
3537 | ((struct parser_control *) parm)->randomness | |
3538 | @end example | |
3539 | ||
3540 | @vindex YYLEX_PARAM | |
3541 | If you wish to pass the additional parameter data to @code{yylex}, | |
3542 | define the macro @code{YYLEX_PARAM} just like @code{YYPARSE_PARAM}, as | |
3543 | shown here: | |
3544 | ||
3545 | @example | |
3546 | %@{ | |
3547 | struct parser_control | |
3548 | @{ | |
3549 | int nastiness; | |
3550 | int randomness; | |
3551 | @}; | |
3552 | ||
3553 | #define YYPARSE_PARAM parm | |
3554 | #define YYLEX_PARAM parm | |
3555 | %@} | |
3556 | @end example | |
3557 | ||
3558 | You should then define @code{yylex} to accept one additional | |
3559 | argument---the value of @code{parm}. (This makes either two or three | |
3560 | arguments in total, depending on whether an argument of type | |
3561 | @code{YYLTYPE} is passed.) You can declare the argument as a pointer to | |
3562 | the proper object type, or you can declare it as @code{void *} and | |
3563 | access the contents as shown above. | |
3564 | ||
3565 | You can use @samp{%pure_parser} to request a reentrant parser without | |
3566 | also using @code{YYPARSE_PARAM}. Then you should call @code{yyparse} | |
3567 | with no arguments, as usual. | |
3568 | ||
3569 | @node Error Reporting, Action Features, Lexical, Interface | |
3570 | @section The Error Reporting Function @code{yyerror} | |
3571 | @cindex error reporting function | |
3572 | @findex yyerror | |
3573 | @cindex parse error | |
3574 | @cindex syntax error | |
3575 | ||
3576 | The Bison parser detects a @dfn{parse error} or @dfn{syntax error} | |
3577 | whenever it reads a token which cannot satisfy any syntax rule. A | |
3578 | action in the grammar can also explicitly proclaim an error, using the | |
3579 | macro @code{YYERROR} (@pxref{Action Features, ,Special Features for Use in Actions}). | |
3580 | ||
3581 | The Bison parser expects to report the error by calling an error | |
3582 | reporting function named @code{yyerror}, which you must supply. It is | |
3583 | called by @code{yyparse} whenever a syntax error is found, and it | |
3584 | receives one argument. For a parse error, the string is normally | |
3585 | @w{@code{"parse error"}}. | |
3586 | ||
3587 | @findex YYERROR_VERBOSE | |
3588 | If you define the macro @code{YYERROR_VERBOSE} in the Bison declarations | |
3589 | section (@pxref{Bison Declarations, ,The Bison Declarations Section}), then Bison provides a more verbose | |
3590 | and specific error message string instead of just plain @w{@code{"parse | |
3591 | error"}}. It doesn't matter what definition you use for | |
3592 | @code{YYERROR_VERBOSE}, just whether you define it. | |
3593 | ||
3594 | The parser can detect one other kind of error: stack overflow. This | |
3595 | happens when the input contains constructions that are very deeply | |
3596 | nested. It isn't likely you will encounter this, since the Bison | |
3597 | parser extends its stack automatically up to a very large limit. But | |
3598 | if overflow happens, @code{yyparse} calls @code{yyerror} in the usual | |
3599 | fashion, except that the argument string is @w{@code{"parser stack | |
3600 | overflow"}}. | |
3601 | ||
3602 | The following definition suffices in simple programs: | |
3603 | ||
3604 | @example | |
3605 | @group | |
3606 | yyerror (s) | |
3607 | char *s; | |
3608 | @{ | |
3609 | @end group | |
3610 | @group | |
3611 | fprintf (stderr, "%s\n", s); | |
3612 | @} | |
3613 | @end group | |
3614 | @end example | |
3615 | ||
3616 | After @code{yyerror} returns to @code{yyparse}, the latter will attempt | |
3617 | error recovery if you have written suitable error recovery grammar rules | |
3618 | (@pxref{Error Recovery}). If recovery is impossible, @code{yyparse} will | |
3619 | immediately return 1. | |
3620 | ||
3621 | @vindex yynerrs | |
3622 | The variable @code{yynerrs} contains the number of syntax errors | |
3623 | encountered so far. Normally this variable is global; but if you | |
3624 | request a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}) then it is a local variable | |
3625 | which only the actions can access. | |
3626 | ||
3627 | @node Action Features, , Error Reporting, Interface | |
3628 | @section Special Features for Use in Actions | |
3629 | @cindex summary, action features | |
3630 | @cindex action features summary | |
3631 | ||
3632 | Here is a table of Bison constructs, variables and macros that | |
3633 | are useful in actions. | |
3634 | ||
3635 | @table @samp | |
3636 | @item $$ | |
3637 | Acts like a variable that contains the semantic value for the | |
3638 | grouping made by the current rule. @xref{Actions}. | |
3639 | ||
3640 | @item $@var{n} | |
3641 | Acts like a variable that contains the semantic value for the | |
3642 | @var{n}th component of the current rule. @xref{Actions}. | |
3643 | ||
3644 | @item $<@var{typealt}>$ | |
3645 | Like @code{$$} but specifies alternative @var{typealt} in the union | |
3646 | specified by the @code{%union} declaration. @xref{Action Types, ,Data Types of Values in Actions}. | |
3647 | ||
3648 | @item $<@var{typealt}>@var{n} | |
3649 | Like @code{$@var{n}} but specifies alternative @var{typealt} in the | |
3650 | union specified by the @code{%union} declaration. | |
3651 | @xref{Action Types, ,Data Types of Values in Actions}.@refill | |
3652 | ||
3653 | @item YYABORT; | |
3654 | Return immediately from @code{yyparse}, indicating failure. | |
3655 | @xref{Parser Function, ,The Parser Function @code{yyparse}}. | |
3656 | ||
3657 | @item YYACCEPT; | |
3658 | Return immediately from @code{yyparse}, indicating success. | |
3659 | @xref{Parser Function, ,The Parser Function @code{yyparse}}. | |
3660 | ||
3661 | @item YYBACKUP (@var{token}, @var{value}); | |
3662 | @findex YYBACKUP | |
3663 | Unshift a token. This macro is allowed only for rules that reduce | |
3664 | a single value, and only when there is no look-ahead token. | |
3665 | It installs a look-ahead token with token type @var{token} and | |
3666 | semantic value @var{value}; then it discards the value that was | |
3667 | going to be reduced by this rule. | |
3668 | ||
3669 | If the macro is used when it is not valid, such as when there is | |
3670 | a look-ahead token already, then it reports a syntax error with | |
3671 | a message @samp{cannot back up} and performs ordinary error | |
3672 | recovery. | |
3673 | ||
3674 | In either case, the rest of the action is not executed. | |
3675 | ||
3676 | @item YYEMPTY | |
3677 | @vindex YYEMPTY | |
3678 | Value stored in @code{yychar} when there is no look-ahead token. | |
3679 | ||
3680 | @item YYERROR; | |
3681 | @findex YYERROR | |
3682 | Cause an immediate syntax error. This statement initiates error | |
3683 | recovery just as if the parser itself had detected an error; however, it | |
3684 | does not call @code{yyerror}, and does not print any message. If you | |
3685 | want to print an error message, call @code{yyerror} explicitly before | |
3686 | the @samp{YYERROR;} statement. @xref{Error Recovery}. | |
3687 | ||
3688 | @item YYRECOVERING | |
3689 | This macro stands for an expression that has the value 1 when the parser | |
3690 | is recovering from a syntax error, and 0 the rest of the time. | |
3691 | @xref{Error Recovery}. | |
3692 | ||
3693 | @item yychar | |
3694 | Variable containing the current look-ahead token. (In a pure parser, | |
3695 | this is actually a local variable within @code{yyparse}.) When there is | |
3696 | no look-ahead token, the value @code{YYEMPTY} is stored in the variable. | |
3697 | @xref{Look-Ahead, ,Look-Ahead Tokens}. | |
3698 | ||
3699 | @item yyclearin; | |
3700 | Discard the current look-ahead token. This is useful primarily in | |
3701 | error rules. @xref{Error Recovery}. | |
3702 | ||
3703 | @item yyerrok; | |
3704 | Resume generating error messages immediately for subsequent syntax | |
3705 | errors. This is useful primarily in error rules. | |
3706 | @xref{Error Recovery}. | |
3707 | ||
3708 | @item @@@var{n} | |
3709 | @findex @@@var{n} | |
3710 | Acts like a structure variable containing information on the line | |
3711 | numbers and column numbers of the @var{n}th component of the current | |
3712 | rule. The structure has four members, like this: | |
3713 | ||
3714 | @example | |
3715 | struct @{ | |
3716 | int first_line, last_line; | |
3717 | int first_column, last_column; | |
3718 | @}; | |
3719 | @end example | |
3720 | ||
3721 | Thus, to get the starting line number of the third component, use | |
3722 | @samp{@@3.first_line}. | |
3723 | ||
3724 | In order for the members of this structure to contain valid information, | |
3725 | you must make @code{yylex} supply this information about each token. | |
3726 | If you need only certain members, then @code{yylex} need only fill in | |
3727 | those members. | |
3728 | ||
3729 | The use of this feature makes the parser noticeably slower. | |
3730 | @end table | |
3731 | ||
3732 | @node Algorithm, Error Recovery, Interface, Top | |
3733 | @chapter The Bison Parser Algorithm | |
3734 | @cindex Bison parser algorithm | |
3735 | @cindex algorithm of parser | |
3736 | @cindex shifting | |
3737 | @cindex reduction | |
3738 | @cindex parser stack | |
3739 | @cindex stack, parser | |
3740 | ||
3741 | As Bison reads tokens, it pushes them onto a stack along with their | |
3742 | semantic values. The stack is called the @dfn{parser stack}. Pushing a | |
3743 | token is traditionally called @dfn{shifting}. | |
3744 | ||
3745 | For example, suppose the infix calculator has read @samp{1 + 5 *}, with a | |
3746 | @samp{3} to come. The stack will have four elements, one for each token | |
3747 | that was shifted. | |
3748 | ||
3749 | But the stack does not always have an element for each token read. When | |
3750 | the last @var{n} tokens and groupings shifted match the components of a | |
3751 | grammar rule, they can be combined according to that rule. This is called | |
3752 | @dfn{reduction}. Those tokens and groupings are replaced on the stack by a | |
3753 | single grouping whose symbol is the result (left hand side) of that rule. | |
3754 | Running the rule's action is part of the process of reduction, because this | |
3755 | is what computes the semantic value of the resulting grouping. | |
3756 | ||
3757 | For example, if the infix calculator's parser stack contains this: | |
3758 | ||
3759 | @example | |
3760 | 1 + 5 * 3 | |
3761 | @end example | |
3762 | ||
3763 | @noindent | |
3764 | and the next input token is a newline character, then the last three | |
3765 | elements can be reduced to 15 via the rule: | |
3766 | ||
3767 | @example | |
3768 | expr: expr '*' expr; | |
3769 | @end example | |
3770 | ||
3771 | @noindent | |
3772 | Then the stack contains just these three elements: | |
3773 | ||
3774 | @example | |
3775 | 1 + 15 | |
3776 | @end example | |
3777 | ||
3778 | @noindent | |
3779 | At this point, another reduction can be made, resulting in the single value | |
3780 | 16. Then the newline token can be shifted. | |
3781 | ||
3782 | The parser tries, by shifts and reductions, to reduce the entire input down | |
3783 | to a single grouping whose symbol is the grammar's start-symbol | |
3784 | (@pxref{Language and Grammar, ,Languages and Context-Free Grammars}). | |
3785 | ||
3786 | This kind of parser is known in the literature as a bottom-up parser. | |
3787 | ||
3788 | @menu | |
3789 | * Look-Ahead:: Parser looks one token ahead when deciding what to do. | |
3790 | * Shift/Reduce:: Conflicts: when either shifting or reduction is valid. | |
3791 | * Precedence:: Operator precedence works by resolving conflicts. | |
3792 | * Contextual Precedence:: When an operator's precedence depends on context. | |
3793 | * Parser States:: The parser is a finite-state-machine with stack. | |
3794 | * Reduce/Reduce:: When two rules are applicable in the same situation. | |
3795 | * Mystery Conflicts:: Reduce/reduce conflicts that look unjustified. | |
3796 | * Stack Overflow:: What happens when stack gets full. How to avoid it. | |
3797 | @end menu | |
3798 | ||
3799 | @node Look-Ahead, Shift/Reduce, , Algorithm | |
3800 | @section Look-Ahead Tokens | |
3801 | @cindex look-ahead token | |
3802 | ||
3803 | The Bison parser does @emph{not} always reduce immediately as soon as the | |
3804 | last @var{n} tokens and groupings match a rule. This is because such a | |
3805 | simple strategy is inadequate to handle most languages. Instead, when a | |
3806 | reduction is possible, the parser sometimes ``looks ahead'' at the next | |
3807 | token in order to decide what to do. | |
3808 | ||
3809 | When a token is read, it is not immediately shifted; first it becomes the | |
3810 | @dfn{look-ahead token}, which is not on the stack. Now the parser can | |
3811 | perform one or more reductions of tokens and groupings on the stack, while | |
3812 | the look-ahead token remains off to the side. When no more reductions | |
3813 | should take place, the look-ahead token is shifted onto the stack. This | |
3814 | does not mean that all possible reductions have been done; depending on the | |
3815 | token type of the look-ahead token, some rules may choose to delay their | |
3816 | application. | |
3817 | ||
3818 | Here is a simple case where look-ahead is needed. These three rules define | |
3819 | expressions which contain binary addition operators and postfix unary | |
3820 | factorial operators (@samp{!}), and allow parentheses for grouping. | |
3821 | ||
3822 | @example | |
3823 | @group | |
3824 | expr: term '+' expr | |
3825 | | term | |
3826 | ; | |
3827 | @end group | |
3828 | ||
3829 | @group | |
3830 | term: '(' expr ')' | |
3831 | | term '!' | |
3832 | | NUMBER | |
3833 | ; | |
3834 | @end group | |
3835 | @end example | |
3836 | ||
3837 | Suppose that the tokens @w{@samp{1 + 2}} have been read and shifted; what | |
3838 | should be done? If the following token is @samp{)}, then the first three | |
3839 | tokens must be reduced to form an @code{expr}. This is the only valid | |
3840 | course, because shifting the @samp{)} would produce a sequence of symbols | |
3841 | @w{@code{term ')'}}, and no rule allows this. | |
3842 | ||
3843 | If the following token is @samp{!}, then it must be shifted immediately so | |
3844 | that @w{@samp{2 !}} can be reduced to make a @code{term}. If instead the | |
3845 | parser were to reduce before shifting, @w{@samp{1 + 2}} would become an | |
3846 | @code{expr}. It would then be impossible to shift the @samp{!} because | |
3847 | doing so would produce on the stack the sequence of symbols @code{expr | |
3848 | '!'}. No rule allows that sequence. | |
3849 | ||
3850 | @vindex yychar | |
3851 | The current look-ahead token is stored in the variable @code{yychar}. | |
3852 | @xref{Action Features, ,Special Features for Use in Actions}. | |
3853 | ||
3854 | @node Shift/Reduce, Precedence, Look-Ahead, Algorithm | |
3855 | @section Shift/Reduce Conflicts | |
3856 | @cindex conflicts | |
3857 | @cindex shift/reduce conflicts | |
3858 | @cindex dangling @code{else} | |
3859 | @cindex @code{else}, dangling | |
3860 | ||
3861 | Suppose we are parsing a language which has if-then and if-then-else | |
3862 | statements, with a pair of rules like this: | |
3863 | ||
3864 | @example | |
3865 | @group | |
3866 | if_stmt: | |
3867 | IF expr THEN stmt | |
3868 | | IF expr THEN stmt ELSE stmt | |
3869 | ; | |
3870 | @end group | |
3871 | @end example | |
3872 | ||
3873 | @noindent | |
3874 | Here we assume that @code{IF}, @code{THEN} and @code{ELSE} are | |
3875 | terminal symbols for specific keyword tokens. | |
3876 | ||
3877 | When the @code{ELSE} token is read and becomes the look-ahead token, the | |
3878 | contents of the stack (assuming the input is valid) are just right for | |
3879 | reduction by the first rule. But it is also legitimate to shift the | |
3880 | @code{ELSE}, because that would lead to eventual reduction by the second | |
3881 | rule. | |
3882 | ||
3883 | This situation, where either a shift or a reduction would be valid, is | |
3884 | called a @dfn{shift/reduce conflict}. Bison is designed to resolve | |
3885 | these conflicts by choosing to shift, unless otherwise directed by | |
3886 | operator precedence declarations. To see the reason for this, let's | |
3887 | contrast it with the other alternative. | |
3888 | ||
3889 | Since the parser prefers to shift the @code{ELSE}, the result is to attach | |
3890 | the else-clause to the innermost if-statement, making these two inputs | |
3891 | equivalent: | |
3892 | ||
3893 | @example | |
3894 | if x then if y then win (); else lose; | |
3895 | ||
3896 | if x then do; if y then win (); else lose; end; | |
3897 | @end example | |
3898 | ||
3899 | But if the parser chose to reduce when possible rather than shift, the | |
3900 | result would be to attach the else-clause to the outermost if-statement, | |
3901 | making these two inputs equivalent: | |
3902 | ||
3903 | @example | |
3904 | if x then if y then win (); else lose; | |
3905 | ||
3906 | if x then do; if y then win (); end; else lose; | |
3907 | @end example | |
3908 | ||
3909 | The conflict exists because the grammar as written is ambiguous: either | |
3910 | parsing of the simple nested if-statement is legitimate. The established | |
3911 | convention is that these ambiguities are resolved by attaching the | |
3912 | else-clause to the innermost if-statement; this is what Bison accomplishes | |
3913 | by choosing to shift rather than reduce. (It would ideally be cleaner to | |
3914 | write an unambiguous grammar, but that is very hard to do in this case.) | |
3915 | This particular ambiguity was first encountered in the specifications of | |
3916 | Algol 60 and is called the ``dangling @code{else}'' ambiguity. | |
3917 | ||
3918 | To avoid warnings from Bison about predictable, legitimate shift/reduce | |
3919 | conflicts, use the @code{%expect @var{n}} declaration. There will be no | |
3920 | warning as long as the number of shift/reduce conflicts is exactly @var{n}. | |
3921 | @xref{Expect Decl, ,Suppressing Conflict Warnings}. | |
3922 | ||
3923 | The definition of @code{if_stmt} above is solely to blame for the | |
3924 | conflict, but the conflict does not actually appear without additional | |
3925 | rules. Here is a complete Bison input file that actually manifests the | |
3926 | conflict: | |
3927 | ||
3928 | @example | |
3929 | @group | |
3930 | %token IF THEN ELSE variable | |
3931 | %% | |
3932 | @end group | |
3933 | @group | |
3934 | stmt: expr | |
3935 | | if_stmt | |
3936 | ; | |
3937 | @end group | |
3938 | ||
3939 | @group | |
3940 | if_stmt: | |
3941 | IF expr THEN stmt | |
3942 | | IF expr THEN stmt ELSE stmt | |
3943 | ; | |
3944 | @end group | |
3945 | ||
3946 | expr: variable | |
3947 | ; | |
3948 | @end example | |
3949 | ||
3950 | @node Precedence, Contextual Precedence, Shift/Reduce, Algorithm | |
3951 | @section Operator Precedence | |
3952 | @cindex operator precedence | |
3953 | @cindex precedence of operators | |
3954 | ||
3955 | Another situation where shift/reduce conflicts appear is in arithmetic | |
3956 | expressions. Here shifting is not always the preferred resolution; the | |
3957 | Bison declarations for operator precedence allow you to specify when to | |
3958 | shift and when to reduce. | |
3959 | ||
3960 | @menu | |
3961 | * Why Precedence:: An example showing why precedence is needed. | |
3962 | * Using Precedence:: How to specify precedence in Bison grammars. | |
3963 | * Precedence Examples:: How these features are used in the previous example. | |
3964 | * How Precedence:: How they work. | |
3965 | @end menu | |
3966 | ||
3967 | @node Why Precedence, Using Precedence, , Precedence | |
3968 | @subsection When Precedence is Needed | |
3969 | ||
3970 | Consider the following ambiguous grammar fragment (ambiguous because the | |
3971 | input @w{@samp{1 - 2 * 3}} can be parsed in two different ways): | |
3972 | ||
3973 | @example | |
3974 | @group | |
3975 | expr: expr '-' expr | |
3976 | | expr '*' expr | |
3977 | | expr '<' expr | |
3978 | | '(' expr ')' | |
3979 | @dots{} | |
3980 | ; | |
3981 | @end group | |
3982 | @end example | |
3983 | ||
3984 | @noindent | |
3985 | Suppose the parser has seen the tokens @samp{1}, @samp{-} and @samp{2}; | |
3986 | should it reduce them via the rule for the addition operator? It depends | |
3987 | on the next token. Of course, if the next token is @samp{)}, we must | |
3988 | reduce; shifting is invalid because no single rule can reduce the token | |
3989 | sequence @w{@samp{- 2 )}} or anything starting with that. But if the next | |
3990 | token is @samp{*} or @samp{<}, we have a choice: either shifting or | |
3991 | reduction would allow the parse to complete, but with different | |
3992 | results. | |
3993 | ||
3994 | To decide which one Bison should do, we must consider the | |
3995 | results. If the next operator token @var{op} is shifted, then it | |
3996 | must be reduced first in order to permit another opportunity to | |
3997 | reduce the sum. The result is (in effect) @w{@samp{1 - (2 | |
3998 | @var{op} 3)}}. On the other hand, if the subtraction is reduced | |
3999 | before shifting @var{op}, the result is @w{@samp{(1 - 2) @var{op} | |
4000 | 3}}. Clearly, then, the choice of shift or reduce should depend | |
4001 | on the relative precedence of the operators @samp{-} and | |
4002 | @var{op}: @samp{*} should be shifted first, but not @samp{<}. | |
4003 | ||
4004 | @cindex associativity | |
4005 | What about input such as @w{@samp{1 - 2 - 5}}; should this be | |
4006 | @w{@samp{(1 - 2) - 5}} or should it be @w{@samp{1 - (2 - 5)}}? For | |
4007 | most operators we prefer the former, which is called @dfn{left | |
4008 | association}. The latter alternative, @dfn{right association}, is | |
4009 | desirable for assignment operators. The choice of left or right | |
4010 | association is a matter of whether the parser chooses to shift or | |
4011 | reduce when the stack contains @w{@samp{1 - 2}} and the look-ahead | |
4012 | token is @samp{-}: shifting makes right-associativity. | |
4013 | ||
4014 | @node Using Precedence, Precedence Examples, Why Precedence, Precedence | |
4015 | @subsection Specifying Operator Precedence | |
4016 | @findex %left | |
4017 | @findex %right | |
4018 | @findex %nonassoc | |
4019 | ||
4020 | Bison allows you to specify these choices with the operator precedence | |
4021 | declarations @code{%left} and @code{%right}. Each such declaration | |
4022 | contains a list of tokens, which are operators whose precedence and | |
4023 | associativity is being declared. The @code{%left} declaration makes all | |
4024 | those operators left-associative and the @code{%right} declaration makes | |
4025 | them right-associative. A third alternative is @code{%nonassoc}, which | |
4026 | declares that it is a syntax error to find the same operator twice ``in a | |
4027 | row''. | |
4028 | ||
4029 | The relative precedence of different operators is controlled by the | |
4030 | order in which they are declared. The first @code{%left} or | |
4031 | @code{%right} declaration in the file declares the operators whose | |
4032 | precedence is lowest, the next such declaration declares the operators | |
4033 | whose precedence is a little higher, and so on. | |
4034 | ||
4035 | @node Precedence Examples, How Precedence, Using Precedence, Precedence | |
4036 | @subsection Precedence Examples | |
4037 | ||
4038 | In our example, we would want the following declarations: | |
4039 | ||
4040 | @example | |
4041 | %left '<' | |
4042 | %left '-' | |
4043 | %left '*' | |
4044 | @end example | |
4045 | ||
4046 | In a more complete example, which supports other operators as well, we | |
4047 | would declare them in groups of equal precedence. For example, @code{'+'} is | |
4048 | declared with @code{'-'}: | |
4049 | ||
4050 | @example | |
4051 | %left '<' '>' '=' NE LE GE | |
4052 | %left '+' '-' | |
4053 | %left '*' '/' | |
4054 | @end example | |
4055 | ||
4056 | @noindent | |
4057 | (Here @code{NE} and so on stand for the operators for ``not equal'' | |
4058 | and so on. We assume that these tokens are more than one character long | |
4059 | and therefore are represented by names, not character literals.) | |
4060 | ||
4061 | @node How Precedence, , Precedence Examples, Precedence | |
4062 | @subsection How Precedence Works | |
4063 | ||
4064 | The first effect of the precedence declarations is to assign precedence | |
4065 | levels to the terminal symbols declared. The second effect is to assign | |
4066 | precedence levels to certain rules: each rule gets its precedence from the | |
4067 | last terminal symbol mentioned in the components. (You can also specify | |
4068 | explicitly the precedence of a rule. @xref{Contextual Precedence, ,Context-Dependent Precedence}.) | |
4069 | ||
4070 | Finally, the resolution of conflicts works by comparing the | |
4071 | precedence of the rule being considered with that of the | |
4072 | look-ahead token. If the token's precedence is higher, the | |
4073 | choice is to shift. If the rule's precedence is higher, the | |
4074 | choice is to reduce. If they have equal precedence, the choice | |
4075 | is made based on the associativity of that precedence level. The | |
4076 | verbose output file made by @samp{-v} (@pxref{Invocation, ,Invoking Bison}) says | |
4077 | how each conflict was resolved. | |
4078 | ||
4079 | Not all rules and not all tokens have precedence. If either the rule or | |
4080 | the look-ahead token has no precedence, then the default is to shift. | |
4081 | ||
4082 | @node Contextual Precedence, Parser States, Precedence, Algorithm | |
4083 | @section Context-Dependent Precedence | |
4084 | @cindex context-dependent precedence | |
4085 | @cindex unary operator precedence | |
4086 | @cindex precedence, context-dependent | |
4087 | @cindex precedence, unary operator | |
4088 | @findex %prec | |
4089 | ||
4090 | Often the precedence of an operator depends on the context. This sounds | |
4091 | outlandish at first, but it is really very common. For example, a minus | |
4092 | sign typically has a very high precedence as a unary operator, and a | |
4093 | somewhat lower precedence (lower than multiplication) as a binary operator. | |
4094 | ||
4095 | The Bison precedence declarations, @code{%left}, @code{%right} and | |
4096 | @code{%nonassoc}, can only be used once for a given token; so a token has | |
4097 | only one precedence declared in this way. For context-dependent | |
4098 | precedence, you need to use an additional mechanism: the @code{%prec} | |
4099 | modifier for rules.@refill | |
4100 | ||
4101 | The @code{%prec} modifier declares the precedence of a particular rule by | |
4102 | specifying a terminal symbol whose precedence should be used for that rule. | |
4103 | It's not necessary for that symbol to appear otherwise in the rule. The | |
4104 | modifier's syntax is: | |
4105 | ||
4106 | @example | |
4107 | %prec @var{terminal-symbol} | |
4108 | @end example | |
4109 | ||
4110 | @noindent | |
4111 | and it is written after the components of the rule. Its effect is to | |
4112 | assign the rule the precedence of @var{terminal-symbol}, overriding | |
4113 | the precedence that would be deduced for it in the ordinary way. The | |
4114 | altered rule precedence then affects how conflicts involving that rule | |
4115 | are resolved (@pxref{Precedence, ,Operator Precedence}). | |
4116 | ||
4117 | Here is how @code{%prec} solves the problem of unary minus. First, declare | |
4118 | a precedence for a fictitious terminal symbol named @code{UMINUS}. There | |
4119 | are no tokens of this type, but the symbol serves to stand for its | |
4120 | precedence: | |
4121 | ||
4122 | @example | |
4123 | @dots{} | |
4124 | %left '+' '-' | |
4125 | %left '*' | |
4126 | %left UMINUS | |
4127 | @end example | |
4128 | ||
4129 | Now the precedence of @code{UMINUS} can be used in specific rules: | |
4130 | ||
4131 | @example | |
4132 | @group | |
4133 | exp: @dots{} | |
4134 | | exp '-' exp | |
4135 | @dots{} | |
4136 | | '-' exp %prec UMINUS | |
4137 | @end group | |
4138 | @end example | |
4139 | ||
4140 | @node Parser States, Reduce/Reduce, Contextual Precedence, Algorithm | |
4141 | @section Parser States | |
4142 | @cindex finite-state machine | |
4143 | @cindex parser state | |
4144 | @cindex state (of parser) | |
4145 | ||
4146 | The function @code{yyparse} is implemented using a finite-state machine. | |
4147 | The values pushed on the parser stack are not simply token type codes; they | |
4148 | represent the entire sequence of terminal and nonterminal symbols at or | |
4149 | near the top of the stack. The current state collects all the information | |
4150 | about previous input which is relevant to deciding what to do next. | |
4151 | ||
4152 | Each time a look-ahead token is read, the current parser state together | |
4153 | with the type of look-ahead token are looked up in a table. This table | |
4154 | entry can say, ``Shift the look-ahead token.'' In this case, it also | |
4155 | specifies the new parser state, which is pushed onto the top of the | |
4156 | parser stack. Or it can say, ``Reduce using rule number @var{n}.'' | |
4157 | This means that a certain number of tokens or groupings are taken off | |
4158 | the top of the stack, and replaced by one grouping. In other words, | |
4159 | that number of states are popped from the stack, and one new state is | |
4160 | pushed. | |
4161 | ||
4162 | There is one other alternative: the table can say that the look-ahead token | |
4163 | is erroneous in the current state. This causes error processing to begin | |
4164 | (@pxref{Error Recovery}). | |
4165 | ||
4166 | @node Reduce/Reduce, Mystery Conflicts, Parser States, Algorithm | |
4167 | @section Reduce/Reduce Conflicts | |
4168 | @cindex reduce/reduce conflict | |
4169 | @cindex conflicts, reduce/reduce | |
4170 | ||
4171 | A reduce/reduce conflict occurs if there are two or more rules that apply | |
4172 | to the same sequence of input. This usually indicates a serious error | |
4173 | in the grammar. | |
4174 | ||
4175 | For example, here is an erroneous attempt to define a sequence | |
4176 | of zero or more @code{word} groupings. | |
4177 | ||
4178 | @example | |
4179 | sequence: /* empty */ | |
4180 | @{ printf ("empty sequence\n"); @} | |
4181 | | maybeword | |
4182 | | sequence word | |
4183 | @{ printf ("added word %s\n", $2); @} | |
4184 | ; | |
4185 | ||
4186 | maybeword: /* empty */ | |
4187 | @{ printf ("empty maybeword\n"); @} | |
4188 | | word | |
4189 | @{ printf ("single word %s\n", $1); @} | |
4190 | ; | |
4191 | @end example | |
4192 | ||
4193 | @noindent | |
4194 | The error is an ambiguity: there is more than one way to parse a single | |
4195 | @code{word} into a @code{sequence}. It could be reduced to a | |
4196 | @code{maybeword} and then into a @code{sequence} via the second rule. | |
4197 | Alternatively, nothing-at-all could be reduced into a @code{sequence} | |
4198 | via the first rule, and this could be combined with the @code{word} | |
4199 | using the third rule for @code{sequence}. | |
4200 | ||
4201 | There is also more than one way to reduce nothing-at-all into a | |
4202 | @code{sequence}. This can be done directly via the first rule, | |
4203 | or indirectly via @code{maybeword} and then the second rule. | |
4204 | ||
4205 | You might think that this is a distinction without a difference, because it | |
4206 | does not change whether any particular input is valid or not. But it does | |
4207 | affect which actions are run. One parsing order runs the second rule's | |
4208 | action; the other runs the first rule's action and the third rule's action. | |
4209 | In this example, the output of the program changes. | |
4210 | ||
4211 | Bison resolves a reduce/reduce conflict by choosing to use the rule that | |
4212 | appears first in the grammar, but it is very risky to rely on this. Every | |
4213 | reduce/reduce conflict must be studied and usually eliminated. Here is the | |
4214 | proper way to define @code{sequence}: | |
4215 | ||
4216 | @example | |
4217 | sequence: /* empty */ | |
4218 | @{ printf ("empty sequence\n"); @} | |
4219 | | sequence word | |
4220 | @{ printf ("added word %s\n", $2); @} | |
4221 | ; | |
4222 | @end example | |
4223 | ||
4224 | Here is another common error that yields a reduce/reduce conflict: | |
4225 | ||
4226 | @example | |
4227 | sequence: /* empty */ | |
4228 | | sequence words | |
4229 | | sequence redirects | |
4230 | ; | |
4231 | ||
4232 | words: /* empty */ | |
4233 | | words word | |
4234 | ; | |
4235 | ||
4236 | redirects:/* empty */ | |
4237 | | redirects redirect | |
4238 | ; | |
4239 | @end example | |
4240 | ||
4241 | @noindent | |
4242 | The intention here is to define a sequence which can contain either | |
4243 | @code{word} or @code{redirect} groupings. The individual definitions of | |
4244 | @code{sequence}, @code{words} and @code{redirects} are error-free, but the | |
4245 | three together make a subtle ambiguity: even an empty input can be parsed | |
4246 | in infinitely many ways! | |
4247 | ||
4248 | Consider: nothing-at-all could be a @code{words}. Or it could be two | |
4249 | @code{words} in a row, or three, or any number. It could equally well be a | |
4250 | @code{redirects}, or two, or any number. Or it could be a @code{words} | |
4251 | followed by three @code{redirects} and another @code{words}. And so on. | |
4252 | ||
4253 | Here are two ways to correct these rules. First, to make it a single level | |
4254 | of sequence: | |
4255 | ||
4256 | @example | |
4257 | sequence: /* empty */ | |
4258 | | sequence word | |
4259 | | sequence redirect | |
4260 | ; | |
4261 | @end example | |
4262 | ||
4263 | Second, to prevent either a @code{words} or a @code{redirects} | |
4264 | from being empty: | |
4265 | ||
4266 | @example | |
4267 | sequence: /* empty */ | |
4268 | | sequence words | |
4269 | | sequence redirects | |
4270 | ; | |
4271 | ||
4272 | words: word | |
4273 | | words word | |
4274 | ; | |
4275 | ||
4276 | redirects:redirect | |
4277 | | redirects redirect | |
4278 | ; | |
4279 | @end example | |
4280 | ||
4281 | @node Mystery Conflicts, Stack Overflow, Reduce/Reduce, Algorithm | |
4282 | @section Mysterious Reduce/Reduce Conflicts | |
4283 | ||
4284 | Sometimes reduce/reduce conflicts can occur that don't look warranted. | |
4285 | Here is an example: | |
4286 | ||
4287 | @example | |
4288 | @group | |
4289 | %token ID | |
4290 | ||
4291 | %% | |
4292 | def: param_spec return_spec ',' | |
4293 | ; | |
4294 | param_spec: | |
4295 | type | |
4296 | | name_list ':' type | |
4297 | ; | |
4298 | @end group | |
4299 | @group | |
4300 | return_spec: | |
4301 | type | |
4302 | | name ':' type | |
4303 | ; | |
4304 | @end group | |
4305 | @group | |
4306 | type: ID | |
4307 | ; | |
4308 | @end group | |
4309 | @group | |
4310 | name: ID | |
4311 | ; | |
4312 | name_list: | |
4313 | name | |
4314 | | name ',' name_list | |
4315 | ; | |
4316 | @end group | |
4317 | @end example | |
4318 | ||
4319 | It would seem that this grammar can be parsed with only a single token | |
4320 | of look-ahead: when a @code{param_spec} is being read, an @code{ID} is | |
4321 | a @code{name} if a comma or colon follows, or a @code{type} if another | |
4322 | @code{ID} follows. In other words, this grammar is LR(1). | |
4323 | ||
4324 | @cindex LR(1) | |
4325 | @cindex LALR(1) | |
4326 | However, Bison, like most parser generators, cannot actually handle all | |
4327 | LR(1) grammars. In this grammar, two contexts, that after an @code{ID} | |
4328 | at the beginning of a @code{param_spec} and likewise at the beginning of | |
4329 | a @code{return_spec}, are similar enough that Bison assumes they are the | |
4330 | same. They appear similar because the same set of rules would be | |
4331 | active---the rule for reducing to a @code{name} and that for reducing to | |
4332 | a @code{type}. Bison is unable to determine at that stage of processing | |
4333 | that the rules would require different look-ahead tokens in the two | |
4334 | contexts, so it makes a single parser state for them both. Combining | |
4335 | the two contexts causes a conflict later. In parser terminology, this | |
4336 | occurrence means that the grammar is not LALR(1). | |
4337 | ||
4338 | In general, it is better to fix deficiencies than to document them. But | |
4339 | this particular deficiency is intrinsically hard to fix; parser | |
4340 | generators that can handle LR(1) grammars are hard to write and tend to | |
4341 | produce parsers that are very large. In practice, Bison is more useful | |
4342 | as it is now. | |
4343 | ||
4344 | When the problem arises, you can often fix it by identifying the two | |
4345 | parser states that are being confused, and adding something to make them | |
4346 | look distinct. In the above example, adding one rule to | |
4347 | @code{return_spec} as follows makes the problem go away: | |
4348 | ||
4349 | @example | |
4350 | @group | |
4351 | %token BOGUS | |
4352 | @dots{} | |
4353 | %% | |
4354 | @dots{} | |
4355 | return_spec: | |
4356 | type | |
4357 | | name ':' type | |
4358 | /* This rule is never used. */ | |
4359 | | ID BOGUS | |
4360 | ; | |
4361 | @end group | |
4362 | @end example | |
4363 | ||
4364 | This corrects the problem because it introduces the possibility of an | |
4365 | additional active rule in the context after the @code{ID} at the beginning of | |
4366 | @code{return_spec}. This rule is not active in the corresponding context | |
4367 | in a @code{param_spec}, so the two contexts receive distinct parser states. | |
4368 | As long as the token @code{BOGUS} is never generated by @code{yylex}, | |
4369 | the added rule cannot alter the way actual input is parsed. | |
4370 | ||
4371 | In this particular example, there is another way to solve the problem: | |
4372 | rewrite the rule for @code{return_spec} to use @code{ID} directly | |
4373 | instead of via @code{name}. This also causes the two confusing | |
4374 | contexts to have different sets of active rules, because the one for | |
4375 | @code{return_spec} activates the altered rule for @code{return_spec} | |
4376 | rather than the one for @code{name}. | |
4377 | ||
4378 | @example | |
4379 | param_spec: | |
4380 | type | |
4381 | | name_list ':' type | |
4382 | ; | |
4383 | return_spec: | |
4384 | type | |
4385 | | ID ':' type | |
4386 | ; | |
4387 | @end example | |
4388 | ||
4389 | @node Stack Overflow, , Mystery Conflicts, Algorithm | |
4390 | @section Stack Overflow, and How to Avoid It | |
4391 | @cindex stack overflow | |
4392 | @cindex parser stack overflow | |
4393 | @cindex overflow of parser stack | |
4394 | ||
4395 | The Bison parser stack can overflow if too many tokens are shifted and | |
4396 | not reduced. When this happens, the parser function @code{yyparse} | |
4397 | returns a nonzero value, pausing only to call @code{yyerror} to report | |
4398 | the overflow. | |
4399 | ||
4400 | @vindex YYMAXDEPTH | |
4401 | By defining the macro @code{YYMAXDEPTH}, you can control how deep the | |
4402 | parser stack can become before a stack overflow occurs. Define the | |
4403 | macro with a value that is an integer. This value is the maximum number | |
4404 | of tokens that can be shifted (and not reduced) before overflow. | |
4405 | It must be a constant expression whose value is known at compile time. | |
4406 | ||
4407 | The stack space allowed is not necessarily allocated. If you specify a | |
4408 | large value for @code{YYMAXDEPTH}, the parser actually allocates a small | |
4409 | stack at first, and then makes it bigger by stages as needed. This | |
4410 | increasing allocation happens automatically and silently. Therefore, | |
4411 | you do not need to make @code{YYMAXDEPTH} painfully small merely to save | |
4412 | space for ordinary inputs that do not need much stack. | |
4413 | ||
4414 | @cindex default stack limit | |
4415 | The default value of @code{YYMAXDEPTH}, if you do not define it, is | |
4416 | 10000. | |
4417 | ||
4418 | @vindex YYINITDEPTH | |
4419 | You can control how much stack is allocated initially by defining the | |
4420 | macro @code{YYINITDEPTH}. This value too must be a compile-time | |
4421 | constant integer. The default is 200. | |
4422 | ||
4423 | @node Error Recovery, Context Dependency, Algorithm, Top | |
4424 | @chapter Error Recovery | |
4425 | @cindex error recovery | |
4426 | @cindex recovery from errors | |
4427 | ||
4428 | It is not usually acceptable to have a program terminate on a parse | |
4429 | error. For example, a compiler should recover sufficiently to parse the | |
4430 | rest of the input file and check it for errors; a calculator should accept | |
4431 | another expression. | |
4432 | ||
4433 | In a simple interactive command parser where each input is one line, it may | |
4434 | be sufficient to allow @code{yyparse} to return 1 on error and have the | |
4435 | caller ignore the rest of the input line when that happens (and then call | |
4436 | @code{yyparse} again). But this is inadequate for a compiler, because it | |
4437 | forgets all the syntactic context leading up to the error. A syntax error | |
4438 | deep within a function in the compiler input should not cause the compiler | |
4439 | to treat the following line like the beginning of a source file. | |
4440 | ||
4441 | @findex error | |
4442 | You can define how to recover from a syntax error by writing rules to | |
4443 | recognize the special token @code{error}. This is a terminal symbol that | |
4444 | is always defined (you need not declare it) and reserved for error | |
4445 | handling. The Bison parser generates an @code{error} token whenever a | |
4446 | syntax error happens; if you have provided a rule to recognize this token | |
4447 | in the current context, the parse can continue. | |
4448 | ||
4449 | For example: | |
4450 | ||
4451 | @example | |
4452 | stmnts: /* empty string */ | |
4453 | | stmnts '\n' | |
4454 | | stmnts exp '\n' | |
4455 | | stmnts error '\n' | |
4456 | @end example | |
4457 | ||
4458 | The fourth rule in this example says that an error followed by a newline | |
4459 | makes a valid addition to any @code{stmnts}. | |
4460 | ||
4461 | What happens if a syntax error occurs in the middle of an @code{exp}? The | |
4462 | error recovery rule, interpreted strictly, applies to the precise sequence | |
4463 | of a @code{stmnts}, an @code{error} and a newline. If an error occurs in | |
4464 | the middle of an @code{exp}, there will probably be some additional tokens | |
4465 | and subexpressions on the stack after the last @code{stmnts}, and there | |
4466 | will be tokens to read before the next newline. So the rule is not | |
4467 | applicable in the ordinary way. | |
4468 | ||
4469 | But Bison can force the situation to fit the rule, by discarding part of | |
4470 | the semantic context and part of the input. First it discards states and | |
4471 | objects from the stack until it gets back to a state in which the | |
4472 | @code{error} token is acceptable. (This means that the subexpressions | |
4473 | already parsed are discarded, back to the last complete @code{stmnts}.) At | |
4474 | this point the @code{error} token can be shifted. Then, if the old | |
4475 | look-ahead token is not acceptable to be shifted next, the parser reads | |
4476 | tokens and discards them until it finds a token which is acceptable. In | |
4477 | this example, Bison reads and discards input until the next newline | |
4478 | so that the fourth rule can apply. | |
4479 | ||
4480 | The choice of error rules in the grammar is a choice of strategies for | |
4481 | error recovery. A simple and useful strategy is simply to skip the rest of | |
4482 | the current input line or current statement if an error is detected: | |
4483 | ||
4484 | @example | |
4485 | stmnt: error ';' /* on error, skip until ';' is read */ | |
4486 | @end example | |
4487 | ||
4488 | It is also useful to recover to the matching close-delimiter of an | |
4489 | opening-delimiter that has already been parsed. Otherwise the | |
4490 | close-delimiter will probably appear to be unmatched, and generate another, | |
4491 | spurious error message: | |
4492 | ||
4493 | @example | |
4494 | primary: '(' expr ')' | |
4495 | | '(' error ')' | |
4496 | @dots{} | |
4497 | ; | |
4498 | @end example | |
4499 | ||
4500 | Error recovery strategies are necessarily guesses. When they guess wrong, | |
4501 | one syntax error often leads to another. In the above example, the error | |
4502 | recovery rule guesses that an error is due to bad input within one | |
4503 | @code{stmnt}. Suppose that instead a spurious semicolon is inserted in the | |
4504 | middle of a valid @code{stmnt}. After the error recovery rule recovers | |
4505 | from the first error, another syntax error will be found straightaway, | |
4506 | since the text following the spurious semicolon is also an invalid | |
4507 | @code{stmnt}. | |
4508 | ||
4509 | To prevent an outpouring of error messages, the parser will output no error | |
4510 | message for another syntax error that happens shortly after the first; only | |
4511 | after three consecutive input tokens have been successfully shifted will | |
4512 | error messages resume. | |
4513 | ||
4514 | Note that rules which accept the @code{error} token may have actions, just | |
4515 | as any other rules can. | |
4516 | ||
4517 | @findex yyerrok | |
4518 | You can make error messages resume immediately by using the macro | |
4519 | @code{yyerrok} in an action. If you do this in the error rule's action, no | |
4520 | error messages will be suppressed. This macro requires no arguments; | |
4521 | @samp{yyerrok;} is a valid C statement. | |
4522 | ||
4523 | @findex yyclearin | |
4524 | The previous look-ahead token is reanalyzed immediately after an error. If | |
4525 | this is unacceptable, then the macro @code{yyclearin} may be used to clear | |
4526 | this token. Write the statement @samp{yyclearin;} in the error rule's | |
4527 | action. | |
4528 | ||
4529 | For example, suppose that on a parse error, an error handling routine is | |
4530 | called that advances the input stream to some point where parsing should | |
4531 | once again commence. The next symbol returned by the lexical scanner is | |
4532 | probably correct. The previous look-ahead token ought to be discarded | |
4533 | with @samp{yyclearin;}. | |
4534 | ||
4535 | @vindex YYRECOVERING | |
4536 | The macro @code{YYRECOVERING} stands for an expression that has the | |
4537 | value 1 when the parser is recovering from a syntax error, and 0 the | |
4538 | rest of the time. A value of 1 indicates that error messages are | |
4539 | currently suppressed for new syntax errors. | |
4540 | ||
4541 | @node Context Dependency, Debugging, Error Recovery, Top | |
4542 | @chapter Handling Context Dependencies | |
4543 | ||
4544 | The Bison paradigm is to parse tokens first, then group them into larger | |
4545 | syntactic units. In many languages, the meaning of a token is affected by | |
4546 | its context. Although this violates the Bison paradigm, certain techniques | |
4547 | (known as @dfn{kludges}) may enable you to write Bison parsers for such | |
4548 | languages. | |
4549 | ||
4550 | @menu | |
4551 | * Semantic Tokens:: Token parsing can depend on the semantic context. | |
4552 | * Lexical Tie-ins:: Token parsing can depend on the syntactic context. | |
4553 | * Tie-in Recovery:: Lexical tie-ins have implications for how | |
4554 | error recovery rules must be written. | |
4555 | @end menu | |
4556 | ||
4557 | (Actually, ``kludge'' means any technique that gets its job done but is | |
4558 | neither clean nor robust.) | |
4559 | ||
4560 | @node Semantic Tokens, Lexical Tie-ins, , Context Dependency | |
4561 | @section Semantic Info in Token Types | |
4562 | ||
4563 | The C language has a context dependency: the way an identifier is used | |
4564 | depends on what its current meaning is. For example, consider this: | |
4565 | ||
4566 | @example | |
4567 | foo (x); | |
4568 | @end example | |
4569 | ||
4570 | This looks like a function call statement, but if @code{foo} is a typedef | |
4571 | name, then this is actually a declaration of @code{x}. How can a Bison | |
4572 | parser for C decide how to parse this input? | |
4573 | ||
4574 | The method used in GNU C is to have two different token types, | |
4575 | @code{IDENTIFIER} and @code{TYPENAME}. When @code{yylex} finds an | |
4576 | identifier, it looks up the current declaration of the identifier in order | |
4577 | to decide which token type to return: @code{TYPENAME} if the identifier is | |
4578 | declared as a typedef, @code{IDENTIFIER} otherwise. | |
4579 | ||
4580 | The grammar rules can then express the context dependency by the choice of | |
4581 | token type to recognize. @code{IDENTIFIER} is accepted as an expression, | |
4582 | but @code{TYPENAME} is not. @code{TYPENAME} can start a declaration, but | |
4583 | @code{IDENTIFIER} cannot. In contexts where the meaning of the identifier | |
4584 | is @emph{not} significant, such as in declarations that can shadow a | |
4585 | typedef name, either @code{TYPENAME} or @code{IDENTIFIER} is | |
4586 | accepted---there is one rule for each of the two token types. | |
4587 | ||
4588 | This technique is simple to use if the decision of which kinds of | |
4589 | identifiers to allow is made at a place close to where the identifier is | |
4590 | parsed. But in C this is not always so: C allows a declaration to | |
4591 | redeclare a typedef name provided an explicit type has been specified | |
4592 | earlier: | |
4593 | ||
4594 | @example | |
4595 | typedef int foo, bar, lose; | |
4596 | static foo (bar); /* @r{redeclare @code{bar} as static variable} */ | |
4597 | static int foo (lose); /* @r{redeclare @code{foo} as function} */ | |
4598 | @end example | |
4599 | ||
4600 | Unfortunately, the name being declared is separated from the declaration | |
4601 | construct itself by a complicated syntactic structure---the ``declarator''. | |
4602 | ||
4603 | As a result, the part of Bison parser for C needs to be duplicated, with | |
4604 | all the nonterminal names changed: once for parsing a declaration in which | |
4605 | a typedef name can be redefined, and once for parsing a declaration in | |
4606 | which that can't be done. Here is a part of the duplication, with actions | |
4607 | omitted for brevity: | |
4608 | ||
4609 | @example | |
4610 | initdcl: | |
4611 | declarator maybeasm '=' | |
4612 | init | |
4613 | | declarator maybeasm | |
4614 | ; | |
4615 | ||
4616 | notype_initdcl: | |
4617 | notype_declarator maybeasm '=' | |
4618 | init | |
4619 | | notype_declarator maybeasm | |
4620 | ; | |
4621 | @end example | |
4622 | ||
4623 | @noindent | |
4624 | Here @code{initdcl} can redeclare a typedef name, but @code{notype_initdcl} | |
4625 | cannot. The distinction between @code{declarator} and | |
4626 | @code{notype_declarator} is the same sort of thing. | |
4627 | ||
4628 | There is some similarity between this technique and a lexical tie-in | |
4629 | (described next), in that information which alters the lexical analysis is | |
4630 | changed during parsing by other parts of the program. The difference is | |
4631 | here the information is global, and is used for other purposes in the | |
4632 | program. A true lexical tie-in has a special-purpose flag controlled by | |
4633 | the syntactic context. | |
4634 | ||
4635 | @node Lexical Tie-ins, Tie-in Recovery, Semantic Tokens, Context Dependency | |
4636 | @section Lexical Tie-ins | |
4637 | @cindex lexical tie-in | |
4638 | ||
4639 | One way to handle context-dependency is the @dfn{lexical tie-in}: a flag | |
4640 | which is set by Bison actions, whose purpose is to alter the way tokens are | |
4641 | parsed. | |
4642 | ||
4643 | For example, suppose we have a language vaguely like C, but with a special | |
4644 | construct @samp{hex (@var{hex-expr})}. After the keyword @code{hex} comes | |
4645 | an expression in parentheses in which all integers are hexadecimal. In | |
4646 | particular, the token @samp{a1b} must be treated as an integer rather than | |
4647 | as an identifier if it appears in that context. Here is how you can do it: | |
4648 | ||
4649 | @example | |
4650 | @group | |
4651 | %@{ | |
4652 | int hexflag; | |
4653 | %@} | |
4654 | %% | |
4655 | @dots{} | |
4656 | @end group | |
4657 | @group | |
4658 | expr: IDENTIFIER | |
4659 | | constant | |
4660 | | HEX '(' | |
4661 | @{ hexflag = 1; @} | |
4662 | expr ')' | |
4663 | @{ hexflag = 0; | |
4664 | $$ = $4; @} | |
4665 | | expr '+' expr | |
4666 | @{ $$ = make_sum ($1, $3); @} | |
4667 | @dots{} | |
4668 | ; | |
4669 | @end group | |
4670 | ||
4671 | @group | |
4672 | constant: | |
4673 | INTEGER | |
4674 | | STRING | |
4675 | ; | |
4676 | @end group | |
4677 | @end example | |
4678 | ||
4679 | @noindent | |
4680 | Here we assume that @code{yylex} looks at the value of @code{hexflag}; when | |
4681 | it is nonzero, all integers are parsed in hexadecimal, and tokens starting | |
4682 | with letters are parsed as integers if possible. | |
4683 | ||
4684 | The declaration of @code{hexflag} shown in the C declarations section of | |
4685 | the parser file is needed to make it accessible to the actions | |
4686 | (@pxref{C Declarations, ,The C Declarations Section}). You must also write the code in @code{yylex} | |
4687 | to obey the flag. | |
4688 | ||
4689 | @node Tie-in Recovery, , Lexical Tie-ins, Context Dependency | |
4690 | @section Lexical Tie-ins and Error Recovery | |
4691 | ||
4692 | Lexical tie-ins make strict demands on any error recovery rules you have. | |
4693 | @xref{Error Recovery}. | |
4694 | ||
4695 | The reason for this is that the purpose of an error recovery rule is to | |
4696 | abort the parsing of one construct and resume in some larger construct. | |
4697 | For example, in C-like languages, a typical error recovery rule is to skip | |
4698 | tokens until the next semicolon, and then start a new statement, like this: | |
4699 | ||
4700 | @example | |
4701 | stmt: expr ';' | |
4702 | | IF '(' expr ')' stmt @{ @dots{} @} | |
4703 | @dots{} | |
4704 | error ';' | |
4705 | @{ hexflag = 0; @} | |
4706 | ; | |
4707 | @end example | |
4708 | ||
4709 | If there is a syntax error in the middle of a @samp{hex (@var{expr})} | |
4710 | construct, this error rule will apply, and then the action for the | |
4711 | completed @samp{hex (@var{expr})} will never run. So @code{hexflag} would | |
4712 | remain set for the entire rest of the input, or until the next @code{hex} | |
4713 | keyword, causing identifiers to be misinterpreted as integers. | |
4714 | ||
4715 | To avoid this problem the error recovery rule itself clears @code{hexflag}. | |
4716 | ||
4717 | There may also be an error recovery rule that works within expressions. | |
4718 | For example, there could be a rule which applies within parentheses | |
4719 | and skips to the close-parenthesis: | |
4720 | ||
4721 | @example | |
4722 | @group | |
4723 | expr: @dots{} | |
4724 | | '(' expr ')' | |
4725 | @{ $$ = $2; @} | |
4726 | | '(' error ')' | |
4727 | @dots{} | |
4728 | @end group | |
4729 | @end example | |
4730 | ||
4731 | If this rule acts within the @code{hex} construct, it is not going to abort | |
4732 | that construct (since it applies to an inner level of parentheses within | |
4733 | the construct). Therefore, it should not clear the flag: the rest of | |
4734 | the @code{hex} construct should be parsed with the flag still in effect. | |
4735 | ||
4736 | What if there is an error recovery rule which might abort out of the | |
4737 | @code{hex} construct or might not, depending on circumstances? There is no | |
4738 | way you can write the action to determine whether a @code{hex} construct is | |
4739 | being aborted or not. So if you are using a lexical tie-in, you had better | |
4740 | make sure your error recovery rules are not of this kind. Each rule must | |
4741 | be such that you can be sure that it always will, or always won't, have to | |
4742 | clear the flag. | |
4743 | ||
4744 | @node Debugging, Invocation, Context Dependency, Top | |
4745 | @chapter Debugging Your Parser | |
4746 | @findex YYDEBUG | |
4747 | @findex yydebug | |
4748 | @cindex debugging | |
4749 | @cindex tracing the parser | |
4750 | ||
4751 | If a Bison grammar compiles properly but doesn't do what you want when it | |
4752 | runs, the @code{yydebug} parser-trace feature can help you figure out why. | |
4753 | ||
4754 | To enable compilation of trace facilities, you must define the macro | |
4755 | @code{YYDEBUG} when you compile the parser. You could use | |
4756 | @samp{-DYYDEBUG=1} as a compiler option or you could put @samp{#define | |
4757 | YYDEBUG 1} in the C declarations section of the grammar file | |
4758 | (@pxref{C Declarations, ,The C Declarations Section}). Alternatively, use the @samp{-t} option when | |
4759 | you run Bison (@pxref{Invocation, ,Invoking Bison}). We always define @code{YYDEBUG} so that | |
4760 | debugging is always possible. | |
4761 | ||
4762 | The trace facility uses @code{stderr}, so you must add @w{@code{#include | |
4763 | <stdio.h>}} to the C declarations section unless it is already there. | |
4764 | ||
4765 | Once you have compiled the program with trace facilities, the way to | |
4766 | request a trace is to store a nonzero value in the variable @code{yydebug}. | |
4767 | You can do this by making the C code do it (in @code{main}, perhaps), or | |
4768 | you can alter the value with a C debugger. | |
4769 | ||
4770 | Each step taken by the parser when @code{yydebug} is nonzero produces a | |
4771 | line or two of trace information, written on @code{stderr}. The trace | |
4772 | messages tell you these things: | |
4773 | ||
4774 | @itemize @bullet | |
4775 | @item | |
4776 | Each time the parser calls @code{yylex}, what kind of token was read. | |
4777 | ||
4778 | @item | |
4779 | Each time a token is shifted, the depth and complete contents of the | |
4780 | state stack (@pxref{Parser States}). | |
4781 | ||
4782 | @item | |
4783 | Each time a rule is reduced, which rule it is, and the complete contents | |
4784 | of the state stack afterward. | |
4785 | @end itemize | |
4786 | ||
4787 | To make sense of this information, it helps to refer to the listing file | |
4788 | produced by the Bison @samp{-v} option (@pxref{Invocation, ,Invoking Bison}). This file | |
4789 | shows the meaning of each state in terms of positions in various rules, and | |
4790 | also what each state will do with each possible input token. As you read | |
4791 | the successive trace messages, you can see that the parser is functioning | |
4792 | according to its specification in the listing file. Eventually you will | |
4793 | arrive at the place where something undesirable happens, and you will see | |
4794 | which parts of the grammar are to blame. | |
4795 | ||
4796 | The parser file is a C program and you can use C debuggers on it, but it's | |
4797 | not easy to interpret what it is doing. The parser function is a | |
4798 | finite-state machine interpreter, and aside from the actions it executes | |
4799 | the same code over and over. Only the values of variables show where in | |
4800 | the grammar it is working. | |
4801 | ||
4802 | @findex YYPRINT | |
4803 | The debugging information normally gives the token type of each token | |
4804 | read, but not its semantic value. You can optionally define a macro | |
4805 | named @code{YYPRINT} to provide a way to print the value. If you define | |
4806 | @code{YYPRINT}, it should take three arguments. The parser will pass a | |
4807 | standard I/O stream, the numeric code for the token type, and the token | |
4808 | value (from @code{yylval}). | |
4809 | ||
4810 | Here is an example of @code{YYPRINT} suitable for the multi-function | |
4811 | calculator (@pxref{Mfcalc Decl, ,Declarations for @code{mfcalc}}): | |
4812 | ||
4813 | @smallexample | |
4814 | #define YYPRINT(file, type, value) yyprint (file, type, value) | |
4815 | ||
4816 | static void | |
4817 | yyprint (file, type, value) | |
4818 | FILE *file; | |
4819 | int type; | |
4820 | YYSTYPE value; | |
4821 | @{ | |
4822 | if (type == VAR) | |
4823 | fprintf (file, " %s", value.tptr->name); | |
4824 | else if (type == NUM) | |
4825 | fprintf (file, " %d", value.val); | |
4826 | @} | |
4827 | @end smallexample | |
4828 | ||
4829 | @node Invocation, Table of Symbols, Debugging, Top | |
4830 | @chapter Invoking Bison | |
4831 | @cindex invoking Bison | |
4832 | @cindex Bison invocation | |
4833 | @cindex options for invoking Bison | |
4834 | ||
4835 | The usual way to invoke Bison is as follows: | |
4836 | ||
4837 | @example | |
4838 | bison @var{infile} | |
4839 | @end example | |
4840 | ||
4841 | Here @var{infile} is the grammar file name, which usually ends in | |
4842 | @samp{.y}. The parser file's name is made by replacing the @samp{.y} | |
4843 | with @samp{.tab.c}. Thus, the @samp{bison foo.y} filename yields | |
4844 | @file{foo.tab.c}, and the @samp{bison hack/foo.y} filename yields | |
4845 | @file{hack/foo.tab.c}.@refill | |
4846 | ||
4847 | @menu | |
4848 | * Bison Options:: All the options described in detail, | |
4849 | in alphabetical order by short options. | |
4850 | * Option Cross Key:: Alphabetical list of long options. | |
4851 | * VMS Invocation:: Bison command syntax on VMS. | |
4852 | @end menu | |
4853 | ||
4854 | @node Bison Options, Option Cross Key, , Invocation | |
4855 | @section Bison Options | |
4856 | ||
4857 | Bison supports both traditional single-letter options and mnemonic long | |
4858 | option names. Long option names are indicated with @samp{--} instead of | |
4859 | @samp{-}. Abbreviations for option names are allowed as long as they | |
4860 | are unique. When a long option takes an argument, like | |
4861 | @samp{--file-prefix}, connect the option name and the argument with | |
4862 | @samp{=}. | |
4863 | ||
4864 | Here is a list of options that can be used with Bison, alphabetized by | |
4865 | short option. It is followed by a cross key alphabetized by long | |
4866 | option. | |
4867 | ||
4868 | @table @samp | |
4869 | @item -b @var{file-prefix} | |
4870 | @itemx --file-prefix=@var{prefix} | |
4871 | Specify a prefix to use for all Bison output file names. The names are | |
4872 | chosen as if the input file were named @file{@var{prefix}.c}. | |
4873 | ||
4874 | @item -d | |
4875 | @itemx --defines | |
4876 | Write an extra output file containing macro definitions for the token | |
4877 | type names defined in the grammar and the semantic value type | |
4878 | @code{YYSTYPE}, as well as a few @code{extern} variable declarations. | |
4879 | ||
4880 | If the parser output file is named @file{@var{name}.c} then this file | |
4881 | is named @file{@var{name}.h}.@refill | |
4882 | ||
4883 | This output file is essential if you wish to put the definition of | |
4884 | @code{yylex} in a separate source file, because @code{yylex} needs to | |
4885 | be able to refer to token type codes and the variable | |
4886 | @code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}.@refill | |
4887 | ||
4888 | @item -l | |
4889 | @itemx --no-lines | |
4890 | Don't put any @code{#line} preprocessor commands in the parser file. | |
4891 | Ordinarily Bison puts them in the parser file so that the C compiler | |
4892 | and debuggers will associate errors with your source file, the | |
4893 | grammar file. This option causes them to associate errors with the | |
4894 | parser file, treating it as an independent source file in its own right. | |
4895 | ||
4896 | @item -n | |
4897 | @itemx --no-parser | |
4898 | Do not include any C code in the parser file; generate tables only. The | |
4899 | parser file contains just @code{#define} directives and static variable | |
4900 | declarations. | |
4901 | ||
4902 | This option also tells Bison to write the C code for the grammar actions | |
4903 | into a file named @file{@var{filename}.act}, in the form of a | |
4904 | brace-surrounded body fit for a @code{switch} statement. | |
4905 | ||
4906 | @item -o @var{outfile} | |
4907 | @itemx --output-file=@var{outfile} | |
4908 | Specify the name @var{outfile} for the parser file. | |
4909 | ||
4910 | The other output files' names are constructed from @var{outfile} | |
4911 | as described under the @samp{-v} and @samp{-d} options. | |
4912 | ||
4913 | @item -p @var{prefix} | |
4914 | @itemx --name-prefix=@var{prefix} | |
4915 | Rename the external symbols used in the parser so that they start with | |
4916 | @var{prefix} instead of @samp{yy}. The precise list of symbols renamed | |
4917 | is @code{yyparse}, @code{yylex}, @code{yyerror}, @code{yynerrs}, | |
4918 | @code{yylval}, @code{yychar} and @code{yydebug}. | |
4919 | ||
4920 | For example, if you use @samp{-p c}, the names become @code{cparse}, | |
4921 | @code{clex}, and so on. | |
4922 | ||
4923 | @xref{Multiple Parsers, ,Multiple Parsers in the Same Program}. | |
4924 | ||
4925 | @item -r | |
4926 | @itemx --raw | |
4927 | Pretend that @code{%raw} was specified. @xref{Decl Summary}. | |
4928 | ||
4929 | @item -t | |
4930 | @itemx --debug | |
4931 | Output a definition of the macro @code{YYDEBUG} into the parser file, | |
4932 | so that the debugging facilities are compiled. @xref{Debugging, ,Debugging Your Parser}. | |
4933 | ||
4934 | @item -v | |
4935 | @itemx --verbose | |
4936 | Write an extra output file containing verbose descriptions of the | |
4937 | parser states and what is done for each type of look-ahead token in | |
4938 | that state. | |
4939 | ||
4940 | This file also describes all the conflicts, both those resolved by | |
4941 | operator precedence and the unresolved ones. | |
4942 | ||
4943 | The file's name is made by removing @samp{.tab.c} or @samp{.c} from | |
4944 | the parser output file name, and adding @samp{.output} instead.@refill | |
4945 | ||
4946 | Therefore, if the input file is @file{foo.y}, then the parser file is | |
4947 | called @file{foo.tab.c} by default. As a consequence, the verbose | |
4948 | output file is called @file{foo.output}.@refill | |
4949 | ||
4950 | @item -V | |
4951 | @itemx --version | |
4952 | Print the version number of Bison and exit. | |
4953 | ||
4954 | @item -h | |
4955 | @itemx --help | |
4956 | Print a summary of the command-line options to Bison and exit. | |
4957 | ||
4958 | @need 1750 | |
4959 | @item -y | |
4960 | @itemx --yacc | |
4961 | @itemx --fixed-output-files | |
4962 | Equivalent to @samp{-o y.tab.c}; the parser output file is called | |
4963 | @file{y.tab.c}, and the other outputs are called @file{y.output} and | |
4964 | @file{y.tab.h}. The purpose of this option is to imitate Yacc's output | |
4965 | file name conventions. Thus, the following shell script can substitute | |
4966 | for Yacc:@refill | |
4967 | ||
4968 | @example | |
4969 | bison -y $* | |
4970 | @end example | |
4971 | @end table | |
4972 | ||
4973 | @node Option Cross Key, VMS Invocation, Bison Options, Invocation | |
4974 | @section Option Cross Key | |
4975 | ||
4976 | Here is a list of options, alphabetized by long option, to help you find | |
4977 | the corresponding short option. | |
4978 | ||
4979 | @tex | |
4980 | \def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill} | |
4981 | ||
4982 | {\tt | |
4983 | \line{ --debug \leaderfill -t} | |
4984 | \line{ --defines \leaderfill -d} | |
4985 | \line{ --file-prefix \leaderfill -b} | |
4986 | \line{ --fixed-output-files \leaderfill -y} | |
4987 | \line{ --help \leaderfill -h} | |
4988 | \line{ --name-prefix \leaderfill -p} | |
4989 | \line{ --no-lines \leaderfill -l} | |
4990 | \line{ --no-parser \leaderfill -n} | |
4991 | \line{ --output-file \leaderfill -o} | |
4992 | \line{ --raw \leaderfill -r} | |
4993 | \line{ --token-table \leaderfill -k} | |
4994 | \line{ --verbose \leaderfill -v} | |
4995 | \line{ --version \leaderfill -V} | |
4996 | \line{ --yacc \leaderfill -y} | |
4997 | } | |
4998 | @end tex | |
4999 | ||
5000 | @ifinfo | |
5001 | @example | |
5002 | --debug -t | |
5003 | --defines -d | |
5004 | --file-prefix=@var{prefix} -b @var{file-prefix} | |
5005 | --fixed-output-files --yacc -y | |
5006 | --help -h | |
5007 | --name-prefix=@var{prefix} -p @var{name-prefix} | |
5008 | --no-lines -l | |
5009 | --no-parser -n | |
5010 | --output-file=@var{outfile} -o @var{outfile} | |
5011 | --raw -r | |
5012 | --token-table -k | |
5013 | --verbose -v | |
5014 | --version -V | |
5015 | @end example | |
5016 | @end ifinfo | |
5017 | ||
5018 | @node VMS Invocation, , Option Cross Key, Invocation | |
5019 | @section Invoking Bison under VMS | |
5020 | @cindex invoking Bison under VMS | |
5021 | @cindex VMS | |
5022 | ||
5023 | The command line syntax for Bison on VMS is a variant of the usual | |
5024 | Bison command syntax---adapted to fit VMS conventions. | |
5025 | ||
5026 | To find the VMS equivalent for any Bison option, start with the long | |
5027 | option, and substitute a @samp{/} for the leading @samp{--}, and | |
5028 | substitute a @samp{_} for each @samp{-} in the name of the long option. | |
5029 | For example, the following invocation under VMS: | |
5030 | ||
5031 | @example | |
5032 | bison /debug/name_prefix=bar foo.y | |
5033 | @end example | |
5034 | ||
5035 | @noindent | |
5036 | is equivalent to the following command under POSIX. | |
5037 | ||
5038 | @example | |
5039 | bison --debug --name-prefix=bar foo.y | |
5040 | @end example | |
5041 | ||
5042 | The VMS file system does not permit filenames such as | |
5043 | @file{foo.tab.c}. In the above example, the output file | |
5044 | would instead be named @file{foo_tab.c}. | |
5045 | ||
5046 | @node Table of Symbols, Glossary, Invocation, Top | |
5047 | @appendix Bison Symbols | |
5048 | @cindex Bison symbols, table of | |
5049 | @cindex symbols in Bison, table of | |
5050 | ||
5051 | @table @code | |
5052 | @item error | |
5053 | A token name reserved for error recovery. This token may be used in | |
5054 | grammar rules so as to allow the Bison parser to recognize an error in | |
5055 | the grammar without halting the process. In effect, a sentence | |
5056 | containing an error may be recognized as valid. On a parse error, the | |
5057 | token @code{error} becomes the current look-ahead token. Actions | |
5058 | corresponding to @code{error} are then executed, and the look-ahead | |
5059 | token is reset to the token that originally caused the violation. | |
5060 | @xref{Error Recovery}. | |
5061 | ||
5062 | @item YYABORT | |
5063 | Macro to pretend that an unrecoverable syntax error has occurred, by | |
5064 | making @code{yyparse} return 1 immediately. The error reporting | |
5065 | function @code{yyerror} is not called. @xref{Parser Function, ,The Parser Function @code{yyparse}}. | |
5066 | ||
5067 | @item YYACCEPT | |
5068 | Macro to pretend that a complete utterance of the language has been | |
5069 | read, by making @code{yyparse} return 0 immediately. | |
5070 | @xref{Parser Function, ,The Parser Function @code{yyparse}}. | |
5071 | ||
5072 | @item YYBACKUP | |
5073 | Macro to discard a value from the parser stack and fake a look-ahead | |
5074 | token. @xref{Action Features, ,Special Features for Use in Actions}. | |
5075 | ||
5076 | @item YYERROR | |
5077 | Macro to pretend that a syntax error has just been detected: call | |
5078 | @code{yyerror} and then perform normal error recovery if possible | |
5079 | (@pxref{Error Recovery}), or (if recovery is impossible) make | |
5080 | @code{yyparse} return 1. @xref{Error Recovery}. | |
5081 | ||
5082 | @item YYERROR_VERBOSE | |
5083 | Macro that you define with @code{#define} in the Bison declarations | |
5084 | section to request verbose, specific error message strings when | |
5085 | @code{yyerror} is called. | |
5086 | ||
5087 | @item YYINITDEPTH | |
5088 | Macro for specifying the initial size of the parser stack. | |
5089 | @xref{Stack Overflow}. | |
5090 | ||
5091 | @item YYLEX_PARAM | |
5092 | Macro for specifying an extra argument (or list of extra arguments) for | |
5093 | @code{yyparse} to pass to @code{yylex}. @xref{Pure Calling,, Calling | |
5094 | Conventions for Pure Parsers}. | |
5095 | ||
5096 | @item YYLTYPE | |
5097 | Macro for the data type of @code{yylloc}; a structure with four | |
5098 | members. @xref{Token Positions, ,Textual Positions of Tokens}. | |
5099 | ||
5100 | @item yyltype | |
5101 | Default value for YYLTYPE. | |
5102 | ||
5103 | @item YYMAXDEPTH | |
5104 | Macro for specifying the maximum size of the parser stack. | |
5105 | @xref{Stack Overflow}. | |
5106 | ||
5107 | @item YYPARSE_PARAM | |
5108 | Macro for specifying the name of a parameter that @code{yyparse} should | |
5109 | accept. @xref{Pure Calling,, Calling Conventions for Pure Parsers}. | |
5110 | ||
5111 | @item YYRECOVERING | |
5112 | Macro whose value indicates whether the parser is recovering from a | |
5113 | syntax error. @xref{Action Features, ,Special Features for Use in Actions}. | |
5114 | ||
5115 | @item YYSTYPE | |
5116 | Macro for the data type of semantic values; @code{int} by default. | |
5117 | @xref{Value Type, ,Data Types of Semantic Values}. | |
5118 | ||
5119 | @item yychar | |
5120 | External integer variable that contains the integer value of the | |
5121 | current look-ahead token. (In a pure parser, it is a local variable | |
5122 | within @code{yyparse}.) Error-recovery rule actions may examine this | |
5123 | variable. @xref{Action Features, ,Special Features for Use in Actions}. | |
5124 | ||
5125 | @item yyclearin | |
5126 | Macro used in error-recovery rule actions. It clears the previous | |
5127 | look-ahead token. @xref{Error Recovery}. | |
5128 | ||
5129 | @item yydebug | |
5130 | External integer variable set to zero by default. If @code{yydebug} | |
5131 | is given a nonzero value, the parser will output information on input | |
5132 | symbols and parser action. @xref{Debugging, ,Debugging Your Parser}. | |
5133 | ||
5134 | @item yyerrok | |
5135 | Macro to cause parser to recover immediately to its normal mode | |
5136 | after a parse error. @xref{Error Recovery}. | |
5137 | ||
5138 | @item yyerror | |
5139 | User-supplied function to be called by @code{yyparse} on error. The | |
5140 | function receives one argument, a pointer to a character string | |
5141 | containing an error message. @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}. | |
5142 | ||
5143 | @item yylex | |
5144 | User-supplied lexical analyzer function, called with no arguments | |
5145 | to get the next token. @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}. | |
5146 | ||
5147 | @item yylval | |
5148 | External variable in which @code{yylex} should place the semantic | |
5149 | value associated with a token. (In a pure parser, it is a local | |
5150 | variable within @code{yyparse}, and its address is passed to | |
5151 | @code{yylex}.) @xref{Token Values, ,Semantic Values of Tokens}. | |
5152 | ||
5153 | @item yylloc | |
5154 | External variable in which @code{yylex} should place the line and | |
5155 | column numbers associated with a token. (In a pure parser, it is a | |
5156 | local variable within @code{yyparse}, and its address is passed to | |
5157 | @code{yylex}.) You can ignore this variable if you don't use the | |
5158 | @samp{@@} feature in the grammar actions. @xref{Token Positions, ,Textual Positions of Tokens}. | |
5159 | ||
5160 | @item yynerrs | |
5161 | Global variable which Bison increments each time there is a parse | |
5162 | error. (In a pure parser, it is a local variable within | |
5163 | @code{yyparse}.) @xref{Error Reporting, ,The Error Reporting Function @code{yyerror}}. | |
5164 | ||
5165 | @item yyparse | |
5166 | The parser function produced by Bison; call this function to start | |
5167 | parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}. | |
5168 | ||
5169 | @item %left | |
5170 | Bison declaration to assign left associativity to token(s). | |
5171 | @xref{Precedence Decl, ,Operator Precedence}. | |
5172 | ||
5173 | @item %no_lines | |
5174 | Bison declaration to avoid generating @code{#line} directives in the | |
5175 | parser file. @xref{Decl Summary}. | |
5176 | ||
5177 | @item %nonassoc | |
5178 | Bison declaration to assign nonassociativity to token(s). | |
5179 | @xref{Precedence Decl, ,Operator Precedence}. | |
5180 | ||
5181 | @item %prec | |
5182 | Bison declaration to assign a precedence to a specific rule. | |
5183 | @xref{Contextual Precedence, ,Context-Dependent Precedence}. | |
5184 | ||
5185 | @item %pure_parser | |
5186 | Bison declaration to request a pure (reentrant) parser. | |
5187 | @xref{Pure Decl, ,A Pure (Reentrant) Parser}. | |
5188 | ||
5189 | @item %raw | |
5190 | Bison declaration to use Bison internal token code numbers in token | |
5191 | tables instead of the usual Yacc-compatible token code numbers. | |
5192 | @xref{Decl Summary}. | |
5193 | ||
5194 | @item %right | |
5195 | Bison declaration to assign right associativity to token(s). | |
5196 | @xref{Precedence Decl, ,Operator Precedence}. | |
5197 | ||
5198 | @item %start | |
5199 | Bison declaration to specify the start symbol. @xref{Start Decl, ,The Start-Symbol}. | |
5200 | ||
5201 | @item %token | |
5202 | Bison declaration to declare token(s) without specifying precedence. | |
5203 | @xref{Token Decl, ,Token Type Names}. | |
5204 | ||
5205 | @item %token_table | |
5206 | Bison declaration to include a token name table in the parser file. | |
5207 | @xref{Decl Summary}. | |
5208 | ||
5209 | @item %type | |
5210 | Bison declaration to declare nonterminals. @xref{Type Decl, ,Nonterminal Symbols}. | |
5211 | ||
5212 | @item %union | |
5213 | Bison declaration to specify several possible data types for semantic | |
5214 | values. @xref{Union Decl, ,The Collection of Value Types}. | |
5215 | @end table | |
5216 | ||
5217 | These are the punctuation and delimiters used in Bison input: | |
5218 | ||
5219 | @table @samp | |
5220 | @item %% | |
5221 | Delimiter used to separate the grammar rule section from the | |
5222 | Bison declarations section or the additional C code section. | |
5223 | @xref{Grammar Layout, ,The Overall Layout of a Bison Grammar}. | |
5224 | ||
5225 | @item %@{ %@} | |
5226 | All code listed between @samp{%@{} and @samp{%@}} is copied directly | |
5227 | to the output file uninterpreted. Such code forms the ``C | |
5228 | declarations'' section of the input file. @xref{Grammar Outline, ,Outline of a Bison Grammar}. | |
5229 | ||
5230 | @item /*@dots{}*/ | |
5231 | Comment delimiters, as in C. | |
5232 | ||
5233 | @item : | |
5234 | Separates a rule's result from its components. @xref{Rules, ,Syntax of Grammar Rules}. | |
5235 | ||
5236 | @item ; | |
5237 | Terminates a rule. @xref{Rules, ,Syntax of Grammar Rules}. | |
5238 | ||
5239 | @item | | |
5240 | Separates alternate rules for the same result nonterminal. | |
5241 | @xref{Rules, ,Syntax of Grammar Rules}. | |
5242 | @end table | |
5243 | ||
5244 | @node Glossary, Index, Table of Symbols, Top | |
5245 | @appendix Glossary | |
5246 | @cindex glossary | |
5247 | ||
5248 | @table @asis | |
5249 | @item Backus-Naur Form (BNF) | |
5250 | Formal method of specifying context-free grammars. BNF was first used | |
5251 | in the @cite{ALGOL-60} report, 1963. @xref{Language and Grammar, ,Languages and Context-Free Grammars}. | |
5252 | ||
5253 | @item Context-free grammars | |
5254 | Grammars specified as rules that can be applied regardless of context. | |
5255 | Thus, if there is a rule which says that an integer can be used as an | |
5256 | expression, integers are allowed @emph{anywhere} an expression is | |
5257 | permitted. @xref{Language and Grammar, ,Languages and Context-Free Grammars}. | |
5258 | ||
5259 | @item Dynamic allocation | |
5260 | Allocation of memory that occurs during execution, rather than at | |
5261 | compile time or on entry to a function. | |
5262 | ||
5263 | @item Empty string | |
5264 | Analogous to the empty set in set theory, the empty string is a | |
5265 | character string of length zero. | |
5266 | ||
5267 | @item Finite-state stack machine | |
5268 | A ``machine'' that has discrete states in which it is said to exist at | |
5269 | each instant in time. As input to the machine is processed, the | |
5270 | machine moves from state to state as specified by the logic of the | |
5271 | machine. In the case of the parser, the input is the language being | |
5272 | parsed, and the states correspond to various stages in the grammar | |
5273 | rules. @xref{Algorithm, ,The Bison Parser Algorithm }. | |
5274 | ||
5275 | @item Grouping | |
5276 | A language construct that is (in general) grammatically divisible; | |
5277 | for example, `expression' or `declaration' in C. | |
5278 | @xref{Language and Grammar, ,Languages and Context-Free Grammars}. | |
5279 | ||
5280 | @item Infix operator | |
5281 | An arithmetic operator that is placed between the operands on which it | |
5282 | performs some operation. | |
5283 | ||
5284 | @item Input stream | |
5285 | A continuous flow of data between devices or programs. | |
5286 | ||
5287 | @item Language construct | |
5288 | One of the typical usage schemas of the language. For example, one of | |
5289 | the constructs of the C language is the @code{if} statement. | |
5290 | @xref{Language and Grammar, ,Languages and Context-Free Grammars}. | |
5291 | ||
5292 | @item Left associativity | |
5293 | Operators having left associativity are analyzed from left to right: | |
5294 | @samp{a+b+c} first computes @samp{a+b} and then combines with | |
5295 | @samp{c}. @xref{Precedence, ,Operator Precedence}. | |
5296 | ||
5297 | @item Left recursion | |
5298 | A rule whose result symbol is also its first component symbol; | |
5299 | for example, @samp{expseq1 : expseq1 ',' exp;}. @xref{Recursion, ,Recursive Rules}. | |
5300 | ||
5301 | @item Left-to-right parsing | |
5302 | Parsing a sentence of a language by analyzing it token by token from | |
5303 | left to right. @xref{Algorithm, ,The Bison Parser Algorithm }. | |
5304 | ||
5305 | @item Lexical analyzer (scanner) | |
5306 | A function that reads an input stream and returns tokens one by one. | |
5307 | @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}. | |
5308 | ||
5309 | @item Lexical tie-in | |
5310 | A flag, set by actions in the grammar rules, which alters the way | |
5311 | tokens are parsed. @xref{Lexical Tie-ins}. | |
5312 | ||
5313 | @item Literal string token | |
5314 | A token which constists of two or more fixed characters. | |
5315 | @xref{Symbols}. | |
5316 | ||
5317 | @item Look-ahead token | |
5318 | A token already read but not yet shifted. @xref{Look-Ahead, ,Look-Ahead Tokens}. | |
5319 | ||
5320 | @item LALR(1) | |
5321 | The class of context-free grammars that Bison (like most other parser | |
5322 | generators) can handle; a subset of LR(1). @xref{Mystery Conflicts, , | |
5323 | Mysterious Reduce/Reduce Conflicts}. | |
5324 | ||
5325 | @item LR(1) | |
5326 | The class of context-free grammars in which at most one token of | |
5327 | look-ahead is needed to disambiguate the parsing of any piece of input. | |
5328 | ||
5329 | @item Nonterminal symbol | |
5330 | A grammar symbol standing for a grammatical construct that can | |
5331 | be expressed through rules in terms of smaller constructs; in other | |
5332 | words, a construct that is not a token. @xref{Symbols}. | |
5333 | ||
5334 | @item Parse error | |
5335 | An error encountered during parsing of an input stream due to invalid | |
5336 | syntax. @xref{Error Recovery}. | |
5337 | ||
5338 | @item Parser | |
5339 | A function that recognizes valid sentences of a language by analyzing | |
5340 | the syntax structure of a set of tokens passed to it from a lexical | |
5341 | analyzer. | |
5342 | ||
5343 | @item Postfix operator | |
5344 | An arithmetic operator that is placed after the operands upon which it | |
5345 | performs some operation. | |
5346 | ||
5347 | @item Reduction | |
5348 | Replacing a string of nonterminals and/or terminals with a single | |
5349 | nonterminal, according to a grammar rule. @xref{Algorithm, ,The Bison Parser Algorithm }. | |
5350 | ||
5351 | @item Reentrant | |
5352 | A reentrant subprogram is a subprogram which can be in invoked any | |
5353 | number of times in parallel, without interference between the various | |
5354 | invocations. @xref{Pure Decl, ,A Pure (Reentrant) Parser}. | |
5355 | ||
5356 | @item Reverse polish notation | |
5357 | A language in which all operators are postfix operators. | |
5358 | ||
5359 | @item Right recursion | |
5360 | A rule whose result symbol is also its last component symbol; | |
5361 | for example, @samp{expseq1: exp ',' expseq1;}. @xref{Recursion, ,Recursive Rules}. | |
5362 | ||
5363 | @item Semantics | |
5364 | In computer languages, the semantics are specified by the actions | |
5365 | taken for each instance of the language, i.e., the meaning of | |
5366 | each statement. @xref{Semantics, ,Defining Language Semantics}. | |
5367 | ||
5368 | @item Shift | |
5369 | A parser is said to shift when it makes the choice of analyzing | |
5370 | further input from the stream rather than reducing immediately some | |
5371 | already-recognized rule. @xref{Algorithm, ,The Bison Parser Algorithm }. | |
5372 | ||
5373 | @item Single-character literal | |
5374 | A single character that is recognized and interpreted as is. | |
5375 | @xref{Grammar in Bison, ,From Formal Rules to Bison Input}. | |
5376 | ||
5377 | @item Start symbol | |
5378 | The nonterminal symbol that stands for a complete valid utterance in | |
5379 | the language being parsed. The start symbol is usually listed as the | |
5380 | first nonterminal symbol in a language specification. | |
5381 | @xref{Start Decl, ,The Start-Symbol}. | |
5382 | ||
5383 | @item Symbol table | |
5384 | A data structure where symbol names and associated data are stored | |
5385 | during parsing to allow for recognition and use of existing | |
5386 | information in repeated uses of a symbol. @xref{Multi-function Calc}. | |
5387 | ||
5388 | @item Token | |
5389 | A basic, grammatically indivisible unit of a language. The symbol | |
5390 | that describes a token in the grammar is a terminal symbol. | |
5391 | The input of the Bison parser is a stream of tokens which comes from | |
5392 | the lexical analyzer. @xref{Symbols}. | |
5393 | ||
5394 | @item Terminal symbol | |
5395 | A grammar symbol that has no rules in the grammar and therefore | |
5396 | is grammatically indivisible. The piece of text it represents | |
5397 | is a token. @xref{Language and Grammar, ,Languages and Context-Free Grammars}. | |
5398 | @end table | |
5399 | ||
5400 | @node Index, , Glossary, Top | |
5401 | @unnumbered Index | |
5402 | ||
5403 | @printindex cp | |
5404 | ||
5405 | @contents | |
5406 | ||
5407 | @bye | |
5408 | ||
5409 | ||
5410 | \f | |
5411 | ||
5412 | @c old menu | |
5413 | ||
5414 | * Introduction:: | |
5415 | * Conditions:: | |
5416 | * Copying:: The GNU General Public License says | |
5417 | how you can copy and share Bison | |
5418 | ||
5419 | Tutorial sections: | |
5420 | * Concepts:: Basic concepts for understanding Bison. | |
5421 | * Examples:: Three simple explained examples of using Bison. | |
5422 | ||
5423 | Reference sections: | |
5424 | * Grammar File:: Writing Bison declarations and rules. | |
5425 | * Interface:: C-language interface to the parser function @code{yyparse}. | |
5426 | * Algorithm:: How the Bison parser works at run-time. | |
5427 | * Error Recovery:: Writing rules for error recovery. | |
5428 | * Context Dependency::What to do if your language syntax is too | |
5429 | messy for Bison to handle straightforwardly. | |
5430 | * Debugging:: Debugging Bison parsers that parse wrong. | |
5431 | * Invocation:: How to run Bison (to produce the parser source file). | |
5432 | * Table of Symbols:: All the keywords of the Bison language are explained. | |
5433 | * Glossary:: Basic concepts are explained. | |
5434 | * Index:: Cross-references to the text. | |
5435 |