grammar and language classes

The recent discussion of what can and cannot be parsed with various
parsers prompts me to post the following set of Venn diagrams and
examples. Most of the information is gleaned from old class notes from
Charlie Fischer's advanced compiler course at the University of Wisconsin,
circa 1981.


There are three postscript files below. They should be printed
independently. They are separated by lines of hyphens.


The first file is a diagram of grammar classes. The second file is a
diagram of *language* classes. Recall that a language is in a
particular class if it has a grammar in that class. As others have
noted recently in this newsgroup, the language hierarchy collapses for
various amounts of lookahead in LR parsers, but not for LL parsers.
NB: non-det. CFL == non-deterministic context-free language
        det CFL == deterministic context-free language
        p.p. == prefix property: no string in the language is a proper prefix
                        of another string in the language; any language with a
                        distinguished terminating token trivially satisfies the prefix
                        property


The third file is a set of example grammars and languages that fall
into some of the more interesting regions of the Venn diagrams.
--
Michael L. Scott
Computer Science Dept. (716) 275-7745, 5671
University of Rochester FAX 461-2018
Rochester, NY 14627-0226 scott@cs.rochester.edu


-----------------------


%!
%%Title: stdin
%%Creator: fig2dev
%%CreationDate: Wed May 13 11:24:38 1992
%%For: scott@gull.cs.rochester.edu (Michael Scott)
%%BoundingBox: 54 71 468 594
%%Pages: 1
%%EndComments
/$F2psDict 6400 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/l {lineto} bind def
/m {moveto} bind def
/s {stroke} bind def
/n {newpath} bind def
/gs {gsave} bind def
/gr {grestore} bind def
/clp {closepath} bind def
/graycol {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
4 -2 roll mul setrgbcolor} bind def
/col-1 {} def
/col0 {0 0 0 setrgbcolor} bind def
/col1 {0 0 1 setrgbcolor} bind def
/col2 {0 1 0 setrgbcolor} bind def
/col3 {0 1 1 setrgbcolor} bind def
/col4 {1 0 0 setrgbcolor} bind def
/col5 {1 0 1 setrgbcolor} bind def
/col6 {1 1 0 setrgbcolor} bind def
/col7 {1 1 1 setrgbcolor} bind def
  /DrawEllipse {
/endangle exch def
/startangle exch def
/yrad exch def
/xrad exch def
/y exch def
/x exch def
/savematrix mtrx currentmatrix def
x y translate xrad yrad scale 0 0 1 startangle endangle arc
savematrix setmatrix
} def newpath 0 0 0 0 0 1 DrawEllipse stroke


  /DrawSplineSection {
/y3 exch def
/x3 exch def
/y2 exch def
/x2 exch def
/y1 exch def
/x1 exch def
/xa x1 x2 x1 sub 0.666667 mul add def
/ya y1 y2 y1 sub 0.666667 mul add def
/xb x3 x2 x3 sub 0.666667 mul add def
/yb y3 y2 y3 sub 0.666667 mul add def
x1 y1 lineto
xa ya xb yb x3 y3 curveto
} def


end
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def
%%EndProlog


$F2psBegin
0 setlinecap 0 setlinejoin
45.0 728.5 translate 0.900 -0.900 scale
0.500 setlinewidth
% Ellipse
n 194 384 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 184 384 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 174 384 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 139 529 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 149 529 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 159 529 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 303 519 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 313 519 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 323 519 2 2 0 360 DrawEllipse gs col0 s gr
% Open spline
n 139.000 324.000 m 149.000 334.000 l
149.000 334.000 159.000 344.000 299.000 344.000 DrawSplineSection
299.000 344.000 439.000 344.000 449.000 334.000 DrawSplineSection
459.000 324.000 l gs col0 s gr
% Open spline
n 109.000 348.000 m 119.000 358.000 l
119.000 358.000 129.000 368.000 299.000 368.000 DrawSplineSection
299.000 368.000 469.000 368.000 479.000 358.000 DrawSplineSection
489.000 348.000 l gs col0 s gr
% Open spline
n 79.000 399.000 m 89.000 409.000 l
89.000 409.000 99.000 419.000 299.000 419.000 DrawSplineSection
299.000 419.000 499.000 419.000 509.000 409.000 DrawSplineSection
519.000 399.000 l gs col0 s gr
% Open spline
n 259.000 429.000 m 269.000 439.000 l
269.000 439.000 279.000 449.000 329.000 449.000 DrawSplineSection
329.000 449.000 379.000 449.000 389.000 439.000 DrawSplineSection
399.000 429.000 l gs col0 s gr
% Open spline
n 259.000 469.000 m 269.000 479.000 l
269.000 479.000 279.000 489.000 329.000 489.000 DrawSplineSection
329.000 489.000 379.000 489.000 389.000 479.000 DrawSplineSection
399.000 469.000 l gs col0 s gr
% Closed spline
n 399.000 389.000 m
399.000 389.000 399.000 539.000 389.000 549.000 DrawSplineSection
389.000 549.000 379.000 559.000 329.000 559.000 DrawSplineSection
329.000 559.000 279.000 559.000 269.000 549.000 DrawSplineSection
269.000 549.000 259.000 539.000 259.000 389.000 DrawSplineSection
259.000 389.000 259.000 239.000 269.000 229.000 DrawSplineSection
269.000 229.000 279.000 219.000 329.000 219.000 DrawSplineSection
329.000 219.000 379.000 219.000 389.000 229.000 DrawSplineSection
389.000 229.000 399.000 239.000 399.000 389.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 170.000 269.000 m
170.000 269.000 170.000 284.000 180.000 294.000 DrawSplineSection
180.000 294.000 190.000 304.000 300.000 304.000 DrawSplineSection
300.000 304.000 410.000 304.000 420.000 294.000 DrawSplineSection
420.000 294.000 430.000 284.000 430.000 269.000 DrawSplineSection
430.000 269.000 430.000 254.000 420.000 244.000 DrawSplineSection
420.000 244.000 410.000 234.000 300.000 234.000 DrawSplineSection
300.000 234.000 190.000 234.000 180.000 244.000 DrawSplineSection
180.000 244.000 170.000 254.000 170.000 269.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 139.000 329.000 m
139.000 329.000 139.000 439.000 149.000 449.000 DrawSplineSection
149.000 449.000 159.000 459.000 299.000 459.000 DrawSplineSection
299.000 459.000 439.000 459.000 449.000 449.000 DrawSplineSection
449.000 449.000 459.000 439.000 459.000 329.000 DrawSplineSection
459.000 329.000 459.000 219.000 449.000 209.000 DrawSplineSection
449.000 209.000 439.000 199.000 299.000 199.000 DrawSplineSection
299.000 199.000 159.000 199.000 149.000 209.000 DrawSplineSection
149.000 209.000 139.000 219.000 139.000 329.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 119.000 179.000 m
119.000 179.000 129.000 169.000 296.500 169.000 DrawSplineSection
296.500 169.000 464.000 169.000 476.500 179.000 DrawSplineSection
476.500 179.000 489.000 189.000 489.000 334.000 DrawSplineSection
489.000 334.000 489.000 479.000 479.000 489.000 DrawSplineSection
479.000 489.000 469.000 499.000 299.000 499.000 DrawSplineSection
299.000 499.000 129.000 499.000 119.000 489.000 DrawSplineSection
119.000 489.000 109.000 479.000 109.000 334.000 DrawSplineSection
109.000 334.000 109.000 189.000 119.000 179.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 79.000 359.000 m
79.000 359.000 79.000 559.000 89.000 569.000 DrawSplineSection
89.000 569.000 99.000 579.000 299.000 579.000 DrawSplineSection
299.000 579.000 499.000 579.000 509.000 569.000 DrawSplineSection
509.000 569.000 519.000 559.000 519.000 359.000 DrawSplineSection
519.000 359.000 519.000 159.000 509.000 149.000 DrawSplineSection
509.000 149.000 499.000 139.000 299.000 139.000 DrawSplineSection
299.000 139.000 99.000 139.000 89.000 149.000 DrawSplineSection
89.000 149.000 79.000 159.000 79.000 359.000 DrawSplineSection closepath gs col0 s gr
/Times-Roman findfont 11.00 scalefont setfont
59 94 m
gs 1 -1 scale (GRAMMAR CLASSES) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
298 438 m
gs 1 -1 scale (LL\(1\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
298 480 m
gs 1 -1 scale (LL\(2\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
306 550 m
gs 1 -1 scale (LL) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
199 278 m
gs 1 -1 scale (LR\(0\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
164 329 m
gs 1 -1 scale (LALR\(1\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
159 358 m
gs 1 -1 scale (LALR\(2\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
156 410 m
gs 1 -1 scale (LALR) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
129 569 m
gs 1 -1 scale (LR) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
149 489 m
gs 1 -1 scale (LR\(2\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
168 449 m
gs 1 -1 scale (LR\(1\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
131 620 m
gs 1 -1 scale (Also, SLL\(k\) is just inside LL\(k\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
132 638 m
gs 1 -1 scale (and SLR\(k\) is just inside LALR\(k\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
396 639 m
gs 1 -1 scale (.) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
132 660 m
gs 1 -1 scale (Other containments are the same.) col0 show gr
showpage
$F2psEnd


------------------------


%!
%%Title: stdin
%%Creator: fig2dev
%%CreationDate: Wed May 13 11:24:26 1992
%%For: scott@gull.cs.rochester.edu (Michael Scott)
%%BoundingBox: 72 164 396 598
%%Pages: 1
%%EndComments
/$F2psDict 6400 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/l {lineto} bind def
/m {moveto} bind def
/s {stroke} bind def
/n {newpath} bind def
/gs {gsave} bind def
/gr {grestore} bind def
/clp {closepath} bind def
/graycol {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
4 -2 roll mul setrgbcolor} bind def
/col-1 {} def
/col0 {0 0 0 setrgbcolor} bind def
/col1 {0 0 1 setrgbcolor} bind def
/col2 {0 1 0 setrgbcolor} bind def
/col3 {0 1 1 setrgbcolor} bind def
/col4 {1 0 0 setrgbcolor} bind def
/col5 {1 0 1 setrgbcolor} bind def
/col6 {1 1 0 setrgbcolor} bind def
/col7 {1 1 1 setrgbcolor} bind def
  /DrawEllipse {
/endangle exch def
/startangle exch def
/yrad exch def
/xrad exch def
/y exch def
/x exch def
/savematrix mtrx currentmatrix def
x y translate xrad yrad scale 0 0 1 startangle endangle arc
savematrix setmatrix
} def newpath 0 0 0 0 0 1 DrawEllipse stroke


  /DrawSplineSection {
/y3 exch def
/x3 exch def
/y2 exch def
/x2 exch def
/y1 exch def
/x1 exch def
/xa x1 x2 x1 sub 0.666667 mul add def
/ya y1 y2 y1 sub 0.666667 mul add def
/xb x3 x2 x3 sub 0.666667 mul add def
/yb y3 y2 y3 sub 0.666667 mul add def
x1 y1 lineto
xa ya xb yb x3 y3 curveto
} def


end
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def
%%EndProlog


$F2psBegin
0 setlinecap 0 setlinejoin
72.0 777.0 translate 0.900 -0.900 scale
0.500 setlinewidth
% Ellipse
n 229 398 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 219 398 2 2 0 360 DrawEllipse gs col0 s gr
% Ellipse
n 239 398 2 2 0 360 DrawEllipse gs col0 s gr
% Open spline
n 159.000 429.000 m 169.000 419.000 l
169.000 419.000 179.000 409.000 229.000 409.000 DrawSplineSection
229.000 409.000 279.000 409.000 289.000 419.000 DrawSplineSection
299.000 429.000 l gs col0 s gr
% Open spline
n 159.000 469.000 m 169.000 459.000 l
169.000 459.000 179.000 449.000 229.000 449.000 DrawSplineSection
229.000 449.000 279.000 449.000 289.000 459.000 DrawSplineSection
299.000 469.000 l gs col0 s gr
% Closed spline
n 99.000 409.000 m
99.000 409.000 99.000 579.000 109.000 589.000 DrawSplineSection
109.000 589.000 119.000 599.000 269.000 599.000 DrawSplineSection
269.000 599.000 419.000 599.000 429.000 589.000 DrawSplineSection
429.000 589.000 439.000 579.000 439.000 409.000 DrawSplineSection
439.000 409.000 439.000 239.000 429.000 229.000 DrawSplineSection
429.000 229.000 419.000 219.000 269.000 219.000 DrawSplineSection
269.000 219.000 119.000 219.000 109.000 229.000 DrawSplineSection
109.000 229.000 99.000 239.000 99.000 409.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 159.000 439.000 m
159.000 439.000 159.000 499.000 169.000 509.000 DrawSplineSection
169.000 509.000 179.000 519.000 229.000 519.000 DrawSplineSection
229.000 519.000 279.000 519.000 289.000 509.000 DrawSplineSection
289.000 509.000 299.000 499.000 299.000 439.000 DrawSplineSection
299.000 439.000 299.000 379.000 289.000 369.000 DrawSplineSection
289.000 369.000 279.000 359.000 229.000 359.000 DrawSplineSection
229.000 359.000 179.000 359.000 169.000 369.000 DrawSplineSection
169.000 369.000 159.000 379.000 159.000 439.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 149.000 549.000 m
149.000 549.000 159.000 559.000 269.000 559.000 DrawSplineSection
269.000 559.000 379.000 559.000 389.000 549.000 DrawSplineSection
389.000 549.000 399.000 539.000 399.000 519.000 DrawSplineSection
399.000 519.000 399.000 499.000 389.000 489.000 DrawSplineSection
389.000 489.000 379.000 479.000 269.000 479.000 DrawSplineSection
269.000 479.000 159.000 479.000 149.000 489.000 DrawSplineSection
149.000 489.000 139.000 499.000 139.000 519.000 DrawSplineSection
139.000 519.000 139.000 539.000 149.000 549.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 119.000 459.000 m
119.000 459.000 119.000 559.000 129.000 569.000 DrawSplineSection
129.000 569.000 139.000 579.000 269.000 579.000 DrawSplineSection
269.000 579.000 399.000 579.000 409.000 569.000 DrawSplineSection
409.000 569.000 419.000 559.000 419.000 459.000 DrawSplineSection
419.000 459.000 419.000 359.000 409.000 349.000 DrawSplineSection
409.000 349.000 399.000 339.000 269.000 339.000 DrawSplineSection
269.000 339.000 139.000 339.000 129.000 349.000 DrawSplineSection
129.000 349.000 119.000 359.000 119.000 459.000 DrawSplineSection closepath gs col0 s gr
% Closed spline
n 119.000 279.000 m
119.000 279.000 119.000 299.000 129.000 309.000 DrawSplineSection
129.000 309.000 139.000 319.000 199.000 319.000 DrawSplineSection
199.000 319.000 259.000 319.000 269.000 309.000 DrawSplineSection
269.000 309.000 279.000 299.000 279.000 279.000 DrawSplineSection
279.000 279.000 279.000 259.000 269.000 249.000 DrawSplineSection
269.000 249.000 259.000 239.000 199.000 239.000 DrawSplineSection
199.000 239.000 139.000 239.000 129.000 249.000 DrawSplineSection
129.000 249.000 119.000 259.000 119.000 279.000 DrawSplineSection closepath gs col0 s gr
/Times-Roman findfont 11.00 scalefont setfont
79 664 m
gs 1 -1 scale (LANGUAGE CLASSES) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
319 419 m
gs 1 -1 scale (= det. CFL) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
319 399 m
gs 1 -1 scale (= LR) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
319 379 m
gs 1 -1 scale (SLR\(1\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
189 384 m
gs 1 -1 scale (LL = SLL) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
179 439 m
gs 1 -1 scale (LL\(2\) = SLL\(2\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
179 499 m
gs 1 -1 scale (LL\(1\) = SLL\(1\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
220 539 m
gs 1 -1 scale (= det. CFL w/ p.p.) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
319 518 m
gs 1 -1 scale (LR\(0\)) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
299 299 m
gs 1 -1 scale (Non-det. CFL) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
139 298 m
gs 1 -1 scale (ambiguous) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
139 279 m
gs 1 -1 scale (Inherently) col0 show gr
/Times-Roman findfont 11.00 scalefont setfont
99 198 m
gs 1 -1 scale (All languages) col0 show gr
showpage
$F2psEnd


-------------------------------


%!PS-Adobe-1.0
%%Creator: gull.cs.rochester.edu:scott (Michael Scott)
%%Title: stdin (ditroff)
%%CreationDate: Thu May 14 13:20:53 1992
%%EndComments
% Start of psdit.pro -- prolog for ditroff translator
% Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved.
% GOVERNMENT END USERS: See Notice file in TranScript library directory
% -- probably /usr/lib/ps/Notice
% RCS: $Header: /usr/src/staff/transcript/lib/psdit.pro,v 1.2 89/08/07 13:52:50 roche Exp $
/$DITroff 180 dict def $DITroff begin


/DocumentInitState [ matrix currentmatrix currentlinewidth currentlinecap
currentlinejoin currentdash currentgray currentmiterlimit ] cvx def


%% Psfig additions
/startFig {
/SavedState save def
userdict maxlength dict begin
currentpoint transform


DocumentInitState setmiterlimit setgray setdash setlinejoin setlinecap
setlinewidth setmatrix


itransform moveto


/ury exch def
/urx exch def
/lly exch def
/llx exch def
/y exch 72 mul resolution div def
/x exch 72 mul resolution div def


currentpoint /cy exch def /cx exch def


/sx x urx llx sub div def % scaling for x
/sy y ury lly sub div def % scaling for y


sx sy scale % scale by (sx,sy)


cx sx div llx sub
cy sy div ury sub translate


/DefFigCTM matrix currentmatrix def


/initmatrix {
DefFigCTM setmatrix
} def
/defaultmatrix {
DefFigCTM exch copy
} def


/initgraphics {
DocumentInitState setmiterlimit setgray setdash
setlinejoin setlinecap setlinewidth setmatrix
DefFigCTM setmatrix
} def


/showpage {
initgraphics
} def


} def
% Args are llx lly urx ury (in figure coordinates)
/clipFig {
currentpoint 6 2 roll
newpath 4 copy
4 2 roll moveto
6 -1 roll exch lineto
exch lineto
exch lineto
closepath clip
newpath
moveto
} def
% doclip, if called, will always be just after a `startfig'
/doclip { llx lly urx ury clipFig } def
/endFig {
end SavedState restore
} def
/globalstart {
% Push details about the enviornment on the stack.
fontnum fontsize fontslant fontheight
% firstpage
mh my resolution slotno currentpoint
pagesave restore gsave
} def
/globalend {
grestore moveto
/slotno exch def /resolution exch def /my exch def
/mh exch def
% /firstpage exch def
/fontheight exch def
/fontslant exch def /fontsize exch def /fontnum exch def
F
/pagesave save def
} def


%% end XMOD additions


/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
/xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
    /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
    /pagesave save def}def
/PB{save /psv exch def currentpoint translate
    resolution 72 div dup neg scale 0 0 moveto}def
/PE{psv restore}def
/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
/tan{dup sin exch cos div}bind def
/point{resolution 72 div mul}bind def
/dround {transform round exch round exch itransform}bind def
/xT{/devname exch def}def
/xr{/mh exch def /my exch def /resolution exch def}def
/xp{}def
/xs{docsave restore end}def
/xt{}def
/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
  {fonts slotno fontname findfont put fontnames slotno fontname put}if}def
/xH{/fontheight exch def F}bind def
/xS{/fontslant exch def F}bind def
/s{/fontsize exch def /fontheight fontsize def F}bind def
/f{/fontnum exch def F}bind def
/F{fontheight 0 le {/fontheight fontsize def}if
      fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
      fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
      makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def
/X{exch currentpoint exch pop moveto show}bind def
/N{3 1 roll moveto show}bind def
/Y{exch currentpoint pop exch moveto show}bind def
/S /show load def
/ditpush{}def/ditpop{}def
/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def
/AN{4 2 roll moveto 0 exch ashow}bind def
/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def
/AS{0 exch ashow}bind def
/MX{currentpoint exch pop moveto}bind def
/MY{currentpoint pop exch moveto}bind def
/MXY /moveto load def
/cb{pop}def % action on unknown char -- nothing for now
/n{}def/w{}def
/p{pop showpage pagesave restore /pagesave save def}def
/abspoint{currentpoint exch pop add exch currentpoint pop add exch}def
/dstroke{currentpoint stroke moveto}bind def
/Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def
/arcellipse{oldmat currentmatrix pop
  currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
  rad 0 rad -180 180 arc oldmat setmatrix}def
/Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke
        grestore diamh 0 rmoveto}def
/De{gsave /diamv exch def /diamh exch def arcellipse dstroke
        grestore diamh 0 rmoveto}def
/Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def
      /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def
      /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add
      2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def
/Barray 200 array def % 200 values in a wiggle
/D~{mark}def
/D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop
  /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and
  {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def
    Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put
    Bcontrol Blen 2 sub 2 copy get 2 mul put
    Bcontrol Blen 1 sub 2 copy get 2 mul put
    /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub
    {/i exch def
      Bcontrol i get 3 div Bcontrol i 1 add get 3 div
      Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div
      Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div
      /Xbi Xcont Bcontrol i 2 add get 2 div add def
      /Ybi Ycont Bcontrol i 3 add get 2 div add def
      /Xcont Xcont Bcontrol i 2 add get add def
      /Ycont Ycont Bcontrol i 3 add get add def
      Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto
    }for dstroke}if}def
end
/ditstart{$DITroff begin
  /nfonts 60 def % NFONTS makedev/ditroff dependent!
  /fonts[nfonts{0}repeat]def
  /fontnames[nfonts{()}repeat]def
/docsave save def
}def


% character outcalls
/oc {/pswid exch def /cc exch def /name exch def
      /ditwid pswid fontsize mul resolution mul 72000 div def
      /ditsiz fontsize resolution mul 72 div def
      ocprocs name known{ocprocs name get exec}{name cb}
      ifelse}def
/fractm [.65 0 0 .6 0 0] def
/fraction
  {/fden exch def /fnum exch def gsave /cf currentfont def
    cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
    fnum show rmoveto currentfont cf setfont(\244)show setfont fden show
    grestore ditwid 0 rmoveto} def
/oce {grestore ditwid 0 rmoveto}def
/dm {ditsiz mul}def
/ocprocs 50 dict def ocprocs begin
(14){(1)(4)fraction}def
(12){(1)(2)fraction}def
(34){(3)(4)fraction}def
(13){(1)(3)fraction}def
(23){(2)(3)fraction}def
(18){(1)(8)fraction}def
(38){(3)(8)fraction}def
(58){(5)(8)fraction}def
(78){(7)(8)fraction}def
(sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def
(is){gsave 0 .15 dm rmoveto(\362)show oce}def
(->){gsave 0 .02 dm rmoveto(\256)show oce}def
(<-){gsave 0 .02 dm rmoveto(\254)show oce}def
(==){gsave 0 .05 dm rmoveto(\272)show oce}def
end
% DIThacks fonts for some special chars
50 dict dup begin
/FontType 3 def
/FontName /DIThacks def
/FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def
/FontBBox [-220 -280 900 900] def% a lie but ...
/Encoding 256 array def
0 1 255{Encoding exch /.notdef put}for
Encoding
  dup 8#040/space put %space
  dup 8#110/rc put %right ceil
  dup 8#111/lt put %left top curl
  dup 8#112/bv put %bold vert
  dup 8#113/lk put %left mid curl
  dup 8#114/lb put %left bot curl
  dup 8#115/rt put %right top curl
  dup 8#116/rk put %right mid curl
  dup 8#117/rb put %right bot curl
  dup 8#120/rf put %right floor
  dup 8#121/lf put %left floor
  dup 8#122/lc put %left ceil
  dup 8#140/sq put %square
  dup 8#141/bx put %box
  dup 8#142/ci put %circle
  dup 8#143/br put %box rule
  dup 8#144/rn put %root extender
  dup 8#145/vr put %vertical rule
  dup 8#146/ob put %outline bullet
  dup 8#147/bu put %bullet
  dup 8#150/ru put %rule
  dup 8#151/ul put %underline
  pop
/DITfd 100 dict def
/BuildChar{0 begin
  /cc exch def /fd exch def
  /charname fd /Encoding get cc get def
  /charwid fd /Metrics get charname get def
  /charproc fd /CharProcs get charname get def
  charwid 0 fd /FontBBox get aload pop setcachedevice
  40 setlinewidth
  newpath 0 0 moveto gsave charproc grestore
  end}def
/BuildChar load 0 DITfd put
%/UniqueID 5 def
/CharProcs 50 dict def
CharProcs begin
/space{}def
/.notdef{}def
/ru{500 0 rls}def
/rn{0 750 moveto 500 0 rls}def
/vr{20 800 moveto 0 -770 rls}def
/bv{20 800 moveto 0 -1000 rls}def
/br{20 770 moveto 0 -1040 rls}def
/ul{0 -250 moveto 500 0 rls}def
/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
/sq{80 0 rmoveto currentpoint dround newpath moveto
        640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
/bx{80 0 rmoveto currentpoint dround newpath moveto
        640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
/ci{355 333 rmoveto currentpoint newpath 333 0 360 arc
        50 setlinewidth stroke}def


/lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
/lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
/rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
/rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
/lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub
        currentpoint stroke moveto
        20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def
/rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub
        currentpoint stroke moveto
        20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def
/lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def
/rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
/lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def
/rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
end


/Metrics 50 dict def Metrics begin
/.notdef 0 def
/space 500 def
/ru 500 def
/br 0 def
/lt 250 def
/lb 250 def
/rt 250 def
/rb 250 def
/lk 250 def
/rk 250 def
/rc 250 def
/lc 250 def
/rf 250 def
/lf 250 def
/bv 250 def
/ob 350 def
/bu 350 def
/ci 750 def
/bx 750 def
/sq 750 def
/rn 500 def
/ul 500 def
/vr 0 def
end


DITfd begin
/s2 500 def /s4 250 def /s3 333 def
/a4p{arcto pop pop pop pop}def
/2cx{2 copy exch}def
/rls{rlineto stroke}def
/currx{currentpoint pop}def
/dround{transform round exch round exch itransform} def


end
end
/DIThacks exch definefont pop


ditstart
(psc)xT
576 1 1 xr
1(Times-Roman)xf 1 f
2(Times-Italic)xf 2 f
3(Times-Bold)xf 3 f
4(Times-BoldItalic)xf 4 f
5(Helvetica)xf 5 f
6(Helvetica-Bold)xf 6 f
7(Courier)xf 7 f
8(Courier-Bold)xf 8 f
9(Symbol)xf 9 f
10(DIThacks)xf 10 f
10 s
1 f
xi
%%EndProlog


%%Page: 1 1
10 s 10 xH 0 xS 1 f
3 f
11 s
1831 771(Grammar)N
2234(and)X
2398(Language)X
2792(Classes)X
1 f
720 1068(LL\(2\))N
952(but)X
1087(not)X
1222(SLL)X
920 1200(S')N
9 f
1150 MX
(->)174 987 oc
1 f
1380($)X
1446(S)X
1517($)X
920 1299(S)N
9 f
1150 MX
(->)174 987 oc
1 f
1380(a)X
1441(A)X
1526(a)X
9 f
1587(|)X
1 f
1627(b)X
1693(A)X
1778(b)X
1844(a)X
920 1398(A)N
9 f
1150 MX
(->)174 987 oc
1 f
1380(b)X
9 f
1446(|)X
1486(e)X
1 f
720 1563(SLL\(k\))N
1001(but)X
1136(not)X
1271(LL\(k)X
9 f
1452(-)X
1 f
1500(1\))X
920 1695(S')N
9 f
1208 MX
(->)174 987 oc
1 f
1496($)X
1562(S)X
1633($)X
920 1811(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(A)X
1581(b)X
9 f
1647(|)X
1 f
1687(E)X
1763(a)X
8 s
1802 1776(k)N
11 s
920 1927(A)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(a)X
8 s
1535 1892(k)N
9 f
(-)S
1 f
1602(1)X
11 s
920 2026(E)N
9 f
1208 MX
(->)174 987 oc
1496(e)X
1 f
720 2191(LR\(0\))N
957(but)X
1092(not)X
1227(LL)X
920 2323(S')N
9 f
1208 MX
(->)174 987 oc
1 f
1496($)X
1562(S)X
1633($)X
920 2422(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(A)X
1581(b)X
920 2521(A)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(A)X
1581(a)X
9 f
1642(|)X
1 f
1682(a)X
720 2686(SLL\(1\))N
1001(but)X
1136(not)X
1271(LALR)X
920 2818(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(A)X
1581(a)X
9 f
1642(|)X
1 f
1682(B)X
1763(b)X
9 f
1829(|)X
1 f
1869(d)X
1935(F)X
920 2917(F)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(A)X
1581(b)X
9 f
1647(|)X
1 f
1687(B)X
1768(a)X
920 3016(A)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(E)X
920 3115(B)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(E)X
920 3214(E)N
9 f
1208 MX
(->)174 987 oc
1496(e)X
1 f
720 3379(SLL\(k\))N
1001(but)X
1136(not)X
1271(LR\(k)X
9 f
1457(-)X
1 f
1505(1\))X
920 3511(S')N
9 f
1208 MX
(->)174 987 oc
1 f
1496($)X
1562(S)X
1633($)X
920 3627(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(A)X
1581(a)X
8 s
1620 3592(k)N
9 f
(-)S
1 f
1687(1)X
11 s
1741 3627(b)N
9 f
1807(|)X
1 f
1847(B)X
1928(a)X
8 s
1967 3592(k)N
9 f
(-)S
1 f
2034(1)X
11 s
2088 3627(c)N
920 3726(A)N
9 f
1208 MX
(->)174 987 oc
1496(e)X
1 f
920 3825(B)N
9 f
1208 MX
(->)174 987 oc
1496(e)X
1 f
720 3990(SLR\(k\))N
1006(but)X
1141(not)X
1276(LR\(k)X
9 f
1462(-)X
1 f
1510(1\))X
920 4122(S')N
9 f
1208 MX
(->)174 987 oc
1 f
1496($)X
1562(S)X
1633($)X
920 4238(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(A)X
1581(b)X
8 s
4203(k)Y
9 f
(-)S
1 f
1692(1)X
11 s
1746 4238(c)N
9 f
1807(|)X
1 f
1847(B)X
1928(b)X
8 s
4203(k)Y
9 f
(-)S
1 f
2039(1)X
11 s
2093 4238(d)N
920 4337(A)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(a)X
920 4436(B)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(a)X
720 4601(LALR\(1\))N
1074(but)X
1209(not)X
1344(SLR)X
920 4733(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(j)X
1543(A)X
1628(j)X
9 f
1675(|)X
1 f
1715(A)X
1800(i)X
9 f
1847(|)X
1 f
1887(a)X
1948(j)X
920 4832(A)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(a)X
720 4997(LR\(1\))N
957(but)X
1092(not)X
1227(LALR)X
920 5129(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(a)X
1557(E)X
1633(a)X
9 f
1694(|)X
1 f
1734(b)X
1800(E)X
1876(b)X
9 f
1942(|)X
1 f
1982(a)X
2043(F)X
2114(b)X
9 f
2180(|)X
1 f
2220(b)X
2286(F)X
2357(a)X
920 5228(E)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(e)X
920 5327(F)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(e)X
720 5492(Unambiguous)N
1236(but)X
1371(not)X
1506(LR)X
920 5624(S)N
9 f
1208 MX
(->)174 987 oc
1 f
1496(a)X
1557(S)X
1628(a)X
9 f
1689(|)X
1729(e)X
1 f
2528 1068(Non-deterministic)N
3192(language)X
2728 1217({)N
2792(0)X
8 s
1182(n)Y
11 s
2890 1217(1)N
8 s
1182(n)Y
11 s
2988 1217(a)N
9 f
3049(|)X
1 f
3089(n)X
9 f
3155(\263)X
1 f
3225(1)X
3291(})X
9 f
3355(\310)X
1 f
3445({)X
3509(0)X
8 s
1182(n)Y
11 s
3607 1217(1)N
8 s
1182(2n)Y
11 s
3737 1217(b)N
9 f
3803(|)X
1 f
3843(n)X
9 f
3909(\263)X
1 f
3979(1)X
4045(})X
2528 1382(Inherently)N
2912(ambiguous)X
3321(language)X
2728 1531({)N
2792(a)X
8 s
2831 1496(i)N
11 s
2871 1531(b)N
8 s
1496(j)Y
11 s
2955 1531(c)N
8 s
2994 1496(k)N
11 s
9 f
3048 1531(|)N
1 f
3088(i)X
3135(=)X
3207(j)X
3254(or)X
3349(j)X
3396(=)X
3468(k;)X
3559(i,)X
3628(j,)X
3697(k)X
9 f
3763(\263)X
1 f
3833(1)X
3899(})X
2528 1696(Language)N
2897(with)X
3076(LL\(k\))X
3308(grammar)X
3648(but)X
3783(no)X
2528 1795(LL\(k)N
9 f
2709(-)X
1 f
2757(1\))X
2852(grammar)X
2728 1944({)N
2792(a)X
8 s
2831 1909(n)N
11 s
2885 1944(\()N
2936(b,)X
3024(c,)X
3107(b)X
8 s
1909(k)Y
11 s
3205 1944(d)N
3271(\))X
8 s
3300 1909(n)N
11 s
9 f
3354 1944(|)N
1 f
3394(n)X
9 f
3460(\263)X
1 f
3530(1)X
3596(})X
2528 2109(Language)N
2897(with)X
3076(LR\(0\))X
3313(grammar)X
3653(but)X
3788(no)X
3898(LL)X
2528 2208(grammar)N
2728 2357({)N
2792(a)X
8 s
2831 2322(n)N
11 s
2885 2357(b)N
8 s
2322(n)Y
11 s
9 f
2983 2357(|)N
1 f
3023(n)X
9 f
3089(\263)X
1 f
3159(1)X
3225(})X
9 f
3289(\310)X
1 f
3379({)X
3443(a)X
8 s
3482 2322(n)N
11 s
3536 2357(c)N
8 s
3575 2322(n)N
11 s
9 f
3629 2357(|)N
1 f
3669(n)X
9 f
3735(\263)X
1 f
3805(1)X
3871(})X


1 p
%%Trailer
xt


xs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.