phpDocumentor PHP_ParserGenerator
[ class tree: PHP_ParserGenerator ] [ index: PHP_ParserGenerator ] [ all elements ]
PHP_ParserGenerator
Packages:
PHP_ParserGenerator

Source for file ActionTable.php

Documentation is available at ActionTable.php

  1. <?php
  2. /**
  3.  * PHP_ParserGenerator, a php 5 parser generator.
  4.  * 
  5.  * This is a direct port of the Lemon parser generator, found at
  6.  * {@link http://www.hwaci.com/sw/lemon/}
  7.  *
  8.  * PHP version 5
  9.  *
  10.  * LICENSE:
  11.  * 
  12.  * Copyright (c) 2006, Gregory Beaver <cellog@php.net>
  13.  * All rights reserved.
  14.  *
  15.  * Redistribution and use in source and binary forms, with or without
  16.  * modification, are permitted provided that the following conditions
  17.  * are met:
  18.  *
  19.  *     * Redistributions of source code must retain the above copyright
  20.  *       notice, this list of conditions and the following disclaimer.
  21.  *     * Redistributions in binary form must reproduce the above copyright
  22.  *       notice, this list of conditions and the following disclaimer in
  23.  *       the documentation and/or other materials provided with the distribution.
  24.  *     * Neither the name of the PHP_ParserGenerator nor the names of its
  25.  *       contributors may be used to endorse or promote products derived
  26.  *       from this software without specific prior written permission.
  27.  *
  28.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
  29.  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  30.  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  31.  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  32.  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  33.  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  34.  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  35.  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  36.  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  37.  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  38.  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39.  *
  40.  * @category   php
  41.  * @package    PHP_ParserGenerator
  42.  * @author     Gregory Beaver <cellog@php.net>
  43.  * @copyright  2006 Gregory Beaver
  44.  * @license    http://www.opensource.org/licenses/bsd-license.php New BSD License
  45.  * @version    CVS: $Id$
  46.  * @since      File available since Release 0.1.0
  47.  */
  48. /**
  49.  * The state of the yy_action table under construction is an instance of
  50.  * the following structure
  51.  * @package    PHP_ParserGenerator
  52.  * @author     Gregory Beaver <cellog@php.net>
  53.  * @copyright  2006 Gregory Beaver
  54.  * @license    http://www.opensource.org/licenses/bsd-license.php New BSD License
  55.  * @version    @package_version@
  56.  * @since      Class available since Release 0.1.0
  57.  */
  58. class PHP_ParserGenerator_ActionTable
  59. {
  60.     /**
  61.      * Number of used slots in {@link $aAction}
  62.      * @var int 
  63.      */
  64.     public $nAction = 0;
  65.     /**
  66.      * The $yy_action table under construction.
  67.      * 
  68.      * Each entry is of format:
  69.      * <code>
  70.      *  array(
  71.      *      'lookahead' => -1, // Value of the lookahead token (symbol index)
  72.      *      'action' => -1     // Action to take on the given lookahead (action index)
  73.      *  );
  74.      * </code>
  75.      * @see PHP_ParserGenerator_Data::compute_action()
  76.      * @var array 
  77.      */
  78.     public $aAction =
  79.         array(array(
  80.             'lookahead' => -1,
  81.             'action' => -1
  82.         ));
  83.     /**
  84.      * A single new transaction set.
  85.      *
  86.      * @see $aAction format of the internal array is described here
  87.      * @var array 
  88.      */
  89.     public $aLookahead =
  90.         array(array(
  91.             'lookahead' => 0,
  92.             'action' => 0
  93.         ));
  94.     /**
  95.      * The smallest (minimum) value of any lookahead token in {@link $aLookahead}
  96.      * 
  97.      * The lowest non-terminal is always introduced earlier in the parser file,
  98.      * and is therefore a more significant token.
  99.      * @var int 
  100.      */
  101.     public $mnLookahead = 0;
  102.     /**
  103.      * The action associated with the smallest lookahead token.
  104.      * @see $mnLookahead
  105.      * @var int 
  106.      */
  107.     public $mnAction = 0;
  108.     /**
  109.      * The largest (maximum) value of any lookahead token in {@link $aLookahead}
  110.      * @var int 
  111.      */
  112.     public $mxLookahead = 0;
  113.     /**
  114.      * The number of slots used in {@link $aLookahead}.
  115.      * 
  116.      * This is the same as count($aLookahead), but there was no pressing reason
  117.      * to change this when porting from C.
  118.      * @see $mnLookahead
  119.      * @var int 
  120.      */
  121.     public $nLookahead = 0;
  122.  
  123.     /**
  124.      * Add a new action to the current transaction set
  125.      * @param int 
  126.      * @param int 
  127.      */
  128.     function acttab_action($lookahead, $action)
  129.     {
  130.         if ($this->nLookahead === 0) {
  131.             $this->aLookahead = array();
  132.             $this->mxLookahead = $lookahead;
  133.             $this->mnLookahead = $lookahead;
  134.             $this->mnAction = $action;
  135.         } else {
  136.             if ($this->mxLookahead < $lookahead) {
  137.                 $this->mxLookahead = $lookahead;
  138.             }
  139.             if ($this->mnLookahead > $lookahead) {
  140.                 $this->mnLookahead = $lookahead;
  141.                 $this->mnAction = $action;
  142.             }
  143.         }
  144.         $this->aLookahead[$this->nLookahead] = array(
  145.             'lookahead' => $lookahead,
  146.             'action' => $action);
  147.         $this->nLookahead++;
  148.     }
  149.  
  150.     /**
  151.      * Add the transaction set built up with prior calls to acttab_action()
  152.      * into the current action table.  Then reset the transaction set back
  153.      * to an empty set in preparation for a new round of acttab_action() calls.
  154.      *
  155.      * Return the offset into the action table of the new transaction.
  156.      * @return int Return the offset that should be added to the lookahead in
  157.      *  order to get the index into $yy_action of the action.  This will be used
  158.      *  in generation of $yy_ofst tables (reduce and shift)
  159.      * @throws Exception
  160.      */
  161.     function acttab_insert()
  162.     {
  163.         if ($this->nLookahead <= 0) {
  164.             throw new Exception('nLookahead is not set up?');
  165.         }
  166.     
  167.         /* Scan the existing action table looking for an offset where we can
  168.         ** insert the current transaction set.  Fall out of the loop when that
  169.         ** offset is found.  In the worst case, we fall out of the loop when
  170.         ** i reaches $this->nAction, which means we append the new transaction set.
  171.         **
  172.         ** i is the index in $this->aAction[] where $this->mnLookahead is inserted.
  173.         */
  174.         for ($i = 0; $i < $this->nAction + $this->mnLookahead; $i++) {
  175.             if (!isset($this->aAction[$i])) {
  176.                 $this->aAction[$i] = array(
  177.                     'lookahead' => -1,
  178.                     'action' => -1,
  179.                 );
  180.             }
  181.             if ($this->aAction[$i]['lookahead'] < 0) {
  182.                 for ($j = 0; $j < $this->nLookahead; $j++) {
  183.                     if (!isset($this->aLookahead[$j])) {
  184.                         $this->aLookahead[$j] = array(
  185.                             'lookahead' => 0,
  186.                             'action' => 0,
  187.                         );
  188.                     }
  189.                     $k = $this->aLookahead[$j]['lookahead'] -
  190.                         $this->mnLookahead + $i;
  191.                     if ($k < 0) {
  192.                         break;
  193.                     }
  194.                     if (!isset($this->aAction[$k])) {
  195.                         $this->aAction[$k] = array(
  196.                             'lookahead' => -1,
  197.                             'action' => -1,
  198.                         );
  199.                     }
  200.                     if ($this->aAction[$k]['lookahead'] >= 0) {
  201.                         break;
  202.                     }
  203.                 }
  204.                 if ($j < $this->nLookahead ) {
  205.                     continue;
  206.                 }
  207.                 for ($j = 0; $j < $this->nAction; $j++) {
  208.                     if (!isset($this->aAction[$j])) {
  209.                         $this->aAction[$j] = array(
  210.                             'lookahead' => -1,
  211.                             'action' => -1,
  212.                         );
  213.                     }
  214.                     if ($this->aAction[$j]['lookahead'] == $j +
  215.                           $this->mnLookahead - $i) {
  216.                         break;
  217.                     }
  218.                 }
  219.                 if ($j == $this->nAction) {
  220.                     break;  /* Fits in empty slots */
  221.                 }
  222.             } elseif ($this->aAction[$i]['lookahead'] == $this->mnLookahead) {
  223.                 if ($this->aAction[$i]['action'] != $this->mnAction) {
  224.                     continue;
  225.                 }
  226.                 for ($j = 0; $j < $this->nLookahead; $j++) {
  227.                     $k = $this->aLookahead[$j]['lookahead'] -
  228.                         $this->mnLookahead + $i;
  229.                     if ($k < 0 || $k >= $this->nAction) {
  230.                         break;
  231.                     }
  232.                     if (!isset($this->aAction[$k])) {
  233.                         $this->aAction[$k] = array(
  234.                             'lookahead' => -1,
  235.                             'action' => -1,
  236.                         );
  237.                     }
  238.                     if ($this->aLookahead[$j]['lookahead'] != 
  239.                           $this->aAction[$k]['lookahead']) {
  240.                         break;
  241.                     }
  242.                     if ($this->aLookahead[$j]['action'] !=
  243.                           $this->aAction[$k]['action']) {
  244.                         break;
  245.                     }
  246.                 }
  247.                 if ($j < $this->nLookahead) {
  248.                     continue;
  249.                 }
  250.                 $n = 0;
  251.                 for ($j = 0; $j < $this->nAction; $j++) {
  252.                     if (!isset($this->aAction[$j])) {
  253.                         $this->aAction[$j] = array(
  254.                             'lookahead' => -1,
  255.                             'action' => -1,
  256.                         );
  257.                     }
  258.                     if ($this->aAction[$j]['lookahead'] < 0) {
  259.                         continue;
  260.                     }
  261.                     if ($this->aAction[$j]['lookahead'] == $j +
  262.                           $this->mnLookahead - $i) {
  263.                         $n++;
  264.                     }
  265.                 }
  266.                 if ($n == $this->nLookahead) {
  267.                     break;  /* Same as a prior transaction set */
  268.                 }
  269.             }
  270.         }
  271.         /* Insert transaction set at index i. */
  272.         for ($j = 0; $j < $this->nLookahead; $j++) {
  273.             if (!isset($this->aLookahead[$j])) {
  274.                 $this->aLookahead[$j] = array(
  275.                     'lookahead' => 0,
  276.                     'action' => 0,
  277.                 );
  278.             }
  279.             $k = $this->aLookahead[$j]['lookahead'] - $this->mnLookahead + $i;
  280.             $this->aAction[$k] = $this->aLookahead[$j];
  281.             if ($k >= $this->nAction) {
  282.                 $this->nAction = $k + 1;
  283.             }
  284.         }
  285.         $this->nLookahead = 0;
  286.         $this->aLookahead = array();
  287.  
  288.         /* Return the offset that is added to the lookahead in order to get the
  289.         ** index into yy_action of the action */
  290.         return $i - $this->mnLookahead;
  291.     }
  292. }
  293. ?>
Documentation generated on Sun, 02 Jul 2006 09:10:57 -0400 by phpDocumentor 1.3.0