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)文法！

LR(1)文法分析器 //c++ 實作

繼續閱讀

HDU 5344 MZL's xor

UVA 590 Always on the run

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)