Source for file Data.php
Documentation is available at Data.php
* PHP_ParserGenerator, a php 5 parser generator.
* This is a direct port of the Lemon parser generator, found at
* {@link http://www.hwaci.com/sw/lemon/}
* Copyright (c) 2006, Gregory Beaver <cellog@php.net>
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the distribution.
* * Neither the name of the PHP_ParserGenerator nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
* @package PHP_ParserGenerator
* @author Gregory Beaver <cellog@php.net>
* @copyright 2006 Gregory Beaver
* @license http://www.opensource.org/licenses/bsd-license.php New BSD License
* @since File available since Release 0.1.0
* The state vector for the entire parser generator is recorded in
* @package PHP_ParserGenerator
* @author Gregory Beaver <cellog@php.net>
* @copyright 2006 Gregory Beaver
* @license http://www.opensource.org/licenses/bsd-license.php New BSD License
* @version @package_version@
* @since Class available since Release 0.1.0
* Used for terminal and non-terminal offsets into the action table
* when their default should be used instead
const NO_OFFSET = - 2147483647;
* Table of states sorted by state number
* @var array array of {@link PHP_ParserGenerator_State} objects
* @var PHP_ParserGenerator_Rule
* Number of terminal and nonterminal symbols
* Number of terminal symbols (tokens)
* Sorted array of pointers to symbols
* @var array array of {@link PHP_ParserGenerator_Symbol} objects
* @var PHP_ParserGenerator_Symbol
* Name of the generated parser
* Unused relic from the C version
* Type of terminal symbols in the parser stack
* Unused relic from the C version
* The default type of non-terminal symbols
* Name of the start symbol for the grammar
* Size of the parser stack
* This is 100 by default, but is set with the %stack_size directive
* Code to put at the start of the parser file
* This is set by the %include directive
* Line number for start of include code
* Code to put in the parser class
* This is set by the %include_class directive
* Line number for start of include code
* any extends/implements code
* This is set by the %declare_class directive
* Line number for class declaration code
* Line number for start of class declaration code
* Code to execute when a syntax error is seen
* This is set by the %syntax_error directive
* Line number for start of error code
* Code to execute on a stack overflow
* This is set by the %stack_overflow directive
* Line number for start of overflow code
* Code to execute on parser failure
* This is set by the %parse_failure directive
* Line number for start of failure code
* Code to execute when the parser acccepts (completes parsing)
* This is set by the %parse_accept directive
* Line number for the start of accept code
* Code appended to the generated file
* This is set by the %code directive
* Line number for the start of the extra code
* Code to execute to destroy token data
* This is set by the %token_destructor directive
* Line number for token destroyer code
* Code for the default non-terminal destructor
* This is set by the %default_destructor directive
* Line number for default non-terminal destructor code
* Name of the input file without its extension
* Name of the current output file
* A prefix added to token names
* Number of parsing conflicts
* Size of the parse tables
* Public only basis configurations
* True if any %fallback is seen in the grammer
/* Find a precedence symbol of every rule in the grammar.
* Those rules which have a precedence symbol coded in the input
* grammar using the "[symbol]" construct will already have the
* $rp->precsym field filled. Other rules take as their precedence
* symbol the first RHS symbol with a defined precedence. If there
* are not RHS symbols with a defined precedence, the precedence
* symbol field is left blank.
for ($rp = $this->rule; $rp; $rp = $rp->next) {
if ($rp->precsym === 0) {
for ($i = 0; $i < $rp->nrhs && $rp->precsym === 0; $i++ ) {
for ($j = 0; $j < $sp->nsubsym; $j++ ) {
if ($sp->subsym[$j]->prec >= 0) {
$rp->precsym = $sp->subsym[$j];
} elseif ($sp->prec >= 0) {
$rp->precsym = $rp->rhs[$i];
* Find all nonterminals which will generate the empty string.
* Then go back and compute the first sets of every nonterminal.
* The first set is the set of all terminal symbols which can begin
* a string generated by that nonterminal.
for ($i = 0; $i < $this->nsymbol; $i++ ) {
$this->symbols[$i]->lambda = false;
$this->symbols[$i]->firstset = array();
/* First compute all lambdas */
for ($rp = $this->rule; $rp; $rp = $rp->next) {
for ($i = 0; $i < $rp->nrhs; $i++ ) {
/* Now compute all first sets */
for ($rp = $this->rule; $rp; $rp = $rp->next) {
for ($i = 0; $i < $rp->nrhs; $i++ ) {
//progress += SetAdd(s1->firstset,s2->index);
$progress += isset ($s1->firstset[$s2->index]) ? 0 : 1;
$s1->firstset[$s2->index] = 1;
for ($j = 0; $j < $s2->nsubsym; $j++ ) {
//progress += SetAdd(s1->firstset,s2->subsym[j]->index);
$progress += isset ($s1->firstset[$s2->subsym[$j]->index]) ? 0 : 1;
$s1->firstset[$s2->subsym[$j]->index] = 1;
if ($s1->lambda === false) {
//progress += SetUnion(s1->firstset,s2->firstset);
if ($s2->lambda === false) {
* Compute all LR(0) states for the grammar. Links
* are added to between some states so that the LR(1) follow sets
/* Find the start symbol */
"The specified start symbol \"%s\" is not " .
"in a nonterminal of the grammar. \"%s\" will be used as the start " .
/* Make sure the start symbol doesn't occur on the right-hand side of
** any rule. Report an error if it does. (YACC would generate a new
** start symbol in this case.) */
for ($rp = $this->rule; $rp; $rp = $rp->next) {
for ($i = 0; $i < $rp->nrhs; $i++ ) {
foreach ($rp->rhs[$i]->subsym as $subsp) {
"The start symbol \"%s\" occurs on the " .
"right-hand side of a rule. This will result in a parser which " .
"does not work properly.", $sp->name);
} elseif ($rp->rhs[$i] === $sp) {
"The start symbol \"%s\" occurs on the " .
"right-hand side of a rule. This will result in a parser which " .
"does not work properly.", $sp->name);
/* The basis configuration set for the first state
** is all rules which have the start symbol as their
for ($rp = $sp->rule; $rp; $rp = $rp->nextlhs) {
/* Compute the first state. All other states will be
** computed automatically during the computation of the first one.
** The returned pointer to the first state is not used. */
$newstp = $this->getstate();
$this->buildshifts($newstp[0]); /* Recursively compute successor states */
* @return PHP_ParserGenerator_State
private function getstate()
/* Extract the sorted basis of the new state. The basis was constructed
** by prior calls to "Configlist_addbasis()". */
/* Get a state with the same basis */
/* A state with the same basis already exists! Copy all the follow-set
** propagation links from the state under construction into the
** preexisting state, then return a pointer to the preexisting state */
for($x = $bp, $y = $stp->bp; $x && $y; $x = $x->bp, $y = $y->bp) {
/* This really is a new state. Construct all the details */
$stp->bp = $bp; /* Remember the configuration basis */
$stp->cfp = $cfp; /* Remember the configuration closure */
$stp->statenum = $this->nstate++ ; /* Every state gets a sequence number */
$stp->ap = 0; /* No actions, yet. */
// this can't work, recursion is too deep, move it into FindStates()
//$this->buildshifts($stp); /* Recursively compute successor states */
* Construct all successor states to the given state. A "successor"
* state is any state which can be reached by a shift action.
* @param PHP_ParserGenerator_Data
* @param PHP_ParserGenerator_State The state from which successors are computed
|