【编译原理】LALR(1)语法分析方法（c++实现）

前文回顾

【编译原理】LR(0)分析方法（c++实现）
【编译原理】SLR(1)分析方法（c++实现）
【编译原理】LR(1)分析方法（c++实现）

这几个程序的代码大部分是一样的，根据不同算法特点做了部分修改而已
 

代码

LALR(1)的代码就是在LR(1)的基础上合并了同心项

Item类

在LR(1)基础上搜索符由string改成了vector<string>

#include <iostream>
#include <fstream>
#include <string.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <utility>
#include <iomanip>
using namespace std;

//返回s的第一个词
string firstWord(string s)
{
    s+=" ";
    string first=s.substr(0,s.find(" "));
    return first;
}

//将字符串划分为一个个词
vector<string> split(string s,string separator)
{
    vector<string>v;

    string::size_type pos1, pos2;
    pos2 = s.find(separator);
    pos1 = 0;

    while(string::npos != pos2)
    {
        v.push_back(s.substr(pos1, pos2-pos1));

        pos1 = pos2 + separator.size();
        pos2 = s.find(separator, pos1);
    }
    if(pos1 != s.length())
        v.push_back(s.substr(pos1));

    return v;
}

class Item
{
private:
    string item;//项目
    string left;//项目左部
    string right;//项目右部
    vector<string> symbol;//向前搜索符号
    static int count;

public:
    int id;

    //参数是产生式
    Item(string i)
    {
        id=count++;
        left=i.substr(0,i.find("->"));
        right=i.substr(i.find("->")+2);
        item=left+"->"+right;
        symbol.push_back("$");//初始向前搜索符为"$"

        if(right.find(".")==string::npos)
            addDot(0);
    }

    //参数是左部和右部
    Item(string l,string r)
    {
        id=count++;
        left=l;
        right=r;
        symbol.push_back("$");
        item=left+"->"+right;

        if(right.find(".")==string::npos)
            addDot(0);
    }

    //参数是左部和右部和向前搜索符号
    Item(string l,string r,string s)
    {
        id=count++;
        left=l;
        right=r;
        symbol.push_back(s);
        item=left+"->"+right;

        if(right.find(".")==string::npos)
            addDot(0);
    }

    string getLeft()
    {
        return left;
    }

    string getRight()
    {
        return right;
    }

    string getItem()
    {
        item=left+"->"+right;
        return item;
    }

    vector<string> getSymbol()
    {
        return symbol;
    }

    //找点的位置
    int getDot(string item)
    {
        return item.find(".");
    }
    //设置向前搜索符号
    //Insert为1，则插入搜索符，为0，则重置搜索符
    void setSymbol(int Insert,string new_symbol)
    {
        if(Insert&&find(symbol.begin(),symbol.end(),new_symbol)==symbol.end())
            symbol.push_back(new_symbol);
        else
        {
            symbol.clear();
            symbol.push_back(new_symbol);
        }
        sort(symbol.begin(), symbol.end());
    }
    //给文法加点
    void addDot(int pos)
    {
        if(right[pos]=='@')
            right=".";
        else if(pos==0)
            right.insert(pos,". ");
        else if(pos==right.size())
            right.insert(pos," .");
        else
            right.insert(pos," . ");
    }

    //判断一个项目进度是否到结尾
    int hasNextDot()
    {
        vector<string>buffer=split(right,".");
        if(buffer.size()>1)
            return 1;
        else
            return 0;
    }

    //得到"."后面的一个文法符号
    string getPath()
    {
        vector<string>buffer=split(item,".");
        buffer[1].erase(0,1);
        string first=firstWord(buffer[1]);
        return first;
    }

    //返回下一个点的串
    string nextDot()
    {
        int dotPos=right.find(".");
        vector<string>buffer=split(item,".");
        buffer[1].erase(0,1);
        string first=firstWord(buffer[1]);
        int nextPos=dotPos+first.size();
        right.erase(right.find("."),2);
        right.insert(nextPos," .");
        return right;
    }

    bool operator ==(Item &x)
    {
        return getItem()==x.getItem();
    }

};
int Item::count=0;

LALR(1)语法分析过程

#include <iostream>
#include <fstream>
#include <string.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <iomanip>
#include "Item.h"

using namespace std;

//DFA的边
struct GOTO
{
    int from;
    int to;
    string path;

