Grammars

Some, but not all languages are describable by a grammar. Languages which are describable by a grammar are typically describable by more than one grammar. According to the definition above the language is the set of lists of tokens, not any particular way of describing which lists belong to the subset.

Here we mean, by the term grammar, a finite set of grammar rules which describe how more complicated expressions are built up from simpler ones. What we’ve considered so far are context free grammars, which always replace a single symbol by a list of zero or more symbols. More complicated grammar rules might allow the replacement of one list of symbols with another list of symbols. That takes us into the world of context sensitive grammars, a world you are well advised to avoid if possible.

Normally we are only interested in a language if its lists of tokens have some sort of interpretation, but it’s important to understand that that’s not part of either the language or the grammar. In linguistic terms, we’re currently discussing only syntax, not semantics.