实验 2：语法分析程序的设计——以LL(1)为例(更适合njupt体质的宝宝)

实验 2：语法分析程序的设计——以LL(1)为例

PS：源码私聊

1.实验软件环境

? 开发平台：Windows 11

? 编程语言：C++

? 编译器版本：GCC 11.20 C++20

? IDE：VS Code

2.实验原理描述

求$First$集合

对每一文法符号$X\in (Vn\cup Vt)?$

①若$X\in Vt，则FIRST(X)=X$。

②若$X\in Vn，且有产生式X\to a，a\in Vt，则a\in FIRST(X)$。

③若$X\in Vn，X\to \epsilon ，则\epsilon \in FIRST(X)$

④若$X\in Vn，Y1，Y2，...，Yi\in VN$，

且有产生式$X\to Y1,...,Yn$。

若对于$1\le i\le k\le n$，都有$Yi\in \epsilon ,$ 则$FIRST(Yk+1)?\epsilon \in FIRST(X)$

求$FOLLOW$集合

①对文法开始符号 $S，将“\#”(结束标记）置于FOLLOW(S)中。即FOLLOW(S)=\#。(\because 有句型\#S\#)$

②若有$A\to aBb，则把FIRST(\beta )?\epsilon 加至FOLLOW(B)$

③若有$A\to aB$或$A\to aBb$，而$b\in \epsilon$即$\epsilon \in FIRST(b))$；则把$FOLLOW(A)$加至$FOLLOW(B)$中。

判断是否为$LL(1)$文法

①文法 不包含左递归 ;
②对于文法中的每一个非终结符 A的各个产生式的 侯选首字符集两两不相交 。
③即 ： 对于产生式$A\to a|b$
若$b\ne \epsilon$, 则$ FIRST( a ) ∩ FIRST( b )= Ф$
若 $b＝\epsilon$ , 则 $FIRST(A)\cap FOLLOW(A)=Ф$
如果文法 G 满足以上条件，则称该文法 G 为 LL(1) 文法

3.功能实现描述

先分类$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.txt$文件，里面有符合条件的文法规则

接着运行$main.cpp$文件，在命令行中输入要打开的文法规则文件，即$1.txt$,按回车。

接着命令行里面就会打印出$First,FELLOW$集合和$LL(1)$文法分析表

同时，我们输入想检验的字符串，判断是否为该文法的句子

5.实验感想

通过这个实验，我对语法分析的重要性有了更深刻的认识，并学到了实现它的方法。LL(1)文法的特点使得语法分析过程简洁高效，它通过预测下一个输入符号和栈顶符号来进行分析，避免了回溯和冲突。这个实验不仅提升了我的代码设计能力，还加深了我对文法和语法规则的理解。通过手动构建LL(1)分析表和编写相应的程序，我深入了解了语法分析算法的工作原理