    GOTO(int s,string p,int t)
    {
        from=s;
        path=p;
        to=t;
    }
};

//DFA中状态
struct State
{
    int id;//状态编号
    set<Item>items;//项目集
};

/*一些操作符的重载*/
bool operator <(const State &x,const State &y)
{

    return x.id<y.id;
}

bool operator ==(const State &x,const State &y)
{

    return x.id==y.id;
}
bool operator <(const GOTO &x,const GOTO &y)
{
    if(x.from<y.from)
        return true;
    if(x.from==y.from && x.path<y.path)
        return true;
    if(x.from==y.from && x.path==y.path && x.to<y.to)
        return true;
}
bool operator <(Item x,Item y)
{

    return x.getItem()<y.getItem();
}

bool operator ==(const GOTO &x,const GOTO &y)
{
    return x.from==y.from && x.path==y.path && x.to==y.to;
}
//两个项目集相等
bool operator ==(const set<Item> &x,const set<Item> &y)
{
    auto it1=x.begin();
    auto it2=y.begin();

    for(; it1!=x.end(),it2!=y.end(); it1++,it2++)
    {
        Item a=*it1;
        Item b=*it2;
        if(a==b&&a.getSymbol()==b.getSymbol())
            continue;

        //有一个项目不相等，两项目集一定不相等
        else
            return false;
    }
    return true;
}

class LR1
{
private:
    int number=0;
    vector<string>T;//终结符号集合
    vector<string>NT;//非终结符号集合
    string S;//开始符号
    map<string,vector<string>>production;//产生式
    map<string,int>numPro;//编号的产生式集合，用于规约
    vector<State>States;//状态集合
    vector<GOTO>GO;//转换函数
    map<string,set<string>>FIRST;//FIRST集
    map<string,set<string>>FOLLOW;//FOLLOW集
    map<pair<int,string>,string>actionTable;//action表
    map<pair<int,string>,int>gotoTable;//goto表

    //读取文法规则
    void readGrammar(string fileName)
    {
        ifstream input(fileName);
        if(!input)
        {
            cout<<fileName<<" Failed"<<endl;
        }

        //读取文法规则
        string line;//读入的每一行
        while(getline(input,line))
        {
            int i;

            //读取左部
            string left="";
            for(i=0; line[i]!='-'&&i<line.size(); i++)
            {
                left+=line[i];
            }

            NT.push_back(left);//左部加入非终结符号集

            //读取右部
            string right=line.substr(i+2,line.size()-i);//获取产生式右部
            addP(left,right);//添加产生式
        }
        addT();//添加终极符
        S=*NT.begin();
        input.close();
    }

    //填产生式
    void addP(string left,string right)
    {
        right+="#";//'#'作为每句文法结尾标志
        string pRight="";
        for(int i=0; i<right.size(); i++)
        {
            if(right[i]=='|'||right[i]=='#')
            {
                production[left].push_back(pRight);
                pRight="";
            }
            else
            {
                pRight+=right[i];
            }
        }
    }

    //带标号的产生式集
    void addNumP()
    {
        int i=0;
        for(string left:NT)
        {
            for(string right:production[left])
            {
                numPro[left+"->"+right]=i;
                i++;
            }
        }
    }

    //填终结符
    void addT()
    {
        string temp="";
        for(string left:NT)
        {
            for(string right:production[left])
            {
                right+="#";
                for(int i=0; i<right.size(); i++)
                {
                    if(right[i]=='|'||right[i]==' '||right[i]=='#')
                    {
                        //不是非终结，且不是空，则加入终结符号
                        if((find(NT.begin(),NT.end(),temp)==NT.end())&&temp!="@")
                        {
                            T.push_back(temp);
                        }
                        temp="";
                    }
                    else
                    {
                        temp+=right[i];
                    }
                }
            }
        }//end left

        //终结符去重
        sort(T.begin(),T.end());
        T.erase(unique(T.begin(), T.end()), T.end());
    }
    //判断是否是非终极符号
    bool isNT(string token)
    {
        if(find(NT.begin(),NT.end(),token)!=NT.end())
            return true;
        return false;
    }
    //判断temp在不在集合c中
    bool isIn(Item temp,set<Item>c)
    {
        for(Item i:c)
        {
            if(i.getItem()==temp.getItem()&&i.getSymbol()==temp.getSymbol())
                return true;
        }
        return false;
    }
    //判断是否应该规约
    string tableReduce(int num)
    {
        for(State s:States)
        {
            //目标状态
            if(s.id==num)
            {
                //遍历项目集
                for(Item i:s.items)
                {
                    //还有下一个点，肯定不是规约项目
                    if(i.hasNextDot())
                        return "";
                    //是规约项目
                    else
                        return i.getLeft();//返回左部NT
                }
            }
        }
        return "";
    }

