算符优先系列之(二)算符优先关系表

Myth丶恋晨 2022-05-23 08:17 168阅读 0赞

**算符优先系列之(二)算符优先关系表**

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description  
学过编译原理的菊苣们都知道算符优先文法，作为一个有点深度的分析方法，我们怎么能只止步于理论呢，实践才是王道哦。

已知文法G\[S\]的表达式，求算符优先关系表。因为某些特殊的原因，我们在这规定一下输入输出格式。

已知文法G\[S\]为：

S\`->\#S\#(拓展文法,不是题目给出的文法)

S->a|@|(T)

T->T,S|S

表达式算符优先关系表中从左到右(从上到下)的顺序为从表达式文法中从左到右从上到下的顺序即为

a @ ( ) , \# （我们默认把\#放在最右边或者最下边）

Input  
多组输入。第一行输入一个n，表示表达式的个数，接下来n行每行一个表达式(记得还有一个要在自己程序中添加的拓展文法哦)

Output  
根据上述的格式，输出算符优先关系表(输出的格式用水平制表符\\t)

Sample Input  
2  
S->a|@|(T)  
T->T,S|S  
Sample Output  
a @ ( ) , \#  
a > > >  
@ > > >  
( < < < = <  
) > > >  
, < < < > >

# < < < = #

Hint

Source

#include <stdio.h>
    #include <math.h>
    #include <string.h>
    #include <stdlib.h>
    #include <iostream>
    #include <sstream>
    #include <algorithm>
    #include <set>
    #include <queue>
    #include <stack>
    #include <map>
    #include <bitset>
    #pragma comment(linker, "/STACK:102400000,102400000")
    typedef long long LL;
    const int inf=0x3f3f3f3f;
    const double pi= acos(-1.0);
    const double esp=1e-6;
    using namespace std;
    
    const int Maxn=110;
    const int maxn=20;
    char str[maxn][Maxn];//输入文法
    char st[maxn];//输入串
    char stac[maxn];//模拟栈的数组
    char nstr[maxn][maxn];//储存转化文法
    char mstr[maxn][maxn];
    char fin[maxn];//存储终结符
    char firstvt[maxn][maxn],lastvt[maxn][maxn];
    char cmp[maxn][maxn];//存储表中的比较符
    int firstflag[maxn],lastflag[maxn];//非终结符的firstvt,lastvt是否求出
    int fcnt[maxn],lcnt[maxn];//非终结符firsvt和lastvt的个数
    int is_fin(char c) { //判断终结符
        for(int i=0; fin[i]!='\0'; i++) {
            if(fin[i]==c)
                return 1;
        }
        return 0;
    }
    int site(char c) { //求在表中的下标
        for(int i=0; fin[i]!='\0'; i++) {
            if(fin[i]==c)
                return i;
        }
    }
    
    void get_firstvt(char s,int t) { //求s非终结符的firstvt值
        int i,j,ii,jj,tt;
        for(i=0; i<t; i++) {
            if(str[i][0]==s)
                break;
        }
        if(!firstflag[i]) {
            int k=fcnt[i];
            for(j=0; str[i][j]!='\0'; j++) {
                if(j==2||str[i][j]=='|') {
                    if(is_fin(str[i][j+1])) {
                        firstvt[i][k++]=str[i][j+1];
                    } else {
                        if(is_fin(str[i][j+2])) {
                            firstvt[i][k++]=str[i][j+2];
                        }
                        if(str[i][j+1]!=s) {
                            get_firstvt(str[i][j+1],t);
                            for(ii=0; ii<t; ii++) {
                                if(str[ii][0]==str[i][j+1])
                                    break;
                            }
                            for(jj=0; jj<fcnt[ii]; jj++) {
                                for(tt=0; tt<k; tt++) {
                                    if(firstvt[i][tt]==firstvt[ii][jj])
                                        break;
                                }
                                if(tt==k) {
                                    firstvt[i][k++]=firstvt[ii][jj];
                                }
                            }
                        }
                    }
                }
            }
            firstvt[i][k]='\0';
            fcnt[i]=k;
            firstflag[i]=1;
        }
    }
    
    void output_firstvt(int T) { //输出firstvt集
        for(int i=0; i<T; i++) {
            get_firstvt(str[i][0],T);
        }
    
    }
    
    void get_lastvt(char s,int t) { //求s非终结符的lastvt值
        int i,j,ii,jj,tt;
        for(i=0; i<t; i++) {
            if(str[i][0]==s)
                break;
        }
        if(!lastflag[i]) {
            int k=lcnt[i];
            for(j=0; str[i][j]!='\0'; j++) {
                if(str[i][j+1]=='|'||str[i][j+1]=='\0') {
                    if(is_fin(str[i][j])) {
                        lastvt[i][k++]=str[i][j];
                    } else {
                        if(is_fin(str[i][j-1])) {
                            lastvt[i][k++]=str[i][j-1];
                        }
                        if(str[i][j]!=s) {
                            get_lastvt(str[i][j],t);
                            for(ii=0; ii<t; ii++) {
                                if(str[ii][0]==str[i][j])
                                    break;
                            }
                            for(jj=0; jj<lcnt[ii]; jj++) {
                                for(tt=0; tt<k; tt++) {
                                    if(lastvt[i][tt]==lastvt[ii][jj])
                                        break;
                                }
                                if(tt==k) {
                                    lastvt[i][k++]=lastvt[ii][jj];
                                }
                            }
                        }
                    }
                }
            }
            lastvt[i][k]='\0';
            lcnt[i]=k;
            lastflag[i]=1;
        }
    }
    
    void output_lastvt(int T) { //输出lastvt集
        for(int i=0; i<T; i++) {
            get_lastvt(str[i][0],T);
        }
    
    }
    
    void get_table(int T,int cnt) { //得到表
        int x=0,y=0;
        int i,j,ii,jj;
        for(i=0; i<T; i++) {
            for(j=0; str[i][j]!='\0'; j++) {
                if(str[i][j]!='|')
                    nstr[x][y++]=str[i][j];
                else if(str[i][j]=='|') {
                    nstr[x][y]='\0';
                    x++;
                    y=0;
                    nstr[x][y++]=str[i][0];
                    nstr[x][y++]='-';
                    nstr[x][y++]='>';
                }
            }
            nstr[x][y]='\0';
            x++;
            y=0;
        }
        //对于S1->#S#;
        char a='#';
        cmp[site(a)][site(a)]='=';
        for(i=0; i<fcnt[0]; i++) {
            cmp[site(a)][site(firstvt[0][i])]='<';
        }
        for(i=0; i<lcnt[0]; i++) {
            cmp[site(lastvt[0][i])][site(a)]='>';
        }
        //对于初始的文法
        for(i=0; i<x; i++) {
            for(j=3; nstr[i][j+1]!='\0'; j++) {
                if(is_fin(nstr[i][j])&&is_fin(nstr[i][j+1]))
                    cmp[site(nstr[i][j])][site(nstr[i][j+1])]='=';
                if(is_fin(nstr[i][j])&&!is_fin(nstr[i][j+1])&&is_fin(nstr[i][j+2])&&nstr[i][j+2]!='\0')
                    cmp[site(nstr[i][j])][site(nstr[i][j+2])]='=';
                if(!is_fin(nstr[i][j])&&is_fin(nstr[i][j+1])) { //对于非终结符在终结符之前
                    for(ii=0; ii<T; ii++) {
                        if(str[ii][0]==nstr[i][j])
                            break;
                    }
                    for(jj=0; jj<lcnt[ii]; jj++)
                        cmp[site(lastvt[ii][jj])][site(nstr[i][j+1])]='>';
                }
                if(is_fin(nstr[i][j])&&!is_fin(nstr[i][j+1])) { //对于终结符在非终结符之前
                    for(ii=0; ii<T; ii++) {
                        if(str[ii][0]==nstr[i][j+1])
                            break;
                    }
                    for(jj=0; jj<fcnt[ii]; jj++)
                        cmp[site(nstr[i][j])][site(firstvt[ii][jj])]='<';
                }
            }
        }
        for(i=0; fin[i]!='\0'; i++)
            printf("\t%c",fin[i]);
        puts("");
        for(i=0; i<cnt; i++) {
            printf("%c\t",fin[i]);
            for(j=0; j<cnt; j++) {
                if(cmp[i][j]!=0)
                    printf("%c\t",cmp[i][j]);
                else
                    printf(" \t");
            }
            puts("");
        }
    
    }
    void output(int i,int j,char *str) {
        printf("\t");
        for(int ii=i; ii<=j; ii++)
            printf("%c",str[ii]);
    }
    
    int isDX(char c)
    {
        if(c>='A'&&c<='Z')
            return 1;
        return 0;
    }
    void exchange()
    {
        int ecnt=0;
        for(int i=0;i<10;i++){
            int mcnt=0;
            for(int j=3;nstr[i][j]!='\0';j++){
                if(isDX(nstr[i][j])&&strlen(nstr[i])!=4)
                    mstr[ecnt][mcnt++]='N';
                else if(!isDX(nstr[i][j]))
                    mstr[ecnt][mcnt++]=nstr[i][j];
                else{
                    break;
                }
            }
            mstr[ecnt][mcnt]='\0';
            if(strlen(mstr[ecnt])!=0)
            ecnt++;
        }
    }
    
    int main() {
        //freopen("D:\\input.txt","r",stdin);
        //freopen("D:\\output.txt","w",stdout);
        int T;
        while(~scanf("%d",&T)){
        int cnt=0;//终结符的个数
        memset(firstflag,0,sizeof(firstflag));
        memset(lastflag,0,sizeof(lastflag));
        memset(cmp,0,sizeof(cmp));
        for(int i=0; i<T; i++) {
            scanf("%s",str[i]);
            fcnt[i]=lcnt[i]=0;
        }
        for(int i=0; i<T; i++) {
            for(int j=0; str[i][j]!='\0'; j++) {
                if((str[i][j]<'A'||str[i][j]>'Z')&&(str[i][j]!='-'&&str[i][j]!='>')&&str[i][j]!='|')
                    fin[cnt++]=str[i][j];
            }
        }
        fin[cnt++]='#';
        fin[cnt]='\0';
        output_firstvt(T);
        output_lastvt(T);
        get_table(T,cnt);
        }
        return 0;
    }