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