欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-13 17:35:12
...

前文回顾

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

代码

和SLR的区别其实只是DFA中多了一个搜索符,构建分析表的时候规约项的列是相应的搜索符而已

代码基本上就在SLR的代码上修修补补,但是写的有点乱,以后有时间再整理一下吧

Item类

#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;//项目右部
    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="$";//初始向前搜索符为"$"

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

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

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

    //参数是左部和右部和向前搜索符号
    Item(string l,string r,string s)
    {
        id=count++;
        left=l;
        right=r;
        symbol=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;
    }

    string getSymbol()
    {
        return symbol;
    }

    //找点的位置
    int getDot(string item)
    {
        return item.find(".");
    }
    //设置向前搜索符号
    void setSymbol(string new_symbol)
    {
        symbol=new_symbol;
    }
    //给文法加点
    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;

LR(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 Item &x,const Item &y)
{

    return x.id<y.id;
}

bool operator <(const GOTO &x,const GOTO &y)
{

    return x.from<y.from;
}

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;//编号的产生式集合,用于规约
    set<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++;
            }
        }

//        for(auto it=numPro.begin();it!=numPro.end();it++)
//            cout<<it->first<<"\t"<<it->second<<endl;
    }

    //填终结符
    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;
    }
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]aaa@qq.com
                    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);
        //cout<<item.getItem()<<endl;

        while(!bfs.empty())
        {
            Item now=bfs.front();
            bfs.pop();
            //cout<<now.getItem()<<endl;

            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());

                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(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.insert(s0);

        //构建DFA
        State temp;
        for(State s:States)
        {
            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());//新状态核心项,向前搜索符继承
                    set<Item>next=closure(nextD);//to

                    //该状态已经有这条路径了,则将新产生的闭包添加到原有目的状态中
                    int oldDes;
                    if(Paths.find(path)!=Paths.end())
                    {
                        oldDes=Paths.find(path)->second;
//                        cout<<oldDes<<endl;
                        for(State dest:States)
                        {
                            if(dest.id==oldDes)
                            {
                                dest.items.insert(next.begin(),next.end());
                                next=dest.items;

                                //更新状态集中状态
                                //set不允许重复插入,因此只能删除再插
                                States.erase(dest);
                                States.insert(dest);


                                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;
//                                            cout<<tID<<endl;
                                        }
                                    }
                                }
                            }

                        }
                    }

                    //如果该目的状态在状态集里没有出现过,就加入状态集
                    int tID=hasState(next);
                    if(tID==-1)
                    {
                        State t;
                        t.id=number++;
                        t.items=next;
                        States.insert(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(State s1:States)
        {
            for(State s2:States)
            {
                //发现重复状态集
                if(s2.id>s1.id&&s1.items==s2.items)
                {
                    int erase_id=s2.id;
                    States.erase(s2);

                    //重复状态后面的所有状态序号-1
                    for(State s:States)
                    {
                        if(s.id>erase_id)
                        {
                            //原地修改set!
                            State &newS=const_cast<State&>(*States.find(s));
                            newS.id--;
                        }
                    }
                    //状态转移函数
                    for(int i=0; i<GO.size(); i++)
                    {
                        if(GO[i].from==erase_id||GO[i].to==erase_id)
                            GO.erase(find(GO.begin(),GO.end(),GO[i]));
                        if(GO[i].from>erase_id)
                            GO[i].from--;
                        if(GO[i].to>erase_id)
                            GO[i].to--;
                    }
                }
            }
        }
        printS();
        printGO();
    }
    //构造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=*(States.find(temp));
                    set<Item>itm(temp.items.begin(),temp.items.end());
                    //向前搜索符下的规约项规约到对应产生式
                    for(Item i:itm)
                    {
                        pair<int,string>title(go.to,i.getSymbol());
                        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();
        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()<<","<<i.getSymbol()<<endl;
        }
        cout<<endl;
    }
};
int main()
{
    string filename="grammar-input.txt";
    LR1 grammar(filename);
    grammar.printP();//输出产生式
    grammar.parser("Tokens.txt");

    return 0;
}
/*
测试文法:
S->id|V := E
V->id
E->V|n
*/

测试结果

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

相关标签: 编译原理