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:


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.

Formal Description

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.


  1. Is the commutative CFG in the mathematical linguistics literature?
  2. Does anyone see a proof that the commutative CFG is strictly stronger than CFG (I am pretty sure this is true)?
  • I don't think mathematical linguistics is banned here. It's a slippery slope from there to banning discussion on computational linguistics :)
    – jogloran
    Commented Mar 13, 2012 at 10:33
  • 9
    Mathematical and computational linguistics are very welcome here. In fact, we are trying to draw more and more attention from people interested in the fields of Natural Language Processing and Computational Linguistics. I didn't downvote this question, but my guess is that statements like "I am shocked that Linguists have not been able to do X" are perceived by professional linguists as rude and arrogant. So, please keep a more respectful tone and you'll attract less downvotes. Commented Mar 13, 2012 at 12:38
  • 8
    +1 to Ron Maimon for an interesting question. That said, Ron, you seem to spend a lot of time in your questions trying to promote your own theories about linguistics, and this isn't really the place for that. If you'd just defined your notion of a commutative CFG and asked for more information, this would have been much shorter and more readable, and also -- I'd predict -- much less controversial. The lengthy "sales pitch" for commutative CFGs is really unnecessary. Commented Mar 13, 2012 at 15:05
  • 1
    @Dan Velleman: Thanks. I notice, however, that even with the lengthy explanation, some people misunderstand the idea. This is not a formal journal, so you need to explain in detail, with examples (something I would do in a formal journal anyway, perhaps leading to rejection). The idea here is likely new, so it is not possible to explain how it is different from linear indexed grammars, for example, except with a detailed exegesis. This is definitely a place for explaining the stuff that linguists routinely miss, otherwise this important field will stay sick forever.
    – Ron Maimon
    Commented Mar 13, 2012 at 18:03
  • Question 2. may be suitable for Computer Science.
    – Raphael
    Commented Jan 26, 2014 at 14:33

2 Answers 2


Modern research into grammar formalisms have developed analyses for many of the constructions you deem to be impossible or difficult to account for.

Out of your list, 'tense matching' and 'subject-verb matching', 'pronoun-reference' (usually called anaphora resolution), 'general "and" and "or"' (coordination) have definitely been addressed in many formalisms including generative grammar, Head-driven Phrase Structure Grammar (HPSG), Combinatory Categorial Grammar (CCG), and many others. (I am not sure what you mean by verb ellipsis, but if you mean:

He baked and she ate a delicious chocolate cake.

this, too, is well-studied and well-addressed by computationally efficient methods in the literature.)

As for the extension to CFGs which you propose,

A+ B -> B A+

can (I think) be expressed in a linear indexed grammar (LIG), so you're right that the generative power required is strictly greater than context-free.

However, I'm not even sure this is a valid generalisation — not all modifiers can occur on either side of the verb phrase (at least not without changing the denotation):

I honestly believe he is a crook.

?I believe he is a crook honestly.

Frankly I don't give a damn.

