nltk.draw.chart

1 # Natural Language Toolkit: Chart Parser Demo 2 # 3 # Copyright (C) 2001-2008 NLTK Project 4 # Author: Edward Loper <[email protected]> 5 # Jean Mark Gawron <[email protected]> 6 # Steven Bird <[email protected]> 7 # URL: <http://nltk.org> 8 # For license information, see LICENSE.TXT 9 # 10 # $Id: chart.py 6265 2008-07-26 09:25:03Z stevenbird $ 11 12 """ 13 A graphical tool for exploring chart parsing. 14 15 Chart parsing is a flexible parsing algorithm that uses a data 16 structure called a "chart" to record hypotheses about syntactic 17 constituents. Each hypothesis is represented by a single "edge" on 18 the chart. A set of "chart rules" determine when new edges can be 19 added to the chart. This set of rules controls the overall behavior 20 of the parser (e.g., whether it parses top-down or bottom-up). 21 22 The chart parsing tool demonstrates the process of parsing a single 23 sentence, with a given grammar and lexicon. Its display is divided 24 into three sections: the bottom section displays the chart; the middle 25 section displays the sentence; and the top section displays the 26 partial syntax tree corresponding to the selected edge. Buttons along 27 the bottom of the window are used to control the execution of the 28 algorithm. 29 30 The chart parsing tool allows for flexible control of the parsing 31 algorithm. At each step of the algorithm, you can select which rule 32 or strategy you wish to apply. This allows you to experiment with 33 mixing different strategies (e.g., top-down and bottom-up). You can 34 exercise fine-grained control over the algorithm by selecting which 35 edge you wish to apply a rule to. 36 """ 37 38 # At some point, we should rewrite this tool to use the new canvas 39 # widget system. 40 41 import pickle 42 from tkFileDialog import asksaveasfilename, askopenfilename 43 import Tkinter, tkFont, tkMessageBox 44 import math 45 import string 46 import os.path 47 48 from nltk.parse.chart import * 49 from nltk import tokenize, Tree, cfg 50 from nltk.draw import ShowText, EntryDialog, in_idle 51 from nltk.draw import MutableOptionMenu 52 from nltk.draw import ColorizedList, SymbolWidget, CanvasFrame 53 from nltk.draw.cfg import CFGEditor 54 from nltk.draw.tree import tree_to_treesegment, TreeSegmentWidget 55 56 # Known bug: ChartView doesn't handle edges generated by epsilon 57 # productions (e.g., [Production: PP -> ]) very well. 58 59 ####################################################################### 60 # Edge List 61 ####################################################################### 62

63 -class EdgeList(ColorizedList):

64 ARROW = SymbolWidget.SYMBOLS['rightarrow'] 65

66 - def _init_colortags(self, textwidget, options):

67 textwidget.tag_config('terminal', foreground='#006000') 68 textwidget.tag_config('arrow', font='symbol', underline='0') 69 textwidget.tag_config('dot', foreground = '#000000') 70 textwidget.tag_config('nonterminal', foreground='blue', 71 font=('helvetica', -12, 'bold'))

72

73 - def _item_repr(self, item):

74 contents = [] 75 contents.append(('%s\t' % item.lhs(), 'nonterminal')) 76 contents.append((self.ARROW, 'arrow')) 77 for i, elt in enumerate(item.rhs()): 78 if i == item.dot(): 79 contents.append((' *', 'dot')) 80 if isinstance(elt, cfg.Nonterminal): 81 contents.append((' %s' % elt.symbol(), 'nonterminal')) 82 else: 83 contents.append((' %r' % elt, 'terminal')) 84 if item.is_complete(): 85 contents.append((' *', 'dot')) 86 return contents

87 88 ####################################################################### 89 # Chart Matrix View 90 ####################################################################### 91

92 -class ChartMatrixView(object):

93 """ 94 A view of a chart that displays the contents of the corresponding matrix. 95 """

96 - def __init__(self, parent, chart, toplevel=True, title='Chart Matrix', 97 show_numedges=False):

98 self._chart = chart 99 self._cells = [] 100 self._marks = [] 101 102 self._selected_cell = None 103 104 if toplevel: 105 self._root = Tkinter.Toplevel(parent) 106 self._root.title(title) 107 self._root.bind('<Control-q>', self.destroy) 108 self._init_quit(self._root) 109 else: 110 self._root = Tkinter.Frame(parent) 111 112 self._init_matrix(self._root) 113 self._init_list(self._root) 114 if show_numedges: 115 self._init_numedges(self._root) 116 else: 117 self._numedges_label = None 118 119 self._callbacks = {} 120 121 self._num_edges = 0 122 123 self.draw()

124

125 - def _init_quit(self, root):

126 quit = Tkinter.Button(root, text='Quit', command=self.destroy) 127 quit.pack(side='bottom', expand=0, fill='none')

128

129 - def _init_matrix(self, root):

130 cframe = Tkinter.Frame(root, border=2, relief='sunken') 131 cframe.pack(expand=0, fill='none', padx=1, pady=3, side='top') 132 self._canvas = Tkinter.Canvas(cframe, width=200, height=200, 133 background='white') 134 self._canvas.pack(expand=0, fill='none')

135

136 - def _init_numedges(self, root):

137 self._numedges_label = Tkinter.Label(root, text='0 edges') 138 self._numedges_label.pack(expand=0, fill='none', side='top')

139

140 - def _init_list(self, root):

141 self._list = EdgeList(root, [], width=20, height=5) 142 self._list.pack(side='top', expand=1, fill='both', pady=3) 143 def cb(edge, self=self): self._fire_callbacks('select', edge) 144 self._list.add_callback('select', cb) 145 self._list.focus()

146

147 - def destroy(self, *e):

148 if self._root is None: return 149 try: self._root.destroy() 150 except: pass 151 self._root = None

152

153 - def set_chart(self, chart):

154 if chart is not self._chart: 155 self._chart = chart 156 self._num_edges = 0 157 self.draw()

158

159 - def update(self):

160 if self._root is None: return 161 162 # Count the edges in each cell 163 N = len(self._cells) 164 cell_edges = [[0 for i in range(N)] for j in range(N)] 165 for edge in self._chart: 166 cell_edges[edge.start()][edge.end()] += 1 167 168 # Color the cells correspondingly. 169 for i in range(N): 170 for j in range(i, N): 171 if cell_edges[i][j] == 0: 172 color = 'gray20' 173 else: 174 color = ('#00%02x%02x' % 175 (min(255, 50+128*cell_edges[i][j]/10), 176 max(0, 128-128*cell_edges[i][j]/10))) 177 cell_tag = self._cells[i][j] 178 self._canvas.itemconfig(cell_tag, fill=color) 179 if (i,j) == self._selected_cell: 180 self._canvas.itemconfig(cell_tag, outline='#00ffff', 181 width=3) 182 self._canvas.tag_raise(cell_tag) 183 else: 184 self._canvas.itemconfig(cell_tag, outline='black', 185 width=1) 186 187 # Update the edge list. 188 edges = list(self._chart.select(span=self._selected_cell)) 189 self._list.set(edges) 190 191 # Update our edge count. 192 self._num_edges = self._chart.num_edges() 193 if self._numedges_label is not None: 194 self._numedges_label['text'] = '%d edges' % self._num_edges

195

196 - def activate(self):

197 self._canvas.itemconfig('inactivebox', state='hidden') 198 self.update()

199

200 - def inactivate(self):

201 self._canvas.itemconfig('inactivebox', state='normal') 202 self.update()

203

204 - def add_callback(self, event, func):

205 self._callbacks.setdefault(event,{})[func] = 1

206

207 - def remove_callback(self, event, func=None):

208 if func is None: del self._callbacks[event] 209 else: 210 try: del self._callbacks[event][func] 211 except: pass

212

213 - def _fire_callbacks(self, event, *args):

214 if not self._callbacks.has_key(event): return 215 for cb_func in self._callbacks[event].keys(): cb_func(*args)

216

217 - def select_cell(self, i, j):

218 if self._root is None: return 219 220 # If the cell is already selected (and the chart contents 221 # haven't changed), then do nothing. 222 if ((i,j) == self._selected_cell and 223 self._chart.num_edges() == self._num_edges): return 224 225 self._selected_cell = (i,j) 226 self.update() 227 228 # Fire the callback. 229 self._fire_callbacks('select_cell', i, j)

230

231 - def deselect_cell(self):

232 if self._root is None: return 233 self._selected_cell = None 234 self._list.set([]) 235 self.update()

236

237 - def _click_cell(self, i, j):

238 if self._selected_cell == (i,j): 239 self.deselect_cell() 240 else: 241 self.select_cell(i, j)

242

243 - def view_edge(self, edge):

244 self.select_cell(*edge.span()) 245 self._list.view(edge)

246

247 - def mark_edge(self, edge):

248 if self._root is None: return 249 self.select_cell(*edge.span()) 250 self._list.mark(edge)

251

252 - def unmark_edge(self, edge=None):

253 if self._root is None: return 254 self._list.unmark(edge)

255

256 - def markonly_edge(self, edge):

257 if self._root is None: return 258 self.select_cell(*edge.span()) 259 self._list.markonly(edge)

260

261 - def draw(self):

262 if self._root is None: return 263 LEFT_MARGIN = BOT_MARGIN = 15 264 TOP_MARGIN = 5 265 c = self._canvas 266 c.delete('all') 267 N = self._chart.num_leaves()+1 268 dx = (int(c['width'])-LEFT_MARGIN)/N 269 dy = (int(c['height'])-TOP_MARGIN-BOT_MARGIN)/N 270 271 c.delete('all') 272 273 # Labels and dotted lines 274 for i in range(N): 275 c.create_text(LEFT_MARGIN-2, i*dy+dy/2+TOP_MARGIN, 276 text=`i`, anchor='e') 277 c.create_text(i*dx+dx/2+LEFT_MARGIN, N*dy+TOP_MARGIN+1, 278 text=`i`, anchor='n') 279 c.create_line(LEFT_MARGIN, dy*(i+1)+TOP_MARGIN, 280 dx*N+LEFT_MARGIN, dy*(i+1)+TOP_MARGIN, dash='.') 281 c.create_line(dx*i+LEFT_MARGIN, TOP_MARGIN, 282 dx*i+LEFT_MARGIN, dy*N+TOP_MARGIN, dash='.') 283 284 # A box around the whole thing 285 c.create_rectangle(LEFT_MARGIN, TOP_MARGIN, 286 LEFT_MARGIN+dx*N, dy*N+TOP_MARGIN, 287 width=2) 288 289 # Cells 290 self._cells = [[None for i in range(N)] for j in range(N)] 291 for i in range(N): 292 for j in range(i, N): 293 t = c.create_rectangle(j*dx+LEFT_MARGIN, i*dy+TOP_MARGIN, 294 (j+1)*dx+LEFT_MARGIN, 295 (i+1)*dy+TOP_MARGIN, 296 fill='gray20') 297 self._cells[i][j] = t 298 def cb(event, self=self, i=i, j=j): self._click_cell(i,j) 299 c.tag_bind(t, '<Button-1>', cb) 300 301 # Inactive box 302 xmax, ymax = int(c['width']), int(c['height']) 303 t = c.create_rectangle(-100, -100, xmax+100, ymax+100, 304 fill='gray50', state='hidden', 305 tag='inactivebox') 306 c.tag_lower(t) 307 308 # Update the cells. 309 self.update()

