Task 1.
Here is a simple context free grammar for arithmetic
expressions.
E → E+E  E*E  (E)  0  1  2  ...
Draw all parsetrees
for the leftmost and rightmost derivations of the
following expressions. Discuss which number
each of the parsetrees would evaluate to (assuming
the natural rules of mathematics).
 16 * 17
 2 + 3 + 4
 2 * 3 + 4 * 5
Task 2. Translate
each of the following language descriptions into CFGs.
 The regular expression ((01*0)  (1(00)*1))? (where
R? is an abbreviation for R  ε).
 The regular expression ((01*0)  (1(00)*1))^{+}.
 Palindromes over {0, 1}, that is, strings that read
the same forwards and backwards such as "anna".
 The language given by the regular expression 0*1*
with the additional constraint that there must be more
0s than 1s. Consider the edge case where you have no
0s and no 1s.
Task 3. Check the grammars
you have devised in Task 2 for the following:
 Are your grammars ambiguous? Recall that a CFG is
ambiguous exactly when there is a string in its language
that has more than one parse tree.
 Are your grammars leftrecursive? A grammar is
leftrecursive if it has a reduction sequence (of one or
more steps) X → ... → Xσ.
Leftrecursion is problematic because it makes some
kinds of parsers (topdown parsers) loop.
If your grammars are
leftrecursive or ambiguous, could you rewrite them so
they are neither leftrecursive nor ambiguous?
Task 4. If you are
already comfortable with lexer and/or parser generators,
express your grammars using such tools.