*I don't give a damn frankly.

  • By verb ellipsis, I meant cases like the Jameson whiskey commercial construction "Jameson was generous; the hawk greedy" discussed here: english.stackexchange.com/questions/60643/… . "I believe he is a crook, honestly" is the correct permutation--- the commas are essential in certain positions. Likewise "I don't give a damn, frankly" (and "Frankly, I don't give a damn") are the correct permutations. They are both semantically identical. Your "and" constructions I have no trouble with.
    – Ron Maimon
    Commented Mar 13, 2012 at 17:20
  • I will not accept this answer, because the list I gave is not a list of things I find difficult to account for, but mostly a list of things that are easy to account for, and I was too lazy to do. The only genuinely difficult thing (because it isn't context free even after permutation of ADVERBs and ADJECTIVEs) is verb ellipsis, like "He walked to the store; she, to the bank", which I am pretty sure is not covered by the common parsers.
    – Ron Maimon
    Commented Mar 13, 2012 at 17:45
  • Also, the linear indexed grammar is a different idea, which is not necessary for English. It is used to match the Swiss-German nonsense, where you have a list of things matched to another list of the same length. This is never necessary in English. The linear indexed grammars have the same problems with ADVERB commutativity as the CFGs. It is not possible to include general commutativity in any obvious way using linear indexed grammars (I tried for a bit).
    – Ron Maimon
    Commented Mar 13, 2012 at 17:50
  • 1
    @prash: That's incorrect: what Julia's paper covers is argument cluster coordination, like "He gave the puppy a bone and the cat some milk". Ellipsis, like RonMaimon is talking about, and like your example covers, is difficult to analyse under CCG. See Steedman, M. "The Syntactic Process" for an attempt using a tentative 'decomposition' combinator.
    – jogloran
    Commented Mar 14, 2012 at 0:17
  • 4
    @RonMaimon: most of the commonly used parsers are probabilistic parsers. These do not work on hand-written rules, but try to induce rules by analyzing annotated data. Hand-written rules (without weightages for the rules) will always have this problem of treating every possible parse as equally valid, and generate a huge number of parses for the most trivial sentences. Such parsers are usually less useful than parsers that generate a far more limited set of parses that are more likely to be correct. They do not have an ever-growing grammar; annotated data is expensive in one way or another.
    – prash
    Commented Mar 14, 2012 at 12:26

It was in the literature! Very recently, though. According to the citations in the paper linked below, the idea first appeared in 2009 here:

  • W. Czerwinski, S. B. Fröschle & S. Lasota (2009): "Partially-Commutative Context-Free Processes." In: CONCUR, pp. 259–273, doi:10.1007/978-3-642-04081-8_18

And the description of the commutation rule for symbols, some basic theorems, were given here:

  • W. Czerwinski, S. B. Fröschle & S. Lasota (2011): Partially-commutative context-free processes: expressibility and tractability. Inf. Comput. 209(5), pp. 782–798, doi:10.1016/j.ic.2010.12.003

Although I found the following free reference first.

This free text only appeared about 6 months after this question, so my ignorance was justified.

The paper describes a formalization of the commutative context free grammer (what they name, more precisely, a "partially commutative context free grammer", but this is what is described in the body of my question. The formalization is not difficult, it is exactly by introducing two-element swap operations). The paper also reviews existing literature, and explains in detail how this differs from other ideas which are naively similar.

The straightforward definition is on page 37, it introduces the "swap operation" for independent symbols, and allows productions which swap, in addition to a standard representation of CFGs. Instead of "plussing" variables and commuting only to the right, it defines an "independent set" of variables which can be moved back and forth to any permutation. This can be more general than what I defined in the question, but it subsumes the right-moving grammars. The paper states an automaton model for the class, using multiple stacks, on page 38.

The main theorems prove that the decision procedure for general pcCFGs (partially commutative context free grammars) is NP complete, and introduces a notion of "shuffling" or "interleaving" of grammars, so that you have two different interleaved grammars going on at the same time (this was one of my own original motivation for thinking about this).

The main difference between what I suggested and the paper is that the paper has a more general class, as it is interested in full automaton theory for such languages, not just in natural language processing. The natural language processing does not require commutation beyond certain natural stopping points--- the commutation steps are only to reorder the ADVERB and ADJECTIVE phrases amongst each other, and with the NOUNPHRASE and VERBPHRASE symbol within the same verb-scope level, they never permute anything into deeper levels of the tree. With this restriction, I am sure that the decision procedure is not NP complete, since the permutation steps can be made to a canonical order level by level. But since this is of current interest, and there is something to reference, one should publish a paper, rather than just say it here.

The implication of this for natural language processing is just that you define the parse tree with commutation rules at each level, so that you can permute the adverb and adjective nodes arbitrary on any one level the tree, so long as they don't go inside deeper parts of the tree. A "level" of the tree is one where you haven't introduced a new verb, it is the collection of all things which attach to one verb.

With this additional commutativity structure, you can permute the adverbs and adjectives in any level to a standard context free form, this should not be NP complete or anything, and then parse the sentence in the usual CFG way. I am pretty sure that there are no remaining issues for a formal description of natural language grammar, as all the verified examples of the failure of CFG come from cases where a permutation on one level fixes the structure of the sentence.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.