美文网首页
编译原理构造LR0分析表

编译原理构造LR0分析表

作者: 吃茶的武士 | 来源:发表于2019-06-24 10:43 被阅读0次

    代码已经调试通,直接从实验报告复制粘贴来的,可能会有中文编码问题,调成utf-8就行。

    【实验名称】              LR(0)分析表的构造              

    【实验目的】

     结合书本上P135面LR(0)分析表构造知识,了解掌握LR(0)分析表构造过程,从构造闭包到构造分析表。为后面LR系列的文法打下基础。

    【实验原理】

     假设构造出来LR(0)项目规范族为C={I0,I1,IN},其中Ik为项目集名字,k为状态名称。S’->.S的项目的集合的Ik的下标k为分析器初始状态。分析表构造如下

    [if !supportLists](1) [endif]若项目A->a.ab属于Ik并且转换函数GO(Ik,a)=Ij,当a为终结符时,置action[k,a]为Sj,动作含义是将终结符号a移进符号栈,状态j进入状态栈(相当于在状态k时遇a转向状态j)。

    [if !supportLists](2) [endif]若项目A->a.属于Ik,则对任何终结符a与#号置ACTION[k,a]和ACTION[k,#]为rj,j为文法中某个归约产生式的序号。动作含义是用A规约a。并把状态栈指针后移|a|位

    [if !supportLists](3) [endif]若GOTO(Ik,A)=Ij,则置GOTO[k,A]为“j”,其中A为非终结符,表示当前状态是“k”时候遇到文法符号A时应该转向j,因此A移入文法符号栈,j移入状态栈。

    [if !supportLists](4) [endif]若项目“S’->S”属于Ik,应置ACTION[k,#]为acc,表示接受

    [if !supportLists](5) [endif]凡不可用上述方法的,应该报错。

    【实验内容】

    1.首先要确定是LR(0)文法,排除项目集中不应该含有‘移进-规约’或者‘归约-规约’冲突。这个自己设计一个简单文法就行

    2. 从拓展文法之后的开始符开始,先求出闭包之后的项目集,之后遍历项目集找出所有活前缀点之后的非终结符与终结符,找下一个项目集,如果有相同的非终结符,要把原来的项目集放入项目集族中,每次找下一个项目集都要检验项目集是否已存在,直到递归找到所有非终结符的带活前缀文法。在此过程中,检验项目集中是否规约移进同时存在,若存在会报错。同时,会把每个项目集之间的联系记录下来,用于分析表的构建。

    【小结或讨论】

    这次实验比较困难,需要结合一些习题来熟悉构造过程。还应该和后面的SLR文法,LR1文法,LALR1文法联系起来看,其实LR(0)文法是一个理想化的情况,因此文法构建的就比较简单才能验证。

    【实验截图】

    文法:

    S’->S

    S->A

    A->aA

    A->b

    结果是正确的,在第一个产生式“S->A”中接受最后的规约,acc

    代码:

    #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

    #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;

                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;

                str.erase ( str.begin()+x);

                str.insert ( str.begin()+x+1 , CH );

                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;

                    }

                 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 )

                {

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

        }

    //closure

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

    }

    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 , inti  , 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 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 );

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

                    bool flag = true;

                    if ( flag )

                        go[i][ch] = j;

                }

            }

        }

    }

    void make_table ( )

    {

        memset( Goto , -1 , sizeof ( Goto ) );

        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;

            }

        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];

                            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;

    }

    int main ( )

    {

        int n;

        char s[MAX];

        printf("输入以S为开始符的文法,请输入文法个数:");

        while ( ~scanf ( "%d" , &n ) )

        {    printf("请输入文法:\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 ) );

            }

            make_item();

            make_set();

            make_V();

            make_go();

            make_table();

        }

    }

    相关文章

      网友评论

          本文标题:编译原理构造LR0分析表

          本文链接:https://www.haomeiwen.com/subject/knlnqctx.html