LL(1)分析器 实验二

实验要求

简单要求：

至少做到对下列已知的文法，用LL（1）分析法对任意输入的符号串进行分析：

（1）E->TG

（2）G->+TG

（3）G->ε

（4）T->FS

（5）S->*FS

（6）S->ε

（7）F->(E)

（8）F->I

高要求：

1、手动输入文法

2、显示文法的非终结符的Follow集

3、显示规则的可选集合

3、构造预测分析表

4、对任意输入的符号串进行分析

记号和规定

• 空串：$
• 符号栈终止符：#
• 规定第一个产生式的左边那个非终结符就是开始符号

简单要求的固定文法（无左递归）

（1）E->TG

（2）G->+TG

（3）G->ε

（4）T->FS

（5）S->*FS

（6）S->ε

（7）F->(E)

（8）F->I

First Follow Select 集合

产生式对应的SELECT集

分析表

简单要求(固定文法递归的预测分析)

在主函数中构造一个RecursionSimple对象调用run方法即可运行

运行示例

[递归式固定文法]请输入需要分析的字符串：
I
[递归式固定文法]*****输入的字符串符合该文法*****success*****
[递归式固定文法]请输入需要分析的字符串：
***
[递归式固定文法]#####输入的字符串符不合该文法#####error#####
[递归式固定文法]请输入需要分析的字符串：
(I)
[递归式固定文法]*****输入的字符串符合该文法*****success*****

头文件 RecursionSimple.h

#pragma once

#include<iostream>
using namespace std;


//简单的递归版本 固定文法 
class RecursionSimple{
	public:
		static const string name;
		static enum over{Run,Error,Success};
		int isOver;
		char cur;
		int len;
		int pos;//当前指向的字符位置
		string text;//需要分析的文本

		//文法函数
		void E();
		void T();
		void G();
		void S();
		void F();

		//执行函数
		void run();
		//读入数据 在末尾插入#
		void cinData();
		//输入的字符串符合文法
		void success();
		//输入的内容不符合文法处理函数
		void error();
		//获取下一个字符 如果已经到了末尾则执行 error()
		void next();
		//输出结果
		void coutResult();


};

源文件 RecursionSimple.cpp

#include "RecursionSimple.h"

#define IS_OVER if(isOver!=Run)return;

const string RecursionSimple::name = "[递归式固定文法]";

void RecursionSimple::E(){
	IS_OVER
	T();
	G();
}

void RecursionSimple::T(){
	IS_OVER
	F();
	S();
}

void RecursionSimple::G(){
	IS_OVER
	if(cur == '+'){
		next();
		T();
		G();
	} else if(cur != '+' && cur != ')' && cur != '#')error();
}

void RecursionSimple::S(){
	IS_OVER
	if(cur == '*'){
		next();
		F();
		S();
	} else if(cur != '+' && cur != ')' && cur != '#')error();
}

void RecursionSimple::F(){
	IS_OVER
	if(cur == '('){
		next();
		E();
		if(cur == ')')next(); else error();

	} else if(cur == 'I'){
		next();
	} else error();
}

void RecursionSimple::run(){
	cout << "文法：\n" << "E->TG\n" << "G->+TG\n" << "G->ε\n" << "T->FS\n" << "S->*FS\n" << "S->ε\n" << "F->(E)\n" << "F->I\n";
	cinData();//读入数据 并初始化
	next();//获取第一个字符
	E();//分析开始（首个非终结符函数）
	if(cur == '#')success();
	else error();
	coutResult();//输出结果
}

void RecursionSimple::cinData(){
	cout << name << "请输入需要分析的字符串：" << endl;
	cin >> text;
	text += '#';
	pos = 0;
	isOver = false;
	len = text.length();
}

void RecursionSimple::success(){
	isOver = Success;
}

void RecursionSimple::error(){
	isOver = Error;
}

void RecursionSimple::next(){
	if(pos < len){
		cur = text[pos++];
		return;
	}
	error();
}

void RecursionSimple::coutResult(){
	if(isOver==Success)	cout << name << "*****输入的字符串符合该文法*****success*****" << endl;
	else cout << name << "#####输入的字符串符不合该文法#####error#####" << endl;
}

高要求(任意文法非递归的预测分析)

1. 读入文法
2. 确定终结符与非终结符
3. 去除左递归
4. First集 Follow集
5. 判断是否为LL(1)文法(First与Follow元素不相交)
6. Select集
7. 预测分析表
8. 分析

解析