310

311 - def pack(self, *args, **kwargs):

312 self._root.pack(*args, **kwargs)

313 314 ####################################################################### 315 # Chart Results View 316 ####################################################################### 317

318 -class ChartResultsView(object):

319 - def __init__(self, parent, chart, grammar, toplevel=True):

320 self._chart = chart 321 self._grammar = grammar 322 self._trees = [] 323 self._y = 10 324 self._treewidgets = [] 325 self._selection = None 326 self._selectbox = None 327 328 if toplevel: 329 self._root = Tkinter.Toplevel(parent) 330 self._root.title('Chart Parsing Demo: Results') 331 self._root.bind('<Control-q>', self.destroy) 332 else: 333 self._root = Tkinter.Frame(parent) 334 335 # Buttons 336 if toplevel: 337 buttons = Tkinter.Frame(self._root) 338 buttons.pack(side='bottom', expand=0, fill='x') 339 Tkinter.Button(buttons, text='Quit', 340 command=self.destroy).pack(side='right') 341 Tkinter.Button(buttons, text='Print All', 342 command=self.print_all).pack(side='left') 343 Tkinter.Button(buttons, text='Print Selection', 344 command=self.print_selection).pack(side='left') 345 346 # Canvas frame. 347 self._cframe = CanvasFrame(self._root, closeenough=20) 348 self._cframe.pack(side='top', expand=1, fill='both') 349 350 # Initial update 351 self.update()

352

353 - def update(self, edge=None):

354 if self._root is None: return 355 # If the edge isn't a parse edge, do nothing. 356 if edge is not None: 357 if edge.lhs() != self._grammar.start(): return 358 if edge.span() != (0, self._chart.num_leaves()): return 359 360 for parse in self._chart.parses(self._grammar.start()): 361 if parse not in self._trees: 362 self._add(parse)

363

364 - def _add(self, parse):

365 # Add it to self._trees. 366 self._trees.append(parse) 367 368 # Create a widget for it. 369 c = self._cframe.canvas() 370 treewidget = tree_to_treesegment(c, parse) 371 372 # Add it to the canvas frame. 373 self._treewidgets.append(treewidget) 374 self._cframe.add_widget(treewidget, 10, self._y) 375 376 # Register callbacks. 377 treewidget.bind_click(self._click) 378 379 # Update y. 380 self._y = treewidget.bbox()[3] + 10

381

382 - def _click(self, widget):

383 c = self._cframe.canvas() 384 if self._selection is not None: 385 c.delete(self._selectbox) 386 self._selection = widget 387 (x1, y1, x2, y2) = widget.bbox() 388 self._selectbox = c.create_rectangle(x1, y1, x2, y2, 389 width=2, outline='#088')

390

391 - def _color(self, treewidget, color):

392 treewidget.node()['color'] = color 393 for child in treewidget.subtrees(): 394 if isinstance(child, TreeSegmentWidget): 395 self._color(child, color) 396 else: 397 child['color'] = color

398

399 - def print_all(self, *e):

400 if self._root is None: return 401 self._cframe.print_to_file()

402

403 - def print_selection(self, *e):

404 if self._root is None: return 405 if self._selection is None: 406 tkMessageBox.showerror('Print Error', 'No tree selected') 407 else: 408 c = self._cframe.canvas() 409 for widget in self._treewidgets: 410 if widget is not self._selection: 411 self._cframe.destroy_widget(widget) 412 c.delete(self._selectbox) 413 (x1,y1,x2,y2) = self._selection.bbox() 414 self._selection.move(10-x1,10-y1) 415 c['scrollregion'] = '0 0 %s %s' % (x2-x1+20, y2-y1+20) 416 self._cframe.print_to_file() 417 418 # Restore our state. 419 self._treewidgets = [self._selection] 420 self.clear() 421 self.update()

422

423 - def clear(self):

424 if self._root is None: return 425 for treewidget in self._treewidgets: 426 self._cframe.destroy_widget(treewidget) 427 self._trees = [] 428 self._treewidgets = [] 429 if self._selection is not None: 430 self._cframe.canvas().delete(self._selectbox) 431 self._selection = None 432 self._y = 10

433

434 - def set_chart(self, chart):

435 self.clear() 436 self._chart = chart 437 self.update()

438

439 - def set_grammar(self, grammar):

440 self.clear() 441 self._grammar = grammar 442 self.update()

443

444 - def destroy(self, *e):

445 if self._root is None: return 446 try: self._root.destroy() 447 except: pass 448 self._root = None

449

450 - def pack(self, *args, **kwargs):

451 self._root.pack(*args, **kwargs)

452 453 ####################################################################### 454 # Chart Comparer 455 ####################################################################### 456

457 -class ChartComparer(object):

458 """ 459 460 @ivar _root: The root window 461 462 @ivar _charts: A dictionary mapping names to charts. When 463 charts are loaded, they are added to this dictionary. 464 465 @ivar _left_chart: The left L{Chart}. 466 @ivar _left_name: The name C{_left_chart} (derived from filename) 467 @ivar _left_matrix: The L{ChartMatrixView} for C{_left_chart} 468 @ivar _left_selector: The drop-down C{MutableOptionsMenu} used 469 to select C{_left_chart}. 470 471 @ivar _right_chart: The right L{Chart}. 472 @ivar _right_name: The name C{_right_chart} (derived from filename) 473 @ivar _right_matrix: The L{ChartMatrixView} for C{_right_chart} 474 @ivar _right_selector: The drop-down C{MutableOptionsMenu} used 475 to select C{_right_chart}. 476 477 @ivar _out_chart: The out L{Chart}. 478 @ivar _out_name: The name C{_out_chart} (derived from filename) 479 @ivar _out_matrix: The L{ChartMatrixView} for C{_out_chart} 480 @ivar _out_label: The label for C{_out_chart}. 481 482 @ivar _op_label: A Label containing the most recent operation. 483 """ 484 485 _OPSYMBOL = {'-': '-', 486 'and': SymbolWidget.SYMBOLS['intersection'], 487 'or': SymbolWidget.SYMBOLS['union']} 488

489 - def __init__(self, *chart_filenames):

490 # This chart is displayed when we don't have a value (eg 491 # before any chart is loaded). 492 faketok = [''] * 8 493 self._emptychart = Chart(faketok) 494 495 # The left & right charts start out empty. 496 self._left_name = 'None' 497 self._right_name = 'None' 498 self._left_chart = self._emptychart 499 self._right_chart = self._emptychart 500 501 # The charts that have been loaded. 502 self._charts = {'None': self._emptychart} 503 504 # The output chart. 505 self._out_chart = self._emptychart 506 507 # The most recent operation 508 self._operator = None 509 510 # Set up the root window. 511 self._root = Tkinter.Tk() 512 self._root.title('Chart Comparison') 513 self._root.bind('<Control-q>', self.destroy) 514 self._root.bind('<Control-x>', self.destroy) 515 516 # Initialize all widgets, etc. 517 self._init_menubar(self._root) 518 self._init_chartviews(self._root) 519 self._init_divider(self._root) 520 self._init_buttons(self._root) 521 self._init_bindings(self._root) 522 523 # Load any specified charts. 524 for filename in chart_filenames: 525 self.load_chart(filename)

526

527 - def destroy(self, *e):

528 if self._root is None: return 529 try: self._root.destroy() 530 except: pass 531 self._root = None

532

533 - def mainloop(self, *args, **kwargs):

534 return 535 self._root.mainloop(*args, **kwargs)

536 537 #//////////////////////////////////////////////////////////// 538 # Initialization 539 #//////////////////////////////////////////////////////////// 540

541 - def _init_menubar(self, root):

542 menubar = Tkinter.Menu(root) 543 544 # File menu 545 filemenu = Tkinter.Menu(menubar, tearoff=0) 546 filemenu.add_command(label='Load Chart', accelerator='Ctrl-o', 547 underline=0, command=self.load_chart_dialog) 548 filemenu.add_command(label='Save Output', accelerator='Ctrl-s', 549 underline=0, command=self.save_chart_dialog) 550 filemenu.add_separator() 551 filemenu.add_command(label='Exit', underline=1, 552 command=self.destroy, accelerator='Ctrl-x') 553 menubar.add_cascade(label='File', underline=0, menu=filemenu) 554 555 # Compare menu 556 opmenu = Tkinter.Menu(menubar, tearoff=0) 557 opmenu.add_command(label='Intersection', 558 command=self._intersection, 559 accelerator='+') 560 opmenu.add_command(label='Union', 561 command=self._union, 562 accelerator='*') 563 opmenu.add_command(label='Difference', 564 command=self._difference, 565 accelerator='-') 566 opmenu.add_separator() 567 opmenu.add_command(label='Swap Charts', 568 command=self._swapcharts) 569 menubar.add_cascade(label='Compare', underline=0, menu=opmenu) 570 571 # Add the menu 572 self._root.config(menu=menubar)

573

574 - def _init_divider(self, root):

575 divider = Tkinter.Frame(root, border=2, relief='sunken') 576 divider.pack(side='top', fill='x', ipady=2)

577

578 - def _init_chartviews(self, root):

579 opfont=('symbol', -36) # Font for operator. 580 eqfont=('helvetica', -36) # Font for equals sign. 581 582 frame = Tkinter.Frame(root, background='#c0c0c0') 583 frame.pack(side='top', expand=1, fill='both') 584 585 # The left matrix. 586 cv1_frame = Tkinter.Frame(frame, border=3, relief='groove') 587 cv1_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both') 588 self._left_selector = MutableOptionMenu( 589 cv1_frame, self._charts.keys(), command=self._select_left) 590 self._left_selector.pack(side='top', pady=5, fill='x') 591 self._left_matrix = ChartMatrixView(cv1_frame, self._emptychart, 592 toplevel=False, 593 show_numedges=True) 594 self._left_matrix.pack(side='bottom', padx=5, pady=5, 595 expand=1, fill='both') 596 self._left_matrix.add_callback('select', self.select_edge) 597 self._left_matrix.add_callback('select_cell', self.select_cell) 598 self._left_matrix.inactivate() 599 600 # The operator. 601 self._op_label = Tkinter.Label(frame, text=' ', width=3, 602 background='#c0c0c0', font=opfont) 603 self._op_label.pack(side='left', padx=5, pady=5) 604 605 # The right matrix. 606 cv2_frame = Tkinter.Frame(frame, border=3, relief='groove') 607 cv2_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both') 608 self._right_selector = MutableOptionMenu( 609 cv2_frame, self._charts.keys(), command=self._select_right) 610 self._right_selector.pack(side='top', pady=5, fill='x') 611 self._right_matrix = ChartMatrixView(cv2_frame, self._emptychart, 612 toplevel=False, 613 show_numedges=True) 614 self._right_matrix.pack(side='bottom', padx=5, pady=5, 615 expand=1, fill='both') 616 self._right_matrix.add_callback('select', self.select_edge) 617 self._right_matrix.add_callback('select_cell', self.select_cell) 618 self._right_matrix.inactivate() 619 620 # The equals sign 621 Tkinter.Label(frame, text='=', width=3, background='#c0c0c0', 622 font=eqfont).pack(side='left', padx=5, pady=5) 623 624 # The output matrix. 625 out_frame = Tkinter.Frame(frame, border=3, relief='groove') 626 out_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both') 627 self._out_label = Tkinter.Label(out_frame, text='Output') 628 self._out_label.pack(side='top', pady=9) 629 self._out_matrix = ChartMatrixView(out_frame, self._emptychart, 630 toplevel=False, 631 show_numedges=True) 632 self._out_matrix.pack(side='bottom', padx=5, pady=5, 633 expand=1, fill='both') 634 self._out_matrix.add_callback('select', self.select_edge) 635 self._out_matrix.add_callback('select_cell', self.select_cell) 636 self._out_matrix.inactivate()

637

638 - def _init_buttons(self, root):

639 buttons = Tkinter.Frame(root) 640 buttons.pack(side='bottom', pady=5, fill='x', expand=0) 641 Tkinter.Button(buttons, text='Intersection', 642 command=self._intersection).pack(side='left') 643 Tkinter.Button(buttons, text='Union', 644 command=self._union).pack(side='left') 645 Tkinter.Button(buttons, text='Difference', 646 command=self._difference).pack(side='left') 647 Tkinter.Frame(buttons, width=20).pack(side='left') 648 Tkinter.Button(buttons, text='Swap Charts', 649 command=self._swapcharts).pack(side='left') 650 651 Tkinter.Button(buttons, text='Detatch Output', 652 command=self._detatch_out).pack(side='right')

653

654 - def _init_bindings(self, root):

655 #root.bind('<Control-s>', self.save_chart) 656 root.bind('<Control-o>', self.load_chart_dialog)

657 #root.bind('<Control-r>', self.reset) 658 659 #//////////////////////////////////////////////////////////// 660 # Input Handling 661 #//////////////////////////////////////////////////////////// 662

663 - def _select_left(self, name):

664 self._left_name = name 665 self._left_chart = self._charts[name] 666 self._left_matrix.set_chart(self._left_chart) 667 if name == 'None': self._left_matrix.inactivate() 668 self._apply_op()

669

670 - def _select_right(self, name):

671 self._right_name = name 672 self._right_chart = self._charts[name] 673 self._right_matrix.set_chart(self._right_chart) 674 if name == 'None': self._right_matrix.inactivate() 675 self._apply_op()

676

677 - def _apply_op(self):

678 if self._operator == '-': self._difference() 679 elif self._operator == 'or': self._union() 680 elif self._operator == 'and': self._intersection()

681 682 683 #//////////////////////////////////////////////////////////// 684 # File 685 #//////////////////////////////////////////////////////////// 686 CHART_FILE_TYPES = [('Pickle file', '.pickle'), 687 ('All files', '*')] 688

689 - def save_chart_dialog(self, *args):

690 filename = asksaveasfilename(filetypes=self.CHART_FILE_TYPES, 691 defaultextension='.pickle') 692 if not filename: return 693 try: pickle.dump((self._out_chart), open(filename, 'w')) 694 except Exception, e: 695 tkMessageBox.showerror('Error Saving Chart', 696 'Unable to open file: %r\n%s' % 697 (filename, e))

698

699 - def load_chart_dialog(self, *args):

700 filename = askopenfilename(filetypes=self.CHART_FILE_TYPES, 701 defaultextension='.pickle') 702 if not filename: return 703 try: self.load_chart(filename) 704 except Exception, e: 705 tkMessageBox.showerror('Error Loading Chart', 706 'Unable to open file: %r\n%s' % 707 (filename, e))

708

709 - def load_chart(self, filename):

710 chart = pickle.load(open(filename, 'r')) 711 name = os.path.basename(filename) 712 if name.endswith('.pickle'): name = name[:-7] 713 if name.endswith('.chart'): name = name[:-6] 714 self._charts[name] = chart 715 self._left_selector.add(name) 716 self._right_selector.add(name) 717 718 # If either left_matrix or right_matrix is empty, then 719 # display the new chart. 720 if self._left_chart is self._emptychart: 721 self._left_selector.set(name) 722 elif self._right_chart is self._emptychart: 723 self._right_selector.set(name)

724

725 - def _update_chartviews(self):

726 self._left_matrix.update() 727 self._right_matrix.update() 728 self._out_matrix.update()

729 730 #//////////////////////////////////////////////////////////// 731 # Selection 732 #//////////////////////////////////////////////////////////// 733

734 - def select_edge(self, edge):

735 if edge in self._left_chart: 736 self._left_matrix.markonly_edge(edge) 737 else: 738 self._left_matrix.unmark_edge() 739 if edge in self._right_chart: 740 self._right_matrix.markonly_edge(edge) 741 else: 742 self._right_matrix.unmark_edge() 743 if edge in self._out_chart: 744 self._out_matrix.markonly_edge(edge) 745 else: 746 self._out_matrix.unmark_edge()

747

748 - def select_cell(self, i, j):

749 self._left_matrix.select_cell(i, j) 750 self._right_matrix.select_cell(i, j) 751 self._out_matrix.select_cell(i, j)

752 753 #//////////////////////////////////////////////////////////// 754 # Operations 755 #//////////////////////////////////////////////////////////// 756

757 - def _difference(self):

758 if not self._checkcompat(): return 759 760 out_chart = Chart(self._left_chart.tokens()) 761 for edge in self._left_chart: 762 if edge not in self._right_chart: 763 out_chart.insert(edge, []) 764 765 self._update('-', out_chart)

766

767 - def _intersection(self):

768 if not self._checkcompat(): return 769 770 out_chart = Chart(self._left_chart.tokens()) 771 for edge in self._left_chart: 772 if edge in self._right_chart: 773 out_chart.insert(edge, []) 774 775 self._update('and', out_chart)

776

777 - def _union(self):

778 if not self._checkcompat(): return 779 780 out_chart = Chart(self._left_chart.tokens()) 781 for edge in self._left_chart: 782 out_chart.insert(edge, []) 783 for edge in self._right_chart: 784 out_chart.insert(edge, []) 785 786 self._update('or', out_chart)

787

788 - def _swapcharts(self):

789 left, right = self._left_name, self._right_name 790 self._left_selector.set(right) 791 self._right_selector.set(left)

792

793 - def _checkcompat(self):

794 if (self._left_chart.tokens() != self._right_chart.tokens() or 795 self._left_chart.property_names() != 796 self._right_chart.property_names() or 797 self._left_chart == self._emptychart or 798 self._right_chart == self._emptychart): 799 # Clear & inactivate the output chart. 800 self._out_chart = self._emptychart 801 self._out_matrix.set_chart(self._out_chart) 802 self._out_matrix.inactivate() 803 self._out_label['text'] = 'Output' 804 # Issue some other warning? 805 return False 806 else: 807 return True

808

809 - def _update(self, operator, out_chart):

810 self._operator = operator 811 self._op_label['text'] = self._OPSYMBOL[operator] 812 self._out_chart = out_chart 813 self._out_matrix.set_chart(out_chart) 814 self._out_label['text'] = '%s %s %s' % (self._left_name, 815 self._operator, 816 self._right_name)

817

818 - def _clear_out_chart(self):

819 self._out_chart = self._emptychart 820 self._out_matrix.set_chart(self._out_chart) 821 self._op_label['text'] = ' ' 822 self._out_matrix.inactivate()

823

824 - def _detatch_out(self):

825 ChartMatrixView(self._root, self._out_chart, 826 title=self._out_label['text'])

827 828 829 830 831 832 833 834 835 ####################################################################### 836 # Chart View 837 ####################################################################### 838

839 -class ChartView(object):

840 """ 841 A component for viewing charts. This is used by C{ChartDemo} to 842 allow students to interactively experiment with various chart 843 parsing techniques. It is also used by C{Chart.draw()}. 844 845 @ivar _chart: The chart that we are giving a view of. This chart 846 may be modified; after it is modified, you should call 847 C{update}. 848 @ivar _sentence: The list of tokens that the chart spans. 849 850 @ivar _root: The root window. 851 @ivar _chart_canvas: The canvas we're using to display the chart 852 itself. 853 @ivar _tree_canvas: The canvas we're using to display the tree 854 that each edge spans. May be None, if we're not displaying 855 trees. 856 @ivar _sentence_canvas: The canvas we're using to display the sentence 857 text. May be None, if we're not displaying the sentence text. 858 @ivar _edgetags: A dictionary mapping from edges to the tags of 859 the canvas elements (lines, etc) used to display that edge. 860 The values of this dictionary have the form 861 C{(linetag, rhstag1, dottag, rhstag2, lhstag)}. 862 @ivar _treetags: A list of all the tags that make up the tree; 863 used to erase the tree (without erasing the loclines). 864 @ivar _chart_height: The height of the chart canvas. 865 @ivar _sentence_height: The height of the sentence canvas. 866 @ivar _tree_height: The height of the tree 867 868 @ivar _text_height: The height of a text string (in the normal 869 font). 870 871 @ivar _edgelevels: A list of edges at each level of the chart (the 872 top level is the 0th element). This list is used to remember 873 where edges should be drawn; and to make sure that no edges 874 are overlapping on the chart view. 875 876 @ivar _unitsize: Pixel size of one unit (from the location). This 877 is determined by the span of the chart's location, and the 878 width of the chart display canvas. 879 880 @ivar _fontsize: The current font size 881 882 @ivar _marks: A dictionary from edges to marks. Marks are 883 strings, specifying colors (e.g. 'green'). 884 """ 885 886 _LEAF_SPACING = 10 887 _MARGIN = 10 888 _TREE_LEVEL_SIZE = 12 889 _CHART_LEVEL_SIZE = 40 890

891 - def __init__(self, chart, root=None, **kw):

