IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 开发工具 -> [编译原理]构造LR分析器和SLR移进归约分析表 -> 正文阅读

[开发工具][编译原理]构造LR分析器和SLR移进归约分析表

目录

目标

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 分析得到各个项目集

e594f1f7b8c0408cade3fe97c8618aac.png

个人理解分析过程:

首先将所有的项目标记一个状态,假设 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分析表中的移进部分

f0812a8a0a0341b4bc77b9c3487ec12e.png

?id-*#ETF
0s4s5??123
1?s6?acc???
2??s7????
3???????
4???????
5s4s5????8
6s4s5???93
7s4s5????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-*#ETF
0s4s5??123
1?s6?acc???
2?r2s7r2???
3?r4r4r4???
4?r6r6r6???
5s4s5????8
6s4s5???93
7s4s5????10
8?r5r5r5???
9?r1s7r1???
10?r3r3r3???

?

1.SLR(1)规约需要用到follow集合,根据文法:

c9c58e64678f4f7e8bea79574c616f4b.png

?可求得:

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中匹配到了 ,

f8c770e33238448594fc2e4a48db2a1f.png

接着获取 . 前面的字符T,由此得知通过什么转移过来的,对应follow(T),接着遍历follow(T)中的元素? ,所以table[9][#] = r1 ,table[9][-] = r1,table[9][*] = r1。

其他以此类推.......

至此,SLR(1)分析表已经构建完成。

3. LR分析构建分析器

cd5a2cc50b734943b261350e94da6ff1.png

?

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 +
                '}';
    }
}

总结:以编程实现为主,个人分析难免有误,请多多指教!

?

  开发工具 最新文章
Postman接口测试之Mock快速入门
ASCII码空格替换查表_最全ASCII码对照表0-2
如何使用 ssh 建立 socks 代理
Typora配合PicGo阿里云图床配置
SoapUI、Jmeter、Postman三种接口测试工具的
github用相对路径显示图片_GitHub 中 readm
Windows编译g2o及其g2o viewer
解决jupyter notebook无法连接/ jupyter连接
Git恢复到之前版本
VScode常用快捷键
上一篇文章      下一篇文章      查看所有文章
加:2022-05-25 11:41:27  更:2022-05-25 11:41:58 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/14 15:15:02-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码