[Summary view] [Print] [Text view]

   1  <?php
   2  /*
   3   [The "BSD licence"]
   4   Copyright (c) 2005-2008 Terence Parr
   5   All rights reserved.
   6  
   7   Redistribution and use in source and binary forms, with or without
   8   modification, are permitted provided that the following conditions
   9   are met:
  10   1. Redistributions of source code must retain the above copyright
  11      notice, this list of conditions and the following disclaimer.
  12   2. Redistributions in binary form must reproduce the above copyright
  13      notice, this list of conditions and the following disclaimer in the
  14      documentation and/or other materials provided with the distribution.
  15   3. The name of the author may not be used to endorse or promote products
  16      derived from this software without specific prior written permission.
  17  
  18   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19   IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20   OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21   IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22   INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23   NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27   THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29  
  30  /** A DFA implemented as a set of transition tables.
  31   *
  32   *  Any state that has a semantic predicate edge is special; those states
  33   *  are generated with if-then-else structures in a specialStateTransition()
  34   *  which is generated by cyclicDFA template.
  35   *
  36   *  There are at most 32767 states (16-bit signed short).
  37   *  Could get away with byte sometimes but would have to generate different
  38   *  types and the simulation code too.  For a point of reference, the Java
  39   *  lexer's Tokens rule DFA has 326 states roughly.
  40   */
  41  class DFA {
  42      protected $eot;
  43      protected $eof;
  44      protected $min;
  45      protected $max;
  46      protected $accept;
  47      protected $special;
  48      protected $transition;
  49  
  50      protected $decisionNumber;
  51  
  52      /** Which recognizer encloses this DFA?  Needed to check backtracking */
  53      protected $recognizer;
  54  
  55      public $debug = false;
  56  
  57      /** From the input stream, predict what alternative will succeed
  58       *  using this DFA (representing the covering regular approximation
  59       *  to the underlying CFL).  Return an alternative number 1..n.  Throw
  60       *  an exception upon error.
  61       */
  62      //TODO: This is a hackish way of doing a try finally, replace this by bunching up the returns.
  63      //Possibly rewrite  predict. There is one more place i might need to fix, where i thought 
  64      //try{}catch(ex){[work]; throw ex}; [work]; would be the same as a try finally;
  65      
  66  	public function predict($input){
  67          if ( $this->debug ) {
  68              echo ("Enter DFA.predict for decision ".$this->decisionNumber);
  69          }
  70          $mark = $input->mark(); // remember where decision started in input
  71          try {
  72              $ret = $this->_predict($input);
  73              
  74          }
  75          catch(Exception $e) {
  76              $input->rewind($mark);
  77              throw $e;
  78          }
  79          $input->rewind($mark);
  80          return $ret;
  81      }
  82      
  83  	public function _predict($input) {
  84          $s = 0; // we always start at s0
  85              while ( true ) {
  86                  if ( $this->debug ) echo ("DFA ".$this->decisionNumber." state ".$s." LA(1)=".$input->LA(1)."(".$input->LA(1)."), index=".$input->index());
  87                  $specialState = $this->special[$s];
  88                  if ( $specialState>=0 ) {
  89                      if ( $this->debug ) {
  90                          echo ("DFA ".$this->decisionNumber.
  91                              " state ".$s." is special state ".$specialState);
  92                      }
  93                      $s = $this->specialStateTransition($specialState, $input);
  94                      if ( $this->debug ) {
  95                          echo ("DFA ".$this->decisionNumber.
  96                              " returns from special state ".$specialState." to ".s);
  97                      }
  98                      if ( $s==-1 ) {
  99                          $this->noViableAlt($s, $input);
 100                          return 0;
 101                      }
 102                      $input->consume();
 103                      continue;
 104                  }
 105                  
 106                  if ( $this->accept[$s] >= 1 ) {
 107                      if ( $this->debug ) echo ("accept; predict "+$this->accept[$s]+" from state "+$this->s);
 108                      return $this->accept[$s];
 109                  }
 110                  // look for a normal char transition
 111                  $c = $input->LA(1); // -1 == \uFFFF, all tokens fit in 65000 space
 112                  if ($c>=$this->min[$s] && $c<=$this->max[$s]) {
 113                      $snext = $this->transition[$s][$c-$this->min[$s]]; // move to next state
 114                      if ( $snext < 0 ) {
 115                          // was in range but not a normal transition
 116                          // must check EOT, which is like the else clause.
 117                          // eot[s]>=0 indicates that an EOT edge goes to another
 118                          // state.
 119                          if ( $this->eot[$s]>=0 ) {  // EOT Transition to accept state?
 120                              if ( $this->debug ) echo("EOT transition");
 121                              $s = $this->eot[$s];
 122                              $input->consume();
 123                              // TODO: I had this as return accept[eot[s]]
 124                              // which assumed here that the EOT edge always
 125                              // went to an accept...faster to do this, but
 126                              // what about predicated edges coming from EOT
 127                              // target?
 128                              continue;
 129                          }
 130                          $this->noViableAlt($s,$input);
 131                          return 0;
 132                      }
 133                      $s = $snext;
 134                      $input->consume();
 135                      continue;
 136                  }
 137                  if ( $eot[$s]>=0 ) {  // EOT Transition?
 138                      if ( $this->debug ) println("EOT transition");
 139                      $s = $this->eot[$s];
 140                      $input->consume();
 141                      continue;
 142                  }
 143                  if ( $c==Token::$EOF && $eof[$s]>=0 ) {  // EOF Transition to accept state?
 144                      if ( $this->debug ) echo ("accept via EOF; predict "+$this->accept[$eof[$s]]+" from "+$eof[$s]);
 145                      return $this->accept[$eof[$s]];
 146                  }
 147                  // not in range and not EOF/EOT, must be invalid symbol
 148                  if ( $this->debug ) {
 149                      echo("min[".$s."]=".$this->min[$s]);
 150                      echo("max[".$s."]=".$this->max[$s]);
 151                      echo("eot[".$s."]=".$this->eot[$s]);
 152                      echo("eof[".$s."]=".$this->eof[$s]);
 153                      for ($p=0; $p<$this->transition[$s]->length; $p++) {
 154                          echo $this->transition[$s][$p]+" ";
 155                      }
 156                      echo "\n";
 157                  }
 158                  $this->noViableAlt($s, $input);
 159                  return 0;
 160              }
 161  
 162      }
 163  
 164  	function noViableAlt($s, $input){
 165          if ($this->recognizer->state->backtracking>0) {
 166              $this->recognizer->state->failed=true;
 167              return;
 168          }
 169          $nvae =
 170              new NoViableAltException($this->getDescription(),
 171                                       $decisionNumber,
 172                                       $s,
 173                                       $input);
 174          $this->error($nvae);
 175          throw $nvae;
 176      }
 177  
 178      /** A hook for debugging interface */
 179  	protected function error($nvae) { ; }
 180  
 181  	function specialStateTransition($s, $input)
 182      {
 183          return -1;
 184      }
 185  
 186  	public function getDescription() {
 187          return "n/a";
 188      }
 189  
 190      /** Given a String that has a run-length-encoding of some unsigned shorts
 191       *  like "\1\2\3\9", convert to short[] {2,9,9,9}.  We do this to avoid
 192       *  static short[] which generates so much init code that the class won't
 193       *  compile. :(
 194       */
 195  	public static function unpackEncodedString($encodedString) {
 196          $data = array();
 197          $di = 0;
 198          for ($i=0,$len=strlen($encodedString); $i<$len; $i+=2) {
 199              $n = charAt($encodedString, $i);
 200              $v = charAt($encodedString, $i+1);
 201              // add v n times to data
 202              for ($j=1; $j<=$n; $j++) {
 203                  if($v==0xff) $v=-1;
 204                  $data[$di++] = $v;
 205              }
 206          }
 207          return $data;
 208      }
 209      
 210  	function __call($fn, $params){
 211          return call_user_func_array(array($this->recognizer, $fn), $params);
 212      }
 213  }
 214  
 215  ?>