当前位置：文档之家 › 编译原理例题与习题解答ppt

编译原理例题与习题解答ppt

  • 格式：ppt
  • 大小：1.05 MB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

编译原理例题与习题解答PPT课件

编译原理例题与习题解答PPT课件
27
第27页/共85页
• 例如，假定状态 s 1和s 2经a 弧 分 别 到 达t1和t2，而t1和t 2属于现行 中的两个
不同子集，说明有一个字， t1读出后到达终态，而t2读出后不能到达终 态，或者反之，那么对于字a ， s1读出a后到达终态，而s2读出a不能到 达终态，或者反之，所以s1和s2不等价。
{c,d,e} {c,d,f}
{c,d1,f}
1
{c,d}
{c,d,e,g}
{c,d,f}
③.重命名后的状态转换矩阵
I1 {b,c,d}
1 {c,dF,e}
{c,d,e}
0{c,d,e}
{c,d,e,g}
{c,d,e}
S
0
1
A(始态)
Φ
B
B
C
D
C
C
D
D
E
D
E
C
F(终态)
33
F(终态)
第33页/共E85页
40
{10,11}
{12}
第40页/共85页
I1
{1,2,3} {5,9,10,11}
{2,3} {2,3,7,8,13} {5,9,10,11} {5,9,10,11} {2,3,5,9,10,11} {5,9,10,11,13} {2,3,5,9,10,11} {5,9,10,11}
{2,3} {2,3,7,8,13} {2,3,7,8,13}
• 描述工具：正规式和有限自动机理论
ห้องสมุดไป่ตู้
• 语法规则：语法单位的形成规则。
• 语法单位通常包括：表达式、语句、子程序、 过程、函数、程序等;
2
• 描述工具：上下文无关文法

编译原理及其习题解答(武汉大学出版社)课件chap6

编译原理及其习题解答(武汉大学出版社)课件chap6

