<?php

function str_replace_once($needle, $haystack, $replace) {
	$pos = strpos ( $haystack, $needle );
	if ($pos !== false) {
		$haystack = substr_replace ( $haystack, $replace, $pos, strlen ( $needle ) );
	}
	return $haystack;
}

class SentencialForm {

	public function __construct($rules, $beginNeterm, $prevRule, $seekSentence, $step = 0, $parent = null) {
		$this->form = $beginNeterm;
		$this->prevRule = $prevRule;
		$this->rules = $rules;
		$this->seekSentence = $seekSentence;
		$this->seekSentenceLength = strlen ( $seekSentence ) + 3;
		$this->step = $step;
		$this->parent = $parent;
	}

	public function isApplicable() {
		if (strlen ( $this->form ) > $this->seekSentenceLength) {
			return false;
		}
		$lSideContained = strpos ( $this->form, $this->prevRule->lSide ) !== false;
		// $allowed = in_array ( $rule, $this->prevRule->allow );
		// $denied = in_array ( $rule, $this->prevRule->deny );
		$allowed = true;
		$denied = true;
		if ($lSideContained && $allowed) {
			$data = array ();
			foreach ( $this->prevRule->allow as $nextRule ) {
				$data [] = new SentencialForm ( $this->rules, str_replace_once ( $this->prevRule->lSide, $this->form, $this->prevRule->rSide ), $nextRule, $this->seekSentence, $this->step + 1, $this );
			}
			return $data;
		} else if (! $lSideContained && $denied) {
			$data = array ();
			foreach ( $this->prevRule->deny as $nextRule ) {
				$data [] = new SentencialForm ( $this->rules, $this->form, $nextRule, $this->seekSentence, $this->step + 1, $this );
			}
			return $data;
		} else {
			return false;
		}
	}

	public function isDone() {
		return $this->form == $this->seekSentence;
	}

	public function getTrace() {
		$trace = array ();
		$parent = $this;
		while ( $parent != null ) {
			$trace [] = $parent;
			$parent = $parent->parent;
		}
		return array_reverse ( $trace );
	}

	public function toString() {
		return "[" . $this->step . "](" . $this->form . "," . $this->prevRule->index . ")";
	}

	public function printTrace() {
		$trace = $this->getTrace ();
		foreach ( $trace as $sentence ) {
			echo $sentence->toString () . "\r\n";
		}
	}

}

class Rule {

	public function __construct($index, $lSide, $rSide, $allow, $deny) {
		$this->index = $index;
		$this->lSide = $lSide;
		$this->rSide = $rSide;
		$this->allow = $allow;
		$this->deny = $deny;
	}

}

class Rules {

	public function __construct($ruleStr) {
		$rs = explode ( "\n", trim ( $ruleStr ) );
		$this->rules = array_map ( function ($x) {
			$toInt = function ($x) {
				return $x * 1;
			};
			$x = explode ( ":", trim ( $x ), 2 );
			$num = $toInt ( $x [0] );
			$x = explode ( "->", $x [1], 2 );
			$lSide = $x [0];
			$x = explode ( "(", $x [1], 2 );
			$rSide = $x [0];
			$x = explode ( ")", $x [1], 2 );
			$allow = $x [0] == "" ? array () : array_map ( $toInt, explode ( ",", $x [0] ) );
			$x = explode ( ",(", $x [1], 2 );
			$x = explode ( ")", $x [1], 2 );
			$deny = $x [0] == "" ? array () : array_map ( $toInt, explode ( ",", $x [0] ) );
			return new Rule ( $num, $lSide, $rSide, $allow, $deny );
		}, $rs );
		$getR = function ($rules, $index) {
			foreach ( $rules as $rule ) {
				if ($rule->index == $index) {
					return $rule;
				}
			}
			return false;
		};

		foreach ( $this->rules as $rule ) {
			$dataAllow = array ();
			foreach ( $rule->allow as $allowI ) {
				$x = $getR ( $this->rules, $allowI );
				if ($x === false) {
					die ( "Invalid allow rule: " . $allowI );
				}
				$dataAllow [] = $x;
			}
			$dataDeny = array ();
			foreach ( $rule->deny as $deniedI ) {
				$x = $getR ( $this->rules, $deniedI );
				if ($x === false) {
					die ( "Invalid deny rule: " . $deniedI );
				}
				$dataDeny [] = $x;
			}
			$rule->allow = $dataAllow;
			$rule->deny = $dataDeny;
		}
	}

}

function parse($sentenceI, $printFailed, $printGood, $printResultInfo) {
	$ruleStr = "1:S->SC(1,2),()
2:S->AA(3),()
3:A->B(4),(5)
4:C->D(3),(7)
5:C->C(6),()
6:B->A(6),(3)
7:B->A(7),(8)
8:D->A(9),(10)
9:D->C(9),(3)
10:A->a(10),()";

	$rules = new Rules ( $ruleStr );
	$sentence = new SentencialForm ( $rules->rules, "S", $rules->rules [0], $sentenceI );

	$stack = array (
			$sentence
	);
	while ( count ( $stack ) > 0 ) {
		$sentence = array_shift ( $stack );
		if ($sentence->isDone ()) {
			if ($printGood) {
				echo "\r\n";
				echo "Finished:\r\n";
				$sentence->printTrace ();
			}
			if ($printResultInfo) {
				echo "Accepted sentence " . $sentenceI . "\r\n";
			}
			return true;
		}
		$expanded = false;
		$nextSentences = $sentence->isApplicable ();
		if ($nextSentences !== false) {
			foreach ( $nextSentences as $nextSentence ) {
				$stack [] = $nextSentence;
				$expanded = true;
			}
		}
		if (! $expanded) {
			if ($printFailed) {
				echo "\r\n";
				echo "Failed:\r\n";
				$sentence->printTrace ();
				echo "\r\n";
			}
		}
	}
	if ($printResultInfo) {
		echo "Rejected sentence " . $sentenceI . "\r\n";
	}
	return false;
}

$s = "a";
for($i = 0; $i < 100; $i ++) {
	if (parse ( $s, false, false, false )) {
		echo "Accepted: " . strlen ( $s ) . "\r\n";
	}
	$s .= "a";
}
//parse ( "aaa", false, false, true );