精华内容
下载资源
问答
  • 算符优先分析

    2019-11-20 19:54:41
    算符优先分析 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 算法优先分析法是一种不太规范的自下而上分析方法,分析速度快,特别适用于表达式的分析。为了便于大家理解和实践算符优先分析法,...

    算符优先分析
    Time Limit: 1000 ms Memory Limit: 65536 KiB

    Problem Description
    算法优先分析法是一种不太规范的自下而上分析方法,分析速度快,特别适用于表达式的分析。为了便于大家理解和实践算符优先分析法,本题目先给出一个算符优先文法,请大家构造该文法的算符优先关系表。然后请对给定的输入串进行算符优先分析,判断其是否为该文法的一个句子。
    例如表达式文法:

    E→E+T |T
    
    T→T*F |F
    
        F→(E) | i
    

    该表达式文法是算符优先文法,其算符优先分析表为:
    在这里插入图片描述
    注意:构造算符优先分析表前,请先拓广文法,例如引入非终结符Q,令Q→#E#。

    Input
    输入数据有多行。
    第一行为一个整数n(n<=50),代表文法中产生式的个数,其中不包括拓广文法增加的产生式。
    接下来的n行,每行给出一个产生式。
    最后一行给出待分析的输入串,长度不超过50个符号。
    Output
    要求输出该文法的算符优先分析表,输出格式请参考上面的表格。
    算符优先分析表中算符的排列顺序为输入文法时终结符出现的顺序,#出现在最后。
    算符之间的优先关系,分别用=、<和>表示,代表相同、低于和高于的优先关系。
    第一行先输出一个空格,然后按顺序输出所有算符。
    第二行开始第一列为对应的算符,接着输出对应算法之间的优先关系。
    输出的最后一行表示对输入串的分析是否成功结束,如果成功分析结束输出Success,表示该输入串是文法的一个句子,否者输出Fail,表示该输入串不是文法的一个句子。
    Sample Input

    6
    E->E+T
    E->T
    T->T*F
    T->F
    F->(E)
    F->i
    i+i*i
    

    Sample Output

    +*()i#
    +><<><>
    *>><><>
    (<<<=< 
    )>> > >
    i>> > >
    #<<< <=
    Success
    
    #include <iostream>
    #include <string.h>
    using namespace std;
    string str[30][100];
    char st[30][100],st1[30][100],order[60],st2[100][2],st3[100],st4[100][2];
    int num[30],num1[30],bj1[30],bj2[150],sum[100][100],st3l,st4l;
    char Stack[100],sta[100];
    int top,top1,end1,number,bj0[150];
    void print(char a)
    {
        int b=a-'A';
        for(int i=0;i<num[b];i++)
        {
            if(st[b][i]>='A'&&st[b][i]<='Z')
                print(st[b][i]);
            else st3[st3l++]=st[b][i];
        }
    }
    void print1(char a)
    {
        int b=a-'A';
        for(int i=0;i<num1[b];i++)
        {
            if(st1[b][i]>='A'&&st1[b][i]<='Z')
                print1(st1[b][i]);
            else st3[st3l++]=st1[b][i];
        }
    }
    void print_stack()
    {
        for(int i=0;i<=top;i++)
            cout<<Stack[i];
    }
    void print_sta()
    {
        if(top1+1==end1) cout<<"#";
        for(int i=top1+1;i<end1;i++)
            cout<<sta[i];
    }
    int main()
    {
        int i,j,k,kk,m,n,nn,mm,bj,l,ll,bj3;
        char s;
        while(cin>>m)
        {
            memset(bj0,0,sizeof(bj0));    //test9
            l=ll=bj3=st4l=0;
            for(i=0;i<150;i++)
                bj2[i]=0;
            for(i=0;i<30;i++)
            {
                num[i]=0; num1[i]=0; bj1[i]=0;
            }
            string str1,str2;
            for(i=0;i<m;i++)
            {
                cin>>str1;
                if(i==0) s=str1[0];
                mm=str1[0]-'A';
                n=str1.size();
                str2=str1.substr(3,n);
                char *p=&str2[0];
    
                //const char *d="|";
                //p=strtok(str3,d);
                //while(p!=NULL)
                //{
                    bj=0;
                    nn=strlen(p);
                    if(nn==1)
                    {
                        st[mm][num[mm]]=p[0];num[mm]++;
                        st1[mm][num1[mm]]=p[0];num1[mm]++;
                        if(p[0]<'A'||p[0]>'Z')
                        {
    
                            bj0[p[0]]=1;     //test9
                            if(p[0]!='#')
                            {
                                order[l++]=p[0]; bj2[p[0]]=1;
                            }
                            else bj3=1;
                        }
                    }
                    else
                    {
                        int aa=0;char bb;
                        for(j=0;j<nn;j++)
                        {
                             if(p[j]<'A'||p[j]>'Z')
                             {
                                 bj0[p[j]]=nn;       //test9
                                 if(aa==0)
                                 {
                                     bb=p[j];aa=1;
                                 }
                                 else
                                 {
                                     st4[st4l][0]=bb;st4[st4l++][1]=p[j];
                                 }
                                 if(bj2[p[j]]==0)
                                 {
                                     if(p[j]!='#')
                                     {
                                         order[l++]=p[j];bj2[p[j]]=1;
                                     }
                                     else bj3=1;
                                 }
                                 if(bj!=1)
                                 {
                                     bj=1;st[mm][num[mm]]=p[j];num[mm]++;
                                 }
                             }
                             if(j>0)
                             {
                                 if((p[j]<'A'||p[j]>'Z')&&p[j-1]>='A'&&p[j-1]<='Z')
                                 {
                                     st2[ll][0]=p[j-1];st2[ll++][1]=p[j];continue;
                                 }
                                 if((p[j-1]<'A'||p[j-1]>'Z')&&p[j]>='A'&&p[j]<='Z')
                                 {
                                     st2[ll][0]=p[j-1];st2[ll++][1]=p[j];
                                 }
                             }
                        }
                        if(bj==0)
                        {
                            st[mm][num[mm]]=p[0];num[mm]++;
                        }
                        bj=0;
                        for(j=nn-1;j>=0;j--)
                        {
                             if(p[j]<'A'||p[j]>'Z')
                             {
                                 bj=1;st1[mm][num1[mm]]=p[j];num1[mm]++;break;
                             }
                        }
                        if(bj==0)
                        {
                            st1[mm][num[mm]]=p[0];num1[mm]++;
                        }
                    }
                    //p=strtok(NULL,d);
                //}
            }
            order[l++]='#';bj2['#']=1;
            st2[ll][0]='#';st2[ll++][1]=s;
            st2[ll][0]=s;st2[ll++][1]='#';
            memset(sum,0,sizeof(sum));
            for(i=0;i<ll;i++)
            {
                st3l=0;
                if(st2[i][0]>='A'&&st2[i][0]<='Z')
                {
                    print1(st2[i][0]);
                    for(j=0;j<l;j++)
                    {
                        if(st2[i][1]==order[j])
                        {
                            for(k=0;k<st3l;k++)
                            {
                                for(kk=0;kk<l;kk++)
                                {
                                    if(st3[k]==order[kk])
                                    {
                                        sum[kk][j]=3;break;
                                    }
                                }
                            }
                            break;
                        }
                    }
                }
                else
                {
                    print(st2[i][1]);
                    for(j=0;j<l;j++)
                    {
                        if(st2[i][0]==order[j])
                        {
                            for(k=0;k<st3l;k++)
                            {
                                for(kk=0;kk<l;kk++)
                                {
                                    if(st3[k]==order[kk])
                                    {
                                        sum[j][kk]=1;break;
                                    }
                                }
                            }
                            break;
                        }
                    }
                }
            }
            for(i=0;i<st4l;i++)
            {
                for(j=0;j<l;j++)
                {
                    if(st4[i][0]==order[j])
                    {
                        for(k=0;k<l;k++)
                        {
                            if(st4[i][1]==order[k])
                            {
                                sum[j][k]=2;break;
                            }
                        }
                        break;
                    }
                }
            }
            sum[l-1][l-1]=2;
            //test9
            cin>>sta;
            cout<<" ";
            for(i=0;i<l;i++)
                cout<<order[i];
            cout<<endl;
            for(i=0;i<l;i++)
            {
                cout<<order[i];
                for(j=0;j<l;j++)
                {
                    if(sum[i][j]==1)
                        cout<<"<";
                    else if(sum[i][j]==2)
                        cout<<"=";
                    else if(sum[i][j]==3)
                        cout<<">";
                    else cout<<" ";
                }
                cout<<endl;
            }
            int flag=0;
            end1=strlen(sta);
            sta[end1]='#';end1++;
            top=number=top1=0;
            Stack[0]='#';
            bj0['#']=1;
            /*for(i=0;i<150;i++)
                cout<<bj0[i]<<" ";
            cout<<endl;*/
            for(i=0;i<end1;i++)
            {
                if(bj0[sta[i]]==0)
                {
                    flag=1;break;
                }
            }
            while(top>=0)
            {
                if(flag==1) break;
                //number++;
                //cout<<number<<"\t";
                //print_stack();
                mm=-1;
                for(i=top;i>=0;i--)
                {
                    if(Stack[i]<'A'||Stack[i]>'Z')
                    {
                        mm=i;break;
                    }
                }
                if(mm==-1) {flag=1;break;}
                k=kk=-1;
                for(i=0;i<l;i++)
                {
                    if(order[i]==Stack[mm])
                    {
                        k=i;
                    }
                    if(order[i]==sta[top1])
                    {
                        kk=i;
                    }
                }
                if(k==-1||kk==-1)
                {
                    flag=1;break;
                }
                //cout<<"\t";
                if(sum[k][kk]==1)
                {
                    //cout<<"<\t";
                }
                else if(sum[k][kk]==2)
                {
                    //cout<<"=\t";
                }
                else if(sum[k][kk]==3)
                {
                    //cout<<">\t";
                }
                else
                {
                    flag=1;break;
                }
                //if(sta[top1]!='#') cout<<sta[top1]<<"\t";
                //else cout<<" \t";
                //print_sta();
                //cout<<"\t";
                if(sum[k][kk]==1)
                {
                    //cout<<"移进"<<endl;
                    top1++;
                    Stack[++top]=sta[top1-1];
                }
                else if(sum[k][kk]==2)
                {
                    if(sta[top1]!='#')
                    {
                        //cout<<"移进"<<endl;
                        top1++;
                        Stack[++top]=sta[top1-1];
                    }
                    else if(Stack[mm]=='#')
                    {
                        //cout<<"接受"<<endl;
                        break;
                    }
                }
                else if(sum[k][kk]==3)
                {
                    //cout<<"归约"<<endl;
                    top-=(bj0[Stack[mm]]-1);
                    Stack[top]='N';
                }
            }
            if(flag==0) cout<<"Success"<<endl;
            else cout<<"Fail"<<endl;
        }
        return 0;
    }
    
    展开全文
  • 第六章 自底向上优先分析 郑先容 回顾简单优先分析法 回顾简单优先分析法 简单优先分析算法的基本思想 算符优先分析法 直观的算符优先分析算符优先分析法 区别是什么 算符优先关系的产生 优先关系的有序性 i i i ...
  • 算符优先分析程序

    2016-05-22 23:00:21
    编写一个算符优先分析程序,能实现以下功能: 1. 输入文法,判断是否为算符文法。 2. 构造并输出文法的每个非终结符的FIRSTVT和LASTVT。 3. 构造并输出算符优先分析表,判断是否为算符优先文法,如果不是提示无法进行...
  • 算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理
  • 自下而上的分析法——算符优先分析

    万次阅读 多人点赞 2018-05-13 19:19:42
     算符优先分析法(Operator Precedence Parse)是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。  优点:简单,有效,适合表达式...

    概述

           算符优先分析法(Operator Precedence Parse)是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作。

           优点:简单,有效,适合表达式的分析。

           缺点:只适合于算符优先文法,是一个不大的文法类。

    名词解释

    定义:

        短语:设有文法G,S是开始符号,设abd是G的一个句型,若有SÞabd且AÞb则称b是句型abd关于A的短语

        直接短语:在上面定义中,如果A直接推出b,即AÞb,则称b是句型abd关于A®b的直接短语。

        句柄:一个句型的最左直接短语称为句柄。

        素短语:文法G某句型的一个短语是素短语,当且仅当它至少含有一个终结符,且除它自身之外不再含更小的素短语。

        最左素短语:在具有多个素短语的句型中处于最左边的那个素短语。

    求法:

        短语:从根结点出发一层一层地找出所有非叶子结点的非终结符,每一个非终结符延伸下去的所有叶子结点从左到右排列起来就是一个短语。

        直接短语:找出所有仅有两代的子树,并将它的所有叶子从左到右排列起来就是一个直接短语。

        句柄:从直接短语集合中找出最左边的短语。

        素短语:从短语集合中找出所有含有终结符的短语,然后选出除它自身之外不再含更小的素短语(这个小的概念是集合中没有被包含的元素,如有两个短语aAA和aAAA,aAA含于aAAA,所以aAA比aAAA小)

        最左素短语:从素短语集合中找出最左边的素短语。

    FIRSTVT集和LASTVT集

    FIRSTVT集

    定义:FIRSTVT(P)={a|P=>a…,或P=>Qa…,a属于VT,Q 属于VN}

    求法

        若P→a…或P→Qa…, 则a属于FIRSTVT(P);

        若P→Q…, 则FIRSTVT(Q)含于FIRSTVT(P);

        直至FIRSTVT(P)不再增大。

    LASTVT集

    定义:LASTVT(P)={a|P=>...a,或P=>…aQ,a含于VT,Q 含于VN}

    求法

        若P→...a或P→…aQ, 则a属于LASTVT(P);

        若P→...Q, 则LASTVT(Q)含于LASTVT(P);

        直至LASTVT(P)不再增大。

     

    构造算符优先关系表

    以以下文法为例:

            E→E+T|T

            T→T*F|F

            F→(E)|i

     

    终结符之间的优先关系

    对算符文法G,  a,b属于VT 定义

    (1)a=b:  G中有P→. . .ab. . .或P→. . .aQb. . .

    (2)a<b:  G中有P→. . .aQ. . .且Q=>b…或Q=>Rb...

    (3)a>b:  G中有P→. . .Qb. . . 且Q=>. ..a或Q=>…aR

     

    算符优先关系表的构造

    (1)  在文法中添加E→#E#。

    (2)  求出FIRSTVT和LASTVT集

    (3)  找出所有终结符,并画出关系表的结构

    (4)  从文法中找出形为aQb(终结符+非终结符+终结符)和ab(终结符+终结符)的部分,本例中为(E)和#E#,然后在(和)与#和#相应的表格填=。

    (5)  从文法中找出形为aQ(终结符+非终结符)的部分,a与Q的FIRSTVT集合中每一个元素在表格中的交叉点填小于号。

        i.找出形为aQ的部分

        

        ii.填小于号(终结符为竖排,非终结符中的元素为横排,以横排为基准填符号)

        

    (6)  从文法中找出形为Qa(非终结符+终结符)的部分, Q的LASTVT集合中每一个元素与a在表格中的交叉点填大于号。
        i.找出形如Qa的部分
        

        ii.填大于号(非终结符中的元素为横排,终结符中的元素为竖排,以竖排为基准填符号)

        

    (7)  合并后的结果为

        

     

        从上表可知:

        (1)相同终结符之间的优先关系未必是=

        (2)有a<b,未必有b>a

        (3)a、b之间未必一定有优先关系

     

        故=、<、>不同于关系运算符“等于”、“小于”、“大于”

     

    展开全文
  • 算符优先分析文法

    2013-03-25 10:11:17
    计算机科学与技术中编译原理中算符优先分析法代码,很有用哈
  • 算符优先分析器设计

    2013-04-08 16:21:43
    算符优先分析器设计
  • 算符优先分析过程是自上而下的归约过程,但未必是严格的最左归约。也就是说,算符优先分析法不是一种规范归约法。 所谓算符优先分析法就是定义算符之间的某种优先关系,借助于这种关系寻找“可归约串”进行归约的一...

    算符优先分析过程是自上而下的归约过程,但未必是严格的最左归约。也就是说,算符优先分析法不是一种规范归约法。

    所谓算符优先分析法就是定义算符之间的某种优先关系,借助于这种关系寻找“可归约串”进行归约的一种方法。

    一,算符优先文法

    FIRSTVT

    推出的第一个终结符集合

    LASTVT

    二,优先表构造

     先行后列

    三,算符优先文法

    素短语:至少含有一个终结符的短语(且不能拆分成最小)

    1. 移进 当栈顶终结符 < 或 = 当前输入符号时
    2. 归约 当栈顶终结符 > 当前输入符号时,在栈中寻找最左素短语进行归约
    3. 接受 当栈顶终结符=当前输入符号=‘#’       时,分析成功结束
    4. 出错 当栈顶终结符与当前输入符号没有优先关系时
    分析:i1+i2*i3
    1 # i+i*i# #<i 移进i
    2 #i +i*i# i>+ 归约F→i
    3 #F +i*i# #<+ 移进+
    4 #F+ i*i# +<i 移进i
    5 #F+i *i# i>* 归约 F→i
    6 #F+F *i# +<* 移进*
    7 #F+F* i# *<i 移进i
    8 #F+F*i # i># 归约 F→i
    9 #F+F*F # *># 归约T→T*F
    10 #F+T # +># 归约 E→E+T
    11 #E # #=# 接受
    展开全文
  • 编译原理 —— 算符优先分析

    千次阅读 多人点赞 2019-05-17 17:12:36
    什么是算符优先分析算符优先分析法是一种简单、直观的自下而上分析法 算符优先分析法就是仿照算术表达式的四则运算过程而设计的一种语法分析方法。 这种分析方法首先要规定运算符之间(确切地说终结符之间)的...

    什么是算符优先分析法

    • 算符优先分析法是一种简单、直观的自下而上分析法
    • 算符优先分析法就是仿照算术表达式的四则运算过程而设计的一种语法分析方法。
    • 这种分析方法首先要规定运算符之间(确切地说终结符之间)的优先关系和结合性质,然后借助这种关系,比较相邻运算符的优先级来确定句型的可归约串并进行归约。

    算符优先文法的定义

    一、算符文法的定义

    • 在算符文法中,任何一个规则右部都不存在两个非终结符相邻的情况。如 AB

    二、定义任意两个终结符号之间的优先关系

    解释:

    (1)ab两个可以同时规约,故优先级相等
    (2)将R的推导式代入P的产生式中,最终也会形成如(1)中一样的P的产生式的形式,但此时需要对b先进行规约,再规约a,故a的优先级小于b的优先级
    (3)同理可得,b的优先级小于a的优先级

    三、算符优先文法的定义


    算符优先关系表的构造

    算符优先分析法借助优先关系表寻找句型的可归约串。

    步骤一:为每个非终结符 A 计算 FIRSTVT(A) 和 LASTVT(A)

    (1)Firstvt集合

    找Firstvt的三条规则:如果要找A的Firstvt,A的候选式中出现:

    • A->a…,即以终结符开头,该终结符入Firstvt
    • A->B…,即以非终结符开头,该非终结符的Firstvt入A的Firstvt
    • A->Ba…,即先以非终结符开头,紧跟终结符,则终结符入Firstvt

    (2)Lastvt集合

    找Lastvt的三条规则:如果要找A的Lastvt,A的候选式中出现:

    • A->…a,即以终结符结尾,该终结符入Lastvt
    • A->…B,即以非终结符结尾,该非终结符的Lastvt入A的Lastvt
    • A->…aB,即先以非终结符结尾,前面是终结符,则终结符入Lastvt

    步骤二:逐条扫描文法规则

    (1)因存在 E → (E)的规则,则有=
    (2)寻找终结符在左边,非终结符在右边的符号对

    • +T 则 +< FIRSTVT(T)
    • *F 则 *< FIRSTVT(F)
    • (E 则 (< FIRSTVT(E)

    (3)寻找非终结符在左边,终结符在右边的符号对

    • E+ 则 LASTVT(E)>+
    • T* 则 LASTVT(T)>*
    • E) 则 LASTVT(E)>)

    步骤三:寻找$与开始符号E的关系

    (1)$=$

    (2)$<FIRSTVT(E)且LASTVT(E)>$

    展开全文
  • 算符优先分析

    2012-05-22 09:01:52
    编译原理 :自底向上算符优先分析法 比较完整的小型论文,包括源代码。
  • 基于算符优先分析方法的表达式语法分析器基于算符优先分析方法的表达式语法分析器基于算符优先分析方法的表达式语法分析器基于算符优先分析方法的表达式语法分析器
  • 实验三 算符优先分析算法的设计与实现 8 学时) 一 实验目的 根据算符优先分析法 对表达式进行语法分析 使其能够判断一个表达式是否正确 过算符优先分析方法的实现加深对自下而上语法分析方法的理解 二 实验要求 1...
  • 给定文法,手工给出算符优先分析表,用算符优先分析法识别句子。
  • 算符优先分析 语法分析器,MFC做的,个人感觉很不错
  • 算符优先分析文法是一种工具,在编译的过程中,隶属于语法分析环节,却又与中间代码的生成息息相关,编译可以分为五个阶段:词法分析、语法分析、语义分析(中间代码的生成)、代码优化、目标代码生成。语法分析是指...
  • 实验三 算符优先分析算法的设计与实现,郑州大学,昝红英,编译原理,源码,已通过
  • 编译原理算符优先分析算法

    千次阅读 2017-06-02 18:14:58
    算符优先分析算法   编译原理中自上而下算符优先分析算法是一种“移进-规约”法,本例运用的是编译原理第三版何炎祥中的算符优先分析算法,省去了输出分析过程部分,读者可以参考我发的编译原理语法分析器中的输出...
  • 编译原理:算符优先分析

    千次阅读 2020-05-28 08:22:45
    编译原理:算符优先分析文法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 617
精华内容 246
关键字:

算符优先分析