1# Natural Language Toolkit: Chart Parser Application 2# 3# Copyright (C) 2001-2019 NLTK Project 4# Author: Edward Loper <edloper@gmail.com> 5# Jean Mark Gawron <gawron@mail.sdsu.edu> 6# Steven Bird <stevenbird1@gmail.com> 7# URL: <http://nltk.org/> 8# For license information, see LICENSE.TXT 9 10""" 11A graphical tool for exploring chart parsing. 12 13Chart parsing is a flexible parsing algorithm that uses a data 14structure called a "chart" to record hypotheses about syntactic 15constituents. Each hypothesis is represented by a single "edge" on 16the chart. A set of "chart rules" determine when new edges can be 17added to the chart. This set of rules controls the overall behavior 18of the parser (e.g. whether it parses top-down or bottom-up). 19 20The chart parsing tool demonstrates the process of parsing a single 21sentence, with a given grammar and lexicon. Its display is divided 22into three sections: the bottom section displays the chart; the middle 23section displays the sentence; and the top section displays the 24partial syntax tree corresponding to the selected edge. Buttons along 25the bottom of the window are used to control the execution of the 26algorithm. 27 28The chart parsing tool allows for flexible control of the parsing 29algorithm. At each step of the algorithm, you can select which rule 30or strategy you wish to apply. This allows you to experiment with 31mixing different strategies (e.g. top-down and bottom-up). You can 32exercise fine-grained control over the algorithm by selecting which 33edge you wish to apply a rule to. 34""" 35 36# At some point, we should rewrite this tool to use the new canvas 37# widget system. 38 39 40from __future__ import division 41import pickle 42import os.path 43 44from six.moves.tkinter import ( 45 Button, 46 Canvas, 47 Checkbutton, 48 Frame, 49 IntVar, 50 Label, 51 Menu, 52 Scrollbar, 53 Tk, 54 Toplevel, 55) 56from six.moves.tkinter_font import Font 57from six.moves.tkinter_messagebox import showerror, showinfo 58from six.moves.tkinter_tkfiledialog import asksaveasfilename, askopenfilename 59 60from nltk.parse.chart import ( 61 BottomUpPredictCombineRule, 62 BottomUpPredictRule, 63 Chart, 64 LeafEdge, 65 LeafInitRule, 66 SingleEdgeFundamentalRule, 67 SteppingChartParser, 68 TopDownInitRule, 69 TopDownPredictRule, 70 TreeEdge, 71) 72from nltk.tree import Tree 73from nltk.grammar import Nonterminal, CFG 74from nltk.util import in_idle 75from nltk.draw.util import ( 76 CanvasFrame, 77 ColorizedList, 78 EntryDialog, 79 MutableOptionMenu, 80 ShowText, 81 SymbolWidget, 82) 83from nltk.draw import CFGEditor, tree_to_treesegment, TreeSegmentWidget 84 85# Known bug: ChartView doesn't handle edges generated by epsilon 86# productions (e.g., [Production: PP -> ]) very well. 87 88####################################################################### 89# Edge List 90####################################################################### 91 92 93class EdgeList(ColorizedList): 94 ARROW = SymbolWidget.SYMBOLS['rightarrow'] 95 96 def _init_colortags(self, textwidget, options): 97 textwidget.tag_config('terminal', foreground='#006000') 98 textwidget.tag_config('arrow', font='symbol', underline='0') 99 textwidget.tag_config('dot', foreground='#000000') 100 textwidget.tag_config( 101 'nonterminal', foreground='blue', font=('helvetica', -12, 'bold') 102 ) 103 104 def _item_repr(self, item): 105 contents = [] 106 contents.append(('%s\t' % item.lhs(), 'nonterminal')) 107 contents.append((self.ARROW, 'arrow')) 108 for i, elt in enumerate(item.rhs()): 109 if i == item.dot(): 110 contents.append((' *', 'dot')) 111 if isinstance(elt, Nonterminal): 112 contents.append((' %s' % elt.symbol(), 'nonterminal')) 113 else: 114 contents.append((' %r' % elt, 'terminal')) 115 if item.is_complete(): 116 contents.append((' *', 'dot')) 117 return contents 118 119 120####################################################################### 121# Chart Matrix View 122####################################################################### 123 124 125class ChartMatrixView(object): 126 """ 127 A view of a chart that displays the contents of the corresponding matrix. 128 """ 129 130 def __init__( 131 self, parent, chart, toplevel=True, title='Chart Matrix', show_numedges=False 132 ): 133 self._chart = chart 134 self._cells = [] 135 self._marks = [] 136 137 self._selected_cell = None 138 139 if toplevel: 140 self._root = Toplevel(parent) 141 self._root.title(title) 142 self._root.bind('<Control-q>', self.destroy) 143 self._init_quit(self._root) 144 else: 145 self._root = Frame(parent) 146 147 self._init_matrix(self._root) 148 self._init_list(self._root) 149 if show_numedges: 150 self._init_numedges(self._root) 151 else: 152 self._numedges_label = None 153 154 self._callbacks = {} 155 156 self._num_edges = 0 157 158 self.draw() 159 160 def _init_quit(self, root): 161 quit = Button(root, text='Quit', command=self.destroy) 162 quit.pack(side='bottom', expand=0, fill='none') 163 164 def _init_matrix(self, root): 165 cframe = Frame(root, border=2, relief='sunken') 166 cframe.pack(expand=0, fill='none', padx=1, pady=3, side='top') 167 self._canvas = Canvas(cframe, width=200, height=200, background='white') 168 self._canvas.pack(expand=0, fill='none') 169 170 def _init_numedges(self, root): 171 self._numedges_label = Label(root, text='0 edges') 172 self._numedges_label.pack(expand=0, fill='none', side='top') 173 174 def _init_list(self, root): 175 self._list = EdgeList(root, [], width=20, height=5) 176 self._list.pack(side='top', expand=1, fill='both', pady=3) 177 178 def cb(edge, self=self): 179 self._fire_callbacks('select', edge) 180 181 self._list.add_callback('select', cb) 182 self._list.focus() 183 184 def destroy(self, *e): 185 if self._root is None: 186 return 187 try: 188 self._root.destroy() 189 except: 190 pass 191 self._root = None 192 193 def set_chart(self, chart): 194 if chart is not self._chart: 195 self._chart = chart 196 self._num_edges = 0 197 self.draw() 198 199 def update(self): 200 if self._root is None: 201 return 202 203 # Count the edges in each cell 204 N = len(self._cells) 205 cell_edges = [[0 for i in range(N)] for j in range(N)] 206 for edge in self._chart: 207 cell_edges[edge.start()][edge.end()] += 1 208 209 # Color the cells correspondingly. 210 for i in range(N): 211 for j in range(i, N): 212 if cell_edges[i][j] == 0: 213 color = 'gray20' 214 else: 215 color = '#00%02x%02x' % ( 216 min(255, 50 + 128 * cell_edges[i][j] / 10), 217 max(0, 128 - 128 * cell_edges[i][j] / 10), 218 ) 219 cell_tag = self._cells[i][j] 220 self._canvas.itemconfig(cell_tag, fill=color) 221 if (i, j) == self._selected_cell: 222 self._canvas.itemconfig(cell_tag, outline='#00ffff', width=3) 223 self._canvas.tag_raise(cell_tag) 224 else: 225 self._canvas.itemconfig(cell_tag, outline='black', width=1) 226 227 # Update the edge list. 228 edges = list(self._chart.select(span=self._selected_cell)) 229 self._list.set(edges) 230 231 # Update our edge count. 232 self._num_edges = self._chart.num_edges() 233 if self._numedges_label is not None: 234 self._numedges_label['text'] = '%d edges' % self._num_edges 235 236 def activate(self): 237 self._canvas.itemconfig('inactivebox', state='hidden') 238 self.update() 239 240 def inactivate(self): 241 self._canvas.itemconfig('inactivebox', state='normal') 242 self.update() 243 244 def add_callback(self, event, func): 245 self._callbacks.setdefault(event, {})[func] = 1 246 247 def remove_callback(self, event, func=None): 248 if func is None: 249 del self._callbacks[event] 250 else: 251 try: 252 del self._callbacks[event][func] 253 except: 254 pass 255 256 def _fire_callbacks(self, event, *args): 257 if event not in self._callbacks: 258 return 259 for cb_func in list(self._callbacks[event].keys()): 260 cb_func(*args) 261 262 def select_cell(self, i, j): 263 if self._root is None: 264 return 265 266 # If the cell is already selected (and the chart contents 267 # haven't changed), then do nothing. 268 if (i, j) == self._selected_cell and self._chart.num_edges() == self._num_edges: 269 return 270 271 self._selected_cell = (i, j) 272 self.update() 273 274 # Fire the callback. 275 self._fire_callbacks('select_cell', i, j) 276 277 def deselect_cell(self): 278 if self._root is None: 279 return 280 self._selected_cell = None 281 self._list.set([]) 282 self.update() 283 284 def _click_cell(self, i, j): 285 if self._selected_cell == (i, j): 286 self.deselect_cell() 287 else: 288 self.select_cell(i, j) 289 290 def view_edge(self, edge): 291 self.select_cell(*edge.span()) 292 self._list.view(edge) 293 294 def mark_edge(self, edge): 295 if self._root is None: 296 return 297 self.select_cell(*edge.span()) 298 self._list.mark(edge) 299 300 def unmark_edge(self, edge=None): 301 if self._root is None: 302 return 303 self._list.unmark(edge) 304 305 def markonly_edge(self, edge): 306 if self._root is None: 307 return 308 self.select_cell(*edge.span()) 309 self._list.markonly(edge) 310 311 def draw(self): 312 if self._root is None: 313 return 314 LEFT_MARGIN = BOT_MARGIN = 15 315 TOP_MARGIN = 5 316 c = self._canvas 317 c.delete('all') 318 N = self._chart.num_leaves() + 1 319 dx = (int(c['width']) - LEFT_MARGIN) / N 320 dy = (int(c['height']) - TOP_MARGIN - BOT_MARGIN) / N 321 322 c.delete('all') 323 324 # Labels and dotted lines 325 for i in range(N): 326 c.create_text( 327 LEFT_MARGIN - 2, i * dy + dy / 2 + TOP_MARGIN, text=repr(i), anchor='e' 328 ) 329 c.create_text( 330 i * dx + dx / 2 + LEFT_MARGIN, 331 N * dy + TOP_MARGIN + 1, 332 text=repr(i), 333 anchor='n', 334 ) 335 c.create_line( 336 LEFT_MARGIN, 337 dy * (i + 1) + TOP_MARGIN, 338 dx * N + LEFT_MARGIN, 339 dy * (i + 1) + TOP_MARGIN, 340 dash='.', 341 ) 342 c.create_line( 343 dx * i + LEFT_MARGIN, 344 TOP_MARGIN, 345 dx * i + LEFT_MARGIN, 346 dy * N + TOP_MARGIN, 347 dash='.', 348 ) 349 350 # A box around the whole thing 351 c.create_rectangle( 352 LEFT_MARGIN, TOP_MARGIN, LEFT_MARGIN + dx * N, dy * N + TOP_MARGIN, width=2 353 ) 354 355 # Cells 356 self._cells = [[None for i in range(N)] for j in range(N)] 357 for i in range(N): 358 for j in range(i, N): 359 t = c.create_rectangle( 360 j * dx + LEFT_MARGIN, 361 i * dy + TOP_MARGIN, 362 (j + 1) * dx + LEFT_MARGIN, 363 (i + 1) * dy + TOP_MARGIN, 364 fill='gray20', 365 ) 366 self._cells[i][j] = t 367 368 def cb(event, self=self, i=i, j=j): 369 self._click_cell(i, j) 370 371 c.tag_bind(t, '<Button-1>', cb) 372 373 # Inactive box 374 xmax, ymax = int(c['width']), int(c['height']) 375 t = c.create_rectangle( 376 -100, 377 -100, 378 xmax + 100, 379 ymax + 100, 380 fill='gray50', 381 state='hidden', 382 tag='inactivebox', 383 ) 384 c.tag_lower(t) 385 386 # Update the cells. 387 self.update() 388 389 def pack(self, *args, **kwargs): 390 self._root.pack(*args, **kwargs) 391 392 393####################################################################### 394# Chart Results View 395####################################################################### 396 397 398class ChartResultsView(object): 399 def __init__(self, parent, chart, grammar, toplevel=True): 400 self._chart = chart 401 self._grammar = grammar 402 self._trees = [] 403 self._y = 10 404 self._treewidgets = [] 405 self._selection = None 406 self._selectbox = None 407 408 if toplevel: 409 self._root = Toplevel(parent) 410 self._root.title('Chart Parser Application: Results') 411 self._root.bind('<Control-q>', self.destroy) 412 else: 413 self._root = Frame(parent) 414 415 # Buttons 416 if toplevel: 417 buttons = Frame(self._root) 418 buttons.pack(side='bottom', expand=0, fill='x') 419 Button(buttons, text='Quit', command=self.destroy).pack(side='right') 420 Button(buttons, text='Print All', command=self.print_all).pack(side='left') 421 Button(buttons, text='Print Selection', command=self.print_selection).pack( 422 side='left' 423 ) 424 425 # Canvas frame. 426 self._cframe = CanvasFrame(self._root, closeenough=20) 427 self._cframe.pack(side='top', expand=1, fill='both') 428 429 # Initial update 430 self.update() 431 432 def update(self, edge=None): 433 if self._root is None: 434 return 435 # If the edge isn't a parse edge, do nothing. 436 if edge is not None: 437 if edge.lhs() != self._grammar.start(): 438 return 439 if edge.span() != (0, self._chart.num_leaves()): 440 return 441 442 for parse in self._chart.parses(self._grammar.start()): 443 if parse not in self._trees: 444 self._add(parse) 445 446 def _add(self, parse): 447 # Add it to self._trees. 448 self._trees.append(parse) 449 450 # Create a widget for it. 451 c = self._cframe.canvas() 452 treewidget = tree_to_treesegment(c, parse) 453 454 # Add it to the canvas frame. 455 self._treewidgets.append(treewidget) 456 self._cframe.add_widget(treewidget, 10, self._y) 457 458 # Register callbacks. 459 treewidget.bind_click(self._click) 460 461 # Update y. 462 self._y = treewidget.bbox()[3] + 10 463 464 def _click(self, widget): 465 c = self._cframe.canvas() 466 if self._selection is not None: 467 c.delete(self._selectbox) 468 self._selection = widget 469 (x1, y1, x2, y2) = widget.bbox() 470 self._selectbox = c.create_rectangle(x1, y1, x2, y2, width=2, outline='#088') 471 472 def _color(self, treewidget, color): 473 treewidget.label()['color'] = color 474 for child in treewidget.subtrees(): 475 if isinstance(child, TreeSegmentWidget): 476 self._color(child, color) 477 else: 478 child['color'] = color 479 480 def print_all(self, *e): 481 if self._root is None: 482 return 483 self._cframe.print_to_file() 484 485 def print_selection(self, *e): 486 if self._root is None: 487 return 488 if self._selection is None: 489 showerror('Print Error', 'No tree selected') 490 else: 491 c = self._cframe.canvas() 492 for widget in self._treewidgets: 493 if widget is not self._selection: 494 self._cframe.destroy_widget(widget) 495 c.delete(self._selectbox) 496 (x1, y1, x2, y2) = self._selection.bbox() 497 self._selection.move(10 - x1, 10 - y1) 498 c['scrollregion'] = '0 0 %s %s' % (x2 - x1 + 20, y2 - y1 + 20) 499 self._cframe.print_to_file() 500 501 # Restore our state. 502 self._treewidgets = [self._selection] 503 self.clear() 504 self.update() 505 506 def clear(self): 507 if self._root is None: 508 return 509 for treewidget in self._treewidgets: 510 self._cframe.destroy_widget(treewidget) 511 self._trees = [] 512 self._treewidgets = [] 513 if self._selection is not None: 514 self._cframe.canvas().delete(self._selectbox) 515 self._selection = None 516 self._y = 10 517 518 def set_chart(self, chart): 519 self.clear() 520 self._chart = chart 521 self.update() 522 523 def set_grammar(self, grammar): 524 self.clear() 525 self._grammar = grammar 526 self.update() 527 528 def destroy(self, *e): 529 if self._root is None: 530 return 531 try: 532 self._root.destroy() 533 except: 534 pass 535 self._root = None 536 537 def pack(self, *args, **kwargs): 538 self._root.pack(*args, **kwargs) 539 540 541####################################################################### 542# Chart Comparer 543####################################################################### 544 545 546class ChartComparer(object): 547 """ 548 549 :ivar _root: The root window 550 551 :ivar _charts: A dictionary mapping names to charts. When 552 charts are loaded, they are added to this dictionary. 553 554 :ivar _left_chart: The left ``Chart``. 555 :ivar _left_name: The name ``_left_chart`` (derived from filename) 556 :ivar _left_matrix: The ``ChartMatrixView`` for ``_left_chart`` 557 :ivar _left_selector: The drop-down ``MutableOptionsMenu`` used 558 to select ``_left_chart``. 559 560 :ivar _right_chart: The right ``Chart``. 561 :ivar _right_name: The name ``_right_chart`` (derived from filename) 562 :ivar _right_matrix: The ``ChartMatrixView`` for ``_right_chart`` 563 :ivar _right_selector: The drop-down ``MutableOptionsMenu`` used 564 to select ``_right_chart``. 565 566 :ivar _out_chart: The out ``Chart``. 567 :ivar _out_name: The name ``_out_chart`` (derived from filename) 568 :ivar _out_matrix: The ``ChartMatrixView`` for ``_out_chart`` 569 :ivar _out_label: The label for ``_out_chart``. 570 571 :ivar _op_label: A Label containing the most recent operation. 572 """ 573 574 _OPSYMBOL = { 575 '-': '-', 576 'and': SymbolWidget.SYMBOLS['intersection'], 577 'or': SymbolWidget.SYMBOLS['union'], 578 } 579 580 def __init__(self, *chart_filenames): 581 # This chart is displayed when we don't have a value (eg 582 # before any chart is loaded). 583 faketok = [''] * 8 584 self._emptychart = Chart(faketok) 585 586 # The left & right charts start out empty. 587 self._left_name = 'None' 588 self._right_name = 'None' 589 self._left_chart = self._emptychart 590 self._right_chart = self._emptychart 591 592 # The charts that have been loaded. 593 self._charts = {'None': self._emptychart} 594 595 # The output chart. 596 self._out_chart = self._emptychart 597 598 # The most recent operation 599 self._operator = None 600 601 # Set up the root window. 602 self._root = Tk() 603 self._root.title('Chart Comparison') 604 self._root.bind('<Control-q>', self.destroy) 605 self._root.bind('<Control-x>', self.destroy) 606 607 # Initialize all widgets, etc. 608 self._init_menubar(self._root) 609 self._init_chartviews(self._root) 610 self._init_divider(self._root) 611 self._init_buttons(self._root) 612 self._init_bindings(self._root) 613 614 # Load any specified charts. 615 for filename in chart_filenames: 616 self.load_chart(filename) 617 618 def destroy(self, *e): 619 if self._root is None: 620 return 621 try: 622 self._root.destroy() 623 except: 624 pass 625 self._root = None 626 627 def mainloop(self, *args, **kwargs): 628 return 629 self._root.mainloop(*args, **kwargs) 630 631 # //////////////////////////////////////////////////////////// 632 # Initialization 633 # //////////////////////////////////////////////////////////// 634 635 def _init_menubar(self, root): 636 menubar = Menu(root) 637 638 # File menu 639 filemenu = Menu(menubar, tearoff=0) 640 filemenu.add_command( 641 label='Load Chart', 642 accelerator='Ctrl-o', 643 underline=0, 644 command=self.load_chart_dialog, 645 ) 646 filemenu.add_command( 647 label='Save Output', 648 accelerator='Ctrl-s', 649 underline=0, 650 command=self.save_chart_dialog, 651 ) 652 filemenu.add_separator() 653 filemenu.add_command( 654 label='Exit', underline=1, command=self.destroy, accelerator='Ctrl-x' 655 ) 656 menubar.add_cascade(label='File', underline=0, menu=filemenu) 657 658 # Compare menu 659 opmenu = Menu(menubar, tearoff=0) 660 opmenu.add_command( 661 label='Intersection', command=self._intersection, accelerator='+' 662 ) 663 opmenu.add_command(label='Union', command=self._union, accelerator='*') 664 opmenu.add_command( 665 label='Difference', command=self._difference, accelerator='-' 666 ) 667 opmenu.add_separator() 668 opmenu.add_command(label='Swap Charts', command=self._swapcharts) 669 menubar.add_cascade(label='Compare', underline=0, menu=opmenu) 670 671 # Add the menu 672 self._root.config(menu=menubar) 673 674 def _init_divider(self, root): 675 divider = Frame(root, border=2, relief='sunken') 676 divider.pack(side='top', fill='x', ipady=2) 677 678 def _init_chartviews(self, root): 679 opfont = ('symbol', -36) # Font for operator. 680 eqfont = ('helvetica', -36) # Font for equals sign. 681 682 frame = Frame(root, background='#c0c0c0') 683 frame.pack(side='top', expand=1, fill='both') 684 685 # The left matrix. 686 cv1_frame = Frame(frame, border=3, relief='groove') 687 cv1_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both') 688 self._left_selector = MutableOptionMenu( 689 cv1_frame, list(self._charts.keys()), command=self._select_left 690 ) 691 self._left_selector.pack(side='top', pady=5, fill='x') 692 self._left_matrix = ChartMatrixView( 693 cv1_frame, self._emptychart, toplevel=False, show_numedges=True 694 ) 695 self._left_matrix.pack(side='bottom', padx=5, pady=5, expand=1, fill='both') 696 self._left_matrix.add_callback('select', self.select_edge) 697 self._left_matrix.add_callback('select_cell', self.select_cell) 698 self._left_matrix.inactivate() 699 700 # The operator. 701 self._op_label = Label( 702 frame, text=' ', width=3, background='#c0c0c0', font=opfont 703 ) 704 self._op_label.pack(side='left', padx=5, pady=5) 705 706 # The right matrix. 707 cv2_frame = Frame(frame, border=3, relief='groove') 708 cv2_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both') 709 self._right_selector = MutableOptionMenu( 710 cv2_frame, list(self._charts.keys()), command=self._select_right 711 ) 712 self._right_selector.pack(side='top', pady=5, fill='x') 713 self._right_matrix = ChartMatrixView( 714 cv2_frame, self._emptychart, toplevel=False, show_numedges=True 715 ) 716 self._right_matrix.pack(side='bottom', padx=5, pady=5, expand=1, fill='both') 717 self._right_matrix.add_callback('select', self.select_edge) 718 self._right_matrix.add_callback('select_cell', self.select_cell) 719 self._right_matrix.inactivate() 720 721 # The equals sign 722 Label(frame, text='=', width=3, background='#c0c0c0', font=eqfont).pack( 723 side='left', padx=5, pady=5 724 ) 725 726 # The output matrix. 727 out_frame = Frame(frame, border=3, relief='groove') 728 out_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both') 729 self._out_label = Label(out_frame, text='Output') 730 self._out_label.pack(side='top', pady=9) 731 self._out_matrix = ChartMatrixView( 732 out_frame, self._emptychart, toplevel=False, show_numedges=True 733 ) 734 self._out_matrix.pack(side='bottom', padx=5, pady=5, expand=1, fill='both') 735 self._out_matrix.add_callback('select', self.select_edge) 736 self._out_matrix.add_callback('select_cell', self.select_cell) 737 self._out_matrix.inactivate() 738 739 def _init_buttons(self, root): 740 buttons = Frame(root) 741 buttons.pack(side='bottom', pady=5, fill='x', expand=0) 742 Button(buttons, text='Intersection', command=self._intersection).pack( 743 side='left' 744 ) 745 Button(buttons, text='Union', command=self._union).pack(side='left') 746 Button(buttons, text='Difference', command=self._difference).pack(side='left') 747 Frame(buttons, width=20).pack(side='left') 748 Button(buttons, text='Swap Charts', command=self._swapcharts).pack(side='left') 749 750 Button(buttons, text='Detatch Output', command=self._detatch_out).pack( 751 side='right' 752 ) 753 754 def _init_bindings(self, root): 755 # root.bind('<Control-s>', self.save_chart) 756 root.bind('<Control-o>', self.load_chart_dialog) 757 # root.bind('<Control-r>', self.reset) 758 759 # //////////////////////////////////////////////////////////// 760 # Input Handling 761 # //////////////////////////////////////////////////////////// 762 763 def _select_left(self, name): 764 self._left_name = name 765 self._left_chart = self._charts[name] 766 self._left_matrix.set_chart(self._left_chart) 767 if name == 'None': 768 self._left_matrix.inactivate() 769 self._apply_op() 770 771 def _select_right(self, name): 772 self._right_name = name 773 self._right_chart = self._charts[name] 774 self._right_matrix.set_chart(self._right_chart) 775 if name == 'None': 776 self._right_matrix.inactivate() 777 self._apply_op() 778 779 def _apply_op(self): 780 if self._operator == '-': 781 self._difference() 782 elif self._operator == 'or': 783 self._union() 784 elif self._operator == 'and': 785 self._intersection() 786 787 # //////////////////////////////////////////////////////////// 788 # File 789 # //////////////////////////////////////////////////////////// 790 CHART_FILE_TYPES = [('Pickle file', '.pickle'), ('All files', '*')] 791 792 def save_chart_dialog(self, *args): 793 filename = asksaveasfilename( 794 filetypes=self.CHART_FILE_TYPES, defaultextension='.pickle' 795 ) 796 if not filename: 797 return 798 try: 799 with open(filename, 'wb') as outfile: 800 pickle.dump(self._out_chart, outfile) 801 except Exception as e: 802 showerror( 803 'Error Saving Chart', 'Unable to open file: %r\n%s' % (filename, e) 804 ) 805 806 def load_chart_dialog(self, *args): 807 filename = askopenfilename( 808 filetypes=self.CHART_FILE_TYPES, defaultextension='.pickle' 809 ) 810 if not filename: 811 return 812 try: 813 self.load_chart(filename) 814 except Exception as e: 815 showerror( 816 'Error Loading Chart', 'Unable to open file: %r\n%s' % (filename, e) 817 ) 818 819 def load_chart(self, filename): 820 with open(filename, 'rb') as infile: 821 chart = pickle.load(infile) 822 name = os.path.basename(filename) 823 if name.endswith('.pickle'): 824 name = name[:-7] 825 if name.endswith('.chart'): 826 name = name[:-6] 827 self._charts[name] = chart 828 self._left_selector.add(name) 829 self._right_selector.add(name) 830 831 # If either left_matrix or right_matrix is empty, then 832 # display the new chart. 833 if self._left_chart is self._emptychart: 834 self._left_selector.set(name) 835 elif self._right_chart is self._emptychart: 836 self._right_selector.set(name) 837 838 def _update_chartviews(self): 839 self._left_matrix.update() 840 self._right_matrix.update() 841 self._out_matrix.update() 842 843 # //////////////////////////////////////////////////////////// 844 # Selection 845 # //////////////////////////////////////////////////////////// 846 847 def select_edge(self, edge): 848 if edge in self._left_chart: 849 self._left_matrix.markonly_edge(edge) 850 else: 851 self._left_matrix.unmark_edge() 852 if edge in self._right_chart: 853 self._right_matrix.markonly_edge(edge) 854 else: 855 self._right_matrix.unmark_edge() 856 if edge in self._out_chart: 857 self._out_matrix.markonly_edge(edge) 858 else: 859 self._out_matrix.unmark_edge() 860 861 def select_cell(self, i, j): 862 self._left_matrix.select_cell(i, j) 863 self._right_matrix.select_cell(i, j) 864 self._out_matrix.select_cell(i, j) 865 866 # //////////////////////////////////////////////////////////// 867 # Operations 868 # //////////////////////////////////////////////////////////// 869 870 def _difference(self): 871 if not self._checkcompat(): 872 return 873 874 out_chart = Chart(self._left_chart.tokens()) 875 for edge in self._left_chart: 876 if edge not in self._right_chart: 877 out_chart.insert(edge, []) 878 879 self._update('-', out_chart) 880 881 def _intersection(self): 882 if not self._checkcompat(): 883 return 884 885 out_chart = Chart(self._left_chart.tokens()) 886 for edge in self._left_chart: 887 if edge in self._right_chart: 888 out_chart.insert(edge, []) 889 890 self._update('and', out_chart) 891 892 def _union(self): 893 if not self._checkcompat(): 894 return 895 896 out_chart = Chart(self._left_chart.tokens()) 897 for edge in self._left_chart: 898 out_chart.insert(edge, []) 899 for edge in self._right_chart: 900 out_chart.insert(edge, []) 901 902 self._update('or', out_chart) 903 904 def _swapcharts(self): 905 left, right = self._left_name, self._right_name 906 self._left_selector.set(right) 907 self._right_selector.set(left) 908 909 def _checkcompat(self): 910 if ( 911 self._left_chart.tokens() != self._right_chart.tokens() 912 or self._left_chart.property_names() != self._right_chart.property_names() 913 or self._left_chart == self._emptychart 914 or self._right_chart == self._emptychart 915 ): 916 # Clear & inactivate the output chart. 917 self._out_chart = self._emptychart 918 self._out_matrix.set_chart(self._out_chart) 919 self._out_matrix.inactivate() 920 self._out_label['text'] = 'Output' 921 # Issue some other warning? 922 return False 923 else: 924 return True 925 926 def _update(self, operator, out_chart): 927 self._operator = operator 928 self._op_label['text'] = self._OPSYMBOL[operator] 929 self._out_chart = out_chart 930 self._out_matrix.set_chart(out_chart) 931 self._out_label['text'] = '%s %s %s' % ( 932 self._left_name, 933 self._operator, 934 self._right_name, 935 ) 936 937 def _clear_out_chart(self): 938 self._out_chart = self._emptychart 939 self._out_matrix.set_chart(self._out_chart) 940 self._op_label['text'] = ' ' 941 self._out_matrix.inactivate() 942 943 def _detatch_out(self): 944 ChartMatrixView(self._root, self._out_chart, title=self._out_label['text']) 945 946 947####################################################################### 948# Chart View 949####################################################################### 950 951 952class ChartView(object): 953 """ 954 A component for viewing charts. This is used by ``ChartParserApp`` to 955 allow students to interactively experiment with various chart 956 parsing techniques. It is also used by ``Chart.draw()``. 957 958 :ivar _chart: The chart that we are giving a view of. This chart 959 may be modified; after it is modified, you should call 960 ``update``. 961 :ivar _sentence: The list of tokens that the chart spans. 962 963 :ivar _root: The root window. 964 :ivar _chart_canvas: The canvas we're using to display the chart 965 itself. 966 :ivar _tree_canvas: The canvas we're using to display the tree 967 that each edge spans. May be None, if we're not displaying 968 trees. 969 :ivar _sentence_canvas: The canvas we're using to display the sentence 970 text. May be None, if we're not displaying the sentence text. 971 :ivar _edgetags: A dictionary mapping from edges to the tags of 972 the canvas elements (lines, etc) used to display that edge. 973 The values of this dictionary have the form 974 ``(linetag, rhstag1, dottag, rhstag2, lhstag)``. 975 :ivar _treetags: A list of all the tags that make up the tree; 976 used to erase the tree (without erasing the loclines). 977 :ivar _chart_height: The height of the chart canvas. 978 :ivar _sentence_height: The height of the sentence canvas. 979 :ivar _tree_height: The height of the tree 980 981 :ivar _text_height: The height of a text string (in the normal 982 font). 983 984 :ivar _edgelevels: A list of edges at each level of the chart (the 985 top level is the 0th element). This list is used to remember 986 where edges should be drawn; and to make sure that no edges 987 are overlapping on the chart view. 988 989 :ivar _unitsize: Pixel size of one unit (from the location). This 990 is determined by the span of the chart's location, and the 991 width of the chart display canvas. 992 993 :ivar _fontsize: The current font size 994 995 :ivar _marks: A dictionary from edges to marks. Marks are 996 strings, specifying colors (e.g. 'green'). 997 """ 998 999 _LEAF_SPACING = 10 1000 _MARGIN = 10 1001 _TREE_LEVEL_SIZE = 12 1002 _CHART_LEVEL_SIZE = 40 1003 1004 def __init__(self, chart, root=None, **kw): 1005 """ 1006 Construct a new ``Chart`` display. 1007 """ 1008 # Process keyword args. 1009 draw_tree = kw.get('draw_tree', 0) 1010 draw_sentence = kw.get('draw_sentence', 1) 1011 self._fontsize = kw.get('fontsize', -12) 1012 1013 # The chart! 1014 self._chart = chart 1015 1016 # Callback functions 1017 self._callbacks = {} 1018 1019 # Keep track of drawn edges 1020 self._edgelevels = [] 1021 self._edgetags = {} 1022 1023 # Keep track of which edges are marked. 1024 self._marks = {} 1025 1026 # These are used to keep track of the set of tree tokens 1027 # currently displayed in the tree canvas. 1028 self._treetoks = [] 1029 self._treetoks_edge = None 1030 self._treetoks_index = 0 1031 1032 # Keep track of the tags used to draw the tree 1033 self._tree_tags = [] 1034 1035 # Put multiple edges on each level? 1036 self._compact = 0 1037 1038 # If they didn't provide a main window, then set one up. 1039 if root is None: 1040 top = Tk() 1041 top.title('Chart View') 1042 1043 def destroy1(e, top=top): 1044 top.destroy() 1045 1046 def destroy2(top=top): 1047 top.destroy() 1048 1049 top.bind('q', destroy1) 1050 b = Button(top, text='Done', command=destroy2) 1051 b.pack(side='bottom') 1052 self._root = top 1053 else: 1054 self._root = root 1055 1056 # Create some fonts. 1057 self._init_fonts(root) 1058 1059 # Create the chart canvas. 1060 (self._chart_sb, self._chart_canvas) = self._sb_canvas(self._root) 1061 self._chart_canvas['height'] = 300 1062 self._chart_canvas['closeenough'] = 15 1063 1064 # Create the sentence canvas. 1065 if draw_sentence: 1066 cframe = Frame(self._root, relief='sunk', border=2) 1067 cframe.pack(fill='both', side='bottom') 1068 self._sentence_canvas = Canvas(cframe, height=50) 1069 self._sentence_canvas['background'] = '#e0e0e0' 1070 self._sentence_canvas.pack(fill='both') 1071 # self._sentence_canvas['height'] = self._sentence_height 1072 else: 1073 self._sentence_canvas = None 1074 1075 # Create the tree canvas. 1076 if draw_tree: 1077 (sb, canvas) = self._sb_canvas(self._root, 'n', 'x') 1078 (self._tree_sb, self._tree_canvas) = (sb, canvas) 1079 self._tree_canvas['height'] = 200 1080 else: 1081 self._tree_canvas = None 1082 1083 # Do some analysis to figure out how big the window should be 1084 self._analyze() 1085 self.draw() 1086 self._resize() 1087 self._grow() 1088 1089 # Set up the configure callback, which will be called whenever 1090 # the window is resized. 1091 self._chart_canvas.bind('<Configure>', self._configure) 1092 1093 def _init_fonts(self, root): 1094 self._boldfont = Font(family='helvetica', weight='bold', size=self._fontsize) 1095 self._font = Font(family='helvetica', size=self._fontsize) 1096 # See: <http://www.astro.washington.edu/owen/ROTKFolklore.html> 1097 self._sysfont = Font(font=Button()["font"]) 1098 root.option_add("*Font", self._sysfont) 1099 1100 def _sb_canvas(self, root, expand='y', fill='both', side='bottom'): 1101 """ 1102 Helper for __init__: construct a canvas with a scrollbar. 1103 """ 1104 cframe = Frame(root, relief='sunk', border=2) 1105 cframe.pack(fill=fill, expand=expand, side=side) 1106 canvas = Canvas(cframe, background='#e0e0e0') 1107 1108 # Give the canvas a scrollbar. 1109 sb = Scrollbar(cframe, orient='vertical') 1110 sb.pack(side='right', fill='y') 1111 canvas.pack(side='left', fill=fill, expand='yes') 1112 1113 # Connect the scrollbars to the canvas. 1114 sb['command'] = canvas.yview 1115 canvas['yscrollcommand'] = sb.set 1116 1117 return (sb, canvas) 1118 1119 def scroll_up(self, *e): 1120 self._chart_canvas.yview('scroll', -1, 'units') 1121 1122 def scroll_down(self, *e): 1123 self._chart_canvas.yview('scroll', 1, 'units') 1124 1125 def page_up(self, *e): 1126 self._chart_canvas.yview('scroll', -1, 'pages') 1127 1128 def page_down(self, *e): 1129 self._chart_canvas.yview('scroll', 1, 'pages') 1130 1131 def _grow(self): 1132 """ 1133 Grow the window, if necessary 1134 """ 1135 # Grow, if need-be 1136 N = self._chart.num_leaves() 1137 width = max( 1138 int(self._chart_canvas['width']), N * self._unitsize + ChartView._MARGIN * 2 1139 ) 1140 1141 # It won't resize without the second (height) line, but I 1142 # don't understand why not. 1143 self._chart_canvas.configure(width=width) 1144 self._chart_canvas.configure(height=self._chart_canvas['height']) 1145 1146 self._unitsize = (width - 2 * ChartView._MARGIN) / N 1147 1148 # Reset the height for the sentence window. 1149 if self._sentence_canvas is not None: 1150 self._sentence_canvas['height'] = self._sentence_height 1151 1152 def set_font_size(self, size): 1153 self._font.configure(size=-abs(size)) 1154 self._boldfont.configure(size=-abs(size)) 1155 self._sysfont.configure(size=-abs(size)) 1156 self._analyze() 1157 self._grow() 1158 self.draw() 1159 1160 def get_font_size(self): 1161 return abs(self._fontsize) 1162 1163 def _configure(self, e): 1164 """ 1165 The configure callback. This is called whenever the window is 1166 resized. It is also called when the window is first mapped. 1167 It figures out the unit size, and redraws the contents of each 1168 canvas. 1169 """ 1170 N = self._chart.num_leaves() 1171 self._unitsize = (e.width - 2 * ChartView._MARGIN) / N 1172 self.draw() 1173 1174 def update(self, chart=None): 1175 """ 1176 Draw any edges that have not been drawn. This is typically 1177 called when a after modifies the canvas that a CanvasView is 1178 displaying. ``update`` will cause any edges that have been 1179 added to the chart to be drawn. 1180 1181 If update is given a ``chart`` argument, then it will replace 1182 the current chart with the given chart. 1183 """ 1184 if chart is not None: 1185 self._chart = chart 1186 self._edgelevels = [] 1187 self._marks = {} 1188 self._analyze() 1189 self._grow() 1190 self.draw() 1191 self.erase_tree() 1192 self._resize() 1193 else: 1194 for edge in self._chart: 1195 if edge not in self._edgetags: 1196 self._add_edge(edge) 1197 self._resize() 1198 1199 def _edge_conflict(self, edge, lvl): 1200 """ 1201 Return True if the given edge overlaps with any edge on the given 1202 level. This is used by _add_edge to figure out what level a 1203 new edge should be added to. 1204 """ 1205 (s1, e1) = edge.span() 1206 for otheredge in self._edgelevels[lvl]: 1207 (s2, e2) = otheredge.span() 1208 if (s1 <= s2 < e1) or (s2 <= s1 < e2) or (s1 == s2 == e1 == e2): 1209 return True 1210 return False 1211 1212 def _analyze_edge(self, edge): 1213 """ 1214 Given a new edge, recalculate: 1215 1216 - _text_height 1217 - _unitsize (if the edge text is too big for the current 1218 _unitsize, then increase _unitsize) 1219 """ 1220 c = self._chart_canvas 1221 1222 if isinstance(edge, TreeEdge): 1223 lhs = edge.lhs() 1224 rhselts = [] 1225 for elt in edge.rhs(): 1226 if isinstance(elt, Nonterminal): 1227 rhselts.append(str(elt.symbol())) 1228 else: 1229 rhselts.append(repr(elt)) 1230 rhs = " ".join(rhselts) 1231 else: 1232 lhs = edge.lhs() 1233 rhs = '' 1234 1235 for s in (lhs, rhs): 1236 tag = c.create_text( 1237 0, 0, text=s, font=self._boldfont, anchor='nw', justify='left' 1238 ) 1239 bbox = c.bbox(tag) 1240 c.delete(tag) 1241 width = bbox[2] # + ChartView._LEAF_SPACING 1242 edgelen = max(edge.length(), 1) 1243 self._unitsize = max(self._unitsize, width / edgelen) 1244 self._text_height = max(self._text_height, bbox[3] - bbox[1]) 1245 1246 def _add_edge(self, edge, minlvl=0): 1247 """ 1248 Add a single edge to the ChartView: 1249 1250 - Call analyze_edge to recalculate display parameters 1251 - Find an available level 1252 - Call _draw_edge 1253 """ 1254 # Do NOT show leaf edges in the chart. 1255 if isinstance(edge, LeafEdge): 1256 return 1257 1258 if edge in self._edgetags: 1259 return 1260 self._analyze_edge(edge) 1261 self._grow() 1262 1263 if not self._compact: 1264 self._edgelevels.append([edge]) 1265 lvl = len(self._edgelevels) - 1 1266 self._draw_edge(edge, lvl) 1267 self._resize() 1268 return 1269 1270 # Figure out what level to draw the edge on. 1271 lvl = 0 1272 while True: 1273 # If this level doesn't exist yet, create it. 1274 while lvl >= len(self._edgelevels): 1275 self._edgelevels.append([]) 1276 self._resize() 1277 1278 # Check if we can fit the edge in this level. 1279 if lvl >= minlvl and not self._edge_conflict(edge, lvl): 1280 # Go ahead and draw it. 1281 self._edgelevels[lvl].append(edge) 1282 break 1283 1284 # Try the next level. 1285 lvl += 1 1286 1287 self._draw_edge(edge, lvl) 1288 1289 def view_edge(self, edge): 1290 level = None 1291 for i in range(len(self._edgelevels)): 1292 if edge in self._edgelevels[i]: 1293 level = i 1294 break 1295 if level is None: 1296 return 1297 # Try to view the new edge.. 1298 y = (level + 1) * self._chart_level_size 1299 dy = self._text_height + 10 1300 self._chart_canvas.yview('moveto', 1.0) 1301 if self._chart_height != 0: 1302 self._chart_canvas.yview('moveto', (y - dy) / self._chart_height) 1303 1304 def _draw_edge(self, edge, lvl): 1305 """ 1306 Draw a single edge on the ChartView. 1307 """ 1308 c = self._chart_canvas 1309 1310 # Draw the arrow. 1311 x1 = edge.start() * self._unitsize + ChartView._MARGIN 1312 x2 = edge.end() * self._unitsize + ChartView._MARGIN 1313 if x2 == x1: 1314 x2 += max(4, self._unitsize / 5) 1315 y = (lvl + 1) * self._chart_level_size 1316 linetag = c.create_line(x1, y, x2, y, arrow='last', width=3) 1317 1318 # Draw a label for the edge. 1319 if isinstance(edge, TreeEdge): 1320 rhs = [] 1321 for elt in edge.rhs(): 1322 if isinstance(elt, Nonterminal): 1323 rhs.append(str(elt.symbol())) 1324 else: 1325 rhs.append(repr(elt)) 1326 pos = edge.dot() 1327 else: 1328 rhs = [] 1329 pos = 0 1330 1331 rhs1 = " ".join(rhs[:pos]) 1332 rhs2 = " ".join(rhs[pos:]) 1333 rhstag1 = c.create_text(x1 + 3, y, text=rhs1, font=self._font, anchor='nw') 1334 dotx = c.bbox(rhstag1)[2] + 6 1335 doty = (c.bbox(rhstag1)[1] + c.bbox(rhstag1)[3]) / 2 1336 dottag = c.create_oval(dotx - 2, doty - 2, dotx + 2, doty + 2) 1337 rhstag2 = c.create_text(dotx + 6, y, text=rhs2, font=self._font, anchor='nw') 1338 lhstag = c.create_text( 1339 (x1 + x2) / 2, y, text=str(edge.lhs()), anchor='s', font=self._boldfont 1340 ) 1341 1342 # Keep track of the edge's tags. 1343 self._edgetags[edge] = (linetag, rhstag1, dottag, rhstag2, lhstag) 1344 1345 # Register a callback for clicking on the edge. 1346 def cb(event, self=self, edge=edge): 1347 self._fire_callbacks('select', edge) 1348 1349 c.tag_bind(rhstag1, '<Button-1>', cb) 1350 c.tag_bind(rhstag2, '<Button-1>', cb) 1351 c.tag_bind(linetag, '<Button-1>', cb) 1352 c.tag_bind(dottag, '<Button-1>', cb) 1353 c.tag_bind(lhstag, '<Button-1>', cb) 1354 1355 self._color_edge(edge) 1356 1357 def _color_edge(self, edge, linecolor=None, textcolor=None): 1358 """ 1359 Color in an edge with the given colors. 1360 If no colors are specified, use intelligent defaults 1361 (dependent on selection, etc.) 1362 """ 1363 if edge not in self._edgetags: 1364 return 1365 c = self._chart_canvas 1366 1367 if linecolor is not None and textcolor is not None: 1368 if edge in self._marks: 1369 linecolor = self._marks[edge] 1370 tags = self._edgetags[edge] 1371 c.itemconfig(tags[0], fill=linecolor) 1372 c.itemconfig(tags[1], fill=textcolor) 1373 c.itemconfig(tags[2], fill=textcolor, outline=textcolor) 1374 c.itemconfig(tags[3], fill=textcolor) 1375 c.itemconfig(tags[4], fill=textcolor) 1376 return 1377 else: 1378 N = self._chart.num_leaves() 1379 if edge in self._marks: 1380 self._color_edge(self._marks[edge]) 1381 if edge.is_complete() and edge.span() == (0, N): 1382 self._color_edge(edge, '#084', '#042') 1383 elif isinstance(edge, LeafEdge): 1384 self._color_edge(edge, '#48c', '#246') 1385 else: 1386 self._color_edge(edge, '#00f', '#008') 1387 1388 def mark_edge(self, edge, mark='#0df'): 1389 """ 1390 Mark an edge 1391 """ 1392 self._marks[edge] = mark 1393 self._color_edge(edge) 1394 1395 def unmark_edge(self, edge=None): 1396 """ 1397 Unmark an edge (or all edges) 1398 """ 1399 if edge is None: 1400 old_marked_edges = list(self._marks.keys()) 1401 self._marks = {} 1402 for edge in old_marked_edges: 1403 self._color_edge(edge) 1404 else: 1405 del self._marks[edge] 1406 self._color_edge(edge) 1407 1408 def markonly_edge(self, edge, mark='#0df'): 1409 self.unmark_edge() 1410 self.mark_edge(edge, mark) 1411 1412 def _analyze(self): 1413 """ 1414 Analyze the sentence string, to figure out how big a unit needs 1415 to be, How big the tree should be, etc. 1416 """ 1417 # Figure out the text height and the unit size. 1418 unitsize = 70 # min unitsize 1419 text_height = 0 1420 c = self._chart_canvas 1421 1422 # Check against all tokens 1423 for leaf in self._chart.leaves(): 1424 tag = c.create_text( 1425 0, 0, text=repr(leaf), font=self._font, anchor='nw', justify='left' 1426 ) 1427 bbox = c.bbox(tag) 1428 c.delete(tag) 1429 width = bbox[2] + ChartView._LEAF_SPACING 1430 unitsize = max(width, unitsize) 1431 text_height = max(text_height, bbox[3] - bbox[1]) 1432 1433 self._unitsize = unitsize 1434 self._text_height = text_height 1435 self._sentence_height = self._text_height + 2 * ChartView._MARGIN 1436 1437 # Check against edges. 1438 for edge in self._chart.edges(): 1439 self._analyze_edge(edge) 1440 1441 # Size of chart levels 1442 self._chart_level_size = self._text_height * 2 1443 1444 # Default tree size.. 1445 self._tree_height = 3 * (ChartView._TREE_LEVEL_SIZE + self._text_height) 1446 1447 # Resize the scrollregions. 1448 self._resize() 1449 1450 def _resize(self): 1451 """ 1452 Update the scroll-regions for each canvas. This ensures that 1453 everything is within a scroll-region, so the user can use the 1454 scrollbars to view the entire display. This does *not* 1455 resize the window. 1456 """ 1457 c = self._chart_canvas 1458 1459 # Reset the chart scroll region 1460 width = self._chart.num_leaves() * self._unitsize + ChartView._MARGIN * 2 1461 1462 levels = len(self._edgelevels) 1463 self._chart_height = (levels + 2) * self._chart_level_size 1464 c['scrollregion'] = (0, 0, width, self._chart_height) 1465 1466 # Reset the tree scroll region 1467 if self._tree_canvas: 1468 self._tree_canvas['scrollregion'] = (0, 0, width, self._tree_height) 1469 1470 def _draw_loclines(self): 1471 """ 1472 Draw location lines. These are vertical gridlines used to 1473 show where each location unit is. 1474 """ 1475 BOTTOM = 50000 1476 c1 = self._tree_canvas 1477 c2 = self._sentence_canvas 1478 c3 = self._chart_canvas 1479 margin = ChartView._MARGIN 1480 self._loclines = [] 1481 for i in range(0, self._chart.num_leaves() + 1): 1482 x = i * self._unitsize + margin 1483 1484 if c1: 1485 t1 = c1.create_line(x, 0, x, BOTTOM) 1486 c1.tag_lower(t1) 1487 if c2: 1488 t2 = c2.create_line(x, 0, x, self._sentence_height) 1489 c2.tag_lower(t2) 1490 t3 = c3.create_line(x, 0, x, BOTTOM) 1491 c3.tag_lower(t3) 1492 t4 = c3.create_text(x + 2, 0, text=repr(i), anchor='nw', font=self._font) 1493 c3.tag_lower(t4) 1494 # if i % 4 == 0: 1495 # if c1: c1.itemconfig(t1, width=2, fill='gray60') 1496 # if c2: c2.itemconfig(t2, width=2, fill='gray60') 1497 # c3.itemconfig(t3, width=2, fill='gray60') 1498 if i % 2 == 0: 1499 if c1: 1500 c1.itemconfig(t1, fill='gray60') 1501 if c2: 1502 c2.itemconfig(t2, fill='gray60') 1503 c3.itemconfig(t3, fill='gray60') 1504 else: 1505 if c1: 1506 c1.itemconfig(t1, fill='gray80') 1507 if c2: 1508 c2.itemconfig(t2, fill='gray80') 1509 c3.itemconfig(t3, fill='gray80') 1510 1511 def _draw_sentence(self): 1512 """Draw the sentence string.""" 1513 if self._chart.num_leaves() == 0: 1514 return 1515 c = self._sentence_canvas 1516 margin = ChartView._MARGIN 1517 y = ChartView._MARGIN 1518 1519 for i, leaf in enumerate(self._chart.leaves()): 1520 x1 = i * self._unitsize + margin 1521 x2 = x1 + self._unitsize 1522 x = (x1 + x2) / 2 1523 tag = c.create_text( 1524 x, y, text=repr(leaf), font=self._font, anchor='n', justify='left' 1525 ) 1526 bbox = c.bbox(tag) 1527 rt = c.create_rectangle( 1528 x1 + 2, 1529 bbox[1] - (ChartView._LEAF_SPACING / 2), 1530 x2 - 2, 1531 bbox[3] + (ChartView._LEAF_SPACING / 2), 1532 fill='#f0f0f0', 1533 outline='#f0f0f0', 1534 ) 1535 c.tag_lower(rt) 1536 1537 def erase_tree(self): 1538 for tag in self._tree_tags: 1539 self._tree_canvas.delete(tag) 1540 self._treetoks = [] 1541 self._treetoks_edge = None 1542 self._treetoks_index = 0 1543 1544 def draw_tree(self, edge=None): 1545 if edge is None and self._treetoks_edge is None: 1546 return 1547 if edge is None: 1548 edge = self._treetoks_edge 1549 1550 # If it's a new edge, then get a new list of treetoks. 1551 if self._treetoks_edge != edge: 1552 self._treetoks = [t for t in self._chart.trees(edge) if isinstance(t, Tree)] 1553 self._treetoks_edge = edge 1554 self._treetoks_index = 0 1555 1556 # Make sure there's something to draw. 1557 if len(self._treetoks) == 0: 1558 return 1559 1560 # Erase the old tree. 1561 for tag in self._tree_tags: 1562 self._tree_canvas.delete(tag) 1563 1564 # Draw the new tree. 1565 tree = self._treetoks[self._treetoks_index] 1566 self._draw_treetok(tree, edge.start()) 1567 1568 # Show how many trees are available for the edge. 1569 self._draw_treecycle() 1570 1571 # Update the scroll region. 1572 w = self._chart.num_leaves() * self._unitsize + 2 * ChartView._MARGIN 1573 h = tree.height() * (ChartView._TREE_LEVEL_SIZE + self._text_height) 1574 self._tree_canvas['scrollregion'] = (0, 0, w, h) 1575 1576 def cycle_tree(self): 1577 self._treetoks_index = (self._treetoks_index + 1) % len(self._treetoks) 1578 self.draw_tree(self._treetoks_edge) 1579 1580 def _draw_treecycle(self): 1581 if len(self._treetoks) <= 1: 1582 return 1583 1584 # Draw the label. 1585 label = '%d Trees' % len(self._treetoks) 1586 c = self._tree_canvas 1587 margin = ChartView._MARGIN 1588 right = self._chart.num_leaves() * self._unitsize + margin - 2 1589 tag = c.create_text(right, 2, anchor='ne', text=label, font=self._boldfont) 1590 self._tree_tags.append(tag) 1591 _, _, _, y = c.bbox(tag) 1592 1593 # Draw the triangles. 1594 for i in range(len(self._treetoks)): 1595 x = right - 20 * (len(self._treetoks) - i - 1) 1596 if i == self._treetoks_index: 1597 fill = '#084' 1598 else: 1599 fill = '#fff' 1600 tag = c.create_polygon( 1601 x, y + 10, x - 5, y, x - 10, y + 10, fill=fill, outline='black' 1602 ) 1603 self._tree_tags.append(tag) 1604 1605 # Set up a callback: show the tree if they click on its 1606 # triangle. 1607 def cb(event, self=self, i=i): 1608 self._treetoks_index = i 1609 self.draw_tree() 1610 1611 c.tag_bind(tag, '<Button-1>', cb) 1612 1613 def _draw_treetok(self, treetok, index, depth=0): 1614 """ 1615 :param index: The index of the first leaf in the tree. 1616 :return: The index of the first leaf after the tree. 1617 """ 1618 c = self._tree_canvas 1619 margin = ChartView._MARGIN 1620 1621 # Draw the children 1622 child_xs = [] 1623 for child in treetok: 1624 if isinstance(child, Tree): 1625 child_x, index = self._draw_treetok(child, index, depth + 1) 1626 child_xs.append(child_x) 1627 else: 1628 child_xs.append((2 * index + 1) * self._unitsize / 2 + margin) 1629 index += 1 1630 1631 # If we have children, then get the node's x by averaging their 1632 # node x's. Otherwise, make room for ourselves. 1633 if child_xs: 1634 nodex = sum(child_xs) / len(child_xs) 1635 else: 1636 # [XX] breaks for null productions. 1637 nodex = (2 * index + 1) * self._unitsize / 2 + margin 1638 index += 1 1639 1640 # Draw the node 1641 nodey = depth * (ChartView._TREE_LEVEL_SIZE + self._text_height) 1642 tag = c.create_text( 1643 nodex, 1644 nodey, 1645 anchor='n', 1646 justify='center', 1647 text=str(treetok.label()), 1648 fill='#042', 1649 font=self._boldfont, 1650 ) 1651 self._tree_tags.append(tag) 1652 1653 # Draw lines to the children. 1654 childy = nodey + ChartView._TREE_LEVEL_SIZE + self._text_height 1655 for childx, child in zip(child_xs, treetok): 1656 if isinstance(child, Tree) and child: 1657 # A "real" tree token: 1658 tag = c.create_line( 1659 nodex, 1660 nodey + self._text_height, 1661 childx, 1662 childy, 1663 width=2, 1664 fill='#084', 1665 ) 1666 self._tree_tags.append(tag) 1667 if isinstance(child, Tree) and not child: 1668 # An unexpanded tree token: 1669 tag = c.create_line( 1670 nodex, 1671 nodey + self._text_height, 1672 childx, 1673 childy, 1674 width=2, 1675 fill='#048', 1676 dash='2 3', 1677 ) 1678 self._tree_tags.append(tag) 1679 if not isinstance(child, Tree): 1680 # A leaf: 1681 tag = c.create_line( 1682 nodex, 1683 nodey + self._text_height, 1684 childx, 1685 10000, 1686 width=2, 1687 fill='#084', 1688 ) 1689 self._tree_tags.append(tag) 1690 1691 return nodex, index 1692 1693 def draw(self): 1694 """ 1695 Draw everything (from scratch). 1696 """ 1697 if self._tree_canvas: 1698 self._tree_canvas.delete('all') 1699 self.draw_tree() 1700 1701 if self._sentence_canvas: 1702 self._sentence_canvas.delete('all') 1703 self._draw_sentence() 1704 1705 self._chart_canvas.delete('all') 1706 self._edgetags = {} 1707 1708 # Redraw any edges we erased. 1709 for lvl in range(len(self._edgelevels)): 1710 for edge in self._edgelevels[lvl]: 1711 self._draw_edge(edge, lvl) 1712 1713 for edge in self._chart: 1714 self._add_edge(edge) 1715 1716 self._draw_loclines() 1717 1718 def add_callback(self, event, func): 1719 self._callbacks.setdefault(event, {})[func] = 1 1720 1721 def remove_callback(self, event, func=None): 1722 if func is None: 1723 del self._callbacks[event] 1724 else: 1725 try: 1726 del self._callbacks[event][func] 1727 except: 1728 pass 1729 1730 def _fire_callbacks(self, event, *args): 1731 if event not in self._callbacks: 1732 return 1733 for cb_func in list(self._callbacks[event].keys()): 1734 cb_func(*args) 1735 1736 1737####################################################################### 1738# Edge Rules 1739####################################################################### 1740# These version of the chart rules only apply to a specific edge. 1741# This lets the user select an edge, and then apply a rule. 1742 1743 1744class EdgeRule(object): 1745 """ 1746 To create an edge rule, make an empty base class that uses 1747 EdgeRule as the first base class, and the basic rule as the 1748 second base class. (Order matters!) 1749 """ 1750 1751 def __init__(self, edge): 1752 super = self.__class__.__bases__[1] 1753 self._edge = edge 1754 self.NUM_EDGES = super.NUM_EDGES - 1 1755 1756 def apply(self, chart, grammar, *edges): 1757 super = self.__class__.__bases__[1] 1758 edges += (self._edge,) 1759 for e in super.apply(self, chart, grammar, *edges): 1760 yield e 1761 1762 def __str__(self): 1763 super = self.__class__.__bases__[1] 1764 return super.__str__(self) 1765 1766 1767class TopDownPredictEdgeRule(EdgeRule, TopDownPredictRule): 1768 pass 1769 1770 1771class BottomUpEdgeRule(EdgeRule, BottomUpPredictRule): 1772 pass 1773 1774 1775class BottomUpLeftCornerEdgeRule(EdgeRule, BottomUpPredictCombineRule): 1776 pass 1777 1778 1779class FundamentalEdgeRule(EdgeRule, SingleEdgeFundamentalRule): 1780 pass 1781 1782 1783####################################################################### 1784# Chart Parser Application 1785####################################################################### 1786 1787 1788class ChartParserApp(object): 1789 def __init__(self, grammar, tokens, title='Chart Parser Application'): 1790 # Initialize the parser 1791 self._init_parser(grammar, tokens) 1792 1793 self._root = None 1794 try: 1795 # Create the root window. 1796 self._root = Tk() 1797 self._root.title(title) 1798 self._root.bind('<Control-q>', self.destroy) 1799 1800 # Set up some frames. 1801 frame3 = Frame(self._root) 1802 frame2 = Frame(self._root) 1803 frame1 = Frame(self._root) 1804 frame3.pack(side='bottom', fill='none') 1805 frame2.pack(side='bottom', fill='x') 1806 frame1.pack(side='bottom', fill='both', expand=1) 1807 1808 self._init_fonts(self._root) 1809 self._init_animation() 1810 self._init_chartview(frame1) 1811 self._init_rulelabel(frame2) 1812 self._init_buttons(frame3) 1813 self._init_menubar() 1814 1815 self._matrix = None 1816 self._results = None 1817 1818 # Set up keyboard bindings. 1819 self._init_bindings() 1820 1821 except: 1822 print('Error creating Tree View') 1823 self.destroy() 1824 raise 1825 1826 def destroy(self, *args): 1827 if self._root is None: 1828 return 1829 self._root.destroy() 1830 self._root = None 1831 1832 def mainloop(self, *args, **kwargs): 1833 """ 1834 Enter the Tkinter mainloop. This function must be called if 1835 this demo is created from a non-interactive program (e.g. 1836 from a secript); otherwise, the demo will close as soon as 1837 the script completes. 1838 """ 1839 if in_idle(): 1840 return 1841 self._root.mainloop(*args, **kwargs) 1842 1843 # //////////////////////////////////////////////////////////// 1844 # Initialization Helpers 1845 # //////////////////////////////////////////////////////////// 1846 1847 def _init_parser(self, grammar, tokens): 1848 self._grammar = grammar 1849 self._tokens = tokens 1850 self._reset_parser() 1851 1852 def _reset_parser(self): 1853 self._cp = SteppingChartParser(self._grammar) 1854 self._cp.initialize(self._tokens) 1855 self._chart = self._cp.chart() 1856 1857 # Insert LeafEdges before the parsing starts. 1858 for _new_edge in LeafInitRule().apply(self._chart, self._grammar): 1859 pass 1860 1861 # The step iterator -- use this to generate new edges 1862 self._cpstep = self._cp.step() 1863 1864 # The currently selected edge 1865 self._selection = None 1866 1867 def _init_fonts(self, root): 1868 # See: <http://www.astro.washington.edu/owen/ROTKFolklore.html> 1869 self._sysfont = Font(font=Button()["font"]) 1870 root.option_add("*Font", self._sysfont) 1871 1872 # TWhat's our font size (default=same as sysfont) 1873 self._size = IntVar(root) 1874 self._size.set(self._sysfont.cget('size')) 1875 1876 self._boldfont = Font(family='helvetica', weight='bold', size=self._size.get()) 1877 self._font = Font(family='helvetica', size=self._size.get()) 1878 1879 def _init_animation(self): 1880 # Are we stepping? (default=yes) 1881 self._step = IntVar(self._root) 1882 self._step.set(1) 1883 1884 # What's our animation speed (default=fast) 1885 self._animate = IntVar(self._root) 1886 self._animate.set(3) # Default speed = fast 1887 1888 # Are we currently animating? 1889 self._animating = 0 1890 1891 def _init_chartview(self, parent): 1892 self._cv = ChartView(self._chart, parent, draw_tree=1, draw_sentence=1) 1893 self._cv.add_callback('select', self._click_cv_edge) 1894 1895 def _init_rulelabel(self, parent): 1896 ruletxt = 'Last edge generated by:' 1897 1898 self._rulelabel1 = Label(parent, text=ruletxt, font=self._boldfont) 1899 self._rulelabel2 = Label( 1900 parent, width=40, relief='groove', anchor='w', font=self._boldfont 1901 ) 1902 self._rulelabel1.pack(side='left') 1903 self._rulelabel2.pack(side='left') 1904 step = Checkbutton(parent, variable=self._step, text='Step') 1905 step.pack(side='right') 1906 1907 def _init_buttons(self, parent): 1908 frame1 = Frame(parent) 1909 frame2 = Frame(parent) 1910 frame1.pack(side='bottom', fill='x') 1911 frame2.pack(side='top', fill='none') 1912 1913 Button( 1914 frame1, 1915 text='Reset\nParser', 1916 background='#90c0d0', 1917 foreground='black', 1918 command=self.reset, 1919 ).pack(side='right') 1920 # Button(frame1, text='Pause', 1921 # background='#90c0d0', foreground='black', 1922 # command=self.pause).pack(side='left') 1923 1924 Button( 1925 frame1, 1926 text='Top Down\nStrategy', 1927 background='#90c0d0', 1928 foreground='black', 1929 command=self.top_down_strategy, 1930 ).pack(side='left') 1931 Button( 1932 frame1, 1933 text='Bottom Up\nStrategy', 1934 background='#90c0d0', 1935 foreground='black', 1936 command=self.bottom_up_strategy, 1937 ).pack(side='left') 1938 Button( 1939 frame1, 1940 text='Bottom Up\nLeft-Corner Strategy', 1941 background='#90c0d0', 1942 foreground='black', 1943 command=self.bottom_up_leftcorner_strategy, 1944 ).pack(side='left') 1945 1946 Button( 1947 frame2, 1948 text='Top Down Init\nRule', 1949 background='#90f090', 1950 foreground='black', 1951 command=self.top_down_init, 1952 ).pack(side='left') 1953 Button( 1954 frame2, 1955 text='Top Down Predict\nRule', 1956 background='#90f090', 1957 foreground='black', 1958 command=self.top_down_predict, 1959 ).pack(side='left') 1960 Frame(frame2, width=20).pack(side='left') 1961 1962 Button( 1963 frame2, 1964 text='Bottom Up Predict\nRule', 1965 background='#90f090', 1966 foreground='black', 1967 command=self.bottom_up, 1968 ).pack(side='left') 1969 Frame(frame2, width=20).pack(side='left') 1970 1971 Button( 1972 frame2, 1973 text='Bottom Up Left-Corner\nPredict Rule', 1974 background='#90f090', 1975 foreground='black', 1976 command=self.bottom_up_leftcorner, 1977 ).pack(side='left') 1978 Frame(frame2, width=20).pack(side='left') 1979 1980 Button( 1981 frame2, 1982 text='Fundamental\nRule', 1983 background='#90f090', 1984 foreground='black', 1985 command=self.fundamental, 1986 ).pack(side='left') 1987 1988 def _init_bindings(self): 1989 self._root.bind('<Up>', self._cv.scroll_up) 1990 self._root.bind('<Down>', self._cv.scroll_down) 1991 self._root.bind('<Prior>', self._cv.page_up) 1992 self._root.bind('<Next>', self._cv.page_down) 1993 self._root.bind('<Control-q>', self.destroy) 1994 self._root.bind('<Control-x>', self.destroy) 1995 self._root.bind('<F1>', self.help) 1996 1997 self._root.bind('<Control-s>', self.save_chart) 1998 self._root.bind('<Control-o>', self.load_chart) 1999 self._root.bind('<Control-r>', self.reset) 2000 2001 self._root.bind('t', self.top_down_strategy) 2002 self._root.bind('b', self.bottom_up_strategy) 2003 self._root.bind('c', self.bottom_up_leftcorner_strategy) 2004 self._root.bind('<space>', self._stop_animation) 2005 2006 self._root.bind('<Control-g>', self.edit_grammar) 2007 self._root.bind('<Control-t>', self.edit_sentence) 2008 2009 # Animation speed control 2010 self._root.bind('-', lambda e, a=self._animate: a.set(1)) 2011 self._root.bind('=', lambda e, a=self._animate: a.set(2)) 2012 self._root.bind('+', lambda e, a=self._animate: a.set(3)) 2013 2014 # Step control 2015 self._root.bind('s', lambda e, s=self._step: s.set(not s.get())) 2016 2017 def _init_menubar(self): 2018 menubar = Menu(self._root) 2019 2020 filemenu = Menu(menubar, tearoff=0) 2021 filemenu.add_command( 2022 label='Save Chart', 2023 underline=0, 2024 command=self.save_chart, 2025 accelerator='Ctrl-s', 2026 ) 2027 filemenu.add_command( 2028 label='Load Chart', 2029 underline=0, 2030 command=self.load_chart, 2031 accelerator='Ctrl-o', 2032 ) 2033 filemenu.add_command( 2034 label='Reset Chart', underline=0, command=self.reset, accelerator='Ctrl-r' 2035 ) 2036 filemenu.add_separator() 2037 filemenu.add_command(label='Save Grammar', command=self.save_grammar) 2038 filemenu.add_command(label='Load Grammar', command=self.load_grammar) 2039 filemenu.add_separator() 2040 filemenu.add_command( 2041 label='Exit', underline=1, command=self.destroy, accelerator='Ctrl-x' 2042 ) 2043 menubar.add_cascade(label='File', underline=0, menu=filemenu) 2044 2045 editmenu = Menu(menubar, tearoff=0) 2046 editmenu.add_command( 2047 label='Edit Grammar', 2048 underline=5, 2049 command=self.edit_grammar, 2050 accelerator='Ctrl-g', 2051 ) 2052 editmenu.add_command( 2053 label='Edit Text', 2054 underline=5, 2055 command=self.edit_sentence, 2056 accelerator='Ctrl-t', 2057 ) 2058 menubar.add_cascade(label='Edit', underline=0, menu=editmenu) 2059 2060 viewmenu = Menu(menubar, tearoff=0) 2061 viewmenu.add_command( 2062 label='Chart Matrix', underline=6, command=self.view_matrix 2063 ) 2064 viewmenu.add_command(label='Results', underline=0, command=self.view_results) 2065 menubar.add_cascade(label='View', underline=0, menu=viewmenu) 2066 2067 rulemenu = Menu(menubar, tearoff=0) 2068 rulemenu.add_command( 2069 label='Top Down Strategy', 2070 underline=0, 2071 command=self.top_down_strategy, 2072 accelerator='t', 2073 ) 2074 rulemenu.add_command( 2075 label='Bottom Up Strategy', 2076 underline=0, 2077 command=self.bottom_up_strategy, 2078 accelerator='b', 2079 ) 2080 rulemenu.add_command( 2081 label='Bottom Up Left-Corner Strategy', 2082 underline=0, 2083 command=self.bottom_up_leftcorner_strategy, 2084 accelerator='c', 2085 ) 2086 rulemenu.add_separator() 2087 rulemenu.add_command(label='Bottom Up Rule', command=self.bottom_up) 2088 rulemenu.add_command( 2089 label='Bottom Up Left-Corner Rule', command=self.bottom_up_leftcorner 2090 ) 2091 rulemenu.add_command(label='Top Down Init Rule', command=self.top_down_init) 2092 rulemenu.add_command( 2093 label='Top Down Predict Rule', command=self.top_down_predict 2094 ) 2095 rulemenu.add_command(label='Fundamental Rule', command=self.fundamental) 2096 menubar.add_cascade(label='Apply', underline=0, menu=rulemenu) 2097 2098 animatemenu = Menu(menubar, tearoff=0) 2099 animatemenu.add_checkbutton( 2100 label="Step", underline=0, variable=self._step, accelerator='s' 2101 ) 2102 animatemenu.add_separator() 2103 animatemenu.add_radiobutton( 2104 label="No Animation", underline=0, variable=self._animate, value=0 2105 ) 2106 animatemenu.add_radiobutton( 2107 label="Slow Animation", 2108 underline=0, 2109 variable=self._animate, 2110 value=1, 2111 accelerator='-', 2112 ) 2113 animatemenu.add_radiobutton( 2114 label="Normal Animation", 2115 underline=0, 2116 variable=self._animate, 2117 value=2, 2118 accelerator='=', 2119 ) 2120 animatemenu.add_radiobutton( 2121 label="Fast Animation", 2122 underline=0, 2123 variable=self._animate, 2124 value=3, 2125 accelerator='+', 2126 ) 2127 menubar.add_cascade(label="Animate", underline=1, menu=animatemenu) 2128 2129 zoommenu = Menu(menubar, tearoff=0) 2130 zoommenu.add_radiobutton( 2131 label='Tiny', 2132 variable=self._size, 2133 underline=0, 2134 value=10, 2135 command=self.resize, 2136 ) 2137 zoommenu.add_radiobutton( 2138 label='Small', 2139 variable=self._size, 2140 underline=0, 2141 value=12, 2142 command=self.resize, 2143 ) 2144 zoommenu.add_radiobutton( 2145 label='Medium', 2146 variable=self._size, 2147 underline=0, 2148 value=14, 2149 command=self.resize, 2150 ) 2151 zoommenu.add_radiobutton( 2152 label='Large', 2153 variable=self._size, 2154 underline=0, 2155 value=18, 2156 command=self.resize, 2157 ) 2158 zoommenu.add_radiobutton( 2159 label='Huge', 2160 variable=self._size, 2161 underline=0, 2162 value=24, 2163 command=self.resize, 2164 ) 2165 menubar.add_cascade(label='Zoom', underline=0, menu=zoommenu) 2166 2167 helpmenu = Menu(menubar, tearoff=0) 2168 helpmenu.add_command(label='About', underline=0, command=self.about) 2169 helpmenu.add_command( 2170 label='Instructions', underline=0, command=self.help, accelerator='F1' 2171 ) 2172 menubar.add_cascade(label='Help', underline=0, menu=helpmenu) 2173 2174 self._root.config(menu=menubar) 2175 2176 # //////////////////////////////////////////////////////////// 2177 # Selection Handling 2178 # //////////////////////////////////////////////////////////// 2179 2180 def _click_cv_edge(self, edge): 2181 if edge != self._selection: 2182 # Clicking on a new edge selects it. 2183 self._select_edge(edge) 2184 else: 2185 # Repeated clicks on one edge cycle its trees. 2186 self._cv.cycle_tree() 2187 # [XX] this can get confused if animation is running 2188 # faster than the callbacks... 2189 2190 def _select_matrix_edge(self, edge): 2191 self._select_edge(edge) 2192 self._cv.view_edge(edge) 2193 2194 def _select_edge(self, edge): 2195 self._selection = edge 2196 # Update the chart view. 2197 self._cv.markonly_edge(edge, '#f00') 2198 self._cv.draw_tree(edge) 2199 # Update the matrix view. 2200 if self._matrix: 2201 self._matrix.markonly_edge(edge) 2202 if self._matrix: 2203 self._matrix.view_edge(edge) 2204 2205 def _deselect_edge(self): 2206 self._selection = None 2207 # Update the chart view. 2208 self._cv.unmark_edge() 2209 self._cv.erase_tree() 2210 # Update the matrix view 2211 if self._matrix: 2212 self._matrix.unmark_edge() 2213 2214 def _show_new_edge(self, edge): 2215 self._display_rule(self._cp.current_chartrule()) 2216 # Update the chart view. 2217 self._cv.update() 2218 self._cv.draw_tree(edge) 2219 self._cv.markonly_edge(edge, '#0df') 2220 self._cv.view_edge(edge) 2221 # Update the matrix view. 2222 if self._matrix: 2223 self._matrix.update() 2224 if self._matrix: 2225 self._matrix.markonly_edge(edge) 2226 if self._matrix: 2227 self._matrix.view_edge(edge) 2228 # Update the results view. 2229 if self._results: 2230 self._results.update(edge) 2231 2232 # //////////////////////////////////////////////////////////// 2233 # Help/usage 2234 # //////////////////////////////////////////////////////////// 2235 2236 def help(self, *e): 2237 self._animating = 0 2238 # The default font's not very legible; try using 'fixed' instead. 2239 try: 2240 ShowText( 2241 self._root, 2242 'Help: Chart Parser Application', 2243 (__doc__ or '').strip(), 2244 width=75, 2245 font='fixed', 2246 ) 2247 except: 2248 ShowText( 2249 self._root, 2250 'Help: Chart Parser Application', 2251 (__doc__ or '').strip(), 2252 width=75, 2253 ) 2254 2255 def about(self, *e): 2256 ABOUT = "NLTK Chart Parser Application\n" + "Written by Edward Loper" 2257 showinfo('About: Chart Parser Application', ABOUT) 2258 2259 # //////////////////////////////////////////////////////////// 2260 # File Menu 2261 # //////////////////////////////////////////////////////////// 2262 2263 CHART_FILE_TYPES = [('Pickle file', '.pickle'), ('All files', '*')] 2264 GRAMMAR_FILE_TYPES = [ 2265 ('Plaintext grammar file', '.cfg'), 2266 ('Pickle file', '.pickle'), 2267 ('All files', '*'), 2268 ] 2269 2270 def load_chart(self, *args): 2271 "Load a chart from a pickle file" 2272 filename = askopenfilename( 2273 filetypes=self.CHART_FILE_TYPES, defaultextension='.pickle' 2274 ) 2275 if not filename: 2276 return 2277 try: 2278 with open(filename, 'rb') as infile: 2279 chart = pickle.load(infile) 2280 self._chart = chart 2281 self._cv.update(chart) 2282 if self._matrix: 2283 self._matrix.set_chart(chart) 2284 if self._matrix: 2285 self._matrix.deselect_cell() 2286 if self._results: 2287 self._results.set_chart(chart) 2288 self._cp.set_chart(chart) 2289 except Exception as e: 2290 raise 2291 showerror('Error Loading Chart', 'Unable to open file: %r' % filename) 2292 2293 def save_chart(self, *args): 2294 "Save a chart to a pickle file" 2295 filename = asksaveasfilename( 2296 filetypes=self.CHART_FILE_TYPES, defaultextension='.pickle' 2297 ) 2298 if not filename: 2299 return 2300 try: 2301 with open(filename, 'wb') as outfile: 2302 pickle.dump(self._chart, outfile) 2303 except Exception as e: 2304 raise 2305 showerror('Error Saving Chart', 'Unable to open file: %r' % filename) 2306 2307 def load_grammar(self, *args): 2308 "Load a grammar from a pickle file" 2309 filename = askopenfilename( 2310 filetypes=self.GRAMMAR_FILE_TYPES, defaultextension='.cfg' 2311 ) 2312 if not filename: 2313 return 2314 try: 2315 if filename.endswith('.pickle'): 2316 with open(filename, 'rb') as infile: 2317 grammar = pickle.load(infile) 2318 else: 2319 with open(filename, 'r') as infile: 2320 grammar = CFG.fromstring(infile.read()) 2321 self.set_grammar(grammar) 2322 except Exception as e: 2323 showerror('Error Loading Grammar', 'Unable to open file: %r' % filename) 2324 2325 def save_grammar(self, *args): 2326 filename = asksaveasfilename( 2327 filetypes=self.GRAMMAR_FILE_TYPES, defaultextension='.cfg' 2328 ) 2329 if not filename: 2330 return 2331 try: 2332 if filename.endswith('.pickle'): 2333 with open(filename, 'wb') as outfile: 2334 pickle.dump((self._chart, self._tokens), outfile) 2335 else: 2336 with open(filename, 'w') as outfile: 2337 prods = self._grammar.productions() 2338 start = [p for p in prods if p.lhs() == self._grammar.start()] 2339 rest = [p for p in prods if p.lhs() != self._grammar.start()] 2340 for prod in start: 2341 outfile.write('%s\n' % prod) 2342 for prod in rest: 2343 outfile.write('%s\n' % prod) 2344 except Exception as e: 2345 showerror('Error Saving Grammar', 'Unable to open file: %r' % filename) 2346 2347 def reset(self, *args): 2348 self._animating = 0 2349 self._reset_parser() 2350 self._cv.update(self._chart) 2351 if self._matrix: 2352 self._matrix.set_chart(self._chart) 2353 if self._matrix: 2354 self._matrix.deselect_cell() 2355 if self._results: 2356 self._results.set_chart(self._chart) 2357 2358 # //////////////////////////////////////////////////////////// 2359 # Edit 2360 # //////////////////////////////////////////////////////////// 2361 2362 def edit_grammar(self, *e): 2363 CFGEditor(self._root, self._grammar, self.set_grammar) 2364 2365 def set_grammar(self, grammar): 2366 self._grammar = grammar 2367 self._cp.set_grammar(grammar) 2368 if self._results: 2369 self._results.set_grammar(grammar) 2370 2371 def edit_sentence(self, *e): 2372 sentence = " ".join(self._tokens) 2373 title = 'Edit Text' 2374 instr = 'Enter a new sentence to parse.' 2375 EntryDialog(self._root, sentence, instr, self.set_sentence, title) 2376 2377 def set_sentence(self, sentence): 2378 self._tokens = list(sentence.split()) 2379 self.reset() 2380 2381 # //////////////////////////////////////////////////////////// 2382 # View Menu 2383 # //////////////////////////////////////////////////////////// 2384 2385 def view_matrix(self, *e): 2386 if self._matrix is not None: 2387 self._matrix.destroy() 2388 self._matrix = ChartMatrixView(self._root, self._chart) 2389 self._matrix.add_callback('select', self._select_matrix_edge) 2390 2391 def view_results(self, *e): 2392 if self._results is not None: 2393 self._results.destroy() 2394 self._results = ChartResultsView(self._root, self._chart, self._grammar) 2395 2396 # //////////////////////////////////////////////////////////// 2397 # Zoom Menu 2398 # //////////////////////////////////////////////////////////// 2399 2400 def resize(self): 2401 self._animating = 0 2402 self.set_font_size(self._size.get()) 2403 2404 def set_font_size(self, size): 2405 self._cv.set_font_size(size) 2406 self._font.configure(size=-abs(size)) 2407 self._boldfont.configure(size=-abs(size)) 2408 self._sysfont.configure(size=-abs(size)) 2409 2410 def get_font_size(self): 2411 return abs(self._size.get()) 2412 2413 # //////////////////////////////////////////////////////////// 2414 # Parsing 2415 # //////////////////////////////////////////////////////////// 2416 2417 def apply_strategy(self, strategy, edge_strategy=None): 2418 # If we're animating, then stop. 2419 if self._animating: 2420 self._animating = 0 2421 return 2422 2423 # Clear the rule display & mark. 2424 self._display_rule(None) 2425 # self._cv.unmark_edge() 2426 2427 if self._step.get(): 2428 selection = self._selection 2429 if (selection is not None) and (edge_strategy is not None): 2430 # Apply the given strategy to the selected edge. 2431 self._cp.set_strategy([edge_strategy(selection)]) 2432 newedge = self._apply_strategy() 2433 2434 # If it failed, then clear the selection. 2435 if newedge is None: 2436 self._cv.unmark_edge() 2437 self._selection = None 2438 else: 2439 self._cp.set_strategy(strategy) 2440 self._apply_strategy() 2441 2442 else: 2443 self._cp.set_strategy(strategy) 2444 if self._animate.get(): 2445 self._animating = 1 2446 self._animate_strategy() 2447 else: 2448 for edge in self._cpstep: 2449 if edge is None: 2450 break 2451 self._cv.update() 2452 if self._matrix: 2453 self._matrix.update() 2454 if self._results: 2455 self._results.update() 2456 2457 def _stop_animation(self, *e): 2458 self._animating = 0 2459 2460 def _animate_strategy(self, speed=1): 2461 if self._animating == 0: 2462 return 2463 if self._apply_strategy() is not None: 2464 if self._animate.get() == 0 or self._step.get() == 1: 2465 return 2466 if self._animate.get() == 1: 2467 self._root.after(3000, self._animate_strategy) 2468 elif self._animate.get() == 2: 2469 self._root.after(1000, self._animate_strategy) 2470 else: 2471 self._root.after(20, self._animate_strategy) 2472 2473 def _apply_strategy(self): 2474 new_edge = next(self._cpstep) 2475 2476 if new_edge is not None: 2477 self._show_new_edge(new_edge) 2478 return new_edge 2479 2480 def _display_rule(self, rule): 2481 if rule is None: 2482 self._rulelabel2['text'] = '' 2483 else: 2484 name = str(rule) 2485 self._rulelabel2['text'] = name 2486 size = self._cv.get_font_size() 2487 2488 # //////////////////////////////////////////////////////////// 2489 # Parsing Strategies 2490 # //////////////////////////////////////////////////////////// 2491 2492 # Basic rules: 2493 _TD_INIT = [TopDownInitRule()] 2494 _TD_PREDICT = [TopDownPredictRule()] 2495 _BU_RULE = [BottomUpPredictRule()] 2496 _BU_LC_RULE = [BottomUpPredictCombineRule()] 2497 _FUNDAMENTAL = [SingleEdgeFundamentalRule()] 2498 2499 # Complete strategies: 2500 _TD_STRATEGY = _TD_INIT + _TD_PREDICT + _FUNDAMENTAL 2501 _BU_STRATEGY = _BU_RULE + _FUNDAMENTAL 2502 _BU_LC_STRATEGY = _BU_LC_RULE + _FUNDAMENTAL 2503 2504 # Button callback functions: 2505 def top_down_init(self, *e): 2506 self.apply_strategy(self._TD_INIT, None) 2507 2508 def top_down_predict(self, *e): 2509 self.apply_strategy(self._TD_PREDICT, TopDownPredictEdgeRule) 2510 2511 def bottom_up(self, *e): 2512 self.apply_strategy(self._BU_RULE, BottomUpEdgeRule) 2513 2514 def bottom_up_leftcorner(self, *e): 2515 self.apply_strategy(self._BU_LC_RULE, BottomUpLeftCornerEdgeRule) 2516 2517 def fundamental(self, *e): 2518 self.apply_strategy(self._FUNDAMENTAL, FundamentalEdgeRule) 2519 2520 def bottom_up_strategy(self, *e): 2521 self.apply_strategy(self._BU_STRATEGY, BottomUpEdgeRule) 2522 2523 def bottom_up_leftcorner_strategy(self, *e): 2524 self.apply_strategy(self._BU_LC_STRATEGY, BottomUpLeftCornerEdgeRule) 2525 2526 def top_down_strategy(self, *e): 2527 self.apply_strategy(self._TD_STRATEGY, TopDownPredictEdgeRule) 2528 2529 2530def app(): 2531 grammar = CFG.fromstring( 2532 """ 2533 # Grammatical productions. 2534 S -> NP VP 2535 VP -> VP PP | V NP | V 2536 NP -> Det N | NP PP 2537 PP -> P NP 2538 # Lexical productions. 2539 NP -> 'John' | 'I' 2540 Det -> 'the' | 'my' | 'a' 2541 N -> 'dog' | 'cookie' | 'table' | 'cake' | 'fork' 2542 V -> 'ate' | 'saw' 2543 P -> 'on' | 'under' | 'with' 2544 """ 2545 ) 2546 2547 sent = 'John ate the cake on the table with a fork' 2548 sent = 'John ate the cake on the table' 2549 tokens = list(sent.split()) 2550 2551 print('grammar= (') 2552 for rule in grammar.productions(): 2553 print((' ', repr(rule) + ',')) 2554 print(')') 2555 print(('tokens = %r' % tokens)) 2556 print('Calling "ChartParserApp(grammar, tokens)"...') 2557 ChartParserApp(grammar, tokens).mainloop() 2558 2559 2560if __name__ == '__main__': 2561 app() 2562 2563 # Chart comparer: 2564 # charts = ['/tmp/earley.pickle', 2565 # '/tmp/topdown.pickle', 2566 # '/tmp/bottomup.pickle'] 2567 # ChartComparer(*charts).mainloop() 2568 2569 # import profile 2570 # profile.run('demo2()', '/tmp/profile.out') 2571 # import pstats 2572 # p = pstats.Stats('/tmp/profile.out') 2573 # p.strip_dirs().sort_stats('time', 'cum').print_stats(60) 2574 # p.strip_dirs().sort_stats('cum', 'time').print_stats(60) 2575 2576__all__ = ['app'] 2577