目录
目标
1、基础知识引入
1.1 文法
1.2 拓广文法
1.3 全部的项目集
2. 计算文法的LR(0)项目集的、识别活前缀的DFA
?2.1 分析得到各个项目集
2.2 构建SLR分析表中的移进部分
2.3 构建SLR分析表中的归约部分
3. LR分析构建分析器
3.1 过程分析
3.2 JavaScript代码实现
3.3 java代码实现(强哥翻译)
?
?
写在前面:本篇文章以编程实现的角度进行分析,分析的过程中难免会有错误,请多多指教。不过最终以实现目标为主。
目标
????????通过文法构造SLR分析表,然后构造SLR(1)分析器。然后通过编码将其实现(本篇主题)。
1、基础知识引入
可以参考本篇文章梳理基础知识,建议先阅读本篇文章。
编译原理-LR(0)文法算法实现https://www.jianshu.com/p/7e4b4f47de7b
1.1 文法
- (1)E - > E - T
- (2)E - > T
- (3)T - > T * F
- (4)T - > F
- (5)F - > - F
- (6)F - > id
1.2 拓广文法
??????? 在文法的基础上增加一个产生式 E ' - >? E
- (0)E' - > E
- (1)E - > E - T
- (2)E - > T
- (3)T - > T * F
- (4)T - > F
- (5)F - > - F
- (6)F - > id
1.3 全部的项目集
- (0)E' - > .E??????? ? E' - > E.
- (1)E - > .E - T???? E - > E. - T???? E - > E - .T???? E - > E - T.
- (2)E - > .T?? ? ? ?? E - > T.???????
- (3)T - > .T * F ? ? T - > T. * F??? T - > T *. F????? T - > T * F.
- (4)T - > .F????????? T - > F.
- (5)F - > .- F??????? F - > -. F???? ?? F - > - F.
- (6)F - > .id??????? ? F - > id.
2. 计算文法的LR(0)项目集的、识别活前缀的DFA
??????? 简而言之,就是各种状态转移形成的项目闭包。
?2.1 分析得到各个项目集
个人理解分析过程:
首先将所有的项目标记一个状态,假设 0 表示这个项目没有用过, 1 表示 这个项目使用过。
然后从初态集(I0)开始分析,初态集里出现的项目全部置为 1 ,代表已经使用了。
第一次,判断项目集(I0)所有经过 E 到达的下一状态是否为 0 ,若为 0 则创建项目集(I1),并将该项目状态置为1,将符合条件的转移项目都加进去。
??????? 加入之后判断 A - > α . β , . 后面的 β 是否为初态集中项目的左部,如果是,则将初态集中以 β 为左部的项目加入到新建的项目集(I1)中,然后再次进行A - > α . β 的判断,直到新项目集中没有项目加入为止。
第二次,判断项目集(I0)所有经过 T 到达的下一状态是否为 0 ,若为 0 则创建项目集(I2),并将该项目状态置为1,将符合条件的转移项目都加进去。
????????加入之后判断 A - > α . β , . 后面的 β 是否为初态集中项目的左部,如果是,则将初态集中以 β 为左部的项目加入到新建的项目集(I2)中,然后再次进行A - > α . β 的判断,直到新项目集中没有项目加入为止。
...........
第五次,判断项目集(I0)所有经过 -? 到达的下一状态是否为 0 ,若为 0 则创建项目集(I5),并将该项目状态置为1,将符合条件的转移项目都加进去。
????????加入之后判断 A - > α . β , . 后面的 β 是否为初态集中项目的左部,如果是,则将初态集中以 β 为左部的项目加入到新建的项目集(I5)中,然后再次进行A - > α . β 的判断,直到新项目集中没有项目加入为止。
??????? 即:F -> .-F 经过 - 到达的下一项目为 F - > - . F , 此项目状态为 0 ,因此创建新的项目集I5 , 将 F - > - . F 加入到新建项目集I5中,状态置为1。加入后判断 . 后的F是否为初态集I0项目中的左部,发现符合,则将F - > .-F 和 F - > .id 加入到项目集I5中,之后在判断 . 后的 - 和 id,发现都不是初态项目集中的左部,所以没有新的项目加入,结束循环判断。
第六次:判断项目集(I1)所有经过 -? 到达的下一状态是否为 0 ,若为 0 则创建项目集(I6),将符合条件的转移项目都加进去。
??????? 即:由于E' - > E. 已经是句柄了,. 后面为空,所以不做讨论。
????????E - > E . -T? 的下一项目 E - > E - . T的状态为0,所以创建新的项目集 I6,并将E - > E - . T加入到新项目集I6中,状态置为1。加入后,继续判断E - > E - . T ,. 后的T是否为初态集中项目的左部,发现是,所以将T - > .T * F 和 T - > .F 都加入到I6中,有新加入继续判断,T - > .T * F 中 . 后的 T 已经加入过了,所以不再加入。接着判断 T - > .F ,.? 后 为 F ,在初态集中项目左部包含F,并且 I6中未加入过 F 的项目,所以将F - > .-F 和 F - > .id 加入到项目集I6中,之后在判断 . 后的 - 和 id,发现都不是初态项目集中的左部,所以没有新的项目加入,结束循环判断。
.........
第九次,判断项目集(I6)所有经过 T? 到达的下一状态是否为 0 ,若为 0 则创建项目集(I9),将符合条件的转移项目都加进去。
????????E - > E? - .T? 的下一项目 E - > E - T .的状态为0,所以创建新的项目集 I9,并将E - > E -? T . 加入到新项目集I9中,状态置为1。(注意这里 I6 所经过 T 到达的 项目有两个 E->E- T. 和T-> T.*F ,第一个状态为 0 所以创建了新的项目集I9,虽然第二个 状态为1 ,但是也是I6通过T到达的,所以也需要加入到I9里面。)然后就是循环判断,下一字符是否在初态集左部出现,出现则加入,往复循环,直至没有为止。
.........
2.2 构建SLR分析表中的移进部分
? | id | - | * | # | E | T | F | 0 | s4 | s5 | ? | ? | 1 | 2 | 3 | 1 | ? | s6 | ? | acc | ? | ? | ? | 2 | ? | ? | s7 | ? | ? | ? | ? | 3 | ? | ? | ? | ? | ? | ? | ? | 4 | ? | ? | ? | ? | ? | ? | ? | 5 | s4 | s5 | ? | ? | ? | ? | 8 | 6 | s4 | s5 | ? | ? | ? | 9 | 3 | 7 | s4 | s5 | ? | ? | ? | ? | 10 | 8 | ? | ? | ? | ? | ? | ? | ? | 9 | ? | ? | s7 | ? | ? | ? | ? | 10 | ? | ? | ? | ? | ? | ? | ? |
?通过 2.1分析可以得到所有的项目集,接下分析转移部分。
1. 首先遍历 I0 - I10项目集(遍历符号记为 i),然后遍历每个项目集中的项目,获取项目中 . 的位置,然后判断 . 后的字符X,如果不为空(句柄)并且不和上次查找? . 后的字符相同,则在所有项目集中查找该项目首次出现的位置(顺序查找I0-I10),若找到该项目所在的项目集I(j),如果该字符X是非终结符,则直接将table[i][X] = j ;如果X是终结符,则将table[i][X] = Sj;
2.举例:
第一次遍历 I0,然后遍历I0中的项目,E' - > . E? 通过 E 到达E' -> E.,在所有项目集中查找该项目,发现 I1中包含E' -> E.,又因为E是非终结符,所以 table[0][E] = 1;
继续遍历 I0 中的项目,此时为 E - > .E - T , . 后的下一字符为 E,前一次已经转移过了,所以跳过。
继续遍历 I0 中的项目,此时为 E - > .T , . 后的下一字符为 T,和前一次转移字符不同,通过 T 到达E -> T. ,在所有项目集中查找该项目,发现 I2中包含E -> T.,又因为T是非终结符,所以 table[0][T] = 2;
.......
继续遍历 I0 中的项目,此时为 F - > .id , . 后的下一字符为 id,和前一次转移字符不同,通过 id 到达F - > id . ,在所有项目集中查找该项目,发现 I4中包含F - > id . ,又因为id 是终结符,所以 table[0][id] = S4;
第二次遍历 I1,然后遍历I1中的项目,因为 E -> E. 的下一个字符为空(句柄),所以跳过。
继续遍历I1中的项目,此时E - > E .- T 的下一个字符为 - ,在所有项目集中查找E - > E - . T ,
发现I6中包含E - > E - . T ,又因为 - 为终结符,所以table[1][-]=S6;
以此类推.......
2.3 构建SLR分析表中的归约部分
? | id | - | * | # | E | T | F | 0 | s4 | s5 | ? | ? | 1 | 2 | 3 | 1 | ? | s6 | ? | acc | ? | ? | ? | 2 | ? | r2 | s7 | r2 | ? | ? | ? | 3 | ? | r4 | r4 | r4 | ? | ? | ? | 4 | ? | r6 | r6 | r6 | ? | ? | ? | 5 | s4 | s5 | ? | ? | ? | ? | 8 | 6 | s4 | s5 | ? | ? | ? | 9 | 3 | 7 | s4 | s5 | ? | ? | ? | ? | 10 | 8 | ? | r5 | r5 | r5 | ? | ? | ? | 9 | ? | r1 | s7 | r1 | ? | ? | ? | 10 | ? | r3 | r3 | r3 | ? | ? | ? |
?
1.SLR(1)规约需要用到follow集合,根据文法:
?可求得:
follow(E)= {#,-}
follow(T)={*} U follow(E) = {#,-,*}
follow(F)= follow(T)= {#,-,*}(不算id)
把每个文法看做成一个句柄:
- (1)E - > E - T .
- (2)E - > T .
- (3)T - > T * F .
- (4)T - > F .
- (5)F - > - F .
- (6)F - > id .
依次遍历上述句柄,在所有的项目集中匹配, 匹配到 Ii 后,获取 . 前面的一个字符X,以此确定follow(X),接着用变量 j 遍历follow(X),在表中输入 table [i][j]? = r +这是第几个产生式句柄。
例如: 第一个产生式句柄(1)E - > E - T . 在 I9中匹配到了 ,
接着获取 . 前面的字符T,由此得知通过什么转移过来的,对应follow(T),接着遍历follow(T)中的元素? ,所以table[9][#] = r1 ,table[9][-] = r1,table[9][*] = r1。
其他以此类推.......
至此,SLR(1)分析表已经构建完成。
3. LR分析构建分析器
?
3.1 过程分析
1. 首先初始化栈内容 stack = { # ,0}
为了方便这里将stack栈拆分成两个栈,状态栈 prestate = {0},符号栈 prefix = { # }。
2. 对当前输入进行判断,以上表为例,第一次当前输入取 id 和 状态状态栈顶 0 进行查表分析,table[0][id] = S4,因此进行移进S4操作,S用当前输入id替换后,将id和4分别加入到栈中,
目前栈为prestate = {0,4},prefix = { # ,id}, 当前输入指向下一个字符,为--id*id#。
第二次,当前输入 - ,栈顶状态 4 ,查表table[4][-] = r6,执行归约操作,r6对应产生式F - > id,此时将prestate栈pop栈顶状态4,,prefix栈pop栈顶符号id并加入符号F,接着再次获取当前栈顶状态 0,查表table[0][F] = 3,最后将 3 加入到状态栈中即可。
3.以此类推,直至达到出错格局或接受格局为止!
注意: 每次格局发生变化,都需进行查表操作,并且一个字符对应一个状态。
?
3.2 JavaScript代码实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>LR分析器测试版</title>
<style>
table {
width: 600px;
text-align: center;
margin: auto;
}
table,
th,
td {
border: 1px solid #ccc;
border-collapse: collapse;
}
caption {
font-size: 18px;
margin-bottom: 10px;
font-weight: 700;
}
tr {
height: 40px;
cursor: pointer;
}
table tr:nth-child(1) {
background-color: #ddd;
}
table tr:not(:first-child):hover {
background-color: #eee;
}
</style>
</head>
<body>
<script>
document.write(`
<table>
<caption>LR(0)分析表</caption>
<tr>
<th>步骤</th>
<th>栈内容</th>
<th>当前输入</th>
<th>动作</th>
</tr>
`);
//保存结果:
let res1 = [];
let res2 = [];
let res3 = [];
let res4 = [];
// var w = 'id--id*id#';
var w = prompt('请输入合法的语句:如(id--id*id#)');
//检查语句是否合法
if(w.charAt(w.length-1) !== '#'){
w += '#';
}
w = w.replaceAll('id','i');
// 移进规约表的构造
var action_goto = [];
//初始化移进规约表
for (let i = 0; i < 11; i++) {
let temp = [];
for (let j = 0; j < 7; j++) {
temp.push('0');
}
action_goto.push(temp);
}
action_goto[1][3] = 'acc';
// 1. 构造文法3.12' 的拓广文法
//初始化文法
var ininGrammer = new Map([
['E', ['E-T', 'T']],
['T', ['T*F', 'F']],
['F', ['i', '-F']]
]);
// 初态项目集, key 表示左部 ,数组[0] 表示状态 0 表示未使用 1 表示已经使用过
// 拓广文法
var ininItems = [{
key: 'e',
item: '.E',
statu: 0
},
{
key: 'e',
item: 'E.',
statu: 0
}
];
//循环求出所有的 LR(0)项目集
for (let keys of ininGrammer.keys()) {
//获取 key 对应的 的值
let value_arr = ininGrammer.get(keys);
for (let k = 0; k < value_arr.length; k++) {
let value = value_arr[k];
//循环将得到子项目
for (let j = 0; j <= value.length; j++) {
let str1 = value.substring(0, j);
let str2 = value.substring(j);
let temp = str1 + '.' + str2;
ininItems.push({
key: keys,
item: temp,
statu: 0
});
}
}
}
console.log(ininItems);
let result = new Map();
let Iis = [];
//初始化
for (let i = 0; i < ininItems.length; i++) {
let Ii = {
key: '',
item: '',
statu: 1
};
if (ininItems[i].item.charAt(0) === '.' && ininItems[i].statu === 0) {
//构建 I0 集合
Ii.key = ininItems[i].key;
Ii.item = ininItems[i].item;
Ii.statu = 1;
ininItems[i].statu = 1;
Iis.push(Ii);
}
}
result.set(0, Iis);
let num = 0;
let n = 0;
let flag = true;
for (let i = 0; i < ininItems.length; i++) {
let tempChar = '';
for (let j = 0; j < result.get(n).length; j++) {
let value = result.get(n)[j].item;
let index = value.indexOf('.');
//获取点后的元素
let char = value.charAt(index + 1);
// 如果点不在末尾
if (char !== '' && char !== tempChar) {
let Iis = [];
// console.log(char);
// 避免重复移动元素
tempChar = char;
for (let k = 0; k < ininItems.length; k++) {
// 因为无法确定下一个项目是谁 ,所以不仅需要判断元素还需要判断点的位置
// 将未使用过的项目移进
if (ininItems[k].item.charAt(index) === char && ininItems[k].item.charAt(index + 1) ===
'.' && ininItems[k].statu === 0) {
let Ii = {
key: '',
item: '',
statu: 1
};
Ii.key = ininItems[k].key;
Ii.item = ininItems[k].item;
Ii.statu = 1;
ininItems[k].statu = 1;
Iis.push(Ii);
// 1.如果发生的新的转移,并且转移的状态本项目集中也包括,则也要添加至新的项目距集中
// 2.除开本身发生变化的
for (let p = 0; p < result.get(n).length; p++) {
let tempItem = result.get(n)[p].item;
let index2 = tempItem.indexOf('.');
if (result.get(n)[p].key !== ininItems[k].key && result.get(n)[p].item.charAt(index2 +
1) === char && char !== '' && n > 0) {
let Ii = {
key: '',
item: '',
statu: 1
};
//当前 项目的 下一项目
tempItem = tempItem.substring(0, index2) + tempItem.substring(index2 + 1);
tempItem = tempItem.substring(0, index2 + 1) + '.' + tempItem.substring(index2 + 1);
Ii.key = result.get(n)[p].key;
Ii.item = tempItem;
Ii.statu = 1;
Iis.push(Ii);
}
}
// 2.判断有没有下一状态转移
if (ininItems[k].item.charAt(index + 2) !== '') {
for (let p = 0; p < result.get(0).length; p++) {
if (result.get(0)[p].key === ininItems[k].item.charAt(index + 2)) {
let Ii = {
key: '',
item: '',
statu: 1
};
Ii.key = result.get(0)[p].key;
Ii.item = result.get(0)[p].item;
Ii.statu = 1;
Iis.push(Ii);
// 获取下一状态转移项目 , 并且不能和上一状态转移相同
if (Ii.item.charAt(1) !== ininItems[k].item.charAt(index + 2)) {
for (let u = 0; u < result.get(0).length; u++) {
if (result.get(0)[u].key === Ii.item.charAt(1)) {
let Ii = {
key: '',
item: '',
statu: 1
};
Ii.key = result.get(0)[u].key;
Ii.item = result.get(0)[u].item;
Ii.statu = 1;
Iis.push(Ii);
}
}
}
}
}
}
}
}
// 将新生成的项目集添加到 总的集合中
num++;
result.set(num, Iis);
}
}
if (n < num) {
n++;
}
}
console.log(ininItems);
console.log(result);
// 对项目集进行整理 ,清除空的项目集
let tempResult = new Map();
let tempKey = 0;
for (let key of result.keys()) {
if (result.get(key).length !== 0) {
tempResult.set(tempKey, result.get(key));
tempKey++;
}
}
//更新项目集
result = tempResult;
console.log(result);
console.log(tempKey);
// 构建位置对照方法 getPosition(字符 起始项目集编号 终点项目集编号)
function getPosition(char, num1, num2) {
switch (char) {
case 'i':
action_goto[num1][0] = 's' + num2;
break;
case '-':
action_goto[num1][1] = 's' + num2;
break;
case '*':
action_goto[num1][2] = 's' + num2;
break;
case '#':
action_goto[num1][3] = 's' + num2;
break;
case 'E':
action_goto[num1][4] = num2 + '';
break;
case 'T':
action_goto[num1][5] = num2 + '';
break;
case 'F':
action_goto[num1][6] = num2 + '';
break;
}
}
function isZJF(char) {
let refer = -1;
switch (char) {
case 'i':
refer = 1;
break;
case '-':
refer = 0;
break;
case '*':
refer = 0;
break;
case '#':
refer = 0;
break;
default:
refer = -1;
break;
}
return refer;
}
// 构建移进规约表 --- 转移操作
for (let i = 0; i < tempKey; i++) {
let tempChar = '';
for (let j = 0; j < result.get(i).length; j++) {
// 将项目集的项目取出
let value = result.get(i)[j].item;
// 找到 . 的位置
let index = value.indexOf('.');
// 找到 . 后的字符
let char = value.charAt(index + 1);
//如果字符为空 ,则说明到了句柄(末尾),如果不为空,则继续分析查询转移项目集
if (char !== '' && tempChar !== char) {
// 避免重复查找项目集中同一字符
tempChar = char;
// 将移动 . 后的 下一项目 在 所有项目集中查找 , 如果有则进行转移
let nextItem = value.substring(0, index) + value.substring(index + 1);
nextItem = nextItem.substring(0, index + 1) + '.' + nextItem.substring(index + 1);
// 在除开 I0的项目集中查找
for (let k = 1; k < tempKey; k++) {
for (let p = 0; p < result.get(k).length; p++) {
//如果查找到项目集中有和 下一项目 相当匹配的
if (result.get(k)[p].item === nextItem) {
// 传递 转移字符 起始项目集 终止项目集
getPosition(char, i, k);
break;
}
}
}
}
}
}
// 上述移进已经完成,接下来进行规约
//首先构造 follow集合
var follow = new Map();
for (let key of ininGrammer.keys()) {
let follow_arr = [];
if (key === 'E') {
follow_arr.push('#');
}
for (let key2 of ininGrammer.keys()) {
// 循环文法的右部
for (let i = 0; i < ininGrammer.get(key2).length; i++) {
// 判断产生式右部是否包含要查找的左部 ,若包含
if (ininGrammer.get(key2)[i].includes(key)) {
//获取该终结符的位置
let indexChar = ininGrammer.get(key2)[i].indexOf(key);
// 查找该非终结符后的终结符
let nextChar = ininGrammer.get(key2)[i].charAt(indexChar + 1);
// 查找,如果符合条件则加入到follow集中
// 如果左部的和右部中某一产生式相同,则将该右部对应的左部加入到查找的follow集中
if (key === ininGrammer.get(key2)[i]) {
follow_arr = follow_arr.concat(follow.get(key2));
}
if (isZJF(nextChar) === 0) {
follow_arr.push(nextChar);
}
}
}
}
follow.set(key, follow_arr);
}
// 获取终结符在表中的位置
function getZJFPosition(char) {
let refer = -1;
switch (char) {
case 'i':
refer = 0;
break;
case '-':
refer = 1;
break;
case '*':
refer = 2;
break;
case '#':
refer = 3;
break;
default:
refer = -1;
break;
}
return refer;
}
ininGrammer.set('F',['-F','i']);
// 构建移进规约表 --- 归约操作
//1. 循环文法
let rn = 1; // 按第n个产生式归约
for (let key of ininGrammer.keys()) {
//遍历每一个产生式
for (let i = 0; i < ininGrammer.get(key).length; i++) {
let tempItem = ininGrammer.get(key)[i] + '.'; // 记录当前的产生式形成的句柄
// 在项目集中判断 该句柄出现在哪个项目集中
for (let key2 of result.keys()) {
for (let j = 0; j < result.get(key2).length; j++) {
//如果在该项目中找到此句柄
if (result.get(key2)[j].item === tempItem) {
// 现在有了 第几个项目集 和 preChar代表用哪个follow(preChar)集 和 对应的规约产生式 rn,只需要写入表即可
for (let k = 0; k < follow.get(key).length; k++) {
let x = getZJFPosition(follow.get(key)[k]) // 查询终结符在表中的位置
if (x !== -1) {
action_goto[key2][x] = 'r' + rn;
}
}
}
}
}
rn++;
}
}
console.log(follow);
console.log(action_goto);
// 移进规约分析器 (步骤推导)
var prefix = ['#']; //活前缀
var preState = [0]; //状态表
function grammer(state) {
let str = '';
switch (state) {
case '1':
str = 'E=E-T';
break;
case '2':
str = 'E=T';
break;
case '3':
str = 'T=T*F';
break;
case '4':
str = 'T=F';
break;
case '5':
str = 'F=-F';
break;
case '6':
str = 'F=i';
break;
}
return str;
}
//查询表
function getQuery(num, char) {
let refer = '';
switch (char) {
case 'i':
refer = action_goto[num][0];
break;
case '-':
refer = action_goto[num][1];
break;
case '*':
refer = action_goto[num][2];
break;
case '#':
refer = action_goto[num][3];
break;
case 'E':
refer = action_goto[num][4];
break;
case 'T':
refer = action_goto[num][5];
break;
case 'F':
refer = action_goto[num][6];
break;
default:
refer = '0';
break;
}
return refer;
}
//循环次数
n = 0;
while(true){
// 获取序列的当前输入
let char = w.charAt(0);
// 获取当前栈顶的状态
let num = preState[preState.length-1];
//获取分析表中对应的 格局
let refer = getQuery(num ,char);
n++;
//收集结果
res1.push(n);
res3.push(w.replaceAll('i','id'));
let resStr = '';
let x = 0,y = 0;
while(true){
x < prefix.length ? resStr += prefix[x] : resStr;
y < preState.length ? resStr += preState[y] : resStr;
x++,y++;
if(x >= prefix.length && y > preState.length){
break;
}
}
res2.push(resStr.replaceAll('i','id'));
if(refer.charAt(0) === '0' ){
res4.push(`出错处理`);
break;
}else if(refer.charAt(0) === 's'){
prefix.push(char);
preState.push(parseInt(refer.charAt(1)));
res4.push(`移进${refer}`);
w = w.substring(1);
}else if(refer.charAt(0) === 'r'){
let temp = refer.charAt(1);
let str = grammer(temp).split('=');
for(let i = 0;i < str[1].length; i++){
preState.pop();
prefix.pop();
}
refer = getQuery(preState[preState.length-1] , str[0]);
preState.push(parseInt(refer));
prefix.push(str[0]);
str[1] = str[1].replaceAll('i','id');
res4.push(`归约:r${temp}(${str[0]}->${str[1]})`);
}else if(refer === 'acc'){
res4.push(`接收`);
break;
}
}
for(let i = 0 ;i < n; i++){
document.write(`
<tr>
<td>${res1[i]}</td>
<td>${res2[i]}</td>
<td>${res3[i]}</td>
<td>${res4[i]}</td>
</tr>
`);
}
document.write(`
</table>
`);
</script>
</body>
</html>
3.3 java代码实现(强哥翻译)
package com.wang;
import java.util.*;
public class Demo3 {
public static List<Integer> res1= new ArrayList<>();
public static List<String> res2= new ArrayList<>();
public static List<String> res3= new ArrayList<>();
public static List<String> res4= new ArrayList<>();
public static String w;
public static String[][] action_goto=new String[11][7];
public static Map<String,String[]> ininGrammer=new HashMap<>();
public static List<InitItem> initItems=new ArrayList<>();
public static Map<Integer,List<InitItem>> result=new HashMap<>();
public static List<InitItem> Iis=new ArrayList<>();
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
w=sc.nextLine();
if (w.charAt(w.length()-1)!='#'){
w+="#";
}
w=w.replaceAll("id","i");
for (int i = 0; i <11 ; i++) {
for (int j = 0; j <7 ; j++) {
action_goto[i][j]="0";
}
}
action_goto[1][3]="acc";
initMap(ininGrammer);
initI(initItems);
for (String key:ininGrammer.keySet()) {
String[] value_arr = ininGrammer.get(key);
for (int k = 0; k <value_arr.length ; k++) {
String value = value_arr[k];
for (int j = 0; j <=value.length() ; j++) {
String str1 = value.substring(0, j);
String str2 = value.substring(j);
String temp = str1 + "." + str2;
initItems.add(new InitItem(key,temp,0));
}
}
}
for (int i = 0; i <initItems.size() ; i++) {
InitItem Ii = new InitItem("", "", 1);
if (initItems.get(i).item.charAt(0)=='.'&&initItems.get(i).status==0){
Ii.key=initItems.get(i).key;
Ii.item=initItems.get(i).item;
Ii.status=1;
initItems.get(i).status=1;
Iis.add(Ii);
}
}
result.put(0,Iis);
int num=0;
int n=0;
boolean flag=true;
for (int i = 0; i <initItems.size() ; i++) {
String tempChar="";
for (int j = 0; j <result.get(n).size() ; j++) {
String value = result.get(n).get(j).item;
int index = value.indexOf(".");
String ch="";
try {
ch = String.valueOf(value.charAt(index + 1));
}catch (Exception e){
ch="";
}
if (!ch.equals("")&&!ch.equals(tempChar)){
List<InitItem> Iis=new ArrayList<>();
tempChar=ch;
for (int k = 0; k <initItems.size() ; k++) {
try {
if (initItems.get(k).item.charAt(index)==ch.toCharArray()[0]&&initItems.get(k).item.charAt(index+1)=='.'&&initItems.get(k).status==0){
InitItem Ii = new InitItem("", "", 1);
Ii.key=initItems.get(k).key;
Ii.item=initItems.get(k).item;
Ii.status=1;
initItems.get(k).status=1;
Iis.add(Ii);
for (int p = 0; p <result.get(n).size() ; p++) {
String tempItem = result.get(n).get(p).item;
int index2 = tempItem.indexOf(".");
try {
if (!result.get(n).get(p).key.equals(initItems.get(k).key)&&result.get(n).get(p).item.charAt(index2+1)==ch.toCharArray()[0]&&!ch.equals("")&&n>0){
InitItem Ii1 = new InitItem("", "", 1);
tempItem=tempItem.substring(0,index2)+tempItem.substring(index2+1);
tempItem=tempItem.substring(0,index2+1)+"."+tempItem.substring(index2+1);
Ii1.key=result.get(n).get(p).key;
Ii1.item=tempItem;
Ii1.status=1;
Iis.add(Ii1);
}
}catch (Exception e){
}
}
try {
if (!String.valueOf(initItems.get(k).item.charAt(index+2)).equals("")){
for (int p = 0; p <result.get(0).size() ; p++) {
if (result.get(0).get(p).key.equals(initItems.get(k).item.charAt(index+2)+"")){
InitItem Ii2 = new InitItem("", "", 1);
Ii2.key=result.get(0).get(p).key;
Ii2.item=result.get(0).get(p).item;
Ii2.status=1;
Iis.add(Ii2);
if (Ii2.item.charAt(1)!=initItems.get(k).item.charAt(index+2)){
for (int u = 0; u <result.get(0).size() ; u++) {
if (result.get(0).get(u).key.equals(Ii2.item.charAt(1)+"")){
InitItem Ii3 = new InitItem("", "", 1);
Ii3.key=result.get(0).get(u).key;
Ii3.item=result.get(0).get(u).item;
Ii3.status=1;
Iis.add(Ii3);
}
}
}
}
}
}
}catch (Exception e){
}
}
}catch (Exception e){
}
}
num++;
result.put(num,Iis);
}
}
if (n<num){
n++;
}
}
// System.out.println(initItems);
// System.out.println(result);
Map<Integer,List<InitItem>> tempResult=new HashMap<>();
int tempKey=0;
for (int key:result.keySet()) {
if (result.get(key).size()!=0){
tempResult.put(tempKey++,result.get(key));
}
}
result=tempResult;
// System.out.println(result);
for (int i = 0; i <tempKey ; i++) {
String tempChar="";
for (int j = 0; j <result.get(i).size() ; j++) {
String value = result.get(i).get(j).item;
int index = value.indexOf(".");
String ch="";
try {
ch = String.valueOf(value.charAt(index + 1));
}catch (Exception e){
ch="";
}
if (!ch.equals("")&&!tempChar.equals(ch)){
tempChar=ch+"";
String nextItem = value.substring(0, index) + value.substring(index + 1);
nextItem=nextItem.substring(0,index+1)+"."+nextItem.substring(index+1);
boolean flag1=false;
for (int k = 0; k <tempKey ; k++) {
for (int p = 0; p <result.get(k).size() ; p++) {
if (result.get(k).get(p).item.equals(nextItem)){
getPosition(ch.toCharArray()[0],i,k);
flag1=true;
break;
}
}
if (flag1){
break;
}
}
}
}
}
Map<String,List<Character>> follow=new HashMap<>();
List<String> tempKeys=new ArrayList<>();
tempKeys.add("E");
tempKeys.add("T");
tempKeys.add("F");
for (String key:tempKeys) {
List<Character> follow_arr=new ArrayList<>();
if (key.equals("E")){
follow_arr.add('#');
}
for (String key2:ininGrammer.keySet()) {
for (int i = 0; i <ininGrammer.get(key2).length ; i++) {
if (ininGrammer.get(key2)[i].contains(key)){
int indexChar = ininGrammer.get(key2)[i].indexOf(key);
char nextChar='a';
try {
nextChar = ininGrammer.get(key2)[i].charAt(indexChar + 1);
}catch (Exception e){
}
if (key.equals(ininGrammer.get(key2)[i])){
try {
follow_arr=concat(follow_arr,follow.get(key2));
}catch (Exception e){
}
}
if (isZJF(nextChar)==0){
follow_arr.add(nextChar);
}
}
}
}
follow.put(key,follow_arr);
}
ininGrammer.put("F",new String[]{"-F","i"});
int rn=1;
for (String key:tempKeys) {
for (int i = 0; i <ininGrammer.get(key).length ; i++) {
String tempItem = ininGrammer.get(key)[i] + ".";
for (int key2:result.keySet()) {
for (int j = 0; j <result.get(key2).size() ; j++) {
if (result.get(key2).get(j).item.equals(tempItem)){
for (int k = 0; k <follow.get(key).size() ; k++) {
int x = getZJFPosition(follow.get(key).get(k));
if (x!=-1){
action_goto[key2][x]="r"+rn;
}
}
}
}
}
rn++;
}
}
// System.out.println(follow);
// for (int i = 0; i <11 ; i++) {
// for (int j = 0; j <7 ; j++) {
// System.out.print(action_goto[i][j]+" ");
// }
// System.out.println();
// }
Stack<Character> prefix=new Stack<>();
prefix.push('#');
Stack<Integer> preState=new Stack<>();
preState.push(0);
n=0;
while (true){
char ch = w.charAt(0);
Integer num1 = preState.get(preState.size() - 1);
String refer = getQuery(num1, ch);
n++;
res1.add(n);
String s1 = w.replaceAll("i", "id");
res3.add(s1);
String resStr="";
int x=0,y=0;
while (true){
resStr=x<prefix.size()?resStr+prefix.get(x):resStr;
resStr=y<preState.size()?resStr+preState.get(y):resStr;
x++;
y++;
if (x>=prefix.size()&&y>preState.size()){
break;
}
}
String s = resStr.replaceAll("i", "id");
res2.add(s);
if (refer.charAt(0)=='0'){
res4.add("出错处理");
break;
}else if (refer.charAt(0)=='s'){
prefix.push(ch);
preState.push(refer.charAt(1)-'0');
res4.add("移进"+refer);
w=w.substring(1);
}else if (refer.charAt(0)=='r'){
char temp = refer.charAt(1);
String[] str = grammer(temp).split("=");
for (int i = 0; i <str[1].length() ; i++) {
preState.pop();
prefix.pop();
}
refer=getQuery(preState.get(preState.size()-1),str[0].toCharArray()[0]);
if (refer.equals("10")){
preState.push(10);
}else {
preState.push(refer.toCharArray()[0]-'0');
}
prefix.push(str[0].toCharArray()[0]);
str[1]=str[1].replaceAll("i","id");
res4.add("归约:r"+temp+"("+str[0]+"->"+str[1]+")");
}else if (refer.equals("acc")){
res4.add("接收:accept");
break;
}
}
for (int i = 0; i <n ; i++) {
int len=0;
System.out.printf("%s",res1.get(i));
len=res1.get(i)<10?1:2;
output(len);
System.out.printf("%s",res2.get(i));
len=res2.get(i).length();
output(len);
System.out.printf("%s",res3.get(i));
len=res3.get(i).length();
output(len);
System.out.printf("%s\n",res4.get(i));
}
}
public static void output(int len){
for (int j = 0; j <25-len ; j++) {
System.out.print(" ");
}
}
public static String getQuery(int num,char ch){
String refer="";
switch (ch){
case 'i':refer=action_goto[num][0];break;
case '-':refer=action_goto[num][1];break;
case '*':refer=action_goto[num][2];break;
case '#':refer=action_goto[num][3];break;
case 'E':refer=action_goto[num][4];break;
case 'T':refer=action_goto[num][5];break;
case 'F':refer=action_goto[num][6];break;
default:refer="0";break;
}
return refer;
}
public static String grammer(char state){
String str="";
switch (state){
case '1':str="E=E-T";break;
case '2':str="E=T";break;
case '3':str="T=T*F";break;
case '4':str="T=F";break;
case '5':str="F=-F";break;
case '6':str="F=i";break;
}
return str;
}
public static int getZJFPosition(char ch){
int refer=-1;
switch (ch){
case 'i':refer=0;break;
case '-':refer=1;break;
case '*':refer=2;break;
case '#':refer=3;break;
default:refer=-1;break;
}
return refer;
}
public static List<Character> concat(List<Character> a,List<Character> b){
List<Character> c=new LinkedList<>();
c.addAll(a);
c.addAll(b);
return DisRepet(c);
}
public static List<Character> DisRepet(List<Character> arr){
List<Character> arrayList=new ArrayList();
for (int i = 0; i <arr.size() ; i++) {
if (!arrayList.contains(arr.get(i))){
arrayList.add(arr.get(i));
}
}
return arrayList;
}
public static int isZJF(char ch){
int refer=-1;
switch (ch){
case 'i':refer=1;break;
case '-':refer=0;break;
case '*':refer=0;break;
case '#':refer=0;break;
default:refer=-1;
}
return refer;
}
public static void getPosition(char ch,int num1,int num2){
switch (ch){
case 'i':action_goto[num1][0]="s"+num2;break;
case '-':action_goto[num1][1]="s"+num2;break;
case '*':action_goto[num1][2]="s"+num2;break;
case '#':action_goto[num1][3]="s"+num2;break;
case 'E':action_goto[num1][4]=num2+"";break;
case 'T':action_goto[num1][5]=num2+"";break;
case 'F':action_goto[num1][6]=num2+"";break;
}
}
public static void initMap(Map<String,String[]> map){
String[] a={"E-T","T"};
map.put("E",a);
String[] b={"T*F","F"};
map.put("T",b);
String[] c={"i","-F"};
map.put("F",c);
}
public static void initI(List<InitItem> initItems){
initItems.add(new InitItem("e",".E",0));
initItems.add(new InitItem("e","E.",0));
}
}
class InitItem{
public String key;
public String item;
public int status;
public InitItem() {
}
public InitItem(String key, String item, int status) {
this.key = key;
this.item = item;
this.status = status;
}
@Override
public String toString() {
return "InitItem{" +
"key='" + key + '\'' +
", item='" + item + '\'' +
", status=" + status +
'}';
}
}
总结:以编程实现为主,个人分析难免有误,请多多指教!
?
|