Associativity of operators

Our grammar gives left associativity. That is, if you traverse the parse tree in postorder and perform the indicated arithmetic you will evaluate the string left to right. Thus 8-8-8 would evaluate to -8. If you wished to generate right associativity (normally exponentiation is right associative, so 2**3**2 gives 512 not 64), you would change the first two productions to

  list → digit + list
  list → digit - list

Produce in class the parse tree for 7+4-5 with this new grammar.

Precedence of operators

We normally want * to have higher precedence than +. We do this by using an additional nonterminal to indicate the items that have been multiplied. The example below gives the four basic arithmetic operations their normal precedence unless overridden by parentheses. Redundant parentheses are permitted. Equal precedence operations are performed left to right.

  expr   → expr + term | expr - term | term
  term   → term * factor | term / factor | factor
  factor → digit | ( expr )
  digit  → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

We use | to indicate that a nonterminal has multiple possible right hand side. So

  A → B | C

is simply shorthand for

  A → B
  A → C

Do the examples 1+2/3-4*5 and (1+2)/3-4*5 on the board.

Note how the precedence is enforced by the grammar; slick!

Statements

Keywords are very helpful for distinguishing statements from one another.

stmt → id := expr
     | if expr then stmt
     | if expr then stmt else stmt
     | while expr do stmt
     | begin opt-stmts end
opt-stmts → stmt-list | ε
stmt-list → stmt-list ; stmt | stmt

Remarks:

1. opt-stmts stands for optional statements. The begin-end block can be empty in some languages.
2. The ε (epsilon) stands for the empty string.
3. The use of epsilon productions will add complications.
4. Some languages do not permit empty blocks For example, Ada has a nullstatement, which does nothing when executed, for this purpose.
5. The above grammar is ambiguous!
6. The notorious “dangling else” problem.
7. How do you parse if x then if y then z=1 else z=2?