    //找到item规约到的产生式，返回其编号
    int findReduce(int num)
    {
        for(State s:States)
        {
            if(s.id==num)
            {
                for(Item i:s.items)
                {
                    string temp=i.getItem();
                    temp.erase(temp.find("."));
                    temp.pop_back();
                    return numPro.find(temp)->second;
                }
            }
        }
        return -1;
    }
    //根据项目找规约的产生式编号
    int findReduce(Item item)
    {
        string temp=item.getItem();
        temp.erase(temp.find("."));
        temp.pop_back();
        if(numPro.find(temp)!=numPro.end())
            return numPro.find(temp)->second;
        return -1;
    }
    //找到产生式序号为pro的产生式右部数量
    int rightCount(string &left,int pro)
    {
        for(auto it=numPro.begin(); it!=numPro.end(); it++)
        {
            if(it->second==pro)
            {
                cout<<it->first<<endl;
                string target=it->first;
                left=target.substr(0,target.find("->"));
                string right=target.substr(target.find("->")+2);
                vector<string>temp=split(right," ");
                return temp.size();
            }
        }
        return 0;
    }
    //合并同心项
    bool _merge(State &s1,State s2)
    {
        auto it1=s1.items.begin();
        auto it2=s2.items.begin();

        for(; it1!=s1.items.end(),it2!=s2.items.end(); it1++,it2++)
        {
            Item &item1=const_cast<Item&>(*s1.items.find(*it1));
            Item temp=*it2;
            item1.setSymbol(1,temp.getSymbol()[0]);
        }

        //检查是否有规约-规约冲突
        for(Item i1:s1.items)
        {
            for(Item i2:s1.items)
            {
                //同一个状态中的两个规约项目具有相同搜索符，则判断为冲突
                if(!i1.hasNextDot()&&!i2.hasNextDot()&&i1.getItem()<i2.getItem())
                {
                    if(i1.getSymbol()==i2.getSymbol())
                        return false;
                }
            }
        }
        return true;
    }

    //判断状态xy是否是同心项
    bool sameCore(State x,State y)
    {
        if(x.items.size()!=y.items.size())
            return false;

        set<Item>temp;

        //取交集，结果放在temp里
        set_intersection(x.items.begin(),x.items.end(),y.items.begin(),y.items.end(),inserter(temp,temp.begin()));

        if(temp.size()==x.items.size())
            return true;
        else
            return false;
    }
    //删除一个状态
    void delete_State(int erase_id,int new_id)
    {
        //重复状态后面的所有状态序号-1
        for(int i=0; i<States.size(); i++)
        {
            if(States[i].id>erase_id)
            {
                States[i].id--;
            }
        }
        //状态转移函数
        for(int i=0; i<GO.size(); i++)
        {
            if(GO[i].from==erase_id||GO[i].to==erase_id)
            {
                //删除这一状态的goto
                if(new_id==-1)
                    GO.erase(find(GO.begin(),GO.end(),GO[i]));
                //更改这一状态的goto
                else
                {
                    if(GO[i].from==erase_id)
                        GO[i].from=new_id;
                    if(GO[i].to==erase_id)
                        GO[i].to=new_id;
                }
            }
            if(GO[i].from>erase_id)
                GO[i].from--;
            if(GO[i].to>erase_id)
                GO[i].to--;
        }
        // printGO();
    }
public:
    //构造函数，读入所需的四元组
    LR1(string fileName)
    {
        readGrammar(fileName);
        Extension();//拓广文法
    }

    //拓广文法
    void Extension()
    {
        string newS=S;
        newS+="'";
        NT.insert(NT.begin(),newS);
        production[newS].push_back(S);
        S=newS;
    }

    //状态集是否已经包含该状态
    int hasState(set<Item>J)
    {
        for(State s:States)
        {
            if(s.items.size()!=J.size())
                continue;

            if(s.items==J)
                return s.id;
            else
                continue;

        }
        return -1;
    }
    //获得FIRST集合
    void getFirst()
    {
        FIRST.clear();

        //终结符号或@
        FIRST["@"].insert("@");
        for(string X:T)
        {
            FIRST[X].insert(X);
        }

        //非终结符号
        int j=0;
        while(j<4)
        {
            for(int i=0; i<NT.size(); i++)
            {
                string A=NT[i];

                //遍历A的每个产生式
                for(int k=0; k<production[A].size(); k++)
                {
                    int Continue=1;//是否添加@
                    string right=production[A][k];

                    //X是每条产生式第一个token
                    string X;
                    if(right.find(" ")==string::npos)
                        X=right;
                    else
                        X=right.substr(0,right.find(" "));
                    //cout<<A<<"\t"<<X<<endl;

                    //FIRST[A]=FIRST[X][e-mail]
                    if(!FIRST[X].empty())
                    {
                        for(string firstX:FIRST[X])
                        {
                            if(firstX=="@")
                                continue;
                            else
                            {
                                FIRST[A].insert(firstX);
                                Continue=0;
                            }
                        }
                        if(Continue)
                            FIRST[A].insert("@");
                    }
                }

            }
            j++;
        }
    }

    //获得FOLLOW集合
    void getFollow()
    {
        getFirst();

        //将界符加入开始符号的follow集
        FOLLOW[S].insert("$");

        int j=0;
        while(j<4)
        {
            //遍历非终结符号
            for(string A:NT)
            {
                for(string right:production[A])
                {
                    for(string B:NT)
                    {
                        //A->Bb
                        if(right.find(B)!=string::npos)
                        {
                            /*找B后的字符b*/
                            string b;
                            int flag=0;
                            //识别到E'
                            if(right[right.find(B)+B.size()]!=' '&&right[right.find(B)+B.size()]!='\0')
                            {
                                string s=right.substr(right.find(B));//E'b
                                string temp=right.substr(right.find(B)+B.size());//' b

                                //A->E'
                                if(temp.find(" ")==string::npos)
                                {
                                    B=s;//B:E->E'
                                    FOLLOW[B].insert(FOLLOW[A].begin(),FOLLOW[A].end());//左部的FOLLOW赋给B
                                    flag=1;
                                }
                                //A->E'b
                                else
                                {
                                    B=s.substr(0,s.find(" "));
                                    temp=temp.substr(temp.find(" ")+1);//b

                                    //b后无字符
                                    if(temp.find(" ")==string::npos)
                                        b=temp;
                                    //b后有字符
                                    else
                                        b=temp.substr(0,temp.find(" "));
                                }
                            }

                            //A->aEb
                            else if(right[right.find(B)+B.size()]==' ')
                            {
                                string temp=right.substr(right.find(B)+B.size()+1);//B后的子串

                                //b后无字符
                                if(temp.find(" ")==string::npos)
                                    b=temp;
                                //b后有字符
                                else
                                    b=temp.substr(0,temp.find(" "));
                            }
                            //A->aE
                            else
                            {
                                FOLLOW[B].insert(FOLLOW[A].begin(),FOLLOW[A].end());
                                flag=1;
                            }

                            //FOLLOW[B]还没求到
                            if(flag==0)
                            {
                                //FIRST[b]中不包含@
                                if(FIRST[b].find("@")==FIRST[b].end())
                                {
                                    FOLLOW[B].insert(FIRST[b].begin(),FIRST[b].end());
                                }
                                else
                                {
                                    for(string follow:FIRST[b])
                                    {
                                        if(follow=="@")
                                            continue;
                                        else
                                            FOLLOW[B].insert(follow);
                                    }
                                    FOLLOW[B].insert(FOLLOW[A].begin(),FOLLOW[A].end());
                                }
                            }
                        }
                    }
                }
            }
            j++;
        }
        //printFIRST();
        printFOLLOW();
    }

