Tutorial Week 4
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.