编译原理第五次实验

里面内容仅供学习参考, 可以基于此代码进行修改加工

LR语法分析学习笔记

LR(0)语法分析程序的设计

测试环境: dev

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
 
///表格数组                a       b        c       d       #      E      A       B
char LR0[50][50][100] = {{"S2"   ,"S3"   ,"null", "null" ,"null" ,"1"    ,"null" ,"null"},///   0
                         {"null" ,"null" ,"null", "null" ,"acc " ,"null" ,"null" ,"null"},///   1
                         {"null" ,"null" ,"S4"  , "S10"  ,"null" ,"null" ,"6"    ,"null"},///   2
                         {"null" ,"null" ,"S5"  , "S11"  ,"null" ,"null" ,"null" ,"7"   },///   3
                         {"null" ,"null" ,"S4"  , "S10"  ,"null" ,"null" ,"8"    ,"null"},///   4
                         {"null" ,"null" ,"S5"  , "S11"  ,"null" ,"null" ,"null" ,"9"   },///   5
                         {"r1"   ,"r1"   ,"r1"  , "r1"   ,"r1"   ,"null" ,"null" ,"null"},///   6
                         {"r2"   ,"r2"   ,"r2"  , "r2"   ,"r2"   ,"null" ,"null" ,"null"},///   7
                         {"r3"   ,"r3"   ,"r3"  , "r3"   ,"r3"   ,"null" ,"null" ,"null"},///   8
                         {"r5"   ,"r5"   ,"r5"  , "r5"   ,"r5"   ,"null" ,"null" ,"null"},///   9
                         {"r4"   ,"r4"   ,"r4"  , "r4"   ,"r4"   ,"null" ,"null" ,"null"},///   10
                         {"r6"   ,"r6"   ,"r6"  , "r6"   ,"r6"   ,"null" ,"null" ,"null"},///   11
                          };
char L[200]="abcd#EAB";    ///列判断依据
int  del[10]={0,2,2,2,1,2,1};//0-6号文法每个文法长度
char head[20]={'S','E','E','A','A','B','B'};
stack<int>con;    ///状态栈
stack<char>cmp;   ///符号栈
char cod[300]="0";///初始状态栈对应输出数组
int cindex = 0;
char sti[300]="#";///初始符号栈对应输出数组
int sindex = 0;
int findL(char b)///对应列寻找
{
    for(int i = 0; i <= 7; i++)
    {
        if(b==L[i])
        {
            return i;
        }
    }
    return -1;
}
void error(int x, int y)       ///报错输出
{
    printf("第%d行%c列为空!",x,L[y]);
}
 
int calculate(int l, char s[])
{
    int num = 0;
    for(int i = 1; i < l; i ++)
    {
        num =  num*10+(s[i]-'0');
    }
    return num;
}
void analyze(char str[],int len)///分析主体过程
{
    int cnt = 1;
    printf("步骤      状态栈    符号栈    输入串    ACTION    GOTO\n");
    int LR = 0;
    while(LR<=len)
    {
        printf("(%d)       %-10s%-10s",cnt,cod,sti);///步骤,状态栈,符号栈输出
        cnt++;
        for(int i = LR; i < len; i++)///输入串输出
        {
            printf("%c",str[i]);
        }
        for(int i = len-LR; i<10;i++)printf(" ");
 
        int x = con.top();///状态栈栈顶
        int y = findL(str[LR]);///待判断串串首
 
        if(strcmp(LR0[x][y],"null")!=0)
        {
            int l = strlen(LR0[x][y]);///当前Ri或Si的长度
 
            if(LR0[x][y][0]=='a')///acc
            {
                printf("acc        \n");///ACTION与GOTO
                return ;
            }
            else if(LR0[x][y][0]=='S')///Si
            {
                printf("%-10s \n",LR0[x][y]);///ACTION与GOTO
                int t = calculate(l,LR0[x][y]);///整数
                con.push(t);
                sindex++;
                sti[sindex] = str[LR];
                cmp.push(str[LR]);
                if(t<10)
                {
                    cindex++;
                    cod[cindex] = LR0[x][y][1];
                }
                else
                {
                    int k = 1;
                    cindex++;
                    cod[cindex] = '(';
                    while(k<l)
                    {
                        cindex++;
                        cod[cindex] = LR0[x][y][k];
                        k++;
                    }
                    cindex++;
                    cod[cindex] = ')';
                }
                LR++;
            }
            else if(LR0[x][y][0]=='r')///ri,退栈,ACTION和GOTO
            {
                printf("%-10s",LR0[x][y]);
                int t = calculate(l,LR0[x][y]);
                int g = del[t];
                while(g--)
                {
                    con.pop();
                    cmp.pop();
                    sti[sindex] = '\0';
                    sindex--;
                }
                g = del[t];
                while(g>0)
                {
                    if(cod[cindex]==')')
                    {
                        cod[cindex]='\0';
                        cindex--;
                        for(;;)
                        {
                            if(cod[cindex]=='(')
                            {
                                cod[cindex]='\0';
                                cindex--;
                                break;
                            }else
                            {
                                cod[cindex]='\0';
                                cindex--;
                            }
                        }
                        g--;
                    }else
                    {
                        cod[cindex] = '\0';
                        cindex--;
                        g--;
                    }
                }///
                cmp.push(head[t]);
                sindex++;
                sti[sindex] = head[t];
                x = con.top();
                y = findL(cmp.top());
                t = LR0[x][y][0]-'0';
                con.push(t);
                cindex++;
                cod[cindex] = LR0[x][y][0];
                printf("%-10d\n",t);
            }else
            {
                int t = LR0[x][y][0]-'0';
                char ch = ' ';
                printf("%-10c%-10d\n",ch,t);
                con.push(t);
                cindex++;
                cod[cindex] = LR0[x][y][0];
                sindex++;
                sti[sindex] = 'E';
                LR++;
            }
        }else
        {
            error(x,y);
            return ;
            ///报错
        }
    }
 
}
void chart()///测试表函数
{
    printf("-\ta\tb\tc\td\t#\tE\tA\tB\n");
    for(int i = 0; i <= 11; i++)
    {
        printf("%d",i);
        for(int j = 0 ; j <= 8; j++)
            printf("\t%s",LR0[i][j]);
            cout<<endl;
    }
    cout<<endl;
}
int main()
{
    chart();
    con.push(0);
    cmp.push('#');
    char str[200];///输入串
    cout<<"请输入字符串(带#):"<<endl;
    cin>>str;
    int len = strlen(str);
    analyze(str,len);
    return 0;
}
/*
输入:bccd#
输出:
步骤      状态栈    符号栈    输入串    ACTION    GOTO
(1)       0         #         bccd#     S3
(2)       03        #b        ccd#      S5
(3)       035       #bc       cd#       S5
(4)       0355      #bcc      d#        S11
(5)       0355(11)  #bccd     #         r6        9
(6)       03559     #bccB     #         r5        9
(7)       0359      #bcB      #         r5        7
(8)       037       #bB       #         r2        1
(9)       01        #E        #         acc
输入:abc
输出:
步骤      状态栈    符号栈    输入串    ACTION    GOTO
(1)       0         #         abc       S2
(2)       02        #a        bc        第2行b列为空!
输入:abc#
输出:
步骤      状态栈    符号栈    输入串    ACTION    GOTO
(1)       0         #         abc#      S2
(2)       02        #a        bc#       第2行b列为空!
输入:E#
输出:
步骤      状态栈    符号栈    输入串    ACTION    GOTO
(1)       0         #         E#                  1
(2)       01        #E        #         acc
输入:cabc#
输出:
步骤      状态栈    符号栈    输入串    ACTION    GOTO
(1)       0         #         cabc#     第0行c列为空!
输入:bccdd#
输出:
步骤      状态栈    符号栈    输入串    ACTION    GOTO
(1)       0         #         bccdd#    S3
(2)       03        #b        ccdd#     S5
(3)       035       #bc       cdd#      S5
(4)       0355      #bcc      dd#       S11
(5)       0355(11)  #bccd     d#        r6        9
(6)       03559     #bccB     d#        r5        9
(7)       0359      #bcB      d#        r5        7
(8)       037       #bB       d#        r2        1
(9)       01        #E        d#        第1行d列为空!
*/

