[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 structure used to represent a state in the associative array
  27   * for a PHP_ParserGenerator_Config.
  28   * @package    PHP_ParserGenerator
  29   * @author     Gregory Beaver <[email protected]>
  30   * @copyright  2006 Gregory Beaver
  31   * @license    http://www.php.net/license/3_01.txt  PHP License 3.01
  32   * @version    0.1.0
  33   * @since      Class available since Release 0.1.0
  34   */
  35  class PHP_ParserGenerator_StateNode
  36  {
  37      public $key;
  38      public $data;
  39      public $from = 0;
  40      public $next = 0;
  41  }
  42  
  43  /**
  44   * Each state of the generated parser's finite state machine
  45   * is encoded as an instance of this class
  46   * 
  47   * @package    PHP_ParserGenerator
  48   * @author     Gregory Beaver <[email protected]>
  49   * @copyright  2006 Gregory Beaver
  50   * @license    http://www.php.net/license/3_01.txt  PHP License 3.01
  51   * @version    0.1.0
  52   * @since      Class available since Release 0.1.0
  53   */
  54  class PHP_ParserGenerator_State {
  55      /**
  56       * The basis configurations for this state
  57       * @var PHP_ParserGenerator_Config
  58       */
  59      public $bp;
  60      /**
  61       * All configurations in this state
  62       * @var PHP_ParserGenerator_Config
  63       */
  64      public $cfp;
  65      /**
  66       * Sequential number for this state
  67       *
  68       * @var int
  69       */
  70      public $statenum;
  71      /**
  72       * Linked list of actions for this state.
  73       * @var PHP_ParserGenerator_Action
  74       */
  75      public $ap;
  76      /**
  77       * Number of terminal (token) actions
  78       *
  79       * @var int
  80       */
  81      public $nTknAct,
  82      /**
  83       * Number of non-terminal actions
  84       *
  85       * @var int
  86       */
  87      $nNtAct;
  88      /**
  89       * The offset into the $yy_action table for terminal tokens.
  90       *
  91       * @var int
  92       */
  93      public $iTknOfst,
  94      /**
  95       * The offset into the $yy_action table for non-terminals.
  96       *
  97       * @var int
  98       */
  99      $iNtOfst;
 100      /**
 101       * Default action
 102       *
 103       * @var int
 104       */
 105      public $iDflt;
 106      /**
 107       * Associative array of PHP_ParserGenerator_State objects
 108       *
 109       * @var array
 110       */
 111      public static $x3a = array();
 112      /**
 113       * Array of PHP_ParserGenerator_State objects
 114       *
 115       * @var array
 116       */
 117      public static $states = array();
 118  
 119      /**
 120       * Compare two states for sorting purposes.  The smaller state is the
 121       * one with the most non-terminal actions.  If they have the same number
 122       * of non-terminal actions, then the smaller is the one with the most
 123       * token actions.
 124       */
 125      static function stateResortCompare($a, $b)
 126      {
 127          $n = $b->nNtAct - $a->nNtAct;
 128          if ($n === 0) {
 129              $n = $b->nTknAct - $a->nTknAct;
 130          }
 131          return $n;
 132      }
 133  
 134      /**
 135       * Compare two states based on their configurations
 136       *
 137       * @param PHP_ParserGenerator_Config|0 $a
 138       * @param PHP_ParserGenerator_Config|0 $b
 139       * @return int
 140       */
 141      static function statecmp($a, $b)
 142      {
 143          for ($rc = 0; $rc == 0 && $a && $b;  $a = $a->bp, $b = $b->bp) {
 144              $rc = $a->rp->index - $b->rp->index;
 145              if ($rc === 0) {
 146                  $rc = $a->dot - $b->dot;
 147              }
 148          }
 149          if ($rc == 0) {
 150              if ($a) {
 151                  $rc = 1;
 152              }
 153              if ($b) {
 154                  $rc = -1;
 155              }
 156          }
 157          return $rc;
 158      }
 159  
 160      /**
 161       * Hash a state based on its configuration
 162       * @return int
 163       */
 164      private static function statehash(PHP_ParserGenerator_Config $a)
 165      {
 166          $h = 0;
 167          while ($a) {
 168              $h = $h * 571 + $a->rp->index * 37 + $a->dot;
 169              $a = $a->bp;
 170          }
 171          return (int) $h;
 172      }
 173  
 174      /**
 175       * Return a pointer to data assigned to the given key.  Return NULL
 176       * if no such key.
 177       * @param PHP_ParserGenerator_Config
 178       * @return null|PHP_ParserGenerator_State
 179       */
 180      static function State_find(PHP_ParserGenerator_Config $key)
 181      {
 182          if (!count(self::$x3a)) {
 183              return 0;
 184          }
 185          $h = self::statehash($key);
 186          if (!isset(self::$x3a[$h])) {
 187              return 0;
 188          }
 189          $np = self::$x3a[$h];
 190          while ($np) {
 191              if (self::statecmp($np->key, $key) == 0) {
 192                  break;
 193              }
 194              $np = $np->next;
 195          }
 196          return $np ? $np->data : 0;
 197      }
 198  
 199      /**
 200       * Insert a new record into the array.  Return TRUE if successful.
 201       * Prior data with the same key is NOT overwritten
 202       *
 203       * @param PHP_ParserGenerator_State $state
 204       * @param PHP_ParserGenerator_Config $key
 205       * @return unknown
 206       */
 207      static function State_insert(PHP_ParserGenerator_State $state,
 208                                   PHP_ParserGenerator_Config $key)
 209      {
 210          $h = self::statehash($key);
 211          if (isset(self::$x3a[$h])) {
 212              $np = self::$x3a[$h];
 213          } else {
 214              $np = 0;
 215          }
 216          while ($np) {
 217              if (self::statecmp($np->key, $key) == 0) {
 218                  /* An existing entry with the same key is found. */
 219                  /* Fail because overwrite is not allows. */
 220                  return 0;
 221              }
 222              $np = $np->next;
 223          }
 224          /* Insert the new data */
 225          $np = new PHP_ParserGenerator_StateNode;
 226          $np->key = $key;
 227          $np->data = $state;
 228          self::$states[] = $np;
 229          // the original lemon code sets the from link always to itself
 230          // setting up a faulty double-linked list
 231          // however, the from links are never used, so I suspect a copy/paste
 232          // error from a standard algorithm that was never caught
 233          if (isset(self::$x3a[$h])) {
 234              self::$x3a[$h]->from = $np; // lemon has $np->next here
 235          } else {
 236              self::$x3a[$h] = 0; // dummy to avoid notice
 237          }
 238          $np->next = self::$x3a[$h];
 239          self::$x3a[$h] = $np;
 240          $np->from = self::$x3a[$h];
 241          return 1;
 242      }
 243  
 244      /**
 245       * Get an array indexed by state number
 246       *
 247       * @return array
 248       */
 249      static function State_arrayof()
 250      {
 251          return self::$states;
 252      }
 253  }