天天看点

LR(1)文法分析器 //c++ 实现

1、先读入终结符,非终结符,和全部产生式。

2、预处理:初始化;getpp()获得每一个非终结符在产生式左边时的产生式编号,

记录在 string getp[]中(能够多个)。

3.获得全部的符号的first集:dfs法,从S開始DFS,遇到终结符则是递归出口,回溯时候沿路保存记录全部路径上VN的first,(遇到有左递归的,continue,左递归的产生式不用不影响求fisrt集)

4:获得项目集族:一个lr(1)项目用一个结构体记录,get_close(项目 t):bfs来完毕对t的闭包。getxmjizu():bfs,并用链式前向星记录图。

5.获得分析表table[][]:遍历对于图的全部边,状态i->j有权为w的边,置action(i,w)=j;go,本质是一样的.其次扫描全部项目,对于归约项目,置归约

6总控程序:俩个栈:状态栈和符号栈,无非移进、归约,接受保存。

測试:

a b

H S B

H->S

B->aB

S->BB

B->b

end

i * ( ) +

E T F

E->E+T

E->T

T->T*F

T->F

F->(E)

F->i

a b c d

S A B

S->A

A->B|cAd

B->aBb|ab

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<cstring>
#include<queue>
using namespace std;
map<char,int>getnum;
char getchar[100];          //获得相应字符
vector<string>proce;        //产生式
int table[30][30];         //预測分析表 -1
int tb_s_r[30][30];        //是移进项还是规约项,-1,-2.
int num=0;int numvt=0;   //numvt是终结符集合,0是‘#’,numvt表空字
void readin()                        //读入vt,vn,编号1-num,读入全部产生式
{
    memset(table,-1,sizeof(table));
    getnum['#']=0;
    getchar[0]='#';
    cout<<"请输入终结符集:"<<endl;
    char x;
    do
    {
      cin>>x;
      getnum[x]=++num;
      getchar[num]=x;
    }while(cin.peek()!='\n');
     numvt=++num;
     getnum['@']=numvt;        //kong zi
     getchar[num]=('@');
    cout<<"请输入非终结符集:"<<endl;
    do
    {
      cin>>x;
      getnum[x]=++num;
      getchar[num]=x;
    }while(cin.peek()!='\n');
    cout<<"输入全部产生式(空字用‘@’表示),以‘end’结束:"<<endl;
    string pro;
     while(cin>>pro&&pro!="end")
     {
         string ss;
         ss+=pro[0];
         for(int i=3;i<pro.size();i++)
         {
             if(pro[i]=='|')
             {
                  proce.push_back(ss);
                  ss.clear();ss+=pro[0];
             }
             else
             {
                 ss+=pro[i];
             }
         }
          proce.push_back(ss);
    }
}
struct xiangmu         //一个项目
{
    int nump;       //产生式编号
    int id;        //.的位置
    string fst;   //集合
};
string getp[100];   //获得某终结符在左边的产生式集合
void getpp()
{
    for(int i=0;i<proce.size();i++)
    {
        int temp=getnum[proce[i][0]];
        getp[temp]+=char('0'+i);
    }
}
string first[100];   //每一个符号的first集
bool gotfirst[100]; //是否已经完毕FIRST集合
void dfsgetfirst(int nv,int nump)  //当前的符号,和相应产生式编号
{
   int temp=getnum[proce[nump][1]];  //产生式推出来的首符
    gotfirst[nump]=1;               //标记
    if(temp<=numvt)first[nv]+=char('0'+temp);  //是终结符
    else
    {
        for(int i=0;i<getp[temp].size();i++)    //全部temp能够推出来的符号相应的产生式
          {
              if(proce[nump][0]==proce[nump][1])continue; //左递归的产生式不用不影响求fisrt集
              dfsgetfirst(temp,getp[temp][i]-'0');
          }

        first[nv]+=first[temp];                  //回溯时候沿途保存
    }
}
void get_first()
{
    for(int i=1;i<=numvt;i++)             //    终结符first集合是它自己.
    {
        first[i]=char('0'+i);
    }
     for(int i=0;i<proce.size();i++)
    {
        if(proce[i][0]==proce[i][1])continue; //左递归的产生式不用不影响求fisrt集
        if(gotfirst[i])continue;              //已经生成。      

int temp=getnum[proce[i][0]];

dfsgetfirst(temp,i);

}

}

vector<vector<xiangmu> >v; //项目集族

