编译原理 第十章 代码优化
第十章代码优化
某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。
本章重点：局部优化基本块的DAG表示
第一节优化技术简介
为了说明问题，我们来看下面这个例子，源程序是：
P :=0
For I :=1 to 20 do
P :=P+A[I]*B[I];
经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。那么，对于这个中间代码段，可进行如下这些优化。
1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。所以，（6）的运算是多余的。我们可以把（6）变换成：T4 :=T1。这种优化称为删除多余运算或称为删除公共子表达式。
2、代码外提减少循环中代码总数的一个重要办法是代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。经过删除多余运算和代码外提后，代码变成图10-1-2。
法运算等等。在图10-1-2的循环中，每循环一次，I的值增1，T1的值与I保持线性关系，每次总是增加4。因此，我们可以把循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变换成加法运算。变换后如图10-1-3所示。
4、变换循环控制条件图10-1-3的代码中，I和T1始终保持T1= 4 * I的线性关系，这样可以把（12）的循环控制条件I≤20变换成T1≤80，这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）可以从循环中删除，这就是我们的目的所在。
5、合并已知量与复写传播图10-1-3中，四元式（3）计算4 * I时，I必为1。所以（3）中的4 * I的两个运算对象都是编码时的已知量，可在编译时计算出它的值，即（3）可变为T1= 4这种变换称为合并已知量。
图10-1-3中，（6）把T1的值复写到T4中，四元式（8）要引用T4的值，而（6）到（8）之间未改变T4和T1的值，则（8）改为T6 : =T5[T1]，之后运算结果保持不变。这种变换称为复写传播。图10-1-3经过变换循环控制条件，合并已知量和复写传播等变换后，变为图10-1-4。
6、删除无用赋值在图10-1-4中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除，如图10-1-5所示（设（6）（2）（11）为无用赋值）。
比较图10-1-1和图10-1-5可看出，经过优化后的代码的执行效率提高了很多。当然，实现这些优化的代价也是很大的。
第二节局部优化
我们所说的局部优化是指基本块内的优化，所谓基本块，是指程序中一顺序执行语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出。对于一个给定的程序，我们可以把它划分为一系列的基本块。在各基本块的范围内分别进行优化。
一、基本块的划分
在介绍基本块的构造之前，我们先定义基本块的入口语句，所谓入口语句，严格地说来就是：
1、程序的第一语句；或者，
2、条件转移语句或无条件转移语句的转移目标语句；或者，
3、紧跟在条件转移语句后面的语句。
有了入口语句的概念之后，我们就可以给出划分中间代码（四元式程序）为基本块的算法，其步骤如下：
1、求出四元式程序中各个基本块的入口语句。
2、对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。
3、凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。
我们仍以上一节所述的例子来说明，对于图10-1-1中的代码段，由规则1，语句（1）是入口语句，由规则2，语句（3）是入口语句。由规则3，跟随语句（12）的语句是入口语句，这样，语句（1）和（2）构成一个基本块，语句（3）—（12）构成一个基本块，也即图10-1-1中的B1和B2。
二、基本块的变换
很多变换可作用于基本块而不改变它计算的表达式集合，这样的变换对改进代码的质量是很有用的。有两类重要的局部等价变换可用于基本块，它们是保结构的变换和代数变换。
基本块的主要保结构变换是 1、删除公共子表达式 2、删除无用代码 3、重新命名临时变量 4、交换语句次序
对于1和2，我们在第一节已经讨论过，在此简单讨论一下3和4。 重新命名临时变量：假如有语句t : = b + c ，其中t 是临时变量。如果把这个语句改为u : = b + c ， 其中u 是新的临时变量，并且把这个t 的所有引用改成u ，那么基本块的运算结果不变。 交换语句次序：如果基本块有两个相邻的语句： t 1 : = b + c t 2 : = x + y
当且仅当x 和y 都不是t 1，b 和c 都不是t 2时我们可以交换这两个语句的次序。
有许多代数变换可以把基本块计算的表达式集合变换成代数等价的集合。其中有用的变换是那些可以简化表达式或用较快运算代替较慢运算的变换。例如：
x : = x + 0 或 x : = x * 1
这样的语句可以从基本块中删除而不改变它计算的表达式集合，又如 x : = y * * 2
的指数算符通常要用函数调用来实现，使用代数变换，这个语句可由快速、等价的语句
x : = y * y 来代替。
第三节 基本块的DAG 表示
这一小节介绍如何应用有向图来进行基本块的优化工作。 先将我们所需使用的DAG 作一说明。
在一个有向图中，我们称任一有向边n i →n j （或表示为有序对（n i ,n j ））中的结点n i 为结点n j 的前驱（父结），结点n j 为结点n i 的后继（子结）。又称任一有向边序列n 1→n 2, n 2→n 3,…,n k —1→n k 为从结点n 1到结点n k 的一条通路。如果其中n 1=n k ，则称通路为环路。该结点序列也记为（n 1 ,n 2,…,n k ）。例如，图10-3-1中有向图的通路（n 2 ,n 2）和（n 3 ,n 4 ,n 3）就是环路。如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG 。图10-3-2的有向图就是一个DAG 。在DAG 中，如果（n 1 ,n 2,…, n k ）是其中一条通路，则称结点n 1为结点n k 的祖先，结点n k 为结点n 1的后代。 我们这一节中要用到的有向图，是一种其结点带有下述标记或附加信息的DAG ：
1、图的叶结点，即无后继的结点，以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A 的地址，则用addr （A ）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。
2、图的内部结点，即有后继的结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
3、图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 上述这种DAG 可用来描述计算过程，又称描述计算过程的DAG 。在以下的讨论中，我们简称DAG 。
下面讨论基本块的DAG表示与构造。
一个基本块，可用一个DAG来表示。下面（图10-3-3）列出各种四元式及相对应的DAG的结点形式。图中n i为结点编号，结点下面的符号（运算符、标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。
四元式DAG结点
（0）A：=B（：=，B，—，A）
（1）A：=op B（op，B，—，A）
（2）A：=B op C（op，B，C，A）
（3）A：=B [C]（=[ ]，B[C]，—，A）
（4）if B rop C goto (s) (jrop, B, C, (S))
（5）D[C]：=B （[]=，B，—，D[C]）
（6）goto(s) (j，—，—，(S))
图10-3-3 四元式与DAG结点
接着给出一种构造基本的DAG算法。假设DAG各结点信息将用某种适当的数据结构来存放。并设有一个标识符（包括常数）与结点的对应表。NODE（A）是描述这种对应关系的一个函数，它的值或者是一个结点的编号n，或者无定义。前一个情况代表DAG中存在一个结点n, A是其上的标记或附加标识符。
我们把图10-3-3中各形式的四元式按其对应结点的后继个数分为四类。其中，四元式（0）称为0型，（1）称为1型；（2）和（3）称为2型；（5）称为3型。对于3型四元式，由于对数组元素赋值的情形需特殊考虑，因此暂不讨论，对四元式（6）也不涉及，下面是仅含0,1,2型四元式的基本块的DAG构造算法。
首先，DAG为空。
对基本块的每一四元式，依次执行：
1、如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；
如果当前四元式是0型，则记NODE（B）的值为n，转4。
如果当前四元式是1型，则转2．（１）。
如果当前四元式是2型，则：（1）如果NODE（C）无定义，则构造一标记为C的叶结点并定义NODE（C）为这个结点，（2）转2．（2）。
2、（1）如果NODE（B）的标记为常数的叶结点，则转2（3），否则转3．（１）。
（2）如果NODE（B）和NODE（C）都是标记为常数的叶结点，则转2．（4），否则转3．（2）。
（3）执行op B（即合并已知量），令得到的新常数为P。如果NODE（B）是处理当前四元式时新构造出来的结点，则删除它。如果NODE（P）无定义，则构造一用P做标记的叶结点n。置NODE（P）= n，转4．。
3、（1）检查DAG中是否已有一结点，其唯一后继为NODE（B），且标记为op（即找公共子表达式）。如果没有，则构造该结点，否则就把已有的结点作为它的结点并设该结点为n，转4.。
（2）检查DAG中是否已有一结点，其左后继为NODE（B），右后继为NODE（C），且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n。转4．。
4、如果NODE（A）无定义，则把A附加在结点n上并令NODE（A）= n；否则先把A从NODE （A）结点上的附加标识符集中删除（注意，如果NODE（A）是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE（A）= n。转处理下一四元式。
例1试构造以下基本块G的DAG。
(1) T0 : = 3.14
(2) T1 : = 2 * T0
(3) T2 : = R + r
(4) A : = T1* T2
(5) B : = A
(6) T3 : = 2 * T0
(7) T4 : = R + r
(8) T5 : = T3* T4
(9) T6 : = R－r
(10) B : = T5* T6
处理每一四元式后构造出的DAG如图10-3-4中各子图所示，具体步聚从略，子图(a) (b)… (j)
分别对应于四元式（1），（2），…，（10）。
图10-3-4 由四元式构造的DAG
第四节代码生成概述
代码生成是把经过语法分析或优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器，因此，代码生成器的构造与输入的中间代码形式和输出的目标代码的机器结构密切相关。特别是高级语言和计算机的多种多样性为代码生成的理论研究和实现技术带来很大的复杂性。
由于一个高级程序设计语言的目标代码需反复使用，因而，代码生成器的设计要着重考虑目标代码的质量问题。衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。到底产生什么样的目标代码取决于具体的机器结构、指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统、存储管理等都密切相关。目标代码的执行效率在很大程度上依赖于寄存器的使用。
第五节习题
一、单项选择题
1、优化可生成的目标代码。
a．运行时间较短b．占用存储空间较小
c．运行时间短但占用内存空间大d．运行时间短且占用存储空间小
2、下列优化方法不是针对循优化进行的。
a．强度削弱b．删除归纳变量c．删除多余运算d．代码外提
3、基本块内的优化为。
a．代码外提，删除归纳变量b．删除多余运算，删除无用赋值
c．强度削弱，代码外提d．循环展开，循环合并
4、关于必经结点的二元关系，下列叙述中不正确的是。
a．满足自反性b．满足传递性c．满足反对称性d．满足对称性
5、对一个基本块来说，是正确的。
a．只有一个入口语句和一个出口语句b．有一个入口语句和多个出口语句
c．有多个入口语句和一个出口语句d．有多个入口语句和多个出口语句
6、在程序流图中，我们称具有下述性质的结点序列为一个循环。
a．它们是非连通的且只有一个入口结点b．它们是强连通的但有多个入口结点
c．它们是非连通的但有多个入口结点d．它们是强连通的且只有一个入口结点
7、不可能是目标代码。
a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码[解答]
1、优化的目的是使目标程序运行时间短、占用存储空间小，故选d。
2、删除多余运算属基本块优化，故选c。
3、基本块优化包括：合并已知量、删除无用赋值及删除多余运算，故选b。
4、必经结点满足自反性、传递性和反对称性关系，故选d。
5、选a。
6、选d。
7、选d。
二、多项选择题
1、根据优化所涉及的范围，可将优化分为。
a．局部优化b．过程优化c．全局优化
d．循环优化e．四元式优化
2、下列优化中，属于循环优化的有。
a．强度削弱b．合并已知量c．删除无用赋值
d．删除归纳变量e．代码外提
3、如果a→b是程序流图中的一条边，则由这条回边构成的循环由结点组成。
a．a b．b c．有通路到达b的结点
d．有通路到达a且该通路上不经过b的结点
e．有通路到达b且该通路上不经过a的结点
4、采用无环有向图（DAG），可以实现的优化有。
a．合并已知量b．删除公共子表达式c．强度削弱
d．删除无用赋值e．删除归纳变量
5、编译程序的输出结果可以是。
a．目标代码b．汇编语言代码c．中间代码
d．优化后的中间代码e．可重定位代码
[解答]
1、选a、c、d。
2、循环优化包括：代码外提、强度削弱、删除归纳变量、循环展开和循环合并，故选a、b、e。
3、如果a→b是回边，则该回边的构成的循环由结点a、b和能够到达a但通路不经过b的结点组成；故选a、b、d。
4、DAG图可进行基本块范围内的优化，故选a、b、d。
5、选b、c、d、e。
三、填空题
1、局部优化是范围内进行的一种优化。
2、在一个基本块内，可实行3种优化方法，即合并已知量、、。
3、优化就是对程序进行各种变换，使之能生成更有效的。
4、在优化中，可把循环中的提到循环外面去，这种方法称为。
[解答]
1、基本块
2、删除无用赋值删除多余运算
3、等价目标代码
4、不变运算代码外提
编译原理复习题(经典)
编译原理复习题 一、是非题 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 3．每个文法都能改写为 LL(1) 文法。 (×) 4．算符优先关系表不一定存在对应的优先函数。 (√) 5．LR分析方法是自顶向下语法分析方法。 (×) 6．“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(× ) 7．一个句型的句柄一定是文法某产生式的右部。 (√) 8．仅考虑一个基本块，不能确定一个赋值是否真是无用的。 (√ ) 9．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 (× ) 10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×) 11．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× ) 12．递归下降分析法是自顶向下分析方法。(√ ) 13．产生式是用于定义词法成分的一种书写规则。 (×) 14．在 SLR(1)分析法的名称中，S的含义是简单的。(√) 15．综合属性是用于“自上而下”传递信息。(× ) 16．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×) 17．程序语言的语言处理程序是一种应用软件。 (×) 18．解释程序适用于 COBOL 和 FORTRAN 语言。 (×) 19．一个 LL(l)文法一定是无二义的。 (√) 20．正规文法产生的语言都可以用上下文无关文法来描述。 (√) 21．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 (×) 22．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 (√) 22．逆波兰法表示的表达式亦称后缀式。 (√ ) 23．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 (√ ) 24．数组元素的地址计算与数组的存储方式有关。(√) 25．算符优先关系表不一定存在对应的优先函数。 (×) 26．编译程序是对高级语言程序的解释执行。(× ) 27．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 28．一个算符优先文法可能不存在算符优先函数与之对应。 (√ ) 29．语法分析时必须先消除文法中的左递归。 (×) 30．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√) 31．逆波兰表示法表示表达式时无须使用括号。 (√ ) 32．静态数组的存储空间可以在编译时确定。 (√) 33．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (√) 34．两个正规集相等的必要条件是他们对应的正规式等价。 (√) 35．一个语义子程序描述了一个文法所对应的翻译工作。 (×) 36．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×) 37．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 38．词法分析作为单独的一遍来处理较好。 (× ) 39．构造LR分析器的任务就是产生LR分析表。 (√) 40．规范归约和规范推导是互逆的两个过程。 (√) 41．同心集的合并有可能产生新的“移进”/“归约”冲突。 (× ) 42．LR分析技术无法适用二义文法。 (× )
编译原理知识点汇总
编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V
编译原理实验指导
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则
编译原理实验代码
[实验任务] 完成以下正则文法所描述的Pascal语言子集单词符号的词法分析程序。 <标识符>→字母︱<标识符>字母︱<标识符>数字 <无符号整数>→数字︱<无符号整数>数字 <单字符分界符> →+ ︱－︱* ︱; ︱(︱) <双字符分界符>→<大于>=︱<小于>=︱<小于>>︱<冒号>=︱<斜竖>* <小于>→< <等于>→= <大于>→> <冒号> →: <斜竖> →/ 该语言的保留字：begin end if then else for do while and or not 说明：1 该语言大小写不敏感。 2 字母为a-z A-Z，数字为0-9。 3可以对上述文法进行扩充和改造。 4 ‘/*……*/’为程序的注释部分。 [设计要求] 1、给出各单词符号的类别编码。 2、词法分析程序应能发现输入串中的错误。 3、词法分析作为单独一遍编写，词法分析结果为二元式序列组成的中间文件。 4、设计两个测试用例（尽可能完备），并给出测试结果。 demo.cpp #include
编译原理 第十章 代码优化
第十章代码优化 某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。 本章重点：局部优化基本块的DAG表示 第一节优化技术简介 为了说明问题，我们来看下面这个例子，源程序是： P :=0 For I :=1 to 20 do P :=P+A[I]*B[I]; 经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。那么，对于这个中间代码段，可进行如下这些优化。 1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。所以，（6）的运算是多余的。我们可以把（6）变换成：T4 :=T1。这种优化称为删除多余运算或称为删除公共子表达式。 2、代码外提减少循环中代码总数的一个重要办法是代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。经过删除多余运算和代码外提后，代码变成图10-1-2。
实验1-3 《编译原理》词法分析程序设计方案
实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表
编译原理实验题目及报告要求
编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术， 如何针对确定的有限状态自动机进行编程序；熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确 地运行；④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法G(S)： S→v = E E→E+E│E-E│E*E│E/E│（E）│v │i 其中，v为标识符，i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序； ②使用算符优先分析方法实现其语法分析程序，在 语法分析过程中同时完成常量表达式的计算。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第一项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理： (1)单词分类：标识符，保留字，常数，运算符，分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第二项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理：构造出算法优先关系表 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
编译原理实验：目标代码的生成
5. 目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 5.1 实验内容 5.1.1 实验要求 为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：https://www.docsj.com/doc/1c5812046.html,/~larus/spim.html。这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围： 1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。
编译原理模拟题
《编译原理》模拟题（补） 一．单项选择题 1.（）是两类程序语言处理程序。 A. 高级语言程序和低级语言程序 B. 解释程序和编译程序 C. 编译程序和操作系统 D. 系统程序和应用程序 2. 编译程序前三个阶段完成的工作是（）。 A. 词法分析、语法分析和代码优化 B. 代码生成、代码优化和词法分析 C. 词法分析、语法分析、语义分析和中间代码生成 D. 词法分析、语法分析和代码优化 3. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（）。 A. 字符串 B. 产生式 C. 非开始符号 D. 文法 4. 词法分析器的输出结果是（）。 A. 单词的种别编码 B. 单词在符号表中的位置 C. 单词的种别编码和自身值 D. 单词自身值 5. 一个句型中称为句柄的是该句型的最左（）。 A. 非终结符号 B. 短语 C. 句子 D. 直接短语 6. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。 A. 自左向右 B. 自顶向下 C. 自底向上 D. 自右向左 7. 在通常的语法分析方法中，（）特别适用于表达式的分析。 A. 算符优先分析法 B. LR分析法 C. 递归下降分析法 D. LL（1）分析法 8. 优化可生成_____的目标代码。 A. 运行时间较短 B. 占用存储空间较小 C. 运行时间短但占用内存空间大 D. 运行时间短且占用存储空间小 9.（）是两类程序语言处理程序。 A. 系统程序和应用程序 B.编译程序和操作系统 C. 解释程序和编译程序 D.高级语言程序和低级语言程序 10. 经过编译所得到的目标程序是（）。 A. 四元式序列 B. 间接三元式序列
编译原理实验 中间代码生成
实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: ";
编译原理实验 (词法语法分析报告 附源代码
编译原理实验报告 ******************************************************************************* ******************************************************************************* PL0语言功能简单、结构清晰、可读性强，而又具备了一般高级程序设计语言的必须部分，因而PL0语言的编译程序能充分体现一个高级语言编译程序实现的基本方法和技术。PL/0语言文法的EBNF表示如下： <程序>::=<分程序>. <分程序> ::=[<常量说明>][<变量说明>][<过程说明>]<语句> <常量说明> ::=CONST<常量定义>{，<常量定义>}; <常量定义> ::=<标识符>=<无符号整数> <无符号整数> ::= <数字>{<数字>} <变量说明> ::=VAR <标识符>{, <标识符>}; <标识符> ::=<字母>{<字母>|<数字>} <过程说明> ::=<过程首部><分程序>{; <过程说明> }; <过程首部> ::=PROCEDURE <标识符>; <语句> ::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句> |<复合语句>|<读语句><写语句>|<空> <赋值语句> ::=<标识符>:=<表达式> <复合语句> ::=BEGIN <语句> {;<语句> }END <条件语句> ::= <表达式> <关系运算符> <表达式> |ODD<表达式> <表达式> ::= [+|-]<项>{<加法运算符> <项>} <项> ::= <因子>{<乘法运算符> <因子>} <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’ <加法运算符> ::= +|- <乘法运算符> ::= *|/ <关系运算符> ::= =|#|<|<=|>|>= <条件语句> ::= IF <条件> THEN <语句> <过程调用语句> ::= CALL 标识符 <当循环语句> ::= WHILE <条件> DO <语句> <读语句> ::= READ‘(’<标识符>{,<标识符>}‘)’ <写语句> ::= WRITE‘(’<表达式>{,<表达式>}‘)’ <字母> ::= a|b|…|X|Y|Z <数字> ::= 0|1|…|8|9 【预处理】 对于一个pl0文法首先应该进行一定的预处理，提取左公因式，消除左递归（直接或间接），接着就可以根据所得的文法进行编写代码。 【实验一】词法分析 【实验目的】给出PL/0文法规，要求编写PL/0语言的词法分析程序。 【实验容】已给PL/0语言文法，输出单词（关键字、专用符号以及其它标记）。
编译原理
一、选择 1．将编译程序分成若干个“遍”是为了_使程序的结构更加清晰__。 2．正规式 MI 和 M2 等价是指__.M1 和 M2 所识别的语言集相等_。 3．中间代码生成时所依据的是 _语义规则_。 4．后缀式 ab+cd+/可用表达式__(a+b)/(c+d)_来表示。 6．一个编译程序中，不仅包含词法分析，_语法分析 ____，中间代码生成，代码优化，目标代码生成等五个部分。 7．词法分析器用于识别__单词___。 8．语法分析器则可以发现源程序中的___语法错误__。 9．下面关于解释程序的描述正确的是__解释程序的特点是处理程序时不产生目标代码 ___。 10．解释程序处理语言时 , 大多数采用的是__先将源程序转化为中间代码 , 再解释执行___方法。 11．编译过程中 , 语法分析器的任务就是__(2)(3)(4)___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 12．编译程序是一种__解释程序__。 13．文法 G 所描述的语言是_由文法的开始符号推出的所有终极符串___的集合。 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___正则文法__。 15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _产生式__。 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_表格处理和出错处理__。 17．文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│ bB ， B→bN} ），该文法所描述的语言是L(G[N])={b2i+1│ i ≥0} 18．一个句型中的最左_简单短语___称为该句型的句柄。 19．设 G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 x∈V*), 则称 x 是 文法 G 的一个__句型__。 21．若一个文法是递归的，则它所产生的语言的句子_是无穷多个___。 22．词法分析器用于识别_单词_。 23．在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_终极符集 ___。 24．在自底向上的语法分析方法中，分析的关键是_寻找句柄 ___。 25．在 LR 分析法中，分析栈中存放的状态是识别规范句型__活前缀__的 DFA 状态。 26．文法 G 产生的__句子___的全体是该文法描述的语言。 27．若文法 G 定义的语言是无限集，则文法必然是 __递归的_ 28．四种形式语言文法中，1 型文法又称为 _短语结构文法__文法。 29．一个文法所描述的语言是_唯一的__。 30． _中间代码生成___和代码优化部分不是每个编译程序都必需的。 31．_解释程序和编译程序___是两类程序语言处理程序。 32．数组的内情向量中肯定不含有数组的_维数___的信息。 33. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。 34．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2 型文法是__上下文无关文法__。 35．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __产生式___。 36．__ BASIC ___是一种典型的解释型语言。 37．与编译系统相比，解释系统___比较简单 , 可移植性好 , 执行速度慢__。 38．用高级语言编写的程序经编译后产生的程序叫__目标程序___。 39．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过__(1)(2)(3)__这几步: (1) 编辑 (2) 编译 (3) 连接 (4) 运行 40．把汇编语言程序翻译成机器可执行的目标程序的工作是由__编译器__完成的。 41．词法分析器的输出结果是__单词的种别编码和自身值__。 42．文法 G ：S→xSx|y 所识别的语言是_ xnyxn(n≥0)___。 43．如果文法 G 是无二义的，则它的任何句子α__最左推导和最右推导对应的语法树必定相同_。 44．构造编译程序应掌握___源程序目标语言编译方法___。 45．四元式之间的联系是通过__临时变量___实现的。 46．表达式( ┐ A ∨B)∧(C∨D)的逆波兰表示为___ A ┐ B∨CD∨∧__。 47. 优化可生成__运行时间短且占用存储空间小___的目标代码。 48．下列__删除多余运算 ____优化方法不是针对循环优化进行的。 49．编译程序使用__说明标识符的过程或函数的静态层次___区别标识符的作用域。 50．编译程序绝大多数时间花在___表格管理__ 上。 51．编译程序是对__高级语言的翻译___。
编译原理试题及答案3
编译原理复习题 一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。 8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。 10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。
编译原理实验-递归下降分析资料报告器地设计(含源代码和运行结果)
《编译原理》实验报告 实验3 递归下降分析器的设计 学号班级计科1001班 时间：2012/4/15 地点:文波 同组人：无 指导教师：朱少林 实验目的 使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。 实验容 a.运用所学知识，编程实现递归下降语法分析程序。使用递归下降分析算法分析表达式 是否符合下文法： exp →exp addop term | term Addop →+ | - term→term mulop factor | factor mulop →* | / factor →(exp) | id | number 其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id 和number的值。 b.从数据文件中读出符号串，输出表达式并给出其正误评判。 实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简
单的也应该有复杂的。每个表达式写在一行，以回车结束。 实验环境 软件：VC++6.0 实验前准备 1、方案设计： ①准备模拟数据：本实验中使用“work..cpp” ②程序思想： 为了使用递归向下的分析，为每个非终结符根据其产生式写一个分析程序，由于写入读出的操作频繁。所以程序中还有一个match(char t)函数，该函数是将字符写入文件打印输出同时从文件中读取下一个字符，而由于id和number可能是多个字符构成，故写了number()和id（）来分析数字和标识符，它们的功能仅仅是把整个number或id完整的读取出来并写入文件，打印输出。 由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符，并返回0或1. 在main()函数中，while((lookahead=='\n'||lookahead==' ')&&lookahead!=EOF) fscanf(resource,"%c",&lookahead); 是为了忽略分析文件中的换行或空格，之后进入分析阶段，根据返回值判断是否是合法的表达式。在该程序中只有发现了非法字符才会返回0，否则就返回1，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。
编译原理课程设计-词法分析器(附含源代码)
编译原理-词法分析器的设计 一．设计说明及设计要求 一般来说，编译程序的整个过程可以划分为五个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。本课程设计即为词法分析阶段。词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。如保留字（关键字或基本字）、标志符、常数、算符和界符等等。 二．设计中相关关键字说明 1．基本字：也称关键字，如C语言中的 if , else , while , do ,for,case,break, return 等。 2．标志符：用来表示各种名字，如常量名、变量名和过程名等。 3．常数：各种类型的常数，如12，6.88，和“ABC” 等。 4．运算符：如 + ，- , * , / ,%, < , > ,<= , >= 等。5．界符，如逗点，冒号，分号，括号，# ，〈〈，〉〉等。 三、程序分析 词法分析是编译的第一个阶段，它的主要任务是从左到右逐个字符地对源 程序进行 扫描，产生一个个单词序列，用以语法分析。词法分析工作可以是独立的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程。然而，更一般的情况，常将
词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则 调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一 些字符，直到识别出一个单词，或说直到下一个单词的第一个字符为止。 四、模块设计 下面是程序的流程图 五、程序介绍 在程序当前目录里建立一个文本文档，取名为infile.txt,所有需要分析的程序都写在此文本文档里，程序的结尾必须以“@”标志符结束。程序结果输出在同一个目录下，文件名为outfile.txt，此文件为自动生成。本程序所输出的单词符号采用以下二元式表示：（单词种别，单词自身的值）如程序输出结果(57,"#")(33,"include")(52,"<")(33,"iostream") 等。 程序的功能：（1）能识别C语言中所有关键字（共32个）（单词种别分别为1 — 32 ，详情见程序代码相关部分，下同） （2）能识别C语言中自定义的标示符（单词种别为 33） （3）能识别C语言中的常数（单词种别为0） （4）能识别C语言中几乎所有运算符（单词种别分别为41 — 54） （5）能识别C语言中绝大多数界符（单词种别分别为 55 — 66）六、运行结果 输入文件infile.txt 运行结果（输出文件 outfile.txt）
编译原理 大题类型
1、 从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？ 答：从优化的范围的角度，优化可以分为局部优化和全局优化两类； 对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。 2、写出表达式a=b*c+b*d 对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 四元式序列： 三元式序列: OP ARG1 ARG2 (1) (*， b ， c ， t 1) (1) (* b ， c ) (2) (*， b ， d ， t 2) (2) (* b ， d ) (3) (+， t1， t 2，t 3) (3) (+ (1)， (2)) (4) (:=， t3， /， a) (4) (:= (3)， a) 3、对于文法G(S): ）Ma L a |(L M bMb S →→→ 答：1） b Ma b Lb b bMb S )((??? 2） 短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma) 三、 设有字母表{a ，b}上的正规式R=(ab|a)*。 解：（1） （2）将（1）所得的非确定有限自动机确定化 ε a b -0 1 1 3 12 2 1 +3 a b -+013 123 +123 123 13 +13 123 0 1 2 3 b a a ε ε - + S b M ( T M a b L )
（3）对（2）得到的DFA 化简，合并状态0和2 为状态2： （4）令状态1和2分别对应非终结符B 和A G: A →aB|a|ε； B →aB|bA|a|b|ε；可化简为：G: A →aB|ε；B →aB|bA|ε 四、 设将文法G 改写成等价的LL(1)文法，并构造预测分析表。 G ：S→S*a T|aT|*aT ； T →+a T|+a 解：消除左递归后的文法G ’: S →aTS ’|*aTS ’ S ’→*aTS ’|ε T →+aT|+a 提取左公因子得文法G ’’: S →aTS ’|*aTS ’ S ’→*aTS ’|ε T →+aT ’ T ’→T|ε Select(S →aTS ’)={a} Select(S →*aTS ’)={*} Select(S →aTS ’)∩Select(S →*aTS ’)=Ф Select(S ’→*aTS ’)={*} Select(S ’→ε)=Follow(s ’)={#} Select(S ’→*aTS ’)∩Select(S ’→ε)= Ф Select(T →+aT ’)={+} Select(T ’→T)=First(T) ={+} Select(T ’→ ε)=Follow(T ’)={*,#} Select(T ’→T)∩Select(T ’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a # S →*aTS ’ →aTS ’ 1 2 a a b a -+ + + 1 2 a a b -+ +
编译原理期末试题(8套含答案+大题集)
《编译原理》期末试题（五） 一、单项选择题(共10小题，每小题2分，共20分) 1．语言是 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 2．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 3．一个句型中称为句柄的是该句型的最左 A．非终结符号B．短语C．句子D．直接短语 4．下推自动机识别的语言是 A．0型语言B．1型语言 C．2型语言D．3型语言 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A．字符B．单词C．句子D．句型 6．对应Chomsky四种文法的四种语言之间的关系是 A．L0?L1?L2?L3 B．L3?L2?L1?L0 C．L3=L2?L1?L0D．L0?L1?L2=L3 7．词法分析的任务是 A．识别单词B．分析句子的含义 C．识别句子D．生成目标代码 8．常用的中间代码形式不含 A．三元式B．四元式C．逆波兰式D．语法树 9．代码优化的目的是 A．节省时间B．节省空间 C．节省时间和空间D．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A．把高级语言翻译成汇编语言 B．把高级语言翻译成机器语言 C．把中间代码变换成依赖具体机器的目标代码 D．把汇编语言翻译成机器语言 二、填空题（本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。
编译原理实验报告——词法分析器(内含源代码)
编译原理实验（一）——词法分析器
一．实验描述 运行环境：vc++2008 对某特定语言A ，构造其词法规则。 该语言的单词符号包括： 1
2状态转换图 3程序流程：
词法分析作成一个子程序，由另一个主程序调用，每次调用返回一个单词对应的二元组，输出标识符表、常数表由主程序来完成。 二．实验目的 通过动手实践，使学生对构造编译系统的基本理论、编译程序的基本结构有更为深入的理解和掌握；使学生掌握编译程序设计的基本方法和步骤；能够设计实现编译系统的重要环节。同时增强编写和调试程序的能力。 三．实验任务 编制程序实现要求的功能，并能完成对测试样例程序的分析。
四．实验原理 char set[1000],str[500],strtaken[20];//set[]存储代码,strtaken[]存储当前字符char sign[50][10],constant[50][10];//存储标识符和常量 定义了一个Analyzer类 class Analyzer{ public: Analyzer(); //构造函数 ~Analyzer(); //析构函数 int IsLetter(char ch); //判断是否是字母，是则返回 1，否则返回 0。 int IsDigit(char ch); //判断是否为数字，是则返回 1，否则返回 0。 void GetChar(char *ch); //将下一个输入字符读到ch中。 void GetBC(char *ch); //检查ch中的字符是否为空白， 若是，则调用GetChar直至ch进入一个非空白字符。 void Concat(char *strTaken, char *ch); //将ch中的字符连接到strToken之后。 int Reserve(char *strTaken); //对strTaken中的字符串查找保留字表，若是一个保留字返回它的数码，否则返回0。 void Retract(char *ch) ; //将搜索指针器回调一个字符位置，将ch置为空白字符。void input();//向存放输入结果的字符数组输入一句语句。 void display();//输出一些程序结束字符显示样式 int analyzerSubFun();//词法分析器子程序，为了实现词法分析的主要功能。 五．代码实现 // cifa.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" #include"stdio.h" #include"string.h" #include"iostream" using namespace std; char set[1000],str[500],strtaken[20];//set[]存储代码,strtaken[]存储当前字符 char sign[50][10],constant[50][10];//存储标识符和常量 //int Words[500][10]; char ch;//当前读入字符 int sr,to=0;//数组str, strtaken 的指针 int st=0,dcount=0; int id=0; static int line=1; int h,l; typedef struct Words /*放置二元组*/ { int num; char letters[20];