Programmer_nltk Programmer_nltk - 3 months ago 25
Python Question

NLTK CFG recursion depth error

import nltk
from nltk.parse.generate import generate,demo_grammar
from nltk import CFG
grammar = CFG.fromstring("""
ROOT -> S
S -> NP VP
NP -> NP PP
NP -> DT NN
DT -> 'The'
NN -> 'work'
PP -> IN NP
IN -> 'of'
NP -> DT NN
DT -> 'the'
NN -> 'painter'
VP -> VBZ ADJP
VBZ -> 'is'
ADJP -> JJ
JJ -> 'good'
""")
print(grammar)
for sentence in generate(grammar, n=100):
print(' '.join(sentence))


Gives an error

RuntimeError: maximum recursion depth exceeded while calling a Python object


Tried changing covert function in functools.py, still the same issue.

Answer

The function generate, as its docstring states, "Generates an iterator of all sentences from a CFG." Clearly it does so by choosing alternative expansions in the order they are listed in the grammar. So, the first time is sees an NP, it expands it with the rule NP -> NP PP. It now has another NP to expand, which it also expands with the same rule... and so on ad infinitum, or rather until python's limits are exceeded.

To fix the problem with the grammar you provide, simply reorder your first two NP rules so that the recursive rule is not the first one encountered:

grammar = CFG.fromstring("""   
ROOT -> S
S -> NP VP
NP -> DT NN
NP -> NP PP
DT -> 'The'
...
""")

Do it like this and the generator will produce lots of complete sentences for you to examine. Note that the corrected grammar is still recursive, hence infinite; if you generate a large enough number of sentences, you will eventually reach the same recursion depth limit.