    //项目闭包
    set<Item> closure(Item item)
    {
        set<Item>C;//项目闭包
        C.insert(item);

        queue<Item>bfs;//bfs求所有闭包项
        bfs.push(item);

        while(!bfs.empty())
        {
            Item now=bfs.front();
            bfs.pop();

            vector<string>buffer=split(now.getRight(),".");

            if(buffer.size()>1)
            {
                string first=firstWord(buffer[1].erase(0,1));

                set<string>fst;
                vector<string>candidate=split(now.getRight(),first);
                //如果first后面有符号，则first后面符号的FIRST作为新的向前搜索符号
                if(candidate.size()>1)
                {
                    candidate[1].erase(0,1);
                    for(string f:FIRST[firstWord(candidate[1])])
                        fst.insert(f);
                }
                //如果first后面没有符号，则向前搜索符号为新的向前搜索符号
                else
                    fst.insert(now.getSymbol()[0]);

                if(isNT(first))//如果"."后面第一个字符是NT
                {
                    for(auto it2=production[first].begin(); it2!=production[first].end(); it2++)
                    {
                        Item temp(first,*it2);

                        if(!isIn(temp,C))
                        {
                            for(string f:fst)
                            {
                                temp.setSymbol(0,f);
                                C.insert(temp);
                                bfs.push(temp);
                            }
                        }
                    }
                }
            }
        }
        return C;
    }

    //构造DFA
    void dfa()
    {
        State s0;//初始项目集
        s0.id=number++;//状态序号

        //初始项目集
        string firstRight=*(production[S].begin());
        Item start(S,firstRight);
        s0.items=closure(start);//加到状态中
        States.push_back(s0);

        //构建DFA
        State temp;
        for(int k=0; k<States.size(); k++)
        {
            State s=States[k];
            map<string,int>Paths;//路径
            for(Item now:s.items)
            {
                now.getItem();
                if(now.hasNextDot())
                {
                    string path=now.getPath();//path
                    Item nextD(now.getLeft(),now.nextDot(),now.getSymbol()[0]);//新状态核心项，向前搜索符继承
                    set<Item>next=closure(nextD);//to

                    //该状态已经有这条路径了，则将新产生的闭包添加到原有目的状态中
                    int oldDes;
                    if(Paths.find(path)!=Paths.end())
                    {
                        oldDes=Paths.find(path)->second;

                        for(int j=0; j<States.size(); j++)
                        {
                            if(States[j].id==oldDes)
                            {
                                States[j].items.insert(next.begin(),next.end());
                                next=States[j].items;

                                int tID=hasState(next);
                                if(tID!=-1)
                                {
                                    //temp=dest;
                                    for(int i=0; i<GO.size(); i++)
                                    {
                                        if(GO[i].to==oldDes)
                                        {
                                            GO[i].to=tID;
                                        }
                                    }
                                }
                            }
                        }
                    }

                    //如果该目的状态在状态集里没有出现过，就加入状态集
                    int tID=hasState(next);
                    if(tID==-1)
                    {
                        State t;
                        t.id=number++;
                        t.items=next;
                        States.push_back(t);
                        Paths.insert(pair<string,int>(path,t.id));
                        GO.push_back(GOTO(s.id,path,t.id));
                    }
                    //该目的状态已经在状态集中了
                    else
                    {
                        Paths.insert(pair<string,int>(path,tID));
                        GO.push_back(GOTO(s.id,path,tID));
                    }
                }
            }
        }
        //删除重复GOTO
        sort(GO.begin(),GO.end());
        GO.erase(unique(GO.begin(), GO.end()), GO.end());

        //处理重复状态
        for(int i=0; i<States.size(); i++)
        {
            State s1=States[i];
            for(int j=0; j<States.size(); j++)
            {
                State s2=States[j];
                //发现重复状态集
                if(s2.id>s1.id&&s1.items==s2.items)
                {
                    int erase_id=s2.id;
                    States.erase(States.begin()+j);
                    delete_State(erase_id,-1);
                }
            }
        }
    }

