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

Source for file Config.php

Documentation is available at Config.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. /** A configuration is a production rule of the grammar together with
  50.  * a mark (dot) showing how much of that rule has been processed so far.
  51.  * 
  52.  * Configurations also contain a follow-set which is a list of terminal
  53.  * symbols which are allowed to immediately follow the end of the rule.
  54.  * Every configuration is recorded as an instance of the following class.
  55.  * 
  56.  * @package    PHP_ParserGenerator
  57.  * @author     Gregory Beaver <cellog@php.net>
  58.  * @copyright  2006 Gregory Beaver
  59.  * @license    http://www.opensource.org/licenses/bsd-license.php New BSD License
  60.  * @version    @package_version@
  61.  * @since      Class available since Release 0.1.0
  62.  */
  63.     const COMPLETE 1;
  64.     const INCOMPLETE 2;
  65.     /**
  66.      * The parser rule upon with the configuration is based.
  67.      * 
  68.      * A parser rule is something like:
  69.      * <pre>
  70.      * blah ::= FOO bar.
  71.      * </pre>
  72.      * @var PHP_ParserGenerator_Rule 
  73.      */
  74.     public $rp;
  75.     /**
  76.      * The parse point.
  77.      *
  78.      * This is the index into the right-hand side of a rule that is
  79.      * represented by this configuration.  In other words, possible
  80.      * dots for this rule:
  81.      * 
  82.      * <pre>
  83.      * blah ::= FOO bar.
  84.      * </pre>
  85.      * 
  86.      * are (represented by "[here]"):
  87.      * 
  88.      * <pre>
  89.      * blah ::= [here] FOO bar.
  90.      * blah ::= FOO [here] bar.
  91.      * blah ::= FOO bar [here].
  92.      * </pre>
  93.      * @var int 
  94.      */
  95.     public $dot;
  96.     /**
  97.      * Follow-set for this configuration only
  98.      *
  99.      * This is the list of terminals and non-terminals that
  100.      * can follow this configuration.
  101.      * @var array 
  102.      */
  103.     public $fws;
  104.     /**
  105.      * Follow-set forward propagation links.
  106.      * @var PHP_ParserGenerator_PropagationLink 
  107.      */
  108.     public $fplp;
  109.     /**
  110.      * Follow-set backwards propagation links
  111.      * @var PHP_ParserGenerator_PropagationLink 
  112.      */
  113.     public $bplp;
  114.     /**
  115.      * State that contains this configuration
  116.      * @var PHP_ParserGenerator_State 
  117.      */
  118.     public $stp;
  119.   /* enum {
  120.     COMPLETE,              /* The status is used during followset and
  121.     INCOMPLETE             /*    shift computations
  122.   } */
  123.     /**
  124.      * Status during followset and shift computations.
  125.      *
  126.      * One of PHP_ParserGenerator_Config::COMPLETE or
  127.      * PHP_ParserGenerator_Config::INCOMPLETE.
  128.      * @var int 
  129.      */
  130.     public $status;
  131.     /**
  132.      * Next configuration in the state.
  133.      * 
  134.      * Index of next PHP_ParserGenerator_Config object.
  135.      * @var int 
  136.      */
  137.     public $next;
  138.     /**
  139.      * Index of the next basis configuration PHP_ParserGenerator_Config object
  140.      * @var int 
  141.      */
  142.     public $bp;
  143.  
  144.     /**
  145.      * Top of the list of configurations for the current state.
  146.      * @var PHP_ParserGenerator_Config 
  147.      */
  148.     static public $current;
  149.     /**
  150.      * Last on the list of configurations for the current state.
  151.      * @var PHP_ParserGenerator_Config 
  152.      */
  153.     static public $currentend;
  154.  
  155.     /**
  156.      * Top of the list of basis configurations for the current state.
  157.      * @var PHP_ParserGenerator_Config 
  158.      */
  159.     static public $basis;
  160.     /**
  161.      * Last on the list of basis configurations for the current state.
  162.      * @var PHP_ParserGenerator_Config 
  163.      */
  164.     static public $basisend;
  165.  
  166.     /**
  167.      * Associative array representation of the linked list of configurations
  168.      * found in {@link $current}
  169.      *
  170.      * @var array 
  171.      */
  172.     static public $x4a = array();
  173.  
  174.     /**
  175.      * Return a pointer to a new configuration
  176.      * @return PHP_ParserGenerator_Config 
  177.      */
  178.     private static function newconfig()
  179.     {
  180.         return new PHP_ParserGenerator_Config;
  181.     }
  182.  
  183.     /**
  184.      * Display the current configuration for the .out file
  185.      *
  186.      * @param PHP_ParserGenerator_Config $cfp 
  187.      * @see PHP_ParserGenerator_Data::ReportOutput()
  188.      */
  189.     static function Configshow(PHP_ParserGenerator_Config $cfp)
  190.     {
  191.         $fp fopen('php://output''w');
  192.         while ($cfp{
  193.             if ($cfp->dot == $cfp->rp->nrhs{
  194.                 $buf sprintf('(%d)'$cfp->rp->index);
  195.                 fprintf($fp'    %5s '$buf);
  196.             else {
  197.                 fwrite($fp,'          ');
  198.             }
  199.             $cfp->ConfigPrint($fp);
  200.             fwrite($fp"\n");
  201.             if (0{
  202.                 //SetPrint(fp,cfp->fws,$this);
  203.                 //PlinkPrint(fp,cfp->fplp,"To  ");
  204.                 //PlinkPrint(fp,cfp->bplp,"From");
  205.             }
  206.             $cfp $cfp->next;
  207.         }
  208.         fwrite($fp"\n");
  209.         fclose($fp);
  210.     }
  211.  
  212.     /**
  213.      * Initialize the configuration list builder for a new state.
  214.      */
  215.     static function Configlist_init()
  216.     {
  217.         self::$current 0;
  218.         self::$currentend &self::$current;
  219.         self::$basis 0;
  220.         self::$basisend &self::$basis;
  221.         self::$x4a array();
  222.     }
  223.  
  224.     /**
  225.      * Remove all data from the table.
  226.      * 
  227.      * Pass each data to the function $f as it is removed if
  228.      * $f is a valid callback.
  229.      * @param callback|null
  230.      * @see Configtable_clear()
  231.      */
  232.     static function Configtable_reset($f)
  233.     {
  234.         self::$current 0;
  235.         self::$currentend &self::$current;
  236.         self::$basis 0;
  237.         self::$basisend &self::$basis;
  238.         self::Configtable_clear(0);
  239.     }
  240.  
  241.     /**
  242.      * Remove all data from the associative array representation
  243.      * of configurations.
  244.      * 
  245.      * Pass each data to the function $f as it is removed if
  246.      * $f is a valid callback.
  247.      * @param callback|null
  248.      */
  249.     static function Configtable_clear($f)
  250.     {
  251.         if (!count(self::$x4a)) {
  252.             return;
  253.         }
  254.         if ($f{
  255.             for ($i 0$i count(self::$x4a)$i++{
  256.                 call_user_func($fself::$x4a[$i]->data);
  257.             }
  258.         }
  259.         self::$x4a array();
  260.     }
  261.  
  262.     /**
  263.      * Reset the configuration list builder for a new state.
  264.      * @see Configtable_clear()
  265.      */
  266.     static function Configlist_reset()
  267.     {
  268.         self::Configtable_clear(0);
  269.     }
  270.  
  271.     /**
  272.      * Add another configuration to the configuration list for this parser state.
  273.      * @param PHP_ParserGenerator_Rule the rule
  274.      * @param int Index into the right-hand side of the rule where the dot goes
  275.      * @return PHP_ParserGenerator_Config 
  276.      */
  277.     static function Configlist_add($rp$dot)
  278.     {
  279.         $model new PHP_ParserGenerator_Config;
  280.         $model->rp $rp;
  281.         $model->dot $dot;
  282.         $cfp self::Configtable_find($model);
  283.         if ($cfp === 0{
  284.             $cfp self::newconfig();
  285.             $cfp->rp $rp;
  286.             $cfp->dot $dot;
  287.             $cfp->fws array();
  288.             $cfp->stp 0;
  289.             $cfp->fplp $cfp->bplp 0;
  290.             $cfp->next 0;
  291.             $cfp->bp 0;
  292.             self::$currentend $cfp;
  293.             self::$currentend &$cfp->next;
  294.             self::Configtable_insert($cfp);
  295.         }
  296.         return $cfp;
  297.     }
  298.  
  299.     /**
  300.      * Add a basis configuration to the configuration list for this parser state.
  301.      * 
  302.      * Basis configurations are the root for a configuration.  This method also
  303.      * inserts the configuration into the regular list of configurations for this
  304.      * reason.
  305.      * @param PHP_ParserGenerator_Rule the rule
  306.      * @param int Index into the right-hand side of the rule where the dot goes
  307.      * @return PHP_ParserGenerator_Config 
  308.      */
  309.     static function Configlist_addbasis($rp$dot)
  310.     {
  311.         $model new PHP_ParserGenerator_Config;
  312.         $model->rp $rp;
  313.         $model->dot $dot;
  314.         $cfp self::Configtable_find($model);
  315.         if ($cfp === 0{
  316.             $cfp self::newconfig();
  317.             $cfp->rp $rp;
  318.             $cfp->dot $dot;
  319.             $cfp->fws array();
  320.             $cfp->stp 0;
  321.             $cfp->fplp $cfp->bplp 0;
  322.             $cfp->next 0;
  323.             $cfp->bp 0;
  324.             self::$currentend $cfp;
  325.             self::$currentend &$cfp->next;
  326.             self::$basisend $cfp;
  327.             self::$basisend &$cfp->bp;
  328.             self::Configtable_insert($cfp);
  329.         }
  330.         return $cfp;
  331.     }
  332.  
  333.     /**
  334.      * Compute the closure of the configuration list.
  335.      * 
  336.      * This calculates all of the possible continuations of
  337.      * each configuration, ensuring that each state accounts
  338.      * for every configuration that could arrive at that state.
  339.      */
  340.     static function Configlist_closure(PHP_ParserGenerator_Data $lemp)
  341.     {
  342.         for ($cfp self::$current$cfp$cfp $cfp->next{
  343.             $rp $cfp->rp;
  344.             $dot $cfp->dot;
  345.             if ($dot >= $rp->nrhs{
  346.                 continue;
  347.             }
  348.             $sp $rp->rhs[$dot];
  349.             if ($sp->type == PHP_ParserGenerator_Symbol::NONTERMINAL{
  350.                 if ($sp->rule === && $sp !== $lemp->errsym{
  351.                     PHP_ParserGenerator::ErrorMsg($lemp->filename$rp->line,
  352.                         "Nonterminal \"%s\" has no rules."$sp->name);
  353.                     $lemp->errorcnt++;
  354.                 }
  355.                 for ($newrp $sp->rule$newrp$newrp $newrp->nextlhs{
  356.                     $newcfp self::Configlist_add($newrp0);
  357.                     for ($i $dot 1$i $rp->nrhs$i++{
  358.                         $xsp $rp->rhs[$i];
  359.                         if ($xsp->type == PHP_ParserGenerator_Symbol::TERMINAL{
  360.                             $newcfp->fws[$xsp->index1;
  361.                             break;
  362.                         elseif ($xsp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL{
  363.                             for ($k 0$k $xsp->nsubsym$k++{
  364.                                 $newcfp->fws[$xsp->subsym[$k]->index1;
  365.                             }
  366.                             break;
  367.                         else {
  368.                             $a array_diff_key($xsp->firstset$newcfp->fws);
  369.                             $newcfp->fws += $a;
  370.                             if ($xsp->lambda === false{
  371.                                 break;
  372.                             }
  373.                         }
  374.                     }
  375.                     if ($i == $rp->nrhs{
  376.                         PHP_ParserGenerator_PropagationLink::Plink_add($cfp->fplp$newcfp);
  377.                     }
  378.                 }
  379.             }
  380.         }
  381.     }
  382.  
  383.     /**
  384.      * Sort the configuration list
  385.      * @uses Configcmp()
  386.      */
  387.     static function Configlist_sort()
  388.     {
  389.         $a 0;
  390.         //self::Configshow(self::$current);
  391.         self::$current PHP_ParserGenerator::msort(self::$current,'next'array('PHP_ParserGenerator_Config''Configcmp'));
  392.         //self::Configshow(self::$current);
  393.         self::$currentend &$a;
  394.         self::$currentend 0;
  395.     }
  396.  
  397.     /**
  398.      * Sort the configuration list
  399.      * @uses Configcmp
  400.      */
  401.     static function Configlist_sortbasis()
  402.     {
  403.         $a 0;
  404.         self::$basis PHP_ParserGenerator::msort(self::$current,'bp'array('PHP_ParserGenerator_Config''Configcmp'));
  405.         self::$basisend &$a;
  406.         self::$basisend 0;
  407.     }
  408.  
  409.     /**
  410.      * Return a pointer to the head of the configuration list and
  411.      * reset the list
  412.      * @see $current
  413.      * @return PHP_ParserGenerator_Config 
  414.      */
  415.     static function Configlist_return()
  416.     {
  417.         $old self::$current;
  418.         self::$current 0;
  419.         self::$currentend &self::$current;
  420.         return $old;
  421.     }
  422.  
  423.     /**
  424.      * Return a pointer to the head of the basis list and
  425.      * reset the list
  426.      * @see $basis
  427.      * @return PHP_ParserGenerator_Config 
  428.      */
  429.     static function Configlist_basis()
  430.     {
  431.         $old self::$basis;
  432.         self::$basis 0;
  433.         self::$basisend &self::$basis;
  434.         return $old;
  435.     }
  436.  
  437.     /**
  438.      * Free all elements of the given configuration list
  439.      * @param PHP_ParserGenerator_Config 
  440.      */
  441.     static function Configlist_eat($cfp)
  442.     {
  443.         for($cfp$cfp $nextcfp){
  444.             $nextcfp $cfp->next;
  445.             if ($cfp->fplp !=0{
  446.                 throw new Exception('fplp of configuration non-zero?');
  447.             }
  448.             if ($cfp->bplp !=0{
  449.                 throw new Exception('bplp of configuration non-zero?');
  450.             }
  451.             if ($cfp->fws{
  452.                 $cfp->fws array();
  453.             }
  454.         }
  455.     }
  456.  
  457.     /**
  458.      * Compare two configurations for sorting purposes.
  459.      *
  460.      * Configurations based on higher precedence rules
  461.      * (those earlier in the file) are chosen first.  Two
  462.      * configurations that are the same rule are sorted by
  463.      * dot (see {@link $dot}), and those configurations
  464.      * with a dot closer to the left-hand side are chosen first.
  465.      * @param unknown_type $a 
  466.      * @param unknown_type $b 
  467.      * @return unknown 
  468.      */
  469.     static function Configcmp($a$b)
  470.     {
  471.         $x $a->rp->index $b->rp->index;
  472.         if (!$x{
  473.             $x $a->dot $b->dot;
  474.         }
  475.         return $x;
  476.     }
  477.  
  478.     /**
  479.      * Print out information on this configuration.
  480.      *
  481.      * @param resource $fp 
  482.      * @see PHP_ParserGenerator_Data::ReportOutput()
  483.      */
  484.     function ConfigPrint($fp)
  485.     {
  486.         $rp $this->rp;
  487.         fprintf($fp"%s ::="$rp->lhs->name);
  488.         for ($i 0$i <= $rp->nrhs$i++{
  489.             if ($i === $this->dot{
  490.                 fwrite($fp,' *');
  491.             }
  492.             if ($i === $rp->nrhs{
  493.                 break;
  494.             }
  495.             $sp $rp->rhs[$i];
  496.             fprintf($fp,' %s'$sp->name);
  497.             if ($sp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL{
  498.                 for ($j 1$j $sp->nsubsym$j++{
  499.                     fprintf($fp'|%s'$sp->subsym[$j]->name);
  500.                 }
  501.             }
  502.         }
  503.     }
  504.  
  505.     /**
  506.      * Hash a configuration for the associative array {@link $x4a}
  507.      */
  508.     private static function confighash(PHP_ParserGenerator_Config $a)
  509.     {
  510.         $h 0;
  511.         $h $h 571 $a->rp->index 37 $a->dot;
  512.         return $h;
  513.     }
  514.  
  515.     /**
  516.      * Insert a new record into the array.  Return TRUE if successful.
  517.      * Prior data with the same key is NOT overwritten
  518.      */
  519.     static function Configtable_insert(PHP_ParserGenerator_Config $data)
  520.     {
  521.         $h self::confighash($data);
  522.         if (isset(self::$x4a[$h])) {
  523.             $np self::$x4a[$h];
  524.         else {
  525.             $np 0;
  526.         }
  527.         while ($np{
  528.             if (self::Configcmp($np->data$data== 0{
  529.                 /* An existing entry with the same key is found. */
  530.                 /* Fail because overwrite is not allows. */
  531.                 return 0;
  532.             }
  533.             $np $np->next;
  534.         }
  535.         /* Insert the new data */
  536.         $np array('data' => $data'next' => 0'from' => 0);
  537.         $np new PHP_ParserGenerator_StateNode;
  538.         $np->data $data;
  539.         if (isset(self::$x4a[$h])) {
  540.             self::$x4a[$h]->from $np->next;
  541.             $np->next self::$x4a[$h];
  542.         }
  543.         $np->from $np;
  544.         self::$x4a[$h$np;
  545.         return 1;
  546.     }
  547.  
  548.     /**
  549.      * Return a pointer to data assigned to the given key.  Return NULL
  550.      * if no such key.
  551.      * @return PHP_ParserGenerator_Config|0
  552.      */
  553.     static function Configtable_find(PHP_ParserGenerator_Config $key)
  554.     {
  555.         $h self::confighash($key);
  556.         if (!isset(self::$x4a[$h])) {
  557.             return 0;
  558.         }
  559.         $np self::$x4a[$h];
  560.         while ($np{
  561.             if (self::Configcmp($np->data$key== 0{
  562.                 break;
  563.             }
  564.             $np $np->next;
  565.         }
  566.         return $np $np->data 0;
  567.     }
  568. }
  569. ?>

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