etc/bench.pl.in

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