精华内容
下载资源
问答
  • 算符优先算法中优先函数的构造

    千次阅读 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(’+’)作为顶点的树去看,发现就是和我上面画的一样。

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

    参考资料

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

    展开全文
  • 优先函数c代码实现

    2020-10-31 15:22:38
    编译原理之求算符优先函数的方法—迭代法 此博文包含图片 (2011-04-26 22:55:38)转载▼ 标签: 编译原理 算符优先函数 迭代法 教育 分类: IT乐园 编译原理之求算符优先函数的方法—迭代法 若已知运算符之间的优先...

    原地址

    编译原理之求算符优先函数的方法—迭代法 此博文包含图片 (2011-04-26 22:55:38)转载▼ 标签: 编译原理 算符优先函数
    迭代法 教育 分类: IT乐园 编译原理之求算符优先函数的方法—迭代法

    若已知运算符之间的优先关系,可按如下步骤构造优先函数:
    1、对每个运算符a(包括#在内)令f(a)=g(a)=1
    2、如果a⋗b且f(a)<=g(b)令f(a)=g(b)+1
    3、如果a⋖b且f(a)>=g(b)令g(b)= f(a)+1
    4、如果a≐b而f(a) ≠g(b),令min{f(a),g(b)}=max{f(a),g(b)}
    5、重复2~4,直到过程收敛。如果重复过程中有一个值大于2n,则表明不存在算符优先函数。

    在这里插入图片描述
    在这里插入图片描述

    程序实现代码为:
    
    #include <stdio.h>
    #include <stdlib.h>
    #define MaxSize 100
    #define MaxOp 9
    struct
    {
          char ch;  //运算符
          int pri;  //优先级
    }
    lpri[]={{'+',1},{'-',1},{'*',1},{'/',1},{'(',1},{')',1},{'#',1}},
    rpri[]={{'+',1},{'-',1},{'*',1},{'/',1},{'(',1},{')',1},{'#',1}};
    int f(char op)   //求左运算符op的优先级
    {
          int i;
          for (i=0;i<MaxOp;i++)
                 if (lpri[i].ch==op) return lpri[i].pri;
    }
    int g(char op) //求右运算符op的优先级
    {
          int i;
          for (i=0;i<MaxOp;i++)
                 if (rpri[i].ch==op) return rpri[i].pri;
    }
    char Precede(char c1,char c2)
    {
    
          int i=0,j=0;
          static char array[49]={
      '>', '>', '<', '<', '<', '>', '>',
      '>', '>', '<', '<', '<', '>', '>',
      '>', '>', '>', '>', '<', '>', '>',
      '>', '>', '>', '>', '<', '>', '>',
      '<', '<', '<', '<', '<', '=', '!',
      '>', '>', '>', '>', '!', '>', '>',
      '<', '<', '<', '<', '<', '!', '='};
      switch(c1)
      {
      case '+' : i=0;break;
      case '-' : i=1;break;
      case '*' : i=2;break;
      case '/' : i=3;break;
      case '(' : i=4;break;
      case ')' : i=5;break;
      case '#' : i=6;break;
      }
      switch(c2)
      {
      case '+' : j=0;break;
      case '-' : j=1;break;
      case '*' : j=2;break;
      case '/' : j=3;break;
      case '(' : j=4;break;
      case ')' : j=5;break;
      case '#' : j=6;break;
      }
      return (array[7*i+j]);
    }
    
    void main()
    {
          int i,j,k=1;
       while(k!=0)
          {
                 k=0;
                 for(i=0;i<7;i++)
                 {
                        for(j=0;j<7;j++)
                        {
                               if(Precede(lpri[i].ch,rpri[j].ch)=='>'&&f(lpri[i].ch)<=g(rpri[j].ch))
                               {     lpri[i].pri=rpri[j].pri+1;k=1;}
                           else if(Precede(lpri[i].ch,rpri[j].ch)=='<'&&f(lpri[i].ch)>=g(rpri[j].ch))
                               {     rpri[j].pri=lpri[i].pri+1;k=1;}
                        }
                 }
          }
          printf("              ");
          for(i=0;i<7;i++)
                 printf("<",lpri[i].ch);
          printf("\n");
          printf("入栈优先函数f:");
          for(i=0;i<7;i++)
                 printf("=",lpri[i].pri);
          printf("\n");
          printf("比较优先函数g:");
          for(i=0;i<7;i++)
                 printf("=",rpri[i].pri);
          printf("\n");
    }
    

    结果如下:

    在这里插入图片描述

    展开全文
  • 算符优先分析 优先函数

    万次阅读 2011-05-05 17:59:00
    简单的方法,计算优先函数 手动计算比较麻烦,而且容易出错。 根据定义,用计算机实现,快捷方便,准确可扩充   // 0505优先函数.cpp : 定义控制台应用程序的入口点。 // /* 使用说明: 1、改#define N 的值 2...

    简单的方法,计算优先函数

    手动计算比较麻烦,而且容易出错。

    根据定义,用计算机实现,快捷方便,准确可扩充

     

    展开全文
  • 编译原理 优先函数实现表达式计算

    千次阅读 2020-04-23 00:36:27
    优先函数实现表达式计算 左/右 + * ( ) i # + ·> · · ·> · ·> * ·> ·> · ·> · ·> ( · · · = · ) ·> ·> ·> ·> i ·> ·> ·> ...

    优先函数实现表达式计算

    左/右 + * ( ) i #
    + ·> <· <· ·> <· ·>
    * ·> ·> <· ·> <· ·>
    ( <· <· <· <·
    ) ·> ·> ·> ·>
    i ·> ·> ·> ·>
    # <· <· <· <·

    由优先表构造优先函数

    优先函数 + * ( ) i #
    f 6 8 2 8 8 1
    g 4 7 9 2 9 1

    本程序使用C语言编写
    支持整数加减乘除带括号的运算
    核心部分和数据结构中利用栈实现表达式运算几乎相同
    程序的难点在于优先级<、=、>分类讨论

    #include<stdio.h>
    #include<stdlib.h>
    #include <string.h>
    //优先函数
    int fplus = 6;
    int gplus = 4;
    
    int fmul = 8;
    int gmul = 7;
    
    int fleft = 2;
    int gleft = 9;
    
    int fright = 8;
    int gright = 2;
    
    int fi = 8;
    int gi = 9;
    
    int fpound = 1;
    int gpound = 1;
    
    char expression[128];
    int flag = 1; 
    
    void Error()
    {
        printf("错误\n");
        exit(0);
    }
        
    void Input()
    {
    	//char over[] = {'#', '\0'};
        printf("请输入表达式,以#结尾:"); 
        gets(expression); 
    	//printf("Input: %s\n",expression);
    }
    
    int f(char opt)
    {
        if(opt == '+' || opt == '-')
        {
    		return fplus;
        }
        else if (opt == '*' || opt == '/')
        {
            return fmul;
        }
        else if (opt == '(')
        {
            return fleft;
        }
        else if (opt == ')')
        {
            return fright;
        }
        else if (opt == 'i')
        {
            return fi;
        }
        else if (opt == '#')
        {
            return fpound;
        }
        return -1;
    }
        
    int g(char opt)
    {
        if(opt == '+' || opt == '-')
        {
            return gplus;
        }
        else if (opt == '*' || opt == '/')
        {
            return gmul;
        }
        else if (opt == '(')
        {
            return gleft;
        }
        else if (opt == ')')
        {
            return gright;
        }
        else if (opt == 'i')
        {
            return gi;
        }
        else if (opt == '#')
        {
            return gpound;
        }
        return -1;
    }
        
    int In(char num)
    {
        if(num == '0' ||num == '1' || num == '2' || num == '3' || num == '4' || 
    	   num == '5'|| num == '6' || num == '7' || num == '8' || num == '9')
    	   return 1;
        else
            return -1;
    }
        
    int Operation(int a, char opt, int b) 
    {
    	switch(opt)
    	{
    		case '+': return a + b; 
    		case '-': return a - b; 
    		case '*': return a * b; 
    		case '/': return a / b; 
    		default : return 0;
    	} 
    } 
    
    int main() 
    {
    	int index_e = 0;	// 字符串下标
    	int	index_oprt = 0; // 算符栈下标
    	int index_opnd = 0; // 算量栈下标
        int Sn[100];
    	char Sp[100];
    	int num1;
    	int num2;
    	char temp[100];
        Sp[0] = '#';
    
        Input();
    	//printf("算符栈: %s\n",Sp);
        while( flag == 1 )
        {
    		int t = 0;
            if( Sp[index_oprt] == '#' && expression[index_e] == '#' )
            {
    			//printf("都为#,结束\n");
                flag = 0;
            }
            else if(Sp[index_oprt] == '(' && expression[index_e] == ')')
            {
    			//printf("读到括号\n");
                index_oprt--;
                index_e++;
            }
            else if(In(expression[index_e]) == 1)
            {
    			//printf("读到数字\n");
                while(In(expression[index_e]) == 1)
                {
                    temp[t] = expression[index_e];
    				t++;
                    index_e++;
                }
    			//printf("temp: %s\n",temp);
    			//atof()是把字符串转换成double
                Sn[index_opnd++] = atof(temp);
    			//printf("number %d\n",Sn[index_opnd-1]);
                //清空temp
    			for(int m=0; m<100; m++)
    				temp[m] = '\0';
            }
            else if(f(Sp[index_oprt]) < g(expression[index_e]))
            {
    			//printf("%d %d\n",f(Sp[index_oprt]),g(expression[index_e]));
    			//printf("小于\n");
                Sp[index_oprt + 1] = expression[index_e];
                index_oprt++;
                index_e++;
    			//printf("%c 入栈\n",Sp[index_oprt]);
    		}
            else if(f(Sp[index_oprt]) > g(expression[index_e]))
            {
    			//printf("大于\n");
    			//出栈两个数
                num2 = Sn[index_opnd - 1];
    			index_opnd--;
                num1 = Sn[index_opnd - 1];
                index_opnd--;
    			//算符栈出一个,算完了结果再入算量栈
    			Sn[index_opnd] = Operation(num1, Sp[index_oprt], num2);
                index_opnd++;
                index_oprt--;
            }
            else
            {
                Error();
            }
        }
        printf("表达式的值为:%d\n", Sn[0]);
    	return 0;
    }
    

    运行截图:
    在这里插入图片描述

    展开全文
  • 若已知运算符之间的优先关系,可按如下步骤构造优先函数: 对每个运算符a(包括\(\sharp\)在内)令f(a)=g(a)=1 如果\(a \gtrdot b\)且\(f(a) \le g(b)\),令f(a)=g(b)+1 如果\(a \lessdot b\)且\(f(a) \ge g(b)\),令g...
  • 若已知运算符之间的优先关系,可按如下步骤构造优先函数: 1、对每个运算符a(包括#在内)令f(a)=g(a)=1 2、如果a⋗b且f(a)<=g(b)令f(a)=g(b)+1 3、如果a⋖b且f(a)>=g(b)令g(b)= f(a)+1 4、如果a≐b而f(a)...
  • 学习PROMETHEE很不错的资料,值得下载
  • 自底向上分析方法,也称移进-归约分析法。 实现思想: 对输入符号串自左向右进行扫描,并将输入符逐个移入一个栈中,...5.1 自底向上优先分析法概述 5.2 简单优先分析法 5.3 算符优先分析法 ...
  • 函数优先 变量优先

    2018-12-19 21:49:04
    js是一门具有函数优先性质的轻量级解释型语言。 什么是函数优先呢? 这跟js的编译器有关系。js编译器在构造算符优先分析的时候,会将 函数声明,变量声明的优先级提高,将他们放在最前面。 所以我们平时才会看到 在...
  • 当一种编程语言被称为函数优先(First-class functions)的编程语言时,是指该语言中函数可以和其他任何变量一样对待。例如,一个函数可以作为参数传递给另一个函数,可以作为返回值被另一个函数返回,可以作为一个...
  • 函数优先法则

    2019-06-20 20:47:27
    众所周知,在ES5的规则下,使用var声明变量,变量会提升,函数亦是如此,但是如果碰到函数名和变量名是同一个的情况下,代码会如何执行呢?先看下面的例子 foo(); //1 var foo; //这是一个函数声明 function foo()...
  • js 函数优先原则

    2019-10-05 02:48:36
    函数声明和变量声明都会被提升,但是其中一个细节是函数会首先被提升然后才是变量 代码 foo(); var foo; function foo(){ console.log(1); } foo = function(){ console.log(2); } 此时输出的是1...
  • 函数声明优先于变量声明 console.log(typeof fn); function fn() {}; var fn; function 因为函数声明优于变量声明。我们知道在代码逐行执行前,函数声明和变量声明会提前进行,而函数声明又会优于变量声明,...
  • rfpify - Promisify一个结果优先的回调函数
  • 用深度优先思想和广度优先思想实现一个拷贝函数需要考虑的几个方面工具函数深度优先的深拷贝函数广度优先的深拷贝函数总结 需要考虑的几个方面 参数校验 不是对象的值直接返回或赋值 判断对象逻辑 typeof 判断...
  • c++ 优先队列 仿函数

    2020-07-26 21:38:37
    其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了) 优先队列如果要自定义排序函数,只能用仿函数,不能用普通函数的指针。 #include #include using namespace std; //方法1 ...
  • Nodejs 异步函数优先顺序打印结果 1,2,3,4; // 把回调函数放在事件队列的尾部,优先级最低 setImmediate(function () { console.log(4) }) // 宏任务 setTimeout(() => console.log(3), 0) // nodejs微...
  • js中的函数优先原则

    千次阅读 2018-04-21 22:56:37
    在js中函数声明和变量都会被提升,但是函数会被优先提升,然后才是变量下面我们贴出我们的示例代码foo();//1 var foo; function foo() { console.log( 1 ); } foo = function() { console.log( 2 ); }我们使用js引擎...
  • 下面的代码实现从.v小到大的队列。是Codeforces Round #655 (Div. 2)D. Omkar and Circle的错误代码。 #include<cstdio> #include<cstring> #include<algorithm> #include<...
  • 优先选择deleted函数而不是私有未定义函数 如果你要提供代码给其他的开发者,而你想要阻止他们调用某个特定函数,一般来说你就不声明这个函数了。没有函数声明也就没有函数可调用。简单,小菜一碟!但有时候C++会...
  • 关于JS里面的函数优先

    千次阅读 2018-04-27 09:32:30
    由于JS编译器的作用,函数声明和变量声明都会被提升,但是一个值得注意的细节是函数会首先被提升,然后才是变量。 提升 变量和函数声明从它们在代码中出现的位置被“移动”到了最上面,这叫变量的提升。分为...
  • C++ 优先队列自定义比较函数

    千次阅读 2020-04-07 15:44:31
    C++中的优先队列实质是一种堆(最大堆或最小堆)
  • 有时候,你写了代码给其他程序员用,并且你想组织他们调用某个特定函数的话,你只需不要声明该函数即可。函数未经声明,不可调用,易如反掌。但是有些特定函数编译器会帮你生成,那么这个时候C++98里的一种常用处理...
  • template <typename T>void f(T a){ cout ; } template <> void f(int & a){ cout ;...为什么输出aaaaaaa,不是应该输出fffffffffff吗,看书上说具体化优先于模板函数的 求知道的大神指点下啦,万分感谢
  • 对于派生类的构造 函数,在定义对象时构造函数的执行顺序为: 1:基类的构造函数 2:成员对象的构造函数 3:派生类本身的构造函数 public class IoTest { public static void main(String[] args) throws ...
  • F.8: Prefer pure functions(优先选择纯函数) 译者注:纯函数是指符合下面两个特点的函数: 同样的输入一定产生同样的输出。但是并不要求所有的数据都一定参数计算输出值。 不会产生副作用。除了可见的...
  • 优先队列是STL中比较重要的一个部分,用起来非常方便,在很多排序题中要比sort一遍一遍排序快很多,它能根据自己定义顺序来进行排序。 主要的两种表达形式(其实还有其他的,这里就先列举两个): 第一种是用friend...
  • 函数声明优先于变量

    2012-04-11 16:11:00
    // 声明一个函数 } alert(typeof fn); // function function fn() { // 声明一个函数 } var fn; // 声明一个变量 alert(typeof fn); // function 无论声明位置先后,functio...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,670
精华内容 3,868
关键字:

优先函数