CFG Examples

We want to extend the programming language grammar that we had last week by adding conditionals and new kinds of statements. Conditionals have the form:

if a == b then
	statement 1
	statement 2
else
	statement 3
	statement 4
end

Our productions:

Cond -> if BoolExpr then 
            StatementList
        else
            StatementList
        end

Okay, the full list of productions is on the slides. Note that BoolExpr is missing things like boolean operators (&&, ||, !) and boolean variables and stuff. It only has comparisons.

There’s also a few examples of parse trees, which aren’t worth copying down in these notes.

Here’s the unambiguous grammar for expressions (without precedence) that wasn’t completed last lecture.

E -> Term | E + Term
Term -> Factor | Term * Factor
Factor -> (E) | num | id

Where num is a decimal number and id is a variable identifier.

The point of this is that terms can only be added to expressions, and terms can only be multiplied by factors. So if you have a string id * id + num, it would parse like this:

            E
          / | \
         E  + Term
        /       \
      Term     Factor
      / | \       \
   Term * Factor  num
     |      |
   Factor  id
     |
    id

No ambiguity here. And it also forces left-associativity.

Next recitation: scoping.