1 Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0 à
5 * bison: (bison). GNU Project parser generator (yacc replacement).
8 This file documents the Bison parser generator.
10 Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999,
11 2000 Free Software Foundation, Inc.
13 Permission is granted to make and distribute verbatim copies of this
14 manual provided the copyright notice and this permission notice are
15 preserved on all copies.
17 Permission is granted to copy and distribute modified versions of
18 this manual under the conditions for verbatim copying, provided also
19 that the sections entitled "GNU General Public License" and "Conditions
20 for Using Bison" are included exactly as in the original, and provided
21 that the entire resulting derived work is distributed under the terms
22 of a permission notice identical to this one.
24 Permission is granted to copy and distribute translations of this
25 manual into another language, under the above conditions for modified
26 versions, except that the sections entitled "GNU General Public
27 License", "Conditions for Using Bison" and this permission notice may be
28 included in translations approved by the Free Software Foundation
29 instead of in the original English.
32 File: bison.info, Node: Rpcalc Rules, Next: Rpcalc Lexer, Prev: Rpcalc Decls, Up: RPN Calc
34 Grammar Rules for `rpcalc'
35 --------------------------
37 Here are the grammar rules for the reverse polish notation
45 | exp '\n' { printf ("\t%.10g\n", $1); }
49 | exp exp '+' { $$ = $1 + $2; }
50 | exp exp '-' { $$ = $1 - $2; }
51 | exp exp '*' { $$ = $1 * $2; }
52 | exp exp '/' { $$ = $1 / $2; }
54 | exp exp '^' { $$ = pow ($1, $2); }
56 | exp 'n' { $$ = -$1; }
60 The groupings of the rpcalc "language" defined here are the
61 expression (given the name `exp'), the line of input (`line'), and the
62 complete input transcript (`input'). Each of these nonterminal symbols
63 has several alternate rules, joined by the `|' punctuator which is read
64 as "or". The following sections explain what these rules mean.
66 The semantics of the language is determined by the actions taken
67 when a grouping is recognized. The actions are the C code that appears
68 inside braces. *Note Actions::.
70 You must specify these actions in C, but Bison provides the means for
71 passing semantic values between the rules. In each action, the
72 pseudo-variable `$$' stands for the semantic value for the grouping
73 that the rule is going to construct. Assigning a value to `$$' is the
74 main job of most actions. The semantic values of the components of the
75 rule are referred to as `$1', `$2', and so on.
84 File: bison.info, Node: Rpcalc Input, Next: Rpcalc Line, Up: Rpcalc Rules
86 Explanation of `input'
87 ......................
89 Consider the definition of `input':
95 This definition reads as follows: "A complete input is either an
96 empty string, or a complete input followed by an input line". Notice
97 that "complete input" is defined in terms of itself. This definition
98 is said to be "left recursive" since `input' appears always as the
99 leftmost symbol in the sequence. *Note Recursive Rules: Recursion.
101 The first alternative is empty because there are no symbols between
102 the colon and the first `|'; this means that `input' can match an empty
103 string of input (no tokens). We write the rules this way because it is
104 legitimate to type `Ctrl-d' right after you start the calculator. It's
105 conventional to put an empty alternative first and write the comment
108 The second alternate rule (`input line') handles all nontrivial
109 input. It means, "After reading any number of lines, read one more
110 line if possible." The left recursion makes this rule into a loop.
111 Since the first alternative matches empty input, the loop can be
112 executed zero or more times.
114 The parser function `yyparse' continues to process input until a
115 grammatical error is seen or the lexical analyzer says there are no more
116 input tokens; we will arrange for the latter to happen at end of file.
119 File: bison.info, Node: Rpcalc Line, Next: Rpcalc Expr, Prev: Rpcalc Input, Up: Rpcalc Rules
121 Explanation of `line'
122 .....................
124 Now consider the definition of `line':
127 | exp '\n' { printf ("\t%.10g\n", $1); }
130 The first alternative is a token which is a newline character; this
131 means that rpcalc accepts a blank line (and ignores it, since there is
132 no action). The second alternative is an expression followed by a
133 newline. This is the alternative that makes rpcalc useful. The
134 semantic value of the `exp' grouping is the value of `$1' because the
135 `exp' in question is the first symbol in the alternative. The action
136 prints this value, which is the result of the computation the user
139 This action is unusual because it does not assign a value to `$$'.
140 As a consequence, the semantic value associated with the `line' is
141 uninitialized (its value will be unpredictable). This would be a bug if
142 that value were ever used, but we don't use it: once rpcalc has printed
143 the value of the user's input line, that value is no longer needed.
146 File: bison.info, Node: Rpcalc Expr, Prev: Rpcalc Line, Up: Rpcalc Rules
148 Explanation of `expr'
149 .....................
151 The `exp' grouping has several rules, one for each kind of
152 expression. The first rule handles the simplest expressions: those
153 that are just numbers. The second handles an addition-expression,
154 which looks like two expressions followed by a plus-sign. The third
155 handles subtraction, and so on.
158 | exp exp '+' { $$ = $1 + $2; }
159 | exp exp '-' { $$ = $1 - $2; }
163 We have used `|' to join all the rules for `exp', but we could
164 equally well have written them separately:
167 exp: exp exp '+' { $$ = $1 + $2; } ;
168 exp: exp exp '-' { $$ = $1 - $2; } ;
171 Most of the rules have actions that compute the value of the
172 expression in terms of the value of its parts. For example, in the
173 rule for addition, `$1' refers to the first component `exp' and `$2'
174 refers to the second one. The third component, `'+'', has no meaningful
175 associated semantic value, but if it had one you could refer to it as
176 `$3'. When `yyparse' recognizes a sum expression using this rule, the
177 sum of the two subexpressions' values is produced as the value of the
178 entire expression. *Note Actions::.
180 You don't have to give an action for every rule. When a rule has no
181 action, Bison by default copies the value of `$1' into `$$'. This is
182 what happens in the first rule (the one that uses `NUM').
184 The formatting shown here is the recommended convention, but Bison
185 does not require it. You can add or change whitespace as much as you
186 wish. For example, this:
188 exp : NUM | exp exp '+' {$$ = $1 + $2; } | ...
190 means the same thing as this:
193 | exp exp '+' { $$ = $1 + $2; }
196 The latter, however, is much more readable.
199 File: bison.info, Node: Rpcalc Lexer, Next: Rpcalc Main, Prev: Rpcalc Rules, Up: RPN Calc
201 The `rpcalc' Lexical Analyzer
202 -----------------------------
204 The lexical analyzer's job is low-level parsing: converting
205 characters or sequences of characters into tokens. The Bison parser
206 gets its tokens by calling the lexical analyzer. *Note The Lexical
207 Analyzer Function `yylex': Lexical.
209 Only a simple lexical analyzer is needed for the RPN calculator.
210 This lexical analyzer skips blanks and tabs, then reads in numbers as
211 `double' and returns them as `NUM' tokens. Any other character that
212 isn't part of a number is a separate token. Note that the token-code
213 for such a single-character token is the character itself.
215 The return value of the lexical analyzer function is a numeric code
216 which represents a token type. The same text used in Bison rules to
217 stand for this token type is also a C expression for the numeric code
218 for the type. This works in two ways. If the token type is a
219 character literal, then its numeric code is the ASCII code for that
220 character; you can use the same character literal in the lexical
221 analyzer to express the number. If the token type is an identifier,
222 that identifier is defined by Bison as a C macro whose definition is
223 the appropriate number. In this example, therefore, `NUM' becomes a
224 macro for `yylex' to use.
226 The semantic value of the token (if it has one) is stored into the
227 global variable `yylval', which is where the Bison parser will look for
228 it. (The C data type of `yylval' is `YYSTYPE', which was defined at
229 the beginning of the grammar; *note Declarations for `rpcalc': Rpcalc
232 A token type code of zero is returned if the end-of-file is
233 encountered. (Bison recognizes any nonpositive value as indicating the
236 Here is the code for the lexical analyzer:
238 /* Lexical analyzer returns a double floating point
239 number on the stack and the token NUM, or the ASCII
240 character read if not a number. Skips all blanks
241 and tabs, returns 0 for EOF. */
250 /* skip white space */
251 while ((c = getchar ()) == ' ' || c == '\t')
253 /* process numbers */
254 if (c == '.' || isdigit (c))
257 scanf ("%lf", &yylval);
260 /* return end-of-file */
263 /* return single chars */
268 File: bison.info, Node: Rpcalc Main, Next: Rpcalc Error, Prev: Rpcalc Lexer, Up: RPN Calc
270 The Controlling Function
271 ------------------------
273 In keeping with the spirit of this example, the controlling function
274 is kept to the bare minimum. The only requirement is that it call
275 `yyparse' to start the process of parsing.
284 File: bison.info, Node: Rpcalc Error, Next: Rpcalc Gen, Prev: Rpcalc Main, Up: RPN Calc
286 The Error Reporting Routine
287 ---------------------------
289 When `yyparse' detects a syntax error, it calls the error reporting
290 function `yyerror' to print an error message (usually but not always
291 `"parse error"'). It is up to the programmer to supply `yyerror'
292 (*note Parser C-Language Interface: Interface.), so here is the
293 definition we will use:
298 yyerror (const char *s) /* Called by yyparse on error */
303 After `yyerror' returns, the Bison parser may recover from the error
304 and continue parsing if the grammar contains a suitable error rule
305 (*note Error Recovery::). Otherwise, `yyparse' returns nonzero. We
306 have not written any error rules in this example, so any invalid input
307 will cause the calculator program to exit. This is not clean behavior
308 for a real calculator, but it is adequate for the first example.
311 File: bison.info, Node: Rpcalc Gen, Next: Rpcalc Compile, Prev: Rpcalc Error, Up: RPN Calc
313 Running Bison to Make the Parser
314 --------------------------------
316 Before running Bison to produce a parser, we need to decide how to
317 arrange all the source code in one or more source files. For such a
318 simple example, the easiest thing is to put everything in one file. The
319 definitions of `yylex', `yyerror' and `main' go at the end, in the
320 "additional C code" section of the file (*note The Overall Layout of a
321 Bison Grammar: Grammar Layout.).
323 For a large project, you would probably have several source files,
324 and use `make' to arrange to recompile them.
326 With all the source in a single file, you use the following command
327 to convert it into a parser file:
331 In this example the file was called `rpcalc.y' (for "Reverse Polish
332 CALCulator"). Bison produces a file named `FILE_NAME.tab.c', removing
333 the `.y' from the original file name. The file output by Bison contains
334 the source code for `yyparse'. The additional functions in the input
335 file (`yylex', `yyerror' and `main') are copied verbatim to the output.
338 File: bison.info, Node: Rpcalc Compile, Prev: Rpcalc Gen, Up: RPN Calc
340 Compiling the Parser File
341 -------------------------
343 Here is how to compile and run the parser file:
345 # List files in current directory.
347 rpcalc.tab.c rpcalc.y
349 # Compile the Bison parser.
350 # `-lm' tells compiler to search math library for `pow'.
351 % cc rpcalc.tab.c -lm -o rpcalc
355 rpcalc rpcalc.tab.c rpcalc.y
357 The file `rpcalc' now contains the executable code. Here is an
358 example session using `rpcalc'.
365 3 7 + 3 4 5 * + - n Note the unary minus, `n'
371 ^D End-of-file indicator
375 File: bison.info, Node: Infix Calc, Next: Simple Error Recovery, Prev: RPN Calc, Up: Examples
377 Infix Notation Calculator: `calc'
378 =================================
380 We now modify rpcalc to handle infix operators instead of postfix.
381 Infix notation involves the concept of operator precedence and the need
382 for parentheses nested to arbitrary depth. Here is the Bison code for
383 `calc.y', an infix desk-top calculator.
385 /* Infix notation calculator--calc */
388 #define YYSTYPE double
392 /* BISON Declarations */
396 %left NEG /* negation--unary minus */
397 %right '^' /* exponentiation */
399 /* Grammar follows */
401 input: /* empty string */
406 | exp '\n' { printf ("\t%.10g\n", $1); }
409 exp: NUM { $$ = $1; }
410 | exp '+' exp { $$ = $1 + $3; }
411 | exp '-' exp { $$ = $1 - $3; }
412 | exp '*' exp { $$ = $1 * $3; }
413 | exp '/' exp { $$ = $1 / $3; }
414 | '-' exp %prec NEG { $$ = -$2; }
415 | exp '^' exp { $$ = pow ($1, $3); }
416 | '(' exp ')' { $$ = $2; }
420 The functions `yylex', `yyerror' and `main' can be the same as before.
422 There are two important new features shown in this code.
424 In the second section (Bison declarations), `%left' declares token
425 types and says they are left-associative operators. The declarations
426 `%left' and `%right' (right associativity) take the place of `%token'
427 which is used to declare a token type name without associativity.
428 (These tokens are single-character literals, which ordinarily don't
429 need to be declared. We declare them here to specify the
432 Operator precedence is determined by the line ordering of the
433 declarations; the higher the line number of the declaration (lower on
434 the page or screen), the higher the precedence. Hence, exponentiation
435 has the highest precedence, unary minus (`NEG') is next, followed by
436 `*' and `/', and so on. *Note Operator Precedence: Precedence.
438 The other important new feature is the `%prec' in the grammar section
439 for the unary minus operator. The `%prec' simply instructs Bison that
440 the rule `| '-' exp' has the same precedence as `NEG'--in this case the
441 next-to-highest. *Note Context-Dependent Precedence: Contextual
444 Here is a sample run of `calc.y':
447 4 + 4.5 - (34/(8*3+-3))
455 File: bison.info, Node: Simple Error Recovery, Next: Multi-function Calc, Prev: Infix Calc, Up: Examples
457 Simple Error Recovery
458 =====================
460 Up to this point, this manual has not addressed the issue of "error
461 recovery"--how to continue parsing after the parser detects a syntax
462 error. All we have handled is error reporting with `yyerror'. Recall
463 that by default `yyparse' returns after calling `yyerror'. This means
464 that an erroneous input line causes the calculator program to exit.
465 Now we show how to rectify this deficiency.
467 The Bison language itself includes the reserved word `error', which
468 may be included in the grammar rules. In the example below it has been
469 added to one of the alternatives for `line':
472 | exp '\n' { printf ("\t%.10g\n", $1); }
473 | error '\n' { yyerrok; }
476 This addition to the grammar allows for simple error recovery in the
477 event of a parse error. If an expression that cannot be evaluated is
478 read, the error will be recognized by the third rule for `line', and
479 parsing will continue. (The `yyerror' function is still called upon to
480 print its message as well.) The action executes the statement
481 `yyerrok', a macro defined automatically by Bison; its meaning is that
482 error recovery is complete (*note Error Recovery::). Note the
483 difference between `yyerrok' and `yyerror'; neither one is a misprint.
485 This form of error recovery deals with syntax errors. There are
486 other kinds of errors; for example, division by zero, which raises an
487 exception signal that is normally fatal. A real calculator program
488 must handle this signal and use `longjmp' to return to `main' and
489 resume parsing input lines; it would also have to discard the rest of
490 the current line of input. We won't discuss this issue further because
491 it is not specific to Bison programs.
494 File: bison.info, Node: Multi-function Calc, Next: Exercises, Prev: Simple Error Recovery, Up: Examples
496 Multi-Function Calculator: `mfcalc'
497 ===================================
499 Now that the basics of Bison have been discussed, it is time to move
500 on to a more advanced problem. The above calculators provided only five
501 functions, `+', `-', `*', `/' and `^'. It would be nice to have a
502 calculator that provides other mathematical functions such as `sin',
505 It is easy to add new operators to the infix calculator as long as
506 they are only single-character literals. The lexical analyzer `yylex'
507 passes back all nonnumber characters as tokens, so new grammar rules
508 suffice for adding a new operator. But we want something more
509 flexible: built-in functions whose syntax has this form:
511 FUNCTION_NAME (ARGUMENT)
513 At the same time, we will add memory to the calculator, by allowing you
514 to create named variables, store values in them, and use them later.
515 Here is a sample session with the multi-function calculator:
532 Note that multiple assignment and nested function calls are
537 * Decl: Mfcalc Decl. Bison declarations for multi-function calculator.
538 * Rules: Mfcalc Rules. Grammar rules for the calculator.
539 * Symtab: Mfcalc Symtab. Symbol table management subroutines.
542 File: bison.info, Node: Mfcalc Decl, Next: Mfcalc Rules, Up: Multi-function Calc
544 Declarations for `mfcalc'
545 -------------------------
547 Here are the C and Bison declarations for the multi-function
551 #include <math.h> /* For math functions, cos(), sin(), etc. */
552 #include "calc.h" /* Contains definition of `symrec' */
555 double val; /* For returning numbers. */
556 symrec *tptr; /* For returning symbol-table pointers */
559 %token <val> NUM /* Simple double precision number */
560 %token <tptr> VAR FNCT /* Variable and Function */
566 %left NEG /* Negation--unary minus */
567 %right '^' /* Exponentiation */
569 /* Grammar follows */
573 The above grammar introduces only two new features of the Bison
574 language. These features allow semantic values to have various data
575 types (*note More Than One Value Type: Multiple Types.).
577 The `%union' declaration specifies the entire list of possible types;
578 this is instead of defining `YYSTYPE'. The allowable types are now
579 double-floats (for `exp' and `NUM') and pointers to entries in the
580 symbol table. *Note The Collection of Value Types: Union Decl.
582 Since values can now have various types, it is necessary to
583 associate a type with each grammar symbol whose semantic value is used.
584 These symbols are `NUM', `VAR', `FNCT', and `exp'. Their declarations
585 are augmented with information about their data type (placed between
588 The Bison construct `%type' is used for declaring nonterminal
589 symbols, just as `%token' is used for declaring token types. We have
590 not used `%type' before because nonterminal symbols are normally
591 declared implicitly by the rules that define them. But `exp' must be
592 declared explicitly so we can specify its value type. *Note
593 Nonterminal Symbols: Type Decl.
596 File: bison.info, Node: Mfcalc Rules, Next: Mfcalc Symtab, Prev: Mfcalc Decl, Up: Multi-function Calc
598 Grammar Rules for `mfcalc'
599 --------------------------
601 Here are the grammar rules for the multi-function calculator. Most
602 of them are copied directly from `calc'; three rules, those which
603 mention `VAR' or `FNCT', are new.
611 | exp '\n' { printf ("\t%.10g\n", $1); }
612 | error '\n' { yyerrok; }
615 exp: NUM { $$ = $1; }
616 | VAR { $$ = $1->value.var; }
617 | VAR '=' exp { $$ = $3; $1->value.var = $3; }
618 | FNCT '(' exp ')' { $$ = (*($1->value.fnctptr))($3); }
619 | exp '+' exp { $$ = $1 + $3; }
620 | exp '-' exp { $$ = $1 - $3; }
621 | exp '*' exp { $$ = $1 * $3; }
622 | exp '/' exp { $$ = $1 / $3; }
623 | '-' exp %prec NEG { $$ = -$2; }
624 | exp '^' exp { $$ = pow ($1, $3); }
625 | '(' exp ')' { $$ = $2; }
631 File: bison.info, Node: Mfcalc Symtab, Prev: Mfcalc Rules, Up: Multi-function Calc
633 The `mfcalc' Symbol Table
634 -------------------------
636 The multi-function calculator requires a symbol table to keep track
637 of the names and meanings of variables and functions. This doesn't
638 affect the grammar rules (except for the actions) or the Bison
639 declarations, but it requires some additional C functions for support.
641 The symbol table itself consists of a linked list of records. Its
642 definition, which is kept in the header `calc.h', is as follows. It
643 provides for either functions or variables to be placed in the table.
645 /* Data type for links in the chain of symbols. */
648 char *name; /* name of symbol */
649 int type; /* type of symbol: either VAR or FNCT */
651 double var; /* value of a VAR */
652 double (*fnctptr)(); /* value of a FNCT */
654 struct symrec *next; /* link field */
657 typedef struct symrec symrec;
659 /* The symbol table: a chain of `struct symrec'. */
660 extern symrec *sym_table;
665 The new version of `main' includes a call to `init_table', a
666 function that initializes the symbol table. Here it is, and
667 `init_table' as well:
679 yyerror (const char *s) /* Called by yyparse on error */
690 struct init arith_fncts[] =
701 /* The symbol table: a chain of `struct symrec'. */
702 symrec *sym_table = (symrec *)0;
704 /* Put arithmetic functions in table. */
710 for (i = 0; arith_fncts[i].fname != 0; i++)
712 ptr = putsym (arith_fncts[i].fname, FNCT);
713 ptr->value.fnctptr = arith_fncts[i].fnct;
717 By simply editing the initialization list and adding the necessary
718 include files, you can add additional functions to the calculator.
720 Two important functions allow look-up and installation of symbols in
721 the symbol table. The function `putsym' is passed a name and the type
722 (`VAR' or `FNCT') of the object to be installed. The object is linked
723 to the front of the list, and a pointer to the object is returned. The
724 function `getsym' is passed the name of the symbol to look up. If
725 found, a pointer to that symbol is returned; otherwise zero is returned.
728 putsym (char *sym_name, int sym_type)
731 ptr = (symrec *) malloc (sizeof (symrec));
732 ptr->name = (char *) malloc (strlen (sym_name) + 1);
733 strcpy (ptr->name,sym_name);
734 ptr->type = sym_type;
735 ptr->value.var = 0; /* set value to 0 even if fctn. */
736 ptr->next = (struct symrec *)sym_table;
742 getsym (const char *sym_name)
745 for (ptr = sym_table; ptr != (symrec *) 0;
746 ptr = (symrec *)ptr->next)
747 if (strcmp (ptr->name,sym_name) == 0)
752 The function `yylex' must now recognize variables, numeric values,
753 and the single-character arithmetic operators. Strings of alphanumeric
754 characters with a leading non-digit are recognized as either variables
755 or functions depending on what the symbol table says about them.
757 The string is passed to `getsym' for look up in the symbol table. If
758 the name appears in the table, a pointer to its location and its type
759 (`VAR' or `FNCT') is returned to `yyparse'. If it is not already in
760 the table, then it is installed as a `VAR' using `putsym'. Again, a
761 pointer and its type (which must be `VAR') is returned to `yyparse'.
763 No change is needed in the handling of numeric values and arithmetic
764 operators in `yylex'.
773 /* Ignore whitespace, get first nonwhite character. */
774 while ((c = getchar ()) == ' ' || c == '\t');
779 /* Char starts a number => parse the number. */
780 if (c == '.' || isdigit (c))
783 scanf ("%lf", &yylval.val);
787 /* Char starts an identifier => read the name. */
791 static char *symbuf = 0;
792 static int length = 0;
795 /* Initially make the buffer long enough
796 for a 40-character symbol name. */
798 length = 40, symbuf = (char *)malloc (length + 1);
803 /* If buffer is full, make it bigger. */
807 symbuf = (char *)realloc (symbuf, length + 1);
809 /* Add this character to the buffer. */
811 /* Get another character. */
814 while (c != EOF && isalnum (c));
821 s = putsym (symbuf, VAR);
826 /* Any other character is a token by itself. */
830 This program is both powerful and flexible. You may easily add new
831 functions, and it is a simple job to modify this code to install
832 predefined variables such as `pi' or `e' as well.
835 File: bison.info, Node: Exercises, Prev: Multi-function Calc, Up: Examples
840 1. Add some new functions from `math.h' to the initialization list.
842 2. Add another array that contains constants and their values. Then
843 modify `init_table' to add these constants to the symbol table.
844 It will be easiest to give the constants type `VAR'.
846 3. Make the program report an error if the user refers to an
847 uninitialized variable in any way except to store a value in it.
850 File: bison.info, Node: Grammar File, Next: Interface, Prev: Examples, Up: Top
855 Bison takes as input a context-free grammar specification and
856 produces a C-language function that recognizes correct instances of the
859 The Bison grammar input file conventionally has a name ending in
864 * Grammar Outline:: Overall layout of the grammar file.
865 * Symbols:: Terminal and nonterminal symbols.
866 * Rules:: How to write grammar rules.
867 * Recursion:: Writing recursive rules.
868 * Semantics:: Semantic values and actions.
869 * Declarations:: All kinds of Bison declarations are described here.
870 * Multiple Parsers:: Putting more than one Bison parser in one program.
873 File: bison.info, Node: Grammar Outline, Next: Symbols, Up: Grammar File
875 Outline of a Bison Grammar
876 ==========================
878 A Bison grammar file has four main sections, shown here with the
879 appropriate delimiters:
893 Comments enclosed in `/* ... */' may appear in any of the sections.
897 * C Declarations:: Syntax and usage of the C declarations section.
898 * Bison Declarations:: Syntax and usage of the Bison declarations section.
899 * Grammar Rules:: Syntax and usage of the grammar rules section.
900 * C Code:: Syntax and usage of the additional C code section.
903 File: bison.info, Node: C Declarations, Next: Bison Declarations, Up: Grammar Outline
905 The C Declarations Section
906 --------------------------
908 The C DECLARATIONS section contains macro definitions and
909 declarations of functions and variables that are used in the actions in
910 the grammar rules. These are copied to the beginning of the parser
911 file so that they precede the definition of `yyparse'. You can use
912 `#include' to get the declarations from a header file. If you don't
913 need any C declarations, you may omit the `%{' and `%}' delimiters that
914 bracket this section.
917 File: bison.info, Node: Bison Declarations, Next: Grammar Rules, Prev: C Declarations, Up: Grammar Outline
919 The Bison Declarations Section
920 ------------------------------
922 The BISON DECLARATIONS section contains declarations that define
923 terminal and nonterminal symbols, specify precedence, and so on. In
924 some simple grammars you may not need any declarations. *Note Bison
925 Declarations: Declarations.
928 File: bison.info, Node: Grammar Rules, Next: C Code, Prev: Bison Declarations, Up: Grammar Outline
930 The Grammar Rules Section
931 -------------------------
933 The "grammar rules" section contains one or more Bison grammar
934 rules, and nothing else. *Note Syntax of Grammar Rules: Rules.
936 There must always be at least one grammar rule, and the first `%%'
937 (which precedes the grammar rules) may never be omitted even if it is
938 the first thing in the file.
941 File: bison.info, Node: C Code, Prev: Grammar Rules, Up: Grammar Outline
943 The Additional C Code Section
944 -----------------------------
946 The ADDITIONAL C CODE section is copied verbatim to the end of the
947 parser file, just as the C DECLARATIONS section is copied to the
948 beginning. This is the most convenient place to put anything that you
949 want to have in the parser file but which need not come before the
950 definition of `yyparse'. For example, the definitions of `yylex' and
951 `yyerror' often go here. *Note Parser C-Language Interface: Interface.
953 If the last section is empty, you may omit the `%%' that separates it
954 from the grammar rules.
956 The Bison parser itself contains many static variables whose names
957 start with `yy' and many macros whose names start with `YY'. It is a
958 good idea to avoid using any such names (except those documented in this
959 manual) in the additional C code section of the grammar file.
962 File: bison.info, Node: Symbols, Next: Rules, Prev: Grammar Outline, Up: Grammar File
964 Symbols, Terminal and Nonterminal
965 =================================
967 "Symbols" in Bison grammars represent the grammatical classifications
970 A "terminal symbol" (also known as a "token type") represents a
971 class of syntactically equivalent tokens. You use the symbol in grammar
972 rules to mean that a token in that class is allowed. The symbol is
973 represented in the Bison parser by a numeric code, and the `yylex'
974 function returns a token type code to indicate what kind of token has
975 been read. You don't need to know what the code value is; you can use
976 the symbol to stand for it.
978 A "nonterminal symbol" stands for a class of syntactically equivalent
979 groupings. The symbol name is used in writing grammar rules. By
980 convention, it should be all lower case.
982 Symbol names can contain letters, digits (not at the beginning),
983 underscores and periods. Periods make sense only in nonterminals.
985 There are three ways of writing terminal symbols in the grammar:
987 * A "named token type" is written with an identifier, like an
988 identifier in C. By convention, it should be all upper case. Each
989 such name must be defined with a Bison declaration such as
990 `%token'. *Note Token Type Names: Token Decl.
992 * A "character token type" (or "literal character token") is written
993 in the grammar using the same syntax used in C for character
994 constants; for example, `'+'' is a character token type. A
995 character token type doesn't need to be declared unless you need to
996 specify its semantic value data type (*note Data Types of Semantic
997 Values: Value Type.), associativity, or precedence (*note Operator
998 Precedence: Precedence.).
1000 By convention, a character token type is used only to represent a
1001 token that consists of that particular character. Thus, the token
1002 type `'+'' is used to represent the character `+' as a token.
1003 Nothing enforces this convention, but if you depart from it, your
1004 program will confuse other readers.
1006 All the usual escape sequences used in character literals in C can
1007 be used in Bison as well, but you must not use the null character
1008 as a character literal because its ASCII code, zero, is the code
1009 `yylex' returns for end-of-input (*note Calling Convention for
1010 `yylex': Calling Convention.).
1012 * A "literal string token" is written like a C string constant; for
1013 example, `"<="' is a literal string token. A literal string token
1014 doesn't need to be declared unless you need to specify its semantic
1015 value data type (*note Value Type::), associativity, or precedence
1016 (*note Precedence::).
1018 You can associate the literal string token with a symbolic name as
1019 an alias, using the `%token' declaration (*note Token
1020 Declarations: Token Decl.). If you don't do that, the lexical
1021 analyzer has to retrieve the token number for the literal string
1022 token from the `yytname' table (*note Calling Convention::).
1024 *WARNING*: literal string tokens do not work in Yacc.
1026 By convention, a literal string token is used only to represent a
1027 token that consists of that particular string. Thus, you should
1028 use the token type `"<="' to represent the string `<=' as a token.
1029 Bison does not enforce this convention, but if you depart from
1030 it, people who read your program will be confused.
1032 All the escape sequences used in string literals in C can be used
1033 in Bison as well. A literal string token must contain two or more
1034 characters; for a token containing just one character, use a
1035 character token (see above).
1037 How you choose to write a terminal symbol has no effect on its
1038 grammatical meaning. That depends only on where it appears in rules and
1039 on when the parser function returns that symbol.
1041 The value returned by `yylex' is always one of the terminal symbols
1042 (or 0 for end-of-input). Whichever way you write the token type in the
1043 grammar rules, you write it the same way in the definition of `yylex'.
1044 The numeric code for a character token type is simply the ASCII code for
1045 the character, so `yylex' can use the identical character constant to
1046 generate the requisite code. Each named token type becomes a C macro in
1047 the parser file, so `yylex' can use the name to stand for the code.
1048 (This is why periods don't make sense in terminal symbols.) *Note
1049 Calling Convention for `yylex': Calling Convention.
1051 If `yylex' is defined in a separate file, you need to arrange for the
1052 token-type macro definitions to be available there. Use the `-d'
1053 option when you run Bison, so that it will write these macro definitions
1054 into a separate header file `NAME.tab.h' which you can include in the
1055 other source files that need it. *Note Invoking Bison: Invocation.
1057 The symbol `error' is a terminal symbol reserved for error recovery
1058 (*note Error Recovery::); you shouldn't use it for any other purpose.
1059 In particular, `yylex' should never return this value.
1062 File: bison.info, Node: Rules, Next: Recursion, Prev: Symbols, Up: Grammar File
1064 Syntax of Grammar Rules
1065 =======================
1067 A Bison grammar rule has the following general form:
1069 RESULT: COMPONENTS...
1072 where RESULT is the nonterminal symbol that this rule describes, and
1073 COMPONENTS are various terminal and nonterminal symbols that are put
1074 together by this rule (*note Symbols::).
1081 says that two groupings of type `exp', with a `+' token in between, can
1082 be combined into a larger grouping of type `exp'.
1084 Whitespace in rules is significant only to separate symbols. You
1085 can add extra whitespace as you wish.
1087 Scattered among the components can be ACTIONS that determine the
1088 semantics of the rule. An action looks like this:
1092 Usually there is only one action and it follows the components. *Note
1095 Multiple rules for the same RESULT can be written separately or can
1096 be joined with the vertical-bar character `|' as follows:
1098 RESULT: RULE1-COMPONENTS...
1099 | RULE2-COMPONENTS...
1103 They are still considered distinct rules even when joined in this way.
1105 If COMPONENTS in a rule is empty, it means that RESULT can match the
1106 empty string. For example, here is how to define a comma-separated
1107 sequence of zero or more `exp' groupings:
1117 It is customary to write a comment `/* empty */' in each rule with no
1121 File: bison.info, Node: Recursion, Next: Semantics, Prev: Rules, Up: Grammar File
1126 A rule is called "recursive" when its RESULT nonterminal appears
1127 also on its right hand side. Nearly all Bison grammars need to use
1128 recursion, because that is the only way to define a sequence of any
1129 number of a particular thing. Consider this recursive definition of a
1130 comma-separated sequence of one or more expressions:
1136 Since the recursive use of `expseq1' is the leftmost symbol in the
1137 right hand side, we call this "left recursion". By contrast, here the
1138 same construct is defined using "right recursion":
1144 Any kind of sequence can be defined using either left recursion or
1145 right recursion, but you should always use left recursion, because it
1146 can parse a sequence of any number of elements with bounded stack
1147 space. Right recursion uses up space on the Bison stack in proportion
1148 to the number of elements in the sequence, because all the elements
1149 must be shifted onto the stack before the rule can be applied even
1150 once. *Note The Bison Parser Algorithm: Algorithm, for further
1151 explanation of this.
1153 "Indirect" or "mutual" recursion occurs when the result of the rule
1154 does not appear directly on its right hand side, but does appear in
1155 rules for other nonterminals which do appear on its right hand side.
1160 | primary '+' primary
1167 defines two mutually-recursive nonterminals, since each refers to the
1171 File: bison.info, Node: Semantics, Next: Declarations, Prev: Recursion, Up: Grammar File
1173 Defining Language Semantics
1174 ===========================
1176 The grammar rules for a language determine only the syntax. The
1177 semantics are determined by the semantic values associated with various
1178 tokens and groupings, and by the actions taken when various groupings
1181 For example, the calculator calculates properly because the value
1182 associated with each expression is the proper number; it adds properly
1183 because the action for the grouping `X + Y' is to add the numbers
1184 associated with X and Y.
1188 * Value Type:: Specifying one data type for all semantic values.
1189 * Multiple Types:: Specifying several alternative data types.
1190 * Actions:: An action is the semantic definition of a grammar rule.
1191 * Action Types:: Specifying data types for actions to operate on.
1192 * Mid-Rule Actions:: Most actions go at the end of a rule.
1193 This says when, why and how to use the exceptional
1194 action in the middle of a rule.
1197 File: bison.info, Node: Value Type, Next: Multiple Types, Up: Semantics
1199 Data Types of Semantic Values
1200 -----------------------------
1202 In a simple program it may be sufficient to use the same data type
1203 for the semantic values of all language constructs. This was true in
1204 the RPN and infix calculator examples (*note Reverse Polish Notation
1205 Calculator: RPN Calc.).
1207 Bison's default is to use type `int' for all semantic values. To
1208 specify some other type, define `YYSTYPE' as a macro, like this:
1210 #define YYSTYPE double
1212 This macro definition must go in the C declarations section of the
1213 grammar file (*note Outline of a Bison Grammar: Grammar Outline.).
1216 File: bison.info, Node: Multiple Types, Next: Actions, Prev: Value Type, Up: Semantics
1218 More Than One Value Type
1219 ------------------------
1221 In most programs, you will need different data types for different
1222 kinds of tokens and groupings. For example, a numeric constant may
1223 need type `int' or `long', while a string constant needs type `char *',
1224 and an identifier might need a pointer to an entry in the symbol table.
1226 To use more than one data type for semantic values in one parser,
1227 Bison requires you to do two things:
1229 * Specify the entire collection of possible data types, with the
1230 `%union' Bison declaration (*note The Collection of Value Types:
1233 * Choose one of those types for each symbol (terminal or
1234 nonterminal) for which semantic values are used. This is done for
1235 tokens with the `%token' Bison declaration (*note Token Type
1236 Names: Token Decl.) and for groupings with the `%type' Bison
1237 declaration (*note Nonterminal Symbols: Type Decl.).
1240 File: bison.info, Node: Actions, Next: Action Types, Prev: Multiple Types, Up: Semantics
1245 An action accompanies a syntactic rule and contains C code to be
1246 executed each time an instance of that rule is recognized. The task of
1247 most actions is to compute a semantic value for the grouping built by
1248 the rule from the semantic values associated with tokens or smaller
1251 An action consists of C statements surrounded by braces, much like a
1252 compound statement in C. It can be placed at any position in the rule;
1253 it is executed at that position. Most rules have just one action at
1254 the end of the rule, following all the components. Actions in the
1255 middle of a rule are tricky and used only for special purposes (*note
1256 Actions in Mid-Rule: Mid-Rule Actions.).
1258 The C code in an action can refer to the semantic values of the
1259 components matched by the rule with the construct `$N', which stands for
1260 the value of the Nth component. The semantic value for the grouping
1261 being constructed is `$$'. (Bison translates both of these constructs
1262 into array element references when it copies the actions into the parser
1265 Here is a typical example:
1271 This rule constructs an `exp' from two smaller `exp' groupings
1272 connected by a plus-sign token. In the action, `$1' and `$3' refer to
1273 the semantic values of the two component `exp' groupings, which are the
1274 first and third symbols on the right hand side of the rule. The sum is
1275 stored into `$$' so that it becomes the semantic value of the
1276 addition-expression just recognized by the rule. If there were a
1277 useful semantic value associated with the `+' token, it could be
1278 referred to as `$2'.
1280 If you don't specify an action for a rule, Bison supplies a default:
1281 `$$ = $1'. Thus, the value of the first symbol in the rule becomes the
1282 value of the whole rule. Of course, the default rule is valid only if
1283 the two data types match. There is no meaningful default action for an
1284 empty rule; every empty rule must have an explicit action unless the
1285 rule's value does not matter.
1287 `$N' with N zero or negative is allowed for reference to tokens and
1288 groupings on the stack _before_ those that match the current rule.
1289 This is a very risky practice, and to use it reliably you must be
1290 certain of the context in which the rule is applied. Here is a case in
1291 which you can use this reliably:
1293 foo: expr bar '+' expr { ... }
1294 | expr bar '-' expr { ... }
1298 { previous_expr = $0; }
1301 As long as `bar' is used only in the fashion shown here, `$0' always
1302 refers to the `expr' which precedes `bar' in the definition of `foo'.
1305 File: bison.info, Node: Action Types, Next: Mid-Rule Actions, Prev: Actions, Up: Semantics
1307 Data Types of Values in Actions
1308 -------------------------------
1310 If you have chosen a single data type for semantic values, the `$$'
1311 and `$N' constructs always have that data type.
1313 If you have used `%union' to specify a variety of data types, then
1314 you must declare a choice among these types for each terminal or
1315 nonterminal symbol that can have a semantic value. Then each time you
1316 use `$$' or `$N', its data type is determined by which symbol it refers
1317 to in the rule. In this example,
1323 `$1' and `$3' refer to instances of `exp', so they all have the data
1324 type declared for the nonterminal symbol `exp'. If `$2' were used, it
1325 would have the data type declared for the terminal symbol `'+'',
1326 whatever that might be.
1328 Alternatively, you can specify the data type when you refer to the
1329 value, by inserting `<TYPE>' after the `$' at the beginning of the
1330 reference. For example, if you have defined types as shown here:
1337 then you can write `$<itype>1' to refer to the first subunit of the
1338 rule as an integer, or `$<dtype>1' to refer to it as a double.