From 4f372f0f415ef6e04fbc305028d16bf6a89db5ae Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 17 Sep 2002 23:03:35 +0000 Subject: [PATCH] Initial checkin of burg documetnation files git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3786 91177308-0d34-0410-b5e6-96231b3b80d8 --- support/tools/Burg/Doc/Makefile | 84 +++++ support/tools/Burg/Doc/doc.aux | 50 +++ support/tools/Burg/Doc/doc.dvi | Bin 0 -> 29856 bytes support/tools/Burg/Doc/doc.log | 157 +++++++++ support/tools/Burg/Doc/doc.tex | 596 ++++++++++++++++++++++++++++++++ utils/Burg/Doc/Makefile | 84 +++++ utils/Burg/Doc/doc.aux | 50 +++ utils/Burg/Doc/doc.dvi | Bin 0 -> 29856 bytes utils/Burg/Doc/doc.log | 157 +++++++++ utils/Burg/Doc/doc.tex | 596 ++++++++++++++++++++++++++++++++ 10 files changed, 1774 insertions(+) create mode 100644 support/tools/Burg/Doc/Makefile create mode 100644 support/tools/Burg/Doc/doc.aux create mode 100644 support/tools/Burg/Doc/doc.dvi create mode 100644 support/tools/Burg/Doc/doc.log create mode 100644 support/tools/Burg/Doc/doc.tex create mode 100644 utils/Burg/Doc/Makefile create mode 100644 utils/Burg/Doc/doc.aux create mode 100644 utils/Burg/Doc/doc.dvi create mode 100644 utils/Burg/Doc/doc.log create mode 100644 utils/Burg/Doc/doc.tex diff --git a/support/tools/Burg/Doc/Makefile b/support/tools/Burg/Doc/Makefile new file mode 100644 index 00000000000..226210d6ca4 --- /dev/null +++ b/support/tools/Burg/Doc/Makefile @@ -0,0 +1,84 @@ +# $Id$ + +#CFLAGS = +#CFLAGS = -O +#CFLAGS = -O -DNOLEX +CFLAGS = -g -DDEBUG +#CFLAGS = -g -DNOLEX -DDEBUG + +SRCS = \ + be.c \ + burs.c \ + closure.c \ + delta.c \ + fe.c \ + item.c \ + lex.c \ + list.c \ + main.c \ + map.c \ + nonterminal.c \ + operator.c \ + pattern.c \ + plank.c \ + queue.c \ + rule.c \ + string.c \ + symtab.c \ + table.c \ + trim.c \ + zalloc.c + +BU_OBJS = \ + burs.o \ + closure.o \ + delta.o \ + item.o \ + list.o \ + map.o \ + nonterminal.o \ + operator.o \ + pattern.o \ + queue.o \ + rule.o \ + table.o \ + trim.o \ + zalloc.o + +FE_OBJS = \ + be.o \ + fe.o \ + lex.o \ + main.o \ + plank.o \ + string.o \ + symtab.o \ + y.tab.o + +all: test + +burg: $(BU_OBJS) $(FE_OBJS) + $(CC) -o burg $(CFLAGS) $(BU_OBJS) $(FE_OBJS) + +y.tab.c y.tab.h: gram.y + yacc -d gram.y + +clean: + rm -f *.o y.tab.h y.tab.c core burg *.aux *.log *.dvi sample sample.c tmp + +$(FE_OBJS): b.h +$(BU_OBJS): b.h +$(FE_OBJS): fe.h + +lex.o: y.tab.h + +doc.dvi: doc.tex + latex doc; latex doc + +test: burg sample.gr + ./burg -I sample.c && cc $(CFLAGS) -o sample sample.c && ./sample + ./burg -I sample.gr >tmp && cmp tmp sample.c + ./burg -I tmp && cmp tmp sample.c + ./burg -I -= tmp && cmp tmp sample.c diff --git a/support/tools/Burg/Doc/doc.aux b/support/tools/Burg/Doc/doc.aux new file mode 100644 index 00000000000..0f7c13f0208 --- /dev/null +++ b/support/tools/Burg/Doc/doc.aux @@ -0,0 +1,50 @@ +\relax +\bibstyle{alpha} +\citation{aho-twig-toplas} +\citation{appel-87} +\citation{balachandran-complang} +\citation{kron-phd} +\citation{hoffmann-jacm} +\citation{hatcher-popl} +\citation{chase-popl} +\citation{pelegri-popl} +\citation{pelegri-phd} +\citation{wilhelm-tr} +\citation{henry-budp} +\citation{fraser-henry-spe-91} +\citation{proebsting-91} +\@writefile{toc}{\contentsline {section}{\numberline {1}Overview}{1}} +\@writefile{toc}{\contentsline {section}{\numberline {2}Input}{1}} +\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces A Sample Tree Grammar}}{2}} +\newlabel{fig-tree-grammar}{{1}{2}} +\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces EBNF Grammar for Tree Grammars for {\sc Burg}\ }}{3}} +\newlabel{fig-grammar-grammar}{{2}{3}} +\@writefile{toc}{\contentsline {section}{\numberline {3}Output}{3}} +\citation{aho-johnson-dp-classic} +\citation{fraser-henry-spe-91} +\citation{henry-budp} +\citation{pelegri-phd} +\@writefile{toc}{\contentsline {section}{\numberline {4}Debugging}{6}} +\@writefile{toc}{\contentsline {section}{\numberline {5}Running {\sc Burg}\ }{6}} +\newlabel{sec-man-page}{{5}{6}} +\citation{pelegri-popl} +\citation{henry-budp} +\citation{balachandran-complang} +\citation{proebsting-91} +\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces A Diverging Tree Grammar}}{7}} +\newlabel{fig-diverge-grammar}{{3}{7}} +\@writefile{toc}{\contentsline {section}{\numberline {6}Acknowledgements}{7}} +\bibcite{aho-twig-toplas}{AGT89} +\bibcite{aho-johnson-dp-classic}{AJ76} +\bibcite{appel-87}{App87} +\bibcite{balachandran-complang}{BDB90} +\bibcite{wilhelm-tr}{BMW87} +\bibcite{chase-popl}{Cha87} +\bibcite{fraser-henry-spe-91}{FH91} +\bibcite{hatcher-popl}{HC86} +\bibcite{henry-budp}{Hen89} +\bibcite{hoffmann-jacm}{HO82} +\bibcite{kron-phd}{Kro75} +\bibcite{pelegri-phd}{PL87} +\bibcite{pelegri-popl}{PLG88} +\bibcite{proebsting-91}{Pro91} diff --git a/support/tools/Burg/Doc/doc.dvi b/support/tools/Burg/Doc/doc.dvi new file mode 100644 index 0000000000000000000000000000000000000000..3211f32c96d4c68f03737a23a53140b6be2ed1f0 GIT binary patch literal 29856 zcmb823!I!)efO8l1O%e3Rq#?oh+-1lU3PO1A(YL1Avco^pdrP{%(J^g=EgiTY?c_& zzG{6dyD~gwIfqoQxsg8FLXtybav{{H7YGqanGrTKi& zotg8T%m4f@zyIZ&=U4Mi`Cqqw{G7F2{7d}skIx$lu0F3=t(2;j^OpAY_4oFz?Co2A zasRTVeQ%=0DQfoL{doUw^Je|Pzc7wgYM{Q0g!S5DNP`I(O%-+FV;ube*Wwzno}7PWITZ%w z$;r1pqpORjuNoX2(6>V`8B(M5K`s|v-+sg254EO#YC2!3^e=rhJvMwTbsZ7JH_D{i`bLS28FcWnOnQw{qOJJTgcvU z+q=pE%u$Jq=*8jas%)4p7GM`QxvmF3zHWOelMRanw}!!J#j;g>ZZB@_`tXgHJX$Gc zGMA;p-Z7r+4Kh`ceDaQ6hyRhOf9eZsAK4hBgFM7@q^~ji{xxg*C-3Ne&A`OO@k>7W z@QypXo-sUZ+sRfQIMl!N2mO<^=WhGL&KqvI`HMmMhHNl4dGB+tf78VAy(Tzk9A7q5 zaP~@YKJkH(dh(4AA76CE&t5s+6}K_I?rUblC>52;#gTF-q^cu%n7!zf!ov~t-3Y+g^EI*t+ucseS2bzlpK*hno$tyygl zM4no)B!6-EadL7*Y4VUVdO zZ!c7eti9{`0HpXtbWZ zxg@>_%1rXj|J5-`@e(t;q4s2EV=9|V>De2yDV{GD8sqt5HH?n;eEYFW4z-xjX{f&G z;YulL4wsAhX!>9ZP1V~WHccC5h-IR-N=5}uXF42ZqZ9WGHy1F>bg6paq65|PNUy%` zeFa-o%wb9>1(L*Qn{c%J%cHiD9Vc~dx-&cp53meF>T6}eczq4T@ z&CG&K1I}q2zwmcmi!SbbsFLmPJDRRPS^99XumBoHDUHqK!=T2OCI`*6wdB+p;=G`q z9DH?N!at7kWI|CGh(Bcryf1P zfO)9iK#CZGkw=l7dh*s4UixA?mGQQzdn);*#bcw{H2XX%W#-n07Q_hVrA6+#Jf>Qd z8Ww(`UuMQEG7)sSpt-QSksW3tQvaeaAKA-Xs7-TIlknWYGH1@u577;gtk0m3Y3mmR z?!7lLhNx&n)R2Zs{g>z%*8wUJo1jTK8)cM~y*1nAD5PK0IS`AObWsRXG;YY2i-jJh z=vkMQ)<0}|Ejjt#c&vP*iYdEm zUcPHnEjd|fLUp&1h(R_qGf-)am$bK;U^oiL^9>oxV$SRs5Ta4cn(7o;i&2W{6r5G7 zC*SuqZ*9Zsfm+wpN3LW2wnS$7yS{ksSuy_&QSo3Dgf*U--nnbm1nW$2+rauw+ZLCW zG}-Rs;q*wZs-| zMlf!27ArPZ;Vey$aMD@^Ez+h8Kn-}{{G1-BC%Ss`tVitPI3Rx7z!@V9R}03!$a3JXHOnG7|R$)-jM0J>}%-UI@`F!FuOj(QSc1}E=0>pdA@@DE?~wf@P;o8>>w8!XJ}w()9g_(_?6&VC>P{r z^=teC)?@O+OzeUq`X9pwHC9;;M)a9=<+bR6FwBk=*7f6~VYpI-%DSb|=Ae=uUAHXS zT&$MYEswTWbL&<_yK>cV-AX-r0sn(ay0~`cO+)chwSB+2bDjF@j~4eW5y!+W)Jd)U zpIhzMrSY!&1#1p_>XnbvJ-yNh>Q8Xn<+1;{mCUe)zhhNwh9n z5x3=Wo2xBru|{4}yZj?}+k{p|i~DW5aU(|$Yvso6`Q0vSxyrS?<3;!@aAf_8uQwfN zkgD&$xRyM2Y#`d>AcL6?c|%*AcOrl8g?Rn~l1`1)6VdXf04M&jx3HmbmwJ`}C)LSsp<2c=0m3rc3g-^qe+GqKR>P`+D$P-HrHP0$u^*$wY&uvw#n$1um$E>BM!I;L=G^dj0Tk1SaT;+TgX)d` zzP`i!*VmAX08XwnZ0!xi5G@vV8uNL7*EIu$8c;)D0xdNk+nHI09zA*UM?4Z;8jWOu zH@47C>vwFf&Ab1TemZ7JTU22|O$}5}yy%X2zI1f|CI=K{airzfeO9AZK!Q$NR~lpT zOND2I`HTfU=Cjsf$<`BX6eL%*SP)z@IK%{C*JKx%8NjQ&A&YyO!}{GboC(rEbskW!3Ea`e#E4RZv|`}8Qjo;>Api#-4UAvQa@ zpp5->djL$Z3AKb0hYFvIZ2gjidff9Oi5poAN=2#4xj0|T|hLxc@SSgP|@r_B@rgcxU&l$%EO+gDG% z;|hgP790|li5nrgj-zVHAAVXGUSWoJTw%g+yQzq50p}O&5reOCl@JA*K=9a{^SEy? z<@av32ODgMeCu)+jMXtZzV{nfq3K3b1~`$hH?B&-h@h58GZ~ADQ+&l79O7f=ANmqY zi15e#0^~l$)M>~$Z=@Px-XamhES?%6!O6?2h3xg!pc{>EniB5MF^i)xeNcvn>&dbCXMRM7 z+BHpvYg9q-+A`rF*sh-V!98rw57Eh&q!{%IVTzxJGNHo%dT$p0iIhJzA32PRJeBYdW{qd0g(aSW|Kh*r8Yz z!@MBQV8NjXAJpm0(ICv;h}^<6`QFB+8(?mQNiIG+Duel>2LJvS2bc(b*rZ@rhl)RKFQZXksw#y+7%Ax)1~e6k9mXc4yZ3#6$MKCN|dfr@(K$hnq^YVy<4H5m}Lni#B*y+MHa@ig*?5_CyW+(#%_+0gOaqS zszm>hazg|_2PN5vm&$^nP&Edk5-5itLb$NC!#}7fu>_s9u(QikeB*Vka37l-#CscL zGVDW^M9F&%3HIa7x->D&=HMT;)DU{Q2f%yq=D`&|?Ka&c|p zk>4(Ij@%-7ay!~M2l}*INVFEIo5K+bx=_guXOWFX>lTsfbT|l)&}o2+Yv+7ycSk=q z_{EEi=rf+s9z~1RE@B}4Y0q7Bp_&KzQe`~4@S@IN7A>~%4OXf1kyM)K1px^Iv$xIcH1()hx19^Ue^H!r)h6R5>8_hr!k? z5iiU536_8P?2=&olQOS=TA;@gj0H#Cawwq#nTmuq2L zQZXPGRF6ecLST|9QY^X=jxk&&()=-p?aQnuCr?}^#Ny#CjwN}3^;g=W%ufUzVvV{R zehlmL9=iu7j**hZt<(4f!U{5hg@{^2rpZQhjWZT}T~huL=&#P|tp1bk(_ zphBI5I`S#=j}^2WyGu-9I;A}r^psnO%B9cO{FW94>0bP5( z%+8lLw-zfjuR4iVO3oQ;C^<}gsGhj?Lf56xws~5bOfDOe^-q50+@W}80!k1WvuJrr zNwu(s8Z!maMt>R+oY`Wo;$`OPIar)z8Ht&_kj8oPa|3uYqxk?fttU@AgRW;%gK^|Z z6C1U7Pd5sCH`+ z_ub(JS`WQbr(Kj9Byhl#4l*;!Q`n0G*-9Co%#YYuKMt|5^tlST;XXW0HbFM>%HY#G79RN_*~VqAjKYeU zCht%Mg;RJ_iNC*;sEcql0hjem#CI36{pZ~Po>x+FdtQ7LR(`fjusL6h>cUB|At6N+&(X3tgB&-71VOpR zFrv0A;IP^Ts9jGcKGs2S2NLH)a*5Xjk|Hb#!H%6hFM)A!`5BnIUG^52Y9a&6w zrJ|!FMRSCRAV~uXQYoGU?O#<-eD@pK0`!;bYdWB;XlGGbwi9|{p89fTB<59y^*x6p z*ou|F$;$F*7#G;_W|0xipRFg}a3t0%(9aW*{eXlIU5xPIV1{wxna#ZU+Zx(Bk#DIF z1Qa0*T6LtzUUe=@#w&}mF;0`kV^led7|IX49un4*KR&LmSYf=i{A#I1B4e)i&aL2Y zu|KSWAvj?)ho+?3!6#LUr_g0FQ)3tB7Y4SHDP|4deKTcb5C8c!zPp7|zlsMGfHh%g zx`z>>ED3SaNfe>)?!jwH<1W?{pT0Shg&GoE z2EZvOWGqbWB1<@BUp#w62BF9O6o;I;r6BY)VG04QAq zsWMQ>fDGTNU$KeI&e21y2+RO+w@X$U_j;1sq{3*ixJe1uVyHy(cs$*3i3|oaRbB*% zfOB3J&cu?YxnPvex{a2T2tgcDtk3)CqZT6x&h+WljKm5-t(4_yYfeR0APg0|>wXO^ z2XJB&4Kj%2E&C7~X<9|jD4*aFw1Xng76<~J0CPIs%4OcIOg=TY@|^!T(XIU5Yid85 zXj*{m-1l|T5AX$bq-J1fpP8`$Y0F4Qxaw36IWo0kr=lUmTyvDIbas!pHARz73Q=q9 zM=FQM-0K_>S0_a-^|Wi_=BB4udbcGI1NU-fgobw>~kJ!RPS+WNW7f`Mz9(+OS z02Lbrp<*>tOct8(*CFd*|`{NNc@6>5DD2K>ZdZcxny(1Plm}Vtc^O6JjbaADC8X@e3!~sfszT)rkgiN+1x66h#8%CdVptEq#;4}J^MhlIhZ}>o znRo2#>V?f8cb<(RE*&0`_o>2$Dhq7DQ56qad$RkZjZ76_Hqst6m4li8V*3CREa1`F zwt6yH+l)6=vOJ6u7zLof>C~1XG8DSSqaiq$tXTR0Me+s=@|y8;4zsjCOdwcHqp=j} z3KUX%B=%X7?)TX`9u0COjOT$We1XuJN-;beJ2~xH(_6=^)w*K`oC_CMEfD6CpD|6b zV1ABVD9^D%CpPLwS#-thg2}g?HBp+Fb`G_o8l>TI1I#}p7lW$N+~7^ ztGC#vCWdD>PR2w=lf~kxVo50@mEaCn>|6KI3P|j8i?`-|;@lSYrGlU%%L5Z>CtG9+7;V%sYu3xG=(yGXXTj+}PXhu~in31XE zBX1zMjEuKmmw6EG!533KWU=8Nk1FWkG65j>INo}c1;9wrw1*7(-JB0 z^2cH-;rj{V2s(e70!11#td~90q^`18_FERokyMiGQov-I6mwvgP*nJ*K}B?r>X68$^F!c zDBMY=<$AqUiG|-h!_MUHJrkUFN#1n3%dvrFvWJF50451VJGOj^MzRvD)D;Cwt2!)U zNW~%{T1TVP#l%OlAKEVFJ?3JP3cI&(GLF;W_2izj70@GH9Y$uctSVBQW9l3=VkBq< zH1rFuE|i0pjkFXSW?*@#^NLbz)`AIAK;Ah;cJ0Aucu}e+F8h_5c}E`yZ0~@%YsE?r z_y!09(FLx$8`EyjqNcA<@wO3IY~ERmYhYI%<#5l0{AoU`(ggp< z3014U$$8AccUgRm8Y*+#!BbZD6kTXAqfiO=?Wg|jaMat|8y%4r#DvxpU)tk`g)%bK znLt$)3eL7H!fd9HH@^FCT>vQ#uSK>B**Z8%QG4x493avB;>cui82Z}8rV^jM*{4dV z!cjHSR~{B~lMhi)$)sp*t_d3`aDD;{Yi^4|qGy(ywmyuPT7faa)+!HM zPY%B_jylSbce+5|#*4O9IDvN_gB<~h<-V4zUn|j4Ui{><8) z8IaFy(!p#doCO7)0tmFuLXneuuJ+nhqpJD7{Z1{k%t-X7;!uB-M|Q*I&sA0ozy4JZ z+Z`{`iE$j&lf0CD=pg!2H6w>-T+!aU_BN}WMuu4don96SiR+0Ue<+S#;4#Eed8rsQ z;527++Az{do1D6W&4QhK@=a2iDDnkxGMs2l;-SqE)xu)Wnjz7W_2eR%ZG31Ij`)DC z;0hp)@+N29m#7tl&$X%*qzgKk3_Hhd>eK^gO^e1Bu5ii*H@*P^#0a4| zn8PeK7bRNeqke{ivX;TZE-)|bf^fBkB3t0epr=f%f~SgKC@?ASX*R@PTT4v6TFdo( zD9^~$gGelH({3n|P0^y^8Wn^eJ9aWX8dBSYSBDxPJfbRwj$Bx05MsFxLd<_^L5PdAzguQ`iuR5ai%Z?=s=qs; z%(!vUh2Fx6km4w7?b6#u+!N=}X=mNvQia%D=62VF1_D%T2rr3fQk$vda`DVc>~1r- zGS`}jSbkJ~fYYL+X+ab=AFb9Erqb<&=;ydkscJvW{ZjcisMHv2(KwDv`sTQI$mroo1IVn!{tm_ z&supZ@@o`qb!3m3!gPDzQjz+O=dZl@mptz+H6=$a5}vsFS&J3@v-{mbeK$C4BydqN zvHEdAac^ZjgNY)Z9gXza{kA^WotR1t^->DUYgCUjH_5#t6>ObvX&^bwo?-7j`@Ek| zG>4>GcfTwadhdP43JY}tTxg|1+A~Ch5-7qwQfw0anqKJjtGVjtu9oqDls*A>xV#-l z%~T{~rC7>AZswq^E0r+?9FHj!)gF^TF5c_M7Ex>Os*(ImX9NXgOL6}ReHUJj-RKDW zxGJU|C3#@0RBnWm?j%7C@8ILjNM#BO5mZqrygfjmF>W455n`y8y#1nf60Du8i5@!C zWD;LHzvZ+=&G>{c@xR!9g&{+`;Jb{JOdZAEa_;BSraD^m(4krJAP!0m)sk=dsYQco zOox#dX^9;*{Po07UKWELRs~r3`@g}wC^U{WLnq4&xH|a%!MLWBQcKjiGkBOQm8yH> zXh9ejG*^%EPu=6)4;`9bV&V6gq8@*G&ykIZ;`5Q+orMZUO^nfW$MG1aD}#}1cML`S zkYM&tgopIg(m8$-lF@I==J<`=!L@#|(iC&FP{+T&h4tUr6$-$*Yzgr>j$11!CPb$YwO~NLUFB>no{yR#1rDTrdANm5K6_}oXRwy| zY_aL`;hxw1SweTNLOd_WT2K%`F8Crth9;I7cJT&>r<~7X5m)_WUb6!DvcHVlajMGz z2?|YqxA{vdR|v%|4wTC1q&b7_y_RB0@z#C&<*v+XU@WET?{WRirs>FbJ-PPZGy^?l z`ZWf(7Q)i6%)T>)R!gQfS+b7Qj*|TTXo9}BAko@?Ly2^hZlmb_MoFA;7ZY;sl9dE8 zER&2=!i!9OwSe}F%E}J^IwnW#9-W*L-ayWxg!Ax>6si>2w}0RAPGa;tC}NoXlZ7$1HSLT{#gDP}Sy*_+7N2y73zc|>J5KdAS9r*I z>QjT9YrlLF$Z0Mvq0`u{HQ)MwBzf|>n<8HOMgU_j_^2~VAhTkdxmg7Po{LOQVv8b= zD4e|aYywOjysl8KZC|l;vP^*8h0$jI))N-QIN3v;;?ju=-C!WnTxJFcj(phID1}Ff zJfUvt$Z?qt!PN-K$hAGv&Cu`reVmow*@meje|VA|u^_@G#t{f#*}oF3f|M4A8milQMbVYD%x zRr4})NgtYFK+wJs6J+$~(BJo=1NckJPe{7^f;UYq}n_bN52Ku3N4 zA1p98%aw=`Tq^kZ6(EgUXUGpIux2UY>vUA`WUDtGCGIdkyL_%Drg%6|fPB>$a?U2e zXWRam81=-y^Rz=qpVbIxn`ZD~e2g(Tq$^@tr-q{;?Wez;rd3DkgA?jd9U-EM$?J}v z2VZy6o|Q)ysj?!1#gSZCeeQX99QXUrPc}&{>lis>a*FJ4USSlM(Tb}dBR_<Fhv@`j-yde3=MT(;{K`LvMWH3cYD1sq%ew*_C;p{Nyj$S<+ z+HZD$f%>)dGUpk6zwYRg1q<*XQshg@Ba|+aHKS6Et5n=^Cd?fH2$w_hNo!q55|O*+ zVhUz#%^2Gu6kTG$2Z0m!MLlumPn*<5_Vt+Xy&T zcb{&BQm9t6YJ3}mi2ltpH=ry*-Y$sitwKCE;L8dJvzP#%%aisqsqv36+u<2^4oI?zB4(kK!AFJ!{K9Y0 z#xe>jRbL#E>tNFBbOWat*6?+XcS}vpyJ}wq>WWoDvda!#>kW&duhMKw%zs_%8`{LN~FN^0?Ih0 z7{j1KreNPa0z1}~#X#&=!Xy<1J%0DrA-Z!9Ct8Dr_$W>mNGy+3m~F{ z3)xat3sZGI;&|UrG__3jOguU}?Tdr$>c}mX<&qQ}&Q{B~ZnjmPEHbt!J*WPPsV?r> z9bX0|2HrQZ)!nsp?m1uCj|=44P_v3TP3%}tt~u)QkPgXF0WUxplg19;wJUwm(`sb6 z1TG>Q8;6)E4QG+ChDt${Acc&LmtKXSF)z|7kbL7GjFLBzIxd8i6doLJ?YJvvIbjR^ zRYPH=mOT8+Ojc(tMgoT`)LZA{1ffW4m=Z93E$?>5me-SoLW_6FLpE_S-LbyPDEBo| zS!NugSQoKf1>b^0qtt`aC-wN89JimP6NH6V{PKh>eDcm#)d?$Z<>ALD-Hrn)%b<`u z89Acbgv4v6Lvr4RdE%TJDH2YJ!49)9q@XZi5r4!TJvQriw2qxKkGD@5MxBYH5~WQB zW7m3O#c9Uzo+YI`9YdmMA9&WF3j>%>3BAlOT-Gn(j7Q16cnCA_q@USe@c}jrRS$Q^ zv7^}7D*eh*(R3rN_{1(Nwqru|vYCC;9VFL71-X(B2eF+Cqs;?|Q#FX+Zv(-;~#T&M}0}8I9 z629VQH^mOcIwq;x?u>f?7V@dH4Xg_|`D+lhB6pQ7Bh1vl~#%+>dBVt!# z*iZd)MHiob^sy8UJQ~>;+NwaDu+}LgBI^3$(V?hl%{Zi^s}I+^n=eTi7KJY{C)AI+ z>S>rkDx*c?Hv7p-wOy80mGyv6l??rNa`=hx;B4fs|5u|<+5N;%p#ph!<9aQbJ|mj;A|c^F@p2N zlI`#0Ke$b^r{e7Lc0%@4I_r>gBt5tl9k+e1g>U-n{zxluqrgA&H9(HKWUAtu8x%wGRCk+(*=!A^LamQldBUbwsyBKkqo!y3Aikv@y0V z(xbBvwZ@kcky}q3zl*y!5!*5;c}dAXy;)`&xRVt+hB9bZAC$Ax_wxjmPuT1W7<=fmo zpedJQ{HPm1{e7P2Km4BA*LM1QMqhH{OJ?5N$wawm2R$=${suR-^o(12bGHFV-QC2P zu9{pv1=dj)#K}E*dTN9!Pz<+u4`!n5`#28Y>ays%)ZQAST%`yH&`xKg0jpAC^n$im z3o*m7V>`90@m6{*NrTSq#3t)TbHQZIyW|Hcm31u(_g>ggd+elFtI!LP5o7s_ZaDMU zprIRaNDhEIE-4^o@i2?fsq=~_%9i+s<@&rQK55v1*_*pWG$183!oHt3XwC*6(HsY@ z0UcA-qi^aPuU_oXtak^=cE)YLNlNm;H`;i@|~0mXYC-@Boh;aGkl zBG8y_9JDj*Bb0*Ad+dNW3}Xb*P&z37oJ%8U`P^tc|Lhg&*lx4Odm!yAB}YxB=~cnhR44|2nX-94*U_w@Cz<_!?F(|ZO7 zLFEeM-7~?v42T-zO7{EaRVTKK^QaAEu z$?ikY0Xwz5u2y5&+|0E z3UwP+-B8MXv|?+}35NNLi`H`~1u-29BEUJ$*XHu`9A#0JXcN1W1L#sWHSgFh8(r{! zE9V=y|5V>xUK~}}Y%B36%)V6BR$|2Rjd(2Jf*<3xXuT@+ozQ}Kyb}6BD+uUS&csA> z-vA&;m;LWY0WX`(4dj4&nfm z2VaPI$;lPH(a?3I9w=-&J#!@H6x5Nw-HoYh6jR;xdAM09roN+ZWOt(v%&iy=+FtC~KrNt4LtzO*_Pq)B*)MNGJ{Cn9beo(TJ zW1aJVc^A@>mIK2P_8`p#VWzYc%f?ok&28o5+{s`+b?SKRai@-L3k&`nn`TZp#F+(= zcf+2Zq1`=wtNVIZuj*!xVEjOqWTv(8ww>KrvwD?Zg1Hp&5=f@pJ-$AbbLYI-MAR|? z<40e;u{YY@8*M~uWaOE7*6c+PLOT}AOi%m#PdC{y-G~cD?j9!@BfB1_9hfSSCsrm! zqUn2%ttVgK=a7c^WBx)8+anNx9YO%HwiuXU%J&_O^-3-Ip+{%1o+=R^{BHjWZCd}* zRfqeR_bG;?@zA$@@sjmg1i$3Vnb=LW->iNk4lk*IcbX7J-#g?vG{p@RP&wR!O=uGX zs)02|lH|r*1fXq^bfdj>Bn#p=bQUi!;wRo9QcJ%1vH>)EY{~4dA)&d}wnx}T(^s9_ zt~e#ij)#vjnI+FbSS$9%11f(Xa&3o{S60f2OYx7#1~cF6j<-(3qxWpySs&HQ<89Z{v2~4C(N=G>{_~u|&*J4X80c zzVlP-^RKxYT894krG0cS+~I~OfGYGq{rJO2_Y{XKV_fJfU;0(MbX5y}e-ylA)1eX} zY`u3W!YQiH|NK{%_7g(rYF39(2X{rN=F92=4z>)+@CywSGg3*(E?S*mA4%`m|Um+Nl}* zF@n$1F+CZdYoVy9%`l=*JbnK(Ig)u&rnlM7K&VX@c(oHbrPF9>oW|-kJ$*}i`j#s* zl9d^OL(FASMrEeI(unnO1DqERseFhO3-9^DkwM(qo(k_CQ=X&Wk#e?Y8!jxn2SNYuMKjmIjXU4u#eFj-ipO)wHzBgvfr6p3fBTqb z%=0$mClACkPM-DA){HS^2jNKub(TdQoXy!K8p{o5X*zti)!t`2{i*qE>HR11*#yxo z+&YsC+!Jx%iDdA*72=_6>-A0)TYSwKPZ@hU_f2p_(ixIJxUF}9;NMwKBls6zYAM6y zUZC{s??Ejx;7%_je*A@_o3p$r$F4KO{?!vf&n&H$2+ovNQwuJ?o^A3xgA|9SVDeqY zbGijdjD@ag%&pXxu33I~S>Ni}%)c71$7A+gdV!QDpy?CS;?$0R?>#eL0N6YAw3`Pg z!=fhAXz8wXkz(+dH-7ILhZo!6y|>{tl(f46BVybh_{Nx~rDCu+7TJb?u}X?vPcC(q z5+fRq64N1`j#mhFBNMV{9sIQh{`z%S*Y(freCMX#lzGb0Pi*Nrt?TrYWDHO8=D(A? xNpsGZXU_eq!MWchIp@nU=YFZ%-0zf{`}I_F->N_78w>xlt1G;I-naSp{{bte`N9AI literal 0 HcmV?d00001 diff --git a/support/tools/Burg/Doc/doc.log b/support/tools/Burg/Doc/doc.log new file mode 100644 index 00000000000..a224a4edf72 --- /dev/null +++ b/support/tools/Burg/Doc/doc.log @@ -0,0 +1,157 @@ +This is TeX, Version 3.14159 (Web2C 7.3.2) (format=latex 2000.8.30) 4 JUN 2001 13:20 +**doc +(doc.tex +LaTeX2e <2000/06/01> +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latex209.def +File: latex209.def 1998/05/13 v0.52 Standard LaTeX file + + + Entering LaTeX 2.09 COMPATIBILITY MODE + ************************************************************* + !!WARNING!! !!WARNING!! !!WARNING!! !!WARNING!! + + This mode attempts to provide an emulation of the LaTeX 2.09 + author environment so that OLD documents can be successfully + processed. It should NOT be used for NEW documents! + + New documents should use Standard LaTeX conventions and start + with the \documentclass command. + + Compatibility mode is UNLIKELY TO WORK with LaTeX 2.09 style + files that change any internal macros, especially not with + those that change the FONT SELECTION or OUTPUT ROUTINES. + + Therefore such style files MUST BE UPDATED to use + Current Standard LaTeX: LaTeX2e. + If you suspect that you may be using such a style file, which + is probably very, very old by now, then you should attempt to + get it updated by sending a copy of this error message to the + author of that file. + ************************************************************* + +\footheight=\dimen102 +\@maxsep=\dimen103 +\@dblmaxsep=\dimen104 +\@cla=\count79 +\@clb=\count80 +\mscount=\count81 +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/tracefnt.sty +Package: tracefnt 1997/05/29 v3.0j Standard LaTeX package (font tracing) +\tracingfonts=\count82 +LaTeX Info: Redefining \selectfont on input line 96. +) +\symbold=\mathgroup4 +\symsans=\mathgroup5 +\symtypewriter=\mathgroup6 +\symitalic=\mathgroup7 +\symsmallcaps=\mathgroup8 +\symslanted=\mathgroup9 +LaTeX Font Info: Redeclaring math alphabet \mathbf on input line 288. +LaTeX Font Info: Redeclaring math alphabet \mathsf on input line 289. +LaTeX Font Info: Redeclaring math alphabet \mathtt on input line 290. +LaTeX Font Info: Redeclaring math alphabet \mathit on input line 296. +LaTeX Info: Redefining \em on input line 306. +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latexsym.sty +Package: latexsym 1998/08/17 v2.2e Standard LaTeX package (lasy symbols) +\symlasy=\mathgroup10 +LaTeX Font Info: Overwriting symbol font `lasy' in version `bold' +(Font) U/lasy/m/n --> U/lasy/b/n on input line 42. +) +LaTeX Font Info: Redeclaring math delimiter \lgroup on input line 370. +LaTeX Font Info: Redeclaring math delimiter \rgroup on input line 372. +LaTeX Font Info: Redeclaring math delimiter \bracevert on input line 374. + +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/config/latex209.cf +g +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/rawfonts.sty +Compatibility mode: package `' requested, but `rawfonts' provided. +Package: rawfonts 1994/05/08 Low-level LaTeX 2.09 font compatibility + +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/somedefs.sty +Package: somedefs 1994/06/01 Toolkit for optional definitions +) +LaTeX Font Info: Try loading font information for U+lasy on input line 44. + (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/ulasy.fd +File: ulasy.fd 1998/08/17 v2.2eLaTeX symbol font definitions +)))) (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/article. +cls +Document Class: article 2000/05/19 v1.4b Standard LaTeX document class +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/size11.clo +File: size11.clo 2000/05/19 v1.4b Standard LaTeX file (size option) +) +\c@part=\count83 +\c@section=\count84 +\c@subsection=\count85 +\c@subsubsection=\count86 +\c@paragraph=\count87 +\c@subparagraph=\count88 +\c@figure=\count89 +\c@table=\count90 +\abovecaptionskip=\skip41 +\belowcaptionskip=\skip42 +Compatibility mode: definition of \rm ignored. +Compatibility mode: definition of \sf ignored. +Compatibility mode: definition of \tt ignored. +Compatibility mode: definition of \bf ignored. +Compatibility mode: definition of \it ignored. +Compatibility mode: definition of \sl ignored. +Compatibility mode: definition of \sc ignored. +LaTeX Info: Redefining \cal on input line 501. +LaTeX Info: Redefining \mit on input line 502. +\bibindent=\dimen105 +) +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/pstex/fullpage.sty +) (doc.aux) +\openout1 = `doc.aux'. + +LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <12> on input line 33. +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <8> on input line 33. +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <6> on input line 33. +LaTeX Font Info: Try loading font information for OMS+cmtt on input line 100 +. +LaTeX Font Info: No file OMScmtt.fd. on input line 100. +LaTeX Font Warning: Font shape `OMS/cmtt/m/n' undefined +(Font) using `OMS/cmsy/m/n' instead +(Font) for symbol `textbraceleft' on input line 100. + [1 + +] +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <10.95> on input line 150. + [2] [3] [4] [5] [6] +Overfull \hbox (1.38191pt too wide) in paragraph at lines 480--484 +[]\OT1/cmr/m/n/10.95 Emit code for \OT1/cmtt/m/n/10.95 burm[]arity\OT1/cmr/m/n/ +10.95 , \OT1/cmtt/m/n/10.95 burm[]child\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95 + burm[]cost\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95 burm[]ntname\OT1/cmr/m/n/10 +.95 , \OT1/cmtt/m/n/10.95 burm[]op[]label\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10. +95 burm[]opname\OT1/cmr/m/n/10.95 , + [] + +[7] [8] [9] (doc.aux) +LaTeX Font Warning: Some font shapes were not available, defaults substituted. + ) +Here is how much of TeX's memory you used: + 543 strings out of 12968 + 6147 string characters out of 289029 + 446019 words of memory out of 1453895 + 3433 multiletter control sequences out of 10000+10000 + 23403 words of font info for 87 fonts, out of 400000 for 2000 + 14 hyphenation exceptions out of 1000 + 21i,6n,20p,308b,283s stack positions out of 300i,100n,500p,50000b,4000s + +Output written on doc.dvi (9 pages, 29856 bytes). diff --git a/support/tools/Burg/Doc/doc.tex b/support/tools/Burg/Doc/doc.tex new file mode 100644 index 00000000000..3dc67be3176 --- /dev/null +++ b/support/tools/Burg/Doc/doc.tex @@ -0,0 +1,596 @@ +\documentstyle[11pt,fullpage]{article} +\begin{document} + +\def\AddSpace#1{\ifcat#1a\ \fi#1} % if next is a letter, add a space +\def\YACC#1{{\sc Yacc}\AddSpace#1} +\def\TWIG#1{{\sc Twig}\AddSpace#1} +\def\PROG#1{{\sc Burg}\AddSpace#1} +\def\PARSER#1{{\sc Burm}\AddSpace#1} +\def\CODEGEN#1{{\sc Codegen}\AddSpace#1} + +\title{{\sc Burg} --- Fast Optimal Instruction Selection and Tree Parsing} +\author{ +Christopher W. Fraser \\ +AT\&T Bell Laboratories \\ +600 Mountain Avenue 2C-464 \\ +Murray Hill, NJ 07974-0636 \\ +{\tt cwf@research.att.com} +\and +Robert R. Henry \\ +Tera Computer Company \\ +400 N. 34th St., Suite 300 \\ +Seattle, WA 98103-8600 \\ +{\tt rrh@tera.com} +\and +Todd A. Proebsting \\ +Dept. of Computer Sciences \\ +University of Wisconsin \\ +Madison, WI 53706 \\ +{\tt todd@cs.wisc.edu} +} +\date{December 1991} + +\maketitle +\bibliographystyle{alpha} +\newcommand\term[1]{{\it #1}} +\newcommand\secref[1]{\S\ref{#1}} +\newcommand\figref[1]{Figure~\ref{#1}} +% +% rationale table making +% +{\catcode`\^^M=13 \gdef\Obeycr{\catcode`\^^M=13 \def^^M{\\}}% +\gdef\Restorecr{\catcode`\^^M=5 }} % + +% +% for printing out options +% +\newcommand\option[1]{% #1=option character +{\tt -#1}% +} +\newcommand\var[1]{% +{\tt #1}% +} +\section{Overview} + +\PROG is a program that generates a fast tree parser using BURS +(Bottom-Up Rewrite System) technology. It accepts a cost-augmented +tree grammar and emits a C program that discovers in linear time an +optimal parse of trees in the language described by the grammar. \PROG +has been used to construct fast optimal instruction selectors for use +in code generation. \PROG addresses many of the problems addressed by +{\sc Twig}~\cite{aho-twig-toplas,appel-87}, but it is somewhat less flexible and +much faster. \PROG is available via anonymous \var{ftp} from +\var{kaese.cs.wisc.edu}. The compressed \var{shar} file +\var{pub/burg.shar.Z} holds the complete distribution. + +This document describes only that fraction of the BURS model that is +required to use \PROG. Readers interested in more detail might start +with Reference~\cite{balachandran-complang}. Other relevant documents +include References~\cite{kron-phd,hoffmann-jacm,hatcher-popl,chase-popl,pelegri-popl,pelegri-phd,wilhelm-tr,henry-budp,fraser-henry-spe-91,proebsting-91}. + +\section{Input} + +\PROG accepts a tree grammar and emits a BURS tree parser. +\figref{fig-tree-grammar} shows a sample grammar that implements a very +simple instruction selector. +\begin{figure} +\begin{verbatim} +%{ +#define NODEPTR_TYPE treepointer +#define OP_LABEL(p) ((p)->op) +#define LEFT_CHILD(p) ((p)->left) +#define RIGHT_CHILD(p) ((p)->right) +#define STATE_LABEL(p) ((p)->state_label) +#define PANIC printf +%} +%start reg +%term Assign=1 Constant=2 Fetch=3 Four=4 Mul=5 Plus=6 +%% +con: Constant = 1 (0); +con: Four = 2 (0); +addr: con = 3 (0); +addr: Plus(con,reg) = 4 (0); +addr: Plus(con,Mul(Four,reg)) = 5 (0); +reg: Fetch(addr) = 6 (1); +reg: Assign(addr,reg) = 7 (1); +\end{verbatim} +\caption{A Sample Tree Grammar\label{fig-tree-grammar}} +\end{figure} +\PROG grammars are structurally similar to \YACC's. Comments follow C +conventions. Text between ``\var{\%\{}'' and ``\var{\%\}}'' is called +the \term{configuration section}; there may be several such segments. +All are concatenated and copied verbatim into the head of the generated +parser, which is called \PARSER. Text after the second ``\var{\%\%}'', +if any, is also copied verbatim into \PARSER, at the end. + +The configuration section configures \PARSER for the trees being parsed +and the client's environment. This section must define +\var{NODEPTR\_TYPE} to be a visible typedef symbol for a pointer to a +node in the subject tree. \PARSER invokes \var{OP\_LABEL(p)}, +\var{LEFT\_CHILD(p)}, and \var{RIGHT\_CHILD(p)} to read the operator +and children from the node pointed to by \var{p}. It invokes +\var{PANIC} when it detects an error. If the configuration section +defines these operations as macros, they are implemented in-line; +otherwise, they must be implemented as functions. The section on +diagnostics elaborates on \var{PANIC}. + +\PARSER computes and stores a single integral \term{state} in each node +of the subject tree. The configuration section must define a macro +\var{STATE\_LABEL(p)} to access the state field of the node pointed to +by \var{p}. A macro is required because \PROG uses it as an lvalue. A +C \var{short} is usually the right choice; typical code generation +grammars require 100--1000 distinct state labels. + +The tree grammar follows the configuration section. +\figref{fig-grammar-grammar} gives an EBNF grammar for \PROG tree +grammars. +\begin{figure} +\begin{verbatim} +grammar: {dcl} '%%' {rule} + +dcl: '%start' Nonterminal +dcl: '%term' { Identifier '=' Integer } + +rule: Nonterminal ':' tree '=' Integer cost ';' +cost: /* empty */ +cost: '(' Integer { ',' Integer } ')' + +tree: Term '(' tree ',' tree ')' +tree: Term '(' tree ')' +tree: Term +tree: Nonterminal +\end{verbatim} +\caption{EBNF Grammar for Tree Grammars for \PROG\ \label{fig-grammar-grammar}} +\end{figure} +Comments, the text between ``\var{\%\{}'' and ``\var{\%\}}'', and the +text after the optional second ``\var{\%\%}'' are treated lexically, so +the figure omits them. In the EBNF grammar, quoted text must appear +literally, \var{Nonterminal} and \var{Integer} are self-explanatory, +and \var{Term} denotes an identifier previously declared as a +terminal. {\tt\{$X$\}} denotes zero or more instances of $X$. + +Text before the first ``\var{\%\%}'' declares the start symbol and the +terminals or operators in subject trees. All terminals must be +declared; each line of such declarations begins with \var{\%term}. +Each terminal has fixed arity, which \PROG infers from the rules using that terminal. +\PROG restricts terminals to have at most two children. Each terminal +is declared with a positive, unique, integral \term{external symbol +number} after a ``\var{=}''. \var{OP\_LABEL(p)} must return the valid +external symbol number for \var{p}. Ideally, external symbol numbers +form a dense enumeration. Non-terminals are not declared, but the +start symbol may be declared with a line that begins with +\var{\%start}. + +Text after the first ``\var{\%\%}'' declares the rules. A tree grammar +is like a context-free grammar: it has rules, non-terminals, +terminals, and a special start non-terminal. The right-hand side of a +rule, called the \term{pattern}, is a tree. Tree patterns appear in +prefix parenthesized form. Every non-terminal denotes a tree. A chain +rule is a rule whose pattern is another non-terminal. If no start +symbol is declared, \PROG uses the non-terminal defined by the first +rule. \PROG needs a single start symbol; grammars for which it is +natural to use multiple start symbols must be augmented with an +artificial start symbol that derives, with zero cost, the grammar's +natural start symbols. \PARSER will automatically select one +that costs least for any given tree. + +\PROG accepts no embedded semantic actions like \YACC's, because no one +format suited all intended applications. Instead, each rule has a +positive, unique, integral \term{external rule number}, after the +pattern and preceded by a ``\var{=}''. Ideally, external rule numbers +form a dense enumeration. \PARSER uses these numbers to report the +matching rule to a user-supplied routine, which must implement any +desired semantic action; see below. Humans may select these integers +by hand, but \PROG is intended as a \term{server} for building BURS +tree parsers. Thus some \PROG clients will consume a richer +description and translate it into \PROG's simpler input. + +Rules end with a vector of non-negative, integer costs, in parentheses +and separated by commas. If the cost vector is omitted, then all +elements are assumed to be zero. \PROG retains only the first four +elements of the list. The cost of a derivation is the sum of the costs +for all rules applied in the derivation. Arithmetic on cost vectors +treats each member of the vector independently. The tree parser finds +the cheapest parse of the subject tree. It breaks ties arbitrarily. +By default, \PROG uses only the \term{principal cost} of each cost +vector, which defaults to the first element, but options described +below provide alternatives. + +\section{Output} + +\PARSER traverses the subject tree twice. The first pass or +\term{labeller} runs bottom-up and left-to-right, visiting each node +exactly once. Each node is labeled with a state, a single number that +encodes all full and partial optimal pattern matches viable at that +node. The second pass or \term{reducer} traverses the subject tree +top-down. The reducer accepts a tree node's state label and a +\term{goal} non-terminal --- initially the root's state label and the +start symbol --- which combine to determine the rule to be applied at +that node. By construction, the rule has the given goal non-terminal +as its left-hand side. The rule's pattern identifies the subject +subtrees and goal non-terminals for all recursive visits. Here, a +``subtree'' is not necessarily an immediate child of the current node. +Patterns with interior operators cause the reducer to skip the +corresponding subject nodes, so the reducer may proceed directly to +grandchildren, great-grandchildren, and so on. On the other hand, +chain rules cause the reducer to revisit the current subject node, with +a new goal +non-terminal, so \term{x} is also regarded as a subtree of \term{x}. + +As the reducer visits (and possibly revisits) each node, user-supplied +code implements semantic action side effects and controls the order in +which subtrees are visited. The labeller is self-contained, but the +reducer combines code from \PROG with code from the user, so \PARSER +does not stand alone. + +The \PARSER that is generated by \PROG provides primitives for +labelling and reducing trees. These mechanisms are a compromise +between expressibility, abstraction, simplicity, flexibility and +efficiency. Clients may combine primitives into labellers and reducers +that can traverse trees in arbitrary ways, and they may call semantic +routines when and how they wish during traversal. Also, \PROG +generates a few higher level routines that implement common +combinations of primitives, and it generates mechanisms that help debug +the tree parse. + +\PROG generates the labeller as a function named \var{burm\_label} with +the signature +\begin{verbatim} +extern int burm_label(NODEPTR_TYPE p); +\end{verbatim} +It labels the entire subject tree pointed to by \var{p} and returns the +root's state label. State zero labels unmatched trees. The trees may +be corrupt or merely inconsistent with the grammar. + +The simpler \var{burm\_state} is \var{burm\_label} without the +code to traverse the tree and to read and write its fields. It may be +used to integrate labelling into user-supplied traversal code. A +typical signature is +\begin{verbatim} +extern int burm_state(int op, int leftstate, int rightstate); +\end{verbatim} +It accepts an external symbol number for a node and the labels for the +node's left and right children. It returns the state label to assign +to that node. For unary operators, the last argument is ignored; for +leaves, the last two arguments are ignored. In general, \PROG +generates a \var{burm\_state} that accepts the maximum number of child +states required by the input grammar. For example, if the grammar +includes no binary operators, then \var{burm\_state} will have the +signature +\begin{verbatim} +extern int burm_state(int op, int leftstate); +\end{verbatim} +This feature is included to permit future expansion to operators with +more than two children. + +The user must write the reducer, but \PARSER writes code and data that +help. Primary is +\begin{verbatim} +extern int burm_rule(int state, int goalnt); +\end{verbatim} +which accepts a tree's state label and a goal non-terminal and returns the +external rule number of a rule. The rule will have matched the tree +and have the goal non-terminal on the left-hand side; \var{burm\_rule} +returns zero when the tree labelled with the given state did not match +the goal non-terminal. For the initial, root-level call, \var{goalnt} +must be one, and \PARSER exports an array that identifies the values +for nested calls: +\begin{verbatim} +extern short *burm_nts[] = { ... }; +\end{verbatim} +is an array indexed by external rule numbers. Each element points to a +zero-terminated vector of short integers, which encode the goal +non-terminals for that rule's pattern, left-to-right. The user needs +only these two externals to write a complete reducer, but a third +external simplifies some applications: +\begin{verbatim} +extern NODEPTR_TYPE *burm_kids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]); +\end{verbatim} +accepts the address of a tree \var{p}, an external rule number, and an +empty vector of pointers to trees. The procedure assumes that \var{p} +matched the given rule, and it fills in the vector with the subtrees (in +the sense described above) of \var{p} that must be reduced recursively. +\var{kids} is returned. It is not zero-terminated. + +The simple user code below labels and then fully reduces a subject tree; +the reducer prints the tree cover. \var{burm\_string} is defined below. +\begin{verbatim} +parse(NODEPTR_TYPE p) { + burm_label(p); /* label the tree */ + reduce(p, 1, 0); /* and reduce it */ +} + +reduce(NODEPTR_TYPE p, int goalnt, int indent) { + int eruleno = burm_rule(STATE_LABEL(p), goalnt); /* matching rule number */ + short *nts = burm_nts[eruleno]; /* subtree goal non-terminals */ + NODEPTR_TYPE kids[10]; /* subtree pointers */ + int i; + + for (i = 0; i < indent; i++) + printf("."); /* print indented ... */ + printf("%s\n", burm_string[eruleno]); /* ... text of rule */ + burm_kids(p, eruleno, kids); /* initialize subtree pointers */ + for (i = 0; nts[i]; i++) /* traverse subtrees left-to-right */ + reduce(kids[i], nts[i], indent+1); /* and print them recursively */ +} +\end{verbatim} +The reducer may recursively traverse subtrees in any order, and it may +interleave arbitrary semantic actions with recursive traversals. +Multiple reducers may be written, to implement multi-pass algorithms +or independent single-pass algorithms. + +For each non-terminal $x$, \PROG emits a preprocessor directive to +equate \var{burm\_}$x$\var{\_NT} with $x$'s integral encoding. It also +defines a macro \var{burm\_}$x$\var{\_rule(a)} that is equivalent to +\var{burm\_rule(a,}$x$\var{)}. For the grammar in +\figref{fig-tree-grammar}, \PROG emits +\begin{verbatim} +#define burm_reg_NT 1 +#define burm_con_NT 2 +#define burm_addr_NT 3 +#define burm_reg_rule(a) ... +#define burm_con_rule(a) ... +#define burm_addr_rule(a) ... +\end{verbatim} +Such symbols are visible only to the code after the second +``\var{\%\%}''. If the symbols \var{burm\_}$x$\var{\_NT} are needed +elsewhere, extract them from the \PARSER source. + +The \option{I} option directs \PROG to emit an encoding of the input +that may help the user produce diagnostics. The vectors +\begin{verbatim} +extern char *burm_opname[]; +extern char burm_arity[]; +\end{verbatim} +hold the name and number of children, respectively, for each terminal. +They are indexed by the terminal's external symbol number. The vectors +\begin{verbatim} +extern char *burm_string[]; +extern short burm_cost[][4]; +\end{verbatim} +hold the text and cost vector for each rule. They are indexed by the +external rule number. The zero-terminated vector +\begin{verbatim} +extern char *burm_ntname[]; +\end{verbatim} +is indexed by \var{burm\_}$x$\var{\_NT} and holds the name of +non-terminal $x$. Finally, the procedures +\begin{verbatim} +extern int burm_op_label(NODEPTR_TYPE p); +extern int burm_state_label(NODEPTR_TYPE p); +extern NODEPTR_TYPE burm_child(NODEPTR_TYPE p, int index); +\end{verbatim} +are callable versions of the configuration macros. +\var{burm\_child(p,0)} implements \var{LEFT\_CHILD(p)}, and +\var{burm\_child(p,1)} implements \var{RIGHT\_CHILD(p)}. A sample use +is the grammar-independent expression +\var{burm\_opname[burm\_op\_label(p)]}, which yields the textual name +for the operator in the tree node pointed to by \var{p}. + +A complete tree parser can be assembled from just \var{burm\_state}, +\var{burm\_rule}, and \var{burm\_nts}, which use none of the +configuration section except \var{PANIC}. The generated routines that +use the rest of the configuration section are compiled only if the +configuration section defines \var{STATE\_LABEL}, so they can be +omitted if the user prefers to hide the tree structure from \PARSER. +This course may be wise if, say, the tree structure is defined in a +large header file with symbols that might collide with \PARSER's. + +\PARSER selects an optimal parse without dynamic programming at compile +time~\cite{aho-johnson-dp-classic}. Instead, \PROG does the dynamic +programming at compile-compile time, as it builds \PARSER. +Consequently, \PARSER parses quickly. Similar labellers have taken as +few as 15 instructions per node, and reducers as few as 35 per node +visited~\cite{fraser-henry-spe-91}. + +\section{Debugging} + +\PARSER invokes \var{PANIC} when an error prevents it from proceeding. +\var{PANIC} has the same signature as \var{printf}. It should pass its +arguments to \var{printf} if diagnostics are desired and then either +abort (say via \var{exit}) or recover (say via \var{longjmp}). If it +returns, \PARSER aborts. Some errors are not caught. + +\PROG assumes a robust preprocessor, so it omits full consistency +checking and error recovery. \PROG constructs a set of states using a +closure algorithm like that used in LR table construction. \PROG +considers all possible trees generated by the tree grammar and +summarizes infinite sets of trees with finite sets. The summary +records the cost of those trees but actually manipulates the +differences in costs between viable alternatives using a dynamic +programming algorithm. Reference~\cite{henry-budp} elaborates. + +Some grammars derive trees whose optimal parses depend on arbitrarily +distant data. When this happens, \PROG and the tree grammar +\term{cost diverge}, and \PROG attempts to build an infinite +set of states; it first thrashes and ultimately exhausts +memory and exits. For example, the tree grammar in +\figref{fig-diverge-grammar} +\begin{figure} +\begin{verbatim} +%term Const=17 RedFetch=20 GreenFetch=21 Plus=22 +%% +reg: GreenFetch(green_reg) = 10 (0); +reg: RedFetch(red_reg) = 11 (0); + +green_reg: Const = 20 (0); +green_reg: Plus(green_reg,green_reg) = 21 (1); + +red_reg: Const = 30 (0); +red_reg: Plus(red_reg,red_reg) = 31 (2); +\end{verbatim} +\caption{A Diverging Tree Grammar\label{fig-diverge-grammar}} +\end{figure} +diverges, since non-terminals \var{green\_reg} and \var{red\_reg} +derive identical infinite trees with different costs. If the cost of +rule 31 is changed to 1, then the grammar does not diverge. + +Practical tree grammars describing instruction selection do not +cost-diverge because infinite trees are derived from non-terminals +that model temporary registers. Machines can move data between +different types of registers for a small bounded cost, and the rules +for these instructions prevent divergence. For example, if +\figref{fig-diverge-grammar} included rules to move data between red +and green registers, the grammar would not diverge. If a bonafide +machine grammar appears to make \PROG loop, try a host with more +memory. To apply \PROG to problems other than instruction selection, +be prepared to consult the literature on +cost-divergence~\cite{pelegri-phd}. + +\section{Running \PROG\ }\label{sec-man-page} + +\PROG reads a tree grammar and writes a \PARSER in C. \PARSER can be +compiled by itself or included in another file. When suitably named +with the \option{p} option, disjoint instances of \PARSER should link +together without name conflicts. The command: +\begin{flushleft} +\var{burg} [ {\it arguments} ] [ {\it file} ] +\end{flushleft} +invokes \PROG. If a {\it file} is named, \PROG expects its grammar +there; otherwise it reads the standard input. The options include: +\def\Empty{} +% +\newcommand\odescr[2]{% #1=option character, #2=optional argument +\gdef\Arg2{#2}% +\item[\option{#1}\ifx\Arg2\Empty\else{{\it #2}}\fi] +} +\begin{description} +% +\odescr{c}{} $N$ +Abort if any relative cost exceeds $N$, which keeps \PROG from looping on +diverging grammars. Several +references~\cite{pelegri-popl,henry-budp,balachandran-complang,proebsting-91} +explain relative costs. +% +\odescr{d}{} +Report a few statistics and flag unused rules and terminals. +% +\odescr{o}{} {\it file} +Write parser into {\it file}. Otherwise it writes to the standard output. +% +\odescr{p}{} {\it prefix} +Start exported names with {\it prefix}. The default is \var{burm}. +% +\odescr{t}{} +Generates smaller tables faster, but all goal non-terminals passed to +\var{burm\_rule} must come from an appropriate \var{burm\_nts}. Using +\var{burm\_}$x$\var{\_NT} instead may give unpredictable results. +% +\odescr{I}{} +Emit code for \var{burm\_arity}, \var{burm\_child}, \var{burm\_cost}, +\var{burm\_ntname}, \var{burm\_op\_label}, \var{burm\_opname}, +\var{burm\_state\_label}, and \var{burm\_string}. +% +\odescr{O}{} $N$ +Change the principal cost to $N$. Elements of each cost vector are +numbered from zero. +% +\odescr{=}{} +Compare costs lexicographically, using all costs in the given order. +This option slows \PROG and may produce a larger parser. Increases +range from small to astronomical. +\end{description} + +\section{Acknowledgements} + +The first \PROG was adapted by the second author from his \CODEGEN +package, which was developed at the University of Washington with +partial support from NSF Grant CCR-88-01806. It was unbundled from +\CODEGEN with the support of Tera Computer. The current \PROG was +written by the third author with the support of NSF grant +CCR-8908355. The interface, documentation, and testing involved +all three authors. + +Comments from a large group at the 1991 Dagstuhl Seminar on Code +Generation improved \PROG's interface. Robert Giegerich and Susan +Graham organized the workshop, and the International Conference and +Research Center for Computer Science, Schloss Dagstuhl, provided an +ideal environment for such collaboration. Beta-testers included Helmut +Emmelmann, Dave Hanson, John Hauser, Hugh Redelmeier, and Bill Waite. + +\begin{thebibliography}{BMW87} + +\bibitem[AGT89]{aho-twig-toplas} +Alfred~V. Aho, Mahadevan Ganapathi, and Steven W.~K. Tjiang. +\newblock Code generation using tree matching and dynamic programming. +\newblock {\em ACM Transactions on Programming Languages and Systems}, + 11(4):491--516, October 1989. + +\bibitem[AJ76]{aho-johnson-dp-classic} +Alfred~V. Aho and Steven~C. Johnson. +\newblock Optimal code generation for expression trees. +\newblock {\em Journal of the ACM}, 23(3):458--501, July 1976. + +\bibitem[App87]{appel-87} +Andrew~W. Appel. +\newblock Concise specification of locally optimal code generators. +\newblock Technical report CS-TR-080-87, Princeton University, 1987. + +\bibitem[BDB90]{balachandran-complang} +A.~Balachandran, D.~M. Dhamdhere, and S.~Biswas. +\newblock Efficient retargetable code generation using bottom-up tree pattern + matching. +\newblock {\em Computer Languages}, 15(3):127--140, 1990. + +\bibitem[BMW87]{wilhelm-tr} +J\"{u}rgen B\"{o}rstler, Ulrich M\"{o}nche, and Reinhard Wilhelm. +\newblock Table compression for tree automata. +\newblock Technical Report Aachener Informatik-Berichte No. 87-12, RWTH Aachen, + Fachgruppe Informatik, Aachen, Fed. Rep. of Germany, 1987. + +\bibitem[Cha87]{chase-popl} +David~R. Chase. +\newblock An improvement to bottom up tree pattern matching. +\newblock {\em Fourteenth Annual ACM Symposium on Principles of Programming + Languages}, pages 168--177, January 1987. + +\bibitem[FH91]{fraser-henry-spe-91} +Christopher~W. Fraser and Robert~R. Henry. +\newblock Hard-coding bottom-up code generation tables to save time and space. +\newblock {\em Software---Practice\&Experience}, 21(1):1--12, January 1991. + +\bibitem[HC86]{hatcher-popl} +Philip~J. Hatcher and Thomas~W. Christopher. +\newblock High-quality code generation via bottom-up tree pattern matching. +\newblock {\em Thirteenth Annual ACM Symposium on Principles of Programming + Languages}, pages 119--130, January 1986. + +\bibitem[Hen89]{henry-budp} +Robert~R. Henry. +\newblock Encoding optimal pattern selection in a table-driven bottom-up + tree-pattern matcher. +\newblock Technical Report 89-02-04, University of Washington Computer Science + Department, Seattle, WA, February 1989. + +\bibitem[HO82]{hoffmann-jacm} +Christoph Hoffmann and Michael~J. O'Donnell. +\newblock Pattern matching in trees. +\newblock {\em Journal of the ACM}, 29(1):68--95, January 1982. + +\bibitem[Kro75]{kron-phd} +H.~H. Kron. +\newblock {\em Tree Templates and Subtree Transformational Grammars}. +\newblock PhD thesis, UC Santa Cruz, December 1975. + +\bibitem[PL87]{pelegri-phd} +Eduardo Pelegri-Llopart. +\newblock {\em Tree Transformations in Compiler Systems}. +\newblock PhD thesis, UC Berkeley, December 1987. + +\bibitem[PLG88]{pelegri-popl} +Eduardo Pelegri-Llopart and Susan~L. Graham. +\newblock Optimal code generation for expression trees: An application of + {BURS} theory. +\newblock {\em Fifteenth Annual ACM Symposium on Principles of Programming + Languages}, pages 294--308, January 1988. + +\bibitem[Pro91]{proebsting-91} +Todd~A. Proebsting. +\newblock Simple and efficient {BURS} table generation. +\newblock Technical report, Department of Computer Sciences, University of + Wisconsin, 1991. + +\end{thebibliography} + +\end{document} + diff --git a/utils/Burg/Doc/Makefile b/utils/Burg/Doc/Makefile new file mode 100644 index 00000000000..226210d6ca4 --- /dev/null +++ b/utils/Burg/Doc/Makefile @@ -0,0 +1,84 @@ +# $Id$ + +#CFLAGS = +#CFLAGS = -O +#CFLAGS = -O -DNOLEX +CFLAGS = -g -DDEBUG +#CFLAGS = -g -DNOLEX -DDEBUG + +SRCS = \ + be.c \ + burs.c \ + closure.c \ + delta.c \ + fe.c \ + item.c \ + lex.c \ + list.c \ + main.c \ + map.c \ + nonterminal.c \ + operator.c \ + pattern.c \ + plank.c \ + queue.c \ + rule.c \ + string.c \ + symtab.c \ + table.c \ + trim.c \ + zalloc.c + +BU_OBJS = \ + burs.o \ + closure.o \ + delta.o \ + item.o \ + list.o \ + map.o \ + nonterminal.o \ + operator.o \ + pattern.o \ + queue.o \ + rule.o \ + table.o \ + trim.o \ + zalloc.o + +FE_OBJS = \ + be.o \ + fe.o \ + lex.o \ + main.o \ + plank.o \ + string.o \ + symtab.o \ + y.tab.o + +all: test + +burg: $(BU_OBJS) $(FE_OBJS) + $(CC) -o burg $(CFLAGS) $(BU_OBJS) $(FE_OBJS) + +y.tab.c y.tab.h: gram.y + yacc -d gram.y + +clean: + rm -f *.o y.tab.h y.tab.c core burg *.aux *.log *.dvi sample sample.c tmp + +$(FE_OBJS): b.h +$(BU_OBJS): b.h +$(FE_OBJS): fe.h + +lex.o: y.tab.h + +doc.dvi: doc.tex + latex doc; latex doc + +test: burg sample.gr + ./burg -I sample.c && cc $(CFLAGS) -o sample sample.c && ./sample + ./burg -I sample.gr >tmp && cmp tmp sample.c + ./burg -I tmp && cmp tmp sample.c + ./burg -I -= tmp && cmp tmp sample.c diff --git a/utils/Burg/Doc/doc.aux b/utils/Burg/Doc/doc.aux new file mode 100644 index 00000000000..0f7c13f0208 --- /dev/null +++ b/utils/Burg/Doc/doc.aux @@ -0,0 +1,50 @@ +\relax +\bibstyle{alpha} +\citation{aho-twig-toplas} +\citation{appel-87} +\citation{balachandran-complang} +\citation{kron-phd} +\citation{hoffmann-jacm} +\citation{hatcher-popl} +\citation{chase-popl} +\citation{pelegri-popl} +\citation{pelegri-phd} +\citation{wilhelm-tr} +\citation{henry-budp} +\citation{fraser-henry-spe-91} +\citation{proebsting-91} +\@writefile{toc}{\contentsline {section}{\numberline {1}Overview}{1}} +\@writefile{toc}{\contentsline {section}{\numberline {2}Input}{1}} +\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces A Sample Tree Grammar}}{2}} +\newlabel{fig-tree-grammar}{{1}{2}} +\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces EBNF Grammar for Tree Grammars for {\sc Burg}\ }}{3}} +\newlabel{fig-grammar-grammar}{{2}{3}} +\@writefile{toc}{\contentsline {section}{\numberline {3}Output}{3}} +\citation{aho-johnson-dp-classic} +\citation{fraser-henry-spe-91} +\citation{henry-budp} +\citation{pelegri-phd} +\@writefile{toc}{\contentsline {section}{\numberline {4}Debugging}{6}} +\@writefile{toc}{\contentsline {section}{\numberline {5}Running {\sc Burg}\ }{6}} +\newlabel{sec-man-page}{{5}{6}} +\citation{pelegri-popl} +\citation{henry-budp} +\citation{balachandran-complang} +\citation{proebsting-91} +\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces A Diverging Tree Grammar}}{7}} +\newlabel{fig-diverge-grammar}{{3}{7}} +\@writefile{toc}{\contentsline {section}{\numberline {6}Acknowledgements}{7}} +\bibcite{aho-twig-toplas}{AGT89} +\bibcite{aho-johnson-dp-classic}{AJ76} +\bibcite{appel-87}{App87} +\bibcite{balachandran-complang}{BDB90} +\bibcite{wilhelm-tr}{BMW87} +\bibcite{chase-popl}{Cha87} +\bibcite{fraser-henry-spe-91}{FH91} +\bibcite{hatcher-popl}{HC86} +\bibcite{henry-budp}{Hen89} +\bibcite{hoffmann-jacm}{HO82} +\bibcite{kron-phd}{Kro75} +\bibcite{pelegri-phd}{PL87} +\bibcite{pelegri-popl}{PLG88} +\bibcite{proebsting-91}{Pro91} diff --git a/utils/Burg/Doc/doc.dvi b/utils/Burg/Doc/doc.dvi new file mode 100644 index 0000000000000000000000000000000000000000..3211f32c96d4c68f03737a23a53140b6be2ed1f0 GIT binary patch literal 29856 zcmb823!I!)efO8l1O%e3Rq#?oh+-1lU3PO1A(YL1Avco^pdrP{%(J^g=EgiTY?c_& zzG{6dyD~gwIfqoQxsg8FLXtybav{{H7YGqanGrTKi& zotg8T%m4f@zyIZ&=U4Mi`Cqqw{G7F2{7d}skIx$lu0F3=t(2;j^OpAY_4oFz?Co2A zasRTVeQ%=0DQfoL{doUw^Je|Pzc7wgYM{Q0g!S5DNP`I(O%-+FV;ube*Wwzno}7PWITZ%w z$;r1pqpORjuNoX2(6>V`8B(M5K`s|v-+sg254EO#YC2!3^e=rhJvMwTbsZ7JH_D{i`bLS28FcWnOnQw{qOJJTgcvU z+q=pE%u$Jq=*8jas%)4p7GM`QxvmF3zHWOelMRanw}!!J#j;g>ZZB@_`tXgHJX$Gc zGMA;p-Z7r+4Kh`ceDaQ6hyRhOf9eZsAK4hBgFM7@q^~ji{xxg*C-3Ne&A`OO@k>7W z@QypXo-sUZ+sRfQIMl!N2mO<^=WhGL&KqvI`HMmMhHNl4dGB+tf78VAy(Tzk9A7q5 zaP~@YKJkH(dh(4AA76CE&t5s+6}K_I?rUblC>52;#gTF-q^cu%n7!zf!ov~t-3Y+g^EI*t+ucseS2bzlpK*hno$tyygl zM4no)B!6-EadL7*Y4VUVdO zZ!c7eti9{`0HpXtbWZ zxg@>_%1rXj|J5-`@e(t;q4s2EV=9|V>De2yDV{GD8sqt5HH?n;eEYFW4z-xjX{f&G z;YulL4wsAhX!>9ZP1V~WHccC5h-IR-N=5}uXF42ZqZ9WGHy1F>bg6paq65|PNUy%` zeFa-o%wb9>1(L*Qn{c%J%cHiD9Vc~dx-&cp53meF>T6}eczq4T@ z&CG&K1I}q2zwmcmi!SbbsFLmPJDRRPS^99XumBoHDUHqK!=T2OCI`*6wdB+p;=G`q z9DH?N!at7kWI|CGh(Bcryf1P zfO)9iK#CZGkw=l7dh*s4UixA?mGQQzdn);*#bcw{H2XX%W#-n07Q_hVrA6+#Jf>Qd z8Ww(`UuMQEG7)sSpt-QSksW3tQvaeaAKA-Xs7-TIlknWYGH1@u577;gtk0m3Y3mmR z?!7lLhNx&n)R2Zs{g>z%*8wUJo1jTK8)cM~y*1nAD5PK0IS`AObWsRXG;YY2i-jJh z=vkMQ)<0}|Ejjt#c&vP*iYdEm zUcPHnEjd|fLUp&1h(R_qGf-)am$bK;U^oiL^9>oxV$SRs5Ta4cn(7o;i&2W{6r5G7 zC*SuqZ*9Zsfm+wpN3LW2wnS$7yS{ksSuy_&QSo3Dgf*U--nnbm1nW$2+rauw+ZLCW zG}-Rs;q*wZs-| zMlf!27ArPZ;Vey$aMD@^Ez+h8Kn-}{{G1-BC%Ss`tVitPI3Rx7z!@V9R}03!$a3JXHOnG7|R$)-jM0J>}%-UI@`F!FuOj(QSc1}E=0>pdA@@DE?~wf@P;o8>>w8!XJ}w()9g_(_?6&VC>P{r z^=teC)?@O+OzeUq`X9pwHC9;;M)a9=<+bR6FwBk=*7f6~VYpI-%DSb|=Ae=uUAHXS zT&$MYEswTWbL&<_yK>cV-AX-r0sn(ay0~`cO+)chwSB+2bDjF@j~4eW5y!+W)Jd)U zpIhzMrSY!&1#1p_>XnbvJ-yNh>Q8Xn<+1;{mCUe)zhhNwh9n z5x3=Wo2xBru|{4}yZj?}+k{p|i~DW5aU(|$Yvso6`Q0vSxyrS?<3;!@aAf_8uQwfN zkgD&$xRyM2Y#`d>AcL6?c|%*AcOrl8g?Rn~l1`1)6VdXf04M&jx3HmbmwJ`}C)LSsp<2c=0m3rc3g-^qe+GqKR>P`+D$P-HrHP0$u^*$wY&uvw#n$1um$E>BM!I;L=G^dj0Tk1SaT;+TgX)d` zzP`i!*VmAX08XwnZ0!xi5G@vV8uNL7*EIu$8c;)D0xdNk+nHI09zA*UM?4Z;8jWOu zH@47C>vwFf&Ab1TemZ7JTU22|O$}5}yy%X2zI1f|CI=K{airzfeO9AZK!Q$NR~lpT zOND2I`HTfU=Cjsf$<`BX6eL%*SP)z@IK%{C*JKx%8NjQ&A&YyO!}{GboC(rEbskW!3Ea`e#E4RZv|`}8Qjo;>Api#-4UAvQa@ zpp5->djL$Z3AKb0hYFvIZ2gjidff9Oi5poAN=2#4xj0|T|hLxc@SSgP|@r_B@rgcxU&l$%EO+gDG% z;|hgP790|li5nrgj-zVHAAVXGUSWoJTw%g+yQzq50p}O&5reOCl@JA*K=9a{^SEy? z<@av32ODgMeCu)+jMXtZzV{nfq3K3b1~`$hH?B&-h@h58GZ~ADQ+&l79O7f=ANmqY zi15e#0^~l$)M>~$Z=@Px-XamhES?%6!O6?2h3xg!pc{>EniB5MF^i)xeNcvn>&dbCXMRM7 z+BHpvYg9q-+A`rF*sh-V!98rw57Eh&q!{%IVTzxJGNHo%dT$p0iIhJzA32PRJeBYdW{qd0g(aSW|Kh*r8Yz z!@MBQV8NjXAJpm0(ICv;h}^<6`QFB+8(?mQNiIG+Duel>2LJvS2bc(b*rZ@rhl)RKFQZXksw#y+7%Ax)1~e6k9mXc4yZ3#6$MKCN|dfr@(K$hnq^YVy<4H5m}Lni#B*y+MHa@ig*?5_CyW+(#%_+0gOaqS zszm>hazg|_2PN5vm&$^nP&Edk5-5itLb$NC!#}7fu>_s9u(QikeB*Vka37l-#CscL zGVDW^M9F&%3HIa7x->D&=HMT;)DU{Q2f%yq=D`&|?Ka&c|p zk>4(Ij@%-7ay!~M2l}*INVFEIo5K+bx=_guXOWFX>lTsfbT|l)&}o2+Yv+7ycSk=q z_{EEi=rf+s9z~1RE@B}4Y0q7Bp_&KzQe`~4@S@IN7A>~%4OXf1kyM)K1px^Iv$xIcH1()hx19^Ue^H!r)h6R5>8_hr!k? z5iiU536_8P?2=&olQOS=TA;@gj0H#Cawwq#nTmuq2L zQZXPGRF6ecLST|9QY^X=jxk&&()=-p?aQnuCr?}^#Ny#CjwN}3^;g=W%ufUzVvV{R zehlmL9=iu7j**hZt<(4f!U{5hg@{^2rpZQhjWZT}T~huL=&#P|tp1bk(_ zphBI5I`S#=j}^2WyGu-9I;A}r^psnO%B9cO{FW94>0bP5( z%+8lLw-zfjuR4iVO3oQ;C^<}gsGhj?Lf56xws~5bOfDOe^-q50+@W}80!k1WvuJrr zNwu(s8Z!maMt>R+oY`Wo;$`OPIar)z8Ht&_kj8oPa|3uYqxk?fttU@AgRW;%gK^|Z z6C1U7Pd5sCH`+ z_ub(JS`WQbr(Kj9Byhl#4l*;!Q`n0G*-9Co%#YYuKMt|5^tlST;XXW0HbFM>%HY#G79RN_*~VqAjKYeU zCht%Mg;RJ_iNC*;sEcql0hjem#CI36{pZ~Po>x+FdtQ7LR(`fjusL6h>cUB|At6N+&(X3tgB&-71VOpR zFrv0A;IP^Ts9jGcKGs2S2NLH)a*5Xjk|Hb#!H%6hFM)A!`5BnIUG^52Y9a&6w zrJ|!FMRSCRAV~uXQYoGU?O#<-eD@pK0`!;bYdWB;XlGGbwi9|{p89fTB<59y^*x6p z*ou|F$;$F*7#G;_W|0xipRFg}a3t0%(9aW*{eXlIU5xPIV1{wxna#ZU+Zx(Bk#DIF z1Qa0*T6LtzUUe=@#w&}mF;0`kV^led7|IX49un4*KR&LmSYf=i{A#I1B4e)i&aL2Y zu|KSWAvj?)ho+?3!6#LUr_g0FQ)3tB7Y4SHDP|4deKTcb5C8c!zPp7|zlsMGfHh%g zx`z>>ED3SaNfe>)?!jwH<1W?{pT0Shg&GoE z2EZvOWGqbWB1<@BUp#w62BF9O6o;I;r6BY)VG04QAq zsWMQ>fDGTNU$KeI&e21y2+RO+w@X$U_j;1sq{3*ixJe1uVyHy(cs$*3i3|oaRbB*% zfOB3J&cu?YxnPvex{a2T2tgcDtk3)CqZT6x&h+WljKm5-t(4_yYfeR0APg0|>wXO^ z2XJB&4Kj%2E&C7~X<9|jD4*aFw1Xng76<~J0CPIs%4OcIOg=TY@|^!T(XIU5Yid85 zXj*{m-1l|T5AX$bq-J1fpP8`$Y0F4Qxaw36IWo0kr=lUmTyvDIbas!pHARz73Q=q9 zM=FQM-0K_>S0_a-^|Wi_=BB4udbcGI1NU-fgobw>~kJ!RPS+WNW7f`Mz9(+OS z02Lbrp<*>tOct8(*CFd*|`{NNc@6>5DD2K>ZdZcxny(1Plm}Vtc^O6JjbaADC8X@e3!~sfszT)rkgiN+1x66h#8%CdVptEq#;4}J^MhlIhZ}>o znRo2#>V?f8cb<(RE*&0`_o>2$Dhq7DQ56qad$RkZjZ76_Hqst6m4li8V*3CREa1`F zwt6yH+l)6=vOJ6u7zLof>C~1XG8DSSqaiq$tXTR0Me+s=@|y8;4zsjCOdwcHqp=j} z3KUX%B=%X7?)TX`9u0COjOT$We1XuJN-;beJ2~xH(_6=^)w*K`oC_CMEfD6CpD|6b zV1ABVD9^D%CpPLwS#-thg2}g?HBp+Fb`G_o8l>TI1I#}p7lW$N+~7^ ztGC#vCWdD>PR2w=lf~kxVo50@mEaCn>|6KI3P|j8i?`-|;@lSYrGlU%%L5Z>CtG9+7;V%sYu3xG=(yGXXTj+}PXhu~in31XE zBX1zMjEuKmmw6EG!533KWU=8Nk1FWkG65j>INo}c1;9wrw1*7(-JB0 z^2cH-;rj{V2s(e70!11#td~90q^`18_FERokyMiGQov-I6mwvgP*nJ*K}B?r>X68$^F!c zDBMY=<$AqUiG|-h!_MUHJrkUFN#1n3%dvrFvWJF50451VJGOj^MzRvD)D;Cwt2!)U zNW~%{T1TVP#l%OlAKEVFJ?3JP3cI&(GLF;W_2izj70@GH9Y$uctSVBQW9l3=VkBq< zH1rFuE|i0pjkFXSW?*@#^NLbz)`AIAK;Ah;cJ0Aucu}e+F8h_5c}E`yZ0~@%YsE?r z_y!09(FLx$8`EyjqNcA<@wO3IY~ERmYhYI%<#5l0{AoU`(ggp< z3014U$$8AccUgRm8Y*+#!BbZD6kTXAqfiO=?Wg|jaMat|8y%4r#DvxpU)tk`g)%bK znLt$)3eL7H!fd9HH@^FCT>vQ#uSK>B**Z8%QG4x493avB;>cui82Z}8rV^jM*{4dV z!cjHSR~{B~lMhi)$)sp*t_d3`aDD;{Yi^4|qGy(ywmyuPT7faa)+!HM zPY%B_jylSbce+5|#*4O9IDvN_gB<~h<-V4zUn|j4Ui{><8) z8IaFy(!p#doCO7)0tmFuLXneuuJ+nhqpJD7{Z1{k%t-X7;!uB-M|Q*I&sA0ozy4JZ z+Z`{`iE$j&lf0CD=pg!2H6w>-T+!aU_BN}WMuu4don96SiR+0Ue<+S#;4#Eed8rsQ z;527++Az{do1D6W&4QhK@=a2iDDnkxGMs2l;-SqE)xu)Wnjz7W_2eR%ZG31Ij`)DC z;0hp)@+N29m#7tl&$X%*qzgKk3_Hhd>eK^gO^e1Bu5ii*H@*P^#0a4| zn8PeK7bRNeqke{ivX;TZE-)|bf^fBkB3t0epr=f%f~SgKC@?ASX*R@PTT4v6TFdo( zD9^~$gGelH({3n|P0^y^8Wn^eJ9aWX8dBSYSBDxPJfbRwj$Bx05MsFxLd<_^L5PdAzguQ`iuR5ai%Z?=s=qs; z%(!vUh2Fx6km4w7?b6#u+!N=}X=mNvQia%D=62VF1_D%T2rr3fQk$vda`DVc>~1r- zGS`}jSbkJ~fYYL+X+ab=AFb9Erqb<&=;ydkscJvW{ZjcisMHv2(KwDv`sTQI$mroo1IVn!{tm_ z&supZ@@o`qb!3m3!gPDzQjz+O=dZl@mptz+H6=$a5}vsFS&J3@v-{mbeK$C4BydqN zvHEdAac^ZjgNY)Z9gXza{kA^WotR1t^->DUYgCUjH_5#t6>ObvX&^bwo?-7j`@Ek| zG>4>GcfTwadhdP43JY}tTxg|1+A~Ch5-7qwQfw0anqKJjtGVjtu9oqDls*A>xV#-l z%~T{~rC7>AZswq^E0r+?9FHj!)gF^TF5c_M7Ex>Os*(ImX9NXgOL6}ReHUJj-RKDW zxGJU|C3#@0RBnWm?j%7C@8ILjNM#BO5mZqrygfjmF>W455n`y8y#1nf60Du8i5@!C zWD;LHzvZ+=&G>{c@xR!9g&{+`;Jb{JOdZAEa_;BSraD^m(4krJAP!0m)sk=dsYQco zOox#dX^9;*{Po07UKWELRs~r3`@g}wC^U{WLnq4&xH|a%!MLWBQcKjiGkBOQm8yH> zXh9ejG*^%EPu=6)4;`9bV&V6gq8@*G&ykIZ;`5Q+orMZUO^nfW$MG1aD}#}1cML`S zkYM&tgopIg(m8$-lF@I==J<`=!L@#|(iC&FP{+T&h4tUr6$-$*Yzgr>j$11!CPb$YwO~NLUFB>no{yR#1rDTrdANm5K6_}oXRwy| zY_aL`;hxw1SweTNLOd_WT2K%`F8Crth9;I7cJT&>r<~7X5m)_WUb6!DvcHVlajMGz z2?|YqxA{vdR|v%|4wTC1q&b7_y_RB0@z#C&<*v+XU@WET?{WRirs>FbJ-PPZGy^?l z`ZWf(7Q)i6%)T>)R!gQfS+b7Qj*|TTXo9}BAko@?Ly2^hZlmb_MoFA;7ZY;sl9dE8 zER&2=!i!9OwSe}F%E}J^IwnW#9-W*L-ayWxg!Ax>6si>2w}0RAPGa;tC}NoXlZ7$1HSLT{#gDP}Sy*_+7N2y73zc|>J5KdAS9r*I z>QjT9YrlLF$Z0Mvq0`u{HQ)MwBzf|>n<8HOMgU_j_^2~VAhTkdxmg7Po{LOQVv8b= zD4e|aYywOjysl8KZC|l;vP^*8h0$jI))N-QIN3v;;?ju=-C!WnTxJFcj(phID1}Ff zJfUvt$Z?qt!PN-K$hAGv&Cu`reVmow*@meje|VA|u^_@G#t{f#*}oF3f|M4A8milQMbVYD%x zRr4})NgtYFK+wJs6J+$~(BJo=1NckJPe{7^f;UYq}n_bN52Ku3N4 zA1p98%aw=`Tq^kZ6(EgUXUGpIux2UY>vUA`WUDtGCGIdkyL_%Drg%6|fPB>$a?U2e zXWRam81=-y^Rz=qpVbIxn`ZD~e2g(Tq$^@tr-q{;?Wez;rd3DkgA?jd9U-EM$?J}v z2VZy6o|Q)ysj?!1#gSZCeeQX99QXUrPc}&{>lis>a*FJ4USSlM(Tb}dBR_<Fhv@`j-yde3=MT(;{K`LvMWH3cYD1sq%ew*_C;p{Nyj$S<+ z+HZD$f%>)dGUpk6zwYRg1q<*XQshg@Ba|+aHKS6Et5n=^Cd?fH2$w_hNo!q55|O*+ zVhUz#%^2Gu6kTG$2Z0m!MLlumPn*<5_Vt+Xy&T zcb{&BQm9t6YJ3}mi2ltpH=ry*-Y$sitwKCE;L8dJvzP#%%aisqsqv36+u<2^4oI?zB4(kK!AFJ!{K9Y0 z#xe>jRbL#E>tNFBbOWat*6?+XcS}vpyJ}wq>WWoDvda!#>kW&duhMKw%zs_%8`{LN~FN^0?Ih0 z7{j1KreNPa0z1}~#X#&=!Xy<1J%0DrA-Z!9Ct8Dr_$W>mNGy+3m~F{ z3)xat3sZGI;&|UrG__3jOguU}?Tdr$>c}mX<&qQ}&Q{B~ZnjmPEHbt!J*WPPsV?r> z9bX0|2HrQZ)!nsp?m1uCj|=44P_v3TP3%}tt~u)QkPgXF0WUxplg19;wJUwm(`sb6 z1TG>Q8;6)E4QG+ChDt${Acc&LmtKXSF)z|7kbL7GjFLBzIxd8i6doLJ?YJvvIbjR^ zRYPH=mOT8+Ojc(tMgoT`)LZA{1ffW4m=Z93E$?>5me-SoLW_6FLpE_S-LbyPDEBo| zS!NugSQoKf1>b^0qtt`aC-wN89JimP6NH6V{PKh>eDcm#)d?$Z<>ALD-Hrn)%b<`u z89Acbgv4v6Lvr4RdE%TJDH2YJ!49)9q@XZi5r4!TJvQriw2qxKkGD@5MxBYH5~WQB zW7m3O#c9Uzo+YI`9YdmMA9&WF3j>%>3BAlOT-Gn(j7Q16cnCA_q@USe@c}jrRS$Q^ zv7^}7D*eh*(R3rN_{1(Nwqru|vYCC;9VFL71-X(B2eF+Cqs;?|Q#FX+Zv(-;~#T&M}0}8I9 z629VQH^mOcIwq;x?u>f?7V@dH4Xg_|`D+lhB6pQ7Bh1vl~#%+>dBVt!# z*iZd)MHiob^sy8UJQ~>;+NwaDu+}LgBI^3$(V?hl%{Zi^s}I+^n=eTi7KJY{C)AI+ z>S>rkDx*c?Hv7p-wOy80mGyv6l??rNa`=hx;B4fs|5u|<+5N;%p#ph!<9aQbJ|mj;A|c^F@p2N zlI`#0Ke$b^r{e7Lc0%@4I_r>gBt5tl9k+e1g>U-n{zxluqrgA&H9(HKWUAtu8x%wGRCk+(*=!A^LamQldBUbwsyBKkqo!y3Aikv@y0V z(xbBvwZ@kcky}q3zl*y!5!*5;c}dAXy;)`&xRVt+hB9bZAC$Ax_wxjmPuT1W7<=fmo zpedJQ{HPm1{e7P2Km4BA*LM1QMqhH{OJ?5N$wawm2R$=${suR-^o(12bGHFV-QC2P zu9{pv1=dj)#K}E*dTN9!Pz<+u4`!n5`#28Y>ays%)ZQAST%`yH&`xKg0jpAC^n$im z3o*m7V>`90@m6{*NrTSq#3t)TbHQZIyW|Hcm31u(_g>ggd+elFtI!LP5o7s_ZaDMU zprIRaNDhEIE-4^o@i2?fsq=~_%9i+s<@&rQK55v1*_*pWG$183!oHt3XwC*6(HsY@ z0UcA-qi^aPuU_oXtak^=cE)YLNlNm;H`;i@|~0mXYC-@Boh;aGkl zBG8y_9JDj*Bb0*Ad+dNW3}Xb*P&z37oJ%8U`P^tc|Lhg&*lx4Odm!yAB}YxB=~cnhR44|2nX-94*U_w@Cz<_!?F(|ZO7 zLFEeM-7~?v42T-zO7{EaRVTKK^QaAEu z$?ikY0Xwz5u2y5&+|0E z3UwP+-B8MXv|?+}35NNLi`H`~1u-29BEUJ$*XHu`9A#0JXcN1W1L#sWHSgFh8(r{! zE9V=y|5V>xUK~}}Y%B36%)V6BR$|2Rjd(2Jf*<3xXuT@+ozQ}Kyb}6BD+uUS&csA> z-vA&;m;LWY0WX`(4dj4&nfm z2VaPI$;lPH(a?3I9w=-&J#!@H6x5Nw-HoYh6jR;xdAM09roN+ZWOt(v%&iy=+FtC~KrNt4LtzO*_Pq)B*)MNGJ{Cn9beo(TJ zW1aJVc^A@>mIK2P_8`p#VWzYc%f?ok&28o5+{s`+b?SKRai@-L3k&`nn`TZp#F+(= zcf+2Zq1`=wtNVIZuj*!xVEjOqWTv(8ww>KrvwD?Zg1Hp&5=f@pJ-$AbbLYI-MAR|? z<40e;u{YY@8*M~uWaOE7*6c+PLOT}AOi%m#PdC{y-G~cD?j9!@BfB1_9hfSSCsrm! zqUn2%ttVgK=a7c^WBx)8+anNx9YO%HwiuXU%J&_O^-3-Ip+{%1o+=R^{BHjWZCd}* zRfqeR_bG;?@zA$@@sjmg1i$3Vnb=LW->iNk4lk*IcbX7J-#g?vG{p@RP&wR!O=uGX zs)02|lH|r*1fXq^bfdj>Bn#p=bQUi!;wRo9QcJ%1vH>)EY{~4dA)&d}wnx}T(^s9_ zt~e#ij)#vjnI+FbSS$9%11f(Xa&3o{S60f2OYx7#1~cF6j<-(3qxWpySs&HQ<89Z{v2~4C(N=G>{_~u|&*J4X80c zzVlP-^RKxYT894krG0cS+~I~OfGYGq{rJO2_Y{XKV_fJfU;0(MbX5y}e-ylA)1eX} zY`u3W!YQiH|NK{%_7g(rYF39(2X{rN=F92=4z>)+@CywSGg3*(E?S*mA4%`m|Um+Nl}* zF@n$1F+CZdYoVy9%`l=*JbnK(Ig)u&rnlM7K&VX@c(oHbrPF9>oW|-kJ$*}i`j#s* zl9d^OL(FASMrEeI(unnO1DqERseFhO3-9^DkwM(qo(k_CQ=X&Wk#e?Y8!jxn2SNYuMKjmIjXU4u#eFj-ipO)wHzBgvfr6p3fBTqb z%=0$mClACkPM-DA){HS^2jNKub(TdQoXy!K8p{o5X*zti)!t`2{i*qE>HR11*#yxo z+&YsC+!Jx%iDdA*72=_6>-A0)TYSwKPZ@hU_f2p_(ixIJxUF}9;NMwKBls6zYAM6y zUZC{s??Ejx;7%_je*A@_o3p$r$F4KO{?!vf&n&H$2+ovNQwuJ?o^A3xgA|9SVDeqY zbGijdjD@ag%&pXxu33I~S>Ni}%)c71$7A+gdV!QDpy?CS;?$0R?>#eL0N6YAw3`Pg z!=fhAXz8wXkz(+dH-7ILhZo!6y|>{tl(f46BVybh_{Nx~rDCu+7TJb?u}X?vPcC(q z5+fRq64N1`j#mhFBNMV{9sIQh{`z%S*Y(freCMX#lzGb0Pi*Nrt?TrYWDHO8=D(A? xNpsGZXU_eq!MWchIp@nU=YFZ%-0zf{`}I_F->N_78w>xlt1G;I-naSp{{bte`N9AI literal 0 HcmV?d00001 diff --git a/utils/Burg/Doc/doc.log b/utils/Burg/Doc/doc.log new file mode 100644 index 00000000000..a224a4edf72 --- /dev/null +++ b/utils/Burg/Doc/doc.log @@ -0,0 +1,157 @@ +This is TeX, Version 3.14159 (Web2C 7.3.2) (format=latex 2000.8.30) 4 JUN 2001 13:20 +**doc +(doc.tex +LaTeX2e <2000/06/01> +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latex209.def +File: latex209.def 1998/05/13 v0.52 Standard LaTeX file + + + Entering LaTeX 2.09 COMPATIBILITY MODE + ************************************************************* + !!WARNING!! !!WARNING!! !!WARNING!! !!WARNING!! + + This mode attempts to provide an emulation of the LaTeX 2.09 + author environment so that OLD documents can be successfully + processed. It should NOT be used for NEW documents! + + New documents should use Standard LaTeX conventions and start + with the \documentclass command. + + Compatibility mode is UNLIKELY TO WORK with LaTeX 2.09 style + files that change any internal macros, especially not with + those that change the FONT SELECTION or OUTPUT ROUTINES. + + Therefore such style files MUST BE UPDATED to use + Current Standard LaTeX: LaTeX2e. + If you suspect that you may be using such a style file, which + is probably very, very old by now, then you should attempt to + get it updated by sending a copy of this error message to the + author of that file. + ************************************************************* + +\footheight=\dimen102 +\@maxsep=\dimen103 +\@dblmaxsep=\dimen104 +\@cla=\count79 +\@clb=\count80 +\mscount=\count81 +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/tracefnt.sty +Package: tracefnt 1997/05/29 v3.0j Standard LaTeX package (font tracing) +\tracingfonts=\count82 +LaTeX Info: Redefining \selectfont on input line 96. +) +\symbold=\mathgroup4 +\symsans=\mathgroup5 +\symtypewriter=\mathgroup6 +\symitalic=\mathgroup7 +\symsmallcaps=\mathgroup8 +\symslanted=\mathgroup9 +LaTeX Font Info: Redeclaring math alphabet \mathbf on input line 288. +LaTeX Font Info: Redeclaring math alphabet \mathsf on input line 289. +LaTeX Font Info: Redeclaring math alphabet \mathtt on input line 290. +LaTeX Font Info: Redeclaring math alphabet \mathit on input line 296. +LaTeX Info: Redefining \em on input line 306. +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latexsym.sty +Package: latexsym 1998/08/17 v2.2e Standard LaTeX package (lasy symbols) +\symlasy=\mathgroup10 +LaTeX Font Info: Overwriting symbol font `lasy' in version `bold' +(Font) U/lasy/m/n --> U/lasy/b/n on input line 42. +) +LaTeX Font Info: Redeclaring math delimiter \lgroup on input line 370. +LaTeX Font Info: Redeclaring math delimiter \rgroup on input line 372. +LaTeX Font Info: Redeclaring math delimiter \bracevert on input line 374. + +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/config/latex209.cf +g +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/rawfonts.sty +Compatibility mode: package `' requested, but `rawfonts' provided. +Package: rawfonts 1994/05/08 Low-level LaTeX 2.09 font compatibility + +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/somedefs.sty +Package: somedefs 1994/06/01 Toolkit for optional definitions +) +LaTeX Font Info: Try loading font information for U+lasy on input line 44. + (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/ulasy.fd +File: ulasy.fd 1998/08/17 v2.2eLaTeX symbol font definitions +)))) (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/article. +cls +Document Class: article 2000/05/19 v1.4b Standard LaTeX document class +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/size11.clo +File: size11.clo 2000/05/19 v1.4b Standard LaTeX file (size option) +) +\c@part=\count83 +\c@section=\count84 +\c@subsection=\count85 +\c@subsubsection=\count86 +\c@paragraph=\count87 +\c@subparagraph=\count88 +\c@figure=\count89 +\c@table=\count90 +\abovecaptionskip=\skip41 +\belowcaptionskip=\skip42 +Compatibility mode: definition of \rm ignored. +Compatibility mode: definition of \sf ignored. +Compatibility mode: definition of \tt ignored. +Compatibility mode: definition of \bf ignored. +Compatibility mode: definition of \it ignored. +Compatibility mode: definition of \sl ignored. +Compatibility mode: definition of \sc ignored. +LaTeX Info: Redefining \cal on input line 501. +LaTeX Info: Redefining \mit on input line 502. +\bibindent=\dimen105 +) +(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/pstex/fullpage.sty +) (doc.aux) +\openout1 = `doc.aux'. + +LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 2. +LaTeX Font Info: ... okay on input line 2. +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <12> on input line 33. +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <8> on input line 33. +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <6> on input line 33. +LaTeX Font Info: Try loading font information for OMS+cmtt on input line 100 +. +LaTeX Font Info: No file OMScmtt.fd. on input line 100. +LaTeX Font Warning: Font shape `OMS/cmtt/m/n' undefined +(Font) using `OMS/cmsy/m/n' instead +(Font) for symbol `textbraceleft' on input line 100. + [1 + +] +LaTeX Font Info: External font `cmex10' loaded for size +(Font) <10.95> on input line 150. + [2] [3] [4] [5] [6] +Overfull \hbox (1.38191pt too wide) in paragraph at lines 480--484 +[]\OT1/cmr/m/n/10.95 Emit code for \OT1/cmtt/m/n/10.95 burm[]arity\OT1/cmr/m/n/ +10.95 , \OT1/cmtt/m/n/10.95 burm[]child\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95 + burm[]cost\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95 burm[]ntname\OT1/cmr/m/n/10 +.95 , \OT1/cmtt/m/n/10.95 burm[]op[]label\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10. +95 burm[]opname\OT1/cmr/m/n/10.95 , + [] + +[7] [8] [9] (doc.aux) +LaTeX Font Warning: Some font shapes were not available, defaults substituted. + ) +Here is how much of TeX's memory you used: + 543 strings out of 12968 + 6147 string characters out of 289029 + 446019 words of memory out of 1453895 + 3433 multiletter control sequences out of 10000+10000 + 23403 words of font info for 87 fonts, out of 400000 for 2000 + 14 hyphenation exceptions out of 1000 + 21i,6n,20p,308b,283s stack positions out of 300i,100n,500p,50000b,4000s + +Output written on doc.dvi (9 pages, 29856 bytes). diff --git a/utils/Burg/Doc/doc.tex b/utils/Burg/Doc/doc.tex new file mode 100644 index 00000000000..3dc67be3176 --- /dev/null +++ b/utils/Burg/Doc/doc.tex @@ -0,0 +1,596 @@ +\documentstyle[11pt,fullpage]{article} +\begin{document} + +\def\AddSpace#1{\ifcat#1a\ \fi#1} % if next is a letter, add a space +\def\YACC#1{{\sc Yacc}\AddSpace#1} +\def\TWIG#1{{\sc Twig}\AddSpace#1} +\def\PROG#1{{\sc Burg}\AddSpace#1} +\def\PARSER#1{{\sc Burm}\AddSpace#1} +\def\CODEGEN#1{{\sc Codegen}\AddSpace#1} + +\title{{\sc Burg} --- Fast Optimal Instruction Selection and Tree Parsing} +\author{ +Christopher W. Fraser \\ +AT\&T Bell Laboratories \\ +600 Mountain Avenue 2C-464 \\ +Murray Hill, NJ 07974-0636 \\ +{\tt cwf@research.att.com} +\and +Robert R. Henry \\ +Tera Computer Company \\ +400 N. 34th St., Suite 300 \\ +Seattle, WA 98103-8600 \\ +{\tt rrh@tera.com} +\and +Todd A. Proebsting \\ +Dept. of Computer Sciences \\ +University of Wisconsin \\ +Madison, WI 53706 \\ +{\tt todd@cs.wisc.edu} +} +\date{December 1991} + +\maketitle +\bibliographystyle{alpha} +\newcommand\term[1]{{\it #1}} +\newcommand\secref[1]{\S\ref{#1}} +\newcommand\figref[1]{Figure~\ref{#1}} +% +% rationale table making +% +{\catcode`\^^M=13 \gdef\Obeycr{\catcode`\^^M=13 \def^^M{\\}}% +\gdef\Restorecr{\catcode`\^^M=5 }} % + +% +% for printing out options +% +\newcommand\option[1]{% #1=option character +{\tt -#1}% +} +\newcommand\var[1]{% +{\tt #1}% +} +\section{Overview} + +\PROG is a program that generates a fast tree parser using BURS +(Bottom-Up Rewrite System) technology. It accepts a cost-augmented +tree grammar and emits a C program that discovers in linear time an +optimal parse of trees in the language described by the grammar. \PROG +has been used to construct fast optimal instruction selectors for use +in code generation. \PROG addresses many of the problems addressed by +{\sc Twig}~\cite{aho-twig-toplas,appel-87}, but it is somewhat less flexible and +much faster. \PROG is available via anonymous \var{ftp} from +\var{kaese.cs.wisc.edu}. The compressed \var{shar} file +\var{pub/burg.shar.Z} holds the complete distribution. + +This document describes only that fraction of the BURS model that is +required to use \PROG. Readers interested in more detail might start +with Reference~\cite{balachandran-complang}. Other relevant documents +include References~\cite{kron-phd,hoffmann-jacm,hatcher-popl,chase-popl,pelegri-popl,pelegri-phd,wilhelm-tr,henry-budp,fraser-henry-spe-91,proebsting-91}. + +\section{Input} + +\PROG accepts a tree grammar and emits a BURS tree parser. +\figref{fig-tree-grammar} shows a sample grammar that implements a very +simple instruction selector. +\begin{figure} +\begin{verbatim} +%{ +#define NODEPTR_TYPE treepointer +#define OP_LABEL(p) ((p)->op) +#define LEFT_CHILD(p) ((p)->left) +#define RIGHT_CHILD(p) ((p)->right) +#define STATE_LABEL(p) ((p)->state_label) +#define PANIC printf +%} +%start reg +%term Assign=1 Constant=2 Fetch=3 Four=4 Mul=5 Plus=6 +%% +con: Constant = 1 (0); +con: Four = 2 (0); +addr: con = 3 (0); +addr: Plus(con,reg) = 4 (0); +addr: Plus(con,Mul(Four,reg)) = 5 (0); +reg: Fetch(addr) = 6 (1); +reg: Assign(addr,reg) = 7 (1); +\end{verbatim} +\caption{A Sample Tree Grammar\label{fig-tree-grammar}} +\end{figure} +\PROG grammars are structurally similar to \YACC's. Comments follow C +conventions. Text between ``\var{\%\{}'' and ``\var{\%\}}'' is called +the \term{configuration section}; there may be several such segments. +All are concatenated and copied verbatim into the head of the generated +parser, which is called \PARSER. Text after the second ``\var{\%\%}'', +if any, is also copied verbatim into \PARSER, at the end. + +The configuration section configures \PARSER for the trees being parsed +and the client's environment. This section must define +\var{NODEPTR\_TYPE} to be a visible typedef symbol for a pointer to a +node in the subject tree. \PARSER invokes \var{OP\_LABEL(p)}, +\var{LEFT\_CHILD(p)}, and \var{RIGHT\_CHILD(p)} to read the operator +and children from the node pointed to by \var{p}. It invokes +\var{PANIC} when it detects an error. If the configuration section +defines these operations as macros, they are implemented in-line; +otherwise, they must be implemented as functions. The section on +diagnostics elaborates on \var{PANIC}. + +\PARSER computes and stores a single integral \term{state} in each node +of the subject tree. The configuration section must define a macro +\var{STATE\_LABEL(p)} to access the state field of the node pointed to +by \var{p}. A macro is required because \PROG uses it as an lvalue. A +C \var{short} is usually the right choice; typical code generation +grammars require 100--1000 distinct state labels. + +The tree grammar follows the configuration section. +\figref{fig-grammar-grammar} gives an EBNF grammar for \PROG tree +grammars. +\begin{figure} +\begin{verbatim} +grammar: {dcl} '%%' {rule} + +dcl: '%start' Nonterminal +dcl: '%term' { Identifier '=' Integer } + +rule: Nonterminal ':' tree '=' Integer cost ';' +cost: /* empty */ +cost: '(' Integer { ',' Integer } ')' + +tree: Term '(' tree ',' tree ')' +tree: Term '(' tree ')' +tree: Term +tree: Nonterminal +\end{verbatim} +\caption{EBNF Grammar for Tree Grammars for \PROG\ \label{fig-grammar-grammar}} +\end{figure} +Comments, the text between ``\var{\%\{}'' and ``\var{\%\}}'', and the +text after the optional second ``\var{\%\%}'' are treated lexically, so +the figure omits them. In the EBNF grammar, quoted text must appear +literally, \var{Nonterminal} and \var{Integer} are self-explanatory, +and \var{Term} denotes an identifier previously declared as a +terminal. {\tt\{$X$\}} denotes zero or more instances of $X$. + +Text before the first ``\var{\%\%}'' declares the start symbol and the +terminals or operators in subject trees. All terminals must be +declared; each line of such declarations begins with \var{\%term}. +Each terminal has fixed arity, which \PROG infers from the rules using that terminal. +\PROG restricts terminals to have at most two children. Each terminal +is declared with a positive, unique, integral \term{external symbol +number} after a ``\var{=}''. \var{OP\_LABEL(p)} must return the valid +external symbol number for \var{p}. Ideally, external symbol numbers +form a dense enumeration. Non-terminals are not declared, but the +start symbol may be declared with a line that begins with +\var{\%start}. + +Text after the first ``\var{\%\%}'' declares the rules. A tree grammar +is like a context-free grammar: it has rules, non-terminals, +terminals, and a special start non-terminal. The right-hand side of a +rule, called the \term{pattern}, is a tree. Tree patterns appear in +prefix parenthesized form. Every non-terminal denotes a tree. A chain +rule is a rule whose pattern is another non-terminal. If no start +symbol is declared, \PROG uses the non-terminal defined by the first +rule. \PROG needs a single start symbol; grammars for which it is +natural to use multiple start symbols must be augmented with an +artificial start symbol that derives, with zero cost, the grammar's +natural start symbols. \PARSER will automatically select one +that costs least for any given tree. + +\PROG accepts no embedded semantic actions like \YACC's, because no one +format suited all intended applications. Instead, each rule has a +positive, unique, integral \term{external rule number}, after the +pattern and preceded by a ``\var{=}''. Ideally, external rule numbers +form a dense enumeration. \PARSER uses these numbers to report the +matching rule to a user-supplied routine, which must implement any +desired semantic action; see below. Humans may select these integers +by hand, but \PROG is intended as a \term{server} for building BURS +tree parsers. Thus some \PROG clients will consume a richer +description and translate it into \PROG's simpler input. + +Rules end with a vector of non-negative, integer costs, in parentheses +and separated by commas. If the cost vector is omitted, then all +elements are assumed to be zero. \PROG retains only the first four +elements of the list. The cost of a derivation is the sum of the costs +for all rules applied in the derivation. Arithmetic on cost vectors +treats each member of the vector independently. The tree parser finds +the cheapest parse of the subject tree. It breaks ties arbitrarily. +By default, \PROG uses only the \term{principal cost} of each cost +vector, which defaults to the first element, but options described +below provide alternatives. + +\section{Output} + +\PARSER traverses the subject tree twice. The first pass or +\term{labeller} runs bottom-up and left-to-right, visiting each node +exactly once. Each node is labeled with a state, a single number that +encodes all full and partial optimal pattern matches viable at that +node. The second pass or \term{reducer} traverses the subject tree +top-down. The reducer accepts a tree node's state label and a +\term{goal} non-terminal --- initially the root's state label and the +start symbol --- which combine to determine the rule to be applied at +that node. By construction, the rule has the given goal non-terminal +as its left-hand side. The rule's pattern identifies the subject +subtrees and goal non-terminals for all recursive visits. Here, a +``subtree'' is not necessarily an immediate child of the current node. +Patterns with interior operators cause the reducer to skip the +corresponding subject nodes, so the reducer may proceed directly to +grandchildren, great-grandchildren, and so on. On the other hand, +chain rules cause the reducer to revisit the current subject node, with +a new goal +non-terminal, so \term{x} is also regarded as a subtree of \term{x}. + +As the reducer visits (and possibly revisits) each node, user-supplied +code implements semantic action side effects and controls the order in +which subtrees are visited. The labeller is self-contained, but the +reducer combines code from \PROG with code from the user, so \PARSER +does not stand alone. + +The \PARSER that is generated by \PROG provides primitives for +labelling and reducing trees. These mechanisms are a compromise +between expressibility, abstraction, simplicity, flexibility and +efficiency. Clients may combine primitives into labellers and reducers +that can traverse trees in arbitrary ways, and they may call semantic +routines when and how they wish during traversal. Also, \PROG +generates a few higher level routines that implement common +combinations of primitives, and it generates mechanisms that help debug +the tree parse. + +\PROG generates the labeller as a function named \var{burm\_label} with +the signature +\begin{verbatim} +extern int burm_label(NODEPTR_TYPE p); +\end{verbatim} +It labels the entire subject tree pointed to by \var{p} and returns the +root's state label. State zero labels unmatched trees. The trees may +be corrupt or merely inconsistent with the grammar. + +The simpler \var{burm\_state} is \var{burm\_label} without the +code to traverse the tree and to read and write its fields. It may be +used to integrate labelling into user-supplied traversal code. A +typical signature is +\begin{verbatim} +extern int burm_state(int op, int leftstate, int rightstate); +\end{verbatim} +It accepts an external symbol number for a node and the labels for the +node's left and right children. It returns the state label to assign +to that node. For unary operators, the last argument is ignored; for +leaves, the last two arguments are ignored. In general, \PROG +generates a \var{burm\_state} that accepts the maximum number of child +states required by the input grammar. For example, if the grammar +includes no binary operators, then \var{burm\_state} will have the +signature +\begin{verbatim} +extern int burm_state(int op, int leftstate); +\end{verbatim} +This feature is included to permit future expansion to operators with +more than two children. + +The user must write the reducer, but \PARSER writes code and data that +help. Primary is +\begin{verbatim} +extern int burm_rule(int state, int goalnt); +\end{verbatim} +which accepts a tree's state label and a goal non-terminal and returns the +external rule number of a rule. The rule will have matched the tree +and have the goal non-terminal on the left-hand side; \var{burm\_rule} +returns zero when the tree labelled with the given state did not match +the goal non-terminal. For the initial, root-level call, \var{goalnt} +must be one, and \PARSER exports an array that identifies the values +for nested calls: +\begin{verbatim} +extern short *burm_nts[] = { ... }; +\end{verbatim} +is an array indexed by external rule numbers. Each element points to a +zero-terminated vector of short integers, which encode the goal +non-terminals for that rule's pattern, left-to-right. The user needs +only these two externals to write a complete reducer, but a third +external simplifies some applications: +\begin{verbatim} +extern NODEPTR_TYPE *burm_kids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]); +\end{verbatim} +accepts the address of a tree \var{p}, an external rule number, and an +empty vector of pointers to trees. The procedure assumes that \var{p} +matched the given rule, and it fills in the vector with the subtrees (in +the sense described above) of \var{p} that must be reduced recursively. +\var{kids} is returned. It is not zero-terminated. + +The simple user code below labels and then fully reduces a subject tree; +the reducer prints the tree cover. \var{burm\_string} is defined below. +\begin{verbatim} +parse(NODEPTR_TYPE p) { + burm_label(p); /* label the tree */ + reduce(p, 1, 0); /* and reduce it */ +} + +reduce(NODEPTR_TYPE p, int goalnt, int indent) { + int eruleno = burm_rule(STATE_LABEL(p), goalnt); /* matching rule number */ + short *nts = burm_nts[eruleno]; /* subtree goal non-terminals */ + NODEPTR_TYPE kids[10]; /* subtree pointers */ + int i; + + for (i = 0; i < indent; i++) + printf("."); /* print indented ... */ + printf("%s\n", burm_string[eruleno]); /* ... text of rule */ + burm_kids(p, eruleno, kids); /* initialize subtree pointers */ + for (i = 0; nts[i]; i++) /* traverse subtrees left-to-right */ + reduce(kids[i], nts[i], indent+1); /* and print them recursively */ +} +\end{verbatim} +The reducer may recursively traverse subtrees in any order, and it may +interleave arbitrary semantic actions with recursive traversals. +Multiple reducers may be written, to implement multi-pass algorithms +or independent single-pass algorithms. + +For each non-terminal $x$, \PROG emits a preprocessor directive to +equate \var{burm\_}$x$\var{\_NT} with $x$'s integral encoding. It also +defines a macro \var{burm\_}$x$\var{\_rule(a)} that is equivalent to +\var{burm\_rule(a,}$x$\var{)}. For the grammar in +\figref{fig-tree-grammar}, \PROG emits +\begin{verbatim} +#define burm_reg_NT 1 +#define burm_con_NT 2 +#define burm_addr_NT 3 +#define burm_reg_rule(a) ... +#define burm_con_rule(a) ... +#define burm_addr_rule(a) ... +\end{verbatim} +Such symbols are visible only to the code after the second +``\var{\%\%}''. If the symbols \var{burm\_}$x$\var{\_NT} are needed +elsewhere, extract them from the \PARSER source. + +The \option{I} option directs \PROG to emit an encoding of the input +that may help the user produce diagnostics. The vectors +\begin{verbatim} +extern char *burm_opname[]; +extern char burm_arity[]; +\end{verbatim} +hold the name and number of children, respectively, for each terminal. +They are indexed by the terminal's external symbol number. The vectors +\begin{verbatim} +extern char *burm_string[]; +extern short burm_cost[][4]; +\end{verbatim} +hold the text and cost vector for each rule. They are indexed by the +external rule number. The zero-terminated vector +\begin{verbatim} +extern char *burm_ntname[]; +\end{verbatim} +is indexed by \var{burm\_}$x$\var{\_NT} and holds the name of +non-terminal $x$. Finally, the procedures +\begin{verbatim} +extern int burm_op_label(NODEPTR_TYPE p); +extern int burm_state_label(NODEPTR_TYPE p); +extern NODEPTR_TYPE burm_child(NODEPTR_TYPE p, int index); +\end{verbatim} +are callable versions of the configuration macros. +\var{burm\_child(p,0)} implements \var{LEFT\_CHILD(p)}, and +\var{burm\_child(p,1)} implements \var{RIGHT\_CHILD(p)}. A sample use +is the grammar-independent expression +\var{burm\_opname[burm\_op\_label(p)]}, which yields the textual name +for the operator in the tree node pointed to by \var{p}. + +A complete tree parser can be assembled from just \var{burm\_state}, +\var{burm\_rule}, and \var{burm\_nts}, which use none of the +configuration section except \var{PANIC}. The generated routines that +use the rest of the configuration section are compiled only if the +configuration section defines \var{STATE\_LABEL}, so they can be +omitted if the user prefers to hide the tree structure from \PARSER. +This course may be wise if, say, the tree structure is defined in a +large header file with symbols that might collide with \PARSER's. + +\PARSER selects an optimal parse without dynamic programming at compile +time~\cite{aho-johnson-dp-classic}. Instead, \PROG does the dynamic +programming at compile-compile time, as it builds \PARSER. +Consequently, \PARSER parses quickly. Similar labellers have taken as +few as 15 instructions per node, and reducers as few as 35 per node +visited~\cite{fraser-henry-spe-91}. + +\section{Debugging} + +\PARSER invokes \var{PANIC} when an error prevents it from proceeding. +\var{PANIC} has the same signature as \var{printf}. It should pass its +arguments to \var{printf} if diagnostics are desired and then either +abort (say via \var{exit}) or recover (say via \var{longjmp}). If it +returns, \PARSER aborts. Some errors are not caught. + +\PROG assumes a robust preprocessor, so it omits full consistency +checking and error recovery. \PROG constructs a set of states using a +closure algorithm like that used in LR table construction. \PROG +considers all possible trees generated by the tree grammar and +summarizes infinite sets of trees with finite sets. The summary +records the cost of those trees but actually manipulates the +differences in costs between viable alternatives using a dynamic +programming algorithm. Reference~\cite{henry-budp} elaborates. + +Some grammars derive trees whose optimal parses depend on arbitrarily +distant data. When this happens, \PROG and the tree grammar +\term{cost diverge}, and \PROG attempts to build an infinite +set of states; it first thrashes and ultimately exhausts +memory and exits. For example, the tree grammar in +\figref{fig-diverge-grammar} +\begin{figure} +\begin{verbatim} +%term Const=17 RedFetch=20 GreenFetch=21 Plus=22 +%% +reg: GreenFetch(green_reg) = 10 (0); +reg: RedFetch(red_reg) = 11 (0); + +green_reg: Const = 20 (0); +green_reg: Plus(green_reg,green_reg) = 21 (1); + +red_reg: Const = 30 (0); +red_reg: Plus(red_reg,red_reg) = 31 (2); +\end{verbatim} +\caption{A Diverging Tree Grammar\label{fig-diverge-grammar}} +\end{figure} +diverges, since non-terminals \var{green\_reg} and \var{red\_reg} +derive identical infinite trees with different costs. If the cost of +rule 31 is changed to 1, then the grammar does not diverge. + +Practical tree grammars describing instruction selection do not +cost-diverge because infinite trees are derived from non-terminals +that model temporary registers. Machines can move data between +different types of registers for a small bounded cost, and the rules +for these instructions prevent divergence. For example, if +\figref{fig-diverge-grammar} included rules to move data between red +and green registers, the grammar would not diverge. If a bonafide +machine grammar appears to make \PROG loop, try a host with more +memory. To apply \PROG to problems other than instruction selection, +be prepared to consult the literature on +cost-divergence~\cite{pelegri-phd}. + +\section{Running \PROG\ }\label{sec-man-page} + +\PROG reads a tree grammar and writes a \PARSER in C. \PARSER can be +compiled by itself or included in another file. When suitably named +with the \option{p} option, disjoint instances of \PARSER should link +together without name conflicts. The command: +\begin{flushleft} +\var{burg} [ {\it arguments} ] [ {\it file} ] +\end{flushleft} +invokes \PROG. If a {\it file} is named, \PROG expects its grammar +there; otherwise it reads the standard input. The options include: +\def\Empty{} +% +\newcommand\odescr[2]{% #1=option character, #2=optional argument +\gdef\Arg2{#2}% +\item[\option{#1}\ifx\Arg2\Empty\else{{\it #2}}\fi] +} +\begin{description} +% +\odescr{c}{} $N$ +Abort if any relative cost exceeds $N$, which keeps \PROG from looping on +diverging grammars. Several +references~\cite{pelegri-popl,henry-budp,balachandran-complang,proebsting-91} +explain relative costs. +% +\odescr{d}{} +Report a few statistics and flag unused rules and terminals. +% +\odescr{o}{} {\it file} +Write parser into {\it file}. Otherwise it writes to the standard output. +% +\odescr{p}{} {\it prefix} +Start exported names with {\it prefix}. The default is \var{burm}. +% +\odescr{t}{} +Generates smaller tables faster, but all goal non-terminals passed to +\var{burm\_rule} must come from an appropriate \var{burm\_nts}. Using +\var{burm\_}$x$\var{\_NT} instead may give unpredictable results. +% +\odescr{I}{} +Emit code for \var{burm\_arity}, \var{burm\_child}, \var{burm\_cost}, +\var{burm\_ntname}, \var{burm\_op\_label}, \var{burm\_opname}, +\var{burm\_state\_label}, and \var{burm\_string}. +% +\odescr{O}{} $N$ +Change the principal cost to $N$. Elements of each cost vector are +numbered from zero. +% +\odescr{=}{} +Compare costs lexicographically, using all costs in the given order. +This option slows \PROG and may produce a larger parser. Increases +range from small to astronomical. +\end{description} + +\section{Acknowledgements} + +The first \PROG was adapted by the second author from his \CODEGEN +package, which was developed at the University of Washington with +partial support from NSF Grant CCR-88-01806. It was unbundled from +\CODEGEN with the support of Tera Computer. The current \PROG was +written by the third author with the support of NSF grant +CCR-8908355. The interface, documentation, and testing involved +all three authors. + +Comments from a large group at the 1991 Dagstuhl Seminar on Code +Generation improved \PROG's interface. Robert Giegerich and Susan +Graham organized the workshop, and the International Conference and +Research Center for Computer Science, Schloss Dagstuhl, provided an +ideal environment for such collaboration. Beta-testers included Helmut +Emmelmann, Dave Hanson, John Hauser, Hugh Redelmeier, and Bill Waite. + +\begin{thebibliography}{BMW87} + +\bibitem[AGT89]{aho-twig-toplas} +Alfred~V. Aho, Mahadevan Ganapathi, and Steven W.~K. Tjiang. +\newblock Code generation using tree matching and dynamic programming. +\newblock {\em ACM Transactions on Programming Languages and Systems}, + 11(4):491--516, October 1989. + +\bibitem[AJ76]{aho-johnson-dp-classic} +Alfred~V. Aho and Steven~C. Johnson. +\newblock Optimal code generation for expression trees. +\newblock {\em Journal of the ACM}, 23(3):458--501, July 1976. + +\bibitem[App87]{appel-87} +Andrew~W. Appel. +\newblock Concise specification of locally optimal code generators. +\newblock Technical report CS-TR-080-87, Princeton University, 1987. + +\bibitem[BDB90]{balachandran-complang} +A.~Balachandran, D.~M. Dhamdhere, and S.~Biswas. +\newblock Efficient retargetable code generation using bottom-up tree pattern + matching. +\newblock {\em Computer Languages}, 15(3):127--140, 1990. + +\bibitem[BMW87]{wilhelm-tr} +J\"{u}rgen B\"{o}rstler, Ulrich M\"{o}nche, and Reinhard Wilhelm. +\newblock Table compression for tree automata. +\newblock Technical Report Aachener Informatik-Berichte No. 87-12, RWTH Aachen, + Fachgruppe Informatik, Aachen, Fed. Rep. of Germany, 1987. + +\bibitem[Cha87]{chase-popl} +David~R. Chase. +\newblock An improvement to bottom up tree pattern matching. +\newblock {\em Fourteenth Annual ACM Symposium on Principles of Programming + Languages}, pages 168--177, January 1987. + +\bibitem[FH91]{fraser-henry-spe-91} +Christopher~W. Fraser and Robert~R. Henry. +\newblock Hard-coding bottom-up code generation tables to save time and space. +\newblock {\em Software---Practice\&Experience}, 21(1):1--12, January 1991. + +\bibitem[HC86]{hatcher-popl} +Philip~J. Hatcher and Thomas~W. Christopher. +\newblock High-quality code generation via bottom-up tree pattern matching. +\newblock {\em Thirteenth Annual ACM Symposium on Principles of Programming + Languages}, pages 119--130, January 1986. + +\bibitem[Hen89]{henry-budp} +Robert~R. Henry. +\newblock Encoding optimal pattern selection in a table-driven bottom-up + tree-pattern matcher. +\newblock Technical Report 89-02-04, University of Washington Computer Science + Department, Seattle, WA, February 1989. + +\bibitem[HO82]{hoffmann-jacm} +Christoph Hoffmann and Michael~J. O'Donnell. +\newblock Pattern matching in trees. +\newblock {\em Journal of the ACM}, 29(1):68--95, January 1982. + +\bibitem[Kro75]{kron-phd} +H.~H. Kron. +\newblock {\em Tree Templates and Subtree Transformational Grammars}. +\newblock PhD thesis, UC Santa Cruz, December 1975. + +\bibitem[PL87]{pelegri-phd} +Eduardo Pelegri-Llopart. +\newblock {\em Tree Transformations in Compiler Systems}. +\newblock PhD thesis, UC Berkeley, December 1987. + +\bibitem[PLG88]{pelegri-popl} +Eduardo Pelegri-Llopart and Susan~L. Graham. +\newblock Optimal code generation for expression trees: An application of + {BURS} theory. +\newblock {\em Fifteenth Annual ACM Symposium on Principles of Programming + Languages}, pages 294--308, January 1988. + +\bibitem[Pro91]{proebsting-91} +Todd~A. Proebsting. +\newblock Simple and efficient {BURS} table generation. +\newblock Technical report, Department of Computer Sciences, University of + Wisconsin, 1991. + +\end{thebibliography} + +\end{document} + -- 2.34.1