LR(0)文法分析法(算法描述和C++代码实现

测试环境: dev

#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" );
    }
}
输入:
5
S->E
E->aAcBe
A->b
A->Ab
B->d 

LR(0)分析方法(c++实现)

测试环境: dev

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long LL;
const int INF=0x7fffffff;
const int MAX_N=10000;
int num_of_a,num_of_A,num_of_S,totalnum;
//小写字母个数、大写字母个数、推导式个数、最终结点总数
char a[50];//字母
char S[50][50];//推导式
bool pushed[100];//访问一个结点的时候,再往外拓展时记录非终结符是否已经被push过
int ans[100][100];
char analyse[50];//分析串
int stack1[50];
char stack2[50];
char stack3[50];
int L1,L2,L3;//三个栈的长度
map<char,int>M;
map<char,int>::iterator m;
struct node{//结点
    int id;//编号
    int num;//包含的推导式个数
    char s[20][50];
};
queue<node>q;//结点型队列
node N[100];
int numN=0;
void outputnd(node k){//输出一个结点的s
    for(int i=0;i<k.num;i++){
        cout<<k.s[i]<<endl;
    }
}
void outputlb(){//输出一个数组的s
    cout<<"链表"<<endl;
    for(int i=0;i<numN;i++){
        outputnd(N[i]);
        cout<<endl;
    }
}
bool samenode(node x,node y){//比较两个node是否一样
     if(x.num!=y.num)return 0;//如果两个node包含的s数量不同直接输出不同
     for(int i=0;i<x.num;i++){//暴力比较
        int flag=0;
        for(int j=0;j<y.num;j++){
            if(strcmp(x.s[i],y.s[j])==0){
                flag=1;
                break;
            }
        }
        if(flag==0)return 0;
     }
     return 1;
}
void init(){//初始化
    totalnum=0;//结点数量
    while(!q.empty())q.pop();//情况队列
    memset(S,0,sizeof(S));
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            ans[i][j]=-10000;
        }
    }
    M.clear();//清空映射
}
void input(){//顾名思义,输入数据
    printf("请输入终结符的个数:");
    scanf("%d",&num_of_a);
    printf("请输入%d个终结符(小写字母):",num_of_a);
    for(int i=0;i<num_of_a;i++){
        scanf(" %c",&a[i]);
        M.insert(make_pair(a[i],i));//建立映射
    }
    a[num_of_a]='#';
    M.insert(make_pair(a[num_of_a],num_of_a));
    printf("请输入非终结符的个数(不包含起始符):");
    scanf("%d",&num_of_A);
    printf("请输入%d个非终结符(大写字母):",num_of_A);
    for(int i=0;i<num_of_A;i++){
        scanf(" %c",&a[num_of_a+1+i]);
        M.insert(make_pair(a[num_of_a+1+i],num_of_a+1+i));
    }
    printf("请输入初始推导式的个数:");
    scanf("%d",&num_of_S);
    printf("下面%d行每行请输入1个推导式:前后用下划线“_”链接(起始为S):\n",num_of_S);
    for(int i=0;i<num_of_S;i++){
        scanf("%s",S[i]);
        for(int j=strlen(S[i]);j>=3;j--){
            S[i][j]=S[i][j-1];
        }
        S[i][2]='.';
    }
}
node pushback(char p,node f){//node f里把所有p开头的推导式push进去
    for(int i=0;i<num_of_S;i++){
        if(S[i][0]==p){
            strcpy(f.s[f.num++],S[i]);
        }
    }
    return f;
}
void bfs(){//宽度优先搜索
    node aa;//声明一个空的状态
    aa.num=0;
    aa.id=totalnum++;//初始化num和id
    aa=pushback('S',aa);//把S开头的推导式放到这个起始结点里
    memset(pushed,0,sizeof(pushed));//用于记录哪些字母被一次性push过,避免重复push
    for(int j=0;j<aa.num;j++){//把需要push的大写字母开头的推导式push进去
        if(aa.s[j][3]>='A'&&aa.s[j][3]<='Z'&&pushed[aa.s[j][3]]==0){
            aa=pushback(aa.s[j][3],aa);
            pushed[aa.s[j][3]]=1;
        }
    }
    q.push(aa);//把起始点放入队列
    N[numN++]=aa;//这个东西记录已经存在过的node
    while(!q.empty()){//只要队列不为空,就一直运行,下面就是宽搜了
        node cur=q.front();
        q.pop();//取出头结点保存然后pop掉
        for(int i=0;i<num_of_a+num_of_A+1;i++){//搜索所有字母
            if(i==num_of_a)continue;//这个位置存储#,所以为了提高程序运行效率,直接过掉
            node newnode;//声明一个可能要添加的新结点
            newnode.num=0;
            newnode.id=-1;
            memset(pushed,0,sizeof(pushed));
            for(int j=0;j<cur.num;j++){//搜索当前刚取出的队列头结点的所有推导式
                for(int k=2;k<strlen(cur.s[j]);k++){//对于每个推导式从左到右爆搜
                    if(cur.s[j][strlen(cur.s[j])-1]=='.')continue;//如果最后一个位置是“.”直接continue
                    if(cur.s[j][k]=='.'&&cur.s[j][k+1]==a[i]){//如果“.”后面正好是当前要搜索的字母
                        if(newnode.id==-1)newnode.id=-2;//这个node可能要被添加了,一个字母加一遍就好,以前没加过就是-1
                        char news[50];//声明一个新的字符串
                        strcpy(news,cur.s[j]);//保留现场,先把找到的这条copy下来
                        swap(news[k],news[k+1]);//把“.”和它后面的字母互换位置
                        strcpy(newnode.s[newnode.num++],news);//把处理好的news粘贴到newnode里面
                        if(news[k+2]>='A'&&news[k+2]<='Z'&&pushed[news[k+2]]==0){//如果发现“.”后面的后面跟着大写字母还要麻烦一下
                            newnode=pushback(news[k+2],newnode);//把所有的以这个大写字母开头的推导式push到newnode里面
                            pushed[news[k+2]]=1;//之前没注释的memset(pushed,0,sizeof(pushed));此时派上了用场
                        }
                    }
                }
            }
            if(newnode.id!=-1){//如果找到了可能需要push的结点
                int flag=-1;//我还需要看看这个结点是否已经存在过,是不是形成了环
                for(int p=0;p<numN;p++){//爆搜一下曾经的结点
                    if(samenode(newnode,N[p])==1){//比较一下是不是一样
                        flag=p;//如果找到一样的,就break,并且保留那个一样的结点的位置
                        break;
                    }
                }
                if(flag!=-1){//发现了一样的结点
                    ans[cur.id][i]=N[flag].id;//最终结果里体现一下
                }
                if(flag==-1){//没发现有一样的,那就是新的结点了,把他push到队列里面去
                    newnode.id=totalnum++;
                    q.push(newnode);
                    N[numN++]=newnode;
                    ans[cur.id][i]=newnode.id;
                }
            }
        }
    }
}
void build_table(){//处理表格
    for(int i=0;i<totalnum;i++){
        int flag=0;
        for(int j=0;j<num_of_A+num_of_a+1;j++){
            if(ans[i][j]!=-10000){
                flag=1;
                break;
            }
        }
        if(flag==0){
            char news[50];
            strcpy(news,N[i].s[0]);
            news[strlen(news)+1]='\0';
            for(int k=strlen(news)-1;k>=3;k--){
                news[k]=news[k-1];
            }
            news[2]='.';
            for(int j=0;j<num_of_S;j++){
                if(!strcmp(news,S[j])){
                    if(j!=0){
                        for(int k=0;k<num_of_a+1;k++){
                            ans[i][k]=-1*j;
                        }
                        break;
                    }
                    for(int k=0;k<num_of_a+1;k++){//r0 用-9999表示,s0用0表示
                        ans[i][k]=-9999;
                    }
                    break;
                }
            }
        }
    }
}
void output_action(int act){
    if(act>=0)cout<<"S"<<setw(3)<<act;
    else if(act==-10000){
        cout<<setw(4)<<" ";
    }
    else if(act==-9999){
        cout<<setw(4)<<"r0";
    }
    else{
        cout<<"r"<<setw(3)<<-1*act;
    }
}
void output_table(){//输出表格
    cout<<left<<"项目  ";
    for(int i=0;i<num_of_A+num_of_a+1;i++){
        cout<<setw(4)<<a[i];
    }cout<<endl;
    for(int i=0;i<totalnum;i++){
        cout<<setw(6)<<i;
        for(int j=0;j<num_of_A+num_of_a+1;j++){
            output_action(ans[i][j]);
        }cout<<endl;
    }
}
int step,action,GOTO;
void output_stacks(){
    cout<<endl<<"步骤:"<<step++<<endl;
    cout<<"状态栈/符号栈/输入串:";
    for(int j=0;j<L1;j++){
        cout<<stack1[j]<<" ";
    }cout<<"     ";
    for(int j=0;j<L2;j++){
        cout<<stack2[j];
    }cout<<"     ";
    for(int j=L3-1;j>=0;j--){
        cout<<stack3[j];
    }cout<<endl;
}
int judge(){
    m=M.find(stack3[L3-1]);//用映射的方式找到要分析的字母是第几个,节省时间提升程序运行效率
    if(m==M.end()){
        return 0;
    }
    action=ans[stack1[L1-1]][m->second];
    if(action==-10000)return 0;
    if(action>=0){
        GOTO=-10000;
        return 1;
    }
    if(action<0&&action>-9999){
        return 2;
    }
    if(action==-9999){
        return 3;
    }
    return 0;
}
void solve(){
    cout<<endl<<"分析字符串"<<endl;
    char c;
    while(1){
        cout<<endl<<"输入一行字符串并且以#结尾:"<<endl;
        memset(analyse,0,sizeof(analyse));
        int i=0;
        while(scanf(" %c",&c)&&c!='#'){
            analyse[i++]=c;
        }
        step=1;
        memset(stack1,0,sizeof(stack1));
        memset(stack2,0,sizeof(stack2));
        memset(stack3,0,sizeof(stack3));
        L1=0,L2=0,L3=0;
        stack1[L1++]=0;
        stack2[L2++]='#';
        stack3[L3++]='#';
        for(int j=strlen(analyse)-1;j>=0;j--){
            stack3[L3++]=analyse[j];
        }
        while(1){
            int oprt=judge();
            if(oprt==0){
                cout<<"error!"<<endl;
                break;
            }
            if(oprt==1){
                output_stacks();
                cout<<"ACTION:";
                output_action(action);
                cout<<"     GOTO:blank"<<endl;
                stack1[L1++]=action;
                stack2[L2++]=stack3[--L3];
            }
            if(oprt==2){
                output_stacks();
                cout<<"ACTION:";
                output_action(action);
                int ct=0;
                for(int j=strlen(S[action*-1])-1;j>=0;j--){
                    if(S[action*-1][j]!='.')ct++;
                    if(S[action*-1][j]=='.')break;
                }
                L1-=ct;
                L2-=ct;
                stack2[L2++]=S[-1*action][0];
                m=M.find(stack2[L2-1]);
                GOTO=ans[stack1[L1-1]][m->second];
                stack1[L1++]=GOTO;
                cout<<"     GOTO:"<<GOTO<<endl;
            }
            if(oprt==3){
                output_stacks();
                if(L3==1){
                    cout<<"ACTION:acc!"<<endl;
                }
                else{
                    cout<<"error!"<<endl;
                }
                break;
            }
        }
    }
}
int main(){
    init();//初始化
    input();//输入
    bfs();//核心程序宽度优先搜索生成表格
    build_table();
    output_table();//输出表格
    solve();
    return 0;
}
//测试数据
/*
4
abcd
3
EAB
7
S_E
E_aA
E_bB
A_cA
A_d
B_cB
B_d
bccd#
4
abcd
3
EAB
7
S_E
E_aB
E_bA
B_bB
A_aA
B_d
A_c
5
abcde
3
EAB
8
S_E
E_aB
E_bB
B_cA
B_cB
A_dB
A_d
B_e
*/

