• Develop a leftmost derivation for the integer 4520. How many steps are required for this derivation?
• Develop a rightmost derivation for the integer 4520. How many steps are required for this derivation?
• In general how many steps are required to derive an integer with an arbitrary number, say d, or Digits?

Reading section: 2.1.1, 2.1.2

Grammar 1:

Expr1 → Expr1 + Term1 | Expr1 * Term1 | Term1

Term1 → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |( Expr1 )

Grammar 2:

Expr2 → Expr2 + Term2 | Term2

Term2 → Term2 * Factor | Factor

Factor → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |( Expr2 )

• Drawing a parse tree for each of the following expressions using Grammar 1 and Grammar 2, respectively

• 5 + 4 * 3
• 5 * 4 + 3

• Compare the above two grammars and identify their differences.

Reading sections: 2.1.3, 2.1.4

3.      Question: What is the ambiguity of a programming language? What is the dangling "else" ambiguity? Show how the Java subgrammar for IfThenStatement eliminates any ambiguity in the if statement. That is, sketch the parse tree using the Java BNF rules, and then argue that no other parse trees can be found using these rules.

Reading sections: 2.1.5, Java website

4.      Question: The following grammar, G, generates numbers in binary notation:

C → C 0 | A 1 | 0

A → B 0 | C 1 | 1

B → A 0 | B 1

• Draw the syntax diagram.
• Show that the generated numbers are all multiples of 3 (Bonus).

Reading sections: 2.2

CSC521 only:

5.      Question: Write a program in Clite to sort an array of integers. The grammar of a small language Clite is given in the text.

Reading sections: 2.3, 2.5, Appendix A.