1<?php 2/** 3 * PHP_ParserGenerator, a php 5 parser generator. 4 * 5 * This is a direct port of the Lemon parser generator, found at 6 * {@link http://www.hwaci.com/sw/lemon/} 7 * 8 * PHP version 5 9 * 10 * LICENSE: 11 * 12 * Copyright (c) 2006, Gregory Beaver <cellog@php.net> 13 * All rights reserved. 14 * 15 * Redistribution and use in source and binary forms, with or without 16 * modification, are permitted provided that the following conditions 17 * are met: 18 * 19 * * Redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer. 21 * * Redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in 23 * the documentation and/or other materials provided with the distribution. 24 * * Neither the name of the PHP_ParserGenerator nor the names of its 25 * contributors may be used to endorse or promote products derived 26 * from this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 29 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 30 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 31 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 32 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 36 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * @category php 41 * @package PHP_ParserGenerator 42 * @author Gregory Beaver <cellog@php.net> 43 * @copyright 2006 Gregory Beaver 44 * @license http://www.opensource.org/licenses/bsd-license.php New BSD License 45 * @version CVS: $Id: Data.php 302209 2010-08-14 14:32:56Z jespino $ 46 * @since File available since Release 0.1.0 47 */ 48/** 49/** 50 * The state vector for the entire parser generator is recorded in 51 * this class. 52 * 53 * @package PHP_ParserGenerator 54 * @author Gregory Beaver <cellog@php.net> 55 * @copyright 2006 Gregory Beaver 56 * @license http://www.opensource.org/licenses/bsd-license.php New BSD License 57 * @version @package_version@ 58 * @since Class available since Release 0.1.0 59 */ 60 61class PHP_ParserGenerator_Data 62{ 63 /** 64 * Used for terminal and non-terminal offsets into the action table 65 * when their default should be used instead 66 */ 67 const NO_OFFSET = -2147483647; 68 /** 69 * Table of states sorted by state number 70 * @var array array of {@link PHP_ParserGenerator_State} objects 71 */ 72 public $sorted; 73 /** 74 * List of all rules 75 * @var PHP_ParserGenerator_Rule 76 */ 77 public $rule; 78 /** 79 * Number of states 80 * @var int 81 */ 82 public $nstate; 83 /** 84 * Number of rules 85 * @var int 86 */ 87 public $nrule; 88 /** 89 * Number of terminal and nonterminal symbols 90 * @var int 91 */ 92 public $nsymbol; 93 /** 94 * Number of terminal symbols (tokens) 95 * @var int 96 */ 97 public $nterminal; 98 /** 99 * Sorted array of pointers to symbols 100 * @var array array of {@link PHP_ParserGenerator_Symbol} objects 101 */ 102 public $symbols = array(); 103 /** 104 * Number of errors 105 * @var int 106 */ 107 public $errorcnt; 108 /** 109 * The error symbol 110 * @var PHP_ParserGenerator_Symbol 111 */ 112 public $errsym; 113 /** 114 * Name of the generated parser 115 * @var string 116 */ 117 public $name; 118 /** 119 * Unused relic from the C version 120 * 121 * Type of terminal symbols in the parser stack 122 * @var string 123 */ 124 public $tokentype; 125 /** 126 * Unused relic from the C version 127 * 128 * The default type of non-terminal symbols 129 * @var string 130 */ 131 public $vartype; 132 /** 133 * Name of the start symbol for the grammar 134 * @var string 135 */ 136 public $start; 137 /** 138 * Size of the parser stack 139 * 140 * This is 100 by default, but is set with the %stack_size directive 141 * @var int 142 */ 143 public $stacksize; 144 /** 145 * Code to put at the start of the parser file 146 * 147 * This is set by the %include directive 148 * @var string 149 */ 150 public $include_code; 151 /** 152 * Line number for start of include code 153 * @var int 154 */ 155 public $includeln; 156 /** 157 * Code to put in the parser class 158 * 159 * This is set by the %include_class directive 160 * @var string 161 */ 162 public $include_classcode; 163 /** 164 * Line number for start of include code 165 * @var int 166 */ 167 public $include_classln; 168 /** 169 * any extends/implements code 170 * 171 * This is set by the %declare_class directive 172 * @var string 173 */ 174 /** 175 * Line number for class declaration code 176 * @var int 177 */ 178 public $declare_classcode; 179 /** 180 * Line number for start of class declaration code 181 * @var int 182 */ 183 public $declare_classln; 184 /** 185 * Code to execute when a syntax error is seen 186 * 187 * This is set by the %syntax_error directive 188 * @var string 189 */ 190 public $error; 191 /** 192 * Line number for start of error code 193 * @var int 194 */ 195 public $errorln; 196 /** 197 * Code to execute on a stack overflow 198 * 199 * This is set by the %stack_overflow directive 200 */ 201 public $overflow; 202 /** 203 * Line number for start of overflow code 204 * @var int 205 */ 206 public $overflowln; 207 /** 208 * Code to execute on parser failure 209 * 210 * This is set by the %parse_failure directive 211 * @var string 212 */ 213 public $failure; 214 /** 215 * Line number for start of failure code 216 * @var int 217 */ 218 public $failureln; 219 /** 220 * Code to execute when the parser acccepts (completes parsing) 221 * 222 * This is set by the %parse_accept directive 223 * @var string 224 */ 225 public $accept; 226 /** 227 * Line number for the start of accept code 228 * @var int 229 */ 230 public $acceptln; 231 /** 232 * Code appended to the generated file 233 * 234 * This is set by the %code directive 235 * @var string 236 */ 237 public $extracode; 238 /** 239 * Line number for the start of the extra code 240 * @var int 241 */ 242 public $extracodeln; 243 /** 244 * Code to execute to destroy token data 245 * 246 * This is set by the %token_destructor directive 247 * @var string 248 */ 249 public $tokendest; 250 /** 251 * Line number for token destroyer code 252 * @var int 253 */ 254 public $tokendestln; 255 /** 256 * Code for the default non-terminal destructor 257 * 258 * This is set by the %default_destructor directive 259 * @var string 260 */ 261 public $vardest; 262 /** 263 * Line number for default non-terminal destructor code 264 * @var int 265 */ 266 public $vardestln; 267 /** 268 * Name of the input file 269 * @var string 270 */ 271 public $filename; 272 /** 273 * Name of the input file without its extension 274 * @var string 275 */ 276 public $filenosuffix; 277 /** 278 * Name of the current output file 279 * @var string 280 */ 281 public $outname; 282 /** 283 * A prefix added to token names 284 * @var string 285 */ 286 public $tokenprefix; 287 /** 288 * Number of parsing conflicts 289 * @var int 290 */ 291 public $nconflict; 292 /** 293 * Size of the parse tables 294 * @var int 295 */ 296 public $tablesize; 297 /** 298 * Public only basis configurations 299 */ 300 public $basisflag; 301 /** 302 * True if any %fallback is seen in the grammer 303 * @var boolean 304 */ 305 public $has_fallback; 306 /** 307 * Name of the program 308 * @var string 309 */ 310 public $argv0; 311 312 /** 313 * Alternate parser template file 314 * @var string 315 */ 316 public $parser_template = ""; 317 318 /* Find a precedence symbol of every rule in the grammar. 319 * 320 * Those rules which have a precedence symbol coded in the input 321 * grammar using the "[symbol]" construct will already have the 322 * $rp->precsym field filled. Other rules take as their precedence 323 * symbol the first RHS symbol with a defined precedence. If there 324 * are not RHS symbols with a defined precedence, the precedence 325 * symbol field is left blank. 326 */ 327 function FindRulePrecedences() 328 { 329 for ($rp = $this->rule; $rp; $rp = $rp->next) { 330 if ($rp->precsym === 0) { 331 for ($i = 0; $i < $rp->nrhs && $rp->precsym === 0; $i++) { 332 $sp = $rp->rhs[$i]; 333 if ($sp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) { 334 for ($j = 0; $j < $sp->nsubsym; $j++) { 335 if ($sp->subsym[$j]->prec >= 0) { 336 $rp->precsym = $sp->subsym[$j]; 337 break; 338 } 339 } 340 } elseif ($sp->prec >= 0) { 341 $rp->precsym = $rp->rhs[$i]; 342 } 343 } 344 } 345 } 346 } 347 348 /** 349 * Find all nonterminals which will generate the empty string. 350 * Then go back and compute the first sets of every nonterminal. 351 * The first set is the set of all terminal symbols which can begin 352 * a string generated by that nonterminal. 353 */ 354 function FindFirstSets() 355 { 356 for ($i = 0; $i < $this->nsymbol; $i++) { 357 $this->symbols[$i]->lambda = false; 358 } 359 for($i = $this->nterminal; $i < $this->nsymbol; $i++) { 360 $this->symbols[$i]->firstset = array(); 361 } 362 363 /* First compute all lambdas */ 364 do{ 365 $progress = 0; 366 for ($rp = $this->rule; $rp; $rp = $rp->next) { 367 if ($rp->lhs->lambda) { 368 continue; 369 } 370 for ($i = 0; $i < $rp->nrhs; $i++) { 371 $sp = $rp->rhs[$i]; 372 if ($sp->type != PHP_ParserGenerator_Symbol::TERMINAL || $sp->lambda === false) { 373 break; 374 } 375 } 376 if ($i === $rp->nrhs) { 377 $rp->lhs->lambda = true; 378 $progress = 1; 379 } 380 } 381 } while ($progress); 382 383 /* Now compute all first sets */ 384 do { 385 $progress = 0; 386 for ($rp = $this->rule; $rp; $rp = $rp->next) { 387 $s1 = $rp->lhs; 388 for ($i = 0; $i < $rp->nrhs; $i++) { 389 $s2 = $rp->rhs[$i]; 390 if ($s2->type == PHP_ParserGenerator_Symbol::TERMINAL) { 391 //progress += SetAdd(s1->firstset,s2->index); 392 $progress += isset($s1->firstset[$s2->index]) ? 0 : 1; 393 $s1->firstset[$s2->index] = 1; 394 break; 395 } elseif ($s2->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) { 396 for ($j = 0; $j < $s2->nsubsym; $j++) { 397 //progress += SetAdd(s1->firstset,s2->subsym[j]->index); 398 $progress += isset($s1->firstset[$s2->subsym[$j]->index]) ? 0 : 1; 399 $s1->firstset[$s2->subsym[$j]->index] = 1; 400 } 401 break; 402 } elseif ($s1 === $s2) { 403 if ($s1->lambda === false) { 404 break; 405 } 406 } else { 407 //progress += SetUnion(s1->firstset,s2->firstset); 408 $test = array_diff_key($s2->firstset, $s1->firstset); 409 if (count($test)) { 410 $progress++; 411 $s1->firstset += $test; 412 } 413 if ($s2->lambda === false) { 414 break; 415 } 416 } 417 } 418 } 419 } while ($progress); 420 } 421 422 /** 423 * Compute all LR(0) states for the grammar. Links 424 * are added to between some states so that the LR(1) follow sets 425 * can be computed later. 426 */ 427 function FindStates() 428 { 429 PHP_ParserGenerator_Config::Configlist_init(); 430 431 /* Find the start symbol */ 432 if ($this->start) { 433 $sp = PHP_ParserGenerator_Symbol::Symbol_find($this->start); 434 if ($sp == 0) { 435 PHP_ParserGenerator::ErrorMsg($this->filename, 0, 436 "The specified start symbol \"%s\" is not " . 437 "in a nonterminal of the grammar. \"%s\" will be used as the start " . 438 "symbol instead.", $this->start, $this->rule->lhs->name); 439 $this->errorcnt++; 440 $sp = $this->rule->lhs; 441 } 442 } else { 443 $sp = $this->rule->lhs; 444 } 445 446 /* Make sure the start symbol doesn't occur on the right-hand side of 447 ** any rule. Report an error if it does. (YACC would generate a new 448 ** start symbol in this case.) */ 449 for ($rp = $this->rule; $rp; $rp = $rp->next) { 450 for ($i = 0; $i < $rp->nrhs; $i++) { 451 if ($rp->rhs[$i]->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) { 452 foreach ($rp->rhs[$i]->subsym as $subsp) { 453 if ($subsp === $sp) { 454 PHP_ParserGenerator::ErrorMsg($this->filename, 0, 455 "The start symbol \"%s\" occurs on the " . 456 "right-hand side of a rule. This will result in a parser which " . 457 "does not work properly.", $sp->name); 458 $this->errorcnt++; 459 } 460 } 461 } elseif ($rp->rhs[$i] === $sp) { 462 PHP_ParserGenerator::ErrorMsg($this->filename, 0, 463 "The start symbol \"%s\" occurs on the " . 464 "right-hand side of a rule. This will result in a parser which " . 465 "does not work properly.", $sp->name); 466 $this->errorcnt++; 467 } 468 } 469 } 470 471 /* The basis configuration set for the first state 472 ** is all rules which have the start symbol as their 473 ** left-hand side */ 474 for ($rp = $sp->rule; $rp; $rp = $rp->nextlhs) { 475 $newcfp = PHP_ParserGenerator_Config::Configlist_addbasis($rp, 0); 476 $newcfp->fws[0] = 1; 477 } 478 479 /* Compute the first state. All other states will be 480 ** computed automatically during the computation of the first one. 481 ** The returned pointer to the first state is not used. */ 482 $newstp = array(); 483 $newstp = $this->getstate(); 484 if (is_array($newstp)) { 485 $this->buildshifts($newstp[0]); /* Recursively compute successor states */ 486 } 487 } 488 489 /** 490 * @return PHP_ParserGenerator_State 491 */ 492 private function getstate() 493 { 494 /* Extract the sorted basis of the new state. The basis was constructed 495 ** by prior calls to "Configlist_addbasis()". */ 496 PHP_ParserGenerator_Config::Configlist_sortbasis(); 497 $bp = PHP_ParserGenerator_Config::Configlist_basis(); 498 499 /* Get a state with the same basis */ 500 $stp = PHP_ParserGenerator_State::State_find($bp); 501 if ($stp) { 502 /* A state with the same basis already exists! Copy all the follow-set 503 ** propagation links from the state under construction into the 504 ** preexisting state, then return a pointer to the preexisting state */ 505 for($x = $bp, $y = $stp->bp; $x && $y; $x = $x->bp, $y = $y->bp) { 506 PHP_ParserGenerator_PropagationLink::Plink_copy($y->bplp, $x->bplp); 507 PHP_ParserGenerator_PropagationLink::Plink_delete($x->fplp); 508 $x->fplp = $x->bplp = 0; 509 } 510 $cfp = PHP_ParserGenerator_Config::Configlist_return(); 511 PHP_ParserGenerator_Config::Configlist_eat($cfp); 512 } else { 513 /* This really is a new state. Construct all the details */ 514 PHP_ParserGenerator_Config::Configlist_closure($this); /* Compute the configuration closure */ 515 PHP_ParserGenerator_Config::Configlist_sort(); /* Sort the configuration closure */ 516 $cfp = PHP_ParserGenerator_Config::Configlist_return(); /* Get a pointer to the config list */ 517 $stp = new PHP_ParserGenerator_State; /* A new state structure */ 518 $stp->bp = $bp; /* Remember the configuration basis */ 519 $stp->cfp = $cfp; /* Remember the configuration closure */ 520 $stp->statenum = $this->nstate++; /* Every state gets a sequence number */ 521 $stp->ap = 0; /* No actions, yet. */ 522 PHP_ParserGenerator_State::State_insert($stp, $stp->bp); /* Add to the state table */ 523 // this can't work, recursion is too deep, move it into FindStates() 524 //$this->buildshifts($stp); /* Recursively compute successor states */ 525 return array($stp); 526 } 527 return $stp; 528 } 529 530 /** 531 * Construct all successor states to the given state. A "successor" 532 * state is any state which can be reached by a shift action. 533 * @param PHP_ParserGenerator_Data 534 * @param PHP_ParserGenerator_State The state from which successors are computed 535 */ 536 private function buildshifts(PHP_ParserGenerator_State $stp) 537 { 538// struct config *cfp; /* For looping thru the config closure of "stp" */ 539// struct config *bcfp; /* For the inner loop on config closure of "stp" */ 540// struct config *new; /* */ 541// struct symbol *sp; /* Symbol following the dot in configuration "cfp" */ 542// struct symbol *bsp; /* Symbol following the dot in configuration "bcfp" */ 543// struct state *newstp; /* A pointer to a successor state */ 544 545 /* Each configuration becomes complete after it contibutes to a successor 546 ** state. Initially, all configurations are incomplete */ 547 $cfp = $stp->cfp; 548 for ($cfp = $stp->cfp; $cfp; $cfp = $cfp->next) { 549 $cfp->status = PHP_ParserGenerator_Config::INCOMPLETE; 550 } 551 552 /* Loop through all configurations of the state "stp" */ 553 for ($cfp = $stp->cfp; $cfp; $cfp = $cfp->next) { 554 if ($cfp->status == PHP_ParserGenerator_Config::COMPLETE) { 555 continue; /* Already used by inner loop */ 556 } 557 if ($cfp->dot >= $cfp->rp->nrhs) { 558 continue; /* Can't shift this config */ 559 } 560 PHP_ParserGenerator_Config::Configlist_reset(); /* Reset the new config set */ 561 $sp = $cfp->rp->rhs[$cfp->dot]; /* Symbol after the dot */ 562 563 /* For every configuration in the state "stp" which has the symbol "sp" 564 ** following its dot, add the same configuration to the basis set under 565 ** construction but with the dot shifted one symbol to the right. */ 566 $bcfp = $cfp; 567 for ($bcfp = $cfp; $bcfp; $bcfp = $bcfp->next) { 568 if ($bcfp->status == PHP_ParserGenerator_Config::COMPLETE) { 569 continue; /* Already used */ 570 } 571 if ($bcfp->dot >= $bcfp->rp->nrhs) { 572 continue; /* Can't shift this one */ 573 } 574 $bsp = $bcfp->rp->rhs[$bcfp->dot]; /* Get symbol after dot */ 575 if (!PHP_ParserGenerator_Symbol::same_symbol($bsp, $sp)) { 576 continue; /* Must be same as for "cfp" */ 577 } 578 $bcfp->status = PHP_ParserGenerator_Config::COMPLETE; /* Mark this config as used */ 579 $new = PHP_ParserGenerator_Config::Configlist_addbasis($bcfp->rp, $bcfp->dot + 1); 580 PHP_ParserGenerator_PropagationLink::Plink_add($new->bplp, $bcfp); 581 } 582 583 /* Get a pointer to the state described by the basis configuration set 584 ** constructed in the preceding loop */ 585 $newstp = $this->getstate(); 586 if (is_array($newstp)) { 587 $this->buildshifts($newstp[0]); /* Recursively compute successor states */ 588 $newstp = $newstp[0]; 589 } 590 591 /* The state "newstp" is reached from the state "stp" by a shift action 592 ** on the symbol "sp" */ 593 if ($sp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) { 594 for($i = 0; $i < $sp->nsubsym; $i++) { 595 PHP_ParserGenerator_Action::Action_add($stp->ap, PHP_ParserGenerator_Action::SHIFT, $sp->subsym[$i], 596 $newstp); 597 } 598 } else { 599 PHP_ParserGenerator_Action::Action_add($stp->ap, PHP_ParserGenerator_Action::SHIFT, $sp, $newstp); 600 } 601 } 602 } 603 604 /** 605 * Construct the propagation links 606 */ 607 function FindLinks() 608 { 609 /* Housekeeping detail: 610 ** Add to every propagate link a pointer back to the state to 611 ** which the link is attached. */ 612 foreach ($this->sorted as $info) { 613 $info->key->stp = $info->data; 614 } 615 616 /* Convert all backlinks into forward links. Only the forward 617 ** links are used in the follow-set computation. */ 618 for ($i = 0; $i < $this->nstate; $i++) { 619 $stp = $this->sorted[$i]; 620 for ($cfp = $stp->data->cfp; $cfp; $cfp = $cfp->next) { 621 for ($plp = $cfp->bplp; $plp; $plp = $plp->next) { 622 $other = $plp->cfp; 623 PHP_ParserGenerator_PropagationLink::Plink_add($other->fplp, $cfp); 624 } 625 } 626 } 627 } 628 629 /** 630 * Compute the reduce actions, and resolve conflicts. 631 */ 632 function FindActions() 633 { 634 /* Add all of the reduce actions 635 ** A reduce action is added for each element of the followset of 636 ** a configuration which has its dot at the extreme right. 637 */ 638 for ($i = 0; $i < $this->nstate; $i++) { /* Loop over all states */ 639 $stp = $this->sorted[$i]->data; 640 for ($cfp = $stp->cfp; $cfp; $cfp = $cfp->next) { 641 /* Loop over all configurations */ 642 if ($cfp->rp->nrhs == $cfp->dot) { /* Is dot at extreme right? */ 643 for ($j = 0; $j < $this->nterminal; $j++) { 644 if (isset($cfp->fws[$j])) { 645 /* Add a reduce action to the state "stp" which will reduce by the 646 ** rule "cfp->rp" if the lookahead symbol is "$this->symbols[j]" */ 647 PHP_ParserGenerator_Action::Action_add($stp->ap, PHP_ParserGenerator_Action::REDUCE, 648 $this->symbols[$j], $cfp->rp); 649 } 650 } 651 } 652 } 653 } 654 655 /* Add the accepting token */ 656 if ($this->start instanceof PHP_ParserGenerator_Symbol) { 657 $sp = PHP_ParserGenerator_Symbol::Symbol_find($this->start); 658 if ($sp === 0) { 659 $sp = $this->rule->lhs; 660 } 661 } else { 662 $sp = $this->rule->lhs; 663 } 664 /* Add to the first state (which is always the starting state of the 665 ** finite state machine) an action to ACCEPT if the lookahead is the 666 ** start nonterminal. */ 667 PHP_ParserGenerator_Action::Action_add($this->sorted[0]->data->ap, PHP_ParserGenerator_Action::ACCEPT, $sp, 0); 668 669 /* Resolve conflicts */ 670 for ($i = 0; $i < $this->nstate; $i++) { 671 // struct action *ap, *nap; 672 // struct state *stp; 673 $stp = $this->sorted[$i]->data; 674 if (!$stp->ap) { 675 throw new Exception('state has no actions associated'); 676 } 677 echo 'processing state ' . $stp->statenum . " actions:\n"; 678 for ($ap = $stp->ap; $ap !== 0 && $ap->next !== 0; $ap = $ap->next) { 679 echo ' Action '; 680 $ap->display(true); 681 } 682 $stp->ap = PHP_ParserGenerator_Action::Action_sort($stp->ap); 683 for ($ap = $stp->ap; $ap !== 0 && $ap->next !== 0; $ap = $ap->next) { 684 for ($nap = $ap->next; $nap !== 0 && $nap->sp === $ap->sp ; $nap = $nap->next) { 685 /* The two actions "ap" and "nap" have the same lookahead. 686 ** Figure out which one should be used */ 687 $this->nconflict += $this->resolve_conflict($ap, $nap, $this->errsym); 688 } 689 } 690 } 691 692 /* Report an error for each rule that can never be reduced. */ 693 for ($rp = $this->rule; $rp; $rp = $rp->next) { 694 $rp->canReduce = false; 695 } 696 for ($i = 0; $i < $this->nstate; $i++) { 697 for ($ap = $this->sorted[$i]->data->ap; $ap !== 0; $ap = $ap->next) { 698 if ($ap->type == PHP_ParserGenerator_Action::REDUCE) { 699 $ap->x->canReduce = true; 700 } 701 } 702 } 703 for ($rp = $this->rule; $rp !== 0; $rp = $rp->next) { 704 if ($rp->canReduce) { 705 continue; 706 } 707 PHP_ParserGenerator::ErrorMsg($this->filename, $rp->ruleline, "This rule can not be reduced (is not connected to the start symbol).\n"); 708 $this->errorcnt++; 709 } 710 } 711 712 /** Resolve a conflict between the two given actions. If the 713 * conflict can't be resolve, return non-zero. 714 * 715 * NO LONGER TRUE: 716 * To resolve a conflict, first look to see if either action 717 * is on an error rule. In that case, take the action which 718 * is not associated with the error rule. If neither or both 719 * actions are associated with an error rule, then try to 720 * use precedence to resolve the conflict. 721 * 722 * If either action is a SHIFT, then it must be apx. This 723 * function won't work if apx->type==REDUCE and apy->type==SHIFT. 724 * @param PHP_ParserGenerator_Action 725 * @param PHP_ParserGenerator_Action 726 * @param PHP_ParserGenerator_Symbol|null The error symbol (if defined. NULL otherwise) 727 */ 728 function resolve_conflict($apx, $apy, $errsym) 729 { 730 $errcnt = 0; 731 if ($apx->sp !== $apy->sp) { 732 throw new Exception('no conflict but resolve_conflict called'); 733 } 734 if ($apx->type == PHP_ParserGenerator_Action::SHIFT && $apy->type == PHP_ParserGenerator_Action::REDUCE) { 735 $spx = $apx->sp; 736 $spy = $apy->x->precsym; 737 if ($spy === 0 || $spx->prec < 0 || $spy->prec < 0) { 738 /* Not enough precedence information. */ 739 $apy->type = PHP_ParserGenerator_Action::CONFLICT; 740 $errcnt++; 741 } elseif ($spx->prec > $spy->prec) { /* Lower precedence wins */ 742 $apy->type = PHP_ParserGenerator_Action::RD_RESOLVED; 743 } elseif ($spx->prec < $spy->prec) { 744 $apx->type = PHP_ParserGenerator_Action::SH_RESOLVED; 745 } elseif ($spx->prec === $spy->prec && $spx->assoc == PHP_ParserGenerator_Symbol::RIGHT) { 746 /* Use operator */ 747 $apy->type = PHP_ParserGenerator_Action::RD_RESOLVED; /* associativity */ 748 } elseif ($spx->prec === $spy->prec && $spx->assoc == PHP_ParserGenerator_Symbol::LEFT) { 749 /* to break tie */ 750 $apx->type = PHP_ParserGenerator_Action::SH_RESOLVED; 751 } else { 752 if ($spx->prec !== $spy->prec || $spx->assoc !== PHP_ParserGenerator_Symbol::NONE) { 753 throw new Exception('$spx->prec !== $spy->prec || $spx->assoc !== PHP_ParserGenerator_Symbol::NONE'); 754 } 755 $apy->type = PHP_ParserGenerator_Action::CONFLICT; 756 $errcnt++; 757 } 758 } elseif ($apx->type == PHP_ParserGenerator_Action::REDUCE && $apy->type == PHP_ParserGenerator_Action::REDUCE) { 759 $spx = $apx->x->precsym; 760 $spy = $apy->x->precsym; 761 if ($spx === 0 || $spy === 0 || $spx->prec < 0 || 762 $spy->prec < 0 || $spx->prec === $spy->prec) { 763 $apy->type = PHP_ParserGenerator_Action::CONFLICT; 764 $errcnt++; 765 } elseif ($spx->prec > $spy->prec) { 766 $apy->type = PHP_ParserGenerator_Action::RD_RESOLVED; 767 } elseif ($spx->prec < $spy->prec) { 768 $apx->type = PHP_ParserGenerator_Action::RD_RESOLVED; 769 } 770 } else { 771 if ($apx->type!== PHP_ParserGenerator_Action::SH_RESOLVED && 772 $apx->type!== PHP_ParserGenerator_Action::RD_RESOLVED && 773 $apx->type!== PHP_ParserGenerator_Action::CONFLICT && 774 $apy->type!== PHP_ParserGenerator_Action::SH_RESOLVED && 775 $apy->type!== PHP_ParserGenerator_Action::RD_RESOLVED && 776 $apy->type!== PHP_ParserGenerator_Action::CONFLICT) { 777 throw new Exception('$apx->type!== PHP_ParserGenerator_Action::SH_RESOLVED && 778 $apx->type!== PHP_ParserGenerator_Action::RD_RESOLVED && 779 $apx->type!== PHP_ParserGenerator_Action::CONFLICT && 780 $apy->type!== PHP_ParserGenerator_Action::SH_RESOLVED && 781 $apy->type!== PHP_ParserGenerator_Action::RD_RESOLVED && 782 $apy->type!== PHP_ParserGenerator_Action::CONFLICT'); 783 } 784 /* The REDUCE/SHIFT case cannot happen because SHIFTs come before 785 ** REDUCEs on the list. If we reach this point it must be because 786 ** the parser conflict had already been resolved. */ 787 } 788 return $errcnt; 789 } 790 791 /** 792 * Reduce the size of the action tables, if possible, by making use 793 * of defaults. 794 * 795 * In this version, we take the most frequent REDUCE action and make 796 * it the default. 797 */ 798 function CompressTables() 799 { 800 for ($i = 0; $i < $this->nstate; $i++) { 801 $stp = $this->sorted[$i]->data; 802 $nbest = 0; 803 $rbest = 0; 804 805 for ($ap = $stp->ap; $ap; $ap = $ap->next) { 806 if ($ap->type != PHP_ParserGenerator_Action::REDUCE) { 807 continue; 808 } 809 $rp = $ap->x; 810 if ($rp === $rbest) { 811 continue; 812 } 813 $n = 1; 814 for ($ap2 = $ap->next; $ap2; $ap2 = $ap2->next) { 815 if ($ap2->type != PHP_ParserGenerator_Action::REDUCE) { 816 continue; 817 } 818 $rp2 = $ap2->x; 819 if ($rp2 === $rbest) { 820 continue; 821 } 822 if ($rp2 === $rp) { 823 $n++; 824 } 825 } 826 if ($n > $nbest) { 827 $nbest = $n; 828 $rbest = $rp; 829 } 830 } 831 832 /* Do not make a default if the number of rules to default 833 ** is not at least 1 */ 834 if ($nbest < 1) { 835 continue; 836 } 837 838 839 /* Combine matching REDUCE actions into a single default */ 840 for ($ap = $stp->ap; $ap; $ap = $ap->next) { 841 if ($ap->type == PHP_ParserGenerator_Action::REDUCE && $ap->x === $rbest) { 842 break; 843 } 844 } 845 if ($ap === 0) { 846 throw new Exception('$ap is not an object'); 847 } 848 $ap->sp = PHP_ParserGenerator_Symbol::Symbol_new("{default}"); 849 for ($ap = $ap->next; $ap; $ap = $ap->next) { 850 if ($ap->type == PHP_ParserGenerator_Action::REDUCE && $ap->x === $rbest) { 851 $ap->type = PHP_ParserGenerator_Action::NOT_USED; 852 } 853 } 854 $stp->ap = PHP_ParserGenerator_Action::Action_sort($stp->ap); 855 } 856 } 857 858 /** 859 * Renumber and resort states so that states with fewer choices 860 * occur at the end. Except, keep state 0 as the first state. 861 */ 862 function ResortStates() 863 { 864 for ($i = 0; $i < $this->nstate; $i++) { 865 $stp = $this->sorted[$i]->data; 866 $stp->nTknAct = $stp->nNtAct = 0; 867 $stp->iDflt = $this->nstate + $this->nrule; 868 $stp->iTknOfst = PHP_ParserGenerator_Data::NO_OFFSET; 869 $stp->iNtOfst = PHP_ParserGenerator_Data::NO_OFFSET; 870 for ($ap = $stp->ap; $ap; $ap = $ap->next) { 871 if ($this->compute_action($ap) >= 0) { 872 if ($ap->sp->index < $this->nterminal) { 873 $stp->nTknAct++; 874 } elseif ($ap->sp->index < $this->nsymbol) { 875 $stp->nNtAct++; 876 } else { 877 $stp->iDflt = $this->compute_action($ap); 878 } 879 } 880 } 881 $this->sorted[$i] = $stp; 882 } 883 $save = $this->sorted[0]; 884 unset($this->sorted[0]); 885 usort($this->sorted, array('PHP_ParserGenerator_State', 'stateResortCompare')); 886 array_unshift($this->sorted, $save); 887 for($i = 0; $i < $this->nstate; $i++) { 888 $this->sorted[$i]->statenum = $i; 889 } 890 } 891 892 /** 893 * Given an action, compute the integer value for that action 894 * which is to be put in the action table of the generated machine. 895 * Return negative if no action should be generated. 896 * @param PHP_ParserGenerator_Action 897 */ 898 function compute_action($ap) 899 { 900 switch ($ap->type) { 901 case PHP_ParserGenerator_Action::SHIFT: 902 $act = $ap->x->statenum; 903 break; 904 case PHP_ParserGenerator_Action::REDUCE: 905 $act = $ap->x->index + $this->nstate; 906 break; 907 case PHP_ParserGenerator_Action::ERROR: 908 $act = $this->nstate + $this->nrule; 909 break; 910 case PHP_ParserGenerator_Action::ACCEPT: 911 $act = $this->nstate + $this->nrule + 1; 912 break; 913 default: 914 $act = -1; 915 break; 916 } 917 return $act; 918 } 919 920 /** 921 * Generate the "Parse.out" log file 922 */ 923 function ReportOutput() 924 { 925 $fp = fopen($this->filenosuffix . ".out", "wb"); 926 if (!$fp) { 927 return; 928 } 929 for ($i = 0; $i < $this->nstate; $i++) { 930 $stp = $this->sorted[$i]; 931 fprintf($fp, "State %d:\n", $stp->statenum); 932 if ($this->basisflag) { 933 $cfp = $stp->bp; 934 } else { 935 $cfp = $stp->cfp; 936 } 937 while ($cfp) { 938 if ($cfp->dot == $cfp->rp->nrhs) { 939 $buf = sprintf('(%d)', $cfp->rp->index); 940 fprintf($fp, ' %5s ', $buf); 941 } else { 942 fwrite($fp,' '); 943 } 944 $cfp->ConfigPrint($fp); 945 fwrite($fp, "\n"); 946 if (0) { 947 //SetPrint(fp,cfp->fws,$this); 948 //PlinkPrint(fp,cfp->fplp,"To "); 949 //PlinkPrint(fp,cfp->bplp,"From"); 950 } 951 if ($this->basisflag) { 952 $cfp = $cfp->bp; 953 } else { 954 $cfp = $cfp->next; 955 } 956 } 957 fwrite($fp, "\n"); 958 for ($ap = $stp->ap; $ap; $ap = $ap->next) { 959 if ($ap->PrintAction($fp, 30)) { 960 fprintf($fp,"\n"); 961 } 962 } 963 fwrite($fp,"\n"); 964 } 965 fclose($fp); 966 } 967 968 /** 969 * The next function finds the template file and opens it, returning 970 * a pointer to the opened file. 971 * @return resource 972 */ 973 private function tplt_open() 974 { 975 $templatename = $this->parser_template ? $this->parser_template : dirname(dirname(__FILE__)) . DIRECTORY_SEPARATOR . "Lempar.php"; 976 977 $buf = $this->filenosuffix . '.lt'; 978 if (file_exists($buf) && is_readable($buf)) { 979 $tpltname = $buf; 980 } elseif (file_exists($templatename) && is_readable($templatename)) { 981 $tpltname = $templatename; 982 } elseif ($fp = @fopen($templatename, 'rb', true)) { 983 return $fp; 984 } 985 if (!isset($tpltname)) { 986 echo "Can't find the parser driver template file \"%s\".\n", 987 $templatename; 988 $this->errorcnt++; 989 return 0; 990 } 991 $in = @fopen($tpltname,"rb"); 992 if (!$in) { 993 printf("Can't open the template file \"%s\".\n", $tpltname); 994 $this->errorcnt++; 995 return 0; 996 } 997 return $in; 998 } 999 1000#define LINESIZE 1000 1001 /**#@+ 1002 * The next cluster of routines are for reading the template file 1003 * and writing the results to the generated parser 1004 */ 1005 /** 1006 * The first function transfers data from "in" to "out" until 1007 * a line is seen which begins with "%%". The line number is 1008 * tracked. 1009 * 1010 * if name!=0, then any word that begin with "Parse" is changed to 1011 * begin with *name instead. 1012 */ 1013 private function tplt_xfer($name, $in, $out, &$lineno) 1014 { 1015 while (($line = fgets($in, 1024)) && ($line[0] != '%' || $line[1] != '%')) { 1016 $lineno++; 1017 $iStart = 0; 1018 if ($name) { 1019 for ($i = 0; $i < strlen($line); $i++) { 1020 if ($line[$i] == 'P' && substr($line, $i, 5) == "Parse" 1021 && ($i === 0 || preg_match('/[^a-zA-Z]/', $line[$i - 1]))) { 1022 if ($i > $iStart) { 1023 fwrite($out, substr($line, $iStart, $i - $iStart)); 1024 } 1025 fwrite($out, $name); 1026 $i += 4; 1027 $iStart = $i + 1; 1028 } 1029 } 1030 } 1031 fwrite($out, substr($line, $iStart)); 1032 } 1033 } 1034 1035 /** 1036 * Print a #line directive line to the output file. 1037 */ 1038 private function tplt_linedir($out, $lineno, $filename) 1039 { 1040 fwrite($out, '#line ' . $lineno . ' "' . $filename . "\"\n"); 1041 } 1042 1043 /** 1044 * Print a string to the file and keep the linenumber up to date 1045 */ 1046 private function tplt_print($out, $str, $strln, &$lineno) 1047 { 1048 if ($str == '') { 1049 return; 1050 } 1051 $this->tplt_linedir($out, $strln, $this->filename); 1052 $lineno++; 1053 fwrite($out, $str); 1054 $lineno += count(explode("\n", $str)) - 1; 1055 $this->tplt_linedir($out, $lineno + 2, $this->outname); 1056 $lineno += 2; 1057 } 1058 /**#@-*/ 1059 1060 /** 1061 * Compute all followsets. 1062 * 1063 * A followset is the set of all symbols which can come immediately 1064 * after a configuration. 1065 */ 1066 function FindFollowSets() 1067 { 1068 for ($i = 0; $i < $this->nstate; $i++) { 1069 for ($cfp = $this->sorted[$i]->data->cfp; $cfp; $cfp = $cfp->next) { 1070 $cfp->status = PHP_ParserGenerator_Config::INCOMPLETE; 1071 } 1072 } 1073 1074 do { 1075 $progress = 0; 1076 for ($i = 0; $i < $this->nstate; $i++) { 1077 for ($cfp = $this->sorted[$i]->data->cfp; $cfp; $cfp = $cfp->next) { 1078 if ($cfp->status == PHP_ParserGenerator_Config::COMPLETE) { 1079 continue; 1080 } 1081 for ($plp = $cfp->fplp; $plp; $plp = $plp->next) { 1082 $a = array_diff_key($cfp->fws, $plp->cfp->fws); 1083 if (count($a)) { 1084 $plp->cfp->fws += $a; 1085 $plp->cfp->status = PHP_ParserGenerator_Config::INCOMPLETE; 1086 $progress = 1; 1087 } 1088 } 1089 $cfp->status = PHP_ParserGenerator_Config::COMPLETE; 1090 } 1091 } 1092 } while ($progress); 1093 } 1094 1095 /** 1096 * Generate C source code for the parser 1097 * @param int Output in makeheaders format if true 1098 */ 1099 function ReportTable($mhflag) 1100 { 1101// FILE *out, *in; 1102// char line[LINESIZE]; 1103// int lineno; 1104// struct state *stp; 1105// struct action *ap; 1106// struct rule *rp; 1107// struct acttab *pActtab; 1108// int i, j, n; 1109// char *name; 1110// int mnTknOfst, mxTknOfst; 1111// int mnNtOfst, mxNtOfst; 1112// struct axset *ax; 1113 1114 $in = $this->tplt_open(); 1115 if (!$in) { 1116 return; 1117 } 1118 $out = fopen($this->filenosuffix . ".php", "wb"); 1119 if (!$out) { 1120 fclose($in); 1121 return; 1122 } 1123 $this->outname = $this->filenosuffix . ".php"; 1124 $lineno = 1; 1125 $this->tplt_xfer($this->name, $in, $out, $lineno); 1126 1127 /* Generate the include code, if any */ 1128 $this->tplt_print($out, $this->include_code, $this->includeln, $lineno); 1129 $this->tplt_xfer($this->name, $in, $out, $lineno); 1130 1131 /* Generate the class declaration code */ 1132 $this->tplt_print($out, $this->declare_classcode, $this->declare_classln, 1133 $lineno); 1134 $this->tplt_xfer($this->name, $in, $out, $lineno); 1135 1136 /* Generate the internal parser class include code, if any */ 1137 $this->tplt_print($out, $this->include_classcode, $this->include_classln, 1138 $lineno); 1139 $this->tplt_xfer($this->name, $in, $out, $lineno); 1140 1141 /* Generate #defines for all tokens */ 1142 //if ($mhflag) { 1143 //fprintf($out, "#if INTERFACE\n"); 1144 $lineno++; 1145 if ($this->tokenprefix) { 1146 $prefix = $this->tokenprefix; 1147 } else { 1148 $prefix = ''; 1149 } 1150 for ($i = 1; $i < $this->nterminal; $i++) { 1151 fprintf($out, " const %s%-30s = %2d;\n", $prefix, $this->symbols[$i]->name, $i); 1152 $lineno++; 1153 } 1154 //fwrite($out, "#endif\n"); 1155 $lineno++; 1156 //} 1157 fwrite($out, " const YY_NO_ACTION = " . 1158 ($this->nstate + $this->nrule + 2) . ";\n"); 1159 $lineno++; 1160 fwrite($out, " const YY_ACCEPT_ACTION = " . 1161 ($this->nstate + $this->nrule + 1) . ";\n"); 1162 $lineno++; 1163 fwrite($out, " const YY_ERROR_ACTION = " . 1164 ($this->nstate + $this->nrule) . ";\n"); 1165 $lineno++; 1166 $this->tplt_xfer($this->name, $in, $out, $lineno); 1167 1168 /* Generate the action table and its associates: 1169 ** 1170 ** yy_action[] A single table containing all actions. 1171 ** yy_lookahead[] A table containing the lookahead for each entry in 1172 ** yy_action. Used to detect hash collisions. 1173 ** yy_shift_ofst[] For each state, the offset into yy_action for 1174 ** shifting terminals. 1175 ** yy_reduce_ofst[] For each state, the offset into yy_action for 1176 ** shifting non-terminals after a reduce. 1177 ** yy_default[] Default action for each state. 1178 */ 1179 1180 /* Compute the actions on all states and count them up */ 1181 1182 $ax = array(); 1183 for ($i = 0; $i < $this->nstate; $i++) { 1184 $stp = $this->sorted[$i]; 1185 $ax[$i * 2] = array(); 1186 $ax[$i * 2]['stp'] = $stp; 1187 $ax[$i * 2]['isTkn'] = 1; 1188 $ax[$i * 2]['nAction'] = $stp->nTknAct; 1189 $ax[$i * 2 + 1] = array(); 1190 $ax[$i * 2 + 1]['stp'] = $stp; 1191 $ax[$i * 2 + 1]['isTkn'] = 0; 1192 $ax[$i * 2 + 1]['nAction'] = $stp->nNtAct; 1193 } 1194 $mxTknOfst = $mnTknOfst = 0; 1195 $mxNtOfst = $mnNtOfst = 0; 1196 1197 /* Compute the action table. In order to try to keep the size of the 1198 ** action table to a minimum, the heuristic of placing the largest action 1199 ** sets first is used. 1200 */ 1201 1202 usort($ax, array('PHP_ParserGenerator_Data', 'axset_compare')); 1203 $pActtab = new PHP_ParserGenerator_ActionTable; 1204 for ($i = 0; $i < $this->nstate * 2 && $ax[$i]['nAction'] > 0; $i++) { 1205 $stp = $ax[$i]['stp']; 1206 if ($ax[$i]['isTkn']) { 1207 for ($ap = $stp->ap; $ap; $ap = $ap->next) { 1208 if ($ap->sp->index >= $this->nterminal) { 1209 continue; 1210 } 1211 $action = $this->compute_action($ap); 1212 if ($action < 0) { 1213 continue; 1214 } 1215 $pActtab->acttab_action($ap->sp->index, $action); 1216 } 1217 $stp->iTknOfst = $pActtab->acttab_insert(); 1218 if ($stp->iTknOfst < $mnTknOfst) { 1219 $mnTknOfst = $stp->iTknOfst; 1220 } 1221 if ($stp->iTknOfst > $mxTknOfst) { 1222 $mxTknOfst = $stp->iTknOfst; 1223 } 1224 } else { 1225 for ($ap = $stp->ap; $ap; $ap = $ap->next) { 1226 if ($ap->sp->index < $this->nterminal) { 1227 continue; 1228 } 1229 if ($ap->sp->index == $this->nsymbol) { 1230 continue; 1231 } 1232 $action = $this->compute_action($ap); 1233 if ($action < 0) { 1234 continue; 1235 } 1236 $pActtab->acttab_action($ap->sp->index, $action); 1237 } 1238 $stp->iNtOfst = $pActtab->acttab_insert(); 1239 if ($stp->iNtOfst < $mnNtOfst) { 1240 $mnNtOfst = $stp->iNtOfst; 1241 } 1242 if ($stp->iNtOfst > $mxNtOfst) { 1243 $mxNtOfst = $stp->iNtOfst; 1244 } 1245 } 1246 } 1247 /* Output the yy_action table */ 1248 1249 fprintf($out, " const YY_SZ_ACTTAB = %d;\n", $pActtab->nAction); 1250 $lineno++; 1251 fwrite($out, "static public \$yy_action = array(\n"); 1252 $lineno++; 1253 $n = $pActtab->nAction; 1254 for($i = $j = 0; $i < $n; $i++) { 1255 $action = $pActtab->aAction[$i]['action']; 1256 if ($action < 0) { 1257 $action = $this->nsymbol + $this->nrule + 2; 1258 } 1259 // change next line 1260 if ($j === 0) { 1261 fprintf($out, " /* %5d */ ", $i); 1262 } 1263 fprintf($out, " %4d,", $action); 1264 if ($j == 9 || $i == $n - 1) { 1265 fwrite($out, "\n"); 1266 $lineno++; 1267 $j = 0; 1268 } else { 1269 $j++; 1270 } 1271 } 1272 fwrite($out, " );\n"); $lineno++; 1273 1274 /* Output the yy_lookahead table */ 1275 1276 fwrite($out, " static public \$yy_lookahead = array(\n"); 1277 $lineno++; 1278 for ($i = $j = 0; $i < $n; $i++) { 1279 $la = $pActtab->aAction[$i]['lookahead']; 1280 if ($la < 0) { 1281 $la = $this->nsymbol; 1282 } 1283 // change next line 1284 if ($j === 0) { 1285 fprintf($out, " /* %5d */ ", $i); 1286 } 1287 fprintf($out, " %4d,", $la); 1288 if ($j == 9 || $i == $n - 1) { 1289 fwrite($out, "\n"); 1290 $lineno++; 1291 $j = 0; 1292 } else { 1293 $j++; 1294 } 1295 } 1296 fwrite($out, ");\n"); 1297 $lineno++; 1298 1299 /* Output the yy_shift_ofst[] table */ 1300 fprintf($out, " const YY_SHIFT_USE_DFLT = %d;\n", $mnTknOfst - 1); 1301 $lineno++; 1302 $n = $this->nstate; 1303 while ($n > 0 && $this->sorted[$n - 1]->iTknOfst == PHP_ParserGenerator_Data::NO_OFFSET) { 1304 $n--; 1305 } 1306 fprintf($out, " const YY_SHIFT_MAX = %d;\n", $n - 1); 1307 $lineno++; 1308 fwrite($out, " static public \$yy_shift_ofst = array(\n"); 1309 $lineno++; 1310 for ($i = $j = 0; $i < $n; $i++) { 1311 $stp = $this->sorted[$i]; 1312 $ofst = $stp->iTknOfst; 1313 if ($ofst === PHP_ParserGenerator_Data::NO_OFFSET) { 1314 $ofst = $mnTknOfst - 1; 1315 } 1316 // change next line 1317 if ($j === 0) { 1318 fprintf($out, " /* %5d */ ", $i); 1319 } 1320 fprintf($out, " %4d,", $ofst); 1321 if ($j == 9 || $i == $n - 1) { 1322 fwrite($out, "\n"); 1323 $lineno++; 1324 $j = 0; 1325 } else { 1326 $j++; 1327 } 1328 } 1329 fwrite($out, ");\n"); 1330 $lineno++; 1331 1332 1333 /* Output the yy_reduce_ofst[] table */ 1334 1335 fprintf($out, " const YY_REDUCE_USE_DFLT = %d;\n", $mnNtOfst - 1); 1336 $lineno++; 1337 $n = $this->nstate; 1338 while ($n > 0 && $this->sorted[$n - 1]->iNtOfst == PHP_ParserGenerator_Data::NO_OFFSET) { 1339 $n--; 1340 } 1341 fprintf($out, " const YY_REDUCE_MAX = %d;\n", $n - 1); 1342 $lineno++; 1343 fwrite($out, " static public \$yy_reduce_ofst = array(\n"); 1344 $lineno++; 1345 for ($i = $j = 0; $i < $n; $i++) { 1346 $stp = $this->sorted[$i]; 1347 $ofst = $stp->iNtOfst; 1348 if ($ofst == PHP_ParserGenerator_Data::NO_OFFSET) { 1349 $ofst = $mnNtOfst - 1; 1350 } 1351 // change next line 1352 if ($j == 0) { 1353 fprintf($out, " /* %5d */ ", $i); 1354 } 1355 fprintf($out, " %4d,", $ofst); 1356 if ($j == 9 || $i == $n - 1) { 1357 fwrite($out, "\n"); 1358 $lineno++; 1359 $j = 0; 1360 } else { 1361 $j++; 1362 } 1363 } 1364 fwrite($out, ");\n"); 1365 $lineno++; 1366 1367 /* Output the expected tokens table */ 1368 1369 fwrite($out, " static public \$yyExpectedTokens = array(\n"); 1370 $lineno++; 1371 for ($i = 0; $i < $this->nstate; $i++) { 1372 $stp = $this->sorted[$i]; 1373 fwrite($out, " /* $i */ array("); 1374 for ($ap = $stp->ap; $ap; $ap = $ap->next) { 1375 if ($ap->sp->index < $this->nterminal) { 1376 if ($ap->type == PHP_ParserGenerator_Action::SHIFT || 1377 $ap->type == PHP_ParserGenerator_Action::REDUCE) { 1378 fwrite($out, $ap->sp->index . ', '); 1379 } 1380 } 1381 } 1382 fwrite($out, "),\n"); 1383 $lineno++; 1384 } 1385 fwrite($out, ");\n"); 1386 $lineno++; 1387 1388 /* Output the default action table */ 1389 1390 fwrite($out, " static public \$yy_default = array(\n"); 1391 $lineno++; 1392 $n = $this->nstate; 1393 for ($i = $j = 0; $i < $n; $i++) { 1394 $stp = $this->sorted[$i]; 1395 // change next line 1396 if ($j == 0) { 1397 fprintf($out, " /* %5d */ ", $i); 1398 } 1399 fprintf($out, " %4d,", $stp->iDflt); 1400 if ($j == 9 || $i == $n - 1) { 1401 fprintf($out, "\n"); $lineno++; 1402 $j = 0; 1403 } else { 1404 $j++; 1405 } 1406 } 1407 fwrite($out, ");\n"); 1408 $lineno++; 1409 $this->tplt_xfer($this->name, $in, $out, $lineno); 1410 1411 /* Generate the defines */ 1412 fprintf($out, " const YYNOCODE = %d;\n", $this->nsymbol + 1); 1413 $lineno++; 1414 if ($this->stacksize) { 1415 if($this->stacksize <= 0) { 1416 PHP_ParserGenerator::ErrorMsg($this->filename, 0, 1417 "Illegal stack size: [%s]. The stack size should be an integer constant.", 1418 $this->stacksize); 1419 $this->errorcnt++; 1420 $this->stacksize = "100"; 1421 } 1422 fprintf($out, " const YYSTACKDEPTH = %s;\n", $this->stacksize); 1423 $lineno++; 1424 } else { 1425 fwrite($out," const YYSTACKDEPTH = 100;\n"); 1426 $lineno++; 1427 } 1428 fprintf($out, " const YYNSTATE = %d;\n", $this->nstate); 1429 $lineno++; 1430 fprintf($out, " const YYNRULE = %d;\n", $this->nrule); 1431 $lineno++; 1432 fprintf($out, " const YYERRORSYMBOL = %d;\n", $this->errsym->index); 1433 $lineno++; 1434 fprintf($out, " const YYERRSYMDT = 'yy%d';\n", $this->errsym->dtnum); 1435 $lineno++; 1436 if ($this->has_fallback) { 1437 fwrite($out, " const YYFALLBACK = 1;\n"); 1438 } else { 1439 fwrite($out, " const YYFALLBACK = 0;\n"); 1440 } 1441 $lineno++; 1442 $this->tplt_xfer($this->name, $in, $out, $lineno); 1443 1444 /* Generate the table of fallback tokens. 1445 */ 1446 1447 if ($this->has_fallback) { 1448 for ($i = 0; $i < $this->nterminal; $i++) { 1449 $p = $this->symbols[$i]; 1450 if ($p->fallback === 0) { 1451 // change next line 1452 fprintf($out, " 0, /* %10s => nothing */\n", $p->name); 1453 } else { 1454 // change next line 1455 fprintf($out, " %3d, /* %10s => %s */\n", 1456 $p->fallback->index, $p->name, $p->fallback->name); 1457 } 1458 $lineno++; 1459 } 1460 } 1461 $this->tplt_xfer($this->name, $in, $out, $lineno); 1462 1463 1464 /* Generate a table containing the symbolic name of every symbol 1465 ($yyTokenName) 1466 */ 1467 1468 for ($i = 0; $i < $this->nsymbol; $i++) { 1469 fprintf($out," %-15s", "'" . $this->symbols[$i]->name . "',"); 1470 if (($i & 3) == 3) { 1471 fwrite($out,"\n"); 1472 $lineno++; 1473 } 1474 } 1475 if (($i & 3) != 0) { 1476 fwrite($out, "\n"); 1477 $lineno++; 1478 } 1479 $this->tplt_xfer($this->name, $in, $out, $lineno); 1480 1481 /* Generate a table containing a text string that describes every 1482 ** rule in the rule set of the grammer. This information is used 1483 ** when tracing REDUCE actions. 1484 */ 1485 1486 for ($i = 0, $rp = $this->rule; $rp; $rp = $rp->next, $i++) { 1487 if ($rp->index !== $i) { 1488 throw new Exception('rp->index != i and should be'); 1489 } 1490 // change next line 1491 fprintf($out, " /* %3d */ \"%s ::=", $i, $rp->lhs->name); 1492 for ($j = 0; $j < $rp->nrhs; $j++) { 1493 $sp = $rp->rhs[$j]; 1494 fwrite($out,' ' . $sp->name); 1495 if ($sp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) { 1496 for($k = 1; $k < $sp->nsubsym; $k++) { 1497 fwrite($out, '|' . $sp->subsym[$k]->name); 1498 } 1499 } 1500 } 1501 fwrite($out, "\",\n"); 1502 $lineno++; 1503 } 1504 $this->tplt_xfer($this->name, $in, $out, $lineno); 1505 1506 /* Generate code which executes every time a symbol is popped from 1507 ** the stack while processing errors or while destroying the parser. 1508 ** (In other words, generate the %destructor actions) 1509 */ 1510 1511 if ($this->tokendest) { 1512 for ($i = 0; $i < $this->nsymbol; $i++) { 1513 $sp = $this->symbols[$i]; 1514 if ($sp === 0 || $sp->type != PHP_ParserGenerator_Symbol::TERMINAL) { 1515 continue; 1516 } 1517 fprintf($out, " case %d:\n", $sp->index); 1518 $lineno++; 1519 } 1520 for ($i = 0; $i < $this->nsymbol && 1521 $this->symbols[$i]->type != PHP_ParserGenerator_Symbol::TERMINAL; $i++); 1522 if ($i < $this->nsymbol) { 1523 $this->emit_destructor_code($out, $this->symbols[$i], $lineno); 1524 fprintf($out, " break;\n"); 1525 $lineno++; 1526 } 1527 } 1528 if ($this->vardest) { 1529 $dflt_sp = 0; 1530 for ($i = 0; $i < $this->nsymbol; $i++) { 1531 $sp = $this->symbols[$i]; 1532 if ($sp === 0 || $sp->type == PHP_ParserGenerator_Symbol::TERMINAL || 1533 $sp->index <= 0 || $sp->destructor != 0) { 1534 continue; 1535 } 1536 fprintf($out, " case %d:\n", $sp->index); 1537 $lineno++; 1538 $dflt_sp = $sp; 1539 } 1540 if ($dflt_sp != 0) { 1541 $this->emit_destructor_code($out, $dflt_sp, $lineno); 1542 fwrite($out, " break;\n"); 1543 $lineno++; 1544 } 1545 } 1546 for ($i = 0; $i < $this->nsymbol; $i++) { 1547 $sp = $this->symbols[$i]; 1548 if ($sp === 0 || $sp->type == PHP_ParserGenerator_Symbol::TERMINAL || 1549 $sp->destructor === 0) { 1550 continue; 1551 } 1552 fprintf($out, " case %d:\n", $sp->index); 1553 $lineno++; 1554 1555 /* Combine duplicate destructors into a single case */ 1556 1557 for ($j = $i + 1; $j < $this->nsymbol; $j++) { 1558 $sp2 = $this->symbols[$j]; 1559 if ($sp2 && $sp2->type != PHP_ParserGenerator_Symbol::TERMINAL && $sp2->destructor 1560 && $sp2->dtnum == $sp->dtnum 1561 && $sp->destructor == $sp2->destructor) { 1562 fprintf($out, " case %d:\n", $sp2->index); 1563 $lineno++; 1564 $sp2->destructor = 0; 1565 } 1566 } 1567 1568 $this->emit_destructor_code($out, $this->symbols[$i], $lineno); 1569 fprintf($out, " break;\n"); 1570 $lineno++; 1571 } 1572 $this->tplt_xfer($this->name, $in, $out, $lineno); 1573 1574 /* Generate code which executes whenever the parser stack overflows */ 1575 1576 $this->tplt_print($out, $this->overflow, $this->overflowln, $lineno); 1577 $this->tplt_xfer($this->name, $in, $out, $lineno); 1578 1579 /* Generate the table of rule information 1580 ** 1581 ** Note: This code depends on the fact that rules are number 1582 ** sequentually beginning with 0. 1583 */ 1584 1585 for ($rp = $this->rule; $rp; $rp = $rp->next) { 1586 fprintf($out, " array( 'lhs' => %d, 'rhs' => %d ),\n", 1587 $rp->lhs->index, $rp->nrhs); 1588 $lineno++; 1589 } 1590 $this->tplt_xfer($this->name, $in, $out, $lineno); 1591 1592 1593 /* Generate code which executes during each REDUCE action */ 1594 1595 for ($rp = $this->rule; $rp; $rp = $rp->next) { 1596 if ($rp->code) { 1597 $this->translate_code($rp); 1598 } 1599 } 1600 1601 /* Generate the method map for each REDUCE action */ 1602 1603 for ($rp = $this->rule; $rp; $rp = $rp->next) { 1604 if ($rp->code === 0) { 1605 continue; 1606 } 1607 fwrite($out, ' ' . $rp->index . ' => ' . $rp->index . ",\n"); 1608 $lineno++; 1609 for ($rp2 = $rp->next; $rp2; $rp2 = $rp2->next) { 1610 if ($rp2->code === $rp->code) { 1611 fwrite($out, ' ' . $rp2->index . ' => ' . 1612 $rp->index . ",\n"); 1613 $lineno++; 1614 $rp2->code = 0; 1615 } 1616 } 1617 } 1618 $this->tplt_xfer($this->name, $in, $out, $lineno); 1619 1620 for ($rp = $this->rule; $rp; $rp = $rp->next) { 1621 if ($rp->code === 0) { 1622 continue; 1623 } 1624 $this->emit_code($out, $rp, $lineno); 1625 } 1626 $this->tplt_xfer($this->name, $in, $out, $lineno); 1627 1628 1629 /* Generate code which executes if a parse fails */ 1630 1631 $this->tplt_print($out, $this->failure, $this->failureln, $lineno); 1632 $this->tplt_xfer($this->name, $in, $out, $lineno); 1633 1634 /* Generate code which executes when a syntax error occurs */ 1635 1636 $this->tplt_print($out, $this->error, $this->errorln, $lineno); 1637 $this->tplt_xfer($this->name, $in, $out, $lineno); 1638 1639 /* Generate code which executes when the parser accepts its input */ 1640 1641 $this->tplt_print($out, $this->accept, $this->acceptln, $lineno); 1642 $this->tplt_xfer($this->name, $in, $out, $lineno); 1643 1644 /* Append any addition code the user desires */ 1645 1646 $this->tplt_print($out, $this->extracode, $this->extracodeln, $lineno); 1647 1648 fclose($in); 1649 fclose($out); 1650 } 1651 1652 /** 1653 * Generate code which executes when the rule "rp" is reduced. Write 1654 * the code to "out". Make sure lineno stays up-to-date. 1655 */ 1656 function emit_code($out, PHP_ParserGenerator_Rule $rp, &$lineno) 1657 { 1658 $linecnt = 0; 1659 1660 /* Generate code to do the reduce action */ 1661 if ($rp->code) { 1662 $this->tplt_linedir($out, $rp->line, $this->filename); 1663 fwrite($out, " function yy_r$rp->index(){" . $rp->code); 1664 $linecnt += count(explode("\n", $rp->code)) - 1; 1665 $lineno += 3 + $linecnt; 1666 fwrite($out, " }\n"); 1667 $this->tplt_linedir($out, $lineno, $this->outname); 1668 } /* End if( rp->code ) */ 1669 } 1670 1671 /** 1672 * Append text to a dynamically allocated string. If zText is 0 then 1673 * reset the string to be empty again. Always return the complete text 1674 * of the string (which is overwritten with each call). 1675 * 1676 * n bytes of zText are stored. If n==0 then all of zText is stored. 1677 * 1678 * If n==-1, then the previous character is overwritten. 1679 * @param string 1680 * @param int 1681 */ 1682 function append_str($zText, $n) 1683 { 1684 static $z = ''; 1685 $zInt = ''; 1686 1687 if ($zText === '') { 1688 $ret = $z; 1689 $z = ''; 1690 return $ret; 1691 } 1692 if ($n <= 0) { 1693 if ($n < 0) { 1694 if (!strlen($z)) { 1695 throw new Exception('z is zero-length'); 1696 } 1697 $z = substr($z, 0, strlen($z) - 1); 1698 if (!$z) { 1699 $z = ''; 1700 } 1701 } 1702 $n = strlen($zText); 1703 } 1704 $i = 0; 1705 $z .= substr($zText, 0, $n); 1706 return $z; 1707 } 1708 1709 /** 1710 * zCode is a string that is the action associated with a rule. Expand 1711 * the symbols in this string so that the refer to elements of the parser 1712 * stack. 1713 */ 1714 function translate_code(PHP_ParserGenerator_Rule $rp) 1715 { 1716 $lhsused = 0; /* True if the LHS element has been used */ 1717 $used = array(); /* True for each RHS element which is used */ 1718 1719 $this->append_str('', 0); 1720 for ($i = 0; $i < strlen($rp->code); $i++) { 1721 $cp = $rp->code[$i]; 1722 if (preg_match('/[A-Za-z]/', $cp) && 1723 ($i === 0 || (!preg_match('/[A-Za-z0-9_]/', $rp->code[$i - 1])))) { 1724 //*xp = 0; 1725 // previous line is in essence a temporary substr, so 1726 // we will simulate it 1727 $test = substr($rp->code, $i); 1728 preg_match('/[A-Za-z0-9_]+/', $test, $matches); 1729 $tempcp = $matches[0]; 1730 $j = strlen($tempcp) + $i; 1731 if ($rp->lhsalias && $tempcp == $rp->lhsalias) { 1732 $this->append_str("\$this->_retvalue", 0); 1733 $cp = $rp->code[$j]; 1734 $i = $j; 1735 $lhsused = 1; 1736 } else { 1737 for ($ii = 0; $ii < $rp->nrhs; $ii++) { 1738 if ($rp->rhsalias[$ii] && $tempcp == $rp->rhsalias[$ii]) { 1739 if ($rp->code[0] == '@') { 1740 /* If the argument is of the form @X then substitute 1741 ** the token number of X, not the value of X */ 1742 $this->append_str("\$this->yystack[\$this->yyidx + " . 1743 ($ii - $rp->nrhs + 1) . "]->major", -1); 1744 } else { 1745 $sp = $rp->rhs[$ii]; 1746 if ($sp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) { 1747 $dtnum = $sp->subsym[0]->dtnum; 1748 } else { 1749 $dtnum = $sp->dtnum; 1750 } 1751 $this->append_str("\$this->yystack[\$this->yyidx + " . 1752 ($ii - $rp->nrhs + 1) . "]->minor", 0); 1753 } 1754 $cp = $rp->code[$j]; 1755 $i = $j; 1756 $used[$ii] = 1; 1757 break; 1758 } 1759 } 1760 } 1761 } 1762 $this->append_str($cp, 1); 1763 } /* End loop */ 1764 1765 /* Check to make sure the LHS has been used */ 1766 if ($rp->lhsalias && !$lhsused) { 1767 PHP_ParserGenerator::ErrorMsg($this->filename, $rp->ruleline, 1768 "Label \"%s\" for \"%s(%s)\" is never used.", 1769 $rp->lhsalias, $rp->lhs->name, $rp->lhsalias); 1770 $this->errorcnt++; 1771 } 1772 1773 /* Generate destructor code for RHS symbols which are not used in the 1774 ** reduce code */ 1775 for($i = 0; $i < $rp->nrhs; $i++) { 1776 if ($rp->rhsalias[$i] && !isset($used[$i])) { 1777 PHP_ParserGenerator::ErrorMsg($this->filename, $rp->ruleline, 1778 "Label %s for \"%s(%s)\" is never used.", 1779 $rp->rhsalias[$i], $rp->rhs[$i]->name, $rp->rhsalias[$i]); 1780 $this->errorcnt++; 1781 } elseif ($rp->rhsalias[$i] == 0) { 1782 if ($rp->rhs[$i]->type == PHP_ParserGenerator_Symbol::TERMINAL) { 1783 $hasdestructor = $this->tokendest != 0; 1784 }else{ 1785 $hasdestructor = $this->vardest !== 0 || $rp->rhs[$i]->destructor !== 0; 1786 } 1787 if ($hasdestructor) { 1788 $this->append_str(" \$this->yy_destructor(" . 1789 ($rp->rhs[$i]->index) . ", \$this->yystack[\$this->yyidx + " . 1790 ($i - $rp->nrhs + 1) . "]->minor);\n", 0); 1791 } else { 1792 /* No destructor defined for this term */ 1793 } 1794 } 1795 } 1796 $cp = $this->append_str('', 0); 1797 $rp->code = $cp; 1798 } 1799 1800 /** 1801 * The following routine emits code for the destructor for the 1802 * symbol sp 1803 */ 1804 function emit_destructor_code($out, PHP_ParserGenerator_Symbol $sp, &$lineno) 1805// FILE *out; 1806// struct symbol *sp; 1807// struct lemon *lemp; 1808// int *lineno; 1809 { 1810 $cp = 0; 1811 1812 $linecnt = 0; 1813 if ($sp->type == PHP_ParserGenerator_Symbol::TERMINAL) { 1814 $cp = $this->tokendest; 1815 if ($cp === 0) { 1816 return; 1817 } 1818 $this->tplt_linedir($out, $this->tokendestln, $this->filename); 1819 fwrite($out, "{"); 1820 } elseif ($sp->destructor) { 1821 $cp = $sp->destructor; 1822 $this->tplt_linedir($out, $sp->destructorln, $this->filename); 1823 fwrite($out, "{"); 1824 } elseif ($this->vardest) { 1825 $cp = $this->vardest; 1826 if ($cp === 0) { 1827 return; 1828 } 1829 $this->tplt_linedir($out, $this->vardestln, $this->filename); 1830 fwrite($out, "{"); 1831 } else { 1832 throw new Exception('emit_destructor'); /* Cannot happen */ 1833 } 1834 for ($i = 0; $i < strlen($cp); $i++) { 1835 if ($cp[$i]=='$' && $cp[$i + 1]=='$' ) { 1836 fprintf($out, "(yypminor->yy%d)", $sp->dtnum); 1837 $i++; 1838 continue; 1839 } 1840 if ($cp[$i] == "\n") { 1841 $linecnt++; 1842 } 1843 fwrite($out, $cp[$i]); 1844 } 1845 $lineno += 3 + $linecnt; 1846 fwrite($out, "}\n"); 1847 $this->tplt_linedir($out, $lineno, $this->outname); 1848 } 1849 1850 /** 1851 * Compare to axset structures for sorting purposes 1852 */ 1853 static function axset_compare($a, $b) 1854 { 1855 return $b['nAction'] - $a['nAction']; 1856 } 1857} 1858