1
2
3
4
5
6
7
8
9
10
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
39
40
41 import pickle
42 from tkFileDialog import asksaveasfilename, askopenfilename
43 import Tkinter, tkFont, tkMessageBox
44 import math, string
45 import os.path
46
47 from nltk_lite.parse.chart import *
48 from nltk_lite.parse import cfg
49 from nltk_lite import tokenize
50 from nltk_lite.parse.tree import Tree
51 from nltk_lite.draw import ShowText, EntryDialog, in_idle
52 from nltk_lite.draw import MutableOptionMenu
53 from nltk_lite.draw import ColorizedList, SymbolWidget, CanvasFrame
54 from nltk_lite.draw.cfg import CFGEditor
55 from nltk_lite.draw.tree import tree_to_treesegment, TreeSegmentWidget
56
57
58
59
60
61
62
63
88
89
90
91
92
94 """
95 A view of a chart that displays the contents of the corresponding matrix.
96 """
97 - def __init__(self, parent, chart, toplevel=True, title='Chart Matrix',
98 show_numedges=False):
99 self._chart = chart
100 self._cells = []
101 self._marks = []
102
103 self._selected_cell = None
104
105 if toplevel:
106 self._root = Tkinter.Toplevel(parent)
107 self._root.title(title)
108 self._root.bind('<Control-q>', self.destroy)
109 self._init_quit(self._root)
110 else:
111 self._root = Tkinter.Frame(parent)
112
113 self._init_matrix(self._root)
114 self._init_list(self._root)
115 if show_numedges:
116 self._init_numedges(self._root)
117 else:
118 self._numedges_label = None
119
120 self._callbacks = {}
121
122 self._num_edges = 0
123
124 self.draw()
125
129
131 cframe = Tkinter.Frame(root, border=2, relief='sunken')
132 cframe.pack(expand=0, fill='none', padx=1, pady=3, side='top')
133 self._canvas = Tkinter.Canvas(cframe, width=200, height=200,
134 background='white')
135 self._canvas.pack(expand=0, fill='none')
136
138 self._numedges_label = Tkinter.Label(root, text='0 edges')
139 self._numedges_label.pack(expand=0, fill='none', side='top')
140
147
149 if self._root is None: return
150 try: self._root.destroy()
151 except: pass
152 self._root = None
153
155 if chart is not self._chart:
156 self._chart = chart
157 self._num_edges = 0
158 self.draw()
159
161 if self._root is None: return
162
163
164 N = len(self._cells)
165 cell_edges = [[0 for i in range(N)] for j in range(N)]
166 for edge in self._chart:
167 cell_edges[edge.start()][edge.end()] += 1
168
169
170 for i in range(N):
171 for j in range(i, N):
172 if cell_edges[i][j] == 0:
173 color = 'gray20'
174 else:
175 color = ('#00%02x%02x' %
176 (min(255, 50+128*cell_edges[i][j]/10),
177 max(0, 128-128*cell_edges[i][j]/10)))
178 cell_tag = self._cells[i][j]
179 self._canvas.itemconfig(cell_tag, fill=color)
180 if (i,j) == self._selected_cell:
181 self._canvas.itemconfig(cell_tag, outline='#00ffff',
182 width=3)
183 self._canvas.tag_raise(cell_tag)
184 else:
185 self._canvas.itemconfig(cell_tag, outline='black',
186 width=1)
187
188
189 edges = list(self._chart.select(span=self._selected_cell))
190 self._list.set(edges)
191
192
193 self._num_edges = self._chart.num_edges()
194 if self._numedges_label is not None:
195 self._numedges_label['text'] = '%d edges' % self._num_edges
196
198 self._canvas.itemconfig('inactivebox', state='hidden')
199 self.update()
200
202 self._canvas.itemconfig('inactivebox', state='normal')
203 self.update()
204
206 self._callbacks.setdefault(event,{})[func] = 1
207
209 if func is None: del self._callbacks[event]
210 else:
211 try: del self._callbacks[event][func]
212 except: pass
213
215 if not self._callbacks.has_key(event): return
216 for cb_func in self._callbacks[event].keys(): cb_func(*args)
217
219 if self._root is None: return
220
221
222
223 if ((i,j) == self._selected_cell and
224 self._chart.num_edges() == self._num_edges): return
225
226 self._selected_cell = (i,j)
227 self.update()
228
229
230 self._fire_callbacks('select_cell', i, j)
231
233 if self._root is None: return
234 self._selected_cell = None
235 self._list.set([])
236 self.update()
237
243
247
252
254 if self._root is None: return
255 self._list.unmark(edge)
256
261
263 if self._root is None: return
264 LEFT_MARGIN = BOT_MARGIN = 15
265 TOP_MARGIN = 5
266 c = self._canvas
267 c.delete('all')
268 N = self._chart.num_leaves()+1
269 dx = (int(c['width'])-LEFT_MARGIN)/N
270 dy = (int(c['height'])-TOP_MARGIN-BOT_MARGIN)/N
271
272 c.delete('all')
273
274
275 for i in range(N):
276 c.create_text(LEFT_MARGIN-2, i*dy+dy/2+TOP_MARGIN,
277 text=`i`, anchor='e')
278 c.create_text(i*dx+dx/2+LEFT_MARGIN, N*dy+TOP_MARGIN+1,
279 text=`i`, anchor='n')
280 c.create_line(LEFT_MARGIN, dy*(i+1)+TOP_MARGIN,
281 dx*N+LEFT_MARGIN, dy*(i+1)+TOP_MARGIN, dash='.')
282 c.create_line(dx*i+LEFT_MARGIN, TOP_MARGIN,
283 dx*i+LEFT_MARGIN, dy*N+TOP_MARGIN, dash='.')
284
285
286 c.create_rectangle(LEFT_MARGIN, TOP_MARGIN,
287 LEFT_MARGIN+dx*N, dy*N+TOP_MARGIN,
288 width=2)
289
290
291 self._cells = [[None for i in range(N)] for j in range(N)]
292 for i in range(N):
293 for j in range(i, N):
294 t = c.create_rectangle(j*dx+LEFT_MARGIN, i*dy+TOP_MARGIN,
295 (j+1)*dx+LEFT_MARGIN,
296 (i+1)*dy+TOP_MARGIN,
297 fill='gray20')
298 self._cells[i][j] = t
299 def cb(event, self=self, i=i, j=j): self._click_cell(i,j)
300 c.tag_bind(t, '<Button-1>', cb)
301
302
303 xmax, ymax = int(c['width']), int(c['height'])
304 t = c.create_rectangle(-100, -100, xmax+100, ymax+100,
305 fill='gray50', state='hidden',
306 tag='inactivebox')
307 c.tag_lower(t)
308
309
310 self.update()
311
312 - def pack(self, *args, **kwargs):
314
315
316
317
318
320 - def __init__(self, parent, chart, grammar, toplevel=True):
321 self._chart = chart
322 self._grammar = grammar
323 self._trees = []
324 self._y = 10
325 self._treewidgets = []
326 self._selection = None
327 self._selectbox = None
328
329 if toplevel:
330 self._root = Tkinter.Toplevel(parent)
331 self._root.title('Chart Parsing Demo: Results')
332 self._root.bind('<Control-q>', self.destroy)
333 else:
334 self._root = Tkinter.Frame(parent)
335
336
337 if toplevel:
338 buttons = Tkinter.Frame(self._root)
339 buttons.pack(side='bottom', expand=0, fill='x')
340 Tkinter.Button(buttons, text='Quit',
341 command=self.destroy).pack(side='right')
342 Tkinter.Button(buttons, text='Print All',
343 command=self.print_all).pack(side='left')
344 Tkinter.Button(buttons, text='Print Selection',
345 command=self.print_selection).pack(side='left')
346
347
348 self._cframe = CanvasFrame(self._root, closeenough=20)
349 self._cframe.pack(side='top', expand=1, fill='both')
350
351
352 self.update()
353
355 if self._root is None: return
356
357 if edge is not None:
358 if edge.lhs() != self._grammar.start(): return
359 if edge.span() != (0, self._chart.num_leaves()): return
360
361 for parse in self._chart.parses(self._grammar.start()):
362 if parse not in self._trees:
363 self._add(parse)
364
365 - def _add(self, parse):
382
384 c = self._cframe.canvas()
385 if self._selection is not None:
386 c.delete(self._selectbox)
387 self._selection = widget
388 (x1, y1, x2, y2) = widget.bbox()
389 self._selectbox = c.create_rectangle(x1, y1, x2, y2,
390 width=2, outline='#088')
391
392 - def _color(self, treewidget, color):
399
401 if self._root is None: return
402 self._cframe.print_to_file()
403
405 if self._root is None: return
406 if self._selection is None:
407 tkMessageBox.showerror('Print Error', 'No tree selected')
408 else:
409 c = self._cframe.canvas()
410 for widget in self._treewidgets:
411 if widget is not self._selection:
412 self._cframe.destroy_widget(widget)
413 c.delete(self._selectbox)
414 (x1,y1,x2,y2) = self._selection.bbox()
415 self._selection.move(10-x1,10-y1)
416 c['scrollregion'] = '0 0 %s %s' % (x2-x1+20, y2-y1+20)
417 self._cframe.print_to_file()
418
419
420 self._treewidgets = [self._selection]
421 self.clear()
422 self.update()
423
425 if self._root is None: return
426 for treewidget in self._treewidgets:
427 self._cframe.destroy_widget(treewidget)
428 self._trees = []
429 self._treewidgets = []
430 if self._selection is not None:
431 self._cframe.canvas().delete(self._selectbox)
432 self._selection = None
433 self._y = 10
434
439
444
446 if self._root is None: return
447 try: self._root.destroy()
448 except: pass
449 self._root = None
450
451 - def pack(self, *args, **kwargs):
453
454
455
456
457
459 """
460
461 @ivar _root: The root window
462
463 @ivar _charts: A dictionary mapping names to charts. When
464 charts are loaded, they are added to this dictionary.
465
466 @ivar _left_chart: The left L{Chart}.
467 @ivar _left_name: The name C{_left_chart} (derived from filename)
468 @ivar _left_matrix: The L{ChartMatrixView} for C{_left_chart}
469 @ivar _left_selector: The drop-down L{MutableOptionsMenu} used
470 to select C{_left_chart}.
471
472 @ivar _right_chart: The right L{Chart}.
473 @ivar _right_name: The name C{_right_chart} (derived from filename)
474 @ivar _right_matrix: The L{ChartMatrixView} for C{_right_chart}
475 @ivar _right_selector: The drop-down L{MutableOptionsMenu} used
476 to select C{_right_chart}.
477
478 @ivar _out_chart: The out L{Chart}.
479 @ivar _out_name: The name C{_out_chart} (derived from filename)
480 @ivar _out_matrix: The L{ChartMatrixView} for C{_out_chart}
481 @ivar _out_label: The label for C{_out_chart}.
482
483 @ivar _op_label: A Label containing the most recent operation.
484 """
485
486 _OPSYMBOL = {'-': '-',
487 'and': SymbolWidget.SYMBOLS['intersection'],
488 'or': SymbolWidget.SYMBOLS['union']}
489
491
492
493 faketok = [''] * 8
494 self._emptychart = Chart(faketok)
495
496
497 self._left_name = 'None'
498 self._right_name = 'None'
499 self._left_chart = self._emptychart
500 self._right_chart = self._emptychart
501
502
503 self._charts = {'None': self._emptychart}
504
505
506 self._out_chart = self._emptychart
507
508
509 self._operator = None
510
511
512 self._root = Tkinter.Tk()
513 self._root.title('Chart Comparison')
514 self._root.bind('<Control-q>', self.destroy)
515 self._root.bind('<Control-x>', self.destroy)
516
517
518 self._init_menubar(self._root)
519 self._init_chartviews(self._root)
520 self._init_divider(self._root)
521 self._init_buttons(self._root)
522 self._init_bindings(self._root)
523
524
525 for filename in chart_filenames:
526 self.load_chart(filename)
527
529 if self._root is None: return
530 try: self._root.destroy()
531 except: pass
532 self._root = None
533
534 - def mainloop(self, *args, **kwargs):
535 return
536 self._root.mainloop(*args, **kwargs)
537
538
539
540
541
543 menubar = Tkinter.Menu(root)
544
545
546 filemenu = Tkinter.Menu(menubar, tearoff=0)
547 filemenu.add_command(label='Load Chart', accelerator='Ctrl-o',
548 underline=0, command=self.load_chart_dialog)
549 filemenu.add_command(label='Save Output', accelerator='Ctrl-s',
550 underline=0, command=self.save_chart_dialog)
551 filemenu.add_separator()
552 filemenu.add_command(label='Exit', underline=1,
553 command=self.destroy, accelerator='Ctrl-x')
554 menubar.add_cascade(label='File', underline=0, menu=filemenu)
555
556
557 opmenu = Tkinter.Menu(menubar, tearoff=0)
558 opmenu.add_command(label='Intersection',
559 command=self._intersection,
560 accelerator='+')
561 opmenu.add_command(label='Union',
562 command=self._union,
563 accelerator='*')
564 opmenu.add_command(label='Difference',
565 command=self._difference,
566 accelerator='-')
567 opmenu.add_separator()
568 opmenu.add_command(label='Swap Charts',
569 command=self._swapcharts)
570 menubar.add_cascade(label='Compare', underline=0, menu=opmenu)
571
572
573 self._root.config(menu=menubar)
574
576 divider = Tkinter.Frame(root, border=2, relief='sunken')
577 divider.pack(side='top', fill='x', ipady=2)
578
580 opfont=('symbol', -36)
581 eqfont=('helvetica', -36)
582
583 frame = Tkinter.Frame(root, background='#c0c0c0')
584 frame.pack(side='top', expand=1, fill='both')
585
586
587 cv1_frame = Tkinter.Frame(frame, border=3, relief='groove')
588 cv1_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both')
589 self._left_selector = MutableOptionMenu(
590 cv1_frame, self._charts.keys(), command=self._select_left)
591 self._left_selector.pack(side='top', pady=5, fill='x')
592 self._left_matrix = ChartMatrixView(cv1_frame, self._emptychart,
593 toplevel=False,
594 show_numedges=True)
595 self._left_matrix.pack(side='bottom', padx=5, pady=5,
596 expand=1, fill='both')
597 self._left_matrix.add_callback('select', self.select_edge)
598 self._left_matrix.add_callback('select_cell', self.select_cell)
599 self._left_matrix.inactivate()
600
601
602 self._op_label = Tkinter.Label(frame, text=' ', width=3,
603 background='#c0c0c0', font=opfont)
604 self._op_label.pack(side='left', padx=5, pady=5)
605
606
607 cv2_frame = Tkinter.Frame(frame, border=3, relief='groove')
608 cv2_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both')
609 self._right_selector = MutableOptionMenu(
610 cv2_frame, self._charts.keys(), command=self._select_right)
611 self._right_selector.pack(side='top', pady=5, fill='x')
612 self._right_matrix = ChartMatrixView(cv2_frame, self._emptychart,
613 toplevel=False,
614 show_numedges=True)
615 self._right_matrix.pack(side='bottom', padx=5, pady=5,
616 expand=1, fill='both')
617 self._right_matrix.add_callback('select', self.select_edge)
618 self._right_matrix.add_callback('select_cell', self.select_cell)
619 self._right_matrix.inactivate()
620
621
622 Tkinter.Label(frame, text='=', width=3, background='#c0c0c0',
623 font=eqfont).pack(side='left', padx=5, pady=5)
624
625
626 out_frame = Tkinter.Frame(frame, border=3, relief='groove')
627 out_frame.pack(side='left', padx=8, pady=7, expand=1, fill='both')
628 self._out_label = Tkinter.Label(out_frame, text='Output')
629 self._out_label.pack(side='top', pady=9)
630 self._out_matrix = ChartMatrixView(out_frame, self._emptychart,
631 toplevel=False,
632 show_numedges=True)
633 self._out_matrix.pack(side='bottom', padx=5, pady=5,
634 expand=1, fill='both')
635 self._out_matrix.add_callback('select', self.select_edge)
636 self._out_matrix.add_callback('select_cell', self.select_cell)
637 self._out_matrix.inactivate()
638
654
658
659
660
661
662
663
670
677
682
683
684
685
686
687 CHART_FILE_TYPES = [('Pickle file', '.pickle'),
688 ('All files', '*')]
689
691 filename = asksaveasfilename(filetypes=self.CHART_FILE_TYPES,
692 defaultextension='.pickle')
693 if not filename: return
694 try: pickle.dump((self._out_chart), open(filename, 'w'))
695 except Exception, e:
696 tkMessageBox.showerror('Error Saving Chart',
697 'Unable to open file: %r\n%s' %
698 (filename, e))
699
701 filename = askopenfilename(filetypes=self.CHART_FILE_TYPES,
702 defaultextension='.pickle')
703 if not filename: return
704 try: self.load_chart(filename)
705 except Exception, e:
706 tkMessageBox.showerror('Error Loading Chart',
707 'Unable to open file: %r\n%s' %
708 (filename, e))
709
711 chart = pickle.load(open(filename, 'r'))
712 name = os.path.basename(filename)
713 if name.endswith('.pickle'): name = name[:-7]
714 if name.endswith('.chart'): name = name[:-6]
715 self._charts[name] = chart
716 self._left_selector.add(name)
717 self._right_selector.add(name)
718
719
720
721 if self._left_chart is self._emptychart:
722 self._left_selector.set(name)
723 elif self._right_chart is self._emptychart:
724 self._right_selector.set(name)
725
727 self._left_matrix.update()
728 self._right_matrix.update()
729 self._out_matrix.update()
730
731
732
733
734
736 if edge in self._left_chart:
737 self._left_matrix.markonly_edge(edge)
738 else:
739 self._left_matrix.unmark_edge()
740 if edge in self._right_chart:
741 self._right_matrix.markonly_edge(edge)
742 else:
743 self._right_matrix.unmark_edge()
744 if edge in self._out_chart:
745 self._out_matrix.markonly_edge(edge)
746 else:
747 self._out_matrix.unmark_edge()
748
753
754
755
756
757
759 if not self._checkcompat(): return
760
761 out_chart = Chart(self._left_chart.tokens())
762 for edge in self._left_chart:
763 if edge not in self._right_chart:
764 out_chart.insert(edge, [])
765
766 self._update('-', out_chart)
767
769 if not self._checkcompat(): return
770
771 out_chart = Chart(self._left_chart.tokens())
772 for edge in self._left_chart:
773 if edge in self._right_chart:
774 out_chart.insert(edge, [])
775
776 self._update('and', out_chart)
777
779 if not self._checkcompat(): return
780
781 out_chart = Chart(self._left_chart.tokens())
782 for edge in self._left_chart:
783 out_chart.insert(edge, [])
784 for edge in self._right_chart:
785 out_chart.insert(edge, [])
786
787 self._update('or', out_chart)
788
790 left, right = self._left_name, self._right_name
791 self._left_selector.set(right)
792 self._right_selector.set(left)
793
795 if (self._left_chart.tokens() != self._right_chart.tokens() or
796 self._left_chart.property_names() !=
797 self._right_chart.property_names() or
798 self._left_chart == self._emptychart or
799 self._right_chart == self._emptychart):
800
801 self._out_chart = self._emptychart
802 self._out_matrix.set_chart(self._out_chart)
803 self._out_matrix.inactivate()
804 self._out_label['text'] = 'Output'
805
806 return False
807 else:
808 return True
809
810 - def _update(self, operator, out_chart):
811 self._operator = operator
812 self._op_label['text'] = self._OPSYMBOL[operator]
813 self._out_chart = out_chart
814 self._out_matrix.set_chart(out_chart)
815 self._out_label['text'] = '%s %s %s' % (self._left_name,
816 self._operator,
817 self._right_name)
818
820 self._out_chart = self._emptychart
821 self._out_matrix.set_chart(self._out_chart)
822 self._op_label['text'] = ' '
823 self._out_matrix.inactivate()
824
826 ChartMatrixView(self._root, self._out_chart,
827 title=self._out_label['text'])
828
829
830
831
832
833
834
835
836
837
838
839
841 """
842 A component for viewing charts. This is used by C{ChartDemo} to
843 allow students to interactively experiment with various chart
844 parsing techniques. It is also used by C{Chart.draw()}.
845
846 @ivar _chart: The chart that we are giving a view of. This chart
847 may be modified; after it is modified, you should call
848 C{update}.
849 @ivar _sentence: The list of tokens that the chart spans.
850
851 @ivar _root: The root window.
852 @ivar _chart_canvas: The canvas we're using to display the chart
853 itself.
854 @ivar _tree_canvas: The canvas we're using to display the tree
855 that each edge spans. May be None, if we're not displaying
856 trees.
857 @ivar _sentence_canvas: The canvas we're using to display the sentence
858 text. May be None, if we're not displaying the sentence text.
859 @ivar _edgetags: A dictionary mapping from edges to the tags of
860 the canvas elements (lines, etc) used to display that edge.
861 The values of this dictionary have the form
862 C{(linetag, rhstag1, dottag, rhstag2, lhstag)}.
863 @ivar _treetags: A list of all the tags that make up the tree;
864 used to erase the tree (without erasing the loclines).
865 @ivar _chart_height: The height of the chart canvas.
866 @ivar _sentence_height: The height of the sentence canvas.
867 @ivar _tree_height: The height of the tree
868
869 @ivar _text_height: The height of a text string (in the normal
870 font).
871
872 @ivar _edgelevels: A list of edges at each level of the chart (the
873 top level is the 0th element). This list is used to remember
874 where edges should be drawn; and to make sure that no edges
875 are overlapping on the chart view.
876
877 @ivar _unitsize: Pixel size of one unit (from the location). This
878 is determined by the span of the chart's location, and the
879 width of the chart display canvas.
880
881 @ivar _fontsize: The current font size
882
883 @ivar _marks: A dictionary from edges to marks. Marks are
884 strings, specifying colors (e.g. 'green').
885 """
886
887 _LEAF_SPACING = 10
888 _MARGIN = 10
889 _TREE_LEVEL_SIZE = 12
890 _CHART_LEVEL_SIZE = 40
891
892 - def __init__(self, chart, root=None, **kw):
893 """
894 Construct a new C{Chart} display.
895 """
896
897 draw_tree = kw.get('draw_tree', 0)
898 draw_sentence = kw.get('draw_sentence', 1)
899 self._fontsize = kw.get('fontsize', -12)
900
901
902 self._chart = chart
903
904
905 self._callbacks = {}
906
907
908 self._edgelevels = []
909 self._edgetags = {}
910
911
912 self._marks = {}
913
914
915
916 self._treetoks = []
917 self._treetoks_edge = None
918 self._treetoks_index = 0
919
920
921 self._tree_tags = []
922
923
924 self._compact = 0
925
926
927 if root is None:
928 top = Tkinter.Tk()
929 top.title('Chart View')
930 def destroy1(e, top=top): top.destroy()
931 def destroy2(top=top): top.destroy()
932 top.bind('q', destroy1)
933 b = Tkinter.Button(top, text='Done', command=destroy2)
934 b.pack(side='bottom')
935 self._root = top
936 else:
937 self._root = root
938
939
940 self._init_fonts(root)
941
942
943 (self._chart_sb, self._chart_canvas) = self._sb_canvas(self._root)
944 self._chart_canvas['height'] = 300
945 self._chart_canvas['closeenough'] = 15
946
947
948 if draw_sentence:
949 cframe = Tkinter.Frame(self._root, relief='sunk', border=2)
950 cframe.pack(fill='both', side='bottom')
951 self._sentence_canvas = Tkinter.Canvas(cframe, height=50)
952 self._sentence_canvas['background'] = '#e0e0e0'
953 self._sentence_canvas.pack(fill='both')
954
955 else:
956 self._sentence_canvas = None
957
958
959 if draw_tree:
960 (sb, canvas) = self._sb_canvas(self._root, 'n', 'x')
961 (self._tree_sb, self._tree_canvas) = (sb, canvas)
962 self._tree_canvas['height'] = 200
963 else:
964 self._tree_canvas = None
965
966
967 self._analyze()
968 self.draw()
969 self._resize()
970 self._grow()
971
972
973
974 self._chart_canvas.bind('<Configure>', self._configure)
975
977 self._boldfont = tkFont.Font(family='helvetica', weight='bold',
978 size=self._fontsize)
979 self._font = tkFont.Font(family='helvetica',
980 size=self._fontsize)
981
982 self._sysfont = tkFont.Font(font=Tkinter.Button()["font"])
983 root.option_add("*Font", self._sysfont)
984
985 - def _sb_canvas(self, root, expand='y',
986 fill='both', side='bottom'):
987 """
988 Helper for __init__: construct a canvas with a scrollbar.
989 """
990 cframe =Tkinter.Frame(root, relief='sunk', border=2)
991 cframe.pack(fill=fill, expand=expand, side=side)
992 canvas = Tkinter.Canvas(cframe, background='#e0e0e0')
993
994
995 sb = Tkinter.Scrollbar(cframe, orient='vertical')
996 sb.pack(side='right', fill='y')
997 canvas.pack(side='left', fill=fill, expand='yes')
998
999
1000 sb['command']= canvas.yview
1001 canvas['yscrollcommand'] = sb.set
1002
1003 return (sb, canvas)
1004
1007
1010
1011 - def page_up(self, *e):
1012 self._chart_canvas.yview('scroll', -1, 'pages')
1013
1014 - def page_down(self, *e):
1015 self._chart_canvas.yview('scroll', 1, 'pages')
1016
1018 """
1019 Grow the window, if necessary
1020 """
1021
1022 N = self._chart.num_leaves()
1023 width = max(int(self._chart_canvas['width']),
1024 N * self._unitsize + ChartView._MARGIN * 2 )
1025
1026
1027
1028 self._chart_canvas.configure(width=width)
1029 self._chart_canvas.configure(height=self._chart_canvas['height'])
1030
1031 self._unitsize = (width - 2*ChartView._MARGIN) / N
1032
1033
1034 if self._sentence_canvas is not None:
1035 self._sentence_canvas['height'] = self._sentence_height
1036
1044
1046 return abs(self._fontsize)
1047
1058
1059 - def update(self, chart=None):
1060 """
1061 Draw any edges that have not been drawn. This is typically
1062 called when a after modifies the canvas that a CanvasView is
1063 displaying. C{update} will cause any edges that have been
1064 added to the chart to be drawn.
1065
1066 If update is given a C{chart} argument, then it will replace
1067 the current chart with the given chart.
1068 """
1069 if chart is not None:
1070 self._chart = chart
1071 self._edgelevels = []
1072 self._marks = {}
1073 self._analyze()
1074 self._grow()
1075 self.draw()
1076 self.erase_tree()
1077 self._resize()
1078 else:
1079 for edge in self._chart:
1080 if not self._edgetags.has_key(edge):
1081 self._add_edge(edge)
1082 self._resize()
1083
1084
1086 """
1087 Return 1 if the given edge overlaps with any edge on the given
1088 level. This is used by _add_edge to figure out what level a
1089 new edge should be added to.
1090 """
1091 (s1, e1) = edge.span()
1092 for otheredge in self._edgelevels[lvl]:
1093 (s2, e2) = otheredge.span()
1094 if (s1 <= s2 < e1) or (s2 <= s1 < e2) or (s1==s2==e1==e2):
1095 return 1
1096 return 0
1097
1099 """
1100 Given a new edge, recalculate:
1101
1102 - _text_height
1103 - _unitsize (if the edge text is too big for the current
1104 _unitsize, then increase _unitsize)
1105 """
1106 c = self._chart_canvas
1107
1108 if isinstance(edge, TreeEdge):
1109 lhs = edge.lhs()
1110 rhselts = []
1111 for elt in edge.rhs():
1112 if isinstance(elt, cfg.Nonterminal):
1113 rhselts.append(str(elt.symbol()))
1114 else:
1115 rhselts.append(repr(elt))
1116 rhs = string.join(rhselts)
1117 else:
1118 lhs = edge.lhs()
1119 rhs = ''
1120
1121 for s in (lhs, rhs):
1122 tag = c.create_text(0,0, text=s,
1123 font=self._boldfont,
1124 anchor='nw', justify='left')
1125 bbox = c.bbox(tag)
1126 c.delete(tag)
1127 width = bbox[2]
1128 edgelen = max(edge.length(), 1)
1129 self._unitsize = max(self._unitsize, width/edgelen)
1130 self._text_height = max(self._text_height, bbox[3] - bbox[1])
1131
1133 """
1134 Add a single edge to the ChartView:
1135
1136 - Call analyze_edge to recalculate display parameters
1137 - Find an available level
1138 - Call _draw_edge
1139 """
1140 if self._edgetags.has_key(edge): return
1141 self._analyze_edge(edge)
1142 self._grow()
1143
1144 if not self._compact:
1145 self._edgelevels.append([edge])
1146 lvl = len(self._edgelevels)-1
1147 self._draw_edge(edge, lvl)
1148 self._resize()
1149 return
1150
1151
1152 lvl = 0
1153 while 1:
1154
1155 while lvl >= len(self._edgelevels):
1156 self._edgelevels.append([])
1157 self._resize()
1158
1159
1160 if lvl>=minlvl and not self._edge_conflict(edge, lvl):
1161
1162 self._edgelevels[lvl].append(edge)
1163 break
1164
1165
1166 lvl += 1
1167
1168 self._draw_edge(edge, lvl)
1169
1171 level = None
1172 for i in range(len(self._edgelevels)):
1173 if edge in self._edgelevels[i]:
1174 level = i
1175 break
1176 if level == None: return
1177
1178 y = (level+1) * self._chart_level_size
1179 dy = self._text_height + 10
1180 self._chart_canvas.yview('moveto', 1.0)
1181 if self._chart_height != 0:
1182 self._chart_canvas.yview('moveto',
1183 float(y-dy)/self._chart_height)
1184
1186 """
1187 Draw a single edge on the ChartView.
1188 """
1189 c = self._chart_canvas
1190
1191
1192 x1 = (edge.start() * self._unitsize + ChartView._MARGIN)
1193 x2 = (edge.end() * self._unitsize + ChartView._MARGIN)
1194 if x2 == x1: x2 += max(4, self._unitsize/5)
1195 y = (lvl+1) * self._chart_level_size
1196 linetag = c.create_line(x1, y, x2, y, arrow='last', width=3)
1197
1198
1199 if isinstance(edge, TreeEdge):
1200 rhs = []
1201 for elt in edge.rhs():
1202 if isinstance(elt, cfg.Nonterminal):
1203 rhs.append(str(elt.symbol()))
1204 else:
1205 rhs.append(repr(elt))
1206 pos = edge.dot()
1207 else:
1208 rhs = []
1209 pos = 0
1210
1211 rhs1 = string.join(rhs[:pos])
1212 rhs2 = string.join(rhs[pos:])
1213 rhstag1 = c.create_text(x1+3, y, text=rhs1,
1214 font=self._font,
1215 anchor='nw')
1216 dotx = c.bbox(rhstag1)[2] + 6
1217 doty = (c.bbox(rhstag1)[1]+c.bbox(rhstag1)[3])/2
1218 dottag = c.create_oval(dotx-2, doty-2, dotx+2, doty+2)
1219 rhstag2 = c.create_text(dotx+6, y, text=rhs2,
1220 font=self._font,
1221 anchor='nw')
1222 lhstag = c.create_text((x1+x2)/2, y, text=str(edge.lhs()),
1223 anchor='s',
1224 font=self._boldfont)
1225
1226
1227 self._edgetags[edge] = (linetag, rhstag1,
1228 dottag, rhstag2, lhstag)
1229
1230
1231 def cb(event, self=self, edge=edge):
1232 self._fire_callbacks('select', edge)
1233 c.tag_bind(rhstag1, '<Button-1>', cb)
1234 c.tag_bind(rhstag2, '<Button-1>', cb)
1235 c.tag_bind(linetag, '<Button-1>', cb)
1236 c.tag_bind(dottag, '<Button-1>', cb)
1237 c.tag_bind(lhstag, '<Button-1>', cb)
1238
1239 self._color_edge(edge)
1240
1241 - def _color_edge(self, edge, linecolor=None, textcolor=None):
1242 """
1243 Color in an edge with the given colors.
1244 If no colors are specified, use intelligent defaults
1245 (dependant on selection, etc.)
1246 """
1247 if not self._edgetags.has_key(edge): return
1248 c = self._chart_canvas
1249
1250 if linecolor is not None and textcolor is not None:
1251 if self._marks.has_key(edge):
1252 linecolor = self._marks[edge]
1253 tags = self._edgetags[edge]
1254 c.itemconfig(tags[0], fill=linecolor)
1255 c.itemconfig(tags[1], fill=textcolor)
1256 c.itemconfig(tags[2], fill=textcolor,
1257 outline=textcolor)
1258 c.itemconfig(tags[3], fill=textcolor)
1259 c.itemconfig(tags[4], fill=textcolor)
1260 return
1261 else:
1262 N = self._chart.num_leaves()
1263 if self._marks.has_key(edge):
1264 self._color_edge(self._marks[edge])
1265 if (edge.is_complete() and edge.span() == (0, N)):
1266 self._color_edge(edge, '#084', '#042')
1267 elif isinstance(edge, LeafEdge):
1268 self._color_edge(edge, '#48c', '#246')
1269 else:
1270 self._color_edge(edge, '#00f', '#008')
1271
1273 """
1274 Mark an edge
1275 """
1276 self._marks[edge] = mark
1277 self._color_edge(edge)
1278
1280 """
1281 Unmark an edge (or all edges)
1282 """
1283 if edge == None:
1284 old_marked_edges = self._marks.keys()
1285 self._marks = {}
1286 for edge in old_marked_edges:
1287 self._color_edge(edge)
1288 else:
1289 del self._marks[edge]
1290 self._color_edge(edge)
1291
1295
1297 """
1298 Analyze the sentence string, to figure out how big a unit needs
1299 to be, How big the tree should be, etc.
1300 """
1301
1302 unitsize = 70
1303 text_height = 0
1304 c = self._chart_canvas
1305
1306
1307 for leaf in self._chart.leaves():
1308 tag = c.create_text(0,0, text=repr(leaf),
1309 font=self._font,
1310 anchor='nw', justify='left')
1311 bbox = c.bbox(tag)
1312 c.delete(tag)
1313 width = bbox[2] + ChartView._LEAF_SPACING
1314 unitsize = max(width, unitsize)
1315 text_height = max(text_height, bbox[3] - bbox[1])
1316
1317 self._unitsize = unitsize
1318 self._text_height = text_height
1319 self._sentence_height = (self._text_height +
1320 2*ChartView._MARGIN)
1321
1322
1323 for edge in self._chart.edges():
1324 self._analyze_edge(edge)
1325
1326
1327 self._chart_level_size = self._text_height * 2.5
1328
1329
1330 self._tree_height = (3 * (ChartView._TREE_LEVEL_SIZE +
1331 self._text_height))
1332
1333
1334 self._resize()
1335
1337 """
1338 Update the scroll-regions for each canvas. This ensures that
1339 everything is within a scroll-region, so the user can use the
1340 scrollbars to view the entire display. This does I{not}
1341 resize the window.
1342 """
1343 c = self._chart_canvas
1344
1345
1346 width = ( self._chart.num_leaves() * self._unitsize +
1347 ChartView._MARGIN * 2 )
1348
1349 levels = len(self._edgelevels)
1350 self._chart_height = (levels+2)*self._chart_level_size
1351 c['scrollregion']=(0,0,width,self._chart_height)
1352
1353
1354 if self._tree_canvas:
1355 self._tree_canvas['scrollregion'] = (0, 0, width,
1356 self._tree_height)
1357
1359 """
1360 Draw location lines. These are vertical gridlines used to
1361 show where each location unit is.
1362 """
1363 BOTTOM = 50000
1364 c1 = self._tree_canvas
1365 c2 = self._sentence_canvas
1366 c3 = self._chart_canvas
1367 margin = ChartView._MARGIN
1368 self._loclines = []
1369 for i in range(0, self._chart.num_leaves()+1):
1370 x = i*self._unitsize + margin
1371
1372 if c1:
1373 t1=c1.create_line(x, 0, x, BOTTOM)
1374 c1.tag_lower(t1)
1375 if c2:
1376 t2=c2.create_line(x, 0, x, self._sentence_height)
1377 c2.tag_lower(t2)
1378 t3=c3.create_line(x, 0, x, BOTTOM)
1379 c3.tag_lower(t3)
1380 t4=c3.create_text(x+2, 0, text=`i`, anchor='nw',
1381 font=self._font)
1382 c3.tag_lower(t4)
1383
1384
1385
1386
1387 if i % 2 == 0:
1388 if c1: c1.itemconfig(t1, fill='gray60')
1389 if c2: c2.itemconfig(t2, fill='gray60')
1390 c3.itemconfig(t3, fill='gray60')
1391 else:
1392 if c1: c1.itemconfig(t1, fill='gray80')
1393 if c2: c2.itemconfig(t2, fill='gray80')
1394 c3.itemconfig(t3, fill='gray80')
1395
1397 """Draw the sentence string."""
1398 if self._chart.num_leaves() == 0: return
1399 c = self._sentence_canvas
1400 margin = ChartView._MARGIN
1401 y = ChartView._MARGIN
1402
1403 for i, leaf in enumerate(self._chart.leaves()):
1404 x1 = i * self._unitsize + margin
1405 x2 = x1 + self._unitsize
1406 x = (x1+x2)/2
1407 tag = c.create_text(x, y, text=repr(leaf),
1408 font=self._font,
1409 anchor='n', justify='left')
1410 bbox = c.bbox(tag)
1411 rt=c.create_rectangle(x1+2, bbox[1]-(ChartView._LEAF_SPACING/2),
1412 x2-2, bbox[3]+(ChartView._LEAF_SPACING/2),
1413 fill='#f0f0f0', outline='#f0f0f0')
1414 c.tag_lower(rt)
1415
1417 for tag in self._tree_tags: self._tree_canvas.delete(tag)
1418 self._treetoks = []
1419 self._treetoks_edge = None
1420 self._treetoks_index = 0
1421
1423 if edge is None and self._treetoks_edge is None: return
1424 if edge is None: edge = self._treetoks_edge
1425
1426
1427 if self._treetoks_edge != edge:
1428 self._treetoks = [t for t in self._chart.trees(edge)
1429 if isinstance(t, Tree)]
1430 self._treetoks_edge = edge
1431 self._treetoks_index = 0
1432
1433
1434 if len(self._treetoks) == 0: return
1435
1436
1437 for tag in self._tree_tags: self._tree_canvas.delete(tag)
1438
1439
1440 tree = self._treetoks[self._treetoks_index]
1441 self._draw_treetok(tree, edge.start())
1442
1443
1444 self._draw_treecycle()
1445
1446
1447 w = self._chart.num_leaves()*self._unitsize+2*ChartView._MARGIN
1448 h = tree.height() * (ChartView._TREE_LEVEL_SIZE+self._text_height)
1449 self._tree_canvas['scrollregion'] = (0, 0, w, h)
1450
1452 self._treetoks_index = (self._treetoks_index+1)%len(self._treetoks)
1453 self.draw_tree(self._treetoks_edge)
1454
1456 if len(self._treetoks) <= 1: return
1457
1458
1459 label = '%d Trees' % len(self._treetoks)
1460 c = self._tree_canvas
1461 margin = ChartView._MARGIN
1462 right = self._chart.num_leaves()*self._unitsize+margin-2
1463 tag = c.create_text(right, 2, anchor='ne', text=label,
1464 font=self._boldfont)
1465 self._tree_tags.append(tag)
1466 _, _, _, y = c.bbox(tag)
1467
1468
1469 for i in range(len(self._treetoks)):
1470 x = right - 20*(len(self._treetoks)-i-1)
1471 if i == self._treetoks_index: fill = '#084'
1472 else: fill = '#fff'
1473 tag = c.create_polygon(x, y+10, x-5, y, x-10, y+10,
1474 fill=fill, outline='black')
1475 self._tree_tags.append(tag)
1476
1477
1478
1479 def cb(event, self=self, i=i):
1480 self._treetoks_index = i
1481 self.draw_tree()
1482 c.tag_bind(tag, '<Button-1>', cb)
1483
1485 """
1486 @param index: The index of the first leaf in the tree.
1487 @return: The index of the first leaf after the tree.
1488 """
1489 c = self._tree_canvas
1490 margin = ChartView._MARGIN
1491
1492
1493 child_xs = []
1494 for child in treetok:
1495 if isinstance(child, Tree):
1496 child_x, index = self._draw_treetok(child, index, depth+1)
1497 child_xs.append(child_x)
1498 else:
1499 child_xs.append((2*index+1)*self._unitsize/2 + margin)
1500 index += 1
1501
1502
1503
1504 if child_xs:
1505 nodex = sum(child_xs)/len(child_xs)
1506 else:
1507
1508 nodex = (2*index+1)*self._unitsize/2 + margin
1509 index += 1
1510
1511
1512 nodey = depth * (ChartView._TREE_LEVEL_SIZE + self._text_height)
1513 tag = c.create_text(nodex, nodey, anchor='n', justify='center',
1514 text=str(treetok.node), fill='#042',
1515 font=self._boldfont)
1516 self._tree_tags.append(tag)
1517
1518
1519 childy = nodey + ChartView._TREE_LEVEL_SIZE + self._text_height
1520 for childx, child in zip(child_xs, treetok):
1521 if isinstance(child, Tree) and child:
1522
1523 tag = c.create_line(nodex, nodey + self._text_height,
1524 childx, childy, width=2, fill='#084')
1525 self._tree_tags.append(tag)
1526 if isinstance(child, Tree) and not child:
1527
1528 tag = c.create_line(nodex, nodey + self._text_height,
1529 childx, childy, width=2,
1530 fill='#048', dash='2 3')
1531 self._tree_tags.append(tag)
1532 if not isinstance(child, Tree):
1533
1534 tag = c.create_line(nodex, nodey + self._text_height,
1535 childx, 10000, width=2, fill='#084')
1536 self._tree_tags.append(tag)
1537
1538 return nodex, index
1539
1541 """
1542 Draw everything (from scratch).
1543 """
1544 if self._tree_canvas:
1545 self._tree_canvas.delete('all')
1546 self.draw_tree()
1547
1548 if self._sentence_canvas:
1549 self._sentence_canvas.delete('all')
1550 self._draw_sentence()
1551
1552 self._chart_canvas.delete('all')
1553 self._edgetags = {}
1554
1555
1556 for lvl in range(len(self._edgelevels)):
1557 for edge in self._edgelevels[lvl]:
1558 self._draw_edge(edge, lvl)
1559
1560 for edge in self._chart:
1561 self._add_edge(edge)
1562
1563 self._draw_loclines()
1564
1566 self._callbacks.setdefault(event,{})[func] = 1
1567
1569 if func is None: del self._callbacks[event]
1570 else:
1571 try: del self._callbacks[event][func]
1572 except: pass
1573
1575 if not self._callbacks.has_key(event): return
1576 for cb_func in self._callbacks[event].keys(): cb_func(*args)
1577
1578
1579
1580
1581
1582
1583
1584
1611
1614 return 'Predictor Rule (aka Top Down Expand Rule)'
1615
1616
1617
1618
1619
1620
1621
1623 """
1624 To create an edge rule, make an empty base class that uses
1625 EdgeRule as the first base class, and the basic rule as the
1626 second base class. (Order matters!)
1627 """
1629 super = self.__class__.__bases__[1]
1630 self._edge = edge
1631 self.NUM_EDGES = super.NUM_EDGES-1
1637 super = self.__class__.__bases__[1]
1638 return super.__str__(self)
1639
1646
1647
1648
1649
1650
1652 - def __init__(self, grammar, tokens, title='Chart Parsing Demo'):
1653
1654 self._init_parser(grammar, tokens)
1655
1656 self._root = None
1657 try:
1658
1659 self._root = Tkinter.Tk()
1660 self._root.title(title)
1661 self._root.bind('<Control-q>', self.destroy)
1662
1663
1664 frame3 = Tkinter.Frame(self._root)
1665 frame2 = Tkinter.Frame(self._root)
1666 frame1 = Tkinter.Frame(self._root)
1667 frame3.pack(side='bottom', fill='none')
1668 frame2.pack(side='bottom', fill='x')
1669 frame1.pack(side='bottom', fill='both', expand=1)
1670
1671 self._init_fonts(self._root)
1672 self._init_animation()
1673 self._init_chartview(frame1)
1674 self._init_rulelabel(frame2)
1675 self._init_buttons(frame3)
1676 self._init_menubar()
1677
1678 self._matrix = None
1679 self._results = None
1680
1681
1682 self._init_bindings()
1683
1684 except:
1685 print 'Error creating Tree View'
1686 self.destroy()
1687 raise
1688
1690 if self._root is None: return
1691 self._root.destroy()
1692 self._root = None
1693
1694 - def mainloop(self, *args, **kwargs):
1695 """
1696 Enter the Tkinter mainloop. This function must be called if
1697 this demo is created from a non-interactive program (e.g.
1698 from a secript); otherwise, the demo will close as soon as
1699 the script completes.
1700 """
1701 if in_idle(): return
1702 self._root.mainloop(*args, **kwargs)
1703
1704
1705
1706
1707
1709 self._grammar = grammar
1710 self._tokens = tokens
1711 self._cp = SteppingChartParse(self._grammar)
1712 self._cp.initialize(self._tokens)
1713 self._chart = self._cp.chart()
1714
1715
1716 self._cpstep = self._cp.step()
1717
1718
1719 self._selection = None
1720
1722
1723 self._sysfont = tkFont.Font(font=Tkinter.Button()["font"])
1724 root.option_add("*Font", self._sysfont)
1725
1726
1727 self._size = Tkinter.IntVar(root)
1728 self._size.set(self._sysfont.cget('size'))
1729
1730 self._boldfont = tkFont.Font(family='helvetica', weight='bold',
1731 size=self._size.get())
1732 self._font = tkFont.Font(family='helvetica',
1733 size=self._size.get())
1734
1736
1737 self._step = Tkinter.IntVar(self._root)
1738 self._step.set(1)
1739
1740
1741 self._animate = Tkinter.IntVar(self._root)
1742 self._animate.set(3)
1743
1744
1745 self._animating = 0
1746
1751
1753 ruletxt = 'Last edge generated by:'
1754
1755 self._rulelabel1 = Tkinter.Label(parent,text=ruletxt,
1756 font=self._boldfont)
1757 self._rulelabel2 = Tkinter.Label(parent, width=40,
1758 relief='groove', anchor='w',
1759 font=self._boldfont)
1760 self._rulelabel1.pack(side='left')
1761 self._rulelabel2.pack(side='left')
1762 step = Tkinter.Checkbutton(parent, variable=self._step,
1763 text='Step')
1764 step.pack(side='right')
1765
1811
1813 self._root.bind('<Up>', self._cv.scroll_up)
1814 self._root.bind('<Down>', self._cv.scroll_down)
1815 self._root.bind('<Prior>', self._cv.page_up)
1816 self._root.bind('<Next>', self._cv.page_down)
1817 self._root.bind('<Control-q>', self.destroy)
1818 self._root.bind('<Control-x>', self.destroy)
1819 self._root.bind('<F1>', self.help)
1820
1821 self._root.bind('<Control-s>', self.save_chart)
1822 self._root.bind('<Control-o>', self.load_chart)
1823 self._root.bind('<Control-r>', self.reset)
1824
1825 self._root.bind('t', self.top_down_strategy)
1826 self._root.bind('b', self.bottom_up_strategy)
1827 self._root.bind('e', self.earley_algorithm)
1828 self._root.bind('<space>', self._stop_animation)
1829
1830 self._root.bind('<Control-g>', self.edit_grammar)
1831 self._root.bind('<Control-t>', self.edit_sentence)
1832
1833
1834 self._root.bind('-', lambda e,a=self._animate:a.set(1))
1835 self._root.bind('=', lambda e,a=self._animate:a.set(2))
1836 self._root.bind('+', lambda e,a=self._animate:a.set(3))
1837
1838
1839 self._root.bind('s', lambda e,s=self._step:s.set(not s.get()))
1840
1842 menubar = Tkinter.Menu(self._root)
1843
1844 filemenu = Tkinter.Menu(menubar, tearoff=0)
1845 filemenu.add_command(label='Save Chart', underline=0,
1846 command=self.save_chart, accelerator='Ctrl-s')
1847 filemenu.add_command(label='Load Chart', underline=0,
1848 command=self.load_chart, accelerator='Ctrl-o')
1849 filemenu.add_command(label='Reset Chart', underline=0,
1850 command=self.reset, accelerator='Ctrl-r')
1851 filemenu.add_separator()
1852 filemenu.add_command(label='Save Grammar',
1853 command=self.save_grammar)
1854 filemenu.add_command(label='Load Grammar',
1855 command=self.load_grammar)
1856 filemenu.add_separator()
1857 filemenu.add_command(label='Exit', underline=1,
1858 command=self.destroy, accelerator='Ctrl-x')
1859 menubar.add_cascade(label='File', underline=0, menu=filemenu)
1860
1861 editmenu = Tkinter.Menu(menubar, tearoff=0)
1862 editmenu.add_command(label='Edit Grammar', underline=5,
1863 command=self.edit_grammar,
1864 accelerator='Ctrl-g')
1865 editmenu.add_command(label='Edit Text', underline=5,
1866 command=self.edit_sentence,
1867 accelerator='Ctrl-t')
1868 menubar.add_cascade(label='Edit', underline=0, menu=editmenu)
1869
1870 viewmenu = Tkinter.Menu(menubar, tearoff=0)
1871 viewmenu.add_command(label='Chart Matrix', underline=6,
1872 command=self.view_matrix)
1873 viewmenu.add_command(label='Results', underline=0,
1874 command=self.view_results)
1875 menubar.add_cascade(label='View', underline=0, menu=viewmenu)
1876
1877 rulemenu = Tkinter.Menu(menubar, tearoff=0)
1878 rulemenu.add_command(label='Top Down Strategy', underline=0,
1879 command=self.top_down_strategy,
1880 accelerator='t')
1881 rulemenu.add_command(label='Bottom Up Strategy', underline=0,
1882 command=self.bottom_up_strategy,
1883 accelerator='b')
1884 rulemenu.add_command(label='Earley Algorithm', underline=0,
1885 command=self.bottom_up_strategy,
1886 accelerator='e')
1887 rulemenu.add_separator()
1888 rulemenu.add_command(label='Bottom Up Init Rule',
1889 command=self.bottom_up_init)
1890 rulemenu.add_command(label='Bottom Up Rule',
1891 command=self.bottom_up)
1892 rulemenu.add_command(label='Top Down Init Rule',
1893 command=self.top_down_init)
1894 rulemenu.add_command(label='Top Down Expand Rule',
1895 command=self.top_down_expand)
1896 rulemenu.add_command(label='Top Down Match Rule',
1897 command=self.top_down_match)
1898 rulemenu.add_command(label='Fundamental Rule',
1899 command=self.fundamental)
1900 menubar.add_cascade(label='Apply', underline=0, menu=rulemenu)
1901
1902 animatemenu = Tkinter.Menu(menubar, tearoff=0)
1903 animatemenu.add_checkbutton(label="Step", underline=0,
1904 variable=self._step,
1905 accelerator='s')
1906 animatemenu.add_separator()
1907 animatemenu.add_radiobutton(label="No Animation", underline=0,
1908 variable=self._animate, value=0)
1909 animatemenu.add_radiobutton(label="Slow Animation", underline=0,
1910 variable=self._animate, value=1,
1911 accelerator='-')
1912 animatemenu.add_radiobutton(label="Normal Animation", underline=0,
1913 variable=self._animate, value=2,
1914 accelerator='=')
1915 animatemenu.add_radiobutton(label="Fast Animation", underline=0,
1916 variable=self._animate, value=3,
1917 accelerator='+')
1918 menubar.add_cascade(label="Animate", underline=1, menu=animatemenu)
1919
1920 zoommenu = Tkinter.Menu(menubar, tearoff=0)
1921 zoommenu.add_radiobutton(label='Tiny', variable=self._size,
1922 underline=0, value=10, command=self.resize)
1923 zoommenu.add_radiobutton(label='Small', variable=self._size,
1924 underline=0, value=12, command=self.resize)
1925 zoommenu.add_radiobutton(label='Medium', variable=self._size,
1926 underline=0, value=14, command=self.resize)
1927 zoommenu.add_radiobutton(label='Large', variable=self._size,
1928 underline=0, value=18, command=self.resize)
1929 zoommenu.add_radiobutton(label='Huge', variable=self._size,
1930 underline=0, value=24, command=self.resize)
1931 menubar.add_cascade(label='Zoom', underline=0, menu=zoommenu)
1932
1933 helpmenu = Tkinter.Menu(menubar, tearoff=0)
1934 helpmenu.add_command(label='About', underline=0,
1935 command=self.about)
1936 helpmenu.add_command(label='Instructions', underline=0,
1937 command=self.help, accelerator='F1')
1938 menubar.add_cascade(label='Help', underline=0, menu=helpmenu)
1939
1940 self._root.config(menu=menubar)
1941
1942
1943
1944
1945
1953
1954
1955
1959
1968
1976
1990
1991
1992
1993
1994
1995 - def help(self, *e):
1996 self._animating = 0
1997
1998 try:
1999 ShowText(self._root, 'Help: Chart Parser Demo',
2000 (__doc__).strip(), width=75, font='fixed')
2001 except:
2002 ShowText(self._root, 'Help: Chart Parser Demo',
2003 (__doc__).strip(), width=75)
2004
2006 ABOUT = ("NLTK Chart Parser Demo\n"+
2007 "Written by Edward Loper")
2008 tkMessageBox.showinfo('About: Chart Parser Demo', ABOUT)
2009
2010
2011
2012
2013
2014 CHART_FILE_TYPES = [('Pickle file', '.pickle'),
2015 ('All files', '*')]
2016 GRAMMAR_FILE_TYPES = [('Plaintext grammar file', '.cfg'),
2017 ('Pickle file', '.pickle'),
2018 ('All files', '*')]
2019
2021 "Load a chart from a pickle file"
2022 filename = askopenfilename(filetypes=self.CHART_FILE_TYPES,
2023 defaultextension='.pickle')
2024 if not filename: return
2025 try:
2026 chart = pickle.load(open(filename, 'r'))
2027 self._chart = chart
2028 self._cv.update(chart)
2029 if self._matrix: self._matrix.set_chart(chart)
2030 if self._matrix: self._matrix.deselect_cell()
2031 if self._results: self._results.set_chart(chart)
2032 self._cp.set_chart(chart)
2033 except Exception, e:
2034 raise
2035 tkMessageBox.showerror('Error Loading Chart',
2036 'Unable to open file: %r' % filename)
2037
2039 "Save a chart to a pickle file"
2040 filename = asksaveasfilename(filetypes=self.CHART_FILE_TYPES,
2041 defaultextension='.pickle')
2042 if not filename: return
2043 try:
2044 pickle.dump(self._chart, open(filename, 'w'))
2045 except Exception, e:
2046 raise
2047 tkMessageBox.showerror('Error Saving Chart',
2048 'Unable to open file: %r' % filename)
2049
2051 "Load a grammar from a pickle file"
2052 filename = askopenfilename(filetypes=self.GRAMMAR_FILE_TYPES,
2053 defaultextension='.cfg')
2054 if not filename: return
2055 try:
2056 if filename.endswith('.pickle'):
2057 grammar = pickle.load(open(filename, 'r'))
2058 else:
2059 grammar = cfg.parse_cfg(open(filename, 'r').read())
2060 self.set_grammar(grammar)
2061 except Exception, e:
2062 tkMessageBox.showerror('Error Loading Grammar',
2063 'Unable to open file: %r' % filename)
2064
2066 filename = asksaveasfilename(filetypes=self.GRAMMAR_FILE_TYPES,
2067 defaultextension='.cfg')
2068 if not filename: return
2069 try:
2070 if filename.endswith('.pickle'):
2071 pickle.dump((self._chart, self._tokens), open(filename, 'w'))
2072 else:
2073 file = open(filename, 'w')
2074 prods = self._grammar.productions()
2075 start = [p for p in prods if p.lhs() == self._grammar.start()]
2076 rest = [p for p in prods if p.lhs() != self._grammar.start()]
2077 for prod in start: file.write('%s\n' % prod)
2078 for prod in rest: file.write('%s\n' % prod)
2079 file.close()
2080 except Exception, e:
2081 tkMessageBox.showerror('Error Saving Grammar',
2082 'Unable to open file: %r' % filename)
2083
2084 - def reset(self, *args):
2085 self._animating = 0
2086 self._cp = SteppingChartParse(self._grammar)
2087 self._cp.initialize(self._tokens)
2088 self._chart = self._cp.chart()
2089 self._cv.update(self._chart)
2090 if self._matrix: self._matrix.set_chart(self._chart)
2091 if self._matrix: self._matrix.deselect_cell()
2092 if self._results: self._results.set_chart(self._chart)
2093 self._cpstep = self._cp.step()
2094
2095
2096
2097
2098
2101
2106
2108 sentence = string.join(self._tokens)
2109 title = 'Edit Text'
2110 instr = 'Enter a new sentence to parse.'
2111 EntryDialog(self._root, sentence, instr, self.set_sentence, title)
2112
2116
2117
2118
2119
2120
2125
2127 if self._results is not None: self._results.destroy()
2128 self._results = ChartResultsView(self._root, self._chart,
2129 self._grammar)
2130
2131
2132
2133
2134
2138
2144
2146 return abs(self._size.get())
2147
2148
2149
2150
2151
2188
2191
2203
2205 new_edge = self._cpstep.next()
2206
2207 if new_edge is not None:
2208 self._show_new_edge(new_edge)
2209 return new_edge
2210
2212 if rule == None:
2213 self._rulelabel2['text'] = ''
2214 else:
2215 name = str(rule)
2216 self._rulelabel2['text'] = name
2217 size = self._cv.get_font_size()
2218
2219
2220
2221
2222
2223
2224 _TD_INIT = [TopDownInitRule()]
2225 _TD_EXPAND = [TopDownExpandRule()]
2226 _TD_MATCH = [TopDownMatchRule()]
2227 _BU_INIT = [BottomUpInitRule()]
2228 _BU_RULE = [BottomUpPredictRule()]
2229 _FUNDAMENTAL = [SingleEdgeFundamentalRule()]
2230 _EARLEY = [PseudoEarleyRule()]
2231 _EARLEY_INIT = [PseudoEarleyInitRule()]
2232
2233
2234 _TD_STRATEGY = _TD_INIT + _TD_EXPAND + _TD_MATCH + _FUNDAMENTAL
2235 _BU_STRATEGY = _BU_INIT + _BU_RULE + _FUNDAMENTAL
2236 _EARLEY = _EARLEY_INIT + _EARLEY
2237
2238
2257
2259 grammar = cfg.parse_cfg("""
2260 # Grammatical productions.
2261 S -> NP VP
2262 VP -> VP PP | V NP | V
2263 NP -> Det N | NP PP
2264 PP -> P NP
2265 # Lexical productions.
2266 NP -> 'John' | 'I'
2267 Det -> 'the' | 'my' | 'a'
2268 N -> 'dog' | 'cookie' | 'table' | 'cake' | 'fork'
2269 V -> 'ate' | 'saw'
2270 P -> 'on' | 'under' | 'with'
2271 """)
2272
2273 sent = 'John ate the cake on the table with a fork'
2274 sent = 'John ate the cake on the table'
2275 tokens = list(tokenize.whitespace(sent))
2276
2277 print 'grammar= ('
2278 for rule in grammar.productions():
2279 print ' ', repr(rule)+','
2280 print ')'
2281 print 'tokens = %r' % tokens
2282 print 'Calling "ChartDemo(grammar, tokens)"...'
2283 ChartDemo(grammar, tokens).mainloop()
2284
2285 if __name__ == '__main__':
2286 demo()
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300