对编译原理有兴趣的入

对编译原理有兴趣的进
最近尝试做了文法分析的东东，问题较多。
请提建议。代码放不下，分两页。下载地址 http://download.csdn.net/detail/xuzuning/4529066

PHP code

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; $iidentifier)) {                    $this->first[$rule[0]] = array_unique(array_merge($this->first[$rule[0]], $this->first[$v]));                    if(! in_array('//m.sbmmt.com/m/faq/#', $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; $iidentifier) && 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]][] = '//m.sbmmt.com/m/faq/#';    }    foreach($this->follow as &$v) if(! $v) $v[] = '//m.sbmmt.com/m/faq/#';    //直接收取 形如 …UP…(P是非终结符)的，把First(P)中非ε收入到Follow(U)中    foreach($this->rule as $rule) {        for($i=1; $iidentifier) && in_array($rule[$i+1], $this->identifier)) {                $this->follow[$rule[$i]] = array_unique(array_merge($this->follow[$rule[$i]], array_diff($this->first[$rule[$i+1]], array('//m.sbmmt.com/m/faq/#'))));            }        }    }    //反复传递 形如U－>aP的(P是非终结符)或U->aPQ(P,Q为非终结符且Q中含ε)，应把Follow(U)中的全部内容传送到Follow(P)中    do {        $t = serialize($this->follow);        foreach($this->rule as $rule) {            $s = $rule[0];            $d = end($rule);            if(in_array($d, $this->leay)) continue;            $p = prev($rule);            if(in_array($p, $this->leay)) $this->follow[$d] = array_unique(array_merge($this->follow[$d], $this->follow[$s]));            elseif(in_array('//m.sbmmt.com/m/faq/#', $this->follow[$d])) $this->follow[$p] = array_unique(array_merge($this->follow[$p], $this->follow[$s]));        }    }while($t != serialize($this->follow));  }  function set_closure() {    $shift = array();    $this->closure[0][] = array('offs' => 1, 'rule' => 0);    for($i=0 ; $i closure); $i++) {        $cnt = count($this->closure);        //构造闭包 closure        $ex = array();        $j = 0;        $tmp = array();        do {            $size = count($this->closure[$i]);            for($j=0; $jclosure[$i]); $j++) {                $dfa = $this->closure[$i][$j];                $rule = $this->rule[$dfa['rule']];                if(isset($rule[$dfa['offs']])) {                    $ch = $ex[] = $rule[$dfa['offs']];                }                foreach($this->rule as $r=>$rule) {                    if(in_array($rule[0], $ex)) {                        $t = array('offs' => 1, 'rule' => $r);                        if(!isset($tmp[$r][1])) $this->closure[$i][] = $t;                        $tmp[$r][1] = 1;                    }                }            }        }while(count($this->closure[$i]) != $size); //直到不再增大        //判断状态转向 go        $out = array();        foreach($this->closure[$i] as $k=>$dfa) {            $rule = $this->rule[$dfa['rule']];            if(isset($rule[$dfa['offs']])) {                $t = "$dfa[rule],$dfa[offs]";                $ch = $rule[$dfa['offs']];                $this->closure[$i][$k]['char'] = $ch;                if(isset($out[$ch])) $shift[$t] = $out[$ch];                if(isset($shift[$t])) {                    $this->closure[$i][$k]['target'] = $shift[$t];                    $dfa['offs']++;                    if(!$this->in_closure($dfa, $this->closure[$shift[$t]])) $this->closure[$shift[$t]][] = $dfa;                } else {                    $cnt = count($this->closure);                    $this->closure[$i][$k]['target'] = $cnt;                    $shift[$t] = $cnt;                    $dfa['offs']++;                    $this->closure[count($this->closure)][] = $dfa;                    $out[$ch] = $cnt;                }            }        }        //构造状态转换表        foreach($this->closure[$i] as $k=>$dfa) {            if(isset($dfa['target'])) {                $v = $dfa['char'];                if(in_array($v, $this->identifier)) $this->goto[$i][$v] = $dfa['target'];                else {                    $this->action[$i][$v][] = "S$dfa[target]";                    $this->request[$i][$v] = $dfa['rule'];                }            } else {                $ch = $this->rule[$dfa['rule']][0];                foreach($this->follow[$ch] as $v) {                    $this->action[$i][$v][] = "r$dfa[rule]";                    $this->request[$i][$v] = $dfa['rule'];                }            }        }        foreach($this->action[$i] as $c=>$v) {            $v = array_unique($v);            if(count($v) > 1) $this->lr = 'SLR(1)';            $this->action[$i][$c] = $v;        }    }  }  function in_closure($t, $s) {    foreach($s as $r) if($t['offs'] == $r['offs'] && $t['rule'] == $r['rule']) return true;    return false;    return in_array(serialize($t), array_map('serialize', $s));  }  function set_select() {    foreach($this->rule as $i=>$rule) {        $y = array($rule[1]);        if(in_array($y[0], $this->leay)) {            if($y[0] != '//m.sbmmt.com/m/faq/#') {                $this->select[$i] = $y;                continue;            }        }else $y = $this->first[$rule[1]];        $x = $this->follow[$rule[0]];        //SELECT(X->Y)=(FIRST(Y)-{ε})并FOLLOW(X)        $this->select[$i] = array_unique( array_merge(array_diff($y, array('//m.sbmmt.com/m/faq/#')), $x) );    }  }  /**   * 构造预测分析表   **/  function set_forecast() {    foreach($this->select as $i=>$r) {        $c = $this->rule[$i][0];        $v = array_reverse(array_slice($this->rule[$i], 1));        foreach($r as $k) {            $this->forecast[$c][$k][] = $v;        }    }    //检查冲突    foreach($this->forecast as $c=>$r) {        foreach($r as $k) {            if(count($k) > 1) {                $this->ll = 'LL(1)';            }        }    }  }