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