%!PS-Adobe-3.0 %%Creator: groff version 1.16.1 %%CreationDate: Sun Jul 7 03:03:32 2002 %%DocumentNeededResources: font Times-Roman %%+ font Times-Bold %%+ font Times-Italic %%DocumentSuppliedResources: procset grops 1.16 1 %%Pages: 30 %%PageOrder: Ascend %%Orientation: Portrait %%EndComments %%BeginProlog %%BeginResource: procset grops 1.16 1 /setpacking where{ pop currentpacking true setpacking }if /grops 120 dict dup begin /SC 32 def /A/show load def /B{0 SC 3 -1 roll widthshow}bind def /C{0 exch ashow}bind def /D{0 exch 0 SC 5 2 roll awidthshow}bind def /E{0 rmoveto show}bind def /F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def /G{0 rmoveto 0 exch ashow}bind def /H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def /I{0 exch rmoveto show}bind def /J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def /K{0 exch rmoveto 0 exch ashow}bind def /L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def /M{rmoveto show}bind def /N{rmoveto 0 SC 3 -1 roll widthshow}bind def /O{rmoveto 0 exch ashow}bind def /P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def /Q{moveto show}bind def /R{moveto 0 SC 3 -1 roll widthshow}bind def /S{moveto 0 exch ashow}bind def /T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def /SF{ findfont exch [exch dup 0 exch 0 exch neg 0 0]makefont dup setfont [exch/setfont cvx]cvx bind def }bind def /MF{ findfont [5 2 roll 0 3 1 roll neg 0 0]makefont dup setfont [exch/setfont cvx]cvx bind def }bind def /level0 0 def /RES 0 def /PL 0 def /LS 0 def /MANUAL{ statusdict begin/manualfeed true store end }bind def /PLG{ gsave newpath clippath pathbbox grestore exch pop add exch pop }bind def /BP{ /level0 save def 1 setlinecap 1 setlinejoin 72 RES div dup scale LS{ 90 rotate }{ 0 PL translate }ifelse 1 -1 scale }bind def /EP{ level0 restore showpage }bind def /DA{ newpath arcn stroke }bind def /SN{ transform .25 sub exch .25 sub exch round .25 add exch round .25 add exch itransform }bind def /DL{ SN moveto SN lineto stroke }bind def /DC{ newpath 0 360 arc closepath }bind def /TM matrix def /DE{ TM currentmatrix pop translate scale newpath 0 0 .5 0 360 arc closepath TM setmatrix }bind def /RC/rcurveto load def /RL/rlineto load def /ST/stroke load def /MT/moveto load def /CL/closepath load def /FL{ currentgray exch setgray fill setgray }bind def /BL/fill load def /LW/setlinewidth load def /RE{ findfont dup maxlength 1 index/FontName known not{1 add}if dict begin { 1 index/FID ne{def}{pop pop}ifelse }forall /Encoding exch def dup/FontName exch def currentdict end definefont pop }bind def /DEFS 0 def /EBEGIN{ moveto DEFS begin }bind def /EEND/end load def /CNT 0 def /level1 0 def /PBEGIN{ /level1 save def translate div 3 1 roll div exch scale neg exch neg exch translate 0 setgray 0 setlinecap 1 setlinewidth 0 setlinejoin 10 setmiterlimit []0 setdash /setstrokeadjust where{ pop false setstrokeadjust }if /setoverprint where{ pop false setoverprint }if newpath /CNT countdictstack def userdict begin /showpage{}def }bind def /PEND{ clear countdictstack CNT sub{end}repeat level1 restore }bind def end def /setpacking where{ pop setpacking }if %%EndResource %%IncludeResource: font Times-Roman %%IncludeResource: font Times-Bold %%IncludeResource: font Times-Italic grops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72 def/PL 792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron /scaron/zcaron/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef /.notdef/.notdef/space/exclam/quotedbl/numbersign/dollar/percent /ampersand/quoteright/parenleft/parenright/asterisk/plus/comma/hyphen /period/slash/zero/one/two/three/four/five/six/seven/eight/nine/colon /semicolon/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N/O /P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright/circumflex /underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y /z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase/guillemotleft /guillemotright/bullet/florin/fraction/perthousand/dagger/daggerdbl /endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut /dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash /quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen /brokenbar/section/dieresis/copyright/ordfeminine/guilsinglleft /logicalnot/minus/registered/macron/degree/plusminus/twosuperior /threesuperior/acute/mu/paragraph/periodcentered/cedilla/onesuperior /ordmasculine/guilsinglright/onequarter/onehalf/threequarters /questiondown/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE /Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex /Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis /multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn /germandbls/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla /egrave/eacute/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis /eth/ntilde/ograve/oacute/ocircumflex/otilde/odieresis/divide/oslash /ugrave/uacute/ucircumflex/udieresis/yacute/thorn/ydieresis]def /Times-Italic@0 ENC0/Times-Italic RE/Times-Bold@0 ENC0/Times-Bold RE /Times-Roman@0 ENC0/Times-Roman RE %%EndProlog %%Page: 1 1 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q/F1 12/Times-Bold@0 SF -1.02 -1.32(YA C) 182.148 135 T 3(C\255Y)1.32 G(et Another Compiler)-4.332 E(-Compiler) -.444 E/F2 10/Times-Italic@0 SF(Stephen C. J)248.545 159 Q(ohnson)-.25 E F0(Bell Laboratories,)251.895 177 Q(Murray Hill, Ne)224.74 189 Q 2.5(wJ) -.25 G(erse)-2.5 E 2.5(y0)-.15 G(7974)-2.5 E F2(ABSTRA)264.535 237 Q(CT) -.3 E F0 .203(Computer program input generally has some structure; in f) 133 261 R .202(act, e)-.1 F -.15(ve)-.25 G .202(ry computer pro-).15 F 1.01(gram which does input can be thought of as de\214ning an `)108 273 R 1.01(`input language')-.74 F 3.51('w)-.74 G 1.01(hich it ac-)-3.51 F 2.853(cepts. The)108 285 R .352(input languages may be as comple)2.853 F 2.852(xa)-.15 G 2.852(sap)-2.852 G .352 (rogramming language, or as simple)-2.852 F .476 (as a sequence of numbers.)108 297 R(Unfortunately)5.476 E 2.976(,s)-.65 G .476(tandard input f)-2.976 F .477(acilities are restricted, dif)-.1 F (\214cult)-.25 E (to use and change, and do not completely check their inputs for v)108 309 Q(alidity)-.25 E(.)-.65 E -1(Ya)133 324.6 S .5(cc pro)1 F .499 (vides a general tool for controlling the input to a computer program.) -.15 F(The)5.499 E -1(Ya)108 336.6 S .377(cc user describes the structu\ res of his input, together with code which is to be in)1 F -.2(vo)-.4 G -.1(ke).2 G(d).1 E .276(when each such structure is recognized.)108 348.6 R -1(Ya)5.275 G .275 (cc turns such a speci\214cation into a subroutine)1 F .238 (which may be in)108 360.6 R -.2(vo)-.4 G -.1(ke).2 G 2.738(dt).1 G 2.738(oh)-2.738 G .239(andle the input process; frequently)-2.738 F 2.739(,i)-.65 G 2.739(ti)-2.739 G 2.739(sc)-2.739 G(on)-2.739 E -.15(ve) -.4 G .239(nient and appro-).15 F .11(priate to ha)108 372.6 R .41 -.15 (ve m)-.2 H .11(ost of the \215o).15 F 2.609(wo)-.25 G 2.609(fc)-2.609 G .109(ontrol in the user\264s application handled by this subrou-)-2.609 F(tine.)108 384.6 Q .914(The input subroutine produced by Y)133 400.2 R .915(acc calls a user supplied routine to return the)-1 F(ne)108 412.2 Q 1.065(xt basic input item.)-.15 F 1.065 (Thus, the user can specify his input in terms of indi)6.065 F 1.064 (vidual input)-.25 F .836(characters, or)108 424.2 R 3.336(,i)-.4 G 3.336(fh)-3.336 G 3.336(ew)-3.336 G .836(ishes, in terms of higher le) -3.336 F -.15(ve)-.25 G 3.336(lc).15 G .836 (onstructs such as names and num-)-3.336 F 2.783(bers. The)108 436.2 R .282(user supplied routine may also handle idiomatic features such as c\ omment and)2.783 F(continuation con)108 448.2 Q -.15(ve)-.4 G (ntions, which typically defy easy speci\214cation.).15 E -1(Ya)133 463.8 S .055(cc is written in C[7], and runs under UNIX.)1 F .055 (The subroutine which is output may)5.055 F .437(be in C or in Ratfor[4\ ], at the user\264s choice; Ratfor permits translation of the output su\ b-)108 475.8 R 1.374(routine into portable F)108 487.8 R 3.874 (ortran[5]. The)-.15 F 1.374(class of speci\214cations accepted is a v) 3.874 F 1.375(ery general)-.15 F .804 (one, called LALR\(1\) grammars with disambiguating rules.)108 499.8 R .803(The theory behind Y)5.804 F .803(acc has)-1 F(been described else) 108 511.8 Q(where[1,2,3].)-.25 E -1(Ya)133 527.4 S .524(cc w)1 F .524 (as originally designed to help produce the `)-.1 F .525(`front end') -.74 F 3.025('o)-.74 G 3.025(fc)-3.025 G .525(ompilers; in ad-)-3.025 F .132(dition to this use, it has been successfully used in man)108 539.4 R 2.631(ya)-.15 G .131(pplication programs, including a)-2.631 F .729 (phototypesetter language, a document retrie)108 551.4 R -.25(va)-.25 G 3.229(ls).25 G .729(ystem, a F)-3.229 F .729(ortran deb)-.15 F .729 (ugging system, and)-.2 F(the Ratfor compiler)108 563.4 Q(.)-.55 E EP %%Page: 1 2 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q/F1 12/Times-Bold@0 SF -1.02 -1.32(YA C) 182.148 135 T 3(C\255Y)1.32 G(et Another Compiler)-4.332 E(-Compiler) -.444 E/F2 10/Times-Italic@0 SF(Stephen C. J)248.545 159 Q(ohnson)-.25 E F0(Bell Laboratories,)251.895 177 Q(Murray Hill, Ne)224.74 189 Q 2.5(wJ) -.25 G(erse)-2.5 E 2.5(y0)-.15 G(7974)-2.5 E/F3 10/Times-Bold@0 SF (Section 0: Intr)72 225 Q(oduction)-.18 E F0 -1(Ya)97 240.6 S .82 (cc pro)1 F .82(vides a general tool for imposing structure on the inpu\ t to a computer program.)-.15 F .82(The Y)5.82 F(acc)-1 E 1.323(user pr\ epares a speci\214cation of the input process; this includes rules whic\ h describe the input structure,)72 252.6 R .006(code which is to be in) 72 264.6 R -.2(vo)-.4 G -.1(ke).2 G 2.506(dw).1 G .006 (hen these structures are recognized, and a lo)-2.506 F(w-le)-.25 E -.15 (ve)-.25 G 2.506(lr).15 G .005(outine to do the basic in-)-2.506 F 3.29 (put. Y)72 276.6 R .791(acc then produces a subroutine to do the input \ procedure; this subroutine, called a)-1 F F2(par)3.291 E(ser)-.1 E(,) -1.11 E F0 .791(calls the)3.291 F(user)72 288.6 Q .382(-supplied lo)-.2 F(w-le)-.25 E -.15(ve)-.25 G 2.882(li).15 G .382 (nput routine \(called the)-2.882 F F2(le)2.881 E .381(xical analyzer\)) -.2 F F0 .381(to pick up the basic items \(called)2.881 F F2(tok)2.881 E (ens\))-.1 E F0 .763(from the input stream.)72 300.6 R .763(These tok) 5.763 F .763(ens are or)-.1 F -.05(ga)-.18 G .764 (nized according to the input structure rules, called).05 F F2(gr)3.264 E(ammar)-.15 E(rules;)72 312.6 Q F0 .476(when one of these rules has be\ en recognized, then the user code supplied for this rule, called an) 2.977 F F2(ac-)2.976 E(tion,)72 324.6 Q F0(is in)2.5 E -.2(vo)-.4 G -.1 (ke).2 G(d; actions ha).1 E .3 -.15(ve t)-.2 H(he ability to return v) .15 E(alues and mak)-.25 E 2.5(eu)-.1 G(se of the v)-2.5 E (alues of other actions.)-.25 E .805(The heart of the input speci\214ca\ tion is a collection of grammar rules.)97 340.2 R .806 (Each rule describes an allo)5.806 F(w-)-.25 E(able structure and gi)72 352.2 Q -.15(ve)-.25 G 2.5(si).15 G 2.5(tan)-2.5 G 2.5(ame. F)-2.5 F (or e)-.15 E(xample, one grammar rule might be)-.15 E .4 LW 168 372.7 163 372.7 DL 2.5(date : month name day \264,\264 year)108 370.2 R(;)7.5 E 151.238 390.7 146.238 390.7 DL 1.294(Here, date, month)72 388.2 R 1.294(name, day)5 F 3.794(,a)-.65 G 1.293(nd year represent structures \ of interest in the input process; presumably)-3.794 F(,)-.65 E 102.56 402.7 97.56 402.7 DL 2.5(month name,)72 400.2 R(day)2.735 E 2.735(,a) -.65 G .235(nd year are de\214ned else)-2.735 F 2.735(where. The)-.25 F .235(comma `)2.735 F(`,)-.74 E 1.715 -.74('' i)-.7 H 2.735(sq).74 G .235 (uoted by single quotes; this implies)-2.735 F .4 (that the comma is to appear literally in the input.)72 412.2 R .4 (The colon and semicolon merely serv)5.4 F 2.9(ea)-.15 G 2.9(sp)-2.9 G .4(unctuation in)-2.9 F(the rule, and ha)72 424.2 Q .3 -.15(ve n)-.2 H 2.5(os).15 G(igni\214cance in controlling the input.)-2.5 E (Thus, with proper de\214nitions, the input)5 E 2.5(July 4,)108 442.2 R (1776)2.5 E(might be matched by the abo)72 460.2 Q .3 -.15(ve r)-.15 H (ule.).15 E .393(As we mentioned abo)97 475.8 R -.15(ve)-.15 G 2.893(,a) .15 G 2.893(ni)-2.893 G .394 (mportant part of the input process is carried out by the le)-2.893 F .394(xical analyzer)-.15 F(.)-.55 E .62(This user routine reads the tru\ e input stream, recognizing those structures which are more con)72 487.8 R -.15(ve)-.4 G .62(niently or).15 F .633(more ef)72 499.8 R .633 (\214ciently recognized directly)-.25 F 3.133(,a)-.65 G .633 (nd communicates these recognized tok)-3.133 F .633(ens to the parser) -.1 F 5.633(.F)-.55 G .634(or histori-)-5.783 F .934 (cal reasons, the name of a structure recognized by the le)72 511.8 R .933(xical analyzer is called a)-.15 F F2 .933(terminal symbol)3.433 F F0(name,)3.433 E .522 (while the name of a structure recognized by the parser is called a)72 523.8 R F2 .522(nonterminal symbol)3.022 F F0 3.023(name. T)3.023 F 3.023(oa)-.8 G -.2(vo)-3.223 G .523(id the).2 F(ob)72 535.8 Q (vious confusion of terminology)-.15 E 2.5(,w)-.65 G 2.5(es)-2.5 G (hall usually refer to terminal symbol names as)-2.5 E F2(tok)2.5 E (en names.)-.1 E F0 .008(There is considerable lee)97 551.4 R -.1(wa) -.25 G 2.508(yi).1 G 2.508(nd)-2.508 G .007 (eciding whether to recognize structures by the le)-2.508 F .007 (xical analyzer or by)-.15 F 2.5(ag)72 563.4 S(rammar rule.)-2.5 E (Thus, in the abo)5 E .3 -.15(ve ex)-.15 H(ample it w).15 E (ould be possible to ha)-.1 E .3 -.15(ve o)-.2 H(ther rules of the form) .15 E 138.56 583.9 133.56 583.9 DL 2.5(month name : \264J\264)108 581.4 R2.5 E(;)7.5 E 138.56 595.9 133.56 595.9 DL 2.5 (month name : \264F\264)108 593.4 R2.5 E(;)7.5 E 2.5 (...)130.5 617.4 S 138.56 643.9 133.56 643.9 DL 2.5 (month name : \264D\264)108 641.4 R2.5 E(;)7.5 E 1.271 (Here, the le)72 659.4 R 1.271(xical analyzer w)-.15 F 1.271 (ould only need to recognize indi)-.1 F 432.244 661.9 427.244 661.9 DL 1.272(vidual letters, and month)323.989 659.4 R 1.272(name w)5 F 1.272 (ould be a)-.1 F .003(nonterminal symbol.)72 671.4 R .003 (Rules of this sort tend to be a bit w)5.003 F .002 (asteful of time and space, and may e)-.1 F -.15(ve)-.25 G 2.502(nr).15 G .002(estrict the)-2.502 F(po)72 683.4 Q .338 (wer of the input process \(although the)-.25 F 2.838(ya)-.15 G .338 (re easy to write\).)-2.838 F -.15(Fo)5.338 G -5.337 2.838(ra m).15 H .339(ore ef)-2.838 F .339(\214cient input process, the le)-.25 F(xical) -.15 E 429.77 697.9 424.77 697.9 DL .431(analyzer itself might recogniz\ e the month names, and return an indication that a month)72 695.4 R .43 (name w)5 F .43(as seen; in)-.1 F 141.72 709.9 136.72 709.9 DL (this case, month)72 707.4 Q(name w)5 E(ould be a tok)-.1 E(en.)-.1 E EP %%Page: 2 3 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893289>278 60 S .638 (Literal characters, such as `)97 108 R(`,)-.74 E -.74('')-.7 G 3.138 (,m).74 G .638(ust also be passed through the le)-3.138 F .638 (xical analyzer)-.15 F 3.138(,a)-.4 G .638(nd are considered)-3.138 F (tok)72 120 Q(ens.)-.1 E .485(As an e)97 135.6 R .484 (xample of the \215e)-.15 F .484 (xibility of the grammar rule approach, we might add to the abo)-.15 F .784 -.15(ve s)-.15 H(peci\214ca-).15 E(tions the rule)72 147.6 Q 2.5 (date : month)108 165.6 R(\264/\264 day \264/\264 year)2.5 E(;)7.5 E (and thus optionally allo)72 183.6 Q 2.5(wt)-.25 G(he form)-2.5 E (7/4/1776)108 201.6 Q(as a synon)72 219.6 Q(ym for)-.15 E(July 4, 1776) 108 237.6 Q 1.117(In most cases, this ne)72 255.6 R 3.617(wr)-.25 G 1.117(ule could be `)-3.617 F 1.117(`slipped in')-.74 F 3.617('t)-.74 G 3.617(oaw)-3.617 G 1.118(orking system with minimal ef)-3.717 F 1.118 (fort, and a v)-.25 F(ery)-.15 E(small chance of disrupting e)72 267.6 Q (xisting input.)-.15 E(Frequently)97 283.2 Q 2.561(,t)-.65 G .061(he in\ put being read does not conform to the speci\214cations due to errors i\ n the input.)-2.561 F(The)5.06 E .158(parsers produced by Y)72 295.2 R .159(acc ha)-1 F .459 -.15(ve t)-.2 H .159(he v).15 F .159 (ery desirable property that the)-.15 F 2.659(yw)-.15 G .159 (ill detect these input errors at the ear)-2.659 F(-)-.2 E .84(liest pl\ ace at which this can be done with a left-to-right scan; thus, not only\ is the chance of reading and)72 307.2 R .47 (computing with bad input data substantially reduced, b)72 319.2 R .471 (ut the bad data can usually be quickly found.)-.2 F(Error)5.471 E .675 (handling f)72 331.2 R .674(acilities, entered as part of the input spe\ ci\214cations, frequently permit the reentry of bad data, or)-.1 F (the continuation of the input process after skipping o)72 343.2 Q -.15 (ve)-.15 G 2.5(rt).15 G(he bad data.)-2.5 E .997(In some cases, Y)97 358.8 R .997(acc f)-1 F .997(ails to produce a parser when gi)-.1 F -.15 (ve)-.25 G 3.497(nas).15 G .997(et of speci\214cations.)-3.497 F -.15 (Fo)5.997 G 3.497(re).15 G .998(xample, the)-3.647 F .443 (speci\214cations may be self contradictory)72 370.8 R 2.942(,o)-.65 G 2.942(rt)-2.942 G(he)-2.942 E 2.942(ym)-.15 G .442(ay require a more po) -2.942 F .442(werful recognition mechanism than)-.25 F .292(that a)72 382.8 R -.25(va)-.2 G .292(ilable to Y).25 F 2.792(acc. The)-1 F .292(f\ ormer cases probably represent true design errors; the latter cases can\ often be)2.792 F .676(corrected by making the le)72 394.8 R .676 (xical analyzer more po)-.15 F .676(werful, or by re)-.25 F .675 (writing some of the grammar rules.)-.25 F(The)5.675 E 1.415 (class of speci\214cations which Y)72 406.8 R 1.415 (acc can handle compares v)-1 F 1.415(ery f)-.15 F -.2(avo)-.1 G 1.416 (rably with other systems of this type;).2 F(moreo)72 418.8 Q -.15(ve) -.15 G .809 -.4(r, t).15 H .008(he constructions which are dif).4 F .008 (\214cult for Y)-.25 F .008(acc to handle are also frequently dif)-1 F .008(\214cult for human be-)-.25 F 1.077(ings to handle.)72 430.8 R 1.077(Some users ha)6.077 F 1.377 -.15(ve r)-.2 H 1.077 (eported that the discipline of formulating v).15 F 1.078(alid Y)-.25 F 1.078(acc speci\214cations for)-1 F(their input re)72 442.8 Q -.15(ve) -.25 G(aled errors of conception or design early in the program de).15 E -.15(ve)-.25 G(lopment.).15 E .596(The ne)97 458.4 R .596(xt se)-.15 F -.15(ve)-.25 G .595 (ral sections describe the basic process of preparing a Y).15 F .595 (acc speci\214cation; Section 1 de-)-1 F .621(scribes the preparation o\ f grammar rules, Section 2 the preparation of the user supplied actions\ associated)72 470.4 R .049 (with these rules, and Section 3 the preparation of le)72 482.4 R .049 (xical analyzers.)-.15 F .049(In Section 4, we discuss the diagnostics) 5.049 F 1.468(produced when Y)72 494.4 R 1.468 (acc is unable to produce a parser from the gi)-1 F -.15(ve)-.25 G 3.968 (ns).15 G 3.968(peci\214cations. This)-3.968 F 1.469(section also de-) 3.968 F .119(scribes a simple, frequently useful mechanism for handling\ operator precedences.)72 506.4 R .118(Section 5 discusses error)5.118 F .617(detection and reco)72 518.4 R -.15(ve)-.15 G(ry).15 E 5.617(.S)-.65 G .617(ections 6C and 6R discuss the operating en)-5.617 F .618 (vironment and special features of the)-.4 F .151(subroutines which Y)72 530.4 R .151(acc produces in C and Ratfor)-1 F 2.651(,r)-.4 G(especti) -2.651 E -.15(ve)-.25 G(ly).15 E 5.151(.S)-.65 G .151(ection 7 gi)-5.151 F -.15(ve)-.25 G 2.65(ss).15 G .15(ome hints which may lead)-2.65 F .686 (to better designed, more ef)72 542.4 R .686 (\214cient, and clearer speci\214cations.)-.25 F(Finally)5.686 E 3.186 (,S)-.65 G .686(ection 8 has a brief summary)-3.186 F 5.686(.A)-.65 G (p-)-5.686 E .476(pendix A has a brief e)72 554.4 R .475 (xample, and Appendix B tells ho)-.15 F 2.975(wt)-.25 G 2.975(or)-2.975 G .475(un Y)-2.975 F .475(acc on the UNIX operating system.)-1 F(Ap-) 5.475 E 1.295(pendix C has a brief description of mechanisms and syntax\ which are no longer acti)72 566.4 R -.15(ve)-.25 G 1.295 (ly supported, b).15 F(ut)-.2 E(which are pro)72 578.4 Q (vided for historical continuity with older v)-.15 E(ersions of Y)-.15 E (acc.)-1 E/F1 10/Times-Bold@0 SF(Section 1: Basic Speci\214cations)72 602.4 Q F0 .27(As we noted abo)97 618 R -.15(ve)-.15 G 2.77(,n).15 G .269(ames refer to either tok)-2.77 F .269(ens or nonterminal symbols.) -.1 F -1(Ya)5.269 G .269(cc requires those names)1 F .26 (which will be used as tok)72 630 R .26 (en names to be declared as such.)-.1 F .261 (In addition, for reasons which will be discussed)5.261 F .346 (in Section 3, it is usually desirable to include the le)72 642 R .346 (xical analyzer as part of the speci\214cation \214le; it may be)-.15 F .102(useful to include other programs as well.)72 654 R .102(Thus, e) 5.102 F -.15(ve)-.25 G .102 (ry speci\214cation \214le consists of three sections: the).15 F/F2 10 /Times-Italic@0 SF(decla-)2.602 E -.15(ra)72 666 S .089(tions, \(gr).15 F .089(ammar\) rules,)-.15 F F0(and)2.589 E F2(pr)2.589 E -.1(og)-.45 G -.15(ra).1 G(ms.).15 E F0 .088 (The sections are separated by double percent `)5.089 F(`%%')-.74 E 2.588('m)-.74 G 2.588(arks. \(The)-2.588 F(per)72 678 Q(-cent `)-.2 E (`%')-.74 E 2.5('i)-.74 G 2.5(sg)-2.5 G(enerally used in Y)-2.5 E (acc speci\214cations as an escape character)-1 E(.\))-.55 E(In other w) 97 693.6 Q(ords, a full speci\214cation \214le looks lik)-.1 E(e)-.1 E EP %%Page: 3 4 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893389>278 60 S(declarations)108 108 Q(%%)108 120 Q(rules)108 132 Q(%%)108 144 Q(programs)108 156 Q .209 (The declaration section may be empty)97 177.6 R 5.209(.M)-.65 G(oreo) -5.209 E -.15(ve)-.15 G 1.009 -.4(r, i).15 H 2.709(ft).4 G .21 (he programs section is omitted, the second %%)-2.709 F (mark may be omitted also; thus, the smallest le)72 189.6 Q -.05(ga)-.15 G 2.5(lY).05 G(acc speci\214cation is)-3.5 E(%%)108 207.6 Q(rules)108 219.6 Q .713(Blanks, tabs, and ne)97 241.2 R .713(wlines are ignored e) -.25 F .713(xcept that the)-.15 F 3.213(ym)-.15 G .712 (ay not appear in names or multi-character)-3.213 F(reserv)72 253.2 Q .245(ed symbols.)-.15 F .245(Comments may appear where)5.245 F -.15(ve) -.25 G 2.745(ran).15 G .245(ame or operator is le)-2.745 F -.05(ga)-.15 G .245(l; the).05 F 2.745(ya)-.15 G .246(re enclosed in /* . . .)-2.745 F(*/, as in C and PL/I.)72 265.2 Q (The rules section is made up of one or more grammar rules.)97 280.8 Q 2.5(Ag)5 G(rammar rule has the form:)-2.5 E 5(A:B)108 298.8 S(OD)-5 E 5 (Y;)-.55 G 3.709(Ar)72 316.8 S 1.208 (epresents a nonterminal name, and BOD)-3.709 F 3.708(Yr)-.55 G 1.208 (epresents a sequence of zero or more names and literals.)-3.708 F (Notice that the colon and the semicolon are Y)72 328.8 Q (acc punctuation.)-1 E .243 (Names may be of arbitrary length, and may be made up of letters, dot `) 97 344.4 R(`.)-.74 E -.74('')-.7 G 2.744(,u).74 G .244(nderscore `) -2.744 F .4 LW 457.322 346.9 452.322 346.9 DL 5(`')448.992 344.4 S .244 (', and non-)-5.74 F .572(initial digits.)72 356.4 R .572(Notice that Y) 5.572 F .571(acc considers that upper and lo)-1 F .571 (wer case letters are distinct.)-.25 F .571(The names used in)5.571 F (the body of a grammar rule may represent tok)72 368.4 Q (ens or nonterminal symbols.)-.1 E 3.204(Al)97 384 S .704 (iteral consists of a character enclosed in single quotes `)-3.204 F (`\264')-.74 E 3.204('. As)-.74 F .704(in C, the backslash `)3.204 F (`\\')-.74 E 3.205('i)-.74 G 3.205(sa)-3.205 G 3.205(ne)-3.205 G(s-) -3.205 E (cape character within literals, and all the C escapes are recognized.) 72 396 Q(Thus)5 E 8.06(\264\\n\264 represents)108 414 R(ne)2.5 E(wline) -.25 E 9.73(\264\\r\264 represents)108 426 R(return)2.5 E 9.73 (\264\\\264\264 represents)108 438 R(single quote `)2.5 E(`\264')-.74 E (')-.74 E 10.28(\264\\\\\264 represents)108 450 R(backslash `)2.5 E (`\\')-.74 E(')-.74 E 10.28(\264\\t\264 represents)108 462 R(tab)2.5 E 8.06(\264\\b\264 represents)108 474 R(backspace)2.5 E (\264\\xxx\264 represents `)108 486 Q(`xxx')-.74 E 2.5('i)-.74 G 2.5(no) -2.5 G(ctal)-2.5 E -.15(Fo)72 504 S 2.5(ran).15 G(umber of technical re\ asons, the nul character \(\264\\0\264 or 000\) should ne)-2.5 E -.15 (ve)-.25 G 2.5(rb).15 G 2.5(eu)-2.5 G(sed in grammar rules.)-2.5 E .903 (If there are se)97 519.6 R -.15(ve)-.25 G .903 (ral grammar rules with the same left hand side, the v).15 F .902 (ertical bar `)-.15 F(`|')-.74 E 3.402('c)-.74 G .902(an be used to) -3.402 F -.2(avo)72 531.6 S .623(id re).2 F .623 (writing the left hand side.)-.25 F .623(In addition, the semicolon at \ the end of a rule can be dropped before a)5.623 F -.15(ve)72 543.6 S (rtical bar).15 E 5(.T)-.55 G(hus the grammar rules)-5 E 2.5(A:BCD ;)108 561.6 S 2.5(A:EF ;)108 573.6 S 2.5(A:G ;)108 585.6 S(can be gi)72 603.6 Q -.15(ve)-.25 G 2.5(nt).15 G 2.5(oY)-2.5 G(acc as)-3.5 E 5 2.5(A: BCD|) 108 621.6 T 2.5(EF|)133 633.6 S 2.5(G;)133 645.6 S .446(It is not neces\ sary that all grammar rules with the same left side appear together in \ the grammar rules sec-)72 663.6 R(tion, although it mak)72 675.6 Q (es the input much more readable, and easy to change.)-.1 E(If a nonter\ minal symbol matches the empty string, this can be indicated in the ob) 97 691.2 Q(vious w)-.15 E(ay:)-.1 E(empty :)108 709.2 Q(;)7.5 E EP %%Page: 4 5 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893489>278 60 S .394 (As we mentioned abo)97 108 R -.15(ve)-.15 G 2.894(,n).15 G .394 (ames which represent tok)-2.894 F .394(ens must be declared as such.) -.1 F .394(The simplest w)5.394 F(ay)-.1 E(of doing this is to write)72 120 Q(%tok)108 138 Q 5(en name1)-.1 F(name2 . . .)2.5 E .702 (in the declarations section.)72 156 R .702 (\(See Sections 3 and 4 for much more discussion\).)5.702 F(Ev)5.702 E .701(ery name not de\214ned in)-.15 F .66 (the declarations section is assumed to represent a nonterminal symbol.) 72 168 R .661(If, by the end of the rules section,)5.661 F .634 (some nonterminal symbol has not appeared on the left of an)72 180 R 3.133(yr)-.15 G .633(ule, then an error message is produced and)-3.133 F -1(Ya)72 192 S(cc halts.)1 E .274(The left hand side of the)97 207.6 R /F1 10/Times-Italic@0 SF<8c72>2.774 E(st)-.1 E F0 .275(grammar rule in \ the grammar rules section has special importance; it is)2.774 F(tak)72 219.6 Q .045(en to be the controlling nonterminal symbol for the entire\ input process; in technical language it is called)-.1 F(the)72 231.6 Q F1 .282(start symbol.)2.782 F F0 .282(In ef)5.282 F .282(fect, the pars\ er is designed to recognize the start symbol; thus, this symbol general\ ly)-.25 F(represents the lar)72 243.6 Q (gest, most general structure described by the grammar rules.)-.18 E .267(The end of the input is signaled by a special tok)97 259.2 R .266 (en, called the)-.1 F F1(endmark)2.766 E(er)-.1 E(.)-1.11 E F0 .266 (If the tok)5.266 F .266(ens up to, b)-.1 F .266(ut not)-.2 F .496 (including, the endmark)72 271.2 R .497(er form a structure which match\ es the start symbol, the parser subroutine returns to)-.1 F .103 (its caller when the endmark)72 283.2 R .103(er is seen; we say that it) -.1 F F1(accepts)2.603 E F0 .103(the input.)2.603 F .103(If the endmark) 5.103 F .103(er is seen in an)-.1 F 2.602(yo)-.15 G(ther)-2.602 E(conte) 72 295.2 Q(xt, it is an error)-.15 E(.)-.55 E .579 (It is the job of the user supplied le)97 310.8 R .58 (xical analyzer to return the endmark)-.15 F .58 (er when appropriate; see sec-)-.1 F 1.533(tion 3, belo)72 322.8 R 5.333 -.65(w. F)-.25 H(requently).65 E 4.033(,t)-.65 G 1.533(he endmark)-4.033 F 1.533(er tok)-.1 F 1.533(en represents some reasonably ob)-.1 F 1.533 (vious I/O status, such as)-.15 F -.74(``)72 334.8 S(end-of-\214le').74 E 2.5('o)-.74 G 2.5(r`)-2.5 G(`end-of-record')-3.24 E('.)-.74 E/F2 10 /Times-Bold@0 SF(Section 2: Actions)72 358.8 Q F0 2.055 -.8(To e)97 374.4 T .455(ach grammar rule, the user may associate an action to be p\ erformed each time the rule is recog-).8 F .358 (nized in the input process.)72 386.4 R .357(This action may return a v) 5.357 F .357(alue, and may obtain the v)-.25 F .357 (alues returned by pre)-.25 F(vious)-.25 E(actions in the grammar rule.) 72 398.4 Q(In addition, the le)5 E(xical analyzer can return v)-.15 E (alues for tok)-.25 E(ens, if desired.)-.1 E 1.142(When in)97 414 R -.2 (vo)-.4 G 1.142(king Y).2 F 1.143 (acc, the user speci\214es a programming language; currently)-1 F 3.643 (,R)-.65 G 1.143(atfor and C are sup-)-3.643 F 2.916(ported. An)72 426 R .415(action is an arbitrary statement in this language, and as such can\ do input and output, call sub-)2.916 F .897(programs, and alter e)72 438 R .897(xternal v)-.15 F .897(ectors and v)-.15 F .897 (ariables \(recall that a `)-.25 F(`statement')-.74 E 3.397('i)-.74 G 3.397(nb)-3.397 G .897(oth C and Ratfor can be)-3.397 F .542 (compound and do man)72 450 R 3.042(yd)-.15 G .542(istinct tasks\).) -3.042 F .542(An action is speci\214ed by an equal sign `)5.542 F(`=') -.74 E 3.041('a)-.74 G 3.041(tt)-3.041 G .541(he end of a gram-)-3.041 F (mar rule, follo)72 462 Q (wed by one or more statements, enclosed in curly braces `)-.25 E(`{') -.74 E 2.5('a)-.74 G(nd `)-2.5 E(`}')-.74 E 2.5('. F)-.74 F(or e)-.15 E (xample,)-.15 E(A: \264\(\264 B \264\)\264 = { hello\( 1, "abc" \);)108 480 Q(})5 E(and)72 498 Q(XXX: YYY ZZZ =)108 516 Q({)133 528 Q (printf\("a message\\n"\);)158 540 Q(\215ag = 25;)158 552 Q(})133 564 Q .039(are grammar rules with actions in C.)72 582 R 2.539(Ag)5.039 G .039 (rammar rule with an action need not end with a semicolon; in f)-2.539 F (act,)-.1 E(it is an error to ha)72 594 Q .3 -.15(ve a s)-.2 H (emicolon before the equal sign.).15 E 1.704 -.8(To f)97 609.6 T .104 (acilitate easy communication between the actions and the parser).7 F 2.603(,t)-.4 G .103(he action statements are altered)-2.603 F(slightly) 72 621.6 Q 5(.T)-.65 G(he symbol `)-5 E(`dollar sign')-.74 E 2.5('`)-.74 G(`$')-3.24 E 2.5('i)-.74 G 2.5(su)-2.5 G(sed as a signal to Y)-2.5 E (acc in this conte)-1 E(xt.)-.15 E 2.208 -.8(To r)97 637.2 T .608 (eturn a v).8 F .608(alue, the action normally sets the pseudo-v)-.25 F .608(ariable `)-.25 F(`$$')-.74 E 3.108('t)-.74 G 3.108(os)-3.108 G .608 (ome inte)-3.108 F .608(ger v)-.15 F 3.109(alue. F)-.25 F .609(or e)-.15 F(x-)-.15 E(ample, an action which does nothing b)72 649.2 Q (ut return the v)-.2 E(alue 1 is)-.25 E 2.5(={$)108 667.2 S 2.5($=1)-2.5 G 2.5(;})-2.5 G 1.766 -.8(To o)97 688.8 T .166(btain the v).8 F .166 (alues returned by pre)-.25 F .166(vious actions and the le)-.25 F .166 (xical analyzer)-.15 F 2.666(,t)-.4 G .166(he action may use the \(in-) -2.666 F(te)72 700.8 Q .567(ger\) pseudo-v)-.15 F .568 (ariables $1, $2, . . ., which refer to the v)-.25 F .568 (alues returned by the components of the right side)-.25 F (of a rule, reading from left to right.)72 712.8 Q(Thus, if the rule is) 5 E EP %%Page: 5 6 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893589>278 60 S(A: B C D ;)108 108 Q(for e)72 126 Q(xample, then $2 has the v)-.15 E (alue returned by C, and $3 the v)-.25 E(alue returned by D.)-.25 E (As a more concrete e)97 141.6 Q(xample, we might ha)-.15 E .3 -.15 (ve t)-.2 H(he rule).15 E -.15(ex)108 159.6 S(pression: \264\(\264 e).15 E(xpression \264\)\264 ;)-.15 E 1.6 -.8(We w)72 177.6 T(ish the v).8 E (alue returned by this rule to be the v)-.25 E(alue of the e)-.25 E (xpression in parentheses.)-.15 E(Then we write)5 E -.15(ex)108 195.6 S (pression: \264\(\264 e).15 E(xpression \264\)\264)-.15 E 2.5(={$)10 G 2.5($=$)-2.5 G 2.5(2;})-2.5 G .209(As a def)97 217.2 R .209(ault, the v) -.1 F .209(alue of a rule is the v)-.25 F .209 (alue of the \214rst element in it \($1\).)-.25 F .208(This is true e) 5.209 F -.15(ve)-.25 G 2.708(ni).15 G 2.708(ft)-2.708 G .208(here is) -2.708 F(no e)72 229.2 Q(xplicit action gi)-.15 E -.15(ve)-.25 G 2.5(nf) .15 G(or the rule.)-2.5 E(Thus, grammar rules of the form)5 E(A: B ;)108 247.2 Q(frequently need not ha)72 265.2 Q .3 -.15(ve a)-.2 H 2.5(ne).15 G(xplict action.)-2.65 E .17(Notice that, although the v)97 280.8 R .17 (alues of actions are inte)-.25 F .17(gers, these inte)-.15 F .17 (gers may in f)-.15 F .17(act contain pointers \(in)-.1 F 1.232 (C\) or indices into an array \(in Ratfor\); in this w)72 292.8 R(ay)-.1 E 3.732(,a)-.65 G 1.231(ctions can return and reference more comple) -3.732 F 3.731(xd)-.15 G(ata)-3.731 E(structures.)72 304.8 Q 1.256(Some\ times, we wish to get control before a rule is fully parsed, as well as\ at the end of the rule.)97 320.4 R .76(There is no e)72 332.4 R .76 (xplicit mechanism in Y)-.15 F .76(acc to allo)-1 F 3.259(wt)-.25 G .759 (his; the same ef)-3.259 F .759(fect can be obtained, ho)-.25 F(we)-.25 E -.15(ve)-.25 G 1.559 -.4(r, b).15 H 3.259(yi).4 G(ntro-)-3.259 E .577 (ducing a ne)72 344.4 R 3.077(ws)-.25 G .577(ymbol which matches the em\ pty string, and inserting an action for this symbol.)-3.077 F -.15(Fo) 5.577 G 3.078(re).15 G(xam-)-3.228 E(ple, we might ha)72 356.4 Q .3 -.15 (ve a r)-.2 H(ule describing an `).15 E -1.95(`if ')-.74 F 2.5('s)-.74 G (tatement:)-2.5 E(statement: IF \264\(\264 e)108 374.4 Q (xpr \264\)\264 THEN statement)-.15 E 1.054(Suppose that we wish to get\ control after seeing the right parenthesis in order to output some cod\ e.)72 392.4 R -.8(We)6.053 G(might accomplish this by the rules:)72 404.4 Q 2.5(statement: IF)108 422.4 R2.5 E (xpr \264\)\264 actn THEN statement)-.15 E 2.5(={c)133 434.4 S (all action1 })-2.5 E 5(actn: /*)108 458.4 R (matches the empty string */)2.5 E 2.5(={c)133 470.4 S(all action2 }) -2.5 E 1.137(Thus, the ne)97 492 R 3.637(wn)-.25 G 1.137 (onterminal symbol actn matches no input, b)-3.637 F 1.138(ut serv)-.2 F 1.138(es only to call action2 after the)-.15 F (right parenthesis is seen.)72 504 Q(Frequently)97 519.6 Q 3.485(,i)-.65 G 3.485(ti)-3.485 G 3.485(sm)-3.485 G .984(ore natural in such cases to\ break the rule into parts where the action is needed.)-3.485 F (Thus, the abo)72 531.6 Q .3 -.15(ve ex)-.15 H(ample might also ha).15 E .3 -.15(ve b)-.2 H(een written).15 E 2.5(statement: ifpart)108 549.6 R (THEN statement)2.5 E 2.5(={c)133 561.6 S(all action1 })-2.5 E 12.5 (ifpart: IF)108 585.6 R2.5 E(xpr \264\)\264)-.15 E 2.5(={c) 133 597.6 S(all action2 })-2.5 E 1.166(In man)97 619.2 R 3.666(ya)-.15 G 1.166(pplications, output is not done directly by the actions; rather) -3.666 F 3.667(,ad)-.4 G 1.167(ata structure, such as a)-3.667 F .146 (parse tree, is constructed in memory)72 631.2 R 2.646(,a)-.65 G .145 (nd transformations are applied to it before output is generated.)-2.646 F -.15(Pa)5.145 G(rse).15 E .716 (trees are particularly easy to construct, gi)72 643.2 R -.15(ve)-.25 G 3.216(nr).15 G .716(outines which b)-3.216 F .716 (uild and maintain the tree structure desired.)-.2 F -.15(Fo)72 655.2 S 2.5(re).15 G(xample, suppose we ha)-2.65 E .3 -.15(ve a C f)-.2 H (unction `).15 E(`node')-.74 E(', written so that the call)-.74 E (node\( L, n1, n2 \))108 673.2 Q .913(creates a node with label L, and \ descendants n1 and n2, and returns a pointer to the ne)72 691.2 R .913 (wly created node.)-.25 F(Then we can cause a parse tree to be b)72 703.2 Q(uilt by supplying actions such as:)-.2 E EP %%Page: 6 7 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893689>278 60 S -.15(ex)108 108 S (pr: e).15 E(xpr \264+\264 e)-.15 E(xpr)-.15 E 2.5(={$)133 120 S 2.5 ($=n)-2.5 G(ode\( \264+\264, $1, $3 \); })-2.5 E (in our speci\214cation.)72 138 Q .735(The user may de\214ne other v)97 153.6 R .736(ariables to be used by the actions.)-.25 F .736 (Declarations and de\214nitions can ap-)5.736 F .007(pear in tw)72 165.6 R 2.507(op)-.1 G .007(laces in the Y)-2.507 F .007(acc speci\214cation:\ in the declarations section, and at the head of the rules sections,)-1 F 1.676(before the \214rst grammar rule.)72 177.6 R 1.676(In each case,\ the declarations and de\214nitions are enclosed in the marks)6.676 F -.74(``)72 189.6 S(%{').74 E 3.53('a)-.74 G 1.03(nd `)-3.53 F(`%}')-.74 E 3.53('. Declarations)-.74 F 1.03 (and de\214nitions placed in the declarations section ha)3.53 F 1.33 -.15(ve g)-.2 H 1.03(lobal scope, and).15 F .328(are thus kno)72 201.6 R .328(wn to the action statements and the le)-.25 F .328(xical analyzer) -.15 F 5.328(.D)-.55 G .328(eclarations and de\214nitions placed at the) -5.328 F .561(head of the rules section ha)72 213.6 R .861 -.15(ve s)-.2 H .561(cope local to the action statements.).15 F .56(Thus, in the abo) 5.56 F .86 -.15(ve ex)-.15 H .56(ample, we might).15 F(ha)72 225.6 Q .3 -.15(ve i)-.2 H(ncluded).15 E(%{ int v)108 243.6 Q(ariable 0; %})-.25 E (in the declarations section, or)72 261.6 Q 2.5(,p)-.4 G(erhaps,)-2.5 E (%{ static int v)108 279.6 Q(ariable; %})-.25 E .582 (at the head of the rules section.)72 297.6 R .582 (If we were writing Ratfor actions, we might w)5.582 F .582 (ant to include some COM-)-.1 F .067(MON statements at the be)72 309.6 R .067(ginning of the rules section, to allo)-.15 F 2.567(wf)-.25 G .067 (or easy communication between the actions)-2.567 F .377 (and other routines.)72 321.6 R -.15(Fo)5.377 G 2.877(rb).15 G .377 (oth C and Ratfor)-2.877 F 2.877(,Y)-.4 G .377(acc has used only e) -3.877 F .377(xternal names be)-.15 F .378(ginning in `)-.15 F(`yy')-.74 E .378('; the user)-.74 F(should a)72 333.6 Q -.2(vo)-.2 G (id such names.).2 E/F1 10/Times-Bold@0 SF(Section 3: Lexical Analysis) 72 357.6 Q F0 .136(The user must supply a le)97 373.2 R .136 (xical analyzer which reads the input stream and communicates tok)-.15 F .136(ens \(with)-.1 F -.25(va)72 385.2 S .662 (lues, if desired\) to the parser).25 F 5.662(.T)-.55 G .662(he le) -5.662 F .662(xical analyzer is an inte)-.15 F .662(ger v)-.15 F .662 (alued function called yyle)-.25 F .663(x, in both C)-.15 F .268 (and Ratfor)72 397.2 R 5.268(.T)-.55 G .268(he function returns an inte) -5.268 F .267(ger which represents the type of the tok)-.15 F 2.767 (en. The)-.1 F -.25(va)2.767 G .267(lue to be associ-).25 F .273 (ated in the parser with that tok)72 409.2 R .273 (en is assigned to the inte)-.1 F .273(ger v)-.15 F .274(ariable yylv) -.25 F 2.774(al. Thus,)-.25 F 2.774(al)2.774 G -.15(ex)-2.774 G .274 (ical analyzer written).15 F(in C should be)72 421.2 Q(gin)-.15 E(yyle) 108 439.2 Q 2.5(x\(\){)-.15 G -.15(ex)133 451.2 S(tern int yylv).15 E (al;)-.25 E 2.5(...)133 463.2 S(while a le)72 481.2 Q (xical analyzer written in Ratfor should be)-.15 E(gin)-.15 E(inte)108 499.2 Q(ger function yyle)-.15 E(x\(yylv)-.15 E(al\))-.25 E(inte)133 511.2 Q(ger yylv)-.15 E(al)-.25 E 2.5(...)133 523.2 S(Clearly)97 544.8 Q 2.907(,t)-.65 G .407(he parser and the le)-2.907 F .407 (xical analyzer must agree on the type numbers in order for communica-) -.15 F .519(tion between them to tak)72 556.8 R 3.019(ep)-.1 G 3.019 (lace. These)-3.019 F .519(numbers may be chosen by Y)3.019 F .519 (acc, or chosen by the user)-1 F 5.519(.I)-.55 G 3.019(ne)-5.519 G (ither)-3.019 E .453(case, the `)72 568.8 R(`de\214ne')-.74 E 2.953('m) -.74 G .453(echanisms of C and Ratfor are used to allo)-2.953 F 2.953 (wt)-.25 G .453(he le)-2.953 F .452(xical analyzer to return these num-) -.15 F .763(bers symbolically)72 580.8 R 5.763(.F)-.65 G .763(or e) -5.913 F .763(xample, suppose that the tok)-.15 F .764 (en name DIGIT has been de\214ned in the declarations)-.1 F (section of the speci\214cation.)72 592.8 Q(The rele)5 E -.25(va)-.25 G (nt portion of the le).25 E(xical analyzer \(in C\) might look lik)-.15 E(e:)-.1 E EP %%Page: 7 8 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893789>278 60 S(yyle)108 108 Q (x\( \) {)-.15 E -.15(ex)133 120 S(tern int yylv).15 E(al;)-.25 E (int c;)133 132 Q 2.5(...)133 144 S 2.5(c=g)133 156 S(etchar\( \);)-2.5 E 2.5(...)133 168 S(if\( c >= \2640\264 && c <= \2649\264 \) {)133 180 Q (yylv)158 192 Q(al = c\255\2640\264;)-.25 E(return\(DIGIT\);)158 204 Q (})133 216 Q 2.5(...)133 228 S(The rele)97 249.6 Q -.25(va)-.25 G (nt portion of the Ratfor le).25 E(xical analyzer might look lik)-.15 E (e:)-.1 E(inte)108 267.6 Q(ger function yyle)-.15 E(x\(yylv)-.15 E(al\)) -.25 E(inte)133 279.6 Q(ger yylv)-.15 E(al, digits\(10\), c)-.25 E 2.5 (...)133 291.6 S(data digits\(1\) / "0" /;)133 303.6 Q (data digits\(2\) / "1" /;)133 315.6 Q 2.5(...)133 327.6 S (data digits\(10\) / "9" /;)133 339.6 Q 2.5(...)133 351.6 S 7.5(#s)108 363.6 S(et c to the ne)-7.5 E(xt input character)-.15 E 2.5(...)133 375.6 S(do i = 1, 10 {)133 387.6 Q(if\(c .EQ. digits\(i\)\) {)158 399.6 Q(yylv)183 411.6 Q(al = i\2551)-.25 E(yyle)183 423.6 Q 2.5(x=D)-.15 G (IGIT)-2.5 E(return)183 435.6 Q(})158 447.6 Q(})133 459.6 Q 2.5(...)133 471.6 S .477(In both cases, the intent is to return a tok)97 493.2 R .476(en type of DIGIT)-.1 F 2.976(,a)-.74 G .476(nd a v)-2.976 F .476 (alue equal to the numerical v)-.25 F(alue)-.25 E .629(of the digit.)72 505.2 R(Pro)5.629 E .629(vided that the le)-.15 F .63(xical analyzer co\ de is placed in the programs section of the speci\214cation,)-.15 F .368 (the identi\214er DIGIT will be rede\214ned to be equal to the type num\ ber associated with the tok)72 517.2 R .367(en name DIG-)-.1 F(IT)72 529.2 Q(.)-.74 E .059 (This mechanism leads to clear and easily modi\214ed le)97 544.8 R .059 (xical analyzers; the only pitf)-.15 F .059(all is that it mak)-.1 F .059(es it)-.1 F 1.16(important to a)72 556.8 R -.2(vo)-.2 G 1.16 (id using an).2 F 3.66(yn)-.15 G 1.159 (ames in the grammar which are reserv)-3.66 F 1.159 (ed or signi\214cant in the chosen lan-)-.15 F .007 (guage; thus, in both C and Ratfor)72 568.8 R 2.507(,t)-.4 G .007 (he use of tok)-2.507 F .007(en names of `)-.1 F -1.95(`if ')-.74 F 2.507('o)-.74 G 2.507(r`)-2.507 G(`yyle)-3.247 E(x')-.15 E 2.507('w)-.74 G .007(ill almost certainly cause se-)-2.507 F -.15(ve)72 580.8 S .589 (re dif).15 F .588(\214culties when the le)-.25 F .588 (xical analyzer is compiled.)-.15 F .588(The tok)5.588 F .588(en name `) -.1 F(`error')-.74 E 3.088('i)-.74 G 3.088(sr)-3.088 G(eserv)-3.088 E .588(ed for error han-)-.15 F(dling, and should not be used nai)72 592.8 Q -.15(ve)-.25 G(ly \(see Section 5\).).15 E .702(As mentioned abo)97 608.4 R -.15(ve)-.15 G 3.202(,t).15 G .702 (he type numbers may be chosen by Y)-3.202 F .702(acc or by the user)-1 F 5.703(.I)-.55 G 3.203(nt)-5.703 G .703(he def)-3.203 F .703 (ault situa-)-.1 F .023(tion, the numbers are chosen by Y)72 620.4 R 2.523(acc. The)-1 F(def)2.523 E .023 (ault type number for a literal character is the numerical v)-.1 F(alue) -.25 E .815(of the character)72 632.4 R 3.315(,c)-.4 G .815 (onsidered as a 1 byte inte)-3.315 F(ger)-.15 E 5.815(.O)-.55 G .815 (ther tok)-5.815 F .816(en names are assigned type numbers starting at) -.1 F 2.587(257. It)72 644.4 R .087(is a dif)2.587 F .087 (\214cult, machine dependent operation to determine the numerical v)-.25 F .086(alue of an input character in)-.25 F .635(Ratfor \(or F)72 656.4 R 3.135(ortran\). Thus,)-.15 F .635(the Ratfor user of Y)3.135 F .635 (acc will probably wish to set his o)-1 F .636(wn type numbers, or not) -.25 F(use an)72 668.4 Q 2.5(yl)-.15 G(iterals in his speci\214cation.) -2.5 E 1.674 -.8(To a)97 684 T .074(ssign a type number to a tok).8 F .074(en \(including literals\), the \214rst appearance of the tok)-.1 F .073(en name or liter)-.1 F(-)-.2 E(al)72 696 Q/F1 10/Times-Italic@0 SF .597(in the declar)3.097 F .597(ations section)-.15 F F0 .597 (can be immediately follo)3.097 F .598(wed by a nonne)-.25 F -.05(ga) -.15 G(ti).05 E .898 -.15(ve i)-.25 H(nte).15 E(ger)-.15 E 5.598(.T)-.55 G .598(his inte)-5.598 F .598(ger is tak)-.15 F(en)-.1 E .299 (to be the type number of the name or literal.)72 708 R .298 (Names and literals not de\214ned by this mechanism retain their)5.298 F (def)72 720 Q(ault de\214nition.)-.1 E (It is important that all type numbers be distinct.)5 E EP %%Page: 8 9 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893889>278 60 S .492 (There is one e)97 108 R .492(xception to this situation.)-.15 F -.15 (Fo)5.493 G 2.993(rs).15 G(tick)-2.993 E 2.993(yh)-.15 G .493 (istorical reasons, the endmark)-2.993 F .493(er must ha)-.1 F .793 -.15 (ve t)-.2 H(ype).15 E .064(number 0.)72 120 R .064 (Note that this is not unattracti)5.064 F .364 -.15(ve i)-.25 H 2.564 (nC).15 G 2.564(,s)-2.564 G .064 (ince the nul character is returned upon end of \214le; in Rat-)-2.564 F (for)72 132 Q 2.774(,i)-.4 G 2.774(tm)-2.774 G(ak)-2.774 E .274 (es no sense.)-.1 F .275 (This type number cannot be rede\214ned by the user; thus, all le)5.274 F .275(xical analyzers should)-.15 F(be prepared to return 0 as a type \ number upon reaching the end of their input.)72 144 Q/F1 10/Times-Bold@0 SF(Section 4: Ambiguity)72 168 Q 2.5(,C)-.55 G(on\215icts, and Pr)-2.5 E (ecedence)-.18 E F0 3.067(As)97 183.6 S .567(et of grammar rules is) -3.067 F/F2 10/Times-Italic@0 SF(ambiguous)3.067 E F0 .566 (if there is some input string which can be structured in tw)3.066 F 3.066(oo)-.1 G(r)-3.066 E(more dif)72 195.6 Q(ferent w)-.25 E 2.5 (ays. F)-.1 F(or e)-.15 E(xample, the grammar rule)-.15 E -.15(ex)108 213.6 S(pr :).15 E -.15(ex)5 G<707220b4adb42065>.15 E(xpr ;)-.15 E .333 (is a natural w)72 231.6 R .333(ay of e)-.1 F .333(xpressing the f)-.15 F .333(act that one w)-.1 F .333(ay of forming an arithmetic e)-.1 F .333(xpression is to put tw)-.15 F 2.833(oo)-.1 G(ther)-2.833 E -.15(ex) 72 243.6 S .065(pressions together with a minus sign between them.).15 F (Unfortunately)5.065 E 2.565(,t)-.65 G .065 (his grammar rule does not complete-)-2.565 F(ly specify the w)72 255.6 Q(ay that all comple)-.1 E 2.5(xi)-.15 G(nputs should be structured.) -2.5 E -.15(Fo)5 G 2.5(re).15 G(xample, if we ha)-2.65 E .3 -.15(ve i) -.2 H(nput of the form).15 E -.15(ex)108 273.6 S(pr \255 e).15 E (xpr \255 e)-.15 E(xpr)-.15 E(the rule w)72 291.6 Q (ould permit us to treat this input either as)-.1 E 2.5(\(e)108 309.6 S (xpr \255 e)-2.65 E(xpr \) \255 e)-.15 E(xpr)-.15 E(or as)72 327.6 Q -.15(ex)108 345.6 S(pr \255 \( e).15 E(xpr \255 e)-.15 E(xpr \))-.15 E (\(W)72 363.6 Q 2.5(es)-.8 G(peak of the \214rst as)-2.5 E F2 (left association)2.5 E F0(of operators, and the second as)2.5 E F2 (right association\).)2.5 E F0 -1(Ya)97 379.2 S .782 (cc detects such ambiguities when it is attempting to b)1 F .783 (uild the parser)-.2 F 5.783(.I)-.55 G 3.283(ti)-5.783 G 3.283(si)-3.283 G(nstructi)-3.283 E 1.083 -.15(ve t)-.25 H 3.283(oc).15 G(onsider)-3.283 E(the problem that confronts the parser when it is gi)72 391.2 Q -.15 (ve)-.25 G 2.5(na).15 G 2.5(ni)-2.5 G(nput such as)-2.5 E -.15(ex)108 409.2 S(pr \255 e).15 E(xpr \255 e)-.15 E(xpr)-.15 E (When the parser has read the second e)72 427.2 Q(xpr)-.15 E 2.5(,t)-.4 G(he input which it has seen:)-2.5 E -.15(ex)108 445.2 S(pr \255 e).15 E (xpr)-.15 E .077(matches the right side of the grammar rule abo)72 463.2 R -.15(ve)-.15 G 5.076(.O).15 G .076(ne v)-5.076 F .076 (alid thing for the parser to do is to)-.25 F F2 -.37(re)2.576 G(duce) .37 E F0 .076(the input)2.576 F .167 (it has seen by applying this rule; after applying the rule, it w)72 475.2 R .168(ould ha)-.1 F .468 -.15(ve r)-.2 H .168 (educed the input it had already seen).15 F(to e)72 487.2 Q (xpr \(the left side of the rule\).)-.15 E (It could then read the \214nal part of the input:)5 E 2.5108 505.2 S(xpr)-2.65 E(and ag)72 523.2 Q(ain reduce by the rule.)-.05 E 1.6 -.8(We s)5 H(ee that the ef).8 E(fect of this is to tak)-.25 E 2.5(et) -.1 G(he left associati)-2.5 E .3 -.15(ve i)-.25 H(nterpretation.).15 E (Alternati)97 538.8 Q -.15(ve)-.25 G(ly).15 E 2.5(,w)-.65 G (hen the parser has seen)-2.5 E -.15(ex)108 556.8 S(pr \255 e).15 E(xpr) -.15 E .154(it could defer the immediate application of the rule, and c\ ontinue reading \(the technical term is)72 574.8 R F2(shifting\))2.654 E F0(the)2.654 E(input until it had seen)72 586.8 Q -.15(ex)108 604.8 S (pr \255 e).15 E(xpr \255 e)-.15 E(xpr)-.15 E(It could then apply the g\ rammar rule to the rightmost three symbols, reducing them to e)72 622.8 Q(xpr and lea)-.15 E(ving)-.2 E -.15(ex)108 640.8 S(pr \255 e).15 E(xpr) -.15 E(No)72 658.8 Q 3.101(wi)-.25 G 3.101(tc)-3.101 G .601 (an reduce by the rule ag)-3.101 F .602(ain; the ef)-.05 F .602 (fect is to tak)-.25 F 3.102(et)-.1 G .602(he right associati)-3.102 F .902 -.15(ve i)-.25 H 3.102(nterpretation. Thus,).15 F(ha)3.102 E(ving) -.2 E(read)72 670.8 Q -.15(ex)108 688.8 S(pr \255 e).15 E(xpr)-.15 E .144(the parser can do tw)72 706.8 R 2.644(ol)-.1 G -2.25 -.15(eg a) -2.644 H 2.644(lt).15 G .144 (hings, a shift or a reduction, and has no w)-2.644 F .144 (ay of deciding between them.)-.1 F 1.743 -.8(We r)5.143 H(e-).8 E .193 (fer to this as a)72 718.8 R F2(shift/r)2.693 E .193(educe con\215ict.) -.37 F F0 .193(It may also happen that the parser has a choice of tw) 5.193 F 2.693(ol)-.1 G -2.25 -.15(eg a)-2.693 H 2.693(lr).15 G (eductions;)-2.693 E(this is called a)72 730.8 Q F2 -.37(re)2.5 G (duce/r).37 E(educe con\215ict.)-.37 E EP %%Page: 9 10 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<893989>278 60 S .837 (When there are shift/reduce or reduce/reduce con\215icts, Y)97 108 R .837(acc still produces a parser)-1 F 5.836(.I)-.55 G 3.336(td)-5.836 G .836(oes this by)-3.336 F .198(selecting one of the v)72 120 R .198 (alid steps where)-.25 F -.15(ve)-.25 G 2.698(ri).15 G 2.698(th)-2.698 G .198(as a choice.)-2.698 F 2.698(Ar)5.198 G .198 (ule which describes which choice to mak)-2.698 F 2.698(ei)-.1 G 2.698 (na)-2.698 G(gi)72 132 Q -.15(ve)-.25 G 2.5(ns).15 G (ituation is called a)-2.5 E/F1 10/Times-Italic@0 SF (disambiguating rule)2.5 E(.)-.15 E F0 -1(Ya)97 147.6 S .024(cc has tw)1 F 2.523(od)-.1 G .023(isambiguating rules which are in)-2.523 F -.2(vo) -.4 G -.1(ke).2 G 2.523(db).1 G 2.523(yd)-2.523 G(ef)-2.523 E .023 (ault, in the absence of an)-.1 F 2.523(yu)-.15 G .023(ser directi) -2.523 F -.15(ve)-.25 G(s).15 E(to the contrary:)72 159.6 Q 15(1. In)72 175.2 R 2.5(as)2.5 G(hift/reduce con\215ict, the def)-2.5 E (ault is to do the shift.)-.1 E 15(2. In)72 190.8 R 4.001(ar)4.001 G 1.501(educe/reduce con\215ict, the def)-4.001 F 1.501 (ault is to reduce by the)-.1 F F1(earlier)4.001 E F0 1.502 (grammar rule \(in the input se-)4.001 F(quence\).)97 202.8 Q .019 (Rule 1 implies that reductions are deferred whene)97 218.4 R -.15(ve) -.25 G 2.518(rt).15 G .018(here is a choice, in f)-2.518 F -.2(avo)-.1 G 2.518(ro).2 G 2.518(fs)-2.518 G 2.518(hifts. Rule)-2.518 F 2.518(2g) 2.518 G -2.15 -.25(iv e)-2.518 H(s).25 E .001 (the user rather crude control o)72 230.4 R -.15(ve)-.15 G 2.501(rt).15 G .001(he beha)-2.501 F .002(vior of the parser in this situation, b)-.2 F .002(ut the proper use of reduce/re-)-.2 F(duce con\215icts is still \ a black art, and is properly considered an adv)72 242.4 Q(anced topic.) -.25 E .657(Con\215icts may arise because of mistak)97 258 R .656 (es in input or logic, or because the grammar rules, while con-)-.1 F .932(sistent, require a more comple)72 270 R 3.432(xp)-.15 G .932 (arser than Y)-3.432 F .932(acc can construct.)-1 F .933 (In these cases, the application of disam-)5.933 F .067(biguating rules\ is inappropriate, and leads to a parser which is in error)72 282 R 5.067(.F)-.55 G .067(or this reason, Y)-5.217 F .067(acc al)-1 F -.1(wa) -.1 G .067(ys reports).1 F(the number of shift/reduce and reduce/reduce\ con\215icts which were resolv)72 294 Q(ed by Rule 1 and Rule 2.)-.15 E .152(In general, whene)97 309.6 R -.15(ve)-.25 G 2.652(ri).15 G 2.652 (ti)-2.652 G 2.652(sp)-2.652 G .152 (ossible to apply disambiguating rules to produce a correct parser) -2.652 F 2.653(,i)-.4 G 2.653(ti)-2.653 G 2.653(sa)-2.653 G(lso)-2.653 E .696(possible to re)72 321.6 R .696 (write the grammar rules so that the same inputs are read, b)-.25 F .696 (ut there are no con\215icts.)-.2 F -.15(Fo)5.695 G 3.195(rt).15 G(his) -3.195 E 1.01(reason, most pre)72 333.6 R 1.01(vious systems lik)-.25 F 3.51(eY)-.1 G 1.011(acc ha)-4.51 F 1.311 -.15(ve c)-.2 H 1.011 (onsidered con\215icts to be f).15 F 1.011(atal errors.)-.1 F 1.011 (Our e)6.011 F 1.011(xperience has)-.15 F .169(suggested that this re)72 345.6 R .169(writing is some)-.25 F .169 (what unnatural to do, and produces slo)-.25 F .168 (wer parsers; thus, Y)-.25 F .168(acc will pro-)-1 F(duce parsers e)72 357.6 Q -.15(ve)-.25 G 2.5(ni).15 G 2.5(nt)-2.5 G (he presence of con\215icts.)-2.5 E .646(As an e)97 373.2 R .646 (xample of the po)-.15 F .647(wer of disambiguating rules, consider a f\ ragment from a programming lan-)-.25 F(guage in)72 385.2 Q -.2(vo)-.4 G (lving an `).2 E(`if-then-else')-.74 E 2.5('c)-.74 G(onstruction:)-2.5 E (stat :)108 403.2 Q(IF \264\(\264 cond \264\)\264 stat |)5.83 E (IF \264\(\264 cond \264\)\264 stat ELSE stat ;)133 415.2 Q .078 (Here, we consider IF and ELSE to be tok)72 433.2 R .077 (ens, cond to be a nonterminal symbol describing conditional \(logi-)-.1 F .015(cal\) e)72 445.2 R .015 (xpressions, and stat to be a nonterminal symbol describing statements.) -.15 F .015(In the follo)5.015 F .015(wing, we shall refer)-.25 F (to these tw)72 457.2 Q 2.5(or)-.1 G(ules as the)-2.5 E F1(simple-if)2.5 E F0(rule and the)2.5 E F1(if-else)2.5 E F0(rule, respecti)2.5 E -.15 (ve)-.25 G(ly).15 E(.)-.65 E(These tw)97 472.8 Q 2.5(or)-.1 G (ules form an ambiguous construction, since input of the form)-2.5 E (IF \( C1 \) IF \( C2 \) S1 ELSE S2)108 490.8 Q (can be structured according to these rules in tw)72 508.8 Q 2.5(ow)-.1 G(ays:)-2.6 E(IF \( C1 \) {)108 526.8 Q(IF \( C2 \) S1)133 538.8 Q(})108 550.8 Q(ELSE S2)108 562.8 Q(or)72 580.8 Q(IF \( C1 \) {)108 598.8 Q (IF \( C2 \) S1)133 610.8 Q(ELSE S2)133 622.8 Q(})108 634.8 Q .095 (The second interpretation is the one gi)72 652.8 R -.15(ve)-.25 G 2.595 (ni).15 G 2.595(nm)-2.595 G .095(ost programming languages which ha) -2.595 F .394 -.15(ve t)-.2 H .094(his construct.).15 F(Each)5.094 E .37 (ELSE is associated with the last preceding `)72 664.8 R(`un-ELSE')-.74 E(d')-.5 E 2.87('I)-.74 G 4.47 -.8(F. I)-2.87 H 2.87(nt).8 G .37(his e) -2.87 F .37(xample, consider the situation where)-.15 F (the parser has seen)72 676.8 Q(IF \( C1 \) IF \( C2 \) S1)108 694.8 Q (and is looking at the ELSE.)72 712.8 Q(It can immediately)5 E F1 -.37 (re)2.5 G(duce).37 E F0(by the simple-if rule to get)2.5 E EP %%Page: 10 11 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3089>-2.5 G (IF \( C1 \) stat)108 108 Q(and then read the remaining input,)72 126 Q (ELSE S2)108 144 Q(and reduce)72 162 Q(IF \( C1 \) stat ELSE S2)108 180 Q(by the if-else rule.)72 198 Q(This leads to the \214rst of the abo)5 E .3 -.15(ve g)-.15 H(roupings of the input.).15 E (On the other hand, we may)97 213.6 Q/F1 10/Times-Italic@0 SF(shift)2.5 E F0(the ELSE and read S2, and then reduce the right hand portion of)2.5 E(IF \( C1 \) IF \( C2 \) S1 ELSE S2)108 231.6 Q (by the if-else rule to get)72 249.6 Q(IF \( C1 \) stat)108 267.6 Q .651 (which can be reduced by the simple-if rule.)72 285.6 R .651 (This leads to the second of the abo)5.651 F .951 -.15(ve g)-.15 H .651 (roupings of the input,).15 F(which is usually desired.)72 297.6 Q .668 (Once ag)97 313.2 R .668(ain the parser can do tw)-.05 F 3.168(ov)-.1 G .668(alid things \255 we ha)-3.418 F .968 -.15(ve a s)-.2 H .669 (hift/reduce con\215ict.).15 F .669(The application of)5.669 F(disambig\ uating rule 1 tells the parser to shift in this case, which leads to th\ e desired grouping.)72 325.2 Q 1.873(Notice that this shift/reduce con\ \215ict arises only when there is a particular current input symbol,)97 340.8 R(ELSE, and particular inputs already seen, such as)72 352.8 Q (IF \( C1 \) IF \( C2 \) S1)108 370.8 Q .389 (In general, there may be man)72 388.8 R 2.889(yc)-.15 G .389(on\215ict\ s, and each one will be associated with an input symbol and a set of) -2.889 F(pre)72 400.8 Q .308(viously read inputs.)-.25 F .307(The pre) 5.307 F .307(viously read inputs are characterized by the)-.25 F F1 (state)2.807 E F0 .307(of the parser)2.807 F 2.807(,w)-.4 G .307 (hich is as-)-2.807 F .028(signed a nonne)72 412.8 R -.05(ga)-.15 G(ti) .05 E .329 -.15(ve i)-.25 H(nte).15 E(ger)-.15 E 5.029(.T)-.55 G .029 (he number of states in the parser is typically tw)-5.029 F 2.529(ot)-.1 G 2.529<6f8c>-2.529 G .329 -.15(ve t)-2.529 H .029(imes the number of) .15 F(grammar rules.)72 424.8 Q .476(When Y)97 440.4 R .476(acc is in)-1 F -.2(vo)-.4 G -.1(ke).2 G 2.976(dw).1 G .476(ith the v)-2.976 F .475(e\ rbose \(\255v\) option \(see Appendix B\), it produces a \214le of user\ out-)-.15 F .792 (put which includes a description of the states in the parser)72 452.4 R 5.792(.F)-.55 G .792(or e)-5.942 F .792 (xample, the output corresponding to the)-.15 F(abo)72 464.4 Q .3 -.15 (ve ex)-.15 H(ample might be:).15 E (23: shift/reduce Con\215ict \(Shift 45, Reduce 18\) on ELSE)72 482.4 Q (State 23)72 506.4 Q .4 LW 182.55 532.9 177.55 532.9 DL (stat : IF \( cond \) stat)97 530.4 Q 182.55 544.9 177.55 544.9 DL (stat : IF \( cond \) stat)97 542.4 Q(ELSE stat)5 E -1.39(ELSE shift)97 566.4 R(45)2.5 E 47.5(.r)97 578.4 S(educe 18)-47.5 E 1.159 (The \214rst line describes the con\215ict, gi)72 608.4 R 1.159 (ving the state and the input symbol.)-.25 F 1.159 (The state title follo)6.159 F 1.158(ws, and a)-.25 F .491 (brief description of the grammar rules which are acti)72 620.4 R .791 -.15(ve i)-.25 H 2.991(nt).15 G .491(his state.)-2.991 F .491 (The underline `)5.491 F 423.214 622.9 418.214 622.9 DL 5(`')414.884 620.4 S 2.992('d)-5.74 G .492(escribes the por)-2.992 F(-)-.2 E 1.236 (tions of the grammar rules which ha)72 632.4 R 1.536 -.15(ve b)-.2 H 1.236(een seen.).15 F 1.236(Thus in the e)6.236 F 1.236 (xample, in state 23 we ha)-.15 F 1.535 -.15(ve s)-.2 H 1.235(een input) .15 F(which corresponds to)72 644.4 Q(IF \( cond \) stat)108 662.4 Q .79 (and the tw)72 680.4 R 3.29(og)-.1 G .79(rammar rules sho)-3.29 F .79 (wn are acti)-.25 F 1.09 -.15(ve a)-.25 H 3.29(tt).15 G .791(his time.) -3.29 F .791(The actions possible are, if the input symbol is)5.791 F (ELSE, we may shift into state 45.)72 692.4 Q(In this state, we should \ \214nd as part of the description a line of the form)5 E 219.94 712.9 214.94 712.9 DL(stat : IF \( cond \) stat ELSE)108 710.4 Q(stat)5 E .719 (because in this state we will ha)72 728.4 R 1.019 -.15(ve r)-.2 H .719 (ead and shifted the ELSE.).15 F .719(Back in state 23, the alternati) 5.719 F 1.019 -.15(ve a)-.25 H .718(ction, de-).15 F EP %%Page: 11 12 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3189>-2.5 G .718(scribed by `)72 108 R(`.)-.74 E -.74('')-.7 G 3.218(,i).74 G 3.218 (st)-3.218 G 3.218(ob)-3.218 G 3.218(ed)-3.218 G .718 (one if the input symbol is not mentioned e)-3.218 F .719 (xplicitly in the abo)-.15 F 1.019 -.15(ve a)-.15 H .719 (ctions; thus, in).15 F(this case, if the input symbol is not ELSE, we \ should reduce by grammar rule 18, which is presumably)72 120 Q (stat : IF \264\(\264 cond \264\)\264 stat)108 138 Q 1.261 (Notice that the numbers follo)72 156 R 1.261(wing `)-.25 F(`shift')-.74 E 3.761('c)-.74 G 1.261 (ommands refer to other states, while the numbers follo)-3.761 F(wing) -.25 E -.74(``)72 168 S(reduce').74 E 3.227('c)-.74 G .727 (ommands refer to grammar rule numbers.)-3.227 F .728 (In most states, there will be only one reduce action)5.727 F .904 (possible in the state, and this will al)72 180 R -.1(wa)-.1 G .904 (ys be the def).1 F .904(ault command.)-.1 F .903 (The user who encounters une)5.904 F(xpected)-.15 E .289 (shift/reduce con\215icts will probably w)72 192 R .289 (ant to look at the v)-.1 F .29(erbose output to decide whether the def) -.15 F .29(ault actions)-.1 F .412(are appropriate.)72 204 R .411 (In really tough cases, the user might need to kno)5.412 F 2.911(wm)-.25 G .411(ore about the beha)-2.911 F .411(vior and construc-)-.2 F .204 (tion of the parser than can be co)72 216 R -.15(ve)-.15 G .204(red her\ e; in this case, a reference such as [1] might be consulted; the ser).15 F(-)-.2 E(vices of a local guru might also be appropriate.)72 228 Q .442 (There is one common situation where the rules gi)97 243.6 R -.15(ve) -.25 G 2.941(na).15 G(bo)-2.941 E .741 -.15(ve f)-.15 H .441 (or resolving con\215icts are not suf).15 F(\214cient;)-.25 E .841 (this is in the area of arithmetic e)72 255.6 R 3.341(xpressions. Most) -.15 F .842(of the commonly used constructions for arithmetic e)3.341 F (x-)-.15 E .76(pressions can be naturally described by the notion of)72 267.6 R/F1 10/Times-Italic@0 SF(pr)3.26 E(ecedence)-.37 E F0(le)3.26 E -.15(ve)-.25 G .76(ls for operators, together with infor).15 F(-)-.2 E 1.717(mation about left or right associati)72 279.6 R(vity)-.25 E 6.717 (.I)-.65 G 4.217(tt)-6.717 G 1.717 (urns out that ambiguous grammars with appropriate disam-)-4.217 F .834 (biguating rules can be used to create parsers which are f)72 291.6 R .833(aster and easier to write than parsers constructed)-.1 F (from unambiguous grammars.)72 303.6 Q (The basic notion is to write grammar rules of the form)5 E -.15(ex)108 321.6 S(pr : e).15 E(xpr OP e)-.15 E(xpr)-.15 E(and)72 339.6 Q -.15(ex) 108 357.6 S(pr : UN).15 E(AR)-.35 E 2.5(Ye)-.65 G(xpr)-2.65 E 1.334 (for all binary and unary operators desired.)72 375.6 R 1.334 (This creates a v)6.334 F 1.334(ery ambiguous grammar)-.15 F 3.834(,w) -.4 G 1.334(ith man)-3.834 F 3.834(yp)-.15 G(arsing)-3.834 E 3.046 (con\215icts. As)72 387.6 R .545(disambiguating rules, the user speci\ \214es the precedence, or binding strength, of all the opera-)3.046 F .036(tors, and the associati)72 399.6 R .036 (vity of the binary operators.)-.25 F .037(This information is suf)5.036 F .037(\214cient to allo)-.25 F 2.537(wY)-.25 G .037(acc to resolv) -3.537 F 2.537(et)-.15 G(he)-2.537 E 1.141(parsing con\215icts in accor\ dance with these rules, and construct a parser which realizes the desir\ ed prece-)72 411.6 R(dences and associati)72 423.6 Q(vities.)-.25 E .887 (The precedences and associati)97 439.2 R .888 (vities are attached to tok)-.25 F .888 (ens in the declarations section.)-.1 F .888(This is done)5.888 F .523 (by a series of lines be)72 451.2 R .523(ginning with a Y)-.15 F .523 (acc k)-1 F -.15(ey)-.1 G -.1(wo).15 G .523 (rd: %left, %right, or %nonassoc, follo).1 F .522(wed by a list of to-) -.25 F -.1(ke)72 463.2 S 3.052(ns. All).1 F .552(of the tok)3.052 F .553 (ens on the same line are assumed to ha)-.1 F .853 -.15(ve t)-.2 H .553 (he same precedence le).15 F -.15(ve)-.25 G 3.053(la).15 G .553 (nd associati)-3.053 F(vity;)-.25 E(the lines are listed in order of in\ creasing precedence or binding strength.)72 475.2 Q(Thus,)5 E <256c65667420b42bb420b4adb4>108 493.2 Q(%left \264*\264 \264/\264)108 505.2 Q .138(describes the precedence and associati)72 523.2 R .138 (vity of the four arithmetic operators.)-.25 F .138 (Plus and minus are left associa-)5.138 F(ti)72 535.2 Q -.15(ve)-.25 G 2.775(,a).15 G .275(nd ha)-2.775 F .576 -.15(ve l)-.2 H -.25(ow).15 G .276(er precedence than star and slash, which are also left associati) .25 F -.15(ve)-.25 G 5.276(.T).15 G .276(he k)-5.276 F -.15(ey)-.1 G -.1 (wo).15 G .276(rd %right is).1 F .4(used to describe right associati)72 547.2 R .7 -.15(ve o)-.25 H .399(perators, and the k).15 F -.15(ey)-.1 G -.1(wo).15 G .399(rd %nonassoc is used to describe operators, lik).1 F (e)-.1 E(the operator .L)72 559.2 Q 1.48 -.74(T. i)-.92 H 2.5(nF).74 G (ortran, which may not associate with themselv)-2.65 E(es; thus,)-.15 E 2.5(A.)108 577.2 S -1.4 -.92(LT .)-2.5 H 2.5(B.)3.42 G -1.4 -.92(LT .) -2.5 H(C)3.42 E .292(is ille)72 595.2 R -.05(ga)-.15 G 2.792(li).05 G 2.792(nF)-2.792 G .293(ortran, and such an operator w)-2.942 F .293 (ould be described with the k)-.1 F -.15(ey)-.1 G -.1(wo).15 G .293 (rd %nonassoc in Y).1 F 2.793(acc. As)-1 F(an)2.793 E -.15(ex)72 607.2 S (ample of the beha).15 E(vior of these declarations, the description)-.2 E EP %%Page: 12 13 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3289>-2.5 G (%right \264=\264)108 108 Q<256c65667420b42bb420b4adb4>108 120 Q (%left \264*\264 \264/\264)108 132 Q(%%)108 156 Q -.15(ex)108 180 S (pr :).15 E -.15(ex)133 192 S(pr \264=\264 e).15 E(xpr |)-.15 E -.15(ex) 133 204 S(pr \264+\264 e).15 E(xpr |)-.15 E -.15(ex)133 216 S <707220b4adb42065>.15 E(xpr |)-.15 E -.15(ex)133 228 S(pr \264*\264 e) .15 E(xpr |)-.15 E -.15(ex)133 240 S(pr \264/\264 e).15 E(xpr |)-.15 E -.35(NA)133 252 S(ME ;).35 E(might be used to structure the input)72 270 Q 2.5(a=b=c)108 288 S(*d \255 e \255 f*g)-2.5 E(as follo)72 306 Q(ws:) -.25 E 2.5(a=\(b=\(\()108 324 S(\(c*d\)\255e\) \255 \(f*g\) \) \))-2.5 E .068 (When this mechanism is used, unary operators must, in general, be gi)72 342 R -.15(ve)-.25 G 2.568(nap).15 G 2.568(recedence. An)-2.568 F .068 (interesting situ-)2.568 F .411(ation arises when we ha)72 354 R .711 -.15(ve a u)-.2 H .411(nary operator and a binary operator which ha).15 F .711 -.15(ve t)-.2 H .412(he same symbolic represen-).15 F .298 (tation, b)72 366 R .298(ut dif)-.2 F .298(ferent precedences.)-.25 F .298(An e)5.298 F .298 (xample is unary and binary \264\255\264; frequently)-.15 F 2.797(,u) -.65 G .297(nary minus is gi)-2.797 F -.15(ve)-.25 G 2.797(nt).15 G(he) -2.797 E .965(same strength as multiplication, or e)72 378 R -.15(ve) -.25 G 3.465(nh).15 G(igher)-3.465 E 3.465(,w)-.4 G .965 (hile binary minus has a lo)-3.465 F .966(wer strength than multiplica-) -.25 F 2.601(tion. W)72 390 R 2.601(ec)-.8 G .101 (an indicate this situation by use of another k)-2.601 F -.15(ey)-.1 G -.1(wo).15 G .1(rd, %prec, to change the precedence le).1 F -.15(ve)-.25 G 2.6(la).15 G(sso-)-2.6 E .427(ciated with a particular grammar rule.) 72 402 R .428 (%prec appears immediately after the body of the grammar rule, be-)5.427 F .246(fore the action or closing semicolon, and is follo)72 414 R .245 (wed by a tok)-.25 F .245 (en name or literal; it causes the precedence of)-.1 F .81 (the grammar rule to become that of the tok)72 426 R .811 (en name or literal.)-.1 F .811(Thus, to mak)5.811 F 3.311(eu)-.1 G .811 (nary minus ha)-3.311 F 1.111 -.15(ve t)-.2 H .811(he same).15 F (precedence as multiplication, we might write:)72 438 Q <256c65667420b42bb420b4adb4>108 456 Q(%left \264*\264 \264/\264)108 468 Q(%%)108 492 Q -.15(ex)108 516 S(pr :).15 E -.15(ex)133 528 S (pr \264+\264 e).15 E(xpr |)-.15 E -.15(ex)133 540 S<707220b4adb42065> .15 E(xpr |)-.15 E -.15(ex)133 552 S(pr \264*\264 e).15 E(xpr |)-.15 E -.15(ex)133 564 S(pr \264/\264 e).15 E(xpr |)-.15 E133 576 Q (xpr %prec \264*\264 |)-.15 E -.35(NA)133 588 S(ME ;).35 E .111(Notice \ that the precedences which are described by %left, %right, and %nonasso\ c are independent of)97 609.6 R .071(the declarations of tok)72 621.6 R .071(en names by %tok)-.1 F 2.572(en. A)-.1 F .072 (symbol can be declared by %tok)2.572 F .072 (en, and, later in the declara-)-.1 F .15(tions section, be gi)72 633.6 R -.15(ve)-.25 G 2.65(nap).15 G .15(recedence and associati)-2.65 F .149 (vity by one of the abo)-.25 F .449 -.15(ve m)-.15 H 2.649(ethods. It) .15 F .149(is true, ho)2.649 F(we)-.25 E -.15(ve)-.25 G .949 -.4(r, t) .15 H(hat).4 E .298(names which are gi)72 645.6 R -.15(ve)-.25 G 2.798 (nap).15 G .298(recedence or associati)-2.798 F .298 (vity are also declared to be tok)-.25 F .299 (en names, and so in general)-.1 F(do not need to be declared by %tok)72 657.6 Q(en, although it does not hurt to do so.)-.1 E .217 (As we mentioned abo)97 673.2 R -.15(ve)-.15 G 2.717(,t).15 G .217 (he precedences and associati)-2.717 F .217(vities are used by Y)-.25 F .216(acc to resolv)-1 F 2.716(ep)-.15 G .216(arsing con-)-2.716 F (\215icts; the)72 685.2 Q 2.5(yg)-.15 G -2.15 -.25(iv e)-2.5 H (rise to disambiguating rules.)2.75 E -.15(Fo)5 G(rmally).15 E 2.5(,t) -.65 G(he rules w)-2.5 E(ork as follo)-.1 E(ws:)-.25 E EP %%Page: 13 14 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3389>-2.5 G 15 (1. The)72 108 R(precedences and associati)2.5 E (vities are recorded for those tok)-.25 E(ens and literals which ha)-.1 E .3 -.15(ve t)-.2 H(hem.).15 E 15(2. A)72 123.6 R .694 (precedence and associati)3.194 F .694(vity is associated with each gra\ mmar rule; it is the precedence and asso-)-.25 F(ciati)97 135.6 Q .382 (vity of the last tok)-.25 F .382 (en or literal in the body of the rule.)-.1 F .381 (If the %prec construction is used, it o)5.381 F -.15(ve)-.15 G -.2(r-) .15 G .317(rides this def)97 147.6 R 2.818(ault. Notice)-.1 F .318 (that some grammar rules may ha)2.818 F .618 -.15(ve n)-.2 H 2.818(op) .15 G .318(recedence and associati)-2.818 F .318(vity associ-)-.25 F (ated with them.)97 159.6 Q 15(3. When)72 175.2 R .46(there is a reduce\ /reduce con\215ict, or there is a shift/reduce con\215ict and either th\ e input symbol)2.96 F .142 (or the grammar rule, or both, has no precedence and associati)97 187.2 R .143(vity associated with it, then the tw)-.25 F 2.643(od)-.1 G(is-) -2.643 E(ambiguating rules gi)97 199.2 Q -.15(ve)-.25 G 2.5(na).15 G 2.5 (tt)-2.5 G(he be)-2.5 E (ginning of the section are used, and the con\215icts are reported.)-.15 E 15(4. If)72 214.8 R .38(there is a shift/reduce con\215ict, and both \ the grammar rule and the input character ha)2.88 F .68 -.15(ve p)-.2 H (recedence).15 E .304(and associati)97 226.8 R .304 (vity associated with them, then the con\215ict is resolv)-.25 F .305 (ed in f)-.15 F -.2(avo)-.1 G 2.805(ro).2 G 2.805(ft)-2.805 G .305 (he action \(shift or re-)-2.805 F .626 (duce\) associated with the higher precedence.)97 238.8 R .626 (If the precedences are the same, then the associati)5.626 F(vity)-.25 E .383(is used; left associati)97 250.8 R .683 -.15(ve i)-.25 H .383 (mplies reduce, right associati).15 F .683 -.15(ve i)-.25 H .383 (mplies shift, and nonassociating implies er).15 F(-)-.2 E(ror)97 262.8 Q(.)-.55 E .552(There are a number of points w)97 278.4 R .551 (orth making about this use of disambiguation.)-.1 F .551 (There is no reporting)5.551 F 1.175(of con\215icts which are resolv)72 290.4 R 1.176(ed by this mechanism, and these con\215icts are not count\ ed in the number of)-.15 F 1 (shift/reduce and reduce/reduce con\215icts found in the grammar)72 302.4 R 6(.T)-.55 G 1(his means that occasionally mistak)-6 F 1(es in) -.1 F .763(the speci\214cation of precedences disguise errors in the in\ put grammar; it is a good idea to be sparing with)72 314.4 R .813 (precedences, and use them in an essentially `)72 326.4 R(`cookbook') -.74 E 3.313('f)-.74 G .813(ashion, until some e)-3.413 F .812 (xperience has been g)-.15 F(ained.)-.05 E(Frequently)72 338.4 Q 3.372 (,n)-.65 G .872(ot enough operators or precedences ha)-3.372 F 1.173 -.15(ve b)-.2 H .873 (een speci\214ed; this leads to a number of messages).15 F .734 (about shift/reduce or reduce/reduce con\215icts.)72 350.4 R .733 (The cure is usually to specify more precedences, or use the)5.734 F .578(%prec mechanism, or both.)72 362.4 R .579 (It is generally good to e)5.579 F .579(xamine the v)-.15 F .579 (erbose output \214le to ensure that the con-)-.15 F (\215icts which are being reported can be v)72 374.4 Q(alidly resolv) -.25 E(ed by precedence.)-.15 E/F1 10/Times-Bold@0 SF(Section 5: Err)72 398.4 Q(or Handling)-.18 E F0 .356(Error handling is an e)97 414 R .356 (xtremely dif)-.15 F .356(\214cult area, and man)-.25 F 2.856(yo)-.15 G 2.856(ft)-2.856 G .355(he problems are semantic ones.)-2.856 F .355 (When an)5.355 F .665(error is found, for e)72 426 R .666(xample, it ma\ y be necessary to reclaim parse tree storage, delete or alter symbol ta\ ble)-.15 F(entries, and, typically)72 438 Q 2.5(,s)-.65 G (et switches to a)-2.5 E -.2(vo)-.2 G(id putting out an).2 E 2.5(yf)-.15 G(urther output.)-2.5 E .146(It is generally not acceptable to stop all\ processing when an error is found; we wish to continue scan-)97 453.6 R .36(ning the input to \214nd an)72 465.6 R 2.86(yf)-.15 G .36 (urther syntax errors.)-2.86 F .36 (This leads to the problem of getting the parser `)5.36 F(`restarted') -.74 E(')-.74 E .097(after an error)72 477.6 R 5.096(.T)-.55 G .096 (he general class of algorithms to do this in)-5.096 F -.2(vo)-.4 G(lv) .2 E .096(es reading ahead and discarding a number of)-.15 F(tok)72 489.6 Q(ens from the input string, and attempting to adjust the parser \ so that input can continue.)-.1 E 1.673 -.8(To a)97 505.2 T(llo).8 E 2.573(wt)-.25 G .073(he user some control o)-2.573 F -.15(ve)-.15 G 2.574(rt).15 G .074(his process, Y)-2.574 F .074(acc pro)-1 F .074 (vides a simple, b)-.15 F .074(ut reasonably general, fea-)-.2 F 3.023 (ture. The)72 517.2 R(tok)3.023 E .523(en name `)-.1 F(`error')-.74 E 3.022('i)-.74 G 3.022(sr)-3.022 G(eserv)-3.022 E .522 (ed for error handling.)-.15 F .522 (This name can be used in grammar rules; in)5.522 F(ef)72 529.2 Q .495 (fect, it suggests places where errors are e)-.25 F .496 (xpected, and reco)-.15 F -.15(ve)-.15 G .496(ry might tak).15 F 2.996 (ep)-.1 G 2.996(lace. The)-2.996 F .496(parser attempts to)2.996 F 1.365 (\214nd the last time in the input when the special tok)72 541.2 R 1.364 (en `)-.1 F(`error')-.74 E 3.864('i)-.74 G 3.864(sp)-3.864 G 3.864 (ermitted. The)-3.864 F 1.364(parser then beha)3.864 F -.15(ve)-.2 G 3.864(sa).15 G(s)-3.864 E .06(though it sa)72 553.2 R 2.56(wt)-.15 G .06 (he tok)-2.56 F .06(en name `)-.1 F(`error')-.74 E 2.56('a)-.74 G 2.56 (sa)-2.56 G 2.56(ni)-2.56 G .06(nput tok)-2.56 F .06 (en, and attempts to parse according to the rule encoun-)-.1 F 2.947 (tered. The)72 565.2 R(tok)2.947 E .447(en at which the error w)-.1 F .446(as detected remains the ne)-.1 F .446(xt input tok)-.15 F .446 (en after this error tok)-.1 F .446(en is pro-)-.1 F 3.304(cessed. If)72 577.2 R .804(no special error rules ha)3.304 F 1.105 -.15(ve b)-.2 H .805(een speci\214ed, the processing ef).15 F(fecti)-.25 E -.15(ve)-.25 G .805(ly halts when an error is de-).15 F(tected.)72 589.2 Q .087 (In order to pre)97 604.8 R -.15(ve)-.25 G .086(nt a cascade of error m\ essages, the parser assumes that, after detecting an error).15 F 2.586 (,i)-.4 G 2.586(tr)-2.586 G(e-)-2.586 E .327 (mains in error state until three tok)72 616.8 R .327(ens ha)-.1 F .627 -.15(ve b)-.2 H .327(een successfully read and shifted.).15 F .328 (If an error is detected when)5.327 F (the parser is already in error state, no error message is gi)72 628.8 Q -.15(ve)-.25 G(n, and the input tok).15 E(en is quietly deleted.)-.1 E (As a common e)97 644.4 Q (xample, the user might include a rule of the form)-.15 E(statement :) 108 662.4 Q(error ;)5 E .075(in his speci\214cation.)72 680.4 R .075 (This w)5.075 F .075(ould, in ef)-.1 F .075 (fect, mean that on a syntax error the parser w)-.25 F .074 (ould attempt to skip o)-.1 F -.15(ve)-.15 G(r).15 E .021 (the statement in which the error w)72 692.4 R .021(as seen.)-.1 F .021 (\(Notice, ho)5.021 F(we)-.25 E -.15(ve)-.25 G .821 -.4(r, t).15 H .021 (hat it may be dif).4 F .021(\214cult or impossible to tell the)-.25 F 1.266(end of a statement, depending on the other grammar rules\).)72 704.4 R 1.265(More precisely)6.266 F 3.765(,t)-.65 G 1.265 (he parser will scan ahead,)-3.765 F .019(looking for three tok)72 716.4 R .019(ens that might le)-.1 F -.05(ga)-.15 G .019(lly follo).05 F 2.519 (was)-.25 G .02 (tatement, and start processing at the \214rst of these; if the)-2.519 F (be)72 728.4 Q .679(ginnings of statements are not suf)-.15 F .679 (\214ciently distincti)-.25 F -.15(ve)-.25 G 3.178(,i).15 G 3.178(tm) -3.178 G .678(ay mak)-3.178 F 3.178(eaf)-.1 G .678 (alse start in the middle of a state-)-3.278 F EP %%Page: 14 15 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3489>-2.5 G (ment, and end up reporting a second error where there is in f)72 108 Q (act no error)-.1 E(.)-.55 E .374(The user may supply actions after the\ se special grammar rules, just as after the other grammar rules.)97 123.6 R(These actions might attempt to reinitialize tables, reclaim sym\ bol table space, etc.)72 135.6 Q .269(The abo)97 151.2 R .569 -.15(ve f) -.15 H .269(orm of grammar rule is v).15 F .269(ery general, b)-.15 F .269(ut some)-.2 F .268(what dif)-.25 F .268(\214cult to control.)-.25 F (Some)5.268 E .268(what easier)-.25 F (to deal with are rules of the form)72 163.2 Q(statement :)108 181.2 Q (error \264;\264)5 E(;)5 E .091(Here, when there is an error)72 199.2 R 2.591(,t)-.4 G .091(he parser will ag)-2.591 F .091 (ain attempt to skip o)-.05 F -.15(ve)-.15 G 2.591(rt).15 G .091 (he statement, b)-2.591 F .091(ut in this case will do)-.2 F .068 (so by skipping to the ne)72 211.2 R .068(xt `)-.15 F(`;')-.74 E 2.568 ('. All)-.74 F(tok)2.568 E .068(ens after the error and before the ne) -.1 F .067(xt `)-.15 F(`;')-.74 E 2.567('g)-.74 G -2.15 -.25(iv e)-2.567 H .067(syntax errors, and are)2.817 F 2.542(discarded. When)72 223.2 R .042(the `)2.542 F(`;')-.74 E 2.542('i)-.74 G 2.542(ss)-2.542 G .042 (een, this rule will be reduced, and an)-2.542 F 2.542(y`)-.15 G (`cleanup')-3.282 E 2.542('a)-.74 G .043(ction associated with it will) -2.542 F(be performed.)72 235.2 Q .832 (Still another form of error rule arises in interacti)97 250.8 R 1.131 -.15(ve a)-.25 H .831(pplications, where we may wish to prompt the).15 F (user who has incorrectly input a line, and allo)72 262.8 Q 2.5(wh)-.25 G(im to reenter the line.)-2.5 E(In C we might write:)5 E 9.16 (inputline: error)108 280.8 R(\264\\n\264 prompt inputline)2.5 E 2.5 (={$)133 292.8 S 2.5($=$)-2.5 G(4; };)-2.5 E 15.83(prompt: /*)108 316.8 R(matches no input */)2.5 E -2.5 2.5(={ p)133 328.8 T (rintf\( "Reenter last line: " \); };)-2.5 E .648(There is one dif)72 346.8 R .649(\214culty with this approach; the parser must correctly pr\ ocess three input tok)-.25 F .649(ens before it is)-.1 F .104 (prepared to admit that it has correctly resynchronized after the error) 72 358.8 R 5.103(.T)-.55 G .103(hus, if the reentered line contains er) -5.103 F(-)-.2 E .434(rors in the \214rst tw)72 370.8 R 2.934(ot)-.1 G (ok)-2.934 E .435(ens, the parser will simply delete the of)-.1 F .435 (fending tok)-.25 F .435(ens, and gi)-.1 F .735 -.15(ve n)-.25 H 2.935 (om).15 G .435(essage; this is)-2.935 F .002(clearly unacceptable.)72 382.8 R -.15(Fo)5.001 G 2.501(rt).15 G .001(his reason, there is a mech\ anism in both C and Ratfor which can be used to force)-2.501 F (the parser to belie)72 394.8 Q .3 -.15(ve t)-.25 H (hat resynchronization has tak).15 E(en place.)-.1 E (One need only include a statement of the form)5 E(yyerrok ;)108 412.8 Q .502(in his action after such a grammar rule, and the desired ef)72 430.8 R .502(fect will tak)-.25 F 3.002(ep)-.1 G .502 (lace; this name will be e)-3.002 F(xpanded,)-.15 E .844(using the `)72 442.8 R .844(`# de\214ne')-.74 F 3.344('m)-.74 G .844 (echanism of C or the `)-3.344 F(`de\214ne')-.74 E 3.343('m)-.74 G .843 (echanism of Ratfor)-3.343 F 3.343(,i)-.4 G .843 (nto an appropriate code se-)-3.343 F 2.842(quence. F)72 454.8 R .342 (or e)-.15 F .342(xample, in the situation discussed abo)-.15 F .642 -.15(ve w)-.15 H .342(here we w).15 F .343 (ant to prompt the user to produce input,)-.1 F .034(we probably w)72 466.8 R .033(ant to consider that the original error has been reco)-.1 F -.15(ve)-.15 G .033(red when we ha).15 F .333 -.15(ve t)-.2 H(hro).15 E .033(wn a)-.25 F -.1(wa)-.15 G 2.533(yt).1 G .033(he pre-)-2.533 F .931 (vious line, including the ne)72 478.8 R 3.431(wline. In)-.25 F .931 (this case, we can reset the error state before putting out the prompt) 3.431 F 2.5(message. The)72 490.8 R (grammar rule for the nonterminal symbol prompt becomes:)2.5 E 15.83 (prompt: /*)108 508.8 R(matches no input */)2.5 E 2.5(={)133 520.8 S (yyerrok;)158 532.8 Q(printf\( "Reenter last line: " \);)158 544.8 Q 2.5 (};)133 556.8 S 1.336(There is another special feature which the user m\ ay wish to use in error reco)97 578.4 R -.15(ve)-.15 G(ry).15 E 6.336 (.A)-.65 G 3.836(sm)-6.336 G(entioned)-3.836 E(abo)72 590.4 Q -.15(ve) -.15 G 3.178(,t).15 G .678(he tok)-3.178 F .679 (en seen immediately after the `)-.1 F(`error')-.74 E 3.179('s)-.74 G .679(ymbol is the input tok)-3.179 F .679(en at which the error w)-.1 F .679(as dis-)-.1 F(co)72 602.4 Q -.15(ve)-.15 G 2.545(red. Sometimes,) .15 F .045(this is seen to be inappropriate; for e)2.545 F .044 (xample, an error reco)-.15 F -.15(ve)-.15 G .044(ry action might tak) .15 F 2.544(eu)-.1 G(pon)-2.544 E .104 (itself the job of \214nding the correct place to resume input.)72 614.4 R .104(In this case, the user wishes a w)5.104 F .104 (ay of clearing the)-.1 F(pre)72 626.4 Q(vious input tok)-.25 E (en held in the parser)-.1 E 5(.O)-.55 G (ne need only include a statement of the form)-5 E(yyclearin ;)108 644.4 Q 1.106(in his action; ag)72 662.4 R 1.106(ain, this e)-.05 F 1.105 (xpands, in both C and Ratfor)-.15 F 3.605(,t)-.4 G 3.605(ot)-3.605 G 1.105(he appropriate code sequence.)-3.605 F -.15(Fo)6.105 G 3.605(re) .15 G(xample,)-3.755 E .139(suppose the action after error were to call\ some sophisticated resynchronization routine, supplied by the us-)72 674.4 R(er)72 686.4 Q 2.517(,w)-.4 G .017(hich attempted to adv)-2.517 F .017(ance the input to the be)-.25 F .017(ginning of the ne)-.15 F .016 (xt v)-.15 F .016(alid statement.)-.25 F .016(After this routine w)5.016 F(as)-.1 E .544(called, the ne)72 698.4 R .544(xt tok)-.15 F .544 (en returned by yyle)-.1 F 3.044(xw)-.15 G .544 (ould presumably be the \214rst tok)-3.144 F .545(en in a le)-.1 F -.05 (ga)-.15 G 3.045(ls).05 G .545(tatement; we wish)-3.045 F(to thro)72 710.4 Q 2.5(wa)-.25 G -.1(wa)-2.65 G 2.5(yt).1 G(he old, ille)-2.5 E -.05(ga)-.15 G 2.5(lt).05 G(ok)-2.5 E(en, and reset the error state.)-.1 E 1.6 -.8(We m)5 H(ight do this by the sequence:).8 E EP %%Page: 15 16 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3589>-2.5 G (statement :)108 108 Q(error)5 E 2.5(={)133 120 S(resynch\( \);)158 132 Q(yyerrok ;)158 144 Q(yyclearin ;)158 156 Q 2.5(};)133 168 S 1.036 (These mechanisms are admittedly crude, b)97 189.6 R 1.036(ut do allo) -.2 F 3.536(wf)-.25 G 1.036(or a simple, f)-3.536 F 1.036(airly ef)-.1 F (fecti)-.25 E 1.336 -.15(ve r)-.25 H(eco).15 E -.15(ve)-.15 G 1.036 (ry of the).15 F .246(parser from man)72 201.6 R 2.746(ye)-.15 G .246 (rrors, and ha)-2.746 F .546 -.15(ve t)-.2 H .246 (he virtue that the user can get `).15 F(`handles')-.74 E 2.747('b)-.74 G 2.747(yw)-2.747 G .247(hich he can deal with the)-2.747 F (error actions required by the le)72 213.6 Q (xical and output portions of the system.)-.15 E/F1 10/Times-Bold@0 SF (Section 6C: The C Language Y)72 237.6 Q(acc En)-.85 E(vir)-.4 E(onment) -.18 E F0 .804(The def)97 253.2 R .804(ault mode of operation in Y)-.1 F .804(acc is to write actions and the le)-1 F .803(xical analyzer in C.) -.15 F .803(This has a)5.803 F .126(number of adv)72 265.2 R .127 (antages; primarily)-.25 F 2.627(,i)-.65 G 2.627(ti)-2.627 G 2.627(se) -2.627 G .127 (asier to write character handling routines, such as the le)-2.627 F .127(xical analyz-)-.15 F(er)72 277.2 Q 2.5(,i)-.4 G 2.5(nal)-2.5 G (anguage which supports character)-2.5 E (-by-character I/O, and has shifting and masking operators.)-.2 E 1.277 (When the user inputs a speci\214cation to Y)97 292.8 R 1.277 (acc, the output is a \214le of C programs, called `)-1 F(`y)-.74 E (.tab)-.65 E(.c')-.4 E('.)-.74 E .67(These are then compiled, and loade\ d with a library; the library has def)72 304.8 R .67(ault v)-.1 F .67 (ersions of a number of useful)-.15 F 2.651(routines. This)72 316.8 R .151(section discusses these routines, and ho)2.651 F 2.651(wt)-.25 G .15(he user can write his o)-2.651 F .15(wn routines if desired.)-.25 F (The)5.15 E(name of the Y)72 328.8 Q (acc library is system dependent; see Appendix B.)-1 E 1.004 (The subroutine produced by Y)97 344.4 R 1.004(acc is called `)-1 F (`yyparse')-.74 E 1.004('; it is an inte)-.74 F 1.005(ger v)-.15 F 1.005 (alued function.)-.25 F 1.005(When it is)6.005 F .632 (called, it in turn repeatedly calls `)72 356.4 R(`yyle)-.74 E(x')-.15 E .632(', the le)-.74 F .631 (xical analyzer supplied by the user \(see Section 3\), to ob-)-.15 F .121(tain input tok)72 368.4 R 2.621(ens. Ev)-.1 F(entually)-.15 E 2.621 (,e)-.65 G .121 (ither an error is detected, in which case \(if no error reco)-2.621 F -.15(ve)-.15 G .122(ry is possible\) yy-).15 F .152(parse returns the v) 72 380.4 R .151(alue 1, or the le)-.25 F .151 (xical analyzer returns the endmark)-.15 F .151(er tok)-.1 F .151 (en \(type number 0\), and the pars-)-.1 F(er accepts.)72 392.4 Q (In this case, yyparse returns the v)5 E(alue 0.)-.25 E .38 (Three of the routines on the Y)97 408 R .381 (acc library are concerned with the `)-1 F(`e)-.74 E(xternal')-.15 E 2.881('e)-.74 G -.4(nv)-2.881 G .381(ironment of yyparse.).4 F .866 (There is a def)72 420 R .866(ault `)-.1 F(`main')-.74 E 3.366('p)-.74 G .865(rogram, a def)-3.366 F .865(ault `)-.1 F(`initialization')-.74 E 3.365('r)-.74 G .865(outine, and a def)-3.365 F .865(ault `)-.1 F (`accept')-.74 E 3.365('r)-.74 G .865(outine, re-)-3.365 F(specti)72 432 Q -.15(ve)-.25 G(ly).15 E 5(.T)-.65 G(he)-5 E 2.5(ya)-.15 G (re so simple that the)-2.5 E 2.5(yw)-.15 G(ill be gi)-2.5 E -.15(ve) -.25 G 2.5(nh).15 G(ere in their entirety:)-2.5 E(main\( ar)108 450 Q (gc, ar)-.18 E(gv \))-.18 E(int ar)108 462 Q(gc;)-.18 E(char *ar)108 474 Q(gv[ ])-.18 E({)108 486 Q(yyinit\( ar)133 498 Q(gc, ar)-.18 E(gv \);) -.18 E(if\( yyparse\( \) \))133 510 Q(return;)158 522 Q(yyaccpt\( \);) 133 534 Q(})108 546 Q(yyinit\( \) { })108 570 Q(yyaccpt\( \) { })108 594 Q .461(By supplying his o)72 612 R .461(wn v)-.25 F .461(ersions of yyi\ nit and/or yyaccpt, the user can get control either before the parser i\ s)-.15 F .34(called \(to set options, open input \214les, etc.\))72 624 R .34 (or after the accept action has been done \(to close \214les, call the) 5.34 F(ne)72 636 Q .534(xt pass of the compiler)-.15 F 3.034(,e)-.4 G 3.035(tc.\). Note)-3.034 F .535(that yyinit is called with the tw)3.035 F 3.035(o`)-.1 G .535(`command line')-3.775 F 3.035('a)-.74 G -.18(rg) -3.035 G .535(uments which).18 F(ha)72 648 Q .579 -.15(ve b)-.2 H .279 (een passed into the main program.).15 F .279 (If neither of these routines is rede\214ned, the def)5.279 F .278 (ault situation sim-)-.1 F .093(ply looks lik)72 660 R 2.593(eac)-.1 G .093(all to the parser)-2.593 F 2.593(,f)-.4 G(ollo)-2.593 E .093 (wed by the termination of the program.)-.25 F .093(Of course, in man) 5.093 F 2.593(yc)-.15 G .093(ases the)-2.593 F .637 (user will wish to supply his o)72 672 R .637(wn main program; for e) -.25 F .636(xample, this is necessary if the parser is to be called)-.15 F(more than once.)72 684 Q .197 (The other major routine on the library is called `)97 699.6 R (`yyerror')-.74 E .197('; its main purpose is to write out a message) -.74 F .978(when a syntax error is detected.)72 711.6 R .977 (It has a number of hooks and handles which attempt to mak)5.978 F 3.477 (et)-.1 G .977(his error)-3.477 F (message general and easy to understand.)72 723.6 Q (This routine is some)5 E(what more comple)-.25 E(x, b)-.15 E (ut still approachable:)-.2 E EP %%Page: 16 17 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3689>-2.5 G -.15(ex)108 108 S(tern int yyline;).15 E(/* input line number */)5 E (yyerror\(s\))108 132 Q(char *s;)108 144 Q({)108 156 Q -.15(ex)133 168 S (tern int yychar;).15 E -.15(ex)133 180 S(tern char *yysterm[ ];).15 E (printf\("\\n%s", s \);)133 204 Q(if\( yyline \))133 216 Q (printf\(", line %d,", yyline \);)158 228 Q(printf\(" on input: "\);)133 240 Q(if\( yychar >= 0400 \))133 252 Q (printf\("%s\\n", yysterm[yychar\2550400] \);)158 264 Q (else switch \( yychar \) {)133 276 Q (case \264\\t\264: printf\( "\\\\t\\n" \); return;)133 288 Q (case \264\\n\264: printf\( "\\\\n\\n" \); return;)133 300 Q (case \264\\0\264: printf\( "$end\\n" \); return;)133 312 Q(def)133 324 Q(ault: printf\( "%c\\n" , yychar \); return;)-.1 E(})133 336 Q(})108 348 Q .192(The ar)72 366 R .193(gument to yyerror is a string containin\ g an error message; most usually)-.18 F 2.693(,i)-.65 G 2.693(ti)-2.693 G 2.693(s`)-2.693 G .193(`syntax error')-3.433 F 2.693('. yyerror)-.74 F .122(also uses the e)72 378 R .122(xternal v)-.15 F .122 (ariables yyline, yychar)-.25 F 2.622(,a)-.4 G .122(nd yysterm.)-2.622 F .121(yyline is a line number which, if set by the us-)5.122 F .012 (er to a nonzero number)72 390 R 2.512(,w)-.4 G .012 (ill be printed out as part of the error message.)-2.512 F .013 (yychar is a v)5.013 F .013(ariable which contains)-.25 F .185 (the type number of the current tok)72 402 R 2.684(en. yysterm)-.1 F .184(has the names, supplied by the user)2.684 F 2.684(,f)-.4 G .184 (or all the tok)-2.684 F .184(ens which)-.1 F(ha)72 414 Q 1.01 -.15 (ve n)-.2 H 3.21(ames. Thus,).15 F .711(the routine spends most of its \ time trying to print out a reasonable name for the input)3.21 F(tok)72 426 Q 2.627(en. The)-.1 F .127(biggest problem with the routine as gi) 2.627 F -.15(ve)-.25 G 2.627(ni).15 G 2.627(st)-2.627 G .127 (hat, on Unix, the error message does not go out on)-2.627 F .481 (the error \214le \(\214le 2\).)72 438 R .482 (This is hard to arrange in such a w)5.482 F .482(ay that it w)-.1 F .482(orks with both the portable I/O library)-.1 F .992 (and the system I/O library; if a w)72 450 R .992(ay can be w)-.1 F(ork) -.1 E .991(ed out, the routine will be changed to do this.)-.1 F/F1 10 /Times-Italic@0 SF(Be)5.991 E(war)-.15 E(e:)-.37 E F0 .079 (This routine will not w)72 462 R .079(ork if an)-.1 F 2.579(yt)-.15 G (ok)-2.579 E .079(en names ha)-.1 F .379 -.15(ve b)-.2 H .079(een gi).15 F -.15(ve)-.25 G 2.579(nr).15 G .079(ede\214ned type numbers.)-2.579 F .079(In this case, the us-)5.079 F(er must supply his o)72 474 Q (wn yyerror routine.)-.25 E(Hopefully)5 E 2.5(,t)-.65 G(his `)-2.5 E (`feature')-.74 E 2.5('w)-.74 G(ill disappear soon.)-2.5 E(Finally)97 489.6 Q 2.653(,t)-.65 G .152 (here is another feature which the C user of Y)-2.653 F .152 (acc might wish to use.)-1 F .152(The inte)5.152 F .152(ger v)-.15 F .152(ariable yy-)-.25 F(deb)72 501.6 Q .057(ug is normally set to 0.)-.2 F .058(If it is set to 1, the parser will output a v)5.057 F .058 (erbose description of its actions, includ-)-.15 F .12 (ing a discussion of which input symbols ha)72 513.6 R .42 -.15(ve b)-.2 H .119(een read, and what the parser actions are.).15 F .119 (Depending on the)5.119 F(operating en)72 525.6 Q (vironment, it may be possible to set this v)-.4 E (ariable by using a deb)-.25 E(ugging system.)-.2 E/F2 10/Times-Bold@0 SF(Section 6R: The Ratf)72 549.6 Q(or Language Y)-.25 E(acc En)-.85 E (vir)-.4 E(onment)-.18 E F0 -.15(Fo)97 565.2 S 3.496(rr).15 G .996 (easons of portability or compatibility with e)-3.496 F .996 (xisting softw)-.15 F .996(are, it may be desired to use Y)-.1 F .997 (acc to)-1 F 1.097(generate parsers in Ratfor)72 577.2 R 3.597(,o)-.4 G 1.896 -.4(r, b)-3.597 H 3.596(ye).4 G 1.096(xtension, in portable F) -3.746 F 3.596(ortran. The)-.15 F 1.096(user is lik)3.596 F 1.096 (ely to w)-.1 F 1.096(ork considerably)-.1 F (harder doing this than he might if he were to use C.)72 589.2 Q .782 (When the user inputs a speci\214cation to Y)97 604.8 R .782 (acc, and speci\214es the Ratfor option \(see Appendix B\), the)-1 F .15 (output is a \214le of Ratfor programs called `)72 616.8 R(`y)-.74 E (.tab)-.65 E(.r')-.4 E 2.65('. These)-.74 F .15 (programs are then compiled, and pro)2.65 F .15(vide the de-)-.15 F (sired subroutine.)72 628.8 Q 1.283(The subroutine produced by Y)97 644.4 R 1.283(acc which does the input process is an inte)-1 F 1.284 (ger function called `)-.15 F(`yy-)-.74 E(pars')72 656.4 Q 3.035 ('. When)-.74 F .535(it is called, it in turn repeatedly calls `)3.035 F (`yyle)-.74 E(x')-.15 E .534(', the le)-.74 F .534 (xical analyzer supplied by the user \(see)-.15 F .055(Section 3\).)72 668.4 R(Ev)5.055 E(entually)-.15 E 2.555(,e)-.65 G .055 (ither an error is detected, in which case \(if no error reco)-2.555 F -.15(ve)-.15 G .055(ry is possible\) yypars re-).15 F .362(turns the v) 72 680.4 R .362(alue 1, or the le)-.25 F .362 (xical analyzer returns the endmark)-.15 F .361 (er \(type number 0\), and the parser accepts.)-.1 F(In)5.361 E (this case, yypars returns 0.)72 692.4 Q(Unlik)97 708 Q 2.871(et)-.1 G .371(he C program situation \(see Section 6C\) there is no library of R\ atfor routines which must be)-2.871 F .533(used in the loading process.) 72 720 R .533(As a side ef)5.533 F .533(fect of this,)-.25 F F1 .532 (the user must supply a main pr)3.032 F -.1(og)-.45 G -.15(ra).1 G 3.032 (mw).15 G(hic)-3.032 E 3.032(hc)-.15 G .532(alls yy-)-3.032 F EP %%Page: 17 18 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3789>-2.5 G/F1 10/Times-Italic@0 SF(par)72 108 Q(s.)-.1 E F0 2.5(As)5 G (uggested Ratfor main program is)-2.5 E(inte)108 126 Q(ger yypars)-.15 E 2.5(n=y)108 138 S(ypars\(0\))-2.5 E(if\( n .EQ. 0 \) {)108 150 Q -2.5 2.5(... h)133 162 T(ere if the program accepted)-2.5 E 2.5(}e)108 174 S (lse {)-2.5 E -2.5 2.5(... h)133 186 T(ere if there were unreco)-2.5 E -.15(ve)-.15 G(rable errors).15 E(})108 198 Q(end)108 210 Q .35 (Notice that there is no easy w)72 228 R .35 (ay for the user to get control when an error is detected, since the F) -.1 F .35(ortran lan-)-.15 F(guage pro)72 240 Q(vides only a v)-.15 E (ery crude character string capability)-.15 E(.)-.65 E .214 (There is another feature which the Ratfor user might wish to use.)97 255.6 R .214(The ar)5.214 F .214(gument to yypars is normal-)-.18 F .857 (ly 0.)72 267.6 R .857(If it is set to 1, the parser will output a v) 5.857 F .858 (erbose description of its actions, including a discussion of)-.15 F .632(which input symbols ha)72 279.6 R .932 -.15(ve b)-.2 H .632 (een read, and what the parser actions are.).15 F .631 (During the input process, the v)5.632 F(alue)-.25 E .049(of this deb)72 291.6 R .049(ug \215ag is k)-.2 F .049(ept in a common v)-.1 F .049 (ariable yydeb)-.25 F .049(u, which is a)-.2 F -.25(va)-.2 G .049 (ilable to the actions and may be set and).25 F(reset at will.)72 303.6 Q .237(Statement labels 1 through 1000 are reserv)97 319.2 R .237 (ed for the parser)-.15 F 2.736(,a)-.4 G .236 (nd may not appear in actions; note that,)-2.736 F .393 (because Ratfor has a more modern control structure than F)72 331.2 R .394(ortran, it is rarely necessary to use statement la-)-.15 F(bels at\ all; the most frequent use of labels in Ratfor is in formatted I/O.)72 343.2 Q .615(Because F)97 358.8 R .615 (ortran has no standard character set and not e)-.15 F -.15(ve)-.25 G 3.115(nas).15 G .615(tandard character width, it is dif)-3.115 F (\214cult)-.25 E 1.035(to produce a le)72 370.8 R 1.035 (xical analyzer in portable F)-.15 F 1.035 (ortran The usual solution is to pro)-.15 F 1.035 (vide a routine which does a)-.15 F .062 (table search to get the internal type number for each input character) 72 382.8 R 2.562(,w)-.4 G .061(ith the understanding that such a rou-) -2.562 F(tine can be recoded to run f)72 394.8 Q(ar f)-.1 E (aster for an)-.1 E 2.5(yp)-.15 G(articular machine.)-2.5 E(Finally)97 410.4 Q 2.513(,w)-.65 G 2.513(em)-2.513 G .013(ust w)-2.513 F .013 (arn the user that the Ratfor feature of Y)-.1 F .014 (acc has been operational for a much shorter)-1 F .385 (time than the other portions of the system.)72 422.4 R .384(If past e) 5.385 F .384(xperience is an)-.15 F 2.884(yg)-.15 G .384 (uide, the Ratfor support will de)-2.884 F -.15(ve)-.25 G(lop).15 E .465 (and become more po)72 434.4 R .465(werful and better human engineered \ in response to user complaints and requirements.)-.25 F(Thus, the poten\ tial Ratfor user might do well to contact the author to discuss his o)72 446.4 Q(wn particular needs.)-.25 E/F2 10/Times-Bold@0 SF (Section 7. Hints f)72 470.4 Q(or Pr)-.25 E(eparing Speci\214cations) -.18 E F0 .543 (This section contains miscellaneous hints on preparing ef)97 486 R .542 (\214cient, easy to change, and clear speci\214ca-)-.25 F 3.332 (tions. The)72 498 R(indi)3.332 E .832 (vidual subsections are, more or less, independent; the reader seeing Y) -.25 F .833(acc for the \214rst time)-1 F (may well \214nd that this entire section could be omitted.)72 510 Q F2 (Input Style)72 534 Q F0 .998(It is dif)97 549.6 R .998 (\214cult to input rules with substantial actions and still ha)-.25 F 1.297 -.15(ve a r)-.2 H .997(eadable speci\214cation \214le.).15 F(The) 5.997 E(follo)72 561.6 Q(wing style hints o)-.25 E(we much to Brian K) -.25 E(ernighan, and are of)-.25 E(\214cially endorsed by the author) -.25 E(.)-.55 E 15.56(a. Use)72 577.2 R .308 (all capital letters for tok)2.808 F .308(en names, all lo)-.1 F .308 (wer case letters for nonterminal names.)-.25 F .309(This rule comes) 5.308 F(under the heading of `)97 589.2 Q(`kno)-.74 E (wing who to blame when things go wrong.`)-.25 E(`)-.74 E 16.2 -.4(b. P) 72 604.8 T .7(ut grammar rules and actions on separate lines.).4 F .7 (This allo)5.7 F .7(ws either to be changed without an auto-)-.25 F (matic need to change the other)97 616.8 Q(.)-.55 E 15.56(c. Put)72 632.4 R .229(all rules with the same left hand side together)2.729 F 5.229(.P)-.55 G .229 (ut the left hand side in only once, and let all fol-)-5.229 F(lo)97 644.4 Q(wing rules be)-.25 E(gin with a v)-.15 E(ertical bar)-.15 E(.) -.55 E 15(d. Indent)72 660 R (rule bodies by one tab stop, and action bodies by tw)2.5 E 2.5(ot)-.1 G (ab stops.)-2.5 E .291(The e)97 675.6 R .291 (xample in Appendix A is written follo)-.15 F .291 (wing this style, as are the e)-.25 F .29(xamples in the te)-.15 F .29 (xt of this pa-)-.15 F .125(per \(where space permits\).)72 687.6 R .125 (The user must mak)5.125 F 2.625(eu)-.1 G 2.625(ph)-2.625 G .125(is o) -2.625 F .126(wn mind about these stylistic questions; the central)-.25 F(problem, ho)72 699.6 Q(we)-.25 E -.15(ve)-.25 G .8 -.4(r, i).15 H 2.5 (st).4 G 2.5(om)-2.5 G(ak)-2.5 E 2.5(et)-.1 G (he rules visible through the morass of action code.)-2.5 E EP %%Page: 18 19 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3889>-2.5 G/F1 10/Times-Bold@0 SF(Common Actions)72 108 Q F0 .078(When se)97 123.6 R -.15(ve)-.25 G .077(ral grammar rules ha).15 F .377 -.15(ve t)-.2 H .077 (he same action, the user might well wish to pro).15 F .077 (vide only one code)-.15 F 2.578(sequence. A)72 135.6 R .079 (simple, general mechanism is, of course, to use subroutine calls.)2.579 F .079(It is also possible to put a la-)5.079 F .345(bel on the \214rst\ statement of an action, and let other actions be simply a goto to this\ label.)72 147.6 R .345(Thus, if the user)5.345 F(had a routine which b) 72 159.6 Q(uilt trees, he might wish to ha)-.2 E .3 -.15(ve o)-.2 H (nly one call to it, as follo).15 E(ws:)-.25 E -.15(ex)108 177.6 S(pr :) .15 E -.15(ex)133 189.6 S(pr \264+\264 e).15 E(xpr =)-.15 E 5({b)133 201.6 S(inary:)-5 E($$ = btree\( $1, $2, $3 \);)158 213.6 Q 2.5(}|)133 225.6 S -.15(ex)133 237.6 S<707220b4adb42065>.15 E(xpr =)-.15 E({)133 249.6 Q(goto binary;)158 261.6 Q 2.5(}|)133 273.6 S -.15(ex)133 285.6 S (pr \264*\264 e).15 E(xpr =)-.15 E({)133 297.6 Q(goto binary;)158 309.6 Q 2.5(};)133 321.6 S F1(Left Recursion)72 351.6 Q F0 .352 (The algorithm used by the Y)97 367.2 R .352 (acc parser encourages so called `)-1 F .352(`left recursi)-.74 F -.15 (ve)-.25 G 1.832 -.74('' g).15 H .352(rammar rules: rules of).74 F (the form)72 379.2 Q .4 LW 181.04 399.7 176.04 399.7 DL (name : name rest)108 397.2 Q 194.37 399.7 189.37 399.7 DL 2.5(of rule) 181.04 397.2 R(;)2.5 E(These rules frequently arise when writing speci\ \214cations of sequences and lists:)72 415.2 Q(list :)108 433.2 Q (item |)133 445.2 Q(list \264,\264 item ;)133 457.2 Q(and)72 475.2 Q (sequence :)108 493.2 Q(item |)133 505.2 Q(sequence item ;)133 517.2 Q .474(Notice that, in each of these cases, the \214rst rule will be redu\ ced for the \214rst item only)72 535.2 R 2.973(,a)-.65 G .473 (nd the second rule)-2.973 F (will be reduced for the second and all succeeding items.)72 547.2 Q (If the user were to write these rules right recursi)97 562.8 Q -.15(ve) -.25 G(ly).15 E 2.5(,s)-.65 G(uch as)-2.5 E(sequence :)108 580.8 Q (item |)133 592.8 Q(item sequence ;)133 604.8 Q .648(the parser w)72 622.8 R .648(ould be a bit bigger)-.1 F 3.148(,a)-.4 G .648 (nd the items w)-3.148 F .648 (ould be seen, and reduced, from right to left.)-.1 F .648(More seri-) 5.648 F(ously)72 634.8 Q 2.965(,a)-.65 G 2.965(ni)-2.965 G .465 (nternal stack in the parser w)-2.965 F .465(ould be in danger of o)-.1 F -.15(ve)-.15 G(r\215o).15 E .465(wing if a v)-.25 F .464 (ery long sequence were read.)-.15 F (Thus, the user should use left recursion where)72 646.8 Q -.15(ve)-.25 G 2.5(rr).15 G(easonable.)-2.5 E 1.112(The user should also consider wh\ ether a sequence with zero elements has an)97 662.4 R 3.612(ym)-.15 G 1.112(eaning, and if so,)-3.612 F (consider writing the sequence speci\214cation with an empty rule:)72 674.4 Q(sequence :)108 692.4 Q 2.5(|/)133 704.4 S 2.5(*e)-2.5 G(mpty */) -2.5 E(sequence item ;)133 716.4 Q EP %%Page: 19 20 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8931>275.5 60 S 2.5<3989>-2.5 G .114(Once ag)72 108 R .114(ain, the \214rst rule w)-.05 F .113(ould al) -.1 F -.1(wa)-.1 G .113(ys be reduced e).1 F .113 (xactly once, before the \214rst item w)-.15 F .113 (as read, and then the)-.1 F 1.609(second rule w)72 120 R 1.609 (ould be reduced once for each item read.)-.1 F 1.61 (Experience suggests that permitting empty se-)6.609 F 1.008 (quences leads to increased generality)72 132 R 3.508(,w)-.65 G 1.008 (hich frequently is not e)-3.508 F 1.007 (vident at the time the rule is \214rst written.)-.25 F .854 (There are cases, ho)72 144 R(we)-.25 E -.15(ve)-.25 G 1.654 -.4(r, w) .15 H .854(hen the Y).4 F .854(acc algorithm can f)-1 F .855 (ail when such a change is made.)-.1 F .855(In ef)5.855 F .855 (fect, con-)-.25 F 1.458(\215icts might arise when Y)72 156 R 1.457 (acc is ask)-1 F 1.457 (ed to decide which empty sequence it has seen, when it hasn\264t seen) -.1 F(enough to kno)72 168 Q 2.5(w! Ne)-.25 F -.15(ve)-.25 G (rtheless, this principle is still w).15 E(orth follo)-.1 E(wing where) -.25 E -.15(ve)-.25 G 2.5(rp).15 G(ossible.)-2.5 E/F1 10/Times-Bold@0 SF (Lexical T)72 192 Q(ie-ins)-.18 E F0(Frequently)97 207.6 Q 3.18(,t)-.65 G .68(here are le)-3.18 F .68 (xical decisions which depend on the presence of v)-.15 F .68 (arious constructions in the)-.25 F 2.896(speci\214cation. F)72 219.6 R .396(or e)-.15 F .396(xample, the le)-.15 F .396(xical analyzer might w) -.15 F .396(ant to delete blanks normally)-.1 F 2.896(,b)-.65 G .396 (ut not within quot-)-3.096 F(ed strings.)72 231.6 Q (Or names might be entered into a symbol table in declarations, b)5 E (ut not in e)-.2 E(xpressions.)-.15 E .445(One w)97 247.2 R .445(ay of \ handling these situations is to create a global \215ag which is e)-.1 F .446(xamined by the le)-.15 F .446(xical ana-)-.15 F(lyzer)72 259.2 Q 2.505(,a)-.4 G .005(nd set by actions.)-2.505 F -.15(Fo)5.004 G 2.504 (re).15 G .004(xample, consider a situation where we ha)-2.654 F .304 -.15(ve a p)-.2 H .004(rogram which consists of 0 or).15 F .582 (more declarations, follo)72 271.2 R .582(wed by 0 or more statements.) -.25 F 2.182 -.8(We d)5.582 H .582(eclare a \215ag called `).8 F (`d\215ag')-.74 E .583(', which is 1 during)-.74 F (declarations, and 0 during statements.)72 283.2 Q 1.6 -.8(We m)5 H (ay do this as follo).8 E(ws:)-.25 E(%{)108 301.2 Q(int d\215ag ;)133 313.2 Q(%})108 325.2 Q(%%)108 337.2 Q(program :)108 349.2 Q 2.5 (decls stats)133 361.2 R(;)2.5 E(decls :)108 385.2 Q 2.5(=/)133 397.2 S 2.5(*e)-2.5 G(mpty */)-2.5 E({)133 409.2 Q(d\215ag = 1;)158 421.2 Q 2.5 (}|)133 433.2 S(decls declaration ;)133 445.2 Q(stats :)108 469.2 Q 2.5 (=/)133 481.2 S 2.5(*e)-2.5 G(mpty */)-2.5 E({)133 493.2 Q(d\215ag = 0;) 158 505.2 Q 2.5(}|)133 517.2 S(stats statement ;)133 529.2 Q -2.5 2.5 (... o)133 553.2 T(ther rules . . .)-2.5 E .512 (The \215ag d\215ag is no)72 571.2 R 3.011(ws)-.25 G .511 (et to zero when reading statements, and 1 when reading declarations,) -3.011 F/F2 10/Times-Italic@0 SF -.2(ex)3.011 G .511(cept for the).2 F <8c72>72 583.2 Q .178(st tok)-.1 F .178(en in the \214r)-.1 F .178 (st statement.)-.1 F F0 .178(This tok)5.178 F .179 (en must be seen by the parser before it can tell that the declaration) -.1 F .06(section has ended and the statements ha)72 595.2 R .36 -.15 (ve b)-.2 H -.15(eg).15 G 2.56(un. Frequently).15 F 2.56(,h)-.65 G -.25 (ow)-2.56 G -2.15 -.25(ev e).25 H .86 -.4(r, t).25 H .06(his single tok) .4 F .06(en e)-.1 F .06(xception does not)-.15 F(af)72 607.2 Q (fect the le)-.25 E(xical scan required.)-.15 E(Clearly)97 622.8 Q 2.652 (,t)-.65 G .152(his kind of `)-2.652 F(`backdoor')-.74 E 2.652('a)-.74 G .152(pproach can be elaborated on to a noxious de)-2.652 F 2.652 (gree. Ne)-.15 F -.15(ve)-.25 G .152(rtheless, it).15 F(represents a w) 72 634.8 Q(ay of doing some things that are dif)-.1 E (\214cult, if not impossible, to do otherwise.)-.25 E EP %%Page: 20 21 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3089>-2.5 G/F1 10/Times-Bold@0 SF(Bundling)72 108 Q F0 .397 (Bundling is a technique for collecting together v)97 123.6 R .397 (arious character strings so that the)-.25 F 2.897(yc)-.15 G .396 (an be output at)-2.897 F(some later time.)72 135.6 Q(It is deri)5 E -.15(ve)-.25 G 2.5(df).15 G (rom a feature of the same name in the compiler/compiler TMG [6].)-2.5 E .663(Bundling has tw)97 151.2 R 3.163(oc)-.1 G .663 (omponents \255 a nice user interf)-3.163 F .663(ace, and a cle)-.1 F -.15(ve)-.25 G 3.164(ri).15 G .664(mplementation trick.)-3.164 F(The) 5.664 E 3.164(yw)-.15 G(ill)-3.164 E(be discussed in that order)72 163.2 Q(.)-.55 E(The user interf)97 178.8 Q(ace consists of tw)-.1 E 2.5(or) -.1 G(outines, `)-2.5 E(`b)-.74 E(undle')-.2 E 2.5('a)-.74 G(nd `)-2.5 E (`bprint')-.74 E('.)-.74 E -.2(bu)108 196.8 S (ndle\( a1, a2, . . ., an \)).2 E .324(accepts a v)72 214.8 R .323 (ariable number of ar)-.25 F .323 (guments which are either character strings or b)-.18 F .323 (undles, and returns a b)-.2 F(undle,)-.2 E(whose v)72 226.8 Q (alue will be the concatenation of the v)-.25 E(alues of a1, . . ., an.) -.25 E(bprint\( b \))108 244.8 Q(accepts a b)72 262.8 Q(undle as ar)-.2 E(gument and outputs its v)-.18 E(alue.)-.25 E -.15(Fo)97 278.4 S 3.24 (re).15 G .74(xample, suppose that we wish to read arithmetic e)-3.39 F .741(xpressions, and output function calls to rou-)-.15 F (tines called `)72 290.4 Q(`add')-.74 E(', `)-.74 E(`sub')-.74 E(', `) -.74 E(`mul')-.74 E(', `)-.74 E(`di)-.74 E(v')-.25 E(', and `)-.74 E (`assign')-.74 E 2.5('. Thus,)-.74 F(we wish to translate)2.5 E 2.5 (a=b\255c)108 308.4 S(*d)-2.5 E(into)72 326.4 Q (assign\(a,sub\(b,mul\(c,d\)\)\))108 344.4 Q 2.854(AY)97 366 S .353 (acc speci\214cation \214le which does this is gi)-3.854 F -.15(ve)-.25 G 2.853(ni).15 G 2.853(nA)-2.853 G .353 (ppendix D; this includes an implementation of)-2.853 F(the b)72 378 Q (undle and bprint routines.)-.2 E 2.5(Ar)5 G(ule and action of the form) -2.5 E -.15(ex)108 396 S(pr:).15 E -.15(ex)133 408 S(pr \264+\264 e).15 E(xpr =)-.15 E({)133 420 Q($$ = b)158 432 Q (undle\( "add\(", $1, ",", $3, "\)" \);)-.2 E(})133 444 Q .009 (causes the returned v)72 462 R .009(alue of e)-.25 F .009 (xpr to be come a b)-.15 F .01(undle, whose v)-.2 F .01 (alue is the character string containing the de-)-.25 F .834 (sired function call.)72 474 R .834(Each N)5.834 F .834(AME tok)-.35 F .834(en has a v)-.1 F .833 (alue which is a pointer to the actual name which has been)-.25 F 2.87 (read. Finally)72 486 R 2.87(,w)-.65 G .37 (hen the entire input line has been read and the v)-2.87 F .371 (alue has been b)-.25 F .371(undled, the v)-.2 F .371(alue is written) -.25 F(out and the b)72 498 Q (undles and names are cleared, in preparation for the ne)-.2 E (xt input line.)-.15 E 1.478(Bundles are implemented as arrays of point\ ers, terminated by a zero pointer)97 513.6 R 6.478(.E)-.55 G 1.477 (ach pointer either)-6.478 F .945(points to a b)72 525.6 R .945 (undle or to a character string.)-.2 F .945(There is an array)5.945 F 3.445(,c)-.65 G(alled)-3.445 E/F2 10/Times-Italic@0 SF -.2(bu)3.445 G .946(ndle space).2 F(,)-.1 E F0 .946(which contains all the)3.446 F -.2 (bu)72 537.6 S(ndles.).2 E .349 (The implementation trick is to check the v)97 553.2 R .349 (alues of the pointers in b)-.25 F .349 (undles \255 if the pointer points into)-.2 F -.2(bu)72 565.2 S (ndle space, it is assumed to point to a b).2 E (undle; otherwise it is assumed to point to a character string.)-.2 E .508(The treatment of functions with a v)97 580.8 R .509 (ariable number of ar)-.25 F .509(guments, lik)-.18 F 3.009(eb)-.1 G .509(undle, is lik)-3.209 F .509(ely to dif)-.1 F .509(fer from)-.25 F (one implementation of C to another)72 592.8 Q(.)-.55 E .38 (In general, one may wish to ha)97 608.4 R .68 -.15(ve a s)-.2 H .379 (imple storage allocator which allocates and frees b).15 F .379 (undles, in or)-.2 F(-)-.2 E(der to handle situations where it is not a\ ppropriate to completely clear all of b)72 620.4 Q (undle space at one time.)-.2 E F1(Reser)72 644.4 Q -.1(ve)-.1 G 2.5(dW) .1 G(ords)-3.25 E F0 .676 (Some programming languages permit the user to use w)97 660 R .677 (ords lik)-.1 F 3.177(e`)-.1 G -1.95(`if ')-3.917 F .677 (', which are normally reserv)-.74 F(ed,)-.15 E .286(as label or v)72 672 R .286(ariable names, pro)-.25 F .286 (vided that such use does not con\215ict with the le)-.15 F -.05(ga)-.15 G 2.786(lu).05 G .286(se of these names in the)-2.786 F .473 (programming language.)72 684 R .474(This is e)5.473 F .474 (xtremely hard to do in the frame)-.15 F -.1(wo)-.25 G .474(rk of Y).1 F .474(acc, since it is dif)-1 F .474(\214cult to pass)-.25 F .438 (the required information to the le)72 696 R .437 (xical analyzer which tells it `)-.15 F .437 (`this instance of if is a k)-.74 F -.15(ey)-.1 G -.1(wo).15 G .437 (rd, and that in-).1 F .298(stance is a v)72 708 R(ariable')-.25 E 2.798 ('. The)-.74 F .298(user can mak)2.798 F 2.798(eas)-.1 G .299 (tab at it, using the mechanism described in the last subsection,)-2.798 F -.2(bu)72 720 S 2.5(ti).2 G 2.5(ti)-2.5 G 2.5(sd)-2.5 G(if)-2.5 E (\214cult.)-.25 E EP %%Page: 21 22 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3189>-2.5 G 3.279(An)97 108 S .779(umber of w)-3.279 F .778(ays of making this easi\ er are under advisement, and one will probably be supported)-.1 F -2.15 -.25(ev e)72 120 T(ntually).25 E 5.676(.U)-.65 G .676 (ntil this day comes, I suggest that the k)-5.676 F -.15(ey)-.1 G -.1 (wo).15 G .676(rds be).1 F/F1 10/Times-Italic@0 SF -.37(re)3.176 G (served;).37 E F0 .676(that is, be forbidden for use as)3.176 F -.25(va) 72 132 S(riable names.).25 E(There are po)5 E (werful stylistic reasons for preferring this, an)-.25 E(yw)-.15 E (ay \(he said weakly . . . \).)-.1 E/F2 10/Times-Bold@0 SF (Non-integer V)72 156 Q(alues)-.92 E F0(Frequently)97 171.6 Q 2.627(,t) -.65 G .127(he user wishes to ha)-2.627 F .427 -.15(ve v)-.2 H .126 (alues which are bigger than inte)-.1 F .126(gers; ag)-.15 F .126 (ain, this is an area where)-.05 F -1(Ya)72 183.6 S .474 (cc does not mak)1 F 2.974(et)-.1 G .475 (he job as easy as it might, and some additional support is lik)-2.974 F (ely)-.1 E 5.475(.N)-.65 G -2.15 -.25(ev e)-5.475 H .475 (rtheless, at the).25 F .248(cost of writing a storage manager)72 195.6 R 2.748(,t)-.4 G .247(he user can return pointers or indices to blocks \ of storage big enough to)-2.748 F(contain the full v)72 207.6 Q (alues desired.)-.25 E F2(Pr)72 231.6 Q -.15(ev)-.18 G(ious W).15 E(ork) -.75 E F0 .57(There ha)97 247.2 R .87 -.15(ve b)-.2 H .57(een man).15 F 3.07(yp)-.15 G(re)-3.07 E .571(vious applications of Y)-.25 F 3.071 (acc. The)-1 F .571(user who is contemplating a big applica-)3.071 F .982(tion might well \214nd that others ha)72 259.2 R 1.281 -.15(ve d) -.2 H -2.15 -.25(ev e).15 H .981(loped rele).25 F -.25(va)-.25 G .981 (nt techniques, or e).25 F -.15(ve)-.25 G 3.481(np).15 G .981 (ortions of grammars.)-3.481 F -1(Ya)5.981 G(cc)1 E .48 (speci\214cations appear to be easier to change than the equi)72 271.2 R -.25(va)-.25 G .481(lent computer programs, so that the `).25 F .481 (`prior art')-.74 F(')-.74 E(is more rele)72 283.2 Q -.25(va)-.25 G (nt here as well.).25 E F2(Section 8: User Experience, Summary)72 307.2 Q 2.5(,a)-.55 G(nd Ackno)-2.5 E(wledgements)-.1 E F0 -1(Ya)97 322.8 S .102(cc has been used in the construction of a C compiler for the Hone)1 F .102(ywell 6000, a system for typeset-)-.15 F .382 (ting mathematical equations, a lo)72 334.8 R 2.882(wl)-.25 G -2.15 -.25 (ev e)-2.882 H 2.883(li).25 G .383 (mplementation language for the PDP 11, APL and Basic compil-)-2.883 F (ers to run under the UNIX system, and a number of other applications.) 72 346.8 Q 2.676 -.8(To s)97 362.4 T 1.076(ummarize, Y).8 F 1.076(acc c\ an be used to construct parsers; these parsers can interact in a f)-1 F 1.075(airly \215e)-.1 F(xible)-.15 E -.1(wa)72 374.4 S 2.834(yw).1 G .334(ith the le)-2.834 F .335(xical analysis and output phases of a lar) -.15 F .335(ger system.)-.18 F .335(The system also pro)5.335 F .335 (vides an indication)-.15 F .051 (of ambiguities in the speci\214cation, and allo)72 386.4 R .051 (ws disambiguating rules to be supplied to resolv)-.25 F 2.55(et)-.15 G .05(hese ambigui-)-2.55 F(ties.)72 398.4 Q 1.058 (Because the output of Y)97 414 R 1.058(acc is lar)-1 F 1.058 (gely tables, the system is relati)-.18 F -.15(ve)-.25 G 1.058 (ly language independent.).15 F 1.058(In the)6.058 F 1.115 (presence of reasonable applications, Y)72 426 R 1.114 (acc could be modi\214ed or adapted to produce subroutines for other)-1 F .315(machines and languages.)72 438 R .315 (In addition, we continue to seek better algorithms to impro)5.315 F .616 -.15(ve t)-.15 H .316(he le).15 F .316(xical analysis)-.15 F (and code generation phases of compilers produced using Y)72 450 Q(acc.) -1 E .378(This document w)97 465.6 R .377 (ould be incomplete if I did not gi)-.1 F .677 -.15(ve c)-.25 H .377 (redit to a most stimulating collection of users,).15 F .626(who ha)72 477.6 R .926 -.15(ve g)-.2 H .627(oaded me be).15 F .627 (yond my inclination, and frequently be)-.15 F .627(yond my ability)-.15 F 3.127(,i)-.65 G 3.127(nt)-3.127 G .627(heir endless search for)-3.127 F -.74(``)72 489.6 S .216(one more feature').74 F 2.716('. Their)-.74 F .216(irritating unwillingness to learn ho)2.716 F 2.716(wt)-.25 G 2.716 (od)-2.716 G 2.715(ot)-2.716 G .215(hings my w)-2.715 F .215 (ay has usually led to my)-.1 F .64(doing things their w)72 501.6 R .64 (ay; most of the time, the)-.1 F 3.14(yh)-.15 G -2.25 -.2(av e)-3.14 H .641(been right.)3.34 F .641(B. W)5.641 F 3.141(.K)-.92 G .641 (ernighan, P)-3.391 F 3.141(.J)-1.11 G 3.141(.P)-3.141 G(lauger)-3.141 E 3.141(,S)-.4 G 3.141(.I)-3.141 G 3.141(.F)-3.141 G(eld-)-3.141 E 1.061 (man, C. Imagna, M. E. Lesk, and A. Sn)72 513.6 R 1.06 (yder will recognize some of their ideas in the current v)-.15 F 1.06 (ersion of)-.15 F -1(Ya)72 525.6 S 2.5(cc. Al)1 F(Aho also deserv)2.5 E (es recognition for bringing the mountain to Mohammed, and other f)-.15 E -.2(avo)-.1 G(rs.).2 E EP %%Page: 22 23 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3289>-2.5 G/F1 10/Times-Bold@0 SF(Refer)72 108 Q(ences)-.18 E F0 20(1A)72 123.6 S 2.101 (ho, A.V)-20 F 4.601(.a)-1.29 G 2.101(nd Johnson, S.C., `)-4.601 F 2.101 (`LR P)-.74 F(arsing')-.15 E 2.101(', Computing Surv)-.74 F -.15(ey)-.15 G 2.101(s, V).15 F 2.102(ol 6, No 2, June 1974, pp.)-1.29 F(99-124.)97 135.6 Q 20(2A)72 151.2 S .251(ho, A.V)-20 F .251 (., Johnson, S.C., and Ullman, J.D., `)-1.29 F .251(`Deterministic P) -.74 F .251(arsing of Ambiguous Grammars')-.15 F .25(', Pro-)-.74 F 1.419(ceedings of the A.C.M. Symposium on Principles of Programming Lan\ guages, October 1973, pp.)97 163.2 R(1-21; to appear in CA)97 175.2 Q (CM.)-.4 E 20(3A)72 190.8 S .862(ho, A.V)-20 F 3.362(.a)-1.29 G .862 (nd Ullman, J.D., Theory of P)-3.362 F .861(arsing, T)-.15 F .861 (ranslation, and Compiling.)-.35 F -1.29(Vo)5.861 G .861 (lume 1 \(1972\) and)1.29 F -1.29(Vo)97 202.8 S (lume 2 \(1973\), Prentice-Hall, Engle)1.29 E -.1(wo)-.25 G(od Clif).1 E (fs, N.J.)-.25 E 20(4K)72 218.4 S(ernighan, B. W)-20.25 E(., Ratfor)-.92 E 2.5(,aR)-.4 G(ational F)-2.5 E(ortran)-.15 E 20(5R)72 234 S(yder)-20 E 2.5(,B)-.4 G 2.5(.B)-2.5 G(., `)-2.5 E(`The PFOR)-.74 E 2.5(TV)-.6 G (eri\214er)-3.61 E -.7(,')-.4 G 2.5('S)-.04 G(oftw)-2.5 E (are\255Practice and Experience, V)-.1 E(ol 4 \(1974\), pp 359-377.) -1.29 E 20(6M)72 249.6 S(cIlro)-20 E 1.3 -.65(y, M)-.1 H 2.5(.D).65 G (., A Manual for the TMG Compiler)-2.5 E(-writing Language)-.2 E 20(7R) 72 265.2 S(itchie, D. M., C Reference Manual)-20 E EP %%Page: 23 24 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3389>-2.5 G/F1 10/Times-Bold@0 SF -.25(Ap)72 108 S(pendix A:).25 E 2.5(AS)5 G (imple Example)-2.5 E F0 .894(This e)97 123.6 R .894(xample gi)-.15 F -.15(ve)-.25 G 3.394(st).15 G .894(he complete Y)-3.394 F .894 (acc speci\214cation for a small desk calculator; the desk calculator)-1 F .219(has 26 re)72 135.6 R .219 (gisters, labeled a through z, and accepts arithmetic e)-.15 F .219 (xpressions made up of the operators +, \255, *, /,)-.15 F 2.836(%\()72 147.6 S .336 (mod operator\), & \(bitwise and\), | \(bitwise or\), and assignment.) -2.836 F .336(If an e)5.336 F .336(xpression is an assignment at the) -.15 F .077(top le)72 159.6 R -.15(ve)-.25 G .077(l, the v).15 F .076 (alue is not printed; otherwise it is.)-.25 F .076(As in C, an inte) 5.076 F .076(ger which be)-.15 F .076(gins with 0 \(zero\) is assumed) -.15 F(to be octal; otherwise, it is assumed to be decimal.)72 171.6 Q .342(As an e)97 187.2 R .342(xample of a Y)-.15 F .342 (acc speci\214cation, the desk calculator does a reasonable job of sho) -1 F .343(wing the w)-.25 F(ay)-.1 E 1.157 (that precedences and ambiguities are used, as well as sho)72 199.2 R 1.157(wing ho)-.25 F 3.656(ws)-.25 G 1.156(imple error reco)-3.656 F -.15(ve)-.15 G 1.156(ry operates.).15 F(The)6.156 E .092(major o)72 211.2 R -.15(ve)-.15 G .092(rsimpli\214cations are that the le).15 F .092 (xical analysis phase is much simpler than for most applications, and) -.15 F .613(the output is produced immediately)72 223.2 R 3.112(,l)-.65 G .612(ine by line.)-3.112 F .612(Note the w)5.612 F .612 (ay that decimal and octal inte)-.1 F .612(gers are read in)-.15 F (by the grammar rules; frequently)72 235.2 Q 2.5(,t)-.65 G (his job is better done by the le)-2.5 E(xical analyzer)-.15 E(.)-.55 E (%tok)72 277.2 Q(en DIGIT LETTER)-.1 E(/* these are tok).12 E (en names */)-.1 E(%left \264|\264)72 289.2 Q (/* declarations of operator precedences */)92.18 E(%left \264&\264)72 301.2 Q<256c65667420b42bb420b4adb4>72 313.2 Q <256c65667420b42ab420b42fb420b425b4>72 325.2 Q(%left UMINUS)72 337.2 Q (/* supplies precedence for unary minus */)61.4 E 109.37(%{ /*)72 349.2 R(declarations used by the actions */)2.5 E(int base;)97 361.2 Q(int re) 97 373.2 Q(gs[26];)-.15 E(%})72 385.2 Q 5(%% /*)72 409.2 R(be)2.5 E (ginning of rules section */)-.15 E(list :)72 433.2 Q (/* list is the start symbol */)32.49 E 23(|/)97 445.2 S 2.5(*e)-23 G (mpty */)-2.5 E(list stat \264\\n\264 |)97 457.2 Q (list error \264\\n\264 =)97 469.2 Q({)97 481.2 Q(yyerrok ;)122 493.2 Q 2.5(};)97 505.2 S(stat :)72 529.2 Q -.15(ex)97 541.2 S(pr =).15 E({)97 553.2 Q(printf\("%d\\n", $1\) ;)122 565.2 Q 2.5(}|)97 577.2 S (LETTER \264=\264 e)97 589.2 Q(xpr =)-.15 E({)97 601.2 Q(re)122 613.2 Q (gs[$1] = $3 ;)-.15 E 2.5(};)97 625.2 S -.15(ex)72 649.2 S(pr :).15 E 97 661.2 Q(xpr \264\)\264 =)-.15 E({)97 673.2 Q($$ = $2 ;) 122 685.2 Q 2.5(}|)97 697.2 S -.15(ex)97 709.2 S(pr \264+\264 e).15 E (xpr =)-.15 E({)97 721.2 Q EP %%Page: 24 25 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3489>-2.5 G ($$ = $1 + $3 ;)122 108 Q 2.5(}|)97 120 S -.15(ex)97 132 S <707220b4adb42065>.15 E(xpr =)-.15 E({)97 144 Q($$ = $1 \255 $3 ;)122 156 Q 2.5(}|)97 168 S -.15(ex)97 180 S(pr \264*\264 e).15 E(xpr =)-.15 E ({)97 192 Q($$ = $1 * $3 ;)122 204 Q 2.5(}|)97 216 S -.15(ex)97 228 S (pr \264/\264 e).15 E(xpr =)-.15 E({)97 240 Q($$ = $1 / $3 ;)122 252 Q 2.5(}|)97 264 S -.15(ex)97 276 S(pr \264%\264 e).15 E(xpr =)-.15 E({)97 288 Q($$ = $1 % $3 ;)122 300 Q 2.5(}|)97 312 S -.15(ex)97 324 S (pr \264&\264 e).15 E(xpr)-.15 E({)97 336 Q($$ = $1 & $3 ;)122 348 Q 2.5 (}|)97 360 S -.15(ex)97 372 S(pr \264|\264 e).15 E(xpr)-.15 E({)97 384 Q ($$ = $1 | $3 ;)122 396 Q 2.5(}|)97 408 S97 420 Q 2.5 (xpr %prec)-.15 F(UMINUS)2.5 E({)97 432 Q($$ = \255 $2 ;)122 444 Q 2.5 (}|)97 456 S(LETTER)97 468 Q({)97 480 Q($$ = re)122 492 Q(gs[$1] ;)-.15 E 2.5(}|)97 504 S(number ;)97 516 Q(number :)72 540 Q(DIGIT =)97 552 Q ({)97 564 Q($$ = $1 ;)122 576 Q(base = 10 ;)122 588 Q(if\( $1 == 0 \)) 122 600 Q(base = 8 ;)147 612 Q 2.5(}|)97 624 S(number DIGIT =)97 636 Q ({)97 648 Q($$ = base * $1 + $2 ;)122 660 Q 2.5(};)97 672 S 30.84(%% /*) 72 696 R(start of programs */)2.5 E(yyle)72 720 Q(x\( \) /* le)-.15 E (xaical analysis routine */)-.15 E EP %%Page: 25 26 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3589>-2.5 G({) 72 108 Q(/* returns LETTER for a lo)97 120 Q(wer case letter)-.25 E 2.5 (,y)-.4 G(ylv)-2.5 E(al = 0 through 25 */)-.25 E (/* return DIGIT for a digit, yylv)97 132 Q(al = 0 through 9 */)-.25 E (/* all other characters are returned immediately */)97 144 Q(int c ;)97 168 Q(while\( \(c=getchar\( \)\) == \264 \264 \))97 192 Q(;)122 204 Q (if\( c >= \264a\264 && c <= \264z\264 \) {)97 216 Q(yylv)122 228 Q (al = c \255 \264a\264 ;)-.25 E(return\( LETTER \) ;)122 240 Q(})97 252 Q(if\( c >= \2640\264 && c <= \2649\264 \) {)97 264 Q(yylv)122 276 Q (al = c \255 \2640\264 ;)-.25 E(return\( DIGIT \) ;)122 288 Q(})97 300 Q (return\( c \) ;)97 312 Q(})72 324 Q EP %%Page: 26 27 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3689>-2.5 G/F1 10/Times-Bold@0 SF -.25(Ap)72 108 S(pendix B: Use of Y).25 E (acc on Unix)-.85 E F0 .057(Suppose that the Y)97 123.6 R .057 (acc speci\214cation is on a \214le called y\214le.)-1 F .058 (If the actions are in C, Y)5.058 F .058(acc is in)-1 F -.2(vo)-.4 G -.1 (ke).2 G 2.558(db).1 G(y)-2.558 E(yacc y\214le)108 141.6 Q (The output appears on \214le y)72 159.6 Q(.tab)-.65 E(.c T)-.4 E 2.5 (oc)-.8 G(ompile the parser and load it with the Y)-2.5 E(acc library)-1 E 2.5(,u)-.65 G(se the command)-2.5 E(cc y)108 177.6 Q(.tab)-.65 E (.c \255ly)-.4 E(If Y)72 195.6 Q(acc is in)-1 E -.2(vo)-.4 G -.1(ke).2 G 2.5(dw).1 G(ith the option \255v:)-2.5 E(yacc \255v y\214le)108 213.6 Q 3.168(av)72 231.6 S .668 (erbose description of the parser is produced on \214le y)-3.318 F 3.168 (.output. The)-.65 F 3.168(Cu)3.168 G .667 (ser should consult section 6C for)-3.168 F (more information about the run time en)72 243.6 Q(vironment.)-.4 E (If the actions are in Ratfor)97 259.2 Q 2.5(,t)-.4 G(he user should in) -2.5 E -.2(vo)-.4 G .2 -.1(ke Y).2 H(acc with the option \255r:)-.9 E (yacc \255r y\214le)108 277.2 Q(The Ratfor output appears on \214le y)72 295.2 Q(.tab)-.65 E(.r It may be compiled by)-.4 E(rc \2552 y)108 313.2 Q(.tab)-.65 E(.r)-.4 E .374(Note that when Y)72 331.2 R .375(acc is use\ d to produce Ratfor programs, there is no need to load these programs w\ ith an)-1 F(y)-.15 E(library)72 343.2 Q(.)-.65 E (If the \255v action is also in)97 358.8 Q -.2(vo)-.4 G -.1(ke).2 G(d:) .1 E(yacc \255rv y\214le)108 376.8 Q 2.93(av)72 394.8 S .43 (erbose description of the parser is produced on \214le y)-3.08 F 2.929 (.output. The)-.65 F .429(Ratfor user should consult section 6R)2.929 F (for more information about the run time en)72 406.8 Q(vironment.)-.4 E F1 -.25(Ap)72 430.8 S(pendix C: Old F).25 E(eatur)-.25 E(es Supported b) -.18 E(ut not Encouraged)-.2 E F0 .213(This appendix mentions synon)97 446.4 R .213 (yms and features which are supported for historical continuity)-.15 F 2.713(,b)-.65 G .214(ut, for)-2.913 F -.25(va)72 458.4 S (rious reasons, are not encouraged.).25 E 15(1. Literals)72 474 R (may be delimited by double quotes `)2.5 E(`"')-.74 E 2.5('a)-.74 G 2.5 (sw)-2.5 G(ell as single quotes `)-2.5 E(`\264')-.74 E('.)-.74 E 15 (2. Literals)72 489.6 R .419(may be more than one character long.)2.919 F .4 LW 486.362 492.1 481.362 492.1 DL .419 (If all the characters are alphabetic, numeric, or)289.192 489.6 R 2.918 (,t)7.918 G(he)-2.918 E .024(type number of the literal is de\214ned, j\ ust as if the literal did not ha)97 501.6 R .324 -.15(ve t)-.2 H .024 (he quotes around it.).15 F(Otherwise,)5.024 E(it is dif)97 513.6 Q (\214cult to \214nd the v)-.25 E(alue for such literals.)-.25 E .884 (The use of multi-character literals is lik)97 529.2 R .883 (ely to mislead those unf)-.1 F .883(amiliar with Y)-.1 F .883 (acc, since it suggests)-1 F(that Y)97 541.2 Q (acc is doing a job which must be actually done by the le)-1 E (xical analyzer)-.15 E(.)-.55 E 15(3. Most)72 556.8 R .628 (places where % is le)3.128 F -.05(ga)-.15 G .628(l, backslash `).05 F (`\\')-.74 E 3.128('m)-.74 G .628(ay be used.)-3.128 F .629 (In particular)5.628 F 3.129(,\\)-.4 G 3.129(\\i)-3.129 G 3.129(st) -3.129 G .629(he same as %%, \\left)-3.129 F(the same as %left, etc.)97 568.8 Q 15(4. There)72 584.4 R(are a number of other synon)2.5 E(yms:) -.15 E(%< is the same as %left)133 602.4 Q(%> is the same as %right)133 614.4 Q(%binary and %2 are the same as %nonassoc)133 626.4 Q (%0 and %term are the same as %tok)133 638.4 Q(en)-.1 E (%= is the same as %prec)133 650.4 Q 15(5. The)72 672 R .215 (curly braces `)2.715 F(`{')-.74 E 2.715('a)-.74 G .214(nd `)-2.715 F (`}')-.74 E 2.714('a)-.74 G .214(round an action are optional if the ac\ tion consists of a single C state-)-2.714 F 2.5(ment. \(The)97 684 R 2.5 (ya)-.15 G(re al)-2.5 E -.1(wa)-.1 G(ys required in Ratfor\).).1 E EP %%Page: 27 28 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3789>-2.5 G/F1 10/Times-Bold@0 SF -.25(Ap)72 108 S(pendix D: An Example of Bundling).25 E F0 .278(The follo)97 123.6 R .278(wing program is an e)-.25 F .279 (xample of the technique of b)-.15 F .279(undling; this e)-.2 F .279 (xample is discussed in Sec-)-.15 F(tion 7.)72 135.6 Q(/* w)72 175.2 Q (arnings:)-.1 E 15(1. This)72 190.8 R -.1(wo)3.372 G .871 (rks on Unix; the handling of functions with a v).1 F .871 (ariable number of ar)-.25 F .871(guments is dif)-.18 F .871(ferent on) -.25 F(dif)97 202.8 Q(ferent systems.)-.25 E 15(2. A)72 218.4 R 1.714 (number of checks for array bounds ha)4.214 F 2.014 -.15(ve b)-.2 H 1.714(een left out to a).15 F -.2(vo)-.2 G 1.714 (id obscuring the basic ideas, b).2 F(ut)-.2 E (should be there in a practical program.)97 230.4 Q(*/)102 246 Q(%tok)72 288 Q(en N)-.1 E(AME)-.35 E(%right \264=\264)72 312 Q <256c65667420b42bb420b4adb4>72 324 Q(%left \264*\264 \264/\264)72 336 Q (%%)72 360 Q(lines :)72 384 Q 2.5(=/)97 396 S 2.5(*e)-2.5 G(mpty */)-2.5 E({)97 408 Q(bclear\( \) ;)122 420 Q 2.5(}|)97 432 S(lines e)97 444 Q (xpr \264\\n\264 =)-.15 E({)97 456 Q(bprint\( $2 \) ;)122 468 Q (printf\( "\\n" \) ;)122 480 Q(bclear\( \) ;)122 492 Q 2.5(}|)97 504 S (lines error \264\\n\264 =)97 516 Q({)97 528 Q(bclear\( \) ;)122 540 Q (yyerrok;)122 552 Q 2.5(};)97 564 S -.15(ex)72 588 S(pr :).15 E -.15(ex) 97 600 S(pr \264+\264 e).15 E(xpr =)-.15 E({)97 612 Q($$ = b)122 624 Q (undle\( "add\(", $1, ",", $3, "\)" \);)-.2 E 2.5(}|)97 636 S -.15(ex)97 648 S<707220b4adb42065>.15 E(xpr =)-.15 E({)97 660 Q($$ = b)122 672 Q (undle\( "sub\(", $1, ",", $3, "\)" \);)-.2 E 2.5(}|)97 684 S -.15(ex)97 696 S(pr \264*\264 e).15 E(xpr =)-.15 E({)97 708 Q($$ = b)122 720 Q (undle\( "mul\(", $1, ",", $3, "\)" \);)-.2 E EP %%Page: 28 29 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3889>-2.5 G 2.5 (}|)97 108 S -.15(ex)97 120 S(pr \264/\264 e).15 E(xpr =)-.15 E({)97 132 Q($$ = b)122 144 Q(undle\( "di)-.2 E(v\(", $1, ",", $3, "\)" \);)-.25 E 2.5(}|)97 156 S97 168 Q(xpr \264\)\264 =)-.15 E({)97 180 Q ($$ = $2;)122 192 Q 2.5(}|)97 204 S -.35(NA)97 216 S(ME \264=\264 e).35 E(xpr =)-.15 E($$ = b)122 228 Q (undle\( "assign\(", $1, ",", $3, "\)" \);)-.2 E 2.5(}|)97 240 S -.35 (NA)97 252 S(ME ;).35 E(%%)72 276 Q 18.06(#de\214ne nsize)72 300 R(200) 2.5 E 5.29(char names[nsize],)72 312 R(*nptr { names };)2.5 E 18.06 (#de\214ne bsize)72 336 R(500)2.5 E 11.94(int bspace[bsize],)72 348 R (*bptr { bspace };)2.5 E(yyle)72 372 Q(x\( \))-.15 E({)72 384 Q(int c;) 97 396 Q 2.5(c=g)97 420 S(etchar\( \);)-2.5 E(while\( c == \264 \264 \)) 97 432 Q 2.5(c=g)122 444 S(etchar\( \);)-2.5 E (if\( c>=\264a\264 && c<=\264z\264 \) {)97 456 Q(yylv)122 468 Q (al = nptr;)-.25 E (for\( ; c>=\264a\264 && c<=\264z\264; c=getchar\( \) \))122 480 Q (*nptr++ = c;)147 492 Q(ungetc\( c \);)122 504 Q(*nptr++ = \264\\0\264;) 122 516 Q(return\( N)122 528 Q(AME \);)-.35 E(})97 540 Q(return\( c \);) 97 552 Q(})72 564 Q(bclear\( \))72 588 Q({)72 600 Q(nptr = names;)97 636 Q(bptr = bspace;)97 648 Q(})72 660 Q -.2(bu)72 684 S (ndle\( a1,a2,a3,a4,a5 \)).2 E({)72 696 Q(int i, j, *p, *obp;)97 708 Q EP %%Page: 29 30 %%BeginPageSetup BP %%EndPageSetup /F0 10/Times-Roman@0 SF(-)0 12 Q 2.5<8932>275.5 60 S 2.5<3989>-2.5 G 2.5 (p=&)97 108 S(a1;)-2.5 E 2.5(i=n)97 120 S(ar)-2.5 E(gs\( \);)-.18 E (obp = bptr;)97 132 Q(for\( j=0; j=bspace && p< &bspace[bsize] \) /* b)97 276 Q(undle */)-.2 E (while\( *p != 0 \))122 288 Q(bprint\( *p++ \);)147 300 Q (else printf\( "%s",)97 312 Q 2.5(p\))5 G(;)-2.5 E(})72 324 Q EP %%Trailer end %%EOF