Tear-Insert-Fold grammars
Adrian Johnstone, Elizabeth A. Scott · 2010
Context Free Grammars (CFGs) are simple and powerful formalisms for defining languages (sets of strings) whose semantics are specified hierarchically --- the meaning of a string is determined by terminals and the meanings of substrings. This hierarchy is captured in the derivation tree corresponding to the string. Derivation trees usually contain more structure than is strictly required to determine the semantics of the string so in practice a simplified or abstract syntax tree is used as an internal representation of a concrete text. Indeed, much of the work of a compiler or source-source translator may be described in terms of stepwise transformation of such trees, culminating in a final traversal during which the translated text is output.