编译原理复习资料1、某操作系统下合法的文件名为：device:name.extension，其中第一部分(device:)和第三部分(.extension )可缺省，若device, name和extension都是字母串，长度不限，但至少为1,画出识别这种文件名的DFA。

用标记d表示任意字母。

d d图1接受文件名的DFA2、用两个不同最左推导来说明下面的文法是二义的。

S A S | bA S A | a答：句型aSAS的两个不同最左推导如下：S AS aS aAS aSASS AS SASASAS aSAS3、证明下面的文法S S A | AA a不是LL(1)文法，但是SLR(1)文法，并画出SLR(1)分析表。

答：该文法的第一个产生式表现出直接左递归，因此该文法不是LL(1)。

接受该文法的活前缀的DFA见下面右边；Follow( S) = {$}，Follow( S) = {$, a}，Follow( A)SLR(1)的。

5、下面是int i, j, k这样的类型声明的两种不同语法:T int | real TL L , id | id L如果用LL(1)分析方法，应该选择哪个文法？如果用某种简要说明理由。

答：对于LL(1)分析方法，两个文法都不合适，左边的文法是左递归的，右边文法有公共左因子。

修改右边文法来适应LL(1)分析的要求，相对来说比较容易一些，因为只要提公共左因子。

对于LR的各种分析方法，两个文法都适用，但是采用左边的文法更好一些。

用左边的文法时，分析器一边扫描一边归约，占用分析栈的空间较少。

而用右边的文法时，分析器要把所有的标识符都移进栈后才进行归约，因此使用较多的分析栈空间。

(结合语法制导的翻译，采用左边的文法还有好处：便于确定T的类型属性在栈中的位置。

) 6、在C语言中，3++和(id + id )++这样的表达式被编译时，编译器都会报告如下的错误：in valid lvalue in in creme nt说明左值不能为数值或表达式。

现有如下简化的C语言表达式文法： E E + E | (E ) | E ++ | id | num请写一个语法制导定义或翻译方案，检查++的运算对象是否合法。

答：给非终结符 E 一个综合属性v,其值可取lvalue或rvalue，分别表示E是左值标识符和右值表达式，那么语法制导定义如下(无输出则表示无错) ：E id E.v := lvalueE num E.v := rvalueE E+T | TT num.num | num给出一个语法制导定义以确定每个子表达式的类型int/real 。

答：E E1+T { if ( E1.type=real or T.type=real )4、用SLR(1)文法能定义的语言集合、定义的语言集合之间有什么关系？答：用SLR⑴文法能定义的语言集合用LR(1)文法能定义的语言集合和用LALR(1)文法能用LALR(1)文法能定义的语言集合，用LALR⑴文法能定义的语言集合用LR(1)文法能定义的语言集合。

int | realid , L | idLR分析方法，选择哪个文法更好?E EE E i + E2 E ( E i ) E E i ++ E.v := rvalueE.v := E i.vif E i.v = rvalue then printf(E.v := rvaluein valid lvalue in in creme nt ”);7、then E.type=real else E.type=integer } E T { E.type = T.type;}T num .num {T.type = real;}T num {T.type = integer;}8、把下列 C 语言程序的可执行语句翻译为：main(){int i; int a[10];while (i<=10) a[i] = 0; }(a) 三地址代码(b) 后缀式答：(a) L0: if i<=10 goto L1goto L2L1: a[i]:=0goto L0L2:(b) 后缀式：i 10 <= a[i] 0 assign while9、试构造下面的程序的流图，并找出其中所有回边及循环。

read Px := 1 c := P * P if c < 100 goto L1 B := P * P x := x + 1 B := B + x write x halt L1: B:= 10x := x + 2 B := B + x write B if B < 100 goto L2 halt L2: x := x + 1goto L1答：程序的流图如下10、对本题中所示的流图，求出其各结点n 的控制结点集 D(n)、回边及循环(n o 为首结点) 答：各结点n 的控制结点集D(n)如下：D(n 0)= ={n o }D(n 1)= ={n 0, n 1}D(n 2)= ={n 0, n 1, n 2}D(n 3)= ={n 0, n 1, n 2, n 3} D(n 4)={n 0, n 1, n 2, n 4} D(n 5)= ={n 0, n 1, n 2, n 5}D(n 6)= ={n 0,n 1, n 2,n 5, n 6}D(n 7)={n 0, n 1, n 2, n 5, n 6, n 7}回边和循环：因为D(n 5) = {n o , n 1, n 2, n 5}，且n 5 -> n 2,所以n 5 -> n 2为一条回边。

根据它 求出的循环 Li = {n 2, n 5, n 3, n 4}。

