Code Coverage for nltk.draw.chart
Untested Functions
- demo()
- ChartComparer: __init__(), _apply_op(), _checkcompat(), _clear_out_chart(), _detatch_out(), _difference(), _init_bindings(), _init_buttons(), _init_chartviews(), _init_divider(), _init_menubar(), _intersection(), _select_left(), _select_right(), _swapcharts(), _union(), _update(), _update_chartviews(), destroy(), load_chart(), load_chart_dialog(), mainloop(), save_chart_dialog(), select_cell(), select_edge()
- ChartDemo: __init__(), _animate_strategy(), _apply_strategy(), _click_cv_edge(), _deselect_edge(), _display_rule(), _init_animation(), _init_bindings(), _init_buttons(), _init_chartview(), _init_fonts(), _init_menubar(), _init_parser(), _init_rulelabel(), _select_edge(), _select_matrix_edge(), _show_new_edge(), _stop_animation(), about(), apply_strategy(), bottom_up(), bottom_up_init(), bottom_up_strategy(), destroy(), earley_algorithm(), edit_grammar(), edit_sentence(), fundamental(), get_font_size(), help(), load_chart(), load_grammar(), mainloop(), reset(), resize(), save_chart(), save_grammar(), set_font_size(), set_grammar(), set_sentence(), top_down_expand(), top_down_init(), top_down_match(), top_down_strategy(), view_matrix(), view_results()
- ChartMatrixView: __init__(), _click_cell(), _fire_callbacks(), _init_list(), _init_matrix(), _init_numedges(), _init_quit(), activate(), add_callback(), deselect_cell(), destroy(), draw(), inactivate(), mark_edge(), markonly_edge(), pack(), remove_callback(), select_cell(), set_chart(), unmark_edge(), update(), view_edge()
- ChartResultsView: __init__(), _add(), _click(), _color(), clear(), destroy(), pack(), print_all(), print_selection(), set_chart(), set_grammar(), update()
- ChartView: __init__(), _add_edge(), _analyze(), _analyze_edge(), _color_edge(), _configure(), _draw_edge(), _draw_loclines(), _draw_sentence(), _draw_treecycle(), _draw_treetok(), _edge_conflict(), _fire_callbacks(), _grow(), _init_fonts(), _resize(), _sb_canvas(), add_callback(), cycle_tree(), draw(), draw_tree(), erase_tree(), get_font_size(), mark_edge(), markonly_edge(), page_down(), page_up(), remove_callback(), scroll_down(), scroll_up(), set_font_size(), unmark_edge(), update(), view_edge()
- EdgeList: _init_colortags(), _item_repr()
- EdgeRule: __init__(), __str__(), apply_iter()
- PseudoEarleyInitRule: __str__()
- PseudoEarleyRule: __str__(), apply_iter()
"""
A graphical tool for exploring chart parsing.
Chart parsing is a flexible parsing algorithm that uses a data
structure called a "chart" to record hypotheses about syntactic
constituents. Each hypothesis is represented by a single "edge" on
the chart. A set of "chart rules" determine when new edges can be
added to the chart. This set of rules controls the overall behavior
of the parser (e.g., whether it parses top-down or bottom-up).
The chart parsing tool demonstrates the process of parsing a single
sentence, with a given grammar and lexicon. Its display is divided
into three sections: the bottom section displays the chart; the middle
section displays the sentence; and the top section displays the
partial syntax tree corresponding to the selected edge. Buttons along
the bottom of the window are used to control the execution of the
algorithm.
The chart parsing tool allows for flexible control of the parsing
algorithm. At each step of the algorithm, you can select which rule
or strategy you wish to apply. This allows you to experiment with
mixing different strategies (e.g., top-down and bottom-up). You can
exercise fine-grained control over the algorithm by selecting which
edge you wish to apply a rule to.
"""
import pickle
from tkFileDialog import asksaveasfilename, askopenfilename
import Tkinter, tkFont, tkMessageBox
import math
import string
import os.path
from nltk.parse.chart import *
from nltk import tokenize, Tree, cfg
from nltk.draw import ShowText, EntryDialog, in_idle
from nltk.draw import MutableOptionMenu
from nltk.draw import ColorizedList, SymbolWidget, CanvasFrame
from nltk.draw.cfg import CFGEditor
from nltk.draw.tree import tree_to_treesegment, TreeSegmentWidget
class EdgeList(ColorizedList):
ARROW = SymbolWidget.SYMBOLS['rightarrow']
def _init_colortags(self, textwidget, options):
textwidget.tag_config('terminal', foreground='#006000')
textwidget.tag_config('arrow', font='symbol', underline='0')
textwidget.tag_config('dot', foreground = '#000000')
textwidget.tag_config('nonterminal', foreground='blue',
font=('helvetica', -12, 'bold'))
def _item_repr(self, item):
contents = []
contents.append(('%s\t' % item.lhs(), 'nonterminal'))
contents.append((self.ARROW, 'arrow'))
for i, elt in enumerate(item.rhs()):
if i == item.dot():
contents.append((' *', 'dot'))
if isinstance(elt, cfg.Nonterminal):
contents.append((' %s' % elt.symbol(), 'nonterminal'))
else:
contents.append((' %r' % elt, 'terminal'))
if item.is_complete():
contents.append((' *', 'dot'))
return contents
class ChartMatrixView(object):
"""
A view of a chart that displays the contents of the corresponding matrix.
"""
def __init__(self, parent, chart, toplevel=True, title='Chart Matrix',
show_numedges=False):
self._chart = chart
self._cells = []
self._marks = []
self._selected_cell = None
if toplevel:
self._root = Tkinter.Toplevel(parent)
self._root.title(title)
self._root.bind('<Control-q>', self.destroy)
self._init_quit(self._root)
else:
self._root = Tkinter.Frame(parent)
self._init_matrix(self._root)
self._init_list(self._root)
if show_numedges:
self._init_numedges(self._root)
else:
self._numedges_label = None
self._callbacks = {}
self._num_edges = 0
self.draw()
def _init_quit(self, root):
quit = Tkinter.Button(root, text='Quit', command=self.destroy)
quit.pack(side='bottom', expand=0, fill='none')
def _init_matrix(self, root):
cframe = Tkinter.Frame(root, border=2, relief='sunken')
cframe.pack(expand=0, fill='none', padx=1, pady=3, side='top')
self._canvas = Tkinter.Canvas(cframe, width=200, height=200,
background='white')
self._canvas.pack(expand=0, fill='none')
def _init_numedges(self, root):
self._numedges_label = Tkinter.Label(root, text='0 edges')
self._numedges_label.pack(expand=0, fill='none', side='top')
def _init_list(self, root):
self._list = EdgeList(root, [], width=20, height=5)
self._list.pack(side='top', expand=1, fill='both', pady=3)
def cb(edge, self=self): self._fire_callbacks('select', edge)
self._list.add_callback('select', cb)
self._list.focus()
def destroy(self, *e):
if self._root is None: return
try: self._root.destroy()
except: pass
self._root = None
def set_chart(self, chart):
if chart is not self._chart:
self._chart = chart
self._num_edges = 0
self.draw()
def update(self):
if self._root is None: return
N = len(self._cells)
cell_edges = [[0 for i in range(N)] for j in range(N)]
for edge in self._chart:
cell_edges[edge.start()][edge.end()] += 1
for i in range(N):
for j in range(i, N):
if cell_edges[i][j] == 0:
color = 'gray20'
else:
color = ('#00%02x%02x' %
(min(255, 50+128*cell_edges[i][j]/10),
max(0, 128-128*cell_edges[i][j]/10)))
cell_tag = self._cells[i][j]
self._canvas.itemconfig(cell_tag, fill=color)
if (i,j) == self._selected_cell:
self._canvas.itemconfig(cell_tag, outline='#00ffff',
width=3)
self._canvas.tag_raise(cell_tag)
else:
self._canvas.itemconfig(cell_tag, outline='black',
width=1)
edges = list(self._chart.select(span=self._selected_cell))
self._list.set(edges)
self._num_edges = self._chart.num_edges()
if self._numedges_label is not None:
self._numedges_label['text'] = '%d edges' % self._num_edges
def activate(self):
self._canvas.itemconfig('inactivebox', state='hidden')
self.update()
def inactivate(self):
self._canvas.itemconfig('inactivebox', state='normal')
self.update()
def add_callback(self, event, func):
self._callbacks.setdefault(event,{})[func] = 1
def remove_callback(self, event, func=None):
if func is None: del self._callbacks[event]
else:
try: del self._callbacks[event][func]
except: pass
def _fire_callbacks(self, event, *args):
if not self._callbacks.has_key(event): return
for cb_func in self._callbacks[event].keys(): cb_func(*args)
def select_cell(self, i, j):
if self._root is None: return
if ((i,j) == self._selected_cell and
self._chart.num_edges() == self._num_edges): return
self._selected_cell = (i,j)
self.update()
self._fire_callbacks('select_cell', i, j)
def deselect_cell(self):
if self._root is None: return
self._selected_cell = None
self._list.set([])
self.update()
def _click_cell(self, i, j):
if self._selected_cell == (i,j):
self.deselect_cell()
else:
self.select_cell(i, j)
def view_edge(self, edge):
self.select_cell(*edge.span())
self._list.view(edge)
def mark_edge(self, edge):
if self._root is None: return
self.select_cell(*edge.span())
self._list.mark(edge)
def unmark_edge(self, edge=None):
if self._root is None: return
self._list.unmark(edge)
def markonly_edge(self, edge):
if self._root is None: return
self.select_cell(*edge.span())
self._list.markonly(edge)
def draw(self):
if self._root is None: return
LEFT_MARGIN = BOT_MARGIN = 15
TOP_MARGIN = 5
c = self._canvas
c.delete('all')
N = self._chart.num_leaves()+1
dx = (int(c['width'])-LEFT_MARGIN)/N
dy = (int(c['height'])-TOP_MARGIN-BOT_MARGIN)/N
c.delete('all')
for i in range(N):
c.create_text(LEFT_MARGIN-2, i*dy+dy/2+TOP_MARGIN,
text=`i`, anchor='e')
c.create_text(i*dx+dx/2+LEFT_MARGIN, N*dy+TOP_MARGIN+1,
text=`i`, anchor='n')
c.create_line(LEFT_MARGIN, dy*(i+1)+TOP_MARGIN,
dx*N+LEFT_MARGIN, dy*(i+1)+TOP_MARGIN, dash='.')
c.create_line(dx*i+LEFT_MARGIN, TOP_MARGIN,
dx*i+LEFT_MARGIN, dy*N+TOP_MARGIN, dash='.')
c.create_rectangle(LEFT_MARGIN, TOP_MARGIN,
LEFT_MARGIN+dx*N, dy*N+TOP_MARGIN,
width=2)
self._cells = [[None for i in range(N)] for j in range(N)]
for i in range(N):
for j in range(i, N):
t = c.create_rectangle(j*dx+LEFT_MARGIN, i*dy+TOP_MARGIN,
(j+1)*dx+LEFT_MARGIN,
(i+1)*dy+TOP_MARGIN,
fill='gray20')
self._cells[i][j] = t
def cb(event, self=self, i=i, j=j): self._click_cell(i,j)
c.tag_bind(t, '<Button-1>', cb)
xmax, ymax = int(c['width']), int(c['height'])
t = c.create_rectangle(-100, -100, xmax+100, ymax+100,
fill='gray50', state='hidden',
tag='inactivebox')
c.tag_lower(t)
self.update()
def pack(self, *args, **kwargs):
self._root.pack(*args, **kwargs)
class ChartResultsView(object):
def __init__(self, parent, chart, grammar, toplevel=True):
self._chart = chart
self._grammar = grammar
self._trees = []
self._y = 10
self._treewidgets = []
self._selection = None
self._selectbox = None
if toplevel:
self._root = Tkinter.Toplevel(parent)
self._root.title('Chart Parsing Demo: Results')
self._root.bind('<Control-q>', self.destroy)
else:
self._root = Tkinter.Frame(parent)
if toplevel:
buttons = Tkinter.Frame(self._root)
buttons.pack(side='bottom', expand=0, fill='x')
Tkinter.Button(buttons, text='Quit',
command=self.destroy).pack(side='right')
Tkinter.Button(buttons, text='Print All',
command=self.print_all).pack(side='left')
Tkinter.Button(buttons, text='Print Selection',
command=self.print_selection).pack(side='left')
self._cframe = CanvasFrame(self._root, closeenough=20)
self._cframe.pack(side='top', expand=1, fill='both')
self.update()
def update(self, edge=None):
if self._root is None: return
if edge is not None:
if edge.lhs() != self._grammar.start(): return
if edge.span() != (0, self._chart.num_leaves()): return
for parse in self._chart.parses(self._grammar.start()):
if parse not in self._trees:
self._add(parse)
def _add(self, parse):
self._trees.append(parse)
c = self._cframe.canvas()
treewidget = tree_to_treesegment(c, parse)
self._treewidgets.append(treewidget)
self._cframe.add_widget(treewidget, 10, self._y)
treewidget.bind_click(self._click)
self._y = treewidget.bbox()[3] + 10
def _click(self, widget):
c = self._cframe.canvas()
if self._selection is not None:
c.delete(self._selectbox)
self._selection = widget
(x1, y1, x2, y2) = widget.bbox()
self._selectbox = c.create_rectangle(x1, y1, x2, y2,
width=2, outline='#088')
def _color(self, treewidget, color):
treewidget.node()['color'] = color
for child in treewidget.subtrees():
if isinstance(child, TreeSegmentWidget):
self._color(child, color)
else:
child['color'] = color
def print_all(self, *e):
if self._root is None: return
self._cframe.print_to_file()
def print_selection(self, *e):
if self._root is None: return
if self._selection is None:
tkMessageBox.showerror('Print Error', 'No tree selected')
else:
c = self._cframe.canvas()
for widget in self._treewidgets:
if widget is not self._selection:
self._cframe.destroy_widget(widget)
c.delete(self._selectbox)
(x1,y1,x2,y2) = self._selection.bbox()
self._selection.move(10-x1,10-y1)
c['scrollregion'] = '0 0 %s %s' % (x2-x1+20, y2-y1+20)
self._cframe.print_to_file()
self._treewidgets = [self._selection]
self.clear()
self.update()
def clear(self):
if self._root is None: return
for treewidget in self._treewidgets:
self._cframe.destroy_widget(treewidget)
self._trees = []
self._treewidgets = []
if self._selection is not None:
self._cframe.canvas().delete(self._selectbox)
self._selection = None
self._y = 10
def set_chart(self, chart):
self.clear()
self._chart = chart
self.update()
def set_grammar(self, grammar):
self.clear()
self._grammar = grammar
self.update()
def destroy(self, *e):
if self._root is None: return
try: self._root.destroy()
except: pass
self._root = None
def pack(self, *args, **kwargs):
self._root.pack(*args, **kwargs)
class ChartComparer(object):
"""
@ivar _root: The root window
@ivar _charts: A dictionary mapping names to charts. When
charts are loaded, they are added to this dictionary.
@ivar _left_chart: The left L{Chart}.
@ivar _left_name: The name C{_left_chart} (derived from filename)
@ivar _left_matrix: The L{ChartMatrixView} for C{_left_chart}
@ivar _left_selector: The drop-down C{MutableOptionsMenu} used
to select C{_left_chart}.
@ivar _right_chart: The right L{Chart}.
@ivar _right_name: The name C{_right_chart} (derived from filename)
@ivar _right_matrix: The L{ChartMatrixView} for C{_right_chart}
@ivar _right_selector: The drop-down C{MutableOptionsMenu} used
to select C{_right_chart}.
@ivar _out_chart: The out L{Chart}.
@ivar _out_name: The name C{_out_chart} (derived from filename)
@ivar _out_matrix: The L{ChartMatrixView} for C{_out_chart}
@ivar _out_label: The label for C{_out_chart}.
@ivar _op_label: A Label containing the most recent operation.
"""
_OPSYMBOL = {'-': '-',
'and': SymbolWidget.SYMBOLS['intersection'],
'or': SymbolWidget.SYMBOLS['union']}
def __init__(self, *chart_filenames):
faketok = [''] * 8
self._emptychart = Chart(faketok)
self._left_name = 'None'
self._right_name = 'None'
self._left_chart = self._emptychart
self._right_chart = self._emptychart
self._charts = {'None': self._emptychart}
self._out_chart = self._emptychart
self._operator = None
self._root = Tkinter.Tk()
self._root.title('Chart Comparison')
self._root.bind('<Control-q>', self.destroy)
self._root.bind('<Control-x>', self.destroy)
self._init_menubar(self._root)
self._init_chartviews(self._root)
self._init_divider(self._root)
self._init_buttons(self._root)
self._init_bindings(self._root)
for filename in chart_filenames:
self.load_chart(filename)
def destroy(self, *e):
if self._root is None: return
try: self._root.destroy()
except: pass
self._root = None
def mainloop(self, *args, **kwargs):
return
self._root.mainloop(*args, **kwargs)
def _init_menubar(self, root):
menubar = Tkinter.Menu(root)
filemenu = Tkinter.Menu(menubar, tearoff=0)
filemenu.add_command(label='Load Chart', accelerator='Ctrl-o',
underline=0, command=self.load_chart_dialog)
filemenu.add_command(label='Save Output', accelerator='Ctrl-s',
underline=0, command=self.save_chart_dialog)
filemenu.add_separator()
filemenu.add_command(label='Exit', underline=1,
command=self.destroy, accelerator='Ctrl-x')
menubar.add_cascade(label='File', underline=0, menu=filemenu)
opmenu = Tkinter.Menu(menubar, tearoff=0)
opmenu.add_command(label='Intersection',
command=self._intersection,
accelerator='+')
opmenu.add_command(label='Union',
command=self._union,
accelerator='*')
opmenu.add_command(label='Difference',
command=self._difference,
accelerator='-')
opmenu.add_separator()
opmenu.add_command(label='Swap Charts',
command=self._swapcharts)
menubar.add_cascade(label='Compare', underline=0, menu=opmenu)
self._root.config(menu=menubar)
def _init_divider(self, root):
divider = Tkinter.Frame(root, border=2, relief='sunken')
divider.pack(side='top', fill='x', ipady=2)
def _init_chartviews(self, root):
opfont=('symbol', -36)
eqfont=('helvetica', -36)
frame = Tkinter.Frame(root, background='#c0c0c0')
frame.pack(side='top', expand=1, fill='both')
cv1_frame = Tkinter.Frame(frame, border=3, relief='groove')
cv1_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both')
self._left_selector = MutableOptionMenu(
cv1_frame, self._charts.keys(), command=self._select_left)
self._left_selector.pack(side='top', pady=5, fill='x')
self._left_matrix = ChartMatrixView(cv1_frame, self._emptychart,
toplevel=False,
show_numedges=True)
self._left_matrix.pack(side='bottom', padx=5, pady=5,
expand=1, fill='both')
self._left_matrix.add_callback('select', self.select_edge)
self._left_matrix.add_callback('select_cell', self.select_cell)
self._left_matrix.inactivate()
self._op_label = Tkinter.Label(frame, text=' ', width=3,
background='#c0c0c0', font=opfont)
self._op_label.pack(side='left', padx=5, pady=5)
cv2_frame = Tkinter.Frame(frame, border=3, relief='groove')
cv2_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both')
self._right_selector = MutableOptionMenu(
cv2_frame, self._charts.keys(), command=self._select_right)
self._right_selector.pack(side='top', pady=5, fill='x')
self._right_matrix = ChartMatrixView(cv2_frame, self._emptychart,
toplevel=False,
show_numedges=True)
self._right_matrix.pack(side='bottom', padx=5, pady=5,
expand=1, fill='both')
self._right_matrix.add_callback('select', self.select_edge)
self._right_matrix.add_callback('select_cell', self.select_cell)
self._right_matrix.inactivate()
Tkinter.Label(frame, text='=', width=3, background='#c0c0c0',
font=eqfont).pack(side='left', padx=5, pady=5)
out_frame = Tkinter.Frame(frame, border=3, relief='groove')
out_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both')
self._out_label = Tkinter.Label(out_frame, text='Output')
self._out_label.pack(side='top', pady=9)
self._out_matrix = ChartMatrixView(out_frame, self._emptychart,
toplevel=False,
show_numedges=True)
self._out_matrix.pack(side='bottom', padx=5, pady=5,
expand=1, fill='both')
self._out_matrix.add_callback('select', self.select_edge)
self._out_matrix.add_callback('select_cell', self.select_cell)
self._out_matrix.inactivate()
def _init_buttons(self, root):
buttons = Tkinter.Frame(root)
buttons.pack(side='bottom', pady=5, fill='x', expand=0)
Tkinter.Button(buttons, text='Intersection',
command=self._intersection).pack(side='left')
Tkinter.Button(buttons, text='Union',
command=self._union).pack(side='left')
Tkinter.Button(buttons, text='Difference',
command=self._difference).pack(side='left')
Tkinter.Frame(buttons, width=20).pack(side='left')
Tkinter.Button(buttons, text='Swap Charts',
command=self._swapcharts).pack(side='left')
Tkinter.Button(buttons, text='Detatch Output',
command=self._detatch_out).pack(side='right')
def _init_bindings(self, root):
root.bind('<Control-o>', self.load_chart_dialog)
def _select_left(self, name):
self._left_name = name
self._left_chart = self._charts[name]
self._left_matrix.set_chart(self._left_chart)
if name == 'None': self._left_matrix.inactivate()
self._apply_op()
def _select_right(self, name):
self._right_name = name
self._right_chart = self._charts[name]
self._right_matrix.set_chart(self._right_chart)
if name == 'None': self._right_matrix.inactivate()
self._apply_op()
def _apply_op(self):
if self._operator == '-': self._difference()
elif self._operator == 'or': self._union()
elif self._operator == 'and': self._intersection()
CHART_FILE_TYPES = [('Pickle file', '.pickle'),
('All files', '*')]
def save_chart_dialog(self, *args):
filename = asksaveasfilename(filetypes=self.CHART_FILE_TYPES,
defaultextension='.pickle')
if not filename: return
try: pickle.dump((self._out_chart), open(filename, 'w'))
except Exception, e:
tkMessageBox.showerror('Error Saving Chart',
'Unable to open file: %r\n%s' %
(filename, e))
def load_chart_dialog(self, *args):
filename = askopenfilename(filetypes=self.CHART_FILE_TYPES,
defaultextension='.pickle')
if not filename: return
try: self.load_chart(filename)
except Exception, e:
tkMessageBox.showerror('Error Loading Chart',
'Unable to open file: %r\n%s' %
(filename, e))
def load_chart(self, filename):
chart = pickle.load(open(filename, 'r'))
name = os.path.basename(filename)
if name.endswith('.pickle'): name = name[:-7]
if name.endswith('.chart'): name = name[:-6]
self._charts[name] = chart
self._left_selector.add(name)
self._right_selector.add(name)
if self._left_chart is self._emptychart:
self._left_selector.set(name)
elif self._right_chart is self._emptychart:
self._right_selector.set(name)
def _update_chartviews(self):
self._left_matrix.update()
self._right_matrix.update()
self._out_matrix.update()
def select_edge(self, edge):
if edge in self._left_chart:
self._left_matrix.markonly_edge(edge)
else:
self._left_matrix.unmark_edge()
if edge in self._right_chart:
self._right_matrix.markonly_edge(edge)
else:
self._right_matrix.unmark_edge()
if edge in self._out_chart:
self._out_matrix.markonly_edge(edge)
else:
self._out_matrix.unmark_edge()
def select_cell(self, i, j):
self._left_matrix.select_cell(i, j)
self._right_matrix.select_cell(i, j)
self._out_matrix.select_cell(i, j)
def _difference(self):
if not self._checkcompat(): return
out_chart = Chart(self._left_chart.tokens())
for edge in self._left_chart:
if edge not in self._right_chart:
out_chart.insert(edge, [])
self._update('-', out_chart)
def _intersection(self):
if not self._checkcompat(): return
out_chart = Chart(self._left_chart.tokens())
for edge in self._left_chart:
if edge in self._right_chart:
out_chart.insert(edge, [])
self._update('and', out_chart)
def _union(self):
if not self._checkcompat(): return
out_chart = Chart(self._left_chart.tokens())
for edge in self._left_chart:
out_chart.insert(edge, [])
for edge in self._right_chart:
out_chart.insert(edge, [])
self._update('or', out_chart)
def _swapcharts(self):
left, right = self._left_name, self._right_name
self._left_selector.set(right)
self._right_selector.set(left)
def _checkcompat(self):
if (self._left_chart.tokens() != self._right_chart.tokens() or
self._left_chart.property_names() !=
self._right_chart.property_names() or
self._left_chart == self._emptychart or
self._right_chart == self._emptychart):
self._out_chart = self._emptychart
self._out_matrix.set_chart(self._out_chart)
self._out_matrix.inactivate()
self._out_label['text'] = 'Output'
return False
else:
return True
def _update(self, operator, out_chart):
self._operator = operator
self._op_label['text'] = self._OPSYMBOL[operator]
self._out_chart = out_chart
self._out_matrix.set_chart(out_chart)
self._out_label['text'] = '%s %s %s' % (self._left_name,
self._operator,
self._right_name)
def _clear_out_chart(self):
self._out_chart = self._emptychart
self._out_matrix.set_chart(self._out_chart)
self._op_label['text'] = ' '
self._out_matrix.inactivate()
def _detatch_out(self):
ChartMatrixView(self._root, self._out_chart,
title=self._out_label['text'])
class ChartView(object):
"""
A component for viewing charts. This is used by C{ChartDemo} to
allow students to interactively experiment with various chart
parsing techniques. It is also used by C{Chart.draw()}.
@ivar _chart: The chart that we are giving a view of. This chart
may be modified; after it is modified, you should call
C{update}.
@ivar _sentence: The list of tokens that the chart spans.
@ivar _root: The root window.
@ivar _chart_canvas: The canvas we're using to display the chart
itself.
@ivar _tree_canvas: The canvas we're using to display the tree
that each edge spans. May be None, if we're not displaying
trees.
@ivar _sentence_canvas: The canvas we're using to display the sentence
text. May be None, if we're not displaying the sentence text.
@ivar _edgetags: A dictionary mapping from edges to the tags of
the canvas elements (lines, etc) used to display that edge.
The values of this dictionary have the form
C{(linetag, rhstag1, dottag, rhstag2, lhstag)}.
@ivar _treetags: A list of all the tags that make up the tree;
used to erase the tree (without erasing the loclines).
@ivar _chart_height: The height of the chart canvas.
@ivar _sentence_height: The height of the sentence canvas.
@ivar _tree_height: The height of the tree
@ivar _text_height: The height of a text string (in the normal
font).
@ivar _edgelevels: A list of edges at each level of the chart (the
top level is the 0th element). This list is used to remember
where edges should be drawn; and to make sure that no edges
are overlapping on the chart view.
@ivar _unitsize: Pixel size of one unit (from the location). This
is determined by the span of the chart's location, and the
width of the chart display canvas.
@ivar _fontsize: The current font size
@ivar _marks: A dictionary from edges to marks. Marks are
strings, specifying colors (e.g. 'green').
"""
_LEAF_SPACING = 10
_MARGIN = 10
_TREE_LEVEL_SIZE = 12
_CHART_LEVEL_SIZE = 40
def __init__(self, chart, root=None, **kw):
"""
Construct a new C{Chart} display.
"""
draw_tree = kw.get('draw_tree', 0)
draw_sentence = kw.get('draw_sentence', 1)
self._fontsize = kw.get('fontsize', -12)
self._chart = chart
self._callbacks = {}
self._edgelevels = []
self._edgetags = {}
self._marks = {}
self._treetoks = []
self._treetoks_edge = None
self._treetoks_index = 0
self._tree_tags = []
self._compact = 0
if root is None:
top = Tkinter.Tk()
top.title('Chart View')
def destroy1(e, top=top): top.destroy()
def destroy2(top=top): top.destroy()
top.bind('q', destroy1)
b = Tkinter.Button(top, text='Done', command=destroy2)
b.pack(side='bottom')
self._root = top
else:
self._root = root
self._init_fonts(root)
(self._chart_sb, self._chart_canvas) = self._sb_canvas(self._root)
self._chart_canvas['height'] = 300
self._chart_canvas['closeenough'] = 15
if draw_sentence:
cframe = Tkinter.Frame(self._root, relief='sunk', border=2)
cframe.pack(fill='both', side='bottom')
self._sentence_canvas = Tkinter.Canvas(cframe, height=50)
self._sentence_canvas['background'] = '#e0e0e0'
self._sentence_canvas.pack(fill='both')
else:
self._sentence_canvas = None
if draw_tree:
(sb, canvas) = self._sb_canvas(self._root, 'n', 'x')
(self._tree_sb, self._tree_canvas) = (sb, canvas)
self._tree_canvas['height'] = 200
else:
self._tree_canvas = None
self._analyze()
self.draw()
self._resize()
self._grow()
self._chart_canvas.bind('<Configure>', self._configure)
def _init_fonts(self, root):
self._boldfont = tkFont.Font(family='helvetica', weight='bold',
size=self._fontsize)
self._font = tkFont.Font(family='helvetica',
size=self._fontsize)
self._sysfont = tkFont.Font(font=Tkinter.Button()["font"])
root.option_add("*Font", self._sysfont)
def _sb_canvas(self, root, expand='y',
fill='both', side='bottom'):
"""
Helper for __init__: construct a canvas with a scrollbar.
"""
cframe =Tkinter.Frame(root, relief='sunk', border=2)
cframe.pack(fill=fill, expand=expand, side=side)
canvas = Tkinter.Canvas(cframe, background='#e0e0e0')
sb = Tkinter.Scrollbar(cframe, orient='vertical')
sb.pack(side='right', fill='y')
canvas.pack(side='left', fill=fill, expand='yes')
sb['command']= canvas.yview
canvas['yscrollcommand'] = sb.set
return (sb, canvas)
def scroll_up(self, *e):
self._chart_canvas.yview('scroll', -1, 'units')
def scroll_down(self, *e):
self._chart_canvas.yview('scroll', 1, 'units')
def page_up(self, *e):
self._chart_canvas.yview('scroll', -1, 'pages')
def page_down(self, *e):
self._chart_canvas.yview('scroll', 1, 'pages')
def _grow(self):
"""
Grow the window, if necessary
"""
N = self._chart.num_leaves()
width = max(int(self._chart_canvas['width']),
N * self._unitsize + ChartView._MARGIN * 2 )
self._chart_canvas.configure(width=width)
self._chart_canvas.configure(height=self._chart_canvas['height'])
self._unitsize = (width - 2*ChartView._MARGIN) / N
if self._sentence_canvas is not None:
self._sentence_canvas['height'] = self._sentence_height
def set_font_size(self, size):
self._font.configure(size=-abs(size))
self._boldfont.configure(size=-abs(size))
self._sysfont.configure(size=-abs(size))
self._analyze()
self._grow()
self.draw()
def get_font_size(self):
return abs(self._fontsize)
def _configure(self, e):
"""
The configure callback. This is called whenever the window is
resized. It is also called when the window is first mapped.
It figures out the unit size, and redraws the contents of each
canvas.
"""
N = self._chart.num_leaves()
self._unitsize = (e.width - 2*ChartView._MARGIN) / N
self.draw()
def update(self, chart=None):
"""
Draw any edges that have not been drawn. This is typically
called when a after modifies the canvas that a CanvasView is
displaying. C{update} will cause any edges that have been
added to the chart to be drawn.
If update is given a C{chart} argument, then it will replace
the current chart with the given chart.
"""
if chart is not None:
self._chart = chart
self._edgelevels = []
self._marks = {}
self._analyze()
self._grow()
self.draw()
self.erase_tree()
self._resize()
else:
for edge in self._chart:
if not self._edgetags.has_key(edge):
self._add_edge(edge)
self._resize()
def _edge_conflict(self, edge, lvl):
"""
Return 1 if the given edge overlaps with any edge on the given
level. This is used by _add_edge to figure out what level a
new edge should be added to.
"""
(s1, e1) = edge.span()
for otheredge in self._edgelevels[lvl]:
(s2, e2) = otheredge.span()
if (s1 <= s2 < e1) or (s2 <= s1 < e2) or (s1==s2==e1==e2):
return 1
return 0
def _analyze_edge(self, edge):
"""
Given a new edge, recalculate:
- _text_height
- _unitsize (if the edge text is too big for the current
_unitsize, then increase _unitsize)
"""
c = self._chart_canvas
if isinstance(edge, TreeEdge):
lhs = edge.lhs()
rhselts = []
for elt in edge.rhs():
if isinstance(elt, cfg.Nonterminal):
rhselts.append(str(elt.symbol()))
else:
rhselts.append(repr(elt))
rhs = string.join(rhselts)
else:
lhs = edge.lhs()
rhs = ''
for s in (lhs, rhs):
tag = c.create_text(0,0, text=s,
font=self._boldfont,
anchor='nw', justify='left')
bbox = c.bbox(tag)
c.delete(tag)
width = bbox[2]
edgelen = max(edge.length(), 1)
self._unitsize = max(self._unitsize, width/edgelen)
self._text_height = max(self._text_height, bbox[3] - bbox[1])
def _add_edge(self, edge, minlvl=0):
"""
Add a single edge to the ChartView:
- Call analyze_edge to recalculate display parameters
- Find an available level
- Call _draw_edge
"""
if self._edgetags.has_key(edge): return
self._analyze_edge(edge)
self._grow()
if not self._compact:
self._edgelevels.append([edge])
lvl = len(self._edgelevels)-1
self._draw_edge(edge, lvl)
self._resize()
return
lvl = 0
while 1:
while lvl >= len(self._edgelevels):
self._edgelevels.append([])
self._resize()
if lvl>=minlvl and not self._edge_conflict(edge, lvl):
self._edgelevels[lvl].append(edge)
break
lvl += 1
self._draw_edge(edge, lvl)
def view_edge(self, edge):
level = None
for i in range(len(self._edgelevels)):
if edge in self._edgelevels[i]:
level = i
break
if level == None: return
y = (level+1) * self._chart_level_size
dy = self._text_height + 10
self._chart_canvas.yview('moveto', 1.0)
if self._chart_height != 0:
self._chart_canvas.yview('moveto',
float(y-dy)/self._chart_height)
def _draw_edge(self, edge, lvl):
"""
Draw a single edge on the ChartView.
"""
c = self._chart_canvas
x1 = (edge.start() * self._unitsize + ChartView._MARGIN)
x2 = (edge.end() * self._unitsize + ChartView._MARGIN)
if x2 == x1: x2 += max(4, self._unitsize/5)
y = (lvl+1) * self._chart_level_size
linetag = c.create_line(x1, y, x2, y, arrow='last', width=3)
if isinstance(edge, TreeEdge):
rhs = []
for elt in edge.rhs():
if isinstance(elt, cfg.Nonterminal):
rhs.append(str(elt.symbol()))
else:
rhs.append(repr(elt))
pos = edge.dot()
else:
rhs = []
pos = 0
rhs1 = string.join(rhs[:pos])
rhs2 = string.join(rhs[pos:])
rhstag1 = c.create_text(x1+3, y, text=rhs1,
font=self._font,
anchor='nw')
dotx = c.bbox(rhstag1)[2] + 6
doty = (c.bbox(rhstag1)[1]+c.bbox(rhstag1)[3])/2
dottag = c.create_oval(dotx-2, doty-2, dotx+2, doty+2)
rhstag2 = c.create_text(dotx+6, y, text=rhs2,
font=self._font,
anchor='nw')
lhstag = c.create_text((x1+x2)/2, y, text=str(edge.lhs()),
anchor='s',
font=self._boldfont)
self._edgetags[edge] = (linetag, rhstag1,
dottag, rhstag2, lhstag)
def cb(event, self=self, edge=edge):
self._fire_callbacks('select', edge)
c.tag_bind(rhstag1, '<Button-1>', cb)
c.tag_bind(rhstag2, '<Button-1>', cb)
c.tag_bind(linetag, '<Button-1>', cb)
c.tag_bind(dottag, '<Button-1>', cb)
c.tag_bind(lhstag, '<Button-1>', cb)
self._color_edge(edge)
def _color_edge(self, edge, linecolor=None, textcolor=None):
"""
Color in an edge with the given colors.
If no colors are specified, use intelligent defaults
(dependant on selection, etc.)
"""
if not self._edgetags.has_key(edge): return
c = self._chart_canvas
if linecolor is not None and textcolor is not None:
if self._marks.has_key(edge):
linecolor = self._marks[edge]
tags = self._edgetags[edge]
c.itemconfig(tags[0], fill=linecolor)
c.itemconfig(tags[1], fill=textcolor)
c.itemconfig(tags[2], fill=textcolor,
outline=textcolor)
c.itemconfig(tags[3], fill=textcolor)
c.itemconfig(tags[4], fill=textcolor)
return
else:
N = self._chart.num_leaves()
if self._marks.has_key(edge):
self._color_edge(self._marks[edge])
if (edge.is_complete() and edge.span() == (0, N)):
self._color_edge(edge, '#084', '#042')
elif isinstance(edge, LeafEdge):
self._color_edge(edge, '#48c', '#246')
else:
self._color_edge(edge, '#00f', '#008')
def mark_edge(self, edge, mark='#0df'):
"""
Mark an edge
"""
self._marks[edge] = mark
self._color_edge(edge)
def unmark_edge(self, edge=None):
"""
Unmark an edge (or all edges)
"""
if edge == None:
old_marked_edges = self._marks.keys()
self._marks = {}
for edge in old_marked_edges:
self._color_edge(edge)
else:
del self._marks[edge]
self._color_edge(edge)
def markonly_edge(self, edge, mark='#0df'):
self.unmark_edge()
self.mark_edge(edge, mark)
def _analyze(self):
"""
Analyze the sentence string, to figure out how big a unit needs
to be, How big the tree should be, etc.
"""
unitsize = 70
text_height = 0
c = self._chart_canvas
for leaf in self._chart.leaves():
tag = c.create_text(0,0, text=repr(leaf),
font=self._font,
anchor='nw', justify='left')
bbox = c.bbox(tag)
c.delete(tag)
width = bbox[2] + ChartView._LEAF_SPACING
unitsize = max(width, unitsize)
text_height = max(text_height, bbox[3] - bbox[1])
self._unitsize = unitsize
self._text_height = text_height
self._sentence_height = (self._text_height +
2*ChartView._MARGIN)
for edge in self._chart.edges():
self._analyze_edge(edge)
self._chart_level_size = self._text_height * 2.5
self._tree_height = (3 * (ChartView._TREE_LEVEL_SIZE +
self._text_height))
self._resize()
def _resize(self):
"""
Update the scroll-regions for each canvas. This ensures that
everything is within a scroll-region, so the user can use the
scrollbars to view the entire display. This does I{not}
resize the window.
"""
c = self._chart_canvas
width = ( self._chart.num_leaves() * self._unitsize +
ChartView._MARGIN * 2 )
levels = len(self._edgelevels)
self._chart_height = (levels+2)*self._chart_level_size
c['scrollregion']=(0,0,width,self._chart_height)
if self._tree_canvas:
self._tree_canvas['scrollregion'] = (0, 0, width,
self._tree_height)
def _draw_loclines(self):
"""
Draw location lines. These are vertical gridlines used to
show where each location unit is.
"""
BOTTOM = 50000
c1 = self._tree_canvas
c2 = self._sentence_canvas
c3 = self._chart_canvas
margin = ChartView._MARGIN
self._loclines = []
for i in range(0, self._chart.num_leaves()+1):
x = i*self._unitsize + margin
if c1:
t1=c1.create_line(x, 0, x, BOTTOM)
c1.tag_lower(t1)
if c2:
t2=c2.create_line(x, 0, x, self._sentence_height)
c2.tag_lower(t2)
t3=c3.create_line(x, 0, x, BOTTOM)
c3.tag_lower(t3)
t4=c3.create_text(x+2, 0, text=`i`, anchor='nw',
font=self._font)
c3.tag_lower(t4)
if i % 2 == 0:
if c1: c1.itemconfig(t1, fill='gray60')
if c2: c2.itemconfig(t2, fill='gray60')
c3.itemconfig(t3, fill='gray60')
else:
if c1: c1.itemconfig(t1, fill='gray80')
if c2: c2.itemconfig(t2, fill='gray80')
c3.itemconfig(t3, fill='gray80')
def _draw_sentence(self):
"""Draw the sentence string."""
if self._chart.num_leaves() == 0: return
c = self._sentence_canvas
margin = ChartView._MARGIN
y = ChartView._MARGIN
for i, leaf in enumerate(self._chart.leaves()):
x1 = i * self._unitsize + margin
x2 = x1 + self._unitsize
x = (x1+x2)/2
tag = c.create_text(x, y, text=repr(leaf),
font=self._font,
anchor='n', justify='left')
bbox = c.bbox(tag)
rt=c.create_rectangle(x1+2, bbox[1]-(ChartView._LEAF_SPACING/2),
x2-2, bbox[3]+(ChartView._LEAF_SPACING/2),
fill='#f0f0f0', outline='#f0f0f0')
c.tag_lower(rt)
def erase_tree(self):
for tag in self._tree_tags: self._tree_canvas.delete(tag)
self._treetoks = []
self._treetoks_edge = None
self._treetoks_index = 0
def draw_tree(self, edge=None):
if edge is None and self._treetoks_edge is None: return
if edge is None: edge = self._treetoks_edge
if self._treetoks_edge != edge:
self._treetoks = [t for t in self._chart.trees(edge)
if isinstance(t, Tree)]
self._treetoks_edge = edge
self._treetoks_index = 0
if len(self._treetoks) == 0: return
for tag in self._tree_tags: self._tree_canvas.delete(tag)
tree = self._treetoks[self._treetoks_index]
self._draw_treetok(tree, edge.start())
self._draw_treecycle()
w = self._chart.num_leaves()*self._unitsize+2*ChartView._MARGIN
h = tree.height() * (ChartView._TREE_LEVEL_SIZE+self._text_height)
self._tree_canvas['scrollregion'] = (0, 0, w, h)
def cycle_tree(self):
self._treetoks_index = (self._treetoks_index+1)%len(self._treetoks)
self.draw_tree(self._treetoks_edge)
def _draw_treecycle(self):
if len(self._treetoks) <= 1: return
label = '%d Trees' % len(self._treetoks)
c = self._tree_canvas
margin = ChartView._MARGIN
right = self._chart.num_leaves()*self._unitsize+margin-2
tag = c.create_text(right, 2, anchor='ne', text=label,
font=self._boldfont)
self._tree_tags.append(tag)
_, _, _, y = c.bbox(tag)
for i in range(len(self._treetoks)):
x = right - 20*(len(self._treetoks)-i-1)
if i == self._treetoks_index: fill = '#084'
else: fill = '#fff'
tag = c.create_polygon(x, y+10, x-5, y, x-10, y+10,
fill=fill, outline='black')
self._tree_tags.append(tag)
def cb(event, self=self, i=i):
self._treetoks_index = i
self.draw_tree()
c.tag_bind(tag, '<Button-1>', cb)
def _draw_treetok(self, treetok, index, depth=0):
"""
@param index: The index of the first leaf in the tree.
@return: The index of the first leaf after the tree.
"""
c = self._tree_canvas
margin = ChartView._MARGIN
child_xs = []
for child in treetok:
if isinstance(child, Tree):
child_x, index = self._draw_treetok(child, index, depth+1)
child_xs.append(child_x)
else:
child_xs.append((2*index+1)*self._unitsize/2 + margin)
index += 1
if child_xs:
nodex = sum(child_xs)/len(child_xs)
else:
nodex = (2*index+1)*self._unitsize/2 + margin
index += 1
nodey = depth * (ChartView._TREE_LEVEL_SIZE + self._text_height)
tag = c.create_text(nodex, nodey, anchor='n', justify='center',
text=str(treetok.node), fill='#042',
font=self._boldfont)
self._tree_tags.append(tag)
childy = nodey + ChartView._TREE_LEVEL_SIZE + self._text_height
for childx, child in zip(child_xs, treetok):
if isinstance(child, Tree) and child:
tag = c.create_line(nodex, nodey + self._text_height,
childx, childy, width=2, fill='#084')
self._tree_tags.append(tag)
if isinstance(child, Tree) and not child:
tag = c.create_line(nodex, nodey + self._text_height,
childx, childy, width=2,
fill='#048', dash='2 3')
self._tree_tags.append(tag)
if not isinstance(child, Tree):
tag = c.create_line(nodex, nodey + self._text_height,
childx, 10000, width=2, fill='#084')
self._tree_tags.append(tag)
return nodex, index
def draw(self):
"""
Draw everything (from scratch).
"""
if self._tree_canvas:
self._tree_canvas.delete('all')
self.draw_tree()
if self._sentence_canvas:
self._sentence_canvas.delete('all')
self._draw_sentence()
self._chart_canvas.delete('all')
self._edgetags = {}
for lvl in range(len(self._edgelevels)):
for edge in self._edgelevels[lvl]:
self._draw_edge(edge, lvl)
for edge in self._chart:
self._add_edge(edge)
self._draw_loclines()
def add_callback(self, event, func):
self._callbacks.setdefault(event,{})[func] = 1
def remove_callback(self, event, func=None):
if func is None: del self._callbacks[event]
else:
try: del self._callbacks[event][func]
except: pass
def _fire_callbacks(self, event, *args):
if not self._callbacks.has_key(event): return
for cb_func in self._callbacks[event].keys(): cb_func(*args)
class PseudoEarleyRule(AbstractChartRule):
NUM_EDGES = 1
_completer = CompleterRule()
_scanner = TopDownMatchRule()
_predictor = PredictorRule()
def __init__(self):
self._most_recent_rule = None
def apply_iter(self, chart, grammar, edge):
for e in self._predictor.apply_iter(chart, grammar, edge):
self._most_recent_rule = self._predictor
yield e
for e in self._scanner.apply_iter(chart, grammar, edge):
self._most_recent_rule = self._scanner
yield e
for e in self._completer.apply_iter(chart, grammar, edge):
self._most_recent_rule = self._completer
yield e
def __str__(self):
if self._most_recent_rule is self._completer:
return 'Completer Rule (aka Fundamental Rule)'
elif self._most_recent_rule is self._scanner:
return 'Scanner Rule (aka Top Down Match Rule)'
elif self._most_recent_rule is self._predictor:
return 'Predictor Rule (aka Top Down Expand Rule)'
else:
return 'Pseudo Earley Rule'
class PseudoEarleyInitRule(TopDownInitRule):
def __str__(self):
return 'Predictor Rule (aka Top Down Expand Rule)'
class EdgeRule(object):
"""
To create an edge rule, make an empty base class that uses
EdgeRule as the first base class, and the basic rule as the
second base class. (Order matters!)
"""
def __init__(self, edge):
super = self.__class__.__bases__[1]
self._edge = edge
self.NUM_EDGES = super.NUM_EDGES-1
def apply_iter(self, chart, grammar, *edges):
super = self.__class__.__bases__[1]
edges += (self._edge,)
for e in super.apply_iter(self, chart, grammar, *edges): yield e
def __str__(self):
super = self.__class__.__bases__[1]
return super.__str__(self)
class TopDownExpandEdgeRule(EdgeRule, TopDownExpandRule): pass
class TopDownMatchEdgeRule(EdgeRule, TopDownMatchRule): pass
class BottomUpEdgeRule(EdgeRule, BottomUpPredictRule): pass
class BottomUpInitEdgeRule(EdgeRule, BottomUpInitRule): pass
class FundamentalEdgeRule(EdgeRule, SingleEdgeFundamentalRule): pass
class PseudoEarleyEdgeRule(EdgeRule, PseudoEarleyRule): pass
class ChartDemo(object):
def __init__(self, grammar, tokens, title='Chart Parsing Demo'):
self._init_parser(grammar, tokens)
self._root = None
try:
self._root = Tkinter.Tk()
self._root.title(title)
self._root.bind('<Control-q>', self.destroy)
frame3 = Tkinter.Frame(self._root)
frame2 = Tkinter.Frame(self._root)
frame1 = Tkinter.Frame(self._root)
frame3.pack(side='bottom', fill='none')
frame2.pack(side='bottom', fill='x')
frame1.pack(side='bottom', fill='both', expand=1)
self._init_fonts(self._root)
self._init_animation()
self._init_chartview(frame1)
self._init_rulelabel(frame2)
self._init_buttons(frame3)
self._init_menubar()
self._matrix = None
self._results = None
self._init_bindings()
except:
print 'Error creating Tree View'
self.destroy()
raise
def destroy(self, *args):
if self._root is None: return
self._root.destroy()
self._root = None
def mainloop(self, *args, **kwargs):
"""
Enter the Tkinter mainloop. This function must be called if
this demo is created from a non-interactive program (e.g.
from a secript); otherwise, the demo will close as soon as
the script completes.
"""
if in_idle(): return
self._root.mainloop(*args, **kwargs)
def _init_parser(self, grammar, tokens):
self._grammar = grammar
self._tokens = tokens
self._cp = SteppingChartParser(self._grammar)
self._cp.initialize(self._tokens)
self._chart = self._cp.chart()
self._cpstep = self._cp.step()
self._selection = None
def _init_fonts(self, root):
self._sysfont = tkFont.Font(font=Tkinter.Button()["font"])
root.option_add("*Font", self._sysfont)
self._size = Tkinter.IntVar(root)
self._size.set(self._sysfont.cget('size'))
self._boldfont = tkFont.Font(family='helvetica', weight='bold',
size=self._size.get())
self._font = tkFont.Font(family='helvetica',
size=self._size.get())
def _init_animation(self):
self._step = Tkinter.IntVar(self._root)
self._step.set(1)
self._animate = Tkinter.IntVar(self._root)
self._animate.set(3)
self._animating = 0
def _init_chartview(self, parent):
self._cv = ChartView(self._chart, parent,
draw_tree=1, draw_sentence=1)
self._cv.add_callback('select', self._click_cv_edge)
def _init_rulelabel(self, parent):
ruletxt = 'Last edge generated by:'
self._rulelabel1 = Tkinter.Label(parent,text=ruletxt,
font=self._boldfont)
self._rulelabel2 = Tkinter.Label(parent, width=40,
relief='groove', anchor='w',
font=self._boldfont)
self._rulelabel1.pack(side='left')
self._rulelabel2.pack(side='left')
step = Tkinter.Checkbutton(parent, variable=self._step,
text='Step')
step.pack(side='right')
def _init_buttons(self, parent):
frame1 = Tkinter.Frame(parent)
frame2 = Tkinter.Frame(parent)
frame1.pack(side='bottom', fill='x')
frame2.pack(side='top', fill='none')
Tkinter.Button(frame1, text='Reset\nParser',
background='#90c0d0', foreground='black',
command=self.reset).pack(side='right')
Tkinter.Button(frame1, text='Top Down\nStrategy',
background='#90c0d0', foreground='black',
command=self.top_down_strategy).pack(side='left')
Tkinter.Button(frame1, text='Bottom Up\nStrategy',
background='#90c0d0', foreground='black',
command=self.bottom_up_strategy).pack(side='left')
Tkinter.Button(frame1, text='Earley\nAlgorithm',
background='#90c0d0', foreground='black',
command=self.earley_algorithm).pack(side='left')
Tkinter.Button(frame2, text='Top Down Init\nRule',
background='#90f090', foreground='black',
command=self.top_down_init).pack(side='left')
Tkinter.Button(frame2, text='Top Down Expand\nRule',
background='#90f090', foreground='black',
command=self.top_down_expand).pack(side='left')
Tkinter.Button(frame2, text='Top Down Match\nRule',
background='#90f090', foreground='black',
command=self.top_down_match).pack(side='left')
Tkinter.Frame(frame2, width=20).pack(side='left')
Tkinter.Button(frame2, text='Bottom Up Init\nRule',
background='#90f090', foreground='black',
command=self.bottom_up_init).pack(side='left')
Tkinter.Button(frame2, text='Bottom Up Predict\nRule',
background='#90f090', foreground='black',
command=self.bottom_up).pack(side='left')
Tkinter.Frame(frame2, width=20).pack(side='left')
Tkinter.Button(frame2, text='Fundamental\nRule',
background='#90f090', foreground='black',
command=self.fundamental).pack(side='left')
def _init_bindings(self):
self._root.bind('<Up>', self._cv.scroll_up)
self._root.bind('<Down>', self._cv.scroll_down)
self._root.bind('<Prior>', self._cv.page_up)
self._root.bind('<Next>', self._cv.page_down)
self._root.bind('<Control-q>', self.destroy)
self._root.bind('<Control-x>', self.destroy)
self._root.bind('<F1>', self.help)
self._root.bind('<Control-s>', self.save_chart)
self._root.bind('<Control-o>', self.load_chart)
self._root.bind('<Control-r>', self.reset)
self._root.bind('t', self.top_down_strategy)
self._root.bind('b', self.bottom_up_strategy)
self._root.bind('e', self.earley_algorithm)
self._root.bind('<space>', self._stop_animation)
self._root.bind('<Control-g>', self.edit_grammar)
self._root.bind('<Control-t>', self.edit_sentence)
self._root.bind('-', lambda e,a=self._animate:a.set(1))
self._root.bind('=', lambda e,a=self._animate:a.set(2))
self._root.bind('+', lambda e,a=self._animate:a.set(3))
self._root.bind('s', lambda e,s=self._step:s.set(not s.get()))
def _init_menubar(self):
menubar = Tkinter.Menu(self._root)
filemenu = Tkinter.Menu(menubar, tearoff=0)
filemenu.add_command(label='Save Chart', underline=0,
command=self.save_chart, accelerator='Ctrl-s')
filemenu.add_command(label='Load Chart', underline=0,
command=self.load_chart, accelerator='Ctrl-o')
filemenu.add_command(label='Reset Chart', underline=0,
command=self.reset, accelerator='Ctrl-r')
filemenu.add_separator()
filemenu.add_command(label='Save Grammar',
command=self.save_grammar)
filemenu.add_command(label='Load Grammar',
command=self.load_grammar)
filemenu.add_separator()
filemenu.add_command(label='Exit', underline=1,
command=self.destroy, accelerator='Ctrl-x')
menubar.add_cascade(label='File', underline=0, menu=filemenu)
editmenu = Tkinter.Menu(menubar, tearoff=0)
editmenu.add_command(label='Edit Grammar', underline=5,
command=self.edit_grammar,
accelerator='Ctrl-g')
editmenu.add_command(label='Edit Text', underline=5,
command=self.edit_sentence,
accelerator='Ctrl-t')
menubar.add_cascade(label='Edit', underline=0, menu=editmenu)
viewmenu = Tkinter.Menu(menubar, tearoff=0)
viewmenu.add_command(label='Chart Matrix', underline=6,
command=self.view_matrix)
viewmenu.add_command(label='Results', underline=0,
command=self.view_results)
menubar.add_cascade(label='View', underline=0, menu=viewmenu)
rulemenu = Tkinter.Menu(menubar, tearoff=0)
rulemenu.add_command(label='Top Down Strategy', underline=0,
command=self.top_down_strategy,
accelerator='t')
rulemenu.add_command(label='Bottom Up Strategy', underline=0,
command=self.bottom_up_strategy,
accelerator='b')
rulemenu.add_command(label='Earley Algorithm', underline=0,
command=self.bottom_up_strategy,
accelerator='e')
rulemenu.add_separator()
rulemenu.add_command(label='Bottom Up Init Rule',
command=self.bottom_up_init)
rulemenu.add_command(label='Bottom Up Rule',
command=self.bottom_up)
rulemenu.add_command(label='Top Down Init Rule',
command=self.top_down_init)
rulemenu.add_command(label='Top Down Expand Rule',
command=self.top_down_expand)
rulemenu.add_command(label='Top Down Match Rule',
command=self.top_down_match)
rulemenu.add_command(label='Fundamental Rule',
command=self.fundamental)
menubar.add_cascade(label='Apply', underline=0, menu=rulemenu)
animatemenu = Tkinter.Menu(menubar, tearoff=0)
animatemenu.add_checkbutton(label="Step", underline=0,
variable=self._step,
accelerator='s')
animatemenu.add_separator()
animatemenu.add_radiobutton(label="No Animation", underline=0,
variable=self._animate, value=0)
animatemenu.add_radiobutton(label="Slow Animation", underline=0,
variable=self._animate, value=1,
accelerator='-')
animatemenu.add_radiobutton(label="Normal Animation", underline=0,
variable=self._animate, value=2,
accelerator='=')
animatemenu.add_radiobutton(label="Fast Animation", underline=0,
variable=self._animate, value=3,
accelerator='+')
menubar.add_cascade(label="Animate", underline=1, menu=animatemenu)
zoommenu = Tkinter.Menu(menubar, tearoff=0)
zoommenu.add_radiobutton(label='Tiny', variable=self._size,
underline=0, value=10, command=self.resize)
zoommenu.add_radiobutton(label='Small', variable=self._size,
underline=0, value=12, command=self.resize)
zoommenu.add_radiobutton(label='Medium', variable=self._size,
underline=0, value=14, command=self.resize)
zoommenu.add_radiobutton(label='Large', variable=self._size,
underline=0, value=18, command=self.resize)
zoommenu.add_radiobutton(label='Huge', variable=self._size,
underline=0, value=24, command=self.resize)
menubar.add_cascade(label='Zoom', underline=0, menu=zoommenu)
helpmenu = Tkinter.Menu(menubar, tearoff=0)
helpmenu.add_command(label='About', underline=0,
command=self.about)
helpmenu.add_command(label='Instructions', underline=0,
command=self.help, accelerator='F1')
menubar.add_cascade(label='Help', underline=0, menu=helpmenu)
self._root.config(menu=menubar)
def _click_cv_edge(self, edge):
if edge != self._selection:
self._select_edge(edge)
else:
self._cv.cycle_tree()
def _select_matrix_edge(self, edge):
self._select_edge(edge)
self._cv.view_edge(edge)
def _select_edge(self, edge):
self._selection = edge
self._cv.markonly_edge(edge, '#f00')
self._cv.draw_tree(edge)
if self._matrix: self._matrix.markonly_edge(edge)
if self._matrix: self._matrix.view_edge(edge)
def _deselect_edge(self):
self._selection = None
self._cv.unmark_edge()
self._cv.erase_tree()
if self._matrix: self._matrix.unmark_edge()
def _show_new_edge(self, edge):
self._display_rule(self._cp.current_chartrule())
self._cv.update()
self._cv.draw_tree(edge)
self._cv.markonly_edge(edge, '#0df')
self._cv.view_edge(edge)
if self._matrix: self._matrix.update()
if self._matrix: self._matrix.markonly_edge(edge)
if self._matrix: self._matrix.view_edge(edge)
if self._results: self._results.update(edge)
def help(self, *e):
self._animating = 0
try:
ShowText(self._root, 'Help: Chart Parser Demo',
(__doc__).strip(), width=75, font='fixed')
except:
ShowText(self._root, 'Help: Chart Parser Demo',
(__doc__).strip(), width=75)
def about(self, *e):
ABOUT = ("NLTK Chart Parser Demo\n"+
"Written by Edward Loper")
tkMessageBox.showinfo('About: Chart Parser Demo', ABOUT)
CHART_FILE_TYPES = [('Pickle file', '.pickle'),
('All files', '*')]
GRAMMAR_FILE_TYPES = [('Plaintext grammar file', '.cfg'),
('Pickle file', '.pickle'),
('All files', '*')]
def load_chart(self, *args):
"Load a chart from a pickle file"
filename = askopenfilename(filetypes=self.CHART_FILE_TYPES,
defaultextension='.pickle')
if not filename: return
try:
chart = pickle.load(open(filename, 'r'))
self._chart = chart
self._cv.update(chart)
if self._matrix: self._matrix.set_chart(chart)
if self._matrix: self._matrix.deselect_cell()
if self._results: self._results.set_chart(chart)
self._cp.set_chart(chart)
except Exception, e:
raise
tkMessageBox.showerror('Error Loading Chart',
'Unable to open file: %r' % filename)
def save_chart(self, *args):
"Save a chart to a pickle file"
filename = asksaveasfilename(filetypes=self.CHART_FILE_TYPES,
defaultextension='.pickle')
if not filename: return
try:
pickle.dump(self._chart, open(filename, 'w'))
except Exception, e:
raise
tkMessageBox.showerror('Error Saving Chart',
'Unable to open file: %r' % filename)
def load_grammar(self, *args):
"Load a grammar from a pickle file"
filename = askopenfilename(filetypes=self.GRAMMAR_FILE_TYPES,
defaultextension='.cfg')
if not filename: return
try:
if filename.endswith('.pickle'):
grammar = pickle.load(open(filename, 'r'))
else:
grammar = cfg.parse_cfg(open(filename, 'r').read())
self.set_grammar(grammar)
except Exception, e:
tkMessageBox.showerror('Error Loading Grammar',
'Unable to open file: %r' % filename)
def save_grammar(self, *args):
filename = asksaveasfilename(filetypes=self.GRAMMAR_FILE_TYPES,
defaultextension='.cfg')
if not filename: return
try:
if filename.endswith('.pickle'):
pickle.dump((self._chart, self._tokens), open(filename, 'w'))
else:
file = open(filename, 'w')
prods = self._grammar.productions()
start = [p for p in prods if p.lhs() == self._grammar.start()]
rest = [p for p in prods if p.lhs() != self._grammar.start()]
for prod in start: file.write('%s\n' % prod)
for prod in rest: file.write('%s\n' % prod)
file.close()
except Exception, e:
tkMessageBox.showerror('Error Saving Grammar',
'Unable to open file: %r' % filename)
def reset(self, *args):
self._animating = 0
self._cp = SteppingChartParser(self._grammar)
self._cp.initialize(self._tokens)
self._chart = self._cp.chart()
self._cv.update(self._chart)
if self._matrix: self._matrix.set_chart(self._chart)
if self._matrix: self._matrix.deselect_cell()
if self._results: self._results.set_chart(self._chart)
self._cpstep = self._cp.step()
def edit_grammar(self, *e):
CFGEditor(self._root, self._grammar, self.set_grammar)
def set_grammar(self, grammar):
self._grammar = grammar
self._cp.set_grammar(grammar)
if self._results: self._results.set_grammar(grammar)
def edit_sentence(self, *e):
sentence = string.join(self._tokens)
title = 'Edit Text'
instr = 'Enter a new sentence to parse.'
EntryDialog(self._root, sentence, instr, self.set_sentence, title)
def set_sentence(self, sentence):
self._tokens = list(sentence.split())
self.reset()
def view_matrix(self, *e):
if self._matrix is not None: self._matrix.destroy()
self._matrix = ChartMatrixView(self._root, self._chart)
self._matrix.add_callback('select', self._select_matrix_edge)
def view_results(self, *e):
if self._results is not None: self._results.destroy()
self._results = ChartResultsView(self._root, self._chart,
self._grammar)
def resize(self):
self._animating = 0
self.set_font_size(self._size.get())
def set_font_size(self, size):
self._cv.set_font_size(size)
self._font.configure(size=-abs(size))
self._boldfont.configure(size=-abs(size))
self._sysfont.configure(size=-abs(size))
def get_font_size(self):
return abs(self._size.get())
def apply_strategy(self, strategy, edge_strategy=None):
if self._animating:
self._animating = 0
return
self._display_rule(None)
if self._step.get():
selection = self._selection
if (selection is not None) and (edge_strategy is not None):
self._cp.set_strategy([edge_strategy(selection)])
newedge = self._apply_strategy()
if newedge is None:
self._cv.unmark_edge()
self._selection = None
else:
self._cp.set_strategy(strategy)
self._apply_strategy()
else:
self._cp.set_strategy(strategy)
if self._animate.get():
self._animating = 1
self._animate_strategy()
else:
for edge in self._cpstep:
if edge is None: break
self._cv.update()
if self._matrix: self._matrix.update()
if self._results: self._results.update()
def _stop_animation(self, *e):
self._animating = 0
def _animate_strategy(self, speed=1):
if self._animating == 0: return
if self._apply_strategy() is not None:
if self._animate.get() == 0 or self._step.get() == 1:
return
if self._animate.get() == 1:
self._root.after(3000, self._animate_strategy)
elif self._animate.get() == 2:
self._root.after(1000, self._animate_strategy)
else:
self._root.after(20, self._animate_strategy)
def _apply_strategy(self):
new_edge = self._cpstep.next()
if new_edge is not None:
self._show_new_edge(new_edge)
return new_edge
def _display_rule(self, rule):
if rule == None:
self._rulelabel2['text'] = ''
else:
name = str(rule)
self._rulelabel2['text'] = name
size = self._cv.get_font_size()
_TD_INIT = [TopDownInitRule()]
_TD_EXPAND = [TopDownExpandRule()]
_TD_MATCH = [TopDownMatchRule()]
_BU_INIT = [BottomUpInitRule()]
_BU_RULE = [BottomUpPredictRule()]
_FUNDAMENTAL = [SingleEdgeFundamentalRule()]
_EARLEY = [PseudoEarleyRule()]
_EARLEY_INIT = [PseudoEarleyInitRule()]
_TD_STRATEGY = _TD_INIT + _TD_EXPAND + _TD_MATCH + _FUNDAMENTAL
_BU_STRATEGY = _BU_INIT + _BU_RULE + _FUNDAMENTAL
_EARLEY = _EARLEY_INIT + _EARLEY
def top_down_init(self, *e):
self.apply_strategy(self._TD_INIT, None)
def top_down_expand(self, *e):
self.apply_strategy(self._TD_EXPAND, TopDownExpandEdgeRule)
def top_down_match(self, *e):
self.apply_strategy(self._TD_MATCH, TopDownMatchEdgeRule)
def bottom_up_init(self, *e):
self.apply_strategy(self._BU_INIT, BottomUpInitEdgeRule)
def bottom_up(self, *e):
self.apply_strategy(self._BU_RULE, BottomUpEdgeRule)
def fundamental(self, *e):
self.apply_strategy(self._FUNDAMENTAL, FundamentalEdgeRule)
def bottom_up_strategy(self, *e):
self.apply_strategy(self._BU_STRATEGY, BottomUpEdgeRule)
def top_down_strategy(self, *e):
self.apply_strategy(self._TD_STRATEGY, TopDownExpandEdgeRule)
def earley_algorithm(self, *e):
self.apply_strategy(self._EARLEY, PseudoEarleyEdgeRule)
def demo():
grammar = cfg.parse_cfg("""
# Grammatical productions.
S -> NP VP
VP -> VP PP | V NP | V
NP -> Det N | NP PP
PP -> P NP
# Lexical productions.
NP -> 'John' | 'I'
Det -> 'the' | 'my' | 'a'
N -> 'dog' | 'cookie' | 'table' | 'cake' | 'fork'
V -> 'ate' | 'saw'
P -> 'on' | 'under' | 'with'
""")
sent = 'John ate the cake on the table with a fork'
sent = 'John ate the cake on the table'
tokens = list(sent.split())
print 'grammar= ('
for rule in grammar.productions():
print ' ', repr(rule)+','
print ')'
print 'tokens = %r' % tokens
print 'Calling "ChartDemo(grammar, tokens)"...'
ChartDemo(grammar, tokens).mainloop()
if __name__ == '__main__':
demo()