hackety org » Another Fun House Language Called Context-Free
September 25, 2007
(Like Logo but with incredible images.)
What are context free grammars?
A context free grammar is a description of a language in a set of rules. Each rule says how a single symbol can be expanded into a sequence of other symbols. Those symbols may, in turn, have rules and can be expanded again. Some symbols are terminals and have no rules. A legal sentence in the described language is a sequence of terminal symbols that can be produced starting with the start symbol of the grammar and proceeding via some sequence of expansions.
The process is considered context free because each expansion of a symbol via some rule can be done independently of any of the expansions of other symbols.
In Context Free, the only two terminals are the shapes CIRCLE and SQUARE. Given a starting shape, the program keeps expanding shapes that have rules until all that is left are terminal shapes, which are then drawn. In essence, the rendered images are legal sentences in the language described by the rules file!
For more about the mathematics of grammars, see Context-free grammar in Wikipedia.