PCFG Parsing using NLTK

(C) 2018-2019 by Damir Cavar

Download: This and various other Jupyter notebooks are available from my GitHub repo.

This notebook is based on my own NLTK notebooks and Michael Elhadad's notebook Constituent-based Syntactic Parsing with NLTK. See for related material:

  1. Python Parsing with NLTK
  2. Python Parsing with NLTK and Foma

This is a tutorial related to the discussion of grammar engineering and parsing in the class Alternative Syntactic Theories and Advanced Natural Language Processing taught at Indiana University in Spring 2017 and Fall 2018 and 2019.

The examples presuppose an installed Python 3.x NLTK module with all the dependent modules and packages, as well as the data set for NLTK.

Using the Penn-Treebank

You can use the NLTK corpus module to read and use the different corpora in the NLTK data set.

In [1]:
import nltk.corpus

We can load the portion of the Penn Treebank:

In [2]:
ptb = nltk.corpus.treebank

The corpus consists of a collection of files. Each file has an ID (file name). You can print the IDs using the fileids method:

In [3]:
print(ptb.fileids())
['wsj_0001.mrg', 'wsj_0002.mrg', 'wsj_0003.mrg', 'wsj_0004.mrg', 'wsj_0005.mrg', 'wsj_0006.mrg', 'wsj_0007.mrg', 'wsj_0008.mrg', 'wsj_0009.mrg', 'wsj_0010.mrg', 'wsj_0011.mrg', 'wsj_0012.mrg', 'wsj_0013.mrg', 'wsj_0014.mrg', 'wsj_0015.mrg', 'wsj_0016.mrg', 'wsj_0017.mrg', 'wsj_0018.mrg', 'wsj_0019.mrg', 'wsj_0020.mrg', 'wsj_0021.mrg', 'wsj_0022.mrg', 'wsj_0023.mrg', 'wsj_0024.mrg', 'wsj_0025.mrg', 'wsj_0026.mrg', 'wsj_0027.mrg', 'wsj_0028.mrg', 'wsj_0029.mrg', 'wsj_0030.mrg', 'wsj_0031.mrg', 'wsj_0032.mrg', 'wsj_0033.mrg', 'wsj_0034.mrg', 'wsj_0035.mrg', 'wsj_0036.mrg', 'wsj_0037.mrg', 'wsj_0038.mrg', 'wsj_0039.mrg', 'wsj_0040.mrg', 'wsj_0041.mrg', 'wsj_0042.mrg', 'wsj_0043.mrg', 'wsj_0044.mrg', 'wsj_0045.mrg', 'wsj_0046.mrg', 'wsj_0047.mrg', 'wsj_0048.mrg', 'wsj_0049.mrg', 'wsj_0050.mrg', 'wsj_0051.mrg', 'wsj_0052.mrg', 'wsj_0053.mrg', 'wsj_0054.mrg', 'wsj_0055.mrg', 'wsj_0056.mrg', 'wsj_0057.mrg', 'wsj_0058.mrg', 'wsj_0059.mrg', 'wsj_0060.mrg', 'wsj_0061.mrg', 'wsj_0062.mrg', 'wsj_0063.mrg', 'wsj_0064.mrg', 'wsj_0065.mrg', 'wsj_0066.mrg', 'wsj_0067.mrg', 'wsj_0068.mrg', 'wsj_0069.mrg', 'wsj_0070.mrg', 'wsj_0071.mrg', 'wsj_0072.mrg', 'wsj_0073.mrg', 'wsj_0074.mrg', 'wsj_0075.mrg', 'wsj_0076.mrg', 'wsj_0077.mrg', 'wsj_0078.mrg', 'wsj_0079.mrg', 'wsj_0080.mrg', 'wsj_0081.mrg', 'wsj_0082.mrg', 'wsj_0083.mrg', 'wsj_0084.mrg', 'wsj_0085.mrg', 'wsj_0086.mrg', 'wsj_0087.mrg', 'wsj_0088.mrg', 'wsj_0089.mrg', 'wsj_0090.mrg', 'wsj_0091.mrg', 'wsj_0092.mrg', 'wsj_0093.mrg', 'wsj_0094.mrg', 'wsj_0095.mrg', 'wsj_0096.mrg', 'wsj_0097.mrg', 'wsj_0098.mrg', 'wsj_0099.mrg', 'wsj_0100.mrg', 'wsj_0101.mrg', 'wsj_0102.mrg', 'wsj_0103.mrg', 'wsj_0104.mrg', 'wsj_0105.mrg', 'wsj_0106.mrg', 'wsj_0107.mrg', 'wsj_0108.mrg', 'wsj_0109.mrg', 'wsj_0110.mrg', 'wsj_0111.mrg', 'wsj_0112.mrg', 'wsj_0113.mrg', 'wsj_0114.mrg', 'wsj_0115.mrg', 'wsj_0116.mrg', 'wsj_0117.mrg', 'wsj_0118.mrg', 'wsj_0119.mrg', 'wsj_0120.mrg', 'wsj_0121.mrg', 'wsj_0122.mrg', 'wsj_0123.mrg', 'wsj_0124.mrg', 'wsj_0125.mrg', 'wsj_0126.mrg', 'wsj_0127.mrg', 'wsj_0128.mrg', 'wsj_0129.mrg', 'wsj_0130.mrg', 'wsj_0131.mrg', 'wsj_0132.mrg', 'wsj_0133.mrg', 'wsj_0134.mrg', 'wsj_0135.mrg', 'wsj_0136.mrg', 'wsj_0137.mrg', 'wsj_0138.mrg', 'wsj_0139.mrg', 'wsj_0140.mrg', 'wsj_0141.mrg', 'wsj_0142.mrg', 'wsj_0143.mrg', 'wsj_0144.mrg', 'wsj_0145.mrg', 'wsj_0146.mrg', 'wsj_0147.mrg', 'wsj_0148.mrg', 'wsj_0149.mrg', 'wsj_0150.mrg', 'wsj_0151.mrg', 'wsj_0152.mrg', 'wsj_0153.mrg', 'wsj_0154.mrg', 'wsj_0155.mrg', 'wsj_0156.mrg', 'wsj_0157.mrg', 'wsj_0158.mrg', 'wsj_0159.mrg', 'wsj_0160.mrg', 'wsj_0161.mrg', 'wsj_0162.mrg', 'wsj_0163.mrg', 'wsj_0164.mrg', 'wsj_0165.mrg', 'wsj_0166.mrg', 'wsj_0167.mrg', 'wsj_0168.mrg', 'wsj_0169.mrg', 'wsj_0170.mrg', 'wsj_0171.mrg', 'wsj_0172.mrg', 'wsj_0173.mrg', 'wsj_0174.mrg', 'wsj_0175.mrg', 'wsj_0176.mrg', 'wsj_0177.mrg', 'wsj_0178.mrg', 'wsj_0179.mrg', 'wsj_0180.mrg', 'wsj_0181.mrg', 'wsj_0182.mrg', 'wsj_0183.mrg', 'wsj_0184.mrg', 'wsj_0185.mrg', 'wsj_0186.mrg', 'wsj_0187.mrg', 'wsj_0188.mrg', 'wsj_0189.mrg', 'wsj_0190.mrg', 'wsj_0191.mrg', 'wsj_0192.mrg', 'wsj_0193.mrg', 'wsj_0194.mrg', 'wsj_0195.mrg', 'wsj_0196.mrg', 'wsj_0197.mrg', 'wsj_0198.mrg', 'wsj_0199.mrg']

We can print out the content of a particular file:

In [4]:
print(ptb.raw('wsj_0001.mrg'))
( (S 
    (NP-SBJ 
      (NP (NNP Pierre) (NNP Vinken) )
      (, ,) 
      (ADJP 
        (NP (CD 61) (NNS years) )
        (JJ old) )
      (, ,) )
    (VP (MD will) 
      (VP (VB join) 
        (NP (DT the) (NN board) )
        (PP-CLR (IN as) 
          (NP (DT a) (JJ nonexecutive) (NN director) ))
        (NP-TMP (NNP Nov.) (CD 29) )))
    (. .) ))
( (S 
    (NP-SBJ (NNP Mr.) (NNP Vinken) )
    (VP (VBZ is) 
      (NP-PRD 
        (NP (NN chairman) )
        (PP (IN of) 
          (NP 
            (NP (NNP Elsevier) (NNP N.V.) )
            (, ,) 
            (NP (DT the) (NNP Dutch) (VBG publishing) (NN group) )))))
    (. .) ))

As you can see, the file wsj_0001.mrg contains two sentence trees. You can access each sentence tree individually. Here we print out the first sentence:

In [5]:
print(ptb.parsed_sents('wsj_0001.mrg')[0])
(S
  (NP-SBJ
    (NP (NNP Pierre) (NNP Vinken))
    (, ,)
    (ADJP (NP (CD 61) (NNS years)) (JJ old))
    (, ,))
  (VP
    (MD will)
    (VP
      (VB join)
      (NP (DT the) (NN board))
      (PP-CLR (IN as) (NP (DT a) (JJ nonexecutive) (NN director)))
      (NP-TMP (NNP Nov.) (CD 29))))
  (. .))

And in the following code we print the second tree:

In [6]:
print(ptb.parsed_sents('wsj_0001.mrg')[1])
(S
  (NP-SBJ (NNP Mr.) (NNP Vinken))
  (VP
    (VBZ is)
    (NP-PRD
      (NP (NN chairman))
      (PP
        (IN of)
        (NP
          (NP (NNP Elsevier) (NNP N.V.))
          (, ,)
          (NP (DT the) (NNP Dutch) (VBG publishing) (NN group))))))
  (. .))

To see the tree structure as a graphic, you can apply the draw() method to the particular tree. The following code will open up a window with the drawing of the first tree in the file wsj_0001.mrg.

In [7]:
ptb.parsed_sents('wsj_0001.mrg')[0].draw()

Notice that in the menu of the window you can export the drawing of the tree as a Postscript file.

NLTK allows you to define your own tree using the bracketed notation and the Tree class.

In [8]:
from nltk import Tree

We can define a string variable with a syntactic tree and create a Tree object by applying the fromstring method from the Tree class:

In [9]:
trees = "(S (NP (NN cats ) ) (VP (V chase ) (NP (NN mice ) ) ))"
myTree = Tree.fromstring(trees)

We can print the tree in bracketed notation:

In [10]:
print(myTree)
(S (NP (NN cats)) (VP (V chase) (NP (NN mice))))

The internal representation of the tree looks as follows:

In [11]:
print(myTree.__repr__())
Tree('S', [Tree('NP', [Tree('NN', ['cats'])]), Tree('VP', [Tree('V', ['chase']), Tree('NP', [Tree('NN', ['mice'])])])])

The tree can be written in LaTeX format for the qtree package:

In [12]:
print(myTree.pformat_latex_qtree())
\Tree [.S [.NP [.NN cats ] ] [.VP [.V chase ] [.NP [.NN mice ] ] ] ]

We can draw the tree by applying the draw() method to the tree object. The following code will open up a window with the drawing of the corresponding tree:

In [13]:
myTree.draw()

We can print the label of a tree or subtrees using the label method:

In [14]:
print(myTree.label())
S

A daughter of the root node of the tree can be accessed using the list index notation:

In [15]:
print(myTree[0])
print(myTree[1])
(NP (NN cats))
(VP (V chase) (NP (NN mice)))

We can print out the label of these subtrees by applying the label method to them:

In [16]:
print(myTree[0].label())
print(myTree[1].label())
NP
VP

We can traverse the tree using these bracketed index operators:

In [17]:
print(myTree[0])
print(myTree[0,0])
print(myTree[0,0,0])
(NP (NN cats))
(NN cats)
cats

Sections of the tree can be modified or replaced using the index notation. We replace the subject (NN cats) with (NN dogs) in the following code:

In [18]:
myTree[0,0] = Tree.fromstring('(NN dogs)')
print(myTree)
(S (NP (NN dogs)) (VP (V chase) (NP (NN mice))))

Various details about the tree can be accessed. We can extract the leaves of the tree using the leaves method:

In [19]:
print(myTree.leaves())
['dogs', 'chase', 'mice']

We can query the height of a tree:

In [20]:
print(myTree.height())
5

For specific purposes and some specific algorithms one might want to convert the tree to remove all unary relations between symbols. To collapse for example (NP (NP (NN dogs ))) to (NP+NP (NN cats )):

In [21]:
trees2 = "(S (NP (NP (NN cats ) ) ) (VP (V chase ) (NP (NN mice ) ) ))"
myTree2 = Tree.fromstring(trees2)
myTree2.collapse_unary()
print(myTree2)
(S (NP+NP (NN cats)) (VP (V chase) (NP (NN mice))))

We can convert a tree to Chomsky Normal Form as well. In the following tree we have a subject NP branching into three daughter nodes. This is converted to a binary branching structure:

In [22]:
trees2 = "(S (NP (NP (DET the ) (JJ big ) (NN cats ) ) ) (VP (V chase ) (NP (NN mice ) ) ))"
myTree2 = Tree.fromstring(trees2)
myTree2.chomsky_normal_form()
print(myTree2)
(S
  (NP (NP (DET the) (NP|<JJ-NN> (JJ big) (NN cats))))
  (VP (V chase) (NP (NN mice))))

We can generate all production rules for a tree:

In [23]:
myTree.productions()
Out[23]:
[S -> NP VP,
 NP -> NN,
 NN -> 'dogs',
 VP -> V NP,
 V -> 'chase',
 NP -> NN,
 NN -> 'mice']

Trees can contain nodes that are complex objects. Nodes do not have to be strings. In the following code we replace the root node of our tree with a tuple of string and integer:

In [24]:
myTree.set_label( ('S', 3) )
print(myTree)
(('S', 3) (NP (NN dogs)) (VP (V chase) (NP (NN mice))))

Probabilistic rules or trees can be defined in the following way:

In [25]:
pt = nltk.tree.ProbabilisticTree('NP', ['DET', 'N'], prob=0.5)
print(pt)
(NP DET N) (p=0.5)

Draw the tree:

In [26]:
pt.draw()

In the previous sections (see links to the other notebooks above), we have seen how CFGs can be defined, read from a file, or used in a parser.

PCFG rules are defined in the same way. In addition a probability is assigned to each right-hand side of a rule. All probabilities for one particular left-hand side have to sum up to 1. The following code imports the PCFG class from NLTK:

In [27]:
from nltk import PCFG

We can define a grammar:

In [28]:
pcfg1 = PCFG.fromstring("""
    S -> NP VP [1.0]
    NP -> Det N [0.5] | NP PP [0.25] | N [0.25]
    PP -> P NP [1.0]
    VP -> VP PP [0.1] | V NP [0.7] | V [0.2]
    N -> 'woman' [0.3] | 'man' [0.3] | 'telescope' [0.3] | 'mixer' [0.1]
    Det -> 'the' [0.6] | 'a' [0.2] | 'my' [0.2]
    V -> 'killed' [0.35] | 'saw' [0.65]
    P -> 'with' [0.61] | 'under' [0.39]
""")

We can print out the productions:

In [29]:
print(pcfg1)
Grammar with 19 productions (start state = S)
    S -> NP VP [1.0]
    NP -> Det N [0.5]
    NP -> NP PP [0.25]
    NP -> N [0.25]
    PP -> P NP [1.0]
    VP -> VP PP [0.1]
    VP -> V NP [0.7]
    VP -> V [0.2]
    N -> 'woman' [0.3]
    N -> 'man' [0.3]
    N -> 'telescope' [0.3]
    N -> 'mixer' [0.1]
    Det -> 'the' [0.6]
    Det -> 'a' [0.2]
    Det -> 'my' [0.2]
    V -> 'killed' [0.35]
    V -> 'saw' [0.65]
    P -> 'with' [0.61]
    P -> 'under' [0.39]

We can import the portion of the Penn Treebank as treebank:

In [30]:
from nltk.corpus import treebank

We can now loop over all files, read the sentences in, extract all production rules from them, and aggregate the production rules in a list:

In [31]:
productions = []
for t in treebank.fileids()[:2]:
    for x in treebank.parsed_sents(t):
        productions += x.productions()
print(productions)
[S -> NP-SBJ VP ., NP-SBJ -> NP , ADJP ,, NP -> NNP NNP, NNP -> 'Pierre', NNP -> 'Vinken', , -> ',', ADJP -> NP JJ, NP -> CD NNS, CD -> '61', NNS -> 'years', JJ -> 'old', , -> ',', VP -> MD VP, MD -> 'will', VP -> VB NP PP-CLR NP-TMP, VB -> 'join', NP -> DT NN, DT -> 'the', NN -> 'board', PP-CLR -> IN NP, IN -> 'as', NP -> DT JJ NN, DT -> 'a', JJ -> 'nonexecutive', NN -> 'director', NP-TMP -> NNP CD, NNP -> 'Nov.', CD -> '29', . -> '.', S -> NP-SBJ VP ., NP-SBJ -> NNP NNP, NNP -> 'Mr.', NNP -> 'Vinken', VP -> VBZ NP-PRD, VBZ -> 'is', NP-PRD -> NP PP, NP -> NN, NN -> 'chairman', PP -> IN NP, IN -> 'of', NP -> NP , NP, NP -> NNP NNP, NNP -> 'Elsevier', NNP -> 'N.V.', , -> ',', NP -> DT NNP VBG NN, DT -> 'the', NNP -> 'Dutch', VBG -> 'publishing', NN -> 'group', . -> '.', S -> NP-SBJ-1 VP ., NP-SBJ-1 -> NP , UCP ,, NP -> NNP NNP, NNP -> 'Rudolph', NNP -> 'Agnew', , -> ',', UCP -> ADJP CC NP, ADJP -> NP JJ, NP -> CD NNS, CD -> '55', NNS -> 'years', JJ -> 'old', CC -> 'and', NP -> NP PP, NP -> JJ NN, JJ -> 'former', NN -> 'chairman', PP -> IN NP, IN -> 'of', NP -> NNP NNP NNP NNP, NNP -> 'Consolidated', NNP -> 'Gold', NNP -> 'Fields', NNP -> 'PLC', , -> ',', VP -> VBD VP, VBD -> 'was', VP -> VBN S, VBN -> 'named', S -> NP-SBJ NP-PRD, NP-SBJ -> -NONE-, -NONE- -> '*-1', NP-PRD -> NP PP, NP -> DT JJ NN, DT -> 'a', JJ -> 'nonexecutive', NN -> 'director', PP -> IN NP, IN -> 'of', NP -> DT JJ JJ NN, DT -> 'this', JJ -> 'British', JJ -> 'industrial', NN -> 'conglomerate', . -> '.']

To be able to induce the PCFG, we need to define a Nonterminal object with the start symbol as label:

In [32]:
from nltk import Nonterminal
S = Nonterminal('S')

We can now induce the PCFG using the Nonterminal start symbol and the list of production rules:

In [33]:
grammar = nltk.induce_pcfg(S, productions)
print(grammar)
Grammar with 71 productions (start state = S)
    S -> NP-SBJ VP . [0.5]
    NP-SBJ -> NP , ADJP , [0.333333]
    NP -> NNP NNP [0.2]
    NNP -> 'Pierre' [0.0714286]
    NNP -> 'Vinken' [0.142857]
    , -> ',' [1.0]
    ADJP -> NP JJ [1.0]
    NP -> CD NNS [0.133333]
    CD -> '61' [0.333333]
    NNS -> 'years' [1.0]
    JJ -> 'old' [0.285714]
    VP -> MD VP [0.2]
    MD -> 'will' [1.0]
    VP -> VB NP PP-CLR NP-TMP [0.2]
    VB -> 'join' [1.0]
    NP -> DT NN [0.0666667]
    DT -> 'the' [0.4]
    NN -> 'board' [0.142857]
    PP-CLR -> IN NP [1.0]
    IN -> 'as' [0.25]
    NP -> DT JJ NN [0.133333]
    DT -> 'a' [0.4]
    JJ -> 'nonexecutive' [0.285714]
    NN -> 'director' [0.285714]
    NP-TMP -> NNP CD [1.0]
    NNP -> 'Nov.' [0.0714286]
    CD -> '29' [0.333333]
    . -> '.' [1.0]
    NP-SBJ -> NNP NNP [0.333333]
    NNP -> 'Mr.' [0.0714286]
    VP -> VBZ NP-PRD [0.2]
    VBZ -> 'is' [1.0]
    NP-PRD -> NP PP [1.0]
    NP -> NN [0.0666667]
    NN -> 'chairman' [0.285714]
    PP -> IN NP [1.0]
    IN -> 'of' [0.75]
    NP -> NP , NP [0.0666667]
    NNP -> 'Elsevier' [0.0714286]
    NNP -> 'N.V.' [0.0714286]
    NP -> DT NNP VBG NN [0.0666667]
    NNP -> 'Dutch' [0.0714286]
    VBG -> 'publishing' [1.0]
    NN -> 'group' [0.142857]
    S -> NP-SBJ-1 VP . [0.25]
    NP-SBJ-1 -> NP , UCP , [1.0]
    NNP -> 'Rudolph' [0.0714286]
    NNP -> 'Agnew' [0.0714286]
    UCP -> ADJP CC NP [1.0]
    CD -> '55' [0.333333]
    CC -> 'and' [1.0]
    NP -> NP PP [0.0666667]
    NP -> JJ NN [0.0666667]
    JJ -> 'former' [0.142857]
    NP -> NNP NNP NNP NNP [0.0666667]
    NNP -> 'Consolidated' [0.0714286]
    NNP -> 'Gold' [0.0714286]
    NNP -> 'Fields' [0.0714286]
    NNP -> 'PLC' [0.0714286]
    VP -> VBD VP [0.2]
    VBD -> 'was' [1.0]
    VP -> VBN S [0.2]
    VBN -> 'named' [1.0]
    S -> NP-SBJ NP-PRD [0.25]
    NP-SBJ -> -NONE- [0.333333]
    -NONE- -> '*-1' [1.0]
    NP -> DT JJ JJ NN [0.0666667]
    DT -> 'this' [0.2]
    JJ -> 'British' [0.142857]
    JJ -> 'industrial' [0.142857]
    NN -> 'conglomerate' [0.142857]

We can normalize the trees by collapsing unary branches and converting them to Chomsky Normal Form before we extract the production rules and induce the grammar:

In [34]:
productions = []
for t in treebank.fileids()[:2]:
    for x in treebank.parsed_sents(t):
        x.collapse_unary(collapsePOS = False)
        x.chomsky_normal_form(horzMarkov = 2)
        productions += x.productions()
grammar = nltk.induce_pcfg(S, productions)
print(grammar)
Grammar with 86 productions (start state = S)
    S -> NP-SBJ S|<VP-.> [0.5]
    NP-SBJ -> NP NP-SBJ|<,-ADJP> [0.333333]
    NP -> NNP NNP [0.2]
    NNP -> 'Pierre' [0.0714286]
    NNP -> 'Vinken' [0.142857]
    NP-SBJ|<,-ADJP> -> , NP-SBJ|<ADJP-,> [1.0]
    , -> ',' [1.0]
    NP-SBJ|<ADJP-,> -> ADJP , [1.0]
    ADJP -> NP JJ [1.0]
    NP -> CD NNS [0.133333]
    CD -> '61' [0.333333]
    NNS -> 'years' [1.0]
    JJ -> 'old' [0.285714]
    S|<VP-.> -> VP . [1.0]
    VP -> MD VP [0.2]
    MD -> 'will' [1.0]
    VP -> VB VP|<NP-PP-CLR> [0.2]
    VB -> 'join' [1.0]
    VP|<NP-PP-CLR> -> NP VP|<PP-CLR-NP-TMP> [1.0]
    NP -> DT NN [0.0666667]
    DT -> 'the' [0.4]
    NN -> 'board' [0.142857]
    VP|<PP-CLR-NP-TMP> -> PP-CLR NP-TMP [1.0]
    PP-CLR -> IN NP [1.0]
    IN -> 'as' [0.25]
    NP -> DT NP|<JJ-NN> [0.133333]
    DT -> 'a' [0.4]
    NP|<JJ-NN> -> JJ NN [1.0]
    JJ -> 'nonexecutive' [0.285714]
    NN -> 'director' [0.285714]
    NP-TMP -> NNP CD [1.0]
    NNP -> 'Nov.' [0.0714286]
    CD -> '29' [0.333333]
    . -> '.' [1.0]
    NP-SBJ -> NNP NNP [0.333333]
    NNP -> 'Mr.' [0.0714286]
    VP -> VBZ NP-PRD [0.2]
    VBZ -> 'is' [1.0]
    NP-PRD -> NP PP [1.0]
    NP -> NN [0.0666667]
    NN -> 'chairman' [0.285714]
    PP -> IN NP [1.0]
    IN -> 'of' [0.75]
    NP -> NP NP|<,-NP> [0.0666667]
    NNP -> 'Elsevier' [0.0714286]
    NNP -> 'N.V.' [0.0714286]
    NP|<,-NP> -> , NP [1.0]
    NP -> DT NP|<NNP-VBG> [0.0666667]
    NP|<NNP-VBG> -> NNP NP|<VBG-NN> [1.0]
    NNP -> 'Dutch' [0.0714286]
    NP|<VBG-NN> -> VBG NN [1.0]
    VBG -> 'publishing' [1.0]
    NN -> 'group' [0.142857]
    S -> NP-SBJ-1 S|<VP-.> [0.25]
    NP-SBJ-1 -> NP NP-SBJ-1|<,-UCP> [1.0]
    NNP -> 'Rudolph' [0.0714286]
    NNP -> 'Agnew' [0.0714286]
    NP-SBJ-1|<,-UCP> -> , NP-SBJ-1|<UCP-,> [1.0]
    NP-SBJ-1|<UCP-,> -> UCP , [1.0]
    UCP -> ADJP UCP|<CC-NP> [1.0]
    CD -> '55' [0.333333]
    UCP|<CC-NP> -> CC NP [1.0]
    CC -> 'and' [1.0]
    NP -> NP PP [0.0666667]
    NP -> JJ NN [0.0666667]
    JJ -> 'former' [0.142857]
    NP -> NNP NP|<NNP-NNP> [0.0666667]
    NNP -> 'Consolidated' [0.0714286]
    NP|<NNP-NNP> -> NNP NP|<NNP-NNP> [0.5]
    NNP -> 'Gold' [0.0714286]
    NP|<NNP-NNP> -> NNP NNP [0.5]
    NNP -> 'Fields' [0.0714286]
    NNP -> 'PLC' [0.0714286]
    VP -> VBD VP [0.2]
    VBD -> 'was' [1.0]
    VP -> VBN S [0.2]
    VBN -> 'named' [1.0]
    S -> NP-SBJ NP-PRD [0.25]
    NP-SBJ -> -NONE- [0.333333]
    -NONE- -> '*-1' [1.0]
    NP -> DT NP|<JJ-JJ> [0.0666667]
    DT -> 'this' [0.2]
    NP|<JJ-JJ> -> JJ NP|<JJ-NN> [1.0]
    JJ -> 'British' [0.142857]
    JJ -> 'industrial' [0.142857]
    NN -> 'conglomerate' [0.142857]

Parsing with PCFGs

NLTK provides various parser implementations. One that implements the Viterbi CKY n-best parses over a PCFG is available in the parse.viterbi module. (See Michael Elhadad's notebook Constituent-based Syntactic Parsing with NLTK for more details.)

In [35]:
print("Parse sentence using induced grammar:")

parser = nltk.pchart.InsideChartParser(grammar)
parser.trace(3)

sent = treebank.parsed_sents('wsj_0001.mrg')[0].leaves()
print(sent)

for parse in parser.parse(sent):
  print(parse)
Parse sentence using induced grammar:
['Pierre', 'Vinken', ',', '61', 'years', 'old', ',', 'will', 'join', 'the', 'board', 'as', 'a', 'nonexecutive', 'director', 'Nov.', '29', '.']
  |[-] . . . . . . . . . . . . . . . . .| [0:1] 'Pierre' [1.0]
  |. [-] . . . . . . . . . . . . . . . .| [1:2] 'Vinken' [1.0]
  |. . [-] . . . . . . . . . . . . . . .| [2:3] ','  [1.0]
  |. . . [-] . . . . . . . . . . . . . .| [3:4] '61' [1.0]
  |. . . . [-] . . . . . . . . . . . . .| [4:5] 'years' [1.0]
  |. . . . . [-] . . . . . . . . . . . .| [5:6] 'old' [1.0]
  |. . . . . . [-] . . . . . . . . . . .| [6:7] ','  [1.0]
  |. . . . . . . [-] . . . . . . . . . .| [7:8] 'will' [1.0]
  |. . . . . . . . [-] . . . . . . . . .| [8:9] 'join' [1.0]
  |. . . . . . . . . [-] . . . . . . . .| [9:10] 'the' [1.0]
  |. . . . . . . . . . [-] . . . . . . .| [10:11] 'board' [1.0]
  |. . . . . . . . . . . [-] . . . . . .| [11:12] 'as' [1.0]
  |. . . . . . . . . . . . [-] . . . . .| [12:13] 'a' [1.0]
  |. . . . . . . . . . . . . [-] . . . .| [13:14] 'nonexecutive' [1.0]
  |. . . . . . . . . . . . . . [-] . . .| [14:15] 'director' [1.0]
  |. . . . . . . . . . . . . . . [-] . .| [15:16] 'Nov.' [1.0]
  |. . . . . . . . . . . . . . . . [-] .| [16:17] '29' [1.0]
  |. . . . . . . . . . . . . . . . . [-]| [17:18] '.' [1.0]
  |. . . . . . . . . . . . . . . . . [-]| [17:18] '.' [1.0]
  |. . . . . . . . . . . . . . . . . [-]| [17:18] .  -> '.' * [1.0]
  |. . . . . . . . . . . . . . . . . > .| [17:17] .  -> * '.' [1.0]
  |. . . . . . . . . . . . . . . . [-] .| [16:17] '29' [1.0]
  |. . . . . . . . . . . . . . . [-] . .| [15:16] 'Nov.' [1.0]
  |. . . . . . . . . . . . . . [-] . . .| [14:15] 'director' [1.0]
  |. . . . . . . . . . . . . [-] . . . .| [13:14] 'nonexecutive' [1.0]
  |. . . . . . . . . . . . [-] . . . . .| [12:13] 'a' [1.0]
  |. . . . . . . . . . . [-] . . . . . .| [11:12] 'as' [1.0]
  |. . . . . . . . . . [-] . . . . . . .| [10:11] 'board' [1.0]
  |. . . . . . . . . [-] . . . . . . . .| [9:10] 'the' [1.0]
  |. . . . . . . . [-] . . . . . . . . .| [8:9] 'join' [1.0]
  |. . . . . . . . [-] . . . . . . . . .| [8:9] VB -> 'join' * [1.0]
  |. . . . . . . . > . . . . . . . . . .| [8:8] VB -> * 'join' [1.0]
  |. . . . . . . [-] . . . . . . . . . .| [7:8] 'will' [1.0]
  |. . . . . . . [-] . . . . . . . . . .| [7:8] MD -> 'will' * [1.0]
  |. . . . . . . > . . . . . . . . . . .| [7:7] MD -> * 'will' [1.0]
  |. . . . . . [-] . . . . . . . . . . .| [6:7] ','  [1.0]
  |. . . . . . [-] . . . . . . . . . . .| [6:7] ,  -> ',' * [1.0]
  |. . . . . . [-> . . . . . . . . . . .| [6:7] NP-SBJ-1|<,-UCP> -> , * NP-SBJ-1|<UCP-,> [1.0]
  |. . . . . . [-> . . . . . . . . . . .| [6:7] NP|<,-NP> -> , * NP [1.0]
  |. . . . . . [-> . . . . . . . . . . .| [6:7] NP-SBJ|<,-ADJP> -> , * NP-SBJ|<ADJP-,> [1.0]
  |. . . . . . > . . . . . . . . . . . .| [6:6] NP-SBJ-1|<,-UCP> -> * , NP-SBJ-1|<UCP-,> [1.0]
  |. . . . . . > . . . . . . . . . . . .| [6:6] NP|<,-NP> -> * , NP [1.0]
  |. . . . . . > . . . . . . . . . . . .| [6:6] NP-SBJ|<,-ADJP> -> * , NP-SBJ|<ADJP-,> [1.0]
  |. . . . . . > . . . . . . . . . . . .| [6:6] ,  -> * ',' [1.0]
  |. . . . . [-] . . . . . . . . . . . .| [5:6] 'old' [1.0]
  |. . . . [-] . . . . . . . . . . . . .| [4:5] 'years' [1.0]
  |. . . . [-] . . . . . . . . . . . . .| [4:5] NNS -> 'years' * [1.0]
  |. . . . > . . . . . . . . . . . . . .| [4:4] NNS -> * 'years' [1.0]
  |. . . [-] . . . . . . . . . . . . . .| [3:4] '61' [1.0]
  |. . [-] . . . . . . . . . . . . . . .| [2:3] ','  [1.0]
  |. . [-] . . . . . . . . . . . . . . .| [2:3] ,  -> ',' * [1.0]
  |. . [-> . . . . . . . . . . . . . . .| [2:3] NP-SBJ-1|<,-UCP> -> , * NP-SBJ-1|<UCP-,> [1.0]
  |. . [-> . . . . . . . . . . . . . . .| [2:3] NP|<,-NP> -> , * NP [1.0]
  |. . [-> . . . . . . . . . . . . . . .| [2:3] NP-SBJ|<,-ADJP> -> , * NP-SBJ|<ADJP-,> [1.0]
  |. . > . . . . . . . . . . . . . . . .| [2:2] NP-SBJ-1|<,-UCP> -> * , NP-SBJ-1|<UCP-,> [1.0]
  |. . > . . . . . . . . . . . . . . . .| [2:2] NP|<,-NP> -> * , NP [1.0]
  |. . > . . . . . . . . . . . . . . . .| [2:2] NP-SBJ|<,-ADJP> -> * , NP-SBJ|<ADJP-,> [1.0]
  |. . > . . . . . . . . . . . . . . . .| [2:2] ,  -> * ',' [1.0]
  |. [-] . . . . . . . . . . . . . . . .| [1:2] 'Vinken' [1.0]
  |[-] . . . . . . . . . . . . . . . . .| [0:1] 'Pierre' [1.0]
  |. . . . . . . . . [-] . . . . . . . .| [9:10] DT -> 'the' * [0.4]
  |. . . . . . . . . > . . . . . . . . .| [9:9] DT -> * 'the' [0.4]
  |. . . . . . . . . . . . [-] . . . . .| [12:13] DT -> 'a' * [0.4]
  |. . . . . . . . . . . . > . . . . . .| [12:12] DT -> * 'a' [0.4]
  |. . . [-] . . . . . . . . . . . . . .| [3:4] CD -> '61' * [0.3333333333333333]
  |. . . > . . . . . . . . . . . . . . .| [3:3] CD -> * '61' [0.3333333333333333]
  |. . . . . . . . . . . . . . . . [-] .| [16:17] CD -> '29' * [0.3333333333333333]
  |. . . . . . . . . . . . . . . . > . .| [16:16] CD -> * '29' [0.3333333333333333]
  |. . . . . [-] . . . . . . . . . . . .| [5:6] JJ -> 'old' * [0.2857142857142857]
  |. . . . . > . . . . . . . . . . . . .| [5:5] NP|<JJ-JJ> -> * JJ NP|<JJ-NN> [1.0]
  |. . . . . > . . . . . . . . . . . . .| [5:5] NP|<JJ-NN> -> * JJ NN [1.0]
  |. . . . . [-> . . . . . . . . . . . .| [5:6] NP|<JJ-JJ> -> JJ * NP|<JJ-NN> [0.2857142857142857]
  |. . . . . [-> . . . . . . . . . . . .| [5:6] NP|<JJ-NN> -> JJ * NN [0.2857142857142857]
  |. . . . . > . . . . . . . . . . . . .| [5:5] JJ -> * 'old' [0.2857142857142857]
  |. . . . . . . . . . . . . [-] . . . .| [13:14] JJ -> 'nonexecutive' * [0.2857142857142857]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP|<JJ-JJ> -> * JJ NP|<JJ-NN> [1.0]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP|<JJ-NN> -> * JJ NN [1.0]
  |. . . . . . . . . . . . . [-> . . . .| [13:14] NP|<JJ-JJ> -> JJ * NP|<JJ-NN> [0.2857142857142857]
  |. . . . . . . . . . . . . [-> . . . .| [13:14] NP|<JJ-NN> -> JJ * NN [0.2857142857142857]
  |. . . . . . . . . . . . . > . . . . .| [13:13] JJ -> * 'nonexecutive' [0.2857142857142857]
  |. . . . . . . . . . . . . . [-] . . .| [14:15] NN -> 'director' * [0.2857142857142857]
  |. . . . . . . . . . . . . . > . . . .| [14:14] NN -> * 'director' [0.2857142857142857]
  |. . . . . . . . . . . [-] . . . . . .| [11:12] IN -> 'as' * [0.25]
  |. . . . . . . . . . . > . . . . . . .| [11:11] PP -> * IN NP [1.0]
  |. . . . . . . . . . . > . . . . . . .| [11:11] PP-CLR -> * IN NP [1.0]
  |. . . . . . . . . . . [-> . . . . . .| [11:12] PP -> IN * NP [0.25]
  |. . . . . . . . . . . [-> . . . . . .| [11:12] PP-CLR -> IN * NP [0.25]
  |. . . . . . . . . . . > . . . . . . .| [11:11] IN -> * 'as' [0.25]
  |. . . . . . . [-> . . . . . . . . . .| [7:8] VP -> MD * VP [0.2]
  |. . . . . . . > . . . . . . . . . . .| [7:7] VP -> * MD VP [0.2]
  |. . . . . . . . [-> . . . . . . . . .| [8:9] VP -> VB * VP|<NP-PP-CLR> [0.2]
  |. . . . . . . . > . . . . . . . . . .| [8:8] VP -> * VB VP|<NP-PP-CLR> [0.2]
  |. [-] . . . . . . . . . . . . . . . .| [1:2] NNP -> 'Vinken' * [0.14285714285714285]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NP|<NNP-VBG> -> * NNP NP|<VBG-NN> [1.0]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NP-TMP -> * NNP CD [1.0]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NP|<NNP-NNP> -> * NNP NNP [0.5]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NP|<NNP-NNP> -> * NNP NP|<NNP-NNP> [0.5]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NP-SBJ -> * NNP NNP [0.3333333333333333]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NP -> * NNP NNP [0.2]
  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP|<NNP-VBG> -> NNP * NP|<VBG-NN> [0.14285714285714285]
  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP-TMP -> NNP * CD [0.14285714285714285]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NNP -> * 'Vinken' [0.14285714285714285]
  |. . . . . . . . . . [-] . . . . . . .| [10:11] NN -> 'board' * [0.14285714285714285]
  |. . . . . . . . . . > . . . . . . . .| [10:10] NN -> * 'board' [0.14285714285714285]
  |. . . . . . . . . . . . . . . . > . .| [16:16] NP -> * CD NNS [0.13333333333333333]
  |. . . > . . . . . . . . . . . . . . .| [3:3] NP -> * CD NNS [0.13333333333333333]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NP|<JJ-NN> [0.13333333333333333]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NP|<JJ-NN> [0.13333333333333333]
  |. . . . . . . . . . . . . [---] . . .| [13:15] NP|<JJ-NN> -> JJ NN * [0.08163265306122448]
  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP|<NNP-NNP> -> NNP * NNP [0.07142857142857142]
  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP|<NNP-NNP> -> NNP * NP|<NNP-NNP> [0.07142857142857142]
  |[-] . . . . . . . . . . . . . . . . .| [0:1] NNP -> 'Pierre' * [0.07142857142857142]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP|<NNP-VBG> -> * NNP NP|<VBG-NN> [1.0]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-TMP -> * NNP CD [1.0]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP|<NNP-NNP> -> * NNP NNP [0.5]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP|<NNP-NNP> -> * NNP NP|<NNP-NNP> [0.5]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ -> * NNP NNP [0.3333333333333333]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NNP NNP [0.2]
  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP|<NNP-VBG> -> NNP * NP|<VBG-NN> [0.07142857142857142]
  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP-TMP -> NNP * CD [0.07142857142857142]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NNP -> * 'Pierre' [0.07142857142857142]
  |. . . . . . . . . . . . . . . [-] . .| [15:16] NNP -> 'Nov.' * [0.07142857142857142]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NP|<NNP-VBG> -> * NNP NP|<VBG-NN> [1.0]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NP-TMP -> * NNP CD [1.0]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NP|<NNP-NNP> -> * NNP NNP [0.5]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NP|<NNP-NNP> -> * NNP NP|<NNP-NNP> [0.5]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NP-SBJ -> * NNP NNP [0.3333333333333333]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NP -> * NNP NNP [0.2]
  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP|<NNP-VBG> -> NNP * NP|<VBG-NN> [0.07142857142857142]
  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP-TMP -> NNP * CD [0.07142857142857142]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NNP -> * 'Nov.' [0.07142857142857142]
  |. . . . . . . . . . . . . . . > . . .| [15:15] NP -> * NNP NP|<NNP-NNP> [0.06666666666666667]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NNP NP|<NNP-NNP> [0.06666666666666667]
  |. . . . . . . . . . > . . . . . . . .| [10:10] NP -> * NN [0.06666666666666667]
  |. > . . . . . . . . . . . . . . . . .| [1:1] NP -> * NNP NP|<NNP-NNP> [0.06666666666666667]
  |. . . . . . . . . . . . . . > . . . .| [14:14] NP -> * NN [0.06666666666666667]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP -> * JJ NN [0.06666666666666667]
  |. . . . . > . . . . . . . . . . . . .| [5:5] NP -> * JJ NN [0.06666666666666667]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NP|<JJ-JJ> [0.06666666666666667]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NP|<NNP-VBG> [0.06666666666666667]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NN [0.06666666666666667]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NP|<JJ-JJ> [0.06666666666666667]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NP|<NNP-VBG> [0.06666666666666667]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NN [0.06666666666666667]
  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NP|<JJ-NN> [0.05333333333333334]
  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NP|<JJ-NN> [0.05333333333333334]
  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP-SBJ -> NNP * NNP [0.047619047619047616]
  |. . . . . . . . . . . . . . . . [-> .| [16:17] NP -> CD * NNS [0.04444444444444444]
  |. . . [-> . . . . . . . . . . . . . .| [3:4] NP -> CD * NNS [0.04444444444444444]
  |. . . [---] . . . . . . . . . . . . .| [3:5] NP -> CD NNS * [0.04444444444444444]
  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]
  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-PRD -> * NP PP [1.0]
  |. . . > . . . . . . . . . . . . . . .| [3:3] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]
  |. . . > . . . . . . . . . . . . . . .| [3:3] ADJP -> * NP JJ [1.0]
  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]
  |. . . > . . . . . . . . . . . . . . .| [3:3] NP -> * NP PP [0.06666666666666667]
  |. . . > . . . . . . . . . . . . . . .| [3:3] NP -> * NP NP|<,-NP> [0.06666666666666667]
  |. . . [---> . . . . . . . . . . . . .| [3:5] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.04444444444444444]
  |. . . [---> . . . . . . . . . . . . .| [3:5] NP-PRD -> NP * PP [0.04444444444444444]
  |. . . [---> . . . . . . . . . . . . .| [3:5] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.04444444444444444]
  |. . . [---> . . . . . . . . . . . . .| [3:5] ADJP -> NP * JJ [0.04444444444444444]
  |. . [-----] . . . . . . . . . . . . .| [2:5] NP|<,-NP> -> , NP * [0.04444444444444444]
  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP|<NNP-NNP> -> NNP * NNP [0.03571428571428571]
  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP|<NNP-NNP> -> NNP * NP|<NNP-NNP> [0.03571428571428571]
  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP|<NNP-NNP> -> NNP * NNP [0.03571428571428571]
  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP|<NNP-NNP> -> NNP * NP|<NNP-NNP> [0.03571428571428571]
  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP -> NNP * NNP [0.02857142857142857]
  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NP|<JJ-JJ> [0.02666666666666667]
  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NP|<NNP-VBG> [0.02666666666666667]
  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NN [0.02666666666666667]
  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NP|<JJ-JJ> [0.02666666666666667]
  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NP|<NNP-VBG> [0.02666666666666667]
  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NN [0.02666666666666667]
  |. . . . . . . . . . . . . . . [---] .| [15:17] NP-TMP -> NNP CD * [0.023809523809523808]
  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP-SBJ -> NNP * NNP [0.023809523809523808]
  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP-SBJ -> NNP * NNP [0.023809523809523808]
  |. . . . . . . . . . . . . . [-] . . .| [14:15] NP -> NN * [0.019047619047619046]
  |. . . . . . . . . . . . . . > . . . .| [14:14] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]
  |. . . . . . . . . . . . . . > . . . .| [14:14] NP-PRD -> * NP PP [1.0]
  |. . . . . . . . . . . . . . > . . . .| [14:14] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]
  |. . . . . . . . . . . . . . > . . . .| [14:14] ADJP -> * NP JJ [1.0]
  |. . . . . . . . . . . . . . > . . . .| [14:14] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]
  |. . . . . . . . . . . . . . > . . . .| [14:14] NP -> * NP PP [0.06666666666666667]
  |. . . . . . . . . . . . . . > . . . .| [14:14] NP -> * NP NP|<,-NP> [0.06666666666666667]
  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.019047619047619046]
  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP-PRD -> NP * PP [0.019047619047619046]
  |. . . . . . . . . . . . . . [-> . . .| [14:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.019047619047619046]
  |. . . . . . . . . . . . . . [-> . . .| [14:15] ADJP -> NP * JJ [0.019047619047619046]
  |. . . . . . . . . . . . . [-> . . . .| [13:14] NP -> JJ * NN [0.019047619047619046]
  |. . . . . [-> . . . . . . . . . . . .| [5:6] NP -> JJ * NN [0.019047619047619046]
  |. . . [---> . . . . . . . . . . . . .| [3:5] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.014814814814814812]
  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP -> NNP * NNP [0.014285714285714285]
  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP -> NNP * NNP [0.014285714285714285]
  |. . . [-----] . . . . . . . . . . . .| [3:6] ADJP -> NP JJ * [0.012698412698412697]
  |. . . > . . . . . . . . . . . . . . .| [3:3] UCP -> * ADJP UCP|<CC-NP> [1.0]
  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-SBJ|<ADJP-,> -> * ADJP , [1.0]
  |. . . [-----> . . . . . . . . . . . .| [3:6] UCP -> ADJP * UCP|<CC-NP> [0.012698412698412697]
  |. . . [-----> . . . . . . . . . . . .| [3:6] NP-SBJ|<ADJP-,> -> ADJP * , [0.012698412698412697]
  |. . . [-------] . . . . . . . . . . .| [3:7] NP-SBJ|<ADJP-,> -> ADJP , * [0.012698412698412697]
  |. . [---------] . . . . . . . . . . .| [2:7] NP-SBJ|<,-ADJP> -> , NP-SBJ|<ADJP-,> * [0.012698412698412697]
  |. . . . . . . . . . [-] . . . . . . .| [10:11] NP -> NN * [0.009523809523809523]
  |. . . . . . . . . . > . . . . . . . .| [10:10] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]
  |. . . . . . . . . . > . . . . . . . .| [10:10] NP-PRD -> * NP PP [1.0]
  |. . . . . . . . . . > . . . . . . . .| [10:10] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]
  |. . . . . . . . . . > . . . . . . . .| [10:10] ADJP -> * NP JJ [1.0]
  |. . . . . . . . . . > . . . . . . . .| [10:10] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]
  |. . . . . . . . . . > . . . . . . . .| [10:10] NP -> * NP PP [0.06666666666666667]
  |. . . . . . . . . . > . . . . . . . .| [10:10] NP -> * NP NP|<,-NP> [0.06666666666666667]
  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.009523809523809523]
  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP-PRD -> NP * PP [0.009523809523809523]
  |. . . . . . . . . . [-> . . . . . . .| [10:11] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.009523809523809523]
  |. . . . . . . . . . [-> . . . . . . .| [10:11] ADJP -> NP * JJ [0.009523809523809523]
  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP -> NNP * NP|<NNP-NNP> [0.009523809523809523]
  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.006349206349206348]
  |. . . . . . . . . . . . . [---] . . .| [13:15] NP -> JJ NN * [0.005442176870748299]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP-PRD -> * NP PP [1.0]
  |. . . . . . . . . . . . . > . . . . .| [13:13] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]
  |. . . . . . . . . . . . . > . . . . .| [13:13] ADJP -> * NP JJ [1.0]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP -> * NP PP [0.06666666666666667]
  |. . . . . . . . . . . . . > . . . . .| [13:13] NP -> * NP NP|<,-NP> [0.06666666666666667]
  |. . . . . . . . . . . . . [---> . . .| [13:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.005442176870748299]
  |. . . . . . . . . . . . . [---> . . .| [13:15] NP-PRD -> NP * PP [0.005442176870748299]
  |. . . . . . . . . . . . . [---> . . .| [13:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.005442176870748299]
  |. . . . . . . . . . . . . [---> . . .| [13:15] ADJP -> NP * JJ [0.005442176870748299]
  |[---] . . . . . . . . . . . . . . . .| [0:2] NP|<NNP-NNP> -> NNP NNP * [0.00510204081632653]
  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP -> NNP * NP|<NNP-NNP> [0.0047619047619047615]
  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP -> NNP * NP|<NNP-NNP> [0.0047619047619047615]
  |. . . . . . . . . . . . [-----] . . .| [12:15] NP -> DT NP|<JJ-NN> * [0.004353741496598639]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP-PRD -> * NP PP [1.0]
  |. . . . . . . . . . . . > . . . . . .| [12:12] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]
  |. . . . . . . . . . . . > . . . . . .| [12:12] ADJP -> * NP JJ [1.0]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * NP PP [0.06666666666666667]
  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * NP NP|<,-NP> [0.06666666666666667]
  |. . . . . . . . . . . . [-----> . . .| [12:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.004353741496598639]
  |. . . . . . . . . . . . [-----> . . .| [12:15] NP-PRD -> NP * PP [0.004353741496598639]
  |. . . . . . . . . . . . [-----> . . .| [12:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.004353741496598639]
  |. . . . . . . . . . . . [-----> . . .| [12:15] ADJP -> NP * JJ [0.004353741496598639]
  |. . . . . . . . . [---] . . . . . . .| [9:11] NP -> DT NN * [0.0038095238095238095]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP-PRD -> * NP PP [1.0]
  |. . . . . . . . . > . . . . . . . . .| [9:9] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]
  |. . . . . . . . . > . . . . . . . . .| [9:9] ADJP -> * NP JJ [1.0]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * NP PP [0.06666666666666667]
  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * NP NP|<,-NP> [0.06666666666666667]
  |. . . . . . . . . [---> . . . . . . .| [9:11] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.0038095238095238095]
  |. . . . . . . . . [---> . . . . . . .| [9:11] NP-PRD -> NP * PP [0.0038095238095238095]
  |. . . . . . . . . [---> . . . . . . .| [9:11] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.0038095238095238095]
  |. . . . . . . . . [---> . . . . . . .| [9:11] ADJP -> NP * JJ [0.0038095238095238095]
  |[---] . . . . . . . . . . . . . . . .| [0:2] NP-SBJ -> NNP NNP * [0.0034013605442176865]
  |> . . . . . . . . . . . . . . . . . .| [0:0] S  -> * NP-SBJ S|<VP-.> [0.5]
  |> . . . . . . . . . . . . . . . . . .| [0:0] S  -> * NP-SBJ NP-PRD [0.25]
  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.003174603174603174]
  |. . . [---> . . . . . . . . . . . . .| [3:5] NP -> NP * PP [0.0029629629629629624]
  |. . . [---> . . . . . . . . . . . . .| [3:5] NP -> NP * NP|<,-NP> [0.0029629629629629624]
  |[---] . . . . . . . . . . . . . . . .| [0:2] NP -> NNP NNP * [0.002040816326530612]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-PRD -> * NP PP [1.0]
  |> . . . . . . . . . . . . . . . . . .| [0:0] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]
  |> . . . . . . . . . . . . . . . . . .| [0:0] ADJP -> * NP JJ [1.0]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NP PP [0.06666666666666667]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NP NP|<,-NP> [0.06666666666666667]
  |[---> . . . . . . . . . . . . . . . .| [0:2] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.002040816326530612]
  |[---> . . . . . . . . . . . . . . . .| [0:2] NP-PRD -> NP * PP [0.002040816326530612]
  |[---> . . . . . . . . . . . . . . . .| [0:2] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.002040816326530612]
  |[---> . . . . . . . . . . . . . . . .| [0:2] ADJP -> NP * JJ [0.002040816326530612]
  |. . . . . . . . . . . . . [---> . . .| [13:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0018140589569160996]
  |[---> . . . . . . . . . . . . . . . .| [0:2] S  -> NP-SBJ * S|<VP-.> [0.0017006802721088433]
  |. . . . . . . . . . . . [-----> . . .| [12:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0014512471655328796]
  |. . . . . . . . . [---> . . . . . . .| [9:11] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0012698412698412698]
  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP -> NP * PP [0.0012698412698412696]
  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP -> NP * NP|<,-NP> [0.0012698412698412696]
  |. . . . . . . . . . . [-------] . . .| [11:15] PP -> IN NP * [0.0010884353741496598]
  |. . . . . . . . . . . [-------] . . .| [11:15] PP-CLR -> IN NP * [0.0010884353741496598]
  |. . . . . . . . . . . > . . . . . . .| [11:11] VP|<PP-CLR-NP-TMP> -> * PP-CLR NP-TMP [1.0]
  |. . . . . . . . . . . [-------> . . .| [11:15] VP|<PP-CLR-NP-TMP> -> PP-CLR * NP-TMP [0.0010884353741496598]
  |[---> . . . . . . . . . . . . . . . .| [0:2] S  -> NP-SBJ * NP-PRD [0.0008503401360544216]
  |[---> . . . . . . . . . . . . . . . .| [0:2] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0006802721088435373]
  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP -> NP * PP [0.0006349206349206348]
  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP -> NP * NP|<,-NP> [0.0006349206349206348]
  |. . . . . . . . . . . . . [---> . . .| [13:15] NP -> NP * PP [0.0003628117913832199]
  |. . . . . . . . . . . . . [---> . . .| [13:15] NP -> NP * NP|<,-NP> [0.0003628117913832199]
  |. . . . . . . . . . . . [-----> . . .| [12:15] NP -> NP * PP [0.00029024943310657596]
  |. . . . . . . . . . . . [-----> . . .| [12:15] NP -> NP * NP|<,-NP> [0.00029024943310657596]
  |. . . . . . . . . [---> . . . . . . .| [9:11] NP -> NP * PP [0.00025396825396825396]
  |. . . . . . . . . [---> . . . . . . .| [9:11] NP -> NP * NP|<,-NP> [0.00025396825396825396]
  |[---> . . . . . . . . . . . . . . . .| [0:2] NP -> NP * PP [0.00013605442176870745]
  |[---> . . . . . . . . . . . . . . . .| [0:2] NP -> NP * NP|<,-NP> [0.00013605442176870745]
  |. . . . . . . . . . . [-----------] .| [11:17] VP|<PP-CLR-NP-TMP> -> PP-CLR NP-TMP * [2.591512795594428e-05]
  |. . . . . . . . . . [---------] . . .| [10:15] NP-PRD -> NP PP * [1.0366051182377711e-05]
  |[-------------] . . . . . . . . . . .| [0:7] NP-SBJ -> NP NP-SBJ|<,-ADJP> * [8.638375985314757e-06]
  |[---------] . . . . . . . . . . . . .| [0:5] NP -> NP NP|<,-NP> * [6.04686318972033e-06]
  |[---------> . . . . . . . . . . . . .| [0:5] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [6.04686318972033e-06]
  |[---------> . . . . . . . . . . . . .| [0:5] NP-PRD -> NP * PP [6.04686318972033e-06]
  |[---------> . . . . . . . . . . . . .| [0:5] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [6.04686318972033e-06]
  |[---------> . . . . . . . . . . . . .| [0:5] ADJP -> NP * JJ [6.04686318972033e-06]
  |[-------------> . . . . . . . . . . .| [0:7] S  -> NP-SBJ * S|<VP-.> [4.319187992657379e-06]
  |. . . . . . . . . [-----------] . . .| [9:15] NP-PRD -> NP PP * [4.146420472951085e-06]
  |[-------------> . . . . . . . . . . .| [0:7] S  -> NP-SBJ * NP-PRD [2.1595939963286893e-06]
  |[---------> . . . . . . . . . . . . .| [0:5] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [2.01562106324011e-06]
  |[-----------] . . . . . . . . . . . .| [0:6] ADJP -> NP JJ * [1.7276751970629514e-06]
  |> . . . . . . . . . . . . . . . . . .| [0:0] UCP -> * ADJP UCP|<CC-NP> [1.0]
  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ|<ADJP-,> -> * ADJP , [1.0]
  |[-----------> . . . . . . . . . . . .| [0:6] UCP -> ADJP * UCP|<CC-NP> [1.7276751970629514e-06]
  |[-----------> . . . . . . . . . . . .| [0:6] NP-SBJ|<ADJP-,> -> ADJP * , [1.7276751970629514e-06]
  |[-------------] . . . . . . . . . . .| [0:7] NP-SBJ|<ADJP-,> -> ADJP , * [1.7276751970629514e-06]
  |. . . . . . . . . . [---------] . . .| [10:15] NP -> NP PP * [6.910700788251807e-07]
  |. . . . . . . . . . [---------> . . .| [10:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [6.910700788251807e-07]
  |. . . . . . . . . . [---------> . . .| [10:15] NP-PRD -> NP * PP [6.910700788251807e-07]
  |. . . . . . . . . . [---------> . . .| [10:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [6.910700788251807e-07]
  |. . . . . . . . . . [---------> . . .| [10:15] ADJP -> NP * JJ [6.910700788251807e-07]
  |[---------> . . . . . . . . . . . . .| [0:5] NP -> NP * PP [4.0312421264802203e-07]
  |[---------> . . . . . . . . . . . . .| [0:5] NP -> NP * NP|<,-NP> [4.0312421264802203e-07]
  |. . . . . . . . . [-----------] . . .| [9:15] NP -> NP PP * [2.764280315300723e-07]
  |. . . . . . . . . [-----------> . . .| [9:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [2.764280315300723e-07]
  |. . . . . . . . . [-----------> . . .| [9:15] NP-PRD -> NP * PP [2.764280315300723e-07]
  |. . . . . . . . . [-----------> . . .| [9:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [2.764280315300723e-07]
  |. . . . . . . . . [-----------> . . .| [9:15] ADJP -> NP * JJ [2.764280315300723e-07]
  |. . . . . . . . . . [-------------] .| [10:17] VP|<NP-PP-CLR> -> NP VP|<PP-CLR-NP-TMP> * [2.4681074243756453e-07]
  |. . . . . . . . . . [---------> . . .| [10:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [2.303566929417269e-07]
  |. . . . . . . . . [---------------] .| [9:17] VP|<NP-PP-CLR> -> NP VP|<PP-CLR-NP-TMP> * [9.872429697502583e-08]
  |. . . . . . . . . [-----------> . . .| [9:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [9.214267717669077e-08]
  |. . . . . . . . . . [---------> . . .| [10:15] NP -> NP * PP [4.607133858834538e-08]
  |. . . . . . . . . . [---------> . . .| [10:15] NP -> NP * NP|<,-NP> [4.607133858834538e-08]
  |. . . . . . . . [-----------------] .| [8:17] VP -> VB VP|<NP-PP-CLR> * [1.9744859395005166e-08]
  |. . . . . . . . > . . . . . . . . . .| [8:8] S|<VP-.> -> * VP . [1.0]
  |. . . . . . . . [-----------------> .| [8:17] S|<VP-.> -> VP * . [1.9744859395005166e-08]
  |. . . . . . . . [-------------------]| [8:18] S|<VP-.> -> VP . * [1.9744859395005166e-08]
  |. . . . . . . . . [-----------> . . .| [9:15] NP -> NP * PP [1.8428535435338155e-08]
  |. . . . . . . . . [-----------> . . .| [9:15] NP -> NP * NP|<,-NP> [1.8428535435338155e-08]
  |. . . . . . . [-------------------] .| [7:17] VP -> MD VP * [3.948971879001034e-09]
  |. . . . . . . > . . . . . . . . . . .| [7:7] S|<VP-.> -> * VP . [1.0]
  |. . . . . . . [-------------------> .| [7:17] S|<VP-.> -> VP * . [3.948971879001034e-09]
  |. . . . . . . [---------------------]| [7:18] S|<VP-.> -> VP . * [3.948971879001034e-09]
  |[===================================]| [0:18] S  -> NP-SBJ S|<VP-.> * [1.705635192312291e-14]
(S
  (NP-SBJ
    (NP (NNP Pierre) (NNP Vinken))
    (NP-SBJ|<,-ADJP>
      (, ,)
      (NP-SBJ|<ADJP-,>
        (ADJP (NP (CD 61) (NNS years)) (JJ old))
        (, ,))))
  (S|<VP-.>
    (VP
      (MD will)
      (VP
        (VB join)
        (VP|<NP-PP-CLR>
          (NP (DT the) (NN board))
          (VP|<PP-CLR-NP-TMP>
            (PP-CLR
              (IN as)
              (NP
                (DT a)
                (NP|<JJ-NN>
                  (JJ nonexecutive)
                  (NN director))))
            (NP-TMP (NNP Nov.) (CD 29))))))
    (. .))) (p=1.70564e-14)

The other parsers are defined in the nltk.parse module.

In [36]:
import sys, time
from nltk import tokenize
from nltk.grammar import toy_pcfg1
from nltk.parse import pchart
from nltk.parse import ViterbiParser

demos = [('I saw John with my telescope', toy_pcfg1)]
sent, grammar = demos[0]

# Tokenize the sentence.
tokens = sent.split()

# Define a list of parsers.  We'll use all parsers.
parsers = [
ViterbiParser(grammar),
pchart.InsideChartParser(grammar),
pchart.RandomChartParser(grammar),
pchart.UnsortedChartParser(grammar),
pchart.LongestChartParser(grammar),
pchart.InsideChartParser(grammar, beam_size = len(tokens)+1)
]

We can now loop over the different parsers and compare the output and performance:

In [37]:
# Run the parsers on the tokenized sentence.
from functools import reduce
times = []
average_p = []
num_parses = []
all_parses = {}
for parser in parsers:
    print('\ns: %s\nparser: %s\ngrammar: %s' % (sent,parser,grammar))
    parser.trace(3)
    t = time.time()
    parses = parser.parse_all(tokens)
    times.append(time.time()-t)
    if parses: 
        lp = len(parses)
        p = reduce(lambda a,b:a+b.prob(), parses, 0.0)
    else: 
        p = 0
    average_p.append(p)
    num_parses.append(len(parses))
    for p in parses: 
        all_parses[p.freeze()] = 1

# Print summary statistics
print()
print('-------------------------+------------------------------------------')
print('   Parser           Beam | Time (secs)   # Parses   Average P(parse)')
print('-------------------------+------------------------------------------')
for i in range(len(parsers)):
    print('%19s %4d |%11.4f%11d%19.14f' % (parsers[i].__class__.__name__,
      getattr(parsers[0], "beam_size", 0),
      times[i], 
      num_parses[i], 
      average_p[i]))
parses = all_parses.keys()
if parses: 
    p = reduce(lambda a,b:a+b.prob(), parses, 0)/len(parses)
else: 
    p = 0
print('-------------------------+------------------------------------------')
print('%19s      |%11s%11d%19.14f' % ('(All Parses)', 'n/a', len(parses), p))
print()

for parse in parses:
    print(parse)
s: I saw John with my telescope
parser: <ViterbiParser for <Grammar with 17 productions>>
grammar: Grammar with 17 productions (start state = S)
    S -> NP VP [1.0]
    NP -> Det N [0.5]
    NP -> NP PP [0.25]
    NP -> 'John' [0.1]
    NP -> 'I' [0.15]
    Det -> 'the' [0.8]
    Det -> 'my' [0.2]
    N -> 'man' [0.5]
    N -> 'telescope' [0.5]
    VP -> VP PP [0.1]
    VP -> V NP [0.7]
    VP -> V [0.2]
    V -> 'ate' [0.35]
    V -> 'saw' [0.65]
    PP -> P NP [1.0]
    P -> 'with' [0.61]
    P -> 'under' [0.39]
Inserting tokens into the most likely constituents table...
   Insert: |=.....| I
   Insert: |.=....| saw
   Insert: |..=...| John
   Insert: |...=..| with
   Insert: |....=.| my
   Insert: |.....=| telescope
Finding the most likely constituents spanning 1 text elements...
   Insert: |=.....| NP -> 'I' [0.15]                0.1500000000 
   Insert: |.=....| V -> 'saw' [0.65]               0.6500000000 
   Insert: |.=....| VP -> V [0.2]                   0.1300000000 
   Insert: |..=...| NP -> 'John' [0.1]              0.1000000000 
   Insert: |...=..| P -> 'with' [0.61]              0.6100000000 
   Insert: |....=.| Det -> 'my' [0.2]               0.2000000000 
   Insert: |.....=| N -> 'telescope' [0.5]          0.5000000000 
Finding the most likely constituents spanning 2 text elements...
   Insert: |==....| S -> NP VP [1.0]                0.0195000000 
   Insert: |.==...| VP -> V NP [0.7]                0.0455000000 
   Insert: |....==| NP -> Det N [0.5]               0.0500000000 
Finding the most likely constituents spanning 3 text elements...
   Insert: |===...| S -> NP VP [1.0]                0.0068250000 
   Insert: |...===| PP -> P NP [1.0]                0.0305000000 
Finding the most likely constituents spanning 4 text elements...
   Insert: |..====| NP -> NP PP [0.25]              0.0007625000 
Finding the most likely constituents spanning 5 text elements...
   Insert: |.=====| VP -> VP PP [0.1]               0.0001387750 
   Insert: |.=====| VP -> V NP [0.7]                0.0003469375 
  Discard: |.=====| VP -> VP PP [0.1]               0.0001387750 
Finding the most likely constituents spanning 6 text elements...
   Insert: |======| S -> NP VP [1.0]                0.0000520406 

s: I saw John with my telescope
parser: <nltk.parse.pchart.InsideChartParser object at 0x00000263D2359748>
grammar: Grammar with 17 productions (start state = S)
    S -> NP VP [1.0]
    NP -> Det N [0.5]
    NP -> NP PP [0.25]
    NP -> 'John' [0.1]
    NP -> 'I' [0.15]
    Det -> 'the' [0.8]
    Det -> 'my' [0.2]
    N -> 'man' [0.5]
    N -> 'telescope' [0.5]
    VP -> VP PP [0.1]
    VP -> V NP [0.7]
    VP -> V [0.2]
    V -> 'ate' [0.35]
    V -> 'saw' [0.65]
    PP -> P NP [1.0]
    P -> 'with' [0.61]
    P -> 'under' [0.39]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]
  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]
  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]
  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]
  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]
  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]
  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]
  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]
  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]
  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]
  |. > . . . . .| [1:1] VP -> * V                    [0.2]
  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]
  |. . . . > . .| [4:4] NP -> * Det N                [0.5]
  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]
  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]
  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]
  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]
  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]
  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]
  |. [-] . . . .| [1:2] VP -> V *                    [0.13]
  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]
  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]
  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]
  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]
  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]
  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]
  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]
  |. . . . [---]| [4:6] NP -> Det N *                [0.05]
  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]
  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]
  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]
  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]
  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]
  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]
  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]
  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]
  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]
  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]
  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]
  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]
  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]
  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]
  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]
  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]
  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]
  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]
  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]
  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]
  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]

s: I saw John with my telescope
parser: <nltk.parse.pchart.RandomChartParser object at 0x00000263D2367208>
grammar: Grammar with 17 productions (start state = S)
    S -> NP VP [1.0]
    NP -> Det N [0.5]
    NP -> NP PP [0.25]
    NP -> 'John' [0.1]
    NP -> 'I' [0.15]
    Det -> 'the' [0.8]
    Det -> 'my' [0.2]
    N -> 'man' [0.5]
    N -> 'telescope' [0.5]
    VP -> VP PP [0.1]
    VP -> V NP [0.7]
    VP -> V [0.2]
    V -> 'ate' [0.35]
    V -> 'saw' [0.65]
    PP -> P NP [1.0]
    P -> 'with' [0.61]
    P -> 'under' [0.39]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]
  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]
  |. . . . > . .| [4:4] NP -> * Det N                [0.5]
  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]
  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]
  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]
  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]
  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]
  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]
  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]
  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]
  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]
  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]
  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]
  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]
  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]
  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]
  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]
  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]
  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]
  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]
  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]
  |. . . . [---]| [4:6] NP -> Det N *                [0.05]
  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]
  |. > . . . . .| [1:1] VP -> * V                    [0.2]
  |. [-] . . . .| [1:2] VP -> V *                    [0.13]
  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]
  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]
  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]
  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]
  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]
  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]
  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]
  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]
  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]
  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]
  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]
  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]
  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]
  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]
  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]
  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]
  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]
  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]
  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]

s: I saw John with my telescope
parser: <nltk.parse.pchart.UnsortedChartParser object at 0x00000263D2367248>
grammar: Grammar with 17 productions (start state = S)
    S -> NP VP [1.0]
    NP -> Det N [0.5]
    NP -> NP PP [0.25]
    NP -> 'John' [0.1]
    NP -> 'I' [0.15]
    Det -> 'the' [0.8]
    Det -> 'my' [0.2]
    N -> 'man' [0.5]
    N -> 'telescope' [0.5]
    VP -> VP PP [0.1]
    VP -> V NP [0.7]
    VP -> V [0.2]
    V -> 'ate' [0.35]
    V -> 'saw' [0.65]
    PP -> P NP [1.0]
    P -> 'with' [0.61]
    P -> 'under' [0.39]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]
  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]
  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]
  |. . . . [---]| [4:6] NP -> Det N *                [0.05]
  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]
  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]
  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]
  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]
  |. . . . > . .| [4:4] NP -> * Det N                [0.5]
  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]
  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]
  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]
  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]
  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]
  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]
  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]
  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]
  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]
  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]
  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]
  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]
  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]
  |. [-] . . . .| [1:2] VP -> V *                    [0.13]
  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]
  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]
  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]
  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]
  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]
  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]
  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]
  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]
  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]
  |. > . . . . .| [1:1] VP -> * V                    [0.2]
  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]
  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]
  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]
  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]
  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]
  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]
  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]
  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]
  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]
  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]
  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]

s: I saw John with my telescope
parser: <nltk.parse.pchart.LongestChartParser object at 0x00000263D2367388>
grammar: Grammar with 17 productions (start state = S)
    S -> NP VP [1.0]
    NP -> Det N [0.5]
    NP -> NP PP [0.25]
    NP -> 'John' [0.1]
    NP -> 'I' [0.15]
    Det -> 'the' [0.8]
    Det -> 'my' [0.2]
    N -> 'man' [0.5]
    N -> 'telescope' [0.5]
    VP -> VP PP [0.1]
    VP -> V NP [0.7]
    VP -> V [0.2]
    V -> 'ate' [0.35]
    V -> 'saw' [0.65]
    PP -> P NP [1.0]
    P -> 'with' [0.61]
    P -> 'under' [0.39]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]
  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]
  |. . . . [---]| [4:6] NP -> Det N *                [0.05]
  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]
  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]
  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]
  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]
  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]
  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]
  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]
  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]
  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]
  |. [-] . . . .| [1:2] VP -> V *                    [0.13]
  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]
  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]
  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]
  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]
  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]
  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]
  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]
  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]
  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]
  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]
  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]
  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]
  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]
  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]
  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]
  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]
  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]
  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]
  |. > . . . . .| [1:1] VP -> * V                    [0.2]
  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]
  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]
  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]
  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]
  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]
  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]
  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]
  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]
  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]
  |. . . . > . .| [4:4] NP -> * Det N                [0.5]
  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]
  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]

