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

Source for file State.php

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