import nltk
from ipythonblocks import BlockGrid, colors
# import time
# from IPython.display import clear_output
def print_chart(chart, num_of_tabs=1):
"""
Nicht notwendige, selbstgebastelte Funktion zum Drucken von Charts.
Wandelt Sets (aus optischen Gründen) in Listen um und kann diese
eingerückt (mit Tabulator) darstellen.
"""
tabstring = '\t' * num_of_tabs
for row in chart:
print tabstring+"\t".join([str(list(element)) for element in row])
words = ["I", "shot", "an", "elephant", "in", "my", "pajamas"]
n = len(words)
grammar = nltk.parse_cfg("""
S -> NP VP
PP -> P NP
NP -> Det N | 'I' | NP PP
VP -> V NP | VP PP
Det -> 'an' | 'my'
N -> 'elephant' | 'pajamas'
V -> 'shot'
P -> 'in'
""")
# leere Chart bauen
chart = []
for i in range(n+1):
# Erzeuge eine leere Zeile
row = []
# Haenge n+1 leere Mengen (set()) an
for j in range(n+1):
row.append(set())
# Haenge die neue Zeile an die Chart an
chart.append(row)
grid = BlockGrid(n+1, n+1)
known_terminals = set()
# Terminalproduktionen
# Iteriere ueber alle Positionen des Eingabesatzes
for i in range(n):
# Iteriere ueber alle Regeln der Grammatik, die das Wort words[i] als rechte Seite haben
# z.B. words[4] = 'elephant' und N -> 'elephant'
print "productions for terminal '{}':".format(words[i])
for prod in grammar.productions(rhs=words[i]):
print prod
# Fuege in die Zelle fuer die Spanne von i bis i+1 die linke Regel (z.B. N) ein
print "\t{0} added to chart[{1}][{2}]\n".format(prod.lhs(), i, i+1)
grid[i, i+1] = colors['White']
grid.flash(display_time=1.0)
chart[i][i+1].add(prod.lhs())
known_terminals.add((i, i+1))
grid.show()
grid = BlockGrid(n+1, n+1)
seconds_per_step = 1.0
known_lhs = set()
# Iteriere ueber alle Spannen ab Laenge 2
for width in range(2, n+1):
# Iteriere ueber alle moeglichen Anfaenge einer Spanne
for i in range(0, n-width+1): # i + width <= n
# Iteriere ueber alle moeglichen Teilungspunkte dieser Spanne
for j in range(1, width): # 1 <= j <= width-1
# Jetzt wollen wir Nichtterminale aus 2 gegebenen Chartzellen kombinieren
nts1 = chart[i][i+j]
grid[i, i+j] = colors['Yellow'] # Nichtterminal 1: gelb
# j ist der Teilungspunkt: eine Spanne geht von i bis i+j, die andere von
# i+j bis i+width
nts2 = chart[i+j][i+width]
grid[i+j, i+width] = colors['Orange'] # Nichtterminal 2: orange
print ("\ntry to combine nonterminals from [{0}][{1}] ({2})"
" and [{3}][{4}] ({5})".format(i, i+j, list(nts1), i+j, i+width, list(nts2)))
# Iteriere nun ueber alle Nichtterminale der ersten Zelle
for nt1 in nts1:
# Bestimme die Kandidatenregeln, die ein Nichtterminal aus nts1 als
# erstes Element auf ihrer rechten Regelseite haben
# Beispiel: nts1 enthaelt NP => suche alle Regeln der Form X => NP Y,
# z.B. S -> NP VP
productions = grammar.productions(rhs=nt1)
if productions:
print "\tproductions, where NT '{0}' is 1st element of RHS: {1}".format(nt1, productions)
else:
print "\tNO productions where nonterminal '{}' is the 1st element of RHS!".format(nt1)
# Gehe nun diese Kandidatenregeln durch
for production in productions:
# Pruefe, ob das 2. Element der rechten Regelseite (production.rhs()[1]),
# (also im Beispiel oben VP) im anderen Kaestchen enthalten ist
if production.rhs()[1] in nts2:
# ok, fuege dann die linke Regelseite (also S) in das Zielkaestchen
# chart[i][i+width] ein. Dieses enthaelt alle Nichtterminale, die die
# Eingabe zwischen den Positionen i und i+width ableitet.
print ("\t\t2nd element of production RHS '{0}' is also in '{1}'"
"\n\t\tLHS will be added to [{2}][{3}]".format(production, list(nts2), i, i+width))
chart[i][i+width].add(production.lhs())
grid[i, i+width] = colors['Green']
known_lhs.add((i, i+width)) # wir merken uns schon gefundene LHS
else:
print "\t\t2nd element of production RHS '{0}' NOT in '{1}'!".format(production, list(nts2))
grid.flash(display_time=seconds_per_step) # Nichtterminale aufleuchten für X Sekunden
# Farben zuruecksetzen
for (row, column) in ((i, i+j), (i+j, i+width)):
if (row, column) in known_terminals:
grid[row, column] = colors['White'] # wenn schon ein Nichtterminal in diesem Kästchen gespeichert ist
elif (row, column) in known_lhs:
grid[row, column] = colors['Green'] # wenn schon eine RHS in diesem Kästchen gespeichert ist
else:
grid[row, column] = colors['Black']
grid.show()
print_chart(chart)
[] [NP] [] [] [S] [] [] [S] [] [] [V] [] [VP] [] [] [VP] [] [] [] [Det] [NP] [] [] [NP] [] [] [] [] [N] [] [] [] [] [] [] [] [] [P] [] [PP] [] [] [] [] [] [] [Det] [NP] [] [] [] [] [] [] [] [N] [] [] [] [] [] [] [] []