892 """ 893 Construct a new C{Chart} display. 894 """ 895 # Process keyword args. 896 draw_tree = kw.get('draw_tree', 0) 897 draw_sentence = kw.get('draw_sentence', 1) 898 self._fontsize = kw.get('fontsize', -12) 899 900 # The chart! 901 self._chart = chart 902 903 # Callback functions 904 self._callbacks = {} 905 906 # Keep track of drawn edges 907 self._edgelevels = [] 908 self._edgetags = {} 909 910 # Keep track of which edges are marked. 911 self._marks = {} 912 913 # These are used to keep track of the set of tree tokens 914 # currently displayed in the tree canvas. 915 self._treetoks = [] 916 self._treetoks_edge = None 917 self._treetoks_index = 0 918 919 # Keep track of the tags used to draw the tree 920 self._tree_tags = [] 921 922 # Put multiple edges on each level? 923 self._compact = 0 924 925 # If they didn't provide a main window, then set one up. 926 if root is None: 927 top = Tkinter.Tk() 928 top.title('Chart View') 929 def destroy1(e, top=top): top.destroy() 930 def destroy2(top=top): top.destroy() 931 top.bind('q', destroy1) 932 b = Tkinter.Button(top, text='Done', command=destroy2) 933 b.pack(side='bottom') 934 self._root = top 935 else: 936 self._root = root 937 938 # Create some fonts. 939 self._init_fonts(root) 940 941 # Create the chart canvas. 942 (self._chart_sb, self._chart_canvas) = self._sb_canvas(self._root) 943 self._chart_canvas['height'] = 300 944 self._chart_canvas['closeenough'] = 15 945 946 # Create the sentence canvas. 947 if draw_sentence: 948 cframe = Tkinter.Frame(self._root, relief='sunk', border=2) 949 cframe.pack(fill='both', side='bottom') 950 self._sentence_canvas = Tkinter.Canvas(cframe, height=50) 951 self._sentence_canvas['background'] = '#e0e0e0' 952 self._sentence_canvas.pack(fill='both') 953 #self._sentence_canvas['height'] = self._sentence_height 954 else: 955 self._sentence_canvas = None 956 957 # Create the tree canvas. 958 if draw_tree: 959 (sb, canvas) = self._sb_canvas(self._root, 'n', 'x') 960 (self._tree_sb, self._tree_canvas) = (sb, canvas) 961 self._tree_canvas['height'] = 200 962 else: 963 self._tree_canvas = None 964 965 # Do some analysis to figure out how big the window should be 966 self._analyze() 967 self.draw() 968 self._resize() 969 self._grow() 970 971 # Set up the configure callback, which will be called whenever 972 # the window is resized. 973 self._chart_canvas.bind('<Configure>', self._configure)

974

975 - def _init_fonts(self, root):

976 self._boldfont = tkFont.Font(family='helvetica', weight='bold', 977 size=self._fontsize) 978 self._font = tkFont.Font(family='helvetica', 979 size=self._fontsize) 980 # See: <http://www.astro.washington.edu/owen/ROTKFolklore.html> 981 self._sysfont = tkFont.Font(font=Tkinter.Button()["font"]) 982 root.option_add("*Font", self._sysfont)

983

984 - def _sb_canvas(self, root, expand='y', 985 fill='both', side='bottom'):

986 """ 987 Helper for __init__: construct a canvas with a scrollbar. 988 """ 989 cframe =Tkinter.Frame(root, relief='sunk', border=2) 990 cframe.pack(fill=fill, expand=expand, side=side) 991 canvas = Tkinter.Canvas(cframe, background='#e0e0e0') 992 993 # Give the canvas a scrollbar. 994 sb = Tkinter.Scrollbar(cframe, orient='vertical') 995 sb.pack(side='right', fill='y') 996 canvas.pack(side='left', fill=fill, expand='yes') 997 998 # Connect the scrollbars to the canvas. 999 sb['command']= canvas.yview 1000 canvas['yscrollcommand'] = sb.set 1001 1002 return (sb, canvas)

1003

1004 - def scroll_up(self, *e):

1005 self._chart_canvas.yview('scroll', -1, 'units')

1006

1007 - def scroll_down(self, *e):

1008 self._chart_canvas.yview('scroll', 1, 'units')

1009

1010 - def page_up(self, *e):

1011 self._chart_canvas.yview('scroll', -1, 'pages')

1012

1013 - def page_down(self, *e):

1014 self._chart_canvas.yview('scroll', 1, 'pages')

1015

1016 - def _grow(self):

1017 """ 1018 Grow the window, if necessary 1019 """ 1020 # Grow, if need-be 1021 N = self._chart.num_leaves() 1022 width = max(int(self._chart_canvas['width']), 1023 N * self._unitsize + ChartView._MARGIN * 2 ) 1024 1025 # It won't resize without the second (height) line, but I 1026 # don't understand why not. 1027 self._chart_canvas.configure(width=width) 1028 self._chart_canvas.configure(height=self._chart_canvas['height']) 1029 1030 self._unitsize = (width - 2*ChartView._MARGIN) / N 1031 1032 # Reset the height for the sentence window. 1033 if self._sentence_canvas is not None: 1034 self._sentence_canvas['height'] = self._sentence_height

1035

1036 - def set_font_size(self, size):

1037 self._font.configure(size=-abs(size)) 1038 self._boldfont.configure(size=-abs(size)) 1039 self._sysfont.configure(size=-abs(size)) 1040 self._analyze() 1041 self._grow() 1042 self.draw()

1043

1044 - def get_font_size(self):

1045 return abs(self._fontsize)

1046

1047 - def _configure(self, e):

1048 """ 1049 The configure callback. This is called whenever the window is 1050 resized. It is also called when the window is first mapped. 1051 It figures out the unit size, and redraws the contents of each 1052 canvas. 1053 """ 1054 N = self._chart.num_leaves() 1055 self._unitsize = (e.width - 2*ChartView._MARGIN) / N 1056 self.draw()

1057

1058 - def update(self, chart=None):

1059 """ 1060 Draw any edges that have not been drawn. This is typically 1061 called when a after modifies the canvas that a CanvasView is 1062 displaying. C{update} will cause any edges that have been 1063 added to the chart to be drawn. 1064 1065 If update is given a C{chart} argument, then it will replace 1066 the current chart with the given chart. 1067 """ 1068 if chart is not None: 1069 self._chart = chart 1070 self._edgelevels = [] 1071 self._marks = {} 1072 self._analyze() 1073 self._grow() 1074 self.draw() 1075 self.erase_tree() 1076 self._resize() 1077 else: 1078 for edge in self._chart: 1079 if not self._edgetags.has_key(edge): 1080 self._add_edge(edge) 1081 self._resize()

1082 1083

1084 - def _edge_conflict(self, edge, lvl):

1085 """ 1086 Return 1 if the given edge overlaps with any edge on the given 1087 level. This is used by _add_edge to figure out what level a 1088 new edge should be added to. 1089 """ 1090 (s1, e1) = edge.span() 1091 for otheredge in self._edgelevels[lvl]: 1092 (s2, e2) = otheredge.span() 1093 if (s1 <= s2 < e1) or (s2 <= s1 < e2) or (s1==s2==e1==e2): 1094 return 1 1095 return 0

1096

1097 - def _analyze_edge(self, edge):

1098 """ 1099 Given a new edge, recalculate: 1100 1101 - _text_height 1102 - _unitsize (if the edge text is too big for the current 1103 _unitsize, then increase _unitsize) 1104 """ 1105 c = self._chart_canvas 1106 1107 if isinstance(edge, TreeEdge): 1108 lhs = edge.lhs() 1109 rhselts = [] 1110 for elt in edge.rhs(): 1111 if isinstance(elt, cfg.Nonterminal): 1112 rhselts.append(str(elt.symbol())) 1113 else: 1114 rhselts.append(repr(elt)) 1115 rhs = string.join(rhselts) 1116 else: 1117 lhs = edge.lhs() 1118 rhs = '' 1119 1120 for s in (lhs, rhs): 1121 tag = c.create_text(0,0, text=s, 1122 font=self._boldfont, 1123 anchor='nw', justify='left') 1124 bbox = c.bbox(tag) 1125 c.delete(tag) 1126 width = bbox[2] #+ ChartView._LEAF_SPACING 1127 edgelen = max(edge.length(), 1) 1128 self._unitsize = max(self._unitsize, width/edgelen) 1129 self._text_height = max(self._text_height, bbox[3] - bbox[1])

1130

1131 - def _add_edge(self, edge, minlvl=0):

1132 """ 1133 Add a single edge to the ChartView: 1134 1135 - Call analyze_edge to recalculate display parameters 1136 - Find an available level 1137 - Call _draw_edge 1138 """ 1139 if self._edgetags.has_key(edge): return 1140 self._analyze_edge(edge) 1141 self._grow() 1142 1143 if not self._compact: 1144 self._edgelevels.append([edge]) 1145 lvl = len(self._edgelevels)-1 1146 self._draw_edge(edge, lvl) 1147 self._resize() 1148 return 1149 1150 # Figure out what level to draw the edge on. 1151 lvl = 0 1152 while 1: 1153 # If this level doesn't exist yet, create it. 1154 while lvl >= len(self._edgelevels): 1155 self._edgelevels.append([]) 1156 self._resize() 1157 1158 # Check if we can fit the edge in this level. 1159 if lvl>=minlvl and not self._edge_conflict(edge, lvl): 1160 # Go ahead and draw it. 1161 self._edgelevels[lvl].append(edge) 1162 break 1163 1164 # Try the next level. 1165 lvl += 1 1166 1167 self._draw_edge(edge, lvl)

1168

1169 - def view_edge(self, edge):

1170 level = None 1171 for i in range(len(self._edgelevels)): 1172 if edge in self._edgelevels[i]: 1173 level = i 1174 break 1175 if level == None: return 1176 # Try to view the new edge.. 1177 y = (level+1) * self._chart_level_size 1178 dy = self._text_height + 10 1179 self._chart_canvas.yview('moveto', 1.0) 1180 if self._chart_height != 0: 1181 self._chart_canvas.yview('moveto', 1182 float(y-dy)/self._chart_height)

1183

1184 - def _draw_edge(self, edge, lvl):

1185 """ 1186 Draw a single edge on the ChartView. 1187 """ 1188 c = self._chart_canvas 1189 1190 # Draw the arrow. 1191 x1 = (edge.start() * self._unitsize + ChartView._MARGIN) 1192 x2 = (edge.end() * self._unitsize + ChartView._MARGIN) 1193 if x2 == x1: x2 += max(4, self._unitsize/5) 1194 y = (lvl+1) * self._chart_level_size 1195 linetag = c.create_line(x1, y, x2, y, arrow='last', width=3) 1196 1197 # Draw a label for the edge. 1198 if isinstance(edge, TreeEdge): 1199 rhs = [] 1200 for elt in edge.rhs(): 1201 if isinstance(elt, cfg.Nonterminal): 1202 rhs.append(str(elt.symbol())) 1203 else: 1204 rhs.append(repr(elt)) 1205 pos = edge.dot() 1206 else: 1207 rhs = [] 1208 pos = 0 1209 1210 rhs1 = string.join(rhs[:pos]) 1211 rhs2 = string.join(rhs[pos:]) 1212 rhstag1 = c.create_text(x1+3, y, text=rhs1, 1213 font=self._font, 1214 anchor='nw') 1215 dotx = c.bbox(rhstag1)[2] + 6 1216 doty = (c.bbox(rhstag1)[1]+c.bbox(rhstag1)[3])/2 1217 dottag = c.create_oval(dotx-2, doty-2, dotx+2, doty+2) 1218 rhstag2 = c.create_text(dotx+6, y, text=rhs2, 1219 font=self._font, 1220 anchor='nw') 1221 lhstag = c.create_text((x1+x2)/2, y, text=str(edge.lhs()), 1222 anchor='s', 1223 font=self._boldfont) 1224 1225 # Keep track of the edge's tags. 1226 self._edgetags[edge] = (linetag, rhstag1, 1227 dottag, rhstag2, lhstag) 1228 1229 # Register a callback for clicking on the edge. 1230 def cb(event, self=self, edge=edge): 1231 self._fire_callbacks('select', edge)

