♻️ 资源
大小：66.2MB
➡️资源下载：https://download.csdn.net/download/s1t16/87450300
LALR(1) 分析表自动构造程序的实现
一、LALR(1) 分析表自动构造程序
1.1 设计任务：
LALR(1) 分析表自动构造程序的实现
1.2 设计内容及要求：
对任意给定的文法 G 构造 LR(1)项目集规范族（按教材 P.115 所述方法构造），要求实现 CLOSURE(I)、Go(I, X)、FIRST（集合 FIRST 的构造方法参见教材 P.78）；然后构造 LALR(1)项目集规范族；再实现 LALR(1)分析表构造算法。以教材 P.115 例 5.13 为输入，构造并输出其 LALR(1)分析表 5.6。
1.3 构造 LR(1)项目规范族：
1.3.1 CLOSURE(I)的构造：
算法思想：
I 中的所有项目都属于 CLOSURE(I)；
若项目[A→a.Bβ,a]属于 CLOSURE(I)，B→ξ 是一个产生式，那么，对于 FIRST<βa> 中的每一个中介符 b,如果[β→.ξ,b]原来不在 CLOSURE(I)中，则把它加进去；
重复执行步骤（2），直到 CLOSURE(I)不再增大为止。
实现及思路：
1.3.2 GO(I,X)的构造：
算法思想：
定义：
GO(I,X)=CLOSURE(J)其中 J={任何形如[A→aX.Β,a]的项目[A→a.X.Β,a]属于 I}
实现及思路：
1.3.3 FIRST 集合的构造：
算法思想：
每一个文法符号 FIRST(X)，X∈(VT∪VN)，对每一个文法符号 X 构造 FIRST(X)，其办法是，连续使用下面的规则，到每个集合 FIRST 不再增大为止：
若 X∈VT，则 FIRST(X)={X}。
若 X∈VN，且有产生式 X->a….，则把 a 加入到 FIRST(X)中；若 X->ε 也是一条产生式，则把 ε 也加到 FIRST(X)中。
若 X->Y…是一个产生式且 Y∈VN，则把 FIRST(Y)中的所有非 ε 元素都加入到 FIRST(X)中；若 X->Y1Y2…Yk 是一个产生式，Y1,Y2,…Yi-1 都是非终结符，而且，对于任何 j，1<=j<=i-1, FIRST(Yj)都含有 ε（即 Y1Y2…Yi-1->ε….(*)），则把 FIRST(Yi)中的所有非 ε 元素都加入到 FIRST(X)中，特别是，若所有的 FIRST(Yj)都含有 ε(1<=j<=k)，则把 ε 加入到 FIRST(X)中。
实现及思路：
初始输入文法后，求出所有的非终结符 FIRST 集合
求闭包时，需构建的 FIRST 集
1.4 构造 LALR(1)项目集规范族：
1.4.1 关键算法：由 LR(1)项目规范族转换为 LALR(1)项目集规范族
名词定义：
同心项目集：
如果除去搜索符之后，这两个集合是相同的，则我们两个 LR(1)项目集具有相同的心。
算法思想：
对于当前一个状态，遍历所有其他的状态，如果发现当前状态和其他某些状态是同心项目集，则保留这个状态，并把这些状态的搜索符全部并入到当前状态的搜索符中，并将这些状态从项目集规范族中移除。
1.4.2 实现及思路：
1.5 建立 LALR(1)分析表：
1.5.1 算法思想：
- 令每个 Ik 的下标 k 为分析表的状态，令含有[S’→·S, #]的 Ik 的 k 为分析器的初态。
- 若项目[A→α·aβ, b]属于 Ik 且 GO(Ik, a)＝Ij，a 为终结符，则置 ACTION[k, a]为 “sj”。
- 若项目[A→α·，a]属于 Ik，则置 ACTION[k, a]为 “rj”；其中假定 A→α 为文法 G’的第 j 个产生式。
- 若项目[S’→S·, #]属于 Ik，则置 ACTION[k, #]为 “acc”。
- 若 GO(Ik，A)＝Ij，则置 GOTO[k, A]=j。
- 分析表中凡不能用规则 1 至 4 填入信息的空白栏均填上“出错标志”。（程序输出时，空白表示）
1.5.2 实现及思路：
1.6 演示及结果：
1.6.1 测试文法：
1.6.2 初始界面：
1.6.3 选择文法文件：
1.6.4 构建 LALR(1)分析表：
1.6.5 查看 First 集合：
1.6.6 查看闭包：
1.6.7 查看自动机：
1.7 开发环境及语言
- 操作系统 : Windows8.1
- 开发软件：Visual Studio 2013
- 语言：MFC
