(C) 2018 by Damir Cavar
This is a tutorial related to the discussion of parsing with Probabilistic Context Free Grammars (PCFG) in the class Advanced Natural Language Processing taught at Indiana University in Fall 2018.
This code and tutorial is based on different summer school courses that I taught and tutorials that I gave at different occasions in Europe and the US. This particular example will use code from the TDAParser.py and other scripts developed since 2002. Most of this material was used in general introduction courses to algorithms in Natural Language Processing that I taught at Indiana University, University of Konstanz, University of Zadar, University of Nova Gorica.
In [1]:
import sys
Let us assume that our Phrase Structure Grammar consists of rules that contain one symbol in the Left-Hand Side, followed by a production symbol, an arrow, and by a list of at least one terminal and symbol. Comments can be introduced using the # symbol. Every rule has to be contained in one line.
In [14]:
grammarText = """
# PSG1
# small English grammar
# (C) 2005 by Damir Cavar, Indiana University
# Grammar:
S -> NP VP
NP -> N
NP -> Adj N
NP -> Art Adj N
NP -> Art N
NP -> Art N PP
#NP -> Art N NP
VP -> V
VP -> V NP
VP -> Adv V NP
VP -> V PP
VP -> V NP PP
PP -> P NP
# Lexicon:
N -> John
N -> Mary
N -> bench
N -> cat
N -> mouse
Art -> the
Art -> a
Adj -> green
Adj -> yellow
Adj -> big
Adj -> small
Adv -> often
Adv -> yesterday
V -> kissed
V -> loves
V -> sees
V -> meets
V -> chases
P -> on
P -> in
P -> beside
P -> under
"""
We can parse this grammar into a representation that allows us to fetch the left- and the right-hand side of a rule for top- or bottom-up parsing.
In [5]:
class PSG:
def __init__(self, grammar):
self.LHS = {}
self.RHS = {}
self.__read__(grammar)
def __str__(self):
text = ""
for i in self.LHS.keys():
if len(text) > 0:
text += "\n"
for x in self.LHS[i]:
text += i + " -> " + " ".join(x) + "\n"
return text
def __read__(self, g):
for i in g.split("\n"):
i = i.split("#")[0].strip() # cut off comment string and strip
if len(i) == 0: continue
tokens = i.split("->")
if len(tokens) != 2: continue
lhs = tokens[0].split()
if len(lhs) != 1: continue
rhs = tuple(tokens[1].split())
value = self.LHS.get(lhs[0], [])
if rhs not in value: value.append(rhs)
self.LHS[lhs[0]] = value
value = self.RHS.get(rhs, [])
if lhs[0] not in value: value.append(lhs[0])
self.RHS[rhs] = value
def getRHS(self, left):
return self.LHS.get(left, [])
def getLHS(self, right):
return self.RHS.get(right, [])
The grammar file:
Defining some parameters:
In [15]:
LIFO = -1
FIFO = 0
strategy = FIFO
In [18]:
def tdparse(inp, goal, grammar, agenda):
print("Got : %s\tinput: %s" % (goal, inp))
if goal == inp == []: print("Success")
elif goal == [] or inp == []:
if agenda == []: print("Fail: Agenda empty!")
else:
entry = agenda.pop(strategy)
print("Backing up to: %s with %s" % (entry[0], entry[1]))
tdparse(entry[1], entry[0], grammar, agenda)
else: # there is something in goal and input
if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
tdparse(inp[1:], goal[1:], grammar, agenda)
else:
for i in grammar.LHS.get(goal[0], []):
if [list(i) + goal[1:], inp] not in agenda:
agenda.append([list(i) + goal[1:], inp])
if len(agenda) > 0:
entry = agenda.pop(strategy)
tdparse(entry[1], entry[0], grammar, agenda)
else: print("Fail: Agenda empty!")
In [19]:
myGrammar = PSG(grammarText)
print(myGrammar)
tdparse( ('John', 'loves', 'Mary') , ["S"], myGrammar, [])
S -> NP VP
NP -> N
NP -> Adj N
NP -> Art Adj N
NP -> Art N
NP -> Art N PP
VP -> V
VP -> V NP
VP -> Adv V NP
VP -> V PP
VP -> V NP PP
PP -> P NP
N -> John
N -> Mary
N -> bench
N -> cat
N -> mouse
Art -> the
Art -> a
Adj -> green
Adj -> yellow
Adj -> big
Adj -> small
Adv -> often
Adv -> yesterday
V -> kissed
V -> loves
V -> sees
V -> meets
V -> chases
P -> on
P -> in
P -> beside
P -> under
Got : ['S'] input: ('John', 'loves', 'Mary')
Got : ['NP', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['Adj', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['Art', 'Adj', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['Art', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['Art', 'N', 'PP', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['John', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['VP'] input: ('loves', 'Mary')
Got : ['Mary', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['bench', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['cat', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['mouse', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['green', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['yellow', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['big', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['small', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['the', 'Adj', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['a', 'Adj', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['the', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['a', 'N', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['the', 'N', 'PP', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['a', 'N', 'PP', 'VP'] input: ('John', 'loves', 'Mary')
Got : ['V'] input: ('loves', 'Mary')
Got : ['V', 'NP'] input: ('loves', 'Mary')
Got : ['Adv', 'V', 'NP'] input: ('loves', 'Mary')
Got : ['V', 'PP'] input: ('loves', 'Mary')
Got : ['V', 'NP', 'PP'] input: ('loves', 'Mary')
Got : ['kissed'] input: ('loves', 'Mary')
Got : ['loves'] input: ('loves', 'Mary')
Got : [] input: ('Mary',)
Backing up to: ['sees'] with ('loves', 'Mary')
Got : ['sees'] input: ('loves', 'Mary')
Got : ['meets'] input: ('loves', 'Mary')
Got : ['chases'] input: ('loves', 'Mary')
Got : ['kissed', 'NP'] input: ('loves', 'Mary')
Got : ['loves', 'NP'] input: ('loves', 'Mary')
Got : ['NP'] input: ('Mary',)
Got : ['sees', 'NP'] input: ('loves', 'Mary')
Got : ['meets', 'NP'] input: ('loves', 'Mary')
Got : ['chases', 'NP'] input: ('loves', 'Mary')
Got : ['often', 'V', 'NP'] input: ('loves', 'Mary')
Got : ['yesterday', 'V', 'NP'] input: ('loves', 'Mary')
Got : ['kissed', 'PP'] input: ('loves', 'Mary')
Got : ['loves', 'PP'] input: ('loves', 'Mary')
Got : ['PP'] input: ('Mary',)
Got : ['sees', 'PP'] input: ('loves', 'Mary')
Got : ['meets', 'PP'] input: ('loves', 'Mary')
Got : ['chases', 'PP'] input: ('loves', 'Mary')
Got : ['kissed', 'NP', 'PP'] input: ('loves', 'Mary')
Got : ['loves', 'NP', 'PP'] input: ('loves', 'Mary')
Got : ['NP', 'PP'] input: ('Mary',)
Got : ['sees', 'NP', 'PP'] input: ('loves', 'Mary')
Got : ['meets', 'NP', 'PP'] input: ('loves', 'Mary')
Got : ['chases', 'NP', 'PP'] input: ('loves', 'Mary')
Got : ['N'] input: ('Mary',)
Got : ['Adj', 'N'] input: ('Mary',)
Got : ['Art', 'Adj', 'N'] input: ('Mary',)
Got : ['Art', 'N'] input: ('Mary',)
Got : ['Art', 'N', 'PP'] input: ('Mary',)
Got : ['P', 'NP'] input: ('Mary',)
Got : ['N', 'PP'] input: ('Mary',)
Got : ['Adj', 'N', 'PP'] input: ('Mary',)
Got : ['Art', 'Adj', 'N', 'PP'] input: ('Mary',)
Got : ['Art', 'N', 'PP', 'PP'] input: ('Mary',)
Got : ['John'] input: ('Mary',)
Got : ['Mary'] input: ('Mary',)
Got : [] input: ()
Backing up to: ['bench'] with ('Mary',)
Got : ['bench'] input: ('Mary',)
Got : ['cat'] input: ('Mary',)
Got : ['mouse'] input: ('Mary',)
Got : ['green', 'N'] input: ('Mary',)
Got : ['yellow', 'N'] input: ('Mary',)
Got : ['big', 'N'] input: ('Mary',)
Got : ['small', 'N'] input: ('Mary',)
Got : ['the', 'Adj', 'N'] input: ('Mary',)
Got : ['a', 'Adj', 'N'] input: ('Mary',)
Got : ['the', 'N'] input: ('Mary',)
Got : ['a', 'N'] input: ('Mary',)
Got : ['the', 'N', 'PP'] input: ('Mary',)
Got : ['a', 'N', 'PP'] input: ('Mary',)
Got : ['on', 'NP'] input: ('Mary',)
Got : ['in', 'NP'] input: ('Mary',)
Got : ['beside', 'NP'] input: ('Mary',)
Got : ['under', 'NP'] input: ('Mary',)
Got : ['John', 'PP'] input: ('Mary',)
Got : ['Mary', 'PP'] input: ('Mary',)
Got : ['PP'] input: ()
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
<ipython-input-19-0f0cc64033ab> in <module>()
1 myGrammar = PSG(grammarText)
2 print(myGrammar)
----> 3 tdparse( ('John', 'loves', 'Mary') , ["S"], myGrammar, [])
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
---> 12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
14 for i in grammar.LHS.get(goal[0], []):
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
---> 12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
14 for i in grammar.LHS.get(goal[0], []):
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
7 entry = agenda.pop(strategy)
8 print("Backing up to: %s with %s" % (entry[0], entry[1]))
----> 9 tdparse(entry[1], entry[0], grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
---> 12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
14 for i in grammar.LHS.get(goal[0], []):
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
---> 12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
14 for i in grammar.LHS.get(goal[0], []):
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
---> 12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
14 for i in grammar.LHS.get(goal[0], []):
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
---> 12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
14 for i in grammar.LHS.get(goal[0], []):
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
7 entry = agenda.pop(strategy)
8 print("Backing up to: %s with %s" % (entry[0], entry[1]))
----> 9 tdparse(entry[1], entry[0], grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
17 if len(agenda) > 0:
18 entry = agenda.pop(strategy)
---> 19 tdparse(entry[1], entry[0], grammar, agenda)
20 else: print("Fail: Agenda empty!")
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
10 else: # there is something in goal and input
11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
---> 12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
14 for i in grammar.LHS.get(goal[0], []):
<ipython-input-18-139594fe9f50> in tdparse(inp, goal, grammar, agenda)
9 tdparse(entry[1], entry[0], grammar, agenda)
10 else: # there is something in goal and input
---> 11 if goal[0] == inp[0]: # if initial symbols match, reduce lists, parse
12 tdparse(inp[1:], goal[1:], grammar, agenda)
13 else:
IndexError: tuple index out of range
In [ ]:
In [ ]:
Content source: dcavar/python-tutorial-for-ipython
Similar notebooks: