%!PS-Adobe-2.0 %%Creator: dvips 5.47 Copyright 1986-91 Radical Eye Software %%Title: twig0.dvi %%Pages: 21 -1 %%BoundingBox: 0 0 612 792 %%EndComments %%BeginProcSet: texc.pro /TeXDict 200 dict def TeXDict begin /N /def load def /B{bind def}N /S /exch load def /X{S N}B /TR /translate load N /isls false N /vsize 10 N /@rigin{ isls{[0 1 -1 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale Resolution VResolution vsize neg mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@letter{/vsize 10 N}B /@landscape{/isls true N /vsize -1 N}B /@a4{/vsize 10.6929133858 N}B /@a3{ /vsize 15.5531 N}B /@ledger{/vsize 16 N}B /@legal{/vsize 13 N}B /@manualfeed{ statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail} B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg}bind{adv 1 chg nd}bind{1 add chg}bind{1 add chg nd}bind{adv lsh}bind{ adv lsh nd}bind{adv rsh}bind{adv rsh nd}bind{1 add adv}bind{/rc X nd}bind{1 add set}bind{1 add clr}bind{adv 2 chg}bind{adv 2 chg nd}bind{pop nd}bind]N /D{ /cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto}N /eop{clear SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for}N /p /show load N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval (Display)eq}{pop false}ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail} B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{ /SS save N}B /eos{clear SS restore}B end %%EndProcSet TeXDict begin 1000 300 300 @start /Fa 4 120 df<007FB6FCB71280A339F803E00FA600 70EC0700000091C7FCB3AB90B57E4880A26C5C212C7EAB26>84 D<90381FC07F90397FF1FF8090 B612C05A3903F07FC73A07C01F0380000FEC8000EB800F001F80EB0007A5EB800F000F5CEBC01F 000791C7FCEBF07EEBFFFC485B6D5AEB1FC090C9FCA27F120790B5FC15E04814F84880393F8001 FE007CC7123F0078140F00F81580481407A46C140F00781500007E143F6C6C13FE391FF007FC6C B55A000314E0C61480D91FFCC7FC22307E9E26>103 D<130E131F497EA36DC7FC130E90C8FCA7 EA3FFF487FA27EEA000FB3A5007FB512C0B612E0A26C14C01B2D7BAC26>105 D<3A7FF803FFC0486C4813E0A26C486C13C0000FC7EA1E00A46D133E0007143CA314E0EB81F0EB 83F8D803C35BA2EBC7BCA300011470141C9038EF1EF0A3EBEE0E3900FE0FE0A2EBFC07A2903878 03C0231F7F9E26>119 D E /Fb 1 1 df0 D E /Fc 39 121 df<49B4FC011F13C090387F80F09038FC00F83801F8010003497EEA07F0A36E5A6E 5A92C7FCA4B612FCA33807F001B3A33A7FFF1FFFC0A3222A7FA926>12 D<121C123E127FEAFF80 A3EA7F00123E121C09097B8813>46 D<130E131E137EEA07FE12FFA212F81200B3AB387FFFFEA3 17277BA622>49 DII<140E141E143E147E14FEA213011303EB077E130EA2131C 1338137013E0A2EA01C0EA0380EA0700120EA25A5A5A5AB612F8A3C7EAFE00A890387FFFF8A31D 277EA622>I<000C1303380F803FEBFFFE5C5C5C5C5C49C7FC000EC8FCA6EB7FC0380FFFF8EB80 FC380E003E000C133FC7EA1F8015C0A215E0A21218127C12FEA315C05A0078EB3F80A26CEB7F00 381F01FE380FFFF800035BC613801B277DA622>II<1238123E003FB512F0A34814E015C0158015003870000EA25C485B5C5CC7FC 495A495A1307A249C7FCA25BA25B133EA2137EA413FEA8137C13381C297CA822>II65 DI<91393FF00180903903 FFFE03010FEBFF8790393FF007DF9039FF8001FF4848C7127F4848143FD807F0141F000F150F48 481407A2485A1603127F5B93C7FC12FFA9127FA26DEC0380123FA26C7EEE07006C7E0007150ED8 03FC141E6C6C5C6C6C6C13F890393FF007E0010FB55A010391C7FC9038003FF829297CA832>I< B612F8EDFF8016E03A03FC001FF8ED07FCED01FE6F7EEE7F80EE3FC0161F17E0A2EE0FF0A417F8 AA17F0A3EE1FE0A217C0163FEE7F801700ED01FE4B5AED1FF8B712E0168003FCC7FC2D297DA835 >II<91387FE003903903FFFC07011FEBFF0F90393FF00FFF9038FF80014848C7FCD803F8 143F485A000F81484880A2485A82127F5B93C7FC12FFA84AB512F8127FA26DC71300123FA26C7E A26C7E12076C7EEA01FE6C6C6C5A90393FF007BF6DB5121F0103497E9039007FF0032D297CA836 >71 D73 D76 D80 D82 D<90387F80603903FFF0E04813F9380F807F381F001F003E1307481303140112FCA214007EA26C 140013C0EA7FFEEBFFE06C13FC6C7F6CEBFF806C14C06C14E0C6FC010713F0EB007FEC0FF81407 14030060130112E0A36C14F0A26C13036C14E0B4EB07C09038E01F8000F3B5120000E05B38C01F F01D297CA826>I<007FB712C0A39039803FC03FD87E00140700781503A20070150100F016E0A2 481500A5C71500B3A4017FB512E0A32B287EA730>I<48B47E000713F0380F81F8381FC07EA280 D80F801380EA0700C7FCA3EB0FFF90B5FC3807FC3FEA0FE0EA3F8013005A12FEA4007E137F007F 13DF393F839FFC380FFF0F3801FC031E1B7E9A21>97 D99 DII<9038FF81F00003EBE7F8390FC1FE7C381F80FC9038 007C3848EB7E1048EB7F00A66C137E6C137CEB80FC380FC1F8381FFFE0001813800038C8FCA212 3C123E383FFFF86C13FF15806C14C06C14E0001F14F0383E000748EB01F8481300A4007CEB01F0 003C14E0001FEB07C0390FC01F803903FFFE0038007FF01E287E9A22>103 DI<1207EA0F80EA1FC0EA3FE0A3EA1FC0EA0F80EA0700C7FCA7EAFFE0A3120F B3A3EAFFFEA30F2B7DAA14>I108 D<38FFC07F9038C1FFC09038C787E0390FCE03F013D88113F0A213E0B03AFFFE3FFF80A3211B7D 9A26>110 DI<38FFE1FE9038E7FF809038FE07E0390FF803F0496C7E496C7E818181A21680A716005DA2 5D4A5A01F05B6D485A9038FE0FE09038E7FF80D9E1FCC7FC01E0C8FCA9EAFFFEA321277E9A26> I<38FFC1F0EBC7FCEBCE3E380FD87FA213F0143E141CEBE000B0B5FCA3181B7E9A1C>114 D<3803FE30380FFFF0EA1E03EA380048137012F0A27E6C1300EAFFE0EA7FFEEBFF806C13E06C13 F0000713F8C6FCEB03FC13000060137C00E0133C7E14387E6C137038FF01E038F7FFC000C11300 161B7E9A1B>I<1370A413F0A312011203A21207381FFFF0B5FCA23807F000AD1438A61203EBF8 70000113603800FFC0EB1F8015267FA51B>I<39FFE03FF8A3000F1303B214071207140F3A03F0 3BFF803801FFF338003FC3211B7D9A26>I<3AFFFE03FF80A33A07F0007000A26D13F000035CEB FC0100015CA26C6C485AA2D97F07C7FCA2148FEB3F8E14DEEB1FDCA2EB0FF8A36D5AA26D5AA26D 5A211B7F9A24>I<39FFFC0FFFA33907F003C06C6C485AEA01FC6C6C48C7FCEBFF1E6D5AEB3FF8 6D5A130FA2130780497E497E131EEB3C7F496C7E496C7ED801E07FEBC00F00036D7E3AFFF01FFF 80A3211B7F9A24>120 D E /Fd 4 120 df<0007B712F05A9039C00FE003D81E00EBC000001C16 E01218003816600030494813E0A24816C0A24AC7FC5AA348017E1480C71500A35CA4495AA4495A A4495AA4495AA4495AA449C9FCA313FFB6FCA22C3173B033>84 D<147E903801FF1C903803C3BE 90380F01FEEB1E00013E13FC49137C137813F8000114F85B1203A23907E001F0A4390FC003E0A4 EC07C0A2EA0780140F9038C01F800003133F147F3801E1EF3900FF9F00EB3E1F1300A2143EA45C 123C007C5B387E01F048485A387C0FC0D87FFFC7FCEA1FF81F2D7D9E21>103 D<1307EB0F80131FA21400130E90C7FCABEA03E0487EEA0C78487E1230137C1260A25B12C0A2EA 01F0A3485AA3485AA2485A13811383EA1F03A21306121E5BA2EA0E38EA0FF0EA03C011307AAF16 >105 D119 D E /Fe 6 107 df<13C0A500C013C0EAF0C33838C700EA0EDCEA03F0EA00C0 EA03F0EA0EDCEA38C738F0C3C0EAC0C000001300A512157D9619>3 D15 D<166082A282A28282EE 0380B812E017C0C9EA0380EE06005E5EA25EA25E2B127D9432>33 D<130F1338137013E0EA01C0 B1EA0380EA0700121E12F0121E1207EA0380EA01C0B1EA00E013701338130F10317CA419>102 D<12F0121E1207EA0380EA01C0B1EA00E013701338130F1338137013E0EA01C0B1EA0380EA0700 121E12F010317CA419>I<12C0B3B3AD02317AA40E>106 D E /Ff 3 111 df<120313801300C7FCA6121C12241246A25A120C5AA31231A21232A2121C09177F960C>105 D<121F1206A45AA4EA181C1366138EEA190CEA3200123C123FEA3180EA60C013C4A213C812C013 700F177E9612>107 D110 D E /Fg 5 52 df<1330ABB512FCA238003000AB16187E931B>43 D48 D<12035AB4FC1207B1EA7FF00C157E9412>III E /Fh 5 75 df<1504150C15181530A21560 15C0A2EC0180EC0300A214065CA25C5CA25C5CA2495A49C7FCA213065BA25B5BA25B5BA2485A48 C8FCA212065AA25A5AA25A5A12401E2C81AA1C>10 D<1302131E137EEA01FE120F12FFA2120F12 01EA007E131E13020F0C7E852A>27 D<7E12F012FCB4FC13E013FEA213E0130012FC12F012800F 0C67852A>45 D63 D<124012C012607EA27E7EA27E7EA26C7E6C7EA213607FA27F7FA27F7FA26D7E6D7EA2146080A2 8080A28080A2EC0180EC00C0A215601530A21518150C15041E2C81AA1C>74 D E /Fi 8 40 df28 D<1A30A91A60A61AC0A4F1 0180A3F10300A31906A261A361A261A26161A24E5A4EC7FCA218066060A26060604D5A4DC8FC17 065F17385F17C0EE03804CC9FC161C5E16E0ED03C0031FCAFC157CEC03E0EC1F80D901FCCBFCEB 7FE0D8FFFECCFC13804444C2C385>I<12C0A81260A67EA47EA37EA37EA27EA36C7EA26C7E1360 A27FA27F7FA27F7F6D7EA26D7E146080808080806E7EEC00E015701518150E81ED01C0ED00F016 38160EEE07C0EE01F0EE003EEF0FC0EF01FC9438003FF0953803FFF0F0000F444480C385>II36 D<1C101C30A91C60A71CC0A4F30180A4F30300A31B06A363A263A363A263A263A2505A50C7FCA2 1A06A2626262A262624F5AA24FC8FC190661616161614E5A4EC9FC180E60183018E04D5A4DCAFC 170E173C1770EE01C0EE0780041ECBFC16F8ED03E0031FCCFC15FCEC0FE002FFCDFCEB7FF0B5CE FC13805455D2D4A6>I<124012C0A91260A67EA57EA37EA37EA37EA26C7EA36C7EA21360A27F7F A27FA27F7FA26D7E6D7EA214608080A28080806E7E6E7E1560818181816F7E6F7EED0060163882 1607707EEE00E01778171C1707EF03C0EF00F8183EF007C0F001F8F0003FF107F8963800FFE097 3807FFF8F2001F555580D4A6>II E /Fj 26 122 df45 D<0003B6FC39003E001F013C130E15061502A35BA31402150014 06EBF004A2141CEBFFFCEBF01C140C3801E008A491C7FCA2485AA61207A2EAFFFE20227EA120> 70 D77 D<0003B5FC39003E01E090 383C007881A2153EA25BA45D1578495B4A5AEC0780D9FFFCC7FCEBF00C1407EA01E06E7EA281A3 3803C007A416401680EA07809039C003E10039FFFC01E3C8127C22237EA124>82 D<001FB512FE393C03E03E0038EBC00C00301404122012601240EB078012C01280A200001400A2 49C7FCA6131EA65BA6137C13FC383FFFF01F227AA123>84 D97 DI< 13FF380381C0EA0603120C381C018048C7FC1278127012F0A55A7E148038700100A2EA3806EA1C 18EA07E012157C9416>I<141E14FE141CA61438A6EBFC70EA0383380700F0120C001C13705A00 7813E0127012F0A438E001C0A4EA7003A238380F80381C33C03807C3F817237CA21B>I<13FE38 038380380701C0380C00E0121C5A12781270B5FC00F0C7FCA45AA26C1340007013801230381803 00EA0E0CEA03F013157D9416>III<136013F01201A2 EA00E01300A8EA01C0120F1201A4EA0380A6EA0700A6120E120FEAFFE00C227FA10E>105 D<1378EA03F8EA0070A65BA63901C07FC0EC3E001438143014405CD80383C7FC1384138E13BE13 CF13873807078013036D7EA26D7E80120E000F7F38FFE3FE1A237FA21A>107 D<1378EA03F8EA0070A613E0A6EA01C0A6EA0380A6EA0700A6120E120FEAFFE00D237FA20E>I< 3A01C1F807E03A1FC60C18303A01D80E60389039E007801CA201C013000003491338EB800EA548 48481370A6000E4913E0000F013C13F03AFFE3FF8FFE27157F942A>I<3801C3F0381FCC183801 D00CEBE00EA213C00003131C1380A538070038A6000E1370000F137838FFE7FF18157F941B>I< 137E38038380380600C04813E0001C13705A00781378127012F0A44813F0A214E0EAF001007013 C0EB038038380700EA1C1CEA07F015157D9418>II<3801C7C0381FC8E0EA01D113E1EBE0C0EBC00012035BA548C7FCA612 0E120FEAFFF013157F9413>114 DI<1380A3120113 005AA25A5A5AEAFFF8EA0E00A55AA6EA3810A51320A2EA1C40EA07800D1F7C9E13>I<000E1370 38FE07F0EA0E001470A34813E0A6383801C0A413031305EB0B80381C13C03807E3F815157C941B >I<38FFC0FE381E0078000E133014201440A26C1380A2EB01005B1382EA0384A2138813C8EA01 D0A213E05B12005B17157C941A>I<3AFFC7FC7F803A1E01E03E00391C00C01801011310000E13 E001025BA201045B146001085B00071370D91071C7FCA2EB20721432EB40343803C03CEB8038A2 EB0030141021157C9423>I<390FFC0FE03901E007800000EB030014025CA2EB7008A25C1430EB 7820EB3840A25C133C011DC7FCA2131E131C130C1308A25BA25B5B12F05B00F1C8FC12C2123C1B 1F80941A>121 D E /Fk 29 121 df<127012F8A3127005057C840E>58 D<127012F812FCA212741204A41208A21210A212201240060F7C840E>I<15181578EC01E0EC07 80EC1E001478EB03E0EB0F80013CC7FC13F0EA03C0000FC8FC123C12F0A2123C120FEA03C0EA00 F0133CEB0F80EB03E0EB0078141EEC0780EC01E0EC007815181D1C7C9926>I<14801301A2EB03 00A31306A35BA35BA35BA35BA35BA3485AA448C7FCA31206A35AA35AA35AA35AA35AA311317DA4 18>I<12C012F0123C120FEA03C0EA00F0133EEB0F80EB01E0EB0078141EEC0780EC01E0EC0078 A2EC01E0EC0780EC1E001478EB01E0EB0F80013EC7FC13F0EA03C0000FC8FC123C12F012C01D1C 7C9926>I<027F138090390380810090380E00630138132749131F49130E485A485A48C7FC4814 04120E121E5A5D4891C7FCA35AA55A1520A25DA26C5C12704AC7FC6C130200185B001C5B000613 30380381C0D800FEC8FC21247DA223>67 D73 D76 DI<90397FC003FF0107EB00 781660D905E0132001091440A2EB08F0A2496C13801478A2800120EB0100143E141EA29038400F 02A3EC07820180138415C41403A239010001E8A215F8140000025C1570A21206000F1420EAFFE0 28227EA127>I<903803F01090380E0C20903818026090382001E0EB400001C013C05B1201A200 031480A21500A27FEA01F013FE3800FFE06D7EEB1FF8EB01FCEB003C141C80A30020130CA31408 00601318141000705B5C00C85BD8C603C7FCEA81FC1C247DA21E>83 D97 DI<133FEB E080380380C0EA0701EA0E03121C003CC7FCA25AA35AA400701340A23830018038380200EA1C1C EA07E012157E9415>I<141EEB01FCEB001CA31438A41470A414E01378EA01C4EA0302380601C0 120E121C123C383803801278A338F00700A31408EB0E101270131E38302620EA18C6380F01C017 237EA219>I<137CEA0382EA0701120E121C1238EA7802EA7004EAFFF800F0C7FCA25AA41480A2 38700300EA3004EA1838EA0FC011157D9417>I<141EEC638014C71301ECC30014801303A449C7 FCA4EBFFF8010EC7FCA65BA55BA55BA4136013E0A35B1270EAF18090C8FC1262123C192D7EA218 >I<13F0EA0FE01200A3485AA4485AA448C7FC131FEB2180EBC0C0380F00E0A2120EA2381C01C0 A438380380A2EB0700140400701308130EA2EB061000E01320386003C016237DA21C>104 D<13E0A21201EA00C01300A9121E1223EA4380A21283A2EA87001207120EA35AA25A1320134012 70A2EA3080EA3100121E0B227EA111>I108 D<383C07C03846186038472030388740 3813801300A2000E1370A44813E0A2EB01C014C1003813C2EB0382A2EB018400701388383000F0 18157E941D>110 D<133EEBC180380380C0380700E0120E4813F0123CA25AA338F001E0A214C0 130300701380EB07001306EA381C6C5AEA07E014157E9417>I<3803C0F03804631CEB740EEA08 78EB7007A2140FEA00E0A43801C01EA3143C38038038A2EBC07014E038072180EB1E0090C7FCA2 120EA45AA3EAFFC0181F819418>I114 D<137E138138030080EA0201EA0603140090C7FC120713F8EA 03FE6C7EEA003FEB07801303127000F01300A2EAE002EA4004EA3018EA0FE011157E9417>I<13 6013E0A4EA01C0A4EA0380EAFFFCEA0380A2EA0700A4120EA45AA31308EA3810A21320121813C0 EA07000E1F7F9E12>I<001E131800231338EA438014701283A2EA8700000713E0120EA3381C01 C0A314C2EB0384A21307380C0988EA0E113803E07017157E941C>I<001EEB18180023EB383CD8 4380133EEC701E0083140E1506EA87000007EBE004120EA3391C01C008A31510A2152001031340 D80C0413C0390708E1003801F03E1F157E9423>119 D<3801E0F03806310C38081A1C0010133C EA201C14181400C65AA45BA314083860E01012F0142038E1704038423080383C1F0016157E941C >I E /Fl 45 123 df45 D<13181378EA01F812FFA21201B3A7387FFF E0A213207C9F1C>49 DI<13FE3807FFC0380F07E0381E03F0123FEB81F8A3EA1F 0314F0120014E0EB07C0EB1F803801FE007F380007C0EB01F014F8EB00FCA2003C13FE127EB4FC A314FCEA7E01007813F8381E07F0380FFFC03801FE0017207E9F1C>I<14E013011303A2130713 0F131FA21337137713E7EA01C71387EA03071207120E120C12181238127012E0B512FEA2380007 E0A7EBFFFEA217207E9F1C>I<00101320381E01E0381FFFC0148014005B13F8EA1BC00018C7FC A4EA19FCEA1FFF381E0FC0381807E01303000013F0A214F8A21238127C12FEA200FC13F0A23870 07E0003013C0381C1F80380FFF00EA03F815207D9F1C>II<1260 1278387FFFFEA214FC14F8A214F038E0006014C038C00180EB0300A2EA00065B131C1318133813 78A25BA31201A31203A76C5A17227DA11C>I<13FE3803FFC0380703E0380E00F05A1478123C12 3E123F1380EBE0F0381FF9E0EBFFC06C13806C13C06C13E04813F0381E7FF8383C1FFCEA7807EB 01FEEAF000143E141EA2141C7E007813387E381F01F0380FFFC00001130017207E9F1C>II<1238127C12FEA3127C12381200A81238127C12FEA3127C123807167C95 10>I<007FB612F0B712F8A2CAFCA9B712F8A26C15F0250F7D932C>61 D67 D69 D72 DI76 DI< EB07FC90383FFF809038FC07E03903F001F848486C7E4848137E48487FA248C7EA1F80A24815C0 007E140FA200FE15E0A9007E15C0007F141FA26C15806D133F001F15006C6C137E6C6C5B6C6C48 5A3900FC07E090383FFF80D907FCC7FC23227DA12A>79 DI<3801FC 043807FF8C381F03FC383C007C007C133C0078131CA200F8130CA27E1400B4FC13E06CB4FC14C0 6C13F06C13F86C13FC000313FEEA003FEB03FFEB007F143FA200C0131FA36C131EA26C133C12FC B413F838C7FFE00080138018227DA11F>83 D<007FB61280A2397E03F80F007814070070140300 60140100E015C0A200C01400A400001500B3A20003B512F8A222227EA127>I91 D93 D97 D99 DI<13FE3807FF80380F87C0 381E01E0003E13F0EA7C0014F812FCA2B5FCA200FCC7FCA3127CA2127E003E13186C1330380FC0 703803FFC0C6130015167E951A>II<3803FC1E380FFF7F381F0F8F383E07CF383C03 C0007C13E0A5003C13C0EA3E07381F0F80EBFF00EA13FC0030C7FCA21238383FFF806C13F06C13 F84813FCEA380048133E00F0131EA40078133C007C137C383F01F8380FFFE00001130018217E95 1C>I I<121C123E127FA3123E121CC7FCA7B4FCA2121FB2EAFFE0A20B247EA310>I108 D<3AFF07F007F090391FFC1FFC3A1F303E303E01401340496C487E A201001300AE3BFFE0FFE0FFE0A22B167E9530>I<38FF07E0EB1FF8381F307CEB403CEB803EA2 1300AE39FFE1FFC0A21A167E951F>I<13FE3807FFC0380F83E0381E00F0003E13F848137CA300 FC137EA7007C137CA26C13F8381F01F0380F83E03807FFC03800FE0017167E951C>I<38FF0FE0 EB3FF8381FF07CEB803E497E1580A2EC0FC0A8EC1F80A29038803F00EBC03EEBE0FCEB3FF8EB0F C090C8FCA8EAFFE0A21A207E951F>I114 DI<487EA41203A21207A2120F123FB5FCA2EA0F80ABEB8180A5EB8300EA07C3EA03FEEA00F811 207F9F16>I<38FF01FEA2381F003EAF147E14FE380F81BE3907FF3FC0EA01FC1A167E951F>I<39 FFE01FE0A2390F800600A2EBC00E0007130CEBE01C00031318A26C6C5AA26C6C5AA2EB7CC0A213 7F6D5AA26DC7FCA2130EA21B167F951E>I<3AFFE7FF07F8A23A1F007800C0D80F80EB0180147C A23A07C07E030014DE01E05B0003EBDF06EBE18FD801F15B01F3138C9038FB079C000014D8EBFE 03017E13F0A2EB7C01013C5BEB380001185B25167F9528>I<39FFE07FC0A2390F801C006C6C5A 6C6C5AEBF0606C6C5A3800F980137F6DC7FC7F80497E1337EB63E0EBC1F03801C0F848487E3807 007E000E133E39FF80FFE0A21B167F951E>I<387FFFF0A2387C03E0387007C0EA600F38E01F80 00C01300133E137EC65A5B485A00031330EA07E013C0380F8070121F383F0060003E13E0EA7C03 B5FCA214167E9519>122 D E /Fm 40 123 df49 DII<157815F8140114031407A2140F141F143F147F147714F7EB01E7EB03C7EB07 871407130F131E133C1378137013F0EA01E0EA03C0EA0780EA0F00A2121E5A5A5AB712F0A3C738 0FF800A9010FB512F0A3242E7EAD29>I<000C1438390FC003F890B5FC15F015E015C01580ECFE 005C14F091C7FC90C8FCA7EB0FF8EB7FFF90B512C09038F01FE09038800FF090380007F8000E14 FCC7120315FEA215FFA2121E123FEA7F8012FF13C015FE1380A2397F0007FC007C14F8003CEB0F F06CEB1FE0390FC07FC06CB512800001EBFE0038003FE0202E7CAD29>II<1238123E003FB612C0A316804815005D5D5D5D387800010070495A4A 5A00F0495A4891C7FC141E143EC75A5CA2495AA213035C1307A2130FA2495AA3133FA5137FA86D 5AA2010EC8FC22307BAF29>II<913A03FF800180023FEBF00349B5EAFC0F01079038007F1FD91FF8EB0FBFD93FE0EB03FF D9FF8013004890C8127F4848153F485A171F485A001F160F5B003F1607A2127F5B94C7FCA212FF A9127FA36DED0380123FA2121F6D1507000F17006C7E170E6C6C151E6C6C5D6C6D5CD93FE05CD9 1FF8EB03E0D907FFEB3F800101D9FFFEC7FCD9003F13F80203138031317BB03C>67 D69 D72 DI76 DI79 DI82 D<90391FF0018090B51203000314C73907F00FFF380F800148C7127F48141F003E140F127E1507 12FEA215037EA26D90C7FC13E0EA7FFCEBFFE014FE6CEBFFC06C14F0816C800003806C806C6C14 80131F010014C01407020013E0153FA2151F126000E0140FA316C07EA26CEC1F807EB4EC3F0001 C0137E9038FC01FC00F1B55AD8E03F13E0D8C00790C7FC23317BB02E>I<003FB8FCA39039E00F FC01D87F009138003F80007E161F007C160F00781607A200701603A448EE01C0A4C792C7FCB3AA 017FB67EA332307DAF39>I97 D99 DII<14FF010713C0011F13E090383FC7F090387F0FF813FE120113FC0003 EB07F0EC03E0EC01C091C7FCA7B512F8A3D803FCC7FCB3A8387FFFF0A31D327EB119>I<90391F F007E09039FFFE3FF0489038FF7FF83907F83FF1390FE00FE1EDE0F03A1FC007F0601600003F80 A5001F5CA26C6C485AA23907F83FC090B5C7FC00065B380E1FF090C9FC121EA2121F7F90B512C0 6C14F815FE6C806C15804815C0001F15E048C7127F007EEC0FF04814071503A4007EEC07E06CEC 0FC0D81FC0EB3F803A0FF801FF006CB55AC614F0011F1380252F7E9F29>III 108 D<2703F007F8EB0FF000FFD93FFFEB7FFE4A6DB5FC913BF03FC1E07F803D0FF1C01FE3803F C03C07F3000FE6001F01F602FC14E013FE495CA2495CB3B500C1B50083B5FCA340207D9F45>I< 3903F007F800FFEB3FFF4A7F9138F03FC03A0FF1C01FE03907F3000F01F68013FE5BA25BB3B500 C1B51280A329207D9F2E>II<3901F80FF000FFEB 7FFE01F9B512809039FFE07FC0000F9038001FE06C48EB0FF001F8EB07F816FC150316FEA21501 16FFA816FE1503A216FC15076D14F86DEB0FF06DEB1FE09039FBE07FC001F9B512009038F87FFE EC1FE091C8FCABB512C0A3282E7E9F2E>I<3803F03F00FFEB7FC09038F1FFE09038F3C7F0000F EB8FF83807F70F13F613FE9038FC07F0EC03E0EC0080491300B2B512E0A31D207E9F22>114 DI<1338A51378A313F8A2120112031207121FB5 12FEA33807F800B01407A70003130E13FC3801FE1C3800FFF8EB7FF0EB0FE0182E7EAD20>IIII< B5EBFFFCA3D807F8EB1F806C6CEB1E006C6C5B6C6C5B6E5A90387FC1E0133F90381FE3C090380F F7806DB4C7FC5C130313016D7E497F81497F9038079FF0EB0F0F90381E07F8496C7E496C7E01F0 7F48486C1380ED7FC00007143F3AFFF801FFFEA327207E9F2C>I<003FB512FCA39038C00FF839 3E001FF0003C133F003814E00078EB7FC0ECFF80EA70011500495A495AC6485AA2495A495A9038 7FC00EA2EBFF80481300485A0007141E5B4848131C4848133C003F147C4913FC387FC007B6FCA3 1F207E9F25>122 D E /Fn 49 122 df<1338137813F0EA01E0EA03C0EA0780EA0F00120E5AA2 5AA25AA35AAA1270A37EA27EA27E120FEA0780EA03C0EA01E0EA00F8137813380D2878A21A>40 D<126012F012787E7E7EEA07801203EA01C0A2EA00E0A21370A31338AA1370A313E0A2EA01C0A2 EA03801207EA0F00121E5A5A5A12600D287CA21A>I<1218123E127E127F123F121F1207120EA2 121C12FC12F812E0080D77851A>44 D<1230127812FCA212781230060676851A>46 D<13C01201A212031207120F127F12FD12711201B2EA7FFFA3101E7B9D1A>49 D<1230127812FCA2127812301200A91230127812FCA212781230061576941A>58 D<1218123C127EA2123C12181200A91218123C127EA2123E121E120EA2121C123C12F812F012C0 071C77941A>I<1338137CA2136C13EEA313C6A2EA01C7A438038380A4380701C0A213FFA24813 E0EA0E00A4481370387F01FC38FF83FE387F01FC171E7F9D1A>65 DIIII<387FFFFCB5FC7E380E001C A41400A3EB0380A3EA0FFFA3EA0E03A390C7FCA8EA7FE012FF127F161E7F9D1A>II73 D76 D<007E133FB4EB7F806C1400381D80DCA313C1A2001C139CA213E3A2EB631C1377A21336A2133E 131CA21300A7007F137F39FF80FF80397F007F00191E809D1A>I<38FE03FE12FFA2381D8070A2 13C0121CA213E0A213601370A213301338A21318131CA2130C130EA21306A213071303A238FF81 F0A21380171E7F9D1A>II I82 D<3803F1C0EA0FFDEA3FFFEA 7C0FEA700312E01301A390C7FC12701278123FEA1FF0EA07FEC67EEB0F80EB03C01301EB00E0A2 126012E0A2EB01C012F038FC0780B5FC38EFFE00EAE3F8131E7D9D1A>I<387FFFFEB5FCA238E0 380EA400001300B3A23803FF80A3171E7F9D1A>I<38FF83FEA3381C0070B3A26C13E0A2380701 C013833803FF806C1300EA007C171E7F9D1A>I<38FF01FEA3381C0070A3001E13F0000E13E0A3 380701C0A438038380A43801C700A4EA00C613EEA3136C137CA21338171E7F9D1A>I<00FE13FE EAFF01EAFE000070131C0078133C00381338A7137C001C137013EEA513C6A2380DC760A31383A3 000F13E0A2380701C0171E7F9D1A>I<38FF01FEA3381C00706C13E0A2380701C0A21383000313 8013C700011300A2EA00EEA2137CA21338AA48B4FCA3171E7F9D1A>89 D97 D<12FEA3120EA6133EEBFF80000F13E0EBC1F0EB8070EB0038120E 141CA7000F13381478EB80F0EBC1E0EBFFC0000E138038063E00161E7F9D1A>IIIII<3801F87C3807FFFE5A381E07 8C381C0380383801C0A5381C0380EA1E07381FFF005BEA39F80038C7FCA27E381FFF8014E04813 F83878007C0070131C48130EA40070131C0078133C003E13F8381FFFF0000713C0000113001721 7F941A>I<12FEA3120EA6133EEBFF80000F13C013C1EB80E01300120EAC38FFE3FE13E713E317 1E7F9D1A>I<13C0487EA26C5A90C7FCA6EA7FE0A31200AF387FFF80B512C06C1380121F7C9E1A> I<12FEA3120EA6EB0FFCEB1FFEEB0FFCEB03C0EB0780EB0F00131E5B5B13FC120F13DE138F380E 07801303EB01C014E0EB00F038FFE3FE14FF14FE181E7F9D1A>107 DI<387CE0E038FFFBF8EA7FFF381F1F1CEA1E1EA2EA1C1CAC387F1F1F39FF9F 9F80397F1F1F00191580941A>IIII<387F83F038FF8FF8387FBFFC3803FC3CEBF018EBE0005B A25BAAEA7FFFB5FC7E16157E941A>114 D<3807FB80EA1FFF127FEA7807EAE003A30078C7FCEA 7FC0EA3FFCEA07FE38003F801307386001C012E0A2EAF00338FC0780B51200EAEFFEEAE3F81215 7C941A>I<13C01201A6387FFFE0B5FCA23801C000AA1470A43800E0E013FFEB7FC0EB1F00141C 7F9B1A>I<38FE0FE0A3EA0E00AD1301EA0F033807FFFE7EEA00FC17157F941A>I<38FF83FE13C7 138338380038A26C1370A31338137CA2380E6CE0A213EEA313C6000613C0EA07C7A23803838017 157F941A>119 D<387FC7F8EBCFFCEBC7F8380703C038038380EBC700EA01EFEA00FE137C1378 1338137C13EE120113C738038380000713C0EA0F01387FC7FC00FF13FE007F13FC17157F941A> I<387FC3FC38FFC7FE387FC3FC380E00E0A27EEB01C013811203EB838013C31201EBC700EA00E7 A213E61366136E133CA31338A35BA21230EA78E01271EA7FC06C5A001EC7FC17207F941A>I E /Fo 85 125 df<90381F83E09038706E309038C07C78380180F8000313F03907007000A9B612 C03907007000B21478397FE3FF801D2380A21C>11 DII<90380FC07F903970 31C0809039E00B00402601801E13E00003EB3E013807003C91381C00C01600A7B712E03907001C 011500B23A7FF1FFCFFE272380A229>I34 DI<7FA2EA03F0EA0C8CEA1082EA208112603840808012C01387A338E083001380127012 78123F13E0EA1FF8EA07FCEA01FEEA009F1387A2EB8380A2EAF081A312E000801300EA4083A2EA 2086EA1084EA0898EA07E0EA0080A311287DA418>II<133C136213C2 EA0181A21203A41382A213841388EA01C813D09039E003FF809039C0007C006C6C133800011430 6D1320D802705B1204486C5BEA183C26301C01C7FC38701E02130E38F0070414881303903801D0 01EB00E00078EB70030038EBB802393C031C04390E0C0E0C3903F003F021257EA326>I<127012 F812FCA212741204A41208A21210A212201240060F7CA20E>I<132013401380EA01005A120612 04120CA25AA25AA312701260A312E0AE1260A312701230A37EA27EA2120412067E7EEA00801340 13200B327CA413>I<7E12407E7E12187E12041206A27EA2EA0180A313C01200A313E0AE13C0A3 12011380A3EA0300A21206A21204120C5A12105A5A5A0B327DA413>I<497EB0B612FEA2390001 8000B01F227D9C26>43 D<127012F812FCA212741204A41208A21210A212201240060F7C840E> II<127012F8A3127005057C840E>I<14801301A2EB0300A31306A35BA3 5BA35BA35BA35BA3485AA448C7FCA31206A35AA35AA35AA35AA35AA311317DA418>II<13801203120F12F31203B3A9EA07C0EAFFFE0F217CA018> III<13021306130EA2131EA2132E134EA2138EA2EA010E1202 A21204A212081210A21220A212401280B512F838000E00A7131F3801FFF015217FA018>I<0010 1380381E0700EA1FFF5B13F8EA13E00010C7FCA613F8EA130EEA1407381803801210380001C0A2 14E0A4127012F0A200E013C01280EA4003148038200700EA1006EA0C1CEA03F013227EA018>I< 137EEA01C138030080380601C0EA0E03121C381801800038C7FCA212781270A2EAF0F8EAF30CEA F4067F00F81380EB01C012F014E0A51270A3003813C0A238180380001C1300EA0C06EA070CEA01 F013227EA018>I<12401260387FFFE014C0A23840008038C0010012801302A2485A5BA25B1330 13201360A313E05BA21201A41203A86C5A13237DA118>II< EA01F0EA060C487EEA1807383803801270A238F001C0A314E0A5127013031238EA1805120CEA06 19EA03E1380001C0A3EB0380A200301300EA78071306EA700CEA20186C5AEA0FC013227EA018> I<127012F8A312701200AB127012F8A3127005157C940E>I<127012F8A312701200AB127012F8 A312781208A41210A312201240A2051F7C940E>I61 D<497EA3497EA3EB05E0A2EB0DF01308A2497E1478A2497EA3497EA3497EA290B5FC3901000780 A24814C000021303A24814E01401A2000CEB00F0A2003EEB01F839FF800FFF20237EA225>65 DI<903807E0109038381830EBE0063901C0017039038000F048C7FC000E1470121E001C14 30123CA2007C14101278A200F81400A812781510127C123CA2001C1420121E000E14407E6C6C13 803901C001003800E002EB381CEB07E01C247DA223>III< B612C0380F80070007130114001540A215601520A314201500A3146014E013FF138014601420A4 91C7FCA9487EEAFFFE1B227EA120>I<903807F00890383C0C18EBE0023901C001B839038000F8 48C71278481438121E15185AA2007C14081278A200F81400A7EC1FFF0078EB00F81578127C123C A27EA27E7E6C6C13B86C7E3900E0031890383C0C08903807F00020247DA226>I<39FFFC3FFF39 0FC003F039078001E0AE90B5FCEB8001AF390FC003F039FFFC3FFF20227EA125>II<3803FFF038001F007FB3A6127012F8A2130EEAF0 1EEA401C6C5AEA1870EA07C014237EA119>I<39FFFC03FF390FC000F86C48136015405D4AC7FC 14025C5C5C5C5C5C1381EB83C0EB87E01389EB88F01390EBA078EBC03C13808080A26E7E811403 6E7EA26E7E81486C7F3AFFFC07FF8021227EA126>III<39FF8007FF3907C000F81570D805E013 20EA04F0A21378137C133C7F131F7FEB0780A2EB03C0EB01E0A2EB00F014F81478143C143E141E 140FA2EC07A0EC03E0A21401A21400000E1460121FD8FFE0132020227EA125>III82 D<3803F020380C0C60EA18 02383001E0EA70000060136012E0A21420A36C1300A21278127FEA3FF0EA1FFE6C7E0003138038 003FC0EB07E01301EB00F0A214707EA46C1360A26C13C07E38C8018038C60700EA81FC14247DA2 1B>I<007FB512F839780780780060141800401408A300C0140C00801404A400001400B3A3497E 0003B5FC1E227EA123>I<39FFFC07FF390FC000F86C4813701520B3A5000314407FA200011480 6C7E9038600100EB3006EB1C08EB03F020237EA125>II<3BFFF03FFC03FE3B1F80 07E000F86C486C4813701720A26C6C6C6C1340A32703C002F01380A33B01E004780100A33A00F0 083C02A39039F8183E06903978101E04A2137C90393C200F08A390391E400790A390390F8003E0 A36D486C5AA36D5C010213002F237FA132>I<397FF807FF3907E001F83903C000E06D5B00015C 6C6C48C7FC6D5AEB7802EB7C04EB3E0CEB1E08EB1F10EB0FB0EB07A014C06D7E130180497EEB02 78EB047CEB0C3EEB081EEB101F9038300F80EB200701407F9038C003E0EB8001D801007F481300 4880391F8001FC3AFFE007FFC022227FA125>II<12FEA212C0B3B3A912FEA207317BA40E> 91 D I<12FEA21206B3B3A912FEA207317FA40E>I97 D<120E12FE121E120EAB131FEB61C0EB8060380F0030000E1338143C141C141EA7141C143C1438 000F1370380C8060EB41C038083F0017237FA21B>II<14E013 0F13011300ABEA01F8EA0704EA0C02EA1C01EA38001278127012F0A7127012781238EA1801EA0C 0238070CF03801F0FE17237EA21B>II<133C 13C6EA018F1203130FEA0700A9EAFFF8EA0700B21380EA7FF8102380A20F>I<14703801F19838 071E18EA0E0E381C0700A2003C1380A4001C1300A2EA0E0EEA0F1CEA19F00010C7FCA21218A2EA 1FFE380FFFC014E0383800F0006013300040131812C0A300601330A2003813E0380E03803803FE 0015217F9518>I<120E12FE121E120EABEB1F80EB60C0EB80E0380F0070A2120EAF38FFE7FF18 237FA21B>I<121C123EA3121CC7FCA8120E12FE121E120EB1EAFFC00A227FA10E>II< 120E12FE121E120EABEB03FCEB01F014C01480EB02005B5B5B133813F8EA0F1CEA0E1E130E7F14 80EB03C0130114E0EB00F014F838FFE3FE17237FA21A>I<120E12FE121E120EB3ADEAFFE00B23 7FA20E>I<390E1FC07F3AFE60E183803A1E807201C03A0F003C00E0A2000E1338AF3AFFE3FF8F FE27157F942A>I<380E1F8038FE60C0381E80E0380F0070A2120EAF38FFE7FF18157F941B>III<3801F82038070460EA0E02EA1C01003813E0EA7800A25AA712701278EA3801121CEA0C02EA 070CEA01F0C7FCA9EB0FFE171F7E941A>III<1202A41206A3120E 121E123EEAFFF8EA0E00AB1304A6EA07081203EA01F00E1F7F9E13>I<000E137038FE07F0EA1E 00000E1370AD14F0A238060170380382783800FC7F18157F941B>I<38FFC1FE381E0078000E13 301420A26C1340A238038080A33801C100A2EA00E2A31374A21338A3131017157F941A>I<39FF 8FF8FF391E01E03C001CEBC018120EECE010A239070260201470A239038430401438A23901C818 80141CA23900F00D00140FA2EB6006A320157F9423>I<38FF83FE381F01F0380E00C06C138038 0381001383EA01C2EA00E41378A21338133C134E138EEA0187EB0380380201C0000413E0EA0C00 383E01F038FF03FE17157F941A>I<38FFC1FE381E0078000E13301420A26C1340A238038080A3 3801C100A2EA00E2A31374A21338A31310A25BA35B12F05B12F10043C7FC123C171F7F941A>I< 383FFFC038380380EA300700201300EA600EEA401C133C1338C65A5B12015B38038040EA07005A 000E13C04813805AEA7801EA7007B5FC12157F9416>III E /Fp 36 123 df45 D<127012F8A212F012E005057A840F>I< 1403A25CA25CA25C142FA2144F15801487A2EB01071302A21304A21308A2131013301320EB7FFF 90384007C013801403EA01005A12025AA2120C003C1307B4EB3FFC1E237DA224>65 D<027F138090390380810090380E00630138132749131F49130E485A485A48C7FC481404120E12 1E5A5D4891C7FCA35AA55A1520A25DA26C5C12704AC7FC6C130200185B001C5B00061330380381 C0D800FEC8FC212479A223>67 D<90B512F090380F003C150E81011EEB0380A2ED01C0A25B16E0 A35BA449EB03C0A44848EB0780A216005D4848130E5D153C153848485B5D4A5A0207C7FC000F13 1CB512F023227DA125>I<90B6128090380F00071501A2131EA21600A25BA2140192C7FCEB7802 A21406140EEBFFFCEBF00CA33801E008A21504EC0008485AA25DA248485B15605D1401000F1307 B65A21227DA121>I<027F138090390380810090380E00630138132749131F49130E485A485A48 C7FC481404120E121E5A5D4891C7FCA35AA4EC3FFC48EB01E0A34A5AA27E12704A5A7E0018130F 001C131300060123C7FC380381C1D800FEC8FC212479A226>71 D<903807FFC09038003C00A35C A45CA4495AA4495AA4495AA449C7FCA212381278EAF81EA2485AEA40385BEA21E0EA1F801A237C A11A>74 D77 D<14FE903807838090380C00E0013813704913385B4848131C485A48C7FC48141E121E121C123C A25AA348143CA31578A25A15F0A2EC01E015C06C1303EC0780007014000078130E00385B6C5B6C 13E038070380D801FCC7FC1F2479A225>79 D<90B512E090380F0038151E150E011E1307A44913 0FA3151E5B153C157815E09038F003C09038FFFE0001F0C7FCA2485AA4485AA4485AA4120FEAFF F820227DA121>I<90B512C090380F0070153C151C011E130EA2150FA249131EA3153C49133815 70EC01E0EC07809038FFFC00EBF00E80EC0380D801E013C0A43903C00780A43907800F001501A2 EC0702120F39FFF8038CC812F020237DA124>82 D<001FB512F8391E03C0380018141812303820 0780A200401410A2EB0F001280A200001400131EA45BA45BA45BA4485AA41203B5FC1D2277A123 >84 D97 DI<137EEA01C138030180EA0703EA0E07121C003CC7FC12381278A35AA45B12701302 EA300CEA1830EA0FC011157B9416>I<143CEB03F8EB0038A31470A414E0A4EB01C013F9EA0185 EA0705380E0380A2121C123C383807001278A3EAF00EA31410EB1C201270133C38305C40138C38 0F078016237BA219>I<13F8EA0384EA0E02121C123C1238EA7804EAF018EAFFE0EAF000A25AA4 1302A2EA6004EA7018EA3060EA0F800F157A9416>I<143E144714CFEB018F1486EB0380A3EB07 00A5130EEBFFF0EB0E00A35BA55BA55BA55BA45B1201A2EA718012F100F3C7FC1262123C182D82 A20F>II<13F0EA 0FE01200A3485AA4485AA448C7FC131FEB2180EBC0C0380F00E0A2120EA2381C01C0A438380380 A3EB070400701308130E1410130600E01320386003C016237DA219>I<13C0EA01E013C0A2C7FC A8121C12231243A25AA3120EA25AA35AA21340EA7080A3EA71001232121C0B217BA00F>I 108 D<391C0F80F8392610C10C39476066063987807807A2EB0070A2000EEBE00EA44848485AA3 ED38202638038013401570168015303A7007003100D83003131E23157B9428>II<137EEA01C338038180380701C0120E001C13E0123C12381278A338F0 03C0A21480130700701300130E130CEA3018EA1870EA07C013157B9419>I<3801C1F038026218 3804741C3808780CEB700EA2141EEA00E0A43801C03CA3147838038070A2EBC0E0EBC1C0380723 80EB1E0090C7FCA2120EA45AA3EAFFC0171F7F9419>I114 D<13FCEA018338020080EA0401EA0C 03140090C7FC120F13F0EA07FC6C7EEA003E130F7F1270EAF006A2EAE004EA4008EA2030EA1FC0 11157D9414>I<13C01201A4EA0380A4EA0700EAFFF8EA0700A2120EA45AA45AA31310EA7020A2 13401380EA3100121E0D1F7C9E10>I<001E1360002313E0EA4380EB81C01283EA8701A2380703 80120EA3381C0700A31408EB0E101218121CEB1E20EA0C263807C3C015157B941A>I<381E0380 382307C0EA43871383EA8381EA8700A200071380120EA3381C0100A31302A25B5BA2EA0C30EA03 C012157B9416>I<001EEB60E00023EBE1F0EA4380EB81C000831470D887011330A23907038020 120EA3391C070040A31580A2EC0100130F000C13023806138C3803E0F01C157B9420>I<3803C1 E0380462103808347038103CF0EA203814601400C65AA45BA314203861C04012F1148038E2C100 EA4462EA383C14157D9416>I<001E133000231370EA438014E01283EA8700A2380701C0120EA3 381C0380A4EB0700A35BEA0C3EEA03CEEA000EA25B1260EAF0381330485AEA80C0EA4380003EC7 FC141F7B9418>I<3801E0203803F0603807F8C038041F80380801001302C65A5B5B5B5B5B48C7 FC120248138038080100485AEA3F06EA61FCEA40F8EA807013157D9414>I E /Fq 13 119 df<127812FCA4127806067B8511>46 D75 D83 D<007FB612F8A2397C007C00007015380060151800401508A200C0150CA2481504A5C714 00B3A614FE90B512FEA226297EA82B>I<3DFFFE03FFF803FFC0A23D0FE0003F80007E006C486D C712186C7E6F6C1310A26C6C5E82A26C6C5EED13E0A26D16C0017CD933F05B1521137E013E6E48 C7FC1540A26D1502ED807CA2D90F805C913881003EA2D907C15C02C2131FA2D903E25C02E4EB0F 90A2D901F414A002F8EB07E0A201005D4A1303A202705C02601301A33A2A7FA83D>87 D97 D<137E3803C380380700E0000E13F0481370003C1378143848133CA212F8A2B512FC00F8C7FCA5 1278127C003C1304A26C1308000E13106C13203801C0C038007F00161A7E991B>101 D103 D<120FEA1F80A4EA0F00C7FCA9EA0780127FA2120F1207B3A2EAFFF8A20D297FA811>105 D<137813FCA413781300A9137CEA07FCA2EA007C133CB3AAEA703812F8137012F0EA60C0EA1F80 0E3582A812>I<380783F838FF8C1CEB900E380FA0070007148013C0A21380B139FFFCFFFCA21E 1A7F9921>110 D<7FA41201A31203A21207120F381FFF80B5FC38078000AD1440A73803C08012 013800E100133E12257FA417>116 D<39FFF00FF8A2390F8003C000071480EC01003803C002A2 13E000015BA26C6C5AA2EBF818EB7810A26D5AA2EB3E60EB1E40A26D5AA26DC7FCA313021D1A7F 9920>118 D E /Fr 14 120 df77 D82 D<003FB812F8A3D9E001EB800790C7EB0001007CEE007C0078173CA20070171C A20060170CA500E0170E481706A4C81500B3B1020313C0011FB612F8A3373B7DBA3E>84 D97 D99 D101 D<143F903801FFC0903803E0E090380781F090380F83F8EB1F07133E137EEC03F090387C01E001 FCC7FCAEB512FCA3D800FCC7FCB3AC487E387FFFFCA31D3D7FBC1A>I<903907F001F890393FFE 0FFC90397C1F1E3E9038F007F03A01E003E01C2603C00113080007ECF000000F80EB8000001F80 A7000F5CEBC00100075C00035C6C6C485A6D485A26037C1FC7FC38073FFE380607F090C9FC120E A3120FA2EA07C090B512C06C14FC6C14FF6C1580000315C03A0780003FE0001FC7EA07F0003EEC 01F8003C1400127C0078157C12F8A5007C15F8A26CEC01F06CEC03E06C6CEB07C0D803E0EB1F00 D801FC13FE39003FFFF00107138027397EA52B>I105 D108 D<3901F807F800FFEB1FFEEC781F9138E00F803A07F980 07C02601FB007F150301FE805BA35BB3A5486C497EB500F1B512E0A32B267EA530>110 D<3903F00F8000FFEB3FE0EC70F0ECC1F83807F1833801F30313F6EC01F0EC004001FC1300A45B B3A3487EB512F8A31D267EA522>114 D117 D119 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300 TeXDict begin %%EndSetup %%Page: 20 1 bop 0 162 a Fm(References)0 271 y Fo([1])24 b(Alfred)18 b(V.)h(Aho)h(and)g (M.)f(J.)g(Corasic)o(k.)31 b(E\016cien)o(t)18 b(string)i(matc)o(hing:)27 b(An)19 b(aid)h(to)g(bibliogrpahic)76 332 y(searc)o(h.)h Fp(Communic)n (ations)c(of)h(the)g(A)o(CM)p Fo(,)d(18\(6\):333{340,)k(June)d(1975.)0 433 y([2])24 b(Alfred)13 b(V.)g(Aho,)i(Mahadev)m(an)g(Ganapathi,)g(and)g (Stev)o(en)e(W.)h(K.)g(Tjiang.)k(Co)q(de)d(generation)g(using)76 493 y(tree)g(matc)o(hing.)20 b(to)d(b)q(e)f(published.)0 595 y([3])24 b(Alfred)17 b(V.)h(Aho)g(and)h(Stephen)g(C.)f(Johnson.)29 b(Optimal)17 b(co)q(de)h(generation)h(for)g(expression)f(trees.)76 655 y Fp(Journal)f(of)h(the)f(A)o(CM)p Fo(,)f(23\(3\):458{501,)j(July)d (1976.)0 757 y([4])24 b(Alfred)16 b(V.)g(Aho)i(and)f(Je\013rey)g(D.)g (Ullman.)22 b Fp(Principles)e(of)e(Compiler)g(Design)p Fo(.)25 b(Addison)18 b(W)l(esley)l(,)76 817 y(April)d(1979.)0 919 y([5])24 b(Mahadev)m(an)19 b(Ganapathi.)28 b Fp(R)n(etar)n(getable)20 b(Co)n(de)e(Gener)n(ator)h(and)g(Optimization)h(using)g(A)o(ttribute)76 979 y(Gr)n(ammars)p Fo(.)f(PhD)e(thesis,)e(Univ)o(ersit)o(y)f(of)i(Wisconsin) h({)f(Madision,)g(1980.)0 1081 y([6])24 b(Rob)q(ert)e(Rettig)g(Henry)l(.)37 b Fp(Gr)n(aham-Glanvil)r(le)24 b(Co)n(de)e(Gener)n(ators)p Fo(.)38 b(PhD)23 b(thesis,)f(Univ)o(ersit)o(y)e(of)76 1141 y(California)c(at)h(Berk)o(eley)l(,)c(Ma)o(y)i(1984.)0 1243 y([7])24 b(Christoph)18 b(M.)f(Ho\013mann)g(and)h(Mic)o(hael)e(J.)h (O'Donnell.)24 b(P)o(attern)17 b(matc)o(hing)f(in)i(trees.)24 b Fp(Journal)76 1303 y(of)17 b(the)h(A)o(CM)p Fo(,)d(29\(1\):68{95,)k(Jan)o (uary)d(1982.)0 1405 y([8])24 b(Stephen)17 b(C.)h(Johnson.)27 b(Y)l(acc)17 b({)h(y)o(et)f(another)i(compiler-com)o(pil)o(er.)k(Comp.)16 b(Sci.)h(T)l(ec)o(h.)g(Rep.)g(32,)76 1465 y(A)l(T&T)f(Bell)f(Lab)q (oratories,)i(July)f(1975.)951 2757 y(20)p eop %%Page: 19 2 bop 0 162 a Fm(8)83 b(P)n(erformance)0 271 y Fo(So)17 b(far,)f(the)g(only)g (exp)q(erience)f(w)o(e)h(ha)o(v)o(e)g(with)g Fp(twig)h Fo(is)f(a)h(V)-5 b(AX)15 b(co)q(de)h(generator)h(written)f(for)h(the)f(p)q(cc2)0 332 y(compiler.)38 b(The)22 b Fp(twig)h Fo(co)q(de)g(generator)g(is)g(25\045) f(faster)h(than)g(the)f(original)h(co)q(de)f(generator.)41 b(The)0 392 y(main)o(tainabilit)o(y)15 b(and)j(mo)q(di\014abilit)o(y)d(of)j (the)g(co)q(de)g(generator)g(has)h(impro)o(v)o(ed.)k(F)l(or)18 b(example)d(adding)0 452 y(the)f(indexed)e(addressing)j(mo)q(de)e(in)o(to)g (the)h(co)q(de)g(generator)g(to)q(ok)g(only)g(a)g(few)g(hours.)21 b(The)14 b(target)g(co)q(de)0 512 y(qualit)o(y)h(is)h(just)g(as)h(go)q(o)q(d) i(as)d(the)g(original)h(co)q(de)f(generator.)73 572 y(The)21 b Fn(twig)d Fo(table)i(generation)h(algorithm)e(is)i(fast.)34 b(F)l(or)20 b(the)g(V)-5 b(AX)19 b(mac)o(hine)f(description)i(whic)o(h)0 633 y(consist)h(of)g(109)i(rules,)e(the)f(generation)i(time)c(w)o(as)k(4.2)f (seconds)h(on)f(a)g(780.)37 b(The)21 b(generation)g(time)0 693 y(could)14 b(b)q(e)g(increased)f(b)o(y)g(t)o(w)o(o)h(orders)g(of)g (magnitude)e(b)q(efore)i(other)g(table)g(driv)o(en)e(system)h(can)h(comp)q (ete)0 753 y(with)19 b Fn(twig)f Fo(on)i(this)g(basis.)31 b(F)l(urthermore,) 18 b(the)i(tables)f(are)h(small.)29 b(The)19 b(V)-5 b(AX)18 b(description)h(is)g(only)0 813 y(7.5K)14 b(and)g(the)f(text)g(space)h(for)g (the)f(w)o(alk)o(er)g(is)g(30K.)h(Again)g(this)f(is)h(m)o(uc)o(h)d(smaller)h (than)i(those)g(of)g(other)0 873 y(table)i(driv)o(en)f(systems.)73 934 y Fp(Twig)20 b Fo(is)e(curren)o(tly)f(a)i(researc)o(h)g(to)q(ol.)29 b(Sev)o(eral)18 b(things)h(can)g(b)q(e)g(done)g(to)g(impro)o(v)o(e)d Fp(twig)p Fo('s)j(p)q(erfor-)0 994 y(mance.)73 1095 y Fe(\017)24 b Fp(Twig)g Fo(do)q(es)g(a)g(lot)g(of)g(pro)q(cedure)f(calls.)43 b(Ev)o(ery)22 b(mac)o(hine)g(transition)h(require)g(at)g(least)h(one)122 1156 y(pro)q(cedure)16 b(call.)21 b(Con)o(trast)c(this)f(to)g(Y)l(A)o(CC)g (where)g(a)g(mac)o(hine)e(transition)j(is)f(done)g(in)g(line.)73 1257 y Fe(\017)24 b Fp(Twig)19 b Fo(p)q(erforms)g(a)g(v)o(ery)e(exp)q(ensiv)o (e)h(closure)g(op)q(eration)i(with)f(resp)q(ect)f(to)i(unit)e(rules.)29 b(A)18 b(unit)122 1317 y(rule)d(is)i(the)f(analogue)h(of)f(a)h(unit)f(pro)q (duction)h(and)g(has)g(the)f(form:)229 1432 y Fk(l)q(abel)330 1439 y Fg(1)348 1432 y Fo(:)21 b Fk(l)q(abel)484 1439 y Fg(2)502 1432 y Fo(;)122 1546 y(This)f(closure)f(is)h(done)g(at)g(run)g(time.)30 b(It)19 b(requires)g(man)o(y)f(pro)q(cedure)i(calls)f(and)h(manipulates)122 1606 y(complex)11 b(data)k(structures.)20 b(W)l(e)14 b(are)g(lo)q(oking)g(at) g(w)o(a)o(ys)g(of)g(doing)g(this)g(at)g(table)f(generation)h(time)122 1666 y(or)19 b(to)h(hash)f(the)g(results)g(of)g(the)g(closures)f(so)i(that)f (redundan)o(t)h(calculations)e(can)h(b)q(e)g(a)o(v)o(oided.)122 1726 y(The)h(problem)e(with)i(doing)h(them)d(in)i(the)f(table)h(generator)g (is)g(the)g(p)q(ossible)g(explosion)g(in)f(its)122 1787 y(running)d(time.)73 1888 y Fe(\017)24 b Fo(Man)o(y)13 b(of)g(the)g(cost)g(parts)h(for)f(the)g (rules)g(are)g(similar)e(and)j(hence)e(some)g(tests)h(are)h(p)q(erformed)d (and)122 1948 y(recalculated)16 b(man)o(y)f(times)g(on)i(a)h(no)q(de.)24 b Fn(Twig)15 b Fo(should)j(b)q(e)f(clev)o(er)d(enough)k(to)f(factor)h(out)f (some)122 2009 y(of)h(these)f(tests)h(and)g(do)g(them)e(only)i(once.)25 b(Ho)o(w)o(ev)o(er,)16 b(the)h(information)g(required)g(for)g Fn(twig)g Fo(to)122 2069 y(do)g(this)f(is)g(not)h(easily)e(a)o(v)m(ailable.) 20 b(It)c(is)g(hidden)g(in)g(the)g(C)h(co)q(de)f(fragmen)o(ts.)73 2171 y Fe(\017)24 b Fo(The)11 b(curren)o(t)f(compact)h(represen)o(tation)f (of)i(the)f(matc)o(hing)e(automaton)j(require)e(linear)g(searc)o(hing)122 2231 y(except)j(at)i(the)f(start)h(state)f(where)g(the)g(large)h(branc)o (hing)f(factor)g(comp)q(elled)e(us)j(to)g(use)f(an)h(arra)o(y)122 2291 y(sc)o(heme.)39 b(Using)23 b(another)g(represen)o(tation)f(w)o(ould)h (sp)q(eed)g(up)h(the)e(matc)o(her.)40 b(F)l(or)23 b(example,)122 2351 y(implem)o(en)o(t)o(ing)17 b(the)j(V)-5 b(AX)18 b(description)h(as)h(an) g(arra)o(y)g(is)g(estimated)d(to)k(use)e(ab)q(out)i(50K)g(b)o(ytes)122 2411 y(but)16 b(ma)o(y)f(pro)o(vide)g(p)q(erformance)h(impro)o(v)o(em)o(e)o (n)o(t.)951 2757 y(19)p eop %%Page: 18 3 bop 122 154 a Fo(stored)22 b(in)f(the)g(sym)o(b)q(ol)f(table)h(to)q(o.)38 b(The)21 b(tree)g(patterns)g(in)g(the)h(rules)e(are)i(un\015attened)f(and)122 214 y(passed)c(to)g(the)f(mac)o(hine)e(builder.)73 307 y Fe(\017)24 b Fo(Mac)o(hine)18 b(Builder)f(|)h(This)h(mo)q(dule)f(tak)o(es)g(tree)g (patterns)h(and)h(incremen)o(tal)o(ly)c(builds)i(an)h(in-)122 368 y(ternal)14 b(represen)o(tation)g(of)g(the)g(matc)o(hing)f(automaton.)21 b(The)14 b(builder)g(tak)o(es)g(this)g(tree)f(and)i(then)122 428 y(en)o(umerates)j(eac)o(h)i(of)g(the)g(p)q(ossible)g(paths)h(from)e(the)h (ro)q(ot)h(to)f(the)g(lea)o(v)o(es.)31 b(These)20 b(paths)h(are)122 488 y(treated)15 b(as)h(strings)f(and)h(a)g(string)f(matc)o(hing)f(automaton) h(is)g(built)f(as)i(describ)q(ed)f(in)g([1])f(and)i([7].)122 565 y(Inside)11 b(the)h(builder)f(the)g(partially)h(built)f(mac)o(hine)e(is)j (k)o(ept)f(in)h(a)g(link)o(ed)e(list)i(form.)18 b(Eac)o(h)12 b(mac)o(hine)122 625 y(state)17 b(is)g(a)h(link)o(ed)d(list)i(and)g(eac)o(h)g (no)q(de)h(represen)o(ts)e(a)h(state)h(transition.)24 b(When)17 b(the)g(tables)g(for)122 685 y(the)e(mac)o(hine)e(are)i(written)f(out)i(in)o (to)30 b Fn(walker.c)p Fo(,)12 b(the)i(link)o(ed)g(list)g(structure)h(is)g (translated)g(in)o(to)122 746 y(a)j(table)f(of)h(sixteen)f(bit)g(in)o (tegers.)25 b(Eac)o(h)18 b(transistion)g(is)f(stored)h(as)g(t)o(w)o(o)g(in)o (tegers.)25 b(The)17 b(\014rst)h(is)122 806 y(the)f(in)o(teger)f(corresp)q (onding)h(to)h(the)e(sym)o(b)q(ol)g(that)h(causes)h(the)e(transistion)i(and)f (the)g(second)g(is)122 866 y(the)f(index)f(of)i(the)f(next)g(state)g(in)g (the)g(table.)73 960 y Fe(\017)24 b Fo(Sym)o(b)q(ol)19 b(T)l(able)i(|)g(The)g (cen)o(tral)f(data)h(structure)g(in)g(this)f(sym)o(b)q(ol)g(table)h(is)f(the) h(hash)h(table.)122 1020 y(Eac)o(h)15 b(en)o(try)f(in)h(the)g(hash)h(table)f (is)g(a)g(buc)o(k)o(et)f(|)h(a)h(link)o(ed)d(list)i(of)g(sym)o(b)q(ol)f (table)h(en)o(tries.)k(There)122 1080 y(is)e(no)g(rehashing.)25 b(All)16 b(colliding)g(items)f(are)i(placed)g(in)f(the)h(link)o(ed)f(list.)23 b(This)17 b(is)g(a)h(simple)c(and)122 1140 y(adequately)k(e\016cien)o(t)f (arrangemen)o(t.)29 b(Dep)q(ending)19 b(on)h(the)f(t)o(yp)q(e)f(of)h(sym)o(b) q(ols,)g(the)f(en)o(try)h(ma)o(y)122 1200 y(p)q(oin)o(t)h(to)g(other)h(data)f (structures.)33 b(En)o(tries)19 b(for)h Fk(l)q(abel)p 1175 1200 15 2 v 17 w(id)p Fo(s)g(p)q(oin)o(t)h(to)f(lists)f(of)i(trees.)32 b Fk(N)5 b(ode)p 1893 1200 V 18 w(id)122 1260 y Fo(en)o(tries)19 b(record)i(the)f(in)o(tegers)g(that)h(ha)o(v)o(e)e(b)q(een)i(asso)q(ciates)g (with)g(them.)32 b(Other)20 b(en)o(tries)g(ma)o(y)122 1321 y(p)q(oin)o(t)d(to)h(data)g(structures)f(holding)h(a)f(textual)g(represen)o (tation)f(of)i(C)f(co)q(de)h(that)g(forms)e(action)122 1381 y(and)h(cost)f(parts.)73 1458 y(Here)k(is)h(a)h(list)e(of)h(the)g(\014les)g (that)g(form)f(the)h Fn(twig)f Fo(compiler's)e(source)j(and)h(their)e(appro)o (ximate)0 1519 y(function.)73 1596 y Fe(\017)k Fn(common.h)18 b Fo(|)i(This)g(\014le)g(con)o(tains)h(data)g(de\014nitions)g(for)f(ho)o(w)h (trees)f(are)h(represen)o(ted)e(in)h(the)122 1656 y(parser.)i(It)15 b(also)i(con)o(tains)f(t)o(yp)q(e)g(de\014nitions)g(for)h(external)e (functions.)73 1750 y Fe(\017)24 b Fn(code.h)14 b Fo(|)i(This)g(\014le)g(con) o(tains)g(de\014nitions)g(for)h(ho)o(w)f(co)q(de)h(fragmen)o(ts)e(are)h (stored.)73 1844 y Fe(\017)24 b Fn(sym.h)14 b Fo(|)i(This)h(\014le)e (de\014nes)h(the)g(ma)s(jor)g(data)h(structures)f(in)g(the)g(sym)o(b)q(ol)f (table.)73 1937 y Fe(\017)24 b Fn(machine.h)14 b Fo(|)j(This)h(\014le)e (de\014nes)i(the)f(ho)o(w)h(the)f(matc)o(hing)f(automaton)h(is)h(represen)o (ted)e(in)o(ter-)122 1998 y(nally)l(.)73 2091 y Fe(\017)24 b Fn(twig.y)14 b Fo(|)i(This)g(is)g(the)g(parser.)73 2185 y Fe(\017)24 b Fn(sym.c)14 b Fo(|)i(This)h(is)f(the)g(sym)o(b)q(ol)f(table)h (manager.)73 2278 y Fe(\017)24 b Fn(path.c)14 b Fo(|)i(The)g(path)h(string)g (en)o(umerator.)73 2372 y Fe(\017)24 b Fn(machine.c)13 b Fo(|)j(The)g(mac)o (hine)e(builder.)73 2466 y Fe(\017)24 b Fn(lex.c)40 b Fo(|)16 b(The)g(lexer.)73 2559 y Fe(\017)24 b Fn(tree.c)p Fo(,)9 b Fn(io.c)p Fo(,)i(and)g Fn(code.c)e Fo(|)i(Miscellaneous)f(routines)h(for)g (manipulating)f(trees,)h(p)q(erforming)122 2620 y(I/O)16 b(and)h (manipulating)e(co)q(de)h(fragmen)o(ts.)951 2757 y(18)p eop %%Page: 17 4 bop 0 243 a Fo(prologue)119 b Fe(f)0 303 y Fk(=)p Fe(\003)17 b Fo(otherdefs.h)e(will)h(ha)o(v)o(e)f(a)i(t)o(yp)q(e)e(de\014nition)h(for)h Fn(NODEPTR)c Fe(\003)p Fk(=)0 363 y Fo(#include)106 b(\\otherdefs.h")0 423 y(#de\014ne)134 b Fn(TEMP)p 407 423 16 2 v 17 w(COST)375 b Fo(5)0 483 y(#de\014ne)134 b Fn(SUB)p 381 483 V 17 w(COST)401 b Fo(30)0 544 y(#de\014ne)134 b Fn(DEC)p 381 544 V 17 w(COST)401 b Fo(10)0 604 y(NODEPTR)51 b(gettemp\(\);)0 664 y Fe(g)p Fo(;)0 741 y(no)q(de)199 b(long)17 b(constan)o(t)f(sub;)0 801 y(lab)q(el)198 b(op)q(erand)17 b(temp;)0 878 y(op)q(erand:)115 b(long;)797 b Fk(=)p Fe(\003)17 b Fo(rule)e(1)i Fe(\003)p Fk(=)0 938 y Fo(op)q(erand:)115 b(constan)o(t;)706 b Fk(=)p Fe(\003)17 b Fo(rule)e(2)i Fe(\003)p Fk(=)0 998 y Fo(op)q(erand:)115 b(temp;)776 b Fk(=)p Fe(\003)17 b Fo(rule)e(3)i Fe(\003)p Fk(=)0 1075 y Fo(temp:)176 b(op)q(erand)729 b Fk(=)p Fe(\003)17 b Fo(rule)e(4)i Fe(\003)p Fk(=)300 1135 y Fe(f)f Fo(cost)h(=)f Fn(TEMP)p 603 1135 V 17 w(COST)p Fo(+$\0451$)d Fe(!)p Fo(cost;)p Fe(g)300 1195 y Fo(=)h Fe(f)600 1255 y Fo(NODEPTR)j(t)f(=)g(gettemp\(\);)600 1316 y(emit\(\\mo)o(v",)d($$,)j(t,)g(0\);)600 1376 y(return\(t\);)300 1436 y Fe(g)p Fo(;)0 1513 y(op)q(erand:)115 b(sub\(op)q(erand,op)q(erand\)) 433 b Fk(=)p Fe(\003)17 b Fo(rule)e(5)i Fe(\003)p Fk(=)300 1573 y Fe(f)p Fo(cost)f(=)h($\0451$)d Fe(!)p Fo(cost)j(+)f($\0452$)e Fe(!)p Fo(cost+)p Fn(SUB)p 1192 1573 V 18 w(COST)p Fo(;)p Fe(g)300 1633 y Fo(=)p Fe(f)600 1693 y Fo(NODEPTR)j(t)f(=)g(gettemp\(\);)600 1754 y(emit\(\\sub",)f($1$,)i($2$,)g(t,)f(0\);)600 1814 y(return\(t\);)300 1874 y Fe(g)p Fo(;)0 1951 y(temp:)176 b(sub\(temp,constan)o(t\))485 b Fk(=)p Fe(\003)17 b Fo(rule)e(6)i Fe(\003)p Fk(=)300 2011 y Fe(f)600 2071 y Fo(if\(v)m(alue\($2$\)==1\))900 2131 y(cost)g(=)f($\0451$)e Fe(!)p Fo(cost+)p Fn(DEC)p 1435 2131 V 18 w(COST)p Fo(;)600 2192 y(else)h(ABOR)l(T;)300 2252 y Fe(g)p Fo(=)p Fe(f)600 2312 y Fo(emit\(\\dec",)f($1$,)j(0\);)600 2372 y(return\($1$\);)300 2432 y Fe(g)p Fo(;)518 2588 y(Figure)f(6:)22 b(Small)14 b(Co)q(de)j (Generation)f(Example)951 2757 y(17)p eop %%Page: 16 5 bop 0 208 a Fo(lT)l(est:)181 b(nNot\(lT)l(est\))300 268 y Fe(f)16 b Fn(TOPDOWN)p Fo(;)d Fe(g)300 329 y Fo(=)p Fe(f)600 389 y Fo($1$)i Fe(!)p Fo(test.truelab)g(=)h($$)f Fe(!)p Fo(test.falselab;)600 449 y($1$)g Fe(!)p Fo(test.falselab)g(=)h($$)f Fe(!)p Fo(test.truelab;)600 509 y(tDO\($\0451$\);)300 569 y Fe(g)p Fo(;)0 646 y(lT)l(est:)181 b(nLess\(lExpr,lExpr\))193 b Fk(=)p Fe(\003)17 b Fj(not)f(top)q(do)o(wn)i(an) o(ymore)31 b Fe(\003)p Fk(=)300 706 y Fo(=)p Fe(f)16 b Fk(:::)f Fj(generate)h(co)q(de)h(for)f(comparison)32 b Fk(:::)15 b Fe(g)p Fo(;)411 922 y(Figure)h(5:)21 b(\(con)o(t.\))g(Short)c(circuited)e(Bo)q (olean)h(Ev)m(aluation)73 1059 y(The)11 b(propro)q(cessor)h(reads)f Fn(arbor.mt)d Fo(and)k(if)e(there)g(are)h(no)h(errors)f(will)e(create)h(t)o (w)o(o)h(\014les:)18 b Fn(symbols.h)0 1119 y Fo(and)f Fn(walker.c)p Fo(.)i(T)l(o)e(build)f Fn(walker.c)p Fo(,)d Fn(twig)i Fo(uses)i(a)g(template) d(\014le)i(called)g Fn(walker.)p Fk(xx)d Fo(where)j Fk(xx)g Fo(is)0 1180 y(the)g(argumen)o(t)f(of)i(the)f(optional)g({)p Fl(w)h Fo(\015ag.)23 b(If)15 b(the)h(\015ag)h(is)g(omitted)d(then)i Fk(xx)g Fo(defaults)g(to)h(\\)p Fn(c1)p Fo(".)73 1240 y Fn(Symbols.h)f Fo(and)j Fn(walker.c)d Fo(can)i(then)h(compiled)d(and)k(link)o(ed)d(with)h (the)h(other)g(mo)q(dules)e(of)i(the)0 1300 y(user's)i(program.)35 b(These)21 b(other)g(mo)q(dules)f(should)h(pro)o(vide)f(the)h(T)l(ree)f(and)i (Cost)f(ADTs)h(describ)q(ed)0 1360 y(ab)q(o)o(v)o(e.)35 b Fn(Walker.h)18 b Fo(is)j(an)g(auxilliary)f(include)f(\014le)i(that)g(is)g(referenced)e(b)o (y)42 b Fn(walker.c)p Fo(.)32 b(A)20 b(t)o(ypical)0 1420 y(compile)14 b(command)g(is:)122 1534 y Fl(cc)i Fo({)h Fl(I)p Fj(include)p 406 1534 15 2 v 16 w(dir)f Fl(-c)g Fo(w)o(alk)o(er.c)73 1649 y(The)d({)p Fl(I)p Fj(include)p 371 1649 V 17 w(dir)f Fo(argumen)o(t)g (causes)h Fl(cc)g Fo(to)g(lo)q(ok)h(for)f(w)o(alk)o(er.h)e(in)i Fj(include)p 1511 1649 V 16 w(dir)p Fo(.)20 b(The)13 b(exact)f(v)m(alue)0 1709 y(of)21 b Fj(include)p 216 1709 V 16 w(dir)f Fo(will)f(dep)q(end)h(on)h (where)f(the)g(\014les)f(are)i(stored)f(at)h(y)o(our)f(site.)32 b(The)20 b(tree)g(matc)o(her)e(is)0 1769 y(initialized)f(b)o(y)h(calling)p 459 1769 16 2 v 37 w Fn(matchinit)e Fo(and)k(matc)o(hing)e(can)h(b)q(egin)g (b)o(y)g(calling)p 1495 1769 V 37 w Fn(match)e Fo(from)h(the)h(user)0 1829 y(program.)0 1996 y Fm(7)83 b(Organization)27 b(of)h(the)f Fa(Twig)f Fm(Compiler)0 2105 y Fo(The)18 b(prepro)q(cessor)i(is)e(written)g (completely)d(in)k(C)f(and)h(Y)l(A)o(CC.)f(It)g(can)g(b)q(e)h(roughly)g(brok) o(en)f(up)g(in)o(to)0 2165 y(four)f(mo)q(dules:)73 2267 y Fe(\017)24 b Fo(Lexer)18 b(|)h(The)g(lexer)e(p)q(erforms)h(lexical)f(analysis.)30 b(The)18 b(input)h(is)g(tok)o(enized)e(b)o(y)h(this)h(mo)q(dule)122 2327 y(and)c(passed)h(to)f(the)f(parser)h(as)g(required.)20 b(Iden)o(ti\014ers)13 b(are)i(lo)q(ok)o(ed)f(up)h(in)f(the)h(sym)o(b)q(ol)e (table)h(and)122 2387 y(space)i(is)g(reserv)o(ed)f(for)i(them)d(if)i(they)g (ha)o(v)o(e)f(nev)o(er)g(b)q(een)i(encoun)o(tered.)73 2489 y Fe(\017)24 b Fo(P)o(arser)f(|)g(This)g(part)h(is)f(written)g(in)f(Y)l(A)o (CC)h(and)h(recognizes)e(the)h Fp(twig)h Fo(language.)43 b(When)122 2549 y(a)21 b(language)g(construct)f(is)g(recognized)f(actions)i(are)f(in)o (v)o(ok)o(ed.)32 b(Declarations,)20 b(prologues)h(and)122 2609 y(inserts)16 b(will)e(in)o(v)o(ok)o(e)g(sym)o(b)q(ol)h(table)g(op)q(erations) i(when)f(recognized.)21 b(Rules)15 b(are)h(brok)o(en)f(up)h(and)951 2757 y(16)p eop %%Page: 15 6 bop 0 234 a Fo(prologue)119 b Fe(f)0 311 y Fo(#include)106 b(\\otherdefs.h")0 371 y(union)16 b(no)q(de)h Fe(f)300 431 y Fk(:::)558 b(=)p Fe(\003)17 b Fo(de\014nition)e(of)i(other)f(no)q(de)h(t)o (yp)q(es)f Fe(\003)p Fk(=)300 492 y Fo(union)g Fe(f)600 552 y Fo(in)o(t)g(op)q(eration;)600 612 y Fn(NODEPTR)e Fo(left,)h(righ)o(t;)600 672 y Fn(LABEL)f Fo(falselab,)i(truelab;)101 b Fk(=)p Fe(\003)17 b Fn(LABEL)d Fo(will)h(de\014ned)h(elsewhere)f Fe(\003)p Fk(=)600 732 y(:::)558 b(=)p Fe(\003)17 b Fo(other)f(de\014nitions)g(relev)m(an)o(t)f (to)i Fj(test)f(no)q(des)h Fe(\003)p Fk(=)300 793 y Fe(g)f Fo(test;)166 b Fk(:::)558 b(=)p Fe(\003)17 b Fo(de\014nition)e(of)i(other)f (no)q(de)h(t)o(yp)q(es)f Fe(\003)p Fk(=)0 853 y Fe(g)p Fo(;)0 930 y Fe(g)p Fo(;)0 1015 y(no)q(de)199 b(nAnd)16 b(nOr)g(nNot)h(nLess;)0 1075 y(lab)q(el)198 b(lT)l(est)16 b(lExpr;)0 1160 y(lT)l(est:)181 b(nAnd\(lT)l(est,lT)l(est\))300 1220 y Fe(f)16 b Fn(TOPDOWN)p Fo(;)d Fe(g)300 1280 y Fo(=)p Fe(f)600 1341 y Fo($1$)i Fe(!)p Fo(test.falselab)g(=)h($$)f Fe(!)p Fo(test.falselab;)600 1401 y($1$)g Fe(!)p Fo(test.truelab)g(=)h(getlab)q(el\(\);)600 1461 y(tDO\($\0451$\);)600 1521 y(prin)o(tlab\($1$)e Fe(!)p Fo(test.truelab\);)600 1581 y($2$)h Fe(!)p Fo(test.falselab)g(=)h($$)f Fe(!)p Fo(test.falselab;)600 1642 y($2$)g Fe(!)p Fo(test.truelab)g(=)h($$)f Fe(!)p Fo(test.truelab;)600 1702 y(tDO\($\0452$\);)300 1762 y Fe(g)p Fo(;)0 1839 y(lT)l(est:)181 b(nOr\(lT)l(est,lT)l(est\))300 1899 y Fe(f)16 b Fn(TOPDOWN)p Fo(;)d Fe(g)300 1959 y Fo(=)p Fe(f)600 2019 y Fo($1$)i Fe(!)p Fo(test.falselab)g(=)h(getlab)q(el\(\);)600 2079 y($1$)f Fe(!)p Fo(test.truelab)g(=)h($$)f Fe(!)p Fo(test.truelab;)600 2140 y(tDO\($\0451$\);)600 2200 y($2$)g Fe(!)p Fo(test.truelab)g(=)h($$)f Fe(!)p Fo(test.truelab;)600 2260 y($2$)g Fe(!)p Fo(test.falselab)g(=)h($$)f Fe(!)p Fo(test.falselab;)600 2320 y(tDO\($\0452$\);)300 2380 y Fe(g)p Fo(;)493 2596 y(Figure)h(5:)21 b(Short)c(circuited)e(Bo)q(olean)h (Ev)m(aluation)951 2757 y(15)p eop %%Page: 14 7 bop 0 154 a Fc(5.2)70 b(Short)23 b(Circuited)e(Bo)r(olean)h(Ev)l(aluation)0 246 y Fo(Short)c(circuited)e(b)q(o)q(olean)j(ev)m(aluation)f(is)g(naturally)f (top)q(do)o(wn.)27 b(A)18 b(fragmen)o(t)e(of)i Fp(twig)h Fo(program)f(that)0 306 y(implem)o(en)o(ts)13 b(this)j(is)g(sho)o(wn)h(in)f(Figure)g(5.)73 420 y Fe(\017)24 b Fo(Lab)q(els)14 b(for)g(true)g(and)g(false)f(branc)o(hes)h (are)g(passed)g(do)o(wn)g(to)g(rules)g(b)q(elo)o(w)f(b)o(y)g(putting)h(them)e (in)o(to)122 480 y(the)k(no)q(des.)22 b(Another)16 b(w)o(a)o(y)g(of)g (accomplishing)f(this)h(is)g(to)h(use)f(an)h(auxillary)e(argumen)o(t)g(stac)o (k.)73 582 y Fe(\017)24 b Fo(The)17 b(rules)g(assume)g(that)g(ev)o(ery)f (test)h(generates)g(a)h(branc)o(h)f(to)h(b)q(oth)g(the)f(false)g(and)h(true)f (lab)q(el.)122 642 y(On)h(con)o(v)o(en)o(tional)e(mac)o(hines,)g(extra)h (branc)o(hes)h(can)g(b)q(e)g(eliminated)d(b)o(y)i(recognizing)h(that)g(one) 122 703 y(could)i(generate)h(co)q(de)g(that)g(falls)f(through)i(to)f(its)f (true)h(or)g(false)f(lab)q(els.)34 b(This)21 b(can)g(b)q(e)g(done)122 763 y(b)o(y)16 b(separating)i Fj(lT)l(est)e Fo(in)o(to)g Fj(lT)l(rueT)l(est)g Fo(and)h Fj(lF)l(alseT)l(est)f Fo(whic)o(h)g(branc)o(hes)h(only)f(when)h (true)f(and)122 823 y(false)g(resp)q(ectiv)o(ely)l(.)j(Rules)c(can)i(then)f (b)q(e)g(written)g(to)h(tak)o(e)e(adv)m(an)o(tage)j(of)e(this.)0 1021 y Fc(5.3)70 b(Co)r(de)22 b(Generation)0 1114 y Fo(Figure)f(6)h(is)g(an)g (example)d(of)j Fp(twig)h Fo(program)e(that)i(can)e(b)q(e)h(used)g(to)g (generate)g(V)-5 b(AX)19 b(co)q(de)j(for)g(the)0 1174 y(subtract)17 b(instruction:)73 1288 y Fe(\017)24 b Fo(Rules)16 b(3)h(and)g(4)g(form)e(a)i (lo)q(op.)23 b(The)17 b(p)q(oten)o(tial)f(lo)q(op:)23 b(temp)p Fe(!)p Fo(op)q(erand)p Fe(!)p Fo(temp)p Fe(!)p Fo(op)q(erand)p Fk(:::)13 b Fo(is)122 1348 y(brok)o(en)h(b)o(y)h(the)f(matc)o(her)f (recognizing)h(that)h(the)g(cost)g(of)g(the)g(second)g(matc)o(h)e(of)i(temp)e (do)q(es)j(not)122 1408 y(cost)g(less)g(than)h(the)f(\014rst)h(matc)o(h)d(of) j(temp.)73 1510 y Fe(\017)24 b Fo(In)12 b(the)h(cost)f(clause)h(of)g(rule)e (5,)j(the)e(cost)h(is)f(the)h(sum)e(of)i(the)f(lea)o(v)o(es)g(plus)g(the)h (cost)f(of)h(the)g(subtract)122 1570 y(instruction.)20 b(The)14 b(action)g(clause)g(emits)e(co)q(de)j(to)f(add)h(the)f(t)o(w)o(o)g(op)q (erands)h(and)g(lea)o(v)o(e)e(the)h(result)122 1631 y(in)j(a)h(temp)q(orary)f (lo)q(cation.)25 b(The)17 b(temp)q(orary)g(is)g(returned)g(as)h(a)g (substitution)g(for)f(the)h(sub)s(ject)122 1691 y(tree.)73 1792 y Fe(\017)24 b Fo(Rule)14 b(6)h(handles)g(a)g(sp)q(ecial)f(case)h(where) f(the)h(left)f(op)q(erand)h(is)g(already)g(in)f(a)h(temp)q(orary)f(and)h(the) 122 1853 y(constan)o(t)k(is)f(one.)28 b(In)18 b(this)g(case,)h(the)f(temp)q (orary)f(is)i(directly)d(decremen)o(ted)f(and)k(returned)f(as)122 1913 y(the)e(new)g(tree.)0 2079 y Fm(6)83 b(Ho)n(w)26 b(to)i(run)f Fa(Twig)0 2189 y Fo(Once)22 b(a)i(user)f(has)h(written)e(the)h(sp)q (eci\014cation,)h Fn(twig)e Fo(is)g(used)i(to)f(compile)e(it)h(in)o(to)h(a)g (subroutine.)0 2249 y(Figure)16 b(1)h(giv)o(es)f(an)i(o)o(v)o(erview)d(of)i (ho)o(w)g Fn(twig)e Fo(do)q(es)j(this.)k(In)17 b(Figure)f(1,)h(rounded)g(b)q (o)o(xes)g(indicate)e(\014les)0 2309 y(and)k(sharp)g(cornered)e(b)q(o)o(xes)i (are)f(pro)q(cessing)g(programs.)27 b(The)19 b(user)f(creates)f(the)h Fp(twig)h Fo(sp)q(eci\014cation)0 2369 y(whic)o(h)14 b(is)h(represen)o(ted)f (b)o(y)h(the)f(top)i(b)q(o)o(x.)21 b(The)15 b(sp)q(eci\014cation)g(\014le)f (m)o(ust)g(ha)o(v)o(e)g(the)h(su\016x)g(\\)p Fn(.mt)p Fo(".)20 b(Let's)0 2429 y(sa)o(y)c(w)o(e)g(ha)o(v)o(e)g(one)g(called)f Fn(arbor.mt)p Fo(.)j(T)l(o)f(in)o(v)o(ok)o(e)e(the)h Fn(twig)e Fo(compiler)g(w)o(e)i(t)o(yp)q(e:)122 2544 y Fl(t)n(wig)g Fo([{)p Fl(w)p Fk(xx)p Fo(])g(arb)q(or.m)o(t)951 2757 y(14)p eop %%Page: 13 8 bop 0 387 a Fo(m)o(tGetNo)q(des\(r,n\))300 447 y Fn(NODEPTR)14 b Fo(r;)300 507 y(in)o(t)i(n;)0 567 y Fe(f)300 627 y Fo(if\(n==1\))600 687 y(return\(r)p Fe(!)p Fo(left\);)300 748 y(else)f(if\(n==1\))600 808 y(return\(r)p Fe(!)p Fo(righ)o(t\);)300 868 y(else)g(if\(n==0)h(&&)h(r==) p Fn(NULL)p Fo(\))600 928 y(return\(Ro)q(ot\);)300 988 y(else)e(return\()p Fn(NULL)p Fo(\);)0 1049 y Fe(g)0 1125 y Fo(m)o(tSetNo)q(des\(r,n,)f(c\))300 1186 y Fn(NODEPTR)g Fo(r,)h(c;)300 1246 y(in)o(t)h(n;)0 1306 y Fe(f)300 1366 y Fo(if\(n==1\))600 1426 y(r)p Fe(!)p Fo(left)f(=)h(c;)300 1487 y(else)f(if\(n==2\))600 1547 y(r)p Fe(!)p Fo(righ)o(t)h(=)g(c;)300 1607 y(else)f(if\(n==0\))600 1667 y(Ro)q(ot)i(=)f(c;)0 1727 y Fe(g)0 1804 y Fo(main\(argc,argv\))559 b Fk(=)p Fe(\003)17 b Fo(called)e(b)o(y)g(user)i(only)f Fe(\003)p Fk(=)300 1864 y Fo(c)o(har)g Fe(\003\003)p Fo(argv;)0 1924 y Fe(f)p 303 1985 15 2 v 318 1985 a Fo(matc)o(hinit\(\);)323 b Fk(=)p Fe(\003)17 b Fo(initialize)c(the)j(matc)o(her)f Fe(\003)p Fk(=)300 2045 y(:::)g Fj(get)h(a)h(tree)e(and)i(set)f(Ro)q(ot)i(to)e(it)p 303 2105 V 318 2105 a Fo(matc)o(h\(\);)397 b Fk(=)p Fe(\003)17 b Fo(do)f(the)g(matc)o(h)f Fe(\003)p Fk(=)0 2165 y Fe(g)0 2225 y(g)358 2441 y Fo(Figure)h(4:)22 b(\(con)o(t.\))e(Prin)o(ting)c(Expression)h (trees)e(to)i(Pre\014x)f(form)951 2757 y(13)p eop %%Page: 12 9 bop 0 287 a Fo(prologue)119 b Fe(f)0 364 y Fo(t)o(yp)q(edef)142 b(struct)16 b(no)q(de)h Fe(\003)316 b Fn(NODEPTR)p Fo(;)0 424 y(#de\014ne)134 b Fn(COST)496 b Fo(in)o(t)0 484 y(#de\014ne)134 b Fn(INFINITY)392 b Fo(100000)0 545 y(#de\014ne)134 b Fn(DEFAULT)p 485 545 16 2 v 16 w(COST)298 b Fo(0)0 621 y Fn(NODEPTR)14 b Fo(Ro)q(ot;)0 682 y(struct)i(co)q(de)63 b Fe(f)300 742 y Fo(c)o(har)16 b(op;)428 b Fk(=)p Fe(\003)17 b Fo(n)o(ull)e(if)g(no)q(de)i(is)f(a)h(leaf)f Fe(\003)p Fk(=)300 802 y Fo(NODEPTR)h(left,)d(righ)o(t;)300 862 y(c)o(har)i Fe(\003)p Fo(id;)0 922 y Fe(g)p Fo(;)0 999 y Fe(g)p Fo(;)0 1084 y(no)q(de)199 b(nOp)16 b(nIden)o(t;)0 1144 y(lab)q(el)198 b(lExpr;)0 1230 y(lExpr:)167 b(nIden)o(t)300 1290 y(=)16 b Fe(f)g Fo(prin)o(tf\(\\\045s",)g(id\);)f Fe(g)p Fo(;)0 1367 y(lExpr:)167 b(nOp\(lExpr,lExpr\))300 1427 y Fe(f)16 b Fn(TOPDOWN)p Fo(;)p Fe(g)300 1487 y Fo(=)g Fe(f)600 1547 y Fo(putc)o(har\($$)f Fe(!)p Fo(op\);)600 1607 y(tDO\($\0451$\);)600 1667 y(tDO\($\0452$\);)300 1728 y Fe(g)p Fo(;)0 1813 y(insert)180 b Fe(f)0 1890 y Fo(m)o(tV)l(alue\(ro)q(ot\))300 1950 y Fn(NODEPTR)14 b Fo(ro)q(ot;)0 2010 y Fe(f)300 2070 y Fo(if\(ro)q(ot)p Fe(!)p Fo(op==0\))600 2130 y(return\(nIden)o(t\);)300 2191 y(else)600 2251 y(return\(nOp\);)0 2311 y Fe(g)440 2543 y Fo(Figure)i(4:)22 b(Prin)o(ting)15 b(Expression)i(trees)e(to)i(Pre\014x)f(form)951 2757 y(12)p eop %%Page: 11 10 bop 0 190 a Fl(Pro)r(cedure)18 b Fp(Exe)n(cute)73 304 y Fe(\017)24 b Fo(If)16 b Fk(M)21 b Fo(is)16 b(a)h Fj(deferred)e Fo(mo)q(de)h(matc)o(h)e (then)j(execution)e(o)q(ccurs)h(b)o(y)g(\014rst)h(applying)f Fp(Exe)n(cute)i Fo(to)e(the)122 364 y Fk(L)155 371 y Ff(i)169 364 y Fo(s)h(from)e(left)h(to)g(righ)o(t.)22 b(That)17 b(is,)e(in)h(the)h (order)f(that)h(they)f(app)q(ear)h(in)f(the)g(pre\014x)g(form)g(of)g(the)122 424 y(tree.)k(When)d(all)e(the)h Fk(L)565 431 y Ff(i)580 424 y Fo(s)g(are)h(executed,)d(the)i(action)g(part)h(of)f Fk(M)22 b Fo(is)16 b(in)o(v)o(ok)o(ed.)73 526 y Fe(\017)24 b Fo(If)16 b Fk(M)23 b Fo(is)16 b(a)i Fj(rewrite)32 b Fo(mo)q(de)16 b(matc)o(h)g(then)g (just)i(the)e(action)h(part)g(of)h Fk(M)k Fo(is)17 b(executed.)k(When)c(the) 122 586 y(action)e(part)h(returns)f(the)g(matc)o(her)e(deletes)h(the)h(sk)o (eleton)f(corresp)q(onding)i(to)g(the)f(subtree)g(that)122 646 y Fk(M)20 b Fo(matc)o(hed)13 b(and)i(rescans)g(the)g(new)g(subtree)f (that)h(ma)o(y)f(ha)o(v)o(e)f(b)q(een)i(substituted)g(b)o(y)f(executing)122 706 y Fk(M)5 b Fo(.)73 808 y Fe(\017)24 b Fo(If)13 b Fk(M)20 b Fo(is)14 b(a)g Fj(top)q(do)o(wn)h Fo(mo)q(de)e(matc)o(h)g(then)h(only)f (the)h(action)g(part)g(of)h Fk(M)k Fo(is)14 b(executed.)19 b(T)l(o)14 b(execute)122 868 y(a)21 b(lab)q(elled)f(lea)o(v)o(es,)g Fk(L)544 875 y Ff(i)558 868 y Fo(,)h Fk(M)5 b Fo('s)21 b(action)g(part)g(ma)o (y)e(do)j(so)f(explicitly)d(b)o(y)i(using)h(the)g Fn(tDO\()p Fo($\045)p Fk(i)p Fo($)p Fn(\))122 928 y Fo(macro.)f(This)d(allo)o(ws)f(the)g (user)g(to)h(arbitrary)f(order)g(the)g(execution)f(of)i(the)f(lab)q(elled)f (lea)o(v)o(es.)0 1052 y(When)20 b(the)f(costing)h(phase)g(is)g(o)o(v)o(er,)f (the)g(execution)g(phase)h(is)g(started)g(b)o(y)f(pic)o(king)f(the)i(lo)o(w)o (est)f(cost)0 1112 y(matc)o(h)14 b(at)h(the)g(ro)q(ot)i(of)e(the)g(sub)s (ject)g(tree.)20 b(This)15 b(will)f(b)q(e)i(the)f(ro)q(ot)h(of)g(the)f(minim) n(um)c(cost)k(co)o(v)o(er.)20 b(The)0 1173 y(matc)o(h)15 b(is)h(executed)f (as)h(describ)q(ed)g(ab)q(o)o(v)o(e.)73 1233 y(The)21 b(execution)e(phase)i (ma)o(y)e(b)q(egin)i(b)q(efore)f(the)g(costing)h(phase)g(is)f(o)o(v)o(er.)34 b(This)20 b(o)q(ccurs)h(when)g(a)0 1293 y(rewrite)e(rule)g(matc)o(hes)f(and)j (its)f(cost)g(is)g(lo)o(w)o(er)f(than)h(all)g(other)g(matc)o(hes)e(at)i(that) h(subtree.)32 b(In)19 b(this)0 1353 y(situation)d(the)f(rewrite)g(rule)g(is)g (executed)g(imme)o(diatel)o(y)e(and)j(the)f(new)h(rewritten)f(subtree)g(is)h (scanned)0 1413 y(once)21 b(more.)35 b(The)22 b(prescence)e(of)i(rewrite)e (rules)h(thro)o(ws)h(a)g(wrenc)o(h)e(in)h(the)h(theoretical)e(niceties)g(of)0 1474 y(the)g(matc)o(hing)f(algorithm.)33 b(F)l(or)21 b(example,)e(there)h(is) g(no)o(w)h(no)g(guaran)o(tee)g(that)g(the)g(algorithm)e(will)0 1534 y(terminate)h(b)q(ecause)h(the)h(tree)f(can)g(b)q(e)h(rep)q(eatedly)f (enlarged.)37 b(Rewrite)20 b(rules)i(can)f(b)q(e)h(dangerous.)0 1594 y(They)17 b(can)h(b)q(e)g(triggered)f(unin)o(ten)o(tionally)f(if)h(the)g (user)h(is)f(not)h(careful)f(to)h(ab)q(ort)g(them)e(in)i(situations)0 1654 y(where)f(they)h(are)g(not)g(w)o(an)o(ted.)25 b(Ho)o(w)o(ev)o(er,)16 b(if)i(used)f(with)h(care)g(they)f(can)h(help)f(to)h(reduce)f(the)h(size)f (of)0 1714 y(the)f Fp(twig)h Fo(sp)q(eci\014cation.)0 1877 y Fm(5)83 b(Some)27 b(Examples)0 2001 y Fc(5.1)70 b(Expression)23 b(T)-6 b(rees)22 b(to)h(Pre\014x)0 2093 y Fo(A)16 b Fp(twig)h Fo(program)f(to)h(prin)o(t)e(out)i(the)f(pre\014x)g(form)f(of)i(expression)f (parse)g(trees)g(is)g(sho)o(wn)h(in)f(Figure)g(4.)73 2174 y Fe(\017)24 b Fo(The)18 b(rules)f(do)i(not)f(ha)o(v)o(e)f(cost)i (calculations.)26 b(Since)17 b(there)g(are)h(no)g(am)o(biguities)e(costs)j (are)f(not)122 2234 y(necessary)l(.)73 2328 y Fe(\017)24 b Fo(The)16 b(second)h(rule)f(is)g(a)h(top)q(do)o(wn)h(mo)q(de)e(rule.)21 b(This)16 b(is)h(essen)o(tial)e(in)h(prin)o(ting)g(the)g(pre\014x)h(form.)122 2388 y(If)f(it)f(w)o(as)i(omitted)e(the)h(p)q(ost\014x)h(form)e(w)o(ould)h(b) q(e)h(prin)o(ted.)73 2481 y Fe(\017)24 b Fo(Before)11 b(an)o(y)g(matc)o(hing) f(can)i(b)q(egin)p 780 2481 16 2 v 30 w Fn(matchinit)c Fo(m)o(ust)i(b)q(e)i (called.)19 b(T)l(rees)11 b(can)h(then)f(b)q(e)h(pro)q(cessed)122 2541 y(b)o(y)18 b(calling)p 353 2541 V 37 w Fn(match)f Fo(after)i(arranging)h (that)f(the)g(call)f Fn(mtGetNodes)p Fo(\()p Fn(N)o(UL)o(L)m Fk(;)8 b Fo(0\))19 b(returns)g(the)g(ro)q(ot)122 2602 y(of)d(the)g(sub)s (ject)g(tree.)951 2757 y(11)p eop %%Page: 10 11 bop 122 201 a Fn(e:)50 b(plus\(e,e\))122 261 y(e:)g(plus\(e,)24 b(plus\(e,e\))o(\))122 321 y(e:)50 b(id)122 381 y(e:)g(const)122 639 y Fk(S)17 b Fe(!)c Fk(e)122 700 y(e)g Fe(!)h Fk(pl)q(us)p Fo(\()p Fk(e;)8 b(e)p Fo(\))122 760 y Fk(e)13 b Fe(!)h Fk(pl)q(us)p Fo(\()p Fk(e;)8 b(pl)q(us)p Fo(\()p Fk(e;)g(e)p Fo(\))122 820 y Fk(e)13 b Fe(!)h Fk(id)122 880 y(e)f Fe(!)h Fk(const)629 1036 y Fo(Figure)h(3:)22 b(P)o(attern)16 b(and)h(Grammar)0 1170 y Fc(4.1)70 b(The)22 b(Costing)g(Phase)0 1262 y Fo(Let)d(the)f(patterns) h(of)f(the)h Fp(twig)g Fo(sp)q(eci\014cations)g(b)q(e)f(in)o(terpreted)f(as)i (grammar)e(pro)q(ductions)i(with)g Fj(la-)0 1323 y(b)q(el)p 67 1323 15 2 v 17 w(id)p Fo(s)14 b(as)h(non-terminals)e(and)i Fj(no)q(de)p 717 1323 V 18 w(id)p Fo(s)f(as)h(terminals.)k(If)14 b(w)o(e)f(add)i(a)g(pro)q(duction)g Fk(S)25 b Fe(!)d Fj(lab)q(el)p 1823 1323 V 17 w(id)14 b Fo(for)0 1383 y(all)h Fj(lab)q(el)p 172 1383 V 17 w(id)p Fo(s)h(where)g Fk(S)i Fo(is)e(the)f(start)i(sym)o(b)q (ol,)d(then)h(a)i(co)o(v)o(ering)d(for)i(a)g(tree)f(is)h(analogous)i(to)e(a)g (deriv)m(a-)0 1443 y(tion)i(for)g(the)f(pre\014xed)g(form)g(of)h(the)f(tree.) 25 b(Figure)18 b(3)g(sho)o(ws)g(some)f(patterns)h(and)h(its)e(corresp)q (onding)0 1503 y(grammar.)24 b(The)17 b(pro)q(ductions)i(of)e(the)h(form)e Fk(S)j Fe(!)d Fj(lab)q(el)p 1080 1503 V 17 w(id)h Fo(re\015ect)g(the)g(fact)h (that)g(an)o(y)f Fj(lab)q(el)p 1788 1503 V 17 w(id)h Fo(ma)o(y)0 1563 y(start)f(a)f(co)o(v)o(er.)73 1623 y(The)h(matc)o(her)e(\014nds)i(the)f (least)h(cost)g(co)o(v)o(er)e(b)o(y)i(doing)g(a)g(preorder)g(tra)o(v)o(ersal) f(of)h(the)f(sub)s(ject)g(tree.)0 1684 y(A)o(t)d(the)g(same)f(time,)g(it)h (builds)g(a)h(sk)o(eleton)e(tree)h(that)h(is)f(structurally)g(isomorphic)f (to)i(the)f(sub)s(ject)g(tree.)0 1744 y(When)18 b(a)g(matc)o(h)e(is)h(disco)o (v)o(ered)g(the)g(cost)h(clause)f(of)h(the)g(pattern)g(is)f(in)o(v)o(ok)o(ed) f(to)i(calculate)f(the)g(cost.)0 1804 y(Man)o(y)e(patterns)i(with)e (di\013eren)o(t)g(lab)q(els)h(could)g(matc)o(h)e(at)i(an)o(y)g(giv)o(en)f(no) q(de)h(but)g(only)g(the)g(lo)o(w)o(est)f(cost)0 1864 y(pattern)h(for)h(eac)o (h)f(lab)q(el)g(is)g(recorded)f(in)h(the)g(sk)o(eleton.)73 1924 y(When)e(a)g(pattern)g(is)g(matc)o(hed,)e(its)i(lab)q(el)f(is)h(then)f (used)h(as)h(input)e(to)i(the)e(pattern)h(matc)o(her)e(so)j(that)0 1985 y(matc)o(hing)h(of)i(patterns)g(with)g(lab)q(elled)f(lea)o(v)o(es)f(can) i(b)q(egin.)26 b(This)18 b(pro)q(cess)g(is)g(analogous)i(to)e(a)g(reduce)0 2045 y(action)e(in)g(b)q(ottom)g(up)h(parsers.)0 2189 y Fc(4.2)70 b(The)22 b(Execution)g(Phase)0 2282 y Fo(The)e(execution)e(phase)j(starts)f (when)g(the)f(costing)h(phase)h(is)e(complete)f(or)i(when)f(a)i(su\016cien)o (tly)c(lo)o(w)0 2342 y(cost)i Fj(rewrite)e Fo(mo)q(de)h(rule)g(is)g(encoun)o (tered.)28 b(Let)18 b Fk(M)24 b Fo(b)q(e)19 b(a)g(matc)o(hing)e(rule)h(and)h Fk(L)1571 2349 y Fg(1)1591 2342 y Fk(;)8 b(L)1646 2349 y Fg(2)1666 2342 y Fk(;)g(L)1721 2349 y Fg(3)1740 2342 y Fk(;)g(:::;)g(L)1859 2349 y Ff(n)1900 2342 y Fo(b)q(e)0 2402 y(the)16 b(lab)q(elled)g(lea)o(v)o (es)f(of)i(the)g(matc)o(hing)e(pattern.)22 b(The)17 b(follo)o(wing)f(pro)q (cedure)h(is)f(used)h(to)g(execute)e(the)0 2462 y(action)h(parts)h(of)g Fk(M)5 b Fo(.)951 2757 y(10)p eop %%Page: 9 12 bop 0 154 a Fc(3.8)70 b(Costs)22 b(and)i(Action)e(co)r(de)0 246 y Fo(Co)q(de)f(fragmen)o(ts)e(suc)o(h)i(as)g(the)f Fk(cost)g Fo(and)h Fk(action)f Fo(clauses)g(of)h(a)g(rule)e(are)i(sp)q(ec\014ed)f(b)o (y)g(enclosing)g(C)0 306 y(co)q(de)h(in)f(braces.)34 b(All)19 b(legal)h(C)h(constructs)g(are)f(p)q(ermitted)f(in)h(co)q(de)h(fragmen)o(ts.) 33 b(In)20 b(addition,)h(the)0 366 y(follo)o(wing)15 b(are)h(pro)o(vided)f (for)h(con)o(v)o(enien)o(t)e(access)i(to)g(the)f(sub)s(ject)g(tree)g(and)i (in)o(ternal)d(data)j(structures)0 427 y(of)g(the)f(matc)o(her.)73 541 y Fe(\017)24 b Fo($\045)p Fk(n)p Fo($)18 b(denotes)f(a)g(p)q(oin)o(ter)g (v)m(alue)g(to)h(the)e(matc)o(her)g(data)i(structure)e(for)i(the)f Fk(n)p Fo(th)g(lab)q(elled)f(leaf.)122 601 y(Th)o(us)e(to)g(access)g(the)f (cost)h(v)m(alue)g(asso)q(ciated)g(with)g(that)g(leaf,)f(the)h(notation)g ($\045)p Fk(n)p Fo($)h Fe(!)p Fn(cost)d Fo(ma)o(y)122 661 y(b)q(e)k(used.)73 763 y Fe(\017)24 b Fo($$)17 b(denotes)f(a)h(p)q(oin)o(ter)f(v)m(alue)g(to)h (the)f(ro)q(ot)h(of)g(the)f(sub)s(ject)f(tree.)73 864 y Fe(\017)24 b Fo($)p Fk(n)175 871 y Fg(1)195 864 y Fk(:n)238 871 y Fg(2)258 864 y Fk(:n)301 871 y Fg(3)320 864 y Fk(:)8 b Fo(...)f Fk(:n)434 871 y Ff(k)q Fb(\000)p Fg(1)500 864 y Fk(:n)543 871 y Ff(k)564 864 y Fo($)17 b(denotes)g(a)g(p)q(oin)o(ter)f(v)m(alue)h(to)g(the)f Fk(n)1291 871 y Ff(k)1313 864 y Fo(th)h(c)o(hild)e(of)i(the)f Fk(n)1663 871 y Ff(k)q Fb(\000)p Fg(1)1730 864 y Fk(th)g Fo(c)o(hild)g(of)122 925 y(the)j Fk(n)238 932 y Ff(k)q Fb(\000)p Fg(2)304 925 y Fo(th)h(c)o(hild)e(of)h(...)f(of)i(the)f Fk(n)784 932 y Fg(1)804 925 y Fo(th)g(c)o(hild)f(of)i(the)f(ro)q(ot)h(of)f(the)h(sub)s(ject)e(tree.) 30 b(Eac)o(h)19 b Fk(n)1840 932 y Ff(i)1874 925 y Fo(is)g(a)122 985 y(p)q(ositiv)o(e)c(non-zero)i(in)o(teger.)73 1099 y(Some)h(sp)q(ecial)h (constructs)g(are)h(a)o(v)m(ailable)e(to)h(co)q(de)h(fragmen)o(ts)e(in)h(the) g(cost)g(part)h(of)f(the)g(sp)q(eci\014-)0 1159 y(cation.)28 b(The)19 b(statemen)o(t)e(\\)p Fn(ABORT;)p Fo(")g(when)i(encoun)o(tered)e (during)i(the)g(execution)e(of)i(the)f(cost)h(co)q(de,)0 1219 y(signals)h(to)f(the)g(matc)o(her)e(that)j(this)f(pattern)g(is)g(to)g(b)q(e)h (rejected.)28 b(When)19 b(a)h(\\)p Fn(REWRITE;)p Fo(")d(statemen)o(t)0 1280 y(is)g(encoun)o(tered,)e(con)o(trol)i(is)f(returned)g(to)i(the)e(matc)o (her)f(and)i(the)g(rule)f(will)g(b)q(ecome)f(a)i Fj(rewrite)f Fo(mo)q(de)0 1340 y(matc)o(h.)i(When)13 b(the)f(end)g(of)g(the)g(cost)h(co)q (de)f(fragmen)o(t)f(is)i(reac)o(hed,)e(con)o(trol)h(is)g(returned)g(to)h(the) f(matc)o(her)0 1400 y(and)19 b(the)f(rule)g(b)q(ecomes)f(a)h Fj(defer)g Fo(mo)q(de)g(matc)o(h.)25 b(The)19 b(statemen)o(t)d(\\)p Fn(TOPDOWN;)p Fo(")h(is)h(lik)o(e)e(\\)p Fn(REWRITE;)p Fo(")0 1460 y(except)e(that)i(the)f(mo)q(de)g(of)g(the)g(matc)o(h)f(b)q(ecomes)g Fj(top)q(do)o(wn)p Fo(.)22 b(The)16 b(meanings)e(of)i(these)f(mo)q(des)g (will)f(b)q(e)0 1520 y(explained)h(in)h(Section)g(4.)73 1581 y(Cost)25 b(v)m(alues)f(are)h(returned)e(to)i(the)f(matc)o(her)e(b)o(y)i (assigning)h(to)f(the)g(\\)p Fn(cost)p Fo(")g(v)m(ariable)f(in)h(the)0 1641 y(cost)c(clause.)30 b(If)19 b(no)h(assignmen)o(t)f(is)g(made)g(to)g(the) h Fn(cost)e Fo(v)m(ariable)h(then)g(the)h(returned)f(cost)g(will)g(b)q(e)0 1701 y Fn(DEFAULT)p 185 1701 16 2 v 16 w(COST)p Fo(.)73 1761 y(Action)13 b(clauses)g(are)h(exp)q(ected)f(to)g(return)h(a)g(new)f(tree)g (whic)o(h)g(will)f(replace)h(the)g(sub)s(ject)g(tree.)20 b(This)0 1821 y(is)d(done)g(b)o(y)f(returning)h(using)g(the)g(\\)p Fn(return\()p Fk(new)p 960 1821 V 17 w(tr)q(ee)p Fn(\);)p Fo(")f(statemen)o(t.)22 b(where)16 b Fk(new)p 1632 1821 V 20 w(tr)q(ee)g Fo(is)g(of)i(t)o(yp)q(e)0 1881 y Fn(NODEPTR)p Fo(.)d(If)j(execution)f(reac)o(hes)h(the)f(end)i(of)f (the)g(action)g(clause,)g(the)g(matc)o(her)e(resumes)h(execution)0 1942 y(and)g(the)f(sub)s(ject)f(tree)h(is)g(not)h(mo)q(di\014ed.)0 2108 y Fm(4)83 b(P)n(attern)27 b(Matc)n(her)g(Op)r(eration)0 2218 y Fo(The)20 b(pattern)h(matc)o(her)d(op)q(erates)j(in)f(t)o(w)o(o)g (phases:)30 b(the)20 b(costing)g(phase)h(and)g(the)f(execution)f(phase.)0 2278 y(During)13 b(the)g(costing)g(phase,)g(a)g(minimal)d(cost)j(co)o(v)o (ering)e(of)i(the)g(sub)s(ject)f(tree)g(is)h(found.)20 b(The)13 b(execution)0 2338 y(phase)22 b(in)o(v)o(ok)o(es)f(the)g(actions)h(that)h (are)f(asso)q(ciated)h(with)e(the)h(patterns)g(making)f(up)h(the)g(co)o(v)o (ering.)0 2398 y(Execution)c(phases)h(ma)o(y)d(b)q(egin)j(during)f(the)g (costing)h(phase)g(to)f(execute)f(the)h(co)o(v)o(ering)f(of)i(a)f(subtree)0 2458 y(as)f(describ)q(ed)f(in)f(Section)h(4.2.)963 2757 y(9)p eop %%Page: 8 13 bop 73 154 a Fe(\017)24 b Fn(NODEPTR)16 b Fo(is)j(the)f(t)o(yp)q(e)h(of)g(a)g (no)q(de.)29 b(The)19 b(actual)g(details)f(of)h(the)g Fn(NODEPTR)d Fo(are)j(irrelev)m(an)o(t)e(and)122 214 y Fn(twig)e Fo(uses)h(this)g (de\014nition)g(only)g(for)h(storage)g(allo)q(cation)g(and)f(declaration)g (purp)q(oses.)73 314 y Fe(\017)24 b Fn(NULL)13 b Fo(is)i(used)g(to)g(denote)g (a)g(n)o(ull)f Fn(NODEPTR)e Fo(v)m(alue.)21 b(In)14 b(the)h(curren)o(t)f (implem)o(en)o(tation)e(this)j(is)f(the)122 374 y(same)i Fn(NULL)f Fo(used)i(b)o(y)f(the)h(C)g(standard)h(I/O)f(pac)o(k)m(age)g(and)g(need)g (not)g(b)q(e)g(de\014ned)g(b)o(y)f(the)g(user.)122 435 y(This)g(restricts)g (the)g Fn(NODEPTR)e Fo(represen)o(tation)h(to)i(b)q(e)f(a)h(p)q(oin)o(ter.)73 535 y Fe(\017)24 b Fn(mtGetNodes)o Fo(\()p Fk(r)o(;)7 b(n)p Fo(\))12 b(returns)i(the)g Fk(n)p Fo(th)h(c)o(hild)e(of)h Fk(r)i Fo(where)e Fk(r)h Fo(is)g(a)f Fn(NODEPTR)p Fo(.)d(The)k(leftmost)d(c)o(hild)h (is)122 595 y Fn(mtGetNodes)o Fo(\()p Fk(r)o(;)7 b Fo(1\).)18 b(If)c Fk(n)g(>)f Fo(degree\()p Fk(r)q Fo(\))h(then)g(the)f(function)h (should)g(return)f Fn(NULL)p Fo(.)f Fn(Twig)h Fo(exp)q(ects)122 655 y(the)j(expression)g Fn(mtGetNodes)o Fo(\()p Fn(NU)o(LL)m Fk(;)8 b Fo(0\))16 b(to)h(denote)f(the)g(ro)q(ot)h(no)q(de)g(of)g(the)f(sub)s (ject)f(tree.)73 756 y Fe(\017)24 b Fn(mtValue)p Fo(\()p Fk(r)q Fo(\))14 b(returns)i(the)g(in)o(teger)f(asso)q(ciated)j(with)e Fk(r)h Fo(\(See)f(section)g(3.3\).)73 856 y Fe(\017)24 b Fn(mtSetNodes)o Fo(\()p Fk(r)o(;)7 b(n;)h(c)p Fo(\))17 b(replaces)j(the)f Fk(n)p Fo(th)h(c)o(hild)e(of)j Fk(r)g Fo(with)e Fk(c)p Fo(.)32 b(This)20 b(routine)g(ma)o(y)e(b)q(e)i(used)g(to)122 916 y(replace)c(whole)g(subtrees)h (with)f(others.)23 b Fn(mtSetNodes)o Fo(\()p Fn(NU)o(LL)m Fk(;)8 b Fo(0)p Fk(;)g(c)p Fo(\))16 b(is)h(used)g(b)o(y)f Fn(twig)f Fo(to)i(set)f(the)122 976 y(ro)q(ot)h(of)g(the)f(sub)s(ject)f(tree)h(to)h Fk(c)p Fo(.)0 1120 y Fc(3.6)70 b(Prologue)23 b(and)g(Inserts)122 1213 y Fn(prologue)13 b Fk(ccode)p Fo(;)0 1321 y(signals)22 b(to)g Fn(twig)e Fo(that)i Fk(ccode)g Fo(should)h(b)q(e)e(inserted)g(at)h (the)g(b)q(eginning)g(of)g(the)f(output)h(source)g(\014le.)0 1382 y Fk(C)t(code)15 b Fo(should)g(con)o(tain)g(de\014nitions)g(relev)m(an)o (t)f(to)i(the)f(C)g(co)q(de)g(in)g(rules)f(that)i(are)f(de\014ned)g(later)g (in)f(the)0 1442 y Fp(twig)j Fo(source)f(\014le.)122 1551 y Fn(insert)e Fk(ccode)p Fo(;)0 1660 y(causes)19 b Fk(ccode)g Fo(to)g(b)q(e)f(placed)g(in)o(to)g(the)g(source)h(\014le.)27 b(There)18 b(can)h(b)q(e)g(m)o(ultiple)c(inserts)j(and)h(they)f(will)0 1720 y(b)q(e)e(placed)g(in)o(to)g(the)g(source)g(\014le)g(in)g(the)g(order)g (that)h(they)f(app)q(ear.)0 1863 y Fc(3.7)70 b(Declarations)0 1956 y Fo(All)15 b Fp(twig)i Fo(iden)o(ti\014ers)e(are)h(declared)g(b)q (efore)g(they)g(are)g(used.)122 2065 y Fn(node)24 b Fk(id)p Fo([\()p Fk(int)389 2072 y Fg(1)408 2065 y Fo(\)][=)13 b Fk(int)570 2072 y Fg(2)589 2065 y Fo(])p Fk(:::)p Fn(;)0 2174 y Fo(A)h(no)q(de)g (declaration)g(declares)g(one)g(or)g(more)f(iden)o(ti\014er)g(to)h(b)q(e)g (asso)q(ciated)h(with)f(no)q(des)h(of)g(the)f(sub)s(ject)0 2234 y(tree.)31 b(The)20 b(iden)o(ti\014ers)f(are)h(assigned)g(n)o(um)o(b)q (ers)f(b)o(y)g Fn(twig)g Fo(but)h(the)f(user)h(can)g(o)o(v)o(eride)f(the)g (assigned)0 2294 y(n)o(um)o(b)q(er)h(b)o(y)i(sp)q(ecifying)f Fk(int)553 2301 y Fg(2)572 2294 y Fo(.)39 b(The)22 b(degree)f(of)i(the)f(no)q (de)g(iden)o(tifer,)f(the)h(n)o(um)o(b)q(er)e(of)j(c)o(hildren,)e(is)0 2354 y(assumed)h(to)h(b)q(e)g(\014xed.)41 b(Normally)l(,)22 b Fn(twig)f Fo(will)h(deduce)g(the)h(degree)f(when)h Fk(id)g Fo(is)f(used)h(in)g(a)g(rule.)0 2414 y(Ho)o(w)o(ev)o(er,)14 b(the)i(user)g(ma)o(y)f(explicitly)e(giv)o(e)j(the)g(degree)f(b)o(y)h(sp)q (ecifying)g Fk(int)1409 2421 y Fg(1)1428 2414 y Fo(.)122 2523 y Fn(label)24 b Fk(id:::)p Fn(;)73 2632 y Fo(A)16 b(lab)q(el)g(declaration)g (indicates)f(that)i(the)f(follo)o(wing)g Fk(id)p Fo('s)g(are)g(to)h(b)q(e)f (used)h(as)g(lab)q(els)f(of)g(rules.)963 2757 y(8)p eop %%Page: 7 14 bop 73 154 a Fo(There)20 b(are)g(t)o(w)o(o)h(t)o(yp)q(es)f(of)g(sym)o(b)q (ols:)28 b Fk(node)p 908 154 15 2 v 18 w(id)p Fo(s)21 b(and)g Fk(l)q(abel)p 1209 154 V 17 w(id)p Fo(s.)33 b Fk(N)5 b(ode)p 1448 154 V 18 w(id)p Fo(s)21 b(are)f(used)g(to)h(denote)0 214 y(in)o(ternal)c(no)q(des)h(and)h(lea)o(v)o(es.)24 b Fk(Label)p 702 214 V 18 w(id)p Fo(s)18 b(lab)q(el)f(tree)g(patterns)h(and)h(are)f (analogous)i(to)e(non)o(terminals)0 274 y(in)g(con)o(text)f(free)g(grammars.) 25 b(F)l(or)18 b(example,)d(the)j(follo)o(wing)g Fp(twig)g Fo(rules)g(without)g(their)f(action)h(parts)0 334 y(describ)q(e)e(simple)e (expression)i(trees)f(with)h(the)g Fn(plus)f Fo(op)q(erator.)195 442 y Fn(expr:)50 b(plus\(expr)o(,)22 b(expr\))195 502 y(expr:)50 b(identifie)o(r)195 562 y(expr:)g(constant)0 669 y Fo(Here,)21 b Fn(identifier)d Fo(and)k Fn(constant)c Fo(are)j Fk(node)p 928 669 V 19 w(id)p Fo(s)g(represen)o(ting)g(lea)o(v)o(es,)f(and)i Fn(plus)e Fo(is)h(a)h Fk(node)p 1893 669 V 18 w(id)0 730 y Fo(represen)o(ting)c(an)h(in)o(ternal)f(no)q(de)h(whereas)g Fn(expr)e Fo(is)i(a)g Fk(l)q(abel)p 1159 730 V 17 w(id)p Fo(.)28 b(P)o(attern)19 b(lea)o(v)o(es)e(that)i(are)g Fk(l)q(abel)p 1876 730 V 17 w(id)p Fo(s)0 790 y(are)d(called)f Fj(lab)q(elled)h(lea)o(v)o (es)p Fo(.)j(In)d(the)g(\014rst)h(rule,)e(b)q(oth)i(lea)o(v)o(es)e(of)i(the)f (pattern)g(are)g(lab)q(elled.)73 850 y Fn(Twig)g Fo(asso)q(ciates)i(an)g(in)o (teger)e(with)h(eac)o(h)g(no)q(de)g(sym)o(b)q(ol)f(and)i(lab)q(el)f(sym)o(b)q (ol.)22 b(These)c(in)o(tegers)e(are)0 910 y(used)e(b)o(y)f(the)g Fp(twig)h Fo(pattern)g(matc)o(her)e(as)i(enco)q(dings)g(for)g(the)f(sym)o(b)q (ols.)19 b(As)14 b(the)f(matc)o(her)f(tra)o(v)o(erses)g(the)0 970 y(tree,)j(a)i(user)f(supplied)g(subroutine)g(is)g(called)f(to)i(pro)o (vide)e(an)i(in)o(teger)e(corresp)q(onding)j(to)e(eac)o(h)g(no)q(de.)0 1114 y Fc(3.4)70 b(Costs)0 1206 y Fo(T)l(o)17 b(increase)f(the)h (\015exibilit)o(y)d(of)j(represen)o(ting)f(costs,)h(the)f(tree)g(matc)o(her)f (views)h(costs)i(as)f(an)g Fj(abstract)0 1266 y(data)j(t)o(yp)q(e)f Fo(or)h(ADT.)f(F)l(or)g(example,)f(costs)h(ma)o(y)f(b)q(e)i(represen)o(ted)e (as)i(an)g(in)o(teger)e(or)i(as)g(a)f(v)o(ector)g(of)0 1327 y(in)o(tegers)c(with)g(eac)o(h)g(elemen)o(t)d(represen)o(ting)j(the)g(cost)h (of)g(a)g(sp)q(eci\014c)e(resource.)21 b(A)15 b(cost)h(ADT)f(suitable)0 1387 y(for)i Fp(twig)g Fo(m)o(ust)e(ha)o(v)o(e)g(the)h(follo)o(wing)g(four)h (de\014nitions:)73 1494 y Fe(\017)24 b Fn(COST)11 b Fo(is)i(a)h(C)f(t)o(yp)q (e.)19 b(Although)13 b(the)g(prop)q(er)h(functioning)e(of)i(the)e(tree)h (matc)o(her)e(do)q(es)i(not)h(dep)q(end)122 1554 y(on)i(the)g(in)o(ternal)f (details)g(of)h(the)f Fn(COST)g Fo(t)o(yp)q(e,)g(it)g(m)o(ust)f(ha)o(v)o(e)h (the)h(t)o(yp)q(e)f(information)g(for)h(storage)122 1615 y(allo)q(cation)g (purp)q(oses.)73 1715 y Fe(\017)24 b Fn(INFINITY)15 b Fo(is)j(the)g(maxim)o (um)c(attainable)k(cost)g(v)m(alue.)27 b(The)18 b(matc)o(her)e(uses)j Fn(INFINITY)c Fo(to)k(ini-)122 1775 y(tialize)c(its)h(data)h(structures.)73 1875 y Fe(\017)24 b Fn(DEFAULT)p 307 1875 16 2 v 16 w(COST)15 b Fo(is)h(the)g(cost)g(v)m(alue)g(returned)g(b)o(y)g(rules)g(without)g(a)h (cost)f(part.)73 1975 y Fe(\017)24 b Fn(COSTLESS)15 b Fo(is)i(a)h(function)g (of)g(t)o(w)o(o)g(cost)g(v)m(alues.)25 b(It)18 b(m)o(ust)e(return)i(true)f (if)g(and)i(only)e(if)g(the)h(\014rst)122 2035 y(argumen)o(t)d(is)h(less)g (than)h(the)f(second.)0 2179 y Fc(3.5)70 b(T)-6 b(rees)0 2271 y Fo(As)19 b(with)h(costs,)g(trees)g(are)f(treated)h(as)g(an)g(ADT.)f(Here,)g (using)h(an)g(ADT)g(is)f(ev)o(en)g(more)f(imp)q(ortan)o(t)0 2331 y(b)q(ecause)g(trees)g(come)e(in)i(a)h(v)m(ariet)o(y)e(of)h(shap)q(es)h (and)g(represen)o(tations.)26 b Fp(Twig)19 b Fo(w)o(ould)f(b)q(e)h(o)o(v)o (erly)d(com-)0 2391 y(plicated)i(if)h(it)g(had)h(to)g(kno)o(w)f(an)o(y)g (more)f(than)i(the)f(fundamen)o(tal)f(prop)q(erties)h(of)h(trees.)30 b(Th)o(us,)20 b Fp(twig)0 2452 y Fo(treats)e(trees)f(as)h(an)g(acyclic)d (directed)i(graph)h(of)g(almost)e(featureless)h(no)q(des)h(with)g(one)f (distinguished)0 2512 y(no)q(de,)g(the)f(ro)q(ot.)23 b(Eac)o(h)17 b(no)q(de)g(has)g(only)g(one)f(feature)h(and)g(that)g(is)f(an)h(in)o(teger)f (corresp)q(onding)h(to)g(the)0 2572 y Fk(node)p 103 2572 15 2 v 18 w(id)p Fo(s)g(discussed)f(ab)q(o)o(v)o(e.)21 b(T)l(o)c(pro)o(vide)f (this)g(view)g(to)g Fp(twig)p Fo(,)h(the)f(user)h(m)o(ust)e(pro)o(vide)g(the) h(follo)o(wing)0 2632 y(de\014nitions)g(and)h(subroutines.)963 2757 y(7)p eop %%Page: 6 15 bop 808 555 124 2 v 808 645 2 91 v 844 615 a Fn(id)p 930 645 V 808 647 124 2 v 1198 555 154 2 v 1198 645 2 91 v 1211 614 a(const)p 1350 645 V 1198 647 154 2 v 988 375 V 988 465 2 91 v 1014 430 a(plus)p 1140 465 V 988 467 154 2 v 778 195 V 778 285 2 91 v 804 250 a(plus)p 930 285 V 778 287 154 2 v 598 375 124 2 v 598 465 2 91 v 634 435 a(id)p 720 465 V 598 467 124 2 v 930 556 a Fh(\012)958 515 y(\012)962 508 y(\012)1172 556 y(J)1145 515 y(J)1140 508 y(J)962 376 y(J)935 335 y(J)930 328 y(J)720 376 y(\012)748 335 y(\012)752 328 y(\012)655 964 y Fn(plus\(id,)22 b(plus\(id,)h(const\)\))563 1120 y Fo(Figure)16 b(2:)22 b(A)16 b(T)l(ree)f(and)i(its)f(pre\014xed)g(form)0 1254 y Fc(3.2)70 b(Rules)0 1346 y Fo(The)16 b(fundamen)o(tal)f(unit)h(of)h(a) f Fp(twig)h Fo(program)g(is)f(a)g(rule.)122 1461 y Fk(l)q(abel)p 227 1461 15 2 v 17 w(id)g Fl(:)21 b Fk(tr)q(ee)p 425 1461 V 17 w(patter)q(n)48 b Fl([)16 b Fk(cost)g Fl(])g([)i(=)e Fk(action)g Fl(])0 1575 y Fo(In)o(tuitiv)o(ely)l(,)10 b(the)i(pattern)i(is)e(used)h(to)g (matc)o(h)f(a)h(subtree.)20 b(The)13 b Fk(cost)g Fo(co)q(de)g(fragmen)o(t)e (is)i(then)g(ev)m(aluated.)0 1635 y(The)j(resulting)f(cost)i(is)e(recorded)h (b)o(y)f(the)h(matc)o(her)e(for)i(use)g(in)g(dynamic)e(programming.)20 b(The)c Fk(action)0 1695 y Fo(is)22 b(executed)e(if)i(the)f(rule)h(is)f(part) i(of)f(the)g(least)g(cost)g(co)o(v)o(er)f(of)h(the)g(tree.)37 b(The)22 b(details)g(of)g(pattern)0 1755 y(matc)o(hing)15 b(will)g(b)q(e)h (discussed)g(in)g(Section)g(4.)73 1816 y(If)i(the)h Fk(cost)g Fo(part)g(is)f(missing,)g Fn(twig)f Fo(will)h(insert)g(default)g(co)q(de)h (that)g(returns)g(the)f(sp)q(ecial)h(v)m(alue,)0 1876 y Fn(DEFAULT)p 185 1876 16 2 v 16 w(COST)p Fo(.)d(A)i(missing)f Fk(action)g Fo(part)i(indicates)e(that)i(nothing)f(will)f(b)q(e)i(done)f(when)g(a)h(matc) o(h)d(is)0 1936 y(found.)0 2080 y Fc(3.3)70 b(T)-6 b(ree)22 b(P)n(atterns)0 2173 y Fo(T)l(ree)12 b(patterns)h(are)g(sp)q(eci\014ed)f(in)g (pre\014x)g(paren)o(thesized)f(form)h(and)h(can)f(b)q(e)h(describ)q(ed)f(b)o (y)g(the)g(follo)o(wing)0 2233 y(BNF:)122 2347 y Fk(tr)q(ee)p 212 2347 15 2 v 17 w(patter)q(n)h Fe(!)h Fk(node)p 567 2347 V 18 w(id)f Fe(j)h Fk(l)q(abel)p 770 2347 V 17 w(id)122 2407 y(tr)q(ee)p 212 2407 V 17 w(patter)q(n)f Fe(!)h Fk(node)p 567 2407 V 18 w(id)f Fo(\()h Fk(tr)q(ee)p 760 2407 V 17 w(l)q(ist)f Fo(\))122 2467 y Fk(tr)q(ee)p 212 2467 V 17 w(l)q(ist)f Fe(!)i Fk(tr)q(ee)f(;)g(tr)q(ee)p 593 2467 V 17 w(l)q(ist)g Fe(j)g Fk(tr)q(ee)0 2582 y Fo(Figure)j(2)g(giv)o(es)g(an)h(example)d(of)i(a)h(tree)e (pattern)i(and)g(its)f(pre\014x)g(paren)o(thesized)f(form.)963 2757 y(6)p eop %%Page: 5 16 bop 73 154 a Fe(\017)24 b Fo(T)l(ree)17 b(templates)f(in)i([3])f(w)o(ere)g (lab)q(elled)g(with)g(either)g Fj(Register)g Fo(or)h Fj(Memory)p Fo(.)24 b(This)18 b(lab)q(el)g(b)q(eing)122 214 y(the)13 b(storage)h(class)f (that)h(the)f(instruction)f(corresp)q(onding)j(to)e(the)g(template)e(w)o (ould)i(put)g(a)h(result.)122 274 y Fp(Twig)j Fo(generalize)e(tree)g(lab)q (els)h(so)h(that)g(they)f(can)g(b)q(e)g(an)o(y)h(sym)o(b)q(ol.)73 376 y Fe(\017)24 b Fo(Instead)16 b(of)h(asso)q(ciating)g(an)g(instruction)f (with)g(eac)o(h)g(template,)e Fp(twig)j Fo(asso)q(ciates)g(an)g(action.)73 477 y Fe(\017)24 b Fo(In)14 b([3],)g(co)q(de)h(is)g(generated)g(b)o(y)f(a)h (b)q(ottom)g(up)g(tra)o(v)o(ersal)f(of)h(the)f(minim)n(um)d(cost)k(co)o(v)o (ering.)k Fp(Twig)122 538 y Fo(allo)o(ws)d(a)h(top)g(do)o(wn)f(tra)o(v)o (ersal)g(of)g(the)h(co)o(v)o(er)e(and)h(also)h(the)f(abilit)o(y)f(for)i(the)f (actions)g(to)h(rewrite)122 598 y(parts)g(of)f(the)g(tree.)73 699 y Fe(\017)24 b Fo(The)d(algorithm)f(in)g([3])h(determines)e(the)h(ev)m (aluation)h(order)g(whic)o(h)g(giv)o(es)f(the)h(optimal)e(co)q(de.)122 760 y Fp(Twig)e Fo(do)q(es)h(not)f(do)g(this.)22 b(The)17 b(ev)m(aluation)f (order)h(determination)e(w)o(as)i(omitted)e(based)i(on)g(the)122 820 y(conjecture)d(that)i(most)e(of)h(the)g(time,)e(simple)f(left)j(to)g (righ)o(t)g(ev)m(aluation)g(of)g(the)g(lea)o(v)o(es)e(will)h(yield)122 880 y(near)k(optimal)e(results.)26 b(In)18 b(situations)g(where)f(a)i (nonstandard)g(ev)m(aluation)f(order)g(is)g(required,)122 940 y(a)f(new)f Fp(twig)h Fo(pattern)f(could)h(b)q(e)f(added)h(that)f(co)q(des)h (the)f(order)g(explicitly)e(\(see)h(Section)h(4.2\).)73 1042 y(In)11 b(this)h(man)o(ual,)f(a)h(brief)e(discussion)i(will)f(b)q(e)g(giv)o (en)g(of)h(the)f Fp(twig)i Fo(language)f(and)g(ho)o(w)g Fp(twig)h Fo(programs)0 1102 y(can)j(b)q(e)h(incorp)q(orated)g(with)f(C.)73 1162 y(Man)o(y)g(statemen)o(ts)g(ha)o(v)o(e)g(b)q(een)g(made)g(in)g(this)h (man)o(ual)e(without)i(pro)q(of.)24 b(If)16 b(the)g(reader)h(wishes)g(to)0 1222 y(pursue)d(it)f(further,)h(more)e(details)h(ab)q(out)i(the)f(algorithms) f(will)f(b)q(e)i(presen)o(ted)f(in)h(an)g(up)q(coming)f(pap)q(er,)0 1283 y([2].)0 1449 y Fm(3)83 b(The)27 b Fd(Twig)h Fm(Language)0 1573 y Fc(3.1)70 b(Lexical)21 b(Issues)i(and)h(Con)n(v)n(en)n(tions)0 1665 y Fo(Curren)o(tly)15 b(the)h(follo)o(wing)g(iden)o(ti\014ers)f(are)h (reserv)o(ed)f(k)o(eyw)o(ords)h(of)g Fp(twig)p Fo(:)0 1780 y(action)170 b(cost)216 b(insert)0 1840 y(lab)q(el)198 b(no)q(de)h(prologue)0 1954 y(;:\(\),=)11 b(are)i(sp)q(ecial)f(c)o(haracters.)19 b(All)12 b(blanks,)h(tabs,)g(formfeeds)e(and)i(newlines)f(are)h(ignored)f(b)o(y)g Fp(twig)i Fo(but)0 2014 y(they)i(ma)o(y)f(not)i(app)q(ear)h(inside)e(iden)o (ti\014ers)f(and)i(n)o(um)o(b)q(ers.)k(Iden)o(ti\014ers)15 b(are)i(nonempt)o(y)e(strings)i(made)0 2074 y(of)j(letters,)g(digits)g(or)h (underscores)f(and)h(starting)f(with)g(a)h(letter.)32 b(Num)o(b)q(ers)18 b(are)i(nonempt)o(y)f(string)0 2135 y(of)f(digits.)27 b(Co)q(de)18 b(fragmen)o(ts)f(or)i(action)f(parts)h(are)f(enclosed)f(in)h(braces.)26 b(Inside)18 b(co)q(de)g(fragmen)o(ts,)f(C)0 2195 y(lexical)11 b(rules)i(m)o(ust)f(b)q(e)i(ob)q(ey)o(ed)f(except)f(that)h(strings)h(of)g (the)f(form)f($)p Fk(:::)p Fo($)h(that)g(are)h(not)g(inside)e(C)i(strings)0 2255 y(ha)o(v)o(e)k(sp)q(ecial)g(meaning)f(to)i Fp(twig)p Fo(.)30 b(In)18 b(the)g(follo)o(wing)g(sections,)h Fk(id)g Fo(denotes)f(an)h(iden)o (ti\014er;)f Fk(int)1815 2262 y Fg(1)1834 2255 y Fo(,)h Fk(int)1931 2262 y Fg(2)0 2315 y Fo(denotes)i(n)o(um)o(b)q(ers;)f Fk(ccode)h Fo(denotes)f(C)h(co)q(de)f(fragmen)o(ts;)h Fk(:::)e Fo(indicates)h(rep)q (etition)f(of)i(the)f(previous)0 2375 y(item;)14 b([)p Fk(:::)p Fo(])g(indicates)h(that)i Fk(:::)e Fo(is)h(optional.)73 2436 y(The)g(input)g(to)h(the)f Fp(twig)h Fo(program)f(will)g(b)q(e)g(referred)f (to)i(as)g(the)f(sub)s(ject)f(tree.)963 2757 y(5)p eop %%Page: 4 17 bop 0 154 a Fo(compiler)15 b(implem)o(e)o(n)o(tor)f(no)o(w)k(sp)q(eci\014es)e (the)h(source)g(language)h(via)f(grammar)e(pro)q(ductions.)24 b(Sym)o(b)q(ol)0 214 y(table)c(manipulations,)f(and)h(IR)g(construction)g (rules)f(are)h(attac)o(hed)g(to)g(pro)q(ductions)h(and)f(activ)m(ated)0 274 y(when)g(a)f(source)h(language)g(construct)g(is)f(recognized.)30 b(The)19 b(fron)o(t)h(end)f(is)g(then)g Fp(automatic)n(al)r(ly)i Fo(gen-)0 334 y(erated)c(b)o(y)g(pro)q(cessing)i(the)e(sp)q(eci\014cation)g (with)g(a)h(parser)g(generator.)26 b(The)17 b(result)g(is)h(a)g(high)f (qualit)o(y)0 394 y(fron)o(t)f(end)g(whose)h(p)q(erformance)e(is)h(close)g (to)h(that)f(of)h(a)g(hand-crafted)g(fron)o(t)f(end.)73 455 y(Pro)o(viding)e(the)h(same)e(t)o(yp)q(e)h(of)h(facilities)e(for)i (automatically)e(building)h(bac)o(k)g(ends)g(has)i(b)q(een)e(m)o(uc)o(h)0 515 y(more)i(di\016cult.)23 b(Extending)17 b(curren)o(t)g(fron)o(t)g(end)g (parsers)h(to)g(do)g(bac)o(k)f(ends)g(has)h(b)q(een)g(w)o(ork)m(able)f(but)0 575 y(not)i(en)o(tirely)d(successful.)26 b(The)19 b(basic)f(idea)g(is)g(that) h(the)f(bac)o(k)f(end)h(impleme)o(n)o(tor)e(writes)i(a)g Fp(machine)0 635 y(gr)n(ammar)d Fo(for)h(the)g(IR)g(and)h(co)q(de)g(generation)f(o)q (ccurs)h(as)g(actions)f(that)h(are)f(executed)f(when)i(patterns)0 695 y(are)i(found)g(in)f(the)g(IR[5,)g(6].)28 b(Unfortunately)l(,)18 b(these)h(grammars)e(are)i(large)f(and)h(am)o(biguous.)28 b(Using)0 756 y(parsers)20 b(to)f(handle)h(them)d(ha)o(v)o(e)i(usually)g(met)e(with)i (man)o(y)f(com)o(binatorial)g(problems)f([6].)30 b(F)l(urther-)0 816 y(more,)20 b(these)h(co)q(de)g(generators)g(are)g(slo)o(w)g(although)h (their)e(output)h(is)g(often)g(of)g(high)g(qualit)o(y)l(.)33 b(The)0 876 y(soft)o(w)o(are)17 b(engineering)g(adv)m(an)o(tages)h(one)g(see) f(with)g(parsers)g(in)g(the)g(fron)o(t)h(end)f(are)g(not)h(so)g(eviden)o(t)d (in)0 936 y(this)j(circumstance.)26 b(Instead)19 b(of)f(ha)o(ving)h(to)g (deal)f(with)g(the)h(complexiti)o(es)d(of)j(co)q(de)f(generation,)h(the)0 996 y(implem)o(en)o(tor)13 b(no)o(w)k(has)g(to)f(deal)g(with)g(the)g (complexities)d(of)k(the)f(v)o(ery)f(large)h(mac)o(hine)e(grammar.)73 1056 y(Another)k(approac)o(h)i(at)f(automatically)d(building)i(bac)o(k)g (ends)h(is)f(to)h(start)g(with)g(kno)o(wn)f(go)q(o)q(d)j(al-)0 1117 y(gorithms)c(for)h(generating)h(co)q(de.)26 b(F)l(rom)17 b(these)h(algorithms,)f(w)o(e)g(can)h(build)g(an)g(abstract)h(in)o(terpreter) 0 1177 y(and)g(then)g(sp)q(eci\014cations)g(can)g(b)q(e)g(written)f(to)i (driv)o(e)d(them.)28 b(W)l(e)18 b(hop)q(e)i(that)f(b)o(y)f(doing)i(this)e(w)o (e)h(can)0 1237 y(deriv)o(e)f(a)i(m)o(uc)o(h)e(more)g(natural)j(co)q(de)e (generation)h(sp)q(eci\014cation)g(tec)o(hnique.)30 b Fp(Twig)20 b Fo(is)g(one)g(p)q(ossible)0 1297 y(result)c(of)h(this)g(approac)o(h.)23 b(The)17 b(algorithms)e(that)j(form)d(the)i(basis)g(of)g Fp(twig)g Fo(are)g(presen)o(ted)f(in)g([3])g(and)0 1357 y([7].)k Fp(Twig)c Fo(sp)q(eci\014cations)e(are)h(m)o(uc)o(h)e(less)h(complex)f(than)i(parser)g (based)g(sp)q(eci\014cations.)21 b(Am)o(biguities)0 1418 y(are)16 b(handled)h(naturally)f(and)g(do)h(not)g(complicate)d(the)i(sp)q (eci\014cations.)73 1478 y(In)22 b([3],)g(it)f(is)h(sho)o(wn)h(ho)o(w)f (optimal)e(co)q(de)j(can)f(b)q(e)g(generated)f(for)i(an)f(expression)f(tree)h (giv)o(en)f(a)0 1538 y(description)g(of)h(a)g(mac)o(hine's)e(instruction)h (set.)37 b(This)22 b(description)f(is)h(in)f(term)f(of)i(tree)f(templates.)0 1598 y(The)16 b(algorithm)f(\014rst)h(determines)d(a)j(minimal)d(cost)j(co)o (v)o(ering)e(of)j(an)f(expression)f(tree)h(using)g(dynamic)0 1658 y(programming.)27 b(The)19 b(co)o(v)o(ering)e(is)i(comp)q(osed)f(from)f (the)i(templates)e(in)h(the)g(description.)28 b(The)19 b(co)q(de)0 1719 y(generated)e(is)h(then)f(the)g(instructions)h(represen)o(ted)e(b)o(y)h (the)g(templates)f(in)h(the)h(co)o(v)o(ering.)23 b(This)18 b(algo-)0 1779 y(rithm)g(w)o(as)i(sho)o(wn)g(to)g(generate)f(the)g(shortest)i (co)q(de)e(sequences)g(for)h(an)g(abstract)g(mac)o(hine)d(and)j(its)0 1839 y(running)d(time)d(w)o(as)i(sho)o(wn)h(to)g(b)q(e)f(linear)g(in)g(the)g (n)o(um)o(b)q(er)e(of)j(no)q(des)g(in)f(the)g(expression)g(tree)f(in)h([3].) 73 1899 y(This)g(is)f(all)g(v)o(ery)f(w)o(ell)g(in)h(theory)h(but)f(what)i (ab)q(out)f(in)f(practice.)20 b(Co)q(de)d(length)e(is)g(not)h(alw)o(a)o(ys)f (the)0 1959 y(quan)o(tit)o(y)h(that)h(one)g(wishes)g(to)g(minim)o(ize)o(.)j (One)d(migh)o(t)e(wish)i(to)g(minim)o(ize)c(the)k(n)o(um)o(b)q(er)e(of)i (memory)0 2020 y(accesses)g(or)h(mac)o(hine)d(cycles)g(executed)h(b)o(y)h (the)g(generated)g(co)q(de.)24 b(F)l(ortunately)l(,)17 b(the)g(algorithm)f (can)0 2080 y(also)f(minimi)o(ze)c(these)k(quan)o(tities.)k(In)c(fact,)f(it)g (can)h(minimi)o(ze)c(an)o(y)k(strictly)e(increasing)i(cost)g(function.)0 2140 y(Let)i Fk(I)k Fo(denote)c(a)g(mac)o(hine)e(instruction)i(and)h Fk(I)888 2147 y Fg(0)907 2140 y Fk(I)929 2147 y Fg(1)948 2140 y Fk(I)970 2147 y Fg(2)989 2140 y Fk(:::I)1053 2147 y Ff(n)1092 2140 y Fo(denote)f(a)h(sequence)e(of)h(instructions.)24 b(Then)0 2200 y(a)16 b(cost)f(function)g Fk(f)20 b Fo(is)15 b(strictly)f(increasing)h (if)g(and)g(only)g(if)g Fk(f)5 b Fo(\()p Fk(I)1171 2207 y Fg(0)1191 2200 y Fk(I)1213 2207 y Fg(1)1232 2200 y Fk(I)1254 2207 y Fg(2)1273 2200 y Fk(:::I)1337 2207 y Ff(n)1359 2200 y Fo(\))13 b Fk(<)h(f)5 b Fo(\()p Fk(I)1513 2207 y Fg(0)1533 2200 y Fk(I)1555 2207 y Fg(1)1574 2200 y Fk(I)1596 2207 y Fg(2)1615 2200 y Fk(:::I)1679 2207 y Ff(n)1701 2200 y Fk(I)1723 2207 y Ff(n)p Fg(+1)1791 2200 y Fo(\))15 b(for)h(all)0 2260 y(instruction)f(sequences)g Fk(I)489 2267 y Fg(0)508 2260 y Fk(I)530 2267 y Fg(1)549 2260 y Fk(I)571 2267 y Fg(2)590 2260 y Fk(:::I)654 2267 y Ff(n)691 2260 y Fo(and)h(instruction)f Fk(I)1053 2267 y Ff(n)p Fg(+1)1121 2260 y Fo(.)21 b(Another)16 b(shortcoming)e(in)i([3)o(])f(is)h(that)g(no)0 2320 y(e\016cien)o(t)g(algorithm)g(is)i(giv)o(en)e(for)i(matc)o(hing)e(the)i (templates)e(in)h(the)g(tree.)25 b(This)18 b(is)f(where)g([7])g(comes)0 2381 y(in.)k(In)16 b(that)h(pap)q(er,)g(t)o(w)o(o)f(algorithms)f(are)i (presen)o(ted)e(for)i(tree)f(matc)o(hing.)k Fp(Twig)d Fo(com)o(bines)d(the)i (w)o(ork)0 2441 y(presen)o(ted)f(in)h(the)g(t)o(w)o(o)g(pap)q(ers.)73 2501 y Fp(Twig)h Fo(di\013ers)f(from)f(the)h(algorithm)g(as)h(presen)o(ted)e (in)h([3])g(in)f(the)h(follo)o(wing)g(w)o(a)o(ys:)73 2603 y Fe(\017)24 b Fo(It)16 b(pro)o(vides)f(a)i(con)o(v)o(enien)o(t)d(sp)q (eci\014cation)i(language)h(for)g(the)f(templates.)963 2757 y(4)p eop %%Page: 3 18 bop 283 1813 a Fi(')p 283 2296 2 401 v 283 2380 a(&)1416 1813 y($)p 1416 2296 V 1416 2380 a(\045)p 366 2380 968 2 v 366 1813 V 494 1882 216 2 v 494 2024 2 142 v 556 1947 a Fo(T)l(ree)548 1994 y(ADT)p 709 2024 V 494 2026 216 2 v 537 2067 V 537 2208 2 142 v 596 2131 a(Cost)590 2178 y(ADT)p 751 2208 V 537 2210 216 2 v 990 2095 287 2 v 990 2237 2 142 v 1043 2178 15 2 v 359 w(matc)o(h\(\))p 1276 2237 2 142 v 990 2239 287 2 v 850 1812 2 142 v 850 1812 a Fh(?)p 636 1386 429 2 v 636 1670 2 284 v 760 1494 a Fo(compiler)831 1550 y(&)791 1597 y(link)o(er)p 1063 1670 V 636 1672 429 2 v 496 1530 142 2 v 596 1529 a Fh(-)p 1063 1530 V 425 w(\033)p 850 1387 2 142 v 850 1387 a(?)70 1459 y Fi(\037)p 70 1533 2 9 v 70 1601 a(\036)495 1459 y(\034)p 495 1533 V 495 1601 a(\035)p 137 1601 293 2 v 137 1459 V 1204 1459 a(\037)p 1204 1533 2 9 v 1204 1601 a(\036)1629 1459 y(\034)p 1629 1533 V 1629 1601 a(\035)p 1271 1601 293 2 v 1271 1459 V 216 1508 a Fo(rest)16 b(of)240 1541 y(user)194 1575 y(program)1329 1546 y(w)o(alk)o(er.h)708 963 y Fi(')p 708 1162 2 118 v 708 1246 a(&)991 963 y($)p 991 1162 V 991 1246 a(\045)p 792 1246 118 2 v 792 963 V 764 1069 a Fo(w)o(alk)o(er.c)831 1116 y(&)745 1163 y(sym)o(b)q(ols.h)p 850 962 2 142 v 850 962 a Fh(?)p 636 536 429 2 v 636 819 2 284 v 796 668 a Fo(Twig)718 712 y(prepro)q(cessor)p 1063 819 V 636 821 429 2 v 850 537 2 142 v 850 537 a Fh(?)708 254 y Fi(\037)p 708 329 2 9 v 708 396 a(\036)991 254 y(\034)p 991 329 V 991 396 a(\035)p 775 396 151 2 v 775 254 V 805 308 a Fo(t)o(wig)720 364 y(sp)q(eci\014cation)p 1063 679 142 2 v 1063 678 a Fh(\033)1204 609 y Fi(\037)p 1204 683 2 9 v 1204 750 a(\036)1629 609 y(\034)p 1629 683 V 1629 750 a(\035)p 1271 750 293 2 v 1271 609 V 1319 696 a Fo(w)o(alk)o(er)p Fp(.xx)666 2481 y Fo(Figure)g(1:)22 b(The)16 b Fl(Twig)35 b Fo(system)963 2757 y(3)p eop %%Page: 2 19 bop 0 162 a Fm(1)83 b(In)n(tro)r(duction)0 271 y Fp(Twig)20 b Fo(is)g(a)g(language)h(for)f(writing)g(tree)f(manipulation)g(programs.)32 b(A)20 b Fp(twig)g Fo(program)g(do)q(es)h(this)f(b)o(y)0 332 y(using)i(a)g(matc)o(her)e(to)i(\014nd)g(a)g(minimal)c(cost)k(co)o(v)o(ering) f(of)h(a)g(tree.)37 b(The)21 b(co)o(v)o(ering)g(is)g(comp)q(osed)h(of)0 392 y(user)f(supplied)f(templates.)33 b(T)l(rees)20 b(are)h(manipulated)e(b)o (y)h(executing)g(the)g(actions)h(asso)q(ciated)h(with)0 452 y(the)f(templates)f(of)i(their)f(co)o(v)o(erings.)37 b(These)22 b(actions)g(ma)o(y)e(rewrite)h(the)g(tree,)h(up)q(date)g(other)g(data)0 512 y(structures,)16 b(or)g(generate)g(output.)73 572 y(Figure)c(1)g(giv)o (es)f(an)i(o)o(v)o(erview)d(of)j(the)e Fp(twig)i Fo(system.)19 b(The)12 b(round)g(b)q(o)o(xes)g(in)g(the)g(\014gure)g(indicates)f(\014les)0 633 y(and)j(the)f(sharp)g(cornered)g(b)q(o)o(xes)g(are)g(pro)q(cessing)h (programs.)20 b(The)14 b(user)f(writes)f(the)h Fp(twig)h Fo(sp)q (eci\014cation)0 693 y(\014le.)21 b(This)c(\014le)f(is)g(then)g(compiled)f(b) o(y)h(the)g Fn(twig)f Fo(compiler)f(in)o(to)i(host)h(language)h(\014les.)j (In)c(the)f(curren)o(t)0 753 y(v)o(ersion)e(of)h Fp(twig)p Fo(,)h(the)f(host)g(language)h(is)f(C.)f(The)h(host)h(language)g(\014les)e (are)h(then)g(compiled)d(and)k(link)o(ed)0 813 y(with)j(other)h(user)f (supplied)g(\014les.)31 b(The)19 b(resulting)g(program)h(represen)o(ted)e(b)o (y)h(the)g(large)h(b)q(o)o(x)f(at)h(the)0 873 y(b)q(ottom)13 b(of)g(\014gure)g(1)h(is)e(the)h(tree)f(manipulation)g(program.)20 b(The)13 b(details)g(of)g(this)g(b)q(o)o(x)g(will)f(b)q(e)h(discussed)0 934 y(later.)0 1100 y Fm(2)83 b(Motiv)-5 b(ation)0 1209 y Fo(Although)18 b Fp(Twig)g Fo(is)g(a)g(language)h(for)f(manipulating)e(trees)i(it)f(w)o(as)h (originally)f(motiv)m(ated)g(b)o(y)g(pattern)0 1270 y(directed)k(co)q(de)h (generation.)39 b(In)22 b(man)o(y)f(compilers,)g(the)h(t)o(ypical)e (structure)i(is)g(a)h Fj(fron)o(t)f(end)g Fo(and)h(a)0 1330 y Fj(bac)o(k)17 b(end)p Fo(.)25 b(The)18 b(fron)o(t)g(end)f(reads)h(the)f (input)h(source)f(program,)h(c)o(hec)o(ks)e(its)h(syn)o(tax)h(and)g(con)o (textual)0 1390 y(conditions,)d(and)g(builds)f(an)i(in)o(termedi)o(ate)c (represen)o(tation)i(of)h(the)g(program.)20 b(The)15 b(language)h(used)f(to)0 1450 y(do)f(this)g(represen)o(tation)f(is)h(often)g(called)f(the)g Fp(interme)n(diate)j(r)n(epr)n(esentation)e Fo(and)h(will)d(b)q(e)i (abbreviated)0 1510 y(as)j(IR.)e(The)h(bac)o(k)g(end)g(tak)o(es)g(the)g(IR)g (and)h(translates)g(it)e(in)o(to)h(the)g(target)h(mac)o(hine)d(co)q(de.)73 1571 y(That)23 b(isn't)e(the)g(whole)h(story)g(but)g(it's)f(close.)37 b(Both)22 b(ends)g(ma)o(y)e(b)q(e)i(sets)g(of)g(programs)g(rather)0 1631 y(than)e(one)f(program.)29 b(There)19 b(ma)o(y)e(also)j(b)q(e)f(a)g Fp(midd)r(le)h Fo(that)f(p)q(erforms)g(transformations)g(on)g(the)g(IR.)0 1691 y(The)e(in)o(ten)o(tion)g(of)g(these)g(transformations)h(is)f(to)h (impro)o(v)o(e)d(the)i(target)h(co)q(de)g(that)g(comes)e(out)i(of)f(the)0 1751 y(compiler.)i(F)l(or)d(this)g(discussion,)g(w)o(e)g(can)g(ignore)h(the)f (middle.)73 1811 y(IRs)f(can)h(v)m(ary)g(greatly)f(from)f(compiler)f(to)j (compiler.)i(Ho)o(w)o(ev)o(er)c(the)h(IRs)h(are)f(implem)o(en)o(te)o(d,)e (they)0 1872 y(are)k(enco)q(dings)g(of)g(graphs.)24 b(Usually)16 b(three)g(t)o(yp)q(es)h(of)g(graphs)h(are)f(eviden)o(t[4)n(].)23 b(There)16 b(is)h(a)g(\015o)o(wgraph)0 1932 y(whose)i(no)q(des)g(are)f Fj(basic)g(blo)q(c)o(ks)f Fo(and)i(the)f(edges)g(corresp)q(onds)h(to)g (transfer)f(of)g(con)o(trol)g(b)q(et)o(w)o(een)f(the)0 1992 y(basic)f(blo)q(c)o(ks.)21 b(Basic)16 b(blo)q(c)o(ks)g(are)g(not)h (featureless.)j(They)c(are)g(graphs)i(themselv)o(es.)g(Some)d(compilers)0 2052 y(will)d(represen)o(t)h(them)f(as)i(a)g(forest)g(of)g Fp(dir)n(e)n(cte)n(d)g(acyclic)i(gr)n(aphs)d Fo(or)h(D)o(A)o(Gs.)20 b(The)14 b(no)q(des)g(are)g(data)g(v)m(alues)0 2112 y(and)k(op)q(erations.)27 b(Since)17 b(op)q(erations)h(yields)f(v)m(alues,)g(one)h(can)g(think)f(of)h (no)q(des)h(as)f(corresp)q(onding)h(to)0 2172 y(v)m(alues.)32 b(An)19 b(edge)h(exists)f(from)g(no)q(de)h Fk(a)g Fo(to)g(no)q(de)g Fk(b)g Fo(if)f(and)i(only)e(if)g(the)h(v)m(alue)f(corresp)q(onding)i(to)f Fk(a)0 2233 y Fo(dep)q(ends)f(on)g(the)f(v)m(alue)h(corresp)q(onding)g(to)g Fk(b)p Fo(.)28 b(Other)19 b(compilers)d(will)i(use)g(trees)g(instead)h(of)g (D)o(A)o(Gs.)0 2293 y(T)l(rees)d(are)g(not)h(as)g(general)e(as)i(D)o(A)o(Gs)f (and)h(these)f(compilers)e(o)o(v)o(ercome)f(that)k(b)o(y)e(using)i(some)e(t)o (yp)q(e)h(of)0 2353 y(lab)q(elling)f(or)i(cop)o(ying.)73 2413 y(W)l(riting)e(a)g(fron)o(t)g(end)g(usually)f(in)o(v)o(olv)o(es)f(writing)i (a)g(recognizer)f(for)h(the)g(source)g(language,)h(design-)0 2473 y(ing)e(a)h(sym)o(b)q(ol)e(table,)h(and)h(determining)d(an)j(error)f (reco)o(v)o(ery)e(strategy)l(.)21 b(What)15 b(has)g(made)e(this)h(pro)q(cess) 0 2534 y(easy)e(are)g(parser)g(generators)h(lik)o(e)d(Y)l(A)o(CC[8)o(].)20 b(They)12 b(separate)g(out)g(the)g(task)g(of)h(recognizing)e(the)h(source)0 2594 y(language)18 b(from)f(the)g(other)h(details.)24 b(This)18 b(mak)o(es)d(the)j(task)f(in)o(tellectually)e(more)h(manageable.)24 b(The)963 2757 y(2)p eop %%Page: 1 20 bop 0 161 a Fm(Con)n(ten)n(ts)0 271 y Fl(1)45 b(In)n(tro)r(duction)1540 b(2)0 380 y(2)45 b(Motiv)m(ation)1579 b(2)0 489 y(3)45 b(The)19 b Fp(Twig)g Fl(Language)1379 b(5)73 549 y Fo(3.1)50 b(Lexical)16 b(Issues)g(and)h(Con)o(v)o(en)o(tions)48 b Fk(:)24 b(:)h(:)f(:)h(:)f(:)h(:)f (:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)92 b Fo(5)73 609 y(3.2)50 b(Rules)17 b Fk(:)25 b(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f (:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h (:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)92 b Fo(6)73 669 y(3.3)50 b(T)l(ree)16 b(P)o(atterns)36 b Fk(:)25 b(:)f(:)h(:)f(:)h(:)f(:) h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f (:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)92 b Fo(6)73 730 y(3.4)50 b(Costs)19 b Fk(:)25 b(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:) h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h (:)f(:)g(:)h(:)f(:)h(:)92 b Fo(7)73 790 y(3.5)50 b(T)l(rees)22 b Fk(:)j(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f (:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h (:)f(:)h(:)92 b Fo(7)73 850 y(3.6)50 b(Prologue)17 b(and)g(Inserts)39 b Fk(:)25 b(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h (:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)92 b Fo(8)73 910 y(3.7)50 b(Declarations)24 b Fk(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h (:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f (:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)92 b Fo(8)73 970 y(3.8)50 b(Costs)18 b(and)f(Action)e(co)q(de)37 b Fk(:)24 b(:)h(:)f(:)g(:)h(:)f(:)h(:) f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h (:)f(:)h(:)92 b Fo(9)0 1079 y Fl(4)45 b(P)n(attern)19 b(Matc)n(her)g(Op)r (eration)1171 b(9)73 1139 y Fo(4.1)50 b(The)17 b(Costing)g(Phase)38 b Fk(:)24 b(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g (:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)67 b Fo(10)73 1200 y(4.2)50 b(The)17 b(Execution)e(Phase)26 b Fk(:)f(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:) h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)67 b Fo(10)0 1309 y Fl(5)45 b(Some)17 b(Examples)1434 b(11)73 1369 y Fo(5.1)50 b(Expression)17 b(T)l(rees)f(to)g(Pre\014x)35 b Fk(:)24 b(:)g(:)h(:)f(:)h(:)f (:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h (:)f(:)h(:)67 b Fo(11)73 1429 y(5.2)50 b(Short)17 b(Circuited)e(Bo)q(olean)i (Ev)m(aluation)25 b Fk(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:) f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)67 b Fo(14)73 1489 y(5.3)50 b(Co)q(de)17 b(Generation)42 b Fk(:)25 b(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h (:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)h(:)f(:)g (:)h(:)f(:)h(:)67 b Fo(14)0 1598 y Fl(6)45 b(Ho)n(w)20 b(to)e(run)h Fn(Twig)1415 b Fl(14)0 1707 y(7)45 b(Organization)18 b(of)h(the)f Fn(Twig)g Fl(Compiler)976 b(16)0 1816 y(8)45 b(P)n(erformance)1511 b(19)963 2757 y Fo(1)p eop %%Page: 0 21 bop 528 780 a Fr(Twig)30 b(Reference)h(Man)n(ual)713 1001 y Fq(Stev)n(en)19 b(W.K.)h(Tjiang)195 1135 y Fp(Twig)f Fo(is)f(a)h(language)g (for)f(manipulating)f(trees.)27 b(A)18 b Fp(twig)h Fo(program)f(consists)h (of)g(a)195 1195 y(set)14 b(of)h(pattern-action)f(rules)g(together)g(with)g (asso)q(ciated)h(declarations.)21 b(P)o(atterns)195 1255 y(describ)q(e)e (trees)f(to)i(b)q(e)f(matc)o(hed.)28 b(Actions)19 b(calculate)f(costs,)i(p)q (erform)e(tree)h(ma-)195 1316 y(nipulations)h(and)h(other)f(functions)g(suc)o (h)g(as)g(emitting)e(co)q(de.)33 b(A)19 b Fp(twig)i Fo(program)195 1376 y(is)d(translated)i(b)o(y)e(the)g Fn(twig)f Fo(compiler)g(in)o(to)h (subroutines)h(and)g(tables)g(in)f(a)h(host)195 1436 y(language.)j(In)16 b(the)g(curren)o(t)g(implem)o(e)o(n)o(tation,)d(the)j(host)h(language)g(is)f (C.)195 1521 y(A)c Fp(twig)h Fo(program)f(manipulates)e(trees)i(b)o(y)g (\014rst)g(\014nding)g(a)h(minim)n(um)8 b(cost)k(co)o(v)o(ering)195 1581 y(of)17 b(the)g(input)g(tree.)22 b(The)17 b(actions)h(of)f(the)f(rules)h (whose)h(pattern)f(parts)g(comp)q(oses)195 1641 y(the)g(co)o(v)o(ering)e(is)i (then)f(executed.)22 b(The)17 b(minim)n(um)12 b(cost)17 b(co)o(v)o(ering)f (is)h(determined)195 1702 y(using)d(dynamic)e(programming.)19 b(This)14 b(tec)o(hnique)e(naturally)h(resolv)o(es)g(man)o(y)g(am-)195 1762 y(biguities)i(that)i(ma)o(y)e(b)q(e)h(in)g(the)g(sp)q(eci\014cations.) 195 1847 y(The)h(prime)e(purp)q(ose)k(of)e Fp(twig)h Fo(is)f(to)h(create)e (tree)h(manipulation)f(programs.)24 b(One)195 1907 y(in)o(teresting)19 b(application)h(of)h(tree)e(manipulation)g(is)h(co)q(de)h(generation)f(and)h Fp(twig)195 1967 y Fo(has)15 b(b)q(een)f(used)g(to)h(implem)o(en)n(t)d(a)i (co)q(de)g(generator)h(for)g(the)f(p)q(cc2)g(compiler)e(on)i(the)195 2028 y(V)-5 b(AX.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF