Working through WACC – chapter 3 , binary operators

Now we get down to some serious parsing.

We have to care about operator associativity (left or right) and operator precedence. Again I wont go into details here because the book does an excellent job.

There are choices presented however and I will say what I did. Page 51 talks about ‘The adequate solution’. This is what I did in previous language projects, but I decided to go with the precedence aware parser presented next. When I got stuck later on in the extra credit for chapter 5 I wondered about this decision.

Confusing EBNF

I spent a long long time trying to reconcile

• Listing 3-4 , the EBNF of the C subset to be supported at the end of this chapter
• Listing 3-6 pseudo code to parse a sample snippet without precedence awareness
• Listing 3-7 pseudo-code to parse the full supported subset

I think that there is a mistake in 3-4, this line

<exp> ::= <factor> | <exp> <binop> <exp>

should be

<exp> ::= <factor> { <binop> <exp> }

The {} syntax has not been introduced in the book yet, but it means repeat 0 or more times.

If you look at 3-7 you can see that this is what the code is doing

parse_exp(tokens, min_prec):
  // always a factor
  left = parse_factor(tokens) 
  next_token = peek(tokens) 
  // loop taking binop exp pairs
  while next_token is a binary operator and precedence(next_token) >= min_prec:
    operator = parse_binop(tokens)
    right = parse_exp(tokens,precedence(next_token) + 1)
    left = Binary(operator, left, right)
    next_token = peek(tokens)
return left

Its interesting that the nand2tetris book has an almost identical line in its grammar for the Jack language in figure 10-2

expression: term (op term)*

Also listing 3-6 is not using the ENBF in 3-4, its in its own little world (note that it calls parse_factor on the line labelled 3, not parse_exp as the 3-4 ENBF suggests)

Extra Credit

This chapter has the first extra credit, implementing & | ^ << and >>

These are all straightforward