JavaCFG is a command-line program for viewing derivation trees in context free grammars. The user specifies a context free grammar (represented in a text file) and a string to be parsed. Two resulting visual parse-trees are created. For example, after parsing the string "racecar" in the grammar of palindromes over the alphabet {a, c, e, r} I obtained the following derivation tree representations:
I use JavaCFG in my Computer Science Theory course to help illustrate derivation trees, and to automatically generate trees for exercises and exams. JavaCFG employs Earley's parsing algorithm which can handle any ε-free context free grammar. This has the advantage that the typical context free grammars encountered in computability theory are handled. Typical tools for generating derivation trees are designed for programming language applications and break down on even the simplest grammars, such as the standard grammar for palindromes. On the other hand, one should be aware that given an ambiguous grammar, JavaCFG returns only one derivation tree per string even though there may be (exponentially) many parse trees.
If you would like to try out JavaCFG you will need to have Java on your system. Then: