X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/0ae99356d5909eb937ad89c2f3473eb2bd4688b0..fa7e68c39761e0ac0f345e7ab6127de3e7604ab7:/doc/bison.texinfo diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 536b2cba..41d13a7a 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -16,6 +16,10 @@ @c @clear shorttitlepage-enabled @c @set shorttitlepage-enabled +@c Set following if you want to document %default-prec and %no-default-prec. +@c This feature is experimental and may change in future Bison versions. +@c @set defaultprec + @c ISPELL CHECK: done, 14 Jan 1993 --bob @c Check COPYRIGHT dates. should be updated in the titlepage, ifinfo @@ -40,7 +44,7 @@ This manual is for @acronym{GNU} Bison (version @value{VERSION}, @value{UPDATED}), the @acronym{GNU} parser generator. Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, -1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc. +1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. @quotation Permission is granted to copy, distribute and/or modify this document @@ -131,13 +135,19 @@ The Concepts of Bison a semantic value (the value of an integer, the name of an identifier, etc.). * Semantic Actions:: Each rule can have an action containing C code. -* GLR Parsers:: Writing parsers for general context-free languages +* GLR Parsers:: Writing parsers for general context-free languages. * Locations Overview:: Tracking Locations. * Bison Parser:: What are Bison's input and output, how is the output used? * Stages:: Stages in writing and running Bison grammars. * Grammar Layout:: Overall structure of a Bison grammar file. +Writing @acronym{GLR} Parsers + +* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars +* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities +* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler + Examples * RPN Calc:: Reverse polish notation calculator; @@ -219,7 +229,7 @@ Bison Declarations * Union Decl:: Declaring the set of all semantic value types. * Type Decl:: Declaring the choice of type for a nonterminal symbol. * Destructor Decl:: Declaring how symbols are freed. -* Expect Decl:: Suppressing warnings about shift/reduce conflicts. +* Expect Decl:: Suppressing warnings about parsing conflicts. * Start Decl:: Specifying the start symbol. * Pure Decl:: Requesting a reentrant parser. * Decl Summary:: Table of all Bison declarations. @@ -352,7 +362,7 @@ encourage people to make other software free. So we decided to make the practical conditions for using Bison match the practical conditions for using the other @acronym{GNU} tools. -This exception applies only when Bison is generating C code for a +This exception applies only when Bison is generating C code for an @acronym{LALR}(1) parser; otherwise, the @acronym{GPL} terms operate as usual. You can tell whether the exception applies to your @samp{.c} output file by @@ -377,7 +387,7 @@ use Bison or Yacc, we suggest you start by reading this chapter carefully. a semantic value (the value of an integer, the name of an identifier, etc.). * Semantic Actions:: Each rule can have an action containing C code. -* GLR Parsers:: Writing parsers for general context-free languages +* GLR Parsers:: Writing parsers for general context-free languages. * Locations Overview:: Tracking Locations. * Bison Parser:: What are Bison's input and output, how is the output used? @@ -655,8 +665,9 @@ from the values of the two subexpressions. @findex %glr-parser @cindex conflicts @cindex shift/reduce conflicts +@cindex reduce/reduce conflicts -In some grammars, there will be cases where Bison's standard +In some grammars, Bison's standard @acronym{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 @@ -669,7 +680,7 @@ input. These are known respectively as @dfn{reduce/reduce} conflicts To use a grammar that is not easily modified to be @acronym{LALR}(1), a more general parsing algorithm is sometimes necessary. If you include @code{%glr-parser} among the Bison declarations in your file -(@pxref{Grammar Outline}), the result will be a Generalized @acronym{LR} +(@pxref{Grammar Outline}), the result is a Generalized @acronym{LR} (@acronym{GLR}) parser. These parsers handle Bison grammars that contain no unresolved conflicts (i.e., after applying precedence declarations) identically to @acronym{LALR}(1) parsers. However, when @@ -696,6 +707,217 @@ involved, or by performing both actions, and then calling a designated user-defined function on the resulting values to produce an arbitrary merged result. +@menu +* Simple GLR Parsers:: Using @acronym{GLR} parsers on unambiguous grammars +* Merging GLR Parses:: Using @acronym{GLR} parsers to resolve ambiguities +* Compiler Requirements:: @acronym{GLR} parsers require a modern C compiler +@end menu + +@node Simple GLR Parsers +@subsection Using @acronym{GLR} on Unambiguous Grammars +@cindex @acronym{GLR} parsing, unambiguous grammars +@cindex generalized @acronym{LR} (@acronym{GLR}) parsing, unambiguous grammars +@findex %glr-parser +@findex %expect-rr +@cindex conflicts +@cindex reduce/reduce conflicts +@cindex shift/reduce conflicts + +In the simplest cases, you can use the @acronym{GLR} algorithm +to parse grammars that are unambiguous, but fail to be @acronym{LALR}(1). +Such grammars typically require more than one symbol of look-ahead, +or (in rare cases) fall into the category of grammars in which the +@acronym{LALR}(1) algorithm throws away too much information (they are in +@acronym{LR}(1), but not @acronym{LALR}(1), @ref{Mystery Conflicts}). + +Consider a problem that +arises in the declaration of enumerated and subrange types in the +programming language Pascal. Here are some examples: + +@example +type subrange = lo .. hi; +type enum = (a, b, c); +@end example + +@noindent +The original language standard allows only numeric +literals and constant identifiers for the subrange bounds (@samp{lo} +and @samp{hi}), but Extended Pascal (@acronym{ISO}/@acronym{IEC} +10206) and many other +Pascal implementations allow arbitrary expressions there. This gives +rise to the following situation, containing a superfluous pair of +parentheses: + +@example +type subrange = (a) .. b; +@end example + +@noindent +Compare this to the following declaration of an enumerated +type with only one value: + +@example +type enum = (a); +@end example + +@noindent +(These declarations are contrived, but they are syntactically +valid, and more-complicated cases can come up in practical programs.) + +These two declarations look identical until the @samp{..} token. +With normal @acronym{LALR}(1) one-token look-ahead it is not +possible to decide between the two forms when the identifier +@samp{a} is parsed. It is, however, desirable +for a parser to decide this, since in the latter case +@samp{a} must become a new identifier to represent the enumeration +value, while in the former case @samp{a} must be evaluated with its +current meaning, which may be a constant or even a function call. + +You could parse @samp{(a)} as an ``unspecified identifier in parentheses'', +to be resolved later, but this typically requires substantial +contortions in both semantic actions and large parts of the +grammar, where the parentheses are nested in the recursive rules for +expressions. + +You might think of using the lexer to distinguish between the two +forms by returning different tokens for currently defined and +undefined identifiers. But if these declarations occur in a local +scope, and @samp{a} is defined in an outer scope, then both forms +are possible---either locally redefining @samp{a}, or using the +value of @samp{a} from the outer scope. So this approach cannot +work. + +A simple solution to this problem is to declare the parser to +use the @acronym{GLR} algorithm. +When the @acronym{GLR} parser reaches the critical state, it +merely splits into two branches and pursues both syntax rules +simultaneously. Sooner or later, one of them runs into a parsing +error. If there is a @samp{..} token before the next +@samp{;}, the rule for enumerated types fails since it cannot +accept @samp{..} anywhere; otherwise, the subrange type rule +fails since it requires a @samp{..} token. So one of the branches +fails silently, and the other one continues normally, performing +all the intermediate actions that were postponed during the split. + +If the input is syntactically incorrect, both branches fail and the parser +reports a syntax error as usual. + +The effect of all this is that the parser seems to ``guess'' the +correct branch to take, or in other words, it seems to use more +look-ahead than the underlying @acronym{LALR}(1) algorithm actually allows +for. In this example, @acronym{LALR}(2) would suffice, but also some cases +that are not @acronym{LALR}(@math{k}) for any @math{k} can be handled this way. + +In general, a @acronym{GLR} parser can take quadratic or cubic worst-case time, +and the current Bison parser even takes exponential time and space +for some grammars. In practice, this rarely happens, and for many +grammars it is possible to prove that it cannot happen. +The present example contains only one conflict between two +rules, and the type-declaration context containing the conflict +cannot be nested. So the number of +branches that can exist at any time is limited by the constant 2, +and the parsing time is still linear. + +Here is a Bison grammar corresponding to the example above. It +parses a vastly simplified form of Pascal type declarations. + +@example +%token TYPE DOTDOT ID + +@group +%left '+' '-' +%left '*' '/' +@end group + +%% + +@group +type_decl : TYPE ID '=' type ';' + ; +@end group + +@group +type : '(' id_list ')' + | expr DOTDOT expr + ; +@end group + +@group +id_list : ID + | id_list ',' ID + ; +@end group + +@group +expr : '(' expr ')' + | expr '+' expr + | expr '-' expr + | expr '*' expr + | expr '/' expr + | ID + ; +@end group +@end example + +When used as a normal @acronym{LALR}(1) grammar, Bison correctly complains +about one reduce/reduce conflict. In the conflicting situation the +parser chooses one of the alternatives, arbitrarily the one +declared first. Therefore the following correct input is not +recognized: + +@example +type t = (a) .. b; +@end example + +The parser can be turned into a @acronym{GLR} parser, while also telling Bison +to be silent about the one known reduce/reduce conflict, by +adding these two declarations to the Bison input file (before the first +@samp{%%}): + +@example +%glr-parser +%expect-rr 1 +@end example + +@noindent +No change in the grammar itself is required. Now the +parser recognizes all valid declarations, according to the +limited syntax above, transparently. In fact, the user does not even +notice when the parser splits. + +So here we have a case where we can use the benefits of @acronym{GLR}, almost +without disadvantages. Even in simple cases like this, however, there +are at least two potential problems to beware. +First, always analyze the conflicts reported by +Bison to make sure that @acronym{GLR} splitting is only done where it is +intended. A @acronym{GLR} parser splitting inadvertently may cause +problems less obvious than an @acronym{LALR} parser statically choosing the +wrong alternative in a conflict. +Second, consider interactions with the lexer (@pxref{Semantic Tokens}) +with great care. Since a split parser consumes tokens +without performing any actions during the split, the lexer cannot +obtain information via parser actions. Some cases of +lexer interactions can be eliminated by using @acronym{GLR} to +shift the complications from the lexer to the parser. You must check +the remaining cases for correctness. + +In our example, it would be safe for the lexer to return tokens +based on their current meanings in some symbol table, because no new +symbols are defined in the middle of a type declaration. Though it +is possible for a parser to define the enumeration +constants as they are parsed, before the type declaration is +completed, it actually makes no difference since they cannot be used +within the same enumerated type declaration. + +@node Merging GLR Parses +@subsection Using @acronym{GLR} to Resolve Ambiguities +@cindex @acronym{GLR} parsing, ambiguous grammars +@cindex generalized @acronym{LR} (@acronym{GLR}) parsing, ambiguous grammars +@findex %dprec +@findex %merge +@cindex conflicts +@cindex reduce/reduce conflicts + Let's consider an example, vastly simplified from a C++ grammar. @example @@ -755,8 +977,21 @@ parses as either an @code{expr} or a @code{stmt} @samp{x} as an @code{ID}). Bison detects this as a reduce/reduce conflict between the rules @code{expr : ID} and @code{declarator : ID}, which it cannot resolve at the -time it encounters @code{x} in the example above. The two @code{%dprec} -declarations, however, give precedence to interpreting the example as a +time it encounters @code{x} in the example above. Since this is a +@acronym{GLR} parser, it therefore splits the problem into two parses, one for +each choice of resolving the reduce/reduce conflict. +Unlike the example from the previous section (@pxref{Simple GLR Parsers}), +however, neither of these parses ``dies,'' because the grammar as it stands is +ambiguous. One of the parsers eventually reduces @code{stmt : expr ';'} and +the other reduces @code{stmt : decl}, after which both parsers are in an +identical state: they've seen @samp{prog stmt} and have the same unprocessed +input remaining. We say that these parses have @dfn{merged.} + +At this point, the @acronym{GLR} parser requires a specification in the +grammar of how to choose between the competing parses. +In the example above, the two @code{%dprec} +declarations specify that Bison is to give precedence +to the parse that interprets the example as a @code{decl}, which implies that @code{x} is a declarator. The parser therefore prints @@ -764,18 +999,21 @@ The parser therefore prints "x" y z + T @end example -Consider a different input string for this parser: +The @code{%dprec} declarations only come into play when more than one +parse survives. Consider a different input string for this parser: @example T (x) + y; @end example @noindent +This is another example of using @acronym{GLR} to parse an unambiguous +construct, as shown in the previous section (@pxref{Simple GLR Parsers}). Here, there is no ambiguity (this cannot be parsed as a declaration). However, at the time the Bison parser encounters @code{x}, it does not have enough information to resolve the reduce/reduce conflict (again, between @code{x} as an @code{expr} or a @code{declarator}). In this -case, no precedence declaration is used. Instead, the parser splits +case, no precedence declaration is used. Again, the parser splits into two, one assuming that @code{x} is an @code{expr}, and the other assuming @code{x} is a @code{declarator}. The second of these parsers then vanishes when it sees @code{+}, and the parser prints @@ -785,7 +1023,7 @@ x T y + @end example Suppose that instead of resolving the ambiguity, you wanted to see all -the possibilities. For this purpose, we must @dfn{merge} the semantic +the possibilities. For this purpose, you must merge 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} as follows: @@ -797,7 +1035,6 @@ stmt : expr ';' %merge @end example @noindent - and define the @code{stmtMerge} function as: @example @@ -821,17 +1058,24 @@ in the C declarations at the beginning of the file: @end example @noindent -With these declarations, the resulting parser will parse the first example -as both an @code{expr} and a @code{decl}, and print +With these declarations, the resulting parser parses the first example +as both an @code{expr} and a @code{decl}, and prints @example "x" y z + T x T y z + = @end example -@sp 1 +Bison requires that all of the +productions that participate in any particular merge have identical +@samp{%merge} clauses. Otherwise, the ambiguity would be unresolvable, +and the parser will report an error during any parse that results in +the offending merge. -@cindex @code{incline} +@node Compiler Requirements +@subsection Considerations when Compiling @acronym{GLR} Parsers +@cindex @code{inline} @cindex @acronym{GLR} parsers and @code{inline} + The @acronym{GLR} parsers require a compiler for @acronym{ISO} C89 or later. In addition, they use the @code{inline} keyword, which is not C89, but is C99 and is a common extension in pre-C99 compilers. It is @@ -1286,7 +1530,7 @@ not require it. You can add or change white space as much as you wish. For example, this: @example -exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{} +exp : NUM | exp exp '+' @{$$ = $1 + $2; @} | @dots{} ; @end example @noindent @@ -1296,6 +1540,7 @@ means the same thing as this: exp: NUM | exp exp '+' @{ $$ = $1 + $2; @} | @dots{} +; @end example @noindent @@ -1415,7 +1660,7 @@ here is the definition we will use: void yyerror (char const *s) @{ - printf ("%s\n", s); + fprintf (stderr, "%s\n", s); @} @end group @end example @@ -2334,7 +2579,7 @@ can be done with two @var{Prologue} blocks, one before and one after the %@} %union @{ - long n; + long int n; tree t; /* @r{@code{tree} is defined in @file{ptypes.h}.} */ @} @@ -2477,7 +2722,8 @@ does not enforce this convention, but if you depart from it, people who read your program will be confused. All the escape sequences used in string literals in C can be used in -Bison as well. However, unlike Standard C, trigraphs have no special +Bison as well, except that you must not use a null character within a +string literal. Also, unlike Standard C, trigraphs have no special meaning in Bison string literals, nor is backslash-newline allowed. A literal string token must contain two or more characters; for a token containing just one character, use a character token (see above). @@ -2750,7 +2996,7 @@ This macro definition must go in the prologue of the grammar file In most programs, you will need different data types for different kinds of tokens and groupings. For example, a numeric constant may need type -@code{int} or @code{long}, while a string constant needs type @code{char *}, +@code{int} or @code{long int}, while a string constant needs type @code{char *}, and an identifier might need a pointer to an entry in the symbol table. To use more than one data type for semantic values in one parser, Bison @@ -2797,9 +3043,10 @@ Actions, ,Actions in Mid-Rule}). The C code in an action can refer to the semantic values of the components matched by the rule with the construct @code{$@var{n}}, which stands for the value of the @var{n}th component. The semantic value for the grouping -being constructed is @code{$$}. (Bison translates both of these constructs -into array element references when it copies the actions into the parser -file.) +being constructed is @code{$$}. Bison translates both of these +constructs into expressions of the appropriate type when it copies the +actions into the parser file. @code{$$} is translated to a modifiable +lvalue, so it can be assigned to. Here is a typical example: @@ -3082,8 +3329,6 @@ Though grammar rules and semantic actions are enough to write a fully functional parser, it can be useful to process some additional information, especially symbol locations. -@c (terminal or not) ? - The way locations are handled is defined by providing a data type, and actions to take when rules are matched. @@ -3148,9 +3393,10 @@ exp: @dots{} 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, + "Division by zero, l%d,c%d-l%d,c%d", + @@3.first_line, @@3.first_column, + @@3.last_line, @@3.last_column); @} @} @end group @@ -3174,9 +3420,10 @@ exp: @dots{} 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, + "Division by zero, l%d,c%d-l%d,c%d", + @@3.first_line, @@3.first_column, + @@3.last_line, @@3.last_column); @} @} @end group @@ -3274,7 +3521,7 @@ Grammars}). * Union Decl:: Declaring the set of all semantic value types. * Type Decl:: Declaring the choice of type for a nonterminal symbol. * Destructor Decl:: Declaring how symbols are freed. -* Expect Decl:: Suppressing warnings about shift/reduce conflicts. +* Expect Decl:: Suppressing warnings about parsing conflicts. * Start Decl:: Specifying the start symbol. * Pure Decl:: Requesting a reentrant parser. * Decl Summary:: Table of all Bison declarations. @@ -3303,10 +3550,12 @@ associativity and precedence. @xref{Precedence Decl, ,Operator Precedence}. You can explicitly specify the numeric code for a token type by appending -an integer value in the field immediately following the token name: +a decimal or hexadecimal integer value in the field immediately +following the token name: @example %token NUM 300 +%token XNUM 0x12d // a GNU extension @end example @noindent @@ -3552,6 +3801,7 @@ typefull: string; // $$ = $1 applies, $1 is not destroyed. @cindex warnings, preventing @cindex conflicts, suppressing warnings of @findex %expect +@findex %expect-rr Bison normally warns if there are any conflicts in the grammar (@pxref{Shift/Reduce, ,Shift/Reduce Conflicts}), but most real grammars @@ -3572,6 +3822,18 @@ reduce/reduce conflicts. The usual warning is given if there are either more or fewer conflicts, or if there are any reduce/reduce conflicts. +For normal @acronym{LALR}(1) parsers, reduce/reduce conflicts are more serious, +and should be eliminated entirely. Bison will always report +reduce/reduce conflicts for these parsers. With @acronym{GLR} parsers, however, +both shift/reduce and reduce/reduce are routine (otherwise, there +would be no need to use @acronym{GLR} parsing). Therefore, it is also possible +to specify an expected number of reduce/reduce conflicts in @acronym{GLR} +parsers, using the declaration: + +@example +%expect-rr @var{n} +@end example + In general, using @code{%expect} involves these steps: @itemize @bullet @@ -3679,9 +3941,16 @@ Declare a terminal symbol (token type name) that is left-associative @deffn {Directive} %nonassoc Declare a terminal symbol (token type name) that is nonassociative -(using it in a way that would be associative is a syntax error) -@end deffn (@pxref{Precedence Decl, ,Operator Precedence}). +Using it in a way that would be associative is a syntax error. +@end deffn + +@ifset defaultprec +@deffn {Directive} %default-prec +Assign a precedence to rules lacking an explicit @code{%prec} modifier +(@pxref{Contextual Precedence, ,Context-Dependent Precedence}). +@end deffn +@end ifset @deffn {Directive} %type Declare the type of semantic values for a nonterminal symbol @@ -3711,22 +3980,40 @@ already defined, so that the debugging facilities are compiled. @xref{Tracing, ,Tracing Your Parser}. @deffn {Directive} %defines -Write an extra output file containing macro definitions for the token -type names defined in the grammar and the semantic value type -@code{YYSTYPE}, as well as a few @code{extern} variable declarations. - +Write a header file containing macro definitions for the token type +names defined in the grammar as well as a few other declarations. If the parser output file is named @file{@var{name}.c} then this file is named @file{@var{name}.h}. -This output file is essential if you wish to put the definition of -@code{yylex} in a separate source file, because @code{yylex} needs to -be able to refer to token type codes and the variable -@code{yylval}. @xref{Token Values, ,Semantic Values of Tokens}. +Unless @code{YYSTYPE} is already defined as a macro, the output header +declares @code{YYSTYPE}. Therefore, if you are using a @code{%union} +(@pxref{Multiple Types, ,More Than One Value Type}) with components +that require other definitions, or if you have defined a +@code{YYSTYPE} macro (@pxref{Value Type, ,Data Types of Semantic +Values}), you need to arrange for these definitions to be propagated to +all modules, e.g., by putting them in a +prerequisite header that is included both by your parser and by any +other module that needs @code{YYSTYPE}. + +Unless your parser is pure, the output header declares @code{yylval} +as an external variable. @xref{Pure Decl, ,A Pure (Reentrant) +Parser}. + +If you have also used locations, the output header declares +@code{YYLTYPE} and @code{yylloc} using a protocol similar to that of +@code{YYSTYPE} and @code{yylval}. @xref{Locations, ,Tracking +Locations}. + +This output file is normally essential if you wish to put the +definition of @code{yylex} in a separate source file, because +@code{yylex} typically needs to be able to refer to the +above-mentioned declarations and to the token type codes. +@xref{Token Values, ,Semantic Values of Tokens}. @end deffn @deffn {Directive} %destructor Specifying how the parser should reclaim the memory associated to -discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}. +discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}. @end deffn @deffn {Directive} %file-prefix="@var{prefix}" @@ -3753,6 +4040,14 @@ and so on. @xref{Multiple Parsers, ,Multiple Parsers in the Same Program}. @end deffn +@ifset defaultprec +@deffn {Directive} %no-default-prec +Do not assign a precedence to rules lacking an explicit @code{%prec} +modifier (@pxref{Contextual Precedence, ,Context-Dependent +Precedence}). +@end deffn +@end ifset + @deffn {Directive} %no-parser Do not include any C code in the parser file; generate tables only. The parser file contains just @code{#define} directives and static variable @@ -4250,7 +4545,8 @@ error recovery if you have written suitable error recovery grammar rules immediately return 1. Obviously, in location tracking pure parsers, @code{yyerror} should have -an access to the current location. This is indeed the case for the GLR +an access to the current location. +This is indeed the case for the @acronym{GLR} parsers, but not for the Yacc parser, for historical reasons. I.e., if @samp{%locations %pure-parser} is passed then the prototypes for @code{yyerror} are: @@ -4267,7 +4563,7 @@ void yyerror (int *nastiness, char const *msg); /* Yacc parsers. */ void yyerror (int *nastiness, char const *msg); /* GLR parsers. */ @end example -Finally, GLR and Yacc parsers share the same @code{yyerror} calling +Finally, @acronym{GLR} and Yacc parsers share the same @code{yyerror} calling convention for absolutely pure parsers, i.e., when the calling convention of @code{yylex} @emph{and} the calling convention of @code{%pure-parser} are pure. I.e.: @@ -4851,6 +5147,28 @@ exp: @dots{} @end group @end example +@ifset defaultprec +If you forget to append @code{%prec UMINUS} to the rule for unary +minus, Bison silently assumes that minus has its usual precedence. +This kind of problem can be tricky to debug, since one typically +discovers the mistake only by testing the code. + +The @code{%no-default-prec;} declaration makes it easier to discover +this kind of problem systematically. It causes rules that lack a +@code{%prec} modifier to have no precedence, even if the last terminal +symbol mentioned in their components has a declared precedence. + +If @code{%no-default-prec;} is in effect, you must specify @code{%prec} +for all rules that participate in precedence conflict resolution. +Then you will see any shift/reduce conflict until you tell Bison how +to resolve it, either by changing your grammar or by adding an +explicit precedence. This will probably add declarations to the +grammar, but it helps to protect against incorrect rule precedences. + +The effect of @code{%no-default-prec;} can be reversed by giving +@code{%default-prec;}, which is the default. +@end ifset + @node Parser States @section Parser States @cindex finite-state machine @@ -5111,13 +5429,13 @@ return_spec: Bison produces @emph{deterministic} 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. +based on a summary of the preceding input and on one extra token of look-ahead. 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 +look-ahead, 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 (@pxref{Mystery Conflicts}), there are languages where Bison's particular choice of how to @@ -5181,7 +5499,7 @@ structure should generally be adequate. On @acronym{LALR}(1) portions of a grammar, in particular, it is only slightly slower than with the default Bison parser. -For a more detailed exposition of GLR parsers, please see: Elizabeth +For a more detailed exposition of @acronym{GLR} parsers, please see: Elizabeth Scott, Adrian Johnstone and Shamsa Sadaf Hussain, Tomita-Style Generalised @acronym{LR} Parsers, Royal Holloway, University of London, Department of Computer Science, TR-00-12, @@ -5729,16 +6047,16 @@ beginning of the parsing, in the initial rule, right before the start symbol (here, @code{exp}). When the parser returns to this state right after having reduced a rule that produced an @code{exp}, the control flow jumps to state 2. If there is no such transition on a nonterminal -symbol, and the lookahead is a @code{NUM}, then this token is shifted on +symbol, and the look-ahead is a @code{NUM}, then this token is shifted on the parse stack, and the control flow jumps to state 1. Any other -lookahead triggers a syntax error.'' +look-ahead triggers a syntax error.'' @cindex core, item set @cindex item set core @cindex kernel, item set @cindex item set core Even though the only active rule in state 0 seems to be rule 0, the -report lists @code{NUM} as a lookahead symbol because @code{NUM} can be +report lists @code{NUM} as a look-ahead token because @code{NUM} can be at the beginning of any rule deriving an @code{exp}. By default Bison reports the so-called @dfn{core} or @dfn{kernel} of the item set, but if you want to see more detail you can invoke @command{bison} with @@ -5772,7 +6090,7 @@ state 1 @end example @noindent -the rule 5, @samp{exp: NUM;}, is completed. Whatever the lookahead +the rule 5, @samp{exp: NUM;}, is completed. Whatever the look-ahead token (@samp{$default}), 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}). @@ -5795,7 +6113,7 @@ state 2 @noindent In state 2, the automaton can only shift a symbol. For instance, -because of the item @samp{exp -> exp . '+' exp}, if the lookahead if +because of the item @samp{exp -> exp . '+' exp}, if the look-ahead if @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}. Since there is no default action, any other token than @@ -5872,7 +6190,7 @@ state 8 $default reduce using rule 1 (exp) @end example -Indeed, there are two actions associated to the lookahead @samp{/}: +Indeed, there are two actions associated to the look-ahead @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 @@ -5890,14 +6208,14 @@ 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 @emph{and} reducing is possible or when @emph{several} reductions are -possible, the lookahead is required to select the action. State 8 is -one such state: if the lookahead is @samp{*} or @samp{/} then the action +possible, the look-ahead is required to select the action. State 8 is +one such state: if the look-ahead is @samp{*} or @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{*}, since we specified that @samp{*} has higher -precedence that @samp{+}. More generally, some items are eligible only -with some set of possible lookaheads. When run with -@option{--report=lookahead}, Bison specifies these lookaheads: +look-ahead token is @samp{*}, since we specified that @samp{*} has higher +precedence than @samp{+}. More generally, some items are eligible only +with some set of possible look-ahead tokens. When run with +@option{--report=look-ahead}, Bison specifies these look-ahead tokens: @example state 8 @@ -5966,8 +6284,9 @@ state 11 @end example @noindent -Observe that state 11 contains conflicts due to the lack of precedence -of @samp{/} wrt @samp{+}, @samp{-}, and @samp{*}, but also because the +Observe that state 11 contains conflicts not only due to the lack of +precedence of @samp{/} with respect to @samp{+}, @samp{-}, and +@samp{*}, but also because the associativity of @samp{/} is not specified. @@ -6171,7 +6490,7 @@ compatibility with @acronym{POSIX}: @example #! /bin/sh -bison -y "$@" +bison -y "$@@" @end example @end table @@ -6223,8 +6542,7 @@ Adjust the output: @itemx --defines Pretend that @code{%defines} 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}, as well as a few -@code{extern} variable declarations. @xref{Decl Summary}. +the grammar, as well as a few other declarations. @xref{Decl Summary}. @item --defines=@var{defines-file} Same as above, but save in the file @var{defines-file}. @@ -6244,9 +6562,9 @@ separated list of @var{things} among: Description of the grammar, conflicts (resolved and unresolved), and @acronym{LALR} automaton. -@item lookahead +@item look-ahead Implies @code{state} and augments the description of the automaton with -each rule's lookahead set. +each rule's look-ahead set. @item itemset Implies @code{state} and augments the description of the automaton with @@ -6420,7 +6738,7 @@ yyparse (char const *file) yyin = fopen (file, "r"); if (!yyin) exit (2); - /* One token only. */ + /* One token only. */ yylex (); if (fclose (yyin) != 0) exit (3); @@ -6465,6 +6783,11 @@ handle features like include files, you might consider using Flex functions like @samp{yy_switch_to_buffer} that manipulate multiple input buffers. +If your Flex-generated scanner uses start conditions (@pxref{Start +conditions, , Start conditions, flex, The Flex Manual}), you might +also want to reset the scanner's state, i.e., go back to the initial +start condition, through a call to @samp{BEGIN (0)}. + @node Strings are Destroyed @section Strings are Destroyed @@ -6490,7 +6813,7 @@ char *yylval = NULL; int main () { - /* Similar to using $1, $2 in a Bison action. */ + /* Similar to using $1, $2 in a Bison action. */ char *fst = (yylex (), yylval); char *snd = (yylex (), yylval); printf ("\"%s\", \"%s\"\n", fst, snd); @@ -6782,6 +7105,14 @@ parsing. @xref{Parser Function, ,The Parser Function @code{yyparse}}. Equip the parser for debugging. @xref{Decl Summary}. @end deffn +@ifset defaultprec +@deffn {Directive} %default-prec +Assign a precedence to rules that lack an explicit @samp{%prec} +modifier. @xref{Contextual Precedence, ,Context-Dependent +Precedence}. +@end deffn +@end ifset + @deffn {Directive} %defines Bison declaration to create a header file meant for the scanner. @xref{Decl Summary}. @@ -6789,7 +7120,7 @@ Bison declaration to create a header file meant for the scanner. @deffn {Directive} %destructor Specifying how the parser should reclaim the memory associated to -discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}. +discarded symbols. @xref{Destructor Decl, , Freeing Discarded Symbols}. @end deffn @deffn {Directive} %dprec @@ -6835,6 +7166,14 @@ function is applied to the two semantic values to get a single result. Bison declaration to rename the external symbols. @xref{Decl Summary}. @end deffn +@ifset defaultprec +@deffn {Directive} %no-default-prec +Do not assign a precedence to rules that lack an explicit @samp{%prec} +modifier. @xref{Contextual Precedence, ,Context-Dependent +Precedence}. +@end deffn +@end ifset + @deffn {Directive} %no-lines Bison declaration to avoid generating @code{#line} directives in the parser file. @xref{Decl Summary}.