Processing Grammars

CS2112 (Design, Use and Implementation of Programming Languages) currently uses Flex and Berkeley Yacc (Byacc) to illustrate language implementation. However, these tools look increasingly old-fashioned, and really need to be supplemented or replaced.

Facilities that could usefully be added, either to improve the tools or to improve students' understanding of them, include:

automatic translation of grammars (possibly including actions or attribute calculations) between BNF, EBNF, syntax diagrams, and the variety of BNF used by Flex and Byacc (possibly also automatically partitioning a grammar between Flex and Byacc)
parser "animation", so that students can see parsing happening step by step, both to understand the process, and to help spot ambiguities in a grammar (I intend to use a modification to Byacc devised by Jim Roskind that does some of this (example), but further improvement would be useful)
help with locating and removing errors in a grammar (e.g. ambiguities, such as those reported as shift-reduce or reduce-reduce conflicts) when creating a parser
help with handling grammatical errors in an input text when running the resulting parser (e.g. locating the error in the text, reporting the error in terms of the original grammar, and "repairing" the text sufficiently for the parser to continue processing the rest of the text)
help with defining abstract grammars from concrete grammars, and with building the corresponding parse trees

Most important of all, the tools must be simple, as students taking CS2112 have very little time available to learn and practice their use.

This project will consist of

searching for public-domain tools that can provide some of these features
creating some or all of the rest of these facilities, either
- by modifying the existing tools, or
- by writing further tools that can e.g. accept grammars written in EBNF and automatically output them in an enhanced form for use by the existing tools.

There is even the possibility of looking at other parsing algorithms, such as LL(n), particularly with a view to animating them to aid student understanding.

COURSE PREREQUISITES: CS2112
EQUIPMENT: Sun, using software available in the department