LR(1)分析法设计与实现

测试环境: dev

语法制导的语义计算

编译原理三——语义分析知识点

代码优化

测试环境: dev

#include <iostream>
#include <cstdlib>
#include <string.h>
using namespace std;
int i=1; 
int j=0,n=0; 
int p; 
int m=1;
int Ti=0;
char prog[100]; 
char ch;
char syn[20],sem[50][3]; 
void SEM(void)
 {
	int i,j;
	for(i=0;i<50;i++)
		for(j=0;j<3;j++)
			sem[i][j]='\0';
}
struct quat//四元式结构
{
	char result[8];
	char ag1[8];
	char op;
	char ag2[8];
}quad[25],newquad[15];
struct Ni//节点结构
{
	int pre[2];
	char op;
	char bz[25][8];
}N[25];
void newN(void)
{
	int l,j;
	i++;
	for(j=0;j<25;j++)
	{
		for(l=0;l<8;l++)
		{
			N[i-1].bz[j][l]='\0';
		}
	}
	for(j=0;j<2;j++)
		N[i-1].pre[j]=0;
	N[i-1].op='\0';
}
void dagt(void);
 void newquat(void);
void fuzhi(void);
//递归语法分析生成中间代码
void E(void);
void T(void);
void F(void);
void pop0(char sz[]);
void push0(char sz[],char x);
void pop1(char sz[50][3]);
void push1(char sz[50][3],char x[3]);
void quat1(void); 
void quat0(char w);
void print1(void);
void print2(void);
char *newT(void)
{
	char *p;
	char m[8];
	p=(char *)malloc(8);
	Ti++;
	itoa(Ti,m,10);
	strcpy(p+1,m);
	p[0]='t';
	return(p);
}
int main()
{
	p=0;
	syn[0]='#';
	SEM();
	sem[0][0]='#';
	cout<<"请输入表达式:"<<endl; 
	do
	{
		cin.get(ch);
		if(ch != '\n')   prog[p++]=ch;
	}while(ch!='#');
	p=0;
	ch=prog[p++];
	while(ch!='#')
	{
		fuzhi();
	}
	print1();
	dagt();
	newquat();
	print2();
	return 0;	
}
void fuzhi(void)
{
	char temp[3];
	temp[0]='\0';
	temp[1]='\0';
	temp[2]='\0';
	if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A'))
	{
		temp[0]=ch;
		push1(sem,temp);
		ch=prog[p++];
		if(ch=='=')
		{
			push0(syn,ch);
			ch=prog[p++];
			E();
			if(m==0)
			{
				cout<<"错误1!"<<endl;
				system("pause");           /////
				return;
			}
			if(ch==';')
			{
				ch=prog[p++];
				quat1();
			}
			else
			{
				cout<<"错误2!"<<endl;
				system("pause"); 
				return;
			}
		}
		else
			{
				cout<<"错误3!"<<endl;
				system("pause"); 
				return;
			}
	}
	else
	{
				cout<<"错误4!"<<endl;
				printf("%d",ch);
				system("pause"); 
				return;
	}
}
//E、T、F是递归下降子程序的语法分析
void E(void)
{
	char w;
	T();
	while(ch=='+'||ch=='-')
	{
		push0(syn,ch);
		w=syn[strlen(syn)-1];
		ch=prog[p++];
		T();
		quat0(w);
	}
}
void T(void)
{
	char w;
	F();
	while(ch=='*'||ch=='/')
	{
		push0(syn,ch);
		w=syn[strlen(syn)-1];
		ch=prog[p++];
		F();
		quat0(w);
	}
}
void F(void)
{
	char temp[3];
	temp[0]='\0';
	temp[1]='\0';
	temp[2]='\0';
	if(ch=='(')
	{
		ch=prog[p++];
		E();
		if(ch==')')
		{
			ch=prog[p++];
		}
		else m=0;
	}
	else if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0'))
	{
		temp[0]=ch;
		push1(sem,temp);
		ch=prog[p++];
	}
		 else m=0;
}
void push0(char sz[],char x)
{
	int top;
	top=strlen(sz);
	sz[top]=x;
	top++;
	sz[top+1]='\0';
}
void pop0(char sz[])
{
	int top;
	top=strlen(sz)-1;
	sz[top]='\0';
}
void push1(char sz[50][3],char x[3])
{
	int top=1;
	while(sz[top][0])
		top++;
	strcpy(sz[top],x);
	top++;
	sz[top+1][0]='\0';
}
void pop1(char sz[50][3])
{
	int top=1;
	while(sz[top][0])
		top++;
	top--;
	sz[top][0]='\0';
	sz[top][1]='\0';
	sz[top][2]='\0';
}
void quat0(char w)
{
	int top=1,i;
	char *p;
	while(sem[top][0])
		top++;
	strcpy(quad[j].ag1,sem[top-2]);
	strcpy(quad[j].ag2,sem[top-1]);
	quad[j].op=w;
	p=newT();
	for(i=0;i<8;i++)
		quad[j].result[i]=p[i];
	pop1(sem);
	top--;
	pop1(sem);
	top--;
	for(i=0;i<3;i++)
		sem[top][i]=quad[j].result[i];
	sem[top][2]='\0';
	j++;
}
void quat1(void)
{
	char ag2[8];
	int top,i;
	top=1;
	while(sem[top][0])
		top++;
	ag2[0]='_';
	for(i=1;i<8;i++)
		ag2[i]='\0';
	strcpy(quad[j].ag1,sem[top-1]);
	strcpy(quad[j].ag2,ag2);
	quad[j].op='=';
	strcpy(quad[j].result,sem[top-2]);
	pop0(syn);
	pop1(sem);
	pop1(sem);
	j++;
}
void print1(void)
{
	int i;
	cout<<"原来的四元组:"<<endl;
	for(i=0;i<j;i++)
		cout<<(i+1)<<"、("<<quad[i].op<<","<<quad[i].ag1<<","<<quad[i].ag2<<","<<quad[i].result<<")"<<endl;
}
void dagt(void)
{
	int m,n,top,l,tag=0,tag1=0,tag2=0;
	char temp;
	for(m=0;m<j;m++)
	{
		tag=0;
		for(n=i;n>0;n--)
			for(l=0;l<25;l++)
			{
				if(strcmp(quad[m].ag1,N[n-1].bz[l])==0)
				{
					tag=n;
					break;
				}
			}
		if(tag!=0)
		{
			tag1=tag-1;
			if('0'<quad[m].ag1[0]&&quad[m].ag1[0]<'9')
				goto N3;
			else goto N3;
		}
		else
		{
			if('0'<quad[m].ag1[0]&&quad[m].ag1[0]<'9')
			{
				if(quad[m].ag2[0]!='_')
				{
					if('0'<quad[m].ag2[0]&&quad[m].ag2[0]<'9')
					{
						quad[m].ag1[0]=quad[m].ag1[0]-'0';
						quad[m].ag2[0]=quad[m].ag2[0]-'0';
						switch(quad[m].op)
						{
							case '+':temp=quad[m].ag1[0]+quad[m].ag2[0];break;
							case '-':temp=quad[m].ag1[0]-quad[m].ag2[0];break;
							case '*':temp=quad[m].ag1[0]*quad[m].ag2[0];break;
							case '/':temp=quad[m].ag1[0]/quad[m].ag2[0];break;
							default:break;
						}
						tag=0;
						for(n=i;n>0;n--)
							for(l=0;l<25;l++)
							{
								if(strcmp(quad[m].result,N[n-1].bz[l])==0)
									{
										tag=n;
										break;
									}
							}
						if(tag!=0)
							continue;
						else
						{
							newN();
							N[i-1].bz[0][0]=temp+'0' ;
							strcpy(N[i-1].bz[1],quad[m].result);
							continue;
						}
					}
					else 
					{
						newN();
						tag1=i-1;
						strcpy(N[i-1].bz[0],quad[m].ag1);
						goto N2;
					}
				}
				else goto N1;
			}
			else 
N1:			
			{
				newN();
				strcpy(N[i-1].bz[0],quad[m].ag1);
				tag1=i-1;
N3:
				if(quad[m].ag2[0]=='_')
				{
					tag=0;
					for(n=i;n>0;n--)
						for(l=0;l<25;l++)
						{
							if(strcmp(quad[m].result,N[n-1].bz[l])==0)
								{
									tag=n;
									top=l;
									break;
								}
						}
					if(tag!=0)
					{
						for(l=top+1;l<25;l++)
						{
							strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]);
						}
						goto N5;
					}
					else
					{
N5:
						if(N[i-1].bz[0][1])
						{
							if(quad[m].result[1])
							{
								top=0;
								while(N[tag1].bz[top][0])
									top++;
								strcpy(N[tag1].bz[top],quad[m].result);
								continue;
							}
							else
							{
								temp=N[i-1].bz[0][1];
								strcpy(N[i-1].bz[0],quad[m].result);
								top=0;
								while(N[tag1].bz[top][0])
									top++;
								N[i-1].bz[top][0]='t';
								N[i-1].bz[top][1]=temp;
								continue;
							}
						}
						else
						{
							top=0;
							while(N[tag1].bz[top][0])
								top++;
							strcpy(N[tag1].bz[top],quad[m].result);
							continue;
						}
					}
				}	
				else
N2:
				{
					tag=0;
					for(n=i;n>0;n--)
						for(l=0;l<25;l++)
						{
							if(strcmp(quad[m].ag2,N[n-1].bz[l])==0)
							{
								tag=n;
								break;
							}
						}
					if(tag!=0)
					{
						tag2=tag-1;
						tag=0;
						for(n=i;n>0;n--)
							if((N[n-1].pre[0]==tag1)&&(N[n-1].pre[1]==tag2))
							{
								tag=n;
								break;
							}
						if(tag!=0)
						{
							if(N[tag-1].op==quad[m].op)
							{
								if(!N[tag-1].bz[0][1])
								{
									top=1;
									while(N[tag-1].bz[top][0])
										top++;
									strcpy(N[tag-1].bz[top],quad[m].result);
								}
								else if(!quad[m].result[1])
								{
									temp=N[tag-1].bz[0][1];
									strcpy(N[tag-1].bz[0],quad[m].result);
									top=1;
									while(N[tag-1].bz[top][0])
										top++;
									N[tag].bz[top][0]='t';
									N[tag].bz[top][1]=temp;
								}
									 else
									 {
										 top=1;
										 while(N[tag-1].bz[top][0])
											 top++;
										 strcpy(N[tag-1].bz[top],quad[m].result);
									 }
								continue;
							}
							else
							{
								newN();
								N[i-1].op=quad[m].op;
								strcpy(N[i-1].bz[0],quad[m].result);
								N[i-1].pre[0]=tag1;
								N[i-1].pre[1]=tag2;
							}
							continue;
						}
						else
						{
							newN();
							N[i-1].op=quad[m].op;
							strcpy(N[i-1].bz[0],quad[m].result);
							N[i-1].pre[0]=tag1;
							N[i-1].pre[1]=tag2;
							continue;
						}
					}
					else
					{
						newN();
						strcpy(N[i-1].bz[0],quad[m].ag2);
						tag2=i-1;
						tag=0;
						for(n=i;n>0;n--)
							for(l=0;l<25;l++)
								if(strcmp(quad[m].result,N[n-1].bz[l])==0)
								{
									tag=n;
									top=l;
									break;
								}
						if(tag==0)
						{
							newN();
							strcpy(N[i-1].bz[0],quad[m].result);
							N[i-1].op=quad[m].op;
							N[i-1].pre[0]=tag1;
							N[i-1].pre[1]=tag2;
							continue;
						}
						else
						{							
							for(l=top+1;l<25;l++)
							{
								strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]);
							}
							newN();
							strcpy(N[i-1].bz[0],quad[m].result);
							N[i-1].op=quad[m].op;
							N[i-1].pre[0]=tag1;
							N[i-1].pre[1]=tag2;
						}
					}
				}
			}
		}
	}
}
void newquat(void)
{
	int l,top;
	for(l=1;l<i;l++)
	{
		if(N[l].pre[1]==0&&N[l].pre[0]==0)
		{
			if(!N[l].bz[0][1])
			{
				if(('0'<N[l].bz[0][0])&&(N[l].bz[0][0]<'9'))
					continue;
				else
				{		
					for(top=1;N[l].bz[top][1];top++)
					{
						if(!N[l].bz[top][0])
						{
							strcpy(newquad[n].ag1,N[l].bz[0]);
							newquad[n].ag2[0]='_';
							newquad[n].op='=';
							strcpy(newquad[n].result,N[l].bz[top]);
							n++;
						}
					}
				}
			}
			else continue;
		}
		else if(N[l].pre[1]!=0||N[l].pre[0]!=0)
		{
			strcpy(newquad[n].ag1,N[N[l].pre[0]].bz[0]);
			strcpy(newquad[n].ag2,N[N[l].pre[1]].bz[0]);
			newquad[n].op=N[l].op;
			strcpy(newquad[n].result,N[l].bz[0]);
			n++;
			if(!N[l].bz[0][1])
				{		
					for(top=1;N[l].bz[top][0];top++)
					{
						if(!N[l].bz[top][1])
						{
							strcpy(newquad[n].ag1,N[l].bz[0]);
							newquad[n].ag2[0]='_';
							newquad[n].op='=';
							strcpy(newquad[n].result,N[l].bz[top]);
							n++;
						}
					}
				}
		}
	}
}
void print2(void)
{
	int i;
	cout<<"优化后的代码:"<<endl;
	for(i=0;i<n;i++)
		cout<<(i+1)<<"、("<<newquad[i].op<<","<<newquad[i].ag1<<","<<newquad[i].ag2<<","<<newquad[i].result<<")"<<endl;
}

