home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 285_01 / bisoninf.2 < prev    next >
Text File  |  1990-07-09  |  52KB  |  1,398 lines
  1. Info file bison.info, produced by Makeinfo, -*- Text -*- from input
  2. file bison.texinfo.
  3.  
  4. This file documents the Bison parser generator.
  5.  
  6. Copyright (C) 1988 Free Software Foundation, Inc.
  7.  
  8. Permission is granted to make and distribute verbatim copies of this
  9. manual provided the copyright notice and this permission notice are
  10. preserved on all copies.
  11.  
  12. Permission is granted to copy and distribute modified versions of
  13. this manual under the conditions for verbatim copying, provided also
  14. that the sections entitled ``Bison General Public License'' and
  15. ``Conditions for Using Bison'' are included exactly as in the
  16. original, and provided that the entire resulting derived work is
  17. distributed under the terms of a permission notice identical to this
  18. one.
  19.  
  20. Permission is granted to copy and distribute translations of this
  21. manual into another language, under the above conditions for modified
  22. versions, except that the text of the translations of the sections
  23. entitled ``Bison General Public License'' and ``Conditions for Using
  24. Bison'' must be approved for accuracy by the Foundation.
  25.  
  26.  
  27.  
  28. File: bison.info,  Node: Mfcalc Decl,  Next: Mfcalc Rules,  Prev: Multi-function Calc,  Up: Multi-function Calc
  29.  
  30. Declarations for `mfcalc'
  31. -------------------------
  32.  
  33. Here are the C and Bison declarations for the multi-function
  34. calculator.
  35.  
  36.      %{
  37.      #include <math.h>  /* For math functions, cos(), sin(), etc      */
  38.      #include "calc.h"  /* Contains definition of `symrec' */
  39.      %}
  40.      %union {
  41.      double     val;  /* For returning numbers.              */
  42.      symrec  *tptr;   /* For returning symbol-table pointers */
  43.      }
  44.      
  45.      %token <val>  NUM        /* Simple double precision number  */
  46.      %token <tptr> VAR FNCT   /* Variable and Function           */
  47.      %type  <val>  exp
  48.      
  49.      %right '='
  50.      %left '-' '+'
  51.      %left '*' '/'
  52.      %left NEG     /* Negation--unary minus */
  53.      %right '^'    /* Exponentiation        */
  54.      
  55.      /* Grammar follows */
  56.      
  57.      %%
  58.  
  59. The above grammar introduces only two new features of the Bison
  60. language.  These features allow semantic values to have various data
  61. types (*note Multiple Types::.).
  62.  
  63. The `%union' declaration specifies the entire list of possible types;
  64. this is instead of defining `YYSTYPE'.  The allowable types are now
  65. double-floats (for `exp' and `NUM') and pointers to entries in the
  66. symbol table.  *Note Union Decl::.
  67.  
  68. Since values can now have various types, it is necessary to associate
  69. a type with each grammar symbol whose semantic value is used.  These
  70. symbols are `NUM', `VAR', `FNCT', and `exp'.  Their declarations are
  71. augmented with information about their data type (placed between
  72. angle brackets).
  73.  
  74. The Bison construct `%type' is used for declaring nonterminal
  75. symbols, just as `%token' is used for declaring token types.  We have
  76. not used `%type' before because nonterminal symbols are normally
  77. declared implicitly by the rules that define them.  But `exp' must be
  78. declared explicitly so we can specify its value type.  *Note Type
  79. Decl::.
  80.  
  81.  
  82.  
  83. File: bison.info,  Node: Mfcalc Rules,  Next: Mfcalc Symtab,  Prev: Mfcalc Decl,  Up: Multi-function Calc
  84.  
  85. Grammar Rules for `mfcalc'
  86. --------------------------
  87.  
  88. Here are the grammar rules for the multi-function calculator.  Most
  89. of them are copied directly from `calc'; three rules, those which
  90. mention `VAR' or `FNCT', are new.
  91.  
  92.      input:   /* empty */
  93.              | input line
  94.      ;
  95.      
  96.      line:
  97.                '\n'
  98.              | exp '\n'   { printf ("\t%.10g\n", $1); }
  99.              | error '\n' { yyerrok;                  }
  100.      ;
  101.      
  102.      exp:      NUM                { $$ = $1;                         }
  103.              | VAR                { $$ = $1->value.var;              }
  104.              | VAR '=' exp        { $$ = $3; $1->value.var = $3;     }
  105.              | FNCT '(' exp ')'   { $$ = (*($1->value.fnctptr))($3); }
  106.              | exp '+' exp        { $$ = $1 + $3;                    }
  107.              | exp '-' exp        { $$ = $1 - $3;                    }
  108.              | exp '*' exp        { $$ = $1 * $3;                    }
  109.              | exp '/' exp        { $$ = $1 / $3;                    }
  110.              | '-' exp  %prec NEG { $$ = -$2;                        }
  111.              | exp '^' exp        { $$ = pow ($1, $3);               }
  112.              | '(' exp ')'        { $$ = $2;                         }
  113.      ;
  114.      /* End of grammar */
  115.      %%
  116.  
  117.  
  118.  
  119. File: bison.info,  Node: Mfcalc Symtab,  Prev: Mfcalc Rules,  Up: Multi-function Calc
  120.  
  121. Managing the Symbol Table for `mfcalc'
  122. --------------------------------------
  123.  
  124. The multi-function calculator requires a symbol table to keep track
  125. of the names and meanings of variables and functions.  This doesn't
  126. affect the grammar rules (except for the actions) or the Bison
  127. declarations, but it requires some additional C functions for support.
  128.  
  129. The symbol table itself consists of a linked list of records.  Its
  130. definition, which is kept in the header `calc.h', is as follows.  It
  131. provides for either functions or variables to be placed in the table.
  132.  
  133.      /* Data type for links in the chain of symbols.  */
  134.      struct symrec
  135.      {
  136.        char *name;  /* name of symbol              */
  137.        int type;    /* type of symbol: either VAR or FNCT */
  138.        union {
  139.          double var;           /* value of a VAR  */
  140.          double (*fnctptr)();  /* value of a FNCT */
  141.        } value;
  142.        struct symrec *next;    /* link field    */
  143.      };
  144.      
  145.      typedef struct symrec symrec;
  146.      
  147.      /* The symbol table: a chain of `struct symrec'.  */
  148.      extern symrec *sym_table;
  149.      
  150.      symrec *putsym ();
  151.      symrec *getsym ();
  152.  
  153. The new version of `main' includes a call to `init_table', a function
  154. that initializes the symbol table.  Here it is, and `init_table' as
  155. well:
  156.  
  157.      #include <stdio.h>
  158.      
  159.      main()
  160.      {
  161.        init_table ();
  162.        yyparse ();
  163.      }
  164.      
  165.      yyerror (s)  /* Called by yyparse on error */
  166.           char *s;
  167.      {
  168.        printf ("%s\n", s);
  169.      }
  170.      
  171.      struct init
  172.      {
  173.        char *fname;
  174.        double (*fnct)();
  175.      };
  176.      
  177.      struct init arith_fncts[]
  178.        = {
  179.            "sin", sin,
  180.            "cos", cos,
  181.            "atan", atan,
  182.            "ln", log,
  183.            "exp", exp,
  184.            "sqrt", sqrt,
  185.            0, 0
  186.          };
  187.      
  188.      /* The symbol table: a chain of `struct symrec'.  */
  189.      symrec *sym_table = (symrec *)0;
  190.      
  191.      init_table ()  /* puts arithmetic functions in table. */
  192.      {
  193.        int i;
  194.        symrec *ptr;
  195.        for (i = 0; arith_fncts[i].fname != 0; i++)
  196.          {
  197.            ptr = putsym (arith_fncts[i].fname, FNCT);
  198.            ptr->value.fnctptr = arith_fncts[i].fnct;
  199.          }
  200.      }
  201.  
  202. By simply editing the initialization list and adding the necessary
  203. include files, you can add additional functions to the calculator.
  204.  
  205. Two important functions allow look-up and installation of symbols in
  206. the symbol table.  The function `putsym' is passed a name and the
  207. type (`VAR' or `FNCT') of the object to be installed.  The object is
  208. linked to the front of the list, and a pointer to the object is
  209. returned.  The function `getsym' is passed the name of the symbol to
  210. look up.  If found, a pointer to that symbol is returned; otherwise
  211. zero is returned.
  212.  
  213.      symrec *
  214.      putsym (sym_name,sym_type)
  215.           char *sym_name;
  216.           int sym_type;
  217.      {
  218.        symrec *ptr;
  219.        ptr = (symrec *) malloc (sizeof(symrec));
  220.        ptr->name = (char *) malloc (strlen(sym_name)+1);
  221.        strcpy (ptr->name,sym_name);
  222.        ptr->type = sym_type;
  223.        ptr->value.var = 0; /* set value to 0 even if fctn.  */
  224.        ptr->next = (struct symrec *)sym_table;
  225.        sym_table = ptr;
  226.        return ptr;
  227.      }
  228.      
  229.      symrec *
  230.      getsym (sym_name)
  231.           char *sym_name;
  232.      {
  233.        symrec *ptr;
  234.        for (ptr = sym_table; ptr != (symrec *) 0;
  235.             ptr = (symrec *)ptr->next)
  236.          if (strcmp (ptr->name,sym_name) == 0)
  237.            return ptr;
  238.        return 0;
  239.      }
  240.  
  241. The function `yylex' must now recognize variables, numeric values,
  242. and the single-character arithmetic operators.  Strings of
  243. alphanumeric characters with a leading nondigit are recognized as
  244. either variables or functions depending on what the symbol table says
  245. about them.
  246.  
  247. The string is passed to `getsym' for look up in the symbol table.  If
  248. the name appears in the table, a pointer to its location and its type
  249. (`VAR' or `FNCT') is returned to `yyparse'.  If it is not already in
  250. the table, then it is installed as a `VAR' using `putsym'.  Again, a
  251. pointer and its type (which must be `VAR') is returned to `yyparse'.
  252.  
  253. No change is needed in the handling of numeric values and arithmetic
  254. operators in `yylex'.
  255.  
  256.      #include <ctype.h>
  257.      yylex()
  258.      {
  259.        int c;
  260.      
  261.        /* Ignore whitespace, get first nonwhite character.  */
  262.        while ((c = getchar ()) == ' ' || c == '\t');
  263.      
  264.        if (c == EOF)
  265.          return 0;
  266.      
  267.        /* Char starts a number => parse the number.  */
  268.        if (c == '.' || isdigit (c))
  269.          {
  270.            ungetc (c, stdin);
  271.            scanf ("%lf", &yylval.val);
  272.            return NUM;
  273.          }
  274.      
  275.        /* Char starts an identifier => read the name.  */
  276.        if (isalpha (c))
  277.          {
  278.            symrec *s;
  279.            static char *symbuf = 0;
  280.            static int length = 0;
  281.            int i;
  282.      
  283.            /* Initially make the buffer long enough
  284.               for a 40-character symbol name.  */
  285.            if (length == 0)
  286.              length = 40, symbuf = (char *)malloc (length + 1);
  287.      
  288.            i = 0;
  289.            do
  290.              {
  291.                /* If buffer is full, make it bigger.  */
  292.                if (i == length)
  293.                  {
  294.                    length *= 2;
  295.                    symbuf = (char *)realloc (symbuf, length + 1);
  296.                  }
  297.                /* Add this character to the buffer.  */
  298.                symbuf[i++] = c;
  299.                /* Get another character.  */
  300.                c = getchar ();
  301.              }
  302.            while (c != EOF && isalnum (c));
  303.      
  304.            ungetc (c, stdin);
  305.            symbuf[i] = '\0';
  306.      
  307.            s = getsym (symbuf);
  308.            if (s == 0)
  309.              s = putsym (symbuf, VAR);
  310.            yylval.tptr = s;
  311.            return s->type;
  312.          }
  313.      
  314.        /* Any other character is a token by itself.  */
  315.        return c;
  316.      }
  317.  
  318. This program is both powerful and flexible. You may easily add new
  319. functions, and it is a simple job to modify this code to install
  320. predefined variables such as `pi' or `e' as well.
  321.  
  322.  
  323.  
  324. File: bison.info,  Node: Exercises,  Prev: Multi-function calc,  Up: Examples
  325.  
  326. Exercises
  327. =========
  328.  
  329.   1. Add some new functions from `math.h' to the initialization list.
  330.  
  331.   2. Add another array that contains constants and their values. 
  332.      Then modify `init_table' to add these constants to the symbol
  333.      table.  It will be easiest to give the constants type `VAR'.
  334.  
  335.   3. Make the program report an error if the user refers to an
  336.      uninitialized variable in any way except to store a value in it.
  337.  
  338.  
  339.  
  340. File: bison.info,  Node: Grammar File*  Hext" IhtUrUQbσ,  PZU].$αQ=XZS:¬  5X*W╕!59╖╖C╣Q:╢░╣#4╢2║à!4╣╖╖:0╡▓╣É0╣É4╖8:║0É1╖╖:2╝:│92▓É3╣0╢╢░╣9╕2▒┤│4▒░║4╖╖0╖2897▓:▒es a C-language function that recognizes correct instances of
  341. the grammar.
  342.  
  343. The Bison grammar input file conventionally has a name ending in `.y'.
  344.  
  345. * Menu:
  346.  
  347. * Grammar Outline::    Overall layout of the grammar file.
  348. * Symbols::            Terminal and nonterminal symbols.
  349. * Rules::              How to write grammar rules.
  350. * Recursion::           Writing recursive rules.
  351. * Semantics::          Semantic values and actions.
  352. * Declarations::       All kinds of Bison declarations are described here.
  353.  
  354.  
  355.  
  356. File: bison.info,  Node: Grammar Outline,  Next: Symbols,  Prev: Grammar File,  Up: Grammar File
  357.  
  358. Outline of a Bison Grammar
  359. ==========================
  360.  
  361. A Bison grammar file has four main sections, shown here with the
  362. appropriate delimiters:
  363.  
  364.      %{
  365.      C DECLARATIONS
  366.      %}
  367.      
  368.      BISON DECLARATIONS
  369.      
  370.      %%
  371.      GRAMMAR RULES
  372.      %%
  373.      
  374.      ADDITIONAL C CODE
  375.  
  376. Comments enclosed in `/* ... */' may appear in any of the sections.
  377.  
  378. * Menu:
  379.  
  380. * C Declarations::      Syntax and usage of the C declarations section.
  381. * Bison Declarations::  Syntax and usage of the Bison declarations section.
  382. * Grammar Rules::       Syntax and usage of the grammar rules section.
  383. * C Code::              Syntax and usage of the additional C code section.
  384.  
  385.  
  386.  
  387. File: bison.info,  Node: C Declarations,  Next: Bison Declarations,  Prev: Grammar Outline,  Up: Grammar Outline
  388.  
  389. The C Declarations Section
  390. --------------------------
  391.  
  392. The C DECLARATIONS section contains macro definitions and
  393. declarations of functions and variables that are used in the actions
  394. in the grammar rules.  These are copied to the beginning of the
  395. parser file so that they precede the definition of `yylex'.  You can
  396. use `#include' to get the declarations from a header file.  If you
  397. don't need any C declarations, you may omit the `%{' and `%}'
  398. delimiters that bracket this section.
  399.  
  400.  
  401.  
  402. File: bison.info,  Node: Bison Declarations,  Next: Grammar Rules,  Prev: C Declarations,  Up: Grammar Outline
  403.  
  404. The Bison Declarations Section
  405. ------------------------------
  406.  
  407. The BISON DECLARATIONS section contains declarations that define
  408. terminal and nonterminal symbols, specify precedence, and so on.  In
  409. some simple grammars you may not need any declarations.  *Note
  410. Declarations::.
  411.  
  412.  
  413.  
  414. File: bison.info,  Node: Grammar Rules,  Next: C Code,  Prev: Bison Declarations,  Up: Grammar Outline
  415.  
  416. The Grammar Rules Section
  417. -------------------------
  418.  
  419. The "grammar rules" section contains one or more Bison grammar rules,
  420. and nothing else.  *Note Rules::.
  421.  
  422. There must always be at least one grammar rule, and the first `%%'
  423. (which precedes the grammar rules) may never be omitted even if it is
  424. the first thing in the file.
  425.  
  426.  
  427.  
  428. File: bison.info,  Node: C Code,  Prev: Grammar Rules,  Up: Grammar Outline
  429.  
  430. The Additional C Code Section
  431. -----------------------------
  432.  
  433. The ADDITIONAL C CODE section is copied verbatim to the end of the
  434. parser file, just as the C DECLARATIONS section is copied to the
  435. beginning.  This is the most convenient place to put anything that
  436. you want to have in the parser file but which need not come before
  437. the definition of `yylex'.  For example, the definitions of `yylex'
  438. and `yyerror' often go here.  *Note Interface::.
  439.  
  440. If the last section is empty, you may omit the `%%' that separates it
  441. from the grammar rules.
  442.  
  443. The Bison parser itself contains many static variables whose names
  444. start with `yy' and many macros whose names start with `YY'.  It is a
  445. good idea to avoid using any such names (except those documented in
  446. this manual) in the additional C code section of the grammar file.
  447.  
  448.  
  449.  
  450. File: bison.info,  Node: Symbols,  Next: Rules,  Prev: Grammar Outline,  Up: Grammar File
  451.  
  452. Symbols, Terminal and Nonterminal
  453. =================================
  454.  
  455. "Symbols" in Bison grammars represent the grammatical classifications
  456. of the language.
  457.  
  458. A "terminal symbol" (also known as a "token type") represents a class
  459. of syntactically equivalent tokens.  You use the symbol in grammar
  460. rules to mean that a token in that class is allowed.  The symbol is
  461. represented in the Bison parser by a numeric code, and the `yylex'
  462. function returns a token type code to indicate what kind of token has
  463. been read.  You don't need to know what the code value is; you can
  464. use the symbol to stand for it.
  465.  
  466. A "nonterminal symbol" stands for a class of syntactically equivalent
  467. groupings.  The symbol name is used in writing grammar rules.  By
  468. convention, it should be all lower case.
  469.  
  470. Symbol names can contain letters, digits (not at the beginning),
  471. underscores and periods.  Periods make sense only in nonterminals.
  472.  
  473. There are two ways of writing terminal symbols in the grammar:
  474.  
  475.    * A "named token type" is written with an identifier, like an
  476.      identifier in C.  By convention, it should be all upper case. 
  477.      Each such name must be defined with a Bison declaration such as
  478.      `%token'.  *Note Token Decl::.
  479.  
  480.    * A "character token type" (or "literal token") is written in the
  481.      grammar using the same syntax used in C for character constants;
  482.      for example, `'+'' is a character token type.  A character token
  483.      type doesn't need to be declared unless you need to specify its
  484.      semantic value data type (*note Value Type::.), associativity,
  485.      or precedence (*note Precedence::.).
  486.  
  487.      By convention, a character token type is used only to represent
  488.      a token that consists of that particular character.  Thus, the
  489.      token type `'+'' is used to represent the character `+' as a
  490.      token.  Nothing enforces this convention, but if you depart from
  491.      it, your program will confuse other readers.
  492.  
  493.      All the usual escape sequences used in character literals in C
  494.      can be used in Bison as well, but you must not use the null
  495.      character as a character literal because its ASCII code, zero,
  496.      is the code `yylex' returns for end-of-input (*note Lexical::.).
  497.  
  498. How you choose to write a terminal symbol has no effect on its
  499. grammatical meaning.  That depends only on where it appears in rules
  500. and on when the parser function returns that symbol.
  501.  
  502. The value returned by `yylex' is always one of the terminal symbols
  503. (or 0 for end-of-input).  Whichever way you write the token type in
  504. the grammar rules, you write it the same way in the definition of
  505. `yylex'.  The numeric code for a character token type is simply the
  506. ASCII code for the character, so `yylex' can use the identical
  507. character constant to generate the requisite code.  Each named token
  508. type becomes a C macro in the parser file, so `yylex' can use the
  509. name to stand for the code.  (This is why periods don't make sense in
  510. terminal symbols.)  *Note Lexical::.
  511.  
  512. If `yylex' is defined in a separate file, you need to arrange for the
  513. token-type macro definitions to be available there.  Use the `-d'
  514. option when you run Bison, so that it will write these macro
  515. definitions into a separate header file `NAME.tab.h' which you can
  516. include in the other source files that need it.  *Note Invocation::.
  517.  
  518. The symbol `error' is a terminal symbol reserved for error recovery
  519. (*note Error Recovery::.); you shouldn't use it for any other purpose.
  520. In particular, `yylex' should never return this value.
  521.  
  522.  
  523.  
  524. File: bison.info,  Node: Rules,  Next: Recursion,  Prev: Symbols,  Up: Grammar File
  525.  
  526. Syntax of Grammar Rules
  527. =======================
  528.  
  529. A Bison grammar rule has the following general form:
  530.  
  531.      RESULT: COMPONENTS...
  532.              ;
  533.  
  534. where RESULT is the nonterminal symbol that this rule describes and
  535. COMPONENTS are various terminal and nonterminal symbols that are put
  536. together by this rule (*note Symbols::.).  For example,
  537.  
  538.      exp:      exp '+' exp
  539.              ;
  540.  
  541. says that two groupings of type `exp', with a `+' token in between,
  542. can be combined into a larger grouping of type `exp'.
  543.  
  544. Whitespace in rules is significant only to separate symbols.  You can
  545. add extra whitespace as you wish.
  546.  
  547. Scattered among the components can be ACTIONS that determine the
  548. semantics of the rule.  An action looks like this:
  549.  
  550.      {C STATEMENTS}
  551.  
  552. Usually there is only one action and it follows the components. 
  553. *Note Actions::.
  554.  
  555. Multiple rules for the same RESULT can be written separately or can
  556. be joined with the vertical-bar character `|' as follows:
  557.  
  558.      RESULT:   RULE1-COMPONENTS...
  559.              | RULE2-COMPONENTS...
  560.              ...
  561.              ;
  562.  
  563. They are still considered distinct rules even when joined in this way.
  564.  
  565. If COMPONENTS in a rule is empty, it means that RESULT can match the
  566. empty string.  For example, here is how to define a comma-separated
  567. sequence of zero or more `exp' groupings:
  568.  
  569.      expseq:   /* empty */
  570.              | expseq1
  571.              ;
  572.      
  573.      expseq1:  exp
  574.              | expseq1 ',' exp
  575.              ;
  576.  
  577. It is customary to write a comment `/* empty */' in each rule with no
  578. components.
  579.  
  580.  
  581.  
  582. File: bison.info,  Node: Recursion,  Next: Semantics,  Prev: Rules,  Up: Grammar File
  583.  
  584. Recursive Rules
  585. ===============
  586.  
  587. A rule is called "recursive" when its RESULT nonterminal appears also
  588. on its right hand side.  Nearly all Bison grammars need to use
  589. recursion, because that is the only way to define a sequence of any
  590. number of somethings.  Consider this recursive definition of a
  591. comma-separated sequence of one or more expressions:
  592.  
  593.      expseq1:  exp
  594.              | expseq1 ',' exp
  595.              ;
  596.  
  597. Since the recursive use of `expseq1' is the leftmost symbol in the
  598. right hand side, we call this "left recursion".  By contrast, here
  599. the same construct is defined using "right recursion":
  600.  
  601.      expseq1:  exp
  602.              | exp ',' expseq1
  603.              ;
  604.  
  605. Any kind of sequence can be defined using either left recursion or
  606. right recursion, but you should always use left recursion, because it
  607. can parse a sequence of any number of elements with bounded stack
  608. space.  Right recursion uses up space on the Bison stack in
  609. proportion to the number of elements in the sequence, because all the
  610. elements must be shifted onto the stack before the rule can be
  611. applied even once.  *Note Algorithm::, for further explanation of this.
  612.  
  613. "Indirect" or "mutual" recursion occurs when the result of the rule
  614. does not appear directly on its right hand side, but does appear in
  615. rules for other nonterminals which do appear on its right hand side. 
  616. For example:
  617.  
  618.      expr:     primary
  619.              | primary '+' primary
  620.              ;
  621.      
  622.      primary:  constant
  623.              | '(' expr ')'
  624.              ;
  625.  
  626. defines two mutually-recursive nonterminals, since each refers to the
  627. other.
  628.  
  629.  
  630.  
  631. File: bison.info,  Node: Semantics,  Next: Declarations,  Prev: Recursion,  Up: Grammar File
  632.  
  633. The Semantics of the Language
  634. =============================
  635.  
  636. The grammar rules for a language determine only the syntax.  The
  637. semantics are determined by the semantic values associated with
  638. various tokens and groupings, and by the actions taken when various
  639. groupings are recognized.
  640.  
  641. For example, the calculator calculates properly because the value
  642. associated with each expression is the proper number; it adds
  643. properly because the action for the grouping `X + Y' is to add the
  644. numbers associated with X and Y.
  645.  
  646. * Menu:
  647.  
  648. * Value Type::       Specifying one data type for all semantic values.
  649. * Multiple Types::   Specifying several alternative data types.
  650. * Actions::          An action is the semantic definition of a grammar rule.
  651. * Action Types::     Specifying data types for actions to operate on.
  652. * Mid-Rule Actions:: Most actions go at the end of a rule.
  653.                       This says when, why and how to use the exceptional
  654.                       action in the middle of a rule.
  655.  
  656.  
  657.  
  658. File: bison.info,  Node: Value Type,  Next: Multiple Types,  Prev: Semantics,  Up: Semantics
  659.  
  660. The Data Types of Semantic Values
  661. ---------------------------------
  662.  
  663. In a simple program it may be sufficient to use the same data type
  664. for the semantic values of all language constructs.  This was true in
  665. the RPN and infix calculator examples (*note RPN Calc::.).
  666.  
  667. Bison's default is to use type `int' for all semantic values.  To
  668. specify some other type, define `YYSTYPE' as a macro, like this:
  669.  
  670.      #define YYSTYPE double
  671.  
  672. This macro definition must go in the C declarations section of the
  673. grammar file (*note Grammar Outline::.).
  674.  
  675.  
  676.  
  677. File: bison.info,  Node: Multiple Types,  Next: Actions,  Prev: Value Type
  678.  
  679. More Than One Type for Semantic Values
  680. --------------------------------------
  681.  
  682. In most programs, you will need different data types for different
  683. kinds of tokens and groupings.  For example, a numeric constant may
  684. need type `int' or `long', while a string constant needs type `char
  685. *', and an identifier might need a pointer to an entry in the symbol
  686. table.
  687.  
  688. To use more than one data type for semantic values in one parser,
  689. Bison requires you to do two things:
  690.  
  691.    * Specify the entire collection of possible data types, with the
  692.      `%union' Bison declaration (*note Union Decl::.).
  693.  
  694.    * Choose one of those types for each symbol (terminal or
  695.      nonterminal) for which semantic values are used.  This is done
  696.      for tokens with the `%token' Bison declaration (*note Token
  697.      Decl::.) and for groupings with the `%type' Bison declaration
  698.      (*note Type Decl::.).
  699.  
  700.  
  701.  
  702. File: bison.info,  Node: Actions,  Next: Action Types,  Prev: Multiple Types,  Up: Semantics
  703.  
  704. Actions
  705. -------
  706.  
  707. An action accompanies a syntactic rule and contains C code to be
  708. executed each time an instance of that rule is recognized.  The task
  709. of most actions is to compute a semantic value for the grouping built
  710. by the rule from the semantic values associated with tokens or
  711. smaller groupings.
  712.  
  713. An action consists of C statements surrounded by braces, much like a
  714. compound statement in C.  It can be placed at any position in the
  715. rule; it is executed at that position.  Most rules have just one
  716. action at the end of the rule, following all the components.  Actions
  717. in the middle of a rule are tricky and used only for special purposes
  718. (*note Mid-Rule Actions::.).
  719.  
  720. The C code in an action can refer to the semantic values of the
  721. components matched by the rule with the construct `$N', which stands
  722. for the value of the Nth component.  The semantic value for the
  723. grouping being constructed is `$$'.  (Bison translates both of these
  724. constructs into array element references when it copies the actions
  725. into the parser file.)
  726.  
  727. Here is a typical example:
  728.  
  729.      exp:    ...
  730.              | exp '+' exp
  731.                  { $$ = $1 + $3; }
  732.  
  733. This rule constructs an `exp' from two smaller `exp' groupings
  734. connected by a plus-sign token.  In the action, `$1' and `$3' refer
  735. to the semantic values of the two component `exp' groupings, which
  736. are the first and third symbols on the right hand side of the rule. 
  737. The sum is stored into `$$' so that it becomes the semantic value of
  738. the addition-expression just recognized by the rule.  If there were a
  739. useful semantic value associated with the `+' token, it could be
  740. referred to as `$2'.
  741.  
  742. `$N' with N zero or negative is allowed for reference to tokens and
  743. groupings on the stack *before* those that match the current rule. 
  744. This is a very risky practice, and to use it reliably you must be
  745. certain of the context in which the rule is applied.  Here is a case
  746. in which you can use this reliably:
  747.  
  748.      foo:      expr bar '+' expr  { ... }
  749.              | expr bar '-' expr  { ... }
  750.              ;
  751.      
  752.      bar:      /* empty */
  753.              { previous_expr = $0; }
  754.              ;
  755.  
  756. As long as `bar' is used only in the fashion shown here, `$0' always
  757. refers to the `expr' which precedes `bar' in the definition of `foo'.
  758.  
  759.  
  760.  
  761. File: bison.info,  Node: Action Types,  Next: Mid-Rule Actions,  Prev: Actions,  Up: Semantics
  762.  
  763. Data Types of Values in Actions
  764. -------------------------------
  765.  
  766. If you have chosen a single data type for semantic values, the `$$'
  767. and `$N' constructs always have that data type.
  768.  
  769. If you have used `%union' to specify a variety of data types, then
  770. you must declare a choice among these types for each terminal or
  771. nonterminal symbol that can have a semantic value.  Then each time
  772. you use `$$' or `$N', its data type is determined by which symbol it
  773. refers to in the rule.  In this example,
  774.  
  775.      exp:    ...
  776.              | exp '+' exp
  777.                  { $$ = $1 + $3; }
  778.  
  779. `$3' and `$$' refer to instances of `exp', so they all have the data
  780. type declared for the nonterminal symbol `exp'.  If `$2' were used,
  781. it would have the data type declared for the terminal symbol `'+'',
  782. whatever that might be.
  783.  
  784. Alternatively, you can specify the data type when you refer to the
  785. value, by inserting `<TYPE>' after the `$' at the beginning of the
  786. reference.  For example, if you have defined types as shown here:
  787.  
  788.      %union {
  789.        int itype;
  790.        double dtype;
  791.      }
  792.  
  793. then you can write `$<itype>1' to refer to the first subunit of the
  794. rule as an integer, or `$<dtype>1' to refer to it as a double.
  795.  
  796.  
  797.  
  798. File: bison.info,  Node: Mid-Rule Actions,  Prev: Action Types,  Up: Semantics
  799.  
  800. Actions in Mid-Rule
  801. -------------------
  802.  
  803. Occasionally it is useful to put an action in the middle of a rule. 
  804. These actions are written just like usual end-of-rule actions, but
  805. they are executed before the parser even recognizes the following
  806. components.
  807.  
  808. A mid-rule action may refer to the components preceding it using
  809. `$N', but it may not refer to subsequent components because it is run
  810. before they are parsed.
  811.  
  812. The mid-rule action itself counts as one of the components of the rule.
  813. This makes a difference when there is another action later in the
  814. same rule (and usually there is another at the end): you have to
  815. count the actions along with the symbols when working out which
  816. number N to use in `$N'.
  817.  
  818. The mid-rule action can also have a semantic value.  This can be set
  819. within that action by an assignment to `$$', and can referred to by
  820. later actions using `$N'.  Since there is no symbol to name the
  821. action, there is no way to declare a data type for the value in
  822. advance, so you must use the `$<...>' construct to specify a data
  823. type each time you refer to this value.
  824.  
  825. Here is an example from a hypothetical compiler, handling a `let'
  826. statement that looks like `let (VARIABLE) STATEMENT' and serves to
  827. create a variable named VARIABLE temporarily for the duration of
  828. STATEMENT.  To parse this construct, we must put VARIABLE into the
  829. symbol table while STATEMENT is parsed, then remove it afterward. 
  830. Here is how it is done:
  831.  
  832.      stmt:   LET '(' var ')'
  833.                      { $<context>$ = push_context ();
  834.                        declare_variable ($3); }
  835.              stmt    { $$ = $6;
  836.                        pop_context ($<context>5); }
  837.  
  838. As soon as `let (VARIABLE)' has been recognized, the first action is
  839. run.  It saves a copy of the current semantic context (the list of
  840. accessible variables) as its semantic value, using alternative
  841. `context' in the data-type union.  Then it calls `declare_variable'
  842. to add the new variable to that list.  Once the first action is
  843. finished, the embedded statement `stmt' can be parsed.  Note that the
  844. mid-rule action is component number 5, so the `stmt' is component
  845. number 6.
  846.  
  847. After the embedded statement is parsed, its semantic value becomes
  848. the value of the entire `let'-statement.  Then the semantic value
  849. from the earlier action is used to restore the prior list of
  850. variables.  This removes the temporary `let'-variable from the list
  851. so that it won't appear to exist while the rest of the program is
  852. parsed.
  853.  
  854. Taking action before a rule is completely recognized often leads to
  855. conflicts since the parser must commit to a parse in order to execute
  856. the action.  For example, the following two rules, without mid-rule
  857. actions, can coexist in a working parser because the parser can shift
  858. the open-brace token and look at what follows before deciding whether
  859. there is a declaration or not:
  860.  
  861.      compound: '{' declarations statements '}'
  862.              | '{' statements '}'
  863.              ;
  864.  
  865. But when we add a mid-rule action as follows, the rules become
  866. nonfunctional:
  867.  
  868.      compound: { prepare_for_local_variables (); }
  869.                '{' declarations statements '}'
  870.  
  871.              | '{' statements '}'
  872.              ;
  873.  
  874. Now the parser is forced to decide whether to run the mid-rule action
  875. when it has read no farther than the open-brace.  In other words, it
  876. must commit to using one rule or the other, without sufficient
  877. information to do it correctly.  (The open-brace token is what is
  878. called the "look-ahead" token at this time, since the parser is still
  879. deciding what to do about it.  *Note Look-Ahead::.)
  880.  
  881. You might think that you could correct the problem by putting
  882. identical actions into the two rules, like this:
  883.  
  884.      compound: { prepare_for_local_variables (); }
  885.                '{' declarations statements '}'
  886.              | { prepare_for_local_variables (); }
  887.                '{' statements '}'
  888.              ;
  889.  
  890. But this does not help, because Bison does not realize that the two
  891. actions are identical.  (Bison never tries to understand the C code
  892. in an action.)
  893.  
  894. If the grammar is such that a declaration can be distinguished from a
  895. statement by the first token (which is true in C), then one solution
  896. which does work is to put the action after the open-brace, like this:
  897.  
  898.      compound: '{' { prepare_for_local_variables (); }
  899.                declarations statements '}'
  900.              | '{' statements '}'
  901.              ;
  902.  
  903. Now the first token of the following declaration or statement, which
  904. would in any case tell Bison which rule to use, can still do so.
  905.  
  906. Another solution is to bury the action inside a nonterminal symbol
  907. which serves as a subroutine:
  908.  
  909.      subroutine: /* empty */
  910.                { prepare_for_local_variables (); }
  911.              ;
  912.      
  913.      compound: subroutine
  914.                '{' declarations statements '}'
  915.              | subroutine
  916.                '{' statements '}'
  917.              ;
  918.  
  919. Now Bison can execute the action in the rule for `subroutine' without
  920. deciding which rule for `compound' it will eventually use.  Note that
  921. the action is now at the end of its rule.  Any mid-rule action can be
  922. converted to an end-of-rule action in this way, and this is what
  923. Bison actually does to implement mid-rule actions.
  924.  
  925.  
  926.  
  927. File: bison.info,  Node: Declarations,  Prev: Semantics,  Up: Grammar File
  928.  
  929. Bison Declarations
  930. ==================
  931.  
  932. The "Bison declarations" section of a Bison grammar defines the
  933. symbols used in formulating the grammar and the data types of
  934. semantic values.  *Note Symbols::.
  935.  
  936. All token type names (but not single-character literal tokens such as
  937. `'+'' and `'*'') must be declared.  Nonterminal symbols must be
  938. declared if you need to specify which data type to use for the
  939. semantic value (*note Multiple Types::.).
  940.  
  941. The first rule in the file also specifies the start symbol, by default.
  942. If you want some other symbol to be the start symbol, you must
  943. declare it explicitly (*note Language and Grammar::.).
  944.  
  945. * Menu:
  946.  
  947. * Token Decl::       Declaring terminal symbols.
  948. * Precedence Decl::  Declaring terminals with precedence and associativity.
  949. * Union Decl::       Declaring the set of all semantic value types.
  950. * Type Decl::        Declaring the choice of type for a nonterminal symbol.
  951. * Expect Decl::      Suppressing warnings about shift/reduce conflicts.
  952. * Start Decl::       Specifying the start symbol.
  953. * Pure Decl::        Requesting a reentrant parser.
  954. * Decl Summary::     Table of all Bison declarations.
  955.  
  956.  
  957.  
  958. File: bison.info,  Node: Token Decl,  Next: Precedence Decl,  Prev: Declarations,  Up: Declarations
  959.  
  960. Declaring Token Type Names
  961. --------------------------
  962.  
  963. The basic way to declare a token type name (terminal symbol) is as
  964. follows:
  965.  
  966.      %token NAME
  967.  
  968. Bison will convert this into a `#define' directive in the parser, so
  969. that the function `yylex' (if it is in this file) can use the name
  970. NAME to stand for this token type's code.
  971.  
  972. Alternatively you can use `%left', `%right', or `%nonassoc' instead
  973. of `%token', if you wish to specify precedence.  *Note Precedence
  974. Decl::.
  975.  
  976. You can explicitly specify the numeric code for a token type by
  977. appending an integer value in the field immediately following the
  978. token name:
  979.  
  980.      %token NUM 300
  981.  
  982. It is generally best, however, to let Bison choose the numeric codes
  983. for all token types.  Bison will automatically select codes that
  984. don't conflict with each other or with ASCII characters.
  985.  
  986. In the event that the stack type is a union, you must augment the
  987. `%token' or other token declaration to include the data type
  988. alternative delimited by angle-brackets (*note Multiple Types::.). 
  989. For example:
  990.  
  991.      %union {              /* define stack type */
  992.        double val;
  993.        symrec *tptr;
  994.      }
  995.      %token <val> NUM      /* define token NUM and its type */
  996.  
  997.  
  998.  
  999. File: bison.info,  Node: Precedence Decl,  Next: Token Decl,  Prev: Union Decl,  Up: Declarations
  1000.  
  1001. Declaring Operator Precedence
  1002. -----------------------------
  1003.  
  1004. Use the `%left', `%right' or `%nonassoc' declaration to declare a
  1005. token and specify its precedence and associativity, all at once. 
  1006. These are called "precedence declarations".  *Note Precedence::, for
  1007. general information on operator precedence.
  1008.  
  1009. The syntax of a precedence declaration is the same as that of
  1010. `%token': either
  1011.  
  1012.      %left SYMBOLS...
  1013.  
  1014.  or
  1015.  
  1016.      %left <TYPE> SYMBOLS...
  1017.  
  1018.  And indeed any of these declarations serves the purposes of `%token'.
  1019. But in addition, they specify the associativity and relative
  1020. precedence for all the SYMBOLS:
  1021.  
  1022.    * The associativity of an operator OP determines how repeated uses
  1023.      of the operator nest: whether `X OP Y OP Z' is parsed by
  1024.      grouping X with Y first or by grouping Y with Z first.  `%left'
  1025.      specifies left-associativity (grouping X with Y first) and
  1026.      `%right' specifies right-associativity (grouping Y with Z
  1027.      first).  `%nonassoc' specifies no associativity, which means
  1028.      that `X OP Y OP Z' is considered a syntax error.
  1029.  
  1030.    * The precedence of an operator determines how it nests with other
  1031.      operators.  All the tokens declared in a single precedence
  1032.      declaration have equal precedence and nest together according to
  1033.      their associativity.  When two tokens declared in different
  1034.      precedence declarations associate, the one declared later has
  1035.      the higher precedence and is grouped first.
  1036.  
  1037.  
  1038.  
  1039. File: bison.info,  Node: Union Decl,  Next: Type Decl,  Prev: Precedence Decl,  Up: Declarations
  1040.  
  1041. Declaring the Collection of Value Types
  1042. ---------------------------------------
  1043.  
  1044. The `%union' declaration specifies the entire collection of possible
  1045. data types for semantic values.  The keyword `%union' is followed by
  1046. a pair of braces containing the same thing that goes inside a `union'
  1047. in C.  For example:
  1048.  
  1049.      %union {
  1050.        double val;
  1051.        symrec *tptr;
  1052.      }
  1053.  
  1054. This says that the two alternative types are `double' and `symrec *'.
  1055. They are given names `val' and `tptr'; these names are used in the
  1056. `%token' and `%type' declarations to pick one of the types for a
  1057. terminal or nonterminal symbol (*note Type Decl::.).
  1058.  
  1059. Note that, unlike making a `union' declaration in C, you do not write
  1060. a semicolon after the closing brace.
  1061.  
  1062.  
  1063.  
  1064. File: bison.info,  Node: Type Decl,  Next: Expect Decl,  Prev: Union Decl,  Up: Declarations
  1065.  
  1066. Declaring Value Types of Nonterminal Symbols
  1067. --------------------------------------------
  1068.  
  1069. When you use `%union' to specify multiple value types, you must
  1070. declare the value type of each nonterminal symbol for which values
  1071. are used.  This is done with a `%type' declaration, like this:
  1072.  
  1073.      %type <TYPE> NONTERMINAL...
  1074.  
  1075.  Here NONTERMINAL is the name of a nonterminal symbol, and TYPE is the
  1076. name given in the `%union' to the alternative that you want (*note
  1077. Union Decl::.).  You can give any number of nonterminal symbols in
  1078. the same `%type' declaration, if they have the same value type.  Use
  1079. spaces to separate the symbol names.
  1080.  
  1081.  
  1082.  
  1083. File: bison.info,  Node: Expect Decl,  Next: Start Decl,  Prev: Type Decl,  Up: Declarations
  1084.  
  1085. Preventing Warnings about Conflicts
  1086. -----------------------------------
  1087.  
  1088. Bison normally warns if there are any conflicts in the grammar (*note
  1089. Shift/Reduce::.), but most real grammars have harmless shift/reduce
  1090. conflicts which are resolved in a predictable way and would be
  1091. difficult to eliminate.  It is desirable to suppress the warning
  1092. about these conflicts unless the number of conflicts changes.  You
  1093. can do this with the `%expect' declaration.
  1094.  
  1095. The declaration looks like this:
  1096.  
  1097.      %expect N
  1098.  
  1099. Here N is a decimal integer.  The declaration says there should be no
  1100. warning if there are N shift/reduce conflicts and no reduce/reduce
  1101. conflicts.  The usual warning is given if there are either more or
  1102. fewer conflicts, or if there are any reduce/reduce conflicts.
  1103.  
  1104. In general, using `%expect' involves these steps:
  1105.  
  1106.    * Compile your grammar without `%expect'.  Use the `-v' option to
  1107.      get a verbose list of where the conflicts occur.  Bison will
  1108.      also print the number of conflicts.
  1109.  
  1110.    * Check each of the conflicts to make sure that Bison's default
  1111.      resolution is what you really want.  If not, rewrite the grammar
  1112.      and go back to the beginning.
  1113.  
  1114.    * Add an `%expect' declaration, copying the number N from the
  1115.      number which Bison printed.
  1116.  
  1117. Now Bison will stop annoying you about the conflicts you have
  1118. checked, but it will warn you again if changes in the grammer result
  1119. in additional conflicts.
  1120.  
  1121.  
  1122.  
  1123. File: bison.info,  Node: Start Decl,  Next: Pure Decl,  Prev: Expect Decl,  Up: Declarations
  1124.  
  1125. Declaring the Start-Symbol
  1126. --------------------------
  1127.  
  1128. Bison assumes by default that the start symbol for the grammar is the
  1129. first nonterminal specified in the grammar specification section. 
  1130. The programmer may override this restriction with the `%start'
  1131. declaration as follows:
  1132.  
  1133.      %start SYMBOL
  1134.  
  1135.  
  1136.  
  1137. File: bison.info,  Node: Pure Decl,  Next: Decl Summary,  Prev: Start Decl,  Up: Declarations
  1138.  
  1139. Requesting a Pure (Reentrant) Parser
  1140. ------------------------------------
  1141.  
  1142. A reentrant program is one which does not alter in the course of
  1143. execution.  Reentrancy is important whenever asynchronous execution
  1144. is possible; for example, a nonreentrant program may not be safe to
  1145. call from a signal handler.  In systems with multiple threads of
  1146. control, a nonreentrant program must be called only within interlocks.
  1147.  
  1148. The Bison parser is not normally a reentrant program, because it uses
  1149. two statically allocated variables for communication with `yylex'. 
  1150. These variables are `yylval' and `yylloc'.
  1151.  
  1152. The Bison declaration `%pure_parser' says that you want the parser to
  1153. be reentrant.  It looks like this:
  1154.  
  1155.      %pure_parser
  1156.  
  1157. The effect is that the the two communication variables become
  1158. automatic variables in `yyparse', and a different calling convention
  1159. is used for the lexical analyzer function `yylex'.  The convention
  1160. for calling `yyparse' is unchanged.  *Note Lexical::, for the details
  1161. of this.
  1162.  
  1163.  
  1164.  
  1165. File: bison.info,  Node: Decl Summary,  Prev: Pure Decl,  Up: Declarations
  1166.  
  1167. Bison Declaration Summary
  1168. -------------------------
  1169.  
  1170. Here is a summary of all Bison declarations:
  1171.  
  1172. `%union'
  1173.      Declare the collection of data types that semantic values may
  1174.      have (*note Union Decl::.).
  1175.  
  1176. `%token'
  1177.      Declare a terminal symbol (token type name) with no precedence
  1178.      or associativity specified (*note Token Decl::.).
  1179.  
  1180. `%right'
  1181.      Declare a terminal symbol (token type name) that is
  1182.      right-associative (*note Precedence Decl::.).
  1183.  
  1184. `%left'
  1185.      Declare a terminal symbol (token type name) that is
  1186.      left-associative (*note Precedence Decl::.).
  1187.  
  1188. `%nonassoc'
  1189.      Declare a terminal symbol (token type name) that is
  1190.      nonassociative (using it in a way that would be associative is a
  1191.      syntax error) (*note Precedence Decl::.).
  1192.  
  1193. `%type'
  1194.      Declare the type of semantic values for a nonterminal symbol
  1195.      (*note Type Decl::.).
  1196.  
  1197. `%start'
  1198.      Specify the grammar's start symbol (*note Start Decl::.).
  1199.  
  1200. `%expect'
  1201.      Declare the expected number of shift-reduce conflicts (*note
  1202.      Expect Decl::.).
  1203.  
  1204. `%pure_parser'
  1205.      Request a pure (reentrant) parser program (*note Pure Decl::.).
  1206.  
  1207.  
  1208.  
  1209. File: bison.info,  Node: Interface,  Next: Algorithm,  Prev: Grammar File,  Up: Top
  1210.  
  1211. Parser C-Language Interface
  1212. ***************************
  1213.  
  1214. The Bison parser is actually a C function named `yyparse'.  Here we
  1215. describe the interface conventions of `yyparse' and the other
  1216. functions that it needs to use.
  1217.  
  1218. Keep in mind that the parser uses many C identifiers starting with
  1219. `yy' and `YY' for internal purposes.  If you use such an identifier
  1220. (aside from those in this manual) in an action or in additional C
  1221. code in the grammar file, you are likely to run into trouble.
  1222.  
  1223. * Menu:
  1224.  
  1225. * Parser Function:: How to call `yyparse' and what it returns.
  1226. * Lexical::         You must supply a function `yylex' which reads tokens.
  1227. * Error Reporting:: You must supply a function `yyerror'.
  1228. * Action Features:: Special features for use in actions.
  1229.  
  1230.  
  1231.  
  1232. File: bison.info,  Node: Parser Function,  Next: Lexical,  Prev: Interface,  Up: Interface
  1233.  
  1234. The Parser Function `yyparse'
  1235. =============================
  1236.  
  1237. You call the function `yyparse' to cause parsing to occur.  This
  1238. function reads tokens, executes actions, and ultimately returns when
  1239. it encounters end-of-input or an unrecoverable syntax error.  You can
  1240. also write an action which directs `yyparse' to return immediately
  1241. without reading further.
  1242.  
  1243. The value returned by `yyparse' is 0 if parsing was successful
  1244. (return is due to end-of-input).
  1245.  
  1246. The value is 1 if parsing failed (return is due to a syntax error).
  1247.  
  1248. In an action, you can cause immediate return from `yyparse' by using
  1249. these macros:
  1250.  
  1251. `YYACCEPT'
  1252.      Return immediately with value 0 (to report success).
  1253.  
  1254. `YYABORT'
  1255.      Return immediately with value 1 (to report failure).
  1256.  
  1257.  
  1258.  
  1259. File: bison.info,  Node: Lexical,  Next: Error Reporting,  Prev: Parser Function,  Up: Interface
  1260.  
  1261. The Lexical Analyzer Function `yylex'
  1262. =====================================
  1263.  
  1264. The "lexical analyzer" function, `yylex', recognizes tokens from the
  1265. input stream and returns them to the parser.  Bison does not create
  1266. this function automatically; you must write it so that `yyparse' can
  1267. call it.  The function is sometimes referred to as a lexical scanner.
  1268.  
  1269. The value that `yylex' returns must be the numeric code for the type
  1270. of token it has just found, or 0 for end-of-input.  *Note Symbols::.
  1271.  
  1272. When a token is referred to in the grammar rules by a name, that name
  1273. in the parser file becomes a C macro whose definition is the proper
  1274. numeric code for that token type.  So `yylex' can use the name to
  1275. indicate that type.
  1276.  
  1277. When a token is referred to in the grammar rules by a character
  1278. literal, the numeric code for that character is also the code for the
  1279. token type.  So `yylex' can simply return that character code.  The
  1280. null character must not be used this way, because its code is zero
  1281. and that is what signifies end-of-input.
  1282.  
  1283. Here is an example showing these things:
  1284.  
  1285.      yylex()
  1286.      {
  1287.        ...
  1288.        if (c == EOF)     /* Detect end of file.  */
  1289.          return 0;
  1290.        ...
  1291.        if (c == '+' || c == '-')
  1292.          return c;      /* Assume token type for `+' is '+'.  */
  1293.        ...
  1294.        return INT;      /* Return the type of the token.  */
  1295.        ...
  1296.      }
  1297.  
  1298. This interface has been designed so that the output from the `lex'
  1299. utility can be used without change as the definition of `yylex'.
  1300.  
  1301. In simple programs, `yylex' is often defined at the end of the Bison
  1302. grammar file.  If `yylex' is defined in a separate source file, you
  1303. need to arrange for the token-type macro definitions to be available
  1304. there.  To do this, use the `-d' option when you run Bison, so that
  1305. it will write these macro definitions into a separate header file
  1306. `NAME.tab.h' which you can include in the other source files that
  1307. need it.  *Note Invocation::.
  1308.  
  1309. In an ordinary (nonreentrant) parser, the semantic value of the token
  1310. must be stored into the global variable `yylval'.  When you are using
  1311. just one data type for semantic values, `yylval' has that type. 
  1312. Thus, if the type is `int' (the default), you might write this in
  1313. `yylex':
  1314.  
  1315.        ...
  1316.        yylval = value;  /* Put value onto Bison stack.  */
  1317.        return INT;      /* Return the type of the token.  */
  1318.        ...
  1319.  
  1320.  When you are using multiple data types, `yylval''s type is a union
  1321. made from the `%union' declaration (*note Union Decl::.).  So when
  1322. you store a token's value, you must use the proper member of the union.
  1323. If the `%union' declaration looks like this:
  1324.  
  1325.      %union {
  1326.        int intval;
  1327.        double val;
  1328.        symrec *tptr;
  1329.      }
  1330.  
  1331. then the code in `yylex' might look like this:
  1332.  
  1333.        ...
  1334.        yylval.intval = value;  /* Put value onto Bison stack.  */
  1335.        return INT;      /* Return the type of the token.  */
  1336.        ...
  1337.  
  1338.  If you are using the `@N'-feature (*note Action Features::.) in
  1339. actions to keep track of the textual locations of tokens and
  1340. groupings, then you must provide this information in `yylex'.  The
  1341. function `yyparse' expects to find the textual location of a token
  1342. just parsed in the global variable `yylloc'.  So `yylex' must store
  1343. the proper data in that variable.  The value of `yylloc' is a
  1344. structure, and you need only initialize the members that are going to
  1345. be used by the actions.  The four members are called `first_line',
  1346. `first_column', `last_line' and `last_column'.  Note that the use of
  1347. this feature makes the parser noticeably slower.
  1348.  
  1349. When you use the Bison declaration `%pure_parser' to request a pure,
  1350. reentrant parser, the global communication variables `yylval' and
  1351. `yylloc' cannot be used.  (*Note Pure Decl::.)  In such parsers the
  1352. two global variables are replaced by pointers passed as arguments to
  1353. `yylex'.  You must declare them as shown here, and pass the
  1354. information back by storing it through those pointers.
  1355.  
  1356.      yylex (lvalp, llocp)
  1357.           YYSTYPE *lvalp;
  1358.           YYLTYPE *llocp;
  1359.      {
  1360.        ...
  1361.        *lvalp = value;  /* Put value onto Bison stack.  */
  1362.        return INT;      /* Return the type of the token.  */
  1363.        ...
  1364.      }
  1365.  
  1366.  
  1367.  
  1368. File: bison.info,  Node: Error Reporting,  Next: Action Features,  Prev: Lexical,  Up: Interface
  1369.  
  1370. The Error Reporting Function `yyerror'
  1371. ======================================
  1372.  
  1373. The Bison parser expects to call an error reporting function named
  1374. `yyerror', which is supplied by you.  It is called by `yyparse'
  1375. whenever a syntax error is found, and it receives one argument, a
  1376. string which can be `"parse error"' or `"parser stack overflow"'. 
  1377. (The latter is unlikely, since you have to work really hard to
  1378. overflow the automatically-extended Bison parser stack.)
  1379.  
  1380. The following definition suffices in simple programs:
  1381.  
  1382.      yyerror (s)
  1383.           char *s;
  1384.      {
  1385.  
  1386.        fprintf (stderr, "%s\n", s);
  1387.      }
  1388.  
  1389. After `yyerror' returns to `yyparse', the latter will attempt error
  1390. recovery if you have written suitable error recovery grammar rules
  1391. (*note Error Recovery::.).  If recovery is impossible, `yyparse' will
  1392. immediately return 1.
  1393.  
  1394. The global variable `yynerr' contains the number of syntax errors
  1395. encountered so far.
  1396.  
  1397.  
  1398.