Discontinuous-constituent phrase structure grammar

Discontinuous-constituent Phrase Structure Grammar (DCPSG) (distinct from Discontinuous Phrase Structure Grammar/DPSG) is a formalism for describing discontinuous phrase structures in natural language, such as verb phrases in VSO languages. The formalism was introduced in the slightly more constrained form of Discontinuous-constituent Phrase Structure Grammar with Subscripts and Deletes (DCPSGsd) in Harman (1963). DCPSGs describe a superset of the context-free languages, by means of rewrite rules that permit a limited amount of wrapping, similar to that found in Head grammar.

Description

Rewrite rules of a DCPSG are identical to those of a CFG, with the addition of a meta-symbol, denoted here as an underscore. DCPSG rules therefore have the general form [math]\displaystyle{ X \to \alpha }[/math] where [math]\displaystyle{ \alpha }[/math] is a string of terminal symbols and/or non-terminal symbols and at most one underscore.

The rewrite semantics of DCPSG are identical as those of a CFG when the rule being used does not contain an underscore: given a rule [math]\displaystyle{ X \to \alpha }[/math], an occurrence of [math]\displaystyle{ X }[/math] may be rewritten as [math]\displaystyle{ \alpha }[/math].

For rules with an underscore, the rewrite semantics are slightly different: given a rule [math]\displaystyle{ X \to \alpha \_ \beta }[/math], an occurrence of [math]\displaystyle{ X }[/math] can be rewritten as [math]\displaystyle{ \alpha }[/math], with [math]\displaystyle{ \beta }[/math] being inserted immediately after the next non-terminal that is introduced at the same time. Using strict left-most productions, [math]\displaystyle{ \beta }[/math] is simply inserted immediately after the non-terminal that follows [math]\displaystyle{ X }[/math] prior to the rewrite.

Example

We can characterize the gross sentence structure of a VSO language such as Irish with the following rules (substituting English words for Irish words, and using subscripts solely for demonstration of discontinuity):

[math]\ce{ S -> VP\ NP_{subj} }[/math]

[math]\ce{ VP -> ITV ~|~ TV \ \_ \ NP_{obj} }[/math]

[math]\ce{ NP -> \it{John} ~|~ \it{Susan} ~|~ ... }[/math]

[math]\ce{ ITV -> \it{ran} ~|~ \it{danced} ~|~ ... }[/math]

[math]\ce{ TV -> \it{saw} ~|~ \it{met} ~|~ ... }[/math]

A derivation for the sentence saw John Susan, where John is the subject, and Susan is the direct object forming a VP with saw is:

[math]\ce{ S -> VP\ NP_{subj} -> TV\ NP_{subj} NP_{obj} -> \mathit{saw}\ NP_{subj}\ NP_{obj} -> \mathit{saw}\ \mathit{John}\ NP_{obj} -> \mathit{saw}\ \mathit{John}\ \mathit{Mary} }[/math]