练习1题目 练习 题目
文法G[T]: T→ F | T*F F →F ↑ P | P P→ (T) | i 证明T*P ↑(T*F)是文法G的一个句型，并 指出这个句型的所有短语、直接短语、 句柄。
编译原理 Compiler Principles
练习１ 练习１解答
证明：T T*F T*F↑P T*F↑(T) 语法树： T T * F P F ↑ ( P T )
编译原理 Compiler Principles
练习2题目
设有文法G[S]: 设有文法 S →V1 V1→ V2 | V1iV2 V2→ V3 | V2+V3 V3→ )V1* | ( (1)给出 (+(i( 的最右推导，并画出相应的语法树； 给出 的最右推导，并画出相应的语法树； (2)证明 2+V3i( 是文法的一个句型，并指出这个句型的短语、直接 证明V 是文法的一个句型，并指出这个句型的短语、 证明 短语、句柄。 短语、句柄。
编译原理 Compiler Principles
非确定的自下而上的分析器
非确定的自下而上的分析器，是一般移进 归约方法 非确定的自下而上的分析器，是一般移进-归约方法 的抽象模型，可识别任何上下文无关语言。 的抽象模型，可识别任何上下文无关语言。给定一个上下 文无关文法，可构造一个自下而上的分析器。 文无关文法，可构造一个自下而上的分析器。 非确定的自下而上的分析器与非确定的自上而下的分 析器的不同之处： 析器的不同之处： 课本P147 课本
编译原理 Compiler Principles
自下而上分析法存在的问题
可归约串的问题；（∵ 该分析的每一步就是从当前串中找一 ；（∵
个子串（ 个子串（称“可归约串”），将它归约到某个非终结符号） 可归约串”），将它归约到某个非终结符号） 将它归约到某个非终结符号 自下而上分析法的关键就是找哪个子串是“可归约串” 自下而上分析法的关键就是找哪个子串是“可归约串”， 关键就是找哪个子串是 哪个不是“可归约串” 例如上例中的(3) 哪个不是“可归约串”。例如上例中的

编译原理例题讲解26页PPT

编译原理例题讲解26页PPT
编译原理例题讲解
46、法律有权打破平静。——马·格林 47、在一千磅法律里，没有一盎司仁 爱。— —英国
48、法律一多，公正就少。——托·富 勒 49、犯罪总是以惩罚相补偿；只有处 罚才能 使犯罪 得到偿 还。— —达雷 尔
50、弱者比强者更能得到法律的保护 。—— 威·厄尔
谢谢！
36、自己的鞋子，自己知道紧在哪里。——西班牙
37、我们唯一不会改正的缺点是软弱。——拉罗什福科
xiexie! 38、我这个人走得很慢，但是我从不后退。——亚伯拉罕·林肯
Hale Waihona Puke 39、勿问成功的秘诀为何，且尽全力做你应该做的事吧。——美华纳
40、学而不思则罔，思而不学则殆。——孔子

编译原理及其习题解答(武汉大学出版社)课件chap1

编译原理及其习题解答(武汉大学出版社)课件chap1
问题: 计算机只能识别二进制数0、1表示的 指令和数构成的本计算机系统的机器 语言。如何让计算机执行高级语言程 序呢？
6
1.1 程序的翻译
1.1.2 翻译程序 所谓翻译程序，是指这样一种程
序，它能将用甲语言（源语言）编写 的程序翻译成与之等价的用乙语言 （目标语言）书写的程序。
程序的翻译通常有两种方式：一是 “编译”方式，二是“解释”方式。
(2) (* ,
id3 t1
(3) (+ ,
id2 t2
(4) (= ,
t3 -
t1 ) t2 ) t3 ) id1 )
29
1.2 编译程序的工作过程
1.2.4 代码优化
依据程序的等价变换规则，尽量压缩目标 程序运行所需的时间和所占的存储空间，以提 高目标程序的质量。
30
代码优化
id1= id2 + id3 * 60
3
第一章 引 论
本节内容： 程序的翻译 编译程序的工作过程 编译程序的结构 编译程序的组织方式 编译程序的构造
4
编译程序在计算机系统中的位置
分类
– 软件 – 系统软件 – 语言处理系统
编译系 统 操作系统
裸机
5
1.1 程序的翻译
1.1.1 程序设计语言 机器语言 001110010010 汇编语言 add R1 2 高级语言 begin x:=9+2 end
行分为两大阶段：编译阶段和运行阶段。 ·如果目标程序是汇编语言程序， 则源程序的执
行分为三大阶段：编译阶段、汇编阶段和运行 阶段。 编译方式下，生成了目标代码，且可多次执行。
9
1.1 程序的翻译
4.关于编译程序的几点说明

编译原理试题及答案(二)ppt课件

编译原理试题及答案(二)ppt课件
编译原理试题 及答案(二)
CH.4.练习题1(P81.)

1.考虑下面文法G1:

S→a|^|(T) T→T，S|S (1) 消去G1的左递归。然后对每个非终结符,写出 不带回溯的递归子程序。

解(1) 消左后的文法G1’: S→a|^|(T) T→ST’ T’→ ,ST’|ε
2018/11/15 2
3
CH.4.练习题1(P81.)

解(1) 不带回溯的递归 子程序: T→ST’ Procedure T; Begin S; T’ end;

解(1) 不带回溯的递归 子程序: T’→,ST’|ε procedure T’; begin if sym=‘,’ then begin advance; S; T’ end End;
4
CH.4.练习题1(P81.)
(2) 经改写后的文法是否是LL(1)的? 给出它的预测分析表。
消左后的文法G1’ :
(2) 因为G1’ : ① 文法不含左递归; ② 对 S→a|^|(T) FIRST(a)={a}, FIRST(^)={^}, FIRST( (T) )={ ( }, 集合互不相交且不含ε; ③ 对 T’→,ST’|ε FIRST( ,ST’ )={ , }, FIRST(ε)={ε}, 其交集为空。 但ε∈FIRST(T’)=FIRST( ,ST’ )∩FIRST(ε)={，,ε}, 然而，FOLLOW(T’)={ ) } FIRST(T’)={，,ε} ，两者 不 相交。 所以，G1’是LL(1)文法。 5
动作, 所用产生式
.
7
CH.4.练习题3(P82.)


3.下面文法中, 哪些是LL(1)的, 说明理由。 (1) S→ABc A→ a|ε B→ b|ε。

编译原理习题及答案课堂ppt课件

编译原理习题及答案课堂ppt课件

A．提高程序的执行效率
B．使程序的结构更加清晰
C．利用有限的机器内存并提高机器的执行效率
D．利用有限的机器内存但降低了机器的执行效
率
(3) 构造编译程序应掌握 。
A．源程序
B．目标语言
C．编译方法
D．A～C项
.
2
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。
来到达2的弧都导向1，并删除状态2。最后，得到如图2-4
所示的化简了的DF.A M′。
21
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。
《编译原理教程》习题解析
22
图2-4 图2-3化简后的DFA M′
.
.
4
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。
《编译原理教程》习题解析
5
(4) 编译各阶段的工作都涉及到构造、查找或更新有 关表格，即编译过程的绝大部分时间都用在造表、查表和 更新表格的事务上。故选D。
《编译原理教程》习题解析
16
(5) NFA可以有DFA与之等价，即两者描述能力相同； 也即，对于任一给定的NFA M，一定存在一个DFA M'，使 L(M)=L(M′)。故选B。
(6) DFA便于识别，易于计算机实现，而NFA便于定 理的证明。故选C。
(7) 本题虽然是第二章的题，但答案参见第三章3.1.3 节。即选C。
.
8
严格执行突发事件上报制度、校外活 动报批 制度等 相关规 章制度 。做到 及时发 现、制 止、汇 报并处 理各类 违纪行 为或突 发事件 。

编译原理习题及答案1～3(课堂PPT)

编译原理习题及答案1～3(课堂PPT)

11
《编译原理教程》习题解析
12
(3) 词法分析器的输出是 。 A．单词的种别编码 B．单词的种别编码和自身的值 C．单词在符号表中的位置 D．单词自身值
(4) 状态转换图(见图2-1)接受的字集为 _______。 A．以0开头的二进制数组成的集合 B．以0结尾的二进制数组成的集合 C．含奇数个0的二进制数组成的集合 D．含偶数个0的二进制数组成的集合
C．汇编语言是计算机唯一能够直接识别并接受 的语言
D．高级语言接近人们的自然语言，但其依赖具 体机器的特性是无法改变的
2
《编译原理教程》习题解析
3
(2) 将编译过程分成若干“遍”是为了 。
A．提高程序的执行效率
B．使程序的结构更加清晰
C．利用有限的机器内存并提高机器的执行效率
D．利用有限的机器内存但降低了机器的执行效
【解答】 计算机执行用高级语言编写的程序主要有两种途 径：解释和编译。
在解释方式下，翻译程序事先并不采用将高级语言程序全 部翻译成机器代码程序，然后执行这个机器代码程序的方法， 而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能 的机器代码语句串并执行，然后再读入下一条源程序语句并解 释执行，而所翻译的机器代码语句串在该语句执行后并不保留。 这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行 的，如果一语句处于一循环体中，则每次循环执行到该语句时， 都要将其翻译成机器代码后再执行。
14
《编译原理教程》习题解析
15
(7) 下面用正规表达式描述词法的论述中，不正确的 是。
A．词法规则简单，采用正规表达式已足以描述 B．正规表达式的表示比上下文无关文法更加简 洁、直观和易于理解 C．正规表达式描述能力强于上下文无关文法 D．有限自动机的构造比下推自动机简单且分析 效率高 (8) 与(a|b)*(a|b)等价的正规式是 。 A．(a|b) (a|b)* B．a*|b* C．(ab)*(a|b)* D．(a|b)*

编译原理习题及答案(课堂PPT)

编译原理习题及答案(课堂PPT)
这两种途径的主要区别在于：解释方式下不生成目 标代码程序，而编译方式下生成目标代码程序。
.
8
《编译原理教程》习题解析
9
1.3 请画出编译程序的总框图。如果你是一个编译程 序的总设计师，设计编译程序时应当考虑哪些问题？
【解答】 编译程序总框图如图1-1所示。 作为一个编译程序的总设计师，首先要深刻理解被编 译的源语言其语法及语义；其次，要充分掌握目标指令的 功能及特点，如果目标语言是机器指令，还要搞清楚机器 的硬件结构以及操作系统的功能；第三，对编译的方法及 使用的软件工具也必须准确化。总之，总设计师在设计编 译程序时必须估量系统功能要求、硬件设备及软件工具等 诸因素对编译程序构造的影响。
《编译原理教程》习题解析
1
第一章 绪 论 第二章 词 法 分 析 第三章 语 法 分 析
.
1
《编译原理教程》习题解析
2
第一章 绪 论
1.1 完成下列选择题： (1) 下面叙述中正确的是 。
A．编译程序是将高级语言程序翻译成等价的机 器语言程序的程序
B．机器语言因其使用过于困难，所以现在计算 机根本不使用机器语言
.
5
《编译原理教程》习题解析
6
(4) 编译各阶段的工作都涉及到构造、查找或更新有 关表格，即编译过程的绝大部分时间都用在造表、查表和 更新表格的事务上。故选D。
(5) 由(1)可知，编译程序实际上实现了对高级语言程 序的翻译。故选D。
.
6
《编译原理教程》习题解析
7
1.2 计算机执行用高级语言编写的程序有哪些途径？它们 之间的主要区别是什么？
.
12
《编译原理教程》习题解析
13
图2-1 习题2.1的DFA M

最新编译原理(课后习题答案ppt课件

最新编译原理(课后习题答案ppt课件
(a) 请指出此文法的终结符号, 非终结符号和开始符号. 终结符号: or, and, not, (, ), true, false 非终结符号: bexpr, bterm, bfactor 开始符号: bexpr
10
(b) 试对于句子 not ( true or false) 构造一棵分析树.
bexpr bterm bfactor not bfactor
a S b S
(d) 此文法产生的语言是什么?
由相同个数的a和b组成的字符串.
9
1.3 考虑文法 bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | ( bfactor ) | true | false
(a) 0 ( 0 | 1)* 0 由0和1组成且以0开始和结束的符号串全体.
(b) ( ( | 0 ) 1* ) * 由0和1组成的符号串全体.
(c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1) 由0和1组成且以000,001,010或011结束的符号串全体. 长度大于等于3且倒数第3个字符为0的01符号串全体.
16
3.4 对于下列语言分别写出它们的正规表达式:
(a) 英文字母组成的所有符号串, 要求符号串中顺序包含 五个元音字母. 令letter={非元音的英文字母} letter* (a|A) letter* (e|E) letter* (i|I) letter* (o|O) letter* (u|U) letter*
18
(e) 带有偶数个0和奇数个1的由0和1组成的符号串全体. E为带有偶数个0和1的由0和1组成的符号串全体. 即 ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E1E|E0E1E0E

编译原理考试习题及答案PPT课件

编译原理考试习题及答案PPT课件

自底向上的语法分析是从输入的字符串出发，逐步将其归约为文法的起始符号。
自底向上的语法分析通常采用LR(0)、SLR(1)、LALR(2)等算法。
自底向上的语法分析可以检测出输入的字符串是否符合语言的语法规则，并生成相应的语法结构。
01
02
03
自底向上的语法分析
语法分析的算法和数据结构
语法分析的算法包括预测分析法、移位/归约法、LR(0)、SLR(1)、LALR(2)等。
三地址代码的生成
对三地址代码进行优化可以提高目标代码的执行效率，常见的优化技术包括常量折叠、死代码删除、循环展开等。
三地址代码的优化
循环优化
循环是程序中常见的结构之一，对循环进行优化可以提高程序的执行效率。常见的循环优化技术包括循环展开、循环合并、循环剪枝等。
要点一
要点二
死代码删除
死代码是指程序中永远不会被执行的代码，删除这些死代码可以减小目标代码的大小并提高程序的执行效率。
习题及答案解析
词法分析习题及答案解析
题目
给定一个字符串，判断它是否是合法的标识符。
答案解析
合法的标识符必须以字母或下划线开头，后面可以跟字母、数字或下划线。
题目
给定一个字符串，判断它是否是关键字。
答案解析
关键字是编程语言中预定义的保留字，不能用作标识符。例如，在C语言中，关键字包括`int`, `float`, `if`, `else`等。
答案解析
上下文无关文法是一种形式文法，它的产生式右部不依赖于左部的任何符号。这意味着产生式右部是一个终结符或一个非终结符的序列。
题目
给定一个抽象语法树，判断它是否是二叉树。
答案解析
抽象语法树是源代码的树形表示，每个节点表示源代码中的一个结构。如果一个抽象语法树中的每个节点最多有两个子节点，则它是二叉树。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

最右推导 E T T*F T*(E) T*(E+T) T*(E+F)
T*(E+i) T*(T+i) T*(F+i) T*(i+i) F*(i+i) i*(i+i)
编译原理
8. 令文法为
E → T|E+T|E-T T → F|T*F|T/F
F → (E)|i
(2) 给出 i+i+i、i+i*i和i-i-i的语法树。 注意：树枝和符号均不可随意增减！
编译原理
5
回顾
文法产生语言
假定G是一个文法，S是它的开始符号。 如果S * ，则称是一个句型。仅含终 结符号的句型是一个句子。
文法G所产生的句子的全体是一个语言， 将它记为L(G) L(G) =｛ | S + & ∈VT*｝
编译原理
6
回顾
文法和语言的二义性
定义：如果一个文法存在某个句子对应两 颗不同的语法树，则说这个文法是二义的。
描述工具：正规式和有限自动机理论
语法规则：语法单位的形成规则。
语法单位通常包括：表达式、语句、子程序、 过程、函数、程序等;
描述工具：上下文无关文法
编译原理
3
回顾
标识符与名字
标识符：以字母开头的，由字母数字组成 的字符串。
标识符与名字两者有本质区别：
标识符是语法概念 名字有确切的意义和属性
语言的二义性：一个语言是二义性的，如 果对它不存在无二义性的文法。
可能存在G和G’，一个为二义的，一个为无二 义的。但L(G)=L(G’)
编译原理
7
例题2.1：有一个文法
G=({S,A,B},{a,b},P,S),其中Pa: S aB|bA A a|aS|bAA B b|bS|aBB 采用最左推导产生句子aabbab 并画出相应的语法树。
i-i-i 的语法树 E
E -T
E-T F
T
Fi
F
i
i
i+i+i 的语法树 E
E+T
E +T FTFra bibliotekFiF
i
i
编译原理
i+i*i 的语法树
E E +T T T* F FF i ii
9、证明文法: S → iSeS | iS | i 是二义的。
二义性的含义: 如果文法存在某个句子对应两棵以上
不同的语法树，或者两种以上不同的最 左/右推导，则称这个文法是二义的。
L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+} （2）给出句子0127、34和568的最左和最右推导。
编译原理
11
注意：1)步骤，和 + 的区别；2) 不能写 为→
解：0127的最左推导： NNDNDDNDDDDDDD
0DDD01DD012D0127 0127的最右推导：
1) 引进新的初态结点X和终态结点Y，X,YS， 从X到S0中任意状态结点连一条箭弧， 从F 中任意状态结点连一条箭弧到Y。
2) 对M的状态转换图进一步施行替换，其中k是 新引入的状态。
编译原理
23
按下面的三条规则对V进行分裂:
i AB j 代之为 i A k
例题与习题解答
第二章
-
1
回顾
程序语言的定义
一个程序语言是一个记号系统,它主要由以下方 面定义：
语法 语义
每个句子构成的规律 研究语言
每个句子的含义
语法 语义
编译原理
2
回顾
语法={词法规则+语法规则}
词法规则：单词符号的形成规则。
单词符号是语言中具有独立意义的最基本结构 。一般包括：常数、标识符、基本字、算符、 界符等。
编译原理
4
回顾
上下文无关文法的定义：一个上下文无关文法 G是一个四元式G=(VT，VN，S，P)，其中
VT：终结符集合(非空)
VN：非终结符集合(非空)，且VT VN=
S：文法的开始符号，SVN
P：产生式集合(有限)，每个产生式形式为
P， PVN， (VT VN)*
开始符S至少必须在某个产生式的左部出现一次。
A aAb|ab B cB|
编译原理
9
例题2.3 请证实文法G(E): E EiT | T T T+F | iF | F F E* | (
是一个二义文法。
编译原理
10
P36-6.
文法G6为:
N →D|ND
D →0|1|2|3|4|5|6|7|8|9
（1） G6的语言L(G6)是什么?
G6的语言是： 0~9的数字组成的任意非空数字串
S aBaaBB aabSB aabbABaabbaB aabbab
S
B aBB
bS
b
bA
a
编译原理
8
例题2.2 试构造生成语言 L={anbnci|n1, i 0}的文法
分析：要求a和b的个数一样多，并至少为一个， 而c的个数为0个以上即可，所以可以用一个终结 符去生成anbn串，用另一个非终结符去生成ci 。 G(Z): ZAB
首先：找到此文法对应的一个句子 iiiei 其次：构造与之对应的两棵语法树
S
S
i SeS
iS
iS
i
i S eS
i
ii
结论：因为该文法存在句子iiiei对应两棵
不同的语法树，因而该文法是二义的。
编译原理
18
10. 把下面文法改写成无二义性的文法 S->SS | (S) | ( )
解答： S-> TS | T T->(S) | ( )
编译原理
19
11、给出下面语言的相应文法
L2={aibncn| n≥1,i≥0}
G2(S): S→AB A→aA|ε B→bBc|bc
L3={anbnambm| m,n≥0}
G3(S): S→AB A→aAb|ε B→aBb|ε
编译原理
20
L4={1n 0m 1m 0n| n,m≥0} 可以看成是两部分：
NNDN7ND7N27ND27 N127D1270127
编译原理
8. 令文法为 E → T|E+T|E-T T → F|T*F|T/F F → (E)|i
(1) 给出 i+i*i、i*(i+i)的最左推导 和最右推导。
解：此处仅以 i*(i+i) 为例给出答案
最左推导
E T T*F F*F i*F i*(E) i*(E+T) i*(T+T) i*(F+T) i*(i+T) i*(i+F ) i*(i+i)
中间部分是 0m 1m ： A→ 0A1 | ε 剩下两边的部分就是： S→ 1S0 | A
所以G4[S]可以写为： S→ 1S0 | A A→ 0A1 |ε
编译原理
21
例题与习题解答
第三章
-
22
非确定有限自动机状态图的改造
1. 假定NFA M=<S, , , S0, F>，我们对M的 状态转换图进行以下改造：

相关主题