Task 1.
Here is a simple context free grammar for arithmetic
expressions.
E → E+E | E*E | (E) | 0 | 1 | 2 | ...
Draw all parse-trees
for the left-most and right-most derivations of the
following expressions. Discuss which number
each of the parse-trees 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 left-recursive? A grammar is
left-recursive if it has a reduction sequence (of one or
more steps) X → ... → Xσ.
Left-recursion is problematic because it makes some
kinds of parsers (top-down parsers) loop.
If your grammars are
left-recursive or ambiguous, could you rewrite them so
they are neither left-recursive nor ambiguous?
Task 4. If you are
already comfortable with lexer and/or parser generators,
express your grammars using such tools.
|