编译原理lr语法分析器c++实现_编译系统上下文无关文法的词法分析器和语法分析器实现技术c++ - CSDN
  • LR分析器是一种由下而上(bottom-up)的上下文无关语法分析器LR意指由左(Left)至右处理输入字符串,并以最右边优先派生(Right derivation)的推导顺序(相对于LL分析器)建构语法树。能以此方式分析的语法...

    LR分析器是一种由下而上(bottom-up)的上下文无关语法分析器。LR意指由左(Left)至右处理输入字符串,并以最右边优先派生(Right derivation)的推导顺序(相对于LL分析器)建构语法树。能以此方式分析的语法称为LR语法。而在LR(k)这样的名称中,k代表的是分析时所需前瞻符号(lookahead symbol)的数量,也就是除了目前处理到的输入符号之外,还得再向右引用几个符号之意;省略 (k)时即视为LR(1),而非LR(0)。

    由于LR分析器尝试由分析树的叶节点开始,向上一层层通过文法规则的化简,最后规约回到树的根部(起始符号),所以它是一种由下而上的分析方法。许多编程语言使用LR(1)描述文法,因此许多编译器都使用LR分析器分析源代码的文法结构。LR分析的优点如下:

    • 众多的编程语言都可以用某种LR分析器(或其变形)分析文法。(C++是个著名的例外)
    • LR分析器可以很有效率的建置。
    • 对所有“由左而右”扫描源代码的分析器而言,LR分析器可以在最短的时间内侦测到文法错误(这是指文法无法描述的字符串)。

    然而LR分析器很难以人工的方式设计,一般使用“分析产生器(parser generator)”或“编译器的编译器(compiler-compiler,产生编译器的工具)”来建构它。LR分析器可根据分析表(parsing table)的建构方式,分类为“简单LR分析器(SLR, Simple LR parser)”、“前瞻LR分析器(LALR, Look-ahead LR parser)”以及“正统LR分析器 (Canonical LR parser)”。这些解析器都可以处理大量的文法规则,其中LALR分析器较SLR分析器强大,而正统LR分析器又比LALR分析器能处理更多的文法。著名的Yacc即是用来产生LALR分析器的工具。


    以上内容来自wiki百科:http://zh.wikipedia.org/wiki/LR_%E5%88%86%E6%9E%90%E5%99%A8

    ================================================================


    以下为LR分析法的主要内容, 截图来源于龙书.


    1. LR语法分析模型


    2. LR分析算法


    3. LR(0)项目集构造


    4. LR(0)项目集构造与DFA构造实例


    5. SLR语法分析表构造算法


    6. LR(1)项目集构造


    7. LR(1)语法分析表构造


    8. LR(1)项目集与分析表实例


    9. LALR分析表构造法


    展开全文
  • #include #include #include #include using namespace std; const int size=100; class stack{  int zt_data[size];char fh_data[size];  int top; public: ... void push_stack(int zt

    #include <iostream>


    #include<cstdlib>
    #include<string>
    #include<cstring>
    using namespace std;
    const int size=100;
    class stack{
      int zt_data[size];char fh_data[size];
      int top;
    public:
      stack();
      void push_stack(int zt,char fh);
      void showstack();
      void pop_stack();
      char get_fh(){return fh_data[top];}
      int get_zt(){return zt_data[top];}
    };
    stack::stack(){zt_data[0]=0;fh_data[0]='#';
                   top=0;
                   }
    void stack::push_stack(int zt,char fh){
                 top++;
                 zt_data[top]=zt;  fh_data[top]=fh;
                 cout<<"push_stack:"<<zt<<'\t'<<fh<<endl;
                 }
    void stack::pop_stack(){
              cout<<"pop_stack:"<<zt_data[top]<<'\t'<<fh_data[top]<<endl;
              zt_data[top]=0;fh_data[top]=NULL;
              top--;
              }
              int main()
              {
                  string input;


        while(1){
            cout<<"please input the string end with '#' "<<endl;
            cin>>input;
            if(input[input.size()-1]=='#') break;
            cout<<"you put worry string";
         }
         stack lr;
         string tab[12][9];
         tab[0][0]="s5";tab[0][3]="s4";tab[0][6]="1";tab[0][7]="2";tab[0][8]="3";
         tab[1][1]="s6";tab[1][5]="acc";
         tab[2][1]="r2";tab[2][2]="s7";tab[2][4]="r2";tab[2][5]="r2";
         tab[3][1]="r4";tab[3][2]="r4";tab[3][4]="r4";tab[3][5]="r4";
         tab[4][0]="s5";tab[4][3]="s4";tab[4][6]="8";tab[4][7]="2";tab[4][8]="3";
         tab[5][1]="r6";tab[5][2]="r6";tab[5][4]="r6";tab[5][5]="r6";
         tab[6][0]="s5";tab[6][3]="s4";tab[6][7]="9";tab[6][8]="3";
         tab[7][0]="s5";tab[7][3]="s4";tab[7][8]="10";
         tab[8][1]="s6";tab[8][4]="s11";
         tab[9][1]="r1";tab[9][2]="s7";tab[9][4]="r1";tab[9][5]="r1";
         tab[10][1]="r3";tab[10][2]="r3";tab[10][4]="r3";tab[10][5]="r3";
         tab[11][1]="r5";tab[11][2]="r5";tab[11][4]="r5";tab[11][5]="r5";
         cout<<"showthetab:"<<endl;
         for(int i=0;i<12;i++)
         {
             for(int j=0;j<9;j++)
             cout<<tab[i][j]<<"\t";
             cout<<endl;
         }
         string unend_char[6]={"E+T","T","T*F","F","(E)","i"};
         char unend_char_l[6]={'E','E','T','T','F','F'};
            char*p=&input[0];
        while(!(('E'==lr.get_fh())&&(*p=='#')))
         {
            int n;
            switch(*p){
            case 'i':n=0;break;
            case '+':n=1;break;
            case '*':n=2;break;
            case '(':n=3;break;
            case ')':n=4;break;
            case '#':n=5;break;
            case 'E':n=6;break;
            case 'T':n=7;break;
            case 'F':n=8;break;
            }
            int m=lr.get_zt();
            string temp=tab[m][n];
            if(temp[0]=='s'){
               int   zt;
             if(temp=="s0")
               zt=0;
             if(temp=="s1")
               zt=1;
              else if(temp=="s2")
               zt=2;
               else if(temp=="s3")
               zt=3;
               else if(temp=="s4")
               zt=4;
               else if(temp=="s5")
               zt=5;
               else if(temp=="s6")
               zt=6;
               else if(temp=="s7")
               zt=7;
               else if(temp=="s8")
               zt=8;
               else if(temp=="s9")
               zt=9;
               else if(temp=="s10")
               zt=10;
               else if (temp=="s11")
               zt=11;
               lr.push_stack(zt,*p);
               p++;
               }
               else  if (temp[0]=='r') {
                   int r_temp;
                   if (temp=="r1")
                    r_temp=1;
                    else if (temp=="r2")
                    r_temp=2;
                    else if (temp=="r3")
                    r_temp=3;
                    else if (temp=="r4")
                    r_temp=4;
                    else if (temp=="r5")
                    r_temp=5;
                    else if (temp=="r6")
                    r_temp=6;
                    string find_string=unend_char[r_temp-1];
                    for(int i=0;i<(int)find_string.size();i++)
                    lr.pop_stack();
                    char fh_temp=unend_char_l[r_temp-1];
                     int  zt_temp=lr.get_zt();




                    int j;
                    switch(fh_temp){
                      case 'i':j=0;break;
                      case '+':j=1;break;
                      case '*':j=2;break;
                      case '(':j=3;break;
                      case ')':j=4;break;
                      case '#':j=5;break;
                      case 'E':j=6;break;
                      case 'T':j=7;break;
                      case 'F':j=8;break;
                  }
                     string zt_temp2=tab[zt_temp][j];
                     //cout<<"hahahahaha"<<zt_temp2<<endl;
                      int zt_temp4=atoi(zt_temp2.c_str());
                     /*char *zt_temp3=const_cast<char*>(zt_temp2.c_str());
                      int zt_temp4=atoi(zt_temp3);*/
                    // char zt_temp4=char(zt_temp4);
                    //cout<<zt_temp4<<endl;
                    lr.push_stack(zt_temp4,fh_temp);






              }


         }
              }

    //纪念我的代码第一次突破150行。




    展开全文
  • 概念梳理最左推导:每一步替换最左边的非终结符 最右推导:每一步替换最右边的非终结符,最右推导称为规范推导 短语:令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有 S⇒∗αAδ且A⇒+β...

    后期DEBUG发现make_set函数和make_go存在问题,于2015年12月4日更新了代码,见谅

    概念梳理

    最左推导:每一步替换最左边的非终结符
    最右推导:每一步替换最右边的非终结符,最右推导称为规范推导
    短语:令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有

    SαAδA+β
    则称 β是相对于非终结符A的, 句型αβδ的短语
    直接短语:令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有
    SαAδAβ
    则称 β是相对于非终结符A的, 句型αβδ的直接短语
    注意:短语和直接短语的区别在于第二个条件, 直接短语中的第二个条件表示有文法规则 Aβ ,因此,每个直接短语都是某规则右部。
    句柄:一个句型的最左直接短语称为该句型的句柄

    • 句柄特征:
      • (1) 它是直接短语,即某规则右部。
      • (2) 它具有最左性。

    规范归约:文法的最右推导为规范推导,自底向上分析是自顶向下最右推导的逆过程,叫规范归约
    活前缀:指规范句型的一个前缀,这种前缀不含句柄之后任何符号。之所以称为活前缀,是因为在右边添加一些符号之首,就可以使它称为一个规范句型。
    项目:对于一个文法G,我们首先要构造一个NFA,它能识别G的所有活前缀。这个NFA的每一个状态是下面定义的一个“项目”。
    项目分类:

    • 归约项目
      凡圆点在最右的项目,如A→α•称为一个“归约项目”
    • 接受项目
      对文法的开始符号S’的归约项目,如S’→α•称为“接受”项目。
    • 移进项目
      形如A→α•aβ的项目,其中a为终结符,称为“移进”项目。
    • 待约项目
      形如A→α•Bβ的项目,其中B为非终结符,称为“待约”项目。

    项目规范族:假定I是文法G’的任一项目集,定义和构造I的闭包CLOSURE(I)的办法是:

    • I的任何项目都属于CLOSURE(I);
    • 若A→α•Bβ属于CLOSURE(I),那么,对任何关于B的产生式B→γ,项目B→•γ也属于CLOSURE(I);

    LR(0)文法:假如一个文法G的拓广文法G’的活前缀识别自动机的每个状态(项目集)不存在下述情况:

    • 既含移进项目又含归约项目。
    • 含多个归约项目。

    则称G是一个LR(0)文法。换言之,LR(0)文法规范族的每个项目集不包含任何冲突项目

    拓广文法:假定文法G是一个以S为开始符号的文法,我们构造一个文法G’,它包含整个G,但它引进了一个不出现在G中的非终结符S’,并加进一个新产生式S’→S,而这个S’是G’的开始符号。那么我们称G’是G的拓广文法。
    函数GO(I,X):函数GO(I,X)是一个状态转换函数。

    • 第一个变元I是一个项目集,
    • 第二个变元X是一个文法符号。
    • 函数值GO(I,X)定义为GO(I,X)=CLOSURE(J),其中J={任何形如A→αX•β的项目 | A→α•Xβ属于I}

    算法描述

    项目集构造算法

    枚举每个规范句型,然后枚举””的位置,获得所有的项目

    项目集规范族构造算法

    假定I是文法G’的任一项目集,定义和构造I的闭包CLOSURE(I)的办法是:
    I的任何项目都属于CLOSURE(I);
    若A→α•Bβ属于CLOSURE(I),那么,对任何关于B的产生式B→γ,项目B→•γ也属于CLOSURE(I);
    重复执行上述两步骤直至CLOSURE(I)不再增大为止。

    Go(I,a)函数构造算法

    遍历所有的项目,如果任意两个项目之间存在边(有向),那么这两个项目所在的项目规范族之间连上对应的有向边。

    LR(0)分析表构造算法

    假定项目集规范族C={I0,I1,…,In}。令每一个项目集Ik的下标k作为分析器的状态。分析表的ACTION子表和GOTO子表可按如下方法构造

    • 令那个包含项目S’→•S的集合Ik的下标k为分析器的初态。
    • 若项目A→α•aβ属于Ik且GO(Ik , a)= Ij,a为终结符,置ACTION[k,a]为“把(j,a)移进栈”,简记为“sj”。
    • 若项目A→α•属于Ik,对任何终结符a(或结束符#),置ACTION[k,a]为“用产生式A→α进行归约”,简记为“rj”(假定产生式A→α是文法G’的第j个产生式)。
    • 若项目S’→S•属于Ik,则置ACTION[k,#]为“接受”,简记为“acc”。
    • 若GO(Ik , A)= Ij,A为非终结符,则置GOTO[k,A]=j。
    • 分析表中凡不能用规则1至4填入信息的空白格均填上“报错标志”。

    LR(0)分析法的分析过程

    • 遍历输入字符串,对于每一个字符,获取当前状态栈的顶部的状态值,通过查询action表获取的当前的操作是移进、规约还是接受
      • 如果当前操作是移进,将新的状态放入状态栈当中,当移入的字符放入符号栈中。
      • 如果当前操作是规约,那么将需要规约的部分的状态从状态栈中弹出,将规约后的状态放入状态栈,将规约后的左部放入符号栈,当前的字符不向下推进
      • 如果接收,则结束

    代码实现

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cctype>
    #include <vector>
    #include <string>
    #include <queue>
    #include <map>
    #include <sstream>
    #define MAX 507
    #define DEBUG
    
    using namespace std;
    
    class WF
    {
        public:
        string left,right;
        int back;
        int id;
        WF ( char s1[] , char s2[] , int x , int y )
        {
            left = s1;
            right = s2;
            back = x;
            id = y;
        }
        WF ( const string& s1 , const string& s2 , int x , int y )
        {
            left = s1;
            right = s2;
            back = x;
            id = y;
        }
        bool operator < ( const WF& a ) const 
        {
            if ( left == a.left ) 
                return right < a.right;
            return left < a.left;
        }
        bool operator == ( const WF& a ) const 
        {
            return ( left == a.left )&& ( right == a.right );
        }
        void print ( )
        {
            printf ( "%s->%s\n" , left.c_str() , right.c_str() );
        }
    };
    
    class Closure
    {
        public:
        vector<WF> element; 
        void print ( string str )
        {
            printf ( "%-15s%-15s\n" , "" , str.c_str());
            for ( int i = 0 ; i < element.size() ; i++ )
                element[i].print();
        }
        bool operator == ( const Closure& a ) const 
        {
            if ( a.element.size() != element.size() ) return false;
            for ( int i = 0 ; i < a.element.size() ; i++ )
                if ( element[i] == a.element[i] ) continue;
                else return false;
            return true;
        }
    };
    
    struct Content
    {
        int type;
        int num;
        string out;
        Content(){ type = -1; }
        Content ( int a , int b )
            :type(a),num(b){}
    };
    
    vector<WF> wf;
    map<string,vector<int> > dic;
    string start = "S";
    vector<Closure> collection;
    vector<WF> items;
    char CH = '$';
    int go[MAX][MAX];
    int to[MAX];
    vector<char> V;
    bool used[MAX];
    Content action[MAX][MAX];
    int Goto[MAX][MAX];
    
    void make_item ( )
    {
        memset ( to , -1 , sizeof ( -1 ) );
        for ( int i = 0 ; i < wf.size() ; i++ )
            for ( int j = 0 ; j <= wf[i].right.length() ; j++ )
            {
                string temp = wf[i].right;
                temp.insert ( temp.begin()+j , CH );
                dic[wf[i].left].push_back ( items.size() );
                if ( j )
                    to[items.size()-1] = items.size();
                items.push_back ( WF ( wf[i].left , temp , i , items.size()) );
            }
    #ifdef DEBUG
        puts("-------------------------项目表-------------------------");
        for ( int i = 0 ; i < items.size() ; i++ )
            printf ( "%s->%s\n" , items[i].left.c_str() , items[i].right.c_str() );
        puts("--------------------------------------------------------");
    #endif
    }
    
    void make_set ( )
    {
        bool has[MAX];
        for ( int i = 0 ; i < items.size() ; i++ )
            if ( items[i].left[0] == 'S' && items[i].right[0] == CH )
            {
                Closure temp;
                string& str = items[i].right;
                vector<WF>& element = temp.element;
                element.push_back ( items[i] );
                int x = 0;
                for ( x = 0 ; x < str.length() ; x++ )
                    if ( str[x] == CH )
                        break;
                /*if ( x != str.length()-1 )
                {
                    string tt = str.substr(x+1,1);
                    vector<int>& id = dic[tt];
                    for ( int j = 0 ; j < id.size() ; j++ )
                    {
                        int tx = id[j];
                        //items[tx].print();
                        if ( items[tx].right[0] == CH )
                            element.push_back ( items[tx] );
                    }
                }*/
                memset ( has , 0 , sizeof ( has ) );
                has[i] = 1;
                if ( x != str.length()-1 )
                {
                    queue<string> q;
                    q.push( str.substr(x+1,1) );
                    while ( !q.empty() )
                    {
                        string u = q.front();
                        q.pop();
                        vector<int>& id = dic[u];
                        for( int j = 0 ; j < id.size() ; j++ )
                        {
                            int tx = id[j];
                            if ( items[tx].right[0] == CH )
                            {   
                                if ( has[tx] ) continue;
                                has[tx] = 1;
                                if ( isupper(items[tx].right[1] ) )
                                    q.push ( items[tx].right.substr(1,1));
                                element.push_back ( items[tx] );
                            }    
                        }
                    }
                }
                collection.push_back ( temp );
            }
        for ( int i = 0 ; i < collection.size() ; i++ )
        {
            map<int,Closure> temp;
            for ( int j = 0 ; j < collection[i].element.size() ; j++ )
            {
                string str = collection[i].element[j].right;
                int x = 0;
                for ( ; x < str.length() ; x++ )
                   if ( str[x] == CH ) break;
                if ( x == str.length()-1 ) 
                    continue;
                int y = str[x+1];
                int ii;
                //cout << i << "previous: " << str << endl;
                str.erase ( str.begin()+x);
                str.insert ( str.begin()+x+1 , CH );
                //cout << i <<"after: " << str << endl;
                WF cmp = WF ( collection[i].element[j].left , str , -1 , -1 );
                for ( int k = 0 ; k< items.size() ; k++ )
                    if ( items[k] == cmp )
                    {
                        ii = k;
                        break;
                    }
                 //string& str1 = items[ii].right;
                 memset ( has , 0 , sizeof ( has ) );
                 vector<WF>& element = temp[y].element;
                 element.push_back ( items[ii] );
                 has[ii] = 1;
                 x++;
                 /*if ( x != str.length()-1 )
                 {
                     string tt = str.substr(x+1,1);
                     vector<int>& id = dic[tt];
                     for ( int j = 0 ; j < id.size() ; j++ )
                     {
                        int tx = id[j];
                        //items[tx].print();
                        if ( items[tx].right[0] == CH )
                            element.push_back ( items[tx] );
                     } 
                 }*/
                if ( x != str.length()-1 )
                {
                    queue<string> q;
                    q.push( str.substr(x+1,1) );
                    while ( !q.empty() )
                    {
                        string u = q.front();
                        q.pop();
                        vector<int>& id = dic[u];
                        for( int j = 0 ; j < id.size() ; j++ )
                        {
                            int tx = id[j];
                            if ( items[tx].right[0] == CH )
                            {   
                                if ( has[tx] ) continue;
                                has[tx] = 1;
                                if ( isupper(items[tx].right[1] ) )
                                    q.push ( items[tx].right.substr(1,1));
                                element.push_back ( items[tx] );
                            }    
                        }
                    }
                }
            }
            map<int,Closure>::iterator it = temp.begin();
            for ( ; it != temp.end() ; it++ )
                    collection.push_back ( it->second );
            for ( int i = 0 ; i < collection.size() ; i++ )
                sort ( collection[i].element.begin() , collection[i].element.end() );
            for ( int i = 0 ; i < collection.size() ; i++ )
                for ( int j = i+1 ; j < collection.size() ; j++ )
                    if ( collection[i] == collection[j] )
                        collection.erase ( collection.begin()+j );
        }
    #ifdef DEBUG
        puts ("-------------CLOSURE---------------------");
        stringstream sin;
        for ( int i = 0 ; i < collection.size() ; i++ )
        {
            sin.clear();
            string out;
            sin <<"closure-I" << i;
            sin >> out;
            collection[i].print ( out );
        }
        puts("");
    #endif  
    }
    
    void make_V ( )
    {
        memset ( used , 0 , sizeof ( used ) );
        for ( int i = 0 ; i < wf.size() ; i++ )
        {
            string& str = wf[i].left;
            for ( int j = 0 ; j < str.length() ; j++ )
            {
                if ( used[str[j]] ) continue;
                used[str[j]] = 1;
                V.push_back ( str[j] );
            }
            string& str1 = wf[i].right;
            for ( int j = 0 ; j < str1.length() ; j++ )
            {
                if ( used[str1[j]] ) continue;
                used[str1[j]] = 1;
                V.push_back ( str1[j] );
            }
        }
        sort ( V.begin() , V.end() );
        V.push_back ( '#' );
    }
    
    void make_cmp ( vector<WF>& cmp1 , int i  , char ch )
    {
        for ( int j = 0 ; j < collection[i].element.size() ; j++ )
        {
            string str = collection[i].element[j].right;
            int k;
            for ( k = 0 ; k < str.length() ; k++ )
                if ( str[k] == CH ) 
                    break;
            if ( k != str.length() - 1 && str[k+1] == ch  )
            {
                str.erase ( str.begin()+k);
                str.insert ( str.begin()+k+1 , CH );
                cmp1.push_back ( WF ( collection[i].element[j].left , str , -1 , -1 ) );
            }
        }
        sort ( cmp1.begin() , cmp1.end() );
    }
    
    void make_go ( )
    {
        memset ( go , -1 , sizeof ( go ) );
        int m = collection.size();
        /*for ( int i = 0 ; i < m ; i++ )
            for ( int j = 0 ; j < collection[i].element.size() ; j++ )
            {
                string left = collection[i].element[j].left;
                string str = collection[i].element[j].right;
                int x = 0;
                for ( ; x < str.length() ; x++ )
                   if ( str[x] == CH ) break;
                if ( x == str.length()-1 ) 
                    continue;
                int y = str[x+1];
               //cout << "before : " << str << endl;
                str.erase ( str.begin()+x);
                str.insert ( str.begin()+x+1 , CH );
               //cout << "after : " << str << endl;
                WF cmp = WF ( collection[i].element[j].left , str , -1 , -1 );
                for ( int k = 0 ; k < m ; k++ )
                {
                    bool flag = false;
                    for ( int t = 0 ; t < collection[k].element.size() ; t++ )
                    {
                        if ( cmp == collection[k].element[t] )
                        {                        
                            flag = true;
                            break;
                        }
                    }
                    if ( flag )
                    {
                        go[i][y] = k;
                    }
                }
            }*/
        for ( int t = 0 ; t < V.size() ; t++ )
        {
            char ch = V[t];
            for ( int i = 0 ; i < m ; i++ )
            {
                vector<WF> cmp1;
                make_cmp ( cmp1 , i , ch );
                cout << cmp1.size() << endl;
                if ( cmp1.size() == 0 ) continue;
                for ( int j = 0 ; j < m ; j++ )
                {
                    vector<WF> cmp2;
                    for ( int k = 0 ; k < collection[j].element.size() ; k++ )
                    {
                        string& str = collection[j].element[k].right;
                        int x;
                        for ( x = 0 ; x < str.length() ; x++ )
                            if ( str[x] == CH )
                                break;
                        if ( x && str[x-1] == ch )
                           cmp2.push_back ( WF( collection[j].element[k].left , str , -1 , -1 ) ); 
                    }
                    sort ( cmp2.begin() , cmp2.end() );
                    cout << cmp2.size() << endl;
                    bool flag = true;
                    if ( cmp2.size() != cmp1.size() ) continue;
                    cout << cmp1.size() << endl;
                    for ( int k = 0 ; k < cmp1.size() ; k++ )
                        if ( cmp1[k] == cmp2[k] ) continue; 
                        else flag = false;
                    cout << "out " << endl;
                    if ( flag ) 
                        go[i][ch] = j;
                }
                //cout << "YES" << endl;
            }
    
        }
    #ifdef DEBUG
        puts ("---------------EDGE----------------------");
        stringstream sin;
        string out;
        for ( int i = 0 ; i < m ; i++ )
            for ( int j = 0 ; j < m ; j++ )
                for ( int k = 0 ; k < MAX ; k++ )
                    if ( go[i][k] == j )
                    {
                        sin.clear();
                        sin << "I" << i << "--" <<(char)(k)<<"--I"<<j;
                        sin >> out;
                        printf ( "%s\n" , out.c_str() );     
                    }   
    #endif
    }
    
    
    void make_table ( )
    {
        memset ( Goto , -1 , sizeof ( Goto ) );
        /*memset ( used , 0 , sizeof ( used ) );
        for ( int i = 0 ; i < wf.size() ; i++ )
        {
            string& str = wf[i].left;
            for ( int j = 0 ; j < str.length() ; j++ )
            {
                if ( used[str[j]] ) continue;
                used[str[j]] = 1;
                V.push_back ( str[j] );
            }
            string& str1 = wf[i].right;
            for ( int j = 0 ; j < str1.length() ; j++ )
            {
                if ( used[str1[j]] ) continue;
                used[str1[j]] = 1;
                V.push_back ( str1[j] );
            }
        }
        sort ( V.begin() , V.end() );
        V.push_back ( '#' );*/
        //write s to the table 
        for( int i = 0 ; i < collection.size() ; i++ )
            for ( int j = 0 ; j < V.size() ; j++ )
            {
                char ch = V[j];
                int x = go[i][ch];
                if ( x == -1 ) continue;
                if ( !isupper(ch) )
                    action[i][ch] = Content ( 0 , x );
                else 
                    Goto[i][ch] = x;
            }
        //write r and acc to the table 
        for ( int i = 0 ; i < collection.size() ; i++ )
            for ( int j = 0 ; j < collection[i].element.size() ; j++ )
            {
                WF& tt = collection[i].element[j];
                if ( tt.right[tt.right.length()-1] == CH )
                {
                    if ( tt.left[0] == 'S' )
                        action[i]['#'] = Content ( 2 , -1 );
                    else 
                        for ( int k = 0 ; k < V.size() ; k++ )
                        {
                            int y = V[k];
                            //cout << "YES " << endl;
                            action[i][y] = Content ( 1, tt.back );
                        }
                }
            }
    #ifdef DEBUG
        puts ( "------------------------------------------LR(0)分析表--------------------------------------------------------" );
        printf ( "%10s%5c%5s" , "|" , V[0]  , "|");
        for ( int i = 1 ; i < V.size() ; i++ )
            printf ( "%5c%5s" , V[i] , "|" );
        puts ("");
        for ( int i = 0 ; i < (V.size()+1)*10 ; i++ )
            printf ( "-" );
        puts("");
        stringstream sin;
        for ( int i = 0 ; i < collection.size() ; i++ )
        {
            printf ( "%5d%5s" , i , "|" );
            for ( int j = 0 ; j < V.size() ; j++ )
            {
                char ch = V[j];
                if ( isupper(ch) )
                {
                    if ( Goto[i][ch] == -1 )
                        printf ( "%10s" , "|" );
                    else 
                        printf ( "%5d%5s" , Goto[i][ch] , "|" );
                }
                else
                {
                    sin.clear();
                    if ( action[i][ch].type == -1 ) 
                        printf ( "%10s" , "|" ); 
                    else 
                    {
                        Content& temp = action[i][ch];
                        if ( temp.type == 0 ) 
                            sin << "S";
                        if ( temp.type == 1 ) 
                            sin << "R";
                        if ( temp.type == 2 )
                            sin << "acc";
                        if ( temp.num != -1 )
                            sin << temp.num;
                        sin >> temp.out;
                        printf ( "%7s%3s" , temp.out.c_str() , "|" );
                    }
                }
            }
            puts ("");
        }
        for ( int i = 0 ; i < (V.size()+1)*10 ; i++ )
            printf ( "-" );
        puts("");
    #endif
    }
    
    void print ( string s1 , string s2 , string s3 , string s4 , string s5 , string s6 , string s7 )
    {
        printf ( "%-15s|%-15s%-15s%-20s|%-15s%-15s%-15s\n" , s1.c_str() , s2.c_str() , s3.c_str() ,s4.c_str(),s5.c_str(),
                                                            s6.c_str() , s7.c_str() );                            
    }
    
    string get_steps ( int x )
    {
        stringstream sin;
        sin << x;
        string ret;
        sin >> ret;
        return ret;
    }
    
    template<class T>
    string get_stk ( vector<T> stk )
    {
        stringstream sin;
        for ( int i = 0 ; i < stk.size() ; i++ )
            sin << stk[i];
        string ret;
        sin >> ret;
        return ret;
    }
    
    string get_shift ( WF& temp )
    {
        stringstream sin;
        sin << "reduce(" << temp.left << "->" << temp.right <<")";
        string out;
        sin >> out;
        return out;
    }
    
    void analyse ( string src )
    {
        print ( "steps","op-stack" ,"input","operation","state-stack" , "ACTION" , "GOTO" );
        vector<char> op_stack;
        vector<int> st_stack;
        src+= "#";
        op_stack.push_back ( '#' );
        st_stack.push_back ( 0 );
        int steps= 1;
        for ( int i = 0 ; i < src.length() ; i++ )
        {
            char u = src[i];
            int top = st_stack[st_stack.size()-1];
            Content& act = action[top][u];
            //cout << "YES : " << i << " " << u << " " << top << " " << act.type << endl;
            if ( act.type == 0 )
            {
                print ( get_steps ( steps++ ) , get_stk ( op_stack ) , src.substr(i), "shift",  get_stk( st_stack ) , act.out , "" );
                op_stack.push_back ( u );
                st_stack.push_back ( act.num );
            }
            else if ( act.type == 1 )
            {
                WF& tt = wf[act.num];
                int y = st_stack[st_stack.size()-tt.right.length()-1];
                int x = Goto[y][tt.left[0]];
                //cout << y << " " << tt.left[0] << " " << x << endl;
                print ( get_steps ( steps++ ) , get_stk ( op_stack ) , src.substr(i) , get_shift(tt) ,get_stk( st_stack),act.out,get_steps(x));
                for ( int j = 0 ; j < tt.right.length() ; j++ )
                {
                    st_stack.pop_back();
                    op_stack.pop_back();
                }
                op_stack.push_back ( tt.left[0] );
                st_stack.push_back ( x );
                i--;
            }
            else if ( act.type == 2 )
            {
                print ( get_steps( steps++ ), get_stk( op_stack ) , src.substr(i) , "Accept" , get_stk(st_stack) , act.out , "" );
                //i--;
            }
            else continue;
        }
    } 
    
    int main ( )
    {
        int n;
        char s[MAX];
        while ( ~scanf ( "%d" , &n ) )
        {
            for ( int i = 0 ; i < n ; i++ )
            {
                scanf ( "%s" , s );
                int len = strlen(s),j;
                for ( j = 0 ; j < len ; j++ )
                    if ( s[j] == '-' ) break;
                s[j] = 0;
                wf.push_back ( WF ( s , s+j+2 ,-1 , -1 ) );
    #ifdef DEBUG
                wf[wf.size()-1].print();
    #endif
            }
            make_item();
            make_set();
        make_V();
            make_go();
            make_table();
            analyse ( "abbcde" );
        }
    }

    Input:

    这里写图片描述

    Output:

    这里写图片描述
    这里写图片描述

    后期调试

    关于12月4日对于make_set函数和make_go函数的更正:
    - 错误主要源自于自己对于概念的模糊,make_set过程中如果加入的新的产生式的右侧””之后依旧是没有出现过的非终结符,那么也要把以它为左部的”$cdot”在首位的项目加入当前的项目规范族
    - make_go是在对规范族之间建边时,一定是通过一个字符的移进,所有与其相关的式子都符合才能建边,而不是只要有两个规范族中有符合要求的规范式就能建边

    展开全文
  • 由于最近学校里在学习编译原理,而且要求实现语法分析器,于是我用了几天的时间搞明白了语法分析器原理并且将其实现了。由于编者还是本科生而且还在学习中,因此出现什么错误请各位指点。 语法分析器的步骤为: ...

    使用C++ 完成LR(0)的语法分析器

    由于最近学校里在学习编译原理,而且要求实现语法分析器,于是我用了几天的时间搞明白了语法分析器的原理并且将其实现了。由于编者还是本科生而且还在学习中,因此出现什么错误请各位指点。
    语法分析器的步骤为:

    1. 读入单词序列
    2. 读入语法规则
    3. 构造基于该语法的Clousure(项目集规范族)集合
    4. 基于上一步构造所有规范句型活前缀的DFA
    5. 根据这个DFA来构造Action表与Goto表(统称为分析表)
    6. 根据分析表来进行分析(具体的分析方法不再赘述)

    由于编者对于所有的处理都是使用字符串与字符进行的,所以在代码理解方面与执行效率方面可能较差。有什么问题都可以与笔者交流,我的Q是1574143668。
    所以相应的代码如下,使用的是IDE是Visual Studio 2017,可以供大家参考:
    具体的代码文件在https://download.csdn.net/download/kiva12138/10750255

    #include "pch.h"
    #include <iostream>
    #include <string>
    #include <sstream> 
    #include <fstream> 
    #include <map>
    #include <typeinfo>
    
    #define MAXNUM 1000
    #define ERROR "err"
    #define ACCUTATE "acc"
    #define MAXNUMOFCLOUSURE 100
    #define MAXNUMOFITEM 100
    #define MAXNUMOFCHAR 30
    
    using namespace std;
    
    class StatusStack{
    protected:
    	int list[MAXNUM];
    	int currentPos;
    public :
    	StatusStack() {
    		currentPos = -1;
    	}
    
    	int getTop() {
    		return this->list[currentPos];
    	}
    
    	int getCurrentPos() {
    		return this->currentPos;
    	}
    
    	int getElement(int pos) {
    		return this->list[pos];
    	}
    
    	void clear() {
    		currentPos = -1;
    	}
    
    	void pop() {
    		currentPos = currentPos - 1;
    	}
    
    	void push(int status) {
    		list[currentPos+1] = status;
    		currentPos++;
    	}
    };
    
    class SymbolStack {
    protected:
    	char list[MAXNUM];
    	int currentPos;
    public:
    	SymbolStack() {
    		list[0] = '#';
    		currentPos = 0;
    	}
    
    	char getTop() {
    		return this->list[currentPos];
    	}
    
    	int getCurrentPos() {
    		return this->currentPos;
    	}
    
    	char getElement(int pos) {
    		return this->list[pos];
    	}
    
    	void clear() {
    		list[0] = '#';
    		currentPos = 0;
    	}
    
    	void pop() {
    		currentPos = currentPos - 1;
    	}
    
    	void push(char str) {
    		list[currentPos + 1] = str;
    		currentPos++;
    	}
    };
    
    class ActionMap {//table[status, inputChar]
    protected:
    	map <int, map<int, string> > table;
    	int numOfStatus;
    	int numOfInputChar;
    
    public:
    	ActionMap(int numOfStatus, int numOfInputChar){
    		this->numOfInputChar = numOfInputChar;
    		this->numOfStatus = numOfStatus;
    		
    		for (int i = 0; i < numOfStatus; i++) {
    			for (int j = 0; j < numOfInputChar; j++) {
    				table[i][j] = ERROR;
    			}
    		}
    	}
    
    	void insert(int status, int inputChar, string ele) {
    		table[status][inputChar] = ele;
    	}
    
    	void remove(int status, int inputChar) {
    		table[status][inputChar] = ERROR;
    	}
    
    	string getElement(int status, int inputChar) {
    		return table[status][inputChar];
    	}
    };
    
    class GotoMap {//table[status, inputStatus]
    protected:
    	map <int, map<int, int> > table;
    	int numOfStatus;
    	int numOfInputStatus;
    
    public:
    	GotoMap(int numOfStatus, int numOfInputStatus) {
    		this->numOfInputStatus = numOfInputStatus;
    		this->numOfStatus = numOfStatus;
    
    		for (int i = 0; i < numOfStatus; i++) {
    			for (int j = 0; j < numOfInputStatus; j++) {
    				table[i][j] = -1;
    			}
    		}
    	}
    
    	void insert(int status, int inputChar, int ele) {
    		table[status][inputChar] = ele;
    	}
    
    	void remove(int status, int inputChar) {
    		table[status][inputChar] = -1;
    	}
    
    	int getElement(int status, int inputChar) {
    		return table[status][inputChar];
    	}
    };
    
    class DFAMap {//[a, b]=B 从状态a接受B到达状态b
    protected:
    	map <int, map<int, char> > table;
    	int firstStatus;
    	int secondStatus;
    public:
    	DFAMap(int numOfStatus) {
    		this->firstStatus = numOfStatus;
    		this->secondStatus = numOfStatus;
    
    		for (int i = 0; i < numOfStatus; i++) {
    			for (int j = 0; j < numOfStatus; j++) {
    				table[i][j] = '*';
    			}
    		}
    	}
    
    	void insert(int status1, int status2, char ele) {
    		table[status1][status2] = ele;
    	}
    
    	void remove(int status1, int status2) {
    		table[status1][status2] = '*';
    	}
    
    	char getElement(int status1, int status2) {
    		return table[status1][status2];
    	}
    };
    
    class NumOfInputChar {
    protected:
    	map<int, char> table;
    	int sum;
    public :
    	NumOfInputChar() {
    		this->sum = 0;
    	}
    	int getSum() {
    		return this->sum;
    	}
    	void inset(char ch) {
    		table [sum++] = ch;
    	}
    	int getNumber(char ch) {
    		for (int i = 0; i <= sum; i++) {
    			if (table[i] == ch) {
    				return i;
    			}
    		}
    		return -1;
    	}
    };
    
    class NumOfInputStatus {
    protected:
    	map<int, char> table;
    	int sum;
    public:
    	NumOfInputStatus() {
    		this->sum = 0;
    	}
    	void inset(int i) {
    		table[sum++] = i;
    	}
    	int getNumber(int in) {
    		for (int i = 0; i <= sum; i++) {
    			if (table[i] == in) {
    				return i;
    			}
    		}
    		return -1;
    	}
    };
    
    class Item {
    public :
    	int posOfDot;
    	string item;
    public :
    	Item() {
    		for (int i = 0; i < 30; i++) {
    			this->item += '\0';
    		}
    	}
    };
    
    class Clousure {
    public:
    	int numOfItem;
    	Item grammer[MAXNUMOFITEM];
    };
    
    void printSymbolStack(SymbolStack symbolStack) {
    	int num = symbolStack.getCurrentPos();
    	cout << "符号栈的内容为:" << endl;
    	for (int i = 0; i <= num; i++) {
    		cout << symbolStack.getElement(i) << " ";
    	}
    	cout << endl;
    }
    
    void printStatusStack(StatusStack statusStack) {
    	int num = statusStack.getCurrentPos();
    	cout << "状态栈的内容为:" << endl;
    	for (int i = 0; i <= num; i++) {
    		cout << statusStack.getElement(i) << " ";
    	}
    	cout << endl;
    }
    
    void getInputSymbol(string strInput[], int * numOfSymbol) {
    	//ifstream fp("input.txt");
    	ifstream fp("input_test.txt");
    	string strRead[MAXNUM];
    	string temp;
    	if (fp.fail()) {
    		std::cout << "Can not open the source file";
    		exit(0);
    	}
    	int num = 0;
    	while (getline(fp, temp)) {
    		strInput[num++] = temp;
    	}
    	*numOfSymbol = num;
    }
    
    void getGrammer(string grammerInput[], int * numOfGrammer) {
    	ifstream fp("grammer_test.txt");
    	string temp;
    	int grammerHasRead = 0;
    	if (fp.fail()) {
    		std::cout << "Can not open the source file";
    		exit(0);
    	}
    	int num = 0;
    	while (getline(fp, temp)) {
    		grammerInput[num++] = temp;
    	}
    	*numOfGrammer = num;
    }
    
    bool grammerAnalysis(string strInput[], ActionMap actionMap, GotoMap gotoMap, 
    					StatusStack statusStack, SymbolStack symbolStack,
    					NumOfInputStatus numOfInputStatus, NumOfInputChar numOfInputChar, 
    					string grammerInput[]) {
    
    	statusStack.push(0);
    	int i = 0;
    	int lastAction = 0;//记录上一动作,0表示移进, 1表示归约
    
    	while (1) {
    		if (lastAction == 0) {
    
    			char temp[1];
    			strInput[i].copy(temp, 1, 0);
    			char inputChar = temp[0];
    			string actionToDo = "";
    			actionToDo = actionMap.getElement(statusStack.getTop(), numOfInputChar.getNumber(inputChar));
    			if (actionToDo == ACCUTATE) {
    				return true;
    			}
    			else if (actionToDo == ERROR) {
    				return false;
    			}
    			if (actionToDo[0] == 'S') {
    				//移进操作
    				statusStack.push(actionToDo[1] - 48);
    				symbolStack.push(inputChar);
    				i++;
    				lastAction = 0;
    
    				//打印信息
    				cout << "移进操作:" <<"移进"<< inputChar << endl;
    				printStatusStack(statusStack);
    				printSymbolStack(symbolStack);
    				cout << endl;
    			}
    			else if (actionToDo[0] == 'R') {
    				//归约操作 使用actionToDo[1]产生式
    				int numOfGrammer = actionToDo[1] - 48;
    				int startPosOfGrammer = 0;//产生式开始的位置
    				int endPosOfGrammer = 0;//产生式结束的的分号的位置
    				
    				char temp[1];
    				grammerInput[numOfGrammer-1].copy(temp, 1, endPosOfGrammer);
    				char todoChar = temp[0];
    				while (todoChar != ';') {
    					grammerInput[numOfGrammer-1].copy(temp, 1, endPosOfGrammer);
    					todoChar = temp[0];
    					endPosOfGrammer++;
    				}
    				endPosOfGrammer--;
    
    				int numOfPop = endPosOfGrammer - startPosOfGrammer - 1;
    				for (; numOfPop > 0; numOfPop--) {
    					symbolStack.pop();
    					statusStack.pop();
    				}
    				grammerInput[numOfGrammer-1].copy(temp, 1, startPosOfGrammer);
    				char charToPush = temp[0];
    				symbolStack.push(charToPush);
    
    				lastAction = 1;
    
    				//打印信息
    				cout << "归约操作:" << "使用第" << actionToDo[1] - 48 << "个产生式" << endl;
    				printStatusStack(statusStack);
    				printSymbolStack(symbolStack);
    				cout << endl;
    			}
    			else {
    				cout << "符号表识别错误" << endl;
    				getchar();
    				exit(0);
    			}
    			continue;
    		}
    		else if (lastAction == 1) {
    			int statusToGo = gotoMap.getElement(statusStack.getTop(), numOfInputStatus.getNumber(symbolStack.getTop()));
    			if (statusToGo == -1) {
    				return false;
    			}
    			statusStack.push(statusToGo);
    			lastAction = 0;
    			//打印信息
    			cout << "状态转移:" << "转移到第" << statusToGo << "状态" << endl;
    			cout << endl;
    			continue;
    		}
    	}
    }
    
    void makeAnalysisChart(string grammerInput[], ActionMap * actionMap, GotoMap * gotoMap, 
    						NumOfInputChar * numOfInputChar, NumOfInputStatus * numOfInputStatus, int numOfGrammer) {	
    	//构造Clousure, s代表S', 其余为大写S
    	//首先构造最基本的0与1号状态
    	int numOfClousure = 0;
    	Clousure clousure[MAXNUMOFCLOUSURE];
    	clousure[0].numOfItem = 1;
    	clousure[0].grammer[0].posOfDot = 1;
    	clousure[0].grammer[0].item = "s.S";
    	clousure[1].numOfItem = 1;
    	clousure[1].grammer[0].item = "sS.";
    	clousure[1].grammer[0].posOfDot = 2;
    
    	int numOfInitClo = 2;
    	for (int i = 0; i < numOfGrammer; i++) {
    		char chs[MAXNUMOFCHAR];
    		int numOfCh = 0;
    		for (int j = 0; j<MAXNUMOFCHAR; j++) {
    				char temp[1];
    				grammerInput[i].copy(temp, 1, j);
    				if (temp[0] == ';') {
    					break;
    				}
    				chs[j] = temp[0];
    				numOfCh = j;
    			}
    		for (int j = 2; j <= numOfCh+1; j++) {
    			clousure[numOfInitClo].numOfItem = 1;
    			bool b = false;
    			for (int k = 0; k <= numOfCh+1; k++) {
    				if (k == j) {
    					b = true;
    					clousure[numOfInitClo].grammer[0].item[j] = '.';
    					continue;
    				}
    				if (b) {
    					clousure[numOfInitClo].grammer[0].item[k] = chs[k-1];
    				}
    				else {
    					clousure[numOfInitClo].grammer[0].item[k] = chs[k];
    				}
    			}
    			clousure[numOfInitClo].grammer[0].posOfDot = j;
    			numOfInitClo++;
    		}
    	}
    
    	while (numOfClousure < numOfInitClo) {
    		int lastNumOfItem = clousure[numOfClousure].numOfItem;
    		while (1) {
    			char toDoChar = clousure[numOfClousure].grammer[clousure[numOfClousure].numOfItem - 1].item[clousure[numOfClousure].grammer[clousure[numOfClousure].numOfItem - 1].posOfDot + 1];
    			if (toDoChar == '\0') {
    				numOfClousure++;
    				break;
    			}
    			for (int i = 0; i < numOfGrammer; i++) {
    				char temp[1];
    				grammerInput[i].copy(temp, 1, 0);
    				char firstGrammerChar = temp[0];
    
    				if (firstGrammerChar == toDoChar) {
    					stringstream stream;
    					stream << firstGrammerChar;
    					string itemToInsert = stream.str() + '.';
    					bool ifExist = false;
    					for (int k = 1; ; k++) {
    						char tempChs[1];
    						grammerInput[i].copy(tempChs, 1, k);
    						char tempCh = tempChs[0];
    						if (tempCh == ';') {
    							break;
    						}
    						itemToInsert = itemToInsert + tempCh;
    					}
    					for (int k = 0; k < clousure[numOfClousure].numOfItem; k++) {
    						if (itemToInsert == clousure[numOfClousure].grammer[k].item) {
    							ifExist = true;
    							break;
    						}
    					}
    					if (ifExist) {
    						continue;
    					}
    
    					clousure[numOfClousure].grammer[clousure[numOfClousure].numOfItem].item = itemToInsert;
    					clousure[numOfClousure].grammer[clousure[numOfClousure].numOfItem].posOfDot = 1;
    					clousure[numOfClousure].numOfItem++;
    
    				}
    			}
    
    			if (lastNumOfItem == clousure[numOfClousure].numOfItem) {
    				numOfClousure++;
    				break;
    			}
    			lastNumOfItem = clousure[numOfClousure].numOfItem;
    
    		}
    	}
    
    	cout << "计算得出的闭包:" << endl << endl;
    	for (int ik = 0; ik < numOfInitClo; ik++) {
    		cout << "Clousure" << ik << ":" << endl;
    		for (int j = 0; j < clousure[ik].numOfItem; j++) {
    			cout << clousure[ik].grammer[j].item[0] << "->";
    			for (int i = 1; i <= clousure[ik].grammer[j].item.length(); i++) {
    				cout << clousure[ik].grammer[j].item[i];
    			}
    			cout << endl;
    		}
    	}
    	cout << endl;
    
    	//下面构造DFA
    	DFAMap * dfaMap = new DFAMap(numOfInitClo);
    	for (int n = 0; n < numOfInitClo; n++) {
    		for (int m = 0; m < clousure[n].numOfItem; m++) {
    			string itemToCal = clousure[n].grammer[m].item;
    			char chToMove = clousure[n].grammer[m].item[clousure[n].grammer[m].posOfDot+1];//需要使用的符号
    			if (chToMove == '\0') {
    				continue;
    			}
    			itemToCal[clousure[n].grammer[m].posOfDot+1] = '.';
    			itemToCal[clousure[n].grammer[m].posOfDot] = chToMove;
    			for (int t = 0; t < numOfInitClo; t++) {
    				for (int e = 0; e < clousure[t].numOfItem; e++) {
    					string itemToCmp = clousure[t].grammer[e].item;
    					//cout << itemToCal.c_str() << "==" << itemToCmp.c_str() << "=" << endl;
    					if (strcmp(itemToCal.c_str() , itemToCmp.c_str()) == 0) {
    						//cout << "OK"<< endl;
    						dfaMap->insert(n, t, chToMove);
    					}
    				}
    			}
    		}
    	}
    
    	//下面构造分析表
    	for (int k = 0; k < numOfInitClo; k++) {
    		if (k == 1) {//第1号一定是sS.
    			actionMap->insert(k, numOfInputChar->getNumber('#'), ACCUTATE);
    			continue;
    		}
    		for (int g = 0; g < clousure[k].numOfItem; g++) {
    			string tempItem = clousure[k].grammer[g].item;
    			if (tempItem[clousure[k].grammer[g].posOfDot+1] == '\0') {
    				tempItem[clousure[k].grammer[g].posOfDot] = '\0';
    				for (int h = 0; h < numOfGrammer; h++) {
    					string tempGrammmer = grammerInput[h];
    					tempGrammmer[tempGrammmer.length() - 1] = '\0';
    					if (strcmp(tempGrammmer.c_str(), tempItem.c_str()) == 0) {
    						//k状态 全部为R(h+1)
    						string str = "R" + to_string(h+1);
    						for (int v = 0; v < numOfInputChar->getSum(); v++) {
    							actionMap->insert(k, v, str);
    						}
    						break;
    					}
    				}
    				continue;
    			}
    			char tempCh = tempItem[clousure[k].grammer[g].posOfDot + 1];
    			if (numOfInputChar->getNumber(tempCh) >= 0) {
    				for (int d = 0; d < numOfClousure; d++) {
    					if (dfaMap->getElement(k, d) == tempCh) {
    						string tempStr = "S"+ to_string(d);
    						actionMap->insert(k, numOfInputChar->getNumber(tempCh), tempStr);
    					}
    				}
    				continue;
    			}
    			if (numOfInputStatus->getNumber(tempCh) >= 0) {
    				for (int d = 0; d < numOfClousure; d++) {
    					if (dfaMap->getElement(k, d) == tempCh) {
    						gotoMap->insert(k, numOfInputStatus->getNumber(tempCh),d);
    					}
    				}
    				continue;
    			}
    			cout << endl << "识别符号出错!" << endl;
    			exit(0);
    		}
    	}
    }
    
    int main()
    {
    	int symbolNum = 0;
    	string inputSymbol[MAXNUM];
    	getInputSymbol(inputSymbol, &symbolNum);
    	cout << "输入序列:" << endl;
    	for (int i = 0; i <= symbolNum; i++) {
    		cout << inputSymbol[i];
    	}
    	cout << endl << endl;
    
    	int grammerNum;
    	string grammerInput[MAXNUM];
    	getGrammer(grammerInput, &grammerNum);
    	cout << "语法序列:" << grammerNum << "个" << endl;
    	for (int i = 0; i < grammerNum; i++) {
    		cout << grammerInput[i] << endl;
    	}
    	cout << endl;
    
    	cout << "构造语法分析表......" << endl << endl;
    	ActionMap *action = new ActionMap(7, 3);//7个状态, 3个终结符
    	NumOfInputChar *numOfInputChar = new NumOfInputChar;//与上面相对应的终结符集合
    	numOfInputChar->inset('a');
    	numOfInputChar->inset('b');
    	numOfInputChar->inset('#');
    	
    	GotoMap *gotoMap = new GotoMap(7, 2);//7个状态,2个非终结符
    	NumOfInputStatus *numOfInputStatus = new NumOfInputStatus;//非终结符集合
    	numOfInputStatus->inset('S');
    	numOfInputStatus->inset('B');
    	
    	makeAnalysisChart(grammerInput, action, gotoMap, numOfInputChar, numOfInputStatus, grammerNum);
    
    	//Test
    	cout << "Action表:" << endl;
    	for (int i = 0; i < 7; i++) {
    		for (int j = 0; j < 3; j++) {
    			cout << action->getElement(i, j) << " ";
    		}
    		cout << endl;
    	}
    	cout << endl;
    
    	cout << "Goto表:" << endl;
    	for (int i = 0; i < 7; i++) {
    		for (int j = 0; j < 2; j++) {
    			cout << gotoMap->getElement(i, j) << " ";
    		}
    		cout << endl;
    	}
    	cout << endl;
    	
    	cout << "语法分析表构造完毕......" << endl << endl;
    
    	cout << "开始语法分析......" << endl << endl;
    	StatusStack *statusStack = new StatusStack;
    	SymbolStack *symbolStack = new SymbolStack;
    
    	bool result = grammerAnalysis(inputSymbol, *action, *gotoMap,
    									*statusStack, *symbolStack,
    									*numOfInputStatus, *numOfInputChar,
    									grammerInput);
    
    	if (result) {
    		cout << endl << "成功完成语法分析!"  << endl << endl;
    	}
    	else {
    		cout << endl << "语法分析失败!" << endl << endl;
    	}
    	cout << "结束语法分析......" << endl;
    	
    	getchar();
    	return 0;
    }
    

    最后的结果大家可以看一下:

    输入序列:
    bab#
    
    语法序列:3个
    S->BB;
    B->aB;
    B->b;
    
    构造语法分析表......
    
    计算得出的闭包:
    
    Clousure0:
    s->.S
    S->.BB
    B->.aB
    B->.b
    Clousure1:
    s->S.
    Clousure2:
    S->B.B
    B->.aB
    B->.b
    Clousure3:
    S->BB.
    Clousure4:
    B->a.B
    B->.aB
    B->.b
    Clousure5:
    B->aB.
    Clousure6:
    B->b.
    
    Action表:
    S4 S6 err
    err err acc
    S4 S6 err
    R1 R1 R1
    S4 S6 err
    R2 R2 R2
    R3 R3 R3
    
    Goto表:
    1 2
    -1 -1
    -1 3
    -1 -1
    -1 5
    -1 -1
    -1 -1
    
    语法分析表构造完毕......
    
    开始语法分析......
    
    移进操作:移进b
    状态栈的内容为:
    0 6
    符号栈的内容为:
    # b
    
    归约操作:使用第3个产生式
    状态栈的内容为:
    0
    符号栈的内容为:
    # B
    
    状态转移:转移到第2状态
    
    移进操作:移进a
    状态栈的内容为:
    0 2 4
    符号栈的内容为:
    # B a
    
    移进操作:移进b
    状态栈的内容为:
    0 2 4 6
    符号栈的内容为:
    # B a b
    
    归约操作:使用第3个产生式
    状态栈的内容为:
    0 2 4
    符号栈的内容为:
    # B a B
    
    状态转移:转移到第5状态
    
    归约操作:使用第2个产生式
    状态栈的内容为:
    0 2
    符号栈的内容为:
    # B B
    
    状态转移:转移到第3状态
    
    归约操作:使用第1个产生式
    状态栈的内容为:
    0
    符号栈的内容为:
    # S
    
    状态转移:转移到第1状态
    
    
    成功完成语法分析!
    
    结束语法分析......
    
    

    最后祝大家学习愉快,大家加油!

    展开全文
  • c++实现lr1分析器

    2020-07-21 09:59:33
    c++实现LR1文法分析,简洁的方式实现编译原理中的LR1分析器
  • 具体要求 已知文法G[E]: E->E+T | T ...(2)根据测试样例及你建立的LR分析表,用c++完成语法分析器的设计。 测试样例 要求格式完全一致,第一行为输入,第二行为要求的输出,共四组样例。 a1 ...
  • 【HIT哈工大编译原理实验】词法分析程序java 【编译原理】求first集合的代码实现java 【编译原理】求GOTO图的代码实现java 【编译原理】LL(1)分析法代码 以及一些关于编译的说明博客……自己按照日期找一下把~! 接...
  • 根据LR分析法的原理,对指定文法构造识别活前缀的DFA,做出相应的LR分析表,并编程实现相应的语法分析程序。或根据预测分析法的原理,对指定文法构造预测分析表,并编程实现相应的语法分析程序。 二、实验原理 1.所谓...
  • 从new.txt文件中读入写好的由正规表达式(a|b)*(aa|bb)(a|b)*所转化的正规文法(右线性),自动构造项目集族,生成LR分析表,并对输入的字符串通过LR分析表进行分析,输出分析过程,指出错误
  • asdadad
  • 编译原理LR(0)分析方法(c++实现) 【编译原理】SLR(1)分析方法(c++实现)   代码 和SLR的区别其实只是DFA中多了一个搜索符,构建分析表的时候规约项的列是相应的搜索符而已 代码基本上就在SLR的代码上...
  • 编译原理-LR0语法分析-java
  • LR(1)语法分析器-QT,C++

    2020-07-30 23:31:26
    基于QT,C++实现LR(1)语法分析器。输入终结符、非终结符和项目集可以得到语法分析表,然后可以对字符串分析。界面随便写了写,没写分辨率适应屏幕。打开可能怪怪的,去UI调调就好。
  • 写在前面:本博客为本人原创,严禁任何形式的转载!本博客只允许放在博客园(.cnblogs.com),如果您在其他网站看到... ...  基于C++语言实现的PL/0语言的算术表达式的自下而上的语法分析程序。该语言的其他语法...
  • LR0语法分析器.zip

    2020-06-03 23:32:33
    编译原理与技术LR0语法分析器实验C语言源码,能用于大多数LR型文法分析,仅需简单的修改便可以运行。
  • 直接输入根据己知文法构造的LR(0)分析表,对于输入的文法和符号串,所编制的语法分析程序应能正确判断此串是否为文法的句子,并要求输出分析过程。 #include<bits/stdc++.h> using namespace std; const ...
  • 实现了三种语法分析程序,即LL1、SLR1和LR1语法分析程序,对满足条件的输入文法能够自动的生成该文法的语法分析程序并执行分析过程,输出所采用的产生式。源代码 对于LL1语法分析程序有以下功能(要求输入文法为...
  • 基本流程 输入文法->拓广文法->求项目集规范族->GO[I,a]转移函数->构造DFA(识别活前缀的自动机->LR(0)分析表->LR(0)分析输入串 代码 c++实现
  • 编译原理语法分析LR1

    2008-11-10 18:29:00
    // LR1.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "CharStack.h"#include "IntStack.h"#include #include #include #include struct BNFNODE // 产生式节点{char ...
  • printf("请输入保存分析结果的文件名:"); scanf("%s",filename); if((fout=fopen(filename,"w"))==NULL) { printf("不能打开文件.\n"); return; } getsym(); //读第一个单词,将单词类别放入sym中 E(); ...
1 2 3 4 5 ... 20
收藏数 1,337
精华内容 534
关键字:

编译原理lr语法分析器c++实现