• Understand how some grammars require back-tracking to parse because it isn't possible to predict perfectly which production should be used.
• Understand how to do parsing using table-driven parsing and recursive descent parsing for LL(1) grammars

• Writing grammars
• Derivations
• Parse trees
• Unambiguous grammars

1. (2 points) Section 13.1 problem 1 ONLY part (a). Show the productions and show the parse tree. (International edition 12.1.1)
2. (2 points) Section 13.1 problem 2. Create ONLY two other sentences. (International edition 12.1.2)
3. (4 points) Give a grammar for the language Time of Day, which accepts strings such as those in the bulleted list below. In general the language has strings with hour times from 1 to 12, followed by a colon, followed by minute times from 00 to 59, and then either am or pm. (Use BNF notation and give good mnemonic names for concepts such as <Time of Day>, which is to be the start symbol, and <Single Hour Digit> for digits that are hour digits (i.e., 1 through 9 but not 0). Make sure that your grammar does not generate any strings that are not valid times.
   • 12:36 pm
   • 1:59 am
   • 4:00 pm
   • 2:45 am
4. (5 points) For the grammar <A> ::= <A><A> '+' | <A><A> '*' | 'a' and the string aa + a*
   • Give the leftmost derivation
   • Give the rightmost derivation
   • Give a parse tree
   • Is the grammar ambiguous or unambiguous? (Justify your answer)
   • Describe the language generated by this grammar
5. (6 points) Design grammars for the following languages:
   • The set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1
   • The set of all strings of 0s and 1s that are palindromes; that is, the string reads the same backward as forward
   • The set of all strings of 0s and 1s with an equal number of 0s and 1s
6. (5 points) Suppose that you are writing a new software development environment for a new programming language. In this new programing language, an expression can have two or more kinds of balanced parentheses. For example, Java expressions can have both round and square parentheses and both must be balanced; that is, every “(” must match “)”, and every “[” must match“]”. Write a grammar for strings of balanced parentheses of these two types. For example ( [ ] ( [ ( ) ] ) ) is in the language but [ ( ] ) is not.
7. (4 points) Suppose we want to implement a DDC (decimal digit calculator) compiler for the DDC language which performs arithmetic operations on integer arguments. The BNF grammar description below was written to describe the DDC language syntactically. Show the grammar is ambiguous given the input 4 - 3 - 2. Indicate the parse tree that gives the correct associativity.
   <expr> ::= <term> | <expr> <op1> <expr>
   <term> ::= <decimal arg> | <term> <op2> <decimal arg>
   <decimal arg> ::= <digit> |<decimal arg> <digit>
   <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   <op1> ::= + | -
   <op2> ::= * | /

These problems are not required or graded. These are here purely for those interested in working additional programs for deeper learning.

1. Fix the grammar in the last problem of the homework to be unambiguous. Show that it now gives the correct answer for the input string 4 - 3 - 2.
2. The following grammar for a fictitious operator '\$' is ambiguous. Demonstrate the ambiguity by creating two parse trees for the expression 2 \$ 3 \$ 0.
   • <number> ::= 0|1|2|3
   • <expression> ::= <number>
   • <expression> ::= <expression>$<expression>
3. Fix the grammar in previous problem so that it is not ambiguous. Is your grammar left associative or right associative?
4. The following grammar is not a simple LL(1) grammar. Without changing the language, modify the grammar so that it is simple LL(1).
   S → ABAe
   A → dB | aS | c
   B → AS | b
5. For the grammar in the previous problem, do the following.
   • Compute FIRST(ABAe).
   • Compute FIRST(AS) ∩ FIRST(b)
   • Although the grammar is not simple LL(1), why is it nevertheless LL(1)?