    //合并同心项,成功返回1，失败返回0
    int Merge()
    {
        for(int i=0; i<States.size(); i++)
        {
            State s1=States[i];
            for(int j=0; j<States.size(); j++)
            {
                State s2=States[j];
                //cout<<s1.id<<s2.id<<"\t"<<sameCore(s1,s2)<<endl;
                if(s2.id>s1.id&&sameCore(s1,s2))//是同心项
                {
                    //合并状态
                    if(_merge(States[i],s2))
                    {
                        int erase_id=s2.id;
                        States.erase(States.begin()+j);
                        delete_State(erase_id,s1.id);
                    }
                    else
                        return 0;
                }
            }
        }
        //删除重复GOTO
        sort(GO.begin(),GO.end());
        GO.erase(unique(GO.begin(), GO.end()), GO.end());
        printS();
        printGO();
        return 1;
    }
    //构造LR(1)分析表
    void getTable()
    {
        addNumP();
        string s=S;
        s=s.erase(s.find("'"));

        pair<int,string>title(1,"$");
        actionTable[title]="acc";

        for(GOTO go:GO)
        {
            //目的地是NT
            if(isNT(go.path))
            {
                pair<int,string>title(go.from,go.path);
                gotoTable[title]=go.to;

            }
            //加入action表
            else
            {
                //shift
                pair<int,string>title(go.from,go.path);
                actionTable[title]="s"+to_string(go.to);
            }
            //reduce，行为状态号，列为向前搜索符
            string rNT=tableReduce(go.to);
            if(rNT!="")
            {
                if(go.path!=s)
                {
                    //找该状态的项目集
                    State temp;
                    temp.id=go.to;
                    temp=*(find(States.begin(),States.end(),temp));
                    set<Item>itm(temp.items.begin(),temp.items.end());
                    //向前搜索符下的规约项规约到对应产生式
                    for(Item i:itm)
                    {
                        vector<string>symbols(i.getSymbol());
                        for(string ss:symbols)
                        {
                            pair<int,string>title(go.to,ss);
                            int nReduce=findReduce(i);
                            if(nReduce!=-1)
                                actionTable[title]="r"+to_string(nReduce);
                            else
                                actionTable[title]="error";
                        }
                    }
                }
            }
        }
        //printTable();
    }
    //语法分析过程
    int parsing(string input)
    {
        stack<string>Analysis;
        input+=" $";

        //0状态入栈
        Analysis.push("$");
        Analysis.push("0");

        vector<string>w=split(input," ");//将输入串分成一个个词
        int ip=0;//输入串的指针

        while(true)
        {
            pair<int,string>title(stoi(Analysis.top()),w[ip]);//stoi函数用于string to int
            string res=actionTable[title];
            cout<<"栈顶：s"<<setw(10)<<Analysis.top()<<"当前输入字符："<<setw(8)<<w[ip];

            //shift
            if(res[0]=='s')
            {
                cout<<"动作：shift"<<endl;
                int state=stoi(res.substr(1));
                Analysis.push(w[ip]);
                Analysis.push(to_string(state));
                ip++;
            }
            //reduce
            else if(res[0]=='r')
            {
                cout<<"动作：reduce ";
                int pro=stoi(res.substr(1));
                string left;//产生式左部
                int b=2*rightCount(left,pro);//2倍的产生式右部符号数量

                while(b>0)
                {
                    Analysis.pop();
                    b--;
                }

                int s1=stoi(Analysis.top());
                Analysis.push(left);

                pair<int,string>t(s1,left);
                Analysis.push(to_string(gotoTable[t]));
            }
            else if(res[0]=='a')
            {
                cout<<"动作：接受"<<endl;
                return 1;
            }

            else
            {
                cout<<"文法错误"<<endl;
                return 0;
            }
        }
    }

    void parser(string fileName)
    {
        ifstream input(fileName);
        if(!input)
        {
            cout<<fileName<<" Failed"<<endl;
            return;
        }

        getFollow();
        dfa();
        if(!Merge())
        {
            cout<<endl<<"**************该文法不是LALR文法**************"<<endl;
            return;
        }
        cout<<endl<<"************该文法是LALR文法************"<<endl<<endl;
        getTable();

        //读取token
        char c;
        string program="";
        int line=1;
        cout<<"源程序的token序列为"<<endl;
        cout<<line<<"  ";
        while((c=input.get())!=EOF)
        {
            cout<<c;
            if(c=='\n')
            {
                cout<<++line<<"  ";
                program+=" ";
            }
            else
                program+=c;
        }
        cout<<endl;


        cout<<"分析结果："<<endl;

        if(parsing(program))
            cout<<endl<<"*********************输入串属于该文法*********************"<<endl;
        else
            cout<<endl<<"********************输入串不属于该文法********************"<<endl;;

    }
    /*=====================打印===========================*/
    //打印NT和T
    void printV()
    {
        cout<<"非终结符号集合："<<endl;
        for(int i=0; i<NT.size(); i++)
        {
            cout<<NT[i]<<" ";
        }
        cout<<endl;
        cout<<"终结符号集合："<<endl;
        for(int i=0; i<T.size(); i++)
        {
            cout<<T[i]<<" ";
        }
        cout<<endl;
    }