1232 c.tag_bind(rhstag1, '<Button-1>', cb) 1233 c.tag_bind(rhstag2, '<Button-1>', cb) 1234 c.tag_bind(linetag, '<Button-1>', cb) 1235 c.tag_bind(dottag, '<Button-1>', cb) 1236 c.tag_bind(lhstag, '<Button-1>', cb) 1237 1238 self._color_edge(edge)

1239

1240 - def _color_edge(self, edge, linecolor=None, textcolor=None):

1241 """ 1242 Color in an edge with the given colors. 1243 If no colors are specified, use intelligent defaults 1244 (dependant on selection, etc.) 1245 """ 1246 if not self._edgetags.has_key(edge): return 1247 c = self._chart_canvas 1248 1249 if linecolor is not None and textcolor is not None: 1250 if self._marks.has_key(edge): 1251 linecolor = self._marks[edge] 1252 tags = self._edgetags[edge] 1253 c.itemconfig(tags[0], fill=linecolor) 1254 c.itemconfig(tags[1], fill=textcolor) 1255 c.itemconfig(tags[2], fill=textcolor, 1256 outline=textcolor) 1257 c.itemconfig(tags[3], fill=textcolor) 1258 c.itemconfig(tags[4], fill=textcolor) 1259 return 1260 else: 1261 N = self._chart.num_leaves() 1262 if self._marks.has_key(edge): 1263 self._color_edge(self._marks[edge]) 1264 if (edge.is_complete() and edge.span() == (0, N)): 1265 self._color_edge(edge, '#084', '#042') 1266 elif isinstance(edge, LeafEdge): 1267 self._color_edge(edge, '#48c', '#246') 1268 else: 1269 self._color_edge(edge, '#00f', '#008')

1270

1271 - def mark_edge(self, edge, mark='#0df'):

1272 """ 1273 Mark an edge 1274 """ 1275 self._marks[edge] = mark 1276 self._color_edge(edge)

1277

1278 - def unmark_edge(self, edge=None):

1279 """ 1280 Unmark an edge (or all edges) 1281 """ 1282 if edge == None: 1283 old_marked_edges = self._marks.keys() 1284 self._marks = {} 1285 for edge in old_marked_edges: 1286 self._color_edge(edge) 1287 else: 1288 del self._marks[edge] 1289 self._color_edge(edge)

1290

1291 - def markonly_edge(self, edge, mark='#0df'):

1292 self.unmark_edge() 1293 self.mark_edge(edge, mark)

1294

1295 - def _analyze(self):

1296 """ 1297 Analyze the sentence string, to figure out how big a unit needs 1298 to be, How big the tree should be, etc. 1299 """ 1300 # Figure out the text height and the unit size. 1301 unitsize = 70 # min unitsize 1302 text_height = 0 1303 c = self._chart_canvas 1304 1305 # Check against all tokens 1306 for leaf in self._chart.leaves(): 1307 tag = c.create_text(0,0, text=repr(leaf), 1308 font=self._font, 1309 anchor='nw', justify='left') 1310 bbox = c.bbox(tag) 1311 c.delete(tag) 1312 width = bbox[2] + ChartView._LEAF_SPACING 1313 unitsize = max(width, unitsize) 1314 text_height = max(text_height, bbox[3] - bbox[1]) 1315 1316 self._unitsize = unitsize 1317 self._text_height = text_height 1318 self._sentence_height = (self._text_height + 1319 2*ChartView._MARGIN) 1320 1321 # Check against edges. 1322 for edge in self._chart.edges(): 1323 self._analyze_edge(edge) 1324 1325 # Size of chart levels 1326 self._chart_level_size = self._text_height * 2.5 1327 1328 # Default tree size.. 1329 self._tree_height = (3 * (ChartView._TREE_LEVEL_SIZE + 1330 self._text_height)) 1331 1332 # Resize the scrollregions. 1333 self._resize()

1334

1335 - def _resize(self):

1336 """ 1337 Update the scroll-regions for each canvas. This ensures that 1338 everything is within a scroll-region, so the user can use the 1339 scrollbars to view the entire display. This does I{not} 1340 resize the window. 1341 """ 1342 c = self._chart_canvas 1343 1344 # Reset the chart scroll region 1345 width = ( self._chart.num_leaves() * self._unitsize + 1346 ChartView._MARGIN * 2 ) 1347 1348 levels = len(self._edgelevels) 1349 self._chart_height = (levels+2)*self._chart_level_size 1350 c['scrollregion']=(0,0,width,self._chart_height) 1351 1352 # Reset the tree scroll region 1353 if self._tree_canvas: 1354 self._tree_canvas['scrollregion'] = (0, 0, width, 1355 self._tree_height)

1356

1357 - def _draw_loclines(self):

1358 """ 1359 Draw location lines. These are vertical gridlines used to 1360 show where each location unit is. 1361 """ 1362 BOTTOM = 50000 1363 c1 = self._tree_canvas 1364 c2 = self._sentence_canvas 1365 c3 = self._chart_canvas 1366 margin = ChartView._MARGIN 1367 self._loclines = [] 1368 for i in range(0, self._chart.num_leaves()+1): 1369 x = i*self._unitsize + margin 1370 1371 if c1: 1372 t1=c1.create_line(x, 0, x, BOTTOM) 1373 c1.tag_lower(t1) 1374 if c2: 1375 t2=c2.create_line(x, 0, x, self._sentence_height) 1376 c2.tag_lower(t2) 1377 t3=c3.create_line(x, 0, x, BOTTOM) 1378 c3.tag_lower(t3) 1379 t4=c3.create_text(x+2, 0, text=`i`, anchor='nw', 1380 font=self._font) 1381 c3.tag_lower(t4) 1382 #if i % 4 == 0: 1383 # if c1: c1.itemconfig(t1, width=2, fill='gray60') 1384 # if c2: c2.itemconfig(t2, width=2, fill='gray60') 1385 # c3.itemconfig(t3, width=2, fill='gray60') 1386 if i % 2 == 0: 1387 if c1: c1.itemconfig(t1, fill='gray60') 1388 if c2: c2.itemconfig(t2, fill='gray60') 1389 c3.itemconfig(t3, fill='gray60') 1390 else: 1391 if c1: c1.itemconfig(t1, fill='gray80') 1392 if c2: c2.itemconfig(t2, fill='gray80') 1393 c3.itemconfig(t3, fill='gray80')

1394

1395 - def _draw_sentence(self):

1396 """Draw the sentence string.""" 1397 if self._chart.num_leaves() == 0: return 1398 c = self._sentence_canvas 1399 margin = ChartView._MARGIN 1400 y = ChartView._MARGIN 1401 1402 for i, leaf in enumerate(self._chart.leaves()): 1403 x1 = i * self._unitsize + margin 1404 x2 = x1 + self._unitsize 1405 x = (x1+x2)/2 1406 tag = c.create_text(x, y, text=repr(leaf), 1407 font=self._font, 1408 anchor='n', justify='left') 1409 bbox = c.bbox(tag) 1410 rt=c.create_rectangle(x1+2, bbox[1]-(ChartView._LEAF_SPACING/2), 1411 x2-2, bbox[3]+(ChartView._LEAF_SPACING/2), 1412 fill='#f0f0f0', outline='#f0f0f0') 1413 c.tag_lower(rt)

1414

1415 - def erase_tree(self):

1416 for tag in self._tree_tags: self._tree_canvas.delete(tag) 1417 self._treetoks = [] 1418 self._treetoks_edge = None 1419 self._treetoks_index = 0

1420

1421 - def draw_tree(self, edge=None):

1422 if edge is None and self._treetoks_edge is None: return 1423 if edge is None: edge = self._treetoks_edge 1424 1425 # If it's a new edge, then get a new list of treetoks. 1426 if self._treetoks_edge != edge: 1427 self._treetoks = [t for t in self._chart.trees(edge) 1428 if isinstance(t, Tree)] 1429 self._treetoks_edge = edge 1430 self._treetoks_index = 0 1431 1432 # Make sure there's something to draw. 1433 if len(self._treetoks) == 0: return 1434 1435 # Erase the old tree. 1436 for tag in self._tree_tags: self._tree_canvas.delete(tag) 1437 1438 # Draw the new tree. 1439 tree = self._treetoks[self._treetoks_index] 1440 self._draw_treetok(tree, edge.start()) 1441 1442 # Show how many trees are available for the edge. 1443 self._draw_treecycle() 1444 1445 # Update the scroll region. 1446 w = self._chart.num_leaves()*self._unitsize+2*ChartView._MARGIN 1447 h = tree.height() * (ChartView._TREE_LEVEL_SIZE+self._text_height) 1448 self._tree_canvas['scrollregion'] = (0, 0, w, h)

1449

1450 - def cycle_tree(self):

1451 self._treetoks_index = (self._treetoks_index+1)%len(self._treetoks) 1452 self.draw_tree(self._treetoks_edge)

1453

1454 - def _draw_treecycle(self):

1455 if len(self._treetoks) <= 1: return 1456 1457 # Draw the label. 1458 label = '%d Trees' % len(self._treetoks) 1459 c = self._tree_canvas 1460 margin = ChartView._MARGIN 1461 right = self._chart.num_leaves()*self._unitsize+margin-2 1462 tag = c.create_text(right, 2, anchor='ne', text=label, 1463 font=self._boldfont) 1464 self._tree_tags.append(tag) 1465 _, _, _, y = c.bbox(tag) 1466 1467 # Draw the triangles. 1468 for i in range(len(self._treetoks)): 1469 x = right - 20*(len(self._treetoks)-i-1) 1470 if i == self._treetoks_index: fill = '#084' 1471 else: fill = '#fff' 1472 tag = c.create_polygon(x, y+10, x-5, y, x-10, y+10, 1473 fill=fill, outline='black') 1474 self._tree_tags.append(tag) 1475 1476 # Set up a callback: show the tree if they click on its 1477 # triangle. 1478 def cb(event, self=self, i=i): 1479 self._treetoks_index = i 1480 self.draw_tree()

1481 c.tag_bind(tag, '<Button-1>', cb) 1482

1483 - def _draw_treetok(self, treetok, index, depth=0):

