[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  /** A configuration is a production rule of the grammar together with
  26   * a mark (dot) showing how much of that rule has been processed so far.
  27   * 
  28   * Configurations also contain a follow-set which is a list of terminal
  29   * symbols which are allowed to immediately follow the end of the rule.
  30   * Every configuration is recorded as an instance of the following class.
  31   * 
  32   * @package    PHP_ParserGenerator
  33   * @author     Gregory Beaver <[email protected]>
  34   * @copyright  2006 Gregory Beaver
  35   * @license    http://www.php.net/license/3_01.txt  PHP License 3.01
  36   * @version    0.1.0
  37   * @since      Class available since Release 0.1.0
  38   */
  39  class PHP_ParserGenerator_Config {
  40      const COMPLETE = 1;
  41      const INCOMPLETE = 2;
  42      /**
  43       * The parser rule upon with the configuration is based.
  44       * 
  45       * A parser rule is something like:
  46       * <pre>
  47       * blah ::= FOO bar.
  48       * </pre>
  49       * @var PHP_ParserGenerator_Rule
  50       */
  51      public $rp;
  52      /**
  53       * The parse point.
  54       *
  55       * This is the index into the right-hand side of a rule that is
  56       * represented by this configuration.  In other words, possible
  57       * dots for this rule:
  58       * 
  59       * <pre>
  60       * blah ::= FOO bar.
  61       * </pre>
  62       * 
  63       * are (represented by "[here]"):
  64       * 
  65       * <pre>
  66       * blah ::= [here] FOO bar.
  67       * blah ::= FOO [here] bar.
  68       * blah ::= FOO bar [here].
  69       * </pre>
  70       * @var int
  71       */
  72      public $dot;
  73      /**
  74       * Follow-set for this configuration only
  75       *
  76       * This is the list of terminals and non-terminals that
  77       * can follow this configuration.
  78       * @var array
  79       */
  80      public $fws;
  81      /**
  82       * Follow-set forward propagation links.
  83       * @var PHP_ParserGenerator_PropagationLink
  84       */
  85      public $fplp;
  86      /**
  87       * Follow-set backwards propagation links
  88       * @var PHP_ParserGenerator_PropagationLink
  89       */
  90      public $bplp;
  91      /**
  92       * State that contains this configuration
  93       * @var PHP_ParserGenerator_State
  94       */
  95      public $stp;
  96    /* enum {
  97      COMPLETE,              /* The status is used during followset and
  98      INCOMPLETE             /*    shift computations
  99    } */
 100      /**
 101       * Status during followset and shift computations.
 102       *
 103       * One of PHP_ParserGenerator_Config::COMPLETE or
 104       * PHP_ParserGenerator_Config::INCOMPLETE.
 105       * @var int
 106       */
 107      public $status;
 108      /**
 109       * Next configuration in the state.
 110       * 
 111       * Index of next PHP_ParserGenerator_Config object.
 112       * @var int
 113       */
 114      public $next;
 115      /**
 116       * Index of the next basis configuration PHP_ParserGenerator_Config object
 117       * @var int
 118       */
 119      public $bp;
 120  
 121      /**
 122       * Top of the list of configurations for the current state.
 123       * @var PHP_ParserGenerator_Config
 124       */
 125      static public $current;
 126      /**
 127       * Last on the list of configurations for the current state.
 128       * @var PHP_ParserGenerator_Config
 129       */
 130      static public $currentend;
 131  
 132      /**
 133       * Top of the list of basis configurations for the current state.
 134       * @var PHP_ParserGenerator_Config
 135       */
 136      static public $basis;
 137      /**
 138       * Last on the list of basis configurations for the current state.
 139       * @var PHP_ParserGenerator_Config
 140       */
 141      static public $basisend;
 142  
 143      /**
 144       * Associative array representation of the linked list of configurations
 145       * found in {@link $current}
 146       *
 147       * @var array
 148       */
 149      static public $x4a = array();
 150  
 151      /**
 152       * Return a pointer to a new configuration
 153       * @return PHP_ParserGenerator_Config
 154       */
 155      private static function newconfig()
 156      {
 157          return new PHP_ParserGenerator_Config;
 158      }
 159  
 160      /**
 161       * Display the current configuration for the .out file
 162       *
 163       * @param PHP_ParserGenerator_Config $cfp
 164       * @see PHP_ParserGenerator_Data::ReportOutput()
 165       */
 166      static function Configshow(PHP_ParserGenerator_Config $cfp)
 167      {
 168          $fp = fopen('php://output', 'w');
 169          while ($cfp) {
 170              if ($cfp->dot == $cfp->rp->nrhs) {
 171                  $buf = sprintf('(%d)', $cfp->rp->index);
 172                  fprintf($fp, '    %5s ', $buf);
 173              } else {
 174                  fwrite($fp,'          ');
 175              }
 176              $cfp->ConfigPrint($fp);
 177              fwrite($fp, "\n");
 178              if (0) {
 179                  //SetPrint(fp,cfp->fws,$this);
 180                  //PlinkPrint(fp,cfp->fplp,"To  ");
 181                  //PlinkPrint(fp,cfp->bplp,"From");
 182              }
 183              $cfp = $cfp->next;
 184          }
 185          fwrite($fp, "\n");
 186          fclose($fp);
 187      }
 188  
 189      /**
 190       * Initialize the configuration list builder for a new state.
 191       */
 192      static function Configlist_init()
 193      {
 194          self::$current = 0;
 195          self::$currentend = &self::$current;
 196          self::$basis = 0;
 197          self::$basisend = &self::$basis;
 198          self::$x4a = array();
 199      }
 200  
 201      /**
 202       * Remove all data from the table.
 203       * 
 204       * Pass each data to the function $f as it is removed if
 205       * $f is a valid callback.
 206       * @param callback|null
 207       * @see Configtable_clear()
 208       */
 209      static function Configtable_reset($f)
 210      {
 211          self::$current = 0;
 212          self::$currentend = &self::$current;
 213          self::$basis = 0;
 214          self::$basisend = &self::$basis;
 215          self::Configtable_clear(0);
 216      }
 217  
 218      /**
 219       * Remove all data from the associative array representation
 220       * of configurations.
 221       * 
 222       * Pass each data to the function $f as it is removed if
 223       * $f is a valid callback.
 224       * @param callback|null
 225       */
 226      static function Configtable_clear($f)
 227      {
 228          if (!count(self::$x4a)) {
 229              return;
 230          }
 231          if ($f) {
 232              for ($i = 0; $i < count(self::$x4a); $i++) {
 233                  call_user_func($f, self::$x4a[$i]->data);
 234              }
 235          }
 236          self::$x4a = array();
 237      }
 238  
 239      /**
 240       * Reset the configuration list builder for a new state.
 241       * @see Configtable_clear()
 242       */
 243      static function Configlist_reset()
 244      {
 245          self::Configtable_clear(0);
 246      }
 247  
 248      /**
 249       * Add another configuration to the configuration list for this parser state.
 250       * @param PHP_ParserGenerator_Rule the rule
 251       * @param int Index into the right-hand side of the rule where the dot goes
 252       * @return PHP_ParserGenerator_Config
 253       */
 254      static function Configlist_add($rp, $dot)
 255      {
 256          $model = new PHP_ParserGenerator_Config;
 257          $model->rp = $rp;
 258          $model->dot = $dot;
 259          $cfp = self::Configtable_find($model);
 260          if ($cfp === 0) {
 261              $cfp = self::newconfig();
 262              $cfp->rp = $rp;
 263              $cfp->dot = $dot;
 264              $cfp->fws = array();
 265              $cfp->stp = 0;
 266              $cfp->fplp = $cfp->bplp = 0;
 267              $cfp->next = 0;
 268              $cfp->bp = 0;
 269              self::$currentend = $cfp;
 270              self::$currentend = &$cfp->next;
 271              self::Configtable_insert($cfp);
 272          }
 273          return $cfp;
 274      }
 275  
 276      /**
 277       * Add a basis configuration to the configuration list for this parser state.
 278       * 
 279       * Basis configurations are the root for a configuration.  This method also
 280       * inserts the configuration into the regular list of configurations for this
 281       * reason.
 282       * @param PHP_ParserGenerator_Rule the rule
 283       * @param int Index into the right-hand side of the rule where the dot goes
 284       * @return PHP_ParserGenerator_Config
 285       */
 286      static function Configlist_addbasis($rp, $dot)
 287      {
 288          $model = new PHP_ParserGenerator_Config;
 289          $model->rp = $rp;
 290          $model->dot = $dot;
 291          $cfp = self::Configtable_find($model);
 292          if ($cfp === 0) {
 293              $cfp = self::newconfig();
 294              $cfp->rp = $rp;
 295              $cfp->dot = $dot;
 296              $cfp->fws = array();
 297              $cfp->stp = 0;
 298              $cfp->fplp = $cfp->bplp = 0;
 299              $cfp->next = 0;
 300              $cfp->bp = 0;
 301              self::$currentend = $cfp;
 302              self::$currentend = &$cfp->next;
 303              self::$basisend = $cfp;
 304              self::$basisend = &$cfp->bp;
 305              self::Configtable_insert($cfp);
 306          }
 307          return $cfp;
 308      }
 309  
 310      /**
 311       * Compute the closure of the configuration list.
 312       * 
 313       * This calculates all of the possible continuations of
 314       * each configuration, ensuring that each state accounts
 315       * for every configuration that could arrive at that state.
 316       */
 317      static function Configlist_closure(PHP_ParserGenerator_Data $lemp)
 318      {
 319          for ($cfp = self::$current; $cfp; $cfp = $cfp->next) {
 320              $rp = $cfp->rp;
 321              $dot = $cfp->dot;
 322              if ($dot >= $rp->nrhs) {
 323                  continue;
 324              }
 325              $sp = $rp->rhs[$dot];
 326              if ($sp->type == PHP_ParserGenerator_Symbol::NONTERMINAL) {
 327                  if ($sp->rule === 0 && $sp !== $lemp->errsym) {
 328                      PHP_ParserGenerator::ErrorMsg($lemp->filename, $rp->line,
 329                          "Nonterminal \"%s\" has no rules.", $sp->name);
 330                      $lemp->errorcnt++;
 331                  }
 332                  for ($newrp = $sp->rule; $newrp; $newrp = $newrp->nextlhs) {
 333                      $newcfp = self::Configlist_add($newrp, 0);
 334                      for ($i = $dot + 1; $i < $rp->nrhs; $i++) {
 335                          $xsp = $rp->rhs[$i];
 336                          if ($xsp->type == PHP_ParserGenerator_Symbol::TERMINAL) {
 337                              $newcfp->fws[$xsp->index] = 1;
 338                              break;
 339                          } elseif ($xsp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) {
 340                              for ($k = 0; $k < $xsp->nsubsym; $k++) {
 341                                  $newcfp->fws[$xsp->subsym[$k]->index] = 1;
 342                              }
 343                              break;
 344                          } else {
 345                              $a = array_diff_key($xsp->firstset, $newcfp->fws);
 346                              $newcfp->fws += $a;
 347                              if ($xsp->lambda === false) {
 348                                  break;
 349                              }
 350                          }
 351                      }
 352                      if ($i == $rp->nrhs) {
 353                          PHP_ParserGenerator_PropagationLink::Plink_add($cfp->fplp, $newcfp);
 354                      }
 355                  }
 356              }
 357          }
 358      }
 359  
 360      /**
 361       * Sort the configuration list
 362       * @uses Configcmp()
 363       */
 364      static function Configlist_sort()
 365      {
 366          $a = 0;
 367          //self::Configshow(self::$current);
 368          self::$current = PHP_ParserGenerator::msort(self::$current,'next', array('PHP_ParserGenerator_Config', 'Configcmp'));
 369          //self::Configshow(self::$current);
 370          self::$currentend = &$a;
 371          self::$currentend = 0;
 372      }
 373  
 374      /**
 375       * Sort the configuration list
 376       * @uses Configcmp
 377       */
 378      static function Configlist_sortbasis()
 379      {
 380          $a = 0;
 381          self::$basis = PHP_ParserGenerator::msort(self::$current,'bp', array('PHP_ParserGenerator_Config', 'Configcmp'));
 382          self::$basisend = &$a;
 383          self::$basisend = 0;
 384      }
 385  
 386      /**
 387       * Return a pointer to the head of the configuration list and
 388       * reset the list
 389       * @see $current
 390       * @return PHP_ParserGenerator_Config
 391       */
 392      static function Configlist_return()
 393      {
 394          $old = self::$current;
 395          self::$current = 0;
 396          self::$currentend = &self::$current;
 397          return $old;
 398      }
 399  
 400      /**
 401       * Return a pointer to the head of the basis list and
 402       * reset the list
 403       * @see $basis
 404       * @return PHP_ParserGenerator_Config
 405       */
 406      static function Configlist_basis()
 407      {
 408          $old = self::$basis;
 409          self::$basis = 0;
 410          self::$basisend = &self::$basis;
 411          return $old;
 412      }
 413  
 414      /**
 415       * Free all elements of the given configuration list
 416       * @param PHP_ParserGenerator_Config
 417       */
 418      static function Configlist_eat($cfp)
 419      {
 420          for(; $cfp; $cfp = $nextcfp){
 421              $nextcfp = $cfp->next;
 422              if ($cfp->fplp !=0) {
 423                  throw new Exception('fplp of configuration non-zero?');
 424              }
 425              if ($cfp->bplp !=0) {
 426                  throw new Exception('bplp of configuration non-zero?');
 427              }
 428              if ($cfp->fws) {
 429                  $cfp->fws = array();
 430              }
 431          }
 432      }
 433  
 434      /**
 435       * Compare two configurations for sorting purposes.
 436       *
 437       * Configurations based on higher precedence rules
 438       * (those earlier in the file) are chosen first.  Two
 439       * configurations that are the same rule are sorted by
 440       * dot (see {@link $dot}), and those configurations
 441       * with a dot closer to the left-hand side are chosen first.
 442       * @param unknown_type $a
 443       * @param unknown_type $b
 444       * @return unknown
 445       */
 446      static function Configcmp($a, $b)
 447      {
 448          $x = $a->rp->index - $b->rp->index;
 449          if (!$x) {
 450              $x = $a->dot - $b->dot;
 451          }
 452          return $x;
 453      }
 454  
 455      /**
 456       * Print out information on this configuration.
 457       *
 458       * @param resource $fp
 459       * @see PHP_ParserGenerator_Data::ReportOutput()
 460       */
 461      function ConfigPrint($fp)
 462      {
 463          $rp = $this->rp;
 464          fprintf($fp, "%s ::=", $rp->lhs->name);
 465          for ($i = 0; $i <= $rp->nrhs; $i++) {
 466              if ($i === $this->dot) {
 467                  fwrite($fp,' *');
 468              }
 469              if ($i === $rp->nrhs) {
 470                  break;
 471              }
 472              $sp = $rp->rhs[$i];
 473              fprintf($fp,' %s', $sp->name);
 474              if ($sp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) {
 475                  for ($j = 1; $j < $sp->nsubsym; $j++) {
 476                      fprintf($fp, '|%s', $sp->subsym[$j]->name);
 477                  }
 478              }
 479          }
 480      }
 481  
 482      /**
 483       * Hash a configuration for the associative array {@link $x4a}
 484       */
 485      private static function confighash(PHP_ParserGenerator_Config $a)
 486      {
 487          $h = 0;
 488          $h = $h * 571 + $a->rp->index * 37 + $a->dot;
 489          return $h;
 490      }
 491  
 492      /**
 493       * Insert a new record into the array.  Return TRUE if successful.
 494       * Prior data with the same key is NOT overwritten
 495       */
 496      static function Configtable_insert(PHP_ParserGenerator_Config $data)
 497      {
 498          $h = self::confighash($data);
 499          if (isset(self::$x4a[$h])) {
 500              $np = self::$x4a[$h];
 501          } else {
 502              $np = 0;
 503          }
 504          while ($np) {
 505              if (self::Configcmp($np->data, $data) == 0) {
 506                  /* An existing entry with the same key is found. */
 507                  /* Fail because overwrite is not allows. */
 508                  return 0;
 509              }
 510              $np = $np->next;
 511          }
 512          /* Insert the new data */
 513          $np = array('data' => $data, 'next' => 0, 'from' => 0);
 514          $np = new PHP_ParserGenerator_StateNode;
 515          $np->data = $data;
 516          if (isset(self::$x4a[$h])) {
 517              self::$x4a[$h]->from = $np->next;
 518              $np->next = self::$x4a[$h];
 519          }
 520          $np->from = $np;
 521          self::$x4a[$h] = $np;
 522          return 1;
 523      }
 524  
 525      /**
 526       * Return a pointer to data assigned to the given key.  Return NULL
 527       * if no such key.
 528       * @return PHP_ParserGenerator_Config|0
 529       */
 530      static function Configtable_find(PHP_ParserGenerator_Config $key)
 531      {
 532          $h = self::confighash($key);
 533          if (!isset(self::$x4a[$h])) {
 534              return 0;
 535          }
 536          $np = self::$x4a[$h];
 537          while ($np) {
 538              if (self::Configcmp($np->data, $key) == 0) {
 539                  break;
 540              }
 541              $np = $np->next;
 542          }
 543          return $np ? $np->data : 0;
 544      }
 545  }
 546  ?>