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 f(\langle x_1, ..., x_m \rangle, \langle y_1, ..., y_n \rangle, ...) = \gamma, where \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 X \to f(Y, Z, ...), where Y, 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. ==Example==
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 \{ ww^R : w \in \{a, b\}^{*} \}, where w^R is the string reverse of w, 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 : S \to conc(\langle a \rangle, S, \langle a \rangle) : conc(\langle a \rangle, conc(\langle b \rangle, S, \langle b \rangle), \langle a \rangle) : conc(\langle a \rangle, conc(\langle b \rangle, conc(\langle b \rangle, S, \langle b \rangle), \langle b \rangle), \langle a \rangle) : 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) : conc(\langle a \rangle, conc(\langle b \rangle, conc(\langle b \rangle, \langle \epsilon \rangle, \langle b \rangle), \langle b \rangle), \langle a \rangle) : conc(\langle a \rangle, conc(\langle b \rangle, \langle bb \rangle, \langle b \rangle), \langle a \rangle) : conc(\langle a \rangle, \langle bbbb \rangle, \langle a \rangle) : \langle abbbba \rangle ==Linear Context-free Rewriting Systems (LCFRSs)==