NLTK Regular Expressions and CFGs

context-free-grammar, nlp, nltk, python, regex

Solution

From the documentation of RegexpParser:

The patterns of a clause are executed in order. An earlier pattern may introduce a chunk boundary that prevents a later pattern from executing. Sometimes an individual pattern will match on multiple, overlapping extents of the input. As with regular expression substitution more generally, the chunker will identify the first match possible, then continue looking for matches after this one has ended.

The clauses of a grammar are also executed in order. A cascaded chunk parser is one having more than one clause. The maximum depth of a parse tree created by this chunk parser is the same as the number of clauses in the grammar.

That is, each clause/pattern is executed once. Thus you'll run into trouble as soon as you need the output of a later clause to be matched by an earlier one.

A practical example is the way something that could be a complete sentence on its own can be used as a clause in a larger sentence:

The cat purred.

He heard that the cat purred.

She saw that he heard that the cat purred.

As we can read from the documentation above, when you construct a RegexpParser you're setting an arbitrary limit for the "depth" of this sort of sentence. There is no "recursion limit" for context-free grammars.

The documentation mentions that you can use looping to mitigate this somewhat -- if you run through a suitable grammar two or three or four times, you can get a deeper parse. You can add external logic to loop your grammar many times, or until nothing more can be parsed.

However, as the documentation also notes, the basic approach of this parser is still "greedy". It proceeds like this for a fixed or variable number of steps:

- Do as much chunking as you can in one step.

- Use the output of the last step as the input of the next step, and repeat.

This is naïve because if an early step makes a mistake, this will ruin the whole parse.

Think of a "garden path sentence":

The horse raced past the barn fell.

And a similar string but an entirely different sentence:

The horse raced past the barn.

It will likely be hard to construct a RegexpParser that will parse both of these sentences, because the approach relies on the initial chunking being correct. Correct initial chunking for one will probably be incorrect initial chunking for the other, yet you can't know "which sentence you're in" until you're at a late level in the parsing logic.

For instance, if "the barn fell" is chunked together early on, the parse will fail.

You can add external logic to backtrack when you end up with a "poor" parse, to see if you can find a better one. However, I think you'll find that at that point, more of the important parts of the parsing algorithm are in your external logic, instead of in RegexpParser.

Problem

Original source