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

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

Documentation generated on Sun, 02 Jul 2006 09:10:57 -0400 by phpDocumentor 1.3.0