[Summary view] [Print] [Text view]

   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: This source file is subject to version 3.01 of the PHP license
  11   * that is available through the world-wide-web at the following URI:
  12   * http://www.php.net/license/3_01.txt.  If you did not receive a copy of
  13   * the PHP License and are unable to obtain it through the web, please
  14   * send a note to [email protected] so we can mail you a copy immediately.
  15   *
  16   * @category   php
  17   * @package    PHP_ParserGenerator
  18   * @author     Gregory Beaver <[email protected]>
  19   * @copyright  2006 Gregory Beaver
  20   * @license    http://www.php.net/license/3_01.txt  PHP License 3.01
  21   * @version    CVS: $Id$
  22   * @since      File available since Release 0.1.0
  23   */
  24  /**
  25   * Symbols (terminals and nonterminals) of the grammar are stored in this class
  26   * 
  27   * @package    PHP_ParserGenerator
  28   * @author     Gregory Beaver <[email protected]>
  29   * @copyright  2006 Gregory Beaver
  30   * @license    http://www.php.net/license/3_01.txt  PHP License 3.01
  31   * @version    0.1.0
  32   * @since      Class available since Release 0.1.0
  33   */
  34  class PHP_ParserGenerator_Symbol
  35  {
  36      /**
  37       * Symbols that start with a capital letter like FOO.
  38       *
  39       * These are tokens directly from the lexer
  40       */
  41      const TERMINAL = 1;
  42      /**
  43       * Symbols that start with a lower-case letter like foo.
  44       *
  45       * These are grammar rules like "foo ::= BLAH."
  46       */
  47      const NONTERMINAL = 2;
  48      /**
  49       * Multiple terminal symbols.
  50       *
  51       * These are a grammar rule that consists of several terminals like
  52       * FOO|BAR|BAZ.  Note that non-terminals cannot be in a multi-terminal,
  53       * and a multi-terminal acts like a single terminal.
  54       * 
  55       * "FOO|BAR FOO|BAZ" is actually two multi-terminals, FOO|BAR and FOO|BAZ.
  56       */
  57      const MULTITERMINAL = 3;
  58      
  59      const LEFT = 1;
  60      const RIGHT = 2;
  61      const NONE = 3;
  62      const UNK = 4;
  63      /**
  64       * Name of the symbol
  65       *
  66       * @var string
  67       */
  68      public $name;
  69      /**
  70       * Index of this symbol.
  71       *
  72       * This will ultimately end up representing the symbol in the generated
  73       * parser
  74       * @var int
  75       */
  76      public $index;
  77      /**
  78       * Symbol type
  79       *
  80       * One of PHP_ParserGenerator_Symbol::TERMINAL,
  81       * PHP_ParserGenerator_Symbol::NONTERMINAL or
  82       * PHP_ParserGenerator_Symbol::MULTITERMINAL
  83       * @var int
  84       */
  85      public $type;
  86      /**
  87       * Linked list of rules that use this symbol, if it is a non-terminal.
  88       * @var PHP_ParserGenerator_Rule
  89       */
  90      public $rule;
  91      /**
  92       * Fallback token in case this token doesn't parse
  93       * @var PHP_ParserGenerator_Symbol
  94       */
  95      public $fallback;
  96      /**
  97       * Precendence, if defined.
  98       *
  99       * -1 if no unusual precedence
 100       * @var int
 101       */
 102      public $prec = -1;
 103      /**
 104       * Associativity if precedence is defined.
 105       *
 106       * One of PHP_ParserGenerator_Symbol::LEFT,
 107       * PHP_ParserGenerator_Symbol::RIGHT, PHP_ParserGenerator_Symbol::NONE
 108       * or PHP_ParserGenerator_Symbol::UNK
 109       * @var unknown_type
 110       */
 111      public $assoc;
 112      /**
 113       * First-set for all rules of this symbol
 114       *
 115       * @var array
 116       */
 117      public $firstset;
 118      /**
 119       * True if this symbol is a non-terminal and can generate an empty
 120       * result.
 121       * 
 122       * For instance "foo ::= ."
 123       * @var boolean
 124       */
 125      public $lambda;
 126      /**
 127       * Code that executes whenever this symbol is popped from the stack during
 128       * error processing.
 129       *
 130       * @var string|0
 131       */
 132      public $destructor = 0;
 133      /**
 134       * Line number of destructor code
 135       * @var int
 136       */
 137      public $destructorln;
 138      /**
 139       * Unused relic of the C version of Lemon.
 140       *
 141       * The data type of information held by this object.  Only used
 142       * if this is a non-terminal
 143       * @var string
 144       */
 145      public $datatype;
 146      /**
 147       * Unused relic of the C version of Lemon.
 148       *
 149       * The data type number.  In the parser, the value
 150       * stack is a union.  The .yy%d element of this
 151       * union is the correct data type for this object
 152       * @var string
 153       */
 154      public $dtnum;
 155      /**#@+
 156       * The following fields are used by MULTITERMINALs only
 157       */
 158      /**
 159       * Number of terminal symbols in the MULTITERMINAL
 160       * 
 161       * This is of course the same as count($this->subsym)
 162       * @var int
 163       */
 164      public $nsubsym;
 165      /**
 166       * Array of terminal symbols in the MULTITERMINAL
 167       * @var array an array of {@link PHP_ParserGenerator_Symbol} objects
 168       */
 169      public $subsym = array();
 170      /**#@-*/
 171      /**
 172       * Singleton storage of symbols
 173       *
 174       * @var array an array of PHP_ParserGenerator_Symbol objects
 175       */
 176      private static $symbol_table = array();
 177      /**
 178       * Return a pointer to the (terminal or nonterminal) symbol "x".
 179       * Create a new symbol if this is the first time "x" has been seen.
 180       * (this is a singleton)
 181       * @param string
 182       * @return PHP_ParserGenerator_Symbol
 183       */
 184      public static function Symbol_new($x)
 185      {
 186          if (isset(self::$symbol_table[$x])) {
 187              return self::$symbol_table[$x];
 188          }
 189          $sp = new PHP_ParserGenerator_Symbol;
 190          $sp->name = $x;
 191          $sp->type = preg_match('/[A-Z]/', $x[0]) ? self::TERMINAL : self::NONTERMINAL;
 192          $sp->rule = 0;
 193          $sp->fallback = 0;
 194          $sp->prec = -1;
 195          $sp->assoc = self::UNK;
 196          $sp->firstset = array();
 197          $sp->lambda = false;
 198          $sp->destructor = 0;
 199          $sp->datatype = 0;
 200          self::$symbol_table[$sp->name] = $sp;
 201          return $sp;
 202      }
 203  
 204      /**
 205       * Return the number of unique symbols
 206       * @return int
 207       */
 208      public static function Symbol_count()
 209      {
 210          return count(self::$symbol_table);
 211      }
 212  
 213      public static function Symbol_arrayof()
 214      {
 215          return array_values(self::$symbol_table);
 216      }
 217  
 218      public static function Symbol_find($x)
 219      {
 220          if (isset(self::$symbol_table[$x])) {
 221              return self::$symbol_table[$x];
 222          }
 223          return 0;
 224      }
 225  
 226      /**
 227       * Sort function helper for symbols
 228       * 
 229       * Symbols that begin with upper case letters (terminals or tokens)
 230       * must sort before symbols that begin with lower case letters
 231       * (non-terminals).  Other than that, the order does not matter.
 232       * 
 233       * We find experimentally that leaving the symbols in their original
 234       * order (the order they appeared in the grammar file) gives the
 235       * smallest parser tables in SQLite.
 236       * @param PHP_ParserGenerator_Symbol
 237       * @param PHP_ParserGenerator_Symbol
 238       */
 239      public static function sortSymbols($a, $b)
 240      {
 241          $i1 = $a->index + 10000000*(ord($a->name[0]) > ord('Z'));
 242          $i2 = $b->index + 10000000*(ord($b->name[0]) > ord('Z'));
 243          return $i1 - $i2;
 244      }
 245  
 246      /**
 247       * Return true if two symbols are the same.
 248       */
 249      public static function same_symbol(PHP_ParserGenerator_Symbol $a, PHP_ParserGenerator_Symbol $b)
 250      {
 251          if ($a === $b) return 1;
 252          if ($a->type != self::MULTITERMINAL) return 0;
 253          if ($b->type != self::MULTITERMINAL) return 0;
 254          if ($a->nsubsym != $b->nsubsym) return 0;
 255          for ($i = 0; $i < $a->nsubsym; $i++) {
 256              if ($a->subsym[$i] != $b->subsym[$i]) return 0;
 257          }
 258          return 1;
 259      }
 260  }