Metal and yacc

Metal is implemented using yacc and lex, so grammars you specify must belong to the class LALR(1). Making the parser involves compiling a Yacc program which may signal shift-reduce conflicts or reduce-reduce conflicts in the concrete syntax. These conflicts, not always harmful, should be resolved by making the concrete syntax LALR(1). You will find that the language Exp, as we have defined it above, contains two shift-reduce conflicts. They concern the production rules for plus and minus:

 
      <exp> ::= <exp> "+" <factor> ;

      <exp> ::= <exp> "-" <factor> ;

These conflict with the production rule concerning assign:

 
      <exp> ::= <var> ":=" <exp>  ;

To picture why this is the case, suppose we have the expression:

a := b + c

We could parse it in two ways, by reducing the assign operator first:

+ c

or, since in the abstract syntax the assignment statement is a valid expression (i.e., can be part of an addition), by shifting first, and reducing the plus operator before the assign operator:

a :=

This is how we would rather interpret the expression. In the concrete syntax, we have not specified the precedences between the operators assign and plus and minus. By default, Yacc resolves the conflict by choosing the shift, but this treatment may not always be desirable or correct. Fortunately, in our case, this is what we want, so we can live with the conflict. To eliminate the conflicts we have two options:

Add another token at the end of the assign production rule that allows Yacc to look ahead and resolve the conflict (the language is then LALR(1)). Unfortunately, this changes the concrete syntax of the language, which we don't want to do.
Give the assign operator a higher priority by creating another non-terminal level (as we did for prod.)

To give assign a higher priority, we redefine the ambiguous part of the concrete syntax:

 
...
      <exp_s> ::= <assign> ;
         exp_s-list ((<assign>))
      <exp_s> ::= <exp_s> ";" <assign> ;
         exp_s-post (<exp_s>, <assign>)
      <assign> ::= <var> ":=" <exp>  ;
         assign (<var>, <exp>)
      <assign> ::= <exp> ;
         <exp> 
      <exp> ::= <factor> ;
         <factor>
      <exp> ::= <exp> "+" <factor> ;
         plus (<exp>, <factor>)
      <exp> ::= <exp> "-" <factor> ;
         minus (<exp>, <factor>)
...

The parser generated from this definition requires us to add grouping parentheses for nested assignment statements:

A := (B := 3 + 4)

Tutorial