[PATCH 4/5] graphs: documentation

[Theophile Ranquet]

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.
---
 NEWS                        |   9 ++++
 TODO                        |  13 ++++++
 doc/Makefile.am             |  27 +++++++++++
 doc/bison.texi              | 110 ++++++++++++++++++++++++++++++++++++++++++++
 doc/figs/example-reduce.dot |  11 +++++
 doc/figs/example-reduce.txt |  16 +++++++
 doc/figs/example-shift.dot  |   9 ++++
 doc/figs/example-shift.txt  |  13 ++++++
 8 files changed, 208 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 9476819..d1b6656 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 4f628a2..978b5c6 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 f695e22..9c650bf 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 $< >address@hidden
+       $(AM_V_at) mv address@hidden $@
+
+.dot.pdf:
+       $(AM_V_GEN) $(MKDIR_P) `echo "./$@" | sed -e 's,/[^/]*$$,,'`
+       $(AM_V_at) dot -Tpdf -Gmargin=0 $< >address@hidden
+       $(AM_V_at) mv address@hidden $@
+
+.dot.png:
+       $(AM_V_GEN) $(MKDIR_P) `echo "./$@" | sed -e 's,/[^/]*$$,,'`
+       $(AM_V_at) dot -Tpng $< >address@hidden
+       $(AM_V_at) mv address@hidden $@
+
 ## -------------- ##
 ## Doxygenation.  ##
 ## -------------- ##
diff --git a/doc/bison.texi b/doc/bison.texi
index 8e8e9bb..4cca463 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.
 
address@hidden ================================================= Graphical 
Representation
+
address@hidden Graphviz
address@hidden Visualizing Your Parser
address@hidden 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
address@hidden, , Invoking Bison}).  Its name is made by removing
address@hidden 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:
+
address@hidden
+%%
address@hidden
+exp: a ";" | b ".";
+a: "0";
+b: "0";
address@hidden group
address@hidden 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
address@hidden, , Debugging Your Parser} for a detailled analysis of the
+textual report.
+
address@hidden 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.
+
address@hidden 1
+
+The transitions are represented as directed edges between the current and
+the target states.
+
address@hidden 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:
+
address@hidden
address@hidden
+state 3
+
+    1 exp: a . ";"
+
+    ";"  shift, and go to state 6
address@hidden group
address@hidden example
+
+A Graphviz rendering of this portion of the graph could be:
+
address@hidden @image{figs/example-shift, 100pt}
+
address@hidden 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}:
address@hidden
+state 1
+
+    3 a: "0" .  [";"]
+    4 b: "0" .  ["."]
+
+    "."       reduce using rule 4 (b)
+    $default  reduce using rule 3 (a)
address@hidden example
+
+A Graphviz rendering of this portion of the graph could be:
+
address@hidden @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".
+
address@hidden 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.
+
address@hidden ================================================= 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 0000000..fdd99c5
--- /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 0000000..ec522cd
--- /dev/null
+++ b/doc/figs/example-reduce.txt
@@ -0,0 +1,16 @@
+      /*-----------------.
+      |     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 0000000..995ba0e
--- /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 0000000..f8d387d
--- /dev/null
+++ b/doc/figs/example-shift.txt
@@ -0,0 +1,13 @@
+/*---------------.
+|    State 3     |
+| 1 exp: a . ";" |
+`----------------*/
+         |
+         | ";"
+         |
+         v
+/*---------------.
+|    State 6     |
+| 1 exp: a ";" . |
+`---------------*/
+
-- 
1.7.11.4