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

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

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