没有合适的资源?快使用搜索试试~ 我知道了~
首页编译原理习题集,并附带有课后题答案解析
编译原理习题集,并附带有课后题答案解析
4星 · 超过85%的资源 需积分: 30 16 下载量 140 浏览量
更新于2023-03-03
评论
收藏 10.92MB DOC 举报
编译原理习题集,并附带有课后题答案解析,供广大大学生学习使用,内容齐全,通俗易懂!
资源详情
资源评论
资源推荐
目 录
第一章 编译概述................................................................................................................................1
第二章 文法和语言............................................................................................................................2
第三章 词法分析................................................................................................................................6
第四章 自顶向下语法分析方法.....................................................................................................13
第五章 算符优先分析法..................................................................................................................17
第六章 LR(K)分析法.......................................................................................................................22
第七章 语义分析..............................................................................................................................31
第九章 运行时刻环境......................................................................................................................40
第十章 代码优化..............................................................................................................................47
- 1 -
第一章 编译概述
1、画出编译程序的总体结构图,简述其部分的主要功能。
[答案]
编译程序的总框图见下图。
图 1 编译程序的总体结构图
其中词法分析器,又称扫描器,它接受输入的源程序,对源程序进行词法分析,识别
出一个个的单词符号,其输出结果上单词符号。
语法分析器对单词符号串进行语法分析(根据语法规则进行推导或归纳),识别出程
序中的各类语法单位,最终判断输入串是否构成语法上正确的“程序”。
语义分析及中间代码产生器,按照语义规则对语法分析器归纳出(或推导出)的语法
单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选
择不同的中间代码形式,有的编译程序甚至没有中间代码形式,而直接生成目标代码。
优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低,因此
要做中间代码的优化,其过程实际上是对中间代码进行等价替换,使程序在执行时能更快
并占用更小的空间。
目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示
形式,只有把它再翻译成与机器硬件相关的机器能识别的语言,即目标程序,才能在机器
上运行。
表格管理模块保持一系列的表格,登记源程序的各类信息和编译各阶段的进展状况。
编译程序各个阶段所产生的中间结果都记录在表格中,所需要的信息也大多从表格中,所
需要的信息也大多从表格中获取,整个编译过程都在不断地和表格打交道。
出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误,编译程序应设法发
现错误,把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误,出错处理
- 1 -
源程序
单词符号
语法单位
四元式
四元式
目标代码
词法分析器
语法分析器
语义分析及中间代码生成器
优化器
目标代码生成器
表
格
管
理
出
错
处
理
程序要对发现的错误进行处理、记录,并反映给用户。
2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?
[答案]
计算机执行用高级语言编写的程序主要途径有两种,即解释与编译。
像 Basic 之类的语言,属于解释型的高级语言。它们的特点是计算机并不事先对高级
语言进行全盘翻译,将其变为机器代码,而是每读入一条高级语句,就用解释器将其翻译
为一条机器代码,予以执行,然后再读入下一条高级语句,翻译为机器代码,再执行,如
此反复。
总而言之,是边翻译边执行。
像 C,Pascal 之类的语言,属于编译型的高级语言。它们的特点是计算机事先对高级
语言进行全盘翻译,将其全部变为机器代码,再统一执行,即先翻译,后执行。从速度上
看,编译型的高级语言比解释型的高级语言更快。
第二章 文法和语言
1、文法 G[S]为:
S→Ac|aB A→ab B→bc
写出 L(G[S])的全部元素。
[答案]
S=>Ac=>abc 或 S=>aB=>abc
所以 L(G[S])={abc}
2、文法 G[N]为:
N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么?
[答案]
G[N]的语言是 V
+
。V={0,1,2,3,4,5,6,7,8,9}
N=>ND=>NDD.... =>NDDDD...D=>D......D
3、已知文法 G[S]:
S→dAB A→aA|a B→ε|bB
问:相应的正规式是什么?G[S]能否改写成为等价的正规文法?
[答案]
正规式是 daa*b*;
相应的正规文法为(由自动机化简来):
G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b
也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε
4、已知文法 G[Z]:
Z→aZb|ab
写出 L(G[Z])的全部元素。
[答案]
- 2 -
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb
L(G[Z])={a
n
b
n
|n>=1}
5、写一文法,使其语言是偶正整数集合。
要求:
(1)允许 0 开头;(2)不允许 0 开头。
[答案]
(1)允许 0 开头的偶正整数集合的文法
E→NT|G|SFM
T→NT|G
N→D|1|3|5|7|9
D→0|G
G→2|4|6|8
S→NS|ε
F→1|3|5|7|9|G
M→M0|0
(2)不允许 0 开头的偶正整数集合的文法
E→NT|D
T→FT|G
N→D|1|3|5|7|9
D→2|4|6|8
F→N|0
G→D|0
6、已知文法 G:
E→E+T|E-T|T T→T*F|T/F|F F→(E)|i
试给出下述表达式的推导及语法树
(1)i; (2)i*i+i (3)i+i*i (4)i+(i+i)
[答案]
(1)E=>T=>F=>i
(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i
(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+
(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)
- 3 -
E
E + T
T
T * F
F i
i
F
i
E + T
i
T
F
i
F
i
E
E + T
E + T
i
T
F
F
( E )
i
T
F
i
F
E
T
F
i
(1)
(2)
(3)
7、为句子 i+i*i 构造两棵语法树,从而证明下述文法 G[<表达式>]是二义的。
〈表达式〉→〈表达式〉〈运算符〉〈表达式〉|(〈表达式〉)|i
〈运算符〉→+|-|*|/
[答案]
可为句子 i+i*i 构造两个不同的最右推导:
最右推导 1
〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉
=>〈表达式〉〈运算符〉i=>〈表达式〉* i=>〈表达式〉〈运算符〉〈表达式〉* i
=>〈表达式〉〈运算符〉i * i=>〈表达式〉+ i * i=> i + i * i
最右推导 2
〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉
=>表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式>
=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉 i
=>〈表达式〉〈运算符〉〈表达式〉 * i
=>〈表达式〉〈运算符〉i * i
=>〈表达式〉+ i * i
=> i + i * i
所以,该文法是二义的。
8、文法 G[S]为:
S→Ac|aB A→ab B→bc
该文法是否为二义的?为什么?
[答案]
对于串 abc
(1)S=>Ac=>abc (2)S=>aB=>abc
即存在两不同的最右推导
所以,该文法是二义的。
9、考虑下面上下文无关文法:
S→SS*|SS+|a
(1)表明通过此文法如何生成串 aa+a*,并为该串构造语法树。
(2)G[S]的语言是什么?
[答案]
(1)此文法生成串 aa+a*的最右推导如下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
(2)该文法生成的语言是即加法和乘法的逆波兰式,
10、令文法 G[E]为:
E→E+T|E-T T→T*F|T/F|F F→(E)|I
证明 E+T*F 是它的一个句型,指出这个句型的所有短语、直接短语和句柄。
[答案]
此句型对应语法树如右,故为此文法一个句型。
或者:因为存在推导序列: E=>E+T=>E+T*F,所以 E+T*F 句
型
- 4 -
(4)
剩余51页未读,继续阅读
Liuqun1986
- 粉丝: 2
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1