From 847bf1f53803bb6b605d19bcde720de43ae57d48 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Wed, 1 Aug 2001 17:49:14 +0000 Subject: [PATCH] * doc/autoconf.texi: Document @$. (Locations): New section. --- ChangeLog | 5 ++ THANKS | 4 + doc/bison.info | 203 ++++++++++++++++++++++---------------------- doc/bison.info-1 | 84 ++++++++---------- doc/bison.info-2 | 49 ++++++++++- doc/bison.info-3 | 212 ++++++++++++++++++++++++++-------------------- doc/bison.info-4 | 65 +++++++++++++- doc/bison.info-5 | 20 ++++- doc/bison.texinfo | 206 ++++++++++++++++++++++++++++++++++++++------ doc/stamp-vti | 2 +- doc/version.texi | 2 +- 11 files changed, 578 insertions(+), 274 deletions(-) diff --git a/ChangeLog b/ChangeLog index 641b5aa6..1b5e1b4d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +2001-08-01 Robert Anisko + + * doc/autoconf.texi: Document @$. + (Locations): New section. + 2001-07-18 Akim Demaille * Makefile.maint, GNUmakefile: New, from Autoconf 2.52. diff --git a/THANKS b/THANKS index 4c3823e6..5bef583f 100644 --- a/THANKS +++ b/THANKS @@ -1,3 +1,6 @@ +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 @@ -9,6 +12,7 @@ Noah Friedman friedman@gnu.org 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. diff --git a/doc/bison.info b/doc/bison.info index f25cd648..55197427 100644 --- a/doc/bison.info +++ b/doc/bison.info @@ -1,5 +1,5 @@ -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). @@ -30,105 +30,110 @@ instead of in the original English.  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  Tag Table: (Indirect) -Node: Top1306 -Node: Introduction8542 -Node: Conditions9817 -Node: Copying11281 -Node: Concepts30473 -Node: Language and Grammar31506 -Node: Grammar in Bison36522 -Node: Semantic Values38446 -Node: Semantic Actions40547 -Node: Bison Parser41730 -Node: Stages44040 -Node: Grammar Layout45323 -Node: Examples46580 -Node: RPN Calc47715 -Node: Rpcalc Decls48689 -Node: Rpcalc Rules50276 -Node: Rpcalc Input52076 -Node: Rpcalc Line53537 -Node: Rpcalc Expr54652 -Node: Rpcalc Lexer56597 -Node: Rpcalc Main59169 -Node: Rpcalc Error59567 -Node: Rpcalc Gen60575 -Node: Rpcalc Compile61724 -Node: Infix Calc62599 -Node: Simple Error Recovery65306 -Node: Multi-function Calc67192 -Node: Mfcalc Decl68758 -Node: Mfcalc Rules70781 -Node: Mfcalc Symtab72161 -Node: Exercises78534 -Node: Grammar File79040 -Node: Grammar Outline79808 -Node: C Declarations80542 -Node: Bison Declarations81122 -Node: Grammar Rules81534 -Node: C Code81994 -Node: Symbols82924 -Node: Rules88005 -Node: Recursion89644 -Node: Semantics91363 -Node: Value Type92460 -Node: Multiple Types93132 -Node: Actions94149 -Node: Action Types96934 -Node: Mid-Rule Actions98237 -Node: Declarations103806 -Node: Token Decl105125 -Node: Precedence Decl107138 -Node: Union Decl108689 -Node: Type Decl109533 -Node: Expect Decl110439 -Node: Start Decl111985 -Node: Pure Decl112363 -Node: Decl Summary114040 -Node: Multiple Parsers119423 -Node: Interface120917 -Node: Parser Function121789 -Node: Lexical122624 -Node: Calling Convention124030 -Node: Token Values126801 -Node: Token Positions127950 -Node: Pure Calling128842 -Node: Error Reporting131774 -Node: Action Features133896 -Node: Algorithm137557 -Node: Look-Ahead139850 -Node: Shift/Reduce141982 -Node: Precedence144894 -Node: Why Precedence145545 -Node: Using Precedence147410 -Node: Precedence Examples148378 -Node: How Precedence149079 -Node: Contextual Precedence150228 -Node: Parser States152019 -Node: Reduce/Reduce153262 -Node: Mystery Conflicts156823 -Node: Stack Overflow160209 -Node: Error Recovery161582 -Node: Context Dependency166718 -Node: Semantic Tokens167566 -Node: Lexical Tie-ins170583 -Node: Tie-in Recovery172131 -Node: Debugging174303 -Node: Invocation177604 -Node: Bison Options178334 -Node: Environment Variables181768 -Node: Option Cross Key182616 -Node: VMS Invocation183460 -Node: Table of Symbols184244 -Node: Glossary191643 -Node: Index197933 +Node: Top1307 +Node: Introduction8543 +Node: Conditions9818 +Node: Copying11282 +Node: Concepts30472 +Node: Language and Grammar31551 +Node: Grammar in Bison36567 +Node: Semantic Values38491 +Node: Semantic Actions40592 +Node: Locations Overview41781 +Node: Bison Parser43228 +Node: Stages45540 +Node: Grammar Layout46823 +Node: Examples48080 +Node: RPN Calc49215 +Node: Rpcalc Decls50189 +Node: Rpcalc Rules51776 +Node: Rpcalc Input53576 +Node: Rpcalc Line55037 +Node: Rpcalc Expr56152 +Node: Rpcalc Lexer58097 +Node: Rpcalc Main60669 +Node: Rpcalc Error61067 +Node: Rpcalc Gen62075 +Node: Rpcalc Compile63224 +Node: Infix Calc64099 +Node: Simple Error Recovery66806 +Node: Multi-function Calc68692 +Node: Mfcalc Decl70258 +Node: Mfcalc Rules72281 +Node: Mfcalc Symtab73661 +Node: Exercises80034 +Node: Grammar File80540 +Node: Grammar Outline81353 +Node: C Declarations82087 +Node: Bison Declarations82667 +Node: Grammar Rules83079 +Node: C Code83539 +Node: Symbols84469 +Node: Rules89550 +Node: Recursion91189 +Node: Semantics92908 +Node: Value Type94002 +Node: Multiple Types94674 +Node: Actions95691 +Node: Action Types98476 +Node: Mid-Rule Actions99779 +Node: Locations105348 +Node: Location Type106013 +Node: Actions and Locations106571 +Node: Location Default Action107735 +Node: Declarations108942 +Node: Token Decl110261 +Node: Precedence Decl112274 +Node: Union Decl113825 +Node: Type Decl114669 +Node: Expect Decl115575 +Node: Start Decl117121 +Node: Pure Decl117499 +Node: Decl Summary119176 +Node: Multiple Parsers124559 +Node: Interface126053 +Node: Parser Function126925 +Node: Lexical127760 +Node: Calling Convention129166 +Node: Token Values131937 +Node: Token Positions133086 +Node: Pure Calling133971 +Node: Error Reporting136903 +Node: Action Features139025 +Node: Algorithm142320 +Node: Look-Ahead144613 +Node: Shift/Reduce146745 +Node: Precedence149657 +Node: Why Precedence150308 +Node: Using Precedence152173 +Node: Precedence Examples153141 +Node: How Precedence153842 +Node: Contextual Precedence154991 +Node: Parser States156782 +Node: Reduce/Reduce158025 +Node: Mystery Conflicts161586 +Node: Stack Overflow164972 +Node: Error Recovery166345 +Node: Context Dependency171481 +Node: Semantic Tokens172329 +Node: Lexical Tie-ins175346 +Node: Tie-in Recovery176894 +Node: Debugging179066 +Node: Invocation182367 +Node: Bison Options183097 +Node: Environment Variables186531 +Node: Option Cross Key187379 +Node: VMS Invocation188223 +Node: Table of Symbols189007 +Node: Glossary196400 +Node: Index202690  End Tag Table diff --git a/doc/bison.info-1 b/doc/bison.info-1 index 37f759cc..e31a327d 100644 --- a/doc/bison.info-1 +++ b/doc/bison.info-1 @@ -1,5 +1,5 @@ -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). @@ -263,7 +263,6 @@ GNU GENERAL PUBLIC LICENSE ************************** Version 2, June 1991 - Copyright (C) 1989, 1991 Free Software Foundation, Inc. 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA @@ -322,7 +321,6 @@ patent must be licensed for everyone's free use or not licensed at all. 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", @@ -639,6 +637,7 @@ 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. +* 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. @@ -830,7 +829,7 @@ programming language, an expression typically has a semantic value that is a tree structure describing the meaning of the expression.  -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 ================ @@ -859,7 +858,38 @@ The action says how to produce the semantic value of the sum expression from the values of the two subexpressions.  -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. + + +File: bison.info, Node: Bison Parser, Next: Stages, Prev: Locations Overview, Up: Concepts Bison Output: the Parser File ============================= @@ -1029,45 +1059,3 @@ extension is a convention used for Bison input files. * Gen: Rpcalc Gen. Running Bison on the grammar file. * Comp: Rpcalc Compile. Run the C compiler on the output code. - -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 - %} - - %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. - diff --git a/doc/bison.info-2 b/doc/bison.info-2 index 6433a01c..09c68fd7 100644 --- a/doc/bison.info-2 +++ b/doc/bison.info-2 @@ -1,5 +1,5 @@ -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). @@ -28,6 +28,48 @@ License", "Conditions for Using Bison" and this permission notice may be included in translations approved by the Free Software Foundation instead of in the original English. + +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 + %} + + %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. +  File: bison.info, Node: Rpcalc Rules, Next: Rpcalc Lexer, Prev: Rpcalc Decls, Up: RPN Calc @@ -870,6 +912,7 @@ grammar. * 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. @@ -1172,7 +1215,7 @@ defines two mutually-recursive nonterminals, since each refers to the other.  -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 =========================== diff --git a/doc/bison.info-3 b/doc/bison.info-3 index 06106f47..ddbd6f5a 100644 --- a/doc/bison.info-3 +++ b/doc/bison.info-3 @@ -1,5 +1,5 @@ -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). @@ -158,7 +158,106 @@ converted to an end-of-rule action in this way, and this is what Bison actually does to implement mid-rule actions.  -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. + + +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; + } + + +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. + + +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. + + +File: bison.info, Node: Declarations, Next: Multiple Parsers, Prev: Locations, Up: Grammar File Bison Declarations ================== @@ -790,16 +889,18 @@ File: bison.info, Node: Token Positions, Next: Pure Calling, Prev: Token Valu 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'. @@ -1023,25 +1124,15 @@ useful in actions. 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.  File: bison.info, Node: Algorithm, Next: Error Recovery, Prev: Interface, Up: Top @@ -1229,62 +1320,3 @@ conflict: expr: variable ; - -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. - - -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. - diff --git a/doc/bison.info-4 b/doc/bison.info-4 index 05b06496..644b95a3 100644 --- a/doc/bison.info-4 +++ b/doc/bison.info-4 @@ -1,5 +1,5 @@ -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). @@ -28,6 +28,65 @@ License", "Conditions for Using Bison" and this permission notice may be included in translations approved by the Free Software Foundation instead of in the original English. + +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. + + +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. +  File: bison.info, Node: Using Precedence, Next: Precedence Examples, Prev: Why Precedence, Up: Precedence @@ -1038,7 +1097,7 @@ Bison Symbols `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. diff --git a/doc/bison.info-5 b/doc/bison.info-5 index a917e95c..de8fa66c 100644 --- a/doc/bison.info-5 +++ b/doc/bison.info-5 @@ -1,5 +1,5 @@ -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). @@ -214,11 +214,15 @@ Index * %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. @@ -252,6 +256,7 @@ Index * 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. @@ -267,6 +272,7 @@ Index * 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. @@ -305,6 +311,9 @@ Index * 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. @@ -324,6 +333,8 @@ Index * 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. @@ -366,6 +377,8 @@ Index * 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. @@ -395,6 +408,7 @@ Index * yylex: Lexical. * YYLEX_PARAM: Pure Calling. * yylloc: Token Positions. +* YYLLOC_DEFAULT: Location Default Action. * YYLTYPE: Token Positions. * yylval: Token Values. * YYMAXDEPTH: Stack Overflow. diff --git a/doc/bison.texinfo b/doc/bison.texinfo index 29ce7b69..f3ec3932 100644 --- a/doc/bison.texinfo +++ b/doc/bison.texinfo @@ -758,6 +758,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. +* 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. @@ -960,7 +961,7 @@ semantic value that is a number. In a compiler for a programming 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 @@ -991,7 +992,36 @@ expr: expr '+' expr @{ $$ = $1 + $3; @} 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 @@ -2119,6 +2149,7 @@ The Bison grammar input file conventionally has a name ending in @samp{.y}. * 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 @@ -2484,7 +2515,7 @@ primary: constant 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 @@ -2837,7 +2868,119 @@ the action is now at the end of its rule. Any mid-rule action can be 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 @@ -3528,13 +3671,15 @@ then the code in @code{yylex} might look like this: @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 @@ -3791,28 +3936,37 @@ Resume generating error messages immediately for subsequent syntax 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 @@ -5202,7 +5356,7 @@ Conventions for Pure Parsers}. @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. diff --git a/doc/stamp-vti b/doc/stamp-vti index 004cad4e..5f4eeb40 100644 --- a/doc/stamp-vti +++ b/doc/stamp-vti @@ -1,3 +1,3 @@ -@set UPDATED 18 July 2001 +@set UPDATED 30 July 2001 @set EDITION 1.28a @set VERSION 1.28a diff --git a/doc/version.texi b/doc/version.texi index 004cad4e..5f4eeb40 100644 --- a/doc/version.texi +++ b/doc/version.texi @@ -1,3 +1,3 @@ -@set UPDATED 18 July 2001 +@set UPDATED 30 July 2001 @set EDITION 1.28a @set VERSION 1.28a -- 2.45.2