s: I saw John with my telescope
parser: <nltk.parse.pchart.InsideChartParser object at 0x00000263D2C20BC8>
grammar: Grammar with 17 productions (start state = S)
    S -> NP VP [1.0]
    NP -> Det N [0.5]
    NP -> NP PP [0.25]
    NP -> 'John' [0.1]
    NP -> 'I' [0.15]
    Det -> 'the' [0.8]
    Det -> 'my' [0.2]
    N -> 'man' [0.5]
    N -> 'telescope' [0.5]
    VP -> VP PP [0.1]
    VP -> V NP [0.7]
    VP -> V [0.2]
    V -> 'ate' [0.35]
    V -> 'saw' [0.65]
    PP -> P NP [1.0]
    P -> 'with' [0.61]
    P -> 'under' [0.39]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . . [-]| [5:6] 'telescope'                  [1.0]
  |. . . . [-] .| [4:5] 'my'                         [1.0]
  |. . . . > . .| [4:4] Det -> * 'my'                [DISCARDED]
  |. . . [-] . .| [3:4] 'with'                       [1.0]
  |. . . . [-] .| [4:5] Det -> 'my' *                [DISCARDED]
  |. . [-] . . .| [2:3] 'John'                       [1.0]
  |. . > . . . .| [2:2] NP -> * 'John'               [DISCARDED]
  |. [-] . . . .| [1:2] 'saw'                        [1.0]
  |. . [-] . . .| [2:3] NP -> 'John' *               [DISCARDED]
  |[-] . . . . .| [0:1] 'I'                          [1.0]
  |> . . . . . .| [0:0] NP -> * 'I'                  [DISCARDED]
  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]
  |. [-] . . . .| [1:2] VP -> V *                    [DISCARDED]
  |[-] . . . . .| [0:1] NP -> 'I' *                  [DISCARDED]
  |. > . . . . .| [1:1] VP -> * V                    [DISCARDED]
  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]
  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]
  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]
  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]
  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]
  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]
  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]
  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]
  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]
  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]
  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]
  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]
  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]

-------------------------+------------------------------------------
   Parser           Beam | Time (secs)   # Parses   Average P(parse)
-------------------------+------------------------------------------
      ViterbiParser    0 |     0.0060          1   0.00005204062500
  InsideChartParser    0 |     0.0100          2   0.00007285687500
  RandomChartParser    0 |     0.0070          2   0.00007285687500
UnsortedChartParser    0 |     0.0070          2   0.00007285687500
 LongestChartParser    0 |     0.0110          2   0.00007285687500
  InsideChartParser    0 |     0.0040          0   0.00000000000000
-------------------------+------------------------------------------
       (All Parses)      |        n/a          2   0.00003642843750

(S
  (NP I)
  (VP
    (V saw)
    (NP
      (NP John)
      (PP (P with) (NP (Det my) (N telescope)))))) [5.204062499999999e-05]
(S
  (NP I)
  (VP
    (VP (V saw) (NP John))
    (PP (P with) (NP (Det my) (N telescope))))) [2.081625e-05]

(C) 2018-2019 by Damir Cavar - Creative Commons Attribution-ShareAlike 4.0 International License (CA BY-SA 4.0). Parts of the code are taken from Michael Elhadad's notebook Constituent-based Syntactic Parsing with NLTK. Please consult him for details about the copyright.