Runner. Programming languages geek. App technologies evangelist at Apple.
CFG Experimenter
Many students learn best from concrete examples. Generating concrete examples of the algorithms used in LL(1) and LR(1) parsing can be tedious for instructors and students. CFG Experimenter is a tool for generating such examples, but beyond that, it is also scaffolding for a programming project where students learn the algorithms by implementing them.
CFG Experimenter includes algorithms for calculating First and Follow sets, canonical collections of LR(1) items, Action and Goto tables, and determining whether a context-free grammar is LL(1) or LR(1) parseable. CFG Experimenter can also animate LL(1) and LR(1) parsing, and allows students to “scrub through” the animation to check their understanding. Whether used as a programming project for students, or simply as a tool for instructors and students to generate and check examples, CFG Experimenter helps students better understand the algorithms used by most common parser-generators.
Resources
Using the Tool
To use the tool, download this jar file. Double click the jar file to run it.
Enter a context-free grammar in the Grammar pane, then click Check Grammar to analyze. The results appear under the Grammar Analysis tab. Download this zip file of sample grammars to experiment with.
Once you have a working grammar, enter a string to be parsed in the Input String pane. Click Parse. CFG Experimenter will parse the string and switch to the Parse Tree pane. Use the buttons and slider at the bottom of the pane to interact with the animated parse tree construction.
Using the Student Project
This pdf file describes the assignment that I gave to my Compiler Construction class. Students had two weeks to complete this very intense project. I asked them to implement the LL(1) algorithms in the first week and the LR(1) algorithms in the second.
This zip file contains the Eclipse project that I give to the students as scaffolding for the assignment. The scaffolding includes the complete user interface, including the parse tree animation. Only the code for the central parser-generator algorithms is omitted. The project requires an Eclipse Java development environment and the Cup/Lex Eclipse plug-in.
People
CFG Experimenter was designed and implemented by Curt Clifton and Brian T. Kelley. The development of CFG Experimenter was supported, in part, by the National Science Foundation under grant CCF-0707701.
Publications
CFG Experimenter: An Animated Parser-Generator Programming Project for Learning Compiler Algorithms Curtis Clifton and Brian T. Kelley 2010. Poster presented at SIGCSE ‘10: the 41st ACM technical symposium on computer science education.
Full text: CliftonKelley10ab.pdf
Abstract: Many students learn best from concrete examples. Generating concrete examples of the algorithms used in ll(1) and lr(1) parsing can be tedious for instructors and students. CFG Experimenter is a tool for generating such examples, but beyond that, it is also scaffolding for a programming project where students learn the algorithms by implementing them. CFG Experimenter includes algorithms for calculating first and follow sets, canonical collections of lr(1) items, action and goto tables, and determining whether a context-free grammar is ll(1) or lr(1) parseable. CFG Experimenter can also animate ll(1) and lr(1) parsing, and allows students to “scrub through” the animation to check their understanding. Whether used as a programming project for students, or simply as a tool for instructors and students to generate and check examples, CFG Experimenter helps students better understand the algorithms used by most common parser-generators.
Runner. Programming languages geek. App technologies evangelist at Apple.