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->firs