1484 """ 1485 @param index: The index of the first leaf in the tree. 1486 @return: The index of the first leaf after the tree. 1487 """ 1488 c = self._tree_canvas 1489 margin = ChartView._MARGIN 1490 1491 # Draw the children 1492 child_xs = [] 1493 for child in treetok: 1494 if isinstance(child, Tree): 1495 child_x, index = self._draw_treetok(child, index, depth+1) 1496 child_xs.append(child_x) 1497 else: 1498 child_xs.append((2*index+1)*self._unitsize/2 + margin) 1499 index += 1 1500 1501 # If we have children, then get the node's x by averaging their 1502 # node x's. Otherwise, make room for ourselves. 1503 if child_xs: 1504 nodex = sum(child_xs)/len(child_xs) 1505 else: 1506 # [XX] breaks for null productions. 1507 nodex = (2*index+1)*self._unitsize/2 + margin 1508 index += 1 1509 1510 # Draw the node 1511 nodey = depth * (ChartView._TREE_LEVEL_SIZE + self._text_height) 1512 tag = c.create_text(nodex, nodey, anchor='n', justify='center', 1513 text=str(treetok.node), fill='#042', 1514 font=self._boldfont) 1515 self._tree_tags.append(tag) 1516 1517 # Draw lines to the children. 1518 childy = nodey + ChartView._TREE_LEVEL_SIZE + self._text_height 1519 for childx, child in zip(child_xs, treetok): 1520 if isinstance(child, Tree) and child: 1521 # A "real" tree token: 1522 tag = c.create_line(nodex, nodey + self._text_height, 1523 childx, childy, width=2, fill='#084') 1524 self._tree_tags.append(tag) 1525 if isinstance(child, Tree) and not child: 1526 # An unexpanded tree token: 1527 tag = c.create_line(nodex, nodey + self._text_height, 1528 childx, childy, width=2, 1529 fill='#048', dash='2 3') 1530 self._tree_tags.append(tag) 1531 if not isinstance(child, Tree): 1532 # A leaf: 1533 tag = c.create_line(nodex, nodey + self._text_height, 1534 childx, 10000, width=2, fill='#084') 1535 self._tree_tags.append(tag) 1536 1537 return nodex, index

1538

1539 - def draw(self):

1540 """ 1541 Draw everything (from scratch). 1542 """ 1543 if self._tree_canvas: 1544 self._tree_canvas.delete('all') 1545 self.draw_tree() 1546 1547 if self._sentence_canvas: 1548 self._sentence_canvas.delete('all') 1549 self._draw_sentence() 1550 1551 self._chart_canvas.delete('all') 1552 self._edgetags = {} 1553 1554 # Redraw any edges we erased. 1555 for lvl in range(len(self._edgelevels)): 1556 for edge in self._edgelevels[lvl]: 1557 self._draw_edge(edge, lvl) 1558 1559 for edge in self._chart: 1560 self._add_edge(edge) 1561 1562 self._draw_loclines()

1563

1564 - def add_callback(self, event, func):

1565 self._callbacks.setdefault(event,{})[func] = 1

1566

1567 - def remove_callback(self, event, func=None):

1568 if func is None: del self._callbacks[event] 1569 else: 1570 try: del self._callbacks[event][func] 1571 except: pass

1572

1573 - def _fire_callbacks(self, event, *args):

1574 if not self._callbacks.has_key(event): return 1575 for cb_func in self._callbacks[event].keys(): cb_func(*args)

1576 1577 ####################################################################### 1578 # Pseudo Earley Rule 1579 ####################################################################### 1580 # This isn't *true* Early, since it doesn't use the separate lexicon 1581 # dictionary. (I.e., it uses TopDownMatchRule instead of ScannerRule) 1582 # But it's close enough for demonstration purposes. 1583

1584 -class PseudoEarleyRule(AbstractChartRule):

1585 NUM_EDGES = 1 1586 _completer = CompleterRule() 1587 _scanner = TopDownMatchRule() 1588 _predictor = PredictorRule()

1589 - def __init__(self):

1590 self._most_recent_rule = None

1591 - def apply_iter(self, chart, grammar, edge):

1592 for e in self._predictor.apply_iter(chart, grammar, edge): 1593 self._most_recent_rule = self._predictor 1594 yield e 1595 for e in self._scanner.apply_iter(chart, grammar, edge): 1596 self._most_recent_rule = self._scanner 1597 yield e 1598 for e in self._completer.apply_iter(chart, grammar, edge): 1599 self._most_recent_rule = self._completer 1600 yield e

1601 - def __str__(self):

1602 if self._most_recent_rule is self._completer: 1603 return 'Completer Rule (aka Fundamental Rule)' 1604 elif self._most_recent_rule is self._scanner: 1605 return 'Scanner Rule (aka Top Down Match Rule)' 1606 elif self._most_recent_rule is self._predictor: 1607 return 'Predictor Rule (aka Top Down Expand Rule)' 1608 else: 1609 return 'Pseudo Earley Rule'

1610

1611 -class PseudoEarleyInitRule(TopDownInitRule):

1612 - def __str__(self):

1613 return 'Predictor Rule (aka Top Down Expand Rule)'

1614 1615 ####################################################################### 1616 # Edge Rules 1617 ####################################################################### 1618 # These version of the chart rules only apply to a specific edge. 1619 # This lets the user select an edge, and then apply a rule. 1620

1621 -class EdgeRule(object):

1622 """ 1623 To create an edge rule, make an empty base class that uses 1624 EdgeRule as the first base class, and the basic rule as the 1625 second base class. (Order matters!) 1626 """

1627 - def __init__(self, edge):

1628 super = self.__class__.__bases__[1] 1629 self._edge = edge 1630 self.NUM_EDGES = super.NUM_EDGES-1

1631 - def apply_iter(self, chart, grammar, *edges):

1632 super = self.__class__.__bases__[1] 1633 edges += (self._edge,) 1634 for e in super.apply_iter(self, chart, grammar, *edges): yield e

1635 - def __str__(self):

1636 super = self.__class__.__bases__[1] 1637 return super.__str__(self)

1638

1639 -class TopDownExpandEdgeRule(EdgeRule, TopDownExpandRule): pass

1640 -class TopDownMatchEdgeRule(EdgeRule, TopDownMatchRule): pass

1641 -class BottomUpEdgeRule(EdgeRule, BottomUpPredictRule): pass

1642 -class BottomUpInitEdgeRule(EdgeRule, BottomUpInitRule): pass

1643 -class FundamentalEdgeRule(EdgeRule, SingleEdgeFundamentalRule): pass

1644 -class PseudoEarleyEdgeRule(EdgeRule, PseudoEarleyRule): pass

1645 1646 ####################################################################### 1647 # Chart Demo 1648 ####################################################################### 1649

1650 -class ChartDemo(object):

1651 - def __init__(self, grammar, tokens, title='Chart Parsing Demo'):

1652 # Initialize the parser 1653 self._init_parser(grammar, tokens) 1654 1655 self._root = None 1656 try: 1657 # Create the root window. 1658 self._root = Tkinter.Tk() 1659 self._root.title(title) 1660 self._root.bind('<Control-q>', self.destroy) 1661 1662 # Set up some frames. 1663 frame3 = Tkinter.Frame(self._root) 1664 frame2 = Tkinter.Frame(self._root) 1665 frame1 = Tkinter.Frame(self._root) 1666 frame3.pack(side='bottom', fill='none') 1667 frame2.pack(side='bottom', fill='x') 1668 frame1.pack(side='bottom', fill='both', expand=1) 1669 1670 self._init_fonts(self._root) 1671 self._init_animation() 1672 self._init_chartview(frame1) 1673 self._init_rulelabel(frame2) 1674 self._init_buttons(frame3) 1675 self._init_menubar() 1676 1677 self._matrix = None 1678 self._results = None 1679 1680 # Set up keyboard bindings. 1681 self._init_bindings() 1682 1683 except: 1684 print 'Error creating Tree View' 1685 self.destroy() 1686 raise

1687

1688 - def destroy(self, *args):

1689 if self._root is None: return 1690 self._root.destroy() 1691 self._root = None

1692

1693 - def mainloop(self, *args, **kwargs):

1694 """ 1695 Enter the Tkinter mainloop. This function must be called if 1696 this demo is created from a non-interactive program (e.g. 1697 from a secript); otherwise, the demo will close as soon as 1698 the script completes. 1699 """ 1700 if in_idle(): return 1701 self._root.mainloop(*args, **kwargs)

1702 1703 #//////////////////////////////////////////////////////////// 1704 # Initialization Helpers 1705 #//////////////////////////////////////////////////////////// 1706

1707 - def _init_parser(self, grammar, tokens):

1708 self._grammar = grammar 1709 self._tokens = tokens 1710 self._cp = SteppingChartParser(self._grammar) 1711 self._cp.initialize(self._tokens) 1712 self._chart = self._cp.chart() 1713 1714 # The step iterator -- use this to generate new edges 1715 self._cpstep = self._cp.step() 1716 1717 # The currently selected edge 1718 self._selection = None

1719

1720 - def _init_fonts(self, root):

1721 # See: <http://www.astro.washington.edu/owen/ROTKFolklore.html> 1722 self._sysfont = tkFont.Font(font=Tkinter.Button()["font"]) 1723 root.option_add("*Font", self._sysfont) 1724 1725 # TWhat's our font size (default=same as sysfont) 1726 self._size = Tkinter.IntVar(root) 1727 self._size.set(self._sysfont.cget('size')) 1728 1729 self._boldfont = tkFont.Font(family='helvetica', weight='bold', 1730 size=self._size.get()) 1731 self._font = tkFont.Font(family='helvetica', 1732 size=self._size.get())

1733

1734 - def _init_animation(self):

1735 # Are we stepping? (default=yes) 1736 self._step = Tkinter.IntVar(self._root) 1737 self._step.set(1) 1738 1739 # What's our animation speed (default=fast) 1740 self._animate = Tkinter.IntVar(self._root) 1741 self._animate.set(3) # Default speed = fast 1742 1743 # Are we currently animating? 1744 self._animating = 0

1745

1746 - def _init_chartview(self, parent):

1747 self._cv = ChartView(self._chart, parent, 1748 draw_tree=1, draw_sentence=1) 1749 self._cv.add_callback('select', self._click_cv_edge)

1750

1751 - def _init_rulelabel(self, parent):

1752 ruletxt = 'Last edge generated by:' 1753 1754 self._rulelabel1 = Tkinter.Label(parent,text=ruletxt, 1755 font=self._boldfont) 1756 self._rulelabel2 = Tkinter.Label(parent, width=40, 1757 relief='groove', anchor='w', 1758 font=self._boldfont) 1759 self._rulelabel1.pack(side='left') 1760 self._rulelabel2.pack(side='left') 1761 step = Tkinter.Checkbutton(parent, variable=self._step, 1762 text='Step') 1763 step.pack(side='right')

1764

1765 - def _init_buttons(self, parent):

