实验 2：语法分析程序的设计——以LL(1)为例
PS：源码私聊
1.实验软件环境
开发平台：Windows 11
编程语言：C++
编译器版本：GCC 11.20 C++20
IDE：VS Code
2.实验原理描述
求 F i r s t First First集合
对每一文法符号 X ∈ ( V n ∪ V t ) ∗ X∈(Vn\cup Vt)* X∈(Vn∪Vt)∗
①若 X ∈ V t ，则 F I R S T ( X ) = X X∈Vt ，则FIRST(X)={X} X∈Vt，则FIRST(X)=X。
②若 X ∈ V n ，且有产生式 X → a ， a ∈ V t ，则 a ∈ F I R S T ( X ) X∈Vn ，且有产生式X→a，a∈Vt，则a∈FIRST(X) X∈Vn，且有产生式X→a，a∈Vt，则a∈FIRST(X)。
③若 X ∈ V n ， X → ε ，则 ε ∈ F I R S T ( X ) X∈Vn ，X→ε，则ε∈FIRST(X) X∈Vn，X→ε，则ε∈FIRST(X)
④若 X ∈ V n ， Y 1 ， Y 2 ， . . . ， Y i ∈ V N X∈Vn，Y1，Y2，...，Yi ∈VN X∈Vn，Y1，Y2，...，Yi∈VN，
且有产生式 X → Y 1 , . . . , Y n X→Y1,...,Yn X→Y1,...,Yn。
若对于 1 ≤ i ≤ k ≤ n 1≤i≤k≤n 1≤i≤k≤n，都有 Y i ∈ ε , Yi∈ε, Yi∈ε, 则 F I R S T ( Y k + 1 ) − ε ∈ F I R S T ( X ) FIRST(Yk+1)-{ε}∈FIRST(X) FIRST(Yk+1)−ε∈FIRST(X)
求 F O L L O W FOLLOW FOLLOW集合
①对文法开始符号 S ，将“ # ” ( 结束标记）置于 F O L L O W ( S ) 中。即 F O L L O W ( S ) = # 。 ( ∵ 有句型 # S # ) S ，将“ \# ” ( 结束标记） 置于 FOLLOW(S) 中。即 FOLLOW(S)= { \# } 。 ( ∵有句型 \#S\#) S，将“#”(结束标记）置于FOLLOW(S)中。即FOLLOW(S)=#。(∵有句型#S#)
②若有 A → a B b ，则把 F I R S T ( β ) − ε 加至 F O L L O W ( B ) A→aBb，则把FIRST(β)-{ε}加至FOLLOW(B) A→aBb，则把FIRST(β)−ε加至FOLLOW(B)
③若有 A → a B A→aB A→aB或 A → a B b A→aBb A→aBb，而 b ∈ ε b∈ε b∈ε即 ε ∈ F I R S T ( b ) ) ε∈FIRST(b)) ε∈FIRST(b))；则把 F O L L O W ( A ) FOLLOW(A) FOLLOW(A)加至 F O L L O W ( B ) FOLLOW(B) FOLLOW(B)中。
判断是否为 L L ( 1 ) LL(1) LL(1)文法
①文法 不包含左递归 ;
②对于文法中的每一个非终结符 A的各个产生式的 侯选首字符集两两不相交 。
③即 ： 对于产生式
A
→
a
∣
b
A→a| b
A→a∣b
若
b
≠
ε
b ≠ ε
b=ε, 则$ FIRST( a ) ∩ FIRST( b )= Ф$
若
b
＝
ε
b ＝ε
b＝ε , 则
F
I
R
S
T
(
A
)
∩
F
O
L
L
O
W
(
A
)
=
Ф
FIRST(A) ∩FOLLOW(A)=Ф
FIRST(A)∩FOLLOW(A)=Ф
如果文法 G 满足以上条件，则称该文法 G 为 LL(1) 文法
3.功能实现描述
先分类 V n , V t Vn,Vt Vn,Vt
while (stream >> str) {
char vnTem = str[0];
vn.insert(vnTem); // 生成非终结符
string tem;
for (int i = 1; i < str.size(); i++) {
if (str[i] == ':' || str[i] == '=')
continue;
if (str[i] == '|') {
production[vnTem].push_back(tem);
rightSen.insert(tem);
tem.clear();
continue;
}
tem += str[i];
}
production[vnTem].push_back(tem);
rightSen.insert(tem);
}
// 生成终结符
for (auto i : production) {
for (auto j : i.second) {
for (auto ch : j) {
if (vn.count(ch))
continue;
vt.insert(ch);
firstSet[ch].insert(ch);
}
}
}
再生成First集合
// 生成First集合
void ShengChengFirst() {
bool ok = true;
while (ok) {
ok = false;
for (auto i : production) {
char vnTem = i.first;
int sz = (int)firstSet[vnTem].size();
for (auto str : i.second) {
if (str == "@") { // 如果str只有空 则直接将空加入
firstSet[vnTem].insert('@');
break;
}
for (int j = 0; j < str.size(); j++) {
char ch = str[j];
// 如果是终结符号 则加入并退出
if (vt.count(ch)) {
firstSet[vnTem].insert(ch);
break;
}
// 不能推导为空时，将first集合加入并退出
if (!firstSet[ch].count('@')) {
addFirstFirst(vnTem, ch);
break;
}
// 如果能够推导为空 将出去空的first集合加入
addFirstFirst(vnTem, ch);
// 如果全部都能推导为空 加入空
if (j == str.size() - 1)
firstSet[vnTem].insert('@');
}
}
if ((int)firstSet[vnTem].size() > sz)
ok = true;
}
}
}
然后生成Follow集合
// 生成Follow集合
void ShengChengFollow() {
followSet['E'].insert('#');
bool ok = true;
while (ok) {
ok = false;
for (auto i : production) {
char vnTem = i.first;
// 对于产生式 A -> aBc
for (auto r : i.second) { // 对于每个非终结符 产生式右块
for (int j = 0; j < r.size(); j++) {
char ch = r[j];
if (vt.count(ch)) { // 如果是终结符 跳过
continue;
}
// 如果是最后一个符号 将vnTem follow集合 加入到ch follow集合
if (j == r.size() - 1) {
int sz = followSet[ch].size();
addFollowFollow(ch, vnTem);
if (followSet[ch].size() > sz)
ok = true;
continue;
}
// 如果当前的下一个符号是终结符
if (vt.count(r[j + 1])) {
int sz = followSet[ch].size();
followSet[ch].insert(r[j + 1]);
if (followSet[ch].size() > sz)
ok = true;
} // 如果是非终结符 将下一个符号的first集合除去空
// 加入到follow集合
else {
int sz = followSet[ch].size();
addFollowFirst(ch, r[j + 1]);
if (j + 1 == r.size() - 1 &&
firstSet[r[j + 1]].count('@'))
addFollowFollow(ch, vnTem);
if (followSet[ch].size() > sz)
ok = true;
}
}
}
}
}
}
接着生成LL(1)分析表
// 生成LL(1)分析表
void ShengChengTable() {
vt.insert('#');
for (auto i : vn) {
for (auto j : vt) {
FenXiTable[i][j] = {string("")};
}
}
// 遍历文法
for (auto i : production) {
char vnTem = i.first;
int sz = (int)firstSet[vnTem].size();
for (auto str : i.second) {
bool empty = false;
for (auto first : firstSen[str]) {
if (first == '@') {
empty = true;
continue;
}
FenXiTable[vnTem][first] = string(1, vnTem) + "::=" + str;
}
if (empty) {
for (auto follow : followSet[vnTem]) {
FenXiTable[vnTem][follow] = string(1, vnTem) + "::=" + str;
}
}
}
}
}
最后再交互输入想要检验的字符串是否为文法中的句子
// 分析输入串
void FenXi(const string& str) {
stack<char> FenXiStack; // 分析栈
stack<char> ShuRuStack; // 输入栈
FenXiStack.push('#');
FenXiStack.push('E');
ShuRuStack.push('#');
for (int i = str.size() - 1; i >= 0; i--)
ShuRuStack.push(str[i]);
while (FenXiStack.size() && ShuRuStack.size()) {
while (FenXiStack.size() && ShuRuStack.size() &&
FenXiStack.top() == ShuRuStack.top())
FenXiStack.pop(), ShuRuStack.pop();
if (FenXiStack.empty() || ShuRuStack.empty())
break;
string tem = FenXiTable[FenXiStack.top()][ShuRuStack.top()];
if (tem.empty())
break;
FenXiStack.pop();
tem = tem.substr(4);
for (int i = tem.size() - 1; i >= 0; i--) {
if (tem[i] == '@')
continue;
FenXiStack.push(tem[i]);
}
}
if (FenXiStack.size() || ShuRuStack.size()) {
cout << "字符串: " << str << " 不是该文法的句子!!" << endl;
} else
cout << "字符串: " << str << " 是该文法的句子!!" << endl;
}
4.实验结果展示与分析
首先在同一文件夹下有一个 1. t x t 1.txt 1.txt文件，里面有符合条件的文法规则
接着运行
m
a
i
n
.
c
p
p
main.cpp
main.cpp文件，在命令行中输入要打开的文法规则文件，即
1.
t
x
t
1.txt
1.txt,按回车。
接着命令行里面就会打印出 F i r s t , F E L L O W First,FELLOW First,FELLOW集合和 L L ( 1 ) LL(1) LL(1)文法分析表
同时，我们输入想检验的字符串，判断是否为该文法的句子
5.实验感想
通过这个实验，我对语法分析的重要性有了更深刻的认识，并学到了实现它的方法。LL(1)文法的特点使得语法分析过程简洁高效，它通过预测下一个输入符号和栈顶符号来进行分析，避免了回溯和冲突。这个实验不仅提升了我的代码设计能力，还加深了我对文法和语法规则的理解。通过手动构建LL(1)分析表和编写相应的程序，我深入了解了语法分析算法的工作原理