因为 D(n 6)= {n 0, n 1, n 2, n5, n 6}，且 n 6 -> n 1，所以 n 6 -> n 1 为一条回边。

根据这条回边，求出的循环 L 2 = {n 6, n 1, n 5, n 3, n 4, n 2}。

11、考虑下面求矩阵 A B 成绩的程序片段：BEGINFOR i := 1 TO n DOFOR j := 1 TO n DOFOR k = 1 TO n DOc[i, j] := c[i, j] + A[i, k} * B[k, j]END (1)假定对数组A 、B 、C 采用静态存储分配，每个字占用 4个字节，存储器以字节为单位编址。

给出该程序的三地址代码序列。

(2) 构造该程序相应的流图。

(3) 删除流图中各基本块内的公共子表达式(4)指出流图中所有回边及其相应循环，并且进行循环优化。

答：(1)设数组元素按行存放，A、B C数组都是n*n的二维数组，各维的下界均为0，每个元素占一个字(4个字节)，则数组元素(如A[i, j])的地址计算公式为：D(A[i, j]) = addr(A) + ((i - 0) * n + (j - 0)) * 4=addr(A) + 4 * ( i * n + j )该程序的三地址代码序列被划分成基本块后如下：(105) if k > 门ecrta 130Bp (130) J := J + 1(131)goto 103(3 )仅基本块B7中有公共子表达式，删除公共子表达式后基本块B7变换成:(106)鼻：二I 半n(107)T：:二 J + J(108)T2 := addr (0(109)T t：= 4 + T”(110)T5:二T2[T t](111)T&:二几+ K(112)T r:二addr (A)(113)T e;= 4 * T6(114)T fi:二T?[t s] ill5) T, ：= K * n(116)Tg ：二Tg + J(117)T lQ:二吕療r(B)(118)T?:二4 * T9(119)T lt - T®[TJ(120)T12:= T3加T n(121)T； T5十T12(122)T JTJ :二(123)K ;= K + 1(124)goto 105(4)根据(2)的程序流图，每个结点的控制结点集如下:D(B i) = { B i }D(B2) = { B 1, B2 }D(B3) = { B 1, B 2, B 3 }D(B4) = { B 1, B 2, B 3, B 4 }D(B5) = { B 1, B 2, B 3, B 4, B 5 }D(B6) = { B 1, B 2, B 3, B 4, B 5, B 6 }D(B7) = { B 1, B 2, B 3, B 4, B 5, B 6, B 7 } D(B8) = { B 1, B 2, B 3, B 4, B 5, B 6, B 8 } D(B9) = { B 1, B 2, B 3, B 4, B 9 }根据回边B7 -> B 6 ，循环L i为：L1 = { B 7, B 6 }根据回边B8 -> B 4 ，循环L2为：L2 = { B 8, B 6, B 7, B 5, B 4 }根据回边B9 -> B2, 循环:L3为：L3 = { B 9, B 4, B 5, B 6, B 7 , B 8, B 3, B 2 } 经循环优化后三地址代码序列变为Sy. 4(2)经理度削弱后的梳圈(3)删除归纳变量：变换循环控制条件，删除归纳变量 I 后的流图显示在图12、试求出如下四元式程序中的循环并进行循环优化 I := 1 read J, K L: A := K * I B := J * IC := A * B write C I := I + 1 if I < 100 goto Lhalt 答：把本题的三地址代码划分成基本块并画出其程序流图显示在图 9.4(1)中 其中有三个基本块B1, B2, B3,有一条回边 B2 -> B2，相应的循环是｛B2｝。

I 1Tead J, KE ;= J * [C - * 8WLL lU €I ：二 I + 1i£ I < 各口丄口 Lhalt 国9. 4(1〕程序毓国 (1 )代码外提：由于循环中没有不变运算，故不做此项优化 (2)强度削弱: B2中A 和B都是 I 的归纳变量。

优化结果显示在图 9.4(2)中。

h 丹】t 9.4(3)中A 用静态分配存储单元，且下届为 0；/* 置初值*/4/* 第一个for 语句*/T 2[T 1] := true i := i + 1图9.4(3)删除归纳变量的程序流图 13、下面是应用筛法求 2到N 之间素数的程序: beginread N; for i := 2 to N do A[i] := true; /*置初值*/ 表幕乘*/ for i := 2 to N**0.5 do/*运算符**代T 2 := addr(A) T 1:= 2 * T 1 /* 数组A 的基地址*/the n/*i false/*j 可被i 除尽*/endif A[i]是一个素数*/for j := 2 * i to N by i doA[j]:=(1)试写出其四元式中间代码，假设对数组 (2 )作出流图并求出其中的循环； (3 )进行代码外提；(4)进行强度削弱和删除归纳变量；答：采用字节地址，两个字节作为一个机器字。