1、上机要求

目的：熟练掌握自上而下的语法分析方法，并能用程序实现。

要求：

例如，使用的文法如下：
编写First函数，实现其求解过程。

E -> TE'
E' -> +TE' | #
T -> FT'
T' -> *FT' | #
F -> (E) | id
end

提示：

• 非终结符为 大写字母；或 后面带'的大写字母
• 终结符为 小写字母和符号（+、*）
• 推导符号→为或->
• 用end结束文法。
  

不针对特定文法，编写求first函数。

2、原理

A -> a， 则将 a 加入 First(A)中
A -> Y1Y2···Yn

将 First(Y1) 除空串外的字符加入到First(A)中，若 1 = i n - 1，Y1，Y2， Yi中均含有空串，则将First(Yi + 1)加入到First(A)中，若Y1，Y2，···，Yn都有空串，则将空串加入到First(A)中

First(a) = { a}

3、一点思路及优化

将输入格式化（扫描输入）
将产生式转换为哈希map：

• 对任一产生式： A -> body_1 | body_2 | ··· | body_n，
• 将 A 作为map的 key，
• map的value为一个string类的向量(vectorstring> )，
• 将 body_1，body_2，···，body_n 都加入value中。
  
• 求解First(str)
• 特殊情况处理，str为空或str不在产生式的key中，返回空；str的首个字符是终结符，返回首个字符构成的集合。
• 一般情况，获取str推导产生的产生体集bodys(其中的每个产生体为body)，遍历产生体集合求解First集
• 针对空串，我们加入标记hasBlank = true，往下遍历body的字符
• body的首个字符为终结符，直接将该字符加入first集，记hasBlank = false以便遍历下一body（如果有的话）。
• body的首个字符为非终结符，递归求解该非终结符first集，记为temp，同时将空串标记记为false，将temp的中除空串外的字符加入first集；若temp中有空串，记空串标记为true，继续遍历当前body的字符，理解上可以将body后面的字符串视为一个新的body继续进行求解步骤。
• body的字符遍历结束后若空串标记hasBlank仍然为true，则将空串加入first集。
• 优化：递归求解的中间结果可以放在全局哈希First（或者换个名字避免冲突）中，避免重复的迭代（本代码没实现，下次一定）。

4、代码

/**
 * @brief Function for generating set of First(a)
 * @author 立秋小猪
 * @time: 2021/10/13
 * @notice: 要求产生体句型不得有空格
 *          左递归的产生体中必须有空串（必须能够终结）
 *          char '#' act as varepsilon 
 * **/

#include iostream>
    
#include unordered_map>
    
#include vector>
    
#include string>
    
#include fstream>
    
#include unordered_set>
    

using namespace std;
    

unordered_mapstring, vectorstring>
    >
     P;
 //产生式P的集合

void scan(){
    
    //scan函数实现从文件扫描文法，将对应的产生式加入到映射P中
    fstream fs;
    
    string input;
    
    fs.open("lan.txt");

    if(!fs.is_open()){
     // 文件打开失败
        cout  "Error: Could not open the file"  endl;
    
        exit(-1);

    }
    
    fs >
    >
     input;

    while(input != "end"){
    
        string VN = input;
     // 产生式的非终结符

        fs >
    >
     input;
     //跳过推导符号
        if (input != "->
    " &
    &
 input != "→"){
    
            cout  "Error: undefined symbol ["  input  "]"  endl;
    
            exit(-2);

        }
    

        fs >
    >
     input;
     //产生体拆开后加入到set集合中，默认推导符号后必有一个产生体
        P[VN].emplace_back(input);
    
        while( fs >
    >
     input &
    &
 input == "|"){
    
                fs >
    >
     input;
    
                P[VN].emplace_back(input);

        }

    }

}


// void generate(){

// }
    

unordered_setchar>
     First(const string&
 str){

    // 终结符以及空串情况下, whether has the VN or not
    if(str == "" || str == "#" || P.find(str) == P.end())
        return {
}
    ;
    
    if(!(str[0] >
    = 'A' &
    &
 str[0] = 'Z'))
        return {
str[0]}
    ;
    

    vectorstring>
     bodys = P[str];
     // str ->
     bodys
    unordered_setchar>
 res = {
}
    ;
    
    for(auto &
s: bodys){
    
        bool hasBlank = true;
    //是否含有空串，是否继续读产生体
        for (int i = 0;
     i  s.size() &
    &
     hasBlank;
 ++i){
    
            if(s[i] >
    = 'A' &
    &
 s[i] = 'Z'){
    //是否为终结符
                unordered_setchar>
 temp = {
}
    ;
    //递归的临时集
                string next;
    
                if(i  s.size() - 1 &
    &
 s[i + 1] == '\''){
     // 大写字母 + ' 的非终结符
                    next = s.substr(i, 2);
    
                    ++i;

                }
else{
     //仅仅是大写字母的终结符
                    next = s[i];

                }

                if(next != str){
     //避免无限递归，默认自身是含有空串（hasBlank为True）
                    temp = First(next);
     //递归求解
                    hasBlank = false;
     //先默认temp中没有空串
                    for(auto &
    c : temp)
                        if(c == '#')
                            hasBlank = true;
    //temp中发现了空串
                        else
                            res.emplace(c);

                }

            }
else{
    
                res.emplace(s[i]);
    
                hasBlank = false;
//默认连接的终结符不为空，故此终结符后不会再有新元素加入First集
            }

        }
    
        if(hasBlank) //产生体中所有非终结符都包含空串，则将空串加入first集中
            res.emplace('#');

    }
    
    return res;

}


 

int main(){
    
    // unordered_mapstring, vectorchar>
    >
     First;
     //First集合
    scan();
    
    cout  "输入的产生式如下：\n"
          "********************************\n";
    
    for(auto &
[vn, bodys]: P){
    
        cout  vn  " ->
     "  bodys[0];
    
        for (int i = 1;
     i  bodys.size();
     ++i)
            cout  " | "  bodys[i];
    
        cout  endl;

    }
    
    cout  "********************************\n";
    

    for(auto &
[vn,_]: P){
    
        unordered_setchar>
     f = First(vn);
    
        cout  "First("  vn  ") : ";
    
        auto iter = f.begin();


        if(iter != f.end()){
    
            cout  *iter;

            while(++iter != f.end()){
    
                cout  " , "  *iter;

            }

        }
    
        cout  endl;

    }
    

    return 0;

}
    

4.1 lan.txt文件内容

E ->
     TE'
E' ->
     +TE' | #
T ->
     FT'
T' ->
     *FT' | #
F ->
     (E) | id
end

运行结果

4.2 lan.txt文件内容

S ->
     SaRb | #
R ->
     RSQ | #
Q ->
     e
end

运行结果

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！