编译原理求解规则怎么说
Ⅰ 编译原理简单文法归约计算
编译原理中的语法和文法是不一样的,但却融会贯通。
在计算机科学中,文法是编译原理的基础,是描述一门程序设计语言和实现其编译器的方法。
文法分成四种类型,即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。
形式语言,这种理论对计算机科学有着深刻的影响,特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。
多数程序设计语言的单词的语法都能用正规文法或3型文法(3型文法G=(VN,VT,P,S)的P中的规则有两种形式:一种是前面定义的形式,即:A→aB或A→a其中A,B∈VN ,a∈VT*,另一种形式是:A→Ba或A→a,前者称为右线性文法,后者称为左线性文法。正规文法所描述的是VT*上的正规集)来描述。
四个文法类的定义是逐渐增加限制的,因此每一种正规文法都是上下文无关的,每一种上下文无关文法都是上下文有关的,而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。
Ⅱ 编译原理求解答案
编译原理是计算机软件专业中的非常重要一门课程。例如:如何把我们编写的高级语言源程序,翻译成机器可执行的目标程序,这个就需要用到编译原理技术。
但是学习编译原理这门课程时,是需要头脑中对编译原理课程中涉及到的所有概念必须是相当清楚的,别人才能够对你的这些问题进行准确的回答。而不是看到这些似曾亲切的内容就敢于回答你的内容的。
故我个人的建议还是:你可以向专门讲授编译原理的老师请教你的问题。
以上就是我很多年前学习编译原理的亲身体会。
Ⅲ 编译原理全部的名词解释
书上有别那么懒!.
编译过程的六个阶段:词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成
解释程序:把某种语言的源程序转换成等价的另一种语言程序——目标语言程序,然后再执行目标程序.解释方式是接受某高级语言的一个语句输入,进行解释并控制计算机执行,马上得到这句的执行结果,然后再接受下一句.
编译程序:就是指这样一种程序,通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序).
解释程序和编译程序的根本区别:是否生成目标代码
句子的二义性(这里的二义性是指语法结构上的.):文法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)删除无用赋值
基本块定义
程序中只有一个入口和一个出口的一段顺序执行的语句序列,称为程序的一个基本块.
给我分数啊.
Ⅳ 编译原理中,LR(0)文法的项目集规范族的I0,I1,I2,I3…………是怎么求的~
先举个例子:
}
将其命名为I1。
其他可类似推出。
Ⅳ 规约的编译原理
推导的逆过程称为规约。规约就是选择一个文法规则:X→ABC,依次从栈顶弹出C、B、A,再将X压进栈。规范规约是文法中句子的一个最右推导的逆过程,而最左推导对应的是最右规约 。
另外在程序设计中的规约:∏和∏'是两个判定性问题,如果存在一个确定性算法A使得对于一个∏的实例I,A可以将I在多项式时间里转换成∏'的实例P,使得I得到肯定的回答,当且仅当I'得到肯定回答,则称∏在多项式时间里规约到∏',记为∏∝poly∏'.
Ⅵ 编译原理问题,求解答
好,我来帮你理解一下,先看基本知识:
四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是:算符op,第一和第二运算对象ARG1和ARG@及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量,有时指编译程序引进的临时变量。例如a∶=b*c+b*d的四元式表示如下:
(1)(*,b,c,t1)
(2)(*,b,d,t2)
(3)(+, t1, t2, t3)
(4)(∶=,t3, -, a)
四元式和三元式的主要不同在于,四元式对中间结果的引用必须通过给定的名字,而三元式是通过产生中间结果的三元式编号。也就是说,四元式之间的联系是通过临时变量实现的。
有时,为了更直观,也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成:
(1)t1∶=b*c
(2)t2∶=b*d
(3)t3∶=t1+t2
(4)a∶=t3
把(jump,-,-,L)写成goto L
把(jrop,B,C,L)写成if B rop C goto L
好,下面分析一下a<b
这是一个表达式,它的结果要么是0,要么是1,因为没有指定这个表达式存放在哪,所以需要一个临时变量来存放它的,在你的问题中,就是T。很显然T有2个值:0或者1
因此,有
101 T:=0 (这个是表达式为假的出口)
103 T:=1 (这个是表达式为真的出口)
因为你的表达式只有一个A<B,因此A<B的真假出口就是表达式的真假出口,所以
100: if a<b goto 103 (a<b为真,跳到真出口103)
101: T:=0(否则,进入假出口)
102: goto 104 (当然要跳过真出口罗,否则T的值不就又进入真出口了,变成真了)
103: T:=1
104:(程序继续执行)
Ⅶ 编译原理问题:求解
E是文法开头。ε代表终结符号(推理中代表终点或结果,程序语言中代表常量等)。E T 这些大写字母一般代表非终结符号(这些代表中间过程,非结果。程序中代表函数等等)。开始是E。因为有个G(E)。E就是文法开始符号。推导就有E开始,它也是一个非终结符(代表函数、或者一个推导过程,类似于程序中的main(c++)、winmain(vc++)、dllmain(dll)等主函数)。
1算术表达式文法:这个文法是一个递归文法。计算机进行逻辑推导时会走很多弯路(类似于遍历一颗树的过程)。为了不让计算机走弯路(提高效率的目的),可以变换为第二种文法。这种文法消除了递归(消除了歧义,类似于后缀表达式),使计算机可以一条直线走到底儿推导出结果。
我也很久没看编译原理了。 呵呵
Ⅷ 编译原理-LL1文法详细讲解
我们知道2型文法( CFG ),它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。
例如, 一个表达式的文法:
最终推导出 id + (id + id) 的句子,那么它的推导过程就会构成一颗树,即 CFG 分析树:
从分析树可以看出,我们从文法开始符号起,不断地利用产生式的右部替换产生式左部的非终结符,最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。
从文法开始符号起,不断用非终结符的候选式(即产生式)替换当前句型中的非终结符,最终得到相应的句子。
在每一步推导过程中,我们需要做两个选择:
因为一个句型中,可能存在多个非终结符,我们就不确定选择那一个非终结符进行替换。
对于这种情况,我们就需要做强制规定,每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。
自顶向下的语法分析采用最左推导方式,即总是选择每个句型的最左非终结符进行替换。
最终的结果是要推导出一个特定句子(例如 id + (id + id) )。
我们将特定句子看成一个输入字符串,而每一个非终结符对应一个处理方法,这个处理方法用来匹配输入字符串的部分,算法如下:
方法解析:
这种方式称为递归下降分析( Recursive-Descent Parsing ):
当选择的候选式不正确,就需要回溯( backtracking ),重新选择候选式,进行下一次尝试匹配。因为要不断的回溯,导致分析效率比较低。
这种方式叫做预测分析( Predictive Parsing ):
要实现预测分析,我们必须保证从文法开始符号起,每一个推导过程中,当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。
根据上面的解决方法,我们首先想到,如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出,如果一个非终结符 A ,它的候选式都是以终结符开头,并且这些终结符都各不相同,那么本身就符合预测分析了。
这就是S_文法,满足下面两个条件:
例子:
这就是一个典型的S_文法,它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB , 只有遇到终结符 a 和 b 的时候,才能返回 S 的候选式,遇到其他终结符时,直接报错,匹配不成功。
虽然S_文法可以实现预测分析,但是从它的定义上看,S_文法不支持空产生式(ε产生式),极大地限制了它的应用。
什么是空产生式(ε产生式)?
例子
这里 A 有了空产生式,那么 S 的产生式组 S -> aA | bAB ,就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。
根据预测分析的定义,非终结符对于任一终结符得到的产生式是确定的,要么能获取唯一的产生式,要么不匹配直接报错。
那么空产生式何时被选择呢?
由此可以引入非终结符 A 的后继符号集的概念:
定义: 由文法 G 推导出来的所有句型,可以出现在非终结符 A 后边的终结符 a 的集合,就是这个非终结符 A 的后继符号集,记为 FOLLOW(A) 。
因此对于 A -> ε 空产生式,只要遇到非终结符 A 的后继符号集中的字符,可以选择这个空产生式。
那么对于 A -> a 这样的产生式,只要遇到终结符 a 就可以选择了。
由此我们引入的产生式可选集概念:
定义: 在进行推导时,选用非终结符 A 一个产生式 A→β 对应的输入符号的集合,记为 SELECT(A→β)
因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组,要求有相同左部的产生式,它们的可选集不相交。
在 S_文法基础上,我们允许有空产生式,但是要做限制:
将上面例子中的文法改造:
但是q_文法的产生式不能是非终结符打头,这就限制了其应用,因此引入LL(1)文法。
LL(1)文法允许产生式的右部首字符是非终结符,那么怎么得到这个产生式可选集。
我们知道对于产生式:
定义: 给定一个文法符号串 α , α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。
定义已经了解清楚了,那么该如何求呢?
例如一个文法符号串 BCDe , 其中 B C D 都是非终结符, e 是终结符。
因此对于一个文法符号串 X1X2 … Xn ,求解 串首终结符集 FIRST(X1X2 … Xn) 算法:
但是这里有一个关键点,如何求非终结符的串首终结符集?
因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:
这里大家可能有个疑惑,怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中,如果问文法符号串 Bβ 中包含非终结符 A ,就产生了循环调用的情况,该怎么办?
对于 串首终结符集 ,我想大家疑惑的点就是,串首终结符集到底是针对 文法符号串 的,还是针对 非终结符 的,这个容易弄混。
其实我们应该知道, 非终结符 本身就属于一个特殊的 文法符号串 。
而求解 文法符号串 的串首终结符集,其实就是要知道文法符号串中每个字符的串首终结符集:
上面章节我们知道了,对于非终结符 A 的 后继符号集 :
就是由文法 G 推导出来的所有句型,可以出现在非终结符 A 后边的终结符的集合,记为 FOLLOW(A) 。
仔细想一下,什么样的终结符可以出现在非终结符 A 后面,应该是在产生式中就位于 A 后面的终结符。例如 S -> Aa ,那么终结符 a 肯定属于 FOLLOW(A) 。
因此求非终结符 A 的 后继符号集 算法:
如果非终结符 A 是产生式结尾,那么说明这个产生式左部非终结符后面能出现的终结符,也都可以出现在非终结符 A 后面。
我们可以求出 LL(1) 文法中每个产生式可选集:
根据产生式可选集,我们可以构建一个预测分析表,表中的每一行都是一个非终结符,表中的每一列都是一个终结符,包括结束符号 $ ,而表中的值就是产生式。
这样进行语法推导的时候,非终结符遇到当前输入字符,就可以从预测分析表中获取对应的产生式了。
有了预测分析表,我们就可以进行预测分析了,具体流程:
可以这么理解:
我们知道要实现预测分析,要求相同左部的产生式,它们的可选集是不相交。
但是有的文法结构不符合这个要求,要进行改造。
如果相同左部的多个产生式有共同前缀,那么它们的可选集必然相交。
例如:
那么如何进行改造呢?
其实很简单,进行如下转换:
如此文法的相同左部的产生式,它们的可选集是不相交,符合现预测分析。
这种改造方法称为 提取公因子算法 。
当我们自顶向下的语法分析时,就需要采用最左推导方式。
而这个时候,如果产生式左部和产生式右部首字符一样(即A→Aα),那么推导就可能陷入无限循环。
例如:
因此对于:
文法中不能包含这两种形式,不然最左推导就没办法进行。
例如:
它能够推导出如下:
你会惊奇的发现,它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:
因此消除 直接左递归 算法的一般形式:
例如:
消除间接左递归的方法就是直接带入消除,即
消除间接左递归算法:
这个算法看起来描述很多,其实理解起来很简单:
思考 : 我们通过 Ai -> Ajβ 来判断是不是间接左递归,那如果有产生式 Ai -> BAjβ 且 B -> ε ,那么它是不是间接左递归呢?
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε,那么这个产生式是不是间接左递归。
Ⅸ 编译原理的定义是什么
编译原理,说得通俗差歼易懂一些就是:让茄弊机器通过某种机制和规则,将一种由人们书写的高级程序代码,经过若干步骤,最终翻译成机器可理解执行的二进制代码。
编译原理技术的具体应用,例如:
(1)、我们用户通常编写的 C/C++ 程序源代码(*.C/*.CPP)虚纳冲,通过 Microsoft Visual C++ 编译器,将由人工书写的 C/C++ 语言程序源代码(*.C/*.CPP),最终翻译成机器可执行的二进制代码(*.EXE);
(2)、人工智能领域中的自然语言处理、机器翻译技术(例如:英/汉翻译、日/汉翻译系统等)等,都需要使用到编译原理技术。
Ⅹ 在编译原理中,语法规则和词法规则有什么不同..
通俗的说,
规则主要识别单词
语法主要识别多个单词组成的句子