相关数据文件 1.txt<?php $G =<<< TXT S -> a H H -> a M d H -> d M -> A b M -> # A -> a M A ->eTXT;$S = 'aaaebbd#'; 2.txt<?php $G =<<< TXT E -> E E -> E + T E -> T T -> T * F T -> F F -> ( E ) F -> iTXT;$S = 'i*(i+i)#';3.txt<?php $G =<<< TXT E → ( L ) E → a L → L , E L → ETXT;$S = '((a),a,(a,a))'; 4.txt<?php $G =<<< TXT S' → S S → A B S → b C A → # A → b B → # B → a D C → A D C → b D → a S D → cTXT;$zS = 'baac';5.txt<?php $G =<<< TXT S → i S e S | i S | aTXT;$S = 'iiaea#'; 6.txt<?php $G =<<< TXT S → a A S → d A → b A S A → #TXT;$S = 'abbb'; 7.txt<?php $G =<<< TXT S' → S S → a S S → b S S → aTXT;$S = 'aabba'; 8.txt<?php $G =<<< TXT S → A a | b A → A c | S d | #TXT;$G1 =<<< TXT S → A a | b A → b d A A → c A | a d A | # TXT;$S = 'bdadcca';
$t = array();
foreach($this->rule as $rule) if($rule[0] == $rule[1]) $t[] = $rule;
if($t) {
foreach($t as $rule) printf('<tr><td colspan=4>%s 存在左递归</td></tr>', preg_replace('/ /', ' → ', join(' ', $rule), 1));
return;
}
$stack = array('#', key($this->forecast));
$i = 0;
$step = 1;
$timeout = 10 * strlen($s);
while($stack && $i < strlen($s) && $timeout--) {
$r = end($stack);
if($r == $s{$i}) {
$msg = $r == '#' ? '成功' : "$r 匹配";
}elseif(isset($this->forecast[$r][$s{$i}])) $msg = $r . ' → ' . join(' ', array_reverse($this->forecast[$r][$s{$i}][0]));
else $msg = '错误';
printf("<tr><td>%d</td><td>%s</td><td>%s</td><td>%s</td></tr>", $step++, substr(join('', $stack), -50), substr($s, $i), $msg);
if($r == $s{$i}) {
array_pop($stack);
$i++;
}elseif(isset($this->forecast[$r][$s{$i}])) {
array_pop($stack);
if(current($this->forecast[$r][$s{$i}][0]) != '#')
$stack = array_merge($stack, $this->forecast[$r][$s{$i}][0]);
}else break;
}
}
function lr_start($s) {
$State = array(0); //状态栈
$Symbol = array('#'); //符号栈
$i = 0;
$step = 1;
$timeout = 10 * strlen($s);
while($i < strlen($s) && $timeout--) {
$ch = $s{$i};
$sp = end($State); $msg = substr($s, $i);
if(isset($this->action[$sp][$ch]) && $this->action[$sp][$ch][0] == 'r0') $msg = 'acc';
if(isset($this->request[$sp][$ch])) $request = preg_replace('/ /', ' → ', join(' ', $this->rule[$this->request[$sp][$ch]]), 1);
else $request = 'error';
printf("<tr><th>%d</td><td>%s</td><td>%s</td><td>%s</td><td>%s</td></tr>", $step++, substr(join('', $State), -50), join('', $Symbol), $msg, $request); if(isset($this->action[$sp][$ch]) || isset($this->goto[$sp][$ch])) {
$t = isset($this->action[$sp][$ch]) ? $this->action[$sp][$ch][0] : $this->goto[$sp][$ch];
$n = substr($t, 1) + 0;
if($t{0} == 'r') {
for($j=0; $j<count($this->rule[$n])-1; $j++) {
array_pop($State);
array_pop($Symbol);
}
if($n == 0) break;
$c = $Symbol[] = $this->rule[$n][0];
$State[] = $this->goto[end($State)][$c];
}elseif($t{0} == 'S') {
$State[] = $n;
$Symbol[] = $ch;
$i++;
}else ;
}else break;
}
}
function report($in='') {
if($in) $in = trim($in, '#') . '#';
echo '<style>table {font-size:10pt</style>'; echo '<table ><tr><td><b>文法</b></td></tr>';
foreach($this->rule as $rule) {
echo '<tr><td>';
echo preg_replace('/ /', ' → ', join(' ', $rule), 1);
echo '</td></tr>';
}
echo '</table>'; $identifier = $this->identifier;
echo '<table><tr><td><b>标识符</b></td>';
echo '<td>' . join(' ', $identifier) . '</td></tr>';
echo '</table>'; $leay = array_diff($this->leay, array('#'));
$leay[] = '#';
echo '<table><tr><td><b>终结符</b></td>';
echo '<td>' . join(' ', $leay) . '</td></tr>';
echo '</table>'; echo '<table width=60% border=1><tr><th>标识符</th><th>推出空</th><th>FIRST集</th><th>FOLLOW集</th></tr>';
foreach($identifier as $ch) {
echo '<tr><td>' . $ch . '</td>';
echo '<td>' . (in_array('#', $this->first[$ch]) ? 'True' : 'false') . '</td>';
echo '<td>' . join(' ', $this->first[$ch]) . '</td>';
echo '<td>' . join(' ', $this->follow[$ch]) . '</td>';
echo '</tr>';
}
echo '</table>'; echo '<table width=100%><tr><td> </td></tr><tr><th>' . $this->ll . '文法分析</th></tr></table>'; echo '<table width=60% border=1><tr><th>产生式</th><th>Select集</th></tr>';
foreach($this->rule as $i=>$rule) {
echo '<tr>';
echo '<td>' . preg_replace('/ /', ' → ', join(' ', $rule), 1) . '</td>';
echo '<td>' . join(' ', $this->select[$i]) . '</td>';
echo '</tr>';
}
echo '</table>'; $forecast = $this->forecast;
echo '<table width=60%><tr><td><b>预测分析表</b></td></tr>';
echo '<tr><td><table width=100% border=1>';
echo '<tr><th> </th><th>' . join('</th><th>', $leay) . '</th></tr>';
foreach($identifier as $ch) {
echo '<tr><td>' . $ch . '</td>';
foreach($leay as $v) {
$s = '';
if(isset($forecast[$ch][$v])) {
foreach($forecast[$ch][$v] as $t) {
if($s) $s .= '<br />';
$s .= $ch . ' → '. join(' ', array_reverse($t));
}
if(count($forecast[$ch][$v]) > 1) $s = "<font color=red>$s</font>";
}else $s .= ' ';
echo '<td>' . $s . '</td>';
}
echo '<tr>';
}
echo '</table></td></tr>';
echo '</table>'; if($in) {
echo '<table><tr><th>测试字符串</th>';
echo '<td>' . trim($in, '#') . '</td></tr></table>';
echo '<table width=100% border=1>';
echo '<tr><th>步骤</th><th>分析栈</th><th>剩余字符</th><th>生成式或匹配</th></tr>';
$this->ll_start($in);
echo '</table>';
} echo '<table width=100%><tr><td> </td></tr>';
echo '<tr><th>' . $this->lr . '文法分析<th></tr></table>';
echo '<table><tr><th>状态转移表</th></tr></table>';
echo '<table width=100% border=1>';
echo '<tr><th rowspan=2>状态</th><th colspan=' . count($leay) . '>Action</th><th colspan=' . count($identifier) . '>Goto</th><th rowspan=2>DFA</th></tr>';
echo '<tr><th>' . join('</th><th>', $leay) . '</th><th>'. join('</th><th>', $identifier) . '</th></tr>';
foreach($this->action as $i=>$item) {
echo "<tr><td>$i</td>";
foreach($leay as $v) {
$s = isset($item[$v]) ? join(',', $item[$v]) : ' ';
if(strpos($s, ',')) $s = "<font color=red>$s</font>";
echo "<td>$s</td>";
}
foreach($identifier as $v) {
$s = isset($this->goto[$i][$v]) ? $this->goto[$i][$v] : ' ';
echo "<td>$s</td>";
}
echo '<td>' . $this->showDFA($i) .'</td>';
echo '</tr>';
}
echo '</table>'; if($in) {
echo '<table><tr><th>测试字符串</th>';
echo '<td>' . trim($in, '#') . '</td></tr></table>';
echo '<table width=100% border=1>';
echo '<tr><th>步骤</th><th>状态栈</th><th>符号栈</th><th>剩余字符</th><th>生成式</th></tr>';
$this->lr_start($in);
echo '</table>';
}
}
function showDFA($i) {
$res = array();
foreach($this->closure[$i] as $dfa) {
$rule = $this->rule[$dfa['rule']];
array_splice($rule, $dfa['offs'], 0, '·');
array_splice($rule, 1, 0, '→');
if(isset($dfa['target'])) $rule[] = " [$dfa[target]]";
$res[] = join('', $rule);
}
return join('; ', $res);
}
}
for($i=1; $i<=count(glob('*.txt')); $i++) echo " <a href=?id=$i>$i</a>";
$n = current($_GET) or $n = 1;
$S = '';
include "$n.txt";$p = new grammar($G);
$p->report($S);ttrie.php<?php
class TTrie {
protected $buffer = array();
protected $dict = array( array() );
protected $input = 0; //字符串当前偏移
protected $backtracking = 0; //字符串回溯位置
public $debug = 0;
public $savematch = 1; function set($word, $action='') {
if(is_array($word)) {
foreach($word as $k=>$v) $this->set($k, $v);
return;
}
$p = count($this->dict);
$cur = 0; //当前节点号
foreach(str_split($word) as $c) {
if (isset($this->dict[$cur][$c])) { //已存在就下移
$cur = $this->dict[$cur][$c];
continue;
}
$this->dict[$p]= array(); //创建新节点
$this->dict[$cur][$c] = $p; //在父节点记录子节点号
$cur = $p; //把当前节点设为新插入的
$p++;
}
$this->dict[$cur]['acc'] = $action; //一个词结束，标记叶子节点
} function match($s) {
$ret = array();
$cur = 0; //当前节点，初始为根节点
$i =& $this->input; //字符串当前偏移
$p =& $this->backtracking; //字符串回溯位置
$s .= "\0"; //附加结束符
$len = strlen($s);
$buf = '';
while($i < $len) {
$c = $s{$i};
if(isset($this->dict[$cur][$c])) { //如果存在
$cur = $this->dict[$cur][$c]; //转到对应的位置
if(isset($this->dict[$cur][$s[$i+1]])) {//检查下一个字符是否也能匹配，长度优先
$i++;
continue;
}
if(isset($this->dict[$cur]['acc'])) { //是叶子节点，单词匹配！
if($buf) {
$this->buffer[] = $buf;
$buf = '';
}
if($this->savematch) $this->buffer[] = substr($s, $p, $i - $p + 1); //取出匹配位置和匹配的词 $ar = explode(',', $this->dict[$cur]['acc']);
call_user_func_array( array($this, array_shift($ar)), $ar ); $p = $i + 1; //设置下一个回溯位置
$cur = 0; //重置当前节点为根节点
}
} else { //不匹配
$buf .= $s{$p}; //substr($s, $p, $i - $p + 1); //保存未匹配位置和未匹配的内容
$cur = 0; //重置当前节点为根节点
$i = $p; //把当前偏移设为回溯位置
$p = $i + 1; //设置下一个回溯位置
}
$i++; //下一个字符
}
if(trim($buf, "\0")) $this->buffer[] = trim($buf, "\0");
} function __call($method, $param) {
if($this->debug) printf("偏移:%d 回溯:%d\n", $this->input, $this->backtracking); }
}
1.txt<?php
$G =<<< TXT
S -> a H
H -> a M d
H -> d
M -> A b
M -> #
A -> a M
A ->eTXT;$S = 'aaaebbd#';
2.txt<?php
$G =<<< TXT
E -> E
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> iTXT;$S = 'i*(i+i)#';3.txt<?php
$G =<<< TXT
E → ( L )
E → a
L → L , E
L → ETXT;$S = '((a),a,(a,a))';
4.txt<?php
$G =<<< TXT
S' → S
S → A B
S → b C
A → #
A → b
B → #
B → a D
C → A D
C → b
D → a S
D → cTXT;$zS = 'baac';5.txt<?php
$G =<<< TXT
S → i S e S | i S | aTXT;$S = 'iiaea#';
6.txt<?php
$G =<<< TXT
S → a A
S → d
A → b A S
A → #TXT;$S = 'abbb';
7.txt<?php
$G =<<< TXT
S' → S
S → a S
S → b S
S → aTXT;$S = 'aabba';
8.txt<?php
$G =<<< TXT
S → A a | b
A → A c | S d | #TXT;$G1 =<<< TXT
S → A a | b
A → b d A
A → c A | a d A | # TXT;$S = 'bdadcca';
1中冲突选择非#
2,3,8 为什么不消除左递归？
5,7 要处理提取因子.LR晚上再看。