1766 frame1 = Tkinter.Frame(parent) 1767 frame2 = Tkinter.Frame(parent) 1768 frame1.pack(side='bottom', fill='x') 1769 frame2.pack(side='top', fill='none') 1770 1771 Tkinter.Button(frame1, text='Reset\nParser', 1772 background='#90c0d0', foreground='black', 1773 command=self.reset).pack(side='right') 1774 #Tkinter.Button(frame1, text='Pause', 1775 # background='#90c0d0', foreground='black', 1776 # command=self.pause).pack(side='left') 1777 1778 Tkinter.Button(frame1, text='Top Down\nStrategy', 1779 background='#90c0d0', foreground='black', 1780 command=self.top_down_strategy).pack(side='left') 1781 Tkinter.Button(frame1, text='Bottom Up\nStrategy', 1782 background='#90c0d0', foreground='black', 1783 command=self.bottom_up_strategy).pack(side='left') 1784 Tkinter.Button(frame1, text='Earley\nAlgorithm', 1785 background='#90c0d0', foreground='black', 1786 command=self.earley_algorithm).pack(side='left') 1787 1788 Tkinter.Button(frame2, text='Top Down Init\nRule', 1789 background='#90f090', foreground='black', 1790 command=self.top_down_init).pack(side='left') 1791 Tkinter.Button(frame2, text='Top Down Expand\nRule', 1792 background='#90f090', foreground='black', 1793 command=self.top_down_expand).pack(side='left') 1794 Tkinter.Button(frame2, text='Top Down Match\nRule', 1795 background='#90f090', foreground='black', 1796 command=self.top_down_match).pack(side='left') 1797 Tkinter.Frame(frame2, width=20).pack(side='left') 1798 1799 Tkinter.Button(frame2, text='Bottom Up Init\nRule', 1800 background='#90f090', foreground='black', 1801 command=self.bottom_up_init).pack(side='left') 1802 Tkinter.Button(frame2, text='Bottom Up Predict\nRule', 1803 background='#90f090', foreground='black', 1804 command=self.bottom_up).pack(side='left') 1805 Tkinter.Frame(frame2, width=20).pack(side='left') 1806 1807 Tkinter.Button(frame2, text='Fundamental\nRule', 1808 background='#90f090', foreground='black', 1809 command=self.fundamental).pack(side='left')

1810

1811 - def _init_bindings(self):

1812 self._root.bind('<Up>', self._cv.scroll_up) 1813 self._root.bind('<Down>', self._cv.scroll_down) 1814 self._root.bind('<Prior>', self._cv.page_up) 1815 self._root.bind('<Next>', self._cv.page_down) 1816 self._root.bind('<Control-q>', self.destroy) 1817 self._root.bind('<Control-x>', self.destroy) 1818 self._root.bind('<F1>', self.help) 1819 1820 self._root.bind('<Control-s>', self.save_chart) 1821 self._root.bind('<Control-o>', self.load_chart) 1822 self._root.bind('<Control-r>', self.reset) 1823 1824 self._root.bind('t', self.top_down_strategy) 1825 self._root.bind('b', self.bottom_up_strategy) 1826 self._root.bind('e', self.earley_algorithm) 1827 self._root.bind('<space>', self._stop_animation) 1828 1829 self._root.bind('<Control-g>', self.edit_grammar) 1830 self._root.bind('<Control-t>', self.edit_sentence) 1831 1832 # Animation speed control 1833 self._root.bind('-', lambda e,a=self._animate:a.set(1)) 1834 self._root.bind('=', lambda e,a=self._animate:a.set(2)) 1835 self._root.bind('+', lambda e,a=self._animate:a.set(3)) 1836 1837 # Step control 1838 self._root.bind('s', lambda e,s=self._step:s.set(not s.get()))

1839

1840 - def _init_menubar(self):

1841 menubar = Tkinter.Menu(self._root) 1842 1843 filemenu = Tkinter.Menu(menubar, tearoff=0) 1844 filemenu.add_command(label='Save Chart', underline=0, 1845 command=self.save_chart, accelerator='Ctrl-s') 1846 filemenu.add_command(label='Load Chart', underline=0, 1847 command=self.load_chart, accelerator='Ctrl-o') 1848 filemenu.add_command(label='Reset Chart', underline=0, 1849 command=self.reset, accelerator='Ctrl-r') 1850 filemenu.add_separator() 1851 filemenu.add_command(label='Save Grammar', 1852 command=self.save_grammar) 1853 filemenu.add_command(label='Load Grammar', 1854 command=self.load_grammar) 1855 filemenu.add_separator() 1856 filemenu.add_command(label='Exit', underline=1, 1857 command=self.destroy, accelerator='Ctrl-x') 1858 menubar.add_cascade(label='File', underline=0, menu=filemenu) 1859 1860 editmenu = Tkinter.Menu(menubar, tearoff=0) 1861 editmenu.add_command(label='Edit Grammar', underline=5, 1862 command=self.edit_grammar, 1863 accelerator='Ctrl-g') 1864 editmenu.add_command(label='Edit Text', underline=5, 1865 command=self.edit_sentence, 1866 accelerator='Ctrl-t') 1867 menubar.add_cascade(label='Edit', underline=0, menu=editmenu) 1868 1869 viewmenu = Tkinter.Menu(menubar, tearoff=0) 1870 viewmenu.add_command(label='Chart Matrix', underline=6, 1871 command=self.view_matrix) 1872 viewmenu.add_command(label='Results', underline=0, 1873 command=self.view_results) 1874 menubar.add_cascade(label='View', underline=0, menu=viewmenu) 1875 1876 rulemenu = Tkinter.Menu(menubar, tearoff=0) 1877 rulemenu.add_command(label='Top Down Strategy', underline=0, 1878 command=self.top_down_strategy, 1879 accelerator='t') 1880 rulemenu.add_command(label='Bottom Up Strategy', underline=0, 1881 command=self.bottom_up_strategy, 1882 accelerator='b') 1883 rulemenu.add_command(label='Earley Algorithm', underline=0, 1884 command=self.bottom_up_strategy, 1885 accelerator='e') 1886 rulemenu.add_separator() 1887 rulemenu.add_command(label='Bottom Up Init Rule', 1888 command=self.bottom_up_init) 1889 rulemenu.add_command(label='Bottom Up Rule', 1890 command=self.bottom_up) 1891 rulemenu.add_command(label='Top Down Init Rule', 1892 command=self.top_down_init) 1893 rulemenu.add_command(label='Top Down Expand Rule', 1894 command=self.top_down_expand) 1895 rulemenu.add_command(label='Top Down Match Rule', 1896 command=self.top_down_match) 1897 rulemenu.add_command(label='Fundamental Rule', 1898 command=self.fundamental) 1899 menubar.add_cascade(label='Apply', underline=0, menu=rulemenu) 1900 1901 animatemenu = Tkinter.Menu(menubar, tearoff=0) 1902 animatemenu.add_checkbutton(label="Step", underline=0, 1903 variable=self._step, 1904 accelerator='s') 1905 animatemenu.add_separator() 1906 animatemenu.add_radiobutton(label="No Animation", underline=0, 1907 variable=self._animate, value=0) 1908 animatemenu.add_radiobutton(label="Slow Animation", underline=0, 1909 variable=self._animate, value=1, 1910 accelerator='-') 1911 animatemenu.add_radiobutton(label="Normal Animation", underline=0, 1912 variable=self._animate, value=2, 1913 accelerator='=') 1914 animatemenu.add_radiobutton(label="Fast Animation", underline=0, 1915 variable=self._animate, value=3, 1916 accelerator='+') 1917 menubar.add_cascade(label="Animate", underline=1, menu=animatemenu) 1918 1919 zoommenu = Tkinter.Menu(menubar, tearoff=0) 1920 zoommenu.add_radiobutton(label='Tiny', variable=self._size, 1921 underline=0, value=10, command=self.resize) 1922 zoommenu.add_radiobutton(label='Small', variable=self._size, 1923 underline=0, value=12, command=self.resize) 1924 zoommenu.add_radiobutton(label='Medium', variable=self._size, 1925 underline=0, value=14, command=self.resize) 1926 zoommenu.add_radiobutton(label='Large', variable=self._size, 1927 underline=0, value=18, command=self.resize) 1928 zoommenu.add_radiobutton(label='Huge', variable=self._size, 1929 underline=0, value=24, command=self.resize) 1930 menubar.add_cascade(label='Zoom', underline=0, menu=zoommenu) 1931 1932 helpmenu = Tkinter.Menu(menubar, tearoff=0) 1933 helpmenu.add_command(label='About', underline=0, 1934 command=self.about) 1935 helpmenu.add_command(label='Instructions', underline=0, 1936 command=self.help, accelerator='F1') 1937 menubar.add_cascade(label='Help', underline=0, menu=helpmenu) 1938 1939 self._root.config(menu=menubar)

1940 1941 #//////////////////////////////////////////////////////////// 1942 # Selection Handling 1943 #//////////////////////////////////////////////////////////// 1944

1945 - def _click_cv_edge(self, edge):

1946 if edge != self._selection: 1947 # Clicking on a new edge selects it. 1948 self._select_edge(edge) 1949 else: 1950 # Repeated clicks on one edge cycle its trees. 1951 self._cv.cycle_tree()

1952 # [XX] this can get confused if animation is running 1953 # faster than the callbacks... 1954

1955 - def _select_matrix_edge(self, edge):

1956 self._select_edge(edge) 1957 self._cv.view_edge(edge)

1958

1959 - def _select_edge(self, edge):

1960 self._selection = edge 1961 # Update the chart view. 1962 self._cv.markonly_edge(edge, '#f00') 1963 self._cv.draw_tree(edge) 1964 # Update the matrix view. 1965 if self._matrix: self._matrix.markonly_edge(edge) 1966 if self._matrix: self._matrix.view_edge(edge)

1967

1968 - def _deselect_edge(self):

1969 self._selection = None 1970 # Update the chart view. 1971 self._cv.unmark_edge() 1972 self._cv.erase_tree() 1973 # Update the matrix view 1974 if self._matrix: self._matrix.unmark_edge()

1975

1976 - def _show_new_edge(self, edge):

1977 self._display_rule(self._cp.current_chartrule()) 1978 # Update the chart view. 1979 self._cv.update() 1980 self._cv.draw_tree(edge) 1981 self._cv.markonly_edge(edge, '#0df') 1982 self._cv.view_edge(edge) 1983 # Update the matrix view. 1984 if self._matrix: self._matrix.update() 1985 if self._matrix: self._matrix.markonly_edge(edge) 1986 if self._matrix: self._matrix.view_edge(edge) 1987 # Update the results view. 1988 if self._results: self._results.update(edge)

1989 1990 #//////////////////////////////////////////////////////////// 1991 # Help/usage 1992 #//////////////////////////////////////////////////////////// 1993

1994 - def help(self, *e):

1995 self._animating = 0 1996 # The default font's not very legible; try using 'fixed' instead. 1997 try: 1998 ShowText(self._root, 'Help: Chart Parser Demo', 1999 (__doc__).strip(), width=75, font='fixed') 2000 except: 2001 ShowText(self._root, 'Help: Chart Parser Demo', 2002 (__doc__).strip(), width=75)

2003

2004 - def about(self, *e):

2005 ABOUT = ("NLTK Chart Parser Demo\n"+ 2006 "Written by Edward Loper") 2007 tkMessageBox.showinfo('About: Chart Parser Demo', ABOUT)

2008 2009 #//////////////////////////////////////////////////////////// 2010 # File Menu 2011 #//////////////////////////////////////////////////////////// 2012 2013 CHART_FILE_TYPES = [('Pickle file', '.pickle'), 2014 ('All files', '*')] 2015 GRAMMAR_FILE_TYPES = [('Plaintext grammar file', '.cfg'), 2016 ('Pickle file', '.pickle'), 2017 ('All files', '*')] 2018

2019 - def load_chart(self, *args):