请输入表达式:

a=1+2-b;
b=3*5+c;
c=3/1*a;#

编译原理(8):代码优化知识点

编译原理实验六—代码优化

编译原理之代码优化

In.txt
T0:=3.14
T1:=2*T0
T2:=R+r
A:=T1*T2 
B:=A
T3:=2*T0   
T4:=R+r  
T5:=T3*T4  
T6:=R-a[B]
B:=T5*T6
Out.txt
T0:=3.14
T1:=6.28
T3:=6.28
T2:=R+r
T4:=T2
A:=6.28*T2
T5:=A
T6:=R-a[B]
B:=A*T6
#include <cstring>
#include <fstream>
#include <iostream>
#include<stdlib.h>
using namespace std;

struct DagNode
{
	int fatherNum;					//是否有父节点
	bool isSingle;					//是否是单分支
	bool isLeaf;
	bool isVal;
	double value;
	char opt;
	int NodeNum;					//该节点的编号
	int RChild,LChild;				//左右子节点的编号
	int flagNum;					//依附于该节点的变量数
	string flags[20];				//依附于该节点的变量
	DagNode()
	{
		isVal = false;
		fatherNum = 0;
		flagNum = 0;
		isLeaf = false;
		isSingle = false;
	}

};

struct VarNode
{
    string str;						
	int flagNode;
	VarNode()
	{
		flagNode = 0;
	}
};

