精华内容
下载资源
问答
  • (1)根据给定文法,先求出FirstVt和LastVt集合,构造算符优先关系表(要求算符优先关系表 输出到显示器或者输出到文件); (2)根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式(要求输出...
  • 算符优先文法是一种自下而上的分析方法,其文法的特点是文法的产生式中不含两个相邻的非终结符。 生成FIRSTVT LASTVT集合 算符优先关系表 可以对输入的语言进行分析 样例 1: S->#E# E->E+T E->T T->T*F T->...
  • 编译原理之算符优先分析

    千次阅读 2019-06-20 11:57:29
    算符文法中,相邻算符之间的优先关系有几种?如何定义?三. 如何构造优先关系矩阵?1. FIRSTVT集、LASTVT集的定义及构造方法;2. 构造优先关系矩阵的算法?举例加以讲解;四. 算符优先分析法最左规约串的确定1. 最...

    一. 什么是算符文法?应满足什么条件

    • 算符文法
      设有一个文法G,若G中有形如U->Vw的产生式,即它的任意产生式的右部都不含两个相继的非终结符,则称G为算数文法,或称为OG文法。

    • 算符优先文法
      (1)是自上而下分析法中的一种,虽然他不是规范规约,但具有分析速度快的特点,是和表达式分析。
      (2)算符优先分析法就是仿照算数四则运算的运算过程。定义任意两个相继出现的终结符号a和b之间的优先关系,一点确定了这种优先关系,就可以用他确定“句柄”进行规约。

    二. 算符文法中,相邻算符之间的优先关系有几种?如何定义?

    设G是不含ε-产生式的文法,对任何终结符a,b∈VT,A,B,C∈VN

    1. a优先级高于b: a > b,a先于b被规约
    2. a优选级等于b: a = b,a与b同时被规约
    3. a优先级低于b: a < b,a后于b被规约

    三. 如何构造优先关系矩阵?

    1. FIRSTVT集、LASTVT集的定义及构造方法;

    定义FirstVT§={a|P(+=>)a···或P(+=>)Qa···,a属于终结字符集,而Q属于非终结字符集},其中···表示所有字符集
    LastVT(P)={a|P(+=>)···a或P(+=>)···aQ,a属于终结字符集,而Q属于非终结字符集}

    • 由以下两条规则来构造FirstVT集:
    1. 若有产生式P=>a···、或P=>Qa···,则a属于FirstVT(P);
    2. 若有a属于FirstVT(Q),且有产生式P=>Q···,则a属于FirstVT§;# 四. 算符优先分析法最左可规约串的确定
    • 类似的有构造LastVT集的规则:
    1. 若有产生式P=>···a或P=>···aQ,则a属于LastVT集。
    2. 若a属于LastVT(Q),且有产生式P=>···Q,则a属于LastVT(P)集。

    2. 构造优先关系矩阵的算法?举例加以讲解;

    在这里插入图片描述

    四. 算符优先分析法最左规约串的确定

    1. 最左素短语的定义是什么?

    • 素短语:某文法句型的短语它至少包含有一个终结符号,并且除它之外,不再包含任何更小的素短语。
    • 最左素短语:任意句型最左边的素短语。

    2. 最左素短语的特征?如何根据其特征确定当前句型的最左可归约串?

    在这里插入图片描述

    3. 什么是“单非产生式”,算符优先分析法进行规约为什么速度快?

    • 右部仅有一个非终结符的产生式
    • 比用文法的优先关系矩阵节省内存,若有n个终结符号,优先关系矩阵占内存为(n+1)2,优先函数为2(n+1);
    • 编程时便于比较运算,即用一般的关系运算即可;

    五. 算符优先分析法总控程序的工作流程及伪代码

    1. 工作流程

    1. 定义两个相继出现的终结符a 和b 的优先关系
    2. 确定要规约的句型的最左素短语
    3. 将最左素短语规约

    2. 伪代码

    void Isleft( )
    {  Stack s;
       k=1;
       s[k]=’#’;
       do{   把下一个输入符号读进a中;
                if (S[k]∈VT)   j=k;
                else                j=k-1;
                while(S[j]>a)
                {  do{    Q=S[j];
                             if(S[j-1] ∈VT)   j=j-1;
                            else                   j=j-2;
                        }while(S[j]>Q);
                  把S[j+1]…S[k]归约为某个N;
                  k=j+1;
                 S[k]=N;
                }
               if(S[j]<a || S[j]=a)
               {   k=k+1;
                   S[k]=a;
                }
              }while(a!=’#’);
    }
    
    
    展开全文
  • 算符优先分析

    2018-10-23 16:52:19
    用java写的算符优先程序,可以运行,但是必须以#结尾。比如i+i*i#或者i+i+i+i-i*i+i#
  • 编译原理中的算符优先文法,构造出一个优先表。
  • 算符优先算法

    2014-06-27 16:13:54
    [实验项目] 实现算符优先分析算法,完成以下描述算术表达式的算符优先文法的算符优先分析过程。 G[E]:E→E+T∣E-T∣T T→T*F∣T/F∣F F→(E)∣i 说明:终结符号i为用户定义的简单变量,即标识符的定义。
  • (Python实现,注释详细)直接输入:3+4*5,一般的...(1)第一阶段,运用算符优先分析算法完成计算器中对算术表达式的语法分析; (2)第二阶段,设计属性文法,改造第一阶段的程序,完成算术表达式的计算和相关的输出。
  • 编译原理 算符优先文法 实验报告 代码 运行成功////////////
  • 语法分析算符优先-Java版 程序设计语言编译原理 (第三版) 根据书上的伪代码用Java语言写的
  • 编译原理算符优先文法实验源码
  • 算符优先分析法

    2018-05-22 21:12:04
    设有文法G[S]:S→SaF | F F→FbP | P P→c | d (1) 构造G[S]的算符优先关系表 (2) 分别给出cadbdac# 和 dbcabc# 的分析过程
  • 编译原理 算符优先文法 实验报告 代码 运行成功
  • 算符优先分析程序

    2016-05-22 23:00:21
    编写一个算符优先分析程序,能实现以下功能: 1. 输入文法,判断是否为算符文法。 2. 构造并输出文法的每个非终结符的FIRSTVT和LASTVT。 3. 构造并输出算符优先分析表,判断是否为算符优先文法,如果不是提示无法进行...
  • 这个算符优先算法文档很详细,大家可以借鉴一下,有什么不懂的私聊我
  • 算符优先分析文法是一种工具,在编译的过程中,隶属于语法分析环节,却又与中间代码的生成息息相关,编译可以分为五个阶段:词法分析、语法分析、语义分析(中间代码的生成)、代码优化、目标代码生成。语法分析是指...
  • 算符优先文法处理判断算术表达式源代码、说明文档、输入输出详细说明及截图
  • 算符优先分析器 #include "stdio.h" #include "stdlib.h" #include "iostream.h" char data[20][20]; //算符优先关系 char s[100]; //模拟符号栈s char lable[20]; //文法终极符集 char input[100]; //文法输入符号...
  • 算符优先语法分析程序

    热门讨论 2012-07-07 21:27:39
    实现算符优先分析算法,完成以下描述算术表达式的算符优先文法的算符优先分析过程。 G[E]:E→E+T∣E-T∣T T→T*F∣T/F∣F F→(E)∣i 说明:终结符号i为用户定义的简单变量,即标识符的定义。 要求: (1)构造该算符...
  • 算符优先法对算术表达式求值(六)

    万次阅读 多人点赞 2018-11-23 00:19:22
    掌握栈在解决实际问题中的应用,设计一个程序,演算用算符优先法对算术表达式求值的过程,利用算符优先关系,实现对算术四则混合运算表达式的求值 。。挺难的。。 思路在这! 思路 这个程序是这样,当你点击运行它的...

    18.11.23
    这是一道最近刚上的实验课的题目。。。。

    基于C语言,欢迎指正

    实验要求

    掌握栈在解决实际问题中的应用,设计一个程序,演算用算符优先法对算术表达式求值的过程,利用算符优先关系,实现对算术四则混合运算表达式的求值

    。。挺难的。。

    思路在这!

    思路

    这个程序是这样,当你点击运行它的时候,你需要输一个表达式,然后按个回车,答案就出来了,跟个计算器一样

    那么,在一开始,我们需要一个数组,来存入你所输入的表达式,这样就得到了一个字符数组,然后呢,我们需要创建两个栈,一个用来存运算符,我们叫他运算符栈opter,一个用来存操作数,我们叫它操作数栈opnd,然后我们开始读入我们输入的表达式,读到一个操作符就加到一个新的字符数组,比如说,23+1这个式子,先读入一个’2’存入字符数组,在读入一个’3’存入字符数组,当读到’+’ ,这个时候字符数组有两个元素,给字符数组的第三号位加上一个’\0’,就变成了一个字符串,这样用atof函数就是可以把这个字符串变成浮点型从而可以参与运算(不然如果还是字符状态是不能参与运算的),然后把得到的这个23压入操作数栈中进行相应操作,相应操作如下:

    这是来自学校发的实验报告册上的:(认真看还是看的懂的)
    (1)首先将操作数栈opnd设为空栈,而将’#'作为运算符栈opter的栈底元素,这样的目的是判断表达式是否求值完毕。
    (2)依次读入表达式的每个字符,表达式须以’#‘结尾,若是操作数则入栈opnd,若是运算符,则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作,具体操作如下:
    (i)若top的优先级小于c,即top<c,则将c直接入栈opter,并读入下一字符赋值给c;
    (ii)若top的优先级等于c,即top=c,则弹出opter的才顶元素,并读入下一字符赋值给c,这一步目的是进行括号操作;
    (iii)若top优先级高于c,即top>c,则表明可以计算,此时弹出opnd的栈顶两个元素,并且弹出opter栈顶的的运算符,计算后将结果放入栈opnd中。直至opter的栈顶元素和当前读入的字符均为’#’,此时求值结束。

    在这里插入图片描述
    表中需要注意的是θ1为opter的栈顶元素,θ2为从表达式中读取的操作符,此优先级表可以用二维数组实现。

    有.思路了,咱们把整个程序拆开来看看

    我们需要的东西

    1. 一堆头文件
    2. 一个用于优先级比较的数组,
    3. 两个栈
    (我们这里用的是顺序栈)

    其中,这个用于运算符比较的数组是这个
    “>><<<>>”,
    “>><<<>>”,
    “>>>><>>”,
    “>>>><>>”,
    “<<<<<=?”,
    “>>>>?>>”,
    “<<<<<?=”
    即这个
    在这里插入图片描述

    代码如下

    #include<stdio.h>
    #include<stdlib.h>//包含exit()函数
    #include<string.h>//跟字符处理有关的头文件
    #include<math.h>
    
    #define Stack_Size 1000    //认为Stack_Size为1000
    
    char cmp[7][8]= {">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<=?",">>>>?>>","<<<<<?="};
    
    typedef struct{//定义一个运算符栈
        char Elem[Stack_Size];
        int top;//标记变量,记录表尾的变化
    }Opter;
    
    typedef struct{//定义一个操作数栈
        double Elem[Stack_Size];
        int top;
    }Opnd;
    
    

    准备活动完成了,接下来是对栈的一些基础操作进行设定

    设置一些栈操作要用的函数

    比如说
    (下面的S是传进来的栈的指针地址)

    1. 初始化栈:就一个操作,S->top=-1
    2. 入栈:首先,S->top++,然后再S->Elem[S->top]=传进来的元素
    3. 出栈:一个操作,S->top–;,当然要排除掉栈空的情况,即S->top==-1,这种情况就要exit()
    4. 取栈顶元素:我们用返回值返回S->Elem[S->top]就行啦,当然也要排除栈空

    代码如下

    void InitOpter(Opter *S){//初始化运算符栈
        S->top=-1;
    }
    void InitOpnd(Opnd *S){//初始化操作数栈
        S->top=-1;
    }
    
    int PopOpter(Opter *S)//弹出运算符栈
    {
        if(S->top==-1)
        {
            printf("运算符栈为空\n");
            exit(10);
        }
        S->top--;
        return 1;
    }
    
    int PopOpnd(Opnd *S)
    {
        if(S->top==-1)
        {
            printf("运算符栈为空\n");
            exit(11);
        }
        S->top--;
        return 1;
    }
    
    int PushOpter(Opter* S,char ch)
    {
        if(S->top==Stack_Size-1)
        {
            printf("运算符栈满\n");
            exit(12);
        }
        S->top++;
        S->Elem[S->top]=ch;
        return 1;
    }
    
    int PushOpnd(Opnd* S,double ch)//入操作数栈
    {
        if(S->top==Stack_Size-1)
        {
            printf("运算符栈满\n");
            exit(13);
        }
        S->top++;
        S->Elem[S->top]=ch;
        return 1;
    }
    
    char GetOpter(Opter *S)//获取运算符栈的栈顶元素,注意区分返回值类型
    {
        if(S->top==-1)
        {
            printf("运算符栈为空\n");
            exit(17);
        }
        return S->Elem[S->top];
    }
    
    double GetOpnd(Opnd *S)
    {
        if(S->top==-1)
        {
            printf("操作数栈为空\n");
            exit(18);
        }
        return S->Elem[S->top];
    }
    

    有了这些基本工具,接下来是计算函数

    计算函数

    double Calc(double a,double b,char opt)//计算函数,传入两个数以及一个运算符
    {
        double T;   //T用于存放计算得出的结果
        if(opt=='+') T=a+b;
        if(opt=='-') T=a-b;
        if(opt=='*') T=a*b;
        if(opt=='/')     //要防止发生除0错误
        {
            if(fabs(b)<0.00001)
            {
                printf("发生除0错误\n");
                exit(15);
            }
            T=a/b;
        }
        printf("中间过程输出:  %.2lf %c %.2lf = %.2lf\n",a,opt,b,T);
        return T;    //返回得到的结果
    }
    

    在程序执行过程中,我们需要比较两个运算符的优先级来进行计算,所以我们需要创建一个比较函数

    比较函数

    int change(char ch)
    {
        switch(ch)
        {
        case '+':
            return 0;
        case '-':
            return 1;
        case '*':
            return 2;
        case '/':
            return 3;
        case '(':
            return 4;
        case ')':
            return 5;
        case '#':
            return 6;
        }
    }
    
    int Compare(char ch1,char ch2)
    {
        if(cmp[change(ch1)][change(ch2)]=='?'){
            printf("输入表达式错误");
            exit(16);
        }
        return cmp[change(ch1)][change(ch2)];
    }
    

    将运算符转变为优先级比较的数组的下标,通过查阅优先级比较数组中对应的结果,再传给函数,其中change函数就是起到查阅的作用

    检查是否输入多余字符

    我们可能输入表达式的时候会多输入了一些不在范围内的字符,这就需要一个检查函数来排查

    int Check(char *S,int len)//检查函数,记得考虑输入带小数点的数字的情况
    {
        int i;
        for(i=0;i<len;i++){
            if(S[i]>='0'&&S[i]<='9')continue;
            if(S[i]=='('||S[i]==')'||S[i]=='*'||S[i]=='/'||S[i]=='+'||S[i]=='-'||S[i]=='.')continue;
            return 0;
        }
        return 1;
    }
    

    有了上面的这些函数,我们就可以在主函数中进行调试了,我们一些具体的运算操作也是要在主函数中实现的

    主函数该怎么写

    我们直接在代码中进行解释
    代码如下

    int main()
    {
        char a[1000],b[1000];         //创建两个数组,a是用来存输入的表达式的,b是用来存操作数的
        
        int len;        //len为输入表达式的长度,通过strlen求得
        Opter S;    //创建一个运算符栈
        Opnd N;    //创建一个操作数栈
        InitOpnd(&N);   //初始化操作数栈
        InitOpter(&S);   //初始化运算符栈
        
        PushOpter(&S,'#');  
         //注意这里,我们事先在运算符栈中压入一个'#',在输入表达式后,在表达式数组中最后一个位置也设为'#',
         //之后在运算结束时这两个#会相见,比较函数返回'=',使得最终的运算结束
         
        printf("输入表达式:\n");
        scanf("%s",a);    //输入表达式,注意这里a不用取地址符&,因为数组其实就是一个地址,它保留的是数组第一个元素的首地址,a其实就是&a[0]
        
        len=strlen(a);   //求输入的表达式的长度,并打印出来
        printf("字符长度为%d\n",len);
        
        if(Check(a,len)==0)   //检查是否多输入了一些奇奇怪怪的东西
        {
            printf("输入中存在多余字符\n");
            exit(19);
        }
        
        int i,j=0,k=0;
        double x,y;  //x,y是从操作数中取出的两个即将用于计算的数
        a[len]='#';  //注意
        for(i=0;i<=len;i++)  //遍历我们输入的表达式
        {
            if((a[i]>='0'&&a[i]<='9')||a[i]=='.')//如果为数字
            {
                b[k++]=a[i];//将数字存入数组b中,注意此时数字仍为字符
                j=1;
                continue;  //在该循环下其余部分都不做了,直接进入下一次xunh
            }
            if(j)//条件成功即遇到了运算字符,将操作数压入操作数栈中
            {
                //此时数组b已经有了一个或者几个数字在里面,需要加一个'\0'使其成为字符串
                //再通过atof函数使其由字符型变为双精度型,然后加入操作数栈中进行相应运算
                b[k]='\0';
                PushOpnd(&N,atof(b));//atof函数可以使char变为double
                j=0;
                k=0;  //k置零为下一次计数做准备
            }
            switch(Compare(GetOpter(&S),a[i]))//比较运算符栈的栈顶运算符top和运算符a[i]的优先级
            { //底下的部分我们按照之前给的规则来写
         
            case '<'://即top<a[i],则将a[i]直接入栈Opter
                PushOpter(&S,a[i]);
                break;
            case'=':
                PopOpter(&S);
                break;
            case'>':
            //当为‘>'的情况,即需要进行运算,先取操作数栈中最上面的两个元素
                y=GetOpnd(&N),PopOpnd(&N);
                x=GetOpnd(&N),PopOpnd(&N);
                //然后将计算结果压入操作数栈中
                PushOpnd(&N,Calc(x,y,GetOpter(&S)));
                //已经用过的运算符就废掉了,弹出!!!
                PopOpter(&S);
                
                i--;//这句是为了重新把反括号入栈,使之与左括号配对,否则会造成左括号多余出来
                break;
            }
        }
        double answer=GetOpnd(&N);//最终操作数栈中的数就是我们想要的结果
            printf("最终结果为%.2lf",answer);
            return 0;
    
    }
    
    
    
    

    那么用算符优先法对算术表达式求值的程序就算是写完啦

    源程序调试

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    
    #define Stack_Size 1000
    
    char cmp[7][8]= {">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<=?",">>>>?>>","<<<<<?="};
    
    typedef struct{//定义一个运算符栈
        char Elem[Stack_Size];
        int top;
    }Opter;
    
    typedef struct{//定义一个操作数栈
        double Elem[Stack_Size];
        int top;
    }Opnd;
    
    
    
    void InitOpter(Opter *S){//初始化运算符栈
        S->top=-1;
    }
    void InitOpnd(Opnd *S){//初始化操作数栈
        S->top=-1;
    }
    
    int PopOpter(Opter *S)//弹出运算符栈
    {
        if(S->top==-1)
        {
            printf("运算符栈为空\n");
            exit(10);
        }
        S->top--;
        return 1;
    }
    
    int PopOpnd(Opnd *S)
    {
        if(S->top==-1)
        {
            printf("运算符栈为空\n");
            exit(11);
        }
        S->top--;
        return 1;
    }
    
    int PushOpter(Opter* S,char ch)
    {
        if(S->top==Stack_Size-1)
        {
            printf("运算符栈满\n");
            exit(12);
        }
        S->top++;
        S->Elem[S->top]=ch;
        return 1;
    }
    
    int PushOpnd(Opnd* S,double ch)//入操作数栈
    {
        if(S->top==Stack_Size-1)
        {
            printf("运算符栈满\n");
            exit(13);
        }
        S->top++;
        S->Elem[S->top]=ch;
        return 1;
    }
    
    char GetOpter(Opter *S)//获取运算符栈的栈顶元素
    {
        if(S->top==-1)
        {
            printf("运算符栈为空\n");
            exit(17);
        }
        return S->Elem[S->top];
    }
    
    double GetOpnd(Opnd *S)
    {
        if(S->top==-1)
        {
            printf("操作数栈为空\n");
            exit(18);
        }
        return S->Elem[S->top];
    }
    
    double Calc(double a,double b,char opt)//计算函数,传入两个数以及一个运算符
    {
        double T;   //T用于存放计算得出的结果
        if(opt=='+') T=a+b;
        if(opt=='-') T=a-b;
        if(opt=='*') T=a*b;
        if(opt=='/')     //要防止发生除0错误
        {
            if(fabs(b)<0.00001)
            {
                printf("发生除0错误\n");
                exit(15);
            }
            T=a/b;
        }
        printf("中间过程输出:  %.2lf %c %.2lf = %.2lf\n",a,opt,b,T);
        return T;    //返回得到的结果
    }
    
    int change(char ch)
    {
        switch(ch)
        {
        case '+':
            return 0;
        case '-':
            return 1;
        case '*':
            return 2;
        case '/':
            return 3;
        case '(':
            return 4;
        case ')':
            return 5;
        case '#':
            return 6;
        }
    }
    
    int Compare(char ch1,char ch2)
    {
        if(cmp[change(ch1)][change(ch2)]=='?'){
            printf("输入表达式错误");
            exit(16);
        }
        return cmp[change(ch1)][change(ch2)];
    }
    
    int Check(char *S,int len)//检查函数,记得考虑输入带小数点的数字的情况
    {
        int i;
        for(i=0;i<len;i++){
            if(S[i]>='0'&&S[i]<='9')continue;
            if(S[i]=='('||S[i]==')'||S[i]=='*'||S[i]=='/'||S[i]=='+'||S[i]=='-'||S[i]=='.')continue;
            return 0;
        }
        return 1;
    }
    
    int main()
    {
        char a[1000],b[1000];         //创建两个数组,a是用来存输入的表达式的,b是用来存操作数的
    
        int len;        //len为输入表达式的长度,通过strlen求得
        Opter S;    //创建一个运算符栈
        Opnd N;    //创建一个操作数栈
        InitOpnd(&N);   //初始化操作数栈
        InitOpter(&S);   //初始化运算符栈
    
        PushOpter(&S,'#');
         //注意这里,我们事先在运算符栈中压入一个'#',在输入表达式后,在表达式数组中最后一个位置也设为'#',
         //之后在运算结束时这两个#会相见,比较函数返回'=',使得最终的运算结束
    
        printf("输入表达式:\n");
        scanf("%s",a);    //输入表达式,注意这里a不用取地址符&,因为数组其实就是一个地址,它保留的是数组第一个元素的首地址,a其实就是&a[0]
    
        len=strlen(a);   //求输入的表达式的长度,并打印出来
        printf("字符长度为%d\n",len);
    
        if(Check(a,len)==0)   //检查是否多输入了一些奇奇怪怪的东西
        {
            printf("输入中存在多余字符\n");
            exit(19);
        }
    
        int i,j=0,k=0;
        double x,y;  //x,y是从操作数中取出的两个即将用于计算的数
        a[len]='#';  //注意
        for(i=0;i<=len;i++)  //遍历我们输入的表达式
        {
            if((a[i]>='0'&&a[i]<='9')||a[i]=='.')//如果为数字
            {
                b[k++]=a[i];//将数字存入数组b中,注意此时数字仍为字符
                j=1;
                continue;  //在该循环下其余部分都不做了,直接进入下一次xunh
            }
            if(j)//条件成功即遇到了运算字符,将操作数压入操作数栈中
            {
                //此时数组b已经有了一个或者几个数字在里面,需要加一个'\0'使其成为字符串
                //再通过atof函数使其由字符型变为双精度型,然后加入操作数栈中进行相应运算
                b[k]='\0';
                PushOpnd(&N,atof(b));//atof函数可以使char变为double
                j=0;
                k=0;  //k置零为下一次计数做准备
            }
            switch(Compare(GetOpter(&S),a[i]))//比较运算符栈的栈顶运算符top和运算符a[i]的优先级
            { //底下的部分我们按照之前给的规则来写
    
            case '<'://即top<a[i],则将a[i]直接入栈Opter
                PushOpter(&S,a[i]);
                break;
            case'=':
                PopOpter(&S);
                break;
            case'>':
            //当为‘>'的情况,即需要进行运算,先取操作数栈中最上面的两个元素
                y=GetOpnd(&N),PopOpnd(&N);
                x=GetOpnd(&N),PopOpnd(&N);
                //然后将计算结果压入操作数栈中
                PushOpnd(&N,Calc(x,y,GetOpter(&S)));
                //已经用过的运算符就废掉了,弹出!!!
                PopOpter(&S);
    
                i--;//这句是为了重新把反括号入栈,使之与左括号配对,否则会造成左括号多余出来
                break;
            }
        }
        double answer=GetOpnd(&N);//最终操作数栈中的数就是我们想要的结果
            printf("最终结果为%.2lf",answer);
            return 0;
    
    }
    

    调试结果
    在这里插入图片描述
    NICE!!!

    展开全文
  • 算符优先算法中优先函数的构造

    千次阅读 2020-11-04 10:29:09
    算符优先分析中“优先函数的简单构造!”


            这里我介绍的是一种简单的方法,不是书本的那个方法。是我后面那个参考资料上面的作者想出来的。因为这个是在知网上面找到的,是1997年的一篇文章。我就是一个总结,然后画几个比较清楚的图而已(因为从知网上下载的的pdf上面的图有点不太清楚)

    优先函数树形构造法

            我们教材上面的就是陈火旺老师的那本,然后方法就是找节点。这个方法虽然简单,但是操作起来的却有些麻烦,因为我们作图的时候,难免就会看不清楚,或者数错。下面介绍的树形构造法就可以避免这个问题,仅仅只需要根据优先矩阵就可以得出正确结果。

    操作步骤

    对于一个优先表先做如下几个步骤(假设优先函数存在)
    1 ) 对于f(a)对应行中“a>=b 的所有终结符b , 把g(b)作为f(a) 的子树。
    2) 对g(a) 对应列中有b <=a 的. 把f(a) 作为g(b)的子树.
    3 ) 对f(a)重做第( 1 ) 步, 对g(b) 重做第( 2 ) 步。
    4) 重复出现的f或g , 作记号不再对其执行第( 1) , ( 2) 步
    方向图
    5) 构造f(a)函数时, 以f(a) 为根结点, 按( 1 ) ,(2 ),( 3),( 4) 执行.
    6) 构造g(b)函数时, 以g(b) 为根结点, 按(2 ) ,( 1 ) , ( 3 ) , ( 4 ) 执行.
    按照以上5步先画出树,然后查树的节点数(包括根节点,做记号的不查),即可以得到根节点的优先函数值。
    但是我觉得这个操作步骤2有点问题。应该是b>=a的时候,就把f(a)作为g(b)的子树。我也自己做了实验,发现这样做才是正确的。不过也可能是我没有理解原作者的意思。反正,就目前看来,我都是按照如果b<=a,就把f(a)作为g(b)的子树。
    所以,下面我举例的例子,第(2)步都是按照“b>=a的时候,就把f(a)作为g(b)的子树”这个来做的。

    举例操作

            假如现有一个优先矩阵是这样的:这个例子是《编译原理》陈火旺老师(下面我说的教材,没有特别说明也是指的这本教材)那本书上面的。在90页。
    在这里插入图片描述
    那么我们现在用树形构造法来试试怎么得到这个优先函数。因为最后的答案是去掉了 i 和 # 之后得到的,所以我下面也将不会考虑 i 和 # 号。至于为什么不考虑 i 和 #,,就是因为这两个不是算符,我们算符优先函数主要针对的就是算符直接的优先级。但是优先关系矩阵中是给出了 i 和 # 与其他算符之间的优先关系的。我这里其实是有一个疑问的:因为在优先函数这里没有 i 的优先关系,那么在使用优先函数来分析一个句子是不是这个文法定义的合法的句子的时候,那么什么时候该移进这个 i 呢?希望知道的小伙伴可以在下面留言,我们讨论一下。

            计算f(+)的优先函数值。

    1. 从优先矩阵中可以得到:’+‘ >= 的算符有;’+’,’)’,’#'三个。因为不考虑i 和 #(下面就不提醒这一点了),所以f(+)的孩子节点有两个,分别是g(+)和g()),如下图所示。
      在这里插入图片描述
    2. 现在就来找g(’+’) 的子树。我这里还是采用的是如果b>=a,就把f(a)作为g(b)的子树。从优先表中可以看到的就是’+‘ >= 的算符有:’(’。注意,我这里说的’+‘是g(’+‘),也就是从’+‘那一列中寻找。在这里插入图片描述
      所以,g(’+’)的子树就是f(’(’);在这里插入图片描述
    3. 然后找到g(’)’) >=的算符:在这里插入图片描述
      但是f(’(’)已经出现过了(作为g(’+’)子树出现的),所以就不用画出来了。
    4. 然后就是寻找f(’(’) >=的算符。在这里插入图片描述但是g(’)’)也已经出现过了,所以这里也不用画出来了。
    5. 最后每一个节点我们都已经检查过了,没有可以重新添加的了。也就是趋于稳定了(编译原理里面好多都是这样子的,得使所有都不再变化的时候,算法就算结束了)。我们数一下节点的个数,就是4个,和书本95页给出的答案是一样的。

            同理,g(’+’)的树也可以这样画出来。我就给出最后的树,就不一一分析了。
    在这里插入图片描述

    自己的思考

            本质上书本上的画图和这里的画一颗树,都是优先级高的指向优先级低的,所以入度为0的节点,给的优先函数值应大一点,出度为0的,给出的优先函数值应该小一点。

            上面提到的这个简单的方法其本质善和我们教材上的方法是一样的。你可以将教材上的方法中的图给截取一部分出来。例如,你截取以g(’+’)作为顶点的树去看,发现就是和我上面画的一样。

            还有注意的一点就是:我们求出一组优先函数之后,就可以构造出无数组优先函数。所以,如果你求出来的和参考答案给出的不是一样的,也不一定是你错了。只要你的优先函数之间的关系和参考答案上给出的关系是一样的就可以了。

    参考资料

    构造优先函数的更简单方法_树型构造_潘群娜
    这个知网上我找到的一篇关于这个优先函数构造比较简单的方法,如果大家对上面的博客解释的不太清楚的话,可以去知网上看这个原作者写的文章。

    展开全文
  • 实验三 算符优先分析算法的设计与实现 8 学时) 一 实验目的 根据算符优先分析法 对表达式进行语法分析 使其能够判断一个表达式是否正确 过算符优先分析方法的实现加深对自下而上语法分析方法的理解 二 实验要求 1...
  • 编译原理-算符优先

    千次阅读 2016-05-17 11:29:08
    *功能:算符优先 *作者:王文堃 *创建时间:2016/5/15 */#include #include #include using namespace std;/* *任务一:构造FIRSTVT,LASTVT *任务开始时间:2016/5/15 *任务结束时间:2016/5/16 *//* *任务二:...

    一、实验目的

    根据文法求出FirstVT和LastVT,构造算法优先表,根据输入二元组判断正确与否

    二、实验内容

    2.1任务一:构造FIRSTVT,LASTVT

    FIRSTVT计算过程:
    (1)若有产生式P->a…或者P->Qa…,则a∈FIRSTVT(P);
    (2)若a∈FIRSTVT(Q),且有产生式P->Q…,则a∈FIRSTVT(P);
    LASTVT计算过程:
    (1)若有产生式P->…a或者P->…aQ,则a∈LASTVT(P);
    (2)若a∈LASTVT(Q),且有产生式P->…Q,则a∈LASTVT(P);

    2.2任务二:构造算符优先表

    (1)对形如 P→…ab…和形如P→…aQb…,有a=b;
    (2)对形如 P→…aR…,而b∈FIRSTVT(R),有a

    2.3任务三:根据输入判断结果

    (1)读入当前输入符号
    (2)若输入符号为数字,则输入符号进OPND,输入指针后移,转第(1)步
    (3)若当前输入符号为终结符,则比较当前字符和符号栈栈顶字符的优先级
    (4)若输入符号和栈顶的优先级相同,则输入指针后移,符号栈出栈
    (5)若输入符号优先级小于栈顶的优先级,则输入符号入符号栈,输入指针后移
    (6)若输入符号优先级大于栈顶的优先级,则从数据栈中弹出两个数,符号栈中弹出符号进行计算,结果压入数据栈。继续判断符号栈栈顶和输入符号的优先级
    (7)若输入符号为“#”且符号栈只剩一个“#”时,表示判断成功。

    三、实验过程

    3.1 开发环境

    使用Visual Studio 2015开发win32控制台程序

    3.2 数据结构设计

    3.2.1 使用的宏定义

    #define MAXSIZE 10
    #define NUM_VT 7
    #define NUM_VN 5

    3.2.2 定义的结构体

    //栈操作
    typedef struct Stack
    {
    char data[MAXSIZE];
    int top;
    };

    3.3 测试数据设计

    3.3.1 文法文件“nick.txt”

    S->E
    E->E+T
    E->T
    T->T*F
    T->F
    F->P^F
    F->P
    P->(E)
    P->i

    3.3.2 输入文件“Input.txt”

    (i,1)
    (+,)
    (i,2)
    (*,)
    (i,3)
    (#,)

    /*
    *功能:算符优先
    *作者:王文堃
    *创建时间:2016/5/15
    */
    
    #include <iostream>
    #include <malloc.h>
    #include <stack>
    using namespace std;
    
    /*
    *任务一:构造FIRSTVT,LASTVT
    *任务开始时间:2016/5/15
    *任务结束时间:2016/5/16
    */
    
    /*
    *任务二:构造算符优先表
    *任务开始时间:2016/5/17
    *任务完成时间:2016/5/17
    */
    
    /*
    *任务三:根据输入判断结果
    *任务开始时间:2016/5/17
    *任务完成时间:2016/5/17
    */
    #define MAXSIZE 10
    #define NUM_VT 7
    #define NUM_VN 5
    
    char WenFa[MAXSIZE][MAXSIZE]; //存放从文件中读取的文法
    int g_num_wenfa = 0; //存放文法的个数,初值为0
    char vt[NUM_VT] = {'+','*','^','i','(',')','#'}; //所有终结符
    char vn[NUM_VN] = {'E','T','F','P','S'}; //存放所有非终结符
    int firstvt[NUM_VN][NUM_VT]; //存放每一个非终结符的firstvt
    int lastvt[NUM_VN][NUM_VT]; //存放每一个非终结符的lastvt
    int labelofch[MAXSIZE]; //存放已ch打头的所有文法的标号
    char OPT[NUM_VT][NUM_VT];  //算符优先表
    
    char Input[MAXSIZE][MAXSIZE]; //保存输入
    int g_num_input = 0; //存放输入的个数
    stack <char> OPTR; //符号栈
    stack <char> OPND; //数据栈
    
    
    
    
    /*-----------------------------------------计算FIRSTVT----------------------------------------*/
    
    //读取文法
    bool readfromfile(char* str)
    {
        FILE* fp = fopen(str, "r");
        if (fp) //succeed
        {
            while (EOF != fscanf(fp, "%s", WenFa[g_num_wenfa]))
            {
                g_num_wenfa++;
            }
            fclose(fp);
            return true;
        }
        else
        {
            printf("error to open the file\n");
            return false;
        }
    }
    
    //判断文法中字符是否为终结符
    int isVt(char ch)
    {
        for (int i = 0; i < NUM_VT; i++)
        {
            if (ch == vt[i])
            {
                return true;
            }
        }
        return false;
    }
    
    //判断文法中字符是否为非终结符
    int isVn(char ch)
    {
        for (int i = 0; i < NUM_VN; i++)
        {
            if (ch == vn[i])
            {
                return true;
            }
        }
        return false;
    }
    
    //找到以ch开头的文法的下标
    int findit(char ch)
    {
        int num = 0;
        for (int i = 0; i < g_num_wenfa; i++)
        {
            if (WenFa[i][0] == ch)
                labelofch[num++] = i;
        }
        return num; //返回以ch开头文法的个数
    }
    
    //将非终结符转换成下标
    int Vn2num(char ch)
    {
        switch (ch)
        {
        case 'E':
            return 0;
            break;
        case 'T':
            return 1;
            break;
        case 'F':
            return 2;
            break;
        case 'P':
            return 3;
            break;
        case 'S':
            return 4;
            break;
        default:
            return -1;
        }
    }
    
    //将终结符转换成下标
    int Vt2num(char ch)
    {
        switch (ch)
        {
        case '+':
            return 0;
            break;
        case '*':
            return 1;
            break;
        case '^':
            return 2;
            break;
        case 'i':
            return 3;
            break;
        case '(':
            return 4;
            break;
        case ')':
            return 5;
            break;
        case '#':
            return 6;
            break;
        default:
            return -1;
        }
    }
    
    //求FIRSTVT(ch)
    void get_firstvt(char ch)
    {
        if (isVn(ch)) //对终非结符ch
        {
            int firstnum = Vn2num(ch); //ch所对应的编号
            int num = findit(ch); //找到以该非终结符开头文法的下标
            for (int i = 0; i < num; i++)
            {
                char rightfirst = WenFa[labelofch[i]][3]; //取出文法推到的第一个字符
                if (isVt(rightfirst)) //该文法推出的第一个字符是终结符
                {
                    firstvt[firstnum][Vt2num(rightfirst)] = 1;
                }
                else //该文法推出的第一个字符是非终结符
                {
                    char rightsc = WenFa[labelofch[i]][4];
                    if (isVt(rightsc)) //判断该非终结符之后的符号是不是终结符
                    {
                        firstvt[firstnum][Vt2num(rightsc)] = 1;
                    }
    
                    if (ch != rightfirst)
                    {
                        get_firstvt(rightfirst); //计算这个非终结符的firstvt集
                        int newvn = Vn2num(rightfirst);
                        for (int j = 0; j < NUM_VT; j++)
                        {
                            if (firstvt[newvn][j] == 1)
                            {
                                firstvt[firstnum][j] = 1;
                            }
                        }
                    }
                }
            }
    
    
        }
    }
    
    //计算所有firstvt
    void do_firstvt()
    {
        for (int i = 0; i < NUM_VN; i++)
        {
            get_firstvt(vn[i]);
        }
    
    }
    
    //输出firstvt表
    void output_firstvt()
    {
        int i = 0;
        printf("---------------firstvt----------------\n");
        printf(" ");
        for (i = 0; i < NUM_VT; i++)
        {
            printf("%5c", vt[i]);
        }
        printf("\n");
        for (i = 0; i < NUM_VN; i++)
        {
            printf("%c", vn[i]);
            for (int j = 0; j < NUM_VT; j++)
            {
                printf("%5d", firstvt[i][j]);
            }
            printf("\n");
        }
        printf("--------------------------------------\n");
        printf("\n");
    }
    
    /*-----------------------------------------计算LASTVT----------------------------------------*/
    //找到下标为num的文法的最后一个字符的下标
    int get_last(int num)
    {
        for (int i = 0; i < MAXSIZE; i++)
        {
            if (WenFa[num][i] == '\0')
            {
                return (i-1); 
            }
        }
    }
    
    //求LASTVT(ch)
    void get_lastvt(char ch)
    {
        if (isVn(ch)) //对终非结符ch
        {
            int lastnum = Vn2num(ch); //ch所对应的编号
            int num = findit(ch); //找到以该非终结符开头文法的下标
            for (int i = 0; i < num; i++)
            {
                int ilast = get_last(labelofch[i]);
                char rightlast = WenFa[labelofch[i]][ilast]; //获得文法的最后一个字符
                if (isVt(rightlast)) //该文法推出的最后一个字符是终结符
                {
                    lastvt[lastnum][Vt2num(rightlast)] = 1;
                }
                else //该文法推出的最后一个字符是非终结符
                {
                    char rightlastsc = WenFa[labelofch[i]][ilast -1]; //文法倒数第二个字符
                    if (isVt(rightlastsc)) //判断倒数第二个字符是不是终结符
                    {
                        lastvt[lastnum][Vt2num(rightlastsc)] = 1;
                    }
    
                    if (ch != rightlast)
                    {
                        get_lastvt(rightlast); //计算这个非终结符的lastvt集
                        int newvn = Vn2num(rightlast);
                        for (int j = 0; j < NUM_VT; j++)
                        {
                            if (lastvt[newvn][j] == 1)
                            {
                                lastvt[lastnum][j] = 1;
                            }
                        }
                    }
                }
            }
    
    
        }
    }
    
    //计算所有lastvt
    void do_lastvt()
    {
        for (int i = 0; i < NUM_VN; i++)
        {
            get_lastvt(vn[i]);
        }
    }
    
    //输出lastvt表
    void output_lastvt()
    {
        int i = 0;
        printf("----------------lastvt----------------\n");
        printf(" ");
        for (i = 0; i < NUM_VT; i++)
        {
            printf("%5c", vt[i]);
        }
        printf("\n");
        for (i = 0; i < NUM_VN; i++)
        {
            printf("%c", vn[i]);
            for (int j = 0; j < NUM_VT; j++)
            {
                printf("%5d", lastvt[i][j]);
            }
            printf("\n");
        }
        printf("--------------------------------------\n");
        printf("\n");
    }
    
    
    /*----------------------------------------构造算符优先表---------------------------------------*/
    //处理小于的情况,a<FIRSTVT(R)
    void do_less(char vtch1, char vnch2)
    {
        int x = Vt2num(vtch1); //a
        int i = Vn2num(vnch2); //firstvt表中的行
        for (int j = 0; j < NUM_VT; j++) //遍历firstvt表
        {
            if (firstvt[i][j] == 1)
                OPT[x][j] = '<';
        }
    }
    
    //处理大于的情况,LASTVT(R)>a
    void do_more(char vnch1, char vtch2)
    {
        int y = Vt2num(vtch2);
        int i = Vn2num(vnch1);
        for (int j = 0; j < NUM_VT; j++) //遍历LASTVT表
        {
            if (lastvt[i][j] == 1)
            {
                OPT[j][y] = '>';
            }
        }
    }
    
    //处理#号
    void dosharp()
    {
        //添加“#=#”
        int temp = Vt2num('#');
        OPT[temp][temp] = '=';
        //添加'#'<FIRSTVT(S)、LASTVT(S)>'#'
        for (int i = 0; i < NUM_VT; i++)
        {
            int x = Vn2num('S');
            int j = Vt2num('#');
            if (firstvt[x][i] == 1)
            {
                OPT[j][i] = '<';
            }
            if (lastvt[x][i] == 1)
            {
                OPT[i][j] = '>';
            }
        }
    }
    
    //构造算法优先表
    void OperatorPrecedence()
    {
        int i = 0; //循环变量
        for (i = 0; i < g_num_wenfa; i++) //对所有的文法
        {
            int j = 3; //内部循环变量,从推出来的第一个字符开始
    
            while (WenFa[i][j] != '\0') //该文法没有完
            {
                char ch = WenFa[i][j];
                if (isVt(ch)) //判断当前字符是不是终结符
                {
                    //判断下一个字符是不是终结符
                    if (isVt(WenFa[i][j + 1]))
                    {
                        //若是,则这两个终结符的优先级相等
                        OPT[Vt2num(ch)][Vt2num(WenFa[i][j + 1])] = '=';
                    }
                    else
                    {
                        //做小于
                        do_less(ch, WenFa[i][j + 1]);
    
                        //继续判断下一个字符是不是终结符
                        if (isVt(WenFa[i][j + 2]))
                        {
                            //若是,则这两个终结符的优先级依然相等
                            OPT[Vt2num(ch)][Vt2num(WenFa[i][j + 2])] = '=';
                        }
                    }
                }
                else //当前是非终结符
                {
                    if (isVt(WenFa[i][j + 1])) //判断下一个字符
                    {
                        //大于
                        do_more(ch, WenFa[i][j + 1]);
                    }
                }
                j++;
            }
        }
        dosharp(); //处理#
    }
    
    //输出算符优先表
    void output_OPT()
    {
        int i = 0;
        printf("------------------OPT-----------------\n");
        printf(" ");
        for (i = 0; i < NUM_VT; i++)
        {
            printf("%5c", vt[i]);
        }
        printf("\n");
        for (i = 0; i < NUM_VT; i++)
        {
            printf("%c", vt[i]);
            for (int j = 0; j < NUM_VT; j++)
            {
                printf("%5c", OPT[i][j]);
            }
            printf("\n");
        }
        printf("--------------------------------------\n");
        printf("\n");
    }
    
    /*---------------------------------------处理输入判断结果---------------------------------------*/
    //从文件中读取输入
    bool inputformfile(char* str)
    {
        FILE* fp = fopen(str, "r");
        if (fp) //succeed
        {
            while (EOF != fscanf(fp, "%s", Input[g_num_input]))
            {
                g_num_input++;
            }
            fclose(fp);
            return true;
        }
        else
        {
            printf("error to open the file\n");
            return false;
        }
    }
    
    //判断输入字符的类型
    int judge(char ch)
    {
        switch (ch)
        {
        case 'i':
            return 0; //表示数字
            break;
        case '+':
            return 1; //表示'+'号
            break;
        case '*':
            return 2; //表示'*'号
            break;
        default:
            return -1;
        }
    }
    
    //将int行数字传化成char型
    int char2int(char ch)
    {
        if (ch >= 48 && ch <= 57) //数字
        {
            return ch - 48;
        }
    }
    
    //处理输入
    bool doinput()
    {
        int iInput = 0; //指向输入下标
        //#入符号栈
        OPTR.push('#');
        while (iInput != (g_num_input-1)  || OPTR.size() != 0) //将输入遍历完
        {
            char* str = Input[iInput]; //取出第一个输入
            int result = judge(str[1]);
            if (result == 0) //数字
            {
                OPND.push(str[3]);
            }
            else //是符号
            {
                //判断符号栈顶的符号和当前符号的优先级
                int topofstack = Vt2num(OPTR.top());
                int topofinput = Vt2num(str[1]);
                if (OPT[topofstack][topofinput] == '<') //栈顶小于输入就入栈
                {
                    OPTR.push(str[1]);
                }
                else if (OPT[topofstack][topofinput] == '>')//否则运算
                {
                    int i = char2int(OPND.top());
                    OPND.pop();
                    int j = char2int(OPND.top());
                    OPND.pop();
    
                    int vtnum = Vt2num(OPTR.top());
                    if (vtnum == 0) //+
                    {
                        OPND.push(i + j);
                        OPTR.pop();
                    }
                    else if (vtnum == 1) //*
                    {
                        OPND.push(i*j);
                        OPTR.pop();
                    }
                }
                else //如果相等就出栈
                {
                    OPTR.pop();
                }
            }
            if (iInput != (g_num_input-1))
            {
                iInput++;
            }
        }
    
        //判断
        if (OPTR.size() == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    int main()
    {
        if (readfromfile("nick.txt"))
        {
            do_firstvt();  //构造firstvt
            output_firstvt(); //输出firstvt
            do_lastvt();  //构造lastvt
            output_lastvt(); //输出lastvt
            OperatorPrecedence(); //构造算符优先表
            output_OPT(); //输出算符优先表
    
            //---
            inputformfile("input.txt");
            bool result = doinput();
            if (result != 0)
            {
                printf("最终结果正确\n");
            }
            else
            {
                printf("最终结果错误\n");
            }
    
        }
        getchar();
        return 0;
    }

    最终的运算结果是:
    这里写图片描述

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

    2013-03-14 00:40:37
    对用户自定义的文法进行算符优先的分析,友好的人际交互界面,计算FIRStVT和LASTVT,并且对一段输入进行分析
  • 实验三 算符优先分析算法的设计与实现,郑州大学,昝红英,编译原理,源码,已通过
  • 算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理算符优先分析 编译原理
  • 《c语言实现算符优先语法分析》由会员分享,可在线阅读,更多相关《c语言实现算符优先语法分析(5页珍藏版)》请在人人文库网上搜索。1、includechar prog100,zhongjian100,shu500;char ch,zh;int syn,p,q,a,b,c,d; /p...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,200
精华内容 2,880
关键字:

优先算符