3.5 Tracking Locations

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.

The way locations are handled is defined by providing a data type, and actions to take when rules are matched.

3.5.1 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.

You can specify the type of locations by defining a macro called YYLTYPE, just as you can specify the semantic value type by defining a YYSTYPE macro (see section Data Types of Semantic Values). When YYLTYPE is not defined, Bison uses a default structure type with four members:

typedef struct YYLTYPE
{
  int first_line;
  int first_column;
  int last_line;
  int last_column;
} YYLTYPE;

When YYLTYPE is not defined, at the beginning of the parsing, Bison initializes all these fields to 1 for yylloc. To initialize yylloc with a custom location type (or to chose a different initialization), use the %initial-action directive. See section Performing Actions before Parsing.

3.5.2 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 @$.

In addition, the named references construct @name and @[name] may also be used to address the symbol locations. See section Named References, for more information about using the named references construct.

Here is a basic example using the default data type for locations:

exp:
  …
| exp '/' exp
    {
      @$.first_column = @1.first_column;
      @$.first_line = @1.first_line;
      @$.last_column = @3.last_column;
      @$.last_line = @3.last_line;
      if ($3)
        $$ = $1 / $3;
      else
        {
          $$ = 1;
          fprintf (stderr, "%d.%d-%d.%d: division by zero",
                   @3.first_line, @3.first_column,
                   @3.last_line, @3.last_column);
        }
    }

As for semantic values, there is a default action for locations that is run each time a rule is matched. It sets the beginning of @$ to the beginning of the first symbol, and the end of @$ to the end of the last symbol.

With this default action, the location tracking can be fully automatic. The example above simply rewrites this way:

exp:
  …
| exp '/' exp
    {
      if ($3)
        $$ = $1 / $3;
      else
        {
          $$ = 1;
          fprintf (stderr, "%d.%d-%d.%d: division by zero",
                   @3.first_line, @3.first_column,
                   @3.last_line, @3.last_column);
        }
    }

It is also possible to access the location of the lookahead token, if any, from a semantic action. This location is stored in yylloc. See section Special Features for Use in Actions.

3.5.3 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 redefine the default action to take for each rule. The YYLLOC_DEFAULT macro is invoked each time a rule is matched, before the associated action is run. It is also invoked while processing a syntax error, to compute the error’s location. Before reporting an unresolvable syntactic ambiguity, a GLR parser invokes YYLLOC_DEFAULT recursively to compute the location of that ambiguity.

Most of the time, this macro is general enough to suppress location dedicated code from semantic actions.

The YYLLOC_DEFAULT macro takes three parameters. The first one is the location of the grouping (the result of the computation). When a rule is matched, the second parameter identifies locations of all right hand side elements of the rule being matched, and the third parameter is the size of the rule’s right hand side. When a GLR parser reports an ambiguity, which of multiple candidate right hand sides it passes to YYLLOC_DEFAULT is undefined. When processing a syntax error, the second parameter identifies locations of the symbols that were discarded during error processing, and the third parameter is the number of discarded symbols.

By default, YYLLOC_DEFAULT is defined this way:

# define YYLLOC_DEFAULT(Cur, Rhs, N)                      \
do                                                        \
  if (N)                                                  \
    {                                                     \
      (Cur).first_line   = YYRHSLOC(Rhs, 1).first_line;   \
      (Cur).first_column = YYRHSLOC(Rhs, 1).first_column; \
      (Cur).last_line    = YYRHSLOC(Rhs, N).last_line;    \
      (Cur).last_column  = YYRHSLOC(Rhs, N).last_column;  \
    }                                                     \
  else                                                    \
    {                                                     \
      (Cur).first_line   = (Cur).last_line   =            \
        YYRHSLOC(Rhs, 0).last_line;                       \
      (Cur).first_column = (Cur).last_column =            \
        YYRHSLOC(Rhs, 0).last_column;                     \
    }                                                     \
while (0)

where YYRHSLOC (rhs, k) is the location of the kth symbol in rhs when k is positive, and the location of the symbol just before the reduction when k and n are both zero.

When defining YYLLOC_DEFAULT, you should consider that:

• All arguments are free of side-effects. However, only the first one (the result) should be modified by YYLLOC_DEFAULT.
• For consistency with semantic actions, valid indexes within the right hand side range from 1 to n. When n is zero, only 0 is a valid index, and it refers to the symbol just before the reduction. During error processing n is always positive.
• Your macro should parenthesize its arguments, if need be, since the actual arguments may not be surrounded by parentheses. Also, your macro should expand to something that can be used as a single statement when it is followed by a semicolon.

This document was generated by Rick Perry on December 29, 2013 using texi2html 1.82.