int e[100][3]; int head[100];int nume=0; //链式前向星项目集族图

void addegde(int from,int to,int w) //加入边

{

e[nume][0]=to;e[nume][1]=head[from];head[from]=nume;

e[nume++][2]=w;

void clear() //初始化函数

for(int i=0;i<100;i++)

head[i]=-1;

for(int i=0;i<30;i++)

for(int j=0;j<30;j++)

tb_s_r[i][j]=table[i][j]=-1;

nume=0;

inline bool xmeq(xiangmu a,xiangmu b)

if(a.fst==b.fst&&a.id==b.id&&a.nump==b.nump)return 1;

return 0;

bool isin(xiangmu a,vector<xiangmu> b) //xm a is in xmji b

for(int i=0;i<b.size();i++)

{

if(xmeq(a,b[i]))return 1;

vector<xiangmu> hebing(vector<xiangmu>a ,vector<xiangmu>b) //合并项目集 a,b 复给 a

if(isin(b[i],a))continue;

else

a.push_back(b[i]);

return a;

bool xmjieq(vector<xiangmu> a,vector<xiangmu> b) //两个项目集是否相等

if(a.size()!=b.size())return 0;

for(int i=0;i<a.size();i++)

{

if(!isin(a[i],b))return 0;

}

return 1;

int xmji_isin_xmjizu(vector<xiangmu>a,vector<vector<xiangmu> >b) //查找项目集,若有,则返回编号,一举俩得

if(xmjieq(a,b[i]))return i;

return -1;

vector<xiangmu> get_close(xiangmu t) //对项目 T作闭包

vector<xiangmu> temp;

temp.push_back(t);

queue<xiangmu> q; //bfs完毕闭包

q.push(t);

while(!q.empty())

xiangmu cur=q.front();

q.pop();

if(cur.id==proce[cur.nump].size()) //归约项舍去

continue;

int tt=getnum[proce[cur.nump][cur.id]]; //tt is thm num of '.'zhihoudefuhao

if(tt<=numvt) continue ; //若是终结符,则不必找了

for(int i=0;i<getp[tt].size();i++) //相应产生式的编号

{

xiangmu c;

c.id=1; //

c.nump=getp[tt][i]-'0'; //

if(proce[cur.nump].size()-cur.id==1) // the last : A->BC.D,a/b

c.fst+=cur.fst;

else //not the last :A->B.CFb,a/b

{

int tttnum=getnum[proce[cur.nump][cur.id+1]];

c.fst+=first[tttnum];

}

if(!isin(c,temp)) //排重,新的项目就加入。

{

q.push(c);

temp.push_back(c);

}

}

return temp;

void get_xiangmujizu() //获得项目集族

vector<xiangmu>temp;

xiangmu t;

t.nump=0;t.id=1;t.fst+='0'; //初始的项目集:0

temp=get_close(t);

queue<vector<xiangmu> >q; //bfs法获得

q.push(temp);

v.push_back(temp); //第一个入

vector<xiangmu> cur=q.front();

q.pop();

for(int i=1;i<=num;i++) //全部符号

if(i==numvt)continue; //'#'

vector<xiangmu> temp;

for(int j=0;j<cur.size();j++) //该项目集中的全部项目

{

if(cur[j].id==proce[cur[j].nump].size())continue; //是规约项目。无法再读入了

int tt=getnum[proce[cur[j].nump][cur[j].id]];

if(tt==i) //can read in 符号i

{

xiangmu tempt;

tempt.fst=cur[j].fst;

tempt.id=cur[j].id+1;

tempt.nump=cur[j].nump;

temp=hebing(temp,get_close(tempt));

}

}

if(temp.size()==0)continue; //该符号无法读入。

int numcur=xmji_isin_xmjizu(cur,v); //当前节点标号

int tttnum=xmji_isin_xmjizu(temp,v); //新目标标号

if(tttnum==-1) //新的项目集

{

v.push_back(temp);

q.push(temp);

addegde(numcur,v.size()-1,i) ; //加入边,权为读入的符号

}

else //老的项目集

addegde(numcur,tttnum,i);

}

void print_xmjizu() //打印项目集族

for(int i=0;i<v.size();i++)

cout<<"项目集"<<i<<":"<<endl;

for(int j=0;j<v[i].size();j++)

cout<<proce[v[i][j].nump]<<" "<<v[i][j].id<<" "<<v[i][j].fst<<endl;

cout<<endl;

for(int j=head[i];j!=-1;j=e[j][1])

cout<<" "<<getchar[e[j][2]]<<endl;

cout<<i<<"--->"<<e[j][0]<<endl;

bool get_table() //获得分析表table[i][j]=w:状态i-->j,读入符号W。

for(int i=0;i<v.size();i++) //遍历图

if(table[i][e[j][2]]!=-1)return 0; //多重入口。报错.

table[i][e[j][2]]=e[j][0];

tb_s_r[i][e[j][2]]=-1; //移近项-1。

for(int i=0;i<v.size();i++) //遍历全部项目

if(v[i][j].id==proce[v[i][j].nump].size()) //归约项

{

for(int k=0;k<v[i][j].fst.size();k++)

if(table[i][(v[i][j].fst)[k]-'0']!=-1)return 0; //多重入口,报错.

if( (v[i][j].fst)[k]=='0'&&v[i][j].nump==0)

table[i][(v[i][j].fst)[k]-'0']=-3 ; //接受态。

else

{

table[i][(v[i][j].fst)[k]-'0']=v[i][j].nump;

tb_s_r[i][(v[i][j].fst)[k]-'0']=-2; //归约态

}

}

void print_table()

cout<<"LR(1)分析表:"<<endl;

cout<<"状态 "<<" actoin "<<endl;

for(int j=0;j<=num;j++)

if(j==numvt)continue;

cout<<" "<<getchar[j];

cout<<endl;

cout<<i<<" ";

for(int j=0;j<=num;j++)

if(table[i][j]==-3) cout<<"acc"<<" "; //接受

else if(table[i][j]==-1)cout<<" "; //空

else if(tb_s_r[i][j]==-1)cout<<"s"<<table[i][j]<<" "; //移近

else if(tb_s_r[i][j]==-2)cout<<"r"<<table[i][j]<<" "; //归约

cout<<endl;

string word;

void print_now_state(int count,stack<int>state,stack<int>wd,int i)

cout<<count<<'\t'<<'\t';

stack<int>temp;

while(!state.empty())

temp.push(state.top());

state.pop();

while(!temp.empty())

cout<<temp.top();

temp.pop();

cout<<'\t'<<'\t';

while(!wd.empty())

temp.push(wd.top());

wd.pop();

cout<<getchar[temp.top()];

for(int j=i;j<word.size();j++)

cout<<word[j];

bool analyze()

cout<<" "<<word<<"的分析过程:"<<endl;

cout<<"步骤\t\t"<<"状态栈\t\t"<<"符号栈\t\t"<<"输入串\t\t"<<"动作说明"<<endl;

stack<int>state; //俩个栈:状态栈和符号栈

stack<int>wd;

int count=0;

state.push(0); //初始化

wd.push(0); //'#'

for(int i=0;;) //i,读入文本的

int cur=state.top();

if(table[cur][getnum[word[i]]]==-1) // 空白,报错误

return 0;

if(table[cur][getnum[word[i]]]==-3) //接受态

print_now_state(count++,state,wd,i);

cout<<" 恭喜。acc!"<<endl;

return 1;

if(tb_s_r[cur][getnum[word[i]]]==-1) //移进项

print_now_state(count++,state,wd,i);

int newstate=table[cur][getnum[word[i]]];

cout<<"action["<<cur<<","<<getnum[word[i]]<<"]="<<newstate;

cout<<",状态"<<newstate<<"入栈"<<endl;

wd.push(getnum[word[i]]);

state.push(newstate);

i++;

else if(tb_s_r[cur][getnum[word[i]]]==-2) //归约

int numpro=table[cur][getnum[word[i]]]; //用该产生式归约

int len=proce[numpro].size()-1;

for(int ii=0;ii<len;ii++) //弹栈

{

wd.pop();

state.pop();

}

wd.push(getnum[proce[numpro][0]]); //新入

int cur=state.top();

cout<<"用"<<proce[numpro][0]<<"->";

for(int ii=1;ii<=len;ii++)

cout<<proce[numpro][ii];

cout<<"进行归约,"<<"goto["<<cur<<","<<getnum[word[i]]<<"]="<<table[cur][getnum[proce[numpro][0]]];

cout<<"入栈"<<endl;

state.push(table[cur][getnum[proce[numpro][0]]]);

return 1;

int main()

clear();

readin();

getpp();

get_first();

get_xiangmujizu();

if(!get_table())

cout<<"此文法在生成分析表时候有多重入口,非LR(1)文法!