| | 1 | #! /usr/bin/perl -w |
| | 2 | |
| | 3 | # Copyright (C) 2006, 2008 Free Software Foundation, Inc. |
| | 4 | # |
| | 5 | # This file is part of Bison, the GNU Compiler Compiler. |
| | 6 | # |
| | 7 | # This program is free software: you can redistribute it and/or modify |
| | 8 | # it under the terms of the GNU General Public License as published by |
| | 9 | # the Free Software Foundation, either version 3 of the License, or |
| | 10 | # (at your option) any later version. |
| | 11 | # |
| | 12 | # This program is distributed in the hope that it will be useful, |
| | 13 | # but WITHOUT ANY WARRANTY; without even the implied warranty of |
| | 14 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| | 15 | # GNU General Public License for more details. |
| | 16 | # |
| | 17 | # You should have received a copy of the GNU General Public License |
| | 18 | # along with this program. If not, see <http://www.gnu.org/licenses/>. |
| | 19 | |
| | 20 | =head1 NAME |
| | 21 | |
| | 22 | bench.pl - perform benches on Bison parsers. |
| | 23 | |
| | 24 | =head1 SYNOPSIS |
| | 25 | |
| | 26 | ./bench.pl |
| | 27 | |
| | 28 | =head1 OPTIONS |
| | 29 | |
| | 30 | =over 4 |
| | 31 | |
| | 32 | =item B<-b>, B<--bench>=I<bench-name> |
| | 33 | |
| | 34 | Specify the set of benches to run. I<bench-name> should be one of: |
| | 35 | |
| | 36 | =over 4 |
| | 37 | |
| | 38 | =item I<fusion> |
| | 39 | |
| | 40 | Test F<lalr1.cc> with three stacks against F<lalr1-fusion.cc> which |
| | 41 | uses a single one. |
| | 42 | |
| | 43 | =item I<push> |
| | 44 | |
| | 45 | Test the push parser vs. the pull interface. Use the C parser. |
| | 46 | |
| | 47 | =item I<variant> |
| | 48 | |
| | 49 | Test the use of variants instead of union in the C++ parser. |
| | 50 | |
| | 51 | =back |
| | 52 | |
| | 53 | =item B<-c>, B<--cflags>=I<flags> |
| | 54 | |
| | 55 | Flags to pass to the C or C++ compiler. Defaults to -O2. |
| | 56 | |
| | 57 | =item B<-h>, B<--help> |
| | 58 | |
| | 59 | Display this message and exit succesfully. The more verbose, the more |
| | 60 | details. |
| | 61 | |
| | 62 | =item B<-i>, B<--iterations>=I<integer> |
| | 63 | |
| | 64 | Say how many times a single test of the bench must be run. If |
| | 65 | negative, specify the minimum number of CPU seconds to run. Defaults |
| | 66 | to -1. |
| | 67 | |
| | 68 | =item B<-q>, B<--quiet> |
| | 69 | |
| | 70 | Decrease the verbosity level (defaults to 1). |
| | 71 | |
| | 72 | =item B<-v>, B<--verbose> |
| | 73 | |
| | 74 | Raise the verbosity level (defaults to 1). |
| | 75 | |
| | 76 | =back |
| | 77 | |
| | 78 | =cut |
| | 79 | |
| | 80 | use IO::File; |
| | 81 | |
| | 82 | ################################################################## |
| | 83 | |
| | 84 | =head1 VARIABLES |
| | 85 | |
| | 86 | =over 4 |
| | 87 | |
| | 88 | =item C<$bison> |
| | 89 | |
| | 90 | The Bison program to use to compile the grammar. |
| | 91 | |
| | 92 | =item C<$cc> |
| | 93 | |
| | 94 | The C compiler. |
| | 95 | |
| | 96 | =item C<$cxx> |
| | 97 | |
| | 98 | The C++ compiler. |
| | 99 | |
| | 100 | =item C<$cflags> |
| | 101 | |
| | 102 | Compiler flags (C or C++). |
| | 103 | |
| | 104 | =item C<$iterations> |
| | 105 | |
| | 106 | The number of times the parser is run for a bench. |
| | 107 | |
| | 108 | =item C<$verbose> |
| | 109 | |
| | 110 | Verbosity level. |
| | 111 | |
| | 112 | =back |
| | 113 | |
| | 114 | =cut |
| | 115 | |
| | 116 | my $bison = $ENV{'BISON'} || '@abs_top_builddir@/tests/bison'; |
| | 117 | my $cc = $ENV{'CC'} || 'gcc'; |
| | 118 | my $cxx = $ENV{'CXX'} || 'g++'; |
| | 119 | my $cflags = '-O2'; |
| | 120 | my $iterations = -1; |
| | 121 | my $verbose = 1; |
| | 122 | |
| | 123 | =head1 FUNCTIONS |
| | 124 | |
| | 125 | =over 4 |
| | 126 | |
| | 127 | =item C<verbose($level, $message)> |
| | 128 | |
| | 129 | Report the C<$message> is C<$level> E<lt>= C<$verbose>. |
| | 130 | |
| | 131 | =cut |
| | 132 | |
| | 133 | sub verbose($$) |
| | 134 | { |
| | 135 | my ($level, $message) = @_; |
| | 136 | print STDERR $message |
| | 137 | if $level <= $verbose; |
| | 138 | } |
| | 139 | |
| | 140 | =item C<directives($bench, @directive)> |
| | 141 | |
| | 142 | Format the list of directives for Bison for bench named C<$bench>. |
| | 143 | |
| | 144 | The special fake C<%variant> directive requests the use of |
| | 145 | Boost.Variants instead of a regular union. So don't pass it, it is |
| | 146 | not a valid directive. |
| | 147 | |
| | 148 | =cut |
| | 149 | |
| | 150 | sub directives($@) |
| | 151 | { |
| | 152 | my ($bench, @directive) = @_; |
| | 153 | my $res = "/* Directives for bench `$bench'. */\n"; |
| | 154 | for my $d (@directive) |
| | 155 | { |
| | 156 | $res .= $d . "\n" |
| | 157 | unless $d eq '%variant'; |
| | 158 | } |
| | 159 | $res .= "/* End of directives for bench `$bench'. */\n"; |
| | 160 | return $res; |
| | 161 | } |
| | 162 | |
| | 163 | =item C<triangular_grammar ($base, $max, @directive)> |
| | 164 | |
| | 165 | Create a large triangular grammar which looks like : |
| | 166 | |
| | 167 | input: |
| | 168 | exp { if ($1 != 0) abort (); $$ = $1; } |
| | 169 | | input exp { if ($2 != $1 + 1) abort (); $$ = $2; } |
| | 170 | ; |
| | 171 | |
| | 172 | exp: |
| | 173 | END { $$ = 0; } |
| | 174 | | "1" END { $$ = 1; } |
| | 175 | | "1" "2" END { $$ = 2; } |
| | 176 | | "1" "2" "3" END { $$ = 3; } |
| | 177 | | "1" "2" "3" "4" END { $$ = 4; } |
| | 178 | | "1" "2" "3" "4" "5" END { $$ = 5; } |
| | 179 | ; |
| | 180 | |
| | 181 | C<$base> is the base name for the file to create (F<$base.y>). |
| | 182 | C<$max> is the number of such rules (here, 5). You may pass |
| | 183 | additional Bison C<@directive>. |
| | 184 | |
| | 185 | The created parser is self contained: it includes its scanner, and |
| | 186 | source of input. |
| | 187 | =cut |
| | 188 | |
| | 189 | sub triangular_grammar ($$$) |
| | 190 | { |
| | 191 | my ($base, $max, @directive) = @_; |
| | 192 | my $directives = directives ($base, @directive); |
| | 193 | |
| | 194 | my $out = new IO::File ">$base.y" |
| | 195 | or die; |
| | 196 | print $out <<EOF; |
| | 197 | %error-verbose |
| | 198 | %debug |
| | 199 | %{ |
| | 200 | #include <stdio.h> |
| | 201 | #include <stdlib.h> |
| | 202 | |
| | 203 | static int yylex (void); |
| | 204 | static void yyerror (const char *msg); |
| | 205 | %} |
| | 206 | $directives |
| | 207 | %union |
| | 208 | { |
| | 209 | int val; |
| | 210 | }; |
| | 211 | |
| | 212 | %token END "end" |
| | 213 | %type <val> exp input |
| | 214 | EOF |
| | 215 | |
| | 216 | for my $size (1 .. $max) |
| | 217 | { |
| | 218 | print $out "%token t$size $size \"$size\"\n"; |
| | 219 | }; |
| | 220 | |
| | 221 | print $out <<EOF; |
| | 222 | %% |
| | 223 | input: |
| | 224 | exp { if (\$1 != 0) abort (); \$\$ = \$1; } |
| | 225 | | input exp { if (\$2 != \$1 + 1) abort (); \$\$ = \$2; } |
| | 226 | ; |
| | 227 | |
| | 228 | exp: |
| | 229 | END |
| | 230 | { \$\$ = 0; } |
| | 231 | EOF |
| | 232 | |
| | 233 | for my $size (1 .. $max) |
| | 234 | { |
| | 235 | use Text::Wrap; |
| | 236 | print $out wrap ("| ", " ", |
| | 237 | (map { "\"$_\"" } (1 .. $size)), |
| | 238 | " END \n"), |
| | 239 | " { \$\$ = $size; }\n"; |
| | 240 | }; |
| | 241 | print $out ";\n"; |
| | 242 | |
| | 243 | print $out <<EOF; |
| | 244 | %% |
| | 245 | static int |
| | 246 | yylex (void) |
| | 247 | { |
| | 248 | static int inner = 1; |
| | 249 | static int outer = 0; |
| | 250 | if (outer > $max) |
| | 251 | return 0; |
| | 252 | else if (inner > outer) |
| | 253 | { |
| | 254 | inner = 1; |
| | 255 | ++outer; |
| | 256 | return END; |
| | 257 | } |
| | 258 | return inner++; |
| | 259 | } |
| | 260 | |
| | 261 | static void |
| | 262 | yyerror (const char *msg) |
| | 263 | { |
| | 264 | fprintf (stderr, "%s\\n", msg); |
| | 265 | } |
| | 266 | |
| | 267 | int |
| | 268 | main (void) |
| | 269 | { |
| | 270 | yydebug = !!getenv ("YYDEBUG"); |
| | 271 | return yyparse (); |
| | 272 | } |
| | 273 | EOF |
| | 274 | } |
| | 275 | |
| | 276 | ################################################################## |
| | 277 | |
| | 278 | =item C<calc_input ($base, $max)> |
| | 279 | |
| | 280 | Generate the input file F<$base.input> for the calc parser. The input |
| | 281 | is composed of two expressions. The first one is using left recursion |
| | 282 | only and consumes no stack. The second one requires a deep stack. |
| | 283 | These two expressions are repeated C<$max> times in the output file. |
| | 284 | |
| | 285 | =cut |
| | 286 | |
| | 287 | sub calc_input ($$) |
| | 288 | { |
| | 289 | my ($base, $max) = @_; |
| | 290 | my $out = new IO::File ">$base.input" |
| | 291 | or die; |
| | 292 | foreach (1 .. $max) |
| | 293 | { |
| | 294 | print $out "0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99\n"; |
| | 295 | print $out "1+1*(2+2*(3+3*(4+4*(5+5*(6+6*(7+7*(8+8*(9+9*(10+10*(11+11*(12+12*(13+13*(14+14*(15+15*(16+16*(17+17*(18+18*(19+19*(20+20*(21+21*(22+22*(23+23*(24+24*(25+25*(26+26*(27+27*(28+28*(29+29*(30+30*(31+31*(32+32*(33+33*(34+34*(35+35*(36+36*(37+37*(38+38*(39+39*(40+40*(41+41*(42+42*(43+43*(44+44*(45+45*(46+46*(47+47*(48+48*(49+49*(50+50*(51+51*(52+52*(53+53*(54+54*(55+55*(56+56*(57+57*(58+58*(59+59*(60+60*(61+61*(62+62*(63+63*(64+64*(65+65*(66+66*(67+67*(68+68*(69+69*(70+70*(71+71*(72+72*(73+73*(74+74*(75+75*(76+76*(77+77*(78+78*(79+79*(80+80*(81+81*(82+82*(83+83*(84+84*(85+85*(86+86*(87+87*(88+88*(89+89*(90+90*(91+91*(92+92*(93+93*(94+94*(95+95*(96+96*(97+97*(98+98*(99+99*(100+100*(101+101*(102+102*(103+103*(104+104*(105+105*(106+106*(107+107*(108+108*(109+109*(110+110*(111+111*(112+112*(113+113*(114+114*(115+115*(116+116*(117+117*(118+118*(119+119*(120+120*(121+121*(122+122*(123+123*(124+124*(125+125*(126+126*(127+127*(128+128*(129+129*(130+130*(131+131*(132+132*(133+133*(134+134*(135+135*(136+136*(137+137*(138+138*(139+139*(140+140*(141+141*(142+142*(143+143*(144+144*(145+145*(146+146*(147+147*(148+148*(149+149*(150+150*(151+151*(152+152*(153+153*(154+154*(155+155*(156+156*(157+157*(158+158*(159+159*(160+160*(161+161*(162+162*(163+163*(164+164*(165+165*(166+166*(167+167*(168+168*(169+169*(170+170*(171+171*(172+172*(173+173*(174+174*(175+175*(176+176*(177+177*(178+178*(179+179*(180+180*(181+181*(182+182*(183+183*(184+184*(185+185*(186+186*(187+187*(188+188*(189+189*(190+190*(191+191*(192+192*(193+193*(194+194*(195+195*(196+196*(197+197*(198+198*(199+199*(200+200*(201+201*(202+202*(203+203*(204+204*(205+205*(206+206*(207+207*(208+208*(209+209*(210+210*(211+211*(212+212*(213+213*(214+214*(215+215*(216+216*(217+217*(218+218*(219+219*(220+220*(221+221*(222+222*(223+223*(224+224*(225+225*(226+226*(227+227*(228+228*(229+229*(230+230*(231+231*(232+232*(233+233*(234+234*(235+235*(236+236*(237+237*(238+238*(239+239*(240+240*(241+241*(242+242*(243+243*(244+244*(245+245*(246+246*(247+247*(248+248*(249+249*(250+250*(251+251*(252+252*(253+253*(254+254*(255+255*(256+256*(257+257*(258+258*(259+259*(260+260*(261+261*(262+262*(263+263*(264+264*(265+265*(266+266*(267+267*(268+268*(269+269*(270+270*(271+271*(272+272*(273+273*(274+274*(275+275*(276+276*(277+277*(278+278*(279+279*(280+280*(281+281*(282+282*(283+283*(284+284*(285+285*(286+286*(287+287*(288+288*(289+289*(290+290*(291+291*(292+292*(293+293*(294+294*(295+295*(296+296*(297+297*(298+298*(299+299*(300+300*(301+301*(302+302*(303+303*(304+304*(305+305*(306+306*(307+307*(308+308*(309+309*(310+310*(311+311*(312+312*(313+313*(314+314*(315+315*(316+316*(317+317*(318+318*(319+319*(320+320*(321+321*(322+322*(323+323*(324+324*(325+325*(326+326*(327+327*(328+328*(329+329*(330+330*(331+331*(332+332*(333+333*(334+334*(335+335*(336+336*(337+337*(338+338*(339+339*(340+340*(341+341*(342+342*(343+343*(344+344*(345+345*(346+346*(347+347*(348+348*(349+349*(350+350*(351+351*(352+352*(353+353*(354+354*(355+355*(356+356*(357+357*(358+358*(359+359*(360+360*(361+361*(362+362*(363+363*(364+364*(365+365*(366+366*(367+367*(368+368*(369+369*(370+370*(371+371*(372+372*(373+373*(374+374*(375+375*(376+376*(377+377*(378+378*(379+379*(380+380*(381+381*(382+382*(383+383*(384+384*(385+385*(386+386*(387+387*(388+388*(389+389*(390+390*(391+391*(392+392*(393+393*(394+394*(395+395*(396+396*(397+397*(398+398*(399+399*(400+400*(401+401*(402+402*(403+403*(404+404*(405+405*(406+406*(407+407*(408+408*(409+409*(410+410*(411+411*(412+412*(413+413*(414+414*(415+415*(416+416*(417+417*(418+418*(419+419*(420+420*(421+421*(422+422*(423+423*(424+424*(425+425*(426+426*(427+427*(428+428*(429+429*(430+430*(431+431*(432+432*(433+433*(434+434*(435+435*(436+436*(437+437*(438+438*(439+439*(440+440*(441+441*(442+442*(443+443*(444+444*(445+445*(446+446*(447+447*(448+448*(449+449*(450+450*(451+451*(452+452*(453+453*(454+454*(455+455*(456+456*(457+457*(458+458*(459+459*(460+460*(461+461*(462+462*(463+463*(464+464*(465+465*(466+466*(467+467*(468+468*(469+469*(470+470*(471+471*(472+472*(473+473*(474+474*(475+475*(476+476*(477+477*(478+478*(479+479*(480+480*(481+481*(482+482*(483+483*(484+484*(485+485*(486+486*(487+487*(488+488*(489+489*(490+490*(491+491*(492+492*(493+493*(494+494*(495+495*(496+496*(497+497*(498+498*(499+499*(500+500*(501+501*(502+502*(503+503*(504+504*(505+505*(506+506*(507+507*(508+508*(509+509*(510+510*(511+511*(512+512*(513+513*(514+514*(515+515*(516+516*(517+517*(518+518*(519+519*(520+520*(521+521*(522+522*(523+523*(524+524*(525+525*(526+526*(527+527*(528+528*(529+529*(530+530*(531+531*(532+532*(533+533*(534+534*(535+535*(536+536*(537+537*(538+538*(539+539*(540+540*(541+541*(542+542*(543+543*(544+544*(545+545*(546+546*(547+547*(548+548*(549+549*(550+550*(551+551*(552+552*(553+553*(554+554*(555+555*(556+556*(557+557*(558+558*(559+559*(560+560*(561+561*(562+562*(563+563*(564+564*(565+565*(566+566*(567+567*(568+568*(569+569*(570+570*(571+571*(572+572*(573+573*(574+574*(575+575*(576+576*(577+577*(578+578*(579+579*(580+580*(581+581*(582+582*(583+583*(584+584*(585+585*(586+586*(587+587*(588+588*(589+589*(590+590*(591+591*(592+592*(593+593*(594+594*(595+595*(596+596*(597+597*(598+598*(599+599*(600+600*(601+601*(602+602*(603+603*(604+604*(605+605*(606+606*(607+607*(608+608*(609+609*(610+610*(611+611*(612+612*(613+613*(614+614*(615+615*(616+616*(617+617*(618+618*(619+619*(620+620*(621+621*(622+622*(623+623*(624+624*(625+625*(626+626*(627+627*(628+628*(629+629*(630+630*(631+631*(632+632*(633+633*(634+634*(635+635*(636+636*(637+637*(638+638*(639+639*(640+640*(641+641*(642+642*(643+643*(644+644*(645+645*(646+646*(647+647*(648+648*(649+649*(650+650*(651+651*(652+652*(653+653*(654+654*(655+655*(656+656*(657+657*(658+658*(659+659*(660+660*(661+661*(662+662*(663+663*(664+664*(665+665*(666+666*(667+667*(668+668*(669+669*(670+670*(671+671*(672+672*(673+673*(674+674*(675+675*(676+676*(677+677*(678+678*(679+679*(680+680*(681+681*(682+682*(683+683*(684+684*(685+685*(686+686*(687+687*(688+688*(689+689*(690+690*(691+691*(692+692*(693+693*(694+694*(695+695*(696+696*(697+697*(698+698*(699+699*(700+700*(701+701*(702+702*(703+703*(704+704*(705+705*(706+706*(707+707*(708+708*(709+709*(710+710*(711+711*(712+712*(713+713*(714+714*(715+715*(716+716*(717+717*(718+718*(719+719*(720+720*(721+721*(722+722*(723+723*(724+724*(725+725*(726+726*(727+727*(728+728*(729+729*(730+730*(731+731*(732+732*(733+733*(734+734*(735+735*(736+736*(737+737*(738+738*(739+739*(740+740*(741+741*(742+742*(743+743*(744+744*(745+745*(746+746*(747+747*(748+748*(749+749*(750+750*(751+751*(752+752*(753+753*(754+754*(755+755*(756+756*(757+757*(758+758*(759+759*(760+760*(761+761*(762+762*(763+763*(764+764*(765+765*(766+766*(767+767*(768+768*(769+769*(770+770*(771+771*(772+772*(773+773*(774+774*(775+775*(776+776*(777+777*(778+778*(779+779*(780+780*(781+781*(782+782*(783+783*(784+784*(785+785*(786+786*(787+787*(788+788*(789+789*(790+790*(791+791*(792+792*(793+793*(794+794*(795+795*(796+796*(797+797*(798+798*(799+799*(800+800*(801+801*(802+802*(803+803*(804+804*(805+805*(806+806*(807+807*(808+808*(809+809*(810+810*(811+811*(812+812*(813+813*(814+814*(815+815*(816+816*(817+817*(818+818*(819+819*(820+820*(821+821*(822+822*(823+823*(824+824*(825+825*(826+826*(827+827*(828+828*(829+829*(830+830*(831+831*(832+832*(833+833*(834+834*(835+835*(836+836*(837+837*(838+838*(839+839*(840+840*(841+841*(842+842*(843+843*(844+844*(845+845*(846+846*(847+847*(848+848*(849+849*(850+850*(851+851*(852+852*(853+853*(854+854*(855+855*(856+856*(857+857*(858+858*(859+859*(860+860*(861+861*(862+862*(863+863*(864+864*(865+865*(866+866*(867+867*(868+868*(869+869*(870+870*(871+871*(872+872*(873+873*(874+874*(875+875*(876+876*(877+877*(878+878*(879+879*(880+880*(881+881*(882+882*(883+883*(884+884*(885+885*(886+886*(887+887*(888+888*(889+889*(890+890*(891+891*(892+892*(893+893*(894+894*(895+895*(896+896*(897+897*(898+898*(899+899*(900+900*(901+901*(902+902*(903+903*(904+904*(905+905*(906+906*(907+907*(908+908*(909+909*(910+910*(911+911*(912+912*(913+913*(914+914*(915+915*(916+916*(917+917*(918+918*(919+919*(920+920*(921+921*(922+922*(923+923*(924+924*(925+925*(926+926*(927+927*(928+928*(929+929*(930+930*(931+931*(932+932*(933+933*(934+934*(935+935*(936+936*(937+937*(938+938*(939+939*(940+940*(941+941*(942+942*(943+943*(944+944*(945+945*(946+946*(947+947*(948+948*(949+949*(950+950*(951+951*(952+952*(953+953*(954+954*(955+955*(956+956*(957+957*(958+958*(959+959*(960+960*(961+961*(962+962*(963+963*(964+964*(965+965*(966+966*(967+967*(968+968*(969+969*(970+970*(971+971*(972+972*(973+973*(974+974*(975+975*(976+976*(977+977*(978+978*(979+979*(980+980*(981+981*(982+982*(983+983*(984+984*(985+985*(986+986*(987+987*(988+988*(989+989*(990+990*(991+991*(992+992*(993+993*(994+994*(995+995*(996+996*(997+997*(998+998*(999+999*(1000+1000*(1001))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))\n"; |
| | 296 | } |
| | 297 | } |
| | 298 | |
| | 299 | ################################################################## |
| | 300 | =item C<calc_grammar ($base, $max, @directive)> |
| | 301 | |
| | 302 | Generate a Bison file F<$base.y> for a calculator parser in C. Pass |
| | 303 | the additional Bison C<@directive>. C<$max> is ignored, but left to |
| | 304 | have the same interface as C<triangular_grammar>. |
| | 305 | |
| | 306 | =cut |
| | 307 | |
| | 308 | sub calc_grammar ($$$) |
| | 309 | { |
| | 310 | my ($base, $max, @directive) = @_; |
| | 311 | my $directives = directives ($base, @directive); |
| | 312 | |
| | 313 | my $out = new IO::File ">$base.y" |
| | 314 | or die; |
| | 315 | print $out <<EOF; |
| | 316 | %{ |
| | 317 | #include <stdio.h> |
| | 318 | |
| | 319 | #include <stdlib.h> |
| | 320 | #include <string.h> |
| | 321 | #include <ctype.h> |
| | 322 | #define USE(Var) |
| | 323 | |
| | 324 | /* Exercise pre-prologue dependency to %union. */ |
| | 325 | typedef int semantic_value; |
| | 326 | |
| | 327 | static semantic_value global_result = 0; |
| | 328 | static int global_count = 0; |
| | 329 | %} |
| | 330 | |
| | 331 | $directives |
| | 332 | %error-verbose |
| | 333 | /* Exercise %union. */ |
| | 334 | %union |
| | 335 | { |
| | 336 | semantic_value ival; |
| | 337 | }; |
| | 338 | |
| | 339 | %{ |
| | 340 | static int power (int base, int exponent); |
| | 341 | /* yyerror receives the location if: |
| | 342 | - %location & %pure & %glr |
| | 343 | - %location & %pure & %yacc & %parse-param. */ |
| | 344 | static void yyerror (const char *s); |
| | 345 | #if YYPURE |
| | 346 | static int yylex (YYSTYPE* yylvalp); |
| | 347 | #else |
| | 348 | static int yylex (void); |
| | 349 | #endif |
| | 350 | %} |
| | 351 | |
| | 352 | /* Bison Declarations */ |
| | 353 | %token CALC_EOF 0 "end of input" |
| | 354 | %token <ival> NUM "number" |
| | 355 | %type <ival> exp |
| | 356 | |
| | 357 | %nonassoc '=' /* comparison */ |
| | 358 | %left '-' '+' |
| | 359 | %left '*' '/' |
| | 360 | %left NEG /* negation--unary minus */ |
| | 361 | %right '^' /* exponentiation */ |
| | 362 | |
| | 363 | /* Grammar follows */ |
| | 364 | %% |
| | 365 | input: |
| | 366 | line |
| | 367 | | input line |
| | 368 | ; |
| | 369 | |
| | 370 | line: |
| | 371 | '\\n' |
| | 372 | | exp '\\n' { USE (\$1); } |
| | 373 | ; |
| | 374 | |
| | 375 | exp: |
| | 376 | NUM { \$\$ = \$1; } |
| | 377 | | exp '=' exp |
| | 378 | { |
| | 379 | if (\$1 != \$3) |
| | 380 | fprintf (stderr, "calc: error: %d != %d\\n", \$1, \$3); |
| | 381 | \$\$ = \$1; |
| | 382 | } |
| | 383 | | exp '+' exp { \$\$ = \$1 + \$3; } |
| | 384 | | exp '-' exp { \$\$ = \$1 - \$3; } |
| | 385 | | exp '*' exp { \$\$ = \$1 * \$3; } |
| | 386 | | exp '/' exp { \$\$ = \$1 / \$3; } |
| | 387 | | '-' exp %prec NEG { \$\$ = -\$2; } |
| | 388 | | exp '^' exp { \$\$ = power (\$1, \$3); } |
| | 389 | | '(' exp ')' { \$\$ = \$2; } |
| | 390 | | '(' error ')' { \$\$ = 1111; } |
| | 391 | | '!' { \$\$ = 0; YYERROR; } |
| | 392 | | '-' error { \$\$ = 0; YYERROR; } |
| | 393 | ; |
| | 394 | %% |
| | 395 | /* The input. */ |
| | 396 | static FILE *input; |
| | 397 | |
| | 398 | static void |
| | 399 | yyerror (const char *s) |
| | 400 | { |
| | 401 | fprintf (stderr, "%s\\n", s); |
| | 402 | } |
| | 403 | |
| | 404 | static int |
| | 405 | get_char (void) |
| | 406 | { |
| | 407 | return getc (input); |
| | 408 | } |
| | 409 | |
| | 410 | |
| | 411 | static void |
| | 412 | unget_char ( int c) |
| | 413 | { |
| | 414 | ungetc (c, input); |
| | 415 | } |
| | 416 | |
| | 417 | static int |
| | 418 | read_signed_integer (void) |
| | 419 | { |
| | 420 | int c = get_char (); |
| | 421 | int sign = 1; |
| | 422 | int n = 0; |
| | 423 | |
| | 424 | if (c == '-') |
| | 425 | { |
| | 426 | c = get_char (); |
| | 427 | sign = -1; |
| | 428 | } |
| | 429 | |
| | 430 | while (isdigit (c)) |
| | 431 | { |
| | 432 | n = 10 * n + (c - '0'); |
| | 433 | c = get_char (); |
| | 434 | } |
| | 435 | |
| | 436 | unget_char (c); |
| | 437 | |
| | 438 | return sign * n; |
| | 439 | } |
| | 440 | |
| | 441 | static int |
| | 442 | #if YYPURE |
| | 443 | # define yylval (*yylvalp) |
| | 444 | yylex (YYSTYPE* yylvalp) |
| | 445 | #else |
| | 446 | yylex (void) |
| | 447 | #endif |
| | 448 | { |
| | 449 | int c; |
| | 450 | |
| | 451 | /* Skip white space. */ |
| | 452 | while ((c = get_char ()) == ' ' || c == '\t') |
| | 453 | continue; |
| | 454 | |
| | 455 | /* process numbers */ |
| | 456 | if (c == '.' || isdigit (c)) |
| | 457 | { |
| | 458 | unget_char ( c); |
| | 459 | yylval.ival = read_signed_integer (); |
| | 460 | return NUM; |
| | 461 | } |
| | 462 | |
| | 463 | /* Return end-of-file. */ |
| | 464 | if (c == EOF) |
| | 465 | return CALC_EOF; |
| | 466 | |
| | 467 | /* Return single chars. */ |
| | 468 | return c; |
| | 469 | } |
| | 470 | |
| | 471 | static int |
| | 472 | power (int base, int exponent) |
| | 473 | { |
| | 474 | int res = 1; |
| | 475 | if (exponent < 0) |
| | 476 | exit (3); |
| | 477 | for (/* Niente */; exponent; --exponent) |
| | 478 | res *= base; |
| | 479 | return res; |
| | 480 | } |
| | 481 | |
| | 482 | |
| | 483 | int |
| | 484 | main (int argc, const char **argv) |
| | 485 | { |
| | 486 | semantic_value result = 0; |
| | 487 | int count = 0; |
| | 488 | int status; |
| | 489 | |
| | 490 | input = fopen ("calc.input", "r"); |
| | 491 | if (!input) |
| | 492 | { |
| | 493 | perror ("calc.input"); |
| | 494 | return 3; |
| | 495 | } |
| | 496 | |
| | 497 | status = yyparse (); |
| | 498 | if (global_result != result) |
| | 499 | abort (); |
| | 500 | if (global_count != count) |
| | 501 | abort (); |
| | 502 | |
| | 503 | return status; |
| | 504 | } |
| | 505 | EOF |
| | 506 | } |
| | 507 | |
| | 508 | ################################################################## |
| | 509 | |
| | 510 | =item C<variant_grammar ($base, $max, @directive)> |
| | 511 | |
| | 512 | Generate a Bison file F<$base.y> that uses, or not, the Boost.Variants |
| | 513 | depending on the C<@directive>. |
| | 514 | |
| | 515 | =cut |
| | 516 | |
| | 517 | sub variant_grammar ($$$) |
| | 518 | { |
| | 519 | my ($base, $max, @directive) = @_; |
| | 520 | my $directives = directives ($base, @directive); |
| | 521 | my $variant = grep { $_ eq '%variant' } @directive; |
| | 522 | |
| | 523 | my $out = new IO::File ">$base.y" |
| | 524 | or die; |
| | 525 | print $out <<EOF; |
| | 526 | %language "C++" |
| | 527 | %defines |
| | 528 | $directives |
| | 529 | |
| | 530 | %code requires // variant.h |
| | 531 | { |
| | 532 | #include <string> |
| | 533 | } |
| | 534 | |
| | 535 | %code // variant.c |
| | 536 | { |
| | 537 | #include <algorithm> |
| | 538 | #include <iostream> |
| | 539 | #include <sstream> |
| | 540 | |
| | 541 | // Prototype of the yylex function providing subsequent tokens. |
| | 542 | static yy::parser::token_type yylex(yy::parser::semantic_type* yylval); |
| | 543 | |
| | 544 | #define STAGE_MAX ($max * 10) |
| | 545 | #define USE_VARIANTS $variant |
| | 546 | #if USE_VARIANTS |
| | 547 | # define IF_VARIANTS(True, False) True |
| | 548 | #else |
| | 549 | # define IF_VARIANTS(True, False) False |
| | 550 | #endif |
| | 551 | } |
| | 552 | EOF |
| | 553 | |
| | 554 | if ($variant) |
| | 555 | { |
| | 556 | print $out <<'EOF'; |
| | 557 | %code variant {int,std::string} |
| | 558 | %token <std::string> TEXT |
| | 559 | %token <int> NUMBER |
| | 560 | %printer { std::cerr << "Number: " << $$; } <int> |
| | 561 | %printer { std::cerr << "Text: " << $$; } <std::string> |
| | 562 | %token END_OF_FILE 0 |
| | 563 | %type <std::string> text result |
| | 564 | |
| | 565 | %% |
| | 566 | result: |
| | 567 | text { /* Throw away the result. */ } |
| | 568 | ; |
| | 569 | |
| | 570 | text: |
| | 571 | /* nothing */ { /* This will generate an empty string */ } |
| | 572 | | text TEXT { std::swap($$,$1); $$.append($2); } |
| | 573 | | text NUMBER { |
| | 574 | std::swap($$,$1); |
| | 575 | std::ostringstream ss; |
| | 576 | ss << ' ' << $2; |
| | 577 | $$.append(ss.str()); |
| | 578 | } |
| | 579 | ; |
| | 580 | EOF |
| | 581 | } |
| | 582 | else |
| | 583 | { |
| | 584 | # Not using Boost variants. |
| | 585 | print $out <<'EOF'; |
| | 586 | %union {int ival; std::string* sval;} |
| | 587 | %token <sval> TEXT |
| | 588 | %token <ival> NUMBER |
| | 589 | %printer { std::cerr << "Number: " << $$; } <ival> |
| | 590 | %printer { std::cerr << "Text: " << *$$; } <sval> |
| | 591 | %token END_OF_FILE 0 |
| | 592 | %type <sval> text result |
| | 593 | |
| | 594 | %% |
| | 595 | result: |
| | 596 | text { delete $1; } |
| | 597 | ; |
| | 598 | |
| | 599 | text: |
| | 600 | /* nothing */ { $$ = new std::string; } |
| | 601 | | text TEXT { $$->append(*$2); delete $2; } |
| | 602 | | text NUMBER { |
| | 603 | std::ostringstream ss; |
| | 604 | ss << ' ' << $2; |
| | 605 | $$->append(ss.str()); |
| | 606 | } |
| | 607 | ; |
| | 608 | EOF |
| | 609 | } |
| | 610 | |
| | 611 | print $out <<'EOF'; |
| | 612 | %% |
| | 613 | static |
| | 614 | yy::parser::token_type |
| | 615 | yylex(yy::parser::semantic_type* yylval) |
| | 616 | { |
| | 617 | static int stage = -1; |
| | 618 | ++stage; |
| | 619 | if (stage == STAGE_MAX) |
| | 620 | return yy::parser::token::END_OF_FILE; |
| | 621 | else if (stage % 2) |
| | 622 | { |
| | 623 | IF_VARIANTS(yylval->build<int>(), yylval->ival) = stage; |
| | 624 | return yy::parser::token::NUMBER; |
| | 625 | } |
| | 626 | else |
| | 627 | { |
| | 628 | IF_VARIANTS(yylval->build<std::string>() =, yylval->sval = new) std::string("A string."); |
| | 629 | return yy::parser::token::TEXT; |
| | 630 | } |
| | 631 | abort(); |
| | 632 | } |
| | 633 | |
| | 634 | // Mandatory error function |
| | 635 | void |
| | 636 | yy::parser::error(const yy::parser::location_type& yylloc, |
| | 637 | const std::string& message) |
| | 638 | { |
| | 639 | std::cerr << yylloc << ": " << message << std::endl; |
| | 640 | } |
| | 641 | |
| | 642 | int main(int argc, char *argv[]) |
| | 643 | { |
| | 644 | yy::parser p; |
| | 645 | #if YYDEBUG |
| | 646 | p.set_debug_level(!!getenv("YYDEBUG")); |
| | 647 | #endif |
| | 648 | p.parse(); |
| | 649 | return 0; |
| | 650 | } |
| | 651 | EOF |
| | 652 | } |
| | 653 | |
| | 654 | ################################################################## |
| | 655 | |
| | 656 | =item C<compile ($base)> |
| | 657 | |
| | 658 | Compile C<$base.y> to an executable C, Using the C or C++ compiler |
| | 659 | depending on the %language specification in C<$base.y>. |
| | 660 | |
| | 661 | =cut |
| | 662 | |
| | 663 | sub compile ($) |
| | 664 | { |
| | 665 | my ($base) = @_; |
| | 666 | my $language = `sed -ne '/%language "\\(.*\\)"/{s//\\1/;p;q;}' $base.y`; |
| | 667 | chomp $language; |
| | 668 | |
| | 669 | my $compiler = $language eq 'C++' ? $cxx : $cc; |
| | 670 | |
| | 671 | system ("$bison $base.y -o $base.c") == 0 |
| | 672 | or die; |
| | 673 | system ("$compiler -o $base $cflags $base.c") == 0 |
| | 674 | or die; |
| | 675 | } |
| | 676 | |
| | 677 | =item C<bench_grammar ($gram, %bench)> |
| | 678 | |
| | 679 | Generate benches for C<$gram>. C<$gram> should be C<calc> or |
| | 680 | C<triangle>. C<%bench> is a hash of the form: |
| | 681 | |
| | 682 | $name => @directive |
| | 683 | |
| | 684 | where C<$name> is the name of the bench, and C<@directive> are the |
| | 685 | Bison directive to use for this bench. All the benches are compared |
| | 686 | against each other, repeated 50 times. |
| | 687 | |
| | 688 | =cut |
| | 689 | |
| | 690 | sub bench_grammar ($%) |
| | 691 | { |
| | 692 | my ($gram, %test) = @_; |
| | 693 | |
| | 694 | use Benchmark qw (:all :hireswallclock); |
| | 695 | |
| | 696 | # Set up the benches as expected by timethese. |
| | 697 | my %bench; |
| | 698 | # For each bench, capture the size. |
| | 699 | my %size; |
| | 700 | while (my ($name, $directives) = each %test) |
| | 701 | { |
| | 702 | verbose 2, "Generating $name\n"; |
| | 703 | # Call the Bison input file generator. |
| | 704 | my $generator = "$gram" . "_grammar"; |
| | 705 | &$generator ($name, 200, @$directives); |
| | 706 | # Compile the executable. |
| | 707 | compile ($name); |
| | 708 | $bench{$name} = "system ('./$name');"; |
| | 709 | chop($size{$name} = `wc -c <$name`); |
| | 710 | } |
| | 711 | |
| | 712 | # Run the benches. |
| | 713 | # |
| | 714 | # STYLE can be any of 'all', 'none', 'noc', 'nop' or 'auto'. 'all' |
| | 715 | # shows each of the 5 times available ('wallclock' time, user time, |
| | 716 | # system time, user time of children, and system time of |
| | 717 | # children). 'noc' shows all except the two children times. 'nop' |
| | 718 | # shows only wallclock and the two children times. 'auto' (the |
| | 719 | # default) will act as 'all' unless the children times are both |
| | 720 | # zero, in which case it acts as 'noc'. 'none' prevents output. |
| | 721 | verbose 2, "Running the benches for $gram\n"; |
| | 722 | my $res = timethese ($iterations, \%bench, 'nop'); |
| | 723 | |
| | 724 | # Output the speed result. |
| | 725 | cmpthese ($res, 'nop'); |
| | 726 | |
| | 727 | # Display the sizes. |
| | 728 | print "Sizes (decreasing):\n"; |
| | 729 | my $width = 10; |
| | 730 | for my $bench (keys %size) |
| | 731 | { |
| | 732 | $width = length $bench |
| | 733 | if $width < length $bench; |
| | 734 | } |
| | 735 | # Benches sorted by decreasing size. |
| | 736 | my @benches_per_size = sort {$size{$b} <=> $size{$a}} keys %size; |
| | 737 | for my $bench (@benches_per_size) |
| | 738 | { |
| | 739 | printf "%${width}s: %5.2fkB\n", $bench, $size{$bench} / 1024; |
| | 740 | } |
| | 741 | } |
| | 742 | |
| | 743 | |
| | 744 | =item C<bench_push_parser ()> |
| | 745 | |
| | 746 | Bench the C push parser against the pull parser, pure and impure |
| | 747 | interfaces. |
| | 748 | |
| | 749 | =cut |
| | 750 | |
| | 751 | sub bench_push_parser () |
| | 752 | { |
| | 753 | calc_input ('calc', 200); |
| | 754 | bench_grammar |
| | 755 | ('calc', |
| | 756 | ( |
| | 757 | "pull-impure" => [], |
| | 758 | "pull-pure" => ['%define api.pure'], |
| | 759 | "push-impure" => ['%define api.push_pull "both"'], |
| | 760 | "push-pure" => ['%define api.push_pull "both"', '%define api.pure'], |
| | 761 | ) |
| | 762 | ); |
| | 763 | } |
| | 764 | |
| | 765 | =item C<bench_variant_parser ()> |
| | 766 | |
| | 767 | Bench the C++ lalr1.cc parser using Boost.Variants or %union. |
| | 768 | |
| | 769 | =cut |
| | 770 | |
| | 771 | sub bench_variant_parser () |
| | 772 | { |
| | 773 | bench_grammar |
| | 774 | ('variant', |
| | 775 | ( |
| | 776 | "f-union" => ['%skeleton "lalr1-fusion.cc"'], |
| | 777 | "f-uni-deb" => ['%skeleton "lalr1-fusion.cc"', '%debug'], |
| | 778 | "f-var" => ['%skeleton "lalr1-fusion.cc"', '%variant'], |
| | 779 | "f-var-deb" => ['%skeleton "lalr1-fusion.cc"', '%debug', '%variant'], |
| | 780 | "f-var-dtr" => ['%skeleton "lalr1-fusion.cc"', '%variant', "%code {\n#define VARIANT_DESTROY\n}"], |
| | 781 | "f-var-deb-dtr" => ['%skeleton "lalr1-fusion.cc"', '%debug', '%variant', "%code {\n#define VARIANT_DESTROY\n}"], |
| | 782 | ) |
| | 783 | ); |
| | 784 | } |
| | 785 | |
| | 786 | =item C<bench_fusion_parser ()> |
| | 787 | |
| | 788 | Bench the C++ lalr1.cc parser using Boost.Variants or %union. |
| | 789 | |
| | 790 | =cut |
| | 791 | |
| | 792 | sub bench_fusion_parser () |
| | 793 | { |
| | 794 | bench_grammar |
| | 795 | ('variant', |
| | 796 | ( |
| | 797 | "split" => [], |
| | 798 | "fused" => ['%skeleton "lalr1-fusion.cc"'], |
| | 799 | ) |
| | 800 | ); |
| | 801 | } |
| | 802 | |
| | 803 | ############################################################################ |
| | 804 | |
| | 805 | sub help ($) |
| | 806 | { |
| | 807 | my ($verbose) = @_; |
| | 808 | use Pod::Usage; |
| | 809 | # See <URL:http://perldoc.perl.org/pod2man.html#NOTES>. |
| | 810 | pod2usage( { -message => "Bench Bison parsers", |
| | 811 | -exitval => 0, |
| | 812 | -verbose => $verbose, |
| | 813 | -output => \*STDOUT }); |
| | 814 | } |
| | 815 | |
| | 816 | sub getopt () |
| | 817 | { |
| | 818 | use Getopt::Long; |
| | 819 | %option = ( |
| | 820 | "b|bench=s" => \$bench, |
| | 821 | "c|cflags=s" => \$cflags, |
| | 822 | "h|help" => sub { help ($verbose) }, |
| | 823 | "i|iterations=i" => \$iterations, |
| | 824 | "q|quiet" => sub { --$verbose }, |
| | 825 | "v|verbose" => sub { ++$verbose }, |
| | 826 | ); |
| | 827 | Getopt::Long::Configure ("bundling", "pass_through"); |
| | 828 | GetOptions (%option) |
| | 829 | or exit 1; |
| | 830 | } |
| | 831 | |
| | 832 | ###################################################################### |
| | 833 | |
| | 834 | getopt; |
| | 835 | verbose 1, "Using bison=$bison.\n"; |
| | 836 | verbose 1, "Using cc=$cc.\n"; |
| | 837 | verbose 1, "Using cxx=$cxx.\n"; |
| | 838 | verbose 1, "Using cflags=$cflags.\n"; |
| | 839 | |
| | 840 | bench_fusion_parser() if $bench eq "fusion"; |
| | 841 | bench_push_parser() if $bench eq "push"; |
| | 842 | bench_variant_parser() if $bench eq "variant"; |
| | 843 | |
| | 844 | ### Setup "GNU" style for perl-mode and cperl-mode. |
| | 845 | ## Local Variables: |
| | 846 | ## perl-indent-level: 2 |
| | 847 | ## perl-continued-statement-offset: 2 |
| | 848 | ## perl-continued-brace-offset: 0 |
| | 849 | ## perl-brace-offset: 0 |
| | 850 | ## perl-brace-imaginary-offset: 0 |
| | 851 | ## perl-label-offset: -2 |
| | 852 | ## cperl-indent-level: 2 |
| | 853 | ## cperl-brace-offset: 0 |
| | 854 | ## cperl-continued-brace-offset: 0 |
| | 855 | ## cperl-label-offset: -2 |
| | 856 | ## cperl-extra-newline-before-brace: t |
| | 857 | ## cperl-merge-trailing-else: nil |
| | 858 | ## cperl-continued-statement-offset: 2 |
| | 859 | ## End: |
projects / bison.git / blame_incremental