1
2
3
4
5
6
7
8
9
10 """
11 A graphical tool for exploring the shift/reduce parser.
12
13 The shift/reduce parser maintains a stack, which records the structure
14 of the portion of the text that has been parsed. The stack is
15 initially empty. Its contents are shown on the left side of the main
16 canvas.
17
18 On the right side of the main canvas is the remaining text. This is
19 the portion of the text which has not yet been considered by the
20 parser.
21
22 The parser builds up a tree structure for the text using two
23 operations:
24
25 - "shift" moves the first token from the remaining text to the top
26 of the stack. In the demo, the top of the stack is its right-hand
27 side.
28 - "reduce" uses a grammar production to combine the rightmost stack
29 elements into a single tree token.
30
31 You can control the parser's operation by using the "shift" and
32 "reduce" buttons; or you can use the "step" button to let the parser
33 automatically decide which operation to apply. The parser uses the
34 following rules to decide which operation to apply:
35
36 - Only shift if no reductions are available.
37 - If multiple reductions are available, then apply the reduction
38 whose CFG production is listed earliest in the grammar.
39
40 The "reduce" button applies the reduction whose CFG production is
41 listed earliest in the grammar. There are two ways to manually choose
42 which reduction to apply:
43
44 - Click on a CFG production from the list of available reductions,
45 on the left side of the main window. The reduction based on that
46 production will be applied to the top of the stack.
47 - Click on one of the stack elements. A popup window will appear,
48 containing all available reductions. Select one, and it will be
49 applied to the top of the stack.
50
51 Note that reductions can only be applied to the top of the stack.
52
53 Keyboard Shortcuts::
54 [Space]\t Perform the next shift or reduce operation
55 [s]\t Perform a shift operation
56 [r]\t Perform a reduction operation
57 [Ctrl-z]\t Undo most recent operation
58 [Delete]\t Reset the parser
59 [g]\t Show/hide available production list
60 [Ctrl-a]\t Toggle animations
61 [h]\t Help
62 [Ctrl-p]\t Print
63 [q]\t Quit
64 """
65
66 """
67 Possible future improvements:
68 - button/window to change and/or select text. Just pop up a window
69 with an entry, and let them modify the text; and then retokenize
70 it? Maybe give a warning if it contains tokens whose types are
71 not in the grammar.
72 - button/window to change and/or select grammar. Select from
73 several alternative grammars? Or actually change the grammar? If
74 the later, then I'd want to define nltk.draw.cfg, which would be
75 responsible for that.
76 """
77
78 from nltk_lite.draw.tree import *
79 from nltk_lite.draw import *
80 from nltk_lite import parse
81 from nltk_lite.draw.cfg import CFGEditor
82 from nltk_lite import tokenize
83 import string
84 from Tkinter import *
85 import tkFont
86
88 """
89 A graphical tool for exploring the shift/reduce parser. The tool
90 displays the parser's stack and the remaining text, and allows the
91 user to control the parser's operation. In particular, the user
92 can shift tokens onto the stack, and can perform reductions on the
93 top elements of the stack. A "step" button simply steps through
94 the parsing process, performing the operations that
95 C{parse.ShiftReduce} would use.
96 """
97 - def __init__(self, grammar, sent, trace=0):
134
135
136
137
138
140
141 self._sysfont = tkFont.Font(font=Button()["font"])
142 root.option_add("*Font", self._sysfont)
143
144
145 self._size = IntVar(root)
146 self._size.set(self._sysfont.cget('size'))
147
148 self._boldfont = tkFont.Font(family='helvetica', weight='bold',
149 size=self._size.get())
150 self._font = tkFont.Font(family='helvetica',
151 size=self._size.get())
152
154
155 self._prodframe = listframe = Frame(parent)
156 self._prodframe.pack(fill='both', side='left', padx=2)
157 self._prodlist_label = Label(self._prodframe,
158 font=self._boldfont,
159 text='Available Reductions')
160 self._prodlist_label.pack()
161 self._prodlist = Listbox(self._prodframe, selectmode='single',
162 relief='groove', background='white',
163 foreground='#909090',
164 font=self._font,
165 selectforeground='#004040',
166 selectbackground='#c0f0c0')
167
168 self._prodlist.pack(side='right', fill='both', expand=1)
169
170 self._productions = list(self._parser.grammar().productions())
171 for production in self._productions:
172 self._prodlist.insert('end', (' %s' % production))
173 self._prodlist.config(height=min(len(self._productions), 25))
174
175
176 if 1:
177 listscroll = Scrollbar(self._prodframe,
178 orient='vertical')
179 self._prodlist.config(yscrollcommand = listscroll.set)
180 listscroll.config(command=self._prodlist.yview)
181 listscroll.pack(side='left', fill='y')
182
183
184 self._prodlist.bind('<<ListboxSelect>>', self._prodlist_select)
185
186
187 self._hover = -1
188 self._prodlist.bind('<Motion>', self._highlight_hover)
189 self._prodlist.bind('<Leave>', self._clear_hover)
190
192
193 self._top.bind('<Control-q>', self.destroy)
194 self._top.bind('<Control-x>', self.destroy)
195 self._top.bind('<Alt-q>', self.destroy)
196 self._top.bind('<Alt-x>', self.destroy)
197
198
199 self._top.bind('<space>', self.step)
200 self._top.bind('<s>', self.shift)
201 self._top.bind('<Alt-s>', self.shift)
202 self._top.bind('<Control-s>', self.shift)
203 self._top.bind('<r>', self.reduce)
204 self._top.bind('<Alt-r>', self.reduce)
205 self._top.bind('<Control-r>', self.reduce)
206 self._top.bind('<Delete>', self.reset)
207 self._top.bind('<u>', self.undo)
208 self._top.bind('<Alt-u>', self.undo)
209 self._top.bind('<Control-u>', self.undo)
210 self._top.bind('<Control-z>', self.undo)
211 self._top.bind('<BackSpace>', self.undo)
212
213
214 self._top.bind('<Control-p>', self.postscript)
215 self._top.bind('<Control-h>', self.help)
216 self._top.bind('<F1>', self.help)
217 self._top.bind('<Control-g>', self.edit_grammar)
218 self._top.bind('<Control-t>', self.edit_sentence)
219
220
221 self._top.bind('-', lambda e,a=self._animate:a.set(20))
222 self._top.bind('=', lambda e,a=self._animate:a.set(10))
223 self._top.bind('+', lambda e,a=self._animate:a.set(4))
224
241
243 menubar = Menu(parent)
244
245 filemenu = Menu(menubar, tearoff=0)
246 filemenu.add_command(label='Reset Parser', underline=0,
247 command=self.reset, accelerator='Del')
248 filemenu.add_command(label='Print to Postscript', underline=0,
249 command=self.postscript, accelerator='Ctrl-p')
250 filemenu.add_command(label='Exit', underline=1,
251 command=self.destroy, accelerator='Ctrl-x')
252 menubar.add_cascade(label='File', underline=0, menu=filemenu)
253
254 editmenu = Menu(menubar, tearoff=0)
255 editmenu.add_command(label='Edit Grammar', underline=5,
256 command=self.edit_grammar,
257 accelerator='Ctrl-g')
258 editmenu.add_command(label='Edit Text', underline=5,
259 command=self.edit_sentence,
260 accelerator='Ctrl-t')
261 menubar.add_cascade(label='Edit', underline=0, menu=editmenu)
262
263 rulemenu = Menu(menubar, tearoff=0)
264 rulemenu.add_command(label='Step', underline=1,
265 command=self.step, accelerator='Space')
266 rulemenu.add_separator()
267 rulemenu.add_command(label='Shift', underline=0,
268 command=self.shift, accelerator='Ctrl-s')
269 rulemenu.add_command(label='Reduce', underline=0,
270 command=self.reduce, accelerator='Ctrl-r')
271 rulemenu.add_separator()
272 rulemenu.add_command(label='Undo', underline=0,
273 command=self.undo, accelerator='Ctrl-u')
274 menubar.add_cascade(label='Apply', underline=0, menu=rulemenu)
275
276 viewmenu = Menu(menubar, tearoff=0)
277 viewmenu.add_checkbutton(label="Show Grammar", underline=0,
278 variable=self._show_grammar,
279 command=self._toggle_grammar)
280 viewmenu.add_separator()
281 viewmenu.add_radiobutton(label='Tiny', variable=self._size,
282 underline=0, value=10, command=self.resize)
283 viewmenu.add_radiobutton(label='Small', variable=self._size,
284 underline=0, value=12, command=self.resize)
285 viewmenu.add_radiobutton(label='Medium', variable=self._size,
286 underline=0, value=14, command=self.resize)
287 viewmenu.add_radiobutton(label='Large', variable=self._size,
288 underline=0, value=18, command=self.resize)
289 viewmenu.add_radiobutton(label='Huge', variable=self._size,
290 underline=0, value=24, command=self.resize)
291 menubar.add_cascade(label='View', underline=0, menu=viewmenu)
292
293 animatemenu = Menu(menubar, tearoff=0)
294 animatemenu.add_radiobutton(label="No Animation", underline=0,
295 variable=self._animate, value=0)
296 animatemenu.add_radiobutton(label="Slow Animation", underline=0,
297 variable=self._animate, value=20,
298 accelerator='-')
299 animatemenu.add_radiobutton(label="Normal Animation", underline=0,
300 variable=self._animate, value=10,
301 accelerator='=')
302 animatemenu.add_radiobutton(label="Fast Animation", underline=0,
303 variable=self._animate, value=4,
304 accelerator='+')
305 menubar.add_cascade(label="Animate", underline=1, menu=animatemenu)
306
307
308 helpmenu = Menu(menubar, tearoff=0)
309 helpmenu.add_command(label='About', underline=0,
310 command=self.about)
311 helpmenu.add_command(label='Instructions', underline=0,
312 command=self.help, accelerator='F1')
313 menubar.add_cascade(label='Help', underline=0, menu=helpmenu)
314
315 parent.config(menu=menubar)
316
318 self._feedbackframe = feedbackframe = Frame(parent)
319 feedbackframe.pack(fill='x', side='bottom', padx=3, pady=3)
320 self._lastoper_label = Label(feedbackframe, text='Last Operation:',
321 font=self._font)
322 self._lastoper_label.pack(side='left')
323 lastoperframe = Frame(feedbackframe, relief='sunken', border=1)
324 lastoperframe.pack(fill='x', side='right', expand=1, padx=5)
325 self._lastoper1 = Label(lastoperframe, foreground='#007070',
326 background='#f0f0f0', font=self._font)
327 self._lastoper2 = Label(lastoperframe, anchor='w', width=30,
328 foreground='#004040', background='#f0f0f0',
329 font=self._font)
330 self._lastoper1.pack(side='left')
331 self._lastoper2.pack(side='left', fill='x', expand=1)
332
334 self._cframe = CanvasFrame(parent, background='white',
335 width=525, closeenough=10,
336 border=2, relief='sunken')
337 self._cframe.pack(expand=1, fill='both', side='top', pady=2)
338 canvas = self._canvas = self._cframe.canvas()
339
340 self._stackwidgets = []
341 self._rtextwidgets = []
342 self._titlebar = canvas.create_rectangle(0,0,0,0, fill='#c0f0f0',
343 outline='black')
344 self._exprline = canvas.create_line(0,0,0,0, dash='.')
345 self._stacktop = canvas.create_line(0,0,0,0, fill='#408080')
346 size = self._size.get()+4
347 self._stacklabel = TextWidget(canvas, 'Stack', color='#004040',
348 font=self._boldfont)
349 self._rtextlabel = TextWidget(canvas, 'Remaining Text',
350 color='#004040', font=self._boldfont)
351 self._cframe.add_widget(self._stacklabel)
352 self._cframe.add_widget(self._rtextlabel)
353
354
355
356
357
359 scrollregion = self._canvas['scrollregion'].split()
360 (cx1, cy1, cx2, cy2) = [int(c) for c in scrollregion]
361
362
363 for stackwidget in self._stackwidgets:
364 self._cframe.destroy_widget(stackwidget)
365 self._stackwidgets = []
366 for rtextwidget in self._rtextwidgets:
367 self._cframe.destroy_widget(rtextwidget)
368 self._rtextwidgets = []
369
370
371 (x1, y1, x2, y2) = self._stacklabel.bbox()
372 y = y2-y1+10
373 self._canvas.coords(self._titlebar, -5000, 0, 5000, y-4)
374 self._canvas.coords(self._exprline, 0, y*2-10, 5000, y*2-10)
375
376
377 (x1, y1, x2, y2) = self._stacklabel.bbox()
378 self._stacklabel.move(5-x1, 3-y1)
379 (x1, y1, x2, y2) = self._rtextlabel.bbox()
380 self._rtextlabel.move(cx2-x2-5, 3-y1)
381
382
383 stackx = 5
384 for tok in self._parser.stack():
385 if isinstance(tok, parse.Tree):
386 attribs = {'tree_color': '#4080a0', 'tree_width': 2,
387 'node_font': self._boldfont,
388 'node_color': '#006060',
389 'leaf_color': '#006060', 'leaf_font':self._font}
390 widget = tree_to_treesegment(self._canvas, tok,
391 **attribs)
392 widget.node()['color'] = '#000000'
393 else:
394 widget = TextWidget(self._canvas, tok,
395 color='#000000', font=self._font)
396 widget.bind_click(self._popup_reduce)
397 self._stackwidgets.append(widget)
398 self._cframe.add_widget(widget, stackx, y)
399 stackx = widget.bbox()[2] + 10
400
401
402 rtextwidth = 0
403 for tok in self._parser.remaining_text():
404 widget = TextWidget(self._canvas, tok,
405 color='#000000', font=self._font)
406 self._rtextwidgets.append(widget)
407 self._cframe.add_widget(widget, rtextwidth, y)
408 rtextwidth = widget.bbox()[2] + 4
409
410
411 if len(self._rtextwidgets) > 0:
412 stackx += self._rtextwidgets[0].width()
413
414
415
416
417 stackx = max(stackx, self._stacklabel.width()+25)
418 rlabelwidth = self._rtextlabel.width()+10
419 if stackx >= cx2-max(rtextwidth, rlabelwidth):
420 cx2 = stackx + max(rtextwidth, rlabelwidth)
421 for rtextwidget in self._rtextwidgets:
422 rtextwidget.move(4+cx2-rtextwidth, 0)
423 self._rtextlabel.move(cx2-self._rtextlabel.bbox()[2]-5, 0)
424
425 midx = (stackx + cx2-max(rtextwidth, rlabelwidth))/2
426 self._canvas.coords(self._stacktop, midx, 0, midx, 5000)
427 (x1, y1, x2, y2) = self._stacklabel.bbox()
428
429
430 if len(self._rtextwidgets) > 0:
431 def drag_shift(widget, midx=midx, self=self):
432 if widget.bbox()[0] < midx: self.shift()
433 else: self._redraw()
434 self._rtextwidgets[0].bind_drag(drag_shift)
435 self._rtextwidgets[0].bind_click(self.shift)
436
437
438 self._highlight_productions()
439
441
442 midx = widget.bbox()[2]+50
443 self._canvas.coords(self._stacktop, midx, 0, midx, 5000)
444
451
452
453
454
455
457 if self._top is None: return
458 self._top.destroy()
459 self._top = None
460
462 self._parser.initialize(self._sent)
463 self._lastoper1['text'] = 'Reset Demo'
464 self._lastoper2['text'] = ''
465 self._redraw()
466
467 - def step(self, *e):
468 if self.reduce(): return 1
469 elif self.shift(): return 1
470 else:
471 if len(self._parser.parses()) > 0:
472 self._lastoper1['text'] = 'Finished:'
473 self._lastoper2['text'] = 'Success'
474 else:
475 self._lastoper1['text'] = 'Finished:'
476 self._lastoper2['text'] = 'Failure'
477
479 if self._animating_lock: return
480 if self._parser.shift():
481 tok = self._parser.stack()[-1]
482 self._lastoper1['text'] = 'Shift:'
483 self._lastoper2['text'] = '%r' % tok
484 if self._animate.get():
485 self._animate_shift()
486 else:
487 self._redraw()
488 return 1
489 return 0
490
492 if self._animating_lock: return
493 production = self._parser.reduce()
494 if production:
495 self._lastoper1['text'] = 'Reduce:'
496 self._lastoper2['text'] = '%s' % production
497 if self._animate.get():
498 self._animate_reduce()
499 else:
500 self._redraw()
501 return production
502
503 - def undo(self, *e):
507
508 - def postscript(self, *e):
509 self._cframe.print_to_file()
510
511 - def mainloop(self, *args, **kwargs):
512 """
513 Enter the Tkinter mainloop. This function must be called if
514 this demo is created from a non-interactive program (e.g.
515 from a secript); otherwise, the demo will close as soon as
516 the script completes.
517 """
518 if in_idle(): return
519 self._top.mainloop(*args, **kwargs)
520
521
522
523
524
526 if size is not None: self._size.set(size)
527 size = self._size.get()
528 self._font.configure(size=-(abs(size)))
529 self._boldfont.configure(size=-(abs(size)))
530 self._sysfont.configure(size=-(abs(size)))
531
532
533
534
535
536
537
538
539 self._redraw()
540
541 - def help(self, *e):
542
543 try:
544 ShowText(self._top, 'Help: Chart Parser Demo',
545 (__doc__).strip(), width=75, font='fixed')
546 except:
547 ShowText(self._top, 'Help: Chart Parser Demo',
548 (__doc__).strip(), width=75)
549
551 ABOUT = ("NLTK Shift-Reduce Parser Demo\n"+
552 "Written by Edward Loper")
553 TITLE = 'About: Shift-Reduce Parser Demo'
554 try:
555 from tkMessageBox import Message
556 Message(message=ABOUT, title=TITLE).show()
557 except:
558 ShowText(self._top, TITLE, ABOUT)
559
562
569
571 sentence = string.join(self._sent)
572 title = 'Edit Text'
573 instr = 'Enter a new sentence to parse.'
574 EntryDialog(self._top, sentence, instr, self.set_sentence, title)
575
579
580
581
582
583
585 if self._show_grammar.get():
586 self._prodframe.pack(fill='both', side='left', padx=2,
587 after=self._feedbackframe)
588 self._lastoper1['text'] = 'Show Grammar'
589 else:
590 self._prodframe.pack_forget()
591 self._lastoper1['text'] = 'Hide Grammar'
592 self._lastoper2['text'] = ''
593
612
624
625
626
627
628
630
631 widget = self._rtextwidgets[0]
632
633
634 right = widget.bbox()[0]
635 if len(self._stackwidgets) == 0: left = 5
636 else: left = self._stackwidgets[-1].bbox()[2]+10
637
638
639 dt = self._animate.get()
640 dx = (left-right)*1.0/dt
641 self._animate_shift_frame(dt, widget, dx)
642
644 if frame > 0:
645 self._animating_lock = 1
646 widget.move(dx, 0)
647 self._top.after(10, self._animate_shift_frame,
648 frame-1, widget, dx)
649 else:
650
651
652
653 del self._rtextwidgets[0]
654 self._stackwidgets.append(widget)
655 self._animating_lock = 0
656
657
658 self._draw_stack_top(widget)
659 self._highlight_productions()
660
662
663 numwidgets = len(self._parser.stack()[-1])
664 widgets = self._stackwidgets[-numwidgets:]
665
666
667 if isinstance(widgets[0], TreeSegmentWidget):
668 ydist = 15 + widgets[0].node().height()
669 else:
670 ydist = 15 + widgets[0].height()
671
672
673 dt = self._animate.get()
674 dy = ydist*2.0/dt
675 self._animate_reduce_frame(dt/2, widgets, dy)
676
678 if frame > 0:
679 self._animating_lock = 1
680 for widget in widgets: widget.move(0, dy)
681 self._top.after(10, self._animate_reduce_frame,
682 frame-1, widgets, dy)
683 else:
684 del self._stackwidgets[-len(widgets):]
685 for widget in widgets:
686 self._cframe.remove_widget(widget)
687 tok = self._parser.stack()[-1]
688 if not isinstance(tok, parse.Tree): raise ValueError()
689 label = TextWidget(self._canvas, str(tok.node), color='#006060',
690 font=self._boldfont)
691 widget = TreeSegmentWidget(self._canvas, label, widgets,
692 width=2)
693 (x1, y1, x2, y2) = self._stacklabel.bbox()
694 y = y2-y1+10
695 if not self._stackwidgets: x = 5
696 else: x = self._stackwidgets[-1].bbox()[2] + 10
697 self._cframe.add_widget(widget, x, y)
698 self._stackwidgets.append(widget)
699
700
701 self._draw_stack_top(widget)
702 self._highlight_productions()
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730 self._animating_lock = 0
731
732
733
734
735
737
738 index = self._prodlist.nearest(event.y)
739 if self._hover == index: return
740
741
742 self._clear_hover()
743
744
745
746 selection = [int(s) for s in self._prodlist.curselection()]
747 if index in selection:
748 rhslen = len(self._productions[index].rhs())
749 for stackwidget in self._stackwidgets[-rhslen:]:
750 if isinstance(stackwidget, TreeSegmentWidget):
751 stackwidget.node()['color'] = '#00a000'
752 else:
753 stackwidget['color'] = '#00a000'
754
755
756 self._hover = index
757
759
760 if self._hover == -1: return
761 self._hover = -1
762 for stackwidget in self._stackwidgets:
763 if isinstance(stackwidget, TreeSegmentWidget):
764 stackwidget.node()['color'] = 'black'
765 else:
766 stackwidget['color'] = 'black'
767
768
770 """
771 Create a shift reduce parser demo, using a simple grammar and
772 text.
773 """
774
775 from nltk_lite.parse import cfg
776 nonterminals = 'S VP NP PP P N Name V Det'
777 (S, VP, NP, PP, P, N, Name, V, Det) = [cfg.Nonterminal(s)
778 for s in nonterminals.split()]
779
780 productions = (
781
782 cfg.Production(S, [NP, VP]),
783 cfg.Production(NP, [Det, N]),
784 cfg.Production(NP, [NP, PP]),
785 cfg.Production(VP, [VP, PP]),
786 cfg.Production(VP, [V, NP, PP]),
787 cfg.Production(VP, [V, NP]),
788 cfg.Production(PP, [P, NP]),
789
790
791 cfg.Production(NP, ['I']), cfg.Production(Det, ['the']),
792 cfg.Production(Det, ['a']), cfg.Production(N, ['man']),
793 cfg.Production(V, ['saw']), cfg.Production(P, ['in']),
794 cfg.Production(P, ['with']), cfg.Production(N, ['park']),
795 cfg.Production(N, ['dog']), cfg.Production(N, ['statue']),
796 cfg.Production(Det, ['my']),
797 )
798
799 grammar = cfg.Grammar(S, productions)
800
801
802 sent = list(tokenize.whitespace('my dog saw a man in the park with a statue'))
803
804 ShiftReduceDemo(grammar, sent).mainloop()
805
806 if __name__ == '__main__': demo()
807