博客

注：本程序只能进行LL(1)文法的分析，非LL(1)文法请转化为LL(1)文法

变量声明

string M[2000][2000];     //任务分析表
stack <char> cc;          //分析栈
queue <char> qq;          //输入串
set <char> ww[200];       //first集
set <char> T;             //终结符集
set <char> N;             //非终结符集合
set <char> vv[200];       //中间过程记录集
set <char> ff[200];       //fllow集合
set <char> select[200];   //select集合

int step = 0;             //步骤统计变量
int error_flag=0;         //错误标志位
int nullflag[1000];       //是否推空标志
int nullselect[1000];     //集合是否推空标志
int ll=0;                 //文法行数
int T_flag[1000];         //右侧是否含有终结符
int length_char[1000];    //每行文法的字符个数
char line[100][1024];     //文法记录表

输入&初步分析：文件输入（每个文法一行,如A->B）

void raedFromFile()
{
    fstream infile("project.txt",ios::in);
    while(infile.getline(line[ll],sizeof(line[ll])))
    {
        for(int i=0;i<100;i++)
        {
            if(int(line[ll][i])==0)
                {
                    length_char[ll]=i;
                    break;
                }
            if(isT(line[ll][i]))
                T_flag[ll]=1;
                T.insert(line[ll][i]);
            if(isN(line[ll][i]))
                N.insert(line[ll][i]);
        }
        if(isT(line[ll][3]))
        {
            //first集合
            if(line[ll][3]=='^')
            {
                nullflag[int(line[ll][0])]=1;
            }
            ww[int(line[ll][0])].insert(line[ll][3]);
        }else
        {
            vv[int(line[ll][0])].insert(line[ll][3]);
        }
        ll++;
    }
}

求FIRST集

void firstSet()
{
    for(int i=0;i<ll;i++)
    {
        if(isN(line[i][3]))
        {
            int j=3;
            while(nullflag[int(line[i][j])]==1)
            {
                if(j+1==length_char[i])
                {
                    break;
                }
                if(isN(line[i][j+1]))
                {
                    vv[int(line[i][0])].insert(line[i][j+1]);
                    j++;
                }
            }
        }
    }
    while(!isEmpty())
    {
        for(set<char>::iterator ite1 = N.begin();ite1!=N.end();ite1++)
        {
            //对于所有非终结符
            //如果他的first已经完毕收集
            if(vv[int(*ite1)].empty())
            {
                //那么就把他的first加入到含有他的vv中
                for(set<char>::iterator ite3 = N.begin();ite3!=N.end();ite3++)
                {
                    for(set<char>::iterator ite4 = vv[int(*ite3)].begin();ite4!=vv[int(*ite3)].end();ite4++)
                    {
                        if(*ite4==*ite1)
                        {
                            vv[int(*ite3)].erase(*ite4);
                            //ite1的first集
                            for(set<char>::iterator ite5 = ww[int(*ite1)].begin();ite5!=ww[int(*ite1)].end();ite5++)
                            {
                              ww[int(*ite3)].insert(*ite5);
                            }
                            break;
                        }
                    }
                }
            }
        }
    }
}

FLLOW集

void fllowSet()
{
    ff[int(line[0][0])].insert('#');
    for(int i=0;i<ll;i++)
    {
        int j=3;
        while(j!=length_char[i])
        {
            //依次考虑每个非终结符,分情况，情况就是我们平时的那几个情况
            if(isN(line[i][j]))
            {
                if(j==length_char[i]-1)
                {
                    if(line[i][0]!=line[i][j])
                        vv[int(line[i][j])].insert(line[i][0]);
                }
                else if(isN(line[i][j+1])&&nullflag[int(line[i][j+1])]==1)
                {
                    if(line[i][0]!=line[i][j])
                        vv[int(line[i][j])].insert(line[i][0]);
                    for(set<char>::iterator ite2 = ww[int(line[i][j+1])].begin();ite2!=ww[int(line[i][j+1])].end();ite2++)
                    {
                        if(*ite2!='^')
                            ff[int(line[i][j])].insert(*ite2);
                    }
                }
                else if(isN(line[i][j+1])&&nullflag[int(line[i][j+1])]==0)
                {
                    for(set<char>::iterator ite2 = ww[int(line[i][j+1])].begin();ite2!=ww[int(line[i][j+1])].end();ite2++)
                    {
                        if(*ite2!='^')
                            ff[int(line[i][j])].insert(*ite2);
                    }
                }
                else if(isT(line[i][j+1]))
                {
                    ff[int(line[i][j])].insert(line[i][j+1]);
                }else{}
            }
            j++;
        }
    }


    while(!isEmpty())
    {
        for(set<char>::iterator ite1 = N.begin();ite1!=N.end();ite1++)
        {
            //对于所有非终结符
            //如果他的fllow已经完毕收集
            if(vv[int(*ite1)].empty())
            {
                //那么就把他的first加入到含有他的vv中
                for(set<char>::iterator ite3 = N.begin();ite3!=N.end();ite3++)
                {
                    for(set<char>::iterator ite4 = vv[int(*ite3)].begin();ite4!=vv[int(*ite3)].end();ite4++)
                    {
                        if(*ite4==*ite1)
                        {
                            vv[int(*ite3)].erase(*ite4);
                            //ite1的first集
                            for(set<char>::iterator ite5 = ff[int(*ite1)].begin();ite5!=ff[int(*ite1)].end();ite5++)
                            {
                              ff[int(*ite3)].insert(*ite5);
                            }
                            break;
                        }
                    }
                }
            }
        }
    }
}

