Pasted

<?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 );