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.^[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(\langle x_{1},...,x_{m}\rangle ,\langle y_{1},...,y_{n}\rangle ,...)=\gamma }${\displaystyle f(\langle x_{1},...,x_{m}\rangle ,\langle y_{1},...,y_{n}\rangle ,...)=\gamma }, where ${\displaystyle \gamma }${\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,...)}${\displaystyle X\to f(Y,Z,...)}, where ${\displaystyle Y}${\displaystyle Y}, ${\displaystyle Z}${\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 \{ww^{R}:w\in \{a,b\}^{*}\}}${\displaystyle \{ww^{R}:w\in \{a,b\}^{*}\}}, where ${\displaystyle w^{R}}${\displaystyle w^{R}} is the string reverse of ${\displaystyle w}${\displaystyle w}, we can define the composition function conc as in (2a ) and the rewrite rules as in (2b ).

The CF production of abbbba is

S

aSa

abSba

abbSbba

abbbba

and the corresponding GCFG production is

${\displaystyle S\to conc(\langle a\rangle ,S,\langle a\rangle )}${\displaystyle S\to conc(\langle a\rangle ,S,\langle a\rangle )}

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle a\rangle )}${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle a\rangle )}

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle ),\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle ),\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,\langle \epsilon \rangle ,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,\langle \epsilon \rangle ,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )}

${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,\langle bb\rangle ,\langle b\rangle ),\langle a\rangle )}${\displaystyle conc(\langle a\rangle ,conc(\langle b\rangle ,\langle bb\rangle ,\langle b\rangle ),\langle a\rangle )}

${\displaystyle conc(\langle a\rangle ,\langle bbbb\rangle ,\langle a\rangle )}${\displaystyle conc(\langle a\rangle ,\langle bbbb\rangle ,\langle a\rangle )}

${\displaystyle \langle abbbba\rangle }${\displaystyle \langle abbbba\rangle }

Weir (1988)^[1] describes two properties of composition functions, linearity and regularity. A function defined as ${\displaystyle f(x_{1},...,x_{n})=...}${\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)}${\displaystyle f(x)=g(x,y)} linear but not ${\displaystyle f(x)=g(x,x)}${\displaystyle f(x)=g(x,x)}. A function defined as ${\displaystyle f(x_{1},...,x_{n})=...}${\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)}${\displaystyle f(x,y)=g(y,x)} regular but not ${\displaystyle f(x)=g(x,y)}${\displaystyle f(x)=g(x,y)} or ${\displaystyle f(x,y)=g(x)}${\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 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).^[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 with multiple context-free grammar (MCFGs [1]).^[3] and minimalist grammars (MGs). The languages generated by LCFRS (and their weakly equivalents) can be parsed in polynomial 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