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