CFG Python

[Peter Otten]

Ranya wrote:

> Let's say I vreated my own CFG in python, How can I check now if a
> sentence match this grammar (return true) or it doesn't match it (return
> false and the wrong element in the grammar), How can I do this ?

Remember, context free grammars may be fine, but context free questions 
aren't ;)

Is this question nltk-related? If so, here's one way (using a grammar found 
at http://www.nltk.org/book/ch08.html):

>>> import nltk
>>> grammar = nltk.CFG.fromstring("""
...   S -> NP VP
...   VP -> V NP | V NP PP
...   PP -> P NP
...   V -> "saw" | "ate" | "walked"
...   NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
...   Det -> "a" | "an" | "the" | "my"
...   N -> "man" | "dog" | "cat" | "telescope" | "park"
...   P -> "in" | "on" | "by" | "with"
...   """)
>>> parser = nltk.RecursiveDescentParser(grammar)
>>> def check(sentence, parser=parser):
...     return parser.parse_one(sentence) is not None
... 
>>> check("Mary saw the telescope".split())
True
>>> check("Mary saw the saw".split())
False
>>> check("Mary saw the chicken".split())
Traceback (most recent call last):
[...]
ValueError: Grammar does not cover some of the input words: "'chicken'".