没有合适的资源?快使用搜索试试~ 我知道了~
编译原理复习题[归纳].pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 22 浏览量
2021-10-12
05:59:39
上传
评论
收藏 638KB PDF 举报
温馨提示
试读
20页
编译原理复习题[归纳].pdf
资源推荐
资源详情
资源评论
编译原理复习
一、简述题
1、简述编译程序的工作过程
编译程序的工作,即从输入源程序开始到输出目标程序为止的整个过程是非常复杂的。
通常,编译程序的工作过程可以划分为 5 个阶段:
第 1 阶段,词法分析。词法分析的任务是输入源程序,对构成源程序的字符串进行扫
描和分解, 识别出一个个的单词 (亦称单词符号或简称符号) ,如保留字 (基本字)、标识符、
算符、界符等。
依循的原则:构词规则
描述工具:有限自动机
第 2 阶段,语法分析。语法分析的任务是在词法分析的基础上,根据语言的语法规则,
把单词符号串分解成各类语法单位(语法范畴) ,如语句、程序块、函数等,判断整个输入
串是否是一个语法上正确的“程序” 。
依循的原则:语法规则
描述工具:上下文无关文法
第 3 阶段,语义分析与中间代码产生。这一阶段的任务是对语法分析所识别出的各类
语法范畴,分析其含义,并进行初步翻译(产生中间代码) 。通常的中间代码有三元式、四
元式、间接三元式、逆波兰式等。
依循的原则:语义规则
第 4 阶段,优化。优化的任务在于对前段产生的中间代码进行加工变换,以期在最后
阶段能产生更为高效 (省时间和空间) 的目标代码。 优化的主要方法有公共子表达式的提取、
循环优化等。
依循的原则:程序的等价变换规则
第 5 阶段,目标代码生成。这一阶段的任务是把中间代码(或经优化处理之后的中间
代码)变换成特定机器上的低级语言代码。
目标代码三种形式 :
绝对指令代码 : 可直接运行
可重新定位指令代码 : 需要连接装配
汇编指令代码 : 需要进行汇编
2、编译程序在分析语言程序的过程中将源语言程序的各种信息都保留在各种表格中, 同时,
在源语言程序出错时, 编译程序要帮助进行错误判断、 错误定位等, 因此表格管理及出错处
理和编译程序的各个阶段都有关联。
编译程序的结构图如图所示。
其中词法分析器,又称扫描器,输入源程序,进行词法分析,输出单词符号。
语法分析器,简称分析器,对单词符号串进行语法分析,识别出各类语法单位,最终
判断输入串是否构成语法上正确的“程序” 。
语义分析器与中间代码产生器,按照语义规则对语法分析器规约出的语法单位进行语
义分析并把它们翻译成一定形式的中间代码。
优化器,对中间代码进行优化处理。
目标代码生成器,把中间代码翻译成目标程序。
3、程序语言的定义
一个程序语言是一个记号系统。 如同自然语言一样, 程序语言主要是由语法和语义两方
面定义的。 有时, 语言定义也包含语用信息, 语用主要是有关程序设计技术和语言成分的使
用方法, 它使语言的基本概念与语言的外界 (如数学概念或计算机的对象和操作) 联系起来。
任何语言程序都可以看做是一定字符集 (称为字母表) 上的一个字符串。 合乎语法的字符串
才算是一个合法的程序。
语言的语法是用来形成一个合法程序的一组规则。这些规则的一部分称为词法规则,
另一部分称为语法规则(或产生规则) 。语言的词法规则是指单词符号的形成规则。语法规
则则规定了如何从单词符号形成更大的结构(即语法单位) ,因此语法规则也可以说是语法
单位的形成规则。
词法规则和语法规则定义了程序语言的形成规则,而程序的意义则用语言的语义规则
来定义。 语义规则规定了语言的单词符号和语法单位的意义, 是定义一个程序意义的一组规
则。
4、上下文无关文法
文法是描述语言的语法结构的形式规则即语法规则。 这些规则必须是准确的, 易于理解
的,而且, 应当有相当强的描述能力,足以描述各种不同的结构。 所谓上下文无关文法是这
样的一种文法,它所定义的语法范畴是完全独立于这种范畴可能出现的环境。
这里有许多重要的概念需要深入理解。
(1)上下文无关文法严格的定义
形式上说,一个上下文无关文法 G 是一个四元式 (V
T
,V
N
,S,P),其中
VT
是一个非空有限集,它的每个元素称为终结符号;
V
N
是一个非空有限集,它的每个元素称为非终结符号,且 V
T
V
N
=
S 是一个非终结符号,称为开始符号, S V N
P是一个产生式集合 (有限 ),每个产生式形式为 P ,其中 P V
N
, (V
T
V
N
)*
开始符 S 至少必须在某个产生式的左部出现一次。
(2)关于文法应用的若干基本概念
严格地说,我们称 A 直接推出 ,即
A
仅当 A 是一个产生式,且 、 (V
T
V
N
)* 。如果
1 2 n
,则我们称
这个序列是从
1
到
n
的一个推导。 若存在一个从
1
到
n
的推导, 则称
1
可以推导出
n 。
我们用
1 n
表示从
1
出发,经一步或若干步,可推导出
n
.
1 n
表示从
1
出发,经
0 步或若干步,可推导出 n.。换言之, 意味着,或者 = 或者 。
对文法 G(E): E i | E+E | E*E | (E)
E (E) (E+E) (i+E) (i+i)
假定 G 是一个文法, S 是它的开始符号。如果 S ,则 称是一个句型。仅含终结符
号的句型是一个句子。文法 G 所产生的句子的全体是一个语言,将它记为 L(G) 。
L(G)={ | S & V
T
*
}
从一个句型到另一个句型的推导往往不唯一。
E+E i+E i+i E+E E+i i+i
最左推导 :任何一步 都是对 中的最左非终结符进行替换。
最右推导 :任何一步 都是对 中的最右非终结符进行替换。
(3)语法分析树与二义性的概念
我们可以用一张图表示一个句型的推导 ,这种表示称为语法树。对于文法
G(E) : E i | E+E | E*E | (E)
(i*i+i) 的语法树如下图所示
E (E)
(E+E)
(E*E+E)
(i*E+E)
(i*i+E)
(i*i+i)
一棵语法树是一些不同推导过程的共性抽象。如果使用最左 (右)推导,则一个最左 (右)
推导与语法树一一对应。在文法中一个句型不一定只对应唯一一棵语法树。
E
i
+
*
( )
E
i
i
E
E
E E
E
i
+
*
( )
E
i
i
E
E
E E
E
+
*
( )
E
i
E
E
i i
E E
剩余19页未读,继续阅读
资源评论
czq131452007
- 粉丝: 2
- 资源: 12万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功