summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAkim Demaille <akim.demaille@gmail.com>2020-07-22 07:26:21 +0200
committerAkim Demaille <akim.demaille@gmail.com>2020-07-22 07:36:02 +0200
commit7d5474e979f63b1f0ad0db1db15edf1438eee427 (patch)
treeb72908c0bf557b5b185681b92a158007560815bc
parent6b78e50cef3c2cd8e6f4e7938be987e8769f8eef (diff)
downloadbison-7d5474e979f63b1f0ad0db1db15edf1438eee427.tar.gz
doc: catch up with the current display of cex
Unfortunately I found no way to use the ↳ glyph in Texinfo, so I used @arrow{} instead, which has a different width, so we have to have all the examples doubled, once for TeX, another for the rest of the world. * doc/bison.texi: Use the current display in the examples. * doc/calc.y, doc/ids.y, doc/if-then-else.y, doc/sequence.y: New.
-rw-r--r--doc/bison.texi276
-rw-r--r--doc/calc.y23
-rw-r--r--doc/ids.y5
-rw-r--r--doc/if-then-else.y13
-rw-r--r--doc/sequence.y10
5 files changed, 275 insertions, 52 deletions
diff --git a/doc/bison.texi b/doc/bison.texi
index 5312cbe2..115c111c 100644
--- a/doc/bison.texi
+++ b/doc/bison.texi
@@ -9889,10 +9889,11 @@ initially developed by Chinawat Isradisaikul and Andrew Myers
As a first example, see the example grammar of @ref{Shift/Reduce}, which
features on shift/reduce conflict:
+@c see doc/if-then-else.y
@example
$ @kbd{bison if-then-else.y}
-if-then-else.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
-if-then-else.y: warning: rerun with option '-Wcounterexamples' to generate conflict counterexamples [-Wother]
+if-then-else.y: @dwarning{warning}: 1 shift/reduce conflict [@dwarning{-Wconflicts-sr}]
+if-then-else.y: @dnotice{note}: rerun with option '-Wcounterexamples' to generate conflict counterexamples
@end example
@noindent
@@ -9900,32 +9901,46 @@ Let's rerun @command{bison} with the option
@option{-Wcex}/@option{-Wcounterexamples}@inlinefmt{info, (the following
output is actually in color)}:
-@ifhtml
+@ifnottex
@example
-Shift/reduce conflict on token "else":
+if-then-else.y: @dwarning{warning}: 1 shift/reduce conflict [@dwarning{-Wconflicts-sr}]
+if-then-else.y: @dwarning{warning}: shift/reduce conflict on token "else" [@dwarning{-Wcounterexamples}]
@group
- Example @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•} @blue{"else" stmt}
- Shift derivation @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt @arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{"else" stmt ]} @green{]} @yellow{]}
- Example @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•} @yellow{"else" stmt}
- Reduce derivation @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt @arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{]} @green{]} @yellow{"else" stmt ]}
+ Example: @yellow{"if" expr "then"} "if" expr "then" stmt • "else" stmt
+ Shift derivation
+ @yellow{if_stmt}
+ @yellow{↳ "if" expr "then"} @green{stmt}
+ @green{↳} @blue{if_stmt}
+ @blue{↳ "if" expr "then" stmt} @red{•} @blue{"else" stmt}
+ Example: @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•} @yellow{"else" stmt}
+ Reduce derivation
+ @yellow{if_stmt}
+ @yellow{↳ "if" expr "then"} @green{stmt} @yellow{"else" stmt}
+ @green{↳} @blue{if_stmt}
+ @blue{↳ "if" expr "then" stmt} @red{•}
@end group
@end example
-@end ifhtml
-@ifnothtml
-@smallexample
-Shift/reduce conflict on token "else":
+@end ifnottex
+@iftex
+@example
+if-then-else.y: @dwarning{warning}: 1 shift/reduce conflict [@dwarning{-Wconflicts-sr}]
+if-then-else.y: @dwarning{warning}: shift/reduce conflict on token "else" [@dwarning{-Wcounterexamples}]
@group
- Example
- @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•} @blue{"else" stmt}
+ Example: @yellow{"if" expr "then"} "if" expr "then" stmt • "else" stmt
Shift derivation
- @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt @arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{"else" stmt ]} @green{]} @yellow{]}
- Example
- @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•} @yellow{"else" stmt}
+ @yellow{if_stmt}
+ @yellow{@arrow{} "if" expr "then"} @green{stmt}
+ @green{@arrow{}} @blue{if_stmt}
+ @blue{@arrow{} "if" expr "then" stmt} @red{•} @blue{"else" stmt}
+ Example: @yellow{"if" expr "then"} @blue{"if" expr "then" stmt} @red{•} @yellow{"else" stmt}
Reduce derivation
- @yellow{if_stmt @arrow{} [ "if" expr "then"} @green{stmt @arrow{} [} @blue{if_stmt @arrow{} [ "if" expr "then" stmt} @red{•} @blue{]} @green{]} @yellow{"else" stmt ]}
+ @yellow{if_stmt}
+ @yellow{@arrow{} "if" expr "then"} @green{stmt} @yellow{"else" stmt}
+ @green{@arrow{}} @blue{if_stmt}
+ @blue{@arrow{} "if" expr "then" stmt} @red{•}
@end group
-@end smallexample
-@end ifnothtml
+@end example
+@end iftex
This shows two different derivations for one single expression. That
demonstrates that the grammar is ambiguous.
@@ -9935,6 +9950,7 @@ demonstrates that the grammar is ambiguous.
As a more delicate example, consider the example grammar of
@ref{Reduce/Reduce}, which features a reduce/reduce conflict:
+@c doc/sequence.y
@example
%%
sequence:
@@ -9950,32 +9966,112 @@ maybeword:
Bison generates the following counterexamples:
+@ifnottex
@example
+@group
$ @kbd{bison -Wcex sequence.y}
sequence.y: @dwarning{warning}: 1 shift/reduce conflict [@dwarning{-Wconflicts-sr}]
sequence.y: @dwarning{warning}: 2 reduce/reduce conflicts [@dwarning{-Wconflicts-rr}]
-Shift/reduce conflict on token "word":
- Example @red{•} @green{"word"}
- Shift derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{} [} @red{•} @green{"word" ]} @yellow{]}
- Example @red{•} @yellow{"word"}
- Reduce derivation @yellow{sequence @arrow{} [} @green{sequence @arrow{} [} @red{•} @green{]} @yellow{"word" ]}
-
-Reduce/reduce conflict on tokens $end, "word":
- Example @red{•}
- First derivation @yellow{sequence @arrow{} [} @red{•} @yellow{]}
- Example @red{•}
- Second derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{} [} @red{•} @green{]} @yellow{]}
-
-Shift/reduce conflict on token "word":
- Example @red{•} @green{"word"}
- Shift derivation @yellow{sequence @arrow{} [} @green{maybeword @arrow{} [} @red{•} @green{"word" ]} @yellow{]}
- Example @red{•} @yellow{"word"}
- Reduce derivation @yellow{sequence @arrow{} [} @green{sequence @arrow{} [} @blue{maybeword @arrow{} [} @red{•} @blue{]} @green{]} @yellow{"word" ]}
-
+@end group
+@group
+sequence.y: @dwarning{warning}: shift/reduce conflict on token "word" [@dwarning{-Wcounterexamples}]
+ Example: @red{•} @green{"word"}
+ Shift derivation
+ @yellow{sequence}
+ @yellow{↳} @green{maybeword}
+ @green{↳} @red{•} @green{"word"}
+ Example: @red{•} @yellow{"word"}
+ Reduce derivation
+ @yellow{sequence}
+ @yellow{↳} @green{sequence} @yellow{"word"}
+ @green{↳} @red{•}
+@end group
+@group
+sequence.y: @dwarning{warning}: reduce/reduce conflict on tokens $end, "word" [@dwarning{-Wcounterexamples}]
+ Example: @red{•}
+ First reduce derivation
+ @yellow{sequence}
+ @yellow{↳} @red{•}
+ Example: @red{•}
+ Second reduce derivation
+ @yellow{sequence}
+ @yellow{↳} @green{maybeword}
+ @green{↳} @red{•}
+@end group
+@group
+sequence.y: @dwarning{warning}: shift/reduce conflict on token "word" [@dwarning{-Wcounterexamples}]
+ Example: @red{•} @green{"word"}
+ Shift derivation
+ @yellow{sequence}
+ @yellow{↳} @green{maybeword}
+ @green{↳} @red{•} @green{"word"}
+ Example: @red{•} @yellow{"word"}
+ Reduce derivation
+ @yellow{sequence}
+ @yellow{↳} @green{sequence} @yellow{"word"}
+ @green{↳} @blue{maybeword}
+ @blue{↳} @red{•}
+@end group
+@group
sequence.y:8.3-45: @dwarning{warning}: rule useless in parser due to conflicts [@dwarning{-Wother}]
8 | @dwarning{%empty @{ printf ("empty maybeword\n"); @}}
| @dwarning{^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
+@end group
@end example
+@end ifnottex
+@iftex
+@example
+@group
+$ @kbd{bison -Wcex sequence.y}
+sequence.y: @dwarning{warning}: 1 shift/reduce conflict [@dwarning{-Wconflicts-sr}]
+sequence.y: @dwarning{warning}: 2 reduce/reduce conflicts [@dwarning{-Wconflicts-rr}]
+@end group
+@group
+sequence.y: @dwarning{warning}: shift/reduce conflict on token "word" [@dwarning{-Wcounterexamples}]
+ Example: @red{•} @green{"word"}
+ Shift derivation
+ @yellow{sequence}
+ @yellow{@arrow{}} @green{maybeword}
+ @green{@arrow{}} @red{•} @green{"word"}
+ Example: @red{•} @yellow{"word"}
+ Reduce derivation
+ @yellow{sequence}
+ @yellow{@arrow{}} @green{sequence} @yellow{"word"}
+ @green{@arrow{}} @red{•}
+@end group
+@group
+sequence.y: @dwarning{warning}: reduce/reduce conflict on tokens $end, "word" [@dwarning{-Wcounterexamples}]
+ Example: @red{•}
+ First reduce derivation
+ @yellow{sequence}
+ @yellow{@arrow{}} @red{•}
+ Example: @red{•}
+ Second reduce derivation
+ @yellow{sequence}
+ @yellow{@arrow{}} @green{maybeword}
+ @green{@arrow{}} @red{•}
+@end group
+@group
+sequence.y: @dwarning{warning}: shift/reduce conflict on token "word" [@dwarning{-Wcounterexamples}]
+ Example: @red{•} @green{"word"}
+ Shift derivation
+ @yellow{sequence}
+ @yellow{@arrow{}} @green{maybeword}
+ @green{@arrow{}} @red{•} @green{"word"}
+ Example: @red{•} @yellow{"word"}
+ Reduce derivation
+ @yellow{sequence}
+ @yellow{@arrow{}} @green{sequence} @yellow{"word"}
+ @green{@arrow{}} @blue{maybeword}
+ @blue{@arrow{}} @red{•}
+@end group
+@group
+sequence.y:8.3-45: @dwarning{warning}: rule useless in parser due to conflicts [@dwarning{-Wother}]
+ 8 | @dwarning{%empty @{ printf ("empty maybeword\n"); @}}
+ | @dwarning{^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
+@end group
+@end example
+@end iftex
Each of these three conflicts, again, prove that the grammar is ambiguous.
For instance, the second conflict (the reduce/reduce one) shows that the
@@ -9989,6 +10085,7 @@ that are the same up until the dot. Most notably, this will happen when
your grammar requires a stronger parser (more lookahead, LR instead of
LALR). The following example isn't LR(1):
+@c doc/ids.y
@example
%token ID
%%
@@ -9999,13 +10096,58 @@ expr: %empty | expr ID ','
@command{bison} reports:
-@smallexample
-Shift/reduce conflict on token ID:
- First example @purple{expr} @red{•} @purple{ID ','} @green{ID} @yellow{$end}
- Shift derivation @yellow{$accept @arrow{} [} @green{s @arrow{} [} @blue{a @arrow{} [} @purple{expr @arrow{} [ expr} @red{•} @purple{ID ',' ]} @blue{]} @green{ID ]} @yellow{$end ]}
- Second example @blue{expr} @red{•} @green{ID} @yellow{$end}
- Reduce derivation @yellow{$accept @arrow{} [} @green{s @arrow{} [} @blue{a @arrow{} [ expr} @red{•} @blue{]} @green{ID ]} @yellow{$end ]}
-@end smallexample
+@ifnottex
+@example
+ids.y: @dwarning{warning}: 1 shift/reduce conflict [@dwarning{-Wconflicts-sr}]
+ids.y: @dwarning{warning}: shift/reduce conflict on token ID [@dwarning{-Wcounterexamples}]
+@group
+ First example: @purple{expr} @red{•} @purple{ID ','} @green{ID} @yellow{$end}
+ Shift derivation
+ @yellow{$accept}
+ @yellow{↳} @green{s} @yellow{$end}
+ @green{↳} @blue{a} @green{ID}
+ @blue{↳} @purple{expr}
+ @purple{↳ expr} @red{•} @purple{ID ','}
+ Second example: @blue{expr} @red{•} @green{ID} @yellow{$end}
+ Reduce derivation
+ @yellow{$accept}
+ @yellow{↳} @green{s} @yellow{$end}
+ @green{↳} @blue{a} @green{ID}
+ @blue{↳ expr} @red{•}
+@end group
+@group
+ids.y:4.4-7: @dwarning{warning}: rule useless in parser due to conflicts [@dwarning{-Wother}]
+ 4 | a: expr
+ | ^~~~
+@end group
+@end example
+@end ifnottex
+@iftex
+@example
+ids.y: @dwarning{warning}: 1 shift/reduce conflict [@dwarning{-Wconflicts-sr}]
+ids.y: @dwarning{warning}: shift/reduce conflict on token ID [@dwarning{-Wcounterexamples}]
+@group
+ First example: @purple{expr} @red{•} @purple{ID ','} @green{ID} @yellow{$end}
+ Shift derivation
+ @yellow{$accept}
+ @yellow{@arrow{}} @green{s} @yellow{$end}
+ @green{@arrow{}} @blue{a} @green{ID}
+ @blue{@arrow{}} @purple{expr}
+ @purple{@arrow{} expr} @red{•} @purple{ID ','}
+ Second example: @blue{expr} @red{•} @green{ID} @yellow{$end}
+ Reduce derivation
+ @yellow{$accept}
+ @yellow{@arrow{}} @green{s} @yellow{$end}
+ @green{@arrow{}} @blue{a} @green{ID}
+ @blue{@arrow{} expr} @red{•}
+@end group
+@group
+ids.y:4.4-7: @dwarning{warning}: rule useless in parser due to conflicts [@dwarning{-Wother}]
+ 4 | a: expr
+ | ^~~~
+@end group
+@end example
+@end iftex
This conflict is caused by the parser not having enough information to know
the difference between these two examples. The parser would need an
@@ -10041,6 +10183,7 @@ by default. As a consequence, the verbose output file is called
The following grammar file, @file{calc.y}, will be used in the sequel:
+@c doc/calc.y
@example
@group
%union
@@ -10084,7 +10227,7 @@ calc.y:19.1-7: @dwarning{warning}: nonterminal useless in grammar: useless [@dwa
19 | @dwarning{useless: STR;}
| @dwarning{^~~~~~~}
calc.y: @dwarning{warning}: 7 shift/reduce conflicts [@dwarning{-Wconflicts-sr}]
-calc.y: @dwarning{warning}: rerun with option '-Wcounterexamples' to generate conflict counterexamples [@dwarning{-Wother}]
+calc.y: @dnotice{note}: rerun with option '-Wcounterexamples' to generate conflict counterexamples
@end smallexample
Going back to the calc example, when given @option{--report=state},
@@ -10396,15 +10539,44 @@ When given @option{--report=counterexamples}, @command{bison} will generate
counterexamples within the report, augmented with the corresponding items
(@pxref{Counterexamples}).
+@ifnottex
+@example
+shift/reduce conflict on token '/':
+ 1 exp: exp '+' exp •
+ 4 exp: exp • '/' exp
+@group
+ Example: exp '+' exp • '/' exp
+ Shift derivation
+ exp
+ ↳ exp '+' exp
+ ↳ exp • '/' exp
+ Example: exp '+' exp • '/' exp
+ Reduce derivation
+ exp
+ ↳ exp '/' exp
+ ↳ exp '+' exp •
+@end group
+@end example
+@end ifnottex
+@iftex
@example
-Shift/reduce conflict on token '/':
+shift/reduce conflict on token '/':
1 exp: exp '+' exp •
4 exp: exp • '/' exp
- Example @yellow{exp '+'} @green{exp} @red{•} @green{'/' exp}
- Shift derivation @yellow{exp @arrow{} [ exp '+'} @green{exp @arrow{} [ exp} @red{•} @green{'/' exp ]} @yellow{]}
- Example @green{exp '+' exp} @red{•} @yellow{'/' exp}
- Reduce derivation @yellow{exp @arrow{} [} @green{exp @arrow{} [ exp '+' exp} @red{•} @green{]} @yellow{'/' exp ]}
+@group
+ Example: exp '+' exp • '/' exp
+ Shift derivation
+ exp
+ @arrow{} exp '+' exp
+ @arrow{} exp • '/' exp
+ Example: exp '+' exp • '/' exp
+ Reduce derivation
+ exp
+ @arrow{} exp '/' exp
+ @arrow{} exp '+' exp •
+@end group
@end example
+@end iftex
This shows two separate derivations in the grammar for the same @code{exp}:
@samp{e1 + e2 / e3}. The derivations show how your rules would parse the
@@ -15854,7 +16026,7 @@ London, Department of Computer Science, TR-00-12 (December 2000).
@c LocalWords: TokenKind Automake's rtti Wcounterexamples Chinawat PLDI
@c LocalWords: Isradisaikul tcite pcite rgbGreen colorGreen rgbYellow Wcex
@c LocalWords: colorYellow rgbRed colorRed rgbBlue colorBlue rgbPurple
-@c LocalWords: colorPurple ifhtml ifnothtml situ rcex
+@c LocalWords: colorPurple ifhtml ifnothtml situ rcex MERCHANTABILITY Wnone
@c Local Variables:
@c ispell-dictionary: "american"
diff --git a/doc/calc.y b/doc/calc.y
new file mode 100644
index 00000000..6f468b20
--- /dev/null
+++ b/doc/calc.y
@@ -0,0 +1,23 @@
+%union
+{
+ int ival;
+ const char *sval;
+}
+
+%token <ival> NUM
+%nterm <ival> exp
+%token <sval> STR
+%nterm <sval> useless
+
+%left '+' '-'
+%left '*'
+
+%%
+exp:
+ exp '+' exp
+| exp '-' exp
+| exp '*' exp
+| exp '/' exp
+| NUM
+;
+useless: STR;
diff --git a/doc/ids.y b/doc/ids.y
new file mode 100644
index 00000000..31a851ca
--- /dev/null
+++ b/doc/ids.y
@@ -0,0 +1,5 @@
+%token ID
+%%
+s: a ID
+a: expr
+expr: %empty | expr ID ','
diff --git a/doc/if-then-else.y b/doc/if-then-else.y
new file mode 100644
index 00000000..01e1f938
--- /dev/null
+++ b/doc/if-then-else.y
@@ -0,0 +1,13 @@
+%%
+stmt:
+ expr
+| if_stmt
+;
+
+if_stmt:
+ "if" expr "then" stmt
+| "if" expr "then" stmt "else" stmt
+;
+
+expr:
+ "identifier"
diff --git a/doc/sequence.y b/doc/sequence.y
new file mode 100644
index 00000000..2423759e
--- /dev/null
+++ b/doc/sequence.y
@@ -0,0 +1,10 @@
+%%
+sequence:
+ %empty
+| maybeword
+| sequence "word"
+;
+maybeword:
+ %empty
+| "word"
+;