I am shocked that Linguists have not given a reasonably small canonical computationally precise representation of any natural language yet, so I wrote a recent EL&U post to explain how one does this for English. I know that this grammar (or a small modification if I forgot something) covers all New York Times English, and all artificial highly embedded sentences, leaving out only:
- Idioms and weird constructions: "How do you do?", "hello, dear.", "Okeh, oops!", etc
- Tense-matching: this is a local finite property, and it doesn't touch the embedding structure. It is a distracting complication. I ignored it.
- Subject-verb matching: again not difficult, but distracting.
- Pronoun-reference: "With a broom, John walked on the floor, beating it.", what does "it" refer to? This is a very interesting linguistic question which I ignore.
- General "and" and "or": The and rules are cut-and-paste for different kinds of objects, debugging (ADVERB "and" ADVERB), (ADJECTIVE and ADJECTIVE), (PREPISH and PREPISH), etc, is tedious, so I skipped this.
- Verb ellipsis: I am not sure when this appears in the NYT, I have not seen an example yet. Verb ellipses can be implemented on the parser level, but at the rule level it's very annoying.
The central possibly new idea that I used is the notion of a commutative context-free grammar. A commutative context-free grammar allows a string of nonterminals to move to different positions in the sentence before expanding. I will illustrate with a sentence with two movable ADVERB phrases, a subject and a verb. At some stage in the generation, it looks like this:
ADVERB+ ADVERB+ ADVERB+ (SUBJECT) (VERB OBJECT)
In the next stages, I can move ADVERB+ to the right, so long as I don't go inside regions enclosed by parentheses. So I might get
ADVERB+ (the ADJ man ) ADVERB+ (takes the box) ADVERB+
The ADVERB is a production that includes anything that attaches to the verb, including "if" clauses, initial "yes"/"no", and prepositional phrases that modify the action, as opposed to modifying the noun. At a later stage of production, the ADVERBs resolve to verb arguments, adverb words, or gerund phrases. So in a few steps, you get
With a broom (the tall man) to the big monster (takes the box) with a limp.
Then you drop parentheses and introduce commas as conventional, to get:
With a broom, the tall man, to the big monster takes the box, with a limp.
The point of this structure is to capture the commutativity of ADVERB position in a phrase. These really can appear anywhere, and often do in poetic work, although there are style conventions in English which tends to place them at canonical positions.
This idea produces a very compact BNF for the phrase structure of English, and explains why other methods don't. The commutativity produces a large number of different nodes if you ignore it. I will point out that the parse description that this generates for the sentence is the same in all permutation of the ADVERBs. It's still a parse tree abstractly, but the tree is not contiguously represented in the sentence. Some arguments far away are bound to distant objects.
There is always a position for the ADVERBs (after the verb) where if you force the writer to place them all there, the grammar becomes context free. If you restrict the ADVERBs to the very beginning too, you can also make it context free while still producing the ADVERBs from the verb, using the following trick:
define a single nonterminal symbol: ADVERBLIST_SUBJECT_VERB_ADVERBLIST, and have context free rules that spit out ADVERBs on both sides, then when you are done spitting out ADVERBs, break it into SUBJECT ADVERBLIST_VERB_ADVERBLIST, then spit out ADVERBs on both sides, then resolve ADVERBLIST_VERB_ADVERBLIST into a VERB. This allows you to artificially remove commutativity, at the cost of introducing more parse levels into the grammar. If you do it wrong, you can easily introduce new parsing ambiguity that isn't there in the original sentence.
Aside from being counterintuitive, a context-free reduction doesn't match the arguments to the verb the correct way, which is independent of their position, this trick also doesn't work in general. If you have two separate commutative lists, a list of ADJECTIVES and ADVERBs, these can commute past each other, so that if you force the grammar to be context free, you requiring an ever-growing number of nonterminals to represent the different permutations. You can probably parse all the New York Times with only a few permutations, since good style places the ADJECTIVE close to the noun it modifies, but this commutativity leads a combinatorial explosion in the representation of English that suggests that the reason is that the commutative grammar is not context free.
While one can define commutative grammars in extreme generality, I will restrict myself to the ones useful in English. The primitive commutation rule is a production of the form:
A+ B: B A+
And likewise for all + marked variables with all unplussed variables. This allows the plus variables to move rightward, and I place them at the leftmost position they can occur.
This production is not context free, it takes two objects to two other objects in the other order. But it isn't going hog-wild either--- the number and type of nonterminal symbols is preserved during this transformation--- it doesn't wreck the tree structure completely, it only permutes the order of the nonterminals, and the moment you expand "B" into something in parentheses, say:
B: (P Q)
Then A no longer is allowed to commute with P and Q. So the commutativity is at each nesting level individually.
I define a language to be commutative context-free if all comutative objects can be generated, commuted, and resolved into unplussed-variables before any other rules are applied. Further, I will only allow them to move in one direction, by convention to the right, since this is no loss of generality in the cases I am considering. Finally, I will require that any further expansion of nonterminals will always be enclosed in parentheses which provide a firm boundary to any commuting variables introduced at a deeper nesting level, so that objects at a lower level will never commute out of their level.
- Is the commutative CFG in the mathematical linguistics literature?
- Does anyone see a proof that the commutative CFG is strictly stronger than CFG (I am pretty sure this is true)?