(Locations): New section.
+2001-08-01 Robert Anisko <anisko_r@epita.fr>
+
+ * doc/autoconf.texi: Document @$.
+ (Locations): New section.
+
2001-07-18 Akim Demaille <akim@epita.fr>
* Makefile.maint, GNUmakefile: New, from Autoconf 2.52.
+Bison was originally written by Robert Corbett. It would not be what
+it is today without the invaluable help of these people:
+
Daniel Hagerty hag@gnu.org
David J. MacKenzie djm@gnu.org
Hans Aberg haberg@matematik.su.se
Paul Eggert eggert@twinsun.com
Piotr Gackiewicz gacek@intertel.com.pl
Richard Stallman rms@gnu.org
+Robert Anisko anisko_r@epita.fr
Many people are not named here because we lost track of them. We
thank them! Please, help us keeping this list up to date.
-Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0 à
-partir bison.texinfo.
+Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0b
+à partir bison.texinfo.
START-INFO-DIR-ENTRY
* bison: (bison). GNU Project parser generator (yacc replacement).
\1f
Indirect:
-bison.info-1: 1306
-bison.info-2: 50276
-bison.info-3: 98237
-bison.info-4: 147410
-bison.info-5: 191643
+bison.info-1: 1307
+bison.info-2: 50189
+bison.info-3: 99779
+bison.info-4: 149657
+bison.info-5: 196400
\1f
Tag Table:
(Indirect)
-Node: Top\7f1306
-Node: Introduction\7f8542
-Node: Conditions\7f9817
-Node: Copying\7f11281
-Node: Concepts\7f30473
-Node: Language and Grammar\7f31506
-Node: Grammar in Bison\7f36522
-Node: Semantic Values\7f38446
-Node: Semantic Actions\7f40547
-Node: Bison Parser\7f41730
-Node: Stages\7f44040
-Node: Grammar Layout\7f45323
-Node: Examples\7f46580
-Node: RPN Calc\7f47715
-Node: Rpcalc Decls\7f48689
-Node: Rpcalc Rules\7f50276
-Node: Rpcalc Input\7f52076
-Node: Rpcalc Line\7f53537
-Node: Rpcalc Expr\7f54652
-Node: Rpcalc Lexer\7f56597
-Node: Rpcalc Main\7f59169
-Node: Rpcalc Error\7f59567
-Node: Rpcalc Gen\7f60575
-Node: Rpcalc Compile\7f61724
-Node: Infix Calc\7f62599
-Node: Simple Error Recovery\7f65306
-Node: Multi-function Calc\7f67192
-Node: Mfcalc Decl\7f68758
-Node: Mfcalc Rules\7f70781
-Node: Mfcalc Symtab\7f72161
-Node: Exercises\7f78534
-Node: Grammar File\7f79040
-Node: Grammar Outline\7f79808
-Node: C Declarations\7f80542
-Node: Bison Declarations\7f81122
-Node: Grammar Rules\7f81534
-Node: C Code\7f81994
-Node: Symbols\7f82924
-Node: Rules\7f88005
-Node: Recursion\7f89644
-Node: Semantics\7f91363
-Node: Value Type\7f92460
-Node: Multiple Types\7f93132
-Node: Actions\7f94149
-Node: Action Types\7f96934
-Node: Mid-Rule Actions\7f98237
-Node: Declarations\7f103806
-Node: Token Decl\7f105125
-Node: Precedence Decl\7f107138
-Node: Union Decl\7f108689
-Node: Type Decl\7f109533
-Node: Expect Decl\7f110439
-Node: Start Decl\7f111985
-Node: Pure Decl\7f112363
-Node: Decl Summary\7f114040
-Node: Multiple Parsers\7f119423
-Node: Interface\7f120917
-Node: Parser Function\7f121789
-Node: Lexical\7f122624
-Node: Calling Convention\7f124030
-Node: Token Values\7f126801
-Node: Token Positions\7f127950
-Node: Pure Calling\7f128842
-Node: Error Reporting\7f131774
-Node: Action Features\7f133896
-Node: Algorithm\7f137557
-Node: Look-Ahead\7f139850
-Node: Shift/Reduce\7f141982
-Node: Precedence\7f144894
-Node: Why Precedence\7f145545
-Node: Using Precedence\7f147410
-Node: Precedence Examples\7f148378
-Node: How Precedence\7f149079
-Node: Contextual Precedence\7f150228
-Node: Parser States\7f152019
-Node: Reduce/Reduce\7f153262
-Node: Mystery Conflicts\7f156823
-Node: Stack Overflow\7f160209
-Node: Error Recovery\7f161582
-Node: Context Dependency\7f166718
-Node: Semantic Tokens\7f167566
-Node: Lexical Tie-ins\7f170583
-Node: Tie-in Recovery\7f172131
-Node: Debugging\7f174303
-Node: Invocation\7f177604
-Node: Bison Options\7f178334
-Node: Environment Variables\7f181768
-Node: Option Cross Key\7f182616
-Node: VMS Invocation\7f183460
-Node: Table of Symbols\7f184244
-Node: Glossary\7f191643
-Node: Index\7f197933
+Node: Top\7f1307
+Node: Introduction\7f8543
+Node: Conditions\7f9818
+Node: Copying\7f11282
+Node: Concepts\7f30472
+Node: Language and Grammar\7f31551
+Node: Grammar in Bison\7f36567
+Node: Semantic Values\7f38491
+Node: Semantic Actions\7f40592
+Node: Locations Overview\7f41781
+Node: Bison Parser\7f43228
+Node: Stages\7f45540
+Node: Grammar Layout\7f46823
+Node: Examples\7f48080
+Node: RPN Calc\7f49215
+Node: Rpcalc Decls\7f50189
+Node: Rpcalc Rules\7f51776
+Node: Rpcalc Input\7f53576
+Node: Rpcalc Line\7f55037
+Node: Rpcalc Expr\7f56152
+Node: Rpcalc Lexer\7f58097
+Node: Rpcalc Main\7f60669
+Node: Rpcalc Error\7f61067
+Node: Rpcalc Gen\7f62075
+Node: Rpcalc Compile\7f63224
+Node: Infix Calc\7f64099
+Node: Simple Error Recovery\7f66806
+Node: Multi-function Calc\7f68692
+Node: Mfcalc Decl\7f70258
+Node: Mfcalc Rules\7f72281
+Node: Mfcalc Symtab\7f73661
+Node: Exercises\7f80034
+Node: Grammar File\7f80540
+Node: Grammar Outline\7f81353
+Node: C Declarations\7f82087
+Node: Bison Declarations\7f82667
+Node: Grammar Rules\7f83079
+Node: C Code\7f83539
+Node: Symbols\7f84469
+Node: Rules\7f89550
+Node: Recursion\7f91189
+Node: Semantics\7f92908
+Node: Value Type\7f94002
+Node: Multiple Types\7f94674
+Node: Actions\7f95691
+Node: Action Types\7f98476
+Node: Mid-Rule Actions\7f99779
+Node: Locations\7f105348
+Node: Location Type\7f106013
+Node: Actions and Locations\7f106571
+Node: Location Default Action\7f107735
+Node: Declarations\7f108942
+Node: Token Decl\7f110261
+Node: Precedence Decl\7f112274
+Node: Union Decl\7f113825
+Node: Type Decl\7f114669
+Node: Expect Decl\7f115575
+Node: Start Decl\7f117121
+Node: Pure Decl\7f117499
+Node: Decl Summary\7f119176
+Node: Multiple Parsers\7f124559
+Node: Interface\7f126053
+Node: Parser Function\7f126925
+Node: Lexical\7f127760
+Node: Calling Convention\7f129166
+Node: Token Values\7f131937
+Node: Token Positions\7f133086
+Node: Pure Calling\7f133971
+Node: Error Reporting\7f136903
+Node: Action Features\7f139025
+Node: Algorithm\7f142320
+Node: Look-Ahead\7f144613
+Node: Shift/Reduce\7f146745
+Node: Precedence\7f149657
+Node: Why Precedence\7f150308
+Node: Using Precedence\7f152173
+Node: Precedence Examples\7f153141
+Node: How Precedence\7f153842
+Node: Contextual Precedence\7f154991
+Node: Parser States\7f156782
+Node: Reduce/Reduce\7f158025
+Node: Mystery Conflicts\7f161586
+Node: Stack Overflow\7f164972
+Node: Error Recovery\7f166345
+Node: Context Dependency\7f171481
+Node: Semantic Tokens\7f172329
+Node: Lexical Tie-ins\7f175346
+Node: Tie-in Recovery\7f176894
+Node: Debugging\7f179066
+Node: Invocation\7f182367
+Node: Bison Options\7f183097
+Node: Environment Variables\7f186531
+Node: Option Cross Key\7f187379
+Node: VMS Invocation\7f188223
+Node: Table of Symbols\7f189007
+Node: Glossary\7f196400
+Node: Index\7f202690
\1f
End Tag Table
-Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0 à
-partir bison.texinfo.
+Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0b
+à partir bison.texinfo.
START-INFO-DIR-ENTRY
* bison: (bison). GNU Project parser generator (yacc replacement).
**************************
Version 2, June 1991
-
Copyright (C) 1989, 1991 Free Software Foundation, Inc.
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
modification follow.
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
-
0. This License applies to any program or other work which contains a
notice placed by the copyright holder saying it may be distributed
under the terms of this General Public License. The "Program",
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.
+* 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.
is a tree structure describing the meaning of the expression.
\1f
-File: bison.info, Node: Semantic Actions, Next: Bison Parser, Prev: Semantic Values, Up: Concepts
+File: bison.info, Node: Semantic Actions, Next: Locations Overview, Prev: Semantic Values, Up: Concepts
Semantic Actions
================
from the values of the two subexpressions.
\1f
-File: bison.info, Node: Bison Parser, Next: Stages, Prev: Semantic Actions, Up: Concepts
+File: bison.info, Node: Locations Overview, Next: Bison Parser, Prev: Semantic Actions, Up: Concepts
+
+Locations
+=========
+
+ 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 the "textual position", or "location", of each syntactic
+construct. Bison provides a mechanism for handling these locations.
+
+ 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 (*note Locations::, for
+more details).
+
+ 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 is `@$', while the locations of the subexpressions are
+`@1' and `@3'.
+
+ When a rule is matched, a default action is used to compute the
+semantic value of its left hand side (*note Actions::). 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 `@$' 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.
+
+\1f
+File: bison.info, Node: Bison Parser, Next: Stages, Prev: Locations Overview, Up: Concepts
Bison Output: the Parser File
=============================
* Gen: Rpcalc Gen. Running Bison on the grammar file.
* Comp: Rpcalc Compile. Run the C compiler on the output code.
-\1f
-File: bison.info, Node: Rpcalc Decls, Next: Rpcalc Rules, Up: RPN Calc
-
-Declarations for `rpcalc'
--------------------------
-
- Here are the C and Bison declarations for the reverse polish notation
-calculator. As in C, comments are placed between `/*...*/'.
-
- /* Reverse polish notation calculator. */
-
- %{
- #define YYSTYPE double
- #include <math.h>
- %}
-
- %token NUM
-
- %% /* Grammar rules and actions follow */
-
- The C declarations section (*note The C Declarations Section: C
-Declarations.) contains two preprocessor directives.
-
- The `#define' directive defines the macro `YYSTYPE', thus specifying
-the C data type for semantic values of both tokens and groupings (*note
-Data Types of Semantic Values: Value Type.). The Bison parser will use
-whatever type `YYSTYPE' is defined as; if you don't define it, `int' is
-the default. Because we specify `double', each token and each
-expression has an associated value, which is a floating point number.
-
- The `#include' directive is used to declare the exponentiation
-function `pow'.
-
- The second section, Bison declarations, provides information to
-Bison about the token types (*note The Bison Declarations Section:
-Bison Declarations.). 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 `NUM', the token type
-for numeric constants.
-
-Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0 à
-partir bison.texinfo.
+Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0b
+à partir bison.texinfo.
START-INFO-DIR-ENTRY
* bison: (bison). GNU Project parser generator (yacc replacement).
included in translations approved by the Free Software Foundation
instead of in the original English.
+\1f
+File: bison.info, Node: Rpcalc Decls, Next: Rpcalc Rules, Up: RPN Calc
+
+Declarations for `rpcalc'
+-------------------------
+
+ Here are the C and Bison declarations for the reverse polish notation
+calculator. As in C, comments are placed between `/*...*/'.
+
+ /* Reverse polish notation calculator. */
+
+ %{
+ #define YYSTYPE double
+ #include <math.h>
+ %}
+
+ %token NUM
+
+ %% /* Grammar rules and actions follow */
+
+ The C declarations section (*note The C Declarations Section: C
+Declarations.) contains two preprocessor directives.
+
+ The `#define' directive defines the macro `YYSTYPE', thus specifying
+the C data type for semantic values of both tokens and groupings (*note
+Data Types of Semantic Values: Value Type.). The Bison parser will use
+whatever type `YYSTYPE' is defined as; if you don't define it, `int' is
+the default. Because we specify `double', each token and each
+expression has an associated value, which is a floating point number.
+
+ The `#include' directive is used to declare the exponentiation
+function `pow'.
+
+ The second section, Bison declarations, provides information to
+Bison about the token types (*note The Bison Declarations Section:
+Bison Declarations.). 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 `NUM', the token type
+for numeric constants.
+
\1f
File: bison.info, Node: Rpcalc Rules, Next: Rpcalc Lexer, Prev: Rpcalc Decls, Up: RPN Calc
* Rules:: How to write grammar rules.
* Recursion:: Writing recursive rules.
* Semantics:: Semantic values and actions.
+* Locations:: Locations and actions.
* Declarations:: All kinds of Bison declarations are described here.
* Multiple Parsers:: Putting more than one Bison parser in one program.
other.
\1f
-File: bison.info, Node: Semantics, Next: Declarations, Prev: Recursion, Up: Grammar File
+File: bison.info, Node: Semantics, Next: Locations, Prev: Recursion, Up: Grammar File
Defining Language Semantics
===========================
-Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0 à
-partir bison.texinfo.
+Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0b
+à partir bison.texinfo.
START-INFO-DIR-ENTRY
* bison: (bison). GNU Project parser generator (yacc replacement).
actually does to implement mid-rule actions.
\1f
-File: bison.info, Node: Declarations, Next: Multiple Parsers, Prev: Semantics, Up: Grammar File
+File: bison.info, Node: Locations, Next: Declarations, Prev: Semantics, Up: Grammar File
+
+Tracking Locations
+==================
+
+ Though grammar rules and semantic actions are enough to write a fully
+functional parser, it can be useful to process some additionnal
+informations, especially locations of tokens and groupings.
+
+ The way locations are handled is defined by providing a data type,
+and actions to take when rules are matched.
+
+* Menu:
+
+* Location Type:: Specifying a data type for locations.
+* Actions and Locations:: Using locations in actions.
+* Location Default Action:: Defining a general way to compute locations.
+
+\1f
+File: bison.info, Node: Location Type, Next: Actions and Locations, Up: Locations
+
+Data Type of Locations
+----------------------
+
+ Defining a data type for locations is much simpler than for semantic
+values, since all tokens and groupings always use the same type.
+
+ The type of locations is specified by defining a macro called
+`YYLTYPE'. When `YYLTYPE' is not defined, Bison uses a default
+structure type with four members:
+
+ struct
+ {
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;
+ }
+
+\1f
+File: bison.info, Node: Actions and Locations, Next: Location Default Action, Prev: Location Type, Up: Locations
+
+Actions and Locations
+---------------------
+
+ Actions are not only useful for defining language semantics, but
+also for describing the behavior of the output parser with locations.
+
+ 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 constructs can be used to access the locations of the
+elements being matched. The location of the Nth component of the right
+hand side is `@N', while the location of the left hand side grouping is
+`@$'.
+
+ Here is a simple example using the default data type for locations:
+
+ exp: ...
+ | exp '+' exp
+ {
+ @$.last_column = @3.last_column;
+ @$.last_line = @3.last_line;
+ $$ = $1 + $3;
+ }
+
+In the example above, there is no need to set the beginning of `@$'. The
+output parser always sets `@$' to `@1' before executing the C code of a
+given action, whether you provide a processing for locations or not.
+
+\1f
+File: bison.info, Node: Location Default Action, Prev: Actions and Locations, Up: Locations
+
+Default Action for Locations
+----------------------------
+
+ 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 define a default action to take for each rule. The
+`YYLLOC_DEFAULT' macro is called each time a rule is matched, before
+the associated action is run.
+
+ This macro takes two parameters, the first one being the location of
+the grouping (the result of the computation), and the second one being
+the location of the last element matched. Of course, before
+`YYLLOC_DEFAULT' is run, the result is set to the location of the first
+component matched.
+
+ By default, this macro computes a location that ranges from the
+beginning of the first element to the end of the last element. It is
+defined this way:
+
+ #define YYLLOC_DEFAULT(Current, Last) \
+ Current.last_line = Last.last_line; \
+ Current.last_column = Last.last_column;
+
+Most of the time, the default action for locations is general enough to
+suppress location dedicated code from most actions.
+
+\1f
+File: bison.info, Node: Declarations, Next: Multiple Parsers, Prev: Locations, Up: Grammar File
Bison Declarations
==================
Textual Positions of Tokens
---------------------------
- If you are using the `@N'-feature (*note Special Features for Use in
-Actions: Action Features.) in actions to keep track of the textual
-locations of tokens and groupings, then you must provide this
-information in `yylex'. The function `yyparse' expects to find the
-textual location of a token just parsed in the global variable
-`yylloc'. So `yylex' must store the proper data in that variable. The
-value of `yylloc' is a structure and you need only initialize the
-members that are going to be used by the actions. The four members are
-called `first_line', `first_column', `last_line' and `last_column'.
-Note that the use of this feature makes the parser noticeably slower.
+ If you are using the `@N'-feature (*note Tracking Locations:
+Locations.) in actions to keep track of the textual locations of tokens
+and groupings, then you must provide this information in `yylex'. The
+function `yyparse' expects to find the textual location of a token just
+parsed in the global variable `yylloc'. So `yylex' must store the
+proper data in that variable.
+
+ By default, the value of `yylloc' is a structure and you need only
+initialize the members that are going to be used by the actions. The
+four members are called `first_line', `first_column', `last_line' and
+`last_column'. Note that the use of this feature makes the parser
+noticeably slower.
The data type of `yylloc' has the name `YYLTYPE'.
errors. This is useful primarily in error rules. *Note Error
Recovery::.
-`@N'
- Acts like a structure variable containing information on the line
- numbers and column numbers of the Nth component of the current
- rule. The structure has four members, like this:
-
- struct {
- int first_line, last_line;
- int first_column, last_column;
- };
-
- Thus, to get the starting line number of the third component, you
- would use `@3.first_line'.
+`@$'
+ Acts like a structure variable containing information on the
+ textual position of the grouping made by the current rule. *Note
+ Tracking Locations: Locations.
- In order for the members of this structure to contain valid
- information, you must make `yylex' supply this information about
- each token. If you need only certain members, then `yylex' need
- only fill in those members.
-
- The use of this feature makes the parser noticeably slower.
+`@N'
+ Acts like a structure variable containing information on the
+ textual position of the Nth component of the current rule. *Note
+ Tracking Locations: Locations.
\1f
File: bison.info, Node: Algorithm, Next: Error Recovery, Prev: Interface, Up: Top
expr: variable
;
-\1f
-File: bison.info, Node: Precedence, Next: Contextual Precedence, Prev: Shift/Reduce, Up: Algorithm
-
-Operator Precedence
-===================
-
- Another situation where shift/reduce conflicts appear is in
-arithmetic expressions. Here shifting is not always the preferred
-resolution; the Bison declarations for operator precedence allow you to
-specify when to shift and when to reduce.
-
-* Menu:
-
-* Why Precedence:: An example showing why precedence is needed.
-* Using Precedence:: How to specify precedence in Bison grammars.
-* Precedence Examples:: How these features are used in the previous example.
-* How Precedence:: How they work.
-
-\1f
-File: bison.info, Node: Why Precedence, Next: Using Precedence, Up: Precedence
-
-When Precedence is Needed
--------------------------
-
- Consider the following ambiguous grammar fragment (ambiguous because
-the input `1 - 2 * 3' can be parsed in two different ways):
-
- expr: expr '-' expr
- | expr '*' expr
- | expr '<' expr
- | '(' expr ')'
- ...
- ;
-
-Suppose the parser has seen the tokens `1', `-' and `2'; should it
-reduce them via the rule for the subtraction operator? It depends on
-the next token. Of course, if the next token is `)', we must reduce;
-shifting is invalid because no single rule can reduce the token
-sequence `- 2 )' or anything starting with that. But if the next token
-is `*' or `<', we have a choice: either shifting or reduction would
-allow the parse to complete, but with different results.
-
- To decide which one Bison should do, we must consider the results.
-If the next operator token OP is shifted, then it must be reduced first
-in order to permit another opportunity to reduce the difference. The
-result is (in effect) `1 - (2 OP 3)'. On the other hand, if the
-subtraction is reduced before shifting OP, the result is
-`(1 - 2) OP 3'. Clearly, then, the choice of shift or reduce should
-depend on the relative precedence of the operators `-' and OP: `*'
-should be shifted first, but not `<'.
-
- What about input such as `1 - 2 - 5'; should this be `(1 - 2) - 5'
-or should it be `1 - (2 - 5)'? For most operators we prefer the
-former, which is called "left association". The latter alternative,
-"right association", is desirable for assignment operators. The choice
-of left or right association is a matter of whether the parser chooses
-to shift or reduce when the stack contains `1 - 2' and the look-ahead
-token is `-': shifting makes right-associativity.
-
-Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0 à
-partir bison.texinfo.
+Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0b
+à partir bison.texinfo.
START-INFO-DIR-ENTRY
* bison: (bison). GNU Project parser generator (yacc replacement).
included in translations approved by the Free Software Foundation
instead of in the original English.
+\1f
+File: bison.info, Node: Precedence, Next: Contextual Precedence, Prev: Shift/Reduce, Up: Algorithm
+
+Operator Precedence
+===================
+
+ Another situation where shift/reduce conflicts appear is in
+arithmetic expressions. Here shifting is not always the preferred
+resolution; the Bison declarations for operator precedence allow you to
+specify when to shift and when to reduce.
+
+* Menu:
+
+* Why Precedence:: An example showing why precedence is needed.
+* Using Precedence:: How to specify precedence in Bison grammars.
+* Precedence Examples:: How these features are used in the previous example.
+* How Precedence:: How they work.
+
+\1f
+File: bison.info, Node: Why Precedence, Next: Using Precedence, Up: Precedence
+
+When Precedence is Needed
+-------------------------
+
+ Consider the following ambiguous grammar fragment (ambiguous because
+the input `1 - 2 * 3' can be parsed in two different ways):
+
+ expr: expr '-' expr
+ | expr '*' expr
+ | expr '<' expr
+ | '(' expr ')'
+ ...
+ ;
+
+Suppose the parser has seen the tokens `1', `-' and `2'; should it
+reduce them via the rule for the subtraction operator? It depends on
+the next token. Of course, if the next token is `)', we must reduce;
+shifting is invalid because no single rule can reduce the token
+sequence `- 2 )' or anything starting with that. But if the next token
+is `*' or `<', we have a choice: either shifting or reduction would
+allow the parse to complete, but with different results.
+
+ To decide which one Bison should do, we must consider the results.
+If the next operator token OP is shifted, then it must be reduced first
+in order to permit another opportunity to reduce the difference. The
+result is (in effect) `1 - (2 OP 3)'. On the other hand, if the
+subtraction is reduced before shifting OP, the result is
+`(1 - 2) OP 3'. Clearly, then, the choice of shift or reduce should
+depend on the relative precedence of the operators `-' and OP: `*'
+should be shifted first, but not `<'.
+
+ What about input such as `1 - 2 - 5'; should this be `(1 - 2) - 5'
+or should it be `1 - (2 - 5)'? For most operators we prefer the
+former, which is called "left association". The latter alternative,
+"right association", is desirable for assignment operators. The choice
+of left or right association is a matter of whether the parser chooses
+to shift or reduce when the stack contains `1 - 2' and the look-ahead
+token is `-': shifting makes right-associativity.
+
\1f
File: bison.info, Node: Using Precedence, Next: Precedence Examples, Prev: Why Precedence, Up: Precedence
`YYLTYPE'
Macro for the data type of `yylloc'; a structure with four
- members. *Note Textual Positions of Tokens: Token Positions.
+ members. *Note Data Types of Locations: Location Type.
`yyltype'
Default value for YYLTYPE.
-Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0 à
-partir bison.texinfo.
+Ceci est le fichier Info bison.info, produit par Makeinfo version 4.0b
+à partir bison.texinfo.
START-INFO-DIR-ENTRY
* bison: (bison). GNU Project parser generator (yacc replacement).
* %token: Token Decl.
* %type: Type Decl.
* %union: Union Decl.
-* @N: Action Features.
+* @$ <1>: Action Features.
+* @$: Actions and Locations.
+* @N <1>: Action Features.
+* @N: Actions and Locations.
* action: Actions.
* action data types: Action Types.
* action features summary: Action Features.
* actions in mid-rule: Mid-Rule Actions.
+* actions, location: Actions and Locations.
* actions, semantic: Semantic Actions.
* additional C code section: C Code.
* algorithm of parser: Algorithm.
* context-free grammar: Language and Grammar.
* controlling function: Rpcalc Main.
* dangling else: Shift/Reduce.
+* data type of locations: Location Type.
* data types in actions: Action Types.
* data types of semantic values: Value Type.
* debugging: Debugging.
* declaring value types, nonterminals: Type Decl.
* default action: Actions.
* default data type: Value Type.
+* default location type: Location Type.
* default stack limit: Stack Overflow.
* default start symbol: Start Decl.
* defining language semantics: Semantics.
* lexical tie-in: Lexical Tie-ins.
* literal string token: Symbols.
* literal token: Symbols.
+* location <1>: Locations.
+* location: Locations Overview.
+* location actions: Actions and Locations.
* look-ahead token: Look-Ahead.
* LR(1): Mystery Conflicts.
* main function in simple example: Rpcalc Main.
* parser stack overflow: Stack Overflow.
* parser state: Parser States.
* polish notation calculator: RPN Calc.
+* position, textual <1>: Locations.
+* position, textual: Locations Overview.
* precedence declarations: Precedence Decl.
* precedence of operators: Precedence.
* precedence, context-dependent: Contextual Precedence.
* syntax error: Error Reporting.
* syntax of grammar rules: Rules.
* terminal symbol: Symbols.
+* textual position <1>: Locations.
+* textual position: Locations Overview.
* token: Language and Grammar.
* token type: Symbols.
* token type names, declaring: Token Decl.
* yylex: Lexical.
* YYLEX_PARAM: Pure Calling.
* yylloc: Token Positions.
+* YYLLOC_DEFAULT: Location Default Action.
* YYLTYPE: Token Positions.
* yylval: Token Values.
* YYMAXDEPTH: Stack Overflow.
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.
+* 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.
language, an expression typically has a semantic value that is a tree
structure describing the meaning of the expression.
-@node Semantic Actions, Bison Parser, Semantic Values, Concepts
+@node Semantic Actions, Locations Overview, Semantic Values, Concepts
@section Semantic Actions
@cindex semantic actions
@cindex actions, semantic
The action says how to produce the semantic value of the sum expression
from the values of the two subexpressions.
-@node Bison Parser, Stages, Semantic Actions, Concepts
+@node Locations Overview, Bison Parser, Semantic Actions, Concepts
+@section Locations
+@cindex location
+@cindex textual position
+@cindex position, textual
+
+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
+the @dfn{textual position}, or @dfn{location}, of each syntactic construct.
+Bison provides a mechanism for handling these locations.
+
+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 (@pxref{Locations}, for more details).
+
+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
+is @code{@@$}, while the locations of the subexpressions are @code{@@1} and
+@code{@@3}.
+
+When a rule is matched, a default action is used to compute the semantic value
+of its left hand side (@pxref{Actions}). 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{@@$} 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.
+
+@node Bison Parser, Stages, Locations Overview, Concepts
@section Bison Output: the Parser File
@cindex Bison parser
@cindex Bison utility
* Rules:: How to write grammar rules.
* Recursion:: Writing recursive rules.
* Semantics:: Semantic values and actions.
+* Locations:: Locations and actions.
* Declarations:: All kinds of Bison declarations are described here.
* Multiple Parsers:: Putting more than one Bison parser in one program.
@end menu
defines two mutually-recursive nonterminals, since each refers to the
other.
-@node Semantics, Declarations, Recursion, Grammar File
+@node Semantics, Locations, Recursion, Grammar File
@section Defining Language Semantics
@cindex defining language semantics
@cindex language semantics, defining
converted to an end-of-rule action in this way, and this is what Bison
actually does to implement mid-rule actions.
-@node Declarations, Multiple Parsers, Semantics, Grammar File
+@node Locations, Declarations, Semantics, Grammar File
+@section Tracking Locations
+@cindex location
+@cindex textual position
+@cindex position, textual
+
+Though grammar rules and semantic actions are enough to write a fully
+functional parser, it can be useful to process some additionnal informations,
+especially locations of tokens and groupings.
+
+The way locations are handled is defined by providing a data type, and actions
+to take when rules are matched.
+
+@menu
+* Location Type:: Specifying a data type for locations.
+* Actions and Locations:: Using locations in actions.
+* Location Default Action:: Defining a general way to compute locations.
+@end menu
+
+@node Location Type, Actions and Locations, , Locations
+@subsection Data Type of Locations
+@cindex data type of locations
+@cindex default location type
+
+Defining a data type for locations is much simpler than for semantic values,
+since all tokens and groupings always use the same type.
+
+The type of locations is specified by defining a macro called @code{YYLTYPE}.
+When @code{YYLTYPE} is not defined, Bison uses a default structure type with
+four members:
+
+@example
+struct
+@{
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;
+@}
+@end example
+
+@node Actions and Locations, Location Default Action, Location Type, Locations
+@subsection Actions and Locations
+@cindex location actions
+@cindex actions, location
+@vindex @@$
+@vindex @@@var{n}
+
+Actions are not only useful for defining language semantics, but also for
+describing the behavior of the output parser with locations.
+
+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
+constructs can be used to access the locations of the elements being matched.
+The location of the @var{n}th component of the right hand side is
+@code{@@@var{n}}, while the location of the left hand side grouping is
+@code{@@$}.
+
+Here is a simple example using the default data type for locations:
+
+@example
+@group
+exp: @dots{}
+ | exp '+' exp
+ @{
+ @@$.last_column = @@3.last_column;
+ @@$.last_line = @@3.last_line;
+ $$ = $1 + $3;
+ @}
+@end group
+@end example
+
+@noindent
+In the example above, there is no need to set the beginning of @code{@@$}. The
+output parser always sets @code{@@$} to @code{@@1} before executing the C
+code of a given action, whether you provide a processing for locations or not.
+
+@node Location Default Action, , Actions and Locations, Locations
+@subsection Default Action for Locations
+@vindex YYLLOC_DEFAULT
+
+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 define a default action to take for each rule. The @code{YYLLOC_DEFAULT}
+macro is called each time a rule is matched, before the associated action is
+run.
+
+@c Documentation for the old (?) YYLLOC_DEFAULT
+
+This macro takes two parameters, the first one being the location of the
+grouping (the result of the computation), and the second one being the
+location of the last element matched. Of course, before @code{YYLLOC_DEFAULT}
+is run, the result is set to the location of the first component matched.
+
+By default, this macro computes a location that ranges from the beginning of
+the first element to the end of the last element. It is defined this way:
+
+@example
+@group
+#define YYLLOC_DEFAULT(Current, Last) \
+ Current.last_line = Last.last_line; \
+ Current.last_column = Last.last_column;
+@end group
+@end example
+
+@c not Documentation for the old (?) YYLLOC_DEFAULT
+
+@noindent
+
+Most of the time, the default action for locations is general enough to
+suppress location dedicated code from most actions.
+
+@node Declarations, Multiple Parsers, Locations, Grammar File
@section Bison Declarations
@cindex declarations, Bison
@cindex Bison declarations
@subsection Textual Positions of Tokens
@vindex yylloc
-If you are using the @samp{@@@var{n}}-feature (@pxref{Action Features,
-,Special Features for Use in Actions}) in actions to keep track of the
+If you are using the @samp{@@@var{n}}-feature (@pxref{Locations, ,
+Tracking Locations}) in actions to keep track of the
textual locations of tokens and groupings, then you must provide this
information in @code{yylex}. The function @code{yyparse} expects to
find the textual location of a token just parsed in the global variable
@code{yylloc}. So @code{yylex} must store the proper data in that
-variable. The value of @code{yylloc} is a structure and you need only
+variable.
+
+By default, the value of @code{yylloc} is a structure and you need only
initialize the members that are going to be used by the actions. The
four members are called @code{first_line}, @code{first_column},
@code{last_line} and @code{last_column}. Note that the use of this
errors. This is useful primarily in error rules.
@xref{Error Recovery}.
-@item @@@var{n}
-@findex @@@var{n}
-Acts like a structure variable containing information on the line
-numbers and column numbers of the @var{n}th component of the current
-rule. The structure has four members, like this:
+@item @@$
+@findex @@$
+Acts like a structure variable containing information on the textual position
+of the grouping made by the current rule. @xref{Locations, ,
+Tracking Locations}.
-@example
-struct @{
- int first_line, last_line;
- int first_column, last_column;
-@};
-@end example
+@c Check if those paragraphs are still useful or not.
+
+@c @example
+@c struct @{
+@c int first_line, last_line;
+@c int first_column, last_column;
+@c @};
+@c @end example
+
+@c Thus, to get the starting line number of the third component, you would
+@c use @samp{@@3.first_line}.
-Thus, to get the starting line number of the third component, you would
-use @samp{@@3.first_line}.
+@c In order for the members of this structure to contain valid information,
+@c you must make @code{yylex} supply this information about each token.
+@c If you need only certain members, then @code{yylex} need only fill in
+@c those members.
-In order for the members of this structure to contain valid information,
-you must make @code{yylex} supply this information about each token.
-If you need only certain members, then @code{yylex} need only fill in
-those members.
+@c The use of this feature makes the parser noticeably slower.
+
+@item @@@var{n}
+@findex @@@var{n}
+Acts like a structure variable containing information on the textual position
+of the @var{n}th component of the current rule. @xref{Locations, ,
+Tracking Locations}.
-The use of this feature makes the parser noticeably slower.
@end table
@node Algorithm, Error Recovery, Interface, Top
@item YYLTYPE
Macro for the data type of @code{yylloc}; a structure with four
-members. @xref{Token Positions, ,Textual Positions of Tokens}.
+members. @xref{Location Type, , Data Types of Locations}.
@item yyltype
Default value for YYLTYPE.
-@set UPDATED 18 July 2001
+@set UPDATED 30 July 2001
@set EDITION 1.28a
@set VERSION 1.28a
-@set UPDATED 18 July 2001
+@set UPDATED 30 July 2001
@set EDITION 1.28a
@set VERSION 1.28a
projects / bison.git / commitdiff
