From fc4fdd623e7613c002f7c7d6cb73b4ab4bb5b494 Mon Sep 17 00:00:00 2001 From: Theophile Ranquet Date: Thu, 18 Oct 2012 15:38:32 +0000 Subject: [PATCH] graphs: documentation Note that 'make web-manual' fails. * NEWS: Document these changes. * doc/Makefile.am: Adjust to generate example files. * doc/bison.texi: Add a Graphviz section after "Understanding::", the section describing the .output file, because these are similar. * doc/figs/example-reduce.dot, doc/figs/example-reduce.txt, doc/figs/example-shift.dot, doc/figs/example-shift.txt: New, minimal examples to illustrate the documentation. Signed-off-by: Akim Demaille --- NEWS | 9 +++ TODO | 13 +++++ doc/Makefile.am | 27 +++++++++ doc/bison.texi | 110 ++++++++++++++++++++++++++++++++++++ doc/figs/example-reduce.dot | 11 ++++ doc/figs/example-reduce.txt | 15 +++++ doc/figs/example-shift.dot | 9 +++ doc/figs/example-shift.txt | 12 ++++ 8 files changed, 206 insertions(+) create mode 100644 doc/figs/example-reduce.dot create mode 100644 doc/figs/example-reduce.txt create mode 100644 doc/figs/example-shift.dot create mode 100644 doc/figs/example-shift.txt diff --git a/NEWS b/NEWS index 9476819e..d1b66564 100644 --- a/NEWS +++ b/NEWS @@ -84,6 +84,15 @@ GNU Bison NEWS position_type are deprecated in favor of api.location.type and api.position.type. +** Graphviz improvements + + The graphical presentation of the states is more readable: their shape is + now rectangular, the state number is clearly displayed, and the items are + numbered and left-justified. + + The reductions are now explicitly represented as transitions to other + diamond shaped nodes. + * Noteworthy changes in release 2.6.2 (2012-08-03) [stable] ** Bug fixes diff --git a/TODO b/TODO index 4f628a20..978b5c6f 100644 --- a/TODO +++ b/TODO @@ -1,4 +1,17 @@ * Short term +** Graphviz display code thoughts +The code for the --graph option is over two files: print_graph, and +graphviz. I believe this is because Bison used to also produce VCG graphs, +but since this is no longer true, maybe we could consider these files for +fusion. + +Little effort factoring seems to have been given to factoring in these files, +and their print-xml and print counterpart. We would very much like to re-use +the pretty format of states from .output in the .dot + +Also, the underscore in print_graph.[ch] isn't very fitting considering +the dashes in the other filenames. + ** Variable names. What should we name `variant' and `lex_symbol'? diff --git a/doc/Makefile.am b/doc/Makefile.am index f695e22d..9c650bf3 100644 --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -96,6 +96,33 @@ PREPATH = $(top_builddir)/src nodist_man_MANS = yacc.1 +## ----------------------------- ## +## Graphviz examples generation. ## +## ----------------------------- ## + +CLEANDIRS += figs +EXTRA_DIST += figs/example-reduce.dot figs/example-shift.dot +SUFFIXES += .dot .eps .pdf .png + +bison.dvi: figs/example-reduce.eps figs/example-shift.eps +bison.html: figs/example-reduce.png figs/example-shift.png +bison.pdf: figs/example-reduce.pdf figs/example-shift.pdf + +.dot.eps: + $(AM_V_GEN) $(MKDIR_P) `echo "./$@" | sed -e 's,/[^/]*$$,,'` + $(AM_V_at) dot -Teps $< >$@.tmp + $(AM_V_at) mv $@.tmp $@ + +.dot.pdf: + $(AM_V_GEN) $(MKDIR_P) `echo "./$@" | sed -e 's,/[^/]*$$,,'` + $(AM_V_at) dot -Tpdf -Gmargin=0 $< >$@.tmp + $(AM_V_at) mv $@.tmp $@ + +.dot.png: + $(AM_V_GEN) $(MKDIR_P) `echo "./$@" | sed -e 's,/[^/]*$$,,'` + $(AM_V_at) dot -Tpng $< >$@.tmp + $(AM_V_at) mv $@.tmp $@ + ## -------------- ## ## Doxygenation. ## ## -------------- ## diff --git a/doc/bison.texi b/doc/bison.texi index 8e8e9bb6..4cca4636 100644 --- a/doc/bison.texi +++ b/doc/bison.texi @@ -294,6 +294,7 @@ Handling Context Dependencies Debugging Your Parser * Understanding:: Understanding the structure of your parser. +* Graphviz:: Getting a visual representation of the parser. * Tracing:: Tracing the execution of your parser. Tracing Your Parser @@ -8093,6 +8094,7 @@ automaton, and how to enable and understand the parser run-time traces. @menu * Understanding:: Understanding the structure of your parser. +* Graphviz:: Getting a visual representation of the parser. * Tracing:: Tracing the execution of your parser. @end menu @@ -8509,6 +8511,114 @@ precedence of @samp{/} with respect to @samp{+}, @samp{-}, and @samp{*}, but also because the associativity of @samp{/} is not specified. +@c ================================================= Graphical Representation + +@node Graphviz +@section Visualizing Your Parser +@cindex dot + +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 @option{--graph} option is specified (see +@pxref{Invocation, , Invoking Bison}). Its name is made by removing +@samp{.tab.c} or @samp{.c} from the parser implementation file name, and +adding @samp{.dot} instead. If the grammar file is @file{foo.y}, the +Graphviz output file is called @file{foo.dot}. + +The following grammar file, @file{rr.y}, will be used in the sequel: + +@example +%% +@group +exp: a ";" | b "."; +a: "0"; +b: "0"; +@end group +@end example + +The graphical output is very similar to the textual one, and as such it is +easier understood by making direct comparisons between them. See +@ref{Debugging, , Debugging Your Parser} for a detailled analysis of the +textual report. + +@subheading Graphical Representation of States + +The items (pointed 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 @option{--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. + +@sp 1 + +The transitions are represented as directed edges between the current and +the target states. + +@subheading Graphical Representation of Shifts + +Shifts are shown as solid arrows, labelled with the lookahead token for that +shift. The following describes a reduction in the @file{rr.output} file: + +@example +@group +state 3 + + 1 exp: a . ";" + + ";" shift, and go to state 6 +@end group +@end example + +A Graphviz rendering of this portion of the graph could be: + +@center @image{figs/example-shift, 100pt} + +@subheading 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 labelled 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 @file{rr.output}: +@example +state 1 + + 3 a: "0" . [";"] + 4 b: "0" . ["."] + + "." reduce using rule 4 (b) + $default reduce using rule 3 (a) +@end example + +A Graphviz rendering of this portion of the graph could be: + +@center @image{figs/example-reduce, 120pt} + +When unresolved conflicts are present, because in deterministic parsing +a single decision can be made, Bison can arbitrarily choose to disable a +reduction, see @ref{Shift/Reduce, , 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, labelled "Acc". + +@subheading Graphical representation of go tos + +The @samp{go to} jump transitions are represented as dotted lines bearing +the name of the rule being jumped to. + +@c ================================================= Tracing @node Tracing @section Tracing Your Parser diff --git a/doc/figs/example-reduce.dot b/doc/figs/example-reduce.dot new file mode 100644 index 00000000..fdd99c5d --- /dev/null +++ b/doc/figs/example-reduce.dot @@ -0,0 +1,11 @@ +digraph "reduce.y" +{ + node [fontname=courier shape=box] + edge [fontname=courier] + + 1 [label="State 1\n 3 a: \"0\" . [\".\"]\l 4 b: \"0\" . [\";\"]\l"] + 1 -> "1R3" [label="" style=solid] + "1R3" [style=filled shape=diamond fillcolor=yellowgreen label="R3"] + 1 -> "1R4" [label="[\";\"]" style=solid] + "1R4" [style=filled shape=diamond fillcolor=yellowgreen label="R4"] +} diff --git a/doc/figs/example-reduce.txt b/doc/figs/example-reduce.txt new file mode 100644 index 00000000..19df1564 --- /dev/null +++ b/doc/figs/example-reduce.txt @@ -0,0 +1,15 @@ + .------------------. + | State 1 | + | 3 a: "0" . [";"] | + | 4 b: "0" . ["."] | + `------------------' + / \ + / \ ["."] + / \ + v v + . . + / \ / \ + / R \ / R \ +(green) \ 3 / \ 4 / (green) + \ / \ / + . . diff --git a/doc/figs/example-shift.dot b/doc/figs/example-shift.dot new file mode 100644 index 00000000..995ba0e4 --- /dev/null +++ b/doc/figs/example-shift.dot @@ -0,0 +1,9 @@ +digraph "shift.y" +{ + node [fontname=courier shape=box] + edge [fontname=courier] + + 3 [label="State 3\n 1 exp: a . \".\"\l"] + 3 -> 6 [style=solid label="\".\""] + 6 [label="State 6\n 1 exp: a \".\" .\l"] +} diff --git a/doc/figs/example-shift.txt b/doc/figs/example-shift.txt new file mode 100644 index 00000000..43b14122 --- /dev/null +++ b/doc/figs/example-shift.txt @@ -0,0 +1,12 @@ +.----------------. +| State 3 | +| 1 exp: a . ";" | +`----------------' + | + | ";" + | + v +.----------------. +| State 6 | +| 1 exp: a ";" . | +`----------------' -- 2.45.2