Derivation Visualization for Context-Free Grammar Design: Helping Students Understand Context-Free Grammars

In Formal Languages and Automata Theory courses, students are exposed to context-free grammars. They are expected to learn how to develop grammars and how to derive words. Despite multiple classroom and textbook examples, some students find grammar design and word derivation difficult due to nondeterminism. A modern pedagogy uses a programming-based approach to introduce students to context-free grammars. Using this methodology, students can design, implement, validate, and verify context-free grammars. However, they find the design and development task challenging. This article presents a novel dynamic visualization tool to help students with grammar design, implementation, and verification. The tool presents the user with the stepwise construction of a derivation tree and with support to visualize whether nonterminal invariants hold. Empirical data from a small formative study suggests that students find the visualization tool useful to understand word derivation, to debug grammars, and to develop correctness proofs.