DagNode *dag[100];
VarNode var[100];
int dagNum,varNum;
ifstream fin;
ofstream fout;
string str1,str2,str3;
char opt;
bool BisNew,CisNew;


void PrintStr(string str)
{
	int i,l;
	double k;
	char s[100];
	l = str.length();
	if (l>0 && str[0]>=48 && str[0]<=57)
	{
		for(i=0; i<l; i++)
			s[i] = str[i];
		s[i] = '\0';
		k = atof(s);
		fout<<k;
		return;
	}
	for (i=0; i<l; i++)
		fout<<str[i];

}
bool isOpt(char ch)
{
	switch (ch)
	{
	case '+': return true;
	case '-': return true;
	case '*': return true;
	case '/': return true;
	case '[': return true;
	}
	return false;

}

double Calc(double a, char op, double b)
{
	switch (op)
	{
	case '+': return a+b;
	case '-': return a-b;
	case '*': return a*b;
	case '/': return a/b;
	}
	return 0;
}
bool strEqual(string str1,string str2)
{
	int i,l;
	l = str1.length();
	i = str2.length();
	if (l!=i) return false;
	for (i=0; i<l; i++)
	  if (str1[i]!=str2[i]) return false;
	return true;
}
int findVar(string str)
{
	double k;
	int i;
	char s[100];
	string ss;
	ss = str;
	if (str.length()>0 && str[0]>=48 && str[0]<=57)
	{
		for(i=0; i<str.length(); i++)
			s[i] = str[i];
		s[i]='\0';
		k = atof(s);
		sprintf(s,"%lf",k);
		ss="";
		for (int i=0; i<strlen(s);i++)
			ss+=s[i];
	}
	for (i=1; i<=varNum; i++)
	{
		if (strEqual(ss,var[i].str))
			return i;
	}
	return 0;
}
void work4(int n)
{
	int a,k;
	int i;
	char s[100];
	a = findVar(str1);
	if (a==0)
	{
		varNum++;
		a = varNum;
		var[a].str = str1;
		var[a].flagNode = n;
		dag[n]->flagNum++;
		dag[n]->flags[dag[n]->flagNum] = str1;
	}
	else
	{
		k = var[a].flagNode;
		if (!dag[k]->isLeaf)
		{
			for (i=1; i<=dag[k]->flagNum; i++)
			  if (strEqual(str1,dag[k]->flags[i]))
			  {
				  for (int j=i+1; j<=dag[k]->flagNum; j++)
					  dag[k]->flags[j-1] = dag[k]->flags[j];
				  break;
			  }
			  dag[k]->flagNum--;
		}
		var[a].flagNode = n;
		dag[n]->flagNum++;
		dag[n]->flags[dag[n]->flagNum] = str1;
	}
}
void work32(int b,int c)
{
	int i,k1,n,k2;
	k1 = var[b].flagNode;
	k2 = var[c].flagNode;
	n = 0;
	for (i=1; i<=dagNum; i++)
		if (dag[i]->opt == opt && dag[i]->LChild ==k1 && dag[i]->RChild ==k2)
		{
			n = i;
			break;
		}
	if (n==0)
	{
		dagNum++;
		n = dagNum;
		dag[n] = new DagNode();
		dag[n]->LChild = k1;
		dag[n]->RChild = k2;
		dag[k1]->fatherNum++;
		dag[k2]->fatherNum++;
		dag[n]->opt = opt;
	}
	work4(n);
}
void work31(int b)
{
	int i,k,n;
	k = var[b].flagNode;
	n = 0;
	for (i=1; i<=dagNum; i++)
		if (dag[i]->opt == opt && dag[i]->isSingle && dag[i]->RChild ==k)
		{
			n = i;
			break;
		}
	if (n==0)
	{
		dagNum++;
		n = dagNum;
		dag[n] = new DagNode();
		dag[n]->isSingle = true;
		dag[n]->RChild = k;
		dag[k]->fatherNum++;
		dag[n]->opt = opt;
	}
	work4(n);

}
void work24(int b, int c)
{
	double p;
	int k;
	int i;
	char s[100];
	string str;
	p = Calc(dag[var[b].flagNode]->value,opt,dag[var[c].flagNode]->value);
	if (CisNew)
	{
       varNum--;
	   delete(dag[dagNum]);
	   dagNum--;
	}
	if (BisNew)
	{
       varNum--;
	   delete(dag[dagNum]);
	   dagNum--;
	}
	sprintf(s,"%lf",p);
	str = "";
	for (i=0; i<strlen(s); i++)
		str+=s[i];
	k= findVar(str);
	if (k ==0)
	{
		dagNum++;
		varNum++;
		k = varNum;
		var[k].str = str;
		var[k].flagNode = dagNum;
		dag[dagNum] = new DagNode();
		dag[dagNum]->isVal = true;
		dag[dagNum]->value =  p;
		dag[dagNum]->flags[1] = str;
		dag[dagNum]->flagNum = 1;
		dag[dagNum]->isLeaf = true;
	}
	work4(var[k].flagNode);
}
void work23(int b)
{
	double p;
	int k;
	int i;
	char s[100];
	string str;
	p = Calc(0,opt,dag[var[b].flagNode]->value);
	if (BisNew)
	{
       varNum--;
	   delete(dag[dagNum]);
	   dagNum--;
	}
	sprintf(s,"%lf",p);
	str = "";
	for (i=0; i<strlen(s); i++)
		str+=s[i];
	k= findVar(str);
	if (k ==0)
	{
		dagNum++;
		varNum++;
		k = varNum;
		var[k].str = str;
		var[k].flagNode = dagNum;
		dag[dagNum] = new DagNode();
		dag[dagNum]->isVal = true;
		dag[dagNum]->value =  p;
		dag[dagNum]->flags[1] = str;
		dag[dagNum]->flagNum = 1;
		dag[dagNum]->isLeaf = true;
	}
	work4(var[k].flagNode);
}
void work22(int b, int c)
{
	if (dag[var[c].flagNode]->isVal && dag[var[b].flagNode]->isVal)
		work24(b,c);
	else
		work32(b,c);
}
void work21(int b)
{
	if (dag[var[b].flagNode]->isVal)
		work23(b);
	else
		work31(b);
}


