LL(1) Table Generation

visualizations in support of

Teaching and Learning about Compilers

as part of the

Webworks Laboratory

LL(1) Table Generation

The study of compilers is a commonly required course in the curriculum of many computer science departments.  The two most commonly taught compiler constructions techniques are top-down (usually recursive descent), based on the theory of LL parsing, and bottom up, based on the theory of LR parsing.  Hand built compilers are nearly always recursive descent, as LR techniques are too complex for hand generated compilers.  

The construction of a recursive descent parser requires that First, Follow, and Predict sets be determined for the grammar of the programming language being parsed.   These sets lead in turn to the generation of the LL(k) table, which can be used to produce a table-driven parser for the language or to allow straightforward construction of a recursive descent parser.  Thus, understanding the principles behind the First, Follow, and Predict sets, and the LL(k) table, are crucial to understanding top down parsing.  Visualizations help instructors present these concepts, and help students learn them.

The Webworks laboratory is just beginning work on the animation of this aspect of compiling.  A preliminary animation was done by Jan Freuer, a foreign exchange student from Germany.  Jan's work is now being extended to include more opportunities for students to interact with (and therefore learn from) the animations. 

Click here to see what's happening so far.