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