void work1()
{
	string str;
	bool isSin;
	int i,b,c;
	int ListType;
	char st[100];
	char s[100];

	int len;
	while(!fin.eof())
	{
		isSin = true;
		fin.getline(st,80);
		len = strlen(st);
        if (len<1) break;
		str = "";
		i = 0;
		while (st[i]!=':')
		{
			if (st[i]!=' ')
			  str += st[i];
			i++;
		}
	    str1 = str;
		str = "";
		i = i+2;
		while (!isOpt(st[i])&& i<len)
		{
		   if (st[i]!=' ')
			str += st[i];
			i++;
		}
		str2 = str;
		if (i<len)
		{
			isSin = false;
			opt = st[i];
			if (opt=='[')
			  len--;
			str = "";
			i++;
		    while (i<len)
			{
			   if (st[i]!=' ')
				str += st[i];
				i++;
			}
			str3 = str;
			if (str2.length() ==0) 
				ListType = 1;
			else
			    ListType = 2;
		}
		else
		{
			ListType = 0;
		}
		b= findVar(str2);
		BisNew = false;
		if (b ==0)
		{
			BisNew = true;
			dagNum++;
			varNum++;
			b = varNum;
			var[b].str = str2;
			var[b].flagNode = dagNum;
			dag[dagNum] = new DagNode();
			if (str2[0]>=48 && str2[0]<=57)
			{
				dag[dagNum]->isVal = true;
				for ( i=0; i<str2.length(); i++)
					s[i] = str2[i];
				s[i] = '\0';
				dag[dagNum]->value = atof(s);
			}
			dag[dagNum]->flags[1] = str2;
			dag[dagNum]->flagNum = 1;
			dag[dagNum]->isLeaf = true;
		}
		switch(ListType)
		{
		case 0: work4(var[b].flagNode);
			    break;
		case 1: work21(b);
			    break;
		case 2: 
			{
				c= findVar(str3);
				CisNew = false;
				if (c ==0)
				{
					CisNew = true;
					dagNum++;
					varNum++;
					c = varNum;
					var[c].str = str3;
					var[c].flagNode = dagNum;
					dag[dagNum] = new DagNode();
					if (str3[0]>=48 && str3[0]<=57)
					{
						dag[dagNum]->isVal = true;
						for ( i=0; i<str3.length(); i++)
							s[i] = str3[i];
						s[i] = '\0';
						dag[dagNum]->value = atof(s);
					}
					dag[dagNum]->flags[1] = str3;
					dag[dagNum]->flagNum = 1;
					dag[dagNum]->isLeaf = true;
				}
				work22(b,c);
			}
		}
	}
}
int main()
{
	int k=0;
	char s[100];
	int i,j;
	string str;
	fin.open("In.txt",ios::in);
	fout.open("Out.txt",ios::out);
	work1();
	for (i=1; i<=dagNum; i++)
	{
		if (dag[i]->flagNum==0 && dag[i]->fatherNum>0)
		{
          ltoa(k,s,10);
		  str = "Var";
		  j = 0;
		  while (s[j]!='\0')
		  {
			  str+=s[j];
			  j++;
		  }
		  dag[i]->flagNum = 1;
		  dag[i]->flags[1] = str;
		  k++;
		}
	}
	for (i=1; i<=dagNum; i++)
	{
		if (dag[i]->isLeaf)
		{
			if (dag[i]->flagNum>1)
			{
				for (j=2; j<=dag[i]->flagNum; j++)
				{
					PrintStr(dag[i]->flags[j]);
					fout<<":=";
					PrintStr(dag[i]->flags[1]);
					fout<<endl;
				}
			}
		}
		else
		{
				PrintStr(dag[i]->flags[1]);
				fout<<":=";
				if (!dag[i]->isSingle)
					PrintStr(dag[dag[i]->LChild]->flags[1]);
				fout<<dag[i]->opt;
				PrintStr(dag[dag[i]->RChild]->flags[1]);
				if (dag[i]->opt=='[')
					fout<<']';
				fout<<endl;
			   for (j=2; j<=dag[i]->flagNum; j++)
			   {
				   PrintStr(dag[i]->flags[j]);
				   fout<<":=";
				   PrintStr(dag[i]->flags[1]);
				   fout<<endl;
			   }

		}
	}
	fin.close();
	fout.close();
}
付费阅读
此内容为付费阅读,请付费后查看
© 版权声明
THE END
喜欢就支持以下吧
点赞2赞赏
分享
评论 共1条

请登录后发表评论

    • dzjw
    • 膜拜大佬,谢谢大佬帮我渡过最后一次实验

      1年前