    //打印FIRST集
    void printFIRST()
    {
        cout<<"FIRST集合为"<<endl;
        cout.setf(ios::left);
        for(string non_terminal:NT)
        {
            cout<<setw(20)<<non_terminal;
            for(string first:FIRST[non_terminal])
                cout<<first<<" ";
            cout<<endl;
        }
        cout<<endl;
    }

    //打印FOLLOW集
    void printFOLLOW()
    {
        cout<<"FOLLOW集合为"<<endl;
        cout.setf(ios::left);
        for(string non_terminal:NT)
        {
            cout<<setw(20)<<non_terminal;
            for(string follow:FOLLOW[non_terminal])
                cout<<follow<<" ";
            cout<<endl;
        }
        cout<<endl;
    }

     //打印分析表
    void printTable()
    {
        cout<<"LR分析表："<<endl;

        vector<string>x=T;//含界符的终结符号集合
        x.push_back("$");

        //输出表格横轴
        cout<<"****************action****************"<<endl;
        cout.setf(ios::left);
        for (auto it1 = x.begin(); it1 != x.end(); it1++)
        {
            if (it1==x.begin())
                cout<<setw(10)<<" ";
            cout<<setw(8)<<*it1;
        }
        cout<<endl;

        for(int i=0; i<States.size(); i++)
        {
            cout<<setw(10)<<i;

            for(string t:x)
            {
                //cout<<i<<"ttt"<<endl;

                if(!actionTable.empty())
                {
                    pair<int,string>title(i,t);
                    cout<<setw(8)<<actionTable[title];
                }

                else
                    cout<<setw(8);
            }
            cout<<endl;
        }
        cout<<endl;

        /*打印GOTO表*/
        vector<string>y=NT;//不含S’的非终结符号集合
        y.erase(y.begin());

        cout<<"****************goto******************"<<endl;
        cout.setf(ios::left);

        for (auto it1 = y.begin(); it1 != y.end(); it1++)
        {
            if(it1==y.begin())
                cout<<setw(10)<<"";

            cout<<setw(8)<<*it1;
        }
        cout<<endl;

        for(int i=0; i<States.size(); i++)
        {
            cout<<setw(10)<<i;

            for(string t:y)
            {
                pair<int,string>title(i,t);

                if(gotoTable[title]!=0)
                {
                    cout<<setw(8)<<gotoTable[title];
                }
                else
                    cout<<setw(8)<<"";
            }
            cout<<endl;
        }

        cout<<endl<<"LR分析表构建完成"<<endl<<endl;
    }


//打印产生式
    void printP()
    {
        cout<<"语法的产生式为"<<endl;
        for(string left:NT)
        {
            cout<<left<<"->";
            for(auto it=production[left].begin(); it!=production[left].end(); it++)
            {
                if(it!=production[left].end()-1)
                    cout<<*it<<"|";
                else
                    cout<<*it<<endl;
            }
        }
        cout<<endl;
    }

//打印状态表
    void printS()
    {
        cout<<"**********状态集合为**********"<<endl;
        for(State s:States)
        {
            cout<<"状态编号："<<s.id<<endl;
            printI(s.items);
        }
        cout<<endl;
    }

//打印状态转移函数
    void printGO()
    {
        cout<<"**********状态转移函数为**********"<<endl;
        for(GOTO go:GO)
        {
            cout<<go.from<<"---"<<go.path<<"-->"<<go.to<<endl;
        }
        cout<<endl;
    }

//打印项目集
    void printI(set<Item>I)
    {
        cout<<"LR的项目集为"<<endl;
        for(Item i:I)
        {
            cout<<i.getItem()<<",";
            for(string s:i.getSymbol())
            {
                cout<<s<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
    }
};
int main()
{
    string filename="grammar-input.txt";
    LR1 grammar(filename);
    grammar.printP();//输出产生式
    grammar.parser("Tokens.txt");

    return 0;
}
/*
测试文法（LALR）：
A->( A )|a
测试文法（不是LALR）：
S->a A d|b B d|a B e|b A e
A->c
B->c
*/

之前状态集States都是用的set，想着可以直接去重，删除查找也更方便，但是LALR里合并同心项要修改的太多了，set修改是真的麻烦，改了一上午也没改好…最后改成用vector了
 

测试结果

1. LALR文法

2. 非LALR文法