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

Source for file ParserGenerator.php

Documentation is available at ParserGenerator.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.  * There are a few PHP-specific changes to the lemon parser generator.
  9.  *
  10.  * - %extra_argument is removed, as class constructor can be used to
  11.  *   pass in extra information
  12.  * - %token_type and company are irrelevant in PHP, and so are removed
  13.  * - %declare_class is added to define the parser class name and any
  14.  *   implements/extends information
  15.  * - %include_class is added to allow insertion of extra class information
  16.  *   such as constants, a class constructor, etc.
  17.  *
  18.  * Other changes make the parser more robust, and also make reporting
  19.  * syntax errors simpler.  Detection of expected tokens eliminates some
  20.  * problematic edge cases where an unexpected token could cause the parser
  21.  * to simply accept input.
  22.  * 
  23.  * Otherwise, the file format is identical to the Lemon parser generator
  24.  *
  25.  * PHP version 5
  26.  *
  27.  * LICENSE:
  28.  * 
  29.  * Copyright (c) 2006, Gregory Beaver <cellog@php.net>
  30.  * All rights reserved.
  31.  *
  32.  * Redistribution and use in source and binary forms, with or without
  33.  * modification, are permitted provided that the following conditions
  34.  * are met:
  35.  *
  36.  *     * Redistributions of source code must retain the above copyright
  37.  *       notice, this list of conditions and the following disclaimer.
  38.  *     * Redistributions in binary form must reproduce the above copyright
  39.  *       notice, this list of conditions and the following disclaimer in
  40.  *       the documentation and/or other materials provided with the distribution.
  41.  *     * Neither the name of the PHP_ParserGenerator nor the names of its
  42.  *       contributors may be used to endorse or promote products derived
  43.  *       from this software without specific prior written permission.
  44.  *
  45.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
  46.  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  47.  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  48.  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  49.  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  50.  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  51.  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  52.  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  53.  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  54.  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  55.  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  56.  *
  57.  * @category   php
  58.  * @package    PHP_ParserGenerator
  59.  * @author     Gregory Beaver <cellog@php.net>
  60.  * @copyright  2006 Gregory Beaver
  61.  * @license    http://www.opensource.org/licenses/bsd-license.php New BSD License
  62.  * @version    CVS: $Id$
  63.  * @since      File available since Release 0.1.0
  64.  */
  65. /**#@+
  66.  * Basic components of the parser generator
  67.  */
  68. require_once 'PHP/ParserGenerator/Action.php';
  69. require_once 'PHP/ParserGenerator/ActionTable.php';
  70. require_once 'PHP/ParserGenerator/Config.php';
  71. require_once 'PHP/ParserGenerator/Data.php';
  72. require_once 'PHP/ParserGenerator/Symbol.php';
  73. require_once 'PHP/ParserGenerator/Rule.php';
  74. require_once 'PHP/ParserGenerator/Parser.php';
  75. require_once 'PHP/ParserGenerator/PropagationLink.php';
  76. require_once 'PHP/ParserGenerator/State.php';
  77. /**#@-*/
  78.  * The basic home class for the parser generator
  79.  * 
  80.  * @package    PHP_ParserGenerator
  81.  * @author     Gregory Beaver <cellog@php.net>
  82.  * @copyright  2006 Gregory Beaver
  83.  * @license    http://www.opensource.org/licenses/bsd-license.php New BSD License
  84.  * @version    @package_version@
  85.  * @since      Class available since Release 0.1.0
  86.  * @example    Lempar.php
  87.  * @example    examples/Parser.y Sample parser file format (PHP_LexerGenerator's parser)
  88.  * @example    examples/Parser.php Sample parser file format PHP code (PHP_LexerGenerator's parser)
  89.  */
  90. class PHP_ParserGenerator
  91. {
  92.     /**
  93.      * Set this to 1 to turn on debugging of Lemon's parsing of
  94.      * grammar files.
  95.      */
  96.     const DEBUG = 0;
  97.     const MAXRHS = 1000;
  98.     const OPT_FLAG = 1, OPT_INT = 2, OPT_DBL = 3, OPT_STR = 4,
  99.           OPT_FFLAG = 5, OPT_FINT = 6, OPT_FDBL = 7, OPT_FSTR = 8;
  100.     public $azDefine = array();
  101.     private static $options = array(
  102.         'b' => array(
  103.             'type' => self::OPT_FLAG,
  104.             'arg' => 'basisflag',
  105.             'message' => 'Print only the basis in report.'
  106.         ),
  107.         'c' => array(
  108.             'type' => self::OPT_FLAG,
  109.             'arg' => 'compress',
  110.             'message' => 'Don\'t compress the action table.'
  111.         ),
  112.         'D' => array(
  113.             'type' => self::OPT_FSTR,
  114.             'arg' => 'handle_D_option',
  115.             'message' => 'Define an %ifdef macro.'
  116.         ),
  117.         'g' => array(
  118.             'type' => self::OPT_FLAG,
  119.             'arg' => 'rpflag',
  120.             'message' => 'Print grammar without actions.'
  121.         ),
  122.         'm' => array(
  123.             'type' => self::OPT_FLAG,
  124.             'arg' => 'mhflag',
  125.             'message' => 'Output a makeheaders compatible file'
  126.         ),
  127.         'q' => array(
  128.             'type' => self::OPT_FLAG,
  129.             'arg' => 'quiet',
  130.             'message' => '(Quiet) Don\'t print the report file.'
  131.         ),
  132.         's' => array(
  133.             'type' => self::OPT_FLAG,
  134.             'arg' => 'statistics',
  135.             'message' => 'Print parser stats to standard output.'
  136.         ),
  137.         'x' => array(
  138.             'type' => self::OPT_FLAG,
  139.             'arg' => 'version',
  140.             'message' => 'Print the version number.'
  141.         )
  142.     );
  143.  
  144.     private $basisflag = 0;
  145.     private $compress = 0;
  146.     private $rpflag = 0;
  147.     private $mhflag = 0;
  148.     private $quiet = 0;
  149.     private $statistics = 0;
  150.     private $version = 0;
  151.     private $size;
  152.     /**
  153.      * Process a flag command line argument.
  154.      * @param int 
  155.      * @param array 
  156.      * @return int 
  157.      */
  158.     function handleflags($i, $argv)
  159.     {
  160.         if (!isset($argv[1]) || !isset(self::$options[$argv[$i][1]])) {
  161.             throw new Exception('Command line syntax error: undefined option "' .  $argv[$i] . '"');
  162.         }
  163.         $v = self::$options[$argv[$i][1]] == '-';
  164.         if (self::$options[$argv[$i][1]]['type'] == self::OPT_FLAG) {
  165.             $this->{self::$options[$argv[$i][1]]['arg']} = (int) $v;
  166.         } elseif (self::$options[$argv[$i][1]]['type'] == self::OPT_FFLAG) {
  167.             $this->{self::$options[$argv[$i][1]]['arg']}($v);
  168.         } elseif (self::$options[$argv[$i][1]]['type'] == self::OPT_FSTR) {
  169.             $this->{self::$options[$argv[$i][1]]['arg']}(substr($v, 2));
  170.         } else {
  171.             throw new Exception('Command line syntax error: missing argument on switch: "' . $argv[$i] . '"');
  172.         }
  173.         return 0;
  174.     }
  175.  
  176.     /**
  177.      * Process a command line switch which has an argument.
  178.      * @param int 
  179.      * @param array 
  180.      * @param array 
  181.      * @return int 
  182.      */
  183.     function handleswitch($i, $argv)
  184.     {
  185.         $lv = 0;
  186.         $dv = 0.0;
  187.         $sv = $end = $cp = '';
  188.         $j; // int
  189.         $errcnt = 0;
  190.         $cp = strstr($argv[$i],'=');
  191.         if (!$cp) {
  192.             throw new Exception('INTERNAL ERROR: handleswitch passed bad argument, no "=" in arg');
  193.         }
  194.         $argv[$i] = substr($argv[$i], 0, strlen($argv[$i]) - strlen($cp));
  195.         if (!isset(self::$options[$argv[$i]])) {
  196.             throw new Exception('Command line syntax error: undefined option "' .  $argv[$i] .
  197.                 $cp . '"');
  198.         }
  199.         $cp = substr($cp, 1);
  200.         switch (self::$options[$argv[$i]]['type']) {
  201.             case self::OPT_FLAG:
  202.             case self::OPT_FFLAG:
  203.                 throw new Exception('Command line syntax error: option requires an argument "' .
  204.                     $argv[$i] . '=' . $cp . '"');
  205.             case self::OPT_DBL:
  206.             case self::OPT_FDBL:
  207.                 $dv = (double) $cp;
  208.                 break;
  209.             case self::OPT_INT:
  210.             case self::OPT_FINT:
  211.                 $lv = (int) $cp;
  212.                 break;
  213.             case self::OPT_STR:
  214.             case self::OPT_FSTR:
  215.                 $sv = $cp;
  216.                 break;
  217.         }
  218.         switch(self::$options[$argv[$i]]['type']) {
  219.             case self::OPT_FLAG:
  220.             case self::OPT_FFLAG:
  221.                 break;
  222.             case self::OPT_DBL:
  223.                 $this->${self::$options[$argv[$i]]['arg']} = $dv;
  224.                 break;
  225.             case self::OPT_FDBL:
  226.                 $this->${self::$options[$argv[$i]]['arg']}($dv);
  227.                 break;
  228.             case self::OPT_INT:
  229.                 $this->${self::$options[$argv[$i]]['arg']} = $lv;
  230.                 break;
  231.             case self::OPT_FINT:
  232.                 $this->${self::$options[$argv[$i]]['arg']}($lv);
  233.                 break;
  234.             case self::OPT_STR:
  235.                 $this->${self::$options[$argv[$i]]['arg']} = $sv;
  236.                 break;
  237.             case self::OPT_FSTR:
  238.                 $this->${self::$options[$argv[$i]]['arg']}($sv);
  239.                 break;
  240.         }
  241.         return 0;
  242.     }
  243.  
  244.     /**
  245.      * @param array arguments
  246.      * @param array valid options
  247.      * @return int 
  248.      */
  249.     function OptInit($a)
  250.     {
  251.         $errcnt = 0;
  252.         $argv = $a;
  253.         try {
  254.             if (is_array($argv) && count($argv) && self::$options) {
  255.                 for($i = 1; $i < count($argv); $i++) {
  256.                     if ($argv[$i][0] == '+' || $argv[$i][0] == '-') {
  257.                         $errcnt += $this->handleflags($i, $argv);
  258.                     } elseif (strstr($argv[$i],'=')) {
  259.                         $errcnt += $this->handleswitch(i, $argv);
  260.                     }
  261.                 }
  262.             }
  263.         } catch (Exception $e) {
  264.             OptPrint();
  265.             echo $e;
  266.             exit(1);
  267.         }
  268.         return 0;
  269.     }
  270.  
  271.     /**
  272.      * Return the index of the N-th non-switch argument.  Return -1
  273.      * if N is out of range.
  274.      * @param int 
  275.      * @return int 
  276.      */
  277.     private function argindex($n, $a)
  278.     {
  279.         $dashdash = 0;
  280.         if (!is_array($a) || !count($a)) {
  281.             return -1;
  282.         }
  283.         for ($i=1; $i < count($a); $i++) {
  284.             if ($dashdash || !($a[$i][0] == '-' || $a[$i][0] == '+' ||
  285.                   strchr($a[$i], '='))) {
  286.                 if ($n == 0) {
  287.                     return $i;
  288.                 }
  289.                 $n--;
  290.             }
  291.             if ($_SERVER['argv'][$i] == '--') {
  292.                 $dashdash = 1;
  293.             }
  294.         }
  295.         return -1;
  296.     }
  297.  
  298.     /**
  299.      * Return the value of the non-option argument as indexed by $i
  300.      *
  301.      * @param int 
  302.      * @param array the value of $argv
  303.      * @return 0|string
  304.      */
  305.     private function OptArg($i, $a)
  306.     {
  307.         if (-1 == ($ind = $this->argindex($i, $a))) {
  308.             return 0;
  309.         }
  310.         return $a[$ind];
  311.     }
  312.  
  313.     /**
  314.      * @return int number of arguments
  315.      */
  316.     function OptNArgs($a)
  317.     {
  318.         $cnt = $dashdash = 0;
  319.         if (is_array($a) && count($a)) {
  320.             for($i = 1; $i < count($a); $i++) {
  321.                 if ($dashdash || !($a[$i][0] == '-' || $a[$i][0] == '+' ||
  322.                       strchr($a[$i], '='))) {
  323.                     $cnt++;
  324.                 }
  325.                 if ($a[$i] == "--") {
  326.                     $dashdash = 1;
  327.                 }
  328.             }
  329.         }
  330.         return $cnt;
  331.     }
  332.  
  333.     /**
  334.      * Print out command-line options
  335.      */
  336.     function OptPrint()
  337.     {
  338.         $max = 0;
  339.         foreach (self::$options as $label => $info) {
  340.             $len = strlen($label) + 1;
  341.             switch ($info['type']) {
  342.                 case self::OPT_FLAG:
  343.                 case self::OPT_FFLAG:
  344.                     break;
  345.                 case self::OPT_INT:
  346.                 case self::OPT_FINT:
  347.                     $len += 9;       /* length of "<integer>" */
  348.                     break;
  349.                 case self::OPT_DBL:
  350.                 case self::OPT_FDBL:
  351.                     $len += 6;       /* length of "<real>" */
  352.                     break;
  353.                 case self::OPT_STR:
  354.                 case self::OPT_FSTR:
  355.                     $len += 8;       /* length of "<string>" */
  356.                     break;
  357.             }
  358.             if ($len > $max) {
  359.                 $max = $len;
  360.             }
  361.         }
  362.         foreach (self::$options as $label => $info) {
  363.             switch ($info['type']) {
  364.                 case self::OPT_FLAG:
  365.                 case self::OPT_FFLAG:
  366.                     printf("  -%-*s  %s\n", $max, $label, $info['message']);
  367.                     break;
  368.                 case self::OPT_INT:
  369.                 case self::OPT_FINT:
  370.                     printf("  %s=<integer>%*s  %s\n", $label, $max - strlen($label) - 9,
  371.                         $info['message']);
  372.                     break;
  373.                 case self::OPT_DBL:
  374.                 case self::OPT_FDBL:
  375.                     printf("  %s=<real>%*s  %s\n", $label, $max - strlen($label) - 6,
  376.                         $info['message']);
  377.                     break;
  378.                 case self::OPT_STR:
  379.                 case self::OPT_FSTR:
  380.                     printf("  %s=<string>%*s  %s\n", $label, $max - strlen($label) - 8,
  381.                         $info['message']);
  382.                     break;
  383.             }
  384.         }
  385.     }
  386.  
  387.     /**
  388.     * This routine is called with the argument to each -D command-line option.
  389.     * Add the macro defined to the azDefine array.
  390.     * @param string 
  391.     */
  392.     private function handle_D_option($z)
  393.     {
  394.         if ($a = strstr($z, '=')) {
  395.             $z = substr($a, 1); // strip first =
  396.         }
  397.         $this->azDefine[] = $z;
  398.     }
  399.  
  400.     /**************** From the file "main.c" ************************************/
  401. /*
  402. ** Main program file for the LEMON parser generator.
  403. */
  404.  
  405.  
  406.     /* The main program.  Parse the command line and do it... */
  407.     function main()
  408.     {
  409.         $lem = new PHP_ParserGenerator_Data;
  410.  
  411.         $this->OptInit($_SERVER['argv']);
  412.         if ($this->version) {
  413.             echo "Lemon version 1.0/PHP_ParserGenerator port version @package_version@\n";
  414.             exit(0); 
  415.         }
  416.         if ($this->OptNArgs($_SERVER['argv']) != 1) {
  417.             echo "Exactly one filename argument is required.\n";
  418.             exit(1);
  419.         }
  420.         $lem->errorcnt = 0;
  421.  
  422.         /* Initialize the machine */
  423.         $lem->argv0 = $_SERVER['argv'][0];
  424.         $lem->filename = $this->OptArg(0, $_SERVER['argv']);
  425.         $a = pathinfo($lem->filename);
  426.         if (isset($a['extension'])) {
  427.             $ext = '.' . $a['extension'];
  428.             $lem->filenosuffix = substr($lem->filename, 0, strlen($lem->filename) - strlen($ext));
  429.         } else {
  430.             $lem->filenosuffix = $lem->filename;
  431.         }
  432.         $lem->basisflag = $this->basisflag;
  433.         $lem->has_fallback = 0;
  434.         $lem->nconflict = 0;
  435.         $lem->name = $lem->include_code = $lem->include_classcode = $lem->arg =
  436.             $lem->tokentype = $lem->start = 0;
  437.         $lem->vartype = 0;
  438.         $lem->stacksize = 0;
  439.         $lem->error = $lem->overflow = $lem->failure = $lem->accept = $lem->tokendest =
  440.           $lem->tokenprefix = $lem->outname = $lem->extracode = 0;
  441.         $lem->vardest = 0;
  442.         $lem->tablesize = 0;
  443.         PHP_ParserGenerator_Symbol::Symbol_new("$");
  444.         $lem->errsym = PHP_ParserGenerator_Symbol::Symbol_new("error");
  445.  
  446.         /* Parse the input file */
  447.         $parser = new PHP_ParserGenerator_Parser($this);
  448.         $parser->Parse($lem);
  449.         if ($lem->errorcnt) {
  450.             exit($lem->errorcnt);
  451.         }
  452.         if ($lem->rule === 0) {
  453.             printf("Empty grammar.\n");
  454.             exit(1);
  455.         }
  456.  
  457.         /* Count and index the symbols of the grammar */
  458.         $lem->nsymbol = PHP_ParserGenerator_Symbol::Symbol_count();
  459.         PHP_ParserGenerator_Symbol::Symbol_new("{default}");
  460.         $lem->symbols = PHP_ParserGenerator_Symbol::Symbol_arrayof();
  461.         for ($i = 0; $i <= $lem->nsymbol; $i++) {
  462.             $lem->symbols[$i]->index = $i;
  463.         }
  464.         usort($lem->symbols, array('PHP_ParserGenerator_Symbol', 'sortSymbols'));
  465.         for ($i = 0; $i <= $lem->nsymbol; $i++) {
  466.             $lem->symbols[$i]->index = $i;
  467.         }
  468.         // find the first lower-case symbol
  469.         for($i = 1; ord($lem->symbols[$i]->name[0]) < ord ('Z'); $i++);
  470.         $lem->nterminal = $i;
  471.  
  472.         /* Generate a reprint of the grammar, if requested on the command line */
  473.         if ($this->rpflag) {
  474.             $this->Reprint();
  475.         } else {
  476.             /* Initialize the size for all follow and first sets */
  477.             $this->SetSize($lem->nterminal);
  478.  
  479.             /* Find the precedence for every production rule (that has one) */
  480.             $lem->FindRulePrecedences();
  481.  
  482.             /* Compute the lambda-nonterminals and the first-sets for every
  483.             ** nonterminal */
  484.             $lem->FindFirstSets();
  485.  
  486.             /* Compute all LR(0) states.  Also record follow-set propagation
  487.             ** links so that the follow-set can be computed later */
  488.             $lem->nstate = 0;
  489.             $lem->FindStates();
  490.             $lem->sorted = PHP_ParserGenerator_State::State_arrayof();
  491.  
  492.             /* Tie up loose ends on the propagation links */
  493.             $lem->FindLinks();
  494.  
  495.             /* Compute the follow set of every reducible configuration */
  496.             $lem->FindFollowSets();
  497.  
  498.             /* Compute the action tables */
  499.             $lem->FindActions();
  500.  
  501.             /* Compress the action tables */
  502.             if ($this->compress===0) {
  503.                 $lem->CompressTables();
  504.             }
  505.  
  506.             /* Reorder and renumber the states so that states with fewer choices
  507.             ** occur at the end. */
  508.             $lem->ResortStates();
  509.  
  510.             /* Generate a report of the parser generated.  (the "y.output" file) */
  511.             if (!$this->quiet) {
  512.                 $lem->ReportOutput();
  513.             }
  514.  
  515.             /* Generate the source code for the parser */
  516.             $lem->ReportTable($this->mhflag);
  517.  
  518.     /* Produce a header file for use by the scanner.  (This step is
  519.     ** omitted if the "-m" option is used because makeheaders will
  520.     ** generate the file for us.) */
  521. //            if (!$this->mhflag) {
  522. //                $this->ReportHeader();
  523. //            }
  524.         }
  525.         if ($this->statistics) {
  526.             printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
  527.                 $lem->nterminal, $lem->nsymbol - $lem->nterminal, $lem->nrule);
  528.             printf("                   %d states, %d parser table entries, %d conflicts\n",
  529.                 $lem->nstate, $lem->tablesize, $lem->nconflict);
  530.         }
  531.         if ($lem->nconflict) {
  532.             printf("%d parsing conflicts.\n", $lem->nconflict);
  533.         }
  534.         exit($lem->errorcnt + $lem->nconflict);
  535.         return ($lem->errorcnt + $lem->nconflict);
  536.     }
  537.  
  538.     function SetSize($n)
  539.     {
  540.         $this->size = $n + 1;
  541.     }
  542.  
  543.     /**
  544.      * Merge in a merge sort for a linked list
  545.      * Inputs:
  546.      *  - a:       A sorted, null-terminated linked list.  (May be null).
  547.      *  - b:       A sorted, null-terminated linked list.  (May be null).
  548.      *  - cmp:     A pointer to the comparison function.
  549.      *  - offset:  Offset in the structure to the "next" field.
  550.      *
  551.      * Return Value:
  552.      *   A pointer to the head of a sorted list containing the elements
  553.      *   of both a and b.
  554.      *
  555.      * Side effects:
  556.      *   The "next" pointers for elements in the lists a and b are
  557.      *   changed.
  558.      */
  559.     static function merge($a, $b, $cmp, $offset)
  560.     {
  561.         if($a === 0) {
  562.             $head = $b;
  563.         } elseif ($b === 0) {
  564.             $head = $a;
  565.         } else {
  566.             if (call_user_func($cmp, $a, $b) < 0) {
  567.                 $ptr = $a;
  568.                 $a = $a->$offset;
  569.             } else {
  570.                 $ptr = $b;
  571.                 $b = $b->$offset;
  572.             }
  573.             $head = $ptr;
  574.             while ($a && $b) {
  575.                 if (call_user_func($cmp, $a, $b) < 0) {
  576.                     $ptr->$offset = $a;
  577.                     $ptr = $a;
  578.                     $a = $a->$offset;
  579.                 } else {
  580.                     $ptr->$offset = $b;
  581.                     $ptr = $b;
  582.                     $b = $b->$offset;
  583.                 }
  584.             }
  585.             if ($a !== 0) {
  586.                 $ptr->$offset = $a;
  587.             } else {
  588.                 $ptr->$offset = $b;
  589.             }
  590.         }
  591.         return $head;
  592.     }
  593.     
  594.     /*
  595.     ** Inputs:
  596.     **   list:      Pointer to a singly-linked list of structures.
  597.     **   next:      Pointer to pointer to the second element of the list.
  598.     **   cmp:       A comparison function.
  599.     **
  600.     ** Return Value:
  601.     **   A pointer to the head of a sorted list containing the elements
  602.     **   orginally in list.
  603.     **
  604.     ** Side effects:
  605.     **   The "next" pointers for elements in list are changed.
  606.     */
  607.     #define LISTSIZE 30
  608.     static function msort($list, $next, $cmp)
  609.     {
  610.         if ($list === 0) {
  611.             return $list;
  612.         }
  613.         if ($list->$next === 0) {
  614.             return $list;
  615.         }
  616.         $set = array_fill(0, 30, 0);
  617.         while ($list) {
  618.             $ep = $list;
  619.             $list = $list->$next;
  620.             $ep->$next = 0;
  621.             for ($i = 0; $i < 29 && $set[$i] !== 0; $i++) {
  622.                 $ep = self::merge($ep, $set[$i], $cmp, $next);
  623.                 $set[$i] = 0;
  624.             }
  625.             $set[$i] = $ep;
  626.         }
  627.         $ep = 0;
  628.         for ($i = 0; $i < 30; $i++) {
  629.             if ($set[$i] !== 0) {
  630.                 $ep = self::merge($ep, $set[$i], $cmp, $next);
  631.             }
  632.         }
  633.         return $ep;
  634.     }
  635.  
  636.     /* Find a good place to break "msg" so that its length is at least "min"
  637.     ** but no more than "max".  Make the point as close to max as possible.
  638.     */
  639.     static function findbreak($msg, $min, $max)
  640.     {
  641.         if ($min >= strlen($msg)) {
  642.             return strlen($msg);
  643.         }
  644.         for ($i = $spot = $min; $i <= $max && $i < strlen($msg); $i++) {
  645.             $c = $msg[$i];
  646.             if ($c == '-' && $i < $max - 1) {
  647.                 $spot = $i + 1;
  648.             }
  649.             if ($c == ' ') {
  650.                 $spot = $i;
  651.             }
  652.         }
  653.         return $spot;
  654.     }
  655.  
  656.     static function ErrorMsg($filename, $lineno, $format)
  657.     {
  658.         /* Prepare a prefix to be prepended to every output line */
  659.         if ($lineno > 0) {
  660.             $prefix = sprintf("%20s:%d: ", $filename, $lineno);
  661.         } else {
  662.             $prefix = sprintf("%20s: ", $filename);
  663.         }
  664.         $prefixsize = strlen($prefix);
  665.         $availablewidth = 79 - $prefixsize;
  666.         
  667.         /* Generate the error message */
  668.         $ap = func_get_args();
  669.         array_shift($ap); // $filename
  670.         array_shift($ap); // $lineno
  671.         array_shift($ap); // $format
  672.         $errmsg = vsprintf($format, $ap);
  673.         $linewidth = strlen($errmsg);
  674.         /* Remove trailing "\n"s from the error message. */
  675.         while ($linewidth > 0 && in_array($errmsg[$linewidth-1], array("\n", "\r"), true)) {
  676.             --$linewidth;
  677.             $errmsg = substr($errmsg, 0, strlen($errmsg) - 1);
  678.         }
  679.         
  680.         /* Print the error message */
  681.         $base = 0;
  682.         $errmsg = str_replace(array("\r", "\n", "\t"), array(' ', ' ', ' '), $errmsg);
  683.         while (strlen($errmsg)) {
  684.             $end = $restart = self::findbreak($errmsg, 0, $availablewidth);
  685.             if (strlen($errmsg) <= 79 && $end < strlen($errmsg) && $end <= 79) {
  686.                 $end = $restart = strlen($errmsg);
  687.             }
  688.             while (isset($errmsg[$restart]) && $errmsg[$restart] == ' ') {
  689.                 $restart++;
  690.             }
  691.             printf("%s%.${end}s\n", $prefix, $errmsg);
  692.             $errmsg = substr($errmsg, $restart);
  693.         }
  694.     }
  695.  
  696.     /**
  697.      * Duplicate the input file without comments and without actions
  698.      * on rules
  699.      */
  700.     function Reprint()
  701.     {
  702.         printf("// Reprint of input file \"%s\".\n// Symbols:\n", $this->filename);
  703.         $maxlen = 10;
  704.         for ($i = 0; $i < $this->nsymbol; $i++) {
  705.             $sp = $this->symbols[$i];
  706.             $len = strlen($sp->name);
  707.             if ($len > $maxlen ) {
  708.                 $maxlen = $len;
  709.             }
  710.         }
  711.         $ncolumns = 76 / ($maxlen + 5);
  712.         if ($ncolumns < 1) {
  713.             $ncolumns = 1;
  714.         }
  715.         $skip = ($this->nsymbol + $ncolumns - 1) / $ncolumns;
  716.         for ($i = 0; $i < $skip; $i++) {
  717.             print "//";
  718.             for ($j = $i; $j < $this->nsymbol; $j += $skip) {
  719.                 $sp = $this->symbols[$j];
  720.                 //assert( sp->index==j );
  721.                 printf(" %3d %-${maxlen}.${maxlen}s", $j, $sp->name);
  722.             }
  723.             print "\n";
  724.         }
  725.         for ($rp = $this->rule; $rp; $rp = $rp->next) {
  726.             printf("%s", $rp->lhs->name);
  727. /*          if ($rp->lhsalias) {
  728.                 printf("(%s)", $rp->lhsalias);
  729.             }*/
  730.             print " ::=";
  731.             for ($i = 0; $i < $rp->nrhs; $i++) {
  732.                 $sp = $rp->rhs[$i];
  733.                 printf(" %s", $sp->name);
  734.                 if ($sp->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) {
  735.                     for ($j = 1; $j < $sp->nsubsym; $j++) {
  736.                         printf("|%s", $sp->subsym[$j]->name);
  737.                     }
  738.                 }
  739. /*              if ($rp->rhsalias[$i]) {
  740.                     printf("(%s)", $rp->rhsalias[$i]);
  741.                 }*/
  742.             }
  743.             print ".";
  744.             if ($rp->precsym) {
  745.                 printf(" [%s]", $rp->precsym->name);
  746.             }
  747. /*          if ($rp->code) {
  748.                 print "\n    " . $rp->code);
  749.             }*/
  750.             print "\n";
  751.         }
  752.     }
  753. }
  754. //$a = new PHP_ParserGenerator;
  755. //$_SERVER['argv'] = array('lemon', '-s', '/development/lemon/PHP_Parser.y');
  756. //$_SERVER['argv'] = array('lemon', '-s', '/development/File_ChessPGN/ChessPGN/Parser.y');
  757. //$a->main();
Documentation generated on Sun, 02 Jul 2006 09:11:04 -0400 by phpDocumentor 1.3.0