posts/yacc2dot.mdwn

   1 YACC precedence and shift/reduce errors
   2 =======================================
   3
   4 While I was working on a BibTeX parser, I ran into some trouble with
   5 shift/reduce errors in `yacc`.  The problem essentially boiled down
   6 to: How do you define implicit multiplication in `yacc`?
   7
   8 Keep reading for my intro to `yacc`, or, if you just want the simple
   9 solution, [skip to the end](#implicit_multiplication).
  10
  11 Related work
  12 ------------
  13
  14 After much googling about, I would like to recommend the following sources:
  15
  16 * David Beazley's [PLY documentation][DB] which has an good
  17   introduction to shift/reduce errors with a nice walkthrough
  18   shift/reduce example;
  19 * Stephen Johnson's [yacc introduction][SJ] (see Section 4: How the
  20   Parser Works), which helped me understand the state-stack concept
  21   which hadn't sunk in until then;
  22 * Leon Kaplan's [yaccviso documenation][LK], which reminded me that
  23   visualizations are good, and inspired my resurrection of the
  24   `yacc2dot` tool in Python; and
  25 * Xavier Leroy et al.'s [ocamlyacc documentation][XL],
  26   where rule-vs-operator precedence finally clicked.
  27
  28 For further details and entertaining browsing, you can take a slow
  29 meander through the [Bison manual][bison].
  30
  31 Tools
  32 -----
  33
  34 The following graphics were generated from the `y.output` files output
  35 by `yacc` using [[yacc2dot.py]] script and [Graphviz dot][graphviz].
  36
  37 Example 1: Single, explicit addition
  38 ------------------------------------
  39
  40 As a brief introduction to how parsers work, consider the *really*
  41 simple grammar
  42
  43 [[!inline pagenames="p.y" template="raw" feeds="no"]]
  44
  45 which generates the following `yacc` output and `dot` image:
  46
  47 [[!inline pagenames="p.output" template="raw" feeds="no"]]
  48 [[!img p.png alt="Visualization of plus-only grammar"
  49              title="Visualization of plus-only grammar" ]]
  50
  51 Parsing input like `X PLUS X` would look like
  52
  53 <table>
  54  <tr><th>Step</th><th>State stack</th><th>Symbol stack</th><th>Symbol queue</th><th>Action</th></tr>
  55  <tr><td>0</td><td>0</td><td>$accept</td><td>X PLUS X $end</td><td>Shift X</td></tr>
  56  <tr><td>1</td><td>01</td><td>$accept X</td><td>PLUS X $end</td><td>Shift PLUS</td></tr>
  57  <tr><td>2</td><td>013</td><td>$accept X PLUS</td><td>X $end</td><td>Shift X</td></tr>
  58  <tr><td>3</td><td>0135</td><td>$accept X PLUS X</td><td>$end</td><td>Reduce using rule 1, pop back to state 0, and goto state 2</td></tr>
  59  <tr><td>4</td><td>02</td><td>$accept expr</td><td>$end</td><td>Shift $end</td></tr>
  60  <tr><td>5</td><td>024</td><td>$accept expr $end</td><td></td><td>Accept using rule 0</td></tr>
  61 </table>
  62
  63 The key step here is 3-to-4.  We reduce using Rule 1
  64
  65     (1) expr: X PLUS X
  66
  67 Since there are three symbols on the rule's right hand side, we pop
  68 three symbols from the stack.  The symbols we pop match the right hand
  69 side, which is why we can apply the rule.  We also pop three *states*
  70 (1, 3, and 5), which returns us to state 0.  We look up state 0's
  71 action for rules reducing to expr, and see that we're supposed to go
  72 to state 2, so we do.  Whew!
  73
  74 It's a lot of words, and not very intuitive for me the first time
  75 around, but the underlying idea is pretty simple.
  76
  77 The tokens `$accept` and `$end` are inserted by the parser so it knows
  78 if the symbols left after parsing are acceptable or not.
  79
  80 The input token string `X PLUS X` is the only valid token string for
  81 this grammar.  For extra credit, you can figure out where other input
  82 strings go wrong.  For example, consider `X` and `X PLUS X PLUS X`.
  83
  84 More examples
  85 -------------
  86
  87 In my gradual work up to implicit multiplication, I went through the
  88 following progressively more complicated examples.
  89
  90 <table>
  91  <tr><th>grammar</th><th>yacc output</th><th>yacc2dot output</th><th>notes</th></tr>
  92  <tr><td>[[pr.y]]</td>
  93      <td>[[pr.output]]</td>
  94      <td>[[!ltio pr.png]]</td>
  95      <td>Recursive addition (allow X PLUS X PLUS X PLUS ...).  Already
  96        a shift/reduce error!</td></tr>
  97  <tr><td>[[pr_prec.y]]</td>
  98      <td>[[pr_prec.output]]</td>
  99      <td>[[!ltio pr_prec.png]]</td>
 100      <td>Add precedence (PLUS > X) to solve in favor of reduction.</td></tr>
 101  <tr><td>[[pt.y]]</td>
 102      <td>[[pt.output]]</td>
 103      <td>[[!ltio pt.png]]</td>
 104      <td>Explicit addition and multiplication with precedence.</td></tr>
 105  <tr><td>[[t_implicit.y]]</td>
 106      <td>[[t_implicit.output]]</td>
 107      <td>[[!ltio t_implicit.png]]</td>
 108      <td>Implicit multiplication.  Shift/reduce error, but no operator handle
 109        for assigning higher precedence to reduction...</td></tr>
 110 </table>
 111
 112 <a name="implicit_multiplication" />
 113 Implicit multiplication
 114 -----------------------
 115
 116 The lack of an operator handle to assign precedence to an
 117 operator-less rule had me stumped for a few days, until I found the
 118 [OCaml site][XL] with a nice, explicit listing of the shift/reduce
 119 decision process.
 120
 121 The shift/reduce decision is not a problem of which operator has a
 122 higher precedence, but about whether a given *token* has a higher
 123 precedence than a given *rule*.  All we have to do is assign
 124 precedence to *both* the tokens *and* the rules.
 125
 126 [[!inline pagenames="t_implicit_prec.y" template="raw" feeds="no"]]
 127
 128 which generates the following `yacc` output and `dot` image:
 129
 130 [[!inline pagenames="t_implicit_prec.output" template="raw" feeds="no"]]
 131
 132 [[!img t_implicit_prec.png
 133   alt="Visualization of implicit_multiplication grammar"
 134   title="Visualization of implicit multiplication grammar" ]]
 135
 136
 137 [DB]: http://www.dabeaz.com/ply/ply.html#ply_nn23
 138 [SJ]: http://dinosaur.compilertools.net/yacc/index.html
 139 [LK]: http://www.lo-res.org/~aaron/yaccviso/docu.pdf
 140 [XL]: http://caml.inria.fr/pub/docs/manual-ocaml/manual026.html#htoc140
 141 [bison]: http://www.gnu.org/software/bison/manual/
 142 [graphviz]: http://www.graphviz.org/
 143 [yaccviso]: http://directory.fsf.org/project/yaccviso/
 144
 145 [[!tag tags/programming]]
 146 [[!tag tags/python]]
 147 [[!tag tags/tools]]