Generalized context-free grammar (GCFG) is a grammar formalism that expands oncontext-free grammars by adding potentially non-context-free composition functions to rewrite rules.^[1]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.

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${\displaystyle f(⟨x_1,...,x_m⟩,⟨y_1,...,y_n⟩,...)=\gamma }$, where${\displaystyle \gamma }$ 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${\displaystyle X\to f(Y,Z,...)}$, where${\displaystyle Y}$,${\displaystyle Z}$, ... 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.

A simple translation of a context-free grammar into a GCFG can be performed in the following fashion. Given the grammar in (1), which generates the palindrome language${\displaystyle \{w{w}^R:w\in \{a,b{\}}^{\ast }\}}$, where${\displaystyle w^R}$ is the string reverse of${\displaystyle w}$, we can define the composition functionconc as in (2a) and the rewrite rules as in (2b).

${\displaystyle S\to ϵ|aSa|bSb}$

1

${\displaystyle conc(⟨x⟩,⟨y⟩,⟨z⟩)=⟨xyz⟩}$

2a

${\displaystyle S\to conc(⟨ϵ⟩,⟨ϵ⟩,⟨ϵ⟩)|conc(⟨a⟩,S,⟨a⟩)|conc(⟨b⟩,S,⟨b⟩)}$

2b

The CF production ofabbbba is

S

aSa

abSba

abbSbba

abbbba

and the corresponding GCFG production is

${\displaystyle S\to conc(⟨a⟩,S,⟨a⟩)}$

${\displaystyle conc(⟨a⟩,conc(⟨b⟩,S,⟨b⟩),⟨a⟩)}$

${\displaystyle conc(⟨a⟩,conc(⟨b⟩,conc(⟨b⟩,S,⟨b⟩),⟨b⟩),⟨a⟩)}$

${\displaystyle conc(⟨a⟩,conc(⟨b⟩,conc(⟨b⟩,conc(⟨ϵ⟩,⟨ϵ⟩,⟨ϵ⟩),⟨b⟩),⟨b⟩),⟨a⟩)}$

${\displaystyle conc(⟨a⟩,conc(⟨b⟩,conc(⟨b⟩,⟨ϵ⟩,⟨b⟩),⟨b⟩),⟨a⟩)}$

${\displaystyle conc(⟨a⟩,conc(⟨b⟩,⟨bb⟩,⟨b⟩),⟨a⟩)}$

${\displaystyle conc(⟨a⟩,⟨bbbb⟩,⟨a⟩)}$

${\displaystyle ⟨abbbba⟩}$

Weir (1988)^[1] describes two properties of composition functions, linearity and regularity. A function defined as${\displaystyle f(x_1,...,x_n)=...}$ is linear if and only if each variable appears at most once on either side of the=, making${\displaystyle f(x)=g(x,y)}$ linear but not${\displaystyle f(x)=g(x,x)}$. A function defined as${\displaystyle f(x_1,...,x_n)=...}$ is regular if the left hand side and right hand side have exactly the same variables, making${\displaystyle f(x,y)=g(y,x)}$ regular but not${\displaystyle f(x)=g(x,y)}$ or${\displaystyle f(x,y)=g(x)}$.

A grammar in which all composition functions are both linear and regular is called a Linear Context-free Rewriting System (LCFRS). LCFRS is aproper 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 thanlinear-indexed grammars and theirweakly equivalent varianttree adjoining grammars (TAGs).^[2]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 withmultiple context-free grammar (MCFGs[1]).^[3] andminimalist grammars (MGs). The languages generated by LCFRS (and their weakly equivalents) can be parsed inpolynomial time.^[4]

• Range concatenation grammar

• Formal languages
• Grammar frameworks

• CS1: long volume value
• Articles with short description
• Short description matches Wikidata
• Use American English from January 2019
• All Wikipedia articles written in American English