帝国小说网站模板,wordpress全站源码,宁波小程序开发,网站后台的数据库怎么做#x1f308; 个人主页#xff1a;十二月的猫-CSDN博客 #x1f525; 系列专栏#xff1a; #x1f3c0;编译原理_十二月的猫的博客-CSDN博客 #x1f4aa;#x1f3fb; 十二月的寒冬阻挡不了春天的脚步#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录
1. 前言
2. … 个人主页十二月的猫-CSDN博客 系列专栏 编译原理_十二月的猫的博客-CSDN博客 十二月的寒冬阻挡不了春天的脚步十二点的黑夜遮蔽不住黎明的曙光 目录
1. 前言
2. 章节导读
3. 属性文法
3.1 综合属性与继承属性
综合属性
继承属性
3.2 不同属性文法
S-SDD
L-SDD
4. 语法制导定义SSD
4.1 根据属性文法构造分析树依赖图
4.1.1 S-SDD分析树
4.1.2 L-SDD分析树
编辑
4.2 分析树的计算顺序
5 抽象语法树
6. 语法制导翻译
5.1 S属性文法的自下而上计算语法制导翻译的实现
7. 总结 1. 前言
为什么打算开始这一系列的文章——编译原理
其实本学期开始就一直想持续更新陆陆续续主要更新了实验部分。
正好趁着快要考试便和大家一起花费几天的时间回顾编译原理的知识点。
目前十二月猫的回顾计划如下
祝大家都能取得好成绩呀~~ 参考书籍 英文名Compilers: Principles,Techniques,and Tools 龙书 作者Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman 1本课程介绍编译器构造的一般原理和基本实现方法主要介绍编译器的各个阶段词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。 2本课程在介绍命令式程序设计语言实现技术的同时强调一些相关的理论知识如形式语言和自动机理论、语法制导的定义和属性文法、类型论等。 3本课程强调形式化描述技术并以语法制导定义作为翻译的主要描述工具。 4本课程强调对编译原理和技术在宏观上的理解而不把读者的注意力分散到一些枝节的算法上如计算开始符号集合和后继符号集合的算法回填技术等。作为原理性的教材本书介绍基本的理论和方法而不偏向于某种源语言或目标机器。 2. 章节导读 如果问起来编译原理最迷的一章是什么很多同学的回答将会是这一章课本里讲了众多的不知道为什么会有的定义和莫名其妙的附加规则但偏偏没有讲它们是为什么来的。你如果不信想想这几个问题为什么会有属性文法有了那么多语法分析方法找出了语法错误对编译器难道不够么它跟语法分析有什么联系呢 首先我们要清楚编译器的工作并不是仅限于我们表面上在IDE里写程序时给我们提醒各种错误其更重要的工作是将我们的源程序翻译成“目标代码”翻译成机器能切切实实执行的代码这是它最初最核心的功能。也就是说编译器首先要理解我们的源程序到底是想让机器干什么这就是“语义”你说学到目前的章节为止编译器有能力知道么 没有哦编译器现在通过词法语法分析只知道了“结构”举个例子它现在知道 “if (a b) { i}”是符合语法的“if (a b) { i }”是不符合语法的因为构造不出语法分析树但真的 a b了计算机应该干什么呢它现在还不知道该i呢只有我们学完了这两章通过附加语义规则让计算机理解了if E {S}这个语法结构的语义是如果E是真的就执行S的操作我们才有可能让计算机理解并执行我们的源程序。 第六章主要站在方法论的角度讨论可以用什么样的方式来对不同的属性文法进行翻译而第七章则举出了几个常用的例子如何翻译布尔表达式的语义如何翻译控制语句的语义来应用第六章讨论的方法明白所处的位置了吧让我们开始 一定要看 表示语义——属性文法语义分析——属性求值属性求值——属性先后计算顺序属性先后计算顺序——依赖图和拓扑排序语义分析和语法分析同时进行——两者顺序需要一样 3. 属性文法 属性文法用来表示语义 拿个实在的例子对于台式计算器的语法制导定义 左边的一列我们前几章都熟悉是产生式右边的就是导读中解释的“语义规则”即告诉计算机看到左边产生式该干什么比如看到 E — E1 T这样的语法结构语义规则告诉计算机应当做加法把E和T的值加起来E.val : E1 .val T.val。 属性文法的定义由此而来我们把左边的产生式和右边的语义规则的结合叫属性文法对于每个文法符号如E它都有对应的属性如.value。 关键点 属性文法 产生式 语义规则在语义规则中给了文法以属性 3.1 综合属性与继承属性 综合属性是信息流流向产生式左部的属性在语法树中体现为S属性节点被其子节点的属性值确立继承属性是流向产生式右部的属性在语法树中体现为被其父节点或兄弟节点的某些属性值确立的。 简单来说 综合属性就是从右流向左的属性从分析树的下面流向上面。继承属性就是从左流向右部的属性从兄弟节点和父节点流过来的属性 综合属性
在分析树上结点N的综合属性通过N的子节点和N本身的属性值来定义。
例如对于产生式E→E1TE→E1T综合属性对应的语义规则可以是E.valE1.valT.valE.valE1.valT.val。
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值因此在SDD中没有计算终结符属性值的语义规则。
继承属性
在分析树上N结点的继承属性只能通过N的父节点、兄弟节点或者N本身的属性值来定义。
终结符没有继承属性终结符从词法分析器处获得的属性值被归为综合属性值。
3.2 不同属性文法
右边语义规则存在不同的写法这会产生不同的属性文法类型。
不同的属性文法处理的方法也不同。 出现不同属性文法的原因就是为了匹配语义分析的流程让语义分析和语法分析同时进行 S-SDD
仅仅使用综合属性的SDD称为S属性的SDD也叫S-属性定义S-SDD。
例如 这里面所有属性均是综合属性都是根据子构造的属性 计算出父构造的属性所以可以自底向上的计算每个属性。
L-SDD
L-属性定义也叫L属性的SDD或者L-SDD。
一个SDD是L-属性定义当且仅当它的每个属性要么是一个综合属性要么是满足如下条件的继承属性假设存在一个产生式A→X1X2...Xn其右部符号Xi(1≤i≤n)的继承属性仅依赖于下列属性
A的继承属性产生式中XiXi左边的符号 X1,X2,…,Xi−1 的属性Xi本身的属性但Xi的全部属性不能在依赖图中形成环路
所以对于L-SDD所有的分析树属性都依赖于左边或者下边的节点。所以不会存在环路。
每个S-属性定义都是L-属性定义
4. 语法制导定义SSD 语法制导定义和属性文法分不开关系就是有属性文法我们才能根据属性文法和产生式构造出分析树并根据分析树进行语法制导翻译完成语义分析。
4.1 根据属性文法构造分析树依赖图
4.1.1 S-SDD分析树
属性文法如下 S-SDD分析树如下 4.1.2 L-SDD分析树 在上面这个SDD就是一个带有继承属性的SDD。首先根据产生式(1)对应的语义规则得到了最上面的L.inhT.typereal然后根据产生式(4)对应的语义规则得到Lbellow.inhLup.inh然后同样的道理依据产生式(4)得到Lbellow.inhLup.inh。
4.2 分析树的计算顺序 这边的计算顺序也就是语义分析的顺序。这里的SDD语义分析顺序和语法分析顺序没有关系。S-SDD和L-SDD语义分析顺序和语法分析顺序相联系。 SDD为CFG中的文法符号设置语义属性。对于给定的输入串xx我们将应用语义规则计算分析树中各结点对应的属性值。SDD声明了语法分析树上属性之间的依赖关系按照这种依赖关系的拓扑排序可以确定他们的求值顺序。
依赖图是一个有向图它描述了分析树中结点属性之间的依赖关系。一个依赖关系图有拓扑排序的充要条件是无环。一个依赖图的示例如下所示 一般说来给定一个SDD很难确定是否存在某棵语法分析树但是**S-属性定义S-SDD和L-属性定义L-SDD**一定存在一个拓扑排序并且这两类SDD可以和自顶向下和自底向上的语法分析过程一起实现。 不同属性文法语法制导得到的分析树如何计算 L里面所有属性均是综合属性都是根据子构造的属性计算出父构造的属性所以可以自底向上的计算每个属性。对于L-SDD所有的分析树属性都依赖于左边或者下边的节点。所以不会存在环路。 5 抽象语法树 适用于翻译的语法结构不只是语法分析树抽象语法树将操作符和关键字都不作为叶节点而是把它们当作内部节点使用如下产生规则构造可以看出它的核心就在于只为idnum运算符创造节点mkleafmknodeT到EF到T的规约E到F的规约只是子树的转移。 最终对a5*b构造抽象语法树的结果如下图所示画出如何通过属性文法边分析语法结构绿线边构造抽象语法树红线也是一个很重要的考察点。 6. 语法制导翻译
将一个S-SDD转换为SDT的方法将每个语义动作都放在产生式的最后 这就是在做语法归约时从右往左去进行除了推导外要加上语义信息 将L-SDD转换为SDT
将计算L-SDD某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上。将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端 这就是在做语法推导时除了推导外要加上语义信息 SDT可以看作是对SDD的一种补充是SDD的具体实施方案它明确指明语义规则的计算顺序说明实现细节。 5.1 S属性文法的自下而上计算语法制导翻译的实现 如果一个SDD的基础文法是LR文法并且此SDD是S属性定义的那么我们可以构造这样一个SDT其中的每个动作都放在产生式的最后并且在按照这个产生式将产生式体归约为产生式头的时候执行这个动作。像这样所有动作都在产生式体最右端的SDT也称为后缀翻译方案后缀SDT。 将一个S属性定义的且基础文法为LR文法的SDD转换为一个SDT的规则如下
将计算一个产生式头的综合属性的动作放置在这个产生式体的最右端。 注意到由于表1中的SDD是S属性定义的且其基础文法G是LR文法因此可以把它转换成后缀SDT表3中的SDT就是此SDD的一个转换形式。下面我们进一步改进表3中的SDT使其能够在语法分析过程中实现 表4中的stack表示LR语法分析栈top指向栈顶。为了帮助读者理解这个SDT中的语义动作以产生式F→(E)为例考虑将(E)归约成F的过程如图6所示 图6显示了把(E)归约成F的LR语法分析过程。图6(a)是即将把(E)归约成F的语法分析栈快照此时有stack[top])stack[top-1]Estack[top-2](。执行的归约动作是连续3次出栈操作将”)”、”E”、”(“依次弹出栈顶如图6(b)和1次入栈操作将”F”压入栈顶如图6(c)。注意到(c)中的top相当于(a)中的top-2也就是说F实际上出现在(a)中的stack[top-2]处另外由于E.val将被赋值给F.val并且E出现在(a)中的stack[top-1]处因此在(a)中有stack[top-2].valstack[top-1].val将(a)变成(c)还需要执行2次出栈操作实际上是3次出栈操作和1次入栈操作因此还需要把top指针向下移动2位。
5.2 从SDT中消除左递归 在详细介绍如何在语法分析过程中实现L属性定义的SDT之前我们先来介绍如何从SDT中消除左递归。在介绍语法分析的时候我们知道了带有左递归的文法不能按照自顶向下的方式进行语法分析并且我们还知道如何从一个左递归的文法中消除左递归。当文法是SDT的一部分时我们还需要考虑如何处理其中的语义动作。
情况1
最简单的情况是我们只需要关心一个SDT中动作的执行顺序。在这种情况下当对文法进行消除左递归的转换时可以简单地将动作当成终结符号处理。之所以可以这样做是因为对文法的转换保持了由文法生成的符号串中终结符号的顺序。举个例子对下面的SDT E → ET { print(); }E → T
将动作看作终结符号消除左递归后得到的SDT为 E → TRR → T { print(); } R | ε 情况2
另一种比较复杂的情况是一个SDT的动作包含了对属性值的计算。举个例子对下面的SDT A → A1Y { A.a g(A1.a, Y.y); }A → X { A.a f(X.x); }
现在尝试在文法中加入语义动作。我们给文法符号R附加上两个属性一个属性i是继承属性它用来保存函数f和g的结果另一个属性s是综合属性它会在计算结束后返回最终的计算结果。得到的SDT为 A → X { R.i f(X.x); } R { A.a R.s; }R → Y { R1.i g(R.i, Y.y); } R1 { R.s R1.s; }R → ε { R.s R.i; }
5.3 S属性文法的自上而下计算语法制导翻译的实现
如果一个SDD的基础文法能够以自顶向下的方式进行语法分析并且此SDD是L属性定义的那么我们可以把这个SDD转换成一个L属性定义的SDT。
将一个L属性定义的SDD转换为一个SDT的规则如下
将计算某个非终结符号A的继承属性的动作插入到产生式体中紧靠在A的本次出现之前的位置上。如果A的多个继承属性以无环的方式相互依赖就需要对这些属性的求值动作进行排序以便先计算需要的属性将计算一个产生式头的综合属性的动作放置在这个产生式体的最右端。
在语法分析过程中实现L属性定义的SDT的方法包括
使用一个递归下降的语法分析器。它为每个非终结符号都建立一个函数对应于非终结符号A的函数以参数的形式接受A的继承属性并返回A的综合属性使用一个递归下降的语法分析器以边扫描边生成的方式生成代码与LL语法分析器结合实现一个SDT。属性的值存放在语法分析栈中各个规则从栈中的已知位置获取需要的属性值与LR语法分析器结合实现一个SDT。如果基础文法是LL的我们总是可以按照自底向上的方式来处理语法分析和翻译过程。
6. 一些习题
例一
解答 例二 解答 7. 总结
本文到这里就结束啦~~
本系列专栏将专注于【编译原理】知识。
内容包括知识点讲解、习题练习、重点知识带练等~~目前已完成
【编译原理】编译原理知识点汇总·概论与文法-CSDN博客
【编译原理】编译原理知识点汇总·词法分析器正则式到NFA、NFA到DFA、DFA最小化-CSDN博客
【编译原理】编译原理知识点汇总·语法分析器消除左递归、消除二义性、自顶向下语法分析、自下向上语法分析-CSDN博客
【编译原理】词法分析器设计山东大学实验一_山东大学编译原理实验-CSDN博客
【编译原理】语法、语义分析器设计山东大学实验二_语法分析实验-实现一个简单语法分析器(自上而下方法)实验小结-CSDN博客
【编译原理】代码生成器的构建与测试山东大学实验三_编译原理实验语义分析代码-CSDN博客 【编译原理】一篇搞定正规式到NFA、NFA到DFA、DFA最小化-CSDN博客
【编译原理】一篇搞定语法分析器对文法的要求上下文无法文法、消除二义性文法、消除左递归-CSDN博客
【编译原理】一篇搞定LR分析法LR(1)、LR(0)、SLR、LALR-CSDN博客
期待您的关注~~
猫猫陪你永远在路上
如果觉得对你有帮助友友们可以点个赞收个藏呀~
