“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.

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

, where

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

, where

, ... 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 ({{EquationNote|1}}), which generates the palindrome language

, where

is the string reverse of

, we can define the composition function conc as in ({{EquationNote|2a}}) and the rewrite rules as in ({{EquationNote|2b}}).

Linear Context-free Rewriting Systems (LCFRSs)

Weir (1988)^[1] describes two properties of composition functions, linearity and regularity. A function defined as

is linear if and only if each variable appears at most once on either side of the =, making

linear but not

. A function defined as

is regular if the left hand side and right hand side have exactly the same variables, making

regular but not

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 ).^[3] and minimalist grammars (MGs). The languages generated by LCFRS (and their weakly equivalents) can be parsed in polynomial time.^[4]

See also

References

1. ^¹{{cite thesis| type=Ph.D.| author=Weir, David Jeremy| title=Characterizing mildly context-sensitive grammar formalisms| date=Sep 1988| volume=AAI8908403| publisher=University of Pennsylvania Ann Arbor| series=Paper| url=http://www.sussex.ac.uk/Users/davidw/resources/papers/dissertation.pdf}}
2. ^{{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA33|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|page=33}}
3. ^{{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA35|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|page=35-36}}
4. ^{{cite book|author1=Johan F.A.K. van Benthem|author2=Alice ter Meulen|title=Handbook of Logic and Language|url=https://books.google.com/books?id=K7yJLmZCbFUC&pg=PA404|year=2010|publisher=Elsevier|isbn=978-0-444-53727-0|page=404|edition=2nd}}