Exercises 2: Regular expressions and finite automata, BNFC

Programming Languages 2010

1. Implement a parser for regular expressions in BNFC. The parser should be able to correctly recognize the expression

    (letter | '_') (letter | digit | '_')*

and any other expression combining the same operators. As for precedences, Kleene star binds stronger than sequence, which binds stronger than union.

2. Write a regular expression for comments of the form /* ... */, where /* inside double quotes does not start a comment.

3. Construct an NFA and DFA for comments as in the previous exercise.

4. Write a program that removes tags from an HTML document, using one of the standard lexer tools. Start by writing a regular expression for tags. Test your program with the course web page.

5. Implement a parser for Lisp in BNFC. It should be able to parse the code example in http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp - which is actually a complete Lisp interpreter!