2020 "Load a chart from a pickle file" 2021 filename = askopenfilename(filetypes=self.CHART_FILE_TYPES, 2022 defaultextension='.pickle') 2023 if not filename: return 2024 try: 2025 chart = pickle.load(open(filename, 'r')) 2026 self._chart = chart 2027 self._cv.update(chart) 2028 if self._matrix: self._matrix.set_chart(chart) 2029 if self._matrix: self._matrix.deselect_cell() 2030 if self._results: self._results.set_chart(chart) 2031 self._cp.set_chart(chart) 2032 except Exception, e: 2033 raise 2034 tkMessageBox.showerror('Error Loading Chart', 2035 'Unable to open file: %r' % filename)

2036

2037 - def save_chart(self, *args):

2038 "Save a chart to a pickle file" 2039 filename = asksaveasfilename(filetypes=self.CHART_FILE_TYPES, 2040 defaultextension='.pickle') 2041 if not filename: return 2042 try: 2043 pickle.dump(self._chart, open(filename, 'w')) 2044 except Exception, e: 2045 raise 2046 tkMessageBox.showerror('Error Saving Chart', 2047 'Unable to open file: %r' % filename)

2048

2049 - def load_grammar(self, *args):

2050 "Load a grammar from a pickle file" 2051 filename = askopenfilename(filetypes=self.GRAMMAR_FILE_TYPES, 2052 defaultextension='.cfg') 2053 if not filename: return 2054 try: 2055 if filename.endswith('.pickle'): 2056 grammar = pickle.load(open(filename, 'r')) 2057 else: 2058 grammar = cfg.parse_cfg(open(filename, 'r').read()) 2059 self.set_grammar(grammar) 2060 except Exception, e: 2061 tkMessageBox.showerror('Error Loading Grammar', 2062 'Unable to open file: %r' % filename)

2063

2064 - def save_grammar(self, *args):

2065 filename = asksaveasfilename(filetypes=self.GRAMMAR_FILE_TYPES, 2066 defaultextension='.cfg') 2067 if not filename: return 2068 try: 2069 if filename.endswith('.pickle'): 2070 pickle.dump((self._chart, self._tokens), open(filename, 'w')) 2071 else: 2072 file = open(filename, 'w') 2073 prods = self._grammar.productions() 2074 start = [p for p in prods if p.lhs() == self._grammar.start()] 2075 rest = [p for p in prods if p.lhs() != self._grammar.start()] 2076 for prod in start: file.write('%s\n' % prod) 2077 for prod in rest: file.write('%s\n' % prod) 2078 file.close() 2079 except Exception, e: 2080 tkMessageBox.showerror('Error Saving Grammar', 2081 'Unable to open file: %r' % filename)

2082

2083 - def reset(self, *args):

2084 self._animating = 0 2085 self._cp = SteppingChartParser(self._grammar) 2086 self._cp.initialize(self._tokens) 2087 self._chart = self._cp.chart() 2088 self._cv.update(self._chart) 2089 if self._matrix: self._matrix.set_chart(self._chart) 2090 if self._matrix: self._matrix.deselect_cell() 2091 if self._results: self._results.set_chart(self._chart) 2092 self._cpstep = self._cp.step()

2093 2094 #//////////////////////////////////////////////////////////// 2095 # Edit 2096 #//////////////////////////////////////////////////////////// 2097

2098 - def edit_grammar(self, *e):

2099 CFGEditor(self._root, self._grammar, self.set_grammar)

2100

2101 - def set_grammar(self, grammar):

2102 self._grammar = grammar 2103 self._cp.set_grammar(grammar) 2104 if self._results: self._results.set_grammar(grammar)

2105

2106 - def edit_sentence(self, *e):

2107 sentence = string.join(self._tokens) 2108 title = 'Edit Text' 2109 instr = 'Enter a new sentence to parse.' 2110 EntryDialog(self._root, sentence, instr, self.set_sentence, title)

2111

2112 - def set_sentence(self, sentence):

2113 self._tokens = list(sentence.split()) 2114 self.reset()

2115 2116 #//////////////////////////////////////////////////////////// 2117 # View Menu 2118 #//////////////////////////////////////////////////////////// 2119

2120 - def view_matrix(self, *e):

2121 if self._matrix is not None: self._matrix.destroy() 2122 self._matrix = ChartMatrixView(self._root, self._chart) 2123 self._matrix.add_callback('select', self._select_matrix_edge)

2124

2125 - def view_results(self, *e):

2126 if self._results is not None: self._results.destroy() 2127 self._results = ChartResultsView(self._root, self._chart, 2128 self._grammar)

2129 2130 #//////////////////////////////////////////////////////////// 2131 # Zoom Menu 2132 #//////////////////////////////////////////////////////////// 2133

2134 - def resize(self):

2135 self._animating = 0 2136 self.set_font_size(self._size.get())

2137

2138 - def set_font_size(self, size):

2139 self._cv.set_font_size(size) 2140 self._font.configure(size=-abs(size)) 2141 self._boldfont.configure(size=-abs(size)) 2142 self._sysfont.configure(size=-abs(size))

2143

2144 - def get_font_size(self):

2145 return abs(self._size.get())

2146 2147 #//////////////////////////////////////////////////////////// 2148 # Parsing 2149 #//////////////////////////////////////////////////////////// 2150

2151 - def apply_strategy(self, strategy, edge_strategy=None):

2152 # If we're animating, then stop. 2153 if self._animating: 2154 self._animating = 0 2155 return 2156 2157 # Clear the rule display & mark. 2158 self._display_rule(None) 2159 #self._cv.unmark_edge() 2160 2161 if self._step.get(): 2162 selection = self._selection 2163 if (selection is not None) and (edge_strategy is not None): 2164 # Apply the given strategy to the selected edge. 2165 self._cp.set_strategy([edge_strategy(selection)]) 2166 newedge = self._apply_strategy() 2167 2168 # If it failed, then clear the selection. 2169 if newedge is None: 2170 self._cv.unmark_edge() 2171 self._selection = None 2172 else: 2173 self._cp.set_strategy(strategy) 2174 self._apply_strategy() 2175 2176 else: 2177 self._cp.set_strategy(strategy) 2178 if self._animate.get(): 2179 self._animating = 1 2180 self._animate_strategy() 2181 else: 2182 for edge in self._cpstep: 2183 if edge is None: break 2184 self._cv.update() 2185 if self._matrix: self._matrix.update() 2186 if self._results: self._results.update()

2187

2188 - def _stop_animation(self, *e):

2189 self._animating = 0

2190

2191 - def _animate_strategy(self, speed=1):

2192 if self._animating == 0: return 2193 if self._apply_strategy() is not None: 2194 if self._animate.get() == 0 or self._step.get() == 1: 2195 return 2196 if self._animate.get() == 1: 2197 self._root.after(3000, self._animate_strategy) 2198 elif self._animate.get() == 2: 2199 self._root.after(1000, self._animate_strategy) 2200 else: 2201 self._root.after(20, self._animate_strategy)

2202

2203 - def _apply_strategy(self):

2204 new_edge = self._cpstep.next() 2205 2206 if new_edge is not None: 2207 self._show_new_edge(new_edge) 2208 return new_edge

2209

2210 - def _display_rule(self, rule):

2211 if rule == None: 2212 self._rulelabel2['text'] = '' 2213 else: 2214 name = str(rule) 2215 self._rulelabel2['text'] = name 2216 size = self._cv.get_font_size()

2217 2218 #//////////////////////////////////////////////////////////// 2219 # Parsing Strategies 2220 #//////////////////////////////////////////////////////////// 2221 2222 # Basic rules: 2223 _TD_INIT = [TopDownInitRule()] 2224 _TD_EXPAND = [TopDownExpandRule()] 2225 _TD_MATCH = [TopDownMatchRule()] 2226 _BU_INIT = [BottomUpInitRule()] 2227 _BU_RULE = [BottomUpPredictRule()] 2228 _FUNDAMENTAL = [SingleEdgeFundamentalRule()] 2229 _EARLEY = [PseudoEarleyRule()] 2230 _EARLEY_INIT = [PseudoEarleyInitRule()] 2231 2232 # Complete strategies: 2233 _TD_STRATEGY = _TD_INIT + _TD_EXPAND + _TD_MATCH + _FUNDAMENTAL 2234 _BU_STRATEGY = _BU_INIT + _BU_RULE + _FUNDAMENTAL 2235 _EARLEY = _EARLEY_INIT + _EARLEY 2236 2237 # Button callback functions:

2238 - def top_down_init(self, *e):

2239 self.apply_strategy(self._TD_INIT, None)

2240 - def top_down_expand(self, *e):

2241 self.apply_strategy(self._TD_EXPAND, TopDownExpandEdgeRule)

2242 - def top_down_match(self, *e):

2243 self.apply_strategy(self._TD_MATCH, TopDownMatchEdgeRule)

2244 - def bottom_up_init(self, *e):

2245 self.apply_strategy(self._BU_INIT, BottomUpInitEdgeRule)

2246 - def bottom_up(self, *e):

2247 self.apply_strategy(self._BU_RULE, BottomUpEdgeRule)

2248 - def fundamental(self, *e):

2249 self.apply_strategy(self._FUNDAMENTAL, FundamentalEdgeRule)

2250 - def bottom_up_strategy(self, *e):

2251 self.apply_strategy(self._BU_STRATEGY, BottomUpEdgeRule)

2252 - def top_down_strategy(self, *e):

2253 self.apply_strategy(self._TD_STRATEGY, TopDownExpandEdgeRule)

2254 - def earley_algorithm(self, *e):

2255 self.apply_strategy(self._EARLEY, PseudoEarleyEdgeRule)

2256

2257 -def demo():

2258 grammar = cfg.parse_cfg(""" 2259 # Grammatical productions. 2260 S -> NP VP 2261 VP -> VP PP | V NP | V 2262 NP -> Det N | NP PP 2263 PP -> P NP 2264 # Lexical productions. 2265 NP -> 'John' | 'I' 2266 Det -> 'the' | 'my' | 'a' 2267 N -> 'dog' | 'cookie' | 'table' | 'cake' | 'fork' 2268 V -> 'ate' | 'saw' 2269 P -> 'on' | 'under' | 'with' 2270 """) 2271 2272 sent = 'John ate the cake on the table with a fork' 2273 sent = 'John ate the cake on the table' 2274 tokens = list(sent.split()) 2275 2276 print 'grammar= (' 2277 for rule in grammar.productions(): 2278 print ' ', repr(rule)+',' 2279 print ')' 2280 print 'tokens = %r' % tokens 2281 print 'Calling "ChartDemo(grammar, tokens)"...' 2282 ChartDemo(grammar, tokens).mainloop()

2283 2284 if __name__ == '__main__': 2285 demo() 2286 2287 # Chart comparer: 2288 #charts = ['/tmp/earley.pickle', 2289 # '/tmp/topdown.pickle', 2290 # '/tmp/bottomup.pickle'] 2291 #ChartComparer(*charts).mainloop() 2292 2293 #import profile 2294 #profile.run('demo2()', '/tmp/profile.out') 2295 #import pstats 2296 #p = pstats.Stats('/tmp/profile.out') 2297 #p.strip_dirs().sort_stats('time', 'cum').print_stats(60) 2298 #p.strip_dirs().sort_stats('cum', 'time').print_stats(60) 2299

Source Code for Module nltk.draw.chart