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.
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 JFlex and CUPS, express your grammars in JFlex and CUPS.