当前位置:文档之家› 2019-2020年编译原理复习资料(1).doc

2019-2020年编译原理复习资料(1).doc

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

用标记d 表示任意字母。

2、用两个不同最左推导来说明下面的文法是二义的。

S
→ A S | b
A → S A | a 答:句型aSAS 的两个不同最左推导如下: S ⇒ AS ⇒ aS ⇒ aAS ⇒ aSAS S ⇒ AS ⇒ SAS ⇒ ASAS ⇒ aSAS 3、证明下面的文法
S → S A | A A → a
不是LL(1)文法,但是SLR(1)文法,并画出SLR(1)分析表。

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

接受该文法的活前缀的DFA 见下面右边;Follow(S ') = {$},Follow(S ) = {$, a },Follow(A ) = {$, a };SLR(1)分析表见下面左边。

该表无冲突,所以该文法d d d
图1 接受文件名的DFA
4、用SLR(1)文
法能定义的语
言集合、用LR(1)
文法能定义的
语言集合和用LALR(1)文法能定义的语言集合之间有什么关系?
答:用SLR(1)文法能定义的语言集合⊂用LALR(1)文法能定义的语言集合,
用LALR(1)文法能定义的语言集合⊂用LR(1)文法能定义的语言集合。

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

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

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

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

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

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

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


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

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

答:给非终结符E一个综合属性v,其值可取lvalue或rvalue,分别表示E是左值标识符和右值表达式,那么语法制导定义如下(无输出则表示无错):E'→ E
E → E
1 + E
2
E.v := rvalue
E → ( E
1 ) E.v := E
1
.v
E → E
1 ++ if E
1
.v = rvalue then printf(“invalid lvalue in
increment”);
E.v := rvalue
E → id E.v := lvalue
E → num E.v := rvalue
7、 E → E+T | T
T → num.num | num
给出一个语法制导定义以确定每个子表达式的类型int/real。

答:E → E1+T { if ( E1.type=real or T.type=real )
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 L1
goto L2
L1: a[i]:=0
goto L0
L2:
(b) 后缀式:i 10 <= a[i] 0 assign while
9、试构造下面的程序的流图,并找出其中所有回边及循环。

read P
x := 1
c := P * P
if c < 100 goto L1
B := P * P
x := x + 1
B := B + x
write x
halt
L1: B:= 10
x := x + 2
B := B + x
write B
if B < 100 goto L2
halt
L2: x := x + 1
goto L1
答: 程序的流图如下
10、对本题中所示的流图,求出其各结点n的控制结点集D(n)、回边及循环(n
0为首结点)。

答:各结点n的控制结点集D(n)如下:
D(n
0) = {n
}
D(n
1) = {n
, n
1
}
D(n
2) = {n
, n
1
, n
2
}
D(n
3) = {n
, n
1
, n
2
, n
3
}
D(n
4) = {n
, n
1
, n
2
, n
4
}
D(n
5) = {n
, n
1
, n
2
, n
5
}
D(n
6) = {n
, n
1
, n
2
, n
5
, n
6
}
D(n
7) = {n
, n
1
, n
2
, n
5
, n
6
, n
7
}
回边和循环:
因为 D(n
5) = {n
, n
1
, n
2
, n
5
} ,且 n
5
-> n
2
,所以 n
5
-> n
2
为一条回
边。

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

因为D(n
6) = {n
, n
1
, n
2
, n
5
, 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成绩的程序片段:
BEGIN
FOR i := 1 TO n DO
FOR j := 1 TO n DO
FOR k = 1 TO n DO
c[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 )
该程序的三地址代码序列被划分成基本块后如下:。

相关主题