include 'ttrie.php';

class Rule extends TTrie {
  public $rule = array();
  public $savematch = 0;

  function __construct($s='') {
    $this->set( array(
        ' ' => 'Separated',
        "\r\n" => 'set_rule',
        "\n" => 'set_rule',
        "\t" => 'Separated',
        '->' => 'Separated',
        '→' => 'Separated',
        '|' => 'set_parallel_rule',
        ));
    $this->match($s);
    if($this->rule[0][0] == $this->rule[0][1]) {
        if(count($this->rule[0]) == 2) $this->rule[0][0] .= "'";
        else array_unshift($this->rule, array($this->rule[0][0]."'", $this->rule[0][0]));
    }else {
        $c = $this->rule[0][0];
        $n = 0;
        foreach($this->rule as $r) if($r[0] == $c) $n++;
        if($n > 1) array_unshift($this->rule, array($this->rule[0][0]."'", $this->rule[0][0]));
    }
  }
  function Separated() {
  }
  function set_rule() {
    $this->rule[] = $this->buffer;
    $this->buffer = array();
  }
  function set_parallel_rule() {
    $t = $this->buffer[0];
    $this->set_rule();
    $this->buffer[] = $t;
  }
}


class Grammar {
  var $closure = array();
  var $first = array();
  var $follow = array();
  var $rule = array();
  var $identifier = array();
  var $leay = array();
  var $forecast = array();
  var $stack = array();
  var $ll = 'LL(0)';
  var $lr = 'LR(0)';

  function __construct($s='') {
    $p = new Rule($s);
    $this->rule = $p->rule;
    $this->set_grammar();
  }

  function set_grammar() {
    foreach($this->rule as $rule) {
        if(! in_array($rule[0], $this->identifier)) $this->identifier[] = $rule[0];
    }
    foreach($this->rule as $rule) {
        foreach($rule as $v)
            if(! in_array($v, $this->identifier) && ! in_array($v, $this->leay))
                $this->leay[] = $v;
    }
    $this->set_first();
    $this->set_follow();
    $this->set_closure();
    $this->set_select();
    $this->set_forecast();
  }
  function set_first() {
    foreach($this->rule as $rule) $this->first[$rule[0]] = array();
    //直接收取 形如U->a…的产生式（其中a是终结符），把a收入到First(U)中
    foreach($this->rule as $v) {
        if(in_array($v[1], $this->leay)) $this->first[$v[0]][] = $v[1];
    }
    //反复传递 形入U->P1P2P3…Pn的产生式（其中P是非终结符），应先把First(P1)中的全部内容传送到First(U)中,如果P1中有ε，把First(P2)中的内容传送到First(U)中,类推直到Pi中无ε
    do {
        $t = serialize($this->first);
        foreach($this->rule as $rule) {
            for($i=1; $i<count($rule); $i++) {
                $v = $rule[$i];
                if(in_array($v, $this->identifier)) {
                    $this->first[$rule[0]] = array_unique(array_merge($this->first[$rule[0]], $this->first[$v]));
                    if(! in_array('#', $this->first[$v])) break;
                }else break;
            }
        }
    }while($t != serialize($this->first));
  }
  function set_follow() {
    foreach($this->rule as $rule) $this->follow[$rule[0]] = array();
    //直接收取 形如 …Ua… 的，把a直接收入到Follow(U)中
    foreach($this->rule as $rule) {
        for($i=1; $i<count($rule)-1; $i++) {
            if(in_array($rule[$i], $this->identifier) && in_array($rule[$i+1], $this->leay))
                $this->follow[$rule[$i]][] = $rule[$i+1];
        }
        if(in_array($rule[$i], $this->identifier)) $this->follow[$rule[$i]][] = '#';
    }
    foreach($this->follow as &$v) if(! $v) $v[] = '#';
    //直接收取 形如 …UP…(P是非终结符)的，把First(P)中非ε收入到Follow(U)中
    foreach($this->rule as $rule) {
        for($i=1; $i<count($rule)-1; $i++) {
            if(in_ar