Write a function that takes a grammar (such as the one defined in 8.3) and retur

Question

Write a function that takes a grammar (such as the one defined in 8.3) and returns a random sentence generated by the grammar. (Use grammar.start() to find the start symbol of the grammar; grammar.productions(lhs) to get the list of productions from the grammar that have the specified left-hand side; and production.rhs() to get the right-hand side of a production.)

8.3

grammar1 = nltk.parse_cfg("""
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"
""")

Explanation / Answer

#!/usr/bin/python
# Analyzing sentence structure

from __future__ import division
import nltk
import re
def simple_cfg():
# grammar = nltk.parse_cfg("""
# 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"
# """)
  
# grammar = nltk.data.load("file:mygrammar.cfg")

# each production is stored along with its left corner element on RHS
# eg, S -> NP VP; VP -> V NP | ... => (S,NP), (VP,V), ...

# nltk.app.chartparser()
def parsing_types():
grammar = nltk.parse_cfg("""
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"
""")
sent = "Mary saw a dog".split()
rd_parser = nltk.RecursiveDescentParser(grammar)
print "==== recursive descent ===="
for t in rd_parser.nbest_parse(sent):
print t
sr_parser = nltk.ShiftReduceParser(grammar)
print "==== shift reduce ===="
for t in sr_parser.nbest_parse(sent):
print t

def _chart_init_wfst(tokens, grammar):
numtokens = len(tokens)
wfst = [[None for i in range(numtokens+1)] for j in range(numtokens+1)]
for i in range(numtokens):
productions = grammar.productions(rhs = tokens[i])
wfst[i][i+1] = productions[0].lhs()
return wfst

def _chart_complete_wfst(wfst, tokens, grammar, trace=False):
index = dict((p.rhs(), p.lhs()) for p in grammar.productions())
numtokens = len(tokens)
for span in range(2, numtokens+1):
for start in range(numtokens+1-+span):
end = start + span
for mid in range(start+1, end):
nt1, nt2 = wfst[start][mid], wfst[mid][end]
if nt1 and nt2 and (nt1,nt2) in index:
wfst[start][end] = index[(nt1, nt2)]
if trace:
print "[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]" %
(start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end)
return wfst

def _chart_display(wfst, tokens):
print " WFST " + " ".join([("%-4d" %i) for i in range(1, len(wfst))])
for i in range(len(wfst)-1):
print "%-4d" % i,
for j in range(1, len(wfst)):
print "%-4s" % (wfst[i][j] or "."),
print
def main():
# sentence_parse_example()
# simple_cfg()
# parsing_types()
# chart_parsing()
# dependency_grammar()
# grammar_development_with_treebank()
# word_valency()
# give_gave_usage()
pcfg_parser()
print "end"
  
if __name__ == "__main__":
main()

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.