1. 读入文法: A -> @B a | c | $

   • 先输入左边 (在这里输入含有 # 的会结束文法输入)
   • 再输入右边 (同时输入各种可能 用 | 隔开 非终结符要在前面加@ ,#号结束本次右边输入)
   • 不可以包含下划线
   • 包含$的将自动转换为$单个字符

2. 确定终结符与非终结符

3. 去除左递归

   • 先将间接左递归转换为直接左递归
   • 将所有直接左递归消除
   • 删除所有不可达的产生式

4. First集 Follow集

   • First集：
     • 遍历每一个左部为x的产生式
     • 如果产生式右部第一个字符为终结符，则将其计入左部非终结符的First集
     • 如果产生式右部第一个字符为非终结符
     • 求该非终结符的First集
     • 将该非终结符的去掉$的First集计入左部的First集
     • 若存在$，继续往后遍历右部
     • 若不存在$，则停止遍历该产生式，进入下一个产生式
     • 若已经到达产生式的最右部的非终结符（即右部的First集都含有空串），则将$加入左部的First集
     • 处理数组中重复的First集中的终结符
   • Follow集：
     • 如果x为起始符，x的Follow集添加#
     • 遍历每一个右部包含非终结符x的产生式
     • 如果x的下一个字符是终结符，添加进x的Follow集
     • 如果x的下一个字符是非终结符，把该字符的First集加入x的Follow集（不能加入空串）
     • 如果下一字符的First集有空串并且该产生式的左部不是x，则把左部的Follow集加入x的Follow集
     • 如果x已经是产生式的末尾，则把左部的Follow集添加到x的Follow集里

5. 判断是否为LL(1)文法：First与Follow元素不相交

6. Select集： First集(除去ε) [+ Follow集(如果First集存在ε)]

7. 预测分析表

   • 遍历每一个左部为x的产生式
   • 如果x右边首字符串为 空串 则添加x的Follow集
   • 如果x右边首字符串为 终结符 则添加该终结符
   • 如果x右边首字符串为 非终结符 则添加x的First集

8. 分析

   • 分析栈放入 S# (S为起始非终结符) 文本栈放入 文本#
   • 获取分析栈顶l与文本栈顶m
   • l如果为空串则直接出栈l
   • l如果为终结符 看l是否等于m 相等则匹配（一起出栈） 否则报错
   • l如果为非终结符 看l的分析表是否有m 有则一起出栈 否则报错
   • 分析栈与文本栈都全部出栈 则分析成功！

运行示例

示例一 固定文法

[郭坤 软工一班 20192758]
欢迎使用LL1文法分析器，输入1使用固定文法，否则自定义文法:1
*****固定文法*****
E->TG
G->+TG|$
T->FS
S->*FS|$
F->(E)|I


First集
E:{ ( I }
F:{ ( I }
G:{ $ + }
S:{ $ * }
T:{ ( I }

Follow集
E:{ # ) }
F:{ # ) * + }
G:{ # ) }
S:{ # ) + }
T:{ # ) + }

是否为LL1文法：是

Select集
E:{ ( I }
F:{ ( I }
G:{ # ) + }
S:{ # ) * + }
T:{ ( I }

预测分析表
                   #         (         )         *         +         I
         E    @empty        TG    @empty    @empty    @empty        TG
         F    @empty       (E)    @empty    @empty    @empty         I
         G         $    @empty         $    @empty       +TG    @empty
         S         $    @empty         $       *FS         $    @empty
         T    @empty        FS    @empty    @empty    @empty        FS

请输入待识别的符号串(空格分割，直到遇到#截止)
( I ) #

              分析栈                    剩余输入串              推导式
                  E#                          (I)#               E->TG
                 TG#                          (I)#               T->FS
                FSG#                          (I)#              F->(E)
              (E)SG#                          (I)#              ( 匹配
               E)SG#                           I)#               E->TG
              TG)SG#                           I)#               T->FS
             FSG)SG#                           I)#                F->I
             ISG)SG#                           I)#              I 匹配
              SG)SG#                            )#          S 空串出栈
               G)SG#                            )#          G 空串出栈
                )SG#                            )#              ) 匹配
                 SG#                             #          S 空串出栈
                  G#                             #          G 空串出栈
                   #                             #            @Accept!

示例二 任意文法

[郭坤 软工一班 20192758]
欢迎使用LL1文法分析器，输入1使用固定文法，否则自定义文法:0
输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
左边的非终结符:A @B c | d # B @A | f # #
右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割！非终结符前加@):
*****结束右边的输入*****
A->Bc|d
输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
左边的非终结符:右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割！非终结符前加@):
*****结束右边的输入*****
B->A|f
输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
左边的非终结符:*****结束文法输入*****
*****输入的文法如下*****
A->Bc|d
B->A|f

*****消除间接左递归*****
A->d|Ac|fc
B->A|f

*****消除直接左递归*****
A->dA_|fcA_
B->A|f
A_->$|cA_

*****删除不可达的文法*****
A->dA_|fcA_
A_->$|cA_


First集
A:{ d f }
A_:{ $ c }

Follow集
A:{ # }
A_:{ # }

是否为LL1文法：是

Select集
A:{ d f }
A_:{ # c }

预测分析表
                   #         B         c         d         f
         A    @empty    @empty    @empty       dA_      fcA_
        A_         $    @empty       cA_    @empty    @empty

请输入待识别的符号串(空格分割，直到遇到#截止)
f c c c #

              分析栈                    剩余输入串              推导式
                  A#                         fccc#            A_->fcA_
               fcA_#                         fccc#              f 匹配
                cA_#                          ccc#              c 匹配
                 A_#                           cc#             A_->cA_
                cA_#                           cc#              c 匹配
                 A_#                            c#             A_->cA_
                cA_#                            c#              c 匹配
                 A_#                             #         A_ 空串出栈
                   #                             #            @Accept!

代码

类头文件 ArbitraryGrammar.h

#pragma once
#include<iostream>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#include<iomanip>
#include<string>
using namespace std;

/*
- 空串：$
- 符号栈终止符：#
*/

//产生式
struct Production{
	string left;    //产生式左边 非终结符
	vector<vector<string>> right;   //产生式右边

    Production(string l,vector<vector<string>>r){ left = l;right = r; }
    Production(string l){ left = l; }

    string getRightString(int i){//获得右边所有元素联合的串
        string s = "";
        for(auto r : right[i])s += r;
        return s;
    }
    void insert(vector<string> temp){
        right.push_back(temp);
    }
    void insert(string temp){
        vector<string>v;
        v.push_back(temp);
        right.push_back(v);
    }
    string toString(){
        string str = left + "->";
        for(auto s : right[0])str += s;
        int len = right.size();
        for(int i = 1;i < len;i++){
            str += "|";
            for(auto s : right[i])str += s;
        }
        return str;
    }
};

//任意文法的LL(1)分析类
class ArbitraryGrammar{
public:
    ArbitraryGrammar();         //构造函数
    void run();                 //运行程序
    void displayGrammarHint(string s);  //打印系统提示语句 中间夹杂当前文法
    void displayGrammar();      //打印当前的文法
    void displayResultTable();  //打印分析结果表
    void displayAnalyzedTable();//打印预测分析表
    bool isNonTer(string x);    //判断是否是 非终结符
    bool isTer(string x);       //判断是否是 终结符
    void inputText();           //待分析的字符串输入 输入#号结束
    void display();             //打印First集,Follow集,Select集
protected:



    int  getNonTerPos(string x);//获取非终结符下标
    int  getTerPos(string x);   //获取终结符下标
    void init();                //初始化
    void load();                //加载数据 调用其他方法
    void inputGrammar();        //输入文法 输出#号结束

    bool isLL1Grammar;          //是否为LL1文法
    bool isLoad;                //是否加载了数据
    bool isAnalyzed;            //是否已经分析了输入的字符串
    string Start;               //起始符


    //文本是否已经分析完毕
    vector<Production> prod;    //产生式集合
    vector<string>text;         //拆分后的 待分析文本
    vector<vector<string>>resultTable;//分析后生成的结果分析表 0 分析栈 1 剩余输出串 2 推导式
    vector<bool>used;          //dfs看看哪些文法是访问了的

    vector<set<string>> first;  //First集
    vector<set<string>> follow; //Follow集
    vector<set<string>> select; //select集

    map<string,int> terAndEnd;  //终结符与#
    map<string,int> ter;        //终结符
    map<string,int> nonTer;     //非终结符 string为非终结符 int为对应编号


    vector<vector<int>> table;  //分析表[非终结符][终结符]-> 存储的是产生式prod的下标 

    void judgeLL1Grammar();     //判断文法是否为LL(1)文法 First与Follow不相交
    void getFirst(string x);    //获取某个非终结符的First集
    void getAllFirst();         //获取所有非终结符的First集
    void getFollow(string x);   //获取某个非终结符的Follow集
    void getAllFollow();        //获取所有非终结符的Follow集
    void getAllSelect();        //获取产生式的Select集
    void getAnalyzTable();      //获取预测分析表
    string getTableE(int prodPos,int rightPos);    //获取预测分析表中的元素 -1 empty -2 synch 
    void getResultTable();      //获取分析后的结果表
    string getVectorString(vector<string> v);//将字符串集合整合为一个字符串
    string getListString(list<string> li);//将字符串集合整合为一个字符串
    void dfs(int x);
    void simplify();
    void removeDirectly(int i);
    void removeIndirect(int i,int len);//消除间接做递归 产生式下标i 产生式数len
    void removeAllDirectly();
    void removeAllIndirect();
    void removeLeftRecursion(); //消除左递归
    void resize(int len);       //更新容器大小
};

类源文件 ArbitraryGrammar.cpp

#include "ArbitraryGrammar.h"

ArbitraryGrammar::ArbitraryGrammar(){
    //init();
}

bool ArbitraryGrammar::isNonTer(string x){
    return nonTer.find(x) != nonTer.end();
}

bool ArbitraryGrammar::isTer(string x){
    return terAndEnd.find(x)!=terAndEnd.end();
}

int ArbitraryGrammar::getNonTerPos(string x){
    return nonTer.at(x);
}

int ArbitraryGrammar::getTerPos(string x){
    return terAndEnd.at(x);
}

void ArbitraryGrammar::init(){
    /*产生式
    （1）E->TG
    （2）G->+TG
    （3）G->ε
    （4）T->FS
    （5）S->*FS
    （6）S->ε
    （7）F->(E)
    （8）F->I
    */

    

    for(auto t : ter)terAndEnd.insert(t);
    int ii = terAndEnd.size();
    terAndEnd["#"] = ii;



    Start = prod[0].left;

    int size = nonTer.size();
    
    resize(size);

    isLoad = false;
}

void ArbitraryGrammar::inputText(){
    //待分析的字符串输入 输入#号结束
    cout << endl;
    cout << "请输入待识别的符号串(空格分割，直到遇到#截止)" << endl;
    vector<string>().swap(text);
    string sin;cin >> sin;
    while(sin.find('#') == string::npos){
        text.push_back(sin);
        cin >> sin;
    }
    isAnalyzed = false;//输入了新的文本 设置为没有被分析
}

void ArbitraryGrammar::inputGrammar(){
    //输入所有非终结符
    string s,ss;
    set<string>st;
    vector<Production>P;
    
    while(1){
        cout << "输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]" << endl;
        cout << "左边的非终结符:";
        cin >> s;
        if(s.find('#') != string::npos){
            cout << "*****结束文法输入*****" << endl;
            break;
        }
        if(s.find('@') != string::npos || s.find('_') != string::npos || s.find('$') != string::npos){
            cout << "*****输入不合法 不能含有 @ 下划线 $ *****" << endl;
            continue;
        }
        int pos;
        if(isNonTer(s)){
            pos = getNonTerPos(s);
        } else{
            int pos = nonTer.size();
            nonTer[s] = pos;
        }
        st.erase(s);//消除未使用的非终结符
        cout << "右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割！非终结符前加@):" << endl;
        vector<vector<string>>V;
        vector<string>v;
        bool flag = 0;
        while(1){
            cin >> ss;
            if(ss.find('#') != string::npos){
                if(v.empty()){
                    cout << "*****产生式为空,不计入*****" << endl;
                    flag = 2;
                    break;
                }
                cout << "*****结束右边的输入*****" << endl;
                V.push_back(v);
                v.clear();
                break;
            }
            if(ss.find('_') != string::npos){
                cout << "*****输入不合法 不能含有下划线*****" << endl;
                flag = 1;
                break;
            }
            if(ss.find('$') != string::npos){
                v.push_back("$");
                continue;
            }
            if(ss.find('@') != string::npos){
                if(ss[0] != '@'){
                    cout << "*****输入不合法 @不在字符串首*****" << endl;
                    flag = 1;
                    break;
                }
                if(ss.size() == 1){
                    cout << "*****输入不合法 @后面没有非终结符串*****" << endl;
                    flag = 1;
                    break;
                }
                for(int i=1;i<ss.size();i++)
                    if(ss[i] == '@'){
                        cout << "*****输入不合法 一个非终结符存在多个@ *****" << endl;
                        flag = 1;
                        break;
                    }
                string nt = ss.substr(1);
                if(!isNonTer(nt))st.insert(nt);//计入非终结符序列
                v.push_back(nt);
                continue;
            }
            if(ss == "|" && !v.empty()){
                V.push_back(v);
                v.clear();
                continue;
            }
            v.push_back(ss);
        }
        if(flag)continue;
        //成功输入一组文法
        Production pr = Production(s,V);
        for(auto vv : V){
            for(auto x : vv){
                if(!isNonTer(x) && x != "$"){
                    int ii = ter.size();
                    ter[x] = ii;
                }
            }
        }
        P.push_back(pr);
        cout << pr.toString() << endl;
    }

    displayGrammarHint("输入的文法如下");

    if(!st.empty()){
        cout << "存在终结符没有对应的产生式！--> ";
        for(auto x : st)cout << x << " ";
        cout << endl << "请重新输入文法！" << endl;
        nonTer.clear();
        ter.clear();
        prod.clear();
        inputGrammar();
    }

    //更新prod
    prod.swap(P);

}

void ArbitraryGrammar::run(){

    

    cout << "[郭坤 软工一班 20192758]" << endl;
    cout << "欢迎使用LL1文法分析器，输入1使用固定文法，否则自定义文法:";
    string sin;
    getline(cin,sin);
    if(sin == "1"){
        prod.push_back(Production("E",{{"T","G"}}));
        prod.push_back(Production("G",{{"+","T","G"},{"$"}}));
        prod.push_back(Production("T",{{"F","S"}}));
        prod.push_back(Production("S",{{"*","F","S"},{"$"}}));
        prod.push_back(Production("F",{{"(","E",")"},{"I"}}));


        ter["+"] = 0;
        ter["*"] = 1;
        ter["("] = 2;
        ter[")"] = 3;
        ter["I"] = 4;

        nonTer["E"] = 0;
        nonTer["G"] = 1;
        nonTer["T"] = 2;
        nonTer["S"] = 3;
        nonTer["F"] = 4;

        init();
        displayGrammarHint("固定文法");

    } else{
        inputGrammar();
        init();
        removeLeftRecursion();
    }

    load();
}

void ArbitraryGrammar::load(){

    isLoad = true;

    getAllFirst();
    getAllFollow();

    judgeLL1Grammar();

    getAllSelect();

    display();

    if(isLL1Grammar){
        getAnalyzTable();
        displayAnalyzedTable();

        while(true){
            inputText();
            getResultTable();
            displayResultTable();
            cout << endl << "是否继续分析一组文本? y|Y" << endl;
            string s;
            cin >> s;
            if(s[0] != 'y' && s[1] != 'Y')break;

        }

    }
}

void ArbitraryGrammar::display(){
    if(isLoad){
        cout << endl;
        cout << "First集" << endl;
        for(auto x : nonTer){
            cout << x.first << ":{ ";
            for(auto f : first[x.second]){
                cout << f << " ";
            }
            cout << "}" << endl;
        }

        cout << endl;
        cout << "Follow集" << endl;
        for(auto x : nonTer){
            cout << x.first << ":{ ";
            for(auto f : follow[x.second]){
                cout << f << " ";
            }
            cout << "}" << endl;
        }

        cout << endl;
        cout << "是否为LL1文法：" << ( isLL1Grammar ? "是" : "不是" ) << endl;

        cout << endl;
        cout << "Select集" << endl;
        for(auto x : nonTer){
            cout << x.first << ":{ ";
            for(auto f : select[x.second]){
                cout << f << " ";
            }
            cout << "}" << endl;
        }
    }


}

void ArbitraryGrammar::displayResultTable(){
    if(isLL1Grammar){

        if(!isAnalyzed)getResultTable();//如果没有分析 则进行分析

        //分析表结果表输出
        int w0 = 20,w1 = 30,w2 = 20;
        cout << endl;
        cout << setw(w0) << "分析栈" << setw(w1) << "剩余输入串" << setw(w2) << "推导式" << endl;
        for(int i = 0;i < resultTable[0].size();i++){
            cout << setw(w0) << resultTable[0][i] << setw(w1) << resultTable[1][i] << setw(w2) << resultTable[2][i] << endl;
        }
    } else{
        cout << "当前文法不合法LL(1)规范，不可以打印LL(1)结果分析表" << endl;
    }
}

void ArbitraryGrammar::displayGrammar(){
    for(auto & p : prod)cout << p.toString() << endl;
}

void ArbitraryGrammar::displayGrammarHint(string s){
    cout << "*****" << s << "*****" << endl;
    displayGrammar();
    cout << endl;
}

void ArbitraryGrammar::displayAnalyzedTable(){
    if(isLL1Grammar){
        int width = 10;
        cout << endl;
        cout << "预测分析表" << endl;

        //打印终结符
        cout << setw(width) << "";
        for(auto s : terAndEnd){
            cout << setw(width) << s.first;
        }

        cout << endl;
        //打印预测的产生式
        for(auto nt : nonTer){
            cout << setw(width) << nt.first;
            int pos = getNonTerPos(nt.first);
            for(auto t : terAndEnd){
                int i = table[nt.second][t.second];
                cout << setw(width) << getTableE(pos,i);
            }
            cout << endl;
        }
    }
}

void ArbitraryGrammar::judgeLL1Grammar(){
    //First与Follow都不相交的才属于LL1文法
    int len = nonTer.size();
    for(int i = 0;i < len;i++){
        set<string>tmp;
        set_intersection(first[i].begin(),first[i].end(),follow[i].begin(),follow[i].end(),inserter(tmp,tmp.begin()));
        if(!tmp.empty()){
            isLL1Grammar = false;
            return;
        }
    }
    isLL1Grammar = true;
}

void ArbitraryGrammar::getFirst(string x){
    bool flag = 0;  //记录非终结符的First集是否有空串 
    int tot = 0;    //记录一个非终结符产生式含有空串的产生式
    int pos = getNonTerPos(x);//该非终结符对应的下标
    

    for(auto v : prod[pos].right){
        //如果右部的第一个字符是终结符 
        if(isTer(v[0])){
            first[pos].insert(v[0]);
        }
        //如果是非终结符
        else{
            //从左到右遍历右部 
            for(int j = 0;j < v.size();j++){
                //如果遇到终结符，直接将该终结符放入first集 并结束
                if(isTer(v[j])){
                    first[pos].insert(v[j]);
                    break;
                }
                //遇到空串
                if(v[j][0] == '$'){
                    //是最后一个符号 则加入first中
                    if(j == v.size() - 1){
                        first[pos].insert("$");
                        break;
                    }
                    //不是最后一个符号 ---其实可以去除它！
                    continue;
                }
                //不是终结符，求该非终结符的First集
                getFirst(v[j]);
                for(string it : first[getNonTerPos(v[j])]){
                    if(it[0] == '$'){//查看是否有空串在该非终结符的first中
                        flag = 1;
                    } else{//将该非终结符的first的非空串元素添加到first集中
                        first[pos].insert(it);
                    }
                }
                //没有空串就不必再找下去了 
                if(flag == 0)break;
                else{//有空串 则继续循环
                    flag = 0;//更新状态
                    tot++;
                }
            }
            //如果右部所有符号的First集都有空串] = 则符号x的First集也有空串 
            if(tot == v.size()){
                first[pos].insert("$");
            }
        }
    }
    
    
}

void ArbitraryGrammar::getAllFirst(){
    //getFirst
    for(auto i : nonTer)getFirst(i.first);
}

void ArbitraryGrammar::getAllFollow(){
    //起始非终结符的follow放入#
    follow[0].insert("#");
    //getFollow
    for(auto i : nonTer)getFollow(i.first);
}

void ArbitraryGrammar::getFollow(string x){
    int pos = getNonTerPos(x);


    //找到非终结符x出现的位置
    for(int i = 0;i < prod.size();i++){
        for(auto v : prod[i].right){
            int index = -1;
            int len = v.size();
            for(int j = 0;j < len;j++){
                if(v[j] == x){
                    index = j;
                    break;
                }
            }
            if(index == -1)continue;//没有包含x结束本次循环
            //如果找到了x] = 并且它不是最后一个字符 
            if(index < len - 1){
                //如果下一个字符是终结符，添加进x的Follow集 
                string next = v[index + 1];
                if(isTer(next))follow[pos].insert(next);
                else{
                //如果下一个字符是非终结符 
                    bool flag = 0;
                    //遍历下一个字符的First集
                    for(string it : first[getNonTerPos(next)]){
                        if(it[0] == '$')flag = 1;
                        else follow[pos].insert(it);
                    }
                    //如果有空串并且左部不是它本身(防止陷入死循环)] = 当前非终结符的Follow集是x的Follow集
                    string l = prod[i].left;
                    if(flag && l != x){
                        getFollow(l);
                        for(string it : follow[getNonTerPos(l)]){
                            follow[pos].insert(it);
                        }
                    }
                }
            } else if(index == len - 1 && x != prod[i].left){
                //如果x在产生式的末尾，则产生式左部的Follow集应该添加到x的Follow集里 
                string l = prod[i].left;
                getFollow(l);
                for(string it : follow[getNonTerPos(l)]){
                    follow[pos].insert(it);
                }
            }
        }
    }
}


void ArbitraryGrammar::getAllSelect(){
    //Slect集 = First集(除去ε) [+ Follow集(如果First集存在ε)]
    for(auto m : nonTer){
        string x = m.first;
        int pos = m.second;
        if(first[pos].find("$") != first[pos].end()){
            //First存在空串 
            set_union(first[pos].begin(),first[pos].end(),follow[pos].begin(),follow[pos].end(),inserter(select[pos],select[pos].begin()));
            //取出select中的空串 $
            select[pos].erase("$");
        } else{//不存在空串
            for(auto s : first[pos])select[pos].insert(s);
        }
    }
}

void ArbitraryGrammar::getAnalyzTable(){
    
    for(int i = 0;i < prod.size();i++){
        for(int j = 0;j < prod[i].right.size();j++){
            string tmp = prod[i].right[j][0];
            int pos = getNonTerPos(prod[i].left);
            //如果产生式右部的第一个字符串是终结符
            if(isTer(tmp) || tmp[0] == '$'){
                //该终结符是空串，遍历左部的follow集，更新table
                if(tmp[0] == '$'){
                    for(auto f : follow[pos])table[pos][getTerPos(f)] = j;
                } else{//该终结符不是空串，更新table
                    table[pos][getTerPos(tmp)] = j;
                }
            } else{
                //如果产生式右部的第一个字符是非终结符，遍历它的First集，更新table
                int tmpPos = getNonTerPos(tmp);
                for(auto f : first[tmpPos]){//添加 除空串$ 以外的所有元素
                    if(f[0] != '$')table[pos][getTerPos(f)] = j;
                }
                //如果有空串，遍历左部的follow集，更新table  
                if(first[tmpPos].find("$") != first[tmpPos].end()){
                    for(auto f : follow[pos])table[pos][getTerPos(f)] = j;
                }
            }
        }
    }
}

string ArbitraryGrammar::getTableE(int prodPos,int rightPos){
    if(rightPos == -1)return "@empty";
    //if(1 == -2)return "@synch";
    return prod[prodPos].getRightString(rightPos);
}

void ArbitraryGrammar::getResultTable(){
    if(isAnalyzed)return;//分析过就不需要再分析了

    isAnalyzed = true;

    auto rs = &resultTable;
    //重置结果表
    vector<vector<string>>().swap(*rs);
    rs->resize(3);
    list<string>a,b;//a-->分析栈 b->剩余输出串栈
    auto A = &rs->at(0),B = &rs->at(1),C = &rs->at(2);
    //把开始符和#push进分析栈
    a.push_back(Start);
    a.push_back("#");
    //把整个串push进剩余符号vector
    for(auto i : text)b.push_back(i);
    b.push_back("#");
    //如果剩余输入串长度不为0，就一直循环
    while(b.size() > 0){
        //输出分析栈内容
        A->push_back(getListString(a));
        //输出剩余输入串内容
        B->push_back(getListString(b));
        
        //获取分析栈首元素与剩余输入串首元素
        string sa = a.front(),sb = b.front();
        int pa;

        if(sa == sb){
            if(sa == "#"){//如果可以匹配，并且都为# 
                C->push_back("@Accept!");//输入串符合文法！
                return;
            } else{//如果可以匹配，并且都为终结符 
                a.pop_front();
                b.pop_front();
                C->push_back(sb + " 匹配");
            }
        }else if(isNonTer(sa)&& isTer(sb) &&table[pa = getNonTerPos(sa)][getTerPos(sb)] > -1){
            //如果在预测分析表中有值
            int index = table[pa][getTerPos(sb)];
            a.pop_front();
            if(getTableE(pa,index) != "$"){
                //E#->TG# 倒叙插入
                for(int i = prod[pa].right[index].size() - 1;i >= 0;i--){
                    a.push_front(prod[pa].right[index][i]);
                }
                C->push_back(prod[pa].left + "->" + getVectorString(prod[pa].right[index]));
            } else{//空串出栈
                C->push_back(sa + " 空串出栈");
            }
        } else{
            C->push_back("@Error!");
            return;
        }
    }
}

string ArbitraryGrammar::getVectorString(vector<string> v){
    string tmp = "";
    for(auto i : v)tmp += i;
    return tmp;
}

string ArbitraryGrammar::getListString(list<string> li){
    string tmp = "";
    for(auto i : li)tmp += i;
    return tmp;
}

//消除间接左递归
void ArbitraryGrammar::removeIndirect(int pa,int len){



    for(int pb = pa; pb < len; pb++){
             //相互循环遍历 一层层的消除间接左递归
        bool flag = false;
        vector<vector<string>> tmp;
        vector<vector<string>> & Ar = prod[pa].right;//检查的产生式右边Ar
        vector<vector<string>> & Br = prod[pb].right;//搜寻的产生式右边Br
        string Bl = prod[pb].left;//搜寻的产生式 左边
        //A->Bc B->Cd => A->Cdc
        for(auto & a : Ar)
            if(a[0] == Bl){//Ar中发现有以Bl开头的式子 
                //将B中非终结符式子Cd筛选出来
                for(auto & b : Br)
                    if(b[0]!=Bl&&b[0]!="$")
                        tmp.push_back(b);
                //找到Bl开头元素
                flag = true;
                break;
            }
        if(flag){
            //使用n--反向读取方式 避免因为删除导致的数组下标错误
            int n = Ar.size();
            while(n--){
                if(Ar[n][0] == Bl){//Ar中发现有以Bl开头的式子 
                    //取出tmp中的元素Cd加上a中的c 然后放入Ar中  Cdc
                    for(auto t : tmp){
                        int nn = Ar[n].size();
                        for(int k = 1;k < nn;k++)
                            t.push_back(Ar[n][k]);
                        //放入Ar中 A->CDc
                        Ar.push_back(t);
                    }
                    //删除A->Bc项
                    Ar.erase(Ar.begin() + n);
                }
            }
        }
    }
}

void ArbitraryGrammar::removeAllDirectly(){
    //固定了原本产生式数量 即使后续增加不会改变 因此之后遍历原有的产生式
    int len = prod.size();
    for(int i = 0;i < len;i++)removeDirectly(i);

    //扩容
    len = prod.size();//获取扩容后的大小
    resize(len);


    displayGrammarHint("消除直接左递归");
}

void ArbitraryGrammar::removeAllIndirect(){
    int len = prod.size();
    for(int i = 0;i < len;i++)removeIndirect(i,len);

    displayGrammarHint("消除间接左递归");
}

void ArbitraryGrammar::removeLeftRecursion(){
    //先消除所有间接左递归 再消除所有 直接左递归
    removeAllIndirect();
    removeAllDirectly();
    simplify();
}

void ArbitraryGrammar::resize(int len){
    first.resize(len);
    follow.resize(len);
    select.resize(len);
    table.resize(len);
    for(auto & i : table){
        i.resize(terAndEnd.size());
        for(auto & x : i)x = -1;//设置为-1 empty
    }
}

//消除直接左递归 
void ArbitraryGrammar::removeDirectly(int pos){
    string l = prod[pos].left;//获取左边
    //遍历看看有没有左递归元素
    bool isLeftRecursion = false;
    for(auto & i : prod[pos].right){
        if(i[0] == l){
            isLeftRecursion = true;
            break;
        }
    }
        
    if(!isLeftRecursion)return;

    //创建A_并放入prod中
    string l_ = l + '_';
    auto A_ = Production(l_);

    //nonTer 添加A_
    nonTer[l_] = prod.size();

    prod.push_back(A_);

    //----这里不知道为什么 不能放在前面声明r（会导致到下面循环时 r变空 只能放在这里了）
    auto & r_ = prod[prod.size() - 1].right;
    //添加空串到A_中
    r_.push_back({"$"});
    auto &r = prod[pos].right;

    //遍历A右边 寻找递归左元素
    for(int x = 0;x < r.size();x++){
        if(r[x][0] == "$")continue;//跳过空串
        if(r[x][0] == l){//A->Ab => A_->bA_
            vector<string>v;
            for(int i = 1;i < r[x].size();i++)
                v.push_back(r[x][i]);//b
            v.push_back(l_);//bA_
            r_.push_back(v);//添加A_->nA_
            r.erase(r.begin()+x);//删掉A->Ab
            x--;//回退一格
        } else{//A->c => A->cA_
            r[x].push_back(l_);//cA_
        }
    }
}


void ArbitraryGrammar::dfs(int x){
    if(used[x]) return;
    used[x] = 1;
    for(vector<string> &v : prod[x].right)
        for(string &s:v)
            if(isNonTer(s))
                dfs(getNonTerPos(s));
}

//化简 没有使用的文法扔掉
void ArbitraryGrammar::simplify(){
    //还没做好
    vector<bool>().swap(used);
    used.resize(prod.size());
    
    dfs(0);

    vector<Production> res;
    for(int i = 0; i < prod.size(); i++)
        if(used[i])
            res.push_back(prod[i]);

    prod.swap(res);

    resize(prod.size());

    nonTer.clear();
    for(int p = 0;p < prod.size();p++)
        nonTer[prod[p].left] = p;


    displayGrammarHint("删除不可达的文法");
}

主函数 main.cpp

#include <iostream>
#include <cmath>
#include "ArbitraryGrammar.h"
using namespace std;

int main(){
	
	ArbitraryGrammar ag = ArbitraryGrammar();
	ag.run();

}