Alternate abstract syntaxes

Let's look at another possible abstract syntax for Exp which imparts more type information and editing freedom. Instead of creating a new operator for each binary operator:


      plus  -> EXP EXP ;
      minus  -> EXP EXP ;
      prod  -> EXP EXP ;

we may group all binary expressions under one operator with three tree descendents instead of two. The value of the atomic operator binop is a string that allows us to distinguish binary operators.


      bexp -> EXP BINOP EXP ;
      binop -> implemented as STRING ;
      BINOP ::= binop ;

and change the phylum EXP accordingly:


     EXP ::= bexp variable integer ... ;

When we compare the small trees constructed with both approaches in Figure , several advantages of the ``clever'' approach stand out:

Trees may be edited with more precision. For example, transforming x + 3 into x - 3 requires reanalyzing a much smaller subtree than would be the case with the simple approach.
The grammar is more concise, and so pretty printers and semantic tools will be smaller and less prone to error.

The primary advantage of the simple approach is its simplicity, so we prefer sticking with it for the rest of the tutorial.

Tutorial