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