src/op5/ninja_sdk/parsegen/js/LalrParserJSGenerator.php

   1 <?php
   2
   3 class LalrParserJSGenerator extends js_class_generator {
   4         private $fsm;
   5         /**
   6          * Reference to the grammar object
   7          * @var LalrGrammar
   8          */
   9         private $grammar;
  10         private $goto_map;
  11
  12         public function __construct( $parser_name, $fsm, $grammar ) {
  13                 $this->classname = $parser_name . "Parser";
  14                 $this->grammar = $grammar;
  15                 $this->fsm = $fsm;
  16
  17
  18                 $this->goto_map = array();
  19                 foreach( $this->fsm->get_statetable() as $state_id => $map ) {
  20                         foreach( $map as $symbol => $action_arr ) {
  21                                 list( $action, $target ) = explode(':',$action_arr,2);
  22                                 if( $action == 'goto' ) {
  23                                         if( !isset( $this->goto_map[$symbol] ) )
  24                                                 $this->goto_map[$symbol] = array();
  25                                         $this->goto_map[$symbol][$state_id] = $target;
  26                                 }
  27                         }
  28                 }
  29         }
  30
  31         public function generate($skip_generated_note = false) {
  32                 parent::generate($skip_generated_note);
  33
  34                 $this->init_class(array('visitor'));
  35                 $this->variable( 'visitor' );
  36                 $this->variable( 'stack', array() );
  37                 $this->variable( 'cont', false );
  38                 $this->variable( 'done', false );
  39                 $this->variable( 'lexer', false );
  40                 $this->write( 'this.visitor = visitor;' );
  41                 $this->generate_parse();
  42
  43                 $this->write( 'this.states = [' );
  44                 foreach( $this->fsm->get_statetable() as $state_id => $map ) {
  45                         $this->generate_state( $state_id, $map );
  46                 }
  47                 $this->write( '];' );
  48                 foreach( $this->grammar->get_rules() as $name => $item ) {
  49                         $this->generate_reduce( $item );
  50                 }
  51                 foreach( $this->grammar->get_errors() as $name => $error ) {
  52                         $this->comment( $name );
  53                         $this->generate_error( $error );
  54                 }
  55                 $this->generate_errorhandler();
  56                 $this->finish_class();
  57         }
  58
  59         private function generate_parse() {
  60                 $this->init_function( 'parse', array( 'lexer' ) );
  61                 $this->write( 'this.stack = new Array();' );
  62                 $this->write( 'this.stack.push( %s );', array(0,"start"));
  63                 $this->write( 'this.done = false;' );
  64                 $this->write( 'this.lexer = lexer;' );
  65                 $this->write( 'var result = false;' );
  66                 $this->write( 'do {' );
  67                 $this->write(   'this.token = lexer.fetch_token();' );
  68                 $this->write(   'do {' );
  69                 $this->write(     'this.cont = false;' );
  70                 $this->write(     'var head = this.stack[this.stack.length-1];' );
  71
  72                 /* Fixme: How to better call the method and not losing "this"? */
  73                 $this->write(     'this.tmp = this.states[head[0]];' );
  74                 $this->write(     'result = this.tmp();');
  75
  76                 $this->write(   '} while( this.cont );' );
  77                 $this->write( '} while( !this.done );' );
  78                 $this->write( 'return result;' );
  79                 $this->finish_function();
  80         }
  81
  82         private function generate_state( $state_id, $map ) {
  83                 $state = $this->fsm->get_state($state_id);
  84                 /* @var $state LalrState */
  85
  86                 $this->init_function( false, array(), 'private' );
  87                 //              $this->comment( "State: $state_id\n".trim(strval( $state )) );
  88                 $this->comment( "State: $state_id" );
  89
  90                 $nextup = array();
  91                 foreach( $state->next_symbols() as $sym ) {
  92                         if( $this->grammar->is_terminal($sym) ) {
  93                                 $nextup[] = $sym;
  94                         }
  95                 }
  96
  97                 $this->write( 'switch( this.token[0] ) {' );
  98
  99                 /* Merge cases per action... many cases use same action... */
 100                 $map_r = array();
 101                 foreach( $map as $token => $action_arr ) {
 102                         if(!isset($map_r[$action_arr])) $map_r[$action_arr] = array();
 103                         $map_r[$action_arr][] = $token;
 104                 }
 105                 foreach( $map_r as $action_arr => $tokens ) {
 106                         list( $action, $target ) = explode(':',$action_arr,2);
 107                         if( $action == 'goto' ) continue;
 108                         foreach( $tokens as $token ) {
 109                                 $this->write( 'case %s:', $token );
 110                         }
 111                         $this->comment( $action_arr );
 112                         switch( $action ) {
 113                                 case 'shift':
 114                                         $this->write( 'this.stack.push( [%s,this.token] );', intval($target) );
 115                                         $this->write( 'return null;' );
 116                                         break;
 117                                 case 'reduce':
 118                                         $this->write( 'this.reduce_'.$target.'();');
 119                                         $this->write( 'return null;' );
 120                                         break;
 121                                 case 'accept':
 122                                         $this->write( 'var program = this.stack.pop();');
 123                                         $this->write( 'this.done = true;' );
 124                                         $this->write( 'return this.visitor.accept(program[1][1]);');
 125                                         break;
 126                         }
 127                 }
 128                 $this->write( '}' );
 129                 $this->write( 'this.errorhandler();');
 130
 131                 $this->write( 'return null;' );
 132                 $this->write( '},' ); // FIXME: Should be finish_function, but with , instead of ;
 133         }
 134
 135         private function generate_reduce( $item ) {
 136                 if( isset($this->goto_map[$item->generates()]) ) {
 137                         $targets = $this->goto_map[$item->generates()];
 138                 } else {
 139                         return; /* This method isn't used appearently */
 140                 }
 141
 142                 $this->init_function( 'reduce_'.$item->get_name(), array(), 'private' );
 143                 $this->write( 'this.cont = true;' );
 144
 145                 $args = array();
 146                 $length_sum = array();
 147                 foreach( array_reverse($item->get_symbols(),true) as $i => $symbol ) {
 148                         $this->write( 'var arg'.$i.' = this.stack.pop();');
 149                         $length_sum[] = 'arg'.$i.'[1][3]';
 150                         if( $item->symbol_enabled($i) ) {
 151                                 $args[] = 'arg'.$i.'[1][1]';
 152                         }
 153                 }
 154                 $length_sum = implode('+',$length_sum);
 155                 $item_name = $item->get_name();
 156                 if( $item_name[0] == '_' ) {
 157                         if( count( $args ) != 1 ) {
 158                                 throw new GeneratorException( "Rule $item_name can not be used as transparent. Should have exactly one usable argument" );
 159                         }
 160                         $this->write( 'var new_token = [%s, '.$args[0].', arg0[1][2], '.$length_sum.'];', $item->generates());
 161                 } else {
 162                         $this->write( 'var new_token = [%s, this.visitor.visit_'.$item->get_name().'('.implode(',',array_reverse($args)).'), arg0[1][2], '.$length_sum.'];', $item->generates());
 163                 }
 164                 $this->write( 'switch( this.stack[this.stack.length-1][0] ) {' );
 165
 166                 /* Merge cases */
 167                 $cases = array();
 168                 foreach( $targets as $old_state => $new_state ) {
 169                         if( !isset( $cases[$new_state] ) ) $cases[$new_state] = array();
 170                         $cases[$new_state][] = $old_state;
 171                 }
 172
 173                 foreach( $cases as $new_state => $old_states ) {
 174                         foreach( $old_states as $old_state ) {
 175                                 $this->write( 'case %s:', $old_state );
 176                         }
 177                         $this->write( 'this.stack.push([%s,new_token]); break;', $new_state );
 178                 }
 179                 $this->write( '}' );
 180                 $this->comment( 'error handler...' );
 181                 $this->write( 'return null;' );
 182                 $this->finish_function();
 183         }
 184
 185         private function generate_error( $error ) {
 186                 if( isset($this->goto_map[$error->generates()]) ) {
 187                         $targets = $this->goto_map[$error->generates()];
 188                 } else {
 189                         return; /* This method isn't used appearently */
 190                 }
 191
 192                 $this->init_function( 'error_'.$error->get_name(), array('stack', 'tokens'), 'private' );
 193
 194                 $this->write('if(typeof this.visitor.error_'.$error->get_name().' == "undefined"){');
 195                 $this->write('throw "Parse error at: " + this.lexer.tokens_to_string(tokens);');
 196                 $this->write('}');
 197
 198                 /* Handle error */
 199                 $this->write('var value = this.visitor.error_'.$error->get_name().'(stack, tokens, this.lexer);');
 200
 201                 /* Generate new token */
 202                 $this->write('var new_token = [%s,value,0,0];', $error->generates());
 203
 204                 /* Merge cases */
 205                 $cases = array();
 206                 foreach( $targets as $old_state => $new_state ) {
 207                         if( !isset( $cases[$new_state] ) ) $cases[$new_state] = array();
 208                         $cases[$new_state][] = $old_state;
 209                 }
 210
 211                 $this->write( 'switch( this.stack[this.stack.length-1][0] ) {' );
 212                 foreach( $cases as $new_state => $old_states ) {
 213                         foreach( $old_states as $old_state ) {
 214                                 $this->write( 'case %s:', $old_state );
 215                         }
 216                         $this->write( 'this.stack.push([%s,new_token]); break;', $new_state );
 217                 }
 218                 $this->write( '}' );
 219                 $this->finish_function();
 220         }
 221
 222         private function generate_errorhandler() {
 223                 $this->init_function( 'errorhandler', array(), 'private' );
 224
 225                 $pop_states = array();
 226                 $shift_states = array();
 227
 228                 foreach( $this->fsm->get_statetable() as $state_id => $map ) {
 229                         switch($this->fsm->get_default_error_handler($state_id)) {
 230                                 case 'pop':
 231                                         $pop_states[] = $state_id;
 232                                         break;
 233                                 case 'shift':
 234                                         $shift_states[$state_id] = $map;
 235                                         break;
 236                         }
 237                 }
 238
 239
 240                 $this->write( 'var errorstack = [];' );
 241                 $this->write( 'var errortokens = [];' );
 242
 243                 $this->write( 'var running = true;');
 244                 $this->write( 'while( running ) {' );
 245                 $this->write( 'switch( this.stack[this.stack.length-1][0] ) {' );
 246                 foreach($pop_states as $state_id) {
 247                         $this->write( 'case %d:', $state_id );
 248                 }
 249                 $this->write( 'var errtok = this.stack.pop();');
 250                 $this->write( 'errorstack.unshift(errtok);');
 251                 $this->write( 'break;' );
 252                 $this->write( 'default:' );
 253                 $this->write( 'running = false;' );
 254                 $this->write( '}' );
 255                 $this->write( '}' );
 256
 257
 258
 259                 $this->write( 'running = true;' );
 260                 $this->write( 'while( running ) {');
 261                 $this->write( 'switch(this.stack[this.stack.length-1][0]) {');
 262                 foreach($shift_states as $state_id => $map) {
 263                         $this->write( 'case %d:', $state_id );
 264                         $this->write( 'switch( this.token[0] ) {' );
 265                         /* Merge cases per action... many cases use same action... */
 266                         $map_r = array();
 267                         foreach( $map as $token => $action_arr ) {
 268                                 if(!isset($map_r[$action_arr])) $map_r[$action_arr] = array();
 269                                 $map_r[$action_arr][] = $token;
 270                         }
 271                         foreach( $map_r as $action_arr => $tokens ) {
 272                                 list( $action, $target ) = explode(':',$action_arr,2);
 273                                 if( $action != 'error' ) continue;
 274                                 foreach( $tokens as $token ) {
 275                                         $this->write( 'case %s:', $token );
 276                                 }
 277                                 $this->comment( $action_arr );
 278
 279                                 $this->write('this.error_'.$target.'(errorstack, errortokens);');
 280                                 $this->write('this.cont = true;');
 281                                 $this->write('running = false;');
 282
 283                                 $this->write('break;');
 284                                 $this->write( 'default:' );
 285                                 /* FIXME: fix this nicer: let parse method handle this... */
 286                                 $this->write( 'errortokens.push(this.token);' );
 287                                 $this->write( 'this.token = this.lexer.fetch_token();' );
 288                         }
 289                         $this->write( '}' );
 290                         $this->write( 'break;' );
 291                 }
 292                 $this->write( 'default:' );
 293                 /* This shouldn't happen, but if it does, don't kill the browser */
 294                 $this->write( 'throw "Internal parser error...";' );
 295                 $this->write( 'return false;' );
 296                 $this->write( '}' );
 297                 $this->write( '}' );
 298
 299                 $this->write('return true;');
 300                 $this->finish_function();
 301         }
 302 }