diff options
author | Akim Demaille <akim.demaille@gmail.com> | 2020-07-22 07:26:21 +0200 |
---|---|---|
committer | Akim Demaille <akim.demaille@gmail.com> | 2020-07-22 07:36:02 +0200 |
commit | 7d5474e979f63b1f0ad0db1db15edf1438eee427 (patch) | |
tree | b72908c0bf557b5b185681b92a158007560815bc | |
parent | 6b78e50cef3c2cd8e6f4e7938be987e8769f8eef (diff) | |
download | bison-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.texi | 276 | ||||
-rw-r--r-- | doc/calc.y | 23 | ||||
-rw-r--r-- | doc/ids.y | 5 | ||||
-rw-r--r-- | doc/if-then-else.y | 13 | ||||
-rw-r--r-- | doc/sequence.y | 10 |
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" +; |