精华内容
下载资源
问答
  • 2020-12-30 19:40:22

    基本要求:
    ①掌握中间代码生成的基本方法。
    ②掌握语法制导翻译模式。
    ③完成算术表达式的中间代码生成程序。
    重点及难点:掌握语法制导翻译模式的核心思想和工作原理,在此基础上完成基于算数表达式的中间代码生成程序的设计和调试运行。

    一、 算符优先分析法

    算符优先分析法是一种简单且直观的自下而上分析方法,它特别适合于分析程序语言中的各类表达式,并且宜于手工实现。所谓算符优先分析,就是依照算术表达式的四则运算过程来进行语法分析,即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质,然后借助于这种关系来比较相邻运算符的优先级,以确定句型的“可归约串”来进行归约。因此,算符优先分析法不是一种规范归约,在整个归约过程中起决定性作用的是相继两个终结符的优先关系。
    附加语义的方法是采用语法制导翻译的方法,语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序),并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段,它一方面指出了一个产生式所产生的符号串的意义,另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析过程中,当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时,此产生式相应的语义子程序就进入工作,完成既定的翻译任务。

    二.算符优先分析法程序源代码

    #include<string.h>
    #include<stdio.h>
    #include<math.h>
    
    int nxq = 100;
    char a[20], optr[10], s, op;
    int i, j, k, opond[10], x1, x2, x3;
    
    int operand(char c) {
    	if ((c >= 48) && (c <= 57)) {
    		return(1);
    	}
    	else {
    		return(0);
    	}
    }
    
    int f(char c) {
    	switch (c) {
    	case'+':return(4);
    	case'-':return(4);
    	case'*':return(6);
    	case'/':return(4);
    	case'(':return(2);
    	case')':return(6);
    	case'#':return(0);
    	default:printf("error!\n");
    	}
    }
    
    int g(char c) {
    	switch (c) {
    	case'+':return(3);
    	case'-':return(3);
    	case'*':return(5);
    	case'/':return(5);
    	case'(':return(7);
    	case')':return(2);
    	case'#':return(0);
    	default:printf("error!\n");
    	}
    }
    
    void get() {
    	s = a[i];
    	i = i + 1;
    }
    
    int main() {
    	printf("please input your exoression:\n");
    	i = 0;
    	do {
    		i = i + 1;
    		scanf_s("%c", &a[i]);
    	} while (a[i] != '#');
    	i = 1;
    	j = k = 1;
    	optr[j] = '#';
    	get();
    	while (!((optr[j] == '#') && (s == '#'))) {
    		if (operand(s)) {
    			opond[k] = s - 48;
    			k = k + 1;
    			get();
    		}
    		else if (f(optr[j]) > g(s)) {
    			op = optr[j];
    			j = j - 1;
    			x1 = opond[k - 2];
    			x2 = opond[k - 1];
    			k = k - 2;
    			switch (op) {
    			case'+':x3 = x1 + x2;break;
    			case'*':x3 = x1 * x2;break;
    			case'-':x3 = x1 - x2;break;
    			case'/':x3 = x1 / x2;break;
    			}			
    			opond[k] = x3;
    			k++;
    			printf("%d (%c,%d,%d,%d)\n", nxq++,op, x1, x2, x3);
    		}
    		else if (f(optr[j]) < g(s)) {
    			j = j + 1;
    			optr[j] = s;
    			get();
    		}
    		else if (f(optr[j]) == g(s)) {
    			if (optr[j] == '(' ||optr[j]== ')') {
    				j = j - 1;
    				get();
    			}
    			else {
    				printf("error!\n");
    			}
    		}
    		else {
    			printf("error!\n");
    		}
    	}
    	return 0;
    }
    
    更多相关内容
  • 详细到不能再详细的代码注释 【实验目的】 构造 LR(1)分析程序,利用它进行语法分析,判断给出的符号串(算术表达 式)是否为该文法识别的句子。了解 LR(K)分析方法是严格的从左向右扫描、 自底向上的语法分析方法...
  • 语法分析与中间代码生成

    千次阅读 2020-12-27 21:28:19
      这章和上一章(属性文法和语法制导翻译)是紧密联系的,共同完成了编译过程的第步——语义分析与中间代码产生。   开篇先解释两个问题:     1. 什么是语义分析?它和之前几部分有什么不同呢?     ...

      这章和上一章(属性文法和语法制导翻译)是紧密联系的,共同完成了编译过程的第三步——语义分析与中间代码产生。

      开篇先解释两个问题:
        1. 什么是语义分析?它和之前几部分有什么不同呢?
        2. 什么是中间代码?为什么需要产生中间代码?

      问题一:什么是语义分析?它和之前几部分有什么不同呢?

      词法分析主要完成的是标识符/算符等等定义是否符合规定。语法分析是看程序的结构是否符合文法的要求,也就是下一部分接这个对不对?语义分析就上升到概念层了,我以C语言举个例子:使用一个变量之前必须对这个变量进行定义,否则就会出现undefine的bug,检查这部分的就是语义分析。再有就是break语句必须要定义在循环体中,如果没有循环而有break,肯定是要报错的呀~还有上下无关文法无法描述整个程序语言就是因为其无法表示语义的相关分析。

      问题二:什么是中间代码?为什么需要产生中间代码?

      编程时写的叫做高级语言,机器运行的叫做机器语言。中间代码可以理解成一个过渡。其实汇编语言也是一种过渡,但中间代码主要强调的指明过程中数据和地址及相关操作。为什么需要产生中间代码,是因为中间代码有如下几点好处
    在这里插入图片描述
      看完了前面的内容,希望你对于语义分析和中间代码有一个简单的了解。再继续看下面的内容。先说一下本文叙述的结构吧,大体可以分为四个部分:
      1. 中间代码的表达形式(大致3种)
      2. 说明语句的翻译
      3. 赋值语句的翻译
      4. 布尔表达式/控制语句的翻译

    一、 中间代码的表达形式

      中间代码的表达形式从大的角度上分可分为3种:后缀式、图表示法、三地址代码,下面简单介绍(其实主要用的还是三地址代码,前两种作为扩充知识提一下吧)

      后缀式

      后缀式也叫逆波兰式,是一种表达式的方法。形式化定义如下:
    在这里插入图片描述
      举个例子:
    在这里插入图片描述
      后缀式看上去有点奇怪,反倒是例子中左边的让人更直观理解。其实左边叫做中缀式,还有一种叫做前缀式(也叫做波兰式)。我们平常写的都是中缀式,但计算机识别字符串从左到右或者从右到左,无法完成中缀式的计算规则。所以在计算机里面输入中缀式,一般也会先转化成后缀式。对于后缀式的计算就需要用到数据结构中栈的相关内容啦!

      图表示法

      这里的图前面介绍过,就是抽象语法树。不过新增的一部分是DAG图。啥是DAG图呢?其实就是将抽象语法树中公共因子凝聚成一个节点。举个例子就过:
    在这里插入图片描述

      三地址代码

      三地址代码是由两个运算操作数地址,一个结果操作数地址组成的。一般形式是z = x op y(op代表运算符,其实和高级语言还是挺像的)。对于三地址代码,有如下这几种类型:
    在这里插入图片描述
      三地址代码还有三种表达形式:四元式、三元式、间接三元式。因为后续内容只涉及到四元式,老师课程上也只讲了这一种。我就只介绍这一种了,剩下的如果感兴趣可以自己网上搜一搜:
      四元式包含的四部分是两个源操作数,一个目的操作数再加上一个操作符,对于运算的转化形式如下:
    在这里插入图片描述
      四元式有一个明显的缺点:会引入大量的临时变量(像上表中的T1,T2,T3,T4,T5)但这个问题在后续的优化过程会得到解决。

    二、 说明语句的翻译

      首先,什么是说明语句呢?就有点儿像变量定义的语句。那这步主要干嘛呢?提一个之前的概念:符号表(我都快忘了~)在词法分析的过程中,当我们识别到一个标识符的时候,会放在符号表中。除了标识符的名字外还有一些其他的属性,比如类型,在内存中存储位置等等。
      先介绍两个概念:
    在这里插入图片描述

      作用域

      每一个函数调用都会有属于它本身的作用域,每一个函数都在维护一个符号表。它们就是当前标识符的有效范围,当两个函数进行嵌套并且标识符名相同时,内层作用域属于里面定义的标识符。(这个很容易理解,就是C语言中的变量覆盖)

      符号表:

      制作符号表用到了下面几个函数:
    在这里插入图片描述
      如果把符号表和翻译模式加在一起,举个例子如下所示:
    在这里插入图片描述
      关于符号表有些信息:
    在这里插入图片描述
      举个例子,看看函数过程中的符号表是什么样子的:
    在这里插入图片描述
      从上面可以看出,符号表表头中维护的就是各个指针。能够在指定的位置进行跳转进行操作。

    三、 赋值语句的翻译

      赋值语句就不用多说了,在大多数语句中赋值之前需要先进行定义。所以在赋值时查询符号表是否进行定义就是翻译的操作之一。在翻译过程中会有lookup(id.name)这样的函数完成检验操作。
      举个赋值语句加翻译模式的例子:
    在这里插入图片描述
      对于赋值语句和说明语句内容比较少,课程主要的内容在后面两个,下面继续开始!

    四、布尔表达式的翻译/控制流语句的翻译

      布尔表达式:用布尔运算符号(and or not)作用到布尔变量或关系表达式上而组成
      布尔表达式一方面可以用来进行逻辑计算,另一方面可用作判断条件。
      当进行布尔运算时,存在一种优化的思想。大体是这样的对于or来说,如果你已知第一个操作数是正确的,那第二个操作数就不重要了,结果一定是true。相反,若第一个错误,则要看看第二个语句的情况。True和false的情况语句不会完全相邻,就需要一些跳转,自然就要生成一些标号。下面我列举下布尔表达式进行计算时的属性文法:
    在这里插入图片描述
    在这里插入图片描述
      那如果是控制流语句呢?比如if,if-else,while语句中的判断条件。那对布尔表达式的翻译都需要干些啥呢?很明显就是要知道在各种情况下指令之间是怎么跳转的。对于布尔表达式的翻译内容主要可以分为两种情况:属性文法和翻译模式。
      属性文法就是先定义语法动作再定义语法规则。写一个程序的属性文法是有套路的。Let me show you! 主要的方法是图解法,因为常用在循环中,我就以循环举例。对于单步的条件判断,可同理得到。
      有产生式S->for(E1;E2;E3)S1,写其属性文法
      先看看结果,如图所示:
    在这里插入图片描述
      那为啥会有这个结果呢?首先我们需要先画一个图从上到下按照产生式的顺序为E1,E2,E3,S1,四段代表代码段。就像这样:
    在这里插入图片描述
      先来分析一下这个循环的执行过程:初始化E1,接着对E2进行判断,满足E2跳转S1,不满足E2跳出循环(即S),S1执行过后(或者S1中的跳转)跳转E3执行自增,E3执行跳转E2再次判断,就这样循环,循环…
      从上面一个简单的过程中可以了解到,有跳转的过程,其中包含if的跳转也包含直接的跳转。但无论哪种,都要有一个跳转的目标,也就是说要为每一个目的地建立一个标记。有一个通用的套路:为if语句建立E.true和E.false两个属性。为每一个终点建立一个标号。结合上面的例题,E2跳转S1——E2是if语句,满足条件跳转,建立一个标号,但因为也是E2.true, 之前建立过了,不需要再建了。S1跳转E3——无条件跳转,生成一个E3.label。E3跳转E2——无条件跳转,生成一个E2.label。把他们标在上面的图里就是这样:
    在这里插入图片描述
      我们再把goto语句写到代码段中,就像这样:
    在这里插入图片描述
      以上过程做好了前期准备,可以开始从上到下写答案了:遵循三个步骤:1.创建标号。2.连链。3.连接代码

      1. 创建标号:上面过程中我们创建了3个标号,就把它们的名字写到左边,右边newlabel。例如E2.true = newlabel。

      2. 连链主要是进行属性间的串联,对于E2如果不满足就要跳出去到S.next。那么就是E2.false = S.next。E3.label = S1.next(注意对于E来说只有true和false两个属性,不要再想E.next了哈!)

      3. 连接代码的过程就比较直观了,连接使用||(双竖线),按照图来,碰到代码块就写上xx.code。碰到标号就gen(‘xxx’,’:’),碰到goto就gen(‘goto’, ‘xxx’)。里面的xxx就是标号吗比如E2.true,E3.label这种

      经过以上的过程,相信你已经会写属性文法了。那翻译模式到底怎么写呢?二者有什么不同吗?且听我慢慢道来!
      还记得翻译模式的主要工作吗?在产生式中插入动作,完成属性的计算。在前面介绍过“遍”的概念,我们追求的应该是一遍完成所有功能。但在控制流语句中,涉及到语句间的跳转。如果在扫描时,还不知道具体的跳转位置怎么办呢?为了完美的完成这个任务,就需要一项技术——回填。
      回填的定义如下图:
    在这里插入图片描述
      下面列举一个回填与布尔表达式判断的例子:
    在这里插入图片描述
      例子中包含三个布尔表达式,对于布尔表达式实际隐含if的跳转语句。同样用两个综合属性E.t和E.f去链接条件表达式为“真”的所有跳转语句和为“假”所有跳转语句。但在从左往右的执行过程中,对于or操作符来说,前面的false会跳转到后面的起始位置。但目前还不知道后面的起始位置在哪里,但我们cd和ef规约之后就可以知道这个起始位置,到了那个时候再通过链表回填即可。
      同样再对产生式S->for(E1;E2;E3)S1,写其翻译模式
      结果直接贴图了:

    在这里插入图片描述
      我们来分析一下这个结果是怎么来的,这就还需要用到上面那个图:
      从图中可以看出有跳转,有标号。跳转的目的地一般是标号,在E2,E3,S1之前都有我们新建立的标号。按照之前翻译模式的构造方法,以M,N构造标号。即写出M->ε{M.quad=nextquad}这样的语义动作。再看下goto语句,总共有三处跳转,其中一个是布尔跳转,另外两个是goto跳转。前文提到跳转需要回填技术。在进行回填时,以M2.next去回填s1.nextlist(goto跳转)。以N.next去回填E2.truelist(if跳转),对于E2.falselist没有明确的回填目标。但已知触发E2.falselist会跳出循环,执行S后的语句,即S.nextlist。所以将S.nextlist与E2.falselist进行绑定。出现关于S.nextlist的赋值语句。下面还剩下一个goto语句,即E3后面的goto语句,目标地址E2(标号为M1)。对于goto语句总会有nextlist这个属性,从表达式和图中的对应位置来看,goto语句对应于N标记符号。说明它不仅承担标记的作用,还要完成跳转。所以把nextlist属性放到N上。按照回填的思路,用M1去回填N.nextlist。当写N的产生式时,一方面要提供标号即N.quad=nextquad,也要指定跳转,N.nextlist相当于我们自己加入的所以需要创建一个链表,即makelist。下面是跳转指令j,目标地址不确定。(可能这里会有人有疑惑,我们都知道N跳转的地址是M1,后面马上就要回填,这里怎么还能不知道跳到哪里呢?原因是这样的语句从左到右执行,回填语句发生在末尾。对于N来说,是一个独立的产生式,所有的语义动作都发生在N完全定义后。N只知道它前面的一些信息,而不知道后面的语义动作是如何规范它的。这也是我们留存一个链表的原因)。别忘记S1之后也有goto语句,emit产生一句即可。按照翻译模式的顺序,先emit动作再回填再连链,就完成了这个循环体的翻译模式书写。
      通过以上的举例,应该可以明白属性文法和翻译模式怎么写了吧,这就是语义分析的整个过程。

      存在这样一种情况,函数调用了另一个函数,或者调用结束后需要返回,那需要做些什么呢?
    在这里插入图片描述
    在这里插入图片描述
      对于第七章语义分析和中间代码产生写的时间非常长,不知从何下笔。究其原因,是对于属性文法和翻译模式的理解不到位(哦,第六章白写了!)同时对于布尔表达式的理解也有问题。
      现在回过头来看属性文法和翻译模式有了不一样的感觉。两者都是语义分析的方式,旨在赋予符号意义的同时分析意义是否符合我们的要求。翻译模式作为特定的一种属性文法,其表现形式有很多,诸如三地址代码形式、抽象语法树形式。以自下而上的规约过程为基础。回填技术的添加是为了满足一遍翻译的需求。
      惭愧的是,在写的时候,脑中大多是一些解题方法,而对于执行过程并没有一个想象的动态图。看来是理解不够,后续仍要继续加强完善!

    感谢编译原理课程谢老师对本文的认真修改,由于作者水平有限,如有错误之处请在下方评论区指正,谢谢!

    展开全文
  • Python实现的编译原理中间代码生成程序,使用了PyQt5写图形界面 题目:设计一个程序,该程序能够将形如x=y op z的简单赋值语句翻译为对应的四元式序列,其中op可为+、-、*、/等二元运算符。要求用图形界面方式编程. ...
  • 编译器通常组织为一连串的处理趟,随着编译器不断推导有关被编译代码的知识,它必须将这些信息从一趟传递到另一趟,因而,对于推导出有关程序的全部事实,编译器需要一种表示,我们将这种表示称为中间表示...

    一、IR分类及其性质

    编译器通常组织为一连串的处理趟,随着编译器不断推导有关被编译代码的知识,它必须将这些信息从一趟传递到另一趟,因而,对于推导出有关程序的全部事实,编译器需要一种表示,我们将这种表示称为中间表示(intermediate representation),简称为IR。如果源语言语法结构较为简单,编译器可能会用唯一的IR,如果源语言语法结构比较复杂(eg:rust),则在转换为目标语言的过程中可能会使用了一系列的IR。

    为记录编译器必须编码的所有细节,大多数编译器编写者都向IR添加了表和集合,以记录额外信息,这些表和集合也是IR的一部分。

    泛泛而言,IR从结构上分为三类:

    1. 图IR, 将编译器的知识编码在图中。算法通过图中的对象来表述:结点、边、列表、树。
    2. 线性IR, 类似于某些抽象机上的伪代码。相应的算法将迭代遍历简单的线性操作序列。本书使用的ILOC代码就是一种线性IR。
    3. 混合IR, 结合了图IR和线性IR的要素,为的是获取两者的优势而避免其弱点。一种常见的混合表示使用底层的线性IR来表示无循环代码的块,使用图来表示这些块之间的控制流。

    二、图IR

    许多编译器使用的IR将底层的代码表示为图。虽然所有的图IR都包含结点和边,但在抽象层次、图与底层代码之间的关系、图的结构等方面,各种图IR均有所不同。

    2.1 与语法相关的树

    1) 语法分析树

    语法分析树是对输入程序的推导或语法分析的图表示。相对于源程序文本,语法分析树比较大,因为它表示了完整的推导过程,树中的每个结点分别对应于推导过程中的各个语法符号,下图b是表达式a × 2 + a × 2 × b的语法分析树。
    在这里插入图片描述

    2) 抽象语法树

    抽象语法树(Abstract Syntax Tree, AST)保留了语法分析树的基本结构,但剔除了其中非必要的结点,表达式的优先级和语义仍然保持原样。这样可减少语法分析树边和节点分配访问内存等操作,从而减少编译器编译时所需时间,下图是表达式a × 2 + a × 2 × b的AST。
    在这里插入图片描述

    3) 有向非循环图

    虽然AST与语法树相比更加简洁,但它仍然保留了原来的源代码结构。例如,表达式a × 2 + a × 2 × b的AST包含了表达式a × 2的两个不同副本。有向非循环图(Directed Acyclic Graph, DAG)是AST避免这种复制的一种简写,其结点可以有多个父结点,相同子树可以被重用,DAG可以理解为是一种具有共享机制的AST。

    在表达式a × 2 + a × 2 × b中,a的值在两次表达式a × 2之间没有改变,所以只需要对a × 2求一次值,而后使用其结果两次,表即达式a × 2可以被共用,可生成如下图所示的DAG。这样做的前提是编译器能够证明a的值在此期间不会改变,如果表达式不包含赋值语句和过程调用,证明起来会比较容易。
    在这里插入图片描述

    4) 抽象层次(底层AST)

    上面介绍的语法分析树、AST和DAG都是接近源代码的IR,现在说一种比较底层的树。语句w <- a - 2 × b,下图a是该语句接近源代码形式的AST,图b是接近目标代码的底层AST,b相比于a多了很多AST => 汇编的实现细节。底层AST引入四种新的结点类型:

    • val结点表示一个值已经加载到某个寄存器;
    • num结点表示已知的常数;
    • lab结点表示汇编层次的标号,通常是一个可重定位符号;
    • 是一个运算符,它反引用一个值,该运算符将值作为内存地址处理,返回该地址处内存中的内容。

    底层AST揭示了对三个变量的地址计算。w存储在与r_arp中的指针偏移量为4处,r_arp中的指针指向当前过程数据区(编译器将具有相同生命周期和可见性的值存储在一起,这块存储区域称为数据区)的地址。对a的双重反引用表明a是一个传引用的形参,参数值本身是一个指针,存储在r_arp之前16字节处。最后,b存储在标号@G之后偏移量12字节处。
    在这里插入图片描述

    2.2 图

    1) 控制流图

    控制流图(Control-Flow Graph, CFG)对程序中各个基本程序块之间的控制流建立了模型。其中基本程序块指的是一段没有分支的代码序列,它开始于一个有标号的操作,结束于一个分支、跳转或条件判断操作。CFG用一个结点表示每个基本程序块,用一条边表示块之间的每个可能的控制转移(AST的边表明源代码的语法结构)。
    在这里插入图片描述
    编译器通常把CFG与另一种IR联用。CFG表示了块之间的关系,而块内部的操作则用另一种IR表示,如表达式层次上的AST、DAG或某种线性IR,由此得到的组合是一种混合IR。

    2) 依赖关系图

    编译器还使用图来编码模拟代码片段中值从创建之处(定义)到使用之处(使用)的流动,数据依赖关系图包含了这种关系。数据依赖关系图中的结点表示操作,大多数操作既包含定义,也包含使用。数据依赖关系图中的边连接两个结点,一个结点定义了一个值,而另一个结点使用该值,绘制依赖关系图时边从定义处指向使用处。如下图中从结点3指向结点7的边反映了r_b在语句3中的定义,及其在语句7中的使用。
    在这里插入图片描述

    数据依赖关系图通常用作衍生IR,即针对特定的任务从权威IR构建依赖关系图,使用依赖关系图完成任务,而后丢弃。如在指令调度领域,数据依赖关系图发挥了核心作用。数据依赖关系图在各种优化中都有应用,特别是在某些重排循环以揭示并行性和提高内存访问效率的转换中,这些转换通常需要对数组下标精密分析以便更精确地确定对数组的访问模式。

    3) 调用图

    表示程序中过程间接调用关系的图。调用图用一个结点表示每个过程,用一条边表示每个调用位置。

    三、线性IR

    图IR的备选方案是线性IR,线性IR对操作序列规定了一种清晰且实用的顺序。编译器中已经使用了许多种线性IR,如单地址代码、二地址代码以及三地址代码。

    3.1 堆栈机代码

    堆栈机代码是一种单地址代码,假定操作数存在一个栈中。大多数操作从栈获得操作数,并将其结果推入栈。例如,整数减法操作会从栈顶移除两个元素,并计算其差值,将结果 推入栈。堆栈机代码比较紧凑,栈本身建立了一个隐式的命名空间,从而消除了IR中的许多名字,缩减了IR形式下程序的大小。

    Smalltalk 80和Java都使用了字节码,这是一种紧凑的IR, 在概念上类似于堆栈机代码。下图是表达式a- 2 x b的栈式IR:
    在这里插入图片描述

    3.2 三地址代码

    在三地址代码中,大多数操作形如i <- j op k,其中包括一个运算符op,两个操作数jk,一个结果i。LLVM IR是一种三地址代码,如%3 = add i32 %0, %1,该IR是完全类型化的,对数组和结构地址提供了显式支持;LuaJIT的Bytecode和SSA IR也都是三地址代码结构,如ADDVV 2 0 10005 int LE 0004 +1000

    三地址代码相当紧凑,大多数操作包含四个项:一个操作和三个名字,操作和名字都取自有限集。操作通常占1或2个字节。名字通常由整数或表索引表示,但不论是哪种情况,4个字节通常就足够了。下图是表达式a- 2 x b的三地址代码:
    在这里插入图片描述

    3.3 线性代码的表示

    三地址代码通常实现为一组四元组。每个四元组表示为四个字段:一个运算符、两个操作数(或源)、一个目标。编译器可以用各种方法实现四元组,如简单数组、指针数组、链表等。

    下图是表达式a- 2 x b三地址码形式的存储实现方法:

    • 最简单的方案是图5-5a,其中使用一个短数组来表示各个基本程序块。通常,编译器编写者会将该数组放置到CFG中一个结点的内部。(这可能是混合IR最常见的形式。)
    • 5-5b中的方案使用指针数组将四元组分组到基本程序块中,该指针数组可包含在CFG结点中。
    • 5-5c是最后一个方案,其中将各个四元组连接起 来形成一个链表。这种方案在CFG结点中不需要太多存储,但代价是只能顺序遍历各个四元组。
      在这里插入图片描述

    一个多趟编译器可能在编译过程中的不同位置,使用不同的实现来表示IR。在前端,其关注点是生成IR,链表既可以简化实现,又可以降低总体代价。在指令调度器中,其关注点是操作的重排,因而两种基于数组的实现可能更有意义。

    3.4 根据线性代码建立控制流图

    编译器通常必须在不同IR之间进行转换(通常是不同风格的IR),一种例行转换是根据线性IR建立CFG。

    首先,编译器必须找到线性IR中各个基本程序块的开始和结束。我们将块中的第一个操作称为前导指令(leader)。如果一个操作是过程中的第一个操作,或者它有标号(即可能是某个分支指令的目标),那么它就是前导指令。如果线性IR包含并非分支指令目标的标号,那么将标号处理为前导指令可能导致块发生不必要的分裂。且如果代码包含任何具有二义性的跳转,那么它无论如何都必须将所有有标号语句处理为前导指令。之后,找到每个基本程序块结尾操作并添加边。

    四、将值映射到名字

    对特定IR和抽象层次的选择有助于确定编译器能够操控和优化的操作,如源代码层次上选择AST,接近目标机器的层次选择底层线性IR。类似地,编译器用来为执行期间计算出的各种值分配内部名字的规则,也对它能够生成的代码有所影响。

    4.1 临时值的命名

    程序的IR形式通常比源代码版本包含更多的细节,其中一些细节在源代码中是隐含的,而其他的细节则来自转换过程中有意的选择。图5-7a所示源代码只涉及四个名字{a,b,c,d},但它引用的值多于四个。在第一个语句执行之前,b、c和d都已经有值。第一个语句计算一个新值b + c;第二个语句同样计算一个新值a - d;第三个语句中的表达式b + c与前面第一个语句中的b + c计算的值是不同的,除非c和d的初始值相等; 最后一个语句计算了 a - d,其结果总是等同于第二个语句产生的结果。
    在这里插入图片描述
    5-7b中的代码比5-7c中的代码使用的名字要少。它沿袭了源代码中的名字,因此阅读者可以轻松地将该代码反向关联到图5-7a中的代码。与图5-7b中的代码相比,图5-7c中的代码使用了更多的名字,其命名规范反映了计算得出的各个值,并确保了文本相同的表达式会产生同样的结果。这种方案可以显而易见地反映ac会接收不同的值(使用了t3t5),而bd必定接收同一个值(使用了t6)。

    在底层IR中,各个中间结果都有自身的名字。使用不同的名字会将这些结果暴露给分析和变换的过程。编译器实现的大多数改进都来自对上下文的利用,所以为了改进,IR必须得暴露上下文信息。命名可能会隐藏上下文信息,因为其中可能将一个名字用于表示许多不同的值。命名也可能暴露上下文信息,只要它能够在名字和值之间建立对应关系。这个问题并不是线性代码的专有性 质,编译器完全可以使用底层的AST来暴露地址计算的全部信息。

    4.2 静态单赋值形式

    静态单赋值形式(Static Single-Assignment Form,SSA)是一IR,具有基于值的命名系统,通过重命名和使用称为Φ函数的伪操作产生的。静态单赋值形式中编码了控制的转移和值的流动,它广泛用于优化中。如果不了解SSA可以看看LLVM IR,或者北大编译实践SSA,主要理解为什么要用SSA形式。

    程序满足两种约束则为静态单赋值形式:

    • 1)每个定义都产生唯一的名字。
    • 2)每次 使用都引用单一的定义。

    Φ函数获取几个名字并将其合并,以定义一个新的名字。其行为取决于上下文,它选择其中一个参数的值来定义其目标SSA的名字。如LLVM IR和LuaJIT SSA IR中的PHI指令,就是Φ函数。下图是用SSA形式的IR表示一个循环:
    在这里插入图片描述

    4.3 内存模型

    编译器对每个值的存储位置的选择选择,对编译器的性能有非常大的影响,一般会使用以下两种内存模型:

    • 寄存器到寄存器的模型(Register-to-Register Model),编译器采取激进策略将值保存在寄存器中,而忽略机器的物理寄存器集合规定的任何限制。对任何值来说,如果它在大部分生命周期中可以合法地保存在寄存器中,那么编译器就选择将其置于寄存器中,只有程序的语义要求将值存储到内存时,编译器才采取相应的操作;如果值在大部分生命周期中无法存放在寄存器中,则将其存储在内存中,编译器会生成相应的代码,在每次计算出值时,将存储到内存,而每次使用值时,将其从内存加载进来。
    • 内存到内存的模型(Memory-to-Memory Model) ,编译器假定所有值都保存在内存中,值在临到使用之前,从内存加载到寄存器。在值定义完毕后,即从寄存器写出到内存。与寄存器到寄存器的模型比较,这种模型下代码的IR版本中引用的寄存器数目要小一些。在这种模型中, 有必要向IR添加内存到内存的操作,如内存到内存的加法。

    如果使用寄存器到寄存器的模型,IR使用的寄存器通常比目标机提供的寄存器更多。因而,寄存器分配器必须将IR程序中使用的虚拟寄存器集合映 射到目标机提供的物理寄存器上。这通常要求插入额外的加载、存储和复制操作,使得代码更大和更慢。

    如果使用内存到内存的模型,代码的IR版本使用的寄存器通常少于目标机提供的寄存器。这种情况下,寄存器分配器需要寻找基于内存的值,并在可能情况下使之长时间驻留在寄存器中。在这种模型中,分配器通过删除掉加载和存储操作,使代码变得更快且更小。

    五、符号表

    作为转换过程的一部分,编译器需要推导源程序中操控的各种对象有关的信息,必须发现并存储它们,如:变量、已定义常数、过程、函数、标号、结构和文件。

    • 对于一个变量,它需要的信息包括数据 类型、存储类别、声明变量的过程的名字和词法层次以及变量在内存中所处的位置(基地址和偏移量)。
    • 对于数组,编译器还需要数组的维数和各维度上索引的上下界。
    • 对于记录或结构而言,编译器 需要成员字段的列表以及每个字段的相关信息。
    • 对于函数和过程,编译器需要参数的数目及各参数 的类型,以及可能的返回值的类型;在更复杂的转换过程中,可能会记录过程可能引用或修改的变量的相关信息。

    编译器需要在IR中记录这些信息,或者按需重新推导计算,别无它法。为效率起见,大多数编译器都选择记录,而非在需要时重新计算。这些信息可以直接记录在IR中,但是访问会比较低效;也可以为这些事实建立一个中央存储库,以提供对相关信息的高效访问能力,这种中央存储库称为符号表

    5.1 散列表

    散列表使用散列函数h将名字映射成小整数,通过得到的小整数来索引表,编译器可以将其推导出的有关名字n的全部信息,存储在表中的槽位h(n)处,如下图中h(b) == 1,h(d) == 2
    在这里插入图片描述

    5.2 建立符号表

    符号表为编译器其余部分定义了两个接口例程。

    1. LookUp(name):如果表中h(name)处存在一个记录,则返回该记录。否则,函数返回一个值, 表明没有找到name
    2. Insert(name, record):将record中的信息存储在表中h(name)处。该函数可能扩展散列表,以容纳为name添加的记录。

    5.3 处理嵌套的作用域

    下图给出了一个C语言程序,其中创建了5个不同的作用域,用数字标记各个作用域,以标明它们之间的嵌套关系。层次0的作用域是最外层的作用域,而层次3的作用域是最内层的,其中有一条赋值语句b = a + b + c + w
    在这里插入图片描述
    为管理嵌套作用域,语法分析器必须稍微改变一下其管理符号表的方法。语法分析器每次进入一个新的词法作用域时,它将为该作用域建立一个新的符号表。这种方案将创建一“束”符号表,按词法作用域层次的嵌套关系连接在一起。当语法分析器在当前作用域中遇到声明时,就将相应的信息输入到当前符号表中。Insert只操作当前作用域的符号表。当遇到变量引用时,Lookup必须首先检查当前作用域的符号表,如果当前符号表并不包含对该名字的声明,则在嵌套作用域层次中向外一层,检查该层次的符号表。整个过程依次类推,在词法作用域的嵌套层次中不断向外,检查编号不断变小的 层次对应的符号表;这个过程或者在最接近的作用域中找到名字的声明,或者一直到最外层的作用域 也未能找到声明,后一种情况表明该变量没有在当前作用域可见的声明。

    下图给出了为图5-10程序建立的符号表,当编译器对名字b调用修改过的Lookup函数时,函数在层次3、层次2都将失败,而会在层次1找到名字b。
    在这里插入图片描述
    如果处理上述方案,需要两个额外的调用。编译器需要一个调用来为作用域初始化一个新的符号表, 还需要另一个调用为作用域释放符号表。

    1. InitializeScope()将当前层次加1,并为该层次创建一个新符号表。它将新的符号表连接到上一层次的符号表,并更新LookupInsert使用的当前层次指针。
    2. FinalizeScope()改变当前层次指针,使之指向上一层次作用域的符号表,然后将当前层次减1。 如果编译器必须保留各个层次上的符号表供后续使用,那么FinalizeScope或者将符号表留在内存中不动,或者将其写出到外部介质并回收其内存空间。

    对图5-10中的程序,这种方案将产生以下调用序列:
    在这里插入图片描述
    编译器在进入每个作用域时都调用InitializeScope,它使用Insert将当前作用域中声明的每个名 字添加到当前符号表。在它离开给定的作用域时将调用FinalizeScope,以丢弃该作用域中的声明。对于赋值语句,编译器将分别查找遇到的每个名字。(调用Lookup的顺序是可变的,这依赖于编译器如何 遍历赋值语句中的各个标识符。)

    5.4 符号表的许多用途

    1、结构表

    在结构或记录中,有的字段文本串可能会函数或过程中的变量命名冲突,且对于结构中的每个字段,编译器必须记录其类型、大小及其在记录内部的偏移量。所以有以下几种方法管理字段命名空间:

    • 独立表:编译器可以为每个记录定义维护一个独立的符号表,并将其关联到结构名在主符号表中对应的表项。这种做法一般是最常用的。
    • 选择符表:编译器可以为所有字段名维护一个独立的表。为避免不同结构中同名字段之间的冲突,需要修饰字段名(为字段名添加一个前缀,前缀可以是结构名)。
    • 统一表:通过使用修饰名,编译器可以将字段名存储在其主符号表中。这种方式能不用就不用,纯粹给自己挖坑。

    2、使用链接表解决面向对象语言中的名字解析问题

    面向对象的语言,会有class,以及class对象的继承、多态等特性。所以每个类都需要一个符号表,这种符号表应该包含一个链接,指向继承层次中父类的符号表。

    如在编译类C中的方法m时,如果要解析一个名字fee,编译器首先查询(对应于m的)词法上作用域化的符号表。如果在该表中没有找到fee,编译器接下来查找继承层次中类的作用域,从C开始向上逐 个查找C的各个超类的作用域。如果这种查找无法找到fee,那么查找过程接下来会检查全局符号表查找名为fee的类,或查找该包的符号表。

    展开全文
  • 编译原理--中间代码生成

    千次阅读 2020-01-08 15:25:16
    语法树是一图形化的中间表示。但语法树中,公共子表达式每出现一次,就有一个对应的子树,产生了大量冗余, 因此定义了另一种中间表示:有向无环图(Directed Acyclic Graph, DAG) 有向无环图的构造与抽象语法树...

    基础

    DAG

    语法树是一种图形化的中间表示。但语法树中,公共子表达式每出现一次,就有一个对应的子树,产生了大量冗余,
    因此定义了另一种中间表示:有向无环图(Directed Acyclic Graph, DAG)
    有向无环图的构造与抽象语法树类似。
    在这里插入图片描述

    三地址代码

    一般包括一个运算符和之多三个运算分量(地址),所以叫做三地址代码。这里的地址包括:变量、常量、临时变量。

    • 指令集合
      • 运算/赋值指令:x=y op z ,x = op y
      • 复制指令:x=y
      • 无条件转移指令:goto L
      • 条件转移指令:if x goto L ,ifFalse x goto L
      • 条件转移指令:if x relop y goto L
      • 过程调用/返回 p(x1, x2, …, xn)
        • param x1 //设置参数
        • param x2
        • …
        • param xn
        • call p, n //调用子过程p,n为参数个数
      • 带下标的复制指令:x=y[i] x[i]=y • 注意:i表示离开数组位置第i个字节,而不是数组的第i个元素
      • 地址/指针赋值指令: • x=&y x=*y *x=y

    在这里插入图片描述

    • 三地址代码的四元式表示
      格式(字段): op arg1 arg2 result
      如:+ x y z
      对于有些指令,一些参数是空缺的,如
      param x1 null null
      [if goto] x null L
      在这里插入图片描述
    • 三地址代码的三元式表示
      op arg1 arg2
      使用三元式的位置来引用三元式的运算结果
      在这里插入图片描述
    • 三地址代码的间接三元式表示
      包含了一个指向三元式的指针的列表  我们可以对这个列表进行操作,完成优化功能;操作时不 需要修改三元式中的参数
      在这里插入图片描述
    • 静态单赋值SAA
      在这里插入图片描述

    问题

    声明语句的翻译

    PPT 24-54

    表达式和赋值语句的翻译

    在这里插入图片描述

    • 数组引用生成代码的翻译方案

    非终结符号L的三个综合属性

    1. L.addr指示一个临时变量,计算数组引用的偏移量 ij * wj
    2. L.array是一个指向数组名字对应的符号表条目的指针, L.array.base为该数组的基地址
    3. L.type是L生成的子数组的类型,对于任何数组类型t,其宽度由 t.width给出,t.elem给出其数组元素的类型
      在这里插入图片描述

    控制流翻译

    • 文法:B表示布尔表达式,S代表语句 S → if (B) S1 ; S → if (B) S1 else S2 ;S → while (B) S1 . 代码的布局见下图
      在这里插入图片描述
    • 继承属性
      • B.true:B为真的跳转目标
      • B.false:B为假的跳转目标
      • S.next:S执行完毕时的跳转目标

    例: S ⟶ i f   B   t h e n   S 1 S\longrightarrow if\ B\ then\ S_1 Sif B then S1
    在这里插入图片描述
    在这里插入图片描述

    布尔表达式的翻译

    • 当布尔表达式的计算用于跳转分治

    布尔表达式翻译的主要语义动作是跳转,而跳转的标签主要根据短路规则来确定。
    在这里插入图片描述
    在这里插入图片描述

    • 当布尔表达式的计算用于赋值
      采用临时变量的方法
      在这里插入图片描述

    switch 语句的翻译

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

    过程调用的翻译

    在这里插入图片描述

    回填

    布尔表达式用于语句的控制流时,它总是在取值true时和取值false 时分别跳转到某个位置

    • 引入两个综合属性

      • truelist: 包含跳转指令(位置)的列表,这些指令在取值true时执行
      • falselist:包含跳转指令(位置)的列表,这些指令在取值false时执行
    • 辅助函数

      • Makelist(i):创建一个只包含i的列表
      • Merge(p1,p2):将p1和p2指向的列表合并
      • Backpatch(p,i):将i作为目标标号插入到p所指列表中的各指令中
        在这里插入图片描述
        在这里插入图片描述
    • 控制转移语句的回填
      M的作用就是用M.instr记录下一个指令的位置 • N的作用是生成goto指令坯,N.nextlist只包含这个指令 的位置

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

    展开全文
  • 编译原理及实现技术:20.中间代码生成_表示形式、语法制导方法.ppt
  • 编译原理 中间代码表示

    千次阅读 2018-10-20 23:03:31
    将抽象层次逐渐降低,有的优化只能在特定的中间表示上才行。 地址码: 不绑定特定的指令集,是抽象的类型 每个地址码只完成一条指令,没有复合的情况出现。 如何生成地址码?     ...
  • 编译原理--中间代码生成

    千次阅读 2022-04-01 21:59:30
    构造DAG的值编码方法 语法树或DAG图中的结点通常存放在一个记录数组中. 假定结点按图6-6所示的方式存放在一个数组中, 每个结点通过其值编码引用. 设每个内部结点的泛型为三元组<op, l, r>, 其中op是标号...
  • 中间语言(简述) ▍后缀表达式 后缀表达式最大的优点是便于计算机处理(栈) ...有向无环图(DAG)也是一图形化的表示方法 构造语法树便于分析语法制导的语义计算 >>>【典例】 >>> a =
  • 编译原理-中间代码生成

    千次阅读 2019-04-17 10:43:52
    如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,移植性差。 1.2 表示形式 逆波兰式(后缀式)、地址码(三元式、四元式)、...
  • 一、生成中间代码的目的 便于优化 让生成的目标代码效率更高 优化不等同于对代码的精简和算法的优化 (对于高级程序设计语言中可能不能继续进行优化,但是仍然可以在编译中进行优化) 比方说多维下标变量地址计算...
  • 【编译原理】中间代码(二)

    万次阅读 多人点赞 2017-12-13 09:37:46
    本文是关于中间代码的第二篇文章。在第一篇文章中,我们介绍了3种表示中间代码方式,本文将接着介绍和静态类型检查以及中间代码生成相关的内容。
  • 中间代码是介于源语言程序和什么之间的一代码?(D)。 A 源代码 B 机器语言 C 汇编语言 D 目标代码 在编译程序中与生成中间代码的目的无关的是(B)。 A 便于目标代码优化 B 便于存储空间的组织 C 便于目标代码...
  • 【编译原理】中间代码(一)

    万次阅读 多人点赞 2017-12-05 15:08:56
    在编译器的分析-综合模型中,前端对源程序进行分析并产生中间表示,后端在此基础上生成目标代码。...和中间代码相关的内容包括中间代码表示、静态类型检查和中间代码生成,本文将讨论关于中间代码表示的内容。
  • 中间代码生成器

    2013-06-13 22:36:45
    非常棒的资源,其中包括了逆波兰表达式和三元组的表示,做实验非常实用
  • 编译原理-中间代码的生成

    千次阅读 2020-03-30 19:17:46
    一、中间代码简介 中间代码应具备的特性: 1)便于语法制导翻译 2)既与机器指令的结构...最常用的中间代码形式是地址码,它的实现形式常采用四元式形式。 符号表是帮助声明语句实现存储空间分配的重要数据...
  • 表达式中间代码生成 二、实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 、实验内容 1. 构造算术表达式的四元式翻译文法 2. 设计算术表达式的递归下降子程序分析算法 3. 设计算术表达的四元式生成算法...
  • 编译原理:中间代码生成

    千次阅读 2020-08-22 15:42:19
    一,基本概念 翻译为中间语言的好处: (1)便于进行与机器无关的代码优化; (2)使编译程序改变目标机更容易;易于编译器的移植 ...(3)使编译程序的结构在逻辑...地址代码:四元式,三元式,间接三元式 二,.
  • IRDiff:基于LLVM中间表示代码差异分析,胡文颖,梁洪亮,代码差异分析是多版本程序分析领域中重要的研究问题之一。已有的工作,包括基于代码行的比较或基于抽象语法树的代码分析,往往会
  • 【编译原理】第六章 中间代码生成

    千次阅读 2019-07-11 23:58:30
    中间代码也叫中间语言(Intermediate code /language)是:源程序的一内部表示,不依赖目标机的结构,复杂性介于源语言和机器语言之间。 中间代码常见的几形式 1、后缀式 2、图表示法 抽象语法树、DAG图 3、...
  • 编译原理实验 语义分析与中间代码生成 Sample语言的语义和代码生成规则,熟悉Sample语言的语义分析和代码生成过
  • 表达式中间代码生成 二、实验目的 熟悉算术表达式的语法分析与中间代码生成原理。 、实验内容 1. 构造算术表达式的四元式翻译文法 2. 设计算术表达式的递归下降子程序分析算法 3. 设计算术表达的四元式生成算法...
  • 文章目录一、什么是后缀式?1.后缀式的特点是什么?2.如何将中缀式转换成后缀...2.三地址码的三种表示形式:三元式、四元式、间接三元式;3.三元式、四元式、间接三元式各自优缺点4. 三元式与间接三元式之间的区别5....
  • 目标代码有哪几形式?生成目标代码时通常应考虑哪目标代码有哪几形式?生成目标代码时通常应考虑哪几个问题?...(采用中间代码是把源程序映射成中间代码表示,再映射成目标代码的工作分在几个阶段进行,使编译...
  • 编译器前端对中间代码进行优化 编译器后端对目标代码进行优化 两个编译器必须等价,编译的结果必须是正确的,即使有99.99%的可能性是不正确的,但是效率很好也不行,正确性是根本。 二、中间代码优化的分类 从...
  • 编译原理之中间代码生成

    千次阅读 2020-04-07 12:35:44
    源程序的一内部表示,不依赖目标机的结构,易于机械生成目标代码的中间表示。 如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,...
  • 常用的中间代码表示形式:后缀式、树形式、三元式、四元式
  • 中间代码生成之四元式

    千次阅读 2020-07-10 23:43:42
    四元式是一地址语句”的等价表示。一般形式:( op , arg1 , arg2 , result ) 即<操作符>,<操作数1>,<操作数2>,<结果> 其中,op为一个二元(也可是一元或零元)运算符; arg1,arg2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 630,710
精华内容 252,284
关键字:

中间代码三种表达方式

友情链接: wireless1.zip