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

发布时间:2024年01月15日

实验 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(VnVt)?

①若 X ∈ V t ,则 F I R S T ( X ) = X X∈Vt ,则FIRST(X)={X} XVt,则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) XVn,且有产生式XaaVt,则aFIRST(X)

③若 X ∈ V n , X → ε ,则 ε ∈ F I R S T ( X ) X∈Vn ,X→ε,则ε∈FIRST(X) XVnXε,则εFIRST(X)

④若 X ∈ V n , Y 1 , Y 2 , . . . , Y i ∈ V N X∈Vn,Y1,Y2,...,Yi ∈VN XVnY1Y2...YiVN

且有产生式 X → Y 1 , . . . , Y n X→Y1,...,Yn XY1,...,Yn

若对于 1 ≤ i ≤ k ≤ n 1≤i≤k≤n 1ikn,都有 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) AaBb,则把FIRST(β)?ε加至FOLLOW(B)

③若有 A → a B A→aB AaB A → a B b A→aBb AaBb,而 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 Aab
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)分析表和编写相应的程序,我深入了解了语法分析算法的工作原理

文章来源:https://blog.csdn.net/ygh2437068791/article/details/135607362
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。