SELECT集

void selectSet()
{
    for(int i=0;i<ll;i++)
    {
        int j=3;
        if(isN(line[i][3]))
        {
            for(set<char>::iterator ite2 = ww[line[i][3]].begin();ite2!=ww[line[i][3]].end();ite2++)
            {
                if(*ite2!='^')
                    select[i].insert(*ite2);
            }
        }
        while(isN(line[i][j])&&nullflag[int(line[i][j])]==1)
        {
            if(j==length_char[i]-1)
                break;
            for(set<char>::iterator ite2 = ww[line[i][j+1]].begin();ite2!=ww[line[i][j+1]].end();ite2++)
            {
                if(*ite2!='^')
                    select[i].insert(*ite2);
            }
            j++;
        }
        if(isT(line[i][j]))
        {
            select[i].insert(line[i][j]);
        }
    }

    _null2();
    for(int i=0;i<ll;i++)
    {
        if(nullselect[i]==1)
        {
            select[i].erase('^');
            for(set<char>::iterator ite5 = ff[int(line[i][0])].begin();ite5!=ff[int(line[i][0])].end();ite5++)
            {
                select[i].insert(*ite5);
            }
        }
    }
}

建表

void LL_1Table()
{
    for(int i=0;i<ll;i++)
    {
        for(set<char>::iterator ite2 = select[i].begin();ite2!=select[i].end();ite2++)
        {
            for(int j=0;j<length_char[i];j++)
                M[int(line[i][0])][int(*ite2)]+=line[i][j];
        }
    }
}

表分析

void grammatical_analysis(string s)
{
    cout<<"步骤  "<<"符号栈 "<<"剩余输入串  "<<"产生式(空用^表示)"<<endl;
    for(int i=0 ; i<s.length();i++)
    {   //初始化输入串队列
        qq.push(s[i]);
    }
    //分析过程
    while((qq.front()=='#'&&cc.top()=='#')==0)
    {
        while(isN(cc.top()))
        {
            string str=M[cc.top()][qq.front()];
            //错误1号
            if(str=="")
            {
                cout<<step<<" "<<"输入句不是文法的合法句型"<<endl;
                error_flag=1;
                break;
            }
            cout<<step<<"\t";
            step++;
            showCC();
            showPP();
            cout<<str<<endl;
            cc.pop();
            for(int i=str.size()-1;i>=0;i--)
            {
                if(str[i]=='>')
                    break;
                if(str[i]!='^')
                cc.push(str[i]);
            }
        }
        //接受
        if(error_flag==1)
        {
            break;
        }
        if(cc.top()=='#'&&qq.front()=='#')
        {
            cout<<step<<"\t";
            step++;
            showCC();
            showPP();
            cout<<"接受"<<endl;
        }
        else if(cc.top()==qq.front())
        {
            cout<<step<<"\t";
            step++;
            showCC();
            showPP();
            cout<<"\""<<cc.top()<<"\"匹配"<<endl;
            qq.pop();
            cc.pop();
        }else{
            //错误2号
            cout<<step<<" "<<"输入句不是文法的合法句型"<<endl;
        }
    }
}

以上是整个的具体思路即核心代码

完整代码请见

点击打开链接