第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
LR(0)语法分析的设计与实现.doc
实 验 报 告 单
实验名称：
LR（0）分析程序的设计与实现
1
同组人：
实验室：
一、实验目的：
实验课时：4
报告日期：
LR 分析程序是一种从左至右扫描输入串，并按照自下而上的方式进行规范
规约的程序。以 LR（0）分析程序为例，了解 LR 分析程序的运行过程，掌握
原理。
二、实验原理：
1 判断文法是不是 LR（0）文法：
a) 定义：
活前缀：指规范句型的一个前缀，这种前缀不含句柄之后任何符号。
项目：文法 G 的每个产生式右部的某个位置添加一个“· ”。
规约项目：凡圆点在最右的项目，如 A→α•称为一个“归约项目”
移进项目：形如 A→α•aβ的项目，其中 a 为终结符，称为“移进”项
目。
拓广文法：假定文法 G 是一个以 S 为开始符号的文法，我们构造一个
文法 G’，它包含整个 G，但它引进了一个不出现在 G 中的非终结符 S’，
并加进一个新产生式 S’→S，而这个 S’是 G’的开始符号。那么我
们称 G’是 G 的拓广文法。
b) 构造 CLOSURE（I）函数和 goto（I，X）函数：
I 是文法 G 的任一项目集，I 的任何项目都属于 CLOSURE(I)； 若
A→α•Bβ属于 CLOSURE(I)，那么，对任何关于 B 的产生式 B→
γ，项目 B→•γ也属于 CLOSURE(I)；
重复执行上述两步骤直至 CLOSURE(I)不再增大为止。
goto（I，X）函数：函数 goto（I，X）是一个状态转换函数。
I 是文法 G 的任一项目集，X 是任一文法符号，函数值 GO(I,X)定
义为 GO(I,X)=CLOSURE(J)，其中 J={任何形如 A→αX•β的项目 |
A→α•Xβ属于 I}
c) 构造 LR（0）项目集规范族：
有了 CLOSURE（I）函数和 goto（I，X）函数，我们可以构造出 LR（0）
的项目集规范族，伪代码算法如下：
Begin
C:={CLOSURE({S’→·S})};
REPEAT
FOR C 中每个项目集 I 和 I 中每个紧接‘· ’后的不同 X do
If goto（I,X）非空且不属于 C then
将 goto（I,X）加到 C
Until C 不在增大
End；
通过这段算法可以得到拓广文法 G’的项目集规范族
d) 根据项目集规范族判断是不是 LR（0）文法：
如果文法 G’的项目集规范族中不存在以下冲突：
1 移进项目和规约项目并存
2 多个规约项目并存
则 G’是 LR（0）文法，否侧不是。
2 构造 LR（0）分析表：
设一文法 G'的项目集规范族 C={I0, I1，，，In};
1 若项目 A→α·xβ∈Ii,且 goto(Ii, x)=Ij ，x∈Σ， 则置 ACTION[i, x]=Sj,
即“ 将状态 j、符号 x 移进栈”;但若 x∈N,则仅置 GOTO[i, x]=j.
2 若 项 目 A → α · ∈ Ii ， 对 于 任 何 输 人 符 号 a ∈ ( Σ U {#}), 则 置
ACTION[i,a]=rj，即“用第 j 条产生式 A→α进行归约” (这里假定 A-
→α是 G 中的第 j 条产生式)
3 若项目 S'→S·∈Ik,则置 ACTION[k, #]=“接收”。
4 分析表中凡不能用规则①~③填人信息的元素均置上 ERROR (用空白表
示) .
3 根据分析表分析输入串：
记状态栈 S，输入栈 str，初始状态符号栈 S 压入 0，输入串末尾加’ #’并逆
序压入输入栈 str。
取输入栈 str 栈顶元素与状态栈 S 顶部比较，查询子表 ACTION 判断规约、
移进还是接受。如果是规约，先将状态栈 S 需要规约的部分出栈，然后规
约符号入栈，再将规约后的状态值入栈，输入栈 str 不变；如果是移进，str
顶部出栈，压入 S，再将新的状态值压入 S；如果是接受，则输入串分析完
毕；如果查表为空，则出现错误，此输入串不合法。
三、实验过程：
部分代码如下：
#include
#include
#include
#include
#include
#include
#include
#include
#include
class WF
{
public:
string left, right;
int back;
int id;
WF(char s1[], char s2[], int x, int y)
{
}
left = s1;
right = s2;
back = x;
id = y;
WF(const string& s1, const string& s2, int x, int y)
{
}
left = s1;
right = s2;
back = x;
id = y;
bool operator < (const WF& a) const
{
}
if (left == a.left)
return right < a.right;
return left < a.left;
bool operator == (const WF& a) const
{
}
return (left == a.left) && (right == a.right);
void print()
printf("%s->%s\n", left.c_str(), right.c_str());
{
}
};
class Closure
{
public:
vector element;
void print(string str)
{
}
printf("%-15s%-15s\n", "", str.c_str());
for (int i = 0; i < element.size(); i++)
element[i].print();
bool operator == (const Closure& a) const
{
}
if (a.element.size() != element.size()) return false;
for (int i = 0; i < a.element.size(); i++)
if (element[i] == a.element[i]) continue;
else return false;
return true;
};
struct Content
{
int type;
int num;
string out;
Content() { type = -1; }
Content(int a, int b)
:type(a), num(b) {}
};
vector wf;
map > dic;
string start = "S";
vector collection;
vector items;
char CH = '$';
int go[MAX][MAX];
int to[MAX];
vector V;
bool used[MAX];
Content action[MAX][MAX];
int Goto[MAX][MAX];
四、实验结果：
输入：
文法规则数量：6
文法规则：
E->E+T
E->T
T->T*F
T->F
F->(E)
F->i
输入串：”i*i+I”
输出：
step
S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
0i5
0F3
0T2
0T2*7
0T2*7i5
0T2*7F10
0T2
0E1
0E1+6
0E1+6i5
0E1+6F3
0E1+6T9
0E1
接收
str
i*i+i#
*i+i#
*i+i#
*i+i#
i+i#
+I#
+i#
+i#
+i#
i#
#
#
#
#
———————————————————————————————
成绩：
批阅教师：
日
期：
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
