8.4 Tracing Your Parser

When a Bison grammar compiles properly but parses “incorrectly”, the yydebug parser-trace feature helps figuring out why.

8.4.1 Enabling Traces

There are several means to enable compilation of trace facilities:

the macro YYDEBUG

Define the macro YYDEBUG to a nonzero value when you compile the parser. This is compliant with POSIX Yacc. You could use ‘-DYYDEBUG=1’ as a compiler option or you could put ‘#define YYDEBUG 1’ in the prologue of the grammar file (see section The Prologue).

If the %define variable api.prefix is used (see section Multiple Parsers in the Same Program), for instance ‘%define api.prefix x’, then if CDEBUG is defined, its value controls the tracing feature (enabled if and only if nonzero); otherwise tracing is enabled if and only if YYDEBUG is nonzero.

the option ‘-t’ (POSIX Yacc compliant)

the option ‘--debug’ (Bison extension)

Use the ‘-t’ option when you run Bison (see section Invoking Bison). With ‘%define api.prefix {c}’, it defines CDEBUG to 1, otherwise it defines YYDEBUG to 1.

the directive ‘%debug’

Add the %debug directive (see section Bison Declaration Summary). This Bison extension is maintained for backward compatibility with previous versions of Bison.

the variable ‘parse.trace’

Add the ‘%define parse.trace’ directive (see section parse.trace), or pass the ‘-Dparse.trace’ option (see section Bison Options). This is a Bison extension, which is especially useful for languages that don’t use a preprocessor. Unless POSIX and Yacc portability matter to you, this is the preferred solution.

We suggest that you always enable the trace option so that debugging is always possible.

The trace facility outputs messages with macro calls of the form YYFPRINTF (stderr, format, args) where format and args are the usual printf format and variadic arguments. If you define YYDEBUG to a nonzero value but do not define YYFPRINTF, <stdio.h> is automatically included and YYFPRINTF is defined to fprintf.

Once you have compiled the program with trace facilities, the way to request a trace is to store a nonzero value in the variable yydebug. You can do this by making the C code do it (in main, perhaps), or you can alter the value with a C debugger.

Each step taken by the parser when yydebug is nonzero produces a line or two of trace information, written on stderr. The trace messages tell you these things:

• Each time the parser calls yylex, what kind of token was read.
• Each time a token is shifted, the depth and complete contents of the state stack (see section Parser States).
• Each time a rule is reduced, which rule it is, and the complete contents of the state stack afterward.

To make sense of this information, it helps to refer to the automaton description file (see section Understanding Your Parser). This file shows the meaning of each state in terms of positions in various rules, and also what each state will do with each possible input token. As you read the successive trace messages, you can see that the parser is functioning according to its specification in the listing file. Eventually you will arrive at the place where something undesirable happens, and you will see which parts of the grammar are to blame.

The parser implementation file is a C/C++/Java program and you can use debuggers on it, but it’s not easy to interpret what it is doing. The parser function is a finite-state machine interpreter, and aside from the actions it executes the same code over and over. Only the values of variables show where in the grammar it is working.

8.4.2 Enabling Debug Traces for mfcalc

The debugging information normally gives the token type of each token read, but not its semantic value. The %printer directive allows specify how semantic values are reported, see Printing Semantic Values. For backward compatibility, Yacc like C parsers may also use the YYPRINT (see section The YYPRINT Macro), but its use is discouraged.

As a demonstration of %printer, consider the multi-function calculator, mfcalc (see section Multi-Function Calculator: mfcalc). To enable run-time traces, and semantic value reports, insert the following directives in its prologue:

/* Generate the parser description file.  */
%verbose
/* Enable run-time traces (yydebug).  */
%define parse.trace

/* Formatting semantic values.  */
%printer { fprintf (yyoutput, "%s", $$->name); } VAR;
%printer { fprintf (yyoutput, "%s()", $$->name); } FNCT;
%printer { fprintf (yyoutput, "%g", $$); } <double>;

The %define directive instructs Bison to generate run-time trace support. Then, activation of these traces is controlled at run-time by the yydebug variable, which is disabled by default. Because these traces will refer to the “states” of the parser, it is helpful to ask for the creation of a description of that parser; this is the purpose of (admittedly ill-named) %verbose directive.

The set of %printer directives demonstrates how to format the semantic value in the traces. Note that the specification can be done either on the symbol type (e.g., VAR or FNCT), or on the type tag: since <double> is the type for both NUM and exp, this printer will be used for them.

Here is a sample of the information provided by run-time traces. The traces are sent onto standard error.

$ echo 'sin(1-1)' | ./mfcalc -p
Starting parse
Entering state 0
Reducing stack by rule 1 (line 34):
-> $$ = nterm input ()
Stack now 0
Entering state 1

This first batch shows a specific feature of this grammar: the first rule (which is in line 34 of ‘mfcalc.y’ can be reduced without even having to look for the first token. The resulting left-hand symbol ($$) is a valueless (‘()’) input non terminal (nterm).

Then the parser calls the scanner.

Reading a token: Next token is token FNCT (sin())
Shifting token FNCT (sin())
Entering state 6

That token (token) is a function (FNCT) whose value is ‘sin’ as formatted per our %printer specification: ‘sin()’. The parser stores (Shifting) that token, and others, until it can do something about it.

Reading a token: Next token is token '(' ()
Shifting token '(' ()
Entering state 14
Reading a token: Next token is token NUM (1.000000)
Shifting token NUM (1.000000)
Entering state 4
Reducing stack by rule 6 (line 44):
   $1 = token NUM (1.000000)
-> $$ = nterm exp (1.000000)
Stack now 0 1 6 14
Entering state 24

The previous reduction demonstrates the %printer directive for <double>: both the token NUM and the resulting nonterminal exp have ‘1’ as value.

Reading a token: Next token is token '-' ()
Shifting token '-' ()
Entering state 17
Reading a token: Next token is token NUM (1.000000)
Shifting token NUM (1.000000)
Entering state 4
Reducing stack by rule 6 (line 44):
   $1 = token NUM (1.000000)
-> $$ = nterm exp (1.000000)
Stack now 0 1 6 14 24 17
Entering state 26
Reading a token: Next token is token ')' ()
Reducing stack by rule 11 (line 49):
   $1 = nterm exp (1.000000)
   $2 = token '-' ()
   $3 = nterm exp (1.000000)
-> $$ = nterm exp (0.000000)
Stack now 0 1 6 14
Entering state 24

The rule for the subtraction was just reduced. The parser is about to discover the end of the call to sin.

Next token is token ')' ()
Shifting token ')' ()
Entering state 31
Reducing stack by rule 9 (line 47):
   $1 = token FNCT (sin())
   $2 = token '(' ()
   $3 = nterm exp (0.000000)
   $4 = token ')' ()
-> $$ = nterm exp (0.000000)
Stack now 0 1
Entering state 11

Finally, the end-of-line allow the parser to complete the computation, and display its result.

Reading a token: Next token is token '\n' ()
Shifting token '\n' ()
Entering state 22
Reducing stack by rule 4 (line 40):
   $1 = nterm exp (0.000000)
   $2 = token '\n' ()
⇒ 0
-> $$ = nterm line ()
Stack now 0 1
Entering state 10
Reducing stack by rule 2 (line 35):
   $1 = nterm input ()
   $2 = nterm line ()
-> $$ = nterm input ()
Stack now 0
Entering state 1

The parser has returned into state 1, in which it is waiting for the next expression to evaluate, or for the end-of-file token, which causes the completion of the parsing.

Reading a token: Now at end of input.
Shifting token $end ()
Entering state 2
Stack now 0 1 2
Cleanup: popping token $end ()
Cleanup: popping nterm input ()

8.4.3 The YYPRINT Macro

Before %printer support, semantic values could be displayed using the YYPRINT macro, which works only for terminal symbols and only with the ‘yacc.c’ skeleton.

Macro: YYPRINT (stream, token, value);

If you define YYPRINT, it should take three arguments. The parser will pass a standard I/O stream, the numeric code for the token type, and the token value (from yylval).

For ‘yacc.c’ only. Obsoleted by %printer.

Here is an example of YYPRINT suitable for the multi-function calculator (see section Declarations for mfcalc):

%{
  static void print_token_value (FILE *, int, YYSTYPE);
  #define YYPRINT(File, Type, Value)            \
    print_token_value (File, Type, Value)
%}

… %% … %% …

static void
print_token_value (FILE *file, int type, YYSTYPE value)
{
  if (type == VAR)
    fprintf (file, "%s", value.tptr->name);
  else if (type == NUM)
    fprintf (file, "%d", value.val);
}

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