Hoa central
Ll1.php
Go to the documentation of this file.
1 <?php
2 
37 namespace Hoa\Compiler;
38 
42 _define('GO', 'GO');
43 _define('__', '__');
44 
53 abstract class Ll1
54 {
62  protected $_initialLine = 0;
63 
77  protected $_skip = [];
78 
109  protected $_tokens = [];
110 
146  protected $_states = [];
147 
161  protected $_terminal = [];
162 
200  protected $_transitions = [];
201 
272  protected $_actions = [];
273 
277  protected $_names = [];
278 
284  private $_stack = [];
285 
291  protected $buffers = [];
292 
298  protected $line = 0;
299 
305  protected $column = 0;
306 
312  protected static $_cache = [];
313 
319  protected static $_cacheEnabled = true;
320 
321 
322 
335  public function __construct(
336  Array $skip,
337  Array $tokens,
338  Array $states,
339  Array $terminal,
340  Array $transitions,
341  Array $actions,
342  Array $names = []
343  ) {
344  $this->setSkip($skip);
345  $this->setTokens($tokens);
346  $this->setStates($states);
347  $this->setTerminal($terminal);
348  $this->setTransitions($transitions);
349  $this->setActions($actions);
350  $this->setNames($names);
351 
352  return;
353  }
354 
363  public function compile($in)
364  {
365  $cacheId = md5($in);
366 
367  if (true === self::$_cacheEnabled &&
368  true === array_key_exists($cacheId, self::$_cache)) {
369  return self::$_cache[$cacheId];
370  }
371 
372  $d = 0;
373  $c = 0; // current automata.
374  $_skip = array_flip($this->_skip);
375  $_tokens = array_flip($this->_tokens[$c]);
376  $_states = array_flip($this->_states[$c]);
377  $_actions = [$c => 0];
378 
379  $nextChar = null;
380  $nextToken = 0;
381  $nextState = $_states['GO'];
382  $nextAction = $_states['GO'];
383 
384  $this->line = $this->getInitialLine();
385  $this->column = 0;
386 
387  $this->buffers = [];
388 
389  $line = $this->line;
391 
392  $this->pre($in);
393 
394  for ($i = 0, $max = strlen($in); $i <= $max; $i++) {
395 
396  //echo "\n---\n\n";
397 
398  // End of parsing (not automata).
399  if ($i == $max) {
400  while ($c > 0 &&
401  in_array($this->_states[$c][$nextState], $this->_terminal[$c])) {
402  list($c, $nextState, ) = array_pop($this->_stack);
403  }
404 
405  if (in_array($this->_states[$c][$nextState], $this->_terminal[$c]) &&
406  0 === $c &&
407  true === $this->end()) {
408 
409  //echo '*********** END REACHED **********' . "\n";
410 
411  if (true === self::$_cacheEnabled) {
412  self::$_cache[$cacheId] = $this->getResult();
413  }
414 
415  return true;
416  }
417 
419  'End of code has been reached but not correctly; ' .
420  'maybe your program is not complete?',
421  0
422  );
423  }
424 
425  $nextChar = $in[$i];
426 
427  // Skip.
428  if (isset($_skip[$nextChar])) {
429  if ("\n" === $nextChar) {
430  $line++;
431  $column = 0;
432  } else {
433  $column++;
434  }
435 
436  continue;
437  } else {
438  $continue = false;
439  $handle = substr($in, $i);
440 
441  foreach ($_skip as $sk => $e) {
442  if ($sk[0] != '#') {
443  continue;
444  }
445 
446  $sk = str_replace('#', '\#', substr($sk, 1));
447 
448  if (0 != preg_match('#^(' . $sk . ')#u', $handle, $match)) {
449  $strlen = strlen($match[1]);
450 
451  if ($strlen > 0) {
452  if (false !== $offset = strrpos($match[1], "\n")) {
453  $column = $strlen - $offset - 1;
454  } else {
455  $column += $strlen;
456  }
457 
458  $line += substr_count($match[1], "\n");
459  $i += $strlen - 1;
460  $continue = true;
461 
462  break;
463  }
464  }
465  }
466 
467  if (true === $continue) {
468  continue;
469  }
470  }
471 
472  // Epsilon-transition.
473  $epsilon = false;
474  while (array_key_exists($nextToken, $this->_actions[$c][$nextState]) &&
475  (
476  (
477  is_array($this->_actions[$c][$nextState][$nextToken]) &&
478  0 < $foo = $this->_actions[$c][$nextState][$nextToken][0]
479  ) ||
480  (
481  is_int($this->_actions[$c][$nextState][$nextToken]) &&
482  0 < $foo = $this->_actions[$c][$nextState][$nextToken]
483  )
484  )
485  ) {
486  $epsilon = true;
487 
488  if ($_actions[$c] == 0) {
489 
490  //echo '*** Change automata (up to ' . ($foo - 1) . ')' . "\n";
491 
492  $this->_stack[$d] = [$c, $nextState, $nextToken];
493  end($this->_stack);
494 
495  $c = $foo - 1;
496  $_tokens = array_flip($this->_tokens[$c]);
497  $_states = array_flip($this->_states[$c]);
498 
499  $nextState = $_states['GO'];
500  $nextAction = $_states['GO'];
501  $nextToken = 0;
502 
503  $_actions[$c] = 0;
504 
505  $d++;
506  } elseif ($_actions[$c] == 2) {
507  $_actions[$c] = 0;
508 
509  break;
510  }
511  }
512 
513  if (true === $epsilon) {
514  $epsilon = false;
515  $nextToken = false;
516  }
517 
518  // Token.
519  if (isset($_tokens[$nextChar])) {
520  $token = $nextChar;
521  $nextToken = $_tokens[$token];
522 
523  if ("\n" === $nextChar) {
524  $line++;
525  $column = 0;
526  } else {
527  $column++;
528  }
529  } else {
530  $nextToken = false;
531  $handle = substr($in, $i);
532 
533  foreach ($_tokens as $token => $e) {
534  if ('#' !== $token[0]) {
535  continue;
536  }
537 
538  $ntoken = str_replace('#', '\#', substr($token, 1));
539 
540  if (0 != preg_match('#^(' . $ntoken . ')#u', $handle, $match)) {
541  $strlen = strlen($match[1]);
542 
543  if ($strlen > 0) {
544  if (false !== $offset = strrpos($match[1], "\n")) {
545  $column = $strlen - $offset - 1;
546  } else {
547  $column += $strlen;
548  }
549 
550  $nextChar = $match[1];
551  $nextToken = $e;
552  $i += $strlen - 1;
553  $line += substr_count($match[1], "\n");
554 
555  break;
556  }
557  }
558  }
559  }
560 
561  /*
562  echo '>>> Automata ' . $c . "\n" .
563  '>>> Next state ' . $nextState . "\n" .
564  '>>> Token ' . $token . "\n" .
565  '>>> Next char ' . $nextChar . "\n";
566  */
567 
568  // Got it!
569  if (false !== $nextToken) {
570  if (is_array($this->_actions[$c][$nextState][$nextToken])) {
571  $nextAction = $this->_actions[$c][$nextState][$nextToken][1];
572  } else {
573  $nextAction = $this->_actions[$c][$nextState][$nextToken];
574  }
575  $nextState = $_states[$this->_transitions[$c][$nextState][$nextToken]];
576  }
577 
578  // Oh :-(.
579  if (false === $nextToken || $nextState === $_states['__']) {
580  $pop = array_pop($this->_stack);
581  $d--;
582 
583  // Go back to a parent automata.
584  if ((in_array($this->_states[$c][$nextState], $this->_terminal[$c]) &&
585  null !== $pop) ||
586  ($nextState === $_states['__'] &&
587  null !== $pop)) {
588 
589  //echo '!!! Change automata (down)' . "\n";
590 
591  list($c, $nextState, $nextToken) = $pop;
592 
593  $_actions[$c] = 2;
594 
595  $i -= strlen($nextChar);
596  $_tokens = array_flip($this->_tokens[$c]);
597  $_states = array_flip($this->_states[$c]);
598 
599  /*
600  echo '!!! Automata ' . $c . "\n" .
601  '!!! Next state ' . $nextState . "\n";
602  */
603 
604  continue;
605  }
606 
607  $error = explode("\n", $in);
608  $error = $error[$this->line];
609 
610  throw new Exception\IllegalToken(
611  'Illegal token at line ' . ($this->line + 1) . ' and column ' .
612  ($this->column + 1) . "\n" . $error . "\n" .
613  str_repeat(' ', $this->column) . '↑',
614  1,
615  [],
616  $this->line + 1, $this->column + 1
617  );
618  }
619 
620  $this->line = $line;
621  $this->column = $column;
622 
623  //echo '<<< Next state ' . $nextState . "\n";
624 
625  $this->buffers[-1] = $nextChar;
626 
627  // Special actions.
628  if ($nextAction < 0) {
629  $buffer = abs($nextAction);
630 
631  if (($buffer & 1) == 0) {
632  $this->buffers[($buffer - 2) / 2] = null;
633  } else {
634  $buffer = ($buffer - 1) / 2;
635 
636  if (!(isset($this->buffers[$buffer]))) {
637  $this->buffers[$buffer] = null;
638  }
639 
640  $this->buffers[$buffer] .= $nextChar;
641  }
642 
643  continue;
644  }
645 
646  if (0 !== $nextAction) {
647  $this->consume($nextAction);
648  }
649  }
650 
651  return;
652  }
653 
661  abstract protected function consume($action);
662 
669  protected function pre(&$in)
670  {
671  return;
672  }
673 
679  protected function end()
680  {
681  return true;
682  }
683 
689  abstract public function getResult();
690 
697  public function setInitialLine($line)
698  {
699  $old = $this->_initialLine;
700  $this->_initialLine = $line;
701 
702  return $old;
703  }
704 
711  public function setSkip(Array $skip)
712  {
713  $old = $this->_skip;
714  $this->_skip = $skip;
715 
716  return $old;
717  }
718 
719 
726  public function setTokens(Array $tokens)
727  {
728  $old = $this->_tokens;
729  $this->_tokens = $tokens;
730 
731  return $old;
732  }
733 
740  public function setStates(Array $states)
741  {
742  $old = $this->_states;
743  $this->_states = $states;
744 
745  return $old;
746  }
747 
754  public function setTerminal(Array $terminal)
755  {
756  $old = $this->_terminal;
757  $this->_terminal = $terminal;
758 
759  return $old;
760  }
761 
768  public function setTransitions(Array $transitions)
769  {
770  $old = $this->_transitions;
771  $this->_transitions = $transitions;
772 
773  return $old;
774  }
775 
782  public function setActions(Array $actions)
783  {
784  foreach ($actions as $e => $automata) {
785  foreach ($automata as $i => $state) {
786  foreach ($state as $j => $token) {
787  if (0 != preg_match('#^(\d+),(.*)$#', $token, $matches)) {
788  $actions[$e][$i][$j] = [(int) $matches[1], $matches[2]];
789  }
790  }
791  }
792  }
793 
794  $old = $this->_actions;
795  $this->_actions = $actions;
796 
797  return $old;
798  }
799 
806  public function setNames(Array $names)
807  {
808  $old = $this->_names;
809  $this->_names = $names;
810 
811  return $old;
812  }
813 
819  public function getInitialLine()
820  {
821  return $this->_initialLine;
822  }
823 
829  public function getSkip()
830  {
831  return $this->_skip;
832  }
833 
839  public function getTokens()
840  {
841  return $this->_tokens;
842  }
843 
849  public function getStates()
850  {
851  return $this->_states;
852  }
853 
859  public function getTerminal()
860  {
861  return $this->_terminal;
862  }
863 
869  public function getTransitions()
870  {
871  return $this->_transitions;
872  }
873 
879  public function getActions()
880  {
881  return $this->_actions;
882  }
883 
889  public function getNames()
890  {
891  return $this->_names;
892  }
893 
899  public static function enableCache()
900  {
901  $old = self::$_cacheEnabled;
902  self::$_cacheEnabled = true;
903 
904  return $old;
905  }
906 
912  public static function disableCache()
913  {
914  $old = self::$_cacheEnabled;
915  self::$_cacheEnabled = false;
916 
917  return $old;
918  }
919 
925  public function __toString()
926  {
927  $out =
928  'digraph ' . str_replace('\\', '', get_class($this)) . ' {' .
929  "\n" .
930  ' rankdir=LR;' . "\n" .
931  ' label="Automata of ' .
932  str_replace('\\', '\\\\', get_class($this)) . '";';
933 
934  $transitions = array_reverse($this->_transitions, true);
935 
936  foreach ($transitions as $e => $automata) {
937  $out .=
938  "\n\n" . ' subgraph cluster_' . $e . ' {' . "\n" .
939  ' label="Automata #' . $e .
940  (isset($this->_names[$e])
941  ? ' (' . str_replace('"', '\\"', $this->_names[$e]) . ')'
942  : '') .
943  '";' . "\n";
944 
945  if (!empty($this->_terminal[$e])) {
946  $out .=
947  ' node[shape=doublecircle] "' . $e . '_' .
948  implode('" "' . $e . '_', $this->_terminal[$e]) . '";' . "\n";
949  }
950 
951  $out .= ' node[shape=circle];' . "\n";
952 
953  foreach ($this->_states[$e] as $i => $state) {
954  $name = [];
955  $label = $state;
956 
957  if (__ != $state) {
958  foreach ($this->_transitions[$e][$i] as $j => $foo) {
959  $ep = $this->_actions[$e][$i][$j];
960 
961  if (is_array($ep)) {
962  $ep = $ep[0];
963  }
964 
965  if (is_int($ep)) {
966  $ep--;
967 
968  if (0 < $ep && !isset($name[$ep])) {
969  $name[$ep] = $ep;
970  }
971  }
972  }
973 
974  if (!empty($name)) {
975  $label .= ' (' . implode(', ', $name) . ')';
976  }
977 
978  $out .=
979  ' "' . $e . '_' . $state . '" ' .
980  '[label="' . $label . '"];' . "\n";
981  }
982  }
983 
984  foreach ($automata as $i => $transition) {
985  $transition = array_reverse($transition, true);
986 
987  foreach ($transition as $j => $state) {
988  if (__ != $this->_states[$e][$i]
989  && __ != $state) {
990  $label = str_replace('\\', '\\\\', $this->_tokens[$e][$j]);
991  $label = str_replace('"', '\\"', $label);
992 
993  if ('#' === $label[0]) {
994  $label = substr($label, 1);
995  }
996 
997  $out .=
998  ' "' . $e . '_' . $this->_states[$e][$i] .
999  '" -> "' . $e . '_' . $state . '"' .
1000  ' [label="' . $label . '"];' . "\n";
1001  }
1002  }
1003  }
1004 
1005  $out .=
1006  ' node[shape=point,label=""] "' . $e . '_";' . "\n" .
1007  ' "' . $e . '_" -> "' . $e . '_GO";' . "\n" .
1008  ' }';
1009  }
1010 
1011  $out .= "\n" . '}' . "\n";
1012 
1013  return $out;
1014  }
1015 }
__construct(Array $skip, Array $tokens, Array $states, Array $terminal, Array $transitions, Array $actions, Array $names=[])
Definition: Ll1.php:335
getTransitions()
Definition: Ll1.php:869
static disableCache()
Definition: Ll1.php:912
static enableCache()
Definition: Ll1.php:899
setTerminal(Array $terminal)
Definition: Ll1.php:754
setTransitions(Array $transitions)
Definition: Ll1.php:768
setActions(Array $actions)
Definition: Ll1.php:782
setStates(Array $states)
Definition: Ll1.php:740
setTokens(Array $tokens)
Definition: Ll1.php:726
static $_cacheEnabled
Definition: Ll1.php:319
static _define($name, $value, $case=false)
Definition: Core.php:338
setSkip(Array $skip)
Definition: Ll1.php:711
compile($in)
Definition: Ll1.php:363
consume($action)
setNames(Array $names)
Definition: Ll1.php:806
getInitialLine()
Definition: Ll1.php:819
setInitialLine($line)
Definition: Ll1.php:697
pre(&$in)
Definition: Ll1.php:669
static $_cache
Definition: Ll1.php:312