OSSP: CVS Repository: Difference in ossp-adm/autotools/bison.html versions 1.1 and 1.2

ossp-adm/autotools/bison.html 1.1 -> 1.2

--- bison.html 2002/07/10 08:46:24 1.1 +++ bison.html 2002/11/09 14:28:38 1.2 @@ -1,13 +1,13 @@ <HTML> <HEAD> - + -<TITLE>Bison 1.30</TITLE> +<TITLE>Bison 1.75</TITLE> </HEAD> <BODY> <H1>Bison</H1> <H2>The YACC-compatible Parser Generator</H2> -<H2>20 September 2001, Bison Version 1.30</H2> +<H2>14 October 2002, Bison Version 1.75</H2> <ADDRESS>by Charles Donnelly and Richard Stallman</ADDRESS> <P> <P><HR><P> @@ -47,7 +47,7 @@ <P> -This edition corresponds to version 1.30 of Bison. +This edition corresponds to version 1.75 of Bison. @@ -56,9 +56,9 @@ <P> As of Bison version 1.24, we have changed the distribution terms for -<CODE>yyparse</CODE> to permit using Bison's output in nonfree programs. -Formerly, Bison parsers could be used only in programs that were free -software. +<CODE>yyparse</CODE> to permit using Bison's output in nonfree programs when +Bison is generating C code for LALR(1) parsers. Formerly, these +parsers could be used only in programs that were free software. <P> @@ -87,6 +87,15 @@ using the other GNU tools. +<P> +This exception applies only when Bison is generating C code for a +LALR(1) parser; otherwise, the GPL terms operate as usual. You can +tell whether the exception applies to your <SAMP>`.c'</SAMP> output file by +inspecting it to see whether it says "As a special exception, when +this file is copied by Bison into a Bison output file, you may use +that output file without restriction." + + <H1><A NAME="SEC3" HREF="bison_toc.html#TOC3">GNU GENERAL PUBLIC LICENSE</A></H1> @@ -569,20 +578,44 @@ <P> -Not all context-free languages can be handled by Bison, only those -that are LALR(1). In brief, this means that it must be possible to +<A NAME="IDX6"></A> +<A NAME="IDX7"></A> +There are various important subclasses of context-free grammar. Although it +can handle almost all context-free grammars, Bison is optimized for what +are called LALR(1) grammars. +In brief, in these grammars, it must be possible to tell how to parse any portion of an input string with just a single token of look-ahead. Strictly speaking, that is a description of an LR(1) grammar, and LALR(1) involves additional restrictions that are hard to explain simply; but it is rare in actual practice to find an -LR(1) grammar that fails to be LALR(1). See section <A HREF="bison.html#SEC88">Mysterious Reduce/Reduce Conflicts</A>, for more information on this. +LR(1) grammar that fails to be LALR(1). See section <A HREF="bison.html#SEC89">Mysterious Reduce/Reduce Conflicts</A>, for more information on this. <P> -<A NAME="IDX6"></A> -<A NAME="IDX7"></A> <A NAME="IDX8"></A> <A NAME="IDX9"></A> +<A NAME="IDX10"></A> +<A NAME="IDX11"></A> +Parsers for LALR(1) grammars are <EM>deterministic</EM>, meaning roughly that +the next grammar rule to apply at any point in the input is uniquely +determined by the preceding input and a fixed, finite portion (called +a <EM>look-ahead</EM>) of the remaining input. +A context-free grammar can be <EM>ambiguous</EM>, meaning that +there are multiple ways to apply the grammar rules to get the some inputs. +Even unambiguous grammars can be <EM>non-deterministic</EM>, meaning that no +fixed look-ahead always suffices to determine the next grammar rule to apply. +With the proper declarations, Bison is also able to parse these more general +context-free grammars, using a technique known as GLR parsing (for +Generalized LR). Bison's GLR parsers are able to handle any context-free +grammar for which the number of possible parses of any given string +is finite. + + +<P> +<A NAME="IDX12"></A> +<A NAME="IDX13"></A> +<A NAME="IDX14"></A> +<A NAME="IDX15"></A> In the formal grammatical rules for a language, each kind of syntactic unit or grouping is named by a <EM>symbol</EM>. Those which are built by grouping smaller constructs according to grammatical rules are called @@ -591,6 +624,7 @@ corresponding to a single terminal symbol a <EM>token</EM>, and a piece corresponding to a single nonterminal symbol a <EM>grouping</EM>. + <P> We can use the C language as an example of what symbols, terminal and nonterminal, mean. The tokens of C are identifiers, constants (numeric and @@ -607,15 +641,14 @@ Here is a simple C function subdivided into tokens: +<P> +@ifnotinfo <PRE> int /* keyword `int' */ -square (x) /* identifier, open-paren, */ - /* identifier, close-paren */ - int x; /* keyword `int', identifier, semicolon */ +square (int x) /* identifier, open-paren, identifier, identifier, close-paren */ { /* open-brace */ - return x * x; /* keyword `return', identifier, */ - /* asterisk, identifier, semicolon */ + return x * x; /* keyword `return', identifier, asterisk, identifier, semicolon */ } /* close-brace */ </PRE> @@ -650,7 +683,7 @@ <P> -<A NAME="IDX10"></A> +<A NAME="IDX16"></A> One nonterminal symbol must be distinguished as the special one which defines a complete utterance in the language. It is called the <EM>start symbol</EM>. In a compiler, this means a complete input program. In the C @@ -678,15 +711,15 @@ <H2><A NAME="SEC9" HREF="bison_toc.html#TOC9">From Formal Rules to Bison Input</A></H2> <P> -<A NAME="IDX11"></A> -<A NAME="IDX12"></A> -<A NAME="IDX13"></A> +<A NAME="IDX17"></A> +<A NAME="IDX18"></A> +<A NAME="IDX19"></A> <P> A formal grammar is a mathematical construct. To define the language for Bison, you must write a file expressing the grammar in Bison syntax: -a <EM>Bison grammar</EM> file. See section <A HREF="bison.html#SEC39">Bison Grammar Files</A>. +a <EM>Bison grammar</EM> file. See section <A HREF="bison.html#SEC40">Bison Grammar Files</A>. <P> @@ -703,7 +736,7 @@ <CODE>RETURN</CODE>. A terminal symbol that stands for a particular keyword in the language should be named after that keyword converted to upper case. The terminal symbol <CODE>error</CODE> is reserved for error recovery. -See section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>. +See section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>. <P> @@ -715,7 +748,7 @@ <P> A third way to represent a terminal symbol is with a C string constant -containing several characters. See section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>, for more information. +containing several characters. See section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>, for more information. <P> @@ -733,15 +766,15 @@ </PRE> <P> -See section <A HREF="bison.html#SEC46">Syntax of Grammar Rules</A>. +See section <A HREF="bison.html#SEC47">Syntax of Grammar Rules</A>. <H2><A NAME="SEC10" HREF="bison_toc.html#TOC10">Semantic Values</A></H2> <P> -<A NAME="IDX14"></A> -<A NAME="IDX15"></A> +<A NAME="IDX20"></A> +<A NAME="IDX21"></A> <P> @@ -752,11 +785,12 @@ <SAMP>`x+4'</SAMP> is grammatical then <SAMP>`x+1'</SAMP> or <SAMP>`x+3989'</SAMP> is equally grammatical. + <P> But the precise value is very important for what the input means once it is parsed. A compiler is useless if it fails to distinguish between 4, 1 and 3989 as constants in the program! Therefore, each token in a Bison grammar -has both a token type and a <EM>semantic value</EM>. See section <A HREF="bison.html#SEC48">Defining Language Semantics</A>, +has both a token type and a <EM>semantic value</EM>. See section <A HREF="bison.html#SEC49">Defining Language Semantics</A>, for details. @@ -767,6 +801,7 @@ group it with other tokens. The grammar rules know nothing about tokens except their types. + <P> The semantic value has all the rest of the information about the meaning of the token, such as the value of an integer, or the name of an @@ -795,8 +830,8 @@ <H2><A NAME="SEC11" HREF="bison_toc.html#TOC11">Semantic Actions</A></H2> <P> -<A NAME="IDX16"></A> -<A NAME="IDX17"></A> +<A NAME="IDX22"></A> +<A NAME="IDX23"></A> <P> @@ -804,7 +839,7 @@ also produce some output based on the input. In a Bison grammar, a grammar rule can have an <EM>action</EM> made up of C statements. Each time the parser recognizes a match for that rule, the action is executed. -See section <A HREF="bison.html#SEC51">Actions</A>. +See section <A HREF="bison.html#SEC52">Actions</A>. <P> @@ -835,52 +870,257 @@ -<H2><A NAME="SEC12" HREF="bison_toc.html#TOC12">Locations</A></H2> +<H2><A NAME="SEC12" HREF="bison_toc.html#TOC12">Writing GLR Parsers</A></H2> <P> -<A NAME="IDX18"></A> -<A NAME="IDX19"></A> -<A NAME="IDX20"></A> +<A NAME="IDX24"></A> +<A NAME="IDX25"></A> +<A NAME="IDX26"></A> +<A NAME="IDX27"></A> +<A NAME="IDX28"></A> + + +<P> +In some grammars, there will be cases where Bison's standard LALR(1) +parsing algorithm cannot decide whether to apply a certain grammar rule +at a given point. That is, it may not be able to decide (on the basis +of the input read so far) which of two possible reductions (applications +of a grammar rule) applies, or whether to apply a reduction or read more +of the input and apply a reduction later in the input. These are known +respectively as <EM>reduce/reduce</EM> conflicts (see section <A HREF="bison.html#SEC88">Reduce/Reduce Conflicts</A>), +and <EM>shift/reduce</EM> conflicts (see section <A HREF="bison.html#SEC80">Shift/Reduce Conflicts</A>). + + +<P> +To use a grammar that is not easily modified to be LALR(1), a more +general parsing algorithm is sometimes necessary. If you include +<CODE>%glr-parser</CODE> among the Bison declarations in your file +(see section <A HREF="bison.html#SEC41">Outline of a Bison Grammar</A>), the result will be a Generalized LR (GLR) +parser. These parsers handle Bison grammars that contain no unresolved +conflicts (i.e., after applying precedence declarations) identically to +LALR(1) parsers. However, when faced with unresolved shift/reduce and +reduce/reduce conflicts, GLR parsers use the simple expedient of doing +both, effectively cloning the parser to follow both possibilities. Each +of the resulting parsers can again split, so that at any given time, +there can be any number of possible parses being explored. The parsers +proceed in lockstep; that is, all of them consume (shift) a given input +symbol before any of them proceed to the next. Each of the cloned +parsers eventually meets one of two possible fates: either it runs into +a parsing error, in which case it simply vanishes, or it merges with +another parser, because the two of them have reduced the input to an +identical set of symbols. + + +<P> +During the time that there are multiple parsers, semantic actions are +recorded, but not performed. When a parser disappears, its recorded +semantic actions disappear as well, and are never performed. When a +reduction makes two parsers identical, causing them to merge, Bison +records both sets of semantic actions. Whenever the last two parsers +merge, reverting to the single-parser case, Bison resolves all the +outstanding actions either by precedences given to the grammar rules +involved, or by performing both actions, and then calling a designated +user-defined function on the resulting values to produce an arbitrary +merged result. + + +<P> +Let's consider an example, vastly simplified from C++. + + + +<PRE> +%{ + #define YYSTYPE const char* +%} + +%token TYPENAME ID + +%right '=' +%left '+' + +%glr-parser + +%% + +prog : + | prog stmt { printf ("\n"); } + ; + +stmt : expr ';' %dprec 1 + | decl %dprec 2 + ; + +expr : ID { printf ("%s ", $$); } + | TYPENAME '(' expr ')' + { printf ("%s <cast> ", $1); } + | expr '+' expr { printf ("+ "); } + | expr '=' expr { printf ("= "); } + ; + +decl : TYPENAME declarator ';' + { printf ("%s <declare> ", $1); } + | TYPENAME declarator '=' expr ';' + { printf ("%s <init-declare> ", $1); } + ; + +declarator : ID { printf ("\"%s\" ", $1); } + | '(' declarator ')' + ; +</PRE> + +<P> +This models a problematic part of the C++ grammar--the ambiguity between +certain declarations and statements. For example, + + + +<PRE> +T (x) = y+z; +</PRE> + +<P> +parses as either an <CODE>expr</CODE> or a <CODE>stmt</CODE> +(assuming that <SAMP>`T'</SAMP> is recognized as a TYPENAME and <SAMP>`x'</SAMP> as an ID). +Bison detects this as a reduce/reduce conflict between the rules +<CODE>expr : ID</CODE> and <CODE>declarator : ID</CODE>, which it cannot resolve at the +time it encounters <CODE>x</CODE> in the example above. The two <CODE>%dprec</CODE> +declarations, however, give precedence to interpreting the example as a +<CODE>decl</CODE>, which implies that <CODE>x</CODE> is a declarator. +The parser therefore prints + + + +<PRE> +"x" y z + T <init-declare> +</PRE> + +<P> +Consider a different input string for this parser: + + + +<PRE> +T (x) + y; +</PRE> + +<P> +Here, there is no ambiguity (this cannot be parsed as a declaration). +However, at the time the Bison parser encounters <CODE>x</CODE>, it does not +have enough information to resolve the reduce/reduce conflict (again, +between <CODE>x</CODE> as an <CODE>expr</CODE> or a <CODE>declarator</CODE>). In this +case, no precedence declaration is used. Instead, the parser splits +into two, one assuming that <CODE>x</CODE> is an <CODE>expr</CODE>, and the other +assuming <CODE>x</CODE> is a <CODE>declarator</CODE>. The second of these parsers +then vanishes when it sees <CODE>+</CODE>, and the parser prints + + + +<PRE> +x T <cast> y + +</PRE> + +<P> +Suppose that instead of resolving the ambiguity, you wanted to see all +the possibilities. For this purpose, we must <EM>merge</EM> the semantic +actions of the two possible parsers, rather than choosing one over the +other. To do so, you could change the declaration of <CODE>stmt</CODE> as +follows: + + + +<PRE> +stmt : expr ';' %merge <stmtMerge> + | decl %merge <stmtMerge> + ; +</PRE> + +<P> + + +<P> +and define the <CODE>stmtMerge</CODE> function as: + + + +<PRE> +static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1) +{ + printf ("<OR> "); + return ""; +} +</PRE> + +<P> +with an accompanying forward declaration +in the C declarations at the beginning of the file: + + + +<PRE> +%{ + #define YYSTYPE const char* + static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1); +%} +</PRE> + +<P> +With these declarations, the resulting parser will parse the first example +as both an <CODE>expr</CODE> and a <CODE>decl</CODE>, and print + + + +<PRE> +"x" y z + T <init-declare> x T <cast> y z + = <OR> +</PRE> + + + +<H2><A NAME="SEC13" HREF="bison_toc.html#TOC13">Locations</A></H2> +<P> +<A NAME="IDX29"></A> +<A NAME="IDX30"></A> +<A NAME="IDX31"></A> <P> Many applications, like interpreters or compilers, have to produce verbose -and useful error messages. To achieve this, one must be able to keep track of +and useful error messages. To achieve this, one must be able to keep track of the <EM>textual position</EM>, or <EM>location</EM>, of each syntactic construct. Bison provides a mechanism for handling these locations. <P> -Each token has a semantic value. In a similar fashion, each token has an +Each token has a semantic value. In a similar fashion, each token has an associated location, but the type of locations is the same for all tokens and -groupings. Moreover, the output parser is equipped with a default data -structure for storing locations (see section <A HREF="bison.html#SEC54">Tracking Locations</A>, for more details). +groupings. Moreover, the output parser is equipped with a default data +structure for storing locations (see section <A HREF="bison.html#SEC55">Tracking Locations</A>, for more details). <P> Like semantic values, locations can be reached in actions using a dedicated -set of constructs. In the example above, the location of the whole grouping +set of constructs. In the example above, the location of the whole grouping is <CODE>@$</CODE>, while the locations of the subexpressions are <CODE>@1</CODE> and <CODE>@3</CODE>. <P> When a rule is matched, a default action is used to compute the semantic value -of its left hand side (see section <A HREF="bison.html#SEC51">Actions</A>). In the same way, another default -action is used for locations. However, the action for locations is general +of its left hand side (see section <A HREF="bison.html#SEC52">Actions</A>). In the same way, another default +action is used for locations. However, the action for locations is general enough for most cases, meaning there is usually no need to describe for each -rule how <CODE>@$</CODE> should be formed. When building a new location for a given +rule how <CODE>@$</CODE> should be formed. When building a new location for a given grouping, the default behavior of the output parser is to take the beginning of the first symbol, and the end of the last symbol. -<H2><A NAME="SEC13" HREF="bison_toc.html#TOC13">Bison Output: the Parser File</A></H2> +<H2><A NAME="SEC14" HREF="bison_toc.html#TOC14">Bison Output: the Parser File</A></H2> <P> -<A NAME="IDX21"></A> -<A NAME="IDX22"></A> -<A NAME="IDX23"></A> -<A NAME="IDX24"></A> +<A NAME="IDX32"></A> +<A NAME="IDX33"></A> +<A NAME="IDX34"></A> +<A NAME="IDX35"></A> <P> @@ -900,12 +1140,13 @@ <P> -The tokens come from a function called the <EM>lexical analyzer</EM> that you -must supply in some fashion (such as by writing it in C). The Bison parser -calls the lexical analyzer each time it wants a new token. It doesn't know -what is "inside" the tokens (though their semantic values may reflect -this). Typically the lexical analyzer makes the tokens by parsing -characters of text, but Bison does not depend on this. See section <A HREF="bison.html#SEC70">The Lexical Analyzer Function <CODE>yylex</CODE></A>. +The tokens come from a function called the <EM>lexical analyzer</EM> that +you must supply in some fashion (such as by writing it in C). The Bison +parser calls the lexical analyzer each time it wants a new token. It +doesn't know what is "inside" the tokens (though their semantic values +may reflect this). Typically the lexical analyzer makes the tokens by +parsing characters of text, but Bison does not depend on this. +See section <A HREF="bison.html#SEC71">The Lexical Analyzer Function <CODE>yylex</CODE></A>. <P> @@ -916,12 +1157,12 @@ parser calls to report an error. In addition, a complete C program must start with a function called <CODE>main</CODE>; you have to provide this, and arrange for it to call <CODE>yyparse</CODE> or the parser will never run. -See section <A HREF="bison.html#SEC68">Parser C-Language Interface</A>. +See section <A HREF="bison.html#SEC69">Parser C-Language Interface</A>. <P> Aside from the token type names and the symbols in the actions you -write, all variable and function names used in the Bison parser file +write, all symbols defined in the Bison parser file itself begin with <SAMP>`yy'</SAMP> or <SAMP>`YY'</SAMP>. This includes interface functions such as the lexical analyzer function <CODE>yylex</CODE>, the error reporting function <CODE>yyerror</CODE> and the parser function <CODE>yyparse</CODE> itself. @@ -931,12 +1172,22 @@ this manual. +<P> +In some cases the Bison parser file includes system headers, and in +those cases your code should respect the identifiers reserved by those +headers. On some non-GNU hosts, <CODE><alloca.h></CODE>, +<CODE><stddef.h></CODE>, and <CODE><stdlib.h></CODE> are included as needed to +declare memory allocators and related types. Other system headers may +be included if you define <CODE>YYDEBUG</CODE> to a nonzero value +(see section <A HREF="bison.html#SEC99">Tracing Your Parser</A>). + + -<H2><A NAME="SEC14" HREF="bison_toc.html#TOC14">Stages in Using Bison</A></H2> +<H2><A NAME="SEC15" HREF="bison_toc.html#TOC15">Stages in Using Bison</A></H2> <P> -<A NAME="IDX25"></A> -<A NAME="IDX26"></A> +<A NAME="IDX36"></A> +<A NAME="IDX37"></A> <P> @@ -949,16 +1200,16 @@ <LI> Formally specify the grammar in a form recognized by Bison -(see section <A HREF="bison.html#SEC39">Bison Grammar Files</A>). For each grammatical rule in the language, -describe the action that is to be taken when an instance of that rule -is recognized. The action is described by a sequence of C statements. +(see section <A HREF="bison.html#SEC40">Bison Grammar Files</A>). For each grammatical rule +in the language, describe the action that is to be taken when an +instance of that rule is recognized. The action is described by a +sequence of C statements. <LI> -Write a lexical analyzer to process input and pass tokens to the -parser. The lexical analyzer may be written by hand in C -(see section <A HREF="bison.html#SEC70">The Lexical Analyzer Function <CODE>yylex</CODE></A>). It could also be produced using Lex, but the use -of Lex is not discussed in this manual. +Write a lexical analyzer to process input and pass tokens to the parser. +The lexical analyzer may be written by hand in C (see section <A HREF="bison.html#SEC71">The Lexical Analyzer Function <CODE>yylex</CODE></A>). It could also be produced +using Lex, but the use of Lex is not discussed in this manual. <LI> @@ -991,12 +1242,12 @@ -<H2><A NAME="SEC15" HREF="bison_toc.html#TOC15">The Overall Layout of a Bison Grammar</A></H2> +<H2><A NAME="SEC16" HREF="bison_toc.html#TOC16">The Overall Layout of a Bison Grammar</A></H2> <P> -<A NAME="IDX27"></A> -<A NAME="IDX28"></A> -<A NAME="IDX29"></A> -<A NAME="IDX30"></A> +<A NAME="IDX38"></A> +<A NAME="IDX39"></A> +<A NAME="IDX40"></A> +<A NAME="IDX41"></A> <P> @@ -1007,7 +1258,7 @@ <PRE> %{ -<VAR>C declarations</VAR> +<VAR>Prologue</VAR> %} <VAR>Bison declarations</VAR> @@ -1015,7 +1266,7 @@ %% <VAR>Grammar rules</VAR> %% -<VAR>Additional C code</VAR> +<VAR>Epilogue</VAR> </PRE> <P> @@ -1024,8 +1275,8 @@ <P> -The C declarations may define types and variables used in the actions. -You can also use preprocessor commands to define macros used there, and use +The prologue may define types and variables used in the actions. You can +also use preprocessor commands to define macros used there, and use <CODE>#include</CODE> to include header files that do any of these things. @@ -1041,18 +1292,18 @@ <P> -The additional C code can contain any C code you want to use. Often the -definition of the lexical analyzer <CODE>yylex</CODE> goes here, plus subroutines -called by the actions in the grammar rules. In a simple program, all the -rest of the program can go here. +The epilogue can contain any code you want to use. Often the definition of +the lexical analyzer <CODE>yylex</CODE> goes here, plus subroutines called by the +actions in the grammar rules. In a simple program, all the rest of the +program can go here. -<H1><A NAME="SEC16" HREF="bison_toc.html#TOC16">Examples</A></H1> +<H1><A NAME="SEC17" HREF="bison_toc.html#TOC17">Examples</A></H1> <P> -<A NAME="IDX31"></A> -<A NAME="IDX32"></A> +<A NAME="IDX42"></A> +<A NAME="IDX43"></A> <P> @@ -1070,12 +1321,12 @@ -<H2><A NAME="SEC17" HREF="bison_toc.html#TOC17">Reverse Polish Notation Calculator</A></H2> +<H2><A NAME="SEC18" HREF="bison_toc.html#TOC18">Reverse Polish Notation Calculator</A></H2> <P> -<A NAME="IDX33"></A> -<A NAME="IDX34"></A> -<A NAME="IDX35"></A> -<A NAME="IDX36"></A> +<A NAME="IDX44"></A> +<A NAME="IDX45"></A> +<A NAME="IDX46"></A> +<A NAME="IDX47"></A> <P> @@ -1092,7 +1343,7 @@ -<H3><A NAME="SEC18" HREF="bison_toc.html#TOC18">Declarations for <CODE>rpcalc</CODE></A></H3> +<H3><A NAME="SEC19" HREF="bison_toc.html#TOC19">Declarations for <CODE>rpcalc</CODE></A></H3> <P> Here are the C and Bison declarations for the reverse polish notation @@ -1101,7 +1352,7 @@ <PRE> -/* Reverse polish notation calculator. */ +/* Reverse polish notation calculator. */ %{ #define YYSTYPE double @@ -1110,21 +1361,22 @@ %token NUM -%% /* Grammar rules and actions follow */ +%% /* Grammar rules and actions follow. */ </PRE> <P> -The C declarations section (see section <A HREF="bison.html#SEC41">The C Declarations Section</A>) contains two +The declarations section (see section <A HREF="bison.html#SEC42">The prologue</A>) contains two preprocessor directives. <P> The <CODE>#define</CODE> directive defines the macro <CODE>YYSTYPE</CODE>, thus -specifying the C data type for semantic values of both tokens and groupings -(see section <A HREF="bison.html#SEC49">Data Types of Semantic Values</A>). The Bison parser will use whatever type -<CODE>YYSTYPE</CODE> is defined as; if you don't define it, <CODE>int</CODE> is the -default. Because we specify <CODE>double</CODE>, each token and each expression -has an associated value, which is a floating point number. +specifying the C data type for semantic values of both tokens and +groupings (see section <A HREF="bison.html#SEC50">Data Types of Semantic Values</A>). The +Bison parser will use whatever type <CODE>YYSTYPE</CODE> is defined as; if you +don't define it, <CODE>int</CODE> is the default. Because we specify +<CODE>double</CODE>, each token and each expression has an associated value, +which is a floating point number. <P> @@ -1133,9 +1385,9 @@ <P> -The second section, Bison declarations, provides information to Bison about -the token types (see section <A HREF="bison.html#SEC42">The Bison Declarations Section</A>). Each terminal symbol that is -not a single-character literal must be declared here. (Single-character +The second section, Bison declarations, provides information to Bison +about the token types (see section <A HREF="bison.html#SEC43">The Bison Declarations Section</A>). Each terminal symbol that is not a +single-character literal must be declared here. (Single-character literals normally don't need to be declared.) In this example, all the arithmetic operators are designated by single-character literals, so the only terminal symbol that needs to be declared is <CODE>NUM</CODE>, the token @@ -1144,7 +1396,7 @@ -<H3><A NAME="SEC19" HREF="bison_toc.html#TOC19">Grammar Rules for <CODE>rpcalc</CODE></A></H3> +<H3><A NAME="SEC20" HREF="bison_toc.html#TOC20">Grammar Rules for <CODE>rpcalc</CODE></A></H3> <P> Here are the grammar rules for the reverse polish notation calculator. @@ -1185,7 +1437,7 @@ <P> The semantics of the language is determined by the actions taken when a grouping is recognized. The actions are the C code that appears inside -braces. See section <A HREF="bison.html#SEC51">Actions</A>. +braces. See section <A HREF="bison.html#SEC52">Actions</A>. <P> @@ -1199,7 +1451,7 @@ -<H4><A NAME="SEC20" HREF="bison_toc.html#TOC20">Explanation of <CODE>input</CODE></A></H4> +<H4><A NAME="SEC21" HREF="bison_toc.html#TOC21">Explanation of <CODE>input</CODE></A></H4> <P> Consider the definition of <CODE>input</CODE>: @@ -1217,7 +1469,7 @@ string, or a complete input followed by an input line". Notice that "complete input" is defined in terms of itself. This definition is said to be <EM>left recursive</EM> since <CODE>input</CODE> appears always as the -leftmost symbol in the sequence. See section <A HREF="bison.html#SEC47">Recursive Rules</A>. +leftmost symbol in the sequence. See section <A HREF="bison.html#SEC48">Recursive Rules</A>. <P> @@ -1240,12 +1492,12 @@ <P> The parser function <CODE>yyparse</CODE> continues to process input until a grammatical error is seen or the lexical analyzer says there are no more -input tokens; we will arrange for the latter to happen at end of file. +input tokens; we will arrange for the latter to happen at end-of-input. -<H4><A NAME="SEC21" HREF="bison_toc.html#TOC21">Explanation of <CODE>line</CODE></A></H4> +<H4><A NAME="SEC22" HREF="bison_toc.html#TOC22">Explanation of <CODE>line</CODE></A></H4> <P> Now consider the definition of <CODE>line</CODE>: @@ -1278,7 +1530,7 @@ -<H4><A NAME="SEC22" HREF="bison_toc.html#TOC22">Explanation of <CODE>expr</CODE></A></H4> +<H4><A NAME="SEC23" HREF="bison_toc.html#TOC23">Explanation of <CODE>expr</CODE></A></H4> <P> The <CODE>exp</CODE> grouping has several rules, one for each kind of expression. @@ -1317,7 +1569,7 @@ associated semantic value, but if it had one you could refer to it as <CODE>$3</CODE>. When <CODE>yyparse</CODE> recognizes a sum expression using this rule, the sum of the two subexpressions' values is produced as the value of -the entire expression. See section <A HREF="bison.html#SEC51">Actions</A>. +the entire expression. See section <A HREF="bison.html#SEC52">Actions</A>. <P> @@ -1328,7 +1580,7 @@ <P> The formatting shown here is the recommended convention, but Bison does -not require it. You can add or change whitespace as much as you wish. +not require it. You can add or change white space as much as you wish. For example, this: @@ -1354,16 +1606,16 @@ -<H3><A NAME="SEC23" HREF="bison_toc.html#TOC23">The <CODE>rpcalc</CODE> Lexical Analyzer</A></H3> +<H3><A NAME="SEC24" HREF="bison_toc.html#TOC24">The <CODE>rpcalc</CODE> Lexical Analyzer</A></H3> <P> -<A NAME="IDX37"></A> -<A NAME="IDX38"></A> +<A NAME="IDX48"></A> +<A NAME="IDX49"></A> <P> -The lexical analyzer's job is low-level parsing: converting characters or -sequences of characters into tokens. The Bison parser gets its tokens by -calling the lexical analyzer. See section <A HREF="bison.html#SEC70">The Lexical Analyzer Function <CODE>yylex</CODE></A>. +The lexical analyzer's job is low-level parsing: converting characters +or sequences of characters into tokens. The Bison parser gets its +tokens by calling the lexical analyzer. See section <A HREF="bison.html#SEC71">The Lexical Analyzer Function <CODE>yylex</CODE></A>. <P> @@ -1379,7 +1631,7 @@ represents a token type. The same text used in Bison rules to stand for this token type is also a C expression for the numeric code for the type. This works in two ways. If the token type is a character literal, then its -numeric code is the ASCII code for that character; you can use the same +numeric code is that of the character; you can use the same character literal in the lexical analyzer to express the number. If the token type is an identifier, that identifier is defined by Bison as a C macro whose definition is the appropriate number. In this example, @@ -1387,16 +1639,15 @@ <P> -The semantic value of the token (if it has one) is stored into the global -variable <CODE>yylval</CODE>, which is where the Bison parser will look for it. -(The C data type of <CODE>yylval</CODE> is <CODE>YYSTYPE</CODE>, which was defined -at the beginning of the grammar; see section <A HREF="bison.html#SEC18">Declarations for <CODE>rpcalc</CODE></A>.) +The semantic value of the token (if it has one) is stored into the +global variable <CODE>yylval</CODE>, which is where the Bison parser will look +for it. (The C data type of <CODE>yylval</CODE> is <CODE>YYSTYPE</CODE>, which was +defined at the beginning of the grammar; see section <A HREF="bison.html#SEC19">Declarations for <CODE>rpcalc</CODE></A>.) <P> -A token type code of zero is returned if the end-of-file is encountered. -(Bison recognizes any nonpositive value as indicating the end of the -input.) +A token type code of zero is returned if the end-of-input is encountered. +(Bison recognizes any nonpositive value as indicating end-of-input.) <P> @@ -1405,10 +1656,10 @@ <PRE> -/* Lexical analyzer returns a double floating point - number on the stack and the token NUM, or the ASCII - character read if not a number. Skips all blanks - and tabs, returns 0 for EOF. */ +/* The lexical analyzer returns a double floating point + number on the stack and the token NUM, or the numeric code + of the character read if not a number. It skips all blanks + and tabs, and returns 0 for end-of-input. */ #include <ctype.h> @@ -1417,30 +1668,30 @@ { int c; - /* skip white space */ + /* Skip white space. */ while ((c = getchar ()) == ' ' || c == '\t') ; - /* process numbers */ + /* Process numbers. */ if (c == '.' || isdigit (c)) { ungetc (c, stdin); scanf ("%lf", &yylval); return NUM; } - /* return end-of-file */ + /* Return end-of-input. */ if (c == EOF) return 0; - /* return single chars */ + /* Return a single char. */ return c; } </PRE> -<H3><A NAME="SEC24" HREF="bison_toc.html#TOC24">The Controlling Function</A></H3> +<H3><A NAME="SEC25" HREF="bison_toc.html#TOC25">The Controlling Function</A></H3> <P> -<A NAME="IDX39"></A> -<A NAME="IDX40"></A> +<A NAME="IDX50"></A> +<A NAME="IDX51"></A> <P> @@ -1460,16 +1711,16 @@ -<H3><A NAME="SEC25" HREF="bison_toc.html#TOC25">The Error Reporting Routine</A></H3> +<H3><A NAME="SEC26" HREF="bison_toc.html#TOC26">The Error Reporting Routine</A></H3> <P> -<A NAME="IDX41"></A> +<A NAME="IDX52"></A> <P> When <CODE>yyparse</CODE> detects a syntax error, it calls the error reporting function <CODE>yyerror</CODE> to print an error message (usually but not always <CODE>"parse error"</CODE>). It is up to the programmer to supply -<CODE>yyerror</CODE> (see section <A HREF="bison.html#SEC68">Parser C-Language Interface</A>), so +<CODE>yyerror</CODE> (see section <A HREF="bison.html#SEC69">Parser C-Language Interface</A>), so here is the definition we will use: @@ -1478,7 +1729,7 @@ #include <stdio.h> void -yyerror (const char *s) /* Called by yyparse on error */ +yyerror (const char *s) /* called by yyparse on error */ { printf ("%s\n", s); } @@ -1487,7 +1738,7 @@ <P> After <CODE>yyerror</CODE> returns, the Bison parser may recover from the error and continue parsing if the grammar contains a suitable error rule -(see section <A HREF="bison.html#SEC90">Error Recovery</A>). Otherwise, <CODE>yyparse</CODE> returns nonzero. We +(see section <A HREF="bison.html#SEC92">Error Recovery</A>). Otherwise, <CODE>yyparse</CODE> returns nonzero. We have not written any error rules in this example, so any invalid input will cause the calculator program to exit. This is not clean behavior for a real calculator, but it is adequate for the first example. @@ -1495,9 +1746,9 @@ -<H3><A NAME="SEC26" HREF="bison_toc.html#TOC26">Running Bison to Make the Parser</A></H3> +<H3><A NAME="SEC27" HREF="bison_toc.html#TOC27">Running Bison to Make the Parser</A></H3> <P> -<A NAME="IDX42"></A> +<A NAME="IDX53"></A> <P> @@ -1505,7 +1756,8 @@ arrange all the source code in one or more source files. For such a simple example, the easiest thing is to put everything in one file. The definitions of <CODE>yylex</CODE>, <CODE>yyerror</CODE> and <CODE>main</CODE> go at the -end, in the "additional C code" section of the file (see section <A HREF="bison.html#SEC15">The Overall Layout of a Bison Grammar</A>). +end, in the epilogue of the file +(see section <A HREF="bison.html#SEC16">The Overall Layout of a Bison Grammar</A>). <P> @@ -1526,7 +1778,7 @@ <P> In this example the file was called <TT>`rpcalc.y'</TT> (for "Reverse Polish CALCulator"). Bison produces a file named <TT>`<VAR>file_name</VAR>.tab.c'</TT>, -removing the <SAMP>`.y'</SAMP> from the original file name. The file output by +removing the <SAMP>`.y'</SAMP> from the original file name. The file output by Bison contains the source code for <CODE>yyparse</CODE>. The additional functions in the input file (<CODE>yylex</CODE>, <CODE>yyerror</CODE> and <CODE>main</CODE>) are copied verbatim to the output. @@ -1534,9 +1786,9 @@ -<H3><A NAME="SEC27" HREF="bison_toc.html#TOC27">Compiling the Parser File</A></H3> +<H3><A NAME="SEC28" HREF="bison_toc.html#TOC28">Compiling the Parser File</A></H3> <P> -<A NAME="IDX43"></A> +<A NAME="IDX54"></A> <P> @@ -1546,15 +1798,15 @@ <PRE> # List files in current directory. -% ls +$ <KBD>ls</KBD> rpcalc.tab.c rpcalc.y # Compile the Bison parser. # <SAMP>`-lm'</SAMP> tells compiler to search math library for <CODE>pow</CODE>. -% cc rpcalc.tab.c -lm -o rpcalc +$ <KBD>cc -lm -o rpcalc rpcalc.tab.c</KBD> # List files again. -% ls +$ <KBD>ls</KBD> rpcalc rpcalc.tab.c rpcalc.y </PRE> @@ -1565,28 +1817,28 @@ <PRE> -% rpcalc -4 9 + +$ <KBD>rpcalc</KBD> +<KBD>4 9 +</KBD> 13 -3 7 + 3 4 5 *+- +<KBD>3 7 + 3 4 5 *+-</KBD> -13 -3 7 + 3 4 5 * + - n Note the unary minus, <SAMP>`n'</SAMP> +<KBD>3 7 + 3 4 5 * + - n</KBD> Note the unary minus, <SAMP>`n'</SAMP> 13 -5 6 / 4 n + +<KBD>5 6 / 4 n +</KBD> -3.166666667 -3 4 ^ Exponentiation +<KBD>3 4 ^</KBD> Exponentiation 81 -^D End-of-file indicator -% +<KBD>^D</KBD> End-of-file indicator +$ </PRE> -<H2><A NAME="SEC28" HREF="bison_toc.html#TOC28">Infix Notation Calculator: <CODE>calc</CODE></A></H2> +<H2><A NAME="SEC29" HREF="bison_toc.html#TOC29">Infix Notation Calculator: <CODE>calc</CODE></A></H2> <P> -<A NAME="IDX44"></A> -<A NAME="IDX45"></A> -<A NAME="IDX46"></A> +<A NAME="IDX55"></A> +<A NAME="IDX56"></A> +<A NAME="IDX57"></A> <P> @@ -1658,14 +1910,14 @@ declarations; the higher the line number of the declaration (lower on the page or screen), the higher the precedence. Hence, exponentiation has the highest precedence, unary minus (<CODE>NEG</CODE>) is next, followed -by <SAMP>`*'</SAMP> and <SAMP>`/'</SAMP>, and so on. See section <A HREF="bison.html#SEC80">Operator Precedence</A>. +by <SAMP>`*'</SAMP> and <SAMP>`/'</SAMP>, and so on. See section <A HREF="bison.html#SEC81">Operator Precedence</A>. <P> -The other important new feature is the <CODE>%prec</CODE> in the grammar section -for the unary minus operator. The <CODE>%prec</CODE> simply instructs Bison that -the rule <SAMP>`| '-' exp'</SAMP> has the same precedence as <CODE>NEG</CODE>---in this -case the next-to-highest. See section <A HREF="bison.html#SEC85">Context-Dependent Precedence</A>. +The other important new feature is the <CODE>%prec</CODE> in the grammar +section for the unary minus operator. The <CODE>%prec</CODE> simply instructs +Bison that the rule <SAMP>`| '-' exp'</SAMP> has the same precedence as +<CODE>NEG</CODE>---in this case the next-to-highest. See section <A HREF="bison.html#SEC86">Context-Dependent Precedence</A>. <P> @@ -1674,20 +1926,20 @@ <PRE> -% calc -4 + 4.5 - (34/(8*3+-3)) +$ <KBD>calc</KBD> +<KBD>4 + 4.5 - (34/(8*3+-3))</KBD> 6.880952381 --56 + 2 +<KBD>-56 + 2</KBD> -54 -3 ^ 2 +<KBD>3 ^ 2</KBD> 9 </PRE> -<H2><A NAME="SEC29" HREF="bison_toc.html#TOC29">Simple Error Recovery</A></H2> +<H2><A NAME="SEC30" HREF="bison_toc.html#TOC30">Simple Error Recovery</A></H2> <P> -<A NAME="IDX47"></A> +<A NAME="IDX58"></A> <P> @@ -1720,10 +1972,11 @@ and parsing will continue. (The <CODE>yyerror</CODE> function is still called upon to print its message as well.) The action executes the statement <CODE>yyerrok</CODE>, a macro defined automatically by Bison; its meaning is -that error recovery is complete (see section <A HREF="bison.html#SEC90">Error Recovery</A>). Note the +that error recovery is complete (see section <A HREF="bison.html#SEC92">Error Recovery</A>). Note the difference between <CODE>yyerrok</CODE> and <CODE>yyerror</CODE>; neither one is a misprint. + <P> This form of error recovery deals with syntax errors. There are other kinds of errors; for example, division by zero, which raises an exception @@ -1736,32 +1989,28 @@ -<H2><A NAME="SEC30" HREF="bison_toc.html#TOC30">Location Tracking Calculator: <CODE>ltcalc</CODE></A></H2> -<P> -<A NAME="IDX48"></A> -<A NAME="IDX49"></A> -<A NAME="IDX50"></A> - - +<H2><A NAME="SEC31" HREF="bison_toc.html#TOC31">Location Tracking Calculator: <CODE>ltcalc</CODE></A></H2> <P> -This example extends the infix notation calculator with location tracking. -This feature will be used to improve error reporting, and provide better -error messages. +<A NAME="IDX59"></A> +<A NAME="IDX60"></A> +<A NAME="IDX61"></A> <P> -For the sake of clarity, we will switch for this example to an integer -calculator, since most of the work needed to use locations will be done -in the lexical analyser. +This example extends the infix notation calculator with location +tracking. This feature will be used to improve the error messages. For +the sake of clarity, this example is a simple integer calculator, since +most of the work needed to use locations will be done in the lexical +analyzer. -<H3><A NAME="SEC31" HREF="bison_toc.html#TOC31">Declarations for <CODE>ltcalc</CODE></A></H3> +<H3><A NAME="SEC32" HREF="bison_toc.html#TOC32">Declarations for <CODE>ltcalc</CODE></A></H3> <P> -The C and Bison declarations for the location tracking calculator are the same -as the declarations for the infix notation calculator. +The C and Bison declarations for the location tracking calculator are +the same as the declarations for the infix notation calculator. @@ -1785,27 +2034,28 @@ </PRE> <P> -In the code above, there are no declarations specific to locations. Defining -a data type for storing locations is not needed: we will use the type provided -by default (see section <A HREF="bison.html#SEC55">Data Type of Locations</A>), which is a four -member structure with the following integer fields: <CODE>first_line</CODE>, -<CODE>first_column</CODE>, <CODE>last_line</CODE> and <CODE>last_column</CODE>. +Note there are no declarations specific to locations. Defining a data +type for storing locations is not needed: we will use the type provided +by default (see section <A HREF="bison.html#SEC56">Data Type of Locations</A>), which is a +four member structure with the following integer fields: +<CODE>first_line</CODE>, <CODE>first_column</CODE>, <CODE>last_line</CODE> and +<CODE>last_column</CODE>. -<H3><A NAME="SEC32" HREF="bison_toc.html#TOC32">Grammar Rules for <CODE>ltcalc</CODE></A></H3> +<H3><A NAME="SEC33" HREF="bison_toc.html#TOC33">Grammar Rules for <CODE>ltcalc</CODE></A></H3> <P> -Whether you choose to handle locations or not has no effect on the syntax of -your language. Therefore, grammar rules for this example will be very close to -those of the previous example: we will only modify them to benefit from the new -informations we will have. +Whether handling locations or not has no effect on the syntax of your +language. Therefore, grammar rules for this example will be very close +to those of the previous example: we will only modify them to benefit +from the new information. <P> -Here, we will use locations to report divisions by zero, and locate the wrong -expressions or subexpressions. +Here, we will use locations to report divisions by zero, and locate the +wrong expressions or subexpressions. @@ -1829,9 +2079,9 @@ else { $$ = 1; - printf("Division by zero, l%d,c%d-l%d,c%d", - @3.first_line, @3.first_column, - @3.last_line, @3.last_column); + fprintf (stderr, "%d.%d-%d.%d: division by zero", + @3.first_line, @3.first_column, + @3.last_line, @3.last_column); } } | '-' exp %preg NEG { $$ = -$2; } @@ -1846,31 +2096,28 @@ <P> -In this example, we never assign a value to <CODE>@$</CODE>, because the -output parser can do this automatically. By default, before executing -the C code of each action, <CODE>@$</CODE> is set to range from the beginning -of <CODE>@1</CODE> to the end of <CODE>@<VAR>n</VAR></CODE>, for a rule with <VAR>n</VAR> -components. +We don't need to assign a value to <CODE>@$</CODE>: the output parser does it +automatically. By default, before executing the C code of each action, +<CODE>@$</CODE> is set to range from the beginning of <CODE>@1</CODE> to the end +of <CODE>@<VAR>n</VAR></CODE>, for a rule with <VAR>n</VAR> components. This behavior +can be redefined (see section <A HREF="bison.html#SEC58">Default Action for Locations</A>), and for very specific rules, <CODE>@$</CODE> can be computed by +hand. -<P> -Of course, this behavior can be redefined (see section <A HREF="bison.html#SEC57">Default Action for Locations</A>), and for very specific rules, -<CODE>@$</CODE> can be computed by hand. - - -<H3><A NAME="SEC33" HREF="bison_toc.html#TOC33">The <CODE>ltcalc</CODE> Lexical Analyzer.</A></H3> +<H3><A NAME="SEC34" HREF="bison_toc.html#TOC34">The <CODE>ltcalc</CODE> Lexical Analyzer.</A></H3> <P> -Until now, we relied on Bison's defaults to enable location tracking. The next -step is to rewrite the lexical analyser, and make it able to feed the parser -with locations of tokens, as he already does for semantic values. +Until now, we relied on Bison's defaults to enable location +tracking. The next step is to rewrite the lexical analyzer, and make it +able to feed the parser with the token locations, as it already does for +semantic values. <P> -To do so, we must take into account every single character of the input text, -to avoid the computed locations of being fuzzy or wrong: +To this end, we must take into account every single character of the +input text, to avoid the computed locations of being fuzzy or wrong: @@ -1880,15 +2127,15 @@ { int c; - /* skip white space */ + /* Skip white space. */ while ((c = getchar ()) == ' ' || c == '\t') ++yylloc.last_column; - /* step */ + /* Step. */ yylloc.first_line = yylloc.last_line; yylloc.first_column = yylloc.last_column; - /* process numbers */ + /* Process numbers. */ if (isdigit (c)) { yylval = c - '0'; @@ -1902,11 +2149,11 @@ return NUM; } - /* return end-of-file */ + /* Return end-of-input. */ if (c == EOF) return 0; - /* return single chars and update location */ + /* Return a single char, and update location. */ if (c == '\n') { ++yylloc.last_line; @@ -1919,17 +2166,17 @@ </PRE> <P> -Basically, the lexical analyzer does the same processing as before: it skips -blanks and tabs, and reads numbers or single-character tokens. In addition -to this, it updates the <CODE>yylloc</CODE> global variable (of type <CODE>YYLTYPE</CODE>), -where the location of tokens is stored. +Basically, the lexical analyzer performs the same processing as before: +it skips blanks and tabs, and reads numbers or single-character tokens. +In addition, it updates <CODE>yylloc</CODE>, the global variable (of type +<CODE>YYLTYPE</CODE>) containing the token's location. <P> -Now, each time this function returns a token, the parser has it's number as -well as it's semantic value, and it's position in the text. The last needed -change is to initialize <CODE>yylloc</CODE>, for example in the controlling -function: +Now, each time this function returns a token, the parser has its number +as well as its semantic value, and its location in the text. The last +needed change is to initialize <CODE>yylloc</CODE>, for example in the +controlling function: @@ -1944,18 +2191,18 @@ </PRE> <P> -Remember that computing locations is not a matter of syntax. Every character -must be associated to a location update, whether it is in valid input, in -comments, in literal strings, and so on... +Remember that computing locations is not a matter of syntax. Every +character must be associated to a location update, whether it is in +valid input, in comments, in literal strings, and so on. -<H2><A NAME="SEC34" HREF="bison_toc.html#TOC34">Multi-Function Calculator: <CODE>mfcalc</CODE></A></H2> +<H2><A NAME="SEC35" HREF="bison_toc.html#TOC35">Multi-Function Calculator: <CODE>mfcalc</CODE></A></H2> <P> -<A NAME="IDX51"></A> -<A NAME="IDX52"></A> -<A NAME="IDX53"></A> +<A NAME="IDX62"></A> +<A NAME="IDX63"></A> +<A NAME="IDX64"></A> <P> @@ -1987,20 +2234,20 @@ <PRE> -% mfcalc -pi = 3.141592653589 +$ <KBD>mfcalc</KBD> +<KBD>pi = 3.141592653589</KBD> 3.1415926536 -sin(pi) +<KBD>sin(pi)</KBD> 0.0000000000 -alpha = beta1 = 2.3 +<KBD>alpha = beta1 = 2.3</KBD> 2.3000000000 -alpha +<KBD>alpha</KBD> 2.3000000000 -ln(alpha) +<KBD>ln(alpha)</KBD> 0.8329091229 -exp(ln(beta1)) +<KBD>exp(ln(beta1))</KBD> 2.3000000000 -% +$ </PRE> <P> @@ -2009,7 +2256,7 @@ -<H3><A NAME="SEC35" HREF="bison_toc.html#TOC35">Declarations for <CODE>mfcalc</CODE></A></H3> +<H3><A NAME="SEC36" HREF="bison_toc.html#TOC36">Declarations for <CODE>mfcalc</CODE></A></H3> <P> Here are the C and Bison declarations for the multi-function calculator. @@ -2018,7 +2265,7 @@ <PRE> %{ -#include <math.h> /* For math functions, cos(), sin(), etc. */ +#include <math.h> /* For math functions, cos(), sin(), etc. */ #include "calc.h" /* Contains definition of `symrec' */ %} %union { @@ -2044,14 +2291,14 @@ <P> The above grammar introduces only two new features of the Bison language. These features allow semantic values to have various data types -(see section <A HREF="bison.html#SEC50">More Than One Value Type</A>). +(see section <A HREF="bison.html#SEC51">More Than One Value Type</A>). <P> The <CODE>%union</CODE> declaration specifies the entire list of possible types; this is instead of defining <CODE>YYSTYPE</CODE>. The allowable types are now double-floats (for <CODE>exp</CODE> and <CODE>NUM</CODE>) and pointers to entries in -the symbol table. See section <A HREF="bison.html#SEC61">The Collection of Value Types</A>. +the symbol table. See section <A HREF="bison.html#SEC62">The Collection of Value Types</A>. <P> @@ -2063,16 +2310,17 @@ <P> -The Bison construct <CODE>%type</CODE> is used for declaring nonterminal symbols, -just as <CODE>%token</CODE> is used for declaring token types. We have not used -<CODE>%type</CODE> before because nonterminal symbols are normally declared -implicitly by the rules that define them. But <CODE>exp</CODE> must be declared -explicitly so we can specify its value type. See section <A HREF="bison.html#SEC62">Nonterminal Symbols</A>. +The Bison construct <CODE>%type</CODE> is used for declaring nonterminal +symbols, just as <CODE>%token</CODE> is used for declaring token types. We +have not used <CODE>%type</CODE> before because nonterminal symbols are +normally declared implicitly by the rules that define them. But +<CODE>exp</CODE> must be declared explicitly so we can specify its value type. +See section <A HREF="bison.html#SEC63">Nonterminal Symbols</A>. -<H3><A NAME="SEC36" HREF="bison_toc.html#TOC36">Grammar Rules for <CODE>mfcalc</CODE></A></H3> +<H3><A NAME="SEC37" HREF="bison_toc.html#TOC37">Grammar Rules for <CODE>mfcalc</CODE></A></H3> <P> Here are the grammar rules for the multi-function calculator. @@ -2110,9 +2358,9 @@ -<H3><A NAME="SEC37" HREF="bison_toc.html#TOC37">The <CODE>mfcalc</CODE> Symbol Table</A></H3> +<H3><A NAME="SEC38" HREF="bison_toc.html#TOC38">The <CODE>mfcalc</CODE> Symbol Table</A></H3> <P> -<A NAME="IDX54"></A> +<A NAME="IDX65"></A> <P> @@ -2130,7 +2378,7 @@ <PRE> -/* Fonctions type. */ +/* Function type. */ typedef double (*func_t) (double); /* Data type for links in the chain of symbols. */ @@ -2198,7 +2446,7 @@ /* The symbol table: a chain of `struct symrec'. */ symrec *sym_table = (symrec *) 0; -/* Put arithmetic functions in table. */ +/* Put arithmetic functions in table. */ void init_table (void) { @@ -2236,7 +2484,7 @@ ptr->name = (char *) malloc (strlen (sym_name) + 1); strcpy (ptr->name,sym_name); ptr->type = sym_type; - ptr->value.var = 0; /* set value to 0 even if fctn. */ + ptr->value.var = 0; /* Set value to 0 even if fctn. */ ptr->next = (struct symrec *)sym_table; sym_table = ptr; return ptr; @@ -2269,6 +2517,7 @@ <CODE>putsym</CODE>. Again, a pointer and its type (which must be <CODE>VAR</CODE>) is returned to <CODE>yyparse</CODE>. + <P> No change is needed in the handling of numeric values and arithmetic operators in <CODE>yylex</CODE>. @@ -2283,7 +2532,7 @@ { int c; - /* Ignore whitespace, get first nonwhite character. */ + /* Ignore white space, get first nonwhite character. */ while ((c = getchar ()) == ' ' || c == '\t'); if (c == EOF) @@ -2324,7 +2573,7 @@ /* Get another character. */ c = getchar (); } - while (c != EOF && isalnum (c)); + while (isalnum (c)); ungetc (c, stdin); symbuf[i] = '\0'; @@ -2342,16 +2591,16 @@ </PRE> <P> -This program is both powerful and flexible. You may easily add new -functions, and it is a simple job to modify this code to install predefined -variables such as <CODE>pi</CODE> or <CODE>e</CODE> as well. +This program is both powerful and flexible. You may easily add new +functions, and it is a simple job to modify this code to install +predefined variables such as <CODE>pi</CODE> or <CODE>e</CODE> as well. -<H2><A NAME="SEC38" HREF="bison_toc.html#TOC38">Exercises</A></H2> +<H2><A NAME="SEC39" HREF="bison_toc.html#TOC39">Exercises</A></H2> <P> -<A NAME="IDX55"></A> +<A NAME="IDX66"></A> @@ -2374,7 +2623,7 @@ -<H1><A NAME="SEC39" HREF="bison_toc.html#TOC39">Bison Grammar Files</A></H1> +<H1><A NAME="SEC40" HREF="bison_toc.html#TOC40">Bison Grammar Files</A></H1> <P> Bison takes as input a context-free grammar specification and produces a @@ -2383,12 +2632,12 @@ <P> The Bison grammar input file conventionally has a name ending in <SAMP>`.y'</SAMP>. -See section <A HREF="bison.html#SEC96">Invoking Bison</A>. +See section <A HREF="bison.html#SEC100">Invoking Bison</A>. -<H2><A NAME="SEC40" HREF="bison_toc.html#TOC40">Outline of a Bison Grammar</A></H2> +<H2><A NAME="SEC41" HREF="bison_toc.html#TOC41">Outline of a Bison Grammar</A></H2> <P> A Bison grammar file has four main sections, shown here with the @@ -2398,7 +2647,7 @@ <PRE> %{ -<VAR>C declarations</VAR> +<VAR>Prologue</VAR> %} <VAR>Bison declarations</VAR> @@ -2407,7 +2656,7 @@ <VAR>Grammar rules</VAR> %% -<VAR>Additional C code</VAR> +<VAR>Epilogue</VAR> </PRE> <P> @@ -2416,14 +2665,15 @@ -<H3><A NAME="SEC41" HREF="bison_toc.html#TOC41">The C Declarations Section</A></H3> +<H3><A NAME="SEC42" HREF="bison_toc.html#TOC42">The prologue</A></H3> <P> -<A NAME="IDX56"></A> -<A NAME="IDX57"></A> +<A NAME="IDX67"></A> +<A NAME="IDX68"></A> +<A NAME="IDX69"></A> <P> -The <VAR>C declarations</VAR> section contains macro definitions and +The <VAR>Prologue</VAR> section contains macro definitions and declarations of functions and variables that are used in the actions in the grammar rules. These are copied to the beginning of the parser file so that they precede the definition of <CODE>yyparse</CODE>. You can use @@ -2432,32 +2682,62 @@ delimiters that bracket this section. +<P> +You may have more than one <VAR>Prologue</VAR> section, intermixed with the +<VAR>Bison declarations</VAR>. This allows you to have C and Bison +declarations that refer to each other. For example, the <CODE>%union</CODE> +declaration may use types defined in a header file, and you may wish to +prototype functions that take arguments of type <CODE>YYSTYPE</CODE>. This +can be done with two <VAR>Prologue</VAR> blocks, one before and one after the +<CODE>%union</CODE> declaration. + + + +<PRE> +%{ +#include <stdio.h> +#include "ptypes.h" +%} + +%union { + long n; + tree t; /* <CODE>tree</CODE> is defined in <TT>`ptypes.h'</TT>. */ +} + +%{ +static void yyprint(FILE *, int, YYSTYPE); +#define YYPRINT(F, N, L) yyprint(F, N, L) +%} + +... +</PRE> + -<H3><A NAME="SEC42" HREF="bison_toc.html#TOC42">The Bison Declarations Section</A></H3> +<H3><A NAME="SEC43" HREF="bison_toc.html#TOC43">The Bison Declarations Section</A></H3> <P> -<A NAME="IDX58"></A> -<A NAME="IDX59"></A> +<A NAME="IDX70"></A> +<A NAME="IDX71"></A> <P> The <VAR>Bison declarations</VAR> section contains declarations that define terminal and nonterminal symbols, specify precedence, and so on. In some simple grammars you may not need any declarations. -See section <A HREF="bison.html#SEC58">Bison Declarations</A>. +See section <A HREF="bison.html#SEC59">Bison Declarations</A>. -<H3><A NAME="SEC43" HREF="bison_toc.html#TOC43">The Grammar Rules Section</A></H3> +<H3><A NAME="SEC44" HREF="bison_toc.html#TOC44">The Grammar Rules Section</A></H3> <P> -<A NAME="IDX60"></A> -<A NAME="IDX61"></A> +<A NAME="IDX72"></A> +<A NAME="IDX73"></A> <P> The <EM>grammar rules</EM> section contains one or more Bison grammar -rules, and nothing else. See section <A HREF="bison.html#SEC46">Syntax of Grammar Rules</A>. +rules, and nothing else. See section <A HREF="bison.html#SEC47">Syntax of Grammar Rules</A>. <P> @@ -2468,19 +2748,20 @@ -<H3><A NAME="SEC44" HREF="bison_toc.html#TOC44">The Additional C Code Section</A></H3> +<H3><A NAME="SEC45" HREF="bison_toc.html#TOC45">The epilogue</A></H3> <P> -<A NAME="IDX62"></A> -<A NAME="IDX63"></A> +<A NAME="IDX74"></A> +<A NAME="IDX75"></A> +<A NAME="IDX76"></A> <P> -The <VAR>additional C code</VAR> section is copied verbatim to the end of the -parser file, just as the <VAR>C declarations</VAR> section is copied to the -beginning. This is the most convenient place to put anything that you -want to have in the parser file but which need not come before the -definition of <CODE>yyparse</CODE>. For example, the definitions of -<CODE>yylex</CODE> and <CODE>yyerror</CODE> often go here. See section <A HREF="bison.html#SEC68">Parser C-Language Interface</A>. +The <VAR>Epilogue</VAR> is copied verbatim to the end of the parser file, just as +the <VAR>Prologue</VAR> is copied to the beginning. This is the most convenient +place to put anything that you want to have in the parser file but which need +not come before the definition of <CODE>yyparse</CODE>. For example, the +definitions of <CODE>yylex</CODE> and <CODE>yyerror</CODE> often go here. +See section <A HREF="bison.html#SEC69">Parser C-Language Interface</A>. <P> @@ -2492,17 +2773,17 @@ The Bison parser itself contains many static variables whose names start with <SAMP>`yy'</SAMP> and many macros whose names start with <SAMP>`YY'</SAMP>. It is a good idea to avoid using any such names (except those documented in this -manual) in the additional C code section of the grammar file. +manual) in the epilogue of the grammar file. -<H2><A NAME="SEC45" HREF="bison_toc.html#TOC45">Symbols, Terminal and Nonterminal</A></H2> +<H2><A NAME="SEC46" HREF="bison_toc.html#TOC46">Symbols, Terminal and Nonterminal</A></H2> <P> -<A NAME="IDX64"></A> -<A NAME="IDX65"></A> -<A NAME="IDX66"></A> -<A NAME="IDX67"></A> +<A NAME="IDX77"></A> +<A NAME="IDX78"></A> +<A NAME="IDX79"></A> +<A NAME="IDX80"></A> <P> @@ -2542,18 +2823,18 @@ A <EM>named token type</EM> is written with an identifier, like an identifier in C. By convention, it should be all upper case. Each such name must be defined with a Bison declaration such as -<CODE>%token</CODE>. See section <A HREF="bison.html#SEC59">Token Type Names</A>. +<CODE>%token</CODE>. See section <A HREF="bison.html#SEC60">Token Type Names</A>. <LI> -<A NAME="IDX68"></A> -<A NAME="IDX69"></A> -<A NAME="IDX70"></A> +<A NAME="IDX81"></A> +<A NAME="IDX82"></A> +<A NAME="IDX83"></A> A <EM>character token type</EM> (or <EM>literal character token</EM>) is written in the grammar using the same syntax used in C for character constants; for example, <CODE>'+'</CODE> is a character token type. A character token type doesn't need to be declared unless you need to -specify its semantic value data type (see section <A HREF="bison.html#SEC49">Data Types of Semantic Values</A>), associativity, or precedence (see section <A HREF="bison.html#SEC80">Operator Precedence</A>). +specify its semantic value data type (see section <A HREF="bison.html#SEC50">Data Types of Semantic Values</A>), associativity, or precedence (see section <A HREF="bison.html#SEC81">Operator Precedence</A>). By convention, a character token type is used only to represent a token that consists of that particular character. Thus, the token @@ -2563,24 +2844,24 @@ All the usual escape sequences used in character literals in C can be used in Bison as well, but you must not use the null character as a -character literal because its ASCII code, zero, is the code <CODE>yylex</CODE> -returns for end-of-input (see section <A HREF="bison.html#SEC71">Calling Convention for <CODE>yylex</CODE></A>). +character literal because its numeric code, zero, signifies +end-of-input (see section <A HREF="bison.html#SEC72">Calling Convention for <CODE>yylex</CODE></A>). <LI> -<A NAME="IDX71"></A> -<A NAME="IDX72"></A> -<A NAME="IDX73"></A> +<A NAME="IDX84"></A> +<A NAME="IDX85"></A> +<A NAME="IDX86"></A> A <EM>literal string token</EM> is written like a C string constant; for example, <CODE>"<="</CODE> is a literal string token. A literal string token doesn't need to be declared unless you need to specify its semantic -value data type (see section <A HREF="bison.html#SEC49">Data Types of Semantic Values</A>), associativity, or precedence -(see section <A HREF="bison.html#SEC80">Operator Precedence</A>). +value data type (see section <A HREF="bison.html#SEC50">Data Types of Semantic Values</A>), associativity, or precedence +(see section <A HREF="bison.html#SEC81">Operator Precedence</A>). You can associate the literal string token with a symbolic name as an -alias, using the <CODE>%token</CODE> declaration (see section <A HREF="bison.html#SEC59">Token Type Names</A>). If you don't do that, the lexical analyzer has to +alias, using the <CODE>%token</CODE> declaration (see section <A HREF="bison.html#SEC60">Token Type Names</A>). If you don't do that, the lexical analyzer has to retrieve the token number for the literal string token from the -<CODE>yytname</CODE> table (see section <A HREF="bison.html#SEC71">Calling Convention for <CODE>yylex</CODE></A>). +<CODE>yytname</CODE> table (see section <A HREF="bison.html#SEC72">Calling Convention for <CODE>yylex</CODE></A>). <STRONG>WARNING</STRONG>: literal string tokens do not work in Yacc. @@ -2603,15 +2884,18 @@ <P> -The value returned by <CODE>yylex</CODE> is always one of the terminal symbols -(or 0 for end-of-input). Whichever way you write the token type in the -grammar rules, you write it the same way in the definition of <CODE>yylex</CODE>. -The numeric code for a character token type is simply the ASCII code for -the character, so <CODE>yylex</CODE> can use the identical character constant to -generate the requisite code. Each named token type becomes a C macro in +The value returned by <CODE>yylex</CODE> is always one of the terminal +symbols, except that a zero or negative value signifies end-of-input. +Whichever way you write the token type in the grammar rules, you write +it the same way in the definition of <CODE>yylex</CODE>. The numeric code +for a character token type is simply the positive numeric code of the +character, so <CODE>yylex</CODE> can use the identical value to generate the +requisite code, though you may need to convert it to <CODE>unsigned +char</CODE> to avoid sign-extension on hosts where <CODE>char</CODE> is signed. +Each named token type becomes a C macro in the parser file, so <CODE>yylex</CODE> can use the name to stand for the code. (This is why periods don't make sense in terminal symbols.) -See section <A HREF="bison.html#SEC71">Calling Convention for <CODE>yylex</CODE></A>. +See section <A HREF="bison.html#SEC72">Calling Convention for <CODE>yylex</CODE></A>. <P> @@ -2619,22 +2903,51 @@ token-type macro definitions to be available there. Use the <SAMP>`-d'</SAMP> option when you run Bison, so that it will write these macro definitions into a separate header file <TT>`<VAR>name</VAR>.tab.h'</TT> which you can include -in the other source files that need it. See section <A HREF="bison.html#SEC96">Invoking Bison</A>. +in the other source files that need it. See section <A HREF="bison.html#SEC100">Invoking Bison</A>. + + +<P> +If you want to write a grammar that is portable to any Standard C +host, you must use only non-null character tokens taken from the basic +execution character set of Standard C. This set consists of the ten +digits, the 52 lower- and upper-case English letters, and the +characters in the following C-language string: + + + +<PRE> +"\a\b\t\n\v\f\r !\"#%&'()*+,-./:;<=>?[\\]^_{|}~" +</PRE> + +<P> +The <CODE>yylex</CODE> function and Bison must use a consistent character +set and encoding for character tokens. For example, if you run Bison in an +ASCII environment, but then compile and run the resulting program +in an environment that uses an incompatible character set like +EBCDIC, the resulting program may not work because the +tables generated by Bison will assume ASCII numeric values for +character tokens. It is standard +practice for software distributions to contain C source files that +were generated by Bison in an ASCII environment, so installers on +platforms that are incompatible with ASCII must rebuild those +files before compiling them. <P> The symbol <CODE>error</CODE> is a terminal symbol reserved for error recovery -(see section <A HREF="bison.html#SEC90">Error Recovery</A>); you shouldn't use it for any other purpose. -In particular, <CODE>yylex</CODE> should never return this value. +(see section <A HREF="bison.html#SEC92">Error Recovery</A>); you shouldn't use it for any other purpose. +In particular, <CODE>yylex</CODE> should never return this value. The default +value of the error token is 256, unless you explicitly assigned 256 to +one of your tokens with a <CODE>%token</CODE> declaration. -<H2><A NAME="SEC46" HREF="bison_toc.html#TOC46">Syntax of Grammar Rules</A></H2> +<H2><A NAME="SEC47" HREF="bison_toc.html#TOC47">Syntax of Grammar Rules</A></H2> <P> -<A NAME="IDX74"></A> -<A NAME="IDX75"></A> -<A NAME="IDX76"></A> +<A NAME="IDX87"></A> +<A NAME="IDX88"></A> +<A NAME="IDX89"></A> <P> @@ -2650,7 +2963,7 @@ <P> where <VAR>result</VAR> is the nonterminal symbol that this rule describes, and <VAR>components</VAR> are various terminal and nonterminal symbols that -are put together by this rule (see section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>). +are put together by this rule (see section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>). <P> @@ -2669,8 +2982,8 @@ <P> -Whitespace in rules is significant only to separate symbols. You can add -extra whitespace as you wish. +White space in rules is significant only to separate symbols. You can add +extra white space as you wish. <P> @@ -2685,11 +2998,11 @@ <P> Usually there is only one action and it follows the components. -See section <A HREF="bison.html#SEC51">Actions</A>. +See section <A HREF="bison.html#SEC52">Actions</A>. <P> -<A NAME="IDX77"></A> +<A NAME="IDX90"></A> Multiple rules for the same <VAR>result</VAR> can be written separately or can be joined with the vertical-bar character <SAMP>`|'</SAMP> as follows: @@ -2730,9 +3043,9 @@ -<H2><A NAME="SEC47" HREF="bison_toc.html#TOC47">Recursive Rules</A></H2> +<H2><A NAME="SEC48" HREF="bison_toc.html#TOC48">Recursive Rules</A></H2> <P> -<A NAME="IDX78"></A> +<A NAME="IDX91"></A> <P> @@ -2751,8 +3064,8 @@ </PRE> <P> -<A NAME="IDX79"></A> -<A NAME="IDX80"></A> +<A NAME="IDX92"></A> +<A NAME="IDX93"></A> Since the recursive use of <CODE>expseq1</CODE> is the leftmost symbol in the right hand side, we call this <EM>left recursion</EM>. By contrast, here the same construct is defined using <EM>right recursion</EM>: @@ -2766,18 +3079,18 @@ </PRE> <P> -Any kind of sequence can be defined using either left recursion or -right recursion, but you should always use left recursion, because it -can parse a sequence of any number of elements with bounded stack -space. Right recursion uses up space on the Bison stack in proportion -to the number of elements in the sequence, because all the elements -must be shifted onto the stack before the rule can be applied even -once. See section <A HREF="bison.html#SEC77">The Bison Parser Algorithm</A>, for -further explanation of this. +Any kind of sequence can be defined using either left recursion or right +recursion, but you should always use left recursion, because it can +parse a sequence of any number of elements with bounded stack space. +Right recursion uses up space on the Bison stack in proportion to the +number of elements in the sequence, because all the elements must be +shifted onto the stack before the rule can be applied even once. +See section <A HREF="bison.html#SEC78">The Bison Parser Algorithm</A>, for further explanation +of this. <P> -<A NAME="IDX81"></A> +<A NAME="IDX94"></A> <EM>Indirect</EM> or <EM>mutual</EM> recursion occurs when the result of the rule does not appear directly on its right hand side, but does appear in rules for other nonterminals which do appear on its right hand @@ -2806,10 +3119,10 @@ -<H2><A NAME="SEC48" HREF="bison_toc.html#TOC48">Defining Language Semantics</A></H2> +<H2><A NAME="SEC49" HREF="bison_toc.html#TOC49">Defining Language Semantics</A></H2> <P> -<A NAME="IDX82"></A> -<A NAME="IDX83"></A> +<A NAME="IDX95"></A> +<A NAME="IDX96"></A> <P> @@ -2827,18 +3140,18 @@ -<H3><A NAME="SEC49" HREF="bison_toc.html#TOC49">Data Types of Semantic Values</A></H3> +<H3><A NAME="SEC50" HREF="bison_toc.html#TOC50">Data Types of Semantic Values</A></H3> <P> -<A NAME="IDX84"></A> -<A NAME="IDX85"></A> -<A NAME="IDX86"></A> -<A NAME="IDX87"></A> +<A NAME="IDX97"></A> +<A NAME="IDX98"></A> +<A NAME="IDX99"></A> +<A NAME="IDX100"></A> <P> In a simple program it may be sufficient to use the same data type for the semantic values of all language constructs. This was true in the -RPN and infix calculator examples (see section <A HREF="bison.html#SEC17">Reverse Polish Notation Calculator</A>). +RPN and infix calculator examples (see section <A HREF="bison.html#SEC18">Reverse Polish Notation Calculator</A>). <P> @@ -2852,13 +3165,13 @@ </PRE> <P> -This macro definition must go in the C declarations section of the grammar -file (see section <A HREF="bison.html#SEC40">Outline of a Bison Grammar</A>). +This macro definition must go in the prologue of the grammar file +(see section <A HREF="bison.html#SEC41">Outline of a Bison Grammar</A>). -<H3><A NAME="SEC50" HREF="bison_toc.html#TOC50">More Than One Value Type</A></H3> +<H3><A NAME="SEC51" HREF="bison_toc.html#TOC51">More Than One Value Type</A></H3> <P> In most programs, you will need different data types for different kinds @@ -2877,23 +3190,23 @@ <LI> Specify the entire collection of possible data types, with the -<CODE>%union</CODE> Bison declaration (see section <A HREF="bison.html#SEC61">The Collection of Value Types</A>). +<CODE>%union</CODE> Bison declaration (see section <A HREF="bison.html#SEC62">The Collection of Value Types</A>). <LI> Choose one of those types for each symbol (terminal or nonterminal) for which semantic values are used. This is done for tokens with the -<CODE>%token</CODE> Bison declaration (see section <A HREF="bison.html#SEC59">Token Type Names</A>) -and for groupings with the <CODE>%type</CODE> Bison declaration (see section <A HREF="bison.html#SEC62">Nonterminal Symbols</A>). +<CODE>%token</CODE> Bison declaration (see section <A HREF="bison.html#SEC60">Token Type Names</A>) +and for groupings with the <CODE>%type</CODE> Bison declaration (see section <A HREF="bison.html#SEC63">Nonterminal Symbols</A>). </UL> -<H3><A NAME="SEC51" HREF="bison_toc.html#TOC51">Actions</A></H3> +<H3><A NAME="SEC52" HREF="bison_toc.html#TOC52">Actions</A></H3> <P> -<A NAME="IDX88"></A> -<A NAME="IDX89"></A> -<A NAME="IDX90"></A> +<A NAME="IDX101"></A> +<A NAME="IDX102"></A> +<A NAME="IDX103"></A> <P> @@ -2905,10 +3218,10 @@ <P> An action consists of C statements surrounded by braces, much like a -compound statement in C. It can be placed at any position in the rule; it -is executed at that position. Most rules have just one action at the end -of the rule, following all the components. Actions in the middle of a rule -are tricky and used only for special purposes (see section <A HREF="bison.html#SEC53">Actions in Mid-Rule</A>). +compound statement in C. It can be placed at any position in the rule; +it is executed at that position. Most rules have just one action at the +end of the rule, following all the components. Actions in the middle of +a rule are tricky and used only for special purposes (see section <A HREF="bison.html#SEC54">Actions in Mid-Rule</A>). <P> @@ -2941,8 +3254,22 @@ useful semantic value associated with the <SAMP>`+'</SAMP> token, it could be referred to as <CODE>$2</CODE>. + <P> -<A NAME="IDX91"></A> +Note that the vertical-bar character <SAMP>`|'</SAMP> is really a rule +separator, and actions are attached to a single rule. This is a +difference with tools like Flex, for which <SAMP>`|'</SAMP> stands for either +"or", or "the same action as that of the next rule". In the +following example, the action is triggered only when <SAMP>`b'</SAMP> is found: + + + +<PRE> +a-or-b: 'a'|'b' { a_or_b_found = 1; }; +</PRE> + +<P> +<A NAME="IDX104"></A> If you don't specify an action for a rule, Bison supplies a default: <CODE>$$ = $1</CODE>. Thus, the value of the first symbol in the rule becomes the value of the whole rule. Of course, the default rule is valid only @@ -2978,10 +3305,10 @@ -<H3><A NAME="SEC52" HREF="bison_toc.html#TOC52">Data Types of Values in Actions</A></H3> +<H3><A NAME="SEC53" HREF="bison_toc.html#TOC53">Data Types of Values in Actions</A></H3> <P> -<A NAME="IDX92"></A> -<A NAME="IDX93"></A> +<A NAME="IDX105"></A> +<A NAME="IDX106"></A> <P> @@ -2997,6 +3324,7 @@ in the rule. In this example, + <PRE> exp: ... | exp '+' exp @@ -3009,6 +3337,7 @@ <CODE>$2</CODE> were used, it would have the data type declared for the terminal symbol <CODE>'+'</CODE>, whatever that might be. + <P> Alternatively, you can specify the data type when you refer to the value, by inserting <SAMP>`<<VAR>type</VAR>>'</SAMP> after the <SAMP>`$'</SAMP> at the beginning of the @@ -3030,10 +3359,10 @@ -<H3><A NAME="SEC53" HREF="bison_toc.html#TOC53">Actions in Mid-Rule</A></H3> +<H3><A NAME="SEC54" HREF="bison_toc.html#TOC54">Actions in Mid-Rule</A></H3> <P> -<A NAME="IDX94"></A> -<A NAME="IDX95"></A> +<A NAME="IDX107"></A> +<A NAME="IDX108"></A> <P> @@ -3143,7 +3472,7 @@ must commit to using one rule or the other, without sufficient information to do it correctly. (The open-brace token is what is called the <EM>look-ahead</EM> token at this time, since the parser is still -deciding what to do about it. See section <A HREF="bison.html#SEC78">Look-Ahead Tokens</A>.) +deciding what to do about it. See section <A HREF="bison.html#SEC79">Look-Ahead Tokens</A>.) <P> @@ -3212,30 +3541,30 @@ -<H2><A NAME="SEC54" HREF="bison_toc.html#TOC54">Tracking Locations</A></H2> +<H2><A NAME="SEC55" HREF="bison_toc.html#TOC55">Tracking Locations</A></H2> <P> -<A NAME="IDX96"></A> -<A NAME="IDX97"></A> -<A NAME="IDX98"></A> +<A NAME="IDX109"></A> +<A NAME="IDX110"></A> +<A NAME="IDX111"></A> <P> Though grammar rules and semantic actions are enough to write a fully -functional parser, it can be useful to process some additionnal informations, +functional parser, it can be useful to process some additional information, especially symbol locations. <P> -The way locations are handled is defined by providing a data type, and actions -to take when rules are matched. +The way locations are handled is defined by providing a data type, and +actions to take when rules are matched. -<H3><A NAME="SEC55" HREF="bison_toc.html#TOC55">Data Type of Locations</A></H3> +<H3><A NAME="SEC56" HREF="bison_toc.html#TOC56">Data Type of Locations</A></H3> <P> -<A NAME="IDX99"></A> -<A NAME="IDX100"></A> +<A NAME="IDX112"></A> +<A NAME="IDX113"></A> <P> @@ -3262,12 +3591,12 @@ -<H3><A NAME="SEC56" HREF="bison_toc.html#TOC56">Actions and Locations</A></H3> +<H3><A NAME="SEC57" HREF="bison_toc.html#TOC57">Actions and Locations</A></H3> <P> -<A NAME="IDX101"></A> -<A NAME="IDX102"></A> -<A NAME="IDX103"></A> -<A NAME="IDX104"></A> +<A NAME="IDX114"></A> +<A NAME="IDX115"></A> +<A NAME="IDX116"></A> +<A NAME="IDX117"></A> <P> @@ -3277,7 +3606,7 @@ <P> The most obvious way for building locations of syntactic groupings is very -similar to the way semantic values are computed. In a given rule, several +similar to the way semantic values are computed. In a given rule, several constructs can be used to access the locations of the elements being matched. The location of the <VAR>n</VAR>th component of the right hand side is <CODE>@<VAR>n</VAR></CODE>, while the location of the left hand side grouping is @@ -3311,13 +3640,13 @@ <P> As for semantic values, there is a default action for locations that is -run each time a rule is matched. It sets the beginning of <CODE>@$</CODE> to the +run each time a rule is matched. It sets the beginning of <CODE>@$</CODE> to the beginning of the first symbol, and the end of <CODE>@$</CODE> to the end of the last symbol. <P> -With this default action, the location tracking can be fully automatic. The +With this default action, the location tracking can be fully automatic. The example above simply rewrites this way: @@ -3340,17 +3669,17 @@ -<H3><A NAME="SEC57" HREF="bison_toc.html#TOC57">Default Action for Locations</A></H3> +<H3><A NAME="SEC58" HREF="bison_toc.html#TOC58">Default Action for Locations</A></H3> <P> -<A NAME="IDX105"></A> +<A NAME="IDX118"></A> <P> -Actually, actions are not the best place to compute locations. Since locations -are much more general than semantic values, there is room in the output parser -to redefine the default action to take for each rule. The -<CODE>YYLLOC_DEFAULT</CODE> macro is called each time a rule is matched, before the -associated action is run. +Actually, actions are not the best place to compute locations. Since +locations are much more general than semantic values, there is room in +the output parser to redefine the default action to take for each +rule. The <CODE>YYLLOC_DEFAULT</CODE> macro is invoked each time a rule is +matched, before the associated action is run. <P> @@ -3359,21 +3688,36 @@ <P> -The <CODE>YYLLOC_DEFAULT</CODE> macro takes three parameters. The first one is -the location of the grouping (the result of the computation). The second one +The <CODE>YYLLOC_DEFAULT</CODE> macro takes three parameters. The first one is +the location of the grouping (the result of the computation). The second one is an array holding locations of all right hand side elements of the rule -being matched. The last one is the size of the right hand side rule. +being matched. The last one is the size of the right hand side rule. + + +<P> +By default, it is defined this way for simple LALR(1) parsers: + +<PRE> +#define YYLLOC_DEFAULT(Current, Rhs, N) \ + Current.first_line = Rhs[1].first_line; \ + Current.first_column = Rhs[1].first_column; \ + Current.last_line = Rhs[N].last_line; \ + Current.last_column = Rhs[N].last_column; +</PRE> + <P> -By default, it is defined this way: +and like this for GLR parsers: <PRE> -#define YYLLOC_DEFAULT(Current, Rhs, N) \ - Current.last_line = Rhs[N].last_line; \ - Current.last_column = Rhs[N].last_column; +#define YYLLOC_DEFAULT(Current, Rhs, N) \ + Current.first_line = YYRHSLOC(Rhs,1).first_line; \ + Current.first_column = YYRHSLOC(Rhs,1).first_column; \ + Current.last_line = YYRHSLOC(Rhs,N).last_line; \ + Current.last_column = YYRHSLOC(Rhs,N).last_column; </PRE> <P> @@ -3384,39 +3728,34 @@ <UL> <LI> -All arguments are free of side-effects. However, only the first one (the +All arguments are free of side-effects. However, only the first one (the result) should be modified by <CODE>YYLLOC_DEFAULT</CODE>. <LI> -Before <CODE>YYLLOC_DEFAULT</CODE> is executed, the output parser sets <CODE>@$</CODE> -to <CODE>@1</CODE>. - -<LI> - -For consistency with semantic actions, valid indexes for the location array -range from 1 to <VAR>n</VAR>. +For consistency with semantic actions, valid indexes for the location +array range from 1 to <VAR>n</VAR>. </UL> -<H2><A NAME="SEC58" HREF="bison_toc.html#TOC58">Bison Declarations</A></H2> +<H2><A NAME="SEC59" HREF="bison_toc.html#TOC59">Bison Declarations</A></H2> <P> -<A NAME="IDX106"></A> -<A NAME="IDX107"></A> +<A NAME="IDX119"></A> +<A NAME="IDX120"></A> <P> The <EM>Bison declarations</EM> section of a Bison grammar defines the symbols used in formulating the grammar and the data types of semantic values. -See section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>. +See section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>. <P> All token type names (but not single-character literal tokens such as <CODE>'+'</CODE> and <CODE>'*'</CODE>) must be declared. Nonterminal symbols must be declared if you need to specify which data type to use for the semantic -value (see section <A HREF="bison.html#SEC50">More Than One Value Type</A>). +value (see section <A HREF="bison.html#SEC51">More Than One Value Type</A>). <P> @@ -3427,12 +3766,12 @@ -<H3><A NAME="SEC59" HREF="bison_toc.html#TOC59">Token Type Names</A></H3> +<H3><A NAME="SEC60" HREF="bison_toc.html#TOC60">Token Type Names</A></H3> <P> -<A NAME="IDX108"></A> -<A NAME="IDX109"></A> -<A NAME="IDX110"></A> -<A NAME="IDX111"></A> +<A NAME="IDX121"></A> +<A NAME="IDX122"></A> +<A NAME="IDX123"></A> +<A NAME="IDX124"></A> <P> @@ -3453,7 +3792,7 @@ <P> Alternatively, you can use <CODE>%left</CODE>, <CODE>%right</CODE>, or <CODE>%nonassoc</CODE> instead of <CODE>%token</CODE>, if you wish to specify -associativity and precedence. See section <A HREF="bison.html#SEC60">Operator Precedence</A>. +associativity and precedence. See section <A HREF="bison.html#SEC61">Operator Precedence</A>. <P> @@ -3469,13 +3808,13 @@ <P> It is generally best, however, to let Bison choose the numeric codes for all token types. Bison will automatically select codes that don't conflict -with each other or with ASCII characters. +with each other or with normal characters. <P> In the event that the stack type is a union, you must augment the <CODE>%token</CODE> or other token declaration to include the data type -alternative delimited by angle-brackets (see section <A HREF="bison.html#SEC50">More Than One Value Type</A>). +alternative delimited by angle-brackets (see section <A HREF="bison.html#SEC51">More Than One Value Type</A>). <P> @@ -3518,23 +3857,24 @@ Once you equate the literal string and the token name, you can use them interchangeably in further declarations or the grammar rules. The <CODE>yylex</CODE> function can use the token name or the literal string to -obtain the token type code number (see section <A HREF="bison.html#SEC71">Calling Convention for <CODE>yylex</CODE></A>). +obtain the token type code number (see section <A HREF="bison.html#SEC72">Calling Convention for <CODE>yylex</CODE></A>). -<H3><A NAME="SEC60" HREF="bison_toc.html#TOC60">Operator Precedence</A></H3> +<H3><A NAME="SEC61" HREF="bison_toc.html#TOC61">Operator Precedence</A></H3> <P> -<A NAME="IDX112"></A> -<A NAME="IDX113"></A> -<A NAME="IDX114"></A> +<A NAME="IDX125"></A> +<A NAME="IDX126"></A> +<A NAME="IDX127"></A> <P> Use the <CODE>%left</CODE>, <CODE>%right</CODE> or <CODE>%nonassoc</CODE> declaration to declare a token and specify its precedence and associativity, all at once. These are called <EM>precedence declarations</EM>. -See section <A HREF="bison.html#SEC80">Operator Precedence</A>, for general information on operator precedence. +See section <A HREF="bison.html#SEC81">Operator Precedence</A>, for general information on +operator precedence. <P> @@ -3587,11 +3927,11 @@ -<H3><A NAME="SEC61" HREF="bison_toc.html#TOC61">The Collection of Value Types</A></H3> +<H3><A NAME="SEC62" HREF="bison_toc.html#TOC62">The Collection of Value Types</A></H3> <P> -<A NAME="IDX115"></A> -<A NAME="IDX116"></A> -<A NAME="IDX117"></A> +<A NAME="IDX128"></A> +<A NAME="IDX129"></A> +<A NAME="IDX130"></A> <P> @@ -3617,7 +3957,7 @@ This says that the two alternative types are <CODE>double</CODE> and <CODE>symrec *</CODE>. They are given names <CODE>val</CODE> and <CODE>tptr</CODE>; these names are used in the <CODE>%token</CODE> and <CODE>%type</CODE> declarations to pick one of the types -for a terminal or nonterminal symbol (see section <A HREF="bison.html#SEC62">Nonterminal Symbols</A>). +for a terminal or nonterminal symbol (see section <A HREF="bison.html#SEC63">Nonterminal Symbols</A>). <P> @@ -3627,11 +3967,11 @@ -<H3><A NAME="SEC62" HREF="bison_toc.html#TOC62">Nonterminal Symbols</A></H3> +<H3><A NAME="SEC63" HREF="bison_toc.html#TOC63">Nonterminal Symbols</A></H3> <P> -<A NAME="IDX118"></A> -<A NAME="IDX119"></A> -<A NAME="IDX120"></A> +<A NAME="IDX131"></A> +<A NAME="IDX132"></A> +<A NAME="IDX133"></A> <P> @@ -3646,11 +3986,12 @@ </PRE> <P> -Here <VAR>nonterminal</VAR> is the name of a nonterminal symbol, and <VAR>type</VAR> -is the name given in the <CODE>%union</CODE> to the alternative that you want -(see section <A HREF="bison.html#SEC61">The Collection of Value Types</A>). You can give any number of nonterminal symbols in -the same <CODE>%type</CODE> declaration, if they have the same value type. Use -spaces to separate the symbol names. +Here <VAR>nonterminal</VAR> is the name of a nonterminal symbol, and +<VAR>type</VAR> is the name given in the <CODE>%union</CODE> to the alternative +that you want (see section <A HREF="bison.html#SEC62">The Collection of Value Types</A>). You +can give any number of nonterminal symbols in the same <CODE>%type</CODE> +declaration, if they have the same value type. Use spaces to separate +the symbol names. <P> @@ -3662,22 +4003,22 @@ -<H3><A NAME="SEC63" HREF="bison_toc.html#TOC63">Suppressing Conflict Warnings</A></H3> +<H3><A NAME="SEC64" HREF="bison_toc.html#TOC64">Suppressing Conflict Warnings</A></H3> <P> -<A NAME="IDX121"></A> -<A NAME="IDX122"></A> -<A NAME="IDX123"></A> -<A NAME="IDX124"></A> -<A NAME="IDX125"></A> +<A NAME="IDX134"></A> +<A NAME="IDX135"></A> +<A NAME="IDX136"></A> +<A NAME="IDX137"></A> +<A NAME="IDX138"></A> <P> Bison normally warns if there are any conflicts in the grammar -(see section <A HREF="bison.html#SEC79">Shift/Reduce Conflicts</A>), but most real grammars have harmless shift/reduce -conflicts which are resolved in a predictable way and would be difficult to -eliminate. It is desirable to suppress the warning about these conflicts -unless the number of conflicts changes. You can do this with the -<CODE>%expect</CODE> declaration. +(see section <A HREF="bison.html#SEC80">Shift/Reduce Conflicts</A>), but most real grammars +have harmless shift/reduce conflicts which are resolved in a predictable +way and would be difficult to eliminate. It is desirable to suppress +the warning about these conflicts unless the number of conflicts +changes. You can do this with the <CODE>%expect</CODE> declaration. <P> @@ -3690,10 +4031,11 @@ </PRE> <P> -Here <VAR>n</VAR> is a decimal integer. The declaration says there should be no -warning if there are <VAR>n</VAR> shift/reduce conflicts and no reduce/reduce -conflicts. The usual warning is given if there are either more or fewer -conflicts, or if there are any reduce/reduce conflicts. +Here <VAR>n</VAR> is a decimal integer. The declaration says there should be +no warning if there are <VAR>n</VAR> shift/reduce conflicts and no +reduce/reduce conflicts. An error, instead of the usual warning, is +given if there are either more or fewer conflicts, or if there are any +reduce/reduce conflicts. <P> @@ -3728,12 +4070,12 @@ -<H3><A NAME="SEC64" HREF="bison_toc.html#TOC64">The Start-Symbol</A></H3> +<H3><A NAME="SEC65" HREF="bison_toc.html#TOC65">The Start-Symbol</A></H3> <P> -<A NAME="IDX126"></A> -<A NAME="IDX127"></A> -<A NAME="IDX128"></A> -<A NAME="IDX129"></A> +<A NAME="IDX139"></A> +<A NAME="IDX140"></A> +<A NAME="IDX141"></A> +<A NAME="IDX142"></A> <P> @@ -3749,11 +4091,11 @@ -<H3><A NAME="SEC65" HREF="bison_toc.html#TOC65">A Pure (Reentrant) Parser</A></H3> +<H3><A NAME="SEC66" HREF="bison_toc.html#TOC66">A Pure (Reentrant) Parser</A></H3> <P> -<A NAME="IDX130"></A> -<A NAME="IDX131"></A> -<A NAME="IDX132"></A> +<A NAME="IDX143"></A> +<A NAME="IDX144"></A> +<A NAME="IDX145"></A> <P> @@ -3775,21 +4117,21 @@ <P> Alternatively, you can generate a pure, reentrant parser. The Bison -declaration <CODE>%pure_parser</CODE> says that you want the parser to be +declaration <CODE>%pure-parser</CODE> says that you want the parser to be reentrant. It looks like this: <PRE> -%pure_parser +%pure-parser </PRE> <P> The result is that the communication variables <CODE>yylval</CODE> and <CODE>yylloc</CODE> become local variables in <CODE>yyparse</CODE>, and a different calling convention is used for the lexical analyzer function -<CODE>yylex</CODE>. See section <A HREF="bison.html#SEC74">Calling Conventions for Pure Parsers</A>, for the details of this. The variable <CODE>yynerrs</CODE> also -becomes local in <CODE>yyparse</CODE> (see section <A HREF="bison.html#SEC75">The Error Reporting Function <CODE>yyerror</CODE></A>). The convention for calling +<CODE>yylex</CODE>. See section <A HREF="bison.html#SEC75">Calling Conventions for Pure Parsers</A>, for the details of this. The variable <CODE>yynerrs</CODE> also +becomes local in <CODE>yyparse</CODE> (see section <A HREF="bison.html#SEC76">The Error Reporting Function <CODE>yyerror</CODE></A>). The convention for calling <CODE>yyparse</CODE> itself is unchanged. @@ -3801,15 +4143,15 @@ -<H3><A NAME="SEC66" HREF="bison_toc.html#TOC66">Bison Declaration Summary</A></H3> +<H3><A NAME="SEC67" HREF="bison_toc.html#TOC67">Bison Declaration Summary</A></H3> <P> -<A NAME="IDX133"></A> -<A NAME="IDX134"></A> -<A NAME="IDX135"></A> +<A NAME="IDX146"></A> +<A NAME="IDX147"></A> +<A NAME="IDX148"></A> <P> -Here is a summary of all Bison declarations: +Here is a summary of the declarations used to define a grammar: <DL COMPACT> @@ -3817,62 +4159,93 @@ <DT><CODE>%union</CODE> <DD> Declare the collection of data types that semantic values may have -(see section <A HREF="bison.html#SEC61">The Collection of Value Types</A>). +(see section <A HREF="bison.html#SEC62">The Collection of Value Types</A>). <DT><CODE>%token</CODE> <DD> Declare a terminal symbol (token type name) with no precedence -or associativity specified (see section <A HREF="bison.html#SEC59">Token Type Names</A>). +or associativity specified (see section <A HREF="bison.html#SEC60">Token Type Names</A>). <DT><CODE>%right</CODE> <DD> Declare a terminal symbol (token type name) that is right-associative -(see section <A HREF="bison.html#SEC60">Operator Precedence</A>). +(see section <A HREF="bison.html#SEC61">Operator Precedence</A>). <DT><CODE>%left</CODE> <DD> Declare a terminal symbol (token type name) that is left-associative -(see section <A HREF="bison.html#SEC60">Operator Precedence</A>). +(see section <A HREF="bison.html#SEC61">Operator Precedence</A>). <DT><CODE>%nonassoc</CODE> <DD> Declare a terminal symbol (token type name) that is nonassociative (using it in a way that would be associative is a syntax error) -(see section <A HREF="bison.html#SEC60">Operator Precedence</A>). +(see section <A HREF="bison.html#SEC61">Operator Precedence</A>). <DT><CODE>%type</CODE> <DD> Declare the type of semantic values for a nonterminal symbol -(see section <A HREF="bison.html#SEC62">Nonterminal Symbols</A>). +(see section <A HREF="bison.html#SEC63">Nonterminal Symbols</A>). <DT><CODE>%start</CODE> <DD> -Specify the grammar's start symbol (see section <A HREF="bison.html#SEC64">The Start-Symbol</A>). +Specify the grammar's start symbol (see section <A HREF="bison.html#SEC65">The Start-Symbol</A>). <DT><CODE>%expect</CODE> <DD> Declare the expected number of shift-reduce conflicts -(see section <A HREF="bison.html#SEC63">Suppressing Conflict Warnings</A>). +(see section <A HREF="bison.html#SEC64">Suppressing Conflict Warnings</A>). +</DL> -<DT><CODE>%yacc</CODE> +<P> +In order to change the behavior of @command{bison}, use the following +directives: + + +<DL COMPACT> + +<DT><CODE>%debug</CODE> <DD> -<DT><CODE>%fixed_output_files</CODE> +In the parser file, define the macro <CODE>YYDEBUG</CODE> to 1 if it is not +already defined, so that the debugging facilities are compiled. +See section <A HREF="bison.html#SEC99">Tracing Your Parser</A>. + +<DT><CODE>%defines</CODE> <DD> -Pretend the option @option{--yacc} was given, i.e., imitate Yacc, -including its naming conventions. See section <A HREF="bison.html#SEC97">Bison Options</A>, for more. +Write an extra output file containing macro definitions for the token +type names defined in the grammar and the semantic value type +<CODE>YYSTYPE</CODE>, as well as a few <CODE>extern</CODE> variable declarations. + +If the parser output file is named <TT>`<VAR>name</VAR>.c'</TT> then this file +is named <TT>`<VAR>name</VAR>.h'</TT>. + +This output file is essential if you wish to put the definition of +<CODE>yylex</CODE> in a separate source file, because <CODE>yylex</CODE> needs to +be able to refer to token type codes and the variable +<CODE>yylval</CODE>. See section <A HREF="bison.html#SEC73">Semantic Values of Tokens</A>. + +<DT><CODE>%file-prefix="<VAR>prefix</VAR>"</CODE> +<DD> +Specify a prefix to use for all Bison output file names. The names are +chosen as if the input file were named <TT>`<VAR>prefix</VAR>.y'</TT>. <DT><CODE>%locations</CODE> <DD> -Generate the code processing the locations (see section <A HREF="bison.html#SEC76">Special Features for Use in Actions</A>). This mode is enabled as soon as +Generate the code processing the locations (see section <A HREF="bison.html#SEC77">Special Features for Use in Actions</A>). This mode is enabled as soon as the grammar uses the special <SAMP>`@<VAR>n</VAR>'</SAMP> tokens, but if your grammar does not use it, using <SAMP>`%locations'</SAMP> allows for more accurate parse error messages. -<DT><CODE>%pure_parser</CODE> +<DT><CODE>%name-prefix="<VAR>prefix</VAR>"</CODE> <DD> -Request a pure (reentrant) parser program (see section <A HREF="bison.html#SEC65">A Pure (Reentrant) Parser</A>). +Rename the external symbols used in the parser so that they start with +<VAR>prefix</VAR> instead of <SAMP>`yy'</SAMP>. The precise list of symbols renamed +is <CODE>yyparse</CODE>, <CODE>yylex</CODE>, <CODE>yyerror</CODE>, <CODE>yynerrs</CODE>, +<CODE>yylval</CODE>, <CODE>yychar</CODE>, <CODE>yydebug</CODE>, and possible +<CODE>yylloc</CODE>. For example, if you use <SAMP>`%name-prefix="c_"'</SAMP>, the +names become <CODE>c_parse</CODE>, <CODE>c_lex</CODE>, and so on. See section <A HREF="bison.html#SEC68">Multiple Parsers in the Same Program</A>. -<DT><CODE>%no_parser</CODE> +<DT><CODE>%no-parser</CODE> <DD> Do not include any C code in the parser file; generate tables only. The parser file contains just <CODE>#define</CODE> directives and static variable @@ -3882,7 +4255,7 @@ into a file named <TT>`<VAR>filename</VAR>.act'</TT>, in the form of a brace-surrounded body fit for a <CODE>switch</CODE> statement. -<DT><CODE>%no_lines</CODE> +<DT><CODE>%no-lines</CODE> <DD> Don't generate any <CODE>#line</CODE> preprocessor commands in the parser file. Ordinarily Bison writes these commands in the parser file so that @@ -3891,45 +4264,22 @@ associate errors with the parser file, treating it an independent source file in its own right. -<DT><CODE>%debug</CODE> +<DT><CODE>%output="<VAR>filename</VAR>"</CODE> <DD> -Output a definition of the macro <CODE>YYDEBUG</CODE> into the parser file, so -that the debugging facilities are compiled. See section <A HREF="bison.html#SEC95">Debugging Your Parser</A>. +Specify the <VAR>filename</VAR> for the parser file. -<DT><CODE>%defines</CODE> -<DD> -Write an extra output file containing macro definitions for the token -type names defined in the grammar and the semantic value type -<CODE>YYSTYPE</CODE>, as well as a few <CODE>extern</CODE> variable declarations. - -If the parser output file is named <TT>`<VAR>name</VAR>.c'</TT> then this file -is named <TT>`<VAR>name</VAR>.h'</TT>. -This output file is essential if you wish to put the definition of -<CODE>yylex</CODE> in a separate source file, because <CODE>yylex</CODE> needs to -be able to refer to token type codes and the variable -<CODE>yylval</CODE>. See section <A HREF="bison.html#SEC72">Semantic Values of Tokens</A>. -<DT><CODE>%verbose</CODE> +<DT><CODE>%pure-parser</CODE> <DD> -Write an extra output file containing verbose descriptions of the -parser states and what is done for each type of look-ahead token in -that state. - -This file also describes all the conflicts, both those resolved by -operator precedence and the unresolved ones. +Request a pure (reentrant) parser program (see section <A HREF="bison.html#SEC66">A Pure (Reentrant) Parser</A>). -The file's name is made by removing <SAMP>`.tab.c'</SAMP> or <SAMP>`.c'</SAMP> from -the parser output file name, and adding <SAMP>`.output'</SAMP> instead. -Therefore, if the input file is <TT>`foo.y'</TT>, then the parser file is -called <TT>`foo.tab.c'</TT> by default. As a consequence, the verbose -output file is called <TT>`foo.output'</TT>. -<DT><CODE>%token_table</CODE> +<DT><CODE>%token-table</CODE> <DD> Generate an array of token names in the parser file. The name of the array is <CODE>yytname</CODE>; <CODE>yytname[<VAR>i</VAR>]</CODE> is the name of the -token whose internal Bison token code number is <VAR>i</VAR>. The first three -elements of <CODE>yytname</CODE> are always <CODE>"$"</CODE>, <CODE>"error"</CODE>, and -<CODE>"$illegal"</CODE>; after these come the symbols defined in the grammar -file. +token whose internal Bison token code number is <VAR>i</VAR>. The first +three elements of <CODE>yytname</CODE> are always <CODE>"$end"</CODE>, +<CODE>"error"</CODE>, and <CODE>"$undefined"</CODE>; after these come the symbols +defined in the grammar file. For single-character literal tokens and literal string tokens, the name in the table includes the single-quote or double-quote characters: for @@ -3941,7 +4291,7 @@ contains <SAMP>`"*"*"'</SAMP>. (In C, that would be written as <CODE>"\"*\"*\""</CODE>). -When you specify <CODE>%token_table</CODE>, Bison also generates macro +When you specify <CODE>%token-table</CODE>, Bison also generates macro definitions for macros <CODE>YYNTOKENS</CODE>, <CODE>YYNNTS</CODE>, and <CODE>YYNRULES</CODE>, and <CODE>YYNSTATES</CODE>: @@ -3958,13 +4308,25 @@ The number of grammar rules, <DT><CODE>YYNSTATES</CODE> <DD> -The number of parser states (see section <A HREF="bison.html#SEC86">Parser States</A>). +The number of parser states (see section <A HREF="bison.html#SEC87">Parser States</A>). </DL> + +<DT><CODE>%verbose</CODE> +<DD> +Write an extra output file containing verbose descriptions of the +parser states and what is done for each type of look-ahead token in +that state. See section <A HREF="bison.html#SEC98">Understanding Your Parser</A>, for more +information. + +<DT><CODE>%yacc</CODE> +<DD> +Pretend the option @option{--yacc} was given, i.e., imitate Yacc, +including its naming conventions. See section <A HREF="bison.html#SEC101">Bison Options</A>, for more. </DL> -<H2><A NAME="SEC67" HREF="bison_toc.html#TOC67">Multiple Parsers in the Same Program</A></H2> +<H2><A NAME="SEC68" HREF="bison_toc.html#TOC68">Multiple Parsers in the Same Program</A></H2> <P> Most programs that use Bison parse only one language and therefore contain @@ -3975,10 +4337,10 @@ <P> The easy way to do this is to use the option <SAMP>`-p <VAR>prefix</VAR>'</SAMP> -(see section <A HREF="bison.html#SEC96">Invoking Bison</A>). This renames the interface functions and -variables of the Bison parser to start with <VAR>prefix</VAR> instead of -<SAMP>`yy'</SAMP>. You can use this to give each parser distinct names that do -not conflict. +(see section <A HREF="bison.html#SEC100">Invoking Bison</A>). This renames the interface +functions and variables of the Bison parser to start with <VAR>prefix</VAR> +instead of <SAMP>`yy'</SAMP>. You can use this to give each parser distinct +names that do not conflict. <P> @@ -3993,7 +4355,7 @@ renamed.</STRONG> These others are not global; there is no conflict if the same name is used in different parsers. For example, <CODE>YYSTYPE</CODE> is not renamed, but defining this in different ways in different parsers causes -no trouble (see section <A HREF="bison.html#SEC49">Data Types of Semantic Values</A>). +no trouble (see section <A HREF="bison.html#SEC50">Data Types of Semantic Values</A>). <P> @@ -4005,10 +4367,10 @@ -<H1><A NAME="SEC68" HREF="bison_toc.html#TOC68">Parser C-Language Interface</A></H1> +<H1><A NAME="SEC69" HREF="bison_toc.html#TOC69">Parser C-Language Interface</A></H1> <P> -<A NAME="IDX136"></A> -<A NAME="IDX137"></A> +<A NAME="IDX149"></A> +<A NAME="IDX150"></A> <P> @@ -4020,15 +4382,15 @@ <P> Keep in mind that the parser uses many C identifiers starting with <SAMP>`yy'</SAMP> and <SAMP>`YY'</SAMP> for internal purposes. If you use such an -identifier (aside from those in this manual) in an action or in additional -C code in the grammar file, you are likely to run into trouble. +identifier (aside from those in this manual) in an action or in epilogue +in the grammar file, you are likely to run into trouble. -<H2><A NAME="SEC69" HREF="bison_toc.html#TOC69">The Parser Function <CODE>yyparse</CODE></A></H2> +<H2><A NAME="SEC70" HREF="bison_toc.html#TOC70">The Parser Function <CODE>yyparse</CODE></A></H2> <P> -<A NAME="IDX138"></A> +<A NAME="IDX151"></A> <P> @@ -4057,21 +4419,21 @@ <DT><CODE>YYACCEPT</CODE> <DD> -<A NAME="IDX139"></A> +<A NAME="IDX152"></A> Return immediately with value 0 (to report success). <DT><CODE>YYABORT</CODE> <DD> -<A NAME="IDX140"></A> +<A NAME="IDX153"></A> Return immediately with value 1 (to report failure). </DL> -<H2><A NAME="SEC70" HREF="bison_toc.html#TOC70">The Lexical Analyzer Function <CODE>yylex</CODE></A></H2> +<H2><A NAME="SEC71" HREF="bison_toc.html#TOC71">The Lexical Analyzer Function <CODE>yylex</CODE></A></H2> <P> -<A NAME="IDX141"></A> -<A NAME="IDX142"></A> +<A NAME="IDX154"></A> +<A NAME="IDX155"></A> <P> @@ -4088,29 +4450,32 @@ To do this, use the <SAMP>`-d'</SAMP> option when you run Bison, so that it will write these macro definitions into a separate header file <TT>`<VAR>name</VAR>.tab.h'</TT> which you can include in the other source files -that need it. See section <A HREF="bison.html#SEC96">Invoking Bison</A>. +that need it. See section <A HREF="bison.html#SEC100">Invoking Bison</A>. -<H3><A NAME="SEC71" HREF="bison_toc.html#TOC71">Calling Convention for <CODE>yylex</CODE></A></H3> + +<H3><A NAME="SEC72" HREF="bison_toc.html#TOC72">Calling Convention for <CODE>yylex</CODE></A></H3> <P> -The value that <CODE>yylex</CODE> returns must be the numeric code for the type -of token it has just found, or 0 for end-of-input. +The value that <CODE>yylex</CODE> returns must be the positive numeric code +for the type of token it has just found; a zero or negative value +signifies end-of-input. <P> When a token is referred to in the grammar rules by a name, that name in the parser file becomes a C macro whose definition is the proper numeric code for that token type. So <CODE>yylex</CODE> can use the name -to indicate that type. See section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>. +to indicate that type. See section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>. <P> When a token is referred to in the grammar rules by a character literal, the numeric code for that character is also the code for the token type. -So <CODE>yylex</CODE> can simply return that character code. The null character -must not be used this way, because its code is zero and that is what +So <CODE>yylex</CODE> can simply return that character code, possibly converted +to <CODE>unsigned char</CODE> to avoid sign-extension. The null character +must not be used this way, because its code is zero and that signifies end-of-input. @@ -4124,13 +4489,13 @@ yylex (void) { ... - if (c == EOF) /* Detect end of file. */ + if (c == EOF) /* Detect end-of-input. */ return 0; ... if (c == '+' || c == '-') - return c; /* Assume token type for `+' is '+'. */ + return c; /* Assume token type for `+' is '+'. */ ... - return INT; /* Return the type of the token. */ + return INT; /* Return the type of the token. */ ... } </PRE> @@ -4172,8 +4537,8 @@ { if (yytname[i] != 0 && yytname[i][0] == '"' - && strncmp (yytname[i] + 1, token_buffer, - strlen (token_buffer)) + && ! strncmp (yytname[i] + 1, token_buffer, + strlen (token_buffer)) && yytname[i][strlen (token_buffer) + 1] == '"' && yytname[i][strlen (token_buffer) + 2] == 0) break; @@ -4181,15 +4546,15 @@ </PRE> The <CODE>yytname</CODE> table is generated only if you use the -<CODE>%token_table</CODE> declaration. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +<CODE>%token-table</CODE> declaration. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. </UL> -<H3><A NAME="SEC72" HREF="bison_toc.html#TOC72">Semantic Values of Tokens</A></H3> +<H3><A NAME="SEC73" HREF="bison_toc.html#TOC73">Semantic Values of Tokens</A></H3> <P> -<A NAME="IDX143"></A> +<A NAME="IDX156"></A> In an ordinary (non-reentrant) parser, the semantic value of the token must be stored into the global variable <CODE>yylval</CODE>. When you are using just one data type for semantic values, <CODE>yylval</CODE> has that type. @@ -4200,16 +4565,16 @@ <PRE> ... - yylval = value; /* Put value onto Bison stack. */ - return INT; /* Return the type of the token. */ + yylval = value; /* Put value onto Bison stack. */ + return INT; /* Return the type of the token. */ ... </PRE> <P> When you are using multiple data types, <CODE>yylval</CODE>'s type is a union -made from the <CODE>%union</CODE> declaration (see section <A HREF="bison.html#SEC61">The Collection of Value Types</A>). So when -you store a token's value, you must use the proper member of the union. -If the <CODE>%union</CODE> declaration looks like this: +made from the <CODE>%union</CODE> declaration (see section <A HREF="bison.html#SEC62">The Collection of Value Types</A>). So when you store a token's value, you +must use the proper member of the union. If the <CODE>%union</CODE> +declaration looks like this: @@ -4228,18 +4593,18 @@ <PRE> ... - yylval.intval = value; /* Put value onto Bison stack. */ - return INT; /* Return the type of the token. */ + yylval.intval = value; /* Put value onto Bison stack. */ + return INT; /* Return the type of the token. */ ... </PRE> -<H3><A NAME="SEC73" HREF="bison_toc.html#TOC73">Textual Positions of Tokens</A></H3> +<H3><A NAME="SEC74" HREF="bison_toc.html#TOC74">Textual Positions of Tokens</A></H3> <P> -<A NAME="IDX144"></A> -If you are using the <SAMP>`@<VAR>n</VAR>'</SAMP>-feature (see section <A HREF="bison.html#SEC54">Tracking Locations</A>) in actions to keep track of the +<A NAME="IDX157"></A> +If you are using the <SAMP>`@<VAR>n</VAR>'</SAMP>-feature (see section <A HREF="bison.html#SEC55">Tracking Locations</A>) in actions to keep track of the textual locations of tokens and groupings, then you must provide this information in <CODE>yylex</CODE>. The function <CODE>yyparse</CODE> expects to find the textual location of a token just parsed in the global variable @@ -4256,18 +4621,18 @@ <P> -<A NAME="IDX145"></A> +<A NAME="IDX158"></A> The data type of <CODE>yylloc</CODE> has the name <CODE>YYLTYPE</CODE>. -<H3><A NAME="SEC74" HREF="bison_toc.html#TOC74">Calling Conventions for Pure Parsers</A></H3> +<H3><A NAME="SEC75" HREF="bison_toc.html#TOC75">Calling Conventions for Pure Parsers</A></H3> <P> -When you use the Bison declaration <CODE>%pure_parser</CODE> to request a +When you use the Bison declaration <CODE>%pure-parser</CODE> to request a pure, reentrant parser, the global communication variables <CODE>yylval</CODE> -and <CODE>yylloc</CODE> cannot be used. (See section <A HREF="bison.html#SEC65">A Pure (Reentrant) Parser</A>.) In such parsers the two global variables are replaced by +and <CODE>yylloc</CODE> cannot be used. (See section <A HREF="bison.html#SEC66">A Pure (Reentrant) Parser</A>.) In such parsers the two global variables are replaced by pointers passed as arguments to <CODE>yylex</CODE>. You must declare them as shown here, and pass the information back by storing it through those pointers. @@ -4293,7 +4658,7 @@ <P> -<A NAME="IDX146"></A> +<A NAME="IDX159"></A> If you use a reentrant parser, you can optionally pass additional parameter information to it in a reentrant way. To do so, define the macro <CODE>YYPARSE_PARAM</CODE> as a variable name. This modifies the @@ -4353,7 +4718,7 @@ </PRE> <P> -<A NAME="IDX147"></A> +<A NAME="IDX160"></A> If you wish to pass the additional parameter data to <CODE>yylex</CODE>, define the macro <CODE>YYLEX_PARAM</CODE> just like <CODE>YYPARSE_PARAM</CODE>, as shown here: @@ -4383,26 +4748,26 @@ <P> -You can use <SAMP>`%pure_parser'</SAMP> to request a reentrant parser without +You can use <SAMP>`%pure-parser'</SAMP> to request a reentrant parser without also using <CODE>YYPARSE_PARAM</CODE>. Then you should call <CODE>yyparse</CODE> with no arguments, as usual. -<H2><A NAME="SEC75" HREF="bison_toc.html#TOC75">The Error Reporting Function <CODE>yyerror</CODE></A></H2> +<H2><A NAME="SEC76" HREF="bison_toc.html#TOC76">The Error Reporting Function <CODE>yyerror</CODE></A></H2> <P> -<A NAME="IDX148"></A> -<A NAME="IDX149"></A> -<A NAME="IDX150"></A> -<A NAME="IDX151"></A> +<A NAME="IDX161"></A> +<A NAME="IDX162"></A> +<A NAME="IDX163"></A> +<A NAME="IDX164"></A> <P> The Bison parser detects a <EM>parse error</EM> or <EM>syntax error</EM> whenever it reads a token which cannot satisfy any syntax rule. An action in the grammar can also explicitly proclaim an error, using the -macro <CODE>YYERROR</CODE> (see section <A HREF="bison.html#SEC76">Special Features for Use in Actions</A>). +macro <CODE>YYERROR</CODE> (see section <A HREF="bison.html#SEC77">Special Features for Use in Actions</A>). <P> @@ -4414,9 +4779,9 @@ <P> -<A NAME="IDX152"></A> +<A NAME="IDX165"></A> If you define the macro <CODE>YYERROR_VERBOSE</CODE> in the Bison declarations -section (see section <A HREF="bison.html#SEC42">The Bison Declarations Section</A>), +section (see section <A HREF="bison.html#SEC43">The Bison Declarations Section</A>), then Bison provides a more verbose and specific error message string instead of just plain <CODE>"parse error"</CODE>. It doesn't matter what definition you use for <CODE>YYERROR_VERBOSE</CODE>, just whether you define @@ -4449,24 +4814,24 @@ <P> After <CODE>yyerror</CODE> returns to <CODE>yyparse</CODE>, the latter will attempt error recovery if you have written suitable error recovery grammar rules -(see section <A HREF="bison.html#SEC90">Error Recovery</A>). If recovery is impossible, <CODE>yyparse</CODE> will +(see section <A HREF="bison.html#SEC92">Error Recovery</A>). If recovery is impossible, <CODE>yyparse</CODE> will immediately return 1. <P> -<A NAME="IDX153"></A> +<A NAME="IDX166"></A> The variable <CODE>yynerrs</CODE> contains the number of syntax errors encountered so far. Normally this variable is global; but if you -request a pure parser (see section <A HREF="bison.html#SEC65">A Pure (Reentrant) Parser</A>) then it is a local variable -which only the actions can access. +request a pure parser (see section <A HREF="bison.html#SEC66">A Pure (Reentrant) Parser</A>) +then it is a local variable which only the actions can access. -<H2><A NAME="SEC76" HREF="bison_toc.html#TOC76">Special Features for Use in Actions</A></H2> +<H2><A NAME="SEC77" HREF="bison_toc.html#TOC77">Special Features for Use in Actions</A></H2> <P> -<A NAME="IDX154"></A> -<A NAME="IDX155"></A> +<A NAME="IDX167"></A> +<A NAME="IDX168"></A> <P> @@ -4479,38 +4844,40 @@ <DT><SAMP>`$$'</SAMP> <DD> Acts like a variable that contains the semantic value for the -grouping made by the current rule. See section <A HREF="bison.html#SEC51">Actions</A>. +grouping made by the current rule. See section <A HREF="bison.html#SEC52">Actions</A>. <DT><SAMP>`$<VAR>n</VAR>'</SAMP> <DD> Acts like a variable that contains the semantic value for the -<VAR>n</VAR>th component of the current rule. See section <A HREF="bison.html#SEC51">Actions</A>. +<VAR>n</VAR>th component of the current rule. See section <A HREF="bison.html#SEC52">Actions</A>. <DT><SAMP>`$<<VAR>typealt</VAR>>$'</SAMP> <DD> Like <CODE>$$</CODE> but specifies alternative <VAR>typealt</VAR> in the union -specified by the <CODE>%union</CODE> declaration. See section <A HREF="bison.html#SEC52">Data Types of Values in Actions</A>. +specified by the <CODE>%union</CODE> declaration. See section <A HREF="bison.html#SEC53">Data Types of Values in Actions</A>. <DT><SAMP>`$<<VAR>typealt</VAR>><VAR>n</VAR>'</SAMP> <DD> Like <CODE>$<VAR>n</VAR></CODE> but specifies alternative <VAR>typealt</VAR> in the union specified by the <CODE>%union</CODE> declaration. -See section <A HREF="bison.html#SEC52">Data Types of Values in Actions</A>. +See section <A HREF="bison.html#SEC53">Data Types of Values in Actions</A>. + <DT><SAMP>`YYABORT;'</SAMP> <DD> Return immediately from <CODE>yyparse</CODE>, indicating failure. -See section <A HREF="bison.html#SEC69">The Parser Function <CODE>yyparse</CODE></A>. +See section <A HREF="bison.html#SEC70">The Parser Function <CODE>yyparse</CODE></A>. <DT><SAMP>`YYACCEPT;'</SAMP> <DD> Return immediately from <CODE>yyparse</CODE>, indicating success. -See section <A HREF="bison.html#SEC69">The Parser Function <CODE>yyparse</CODE></A>. +See section <A HREF="bison.html#SEC70">The Parser Function <CODE>yyparse</CODE></A>. <DT><SAMP>`YYBACKUP (<VAR>token</VAR>, <VAR>value</VAR>);'</SAMP> <DD> -<A NAME="IDX156"></A> +<A NAME="IDX169"></A> Unshift a token. This macro is allowed only for rules that reduce a single value, and only when there is no look-ahead token. +It is also disallowed in GLR parsers. It installs a look-ahead token with token type <VAR>token</VAR> and semantic value <VAR>value</VAR>; then it discards the value that was going to be reduced by this rule. @@ -4524,66 +4891,66 @@ <DT><SAMP>`YYEMPTY'</SAMP> <DD> -<A NAME="IDX157"></A> +<A NAME="IDX170"></A> Value stored in <CODE>yychar</CODE> when there is no look-ahead token. <DT><SAMP>`YYERROR;'</SAMP> <DD> -<A NAME="IDX158"></A> +<A NAME="IDX171"></A> Cause an immediate syntax error. This statement initiates error recovery just as if the parser itself had detected an error; however, it does not call <CODE>yyerror</CODE>, and does not print any message. If you want to print an error message, call <CODE>yyerror</CODE> explicitly before -the <SAMP>`YYERROR;'</SAMP> statement. See section <A HREF="bison.html#SEC90">Error Recovery</A>. +the <SAMP>`YYERROR;'</SAMP> statement. See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><SAMP>`YYRECOVERING'</SAMP> <DD> This macro stands for an expression that has the value 1 when the parser is recovering from a syntax error, and 0 the rest of the time. -See section <A HREF="bison.html#SEC90">Error Recovery</A>. +See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><SAMP>`yychar'</SAMP> <DD> Variable containing the current look-ahead token. (In a pure parser, this is actually a local variable within <CODE>yyparse</CODE>.) When there is no look-ahead token, the value <CODE>YYEMPTY</CODE> is stored in the variable. -See section <A HREF="bison.html#SEC78">Look-Ahead Tokens</A>. +See section <A HREF="bison.html#SEC79">Look-Ahead Tokens</A>. <DT><SAMP>`yyclearin;'</SAMP> <DD> Discard the current look-ahead token. This is useful primarily in -error rules. See section <A HREF="bison.html#SEC90">Error Recovery</A>. +error rules. See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><SAMP>`yyerrok;'</SAMP> <DD> Resume generating error messages immediately for subsequent syntax errors. This is useful primarily in error rules. -See section <A HREF="bison.html#SEC90">Error Recovery</A>. +See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><SAMP>`@$'</SAMP> <DD> -<A NAME="IDX159"></A> +<A NAME="IDX172"></A> Acts like a structure variable containing information on the textual position -of the grouping made by the current rule. See section <A HREF="bison.html#SEC54">Tracking Locations</A>. +of the grouping made by the current rule. See section <A HREF="bison.html#SEC55">Tracking Locations</A>. <DT><SAMP>`@<VAR>n</VAR>'</SAMP> <DD> -<A NAME="IDX160"></A> +<A NAME="IDX173"></A> Acts like a structure variable containing information on the textual position -of the <VAR>n</VAR>th component of the current rule. See section <A HREF="bison.html#SEC54">Tracking Locations</A>. +of the <VAR>n</VAR>th component of the current rule. See section <A HREF="bison.html#SEC55">Tracking Locations</A>. </DL> -<H1><A NAME="SEC77" HREF="bison_toc.html#TOC77">The Bison Parser Algorithm</A></H1> +<H1><A NAME="SEC78" HREF="bison_toc.html#TOC78">The Bison Parser Algorithm</A></H1> <P> -<A NAME="IDX161"></A> -<A NAME="IDX162"></A> -<A NAME="IDX163"></A> -<A NAME="IDX164"></A> -<A NAME="IDX165"></A> -<A NAME="IDX166"></A> +<A NAME="IDX174"></A> +<A NAME="IDX175"></A> +<A NAME="IDX176"></A> +<A NAME="IDX177"></A> +<A NAME="IDX178"></A> +<A NAME="IDX179"></A> <P> @@ -4653,9 +5020,9 @@ -<H2><A NAME="SEC78" HREF="bison_toc.html#TOC78">Look-Ahead Tokens</A></H2> +<H2><A NAME="SEC79" HREF="bison_toc.html#TOC79">Look-Ahead Tokens</A></H2> <P> -<A NAME="IDX167"></A> +<A NAME="IDX180"></A> <P> @@ -4713,19 +5080,19 @@ <P> -<A NAME="IDX168"></A> +<A NAME="IDX181"></A> The current look-ahead token is stored in the variable <CODE>yychar</CODE>. -See section <A HREF="bison.html#SEC76">Special Features for Use in Actions</A>. +See section <A HREF="bison.html#SEC77">Special Features for Use in Actions</A>. -<H2><A NAME="SEC79" HREF="bison_toc.html#TOC79">Shift/Reduce Conflicts</A></H2> +<H2><A NAME="SEC80" HREF="bison_toc.html#TOC80">Shift/Reduce Conflicts</A></H2> <P> -<A NAME="IDX169"></A> -<A NAME="IDX170"></A> -<A NAME="IDX171"></A> -<A NAME="IDX172"></A> +<A NAME="IDX182"></A> +<A NAME="IDX183"></A> +<A NAME="IDX184"></A> +<A NAME="IDX185"></A> <P> @@ -4803,7 +5170,7 @@ To avoid warnings from Bison about predictable, legitimate shift/reduce conflicts, use the <CODE>%expect <VAR>n</VAR></CODE> declaration. There will be no warning as long as the number of shift/reduce conflicts is exactly <VAR>n</VAR>. -See section <A HREF="bison.html#SEC63">Suppressing Conflict Warnings</A>. +See section <A HREF="bison.html#SEC64">Suppressing Conflict Warnings</A>. <P> @@ -4832,10 +5199,10 @@ -<H2><A NAME="SEC80" HREF="bison_toc.html#TOC80">Operator Precedence</A></H2> +<H2><A NAME="SEC81" HREF="bison_toc.html#TOC81">Operator Precedence</A></H2> <P> -<A NAME="IDX173"></A> -<A NAME="IDX174"></A> +<A NAME="IDX186"></A> +<A NAME="IDX187"></A> <P> @@ -4847,7 +5214,7 @@ -<H3><A NAME="SEC81" HREF="bison_toc.html#TOC81">When Precedence is Needed</A></H3> +<H3><A NAME="SEC82" HREF="bison_toc.html#TOC82">When Precedence is Needed</A></H3> <P> Consider the following ambiguous grammar fragment (ambiguous because the @@ -4888,7 +5255,7 @@ <P> -<A NAME="IDX175"></A> +<A NAME="IDX188"></A> What about input such as <SAMP>`1 - 2 - 5'</SAMP>; should this be <SAMP>`(1 - 2) - 5'</SAMP> or should it be <SAMP>`1 - (2 - 5)'</SAMP>? For most operators we prefer the former, which is called <EM>left association</EM>. @@ -4901,11 +5268,11 @@ -<H3><A NAME="SEC82" HREF="bison_toc.html#TOC82">Specifying Operator Precedence</A></H3> +<H3><A NAME="SEC83" HREF="bison_toc.html#TOC83">Specifying Operator Precedence</A></H3> <P> -<A NAME="IDX176"></A> -<A NAME="IDX177"></A> -<A NAME="IDX178"></A> +<A NAME="IDX189"></A> +<A NAME="IDX190"></A> +<A NAME="IDX191"></A> <P> @@ -4929,7 +5296,7 @@ -<H3><A NAME="SEC83" HREF="bison_toc.html#TOC83">Precedence Examples</A></H3> +<H3><A NAME="SEC84" HREF="bison_toc.html#TOC84">Precedence Examples</A></H3> <P> In our example, we would want the following declarations: @@ -4963,25 +5330,25 @@ -<H3><A NAME="SEC84" HREF="bison_toc.html#TOC84">How Precedence Works</A></H3> +<H3><A NAME="SEC85" HREF="bison_toc.html#TOC85">How Precedence Works</A></H3> <P> The first effect of the precedence declarations is to assign precedence levels to the terminal symbols declared. The second effect is to assign -precedence levels to certain rules: each rule gets its precedence from the -last terminal symbol mentioned in the components. (You can also specify -explicitly the precedence of a rule. See section <A HREF="bison.html#SEC85">Context-Dependent Precedence</A>.) +precedence levels to certain rules: each rule gets its precedence from +the last terminal symbol mentioned in the components. (You can also +specify explicitly the precedence of a rule. See section <A HREF="bison.html#SEC86">Context-Dependent Precedence</A>.) <P> -Finally, the resolution of conflicts works by comparing the -precedence of the rule being considered with that of the -look-ahead token. If the token's precedence is higher, the -choice is to shift. If the rule's precedence is higher, the -choice is to reduce. If they have equal precedence, the choice -is made based on the associativity of that precedence level. The -verbose output file made by <SAMP>`-v'</SAMP> (see section <A HREF="bison.html#SEC96">Invoking Bison</A>) says -how each conflict was resolved. +Finally, the resolution of conflicts works by comparing the precedence +of the rule being considered with that of the look-ahead token. If the +token's precedence is higher, the choice is to shift. If the rule's +precedence is higher, the choice is to reduce. If they have equal +precedence, the choice is made based on the associativity of that +precedence level. The verbose output file made by <SAMP>`-v'</SAMP> +(see section <A HREF="bison.html#SEC100">Invoking Bison</A>) says how each conflict was +resolved. <P> @@ -4991,13 +5358,13 @@ -<H2><A NAME="SEC85" HREF="bison_toc.html#TOC85">Context-Dependent Precedence</A></H2> +<H2><A NAME="SEC86" HREF="bison_toc.html#TOC86">Context-Dependent Precedence</A></H2> <P> -<A NAME="IDX179"></A> -<A NAME="IDX180"></A> -<A NAME="IDX181"></A> -<A NAME="IDX182"></A> -<A NAME="IDX183"></A> +<A NAME="IDX192"></A> +<A NAME="IDX193"></A> +<A NAME="IDX194"></A> +<A NAME="IDX195"></A> +<A NAME="IDX196"></A> <P> @@ -5014,6 +5381,7 @@ precedence, you need to use an additional mechanism: the <CODE>%prec</CODE> modifier for rules. + <P> The <CODE>%prec</CODE> modifier declares the precedence of a particular rule by specifying a terminal symbol whose precedence should be used for that rule. @@ -5031,7 +5399,7 @@ assign the rule the precedence of <VAR>terminal-symbol</VAR>, overriding the precedence that would be deduced for it in the ordinary way. The altered rule precedence then affects how conflicts involving that rule -are resolved (see section <A HREF="bison.html#SEC80">Operator Precedence</A>). +are resolved (see section <A HREF="bison.html#SEC81">Operator Precedence</A>). <P> @@ -5063,11 +5431,11 @@ -<H2><A NAME="SEC86" HREF="bison_toc.html#TOC86">Parser States</A></H2> +<H2><A NAME="SEC87" HREF="bison_toc.html#TOC87">Parser States</A></H2> <P> -<A NAME="IDX184"></A> -<A NAME="IDX185"></A> -<A NAME="IDX186"></A> +<A NAME="IDX197"></A> +<A NAME="IDX198"></A> +<A NAME="IDX199"></A> <P> @@ -5093,15 +5461,15 @@ <P> There is one other alternative: the table can say that the look-ahead token is erroneous in the current state. This causes error processing to begin -(see section <A HREF="bison.html#SEC90">Error Recovery</A>). +(see section <A HREF="bison.html#SEC92">Error Recovery</A>). -<H2><A NAME="SEC87" HREF="bison_toc.html#TOC87">Reduce/Reduce Conflicts</A></H2> +<H2><A NAME="SEC88" HREF="bison_toc.html#TOC88">Reduce/Reduce Conflicts</A></H2> <P> -<A NAME="IDX187"></A> -<A NAME="IDX188"></A> +<A NAME="IDX200"></A> +<A NAME="IDX201"></A> <P> @@ -5241,7 +5609,7 @@ -<H2><A NAME="SEC88" HREF="bison_toc.html#TOC88">Mysterious Reduce/Reduce Conflicts</A></H2> +<H2><A NAME="SEC89" HREF="bison_toc.html#TOC89">Mysterious Reduce/Reduce Conflicts</A></H2> <P> Sometimes reduce/reduce conflicts can occur that don't look warranted. @@ -5281,8 +5649,8 @@ <P> -<A NAME="IDX189"></A> -<A NAME="IDX190"></A> +<A NAME="IDX202"></A> +<A NAME="IDX203"></A> However, Bison, like most parser generators, cannot actually handle all LR(1) grammars. In this grammar, two contexts, that after an <CODE>ID</CODE> at the beginning of a <CODE>param_spec</CODE> and likewise at the beginning of @@ -5357,11 +5725,100 @@ -<H2><A NAME="SEC89" HREF="bison_toc.html#TOC89">Stack Overflow, and How to Avoid It</A></H2> +<H2><A NAME="SEC90" HREF="bison_toc.html#TOC90">Generalized LR (GLR) Parsing</A></H2> <P> -<A NAME="IDX191"></A> -<A NAME="IDX192"></A> -<A NAME="IDX193"></A> +<A NAME="IDX204"></A> +<A NAME="IDX205"></A> +<A NAME="IDX206"></A> +<A NAME="IDX207"></A> + + +<P> +Bison produces <EM>deterministic</EM> parsers that choose uniquely +when to reduce and which reduction to apply +based on a summary of the preceding input and on one extra token of lookahead. +As a result, normal Bison handles a proper subset of the family of +context-free languages. +Ambiguous grammars, since they have strings with more than one possible +sequence of reductions cannot have deterministic parsers in this sense. +The same is true of languages that require more than one symbol of +lookahead, since the parser lacks the information necessary to make a +decision at the point it must be made in a shift-reduce parser. +Finally, as previously mentioned (see section <A HREF="bison.html#SEC89">Mysterious Reduce/Reduce Conflicts</A>), +there are languages where Bison's particular choice of how to +summarize the input seen so far loses necessary information. + + +<P> +When you use the <SAMP>`%glr-parser'</SAMP> declaration in your grammar file, +Bison generates a parser that uses a different algorithm, called +Generalized LR (or GLR). A Bison GLR parser uses the same basic +algorithm for parsing as an ordinary Bison parser, but behaves +differently in cases where there is a shift-reduce conflict that has not +been resolved by precedence rules (see section <A HREF="bison.html#SEC81">Operator Precedence</A>) or a +reduce-reduce conflict. When a GLR parser encounters such a situation, it +effectively <EM>splits</EM> into a several parsers, one for each possible +shift or reduction. These parsers then proceed as usual, consuming +tokens in lock-step. Some of the stacks may encounter other conflicts +and split further, with the result that instead of a sequence of states, +a Bison GLR parsing stack is what is in effect a tree of states. + + +<P> +In effect, each stack represents a guess as to what the proper parse +is. Additional input may indicate that a guess was wrong, in which case +the appropriate stack silently disappears. Otherwise, the semantics +actions generated in each stack are saved, rather than being executed +immediately. When a stack disappears, its saved semantic actions never +get executed. When a reduction causes two stacks to become equivalent, +their sets of semantic actions are both saved with the state that +results from the reduction. We say that two stacks are equivalent +when they both represent the same sequence of states, +and each pair of corresponding states represents a +grammar symbol that produces the same segment of the input token +stream. + + +<P> +Whenever the parser makes a transition from having multiple +states to having one, it reverts to the normal LALR(1) parsing +algorithm, after resolving and executing the saved-up actions. +At this transition, some of the states on the stack will have semantic +values that are sets (actually multisets) of possible actions. The +parser tries to pick one of the actions by first finding one whose rule +has the highest dynamic precedence, as set by the <SAMP>`%dprec'</SAMP> +declaration. Otherwise, if the alternative actions are not ordered by +precedence, but there the same merging function is declared for both +rules by the <SAMP>`%merge'</SAMP> declaration, +Bison resolves and evaluates both and then calls the merge function on +the result. Otherwise, it reports an ambiguity. + + +<P> +It is possible to use a data structure for the GLR parsing tree that +permits the processing of any LALR(1) grammar in linear time (in the +size of the input), any unambiguous (not necessarily LALR(1)) grammar in +quadratic worst-case time, and any general (possibly ambiguous) +context-free grammar in cubic worst-case time. However, Bison currently +uses a simpler data structure that requires time proportional to the +length of the input times the maximum number of stacks required for any +prefix of the input. Thus, really ambiguous or non-deterministic +grammars can require exponential time and space to process. Such badly +behaving examples, however, are not generally of practical interest. +Usually, non-determinism in a grammar is local--the parser is "in +doubt" only for a few tokens at a time. Therefore, the current data +structure should generally be adequate. On LALR(1) portions of a +grammar, in particular, it is only slightly slower than with the default +Bison parser. + + + + +<H2><A NAME="SEC91" HREF="bison_toc.html#TOC91">Stack Overflow, and How to Avoid It</A></H2> +<P> +<A NAME="IDX208"></A> +<A NAME="IDX209"></A> +<A NAME="IDX210"></A> <P> @@ -5372,7 +5829,13 @@ <P> -<A NAME="IDX194"></A> +Becaue Bison parsers have growing stacks, hitting the upper limit +usually results from using a right recursion instead of a left +recursion, See section <A HREF="bison.html#SEC48">Recursive Rules</A>. + + +<P> +<A NAME="IDX211"></A> By defining the macro <CODE>YYMAXDEPTH</CODE>, you can control how deep the parser stack can become before a stack overflow occurs. Define the macro with a value that is an integer. This value is the maximum number @@ -5390,24 +5853,32 @@ <P> -<A NAME="IDX195"></A> +<A NAME="IDX212"></A> The default value of <CODE>YYMAXDEPTH</CODE>, if you do not define it, is 10000. <P> -<A NAME="IDX196"></A> +<A NAME="IDX213"></A> You can control how much stack is allocated initially by defining the macro <CODE>YYINITDEPTH</CODE>. This value too must be a compile-time constant integer. The default is 200. +<P> +Because of semantical differences between C and C++, the LALR(1) parsers +in C produced by Bison by compiled as C++ cannot grow. In this precise +case (compiling a C parser as C++) you are suggested to grow +<CODE>YYINITDEPTH</CODE>. In the near future, a C++ output output will be +provided which addresses this issue. + -<H1><A NAME="SEC90" HREF="bison_toc.html#TOC90">Error Recovery</A></H1> + +<H1><A NAME="SEC92" HREF="bison_toc.html#TOC92">Error Recovery</A></H1> <P> -<A NAME="IDX197"></A> -<A NAME="IDX198"></A> +<A NAME="IDX214"></A> +<A NAME="IDX215"></A> <P> @@ -5428,7 +5899,7 @@ <P> -<A NAME="IDX199"></A> +<A NAME="IDX216"></A> You can define how to recover from a syntax error by writing rules to recognize the special token <CODE>error</CODE>. This is a terminal symbol that is always defined (you need not declare it) and reserved for error @@ -5485,7 +5956,7 @@ <PRE> -stmnt: error ';' /* on error, skip until ';' is read */ +stmnt: error ';' /* On error, skip until ';' is read. */ </PRE> <P> @@ -5527,7 +5998,7 @@ <P> -<A NAME="IDX200"></A> +<A NAME="IDX217"></A> You can make error messages resume immediately by using the macro <CODE>yyerrok</CODE> in an action. If you do this in the error rule's action, no error messages will be suppressed. This macro requires no arguments; @@ -5535,7 +6006,7 @@ <P> -<A NAME="IDX201"></A> +<A NAME="IDX218"></A> The previous look-ahead token is reanalyzed immediately after an error. If this is unacceptable, then the macro <CODE>yyclearin</CODE> may be used to clear this token. Write the statement <SAMP>`yyclearin;'</SAMP> in the error rule's @@ -5551,7 +6022,7 @@ <P> -<A NAME="IDX202"></A> +<A NAME="IDX219"></A> The macro <CODE>YYRECOVERING</CODE> stands for an expression that has the value 1 when the parser is recovering from a syntax error, and 0 the rest of the time. A value of 1 indicates that error messages are @@ -5560,7 +6031,7 @@ -<H1><A NAME="SEC91" HREF="bison_toc.html#TOC91">Handling Context Dependencies</A></H1> +<H1><A NAME="SEC93" HREF="bison_toc.html#TOC93">Handling Context Dependencies</A></H1> <P> The Bison paradigm is to parse tokens first, then group them into larger @@ -5577,7 +6048,7 @@ -<H2><A NAME="SEC92" HREF="bison_toc.html#TOC92">Semantic Info in Token Types</A></H2> +<H2><A NAME="SEC94" HREF="bison_toc.html#TOC94">Semantic Info in Token Types</A></H2> <P> The C language has a context dependency: the way an identifier is used @@ -5673,9 +6144,9 @@ -<H2><A NAME="SEC93" HREF="bison_toc.html#TOC93">Lexical Tie-ins</A></H2> +<H2><A NAME="SEC95" HREF="bison_toc.html#TOC95">Lexical Tie-ins</A></H2> <P> -<A NAME="IDX203"></A> +<A NAME="IDX220"></A> <P> @@ -5724,19 +6195,18 @@ <P> -The declaration of <CODE>hexflag</CODE> shown in the C declarations section of -the parser file is needed to make it accessible to the actions -(see section <A HREF="bison.html#SEC41">The C Declarations Section</A>). You must also write the code in <CODE>yylex</CODE> -to obey the flag. +The declaration of <CODE>hexflag</CODE> shown in the prologue of the parser file +is needed to make it accessible to the actions (see section <A HREF="bison.html#SEC42">The prologue</A>). +You must also write the code in <CODE>yylex</CODE> to obey the flag. -<H2><A NAME="SEC94" HREF="bison_toc.html#TOC94">Lexical Tie-ins and Error Recovery</A></H2> +<H2><A NAME="SEC96" HREF="bison_toc.html#TOC96">Lexical Tie-ins and Error Recovery</A></H2> <P> Lexical tie-ins make strict demands on any error recovery rules you have. -See section <A HREF="bison.html#SEC90">Error Recovery</A>. +See section <A HREF="bison.html#SEC92">Error Recovery</A>. <P> @@ -5802,12 +6272,473 @@ -<H1><A NAME="SEC95" HREF="bison_toc.html#TOC95">Debugging Your Parser</A></H1> +<H1><A NAME="SEC97" HREF="bison_toc.html#TOC97">Debugging Your Parser</A></H1> + <P> -<A NAME="IDX204"></A> -<A NAME="IDX205"></A> -<A NAME="IDX206"></A> -<A NAME="IDX207"></A> +Developing a parser can be a challenge, especially if you don't +understand the algorithm (see section <A HREF="bison.html#SEC78">The Bison Parser Algorithm</A>). Even so, sometimes a detailed description of the automaton +can help (see section <A HREF="bison.html#SEC98">Understanding Your Parser</A>), or +tracing the execution of the parser can give some insight on why it +behaves improperly (see section <A HREF="bison.html#SEC99">Tracing Your Parser</A>). + + + + +<H2><A NAME="SEC98" HREF="bison_toc.html#TOC98">Understanding Your Parser</A></H2> + +<P> +As documented elsewhere (see section <A HREF="bison.html#SEC78">The Bison Parser Algorithm</A>) +Bison parsers are <EM>shift/reduce automata</EM>. In some cases (much more +frequent than one would hope), looking at this automaton is required to +tune or simply fix a parser. Bison provides two different +representation of it, either textually or graphically (as a VCG +file). + + +<P> +The textual file is generated when the options @option{--report} or +@option{--verbose} are specified, see See section <A HREF="bison.html#SEC100">Invoking Bison</A>. Its name is made by removing <SAMP>`.tab.c'</SAMP> or <SAMP>`.c'</SAMP> from +the parser output file name, and adding <SAMP>`.output'</SAMP> instead. +Therefore, if the input file is <TT>`foo.y'</TT>, then the parser file is +called <TT>`foo.tab.c'</TT> by default. As a consequence, the verbose +output file is called <TT>`foo.output'</TT>. + + +<P> +The following grammar file, <TT>`calc.y'</TT>, will be used in the sequel: + + + +<PRE> +%token NUM STR +%left '+' '-' +%left '*' +%% +exp: exp '+' exp + | exp '-' exp + | exp '*' exp + | exp '/' exp + | NUM + ; +useless: STR; +%% +</PRE> + +<P> +@command{bison} reports: + + + +<PRE> +calc.y: warning: 1 useless nonterminal and 1 useless rule +calc.y:11.1-7: warning: useless nonterminal: useless +calc.y:11.8-12: warning: useless rule: useless: STR +calc.y contains 7 shift/reduce conflicts. +</PRE> + +<P> +When given @option{--report=state}, in addition to <TT>`calc.tab.c'</TT>, it +creates a file <TT>`calc.output'</TT> with contents detailed below. The +order of the output and the exact presentation might vary, but the +interpretation is the same. + + +<P> +The first section includes details on conflicts that were solved thanks +to precedence and/or associativity: + + + +<PRE> +Conflict in state 8 between rule 2 and token '+' resolved as reduce. +Conflict in state 8 between rule 2 and token '-' resolved as reduce. +Conflict in state 8 between rule 2 and token '*' resolved as shift. +... +</PRE> + +<P> +The next section lists states that still have conflicts. + + + +<PRE> +State 8 contains 1 shift/reduce conflict. +State 9 contains 1 shift/reduce conflict. +State 10 contains 1 shift/reduce conflict. +State 11 contains 4 shift/reduce conflicts. +</PRE> + +<P> +<A NAME="IDX221"></A> +<A NAME="IDX222"></A> +<A NAME="IDX223"></A> +<A NAME="IDX224"></A> +<A NAME="IDX225"></A> +<A NAME="IDX226"></A> +The next section reports useless tokens, nonterminal and rules. Useless +nonterminals and rules are removed in order to produce a smaller parser, +but useless tokens are preserved, since they might be used by the +scanner (note the difference between "useless" and "not used" +below): + + + +<PRE> +Useless nonterminals: + useless + +Terminals which are not used: + STR + +Useless rules: +#6 useless: STR; +</PRE> + +<P> +The next section reproduces the exact grammar that Bison used: + + + +<PRE> +Grammar + + Number, Line, Rule + 0 5 $accept -> exp $end + 1 5 exp -> exp '+' exp + 2 6 exp -> exp '-' exp + 3 7 exp -> exp '*' exp + 4 8 exp -> exp '/' exp + 5 9 exp -> NUM +</PRE> + +<P> +and reports the uses of the symbols: + + + +<PRE> +Terminals, with rules where they appear + +$end (0) 0 +'*' (42) 3 +'+' (43) 1 +'-' (45) 2 +'/' (47) 4 +error (256) +NUM (258) 5 + +Nonterminals, with rules where they appear + +$accept (8) + on left: 0 +exp (9) + on left: 1 2 3 4 5, on right: 0 1 2 3 4 +</PRE> + +<P> +<A NAME="IDX227"></A> +<A NAME="IDX228"></A> +<A NAME="IDX229"></A> +Bison then proceeds onto the automaton itself, describing each state +with it set of <EM>items</EM>, also known as <EM>pointed rules</EM>. Each +item is a production rule together with a point (marked by <SAMP>`.'</SAMP>) +that the input cursor. + + + +<PRE> +state 0 + + $accept -> . exp $ (rule 0) + + NUM shift, and go to state 1 + + exp go to state 2 +</PRE> + +<P> +This reads as follows: "state 0 corresponds to being at the very +beginning of the parsing, in the initial rule, right before the start +symbol (here, <CODE>exp</CODE>). When the parser returns to this state right +after having reduced a rule that produced an <CODE>exp</CODE>, the control +flow jumps to state 2. If there is no such transition on a nonterminal +symbol, and the lookahead is a <CODE>NUM</CODE>, then this token is shifted on +the parse stack, and the control flow jumps to state 1. Any other +lookahead triggers a parse error." + + +<P> +<A NAME="IDX230"></A> +<A NAME="IDX231"></A> +<A NAME="IDX232"></A> +<A NAME="IDX233"></A> +Even though the only active rule in state 0 seems to be rule 0, the +report lists <CODE>NUM</CODE> as a lookahead symbol because <CODE>NUM</CODE> can be +at the beginning of any rule deriving an <CODE>exp</CODE>. By default Bison +reports the so-called <EM>core</EM> or <EM>kernel</EM> of the item set, but if +you want to see more detail you can invoke @command{bison} with +@option{--report=itemset} to list all the items, include those that can +be derived: + + + +<PRE> +state 0 + + $accept -> . exp $ (rule 0) + exp -> . exp '+' exp (rule 1) + exp -> . exp '-' exp (rule 2) + exp -> . exp '*' exp (rule 3) + exp -> . exp '/' exp (rule 4) + exp -> . NUM (rule 5) + + NUM shift, and go to state 1 + + exp go to state 2 +</PRE> + +<P> +In the state 1... + + + +<PRE> +state 1 + + exp -> NUM . (rule 5) + + $default reduce using rule 5 (exp) +</PRE> + +<P> +the rule 5, <SAMP>`exp: NUM;'</SAMP>, is completed. Whatever the lookahead +(<SAMP>`$default'</SAMP>), the parser will reduce it. If it was coming from +state 0, then, after this reduction it will return to state 0, and will +jump to state 2 (<SAMP>`exp: go to state 2'</SAMP>). + + + +<PRE> +state 2 + + $accept -> exp . $ (rule 0) + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + $ shift, and go to state 3 + '+' shift, and go to state 4 + '-' shift, and go to state 5 + '*' shift, and go to state 6 + '/' shift, and go to state 7 +</PRE> + +<P> +In state 2, the automaton can only shift a symbol. For instance, +because of the item <SAMP>`exp -> exp . '+' exp'</SAMP>, if the lookahead if +<SAMP>`+'</SAMP>, it will be shifted on the parse stack, and the automaton +control will jump to state 4, corresponding to the item <SAMP>`exp -> exp +'+' . exp'</SAMP>. Since there is no default action, any other token than +those listed above will trigger a parse error. + + +<P> +The state 3 is named the <EM>final state</EM>, or the <EM>accepting +state</EM>: + + + +<PRE> +state 3 + + $accept -> exp $ . (rule 0) + + $default accept +</PRE> + +<P> +the initial rule is completed (the start symbol and the end +of input were read), the parsing exits successfully. + + +<P> +The interpretation of states 4 to 7 is straightforward, and is left to +the reader. + + + +<PRE> +state 4 + + exp -> exp '+' . exp (rule 1) + + NUM shift, and go to state 1 + + exp go to state 8 + +state 5 + + exp -> exp '-' . exp (rule 2) + + NUM shift, and go to state 1 + + exp go to state 9 + +state 6 + + exp -> exp '*' . exp (rule 3) + + NUM shift, and go to state 1 + + exp go to state 10 + +state 7 + + exp -> exp '/' . exp (rule 4) + + NUM shift, and go to state 1 + + exp go to state 11 +</PRE> + +<P> +As was announced in beginning of the report, <SAMP>`State 8 contains 1 +shift/reduce conflict'</SAMP>: + + + +<PRE> +state 8 + + exp -> exp . '+' exp (rule 1) + exp -> exp '+' exp . (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '/' [reduce using rule 1 (exp)] + $default reduce using rule 1 (exp) +</PRE> + +<P> +Indeed, there are two actions associated to the lookahead <SAMP>`/'</SAMP>: +either shifting (and going to state 7), or reducing rule 1. The +conflict means that either the grammar is ambiguous, or the parser lacks +information to make the right decision. Indeed the grammar is +ambiguous, as, since we did not specify the precedence of <SAMP>`/'</SAMP>, the +sentence <SAMP>`NUM + NUM / NUM'</SAMP> can be parsed as <SAMP>`NUM + (NUM / +NUM)'</SAMP>, which corresponds to shifting <SAMP>`/'</SAMP>, or as <SAMP>`(NUM + NUM) / +NUM'</SAMP>, which corresponds to reducing rule 1. + + +<P> +Because in LALR(1) parsing a single decision can be made, Bison +arbitrarily chose to disable the reduction, see section <A HREF="bison.html#SEC80">Shift/Reduce Conflicts</A>. Discarded actions are reported in between +square brackets. + + +<P> +Note that all the previous states had a single possible action: either +shifting the next token and going to the corresponding state, or +reducing a single rule. In the other cases, i.e., when shifting +<EM>and</EM> reducing is possible or when <EM>several</EM> reductions are +possible, the lookahead is required to select the action. State 8 is +one such state: if the lookahead is <SAMP>`*'</SAMP> or <SAMP>`/'</SAMP> then the action +is shifting, otherwise the action is reducing rule 1. In other words, +the first two items, corresponding to rule 1, are not eligible when the +lookahead is <SAMP>`*'</SAMP>, since we specified that <SAMP>`*'</SAMP> has higher +precedence that <SAMP>`+'</SAMP>. More generally, some items are eligible only +with some set of possible lookaheads. When run with +@option{--report=lookahead}, Bison specifies these lookaheads: + + + +<PRE> +state 8 + + exp -> exp . '+' exp [$, '+', '-', '/'] (rule 1) + exp -> exp '+' exp . [$, '+', '-', '/'] (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '/' [reduce using rule 1 (exp)] + $default reduce using rule 1 (exp) +</PRE> + +<P> +The remaining states are similar: + + + +<PRE> +state 9 + + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp '-' exp . (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '/' [reduce using rule 2 (exp)] + $default reduce using rule 2 (exp) + +state 10 + + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp '*' exp . (rule 3) + exp -> exp . '/' exp (rule 4) + + '/' shift, and go to state 7 + + '/' [reduce using rule 3 (exp)] + $default reduce using rule 3 (exp) + +state 11 + + exp -> exp . '+' exp (rule 1) + exp -> exp . '-' exp (rule 2) + exp -> exp . '*' exp (rule 3) + exp -> exp . '/' exp (rule 4) + exp -> exp '/' exp . (rule 4) + + '+' shift, and go to state 4 + '-' shift, and go to state 5 + '*' shift, and go to state 6 + '/' shift, and go to state 7 + + '+' [reduce using rule 4 (exp)] + '-' [reduce using rule 4 (exp)] + '*' [reduce using rule 4 (exp)] + '/' [reduce using rule 4 (exp)] + $default reduce using rule 4 (exp) +</PRE> + +<P> +Observe that state 11 contains conflicts due to the lack of precedence +of <SAMP>`/'</SAMP> wrt <SAMP>`+'</SAMP>, <SAMP>`-'</SAMP>, and <SAMP>`*'</SAMP>, but also because the +associativity of <SAMP>`/'</SAMP> is not specified. + + + + +<H2><A NAME="SEC99" HREF="bison_toc.html#TOC99">Tracing Your Parser</A></H2> +<P> +<A NAME="IDX234"></A> +<A NAME="IDX235"></A> +<A NAME="IDX236"></A> <P> @@ -5816,18 +6747,44 @@ <P> -To enable compilation of trace facilities, you must define the macro -<CODE>YYDEBUG</CODE> when you compile the parser. You could use +There are several means to enable compilation of trace facilities: + + +<DL COMPACT> + +<DT>the macro <CODE>YYDEBUG</CODE> +<DD> +<A NAME="IDX237"></A> +Define the macro <CODE>YYDEBUG</CODE> to a nonzero value when you compile the +parser. This is compliant with POSIX Yacc. You could use <SAMP>`-DYYDEBUG=1'</SAMP> as a compiler option or you could put <SAMP>`#define -YYDEBUG 1'</SAMP> in the C declarations section of the grammar file -(see section <A HREF="bison.html#SEC41">The C Declarations Section</A>). Alternatively, use the <SAMP>`-t'</SAMP> option when -you run Bison (see section <A HREF="bison.html#SEC96">Invoking Bison</A>). We always define <CODE>YYDEBUG</CODE> so that -debugging is always possible. +YYDEBUG 1'</SAMP> in the prologue of the grammar file (see section <A HREF="bison.html#SEC42">The prologue</A>). + +<DT>the option @option{-t, @option{--debug}} +<DD> +Use the <SAMP>`-t'</SAMP> option when you run Bison (see section <A HREF="bison.html#SEC100">Invoking Bison</A>). This is POSIX compliant too. +<DT>the directive <SAMP>`%debug'</SAMP> +<DD> +<A NAME="IDX238"></A> +Add the <CODE>%debug</CODE> directive (see section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>). This is a Bison extension, which will prove +useful when Bison will output parsers for languages that don't use a +preprocessor. Useless POSIX and Yacc portability matter to you, this is +the preferred solution. +</DL> <P> -The trace facility uses <CODE>stderr</CODE>, so you must add <CODE>#include -<stdio.h></CODE> to the C declarations section unless it is already there. +We suggest that you always enable the debug option so that debugging is +always possible. + + +<P> +The trace facility outputs messages with macro calls of the form +<CODE>YYFPRINTF (stderr, <VAR>format</VAR>, <VAR>args</VAR>)</CODE> where +<VAR>format</VAR> and <VAR>args</VAR> are the usual <CODE>printf</CODE> format and +arguments. If you define <CODE>YYDEBUG</CODE> to a nonzero value but do not +define <CODE>YYFPRINTF</CODE>, <CODE><stdio.h></CODE> is automatically included +and <CODE>YYPRINTF</CODE> is defined to <CODE>fprintf</CODE>. <P> @@ -5852,7 +6809,7 @@ <LI> Each time a token is shifted, the depth and complete contents of the -state stack (see section <A HREF="bison.html#SEC86">Parser States</A>). +state stack (see section <A HREF="bison.html#SEC87">Parser States</A>). <LI> @@ -5862,13 +6819,13 @@ <P> To make sense of this information, it helps to refer to the listing file -produced by the Bison <SAMP>`-v'</SAMP> option (see section <A HREF="bison.html#SEC96">Invoking Bison</A>). This file -shows the meaning of each state in terms of positions in various rules, and -also what each state will do with each possible input token. As you read -the successive trace messages, you can see that the parser is functioning -according to its specification in the listing file. Eventually you will -arrive at the place where something undesirable happens, and you will see -which parts of the grammar are to blame. +produced by the Bison <SAMP>`-v'</SAMP> option (see section <A HREF="bison.html#SEC100">Invoking Bison</A>). This file shows the meaning of each state in terms of +positions in various rules, and also what each state will do with each +possible input token. As you read the successive trace messages, you +can see that the parser is functioning according to its specification in +the listing file. Eventually you will arrive at the place where +something undesirable happens, and you will see which parts of the +grammar are to blame. <P> @@ -5880,7 +6837,7 @@ <P> -<A NAME="IDX208"></A> +<A NAME="IDX239"></A> The debugging information normally gives the token type of each token read, but not its semantic value. You can optionally define a macro named <CODE>YYPRINT</CODE> to provide a way to print the value. If you define @@ -5891,7 +6848,7 @@ <P> Here is an example of <CODE>YYPRINT</CODE> suitable for the multi-function -calculator (see section <A HREF="bison.html#SEC35">Declarations for <CODE>mfcalc</CODE></A>): +calculator (see section <A HREF="bison.html#SEC36">Declarations for <CODE>mfcalc</CODE></A>): @@ -5910,11 +6867,11 @@ -<H1><A NAME="SEC96" HREF="bison_toc.html#TOC96">Invoking Bison</A></H1> +<H1><A NAME="SEC100" HREF="bison_toc.html#TOC100">Invoking Bison</A></H1> <P> -<A NAME="IDX209"></A> -<A NAME="IDX210"></A> -<A NAME="IDX211"></A> +<A NAME="IDX240"></A> +<A NAME="IDX241"></A> +<A NAME="IDX242"></A> <P> @@ -5931,10 +6888,11 @@ <SAMP>`.y'</SAMP>. The parser file's name is made by replacing the <SAMP>`.y'</SAMP> with <SAMP>`.tab.c'</SAMP>. Thus, the <SAMP>`bison foo.y'</SAMP> filename yields <TT>`foo.tab.c'</TT>, and the <SAMP>`bison hack/foo.y'</SAMP> filename yields -<TT>`hack/foo.tab.c'</TT>. It's is also possible, in case you are writting +<TT>`hack/foo.tab.c'</TT>. It's also possible, in case you are writing C++ code instead of C in your grammar file, to name it <TT>`foo.ypp'</TT> -or <TT>`foo.y++'</TT>. Then, the output files will take an extention like -the given one as input (repectively <TT>`foo.tab.cpp'</TT> and <TT>`foo.tab.c++'</TT>). +or <TT>`foo.y++'</TT>. Then, the output files will take an extension like +the given one as input (respectively <TT>`foo.tab.cpp'</TT> and +<TT>`foo.tab.c++'</TT>). This feature takes effect with all options that manipulate filenames like <SAMP>`-o'</SAMP> or <SAMP>`-d'</SAMP>. @@ -5949,12 +6907,12 @@ </PRE> <P> -will produce <TT>`infile.tab.cxx'</TT> and <TT>`infile.tab.hxx'</TT>. and +will produce <TT>`infile.tab.cxx'</TT> and <TT>`infile.tab.hxx'</TT>, and <PRE> -bison -d <VAR>infile.y</VAR> -o <VAR>output.c++</VAR> +bison -d -o <VAR>output.c++</VAR> <VAR>infile.y</VAR> </PRE> <P> @@ -5963,7 +6921,7 @@ -<H2><A NAME="SEC97" HREF="bison_toc.html#TOC97">Bison Options</A></H2> +<H2><A NAME="SEC101" HREF="bison_toc.html#TOC101">Bison Options</A></H2> <P> Bison supports both traditional single-letter options and mnemonic long @@ -6000,14 +6958,13 @@ <DD> <DT>@option{--yacc} <DD> -<DT>@option{--fixed-output-files} -<DD> Equivalent to <SAMP>`-o y.tab.c'</SAMP>; the parser output file is called <TT>`y.tab.c'</TT>, and the other outputs are called <TT>`y.output'</TT> and <TT>`y.tab.h'</TT>. The purpose of this option is to imitate Yacc's output file name conventions. Thus, the following shell script can substitute for Yacc: + <PRE> bison -y $* </PRE> @@ -6031,26 +6988,20 @@ <DD> <DT>@option{--debug} <DD> -Output a definition of the macro <CODE>YYDEBUG</CODE> into the parser file, so -that the debugging facilities are compiled. See section <A HREF="bison.html#SEC95">Debugging Your Parser</A>. +In the parser file, define the macro <CODE>YYDEBUG</CODE> to 1 if it is not +already defined, so that the debugging facilities are compiled. +See section <A HREF="bison.html#SEC99">Tracing Your Parser</A>. <DT>@option{--locations} <DD> -Pretend that <CODE>%locactions</CODE> was specified. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +Pretend that <CODE>%locations</CODE> was specified. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT>@option{-p <VAR>prefix</VAR>} <DD> <DT>@option{--name-prefix=<VAR>prefix</VAR>} <DD> -Rename the external symbols used in the parser so that they start with -<VAR>prefix</VAR> instead of <SAMP>`yy'</SAMP>. The precise list of symbols renamed -is <CODE>yyparse</CODE>, <CODE>yylex</CODE>, <CODE>yyerror</CODE>, <CODE>yynerrs</CODE>, -<CODE>yylval</CODE>, <CODE>yychar</CODE> and <CODE>yydebug</CODE>. - -For example, if you use <SAMP>`-p c'</SAMP>, the names become <CODE>cparse</CODE>, -<CODE>clex</CODE>, and so on. - -See section <A HREF="bison.html#SEC67">Multiple Parsers in the Same Program</A>. +Pretend that <CODE>%name-prefix="<VAR>prefix</VAR>"</CODE> was specified. +See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT>@option{-l} <DD> @@ -6066,13 +7017,13 @@ <DD> <DT>@option{--no-parser} <DD> -Pretend that <CODE>%no_parser</CODE> was specified. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +Pretend that <CODE>%no-parser</CODE> was specified. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT>@option{-k} <DD> <DT>@option{--token-table} <DD> -Pretend that <CODE>%token_table</CODE> was specified. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +Pretend that <CODE>%token-table</CODE> was specified. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. </DL> <P> @@ -6083,23 +7034,50 @@ <DT>@option{-d} <DD> -Pretend that <CODE>%verbose</CODE> was specified, i.e., write an extra output +<DT>@option{--defines} +<DD> +Pretend that <CODE>%defines</CODE> was specified, i.e., write an extra output file containing macro definitions for the token type names defined in the grammar and the semantic value type <CODE>YYSTYPE</CODE>, as well as a few -<CODE>extern</CODE> variable declarations. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +<CODE>extern</CODE> variable declarations. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT>@option{--defines=<VAR>defines-file</VAR>} <DD> -The behaviour of <VAR>--defines</VAR> is the same than <SAMP>`-d'</SAMP>. The only -difference is that it has an optionnal argument which is the name of -the output filename. +Same as above, but save in the file <VAR>defines-file</VAR>. <DT>@option{-b <VAR>file-prefix</VAR>} <DD> <DT>@option{--file-prefix=<VAR>prefix</VAR>} <DD> -Specify a prefix to use for all Bison output file names. The names are -chosen as if the input file were named <TT>`<VAR>prefix</VAR>.c'</TT>. +Pretend that <CODE>%verbose</CODE> was specified, i.e, specify prefix to use +for all Bison output file names. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. + +<DT>@option{-r <VAR>things</VAR>} +<DD> +<DT>@option{--report=<VAR>things</VAR>} +<DD> +Write an extra output file containing verbose description of the comma +separated list of <VAR>things</VAR> among: + +<DL COMPACT> + +<DT><CODE>state</CODE> +<DD> +Description of the grammar, conflicts (resolved and unresolved), and +LALR automaton. + +<DT><CODE>lookahead</CODE> +<DD> +Implies <CODE>state</CODE> and augments the description of the automaton with +each rule's lookahead set. + +<DT><CODE>itemset</CODE> +<DD> +Implies <CODE>state</CODE> and augments the description of the automaton with +the full set of items for each state, instead of its core only. +</DL> + +For instance, on the following grammar <DT>@option{-v} <DD> @@ -6107,66 +7085,33 @@ <DD> Pretend that <CODE>%verbose</CODE> was specified, i.e, write an extra output file containing verbose descriptions of the grammar and -parser. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>, for more. +parser. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. -<DT>@option{-o <VAR>outfile</VAR>} +<DT>@option{-o <VAR>filename</VAR>} <DD> -<DT>@option{--output-file=<VAR>outfile</VAR>} +<DT>@option{--output=<VAR>filename</VAR>} <DD> -Specify the name <VAR>outfile</VAR> for the parser file. +Specify the <VAR>filename</VAR> for the parser file. -The other output files' names are constructed from <VAR>outfile</VAR> -as described under the <SAMP>`-v'</SAMP> and <SAMP>`-d'</SAMP> options. +The other output files' names are constructed from <VAR>filename</VAR> as +described under the <SAMP>`-v'</SAMP> and <SAMP>`-d'</SAMP> options. <DT>@option{-g} <DD> Output a VCG definition of the LALR(1) grammar automaton computed by -Bison. If the grammar file is <TT>`foo.y'</TT>, the VCG output file will +Bison. If the grammar file is <TT>`foo.y'</TT>, the VCG output file will be <TT>`foo.vcg'</TT>. <DT>@option{--graph=<VAR>graph-file</VAR>} <DD> -The behaviour of <VAR>--graph</VAR> is the same than <SAMP>`-g'</SAMP>. The only -difference is that it has an optionnal argument which is the name of +The behavior of <VAR>--graph</VAR> is the same than <SAMP>`-g'</SAMP>. The only +difference is that it has an optional argument which is the name of the output graph filename. </DL> -<H2><A NAME="SEC98" HREF="bison_toc.html#TOC98">Environment Variables</A></H2> -<P> -<A NAME="IDX212"></A> -<A NAME="IDX213"></A> -<A NAME="IDX214"></A> - - -<P> -Here is a list of environment variables which affect the way Bison -runs. - - -<DL COMPACT> - -<DT><SAMP>`BISON_SIMPLE'</SAMP> -<DD> -<DT><SAMP>`BISON_HAIRY'</SAMP> -<DD> -Much of the parser generated by Bison is copied verbatim from a file -called <TT>`bison.simple'</TT>. If Bison cannot find that file, or if you -would like to direct Bison to use a different copy, setting the -environment variable <CODE>BISON_SIMPLE</CODE> to the path of the file will -cause Bison to use that copy instead. - -When the <SAMP>`%semantic_parser'</SAMP> declaration is used, Bison copies from -a file called <TT>`bison.hairy'</TT> instead. The location of this file can -also be specified or overridden in a similar fashion, with the -<CODE>BISON_HAIRY</CODE> environment variable. - -</DL> - - - -<H2><A NAME="SEC99" HREF="bison_toc.html#TOC99">Option Cross Key</A></H2> +<H2><A NAME="SEC102" HREF="bison_toc.html#TOC102">Option Cross Key</A></H2> <P> Here is a list of options, alphabetized by long option, to help you find @@ -6175,10 +7120,10 @@ -<H2><A NAME="SEC100" HREF="bison_toc.html#TOC100">Invoking Bison under VMS</A></H2> +<H2><A NAME="SEC103" HREF="bison_toc.html#TOC103">Invoking Bison under VMS</A></H2> <P> -<A NAME="IDX215"></A> -<A NAME="IDX216"></A> +<A NAME="IDX243"></A> +<A NAME="IDX244"></A> <P> @@ -6215,14 +7160,77 @@ -<H1><A NAME="SEC101" HREF="bison_toc.html#TOC101">Bison Symbols</A></H1> +<H1><A NAME="SEC104" HREF="bison_toc.html#TOC104">Frequently Asked Questions</A></H1> <P> -<A NAME="IDX217"></A> -<A NAME="IDX218"></A> +<A NAME="IDX245"></A> +<A NAME="IDX246"></A> + + +<P> +Several questions about Bison come up occasionally. Here some of them +are addressed. + + + + +<H2><A NAME="SEC105" HREF="bison_toc.html#TOC105">Parser Stack Overflow</A></H2> + + +<PRE> +My parser returns with error with a <SAMP>`parser stack overflow'</SAMP> +message. What can I do? +</PRE> + +<P> +This question is already addressed elsewhere, See section <A HREF="bison.html#SEC48">Recursive Rules</A>. + + + + +<H1><A NAME="SEC106" HREF="bison_toc.html#TOC106">Bison Symbols</A></H1> +<P> +<A NAME="IDX247"></A> +<A NAME="IDX248"></A> <DL COMPACT> +<DT><CODE>@$</CODE> +<DD> +In an action, the location of the left-hand side of the rule. +See section <A HREF="bison.html#SEC55">Tracking Locations</A>. + +<DT><CODE>@<VAR>n</VAR></CODE> +<DD> +In an action, the location of the <VAR>n</VAR>-th symbol of the right-hand +side of the rule. See section <A HREF="bison.html#SEC55">Tracking Locations</A>. + +<DT><CODE>$$</CODE> +<DD> +In an action, the semantic value of the left-hand side of the rule. +See section <A HREF="bison.html#SEC52">Actions</A>. + +<DT><CODE>$<VAR>n</VAR></CODE> +<DD> +In an action, the semantic value of the <VAR>n</VAR>-th symbol of the +right-hand side of the rule. See section <A HREF="bison.html#SEC52">Actions</A>. + +<DT><CODE>$accept</CODE> +<DD> +The predefined nonterminal whose only rule is <SAMP>`$accept: <VAR>start</VAR> +$end'</SAMP>, where <VAR>start</VAR> is the start symbol. See section <A HREF="bison.html#SEC65">The Start-Symbol</A>. It cannot be used in the grammar. + +<DT><CODE>$end</CODE> +<DD> +The predefined token marking the end of the token stream. It cannot be +used in the grammar. + +<DT><CODE>$undefined</CODE> +<DD> +The predefined token onto which all undefined values returned by +<CODE>yylex</CODE> are mapped. It cannot be used in the grammar, rather, use +<CODE>error</CODE>. + <DT><CODE>error</CODE> <DD> A token name reserved for error recovery. This token may be used in @@ -6232,31 +7240,35 @@ token <CODE>error</CODE> becomes the current look-ahead token. Actions corresponding to <CODE>error</CODE> are then executed, and the look-ahead token is reset to the token that originally caused the violation. -See section <A HREF="bison.html#SEC90">Error Recovery</A>. +See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><CODE>YYABORT</CODE> <DD> Macro to pretend that an unrecoverable syntax error has occurred, by making <CODE>yyparse</CODE> return 1 immediately. The error reporting -function <CODE>yyerror</CODE> is not called. See section <A HREF="bison.html#SEC69">The Parser Function <CODE>yyparse</CODE></A>. +function <CODE>yyerror</CODE> is not called. See section <A HREF="bison.html#SEC70">The Parser Function <CODE>yyparse</CODE></A>. <DT><CODE>YYACCEPT</CODE> <DD> Macro to pretend that a complete utterance of the language has been read, by making <CODE>yyparse</CODE> return 0 immediately. -See section <A HREF="bison.html#SEC69">The Parser Function <CODE>yyparse</CODE></A>. +See section <A HREF="bison.html#SEC70">The Parser Function <CODE>yyparse</CODE></A>. <DT><CODE>YYBACKUP</CODE> <DD> Macro to discard a value from the parser stack and fake a look-ahead -token. See section <A HREF="bison.html#SEC76">Special Features for Use in Actions</A>. +token. See section <A HREF="bison.html#SEC77">Special Features for Use in Actions</A>. + +<DT><CODE>YYDEBUG</CODE> +<DD> +Macro to define to equip the parser with tracing code. See section <A HREF="bison.html#SEC99">Tracing Your Parser</A>. <DT><CODE>YYERROR</CODE> <DD> Macro to pretend that a syntax error has just been detected: call <CODE>yyerror</CODE> and then perform normal error recovery if possible -(see section <A HREF="bison.html#SEC90">Error Recovery</A>), or (if recovery is impossible) make -<CODE>yyparse</CODE> return 1. See section <A HREF="bison.html#SEC90">Error Recovery</A>. +(see section <A HREF="bison.html#SEC92">Error Recovery</A>), or (if recovery is impossible) make +<CODE>yyparse</CODE> return 1. See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><CODE>YYERROR_VERBOSE</CODE> <DD> @@ -6267,17 +7279,17 @@ <DT><CODE>YYINITDEPTH</CODE> <DD> Macro for specifying the initial size of the parser stack. -See section <A HREF="bison.html#SEC89">Stack Overflow, and How to Avoid It</A>. +See section <A HREF="bison.html#SEC91">Stack Overflow, and How to Avoid It</A>. <DT><CODE>YYLEX_PARAM</CODE> <DD> Macro for specifying an extra argument (or list of extra arguments) for -<CODE>yyparse</CODE> to pass to <CODE>yylex</CODE>. See section <A HREF="bison.html#SEC74">Calling Conventions for Pure Parsers</A>. +<CODE>yyparse</CODE> to pass to <CODE>yylex</CODE>. See section <A HREF="bison.html#SEC75">Calling Conventions for Pure Parsers</A>. <DT><CODE>YYLTYPE</CODE> <DD> Macro for the data type of <CODE>yylloc</CODE>; a structure with four -members. See section <A HREF="bison.html#SEC55">Data Type of Locations</A>. +members. See section <A HREF="bison.html#SEC56">Data Type of Locations</A>. <DT><CODE>yyltype</CODE> <DD> @@ -6286,70 +7298,70 @@ <DT><CODE>YYMAXDEPTH</CODE> <DD> Macro for specifying the maximum size of the parser stack. -See section <A HREF="bison.html#SEC89">Stack Overflow, and How to Avoid It</A>. +See section <A HREF="bison.html#SEC91">Stack Overflow, and How to Avoid It</A>. <DT><CODE>YYPARSE_PARAM</CODE> <DD> Macro for specifying the name of a parameter that <CODE>yyparse</CODE> should -accept. See section <A HREF="bison.html#SEC74">Calling Conventions for Pure Parsers</A>. +accept. See section <A HREF="bison.html#SEC75">Calling Conventions for Pure Parsers</A>. <DT><CODE>YYRECOVERING</CODE> <DD> Macro whose value indicates whether the parser is recovering from a -syntax error. See section <A HREF="bison.html#SEC76">Special Features for Use in Actions</A>. +syntax error. See section <A HREF="bison.html#SEC77">Special Features for Use in Actions</A>. <DT><CODE>YYSTACK_USE_ALLOCA</CODE> <DD> -Macro used to control the use of <CODE>alloca</CODE>. If defined to <SAMP>`0'</SAMP>, +Macro used to control the use of <CODE>alloca</CODE>. If defined to <SAMP>`0'</SAMP>, the parser will not use <CODE>alloca</CODE> but <CODE>malloc</CODE> when trying to -grow its internal stacks. Do <EM>not</EM> define <CODE>YYSTACK_USE_ALLOCA</CODE> +grow its internal stacks. Do <EM>not</EM> define <CODE>YYSTACK_USE_ALLOCA</CODE> to anything else. <DT><CODE>YYSTYPE</CODE> <DD> Macro for the data type of semantic values; <CODE>int</CODE> by default. -See section <A HREF="bison.html#SEC49">Data Types of Semantic Values</A>. +See section <A HREF="bison.html#SEC50">Data Types of Semantic Values</A>. <DT><CODE>yychar</CODE> <DD> External integer variable that contains the integer value of the current look-ahead token. (In a pure parser, it is a local variable within <CODE>yyparse</CODE>.) Error-recovery rule actions may examine this variable. -See section <A HREF="bison.html#SEC76">Special Features for Use in Actions</A>. +See section <A HREF="bison.html#SEC77">Special Features for Use in Actions</A>. <DT><CODE>yyclearin</CODE> <DD> Macro used in error-recovery rule actions. It clears the previous -look-ahead token. See section <A HREF="bison.html#SEC90">Error Recovery</A>. +look-ahead token. See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><CODE>yydebug</CODE> <DD> External integer variable set to zero by default. If <CODE>yydebug</CODE> is given a nonzero value, the parser will output information on input -symbols and parser action. See section <A HREF="bison.html#SEC95">Debugging Your Parser</A>. +symbols and parser action. See section <A HREF="bison.html#SEC99">Tracing Your Parser</A>. <DT><CODE>yyerrok</CODE> <DD> Macro to cause parser to recover immediately to its normal mode -after a parse error. See section <A HREF="bison.html#SEC90">Error Recovery</A>. +after a parse error. See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT><CODE>yyerror</CODE> <DD> User-supplied function to be called by <CODE>yyparse</CODE> on error. The function receives one argument, a pointer to a character string -containing an error message. See section <A HREF="bison.html#SEC75">The Error Reporting Function <CODE>yyerror</CODE></A>. +containing an error message. See section <A HREF="bison.html#SEC76">The Error Reporting Function <CODE>yyerror</CODE></A>. <DT><CODE>yylex</CODE> <DD> -User-supplied lexical analyzer function, called with no arguments -to get the next token. See section <A HREF="bison.html#SEC70">The Lexical Analyzer Function <CODE>yylex</CODE></A>. +User-supplied lexical analyzer function, called with no arguments to get +the next token. See section <A HREF="bison.html#SEC71">The Lexical Analyzer Function <CODE>yylex</CODE></A>. <DT><CODE>yylval</CODE> <DD> External variable in which <CODE>yylex</CODE> should place the semantic value associated with a token. (In a pure parser, it is a local variable within <CODE>yyparse</CODE>, and its address is passed to -<CODE>yylex</CODE>.) See section <A HREF="bison.html#SEC72">Semantic Values of Tokens</A>. +<CODE>yylex</CODE>.) See section <A HREF="bison.html#SEC73">Semantic Values of Tokens</A>. <DT><CODE>yylloc</CODE> <DD> @@ -6357,80 +7369,108 @@ numbers associated with a token. (In a pure parser, it is a local variable within <CODE>yyparse</CODE>, and its address is passed to <CODE>yylex</CODE>.) You can ignore this variable if you don't use the -<SAMP>`@'</SAMP> feature in the grammar actions. See section <A HREF="bison.html#SEC73">Textual Positions of Tokens</A>. +<SAMP>`@'</SAMP> feature in the grammar actions. See section <A HREF="bison.html#SEC74">Textual Positions of Tokens</A>. <DT><CODE>yynerrs</CODE> <DD> Global variable which Bison increments each time there is a parse error. (In a pure parser, it is a local variable within <CODE>yyparse</CODE>.) -See section <A HREF="bison.html#SEC75">The Error Reporting Function <CODE>yyerror</CODE></A>. +See section <A HREF="bison.html#SEC76">The Error Reporting Function <CODE>yyerror</CODE></A>. <DT><CODE>yyparse</CODE> <DD> The parser function produced by Bison; call this function to start -parsing. See section <A HREF="bison.html#SEC69">The Parser Function <CODE>yyparse</CODE></A>. +parsing. See section <A HREF="bison.html#SEC70">The Parser Function <CODE>yyparse</CODE></A>. <DT><CODE>%debug</CODE> <DD> -Equip the parser for debugging. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +Equip the parser for debugging. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT><CODE>%defines</CODE> <DD> Bison declaration to create a header file meant for the scanner. -See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. + +<DT><CODE>%dprec</CODE> +<DD> +Bison declaration to assign a precedence to a rule that is used at parse +time to resolve reduce/reduce conflicts. See section <A HREF="bison.html#SEC12">Writing GLR Parsers</A>. + +<DT><CODE>%file-prefix="<VAR>prefix</VAR>"</CODE> +<DD> +Bison declaration to set the prefix of the output files. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. + +<DT><CODE>%glr-parser</CODE> +<DD> +Bison declaration to produce a GLR parser. See section <A HREF="bison.html#SEC12">Writing GLR Parsers</A>. <DT><CODE>%left</CODE> <DD> Bison declaration to assign left associativity to token(s). -See section <A HREF="bison.html#SEC60">Operator Precedence</A>. +See section <A HREF="bison.html#SEC61">Operator Precedence</A>. + +<DT><CODE>%merge</CODE> +<DD> +Bison declaration to assign a merging function to a rule. If there is a +reduce/reduce conflict with a rule having the same merging function, the +function is applied to the two semantic values to get a single result. +See section <A HREF="bison.html#SEC12">Writing GLR Parsers</A>. + +<DT><CODE>%name-prefix="<VAR>prefix</VAR>"</CODE> +<DD> +Bison declaration to rename the external symbols. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. -<DT><CODE>%no_lines</CODE> +<DT><CODE>%no-lines</CODE> <DD> Bison declaration to avoid generating <CODE>#line</CODE> directives in the -parser file. See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +parser file. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT><CODE>%nonassoc</CODE> <DD> Bison declaration to assign non-associativity to token(s). -See section <A HREF="bison.html#SEC60">Operator Precedence</A>. +See section <A HREF="bison.html#SEC61">Operator Precedence</A>. + +<DT><CODE>%output="<VAR>filename</VAR>"</CODE> +<DD> +Bison declaration to set the name of the parser file. See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT><CODE>%prec</CODE> <DD> Bison declaration to assign a precedence to a specific rule. -See section <A HREF="bison.html#SEC85">Context-Dependent Precedence</A>. +See section <A HREF="bison.html#SEC86">Context-Dependent Precedence</A>. -<DT><CODE>%pure_parser</CODE> +<DT><CODE>%pure-parser</CODE> <DD> Bison declaration to request a pure (reentrant) parser. -See section <A HREF="bison.html#SEC65">A Pure (Reentrant) Parser</A>. +See section <A HREF="bison.html#SEC66">A Pure (Reentrant) Parser</A>. <DT><CODE>%right</CODE> <DD> Bison declaration to assign right associativity to token(s). -See section <A HREF="bison.html#SEC60">Operator Precedence</A>. +See section <A HREF="bison.html#SEC61">Operator Precedence</A>. <DT><CODE>%start</CODE> <DD> -Bison declaration to specify the start symbol. See section <A HREF="bison.html#SEC64">The Start-Symbol</A>. +Bison declaration to specify the start symbol. See section <A HREF="bison.html#SEC65">The Start-Symbol</A>. <DT><CODE>%token</CODE> <DD> Bison declaration to declare token(s) without specifying precedence. -See section <A HREF="bison.html#SEC59">Token Type Names</A>. +See section <A HREF="bison.html#SEC60">Token Type Names</A>. -<DT><CODE>%token_table</CODE> +<DT><CODE>%token-table</CODE> <DD> Bison declaration to include a token name table in the parser file. -See section <A HREF="bison.html#SEC66">Bison Declaration Summary</A>. +See section <A HREF="bison.html#SEC67">Bison Declaration Summary</A>. <DT><CODE>%type</CODE> <DD> -Bison declaration to declare nonterminals. See section <A HREF="bison.html#SEC62">Nonterminal Symbols</A>. +Bison declaration to declare nonterminals. See section <A HREF="bison.html#SEC63">Nonterminal Symbols</A>. <DT><CODE>%union</CODE> <DD> Bison declaration to specify several possible data types for semantic -values. See section <A HREF="bison.html#SEC61">The Collection of Value Types</A>. +values. See section <A HREF="bison.html#SEC62">The Collection of Value Types</A>. </DL> <P> @@ -6442,14 +7482,14 @@ <DT><SAMP>`%%'</SAMP> <DD> Delimiter used to separate the grammar rule section from the -Bison declarations section or the additional C code section. -See section <A HREF="bison.html#SEC15">The Overall Layout of a Bison Grammar</A>. +Bison declarations section or the epilogue. +See section <A HREF="bison.html#SEC16">The Overall Layout of a Bison Grammar</A>. <DT><SAMP>`%{ %}'</SAMP> <DD> All code listed between <SAMP>`%{'</SAMP> and <SAMP>`%}'</SAMP> is copied directly to -the output file uninterpreted. Such code forms the "C declarations" -section of the input file. See section <A HREF="bison.html#SEC40">Outline of a Bison Grammar</A>. +the output file uninterpreted. Such code forms the prologue of the input +file. See section <A HREF="bison.html#SEC41">Outline of a Bison Grammar</A>. <DT><SAMP>`/*...*/'</SAMP> <DD> @@ -6457,23 +7497,23 @@ <DT><SAMP>`:'</SAMP> <DD> -Separates a rule's result from its components. See section <A HREF="bison.html#SEC46">Syntax of Grammar Rules</A>. +Separates a rule's result from its components. See section <A HREF="bison.html#SEC47">Syntax of Grammar Rules</A>. <DT><SAMP>`;'</SAMP> <DD> -Terminates a rule. See section <A HREF="bison.html#SEC46">Syntax of Grammar Rules</A>. +Terminates a rule. See section <A HREF="bison.html#SEC47">Syntax of Grammar Rules</A>. <DT><SAMP>`|'</SAMP> <DD> Separates alternate rules for the same result nonterminal. -See section <A HREF="bison.html#SEC46">Syntax of Grammar Rules</A>. +See section <A HREF="bison.html#SEC47">Syntax of Grammar Rules</A>. </DL> -<H1><A NAME="SEC102" HREF="bison_toc.html#TOC102">Glossary</A></H1> +<H1><A NAME="SEC107" HREF="bison_toc.html#TOC107">Glossary</A></H1> <P> -<A NAME="IDX219"></A> +<A NAME="IDX249"></A> <DL COMPACT> @@ -6507,7 +7547,15 @@ machine moves from state to state as specified by the logic of the machine. In the case of the parser, the input is the language being parsed, and the states correspond to various stages in the grammar -rules. See section <A HREF="bison.html#SEC77">The Bison Parser Algorithm</A>. +rules. See section <A HREF="bison.html#SEC78">The Bison Parser Algorithm</A>. + +<DT>Generalized LR (GLR) +<DD> +A parsing algorithm that can handle all context-free grammars, including those +that are not LALR(1). It resolves situations that Bison's usual LALR(1) +algorithm cannot by effectively splitting off multiple parsers, trying all +possible parsers, and discarding those that fail in the light of additional +right context. See section <A HREF="bison.html#SEC90">Generalized LR (GLR) Parsing</A>. <DT>Grouping <DD> @@ -6534,40 +7582,40 @@ <DD> Operators having left associativity are analyzed from left to right: <SAMP>`a+b+c'</SAMP> first computes <SAMP>`a+b'</SAMP> and then combines with -<SAMP>`c'</SAMP>. See section <A HREF="bison.html#SEC80">Operator Precedence</A>. +<SAMP>`c'</SAMP>. See section <A HREF="bison.html#SEC81">Operator Precedence</A>. <DT>Left recursion <DD> A rule whose result symbol is also its first component symbol; for -example, <SAMP>`expseq1 : expseq1 ',' exp;'</SAMP>. See section <A HREF="bison.html#SEC47">Recursive Rules</A>. +example, <SAMP>`expseq1 : expseq1 ',' exp;'</SAMP>. See section <A HREF="bison.html#SEC48">Recursive Rules</A>. <DT>Left-to-right parsing <DD> Parsing a sentence of a language by analyzing it token by token from -left to right. See section <A HREF="bison.html#SEC77">The Bison Parser Algorithm</A>. +left to right. See section <A HREF="bison.html#SEC78">The Bison Parser Algorithm</A>. <DT>Lexical analyzer (scanner) <DD> A function that reads an input stream and returns tokens one by one. -See section <A HREF="bison.html#SEC70">The Lexical Analyzer Function <CODE>yylex</CODE></A>. +See section <A HREF="bison.html#SEC71">The Lexical Analyzer Function <CODE>yylex</CODE></A>. <DT>Lexical tie-in <DD> A flag, set by actions in the grammar rules, which alters the way -tokens are parsed. See section <A HREF="bison.html#SEC93">Lexical Tie-ins</A>. +tokens are parsed. See section <A HREF="bison.html#SEC95">Lexical Tie-ins</A>. <DT>Literal string token <DD> -A token which consists of two or more fixed characters. See section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>. +A token which consists of two or more fixed characters. See section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>. <DT>Look-ahead token <DD> -A token already read but not yet shifted. See section <A HREF="bison.html#SEC78">Look-Ahead Tokens</A>. +A token already read but not yet shifted. See section <A HREF="bison.html#SEC79">Look-Ahead Tokens</A>. <DT>LALR(1) <DD> The class of context-free grammars that Bison (like most other parser -generators) can handle; a subset of LR(1). See section <A HREF="bison.html#SEC88">Mysterious Reduce/Reduce Conflicts</A>. +generators) can handle; a subset of LR(1). See section <A HREF="bison.html#SEC89">Mysterious Reduce/Reduce Conflicts</A>. <DT>LR(1) <DD> @@ -6578,12 +7626,12 @@ <DD> A grammar symbol standing for a grammatical construct that can be expressed through rules in terms of smaller constructs; in other -words, a construct that is not a token. See section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>. +words, a construct that is not a token. See section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>. <DT>Parse error <DD> An error encountered during parsing of an input stream due to invalid -syntax. See section <A HREF="bison.html#SEC90">Error Recovery</A>. +syntax. See section <A HREF="bison.html#SEC92">Error Recovery</A>. <DT>Parser <DD> @@ -6599,13 +7647,13 @@ <DT>Reduction <DD> Replacing a string of nonterminals and/or terminals with a single -nonterminal, according to a grammar rule. See section <A HREF="bison.html#SEC77">The Bison Parser Algorithm</A>. +nonterminal, according to a grammar rule. See section <A HREF="bison.html#SEC78">The Bison Parser Algorithm</A>. <DT>Reentrant <DD> A reentrant subprogram is a subprogram which can be in invoked any number of times in parallel, without interference between the various -invocations. See section <A HREF="bison.html#SEC65">A Pure (Reentrant) Parser</A>. +invocations. See section <A HREF="bison.html#SEC66">A Pure (Reentrant) Parser</A>. <DT>Reverse polish notation <DD> @@ -6614,19 +7662,19 @@ <DT>Right recursion <DD> A rule whose result symbol is also its last component symbol; for -example, <SAMP>`expseq1: exp ',' expseq1;'</SAMP>. See section <A HREF="bison.html#SEC47">Recursive Rules</A>. +example, <SAMP>`expseq1: exp ',' expseq1;'</SAMP>. See section <A HREF="bison.html#SEC48">Recursive Rules</A>. <DT>Semantics <DD> In computer languages, the semantics are specified by the actions taken for each instance of the language, i.e., the meaning of -each statement. See section <A HREF="bison.html#SEC48">Defining Language Semantics</A>. +each statement. See section <A HREF="bison.html#SEC49">Defining Language Semantics</A>. <DT>Shift <DD> A parser is said to shift when it makes the choice of analyzing further input from the stream rather than reducing immediately some -already-recognized rule. See section <A HREF="bison.html#SEC77">The Bison Parser Algorithm</A>. +already-recognized rule. See section <A HREF="bison.html#SEC78">The Bison Parser Algorithm</A>. <DT>Single-character literal <DD> @@ -6638,20 +7686,20 @@ The nonterminal symbol that stands for a complete valid utterance in the language being parsed. The start symbol is usually listed as the first nonterminal symbol in a language specification. -See section <A HREF="bison.html#SEC64">The Start-Symbol</A>. +See section <A HREF="bison.html#SEC65">The Start-Symbol</A>. <DT>Symbol table <DD> A data structure where symbol names and associated data are stored during parsing to allow for recognition and use of existing -information in repeated uses of a symbol. See section <A HREF="bison.html#SEC34">Multi-Function Calculator: <CODE>mfcalc</CODE></A>. +information in repeated uses of a symbol. See section <A HREF="bison.html#SEC35">Multi-Function Calculator: <CODE>mfcalc</CODE></A>. <DT>Token <DD> A basic, grammatically indivisible unit of a language. The symbol that describes a token in the grammar is a terminal symbol. The input of the Bison parser is a stream of tokens which comes from -the lexical analyzer. See section <A HREF="bison.html#SEC45">Symbols, Terminal and Nonterminal</A>. +the lexical analyzer. See section <A HREF="bison.html#SEC46">Symbols, Terminal and Nonterminal</A>. <DT>Terminal symbol <DD> @@ -6662,14 +7710,14 @@ -<H1><A NAME="SEC103" HREF="bison_toc.html#TOC103">Copying This Manual</A></H1> +<H1><A NAME="SEC108" HREF="bison_toc.html#TOC108">Copying This Manual</A></H1> -<H2><A NAME="SEC104" HREF="bison_toc.html#TOC104">GNU Free Documentation License</A></H2> +<H2><A NAME="SEC109" HREF="bison_toc.html#TOC109">GNU Free Documentation License</A></H2> <P> -<A NAME="IDX220"></A> +<A NAME="IDX250"></A> Version 1.1, March 2000 @@ -7065,7 +8113,7 @@ -<H3><A NAME="SEC105" HREF="bison_toc.html#TOC105">ADDENDUM: How to use this License for your documents</A></H3> +<H3><A NAME="SEC110" HREF="bison_toc.html#TOC110">ADDENDUM: How to use this License for your documents</A></H3> <P> To use this License in a document you have written, include a copy of @@ -7101,7 +8149,7 @@ -<H1><A NAME="SEC106" HREF="bison_toc.html#TOC106">Index</A></H1> +<H1><A NAME="SEC111" HREF="bison_toc.html#TOC111">Index</A></H1> <P> Jump to: @@ -7127,6 +8175,8 @@ - <A HREF="#cindex_i">i</A> - +<A HREF="#cindex_k">k</A> +- <A HREF="#cindex_l">l</A> - <A HREF="#cindex_m">m</A> @@ -7137,6 +8187,8 @@ - <A HREF="#cindex_p">p</A> - +<A HREF="#cindex_q">q</A> +- <A HREF="#cindex_r">r</A> - <A HREF="#cindex_s">s</A> @@ -7155,295 +8207,322 @@ <P> <H2><A NAME="cindex_$">$</A></H2> <DIR> -<LI><A HREF="bison.html#IDX89">$$</A> -<LI><A HREF="bison.html#IDX90">$<VAR>n</VAR></A> +<LI><A HREF="bison.html#IDX102">$$</A> +<LI><A HREF="bison.html#IDX103">$<VAR>n</VAR></A> </DIR> <H2><A NAME="cindex_%">%</A></H2> <DIR> -<LI><A HREF="bison.html#IDX125">%expect</A> -<LI><A HREF="bison.html#IDX176">%left</A> -<LI><A HREF="bison.html#IDX178">%nonassoc</A> -<LI><A HREF="bison.html#IDX183">%prec</A> -<LI><A HREF="bison.html#IDX132">%pure_parser</A> -<LI><A HREF="bison.html#IDX177">%right</A> -<LI><A HREF="bison.html#IDX129">%start</A> -<LI><A HREF="bison.html#IDX111">%token</A> -<LI><A HREF="bison.html#IDX120">%type</A> -<LI><A HREF="bison.html#IDX117">%union</A> +<LI><A HREF="bison.html#IDX238">%debug</A> +<LI><A HREF="bison.html#IDX138">%expect</A> +<LI><A HREF="bison.html#IDX26">%glr-parser</A> +<LI><A HREF="bison.html#IDX189">%left</A> +<LI><A HREF="bison.html#IDX191">%nonassoc</A> +<LI><A HREF="bison.html#IDX196">%prec</A> +<LI><A HREF="bison.html#IDX145">%pure-parser</A> +<LI><A HREF="bison.html#IDX190">%right</A> +<LI><A HREF="bison.html#IDX142">%start</A> +<LI><A HREF="bison.html#IDX124">%token</A> +<LI><A HREF="bison.html#IDX133">%type</A> +<LI><A HREF="bison.html#IDX130">%union</A> </DIR> <H2><A NAME="cindex_@">@</A></H2> <DIR> -<LI><A HREF="bison.html#IDX103">@$</A>, <A HREF="bison.html#IDX159">@$</A> -<LI><A HREF="bison.html#IDX104">@<VAR>n</VAR></A>, <A HREF="bison.html#IDX160">@<VAR>n</VAR></A> +<LI><A HREF="bison.html#IDX116">@$</A>, <A HREF="bison.html#IDX172">@$</A> +<LI><A HREF="bison.html#IDX117">@<VAR>n</VAR></A>, <A HREF="bison.html#IDX173">@<VAR>n</VAR></A> </DIR> <H2><A NAME="cindex_a">a</A></H2> <DIR> -<LI><A HREF="bison.html#IDX88">action</A> -<LI><A HREF="bison.html#IDX92">action data types</A> -<LI><A HREF="bison.html#IDX155">action features summary</A> -<LI><A HREF="bison.html#IDX94">actions in mid-rule</A> -<LI><A HREF="bison.html#IDX102">actions, location</A> -<LI><A HREF="bison.html#IDX17">actions, semantic</A> -<LI><A HREF="bison.html#IDX62">additional C code section</A> -<LI><A HREF="bison.html#IDX162">algorithm of parser</A> -<LI><A HREF="bison.html#IDX175">associativity</A> +<LI><A HREF="bison.html#IDX101">action</A> +<LI><A HREF="bison.html#IDX105">action data types</A> +<LI><A HREF="bison.html#IDX168">action features summary</A> +<LI><A HREF="bison.html#IDX107">actions in mid-rule</A> +<LI><A HREF="bison.html#IDX115">actions, location</A> +<LI><A HREF="bison.html#IDX23">actions, semantic</A> +<LI><A HREF="bison.html#IDX74">additional C code section</A> +<LI><A HREF="bison.html#IDX175">algorithm of parser</A> +<LI><A HREF="bison.html#IDX10">ambiguous grammars</A>, <A HREF="bison.html#IDX206">ambiguous grammars</A> +<LI><A HREF="bison.html#IDX188">associativity</A> </DIR> <H2><A NAME="cindex_b">b</A></H2> <DIR> <LI><A HREF="bison.html#IDX5">Backus-Naur form</A> -<LI><A HREF="bison.html#IDX133">Bison declaration summary</A> -<LI><A HREF="bison.html#IDX107">Bison declarations</A> -<LI><A HREF="bison.html#IDX58">Bison declarations (introduction)</A> -<LI><A HREF="bison.html#IDX11">Bison grammar</A> -<LI><A HREF="bison.html#IDX210">Bison invocation</A> -<LI><A HREF="bison.html#IDX21">Bison parser</A> -<LI><A HREF="bison.html#IDX161">Bison parser algorithm</A> -<LI><A HREF="bison.html#IDX217">Bison symbols, table of</A> -<LI><A HREF="bison.html#IDX22">Bison utility</A> -<LI><A HREF="bison.html#IDX213">BISON_HAIRY</A> -<LI><A HREF="bison.html#IDX214">BISON_SIMPLE</A> +<LI><A HREF="bison.html#IDX146">Bison declaration summary</A> +<LI><A HREF="bison.html#IDX120">Bison declarations</A> +<LI><A HREF="bison.html#IDX70">Bison declarations (introduction)</A> +<LI><A HREF="bison.html#IDX17">Bison grammar</A> +<LI><A HREF="bison.html#IDX241">Bison invocation</A> +<LI><A HREF="bison.html#IDX32">Bison parser</A> +<LI><A HREF="bison.html#IDX174">Bison parser algorithm</A> +<LI><A HREF="bison.html#IDX247">Bison symbols, table of</A> +<LI><A HREF="bison.html#IDX33">Bison utility</A> <LI><A HREF="bison.html#IDX4">BNF</A> </DIR> <H2><A NAME="cindex_c">c</A></H2> <DIR> -<LI><A HREF="bison.html#IDX63">C code, section for additional</A> -<LI><A HREF="bison.html#IDX56">C declarations section</A> -<LI><A HREF="bison.html#IDX136">C-language interface</A> -<LI><A HREF="bison.html#IDX45"><CODE>calc</CODE></A> -<LI><A HREF="bison.html#IDX46">calculator, infix notation</A> -<LI><A HREF="bison.html#IDX50">calculator, location tracking</A> -<LI><A HREF="bison.html#IDX53">calculator, multi-function</A> -<LI><A HREF="bison.html#IDX36">calculator, simple</A> -<LI><A HREF="bison.html#IDX68">character token</A> -<LI><A HREF="bison.html#IDX43">compiling the parser</A> -<LI><A HREF="bison.html#IDX169">conflicts</A> -<LI><A HREF="bison.html#IDX188">conflicts, reduce/reduce</A> -<LI><A HREF="bison.html#IDX124">conflicts, suppressing warnings of</A> -<LI><A HREF="bison.html#IDX179">context-dependent precedence</A> +<LI><A HREF="bison.html#IDX76">C code, section for additional</A> +<LI><A HREF="bison.html#IDX149">C-language interface</A> +<LI><A HREF="bison.html#IDX56"><CODE>calc</CODE></A> +<LI><A HREF="bison.html#IDX57">calculator, infix notation</A> +<LI><A HREF="bison.html#IDX61">calculator, location tracking</A> +<LI><A HREF="bison.html#IDX64">calculator, multi-function</A> +<LI><A HREF="bison.html#IDX47">calculator, simple</A> +<LI><A HREF="bison.html#IDX81">character token</A> +<LI><A HREF="bison.html#IDX54">compiling the parser</A> +<LI><A HREF="bison.html#IDX27">conflicts</A>, <A HREF="bison.html#IDX182">conflicts</A> +<LI><A HREF="bison.html#IDX201">conflicts, reduce/reduce</A> +<LI><A HREF="bison.html#IDX137">conflicts, suppressing warnings of</A> +<LI><A HREF="bison.html#IDX192">context-dependent precedence</A> <LI><A HREF="bison.html#IDX2">context-free grammar</A> -<LI><A HREF="bison.html#IDX39">controlling function</A> +<LI><A HREF="bison.html#IDX50">controlling function</A> +<LI><A HREF="bison.html#IDX230">core, item set</A> </DIR> <H2><A NAME="cindex_d">d</A></H2> <DIR> -<LI><A HREF="bison.html#IDX171">dangling <CODE>else</CODE></A> -<LI><A HREF="bison.html#IDX99">data type of locations</A> -<LI><A HREF="bison.html#IDX93">data types in actions</A> -<LI><A HREF="bison.html#IDX86">data types of semantic values</A> -<LI><A HREF="bison.html#IDX206">debugging</A> -<LI><A HREF="bison.html#IDX134">declaration summary</A> -<LI><A HREF="bison.html#IDX106">declarations, Bison</A> -<LI><A HREF="bison.html#IDX59">declarations, Bison (introduction)</A> -<LI><A HREF="bison.html#IDX57">declarations, C</A> -<LI><A HREF="bison.html#IDX110">declaring literal string tokens</A> -<LI><A HREF="bison.html#IDX113">declaring operator precedence</A> -<LI><A HREF="bison.html#IDX126">declaring the start symbol</A> -<LI><A HREF="bison.html#IDX108">declaring token type names</A> -<LI><A HREF="bison.html#IDX115">declaring value types</A> -<LI><A HREF="bison.html#IDX118">declaring value types, nonterminals</A> -<LI><A HREF="bison.html#IDX91">default action</A> -<LI><A HREF="bison.html#IDX87">default data type</A> -<LI><A HREF="bison.html#IDX100">default location type</A> -<LI><A HREF="bison.html#IDX195">default stack limit</A> -<LI><A HREF="bison.html#IDX128">default start symbol</A> -<LI><A HREF="bison.html#IDX82">defining language semantics</A> +<LI><A HREF="bison.html#IDX184">dangling <CODE>else</CODE></A> +<LI><A HREF="bison.html#IDX112">data type of locations</A> +<LI><A HREF="bison.html#IDX106">data types in actions</A> +<LI><A HREF="bison.html#IDX99">data types of semantic values</A> +<LI><A HREF="bison.html#IDX235">debugging</A> +<LI><A HREF="bison.html#IDX147">declaration summary</A> +<LI><A HREF="bison.html#IDX69">declarations</A> +<LI><A HREF="bison.html#IDX67">declarations section</A> +<LI><A HREF="bison.html#IDX119">declarations, Bison</A> +<LI><A HREF="bison.html#IDX71">declarations, Bison (introduction)</A> +<LI><A HREF="bison.html#IDX123">declaring literal string tokens</A> +<LI><A HREF="bison.html#IDX126">declaring operator precedence</A> +<LI><A HREF="bison.html#IDX139">declaring the start symbol</A> +<LI><A HREF="bison.html#IDX121">declaring token type names</A> +<LI><A HREF="bison.html#IDX128">declaring value types</A> +<LI><A HREF="bison.html#IDX131">declaring value types, nonterminals</A> +<LI><A HREF="bison.html#IDX104">default action</A> +<LI><A HREF="bison.html#IDX100">default data type</A> +<LI><A HREF="bison.html#IDX113">default location type</A> +<LI><A HREF="bison.html#IDX212">default stack limit</A> +<LI><A HREF="bison.html#IDX141">default start symbol</A> +<LI><A HREF="bison.html#IDX95">defining language semantics</A> </DIR> <H2><A NAME="cindex_e">e</A></H2> <DIR> -<LI><A HREF="bison.html#IDX172"><CODE>else</CODE>, dangling</A> -<LI><A HREF="bison.html#IDX212">environment variables</A> -<LI><A HREF="bison.html#IDX199">error</A> -<LI><A HREF="bison.html#IDX197">error recovery</A> -<LI><A HREF="bison.html#IDX47">error recovery, simple</A> -<LI><A HREF="bison.html#IDX148">error reporting function</A> -<LI><A HREF="bison.html#IDX41">error reporting routine</A> -<LI><A HREF="bison.html#IDX32">examples, simple</A> -<LI><A HREF="bison.html#IDX55">exercises</A> +<LI><A HREF="bison.html#IDX185"><CODE>else</CODE>, dangling</A> +<LI><A HREF="bison.html#IDX75">epilogue</A> +<LI><A HREF="bison.html#IDX216">error</A> +<LI><A HREF="bison.html#IDX214">error recovery</A> +<LI><A HREF="bison.html#IDX58">error recovery, simple</A> +<LI><A HREF="bison.html#IDX161">error reporting function</A> +<LI><A HREF="bison.html#IDX52">error reporting routine</A> +<LI><A HREF="bison.html#IDX43">examples, simple</A> +<LI><A HREF="bison.html#IDX66">exercises</A> </DIR> <H2><A NAME="cindex_f">f</A></H2> <DIR> -<LI><A HREF="bison.html#IDX220">FDL, GNU Free Documentation License</A> -<LI><A HREF="bison.html#IDX28">file format</A> -<LI><A HREF="bison.html#IDX184">finite-state machine</A> -<LI><A HREF="bison.html#IDX13">formal grammar</A> -<LI><A HREF="bison.html#IDX29">format of grammar file</A> +<LI><A HREF="bison.html#IDX250">FDL, GNU Free Documentation License</A> +<LI><A HREF="bison.html#IDX39">file format</A> +<LI><A HREF="bison.html#IDX197">finite-state machine</A> +<LI><A HREF="bison.html#IDX19">formal grammar</A> +<LI><A HREF="bison.html#IDX40">format of grammar file</A> +<LI><A HREF="bison.html#IDX245">frequently asked questions</A> </DIR> <H2><A NAME="cindex_g">g</A></H2> <DIR> -<LI><A HREF="bison.html#IDX219">glossary</A> -<LI><A HREF="bison.html#IDX27">grammar file</A> -<LI><A HREF="bison.html#IDX75">grammar rule syntax</A> -<LI><A HREF="bison.html#IDX60">grammar rules section</A> -<LI><A HREF="bison.html#IDX12">grammar, Bison</A> +<LI><A HREF="bison.html#IDX9">generalized LR (GLR) parsing</A>, <A HREF="bison.html#IDX25">generalized LR (GLR) parsing</A>, <A HREF="bison.html#IDX205">generalized LR (GLR) parsing</A> +<LI><A HREF="bison.html#IDX249">glossary</A> +<LI><A HREF="bison.html#IDX8">GLR parsing</A>, <A HREF="bison.html#IDX24">GLR parsing</A>, <A HREF="bison.html#IDX204">GLR parsing</A> +<LI><A HREF="bison.html#IDX38">grammar file</A> +<LI><A HREF="bison.html#IDX88">grammar rule syntax</A> +<LI><A HREF="bison.html#IDX72">grammar rules section</A> +<LI><A HREF="bison.html#IDX18">grammar, Bison</A> <LI><A HREF="bison.html#IDX3">grammar, context-free</A> -<LI><A HREF="bison.html#IDX9">grouping, syntactic</A> +<LI><A HREF="bison.html#IDX15">grouping, syntactic</A> </DIR> <H2><A NAME="cindex_i">i</A></H2> <DIR> -<LI><A HREF="bison.html#IDX44">infix notation calculator</A> -<LI><A HREF="bison.html#IDX137">interface</A> +<LI><A HREF="bison.html#IDX55">infix notation calculator</A> +<LI><A HREF="bison.html#IDX150">interface</A> <LI><A HREF="bison.html#IDX1">introduction</A> -<LI><A HREF="bison.html#IDX209">invoking Bison</A> -<LI><A HREF="bison.html#IDX215">invoking Bison under VMS</A> +<LI><A HREF="bison.html#IDX240">invoking Bison</A> +<LI><A HREF="bison.html#IDX243">invoking Bison under VMS</A> +<LI><A HREF="bison.html#IDX227">item</A> +<LI><A HREF="bison.html#IDX231">item set core</A>, <A HREF="bison.html#IDX233">item set core</A> +</DIR> +<H2><A NAME="cindex_k">k</A></H2> +<DIR> +<LI><A HREF="bison.html#IDX232">kernel, item set</A> </DIR> <H2><A NAME="cindex_l">l</A></H2> <DIR> -<LI><A HREF="bison.html#IDX190">LALR(1)</A> -<LI><A HREF="bison.html#IDX83">language semantics, defining</A> -<LI><A HREF="bison.html#IDX30">layout of Bison grammar</A> -<LI><A HREF="bison.html#IDX79">left recursion</A> -<LI><A HREF="bison.html#IDX142">lexical analyzer</A> -<LI><A HREF="bison.html#IDX23">lexical analyzer, purpose</A> -<LI><A HREF="bison.html#IDX38">lexical analyzer, writing</A> -<LI><A HREF="bison.html#IDX203">lexical tie-in</A> -<LI><A HREF="bison.html#IDX72">literal string token</A> -<LI><A HREF="bison.html#IDX69">literal token</A> -<LI><A HREF="bison.html#IDX18">location</A>, <A HREF="bison.html#IDX96">location</A> -<LI><A HREF="bison.html#IDX101">location actions</A> -<LI><A HREF="bison.html#IDX48">location tracking calculator</A> -<LI><A HREF="bison.html#IDX167">look-ahead token</A> -<LI><A HREF="bison.html#IDX189">LR(1)</A> -<LI><A HREF="bison.html#IDX49"><CODE>ltcalc</CODE></A> +<LI><A HREF="bison.html#IDX203">LALR(1)</A> +<LI><A HREF="bison.html#IDX6">LALR(1) grammars</A> +<LI><A HREF="bison.html#IDX96">language semantics, defining</A> +<LI><A HREF="bison.html#IDX41">layout of Bison grammar</A> +<LI><A HREF="bison.html#IDX92">left recursion</A> +<LI><A HREF="bison.html#IDX155">lexical analyzer</A> +<LI><A HREF="bison.html#IDX34">lexical analyzer, purpose</A> +<LI><A HREF="bison.html#IDX49">lexical analyzer, writing</A> +<LI><A HREF="bison.html#IDX220">lexical tie-in</A> +<LI><A HREF="bison.html#IDX85">literal string token</A> +<LI><A HREF="bison.html#IDX82">literal token</A> +<LI><A HREF="bison.html#IDX29">location</A>, <A HREF="bison.html#IDX109">location</A> +<LI><A HREF="bison.html#IDX114">location actions</A> +<LI><A HREF="bison.html#IDX59">location tracking calculator</A> +<LI><A HREF="bison.html#IDX180">look-ahead token</A> +<LI><A HREF="bison.html#IDX202">LR(1)</A> +<LI><A HREF="bison.html#IDX7">LR(1) grammars</A> +<LI><A HREF="bison.html#IDX60"><CODE>ltcalc</CODE></A> </DIR> <H2><A NAME="cindex_m">m</A></H2> <DIR> -<LI><A HREF="bison.html#IDX40">main function in simple example</A> -<LI><A HREF="bison.html#IDX52"><CODE>mfcalc</CODE></A> -<LI><A HREF="bison.html#IDX95">mid-rule actions</A> -<LI><A HREF="bison.html#IDX51">multi-function calculator</A> -<LI><A HREF="bison.html#IDX73">multicharacter literal</A> -<LI><A HREF="bison.html#IDX81">mutual recursion</A> +<LI><A HREF="bison.html#IDX51">main function in simple example</A> +<LI><A HREF="bison.html#IDX63"><CODE>mfcalc</CODE></A> +<LI><A HREF="bison.html#IDX108">mid-rule actions</A> +<LI><A HREF="bison.html#IDX62">multi-function calculator</A> +<LI><A HREF="bison.html#IDX86">multicharacter literal</A> +<LI><A HREF="bison.html#IDX94">mutual recursion</A> </DIR> <H2><A NAME="cindex_n">n</A></H2> <DIR> -<LI><A HREF="bison.html#IDX64">nonterminal symbol</A> +<LI><A HREF="bison.html#IDX11">non-deterministic parsing</A>, <A HREF="bison.html#IDX207">non-deterministic parsing</A> +<LI><A HREF="bison.html#IDX77">nonterminal symbol</A> +<LI><A HREF="bison.html#IDX223">nonterminal, useless</A> </DIR> <H2><A NAME="cindex_o">o</A></H2> <DIR> -<LI><A HREF="bison.html#IDX173">operator precedence</A> -<LI><A HREF="bison.html#IDX114">operator precedence, declaring</A> -<LI><A HREF="bison.html#IDX211">options for invoking Bison</A> -<LI><A HREF="bison.html#IDX193">overflow of parser stack</A> +<LI><A HREF="bison.html#IDX186">operator precedence</A> +<LI><A HREF="bison.html#IDX127">operator precedence, declaring</A> +<LI><A HREF="bison.html#IDX242">options for invoking Bison</A> +<LI><A HREF="bison.html#IDX210">overflow of parser stack</A> </DIR> <H2><A NAME="cindex_p">p</A></H2> <DIR> -<LI><A HREF="bison.html#IDX150">parse error</A> -<LI><A HREF="bison.html#IDX24">parser</A> -<LI><A HREF="bison.html#IDX165">parser stack</A> -<LI><A HREF="bison.html#IDX192">parser stack overflow</A> -<LI><A HREF="bison.html#IDX185">parser state</A> -<LI><A HREF="bison.html#IDX34">polish notation calculator</A> -<LI><A HREF="bison.html#IDX20">position, textual</A>, <A HREF="bison.html#IDX98">position, textual</A> -<LI><A HREF="bison.html#IDX112">precedence declarations</A> -<LI><A HREF="bison.html#IDX174">precedence of operators</A> -<LI><A HREF="bison.html#IDX181">precedence, context-dependent</A> -<LI><A HREF="bison.html#IDX182">precedence, unary operator</A> -<LI><A HREF="bison.html#IDX122">preventing warnings about conflicts</A> -<LI><A HREF="bison.html#IDX131">pure parser</A> +<LI><A HREF="bison.html#IDX163">parse error</A> +<LI><A HREF="bison.html#IDX35">parser</A> +<LI><A HREF="bison.html#IDX178">parser stack</A> +<LI><A HREF="bison.html#IDX209">parser stack overflow</A> +<LI><A HREF="bison.html#IDX198">parser state</A> +<LI><A HREF="bison.html#IDX228">pointed rule</A> +<LI><A HREF="bison.html#IDX45">polish notation calculator</A> +<LI><A HREF="bison.html#IDX31">position, textual</A>, <A HREF="bison.html#IDX111">position, textual</A> +<LI><A HREF="bison.html#IDX125">precedence declarations</A> +<LI><A HREF="bison.html#IDX187">precedence of operators</A> +<LI><A HREF="bison.html#IDX194">precedence, context-dependent</A> +<LI><A HREF="bison.html#IDX195">precedence, unary operator</A> +<LI><A HREF="bison.html#IDX135">preventing warnings about conflicts</A> +<LI><A HREF="bison.html#IDX68">Prologue</A> +<LI><A HREF="bison.html#IDX144">pure parser</A> +</DIR> +<H2><A NAME="cindex_q">q</A></H2> +<DIR> +<LI><A HREF="bison.html#IDX246">questions</A> </DIR> <H2><A NAME="cindex_r">r</A></H2> <DIR> -<LI><A HREF="bison.html#IDX198">recovery from errors</A> -<LI><A HREF="bison.html#IDX78">recursive rule</A> -<LI><A HREF="bison.html#IDX187">reduce/reduce conflict</A> -<LI><A HREF="bison.html#IDX164">reduction</A> -<LI><A HREF="bison.html#IDX130">reentrant parser</A> -<LI><A HREF="bison.html#IDX33">reverse polish notation</A> -<LI><A HREF="bison.html#IDX80">right recursion</A> -<LI><A HREF="bison.html#IDX35"><CODE>rpcalc</CODE></A> -<LI><A HREF="bison.html#IDX74">rule syntax</A> -<LI><A HREF="bison.html#IDX61">rules section for grammar</A> -<LI><A HREF="bison.html#IDX42">running Bison (introduction)</A> +<LI><A HREF="bison.html#IDX215">recovery from errors</A> +<LI><A HREF="bison.html#IDX91">recursive rule</A> +<LI><A HREF="bison.html#IDX200">reduce/reduce conflict</A> +<LI><A HREF="bison.html#IDX177">reduction</A> +<LI><A HREF="bison.html#IDX143">reentrant parser</A> +<LI><A HREF="bison.html#IDX44">reverse polish notation</A> +<LI><A HREF="bison.html#IDX93">right recursion</A> +<LI><A HREF="bison.html#IDX46"><CODE>rpcalc</CODE></A> +<LI><A HREF="bison.html#IDX87">rule syntax</A> +<LI><A HREF="bison.html#IDX229">rule, pointed</A> +<LI><A HREF="bison.html#IDX225">rule, useless</A> +<LI><A HREF="bison.html#IDX73">rules section for grammar</A> +<LI><A HREF="bison.html#IDX53">running Bison (introduction)</A> </DIR> <H2><A NAME="cindex_s">s</A></H2> <DIR> -<LI><A HREF="bison.html#IDX16">semantic actions</A> -<LI><A HREF="bison.html#IDX14">semantic value</A> -<LI><A HREF="bison.html#IDX84">semantic value type</A> -<LI><A HREF="bison.html#IDX170">shift/reduce conflicts</A> -<LI><A HREF="bison.html#IDX163">shifting</A> -<LI><A HREF="bison.html#IDX31">simple examples</A> -<LI><A HREF="bison.html#IDX70">single-character literal</A> -<LI><A HREF="bison.html#IDX191">stack overflow</A> -<LI><A HREF="bison.html#IDX166">stack, parser</A> -<LI><A HREF="bison.html#IDX25">stages in using Bison</A> -<LI><A HREF="bison.html#IDX10">start symbol</A> -<LI><A HREF="bison.html#IDX127">start symbol, declaring</A> -<LI><A HREF="bison.html#IDX186">state (of parser)</A> -<LI><A HREF="bison.html#IDX71">string token</A> -<LI><A HREF="bison.html#IDX154">summary, action features</A> -<LI><A HREF="bison.html#IDX135">summary, Bison declaration</A> -<LI><A HREF="bison.html#IDX121">suppressing conflict warnings</A> -<LI><A HREF="bison.html#IDX67">symbol</A> -<LI><A HREF="bison.html#IDX54">symbol table example</A> -<LI><A HREF="bison.html#IDX6">symbols (abstract)</A> -<LI><A HREF="bison.html#IDX218">symbols in Bison, table of</A> -<LI><A HREF="bison.html#IDX8">syntactic grouping</A> -<LI><A HREF="bison.html#IDX151">syntax error</A> -<LI><A HREF="bison.html#IDX76">syntax of grammar rules</A> +<LI><A HREF="bison.html#IDX22">semantic actions</A> +<LI><A HREF="bison.html#IDX20">semantic value</A> +<LI><A HREF="bison.html#IDX97">semantic value type</A> +<LI><A HREF="bison.html#IDX28">shift/reduce conflicts</A>, <A HREF="bison.html#IDX183">shift/reduce conflicts</A> +<LI><A HREF="bison.html#IDX176">shifting</A> +<LI><A HREF="bison.html#IDX42">simple examples</A> +<LI><A HREF="bison.html#IDX83">single-character literal</A> +<LI><A HREF="bison.html#IDX208">stack overflow</A> +<LI><A HREF="bison.html#IDX179">stack, parser</A> +<LI><A HREF="bison.html#IDX36">stages in using Bison</A> +<LI><A HREF="bison.html#IDX16">start symbol</A> +<LI><A HREF="bison.html#IDX140">start symbol, declaring</A> +<LI><A HREF="bison.html#IDX199">state (of parser)</A> +<LI><A HREF="bison.html#IDX84">string token</A> +<LI><A HREF="bison.html#IDX167">summary, action features</A> +<LI><A HREF="bison.html#IDX148">summary, Bison declaration</A> +<LI><A HREF="bison.html#IDX134">suppressing conflict warnings</A> +<LI><A HREF="bison.html#IDX80">symbol</A> +<LI><A HREF="bison.html#IDX65">symbol table example</A> +<LI><A HREF="bison.html#IDX12">symbols (abstract)</A> +<LI><A HREF="bison.html#IDX248">symbols in Bison, table of</A> +<LI><A HREF="bison.html#IDX14">syntactic grouping</A> +<LI><A HREF="bison.html#IDX164">syntax error</A> +<LI><A HREF="bison.html#IDX89">syntax of grammar rules</A> </DIR> <H2><A NAME="cindex_t">t</A></H2> <DIR> -<LI><A HREF="bison.html#IDX65">terminal symbol</A> -<LI><A HREF="bison.html#IDX19">textual position</A>, <A HREF="bison.html#IDX97">textual position</A> -<LI><A HREF="bison.html#IDX7">token</A> -<LI><A HREF="bison.html#IDX66">token type</A> -<LI><A HREF="bison.html#IDX109">token type names, declaring</A> -<LI><A HREF="bison.html#IDX207">tracing the parser</A> +<LI><A HREF="bison.html#IDX78">terminal symbol</A> +<LI><A HREF="bison.html#IDX30">textual position</A>, <A HREF="bison.html#IDX110">textual position</A> +<LI><A HREF="bison.html#IDX13">token</A> +<LI><A HREF="bison.html#IDX79">token type</A> +<LI><A HREF="bison.html#IDX122">token type names, declaring</A> +<LI><A HREF="bison.html#IDX221">token, useless</A> +<LI><A HREF="bison.html#IDX236">tracing the parser</A> </DIR> <H2><A NAME="cindex_u">u</A></H2> <DIR> -<LI><A HREF="bison.html#IDX180">unary operator precedence</A> -<LI><A HREF="bison.html#IDX26">using Bison</A> +<LI><A HREF="bison.html#IDX193">unary operator precedence</A> +<LI><A HREF="bison.html#IDX224">useless nonterminal</A> +<LI><A HREF="bison.html#IDX226">useless rule</A> +<LI><A HREF="bison.html#IDX222">useless token</A> +<LI><A HREF="bison.html#IDX37">using Bison</A> </DIR> <H2><A NAME="cindex_v">v</A></H2> <DIR> -<LI><A HREF="bison.html#IDX85">value type, semantic</A> -<LI><A HREF="bison.html#IDX116">value types, declaring</A> -<LI><A HREF="bison.html#IDX119">value types, nonterminals, declaring</A> -<LI><A HREF="bison.html#IDX15">value, semantic</A> -<LI><A HREF="bison.html#IDX216">VMS</A> +<LI><A HREF="bison.html#IDX98">value type, semantic</A> +<LI><A HREF="bison.html#IDX129">value types, declaring</A> +<LI><A HREF="bison.html#IDX132">value types, nonterminals, declaring</A> +<LI><A HREF="bison.html#IDX21">value, semantic</A> +<LI><A HREF="bison.html#IDX244">VMS</A> </DIR> <H2><A NAME="cindex_w">w</A></H2> <DIR> -<LI><A HREF="bison.html#IDX123">warnings, preventing</A> -<LI><A HREF="bison.html#IDX37">writing a lexical analyzer</A> +<LI><A HREF="bison.html#IDX136">warnings, preventing</A> +<LI><A HREF="bison.html#IDX48">writing a lexical analyzer</A> </DIR> <H2><A NAME="cindex_y">y</A></H2> <DIR> -<LI><A HREF="bison.html#IDX140">YYABORT</A> -<LI><A HREF="bison.html#IDX139">YYACCEPT</A> -<LI><A HREF="bison.html#IDX156">YYBACKUP</A> -<LI><A HREF="bison.html#IDX168">yychar</A> -<LI><A HREF="bison.html#IDX201">yyclearin</A> -<LI><A HREF="bison.html#IDX204">YYDEBUG</A> -<LI><A HREF="bison.html#IDX205">yydebug</A> -<LI><A HREF="bison.html#IDX157">YYEMPTY</A> -<LI><A HREF="bison.html#IDX200">yyerrok</A> -<LI><A HREF="bison.html#IDX158">YYERROR</A> -<LI><A HREF="bison.html#IDX149">yyerror</A> -<LI><A HREF="bison.html#IDX152">YYERROR_VERBOSE</A> -<LI><A HREF="bison.html#IDX196">YYINITDEPTH</A> -<LI><A HREF="bison.html#IDX141">yylex</A> -<LI><A HREF="bison.html#IDX147">YYLEX_PARAM</A> -<LI><A HREF="bison.html#IDX144">yylloc</A> -<LI><A HREF="bison.html#IDX105">YYLLOC_DEFAULT</A> -<LI><A HREF="bison.html#IDX145">YYLTYPE</A> -<LI><A HREF="bison.html#IDX143">yylval</A> -<LI><A HREF="bison.html#IDX194">YYMAXDEPTH</A> -<LI><A HREF="bison.html#IDX153">yynerrs</A> -<LI><A HREF="bison.html#IDX138">yyparse</A> -<LI><A HREF="bison.html#IDX146">YYPARSE_PARAM</A> -<LI><A HREF="bison.html#IDX208">YYPRINT</A> -<LI><A HREF="bison.html#IDX202">YYRECOVERING</A> +<LI><A HREF="bison.html#IDX153">YYABORT</A> +<LI><A HREF="bison.html#IDX152">YYACCEPT</A> +<LI><A HREF="bison.html#IDX169">YYBACKUP</A> +<LI><A HREF="bison.html#IDX181">yychar</A> +<LI><A HREF="bison.html#IDX218">yyclearin</A> +<LI><A HREF="bison.html#IDX234">yydebug</A> +<LI><A HREF="bison.html#IDX237">YYDEBUG</A> +<LI><A HREF="bison.html#IDX170">YYEMPTY</A> +<LI><A HREF="bison.html#IDX217">yyerrok</A> +<LI><A HREF="bison.html#IDX162">yyerror</A> +<LI><A HREF="bison.html#IDX171">YYERROR</A> +<LI><A HREF="bison.html#IDX165">YYERROR_VERBOSE</A> +<LI><A HREF="bison.html#IDX213">YYINITDEPTH</A> +<LI><A HREF="bison.html#IDX154">yylex</A> +<LI><A HREF="bison.html#IDX160">YYLEX_PARAM</A> +<LI><A HREF="bison.html#IDX157">yylloc</A> +<LI><A HREF="bison.html#IDX118">YYLLOC_DEFAULT</A> +<LI><A HREF="bison.html#IDX158">YYLTYPE</A> +<LI><A HREF="bison.html#IDX156">yylval</A> +<LI><A HREF="bison.html#IDX211">YYMAXDEPTH</A> +<LI><A HREF="bison.html#IDX166">yynerrs</A> +<LI><A HREF="bison.html#IDX151">yyparse</A> +<LI><A HREF="bison.html#IDX159">YYPARSE_PARAM</A> +<LI><A HREF="bison.html#IDX239">YYPRINT</A> +<LI><A HREF="bison.html#IDX219">YYRECOVERING</A> </DIR> <H2><A NAME="cindex_|">|</A></H2> <DIR> -<LI><A HREF="bison.html#IDX77">|</A> +<LI><A HREF="bison.html#IDX90">|</A> </DIR> <P><HR><P> -This document was generated on 4 November 2001 using +This document was generated on 9 November 2002 using <A HREF="http://wwwinfo.cern.ch/dis/texi2html/">texi2html</A> 1.56k. </BODY> </HTML>

OSSP CVS Repository