Generalized context-free grammar
Generalized context-free grammar (GCFG) is a grammar formalism that expands on context-free grammars by adding potentially non-context-free composition functions to rewrite rules. Head grammar (and its weak equivalents) is an instance of such a GCFG which is known to be especially adept at handling a wide variety of non-CF properties of natural language. Description. A GCFG consists of two components: a set of composition functions that combine string tuples, and a set of rewrite rules. The composition functions all have the form formula_1, where formula_2 is either a single string tuple , or some use of a (potentially different) composition function which reduces to a string tuple. Rewrite rules look like formula_3, where formula_4, formula_5, ... are string tuples or non-terminal symbols. The rewrite semantics of GCFGs is fairly straightforward. An occurrence of a non-terminal symbol is rewritten using rewrite rules as in a context-free grammar, eventually yielding just compositions (composition functions applied to string tuples or other compositions). The composition functions are then applied, successively reducing the tuples to a single tuple. Example. A simple translation of a context-free grammar into a GCFG can be performed in the  following fashion. Given the grammar in (), which generates the palindrome language formula_6, where formula_7 is the string reverse of formula_8, we can define the composition function "conc" as in () and the rewrite rules as in (). The CF production of "" is and the corresponding GCFG production is Linear Context-free Rewriting Systems (LCFRSs). Weir (1988) describes two properties of composition functions, linearity and regularity. A function defined as formula_17 is linear if and only if each variable appears at most once on either side of the "=", making formula_18 linear but not formula_19. A function defined as formula_17 is regular if  the left hand side and right hand side have exactly the same variables, making formula_21 regular but not formula_18 or formula_23. A grammar in which all composition functions are both linear and regular is called a Linear Context-free Rewriting System (LCFRS). LCFRS is a proper subclass of the GCFGs, i.e. it has strictly less computational power than the GCFGs as a whole. On the other hand, LCFRSs are strictly more expressive than linear-indexed grammars and their weakly equivalent variant tree adjoining grammars (TAGs). Head grammar is another example of an LCFRS that is strictly less powerful than the  class of LCFRSs as a whole. LCFRS are weakly equivalent to (set-local) "multicomponent" TAGs (MCTAGs) and also with multiple context-free grammar (MCFGs ). and minimalist grammars (MGs). The languages generated by LCFRS (and their weakly equivalents) can be parsed in polynomial time.