[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   * The state of the yy_action table under construction is an instance of
  26   * the following structure
  27   * @package    PHP_ParserGenerator
  28   * @author     Gregory Beaver <[email protected]>
  29   * @copyright  2006 Gregory Beaver
  30   * @license    http://www.php.net/license/3_01.txt  PHP License 3.01
  31   * @version    0.1.0
  32   * @since      Class available since Release 0.1.0
  33   */
  34  class PHP_ParserGenerator_ActionTable
  35  {
  36      /**
  37       * Number of used slots in {@link $aAction}
  38       * @var int
  39       */
  40      public $nAction = 0;
  41      /**
  42       * The $yy_action table under construction.
  43       * 
  44       * Each entry is of format:
  45       * <code>
  46       *  array(
  47       *      'lookahead' => -1, // Value of the lookahead token (symbol index)
  48       *      'action' => -1     // Action to take on the given lookahead (action index)
  49       *  );
  50       * </code>
  51       * @see PHP_ParserGenerator_Data::compute_action()
  52       * @var array
  53       */
  54      public $aAction =
  55          array(array(
  56              'lookahead' => -1,
  57              'action' => -1
  58          ));
  59      /**
  60       * A single new transaction set.
  61       *
  62       * @see $aAction format of the internal array is described here
  63       * @var array
  64       */
  65      public $aLookahead =
  66          array(array(
  67              'lookahead' => 0,
  68              'action' => 0
  69          ));
  70      /**
  71       * The smallest (minimum) value of any lookahead token in {@link $aLookahead}
  72       * 
  73       * The lowest non-terminal is always introduced earlier in the parser file,
  74       * and is therefore a more significant token.
  75       * @var int
  76       */
  77      public $mnLookahead = 0;
  78      /**
  79       * The action associated with the smallest lookahead token.
  80       * @see $mnLookahead
  81       * @var int
  82       */
  83      public $mnAction = 0;
  84      /**
  85       * The largest (maximum) value of any lookahead token in {@link $aLookahead}
  86       * @var int
  87       */
  88      public $mxLookahead = 0;
  89      /**
  90       * The number of slots used in {@link $aLookahead}.
  91       * 
  92       * This is the same as count($aLookahead), but there was no pressing reason
  93       * to change this when porting from C.
  94       * @see $mnLookahead
  95       * @var int
  96       */
  97      public $nLookahead = 0;
  98  
  99      /**
 100       * Add a new action to the current transaction set
 101       * @param int
 102       * @param int
 103       */
 104      function acttab_action($lookahead, $action)
 105      {
 106          if ($this->nLookahead === 0) {
 107              $this->aLookahead = array();
 108              $this->mxLookahead = $lookahead;
 109              $this->mnLookahead = $lookahead;
 110              $this->mnAction = $action;
 111          } else {
 112              if ($this->mxLookahead < $lookahead) {
 113                  $this->mxLookahead = $lookahead;
 114              }
 115              if ($this->mnLookahead > $lookahead) {
 116                  $this->mnLookahead = $lookahead;
 117                  $this->mnAction = $action;
 118              }
 119          }
 120          $this->aLookahead[$this->nLookahead] = array(
 121              'lookahead' => $lookahead,
 122              'action' => $action);
 123          $this->nLookahead++;
 124      }
 125  
 126      /**
 127       * Add the transaction set built up with prior calls to acttab_action()
 128       * into the current action table.  Then reset the transaction set back
 129       * to an empty set in preparation for a new round of acttab_action() calls.
 130       *
 131       * Return the offset into the action table of the new transaction.
 132       * @return int Return the offset that should be added to the lookahead in
 133       * order to get the index into $yy_action of the action.  This will be used
 134       * in generation of $yy_ofst tables (reduce and shift)
 135       * @throws Exception
 136       */
 137      function acttab_insert()
 138      {
 139          if ($this->nLookahead <= 0) {
 140              throw new Exception('nLookahead is not set up?');
 141          }
 142      
 143          /* Scan the existing action table looking for an offset where we can
 144          ** insert the current transaction set.  Fall out of the loop when that
 145          ** offset is found.  In the worst case, we fall out of the loop when
 146          ** i reaches $this->nAction, which means we append the new transaction set.
 147          **
 148          ** i is the index in $this->aAction[] where $this->mnLookahead is inserted.
 149          */
 150          for ($i = 0; $i < $this->nAction + $this->mnLookahead; $i++) {
 151              if (!isset($this->aAction[$i])) {
 152                  $this->aAction[$i] = array(
 153                      'lookahead' => -1,
 154                      'action' => -1,
 155                  );
 156              }
 157              if ($this->aAction[$i]['lookahead'] < 0) {
 158                  for ($j = 0; $j < $this->nLookahead; $j++) {
 159                      if (!isset($this->aLookahead[$j])) {
 160                          $this->aLookahead[$j] = array(
 161                              'lookahead' => 0,
 162                              'action' => 0,
 163                          );
 164                      }
 165                      $k = $this->aLookahead[$j]['lookahead'] -
 166                          $this->mnLookahead + $i;
 167                      if ($k < 0) {
 168                          break;
 169                      }
 170                      if (!isset($this->aAction[$k])) {
 171                          $this->aAction[$k] = array(
 172                              'lookahead' => -1,
 173                              'action' => -1,
 174                          );
 175                      }
 176                      if ($this->aAction[$k]['lookahead'] >= 0) {
 177                          break;
 178                      }
 179                  }
 180                  if ($j < $this->nLookahead ) {
 181                      continue;
 182                  }
 183                  for ($j = 0; $j < $this->nAction; $j++) {
 184                      if (!isset($this->aAction[$j])) {
 185                          $this->aAction[$j] = array(
 186                              'lookahead' => -1,
 187                              'action' => -1,
 188                          );
 189                      }
 190                      if ($this->aAction[$j]['lookahead'] == $j +
 191                            $this->mnLookahead - $i) {
 192                          break;
 193                      }
 194                  }
 195                  if ($j == $this->nAction) {
 196                      break;  /* Fits in empty slots */
 197                  }
 198              } elseif ($this->aAction[$i]['lookahead'] == $this->mnLookahead) {
 199                  if ($this->aAction[$i]['action'] != $this->mnAction) {
 200                      continue;
 201                  }
 202                  for ($j = 0; $j < $this->nLookahead; $j++) {
 203                      $k = $this->aLookahead[$j]['lookahead'] -
 204                          $this->mnLookahead + $i;
 205                      if ($k < 0 || $k >= $this->nAction) {
 206                          break;
 207                      }
 208                      if (!isset($this->aAction[$k])) {
 209                          $this->aAction[$k] = array(
 210                              'lookahead' => -1,
 211                              'action' => -1,
 212                          );
 213                      }
 214                      if ($this->aLookahead[$j]['lookahead'] != 
 215                            $this->aAction[$k]['lookahead']) {
 216                          break;
 217                      }
 218                      if ($this->aLookahead[$j]['action'] !=
 219                            $this->aAction[$k]['action']) {
 220                          break;
 221                      }
 222                  }
 223                  if ($j < $this->nLookahead) {
 224                      continue;
 225                  }
 226                  $n = 0;
 227                  for ($j = 0; $j < $this->nAction; $j++) {
 228                      if (!isset($this->aAction[$j])) {
 229                          $this->aAction[$j] = array(
 230                              'lookahead' => -1,
 231                              'action' => -1,
 232                          );
 233                      }
 234                      if ($this->aAction[$j]['lookahead'] < 0) {
 235                          continue;
 236                      }
 237                      if ($this->aAction[$j]['lookahead'] == $j +
 238                            $this->mnLookahead - $i) {
 239                          $n++;
 240                      }
 241                  }
 242                  if ($n == $this->nLookahead) {
 243                      break;  /* Same as a prior transaction set */
 244                  }
 245              }
 246          }
 247          /* Insert transaction set at index i. */
 248          for ($j = 0; $j < $this->nLookahead; $j++) {
 249              if (!isset($this->aLookahead[$j])) {
 250                  $this->aLookahead[$j] = array(
 251                      'lookahead' => 0,
 252                      'action' => 0,
 253                  );
 254              }
 255              $k = $this->aLookahead[$j]['lookahead'] - $this->mnLookahead + $i;
 256              $this->aAction[$k] = $this->aLookahead[$j];
 257              if ($k >= $this->nAction) {
 258                  $this->nAction = $k + 1;
 259              }
 260          }
 261          $this->nLookahead = 0;
 262          $this->aLookahead = array();
 263  
 264          /* Return the offset that is added to the lookahead in order to get the
 265          ** index into yy_action of the action */
 266          return $i - $this->mnLookahead;
 267      }
 268  }
 269  ?>