src/op5/ninja_sdk/parsegen/LalrStateMachine.php

   1 <?php
   2
   3 require_once( 'LalrItem.php' );
   4 require_once( 'LalrState.php' );
   5 require_once( 'LalrGrammar.php' );
   6
   7 class LalrStateMachine {
   8         /**
   9          *
  10          * @var LalrGrammar
  11          */
  12         private $grammar;
  13         private $states;
  14         private $statetable;
  15         private $errortable;
  16
  17         public function __construct( LalrGrammar $grammar ) {
  18                 $this->grammar = $grammar;
  19
  20                 $this->build_states();
  21                 $this->build_table();
  22         }
  23
  24         private function build_states() {
  25                 $state_queue = array(
  26                                 new LalrState( $this->grammar->get('entry'), $this->grammar )
  27                                 );
  28
  29                 $this->states = array();
  30
  31                 while( count( $state_queue ) ) {
  32                         $state = array_pop( $state_queue );
  33                         $this->states[] = $state;
  34
  35                         $next_symbols = $state->next_symbols();
  36
  37                         foreach( $next_symbols as $sym ) {
  38                                 if( $sym == 'end' ) continue;
  39                                 $sub_state = $state->take( $sym );
  40
  41                                 if( !$this->has_state( $sub_state ) ) {
  42                                         $state_queue[] = $sub_state;
  43                                 }
  44                         }
  45                 }
  46         }
  47
  48         private function build_table() {
  49                 $this->statetable = array();
  50                 $this->errortable = array();
  51                 foreach( $this->states as $i => $state ) {
  52                         /* @var $state LalrState */
  53                         $transistions = array();
  54
  55                         /* reduce */
  56                         foreach( $state->closure() as $item ) {
  57                                 if( $item->complete() ) {
  58                                         foreach( $this->grammar->follow( $item->generates() ) as $sym ) {
  59                                                 if( !isset( $transistions[$sym] ) ) {
  60                                                         $transistions[$sym] = array();
  61                                                 }
  62                                                 $transistions[$sym][] = 'reduce:'.$item->get_name();
  63                                         }
  64                                 }
  65                         }
  66
  67                         /* shift */
  68                         foreach( $state->next_symbols() as $sym ) {
  69                                 if( $sym == 'end' ) {
  70                                         if( !isset( $transistions[$sym] ) ) {
  71                                                 $transistions[$sym] = array();
  72                                         }
  73                                         $transistions[$sym][] = 'accept:';
  74                                 } else {
  75                                         $next_state = $state->take( $sym );
  76                                         $j = $this->get_state_id( $next_state );
  77                                         if( $j === false ) {
  78                                                 throw new GeneratorException( "ERROR in parser generator, should never happend...");
  79                                         }
  80                                         if( $this->grammar->is_terminal($sym) ) {
  81                                                 if( !isset( $transistions[$sym] ) ) {
  82                                                         $transistions[$sym] = array();
  83                                                 }
  84                                                 $transistions[$sym][] = 'shift:'.$j;
  85                                         }
  86                                 }
  87                         }
  88
  89                         /* goto */
  90                         foreach( $this->grammar->non_terminals() as $sym ) {
  91                                 $next_state = $state->take( $sym );
  92                                 $j = $this->get_state_id( $next_state );
  93                                 if( $j !== false ) {
  94                                         if( !isset( $transistions[$sym] ) ) {
  95                                                 $transistions[$sym] = array();
  96                                         }
  97                                         $transistions[$sym][] = 'goto:'.$j;
  98                                 }
  99                         }
 100
 101                         /* Error handlers */
 102                         $errors = $state->errors();
 103
 104                         if( empty($errors) ) {
 105                                 /* Insert pop error handler */
 106                                 $errorhandler = 'pop';
 107                         } else {
 108                                 /* Insert shift error handler */
 109                                 $errorhandler = 'shift';
 110                                 foreach( $errors as $sym => $errorrule ) {
 111                                         if(!isset($transistions[$sym])) {
 112                                                 $transistions[$sym] = array('error:'.$errors[$sym]->get_name());
 113                                         }
 114                                 }
 115                         }
 116
 117                         /* Resolve ambiguities */
 118                         $resolved_transitions = array();
 119                         foreach( $transistions as $sym => $trans ) {
 120                                 if(count($trans)>1) {
 121                                         /* TODO: resolve ambiguities depending on rule/token priorities and left/right recursion
 122                                          * Allowing defined grammar ambiguities and resolving those here makes the parse table smaller and parsing faster.
 123                                          * Also, the if a then if b else c-ambiguity can be resolved (else has higher priority than if, triggering a shift before reduce)
 124                                          */
 125                                         throw new GeneratorException( "Ambigous grammar\n".var_export($transistions,true)."\nAdding: $sym\n".$state);
 126                                 } else {
 127                                         $resolved_transitions[$sym] = $trans[0];
 128                                 }
 129                         }
 130
 131                         $this->statetable[$i] = $resolved_transitions;
 132                         $this->errortable[$i] = $errorhandler;
 133                 }
 134         }
 135
 136         private function has_state( $state ) {
 137                 return $this->get_state_id( $state ) !== false;
 138         }
 139
 140         private function get_state_id( $state ) {
 141                 foreach( $this->states as $i=>$cur_state ) {
 142                         if( $cur_state->equals($state) ) {
 143                                 return $i;
 144                         }
 145                 }
 146                 return false;
 147         }
 148
 149         public function get_statetable() {
 150                 return $this->statetable;
 151         }
 152
 153         public function get_errortable() {
 154                 return $this->errortable;
 155         }
 156
 157         public function get_default_error_handler($stateid) {
 158                 return $this->errortable[$stateid];
 159         }
 160
 161         public function get_state( $state_id ) {
 162                 return $this->states[$state_id];
 163         }
 164
 165         public function __toString() {
 166                 $outp = "";
 167                 foreach( $this->states as $i => $state ) {
 168                         $outp .= "===== State $i =====\n";
 169                         $outp .= $state;
 170                         $outp .= "\n";
 171
 172                         foreach( $this->statetable[$i] as $sym => $action ) {
 173                                 $outp .= sprintf( "%20s: ", $sym );
 174                                 list( $a, $t ) = $action;
 175                                 $outp .= "$a $t";
 176                                 $outp .= "\n";
 177                         }
 178                         $outp .= "\n";
 179                 }
 180                 return $outp;
 181         }
 182 }