❶ 【编译原理】第二章:语言和文法
上述文法 表示,该文法由终结符集合 ,非终结符集合 ,产生式集合 ,以及开始符号 构成。
而产生式 表示,一个表达式(Expression) ,可以由一个标识符(Identifier) 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹( )构成。
约定 :在不引起歧义的情况下,可以只写产生式。如以上文法可以简写为:
产生式
可以简写为:
如上例中,
可以简写为:
给定文法 ,如果有 ,那么可以将符号串 重写 为 ,记作 ,这个过程称为 推导 。
如上例中, 可以推导出 或 或 等等。
如果 ,
可以记作 ,则称为 经过n步推导出 ,记作 。
推导的反过程称为 归约 。
如果 ,则称 是 的一个 句型(sentential form )。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ,记作 。
即:
例
文法
表示什么呢?
代表小写字母;
代表数字;
表示若干个字母和数字构成的字符串;
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是,以字母开头的、非空的字符串,即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为:
中必须包含一个 非终结符 。
产生式一般形式:
即上式中只有当上下文满足 与 时,才能进行从 到 的推导。
上下文有关文法不包含空产生式( )。
产生式的一般形式:
即产生式左边都是非终结符。
右线性文法 :
左线性文法 :
以上都成为正则文法。
即产生式的右侧只能有一个终结符,且所有终结符只能在同一侧。
例:(右线性文法)
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串(标识符)。
以上文法等价于 上下文无关文法 :
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词,但不能表示句子构造,所以用到最多的是CFG。
根节点 表示文法开始符号S;
内部节点 表示对产生式 的应用;该节点的标号是产生式左部,子节点从左到右表示了产生式的右部;
叶节点 (又称边缘)既可以是非终结符也可以是终结符。
给定一个句型,其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2,那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部,但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ,则称这个文法是 二义性的 。
二义性原因:多个if只有一个else;
消岐规则:每个else只与最近的if匹配。
❷ 编译原理
编译原理):利用编译程序从源语言编写的源程序产生目标程序的过程; 用编译程序产生目标程序的动作。 编译就是把高级语言变成计算机可以识别的2进制语言,计算机只认识1和0,编译程序把人们熟悉的语言换成2进制的。
编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段:词法分析;语法分析;语义检查和中间代码生成
(2)编译原理推导是什么意思扩展阅读:
编译程序的语法分析器以单词符号作为输入,分析单词符号串是否形成符合语法规则的语法单位,如表达式、赋值、循环等,最后看是否构成一个符合要求的程序,按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构,程序是最终的一个语法单位。
编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种:自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发,向下推导,推出句子。
而自下而上分析法采用的是移进归约法,基本思想是:用一个寄存符号的先进后出栈,把输入符号一个一个地移进栈里,当栈顶形成某个产生式的一个候选式时,即把栈顶的这一部分归约成该产生式的左邻符号。
❸ (编译原理) 求下述文法对应正规式: S->0A|1B A->1S|1 B->0S|0
一、简单的推导思路
1、该文法的对应正规式为:[01|10]+
2、推导:
(1)首先,展开产生式S,可知S要么以0开头,要么以1开头;
(2)如果S按产生式S->0A展开,则S必以01开头,因为通过产生式A->1S|1可知,A必定是以1开头的;
(3)如果S按产生式S->1B展开,则S必以10开头,因为产生式B必定以0开头;
(4)综上,可知,S是以01或10开头的非终结符号;
(5)当A以产生式A->1展开或 B以B->0展开时,S将推导结束;
(6)当A以产生式A->1S展开或 B以B->0S展开时,产生式中的非终结符号S将重复(1)-(3)的推导步骤;
(7)综上所述,该文法的对应正规式为:[01|10]+。
二、联立方程组求解
假设非终结符号S、A、B都分别代表一个正规式,则正规文法的产生式集合所代表的就是关于正规式S、A、B的一个方程组。
我们将文法“|”符号替换为正规式“+”符号,可得,
S=0A+1B=0(1S+1)+1(0S+0)=01(S+ε)+10(S+ε)=(01+10)(S+ε)=(01+10)S+(01+10)。
根据方程X=rX+t有形如X=r*t的解论断,可得,
S=(01+10)*(01+10)=[01|10]+。
❹ 编译原理的最左推导和最右推导问题
最左推导:
S=> (L) =>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=>(a,(S,S))=>(a,((L),S))=>(a,((L,S),S))
=>(a,((S,S),S))=>(a,((a,S),S))=>(a,((a,a),S))=>(a,((a,a),(L)))=>(a,((a,a),(L,S)))
=>(a,((a,a),(S,S)))=>(a,((a,a),(a,S)))=>(a,((a,a),(a,a))) 共17步
最右推导
S=> (L) =>(L,S)=>(L,(L))=>(L,(L,S))=>(L,(L,(L)))=>(L,(L,(L,S)))=>(L,(L,(L,a)))=>(L,(L,(S,a)))
=>(L,(L,(a,a)))=>(L,(S,(a,a)))=>(L,((L),(a,a)))=>(L,((L,S),(a,a)))=>(L,((L,a),(a,a)))
=>(L,((S,a),(a,a)))=>(L,((a,a),(a,a)))=>(S,((a,a),(a,a)))=>(a,((a,a),(a,a)))
❺ 编译原理问题:求解
E是文法开头。ε代表终结符号(推理中代表终点或结果,程序语言中代表常量等)。E T 这些大写字母一般代表非终结符号(这些代表中间过程,非结果。程序中代表函数等等)。开始是E。因为有个G(E)。E就是文法开始符号。推导就有E开始,它也是一个非终结符(代表函数、或者一个推导过程,类似于程序中的main(c++)、winmain(vc++)、dllmain(dll)等主函数)。
1算术表达式文法:这个文法是一个递归文法。计算机进行逻辑推导时会走很多弯路(类似于遍历一颗树的过程)。为了不让计算机走弯路(提高效率的目的),可以变换为第二种文法。这种文法消除了递归(消除了歧义,类似于后缀表达式),使计算机可以一条直线走到底儿推导出结果。
我也很久没看编译原理了。 呵呵
❻ 编译原理全部的名词解释
书上有别那么懒!。。。。
编译过程的六个阶段:词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成
解释程序:把某种语言的源程序转换成等价的另一种语言程序——目标语言程序,然后再执行目标程序。解释方式是接受某高级语言的一个语句输入,进行解释并控制计算机执行,马上得到这句的执行结果,然后再接受下一句。
编译程序:就是指这样一种程序,通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。
解释程序和编译程序的根本区别:是否生成目标代码
句子的二义性(这里的二义性是指语法结构上的。):文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导),或者存在两棵不同的语法树,则称这个句子是二义性的。
文法的二义性:一个文法如果包含二义性的句子,则这个文法是二义文法,否则是无二义文法。
LL(1)的含义:(LL(1)文法是无二义的; LL(1)文法不含左递归)
第1个L:从左到右扫描输入串 第2个L:生成的是最左推导
1 :向右看1个输入符号便可决定选择哪个产生式
某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归
文法符号的属性:单词的含义,即与文法符号相关的一些信息。如,类型、值、存储地址等。
一个属性文法(attribute grammar)是一个三元组A=(G, V, F)
G:上下文无关文法。
V:属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样,可以进行计算和传递。
F:关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。
综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属
继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。
(1)非终结符既可有综合属性也可有继承属性,但文法开始符号没有继承属性。
(2) 终结符只有综合属性,没有继承属性,它们由词法程序提供。
在计算时: 综合属性沿属性语法树向上传递;继承属性沿属性语法树向下传递。
语法制导翻译:是指在语法分析过程中,完成附加在所使用的产生式上的语义规则描述的动作。
语法制导翻译实现:对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算。
中间代码(中间语言)
1、是复杂性介于源程序语言和机器语言的一种表示形式。
2、一般,快速编译程序直接生成目标代码。
3、为了使编译程序结构在逻辑上更为简单明确,常采用中间代码,这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理,并且可以在中间代码一级进行优化工作,使得代码优化比较容易实现。
何谓中间代码:源程序的一种内部表示,不依赖目标机的结构,易于代码的机械生成。
为何要转换成中间代码:(1)逻辑结构清楚;利于不同目标机上实现同一种语言。
(2)便于移植,便于修改,便于进行与机器无关的优化。
中间代码的几种形式:逆波兰记号 ,三元式和树形表示 ,四元式
符号表的一般形式:一张符号表的的组成包括两项,即名字栏和信息栏。
信息栏包含许多子栏和标志位,用来记录相应名字和种种不同属性,名字栏也称主栏。主栏的内容称为关键字(key word)。
符号表的功能:(1)收集符号属性 (2) 上下文语义的合法性检查的依据: 检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据
符号的主要属性及作用:
1. 符号名 2. 符号的类型 (整型、实型、字符串型等))3. 符号的存储类别(公共、私有)
4. 符号的作用域及可视性 (全局、局部) 5. 符号变量的存储分配信息 (静态存储区、动态存储区)
存储分配方案策略:静态存储分配;动态存储分配:栈式、 堆式。
静态存储分配
1、基本策略
在编译时就安排好目标程序运行时的全部数据空间,并能确定每个数据项的单元地址。
2、适用的分配对象:子程序的目标代码段;全局数据目标(全局变量)
3、静态存储分配的要求:不允许递归调用,不含有可变数组。
FORTRAN程序是段结构,不允许递归,数据名大小、性质固定。 是典型的静态分配
动态存储分配
1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间,那么,就需要采用动态存储管理技术。
2、两种动态存储分配方式:栈式,堆式
栈式动态存储分配
分配策略:将整个程序的数据空间设计为一个栈。
【例】在具有递归结构的语言程序中,每当调用一个过程时,它所需的数据空间就分配在栈顶,每当过程工作结束时就释放这部分空间。
过程所需的数据空间包括两部分
一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等;
另一部分则是用以管理过程活动的记录信息(连接数据)。
活动记录(AR)
一个过程的一次执行所需要的信息使用一个连续的存储区来管理,这个区 (块)叫做一个活动记录。
构成
1、临时工作单元;2、局部变量;3、机器状态信息;4、存取链;
5、控制链;6、实参;7、返回地址
什么是代码优化
所谓优化,就是对代码进行等价变换,使得变换后的代码运行结果与变换前代码运行结果相同,而运行速度加快或占用存储空间减少。
优化原则:等价原则:经过优化后不应改变程序运行的结果。
有效原则:使优化后所产生的目标代码运行时间较短,占用的存储空间较小。
合算原则:以尽可能低的代价取得较好的优化效果。
常见的优化技术
(1) 删除多余运算(删除公共子表达式) (2) 代码外提 +删除归纳变量+ (3)强度削弱; (4)变换循环控制条件 (5)合并已知量与复写传播 (6)删除无用赋值
基本块定义
程序中只有一个入口和一个出口的一段顺序执行的语句序列,称为程序的一个基本块。
给我分数啊。。。
❼ 编译原理-句型、句子、短语、直接短语、句柄、素短语、最左素短语
在进行语法分析的时候,有时候会对这些词语的概念不清晰,这里我们就详细归纳总结一下。
可以看出这个里面,最需要理解的概念就是短语,其他大部分概念都是在短语基础上延伸的,从概念上可以看出:
假设有一个文法
针对文法的一个特定句型 (Sd(T)db) , 其推导过程如下:
这个句型 (Sd(T)db) 对应的 CFG 分析树如下:
那个这个句型 (Sd(T)db) 有多少个短语呢?
还记得短语的定义么, S ⇒* αβδ , αβδ 代表句型就是这里的 (Sd(T)db) 。
因此这个句型 (Sd(T)db) :
算法非常简单,就是通过分析树的后序遍历,先将子树的叶节点从左到右排合并成字符串(即一个短语),然后用它代表子树的根节点的值,再和与子树根节点同一层节点值合并,得到新的短语。就这样从分析树的最底层,一路合并到分析树的根节点,就能得到所有的短语了。
通过递归的方法,获取短语列表 phraseList , 直接短语列表 directPhraseList 和 素短语列表 plainPhraseList 。
运行结果:
❽ 编译原理的LL(1)文法是什么意思
LL(1)的含义:第1个L表明自顶向下分析是从左向右扫描输入串,第2个L表明分析过程中将用最左到推倒,1表明只需向右看一个符号便可决定如何推倒即选择哪个产生式(规则)进行推导,类似也可以有LL(k)文法,也就是需要向前查看k个符号才能确定选用哪个产生式。
这是从我们编译原理课本上抄来的,希望对你有帮助