[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 6/6] graphs: documentation
From: |
Theophile Ranquet |
Subject: |
[PATCH 6/6] graphs: documentation |
Date: |
Wed, 10 Oct 2012 17:14:06 +0000 |
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 | 8 ++++
TODO | 13 ++++++
doc/Makefile.am | 24 ++++++++++
doc/bison.texi | 111 ++++++++++++++++++++++++++++++++++++++++++++
doc/figs/example-reduce.dot | 10 ++++
doc/figs/example-reduce.txt | 14 ++++++
doc/figs/example-shift.dot | 7 +++
doc/figs/example-shift.txt | 13 ++++++
8 files changed, 200 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 1fe419f..3ca6885 100644
--- a/NEWS
+++ b/NEWS
@@ -2,6 +2,14 @@ GNU Bison NEWS
* Noteworthy changes in release ?.? (????-??-??) [?]
+** Graphviz improvements
+
+ The reductions are now explicitly shown. Other improvements were made
+ to the display of states: the state number is now centered and called
+ "state N" instead of just a number, and the rules are now both numbered
+ and left-justified. An other change was done to the shape of the nodes: they
+ used to be boxes, they are now ellipses.
+
** Bug fixes
Bugs and portability issues in the test suite have been fixed.
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..762ea0b 100644
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -96,6 +96,30 @@ 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) `dirname '$@'`
+ $(AM_V_at) dot -Teps $< >$@
+
+.dot.pdf:
+ $(AM_V_GEN) $(mkdir_p) `dirname '$@'`
+ $(AM_V_at) dot -Tpdf $< >$@
+
+.dot.png:
+ $(AM_V_GEN) $(mkdir_p) `dirname '$@'`
+ $(AM_V_at) dot -Tpng $< >$@
+
## -------------- ##
## Doxygenation. ##
## -------------- ##
diff --git a/doc/bison.texi b/doc/bison.texi
index ce1ebd1..af08ceb 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
@@ -8075,6 +8076,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
@@ -8491,6 +8493,115 @@ 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
address@hidden/reduce automaton} corresponding to the Bison parser, a DOT file
can
+be generated.
+
+This file is generated when the @option{--graph} option is specified, see
address@hidden, , 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. Therefore, if the grammar file is @file{foo.y}, then the
+parser implementation file is called @file{foo.tab.c} by default. As
+a consequence, the Graphviz output file is called @file{foo.dot}.
+
+The following grammar file, @file{rr.y}, will be used in the sequel:
+
address@hidden
+%%
+exp: a ";" | b "." ;
+a : "0";
+b : "0";
+%%
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
@ref{Debugging, ,
+Undertanding} for a detailled analysis of the textual report.
+
address@hidden @code
address@hidden states
+
+This how a state is represented in the verbose file @file{rr.output}:
address@hidden
+state 3
+
+ 1 exp: a . ";"
+
+ ";" shift, and go to state 6
address@hidden example
+
+The rules for each state are grouped together in graph nodes. Their numbering
+is the same as in the verbose file. The following line is the @file{rr.dot}
+version of the previous state definition:
address@hidden
+3 [label="state 3\n1: exp -> a . \";\""]
address@hidden example
+
+Note that for states with several rules, those rules are separated by a \l,
+which is the DOT way of making a left justification of the label text.
+
address@hidden transitions
+
+The transitions are represented as directed edges between the current
+and the target states.
+
address@hidden @code
address@hidden shifts
+
+Shifts are shown as solid arrows, labelled with the lookahead token for that
+shift. From the previous example, the following line is the @file{rr.dot}
+version of the shift:
+
address@hidden
+3 -> 6 [style=solid label="\";\""]
address@hidden example
+
+A Graphviz rendering of this portion of the graph could be:
+
address@hidden/example-shift}
+
address@hidden 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, instead of the token, the label is "$default".
+
+This 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/example-reduce}
+
+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.
+
address@hidden go to
+
+The @samp{go to} jump transitions are represented as dotted lines bearing the
+name of the rule being jumped to.
address@hidden table
address@hidden table
+
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..720698d
--- /dev/null
+++ b/doc/figs/example-reduce.dot
@@ -0,0 +1,10 @@
+digraph "reduce.y"
+{
+node [shape=box]
+ 1 [label="state 1\n3: a -> \"0\" .[\";\"]\l4: b -> \"0\" .[\".\"]\l"]
+ 1 -> "1R3" [label="$default",style=solid]
+ "1R3"
[style=filled,shape=diamond,fillcolor=yellowgreen,label="R3",width=0,height=0]
+ 1 -> "1R4" [label="\".\"",style=solid]
+ "1R4"
[style=filled,shape=diamond,fillcolor=yellowgreen,label="R4",width=0,height=0]
+ }
+
diff --git a/doc/figs/example-reduce.txt b/doc/figs/example-reduce.txt
new file mode 100644
index 0000000..6017791
--- /dev/null
+++ b/doc/figs/example-reduce.txt
@@ -0,0 +1,14 @@
+ /*--------------------.
+ | state 1 |
+ | 3: a -> "0" . [";"] |
+ | 4: b -> "0" . ["."] |
+ `--------------------*/
+ / \
+ $default / \ "."
+ / \
+ 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..864f4df
--- /dev/null
+++ b/doc/figs/example-shift.dot
@@ -0,0 +1,7 @@
+digraph "shift.y"
+{
+node [shape=box]
+ 3 [label="state 3\n1: exp -> a . \";\"\l"]
+ 3 -> 6 [style=solid label="\";\""]
+ 6 [label="state 6\n1: exp -> a \";\" .\l"]
+}
diff --git a/doc/figs/example-shift.txt b/doc/figs/example-shift.txt
new file mode 100644
index 0000000..a628567
--- /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
- Re: [PATCH 3/6] graphs: style: use left justification for states, (continued)
- Re: [PATCH 3/6] graphs: style: use left justification for states, Akim Demaille, 2012/10/11
- Re: [PATCH 3/6] graphs: style: use left justification for states, Théophile Ranquet, 2012/10/11
- Re: [PATCH 3/6] graphs: style: use left justification for states, Théophile Ranquet, 2012/10/11
- Re: [PATCH 3/6] graphs: style: use left justification for states, Théophile Ranquet, 2012/10/11
- Re: [PATCH 3/6] graphs: style: use left justification for states, Akim Demaille, 2012/10/11
- Re: [PATCH 3/6] graphs: style: use left justification for states, Théophile Ranquet, 2012/10/11
- Re: [PATCH 3/6] graphs: style: use left justification for states, Théophile Ranquet, 2012/10/11
- Re: [PATCH 3/6] graphs: style: use left justification for states, Akim Demaille, 2012/10/11
[PATCH 5/6] graphs: show reductions, Theophile Ranquet, 2012/10/10
[PATCH 4/6] graphs: style: prefix state number with "state", Theophile Ranquet, 2012/10/10
[PATCH 6/6] graphs: documentation,
Theophile Ranquet <=