A Unifying Framework for Concatenation-based Grammar Formalisms

Linear Context Free Rewriting Systems (LCFRS, [Wei88]) are a general class of trans-context-free grammar systems; it is the largest well-known class of mildly context sensitive grammar; languages recognized by LCFRS strictly include those generated by the HG, TAG, LIG, CCG family. (Parallel) Multiple Context-Free Grammar (PMCFG, [KNSK92]) is a straightforward extension of LCFRS. Literal Movement Grammars, introduced by the author of this paper in [Gro95c], are a form of CFG augmented with inherited string-valued attributes. LCFRS, PMCFG and LMG are primarily aimed at the analysis of natural language. String Attributed Grammars are the concatenative variant of the attribute grammar formalism, which is widely used in programming language semantics. The properties of the class of attribute output languages OUT(SAG) are studied in [Eng86]. We present an attractive general purpose grammar formalism, concatenative predicate grammar, in which all the mentioned formalisms can be represented. This results in both a more readable notation, and an elegant hierarchical classification of the grammar formalisms.