src/op5/ninja_sdk/parsegen/LalrGrammar.php

   1 <?php
   2
   3 require_once( 'LalrItem.php' );
   4 require_once( 'LalrError.php' );
   5
   6 class LalrGrammar {
   7         private $tokens;
   8         private $rules;
   9         private $errors;
  10
  11         public function __construct( $grammar ) {
  12                 $this->tokens = array_map( 'trim', $grammar['tokens'] );
  13                 $this->rules = array();
  14
  15                 foreach( $grammar['rules'] as $name => $rule ) {
  16                         $rule = array_map( 'trim', $rule );
  17                         $generates = array_shift( $rule );
  18                         $this->rules[$name] = new LalrItem( $name, $generates, $rule );
  19                 }
  20
  21                 $this->errors = array();
  22                 if( isset($grammar['errors']) ) {
  23                         foreach( $grammar['errors'] as $name => $error ) {
  24                                 $error = array_map( 'trim', $error );
  25                                 $generates = array_shift( $error );
  26                                 if(isset($this->errors[$generates])) {
  27                                         /* FIXME: conflicting error handlers */
  28                                 }
  29                                 if(empty($error)) {
  30                                         foreach($this->rules as $rule ) {
  31                                                 foreach( $this->follow($generates) as $next ) {
  32                                                         if( !in_array( $next, $error ) ) {
  33                                                                 $error[] = $next;
  34                                                         }
  35                                                 }
  36                                         }
  37                                 }
  38                                 $this->errors[$generates] = new LalrError( $name, $generates, $error );
  39                         }
  40                 }
  41
  42                 /* If no default error handler exists, inject it */
  43                 $program_element = $this->rules['entry']->next();
  44                 if(!isset($this->errors[$program_element])) {
  45                         /* As the default error handler is to kill the parser without recover, we only end at the end token, and not in the middle of the parse */
  46                         $error = array('end');
  47                         $this->errors[$program_element] = new LalrError( 'default_error_handler', $program_element, array('end'));
  48                 }
  49         }
  50
  51         public function get_tokens() {
  52                 return $this->tokens;
  53         }
  54
  55         public function get_rules() {
  56                 return $this->rules;
  57         }
  58
  59         public function get_errors() {
  60                 return $this->errors;
  61         }
  62
  63         public function get( $name ) {
  64                 if( !isset( $this->rules[$name] ) )
  65                         return false;
  66                 return $this->rules[$name];
  67         }
  68
  69         public function productions( $symbol ) {
  70                 $items = array();
  71                 foreach( $this->rules as $item ) {
  72                         if( $item->produces( $symbol ) ) {
  73                                 $items[] = $item;
  74                         }
  75                 }
  76                 return $items;
  77         }
  78
  79         public function is_terminal( $symbol ) {
  80                 if( $symbol == 'end' ) return true;
  81                 return isset( $this->tokens[$symbol] );
  82         }
  83
  84         public function terminals() {
  85                 $symbols = array('end');
  86                 foreach( $this->tokens as $sym => $re ) {
  87                         if( $sym[0] != '.' ) {
  88                                 $symbols[] = $sym;
  89                         }
  90                 }
  91                 return $symbols;
  92         }
  93
  94         public function non_terminals() {
  95                 $symbols = array();
  96                 foreach( $this->rules as $rule ) {
  97                         if( !in_array( $rule->generates(), $symbols ) ) {
  98                                 $symbols[] = $rule->generates();
  99                         }
 100                 }
 101                 return $symbols;
 102         }
 103
 104         public function symbols() {
 105                 return array_merge( $this->terminals(), $this->non_terminals() );
 106         }
 107
 108         public function follow( $symbol ) {
 109                 $next = array();
 110                 $search_list = array($symbol);
 111
 112                 /* Exctract next */
 113                 for( $i=0; $i < count( $search_list ); $i++ ) {
 114                         $cur_symbol = $search_list[$i];
 115                         foreach( $this->rules as $rule ) {
 116                                 foreach( $rule->follow( $cur_symbol ) as $sym ) {
 117                                         if( $sym === false ) {
 118                                                 $gen = $rule->generates();
 119                                                 if( !in_array( $gen, $search_list ) ) {
 120                                                         $search_list[] = $gen;
 121                                                 }
 122                                         } else {
 123                                                 $next[] = $sym;
 124                                         }
 125                                 }
 126                         }
 127                 }
 128
 129                 /* Reduce to next terminal */
 130                 $next_term = array();
 131                 for( $i=0; $i<count($next);$i++ ) {
 132                         if( $this->is_terminal($next[$i]) ) {
 133                                 if( !in_array( $next[$i], $next_term ) ) {
 134                                         $next_term[] = $next[$i];
 135                                 }
 136                         } else {
 137                                 foreach( $this->productions($next[$i]) as $rule ) {
 138                                         $next_sym = $rule->next();
 139                                         if( $next_sym === false ) {
 140                                                 print_r( $rule );
 141                                         } else {
 142                                                 if( !in_array( $next_sym, $next ) ) {
 143                                                         $next[] = $next_sym;
 144                                                 }
 145                                         }
 146                                 }
 147                         }
 148                 }
 149
 150                 return $next_term;
 151         }
 152
 153         public function errors($sym) {
 154                 if(!isset($this->errors[$sym]))
 155                         return false;
 156                 return $this->errors[$sym];
 157         }
 158
 159         public function __toString() {
 160                 $outp = "";
 161                 foreach( $this->tokens as $name => $el ) {
 162                         $outp .= $name . ' = ' . strval($el)."\n";
 163                 }
 164                 foreach( $this->rules as $el ) {
 165                         $outp .= strval($el)."\n";
 166                 }
 167                 foreach( $this->errors as $el ) {
 168                         $outp .= strval($el)."\n";
 169                 }
 170                 return $outp;
 171         }
 172 }