8.3 Visualizing Your Parser

As another means to gain better understanding of the shift/reduce automaton corresponding to the Bison parser, a DOT file can be generated. Note that debugging a real grammar with this is tedious at best, and impractical most of the times, because the generated files are huge (the generation of a PDF or PNG file from it will take very long, and more often than not it will fail due to memory exhaustion). This option was rather designed for beginners, to help them understand LR parsers.

This file is generated when the --graph option is specified (see Invoking Bison). Its name is made by removing ‘.tab.c’ or ‘.c’ from the parser implementation file name, and adding ‘.gv’ instead. If the grammar file is foo.y, the Graphviz output file is called foo.gv. A DOT file may also be produced via an XML file and XSLT processing (see Visualizing your parser in multiple formats).

The following grammar file, rr.y, will be used in the sequel:

%%

exp: a ";" | b ".";
a: "0";
b: "0";

The graphical output (see Figure 8.1) is very similar to the textual one, and as such it is easier understood by making direct comparisons between them. See Debugging Your Parser, for a detailed analysis of the textual report.

Figure 8.1: A graphical rendering of the parser.

Graphical Representation of States

The items (dotted rules) for each state are grouped together in graph nodes. Their numbering is the same as in the verbose file. See the following points, about transitions, for examples

When invoked with --report=lookaheads, the lookahead tokens, when needed, are shown next to the relevant rule between square brackets as a comma separated list. This is the case in the figure for the representation of reductions, below.

The transitions are represented as directed edges between the current and the target states.

Graphical Representation of Shifts

Shifts are shown as solid arrows, labeled with the lookahead token for that shift. The following describes a reduction in the rr.output file:

State 3

    1 exp: a • ";"

    ";"  shift, and go to state 6

A Graphviz rendering of this portion of the graph could be:

Graphical Representation of Reductions

Reductions are shown as solid arrows, leading to a diamond-shaped node bearing the number of the reduction rule. The arrow is labeled with the appropriate comma separated lookahead tokens. If the reduction is the default action for the given state, there is no such label.

This is how reductions are represented in the verbose file rr.output:

State 1

    3 a: "0" •  [";"]
    4 b: "0" •  ["."]

    "."       reduce using rule 4 (b)
    $default  reduce using rule 3 (a)

A Graphviz rendering of this portion of the graph could be:

When unresolved conflicts are present, because in deterministic parsing a single decision can be made, Bison can arbitrarily choose to disable a reduction, see Shift/Reduce Conflicts. Discarded actions are distinguished by a red filling color on these nodes, just like how they are reported between square brackets in the verbose file.

The reduction corresponding to the rule number 0 is the acceptation state. It is shown as a blue diamond, labeled “Acc”.

Graphical Representation of Gotos

The ‘go to’ jump transitions are represented as dotted lines bearing the name of the rule being jumped to.