3.4 给出文法G[S]，构造相应最小的DFA。

      S->aS|bA|b

      A->aS

解：  原文法等价于：S->aS|bA|bB

                    A->aS

                    B->ε

NFA：令 ①-S, ②-A, ③-B

          a                                           

                 a                   

        +①    b     ②        ③-

                          b                   

 

NFA化为DFA：

              a         b

  {1}       {1}       {2,3}       +{1}

{2,3}      {1}                  - {2}

          a                                           

                 a                   

        +①    b     ②-

 

3.6 给出与下图中的NFA等价的正规文法G。

a

Ａ

+

Ｂ

Ｃ

Ｄ

-

b

a

b

b

b

a

-

解：G(A)：A à aB | bD

          B à bC

          C à aA | bD | ε

          D à aB | bD| ε

补充题1：构造与正规式(a|b)*c⁺|ab等价的DFA

(1) 与之等价的NFA为

(2) 消除ε边后的NFA为

(3)确定化过程如下：

	a	b	c
+ A {1,2}	B {2,4}	C {2}	D {3}
B {2,4}	C {2}	E {2,5}	D {3}
C {2}	C {2}	C {2}	D {3}
- D {3}			D {3}
- E {2,5}	C {2}	C {2}	D {3}

得到的DFA为：

第5章 语法分析

4.3 设有文法G[S]:

      S->A

      A->B | AiB

      B->C | B+C

      C-> )A* | (

      (1) 将文法G[S]改写为LL(1)文法。

      (2) 构造改写后的文法的递归子程序(给出流程图即可) 。

      (3) 求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。

      (4) 构造相应的LL(1)分析表，并给出输入串 (+)(*# 的分析过程。

解答：

(1) 原文法有左递归，利用A->Ab|a可以化为

A->aA`

A`->bA`|e

可以得到，原文法可以化为G`(S)：

S->A

A->BA`

A`->iBA`|e

B->CB`

B`->+CB`|e

C->)A*|(

(2) 扩展文法，增设一个产生式S`->S，作为主程序，得到的递归下降子程序的流程如下：

主程序           子程序S：      子程序A：          子程序A`：

                             

    子程序B：          子程序B`：         子程序C：

                 

(3) 每个非终结符的FIRST集和FOLLOW集如下：

	first	Follow
S	{ ), ( }	{ # }
A	{ ), ( }	{ #, * }
A`	{ i }	{ # , * }
B	{ ), ( }	{ i, # ,*}
B`	{ + }	{ i,#,* }
C	{ ), ( }	{ +, i ,# ,*}

其中，follow(B)=first(A`)∪follow(A)= first(A`)∪{*}∪follow(S)={i}∪{*}∪{#}

(4) 为产生式编号：

S->A   ①

A->BA` ②

A`->iBA` ③ |e ④

B->CB` ⑤

B`->+CB` ⑥ |e ⑦

C->)A* ⑧ |( ⑨

       根据每个非终结符的FIRST集和FOLLOW集，可以得到各产生式的select集如下：

       select(①)=first(A) ={), (}

       select(②)= first(B) ={), (}

       select(③)=first(iBA`)={i}

       select(④)=first(e)∪follow(A`)={#,*}

select(⑤)=first(C)= {), (}

select(⑥)=first(+CB`)={+}

select(⑦)= first(e)∪follow(B`)={i,#,*}

select(⑧)=first()A*)={)}

select(⑨)=first(()={(}

       根据以上select集，可以得到LL(1)分析表：

 

 

 

 

根据以上LL(1)分析表，得出输入串 (+)(*# 的分析过程如下：

 

4.9 设文法G[S]为:

      S->rD

      D->D,i | i

      (1) 构造文法的句柄识别器。

      (2) 该文法是LR(0)文法吗？请说明理由。

      (3) 该文法是SLR(1)文法吗？若是，构造它的SLR(1)分析表，并给出符号串 ri,i# 的分析过程。

解答：

(1)扩展文法：

       S`->S  (0)

       S->r D  (1)

       D->D , i  (2)| i  (3)

构造的文法的句柄识别器为：

 

(2)由上图可以看出，在③状态处存在移进和规约冲突，即{,4}和{r(1)}，因此，不是LR(0)文法。

(3)对以上移进和规约冲突{,4}和{r(1)}，(1)号产生式为S->r D，follow(S)∩{,}={#}∩{,}=F，因此，是SLR(1)文法。

根据文法的句柄识别器及移进和规约冲突的解决，得到的SLR(1)分析表如下：

符号串ri,i# 的SLR(1)分析过程为：

4.10 考虑文法G[S]:

      S->aA | bB

      A->0A |1

      B->0B |1

      (1) 构造文法的句柄识别器。

      (2) 判断该文法是否为LR(0)文法，若是，请构造LR(0)分析表，并给出符号串 a001# 的分析过程；若不是，请说明理由。

解答：

(1) 扩展文法：

       S`->S  (0)

S->a A (1)| b B (2)

    A->0 A (3) |1 (4)

    B->0 B (5) |1 (6)

构造的文法的句柄识别器为：

 

(2) 从以上句柄识别器中可以看出，没有任何状态存在移进和规约冲突，因此，是LR(0)文法。根据句柄识别器，可以得到LR(0)分析表如下：

符号串 a001# 的LR(0)分析过程如下：

附加题1：已知文法G[A]为：

A->aAB1|a

B->Bb|d

(1) 给出与G[A]等价的LL(1)文法G'[A];

(2) 构造G'[A]的预测分析表;

(3) 给出输入串aad1#的分析过程;

解答：

(1) 将递归和公因子处理后，得到的文法G'[A]为：

A->aA'

A'->AB1|ε

B->dB'

B'->bB'|ε

(2) 预测分析表为

	a	b	1	d	#
A	->aA'
A'	->AB1			->ε	->ε
B				->dB'
B'		->bB	->ε

(3) 输入串aad1#的分析过程：

 

第6章  中间代码及其翻译

【习题1】写出下列语句的四元式序列：

      (1) if(x>0) x=(a-b/2)*c；

      (2) while (a∨b) b=2*a/5;

      (3) a1: y=2*x-6; …; goto a1;

解答：

(1)    四元式序列：

(2)    四元式序列：

(3)    四元式序列：

(1) ( lb  _  _  a1 )

(2) (*  2  x  t1 )

(3) ( -  t1  6  t2 )

(4) ( =  t2  _  y )

......

(8)  ( gt  _  _  a1 )

【习题2】表达式E的“值”描述如下：

如采用LR分析法，给出表达式(5*4+8)*2的语法树并在各结点注明语义值 val。

解答：

按照表达式属性文法中的语义动作，得到属性语法树：

【习题3】设有文法G：

E-> E + T | T

T-> T * F | F

F-> P↑F | P

P-> (E) | i

(1) 消除文法的左递归性，并构造适合递归子程序法的属性翻译文法。

(2) 消除文法的左递归性，并构造适合LL(1)分析法的属性翻译文法。

解答:

(1)    消除文法的左递归，可得到以下文法：

E -> T { + T}

T -> F { * F}

F-> P↑F | P

P -> ( E ) | i

根据这个文法，构造的适合递归子程序法的属性翻译文法:

E -> T { + T{GEQ(+)}}

T -> F { * F{GEQ(*)}}

F-> P↑F{GEQ(↑)} | P

P -> ( E ) | i {PUSH(i)}

(2) 消除文法的左递归，可得到以下文法：

E -> T E´                    

E´-> + T E´| e

T -> F T´

T´-> * F T´| e

F-> P↑F | P

P -> ( E ) | i

根据以上文法，构造的适合LL(1)分析法的属性翻译文法:

E -> T E´                    

E´-> + T {GEQ(+)} E´| e

T -> F T´

T´-> * F {GEQ(*)} T´| e

F-> P↑F{GEQ(↑)} | P

P -> ( E ) | i {PUSH(i)}

【习题4】根据6.4.2节给出的表达式的四元式属性翻译文法，写出a+b/c-d#的四元式 LL(1)法翻译过程（参照【例6.13 】）。

解答：

6.4.2节给出的表达式的四元式属性翻译文法为：

E -> T E´ ①                   

E´-> + T {GEQ(+)} E´②| - T {GEQ(-)} E´③| e ④

T -> F T´⑤

T´-> * F {GEQ(*)} T´⑥| / F {GEQ(/)} T´⑦| e ⑧

F -> i {PUSH(i)} ⑨ | ( E ) ⑩

LL(1)分析表如下：

a+b/c-d#的四元式 LL(1)法翻译过程为：

 

【习题5】给定二进制数的文法G(S)如下:

令 S 的综合属性 val 给出G(S)中 S 产生的二进制数的值，例如，对于输入 101.101 时，S.val=5.625。

试给出二进制数求值的属性文法（给出属性求值规则）。

 

 

第7章  符号表组织

【习题】设有程序片断如下，试填写符号表：

       float exe(x,y)

          int  x, y[5][10];

         { float a;  int b[5][10];

             …

            b[2,5]=15; …

         }

 

第8章  代码优化

【习题1】试把以下程序段划分为基本块，并做出其程序流程：     

int C;

A = 0;

B = 1;

L1 :  A = A + B;

If B >= C goto L2;

B = B + 1;

goto L1;

L2:  print A;

halt;

基本块的划分：                           程序流程如下：

                  

根据基本块的入口语句的判断条件，入口语句为(1)、(4)、(8)、(9)、(12)

【习题2】设有基本块上的语句序列：

      A=2*3+B/C;

      B=2*3+B/C;

      C=2*3+B/C;

   1. 写出四元式序列，构造优化的 DAG 表示；

   2. 根据优化的 DAG ，重组四元式。

解答：

1.         以上序列的四元式序列为

(1)    ( * 2 3 t1)

(2)    (/ B C t2)

(3)    (+ t1 t2 t3)

(4)    (= t3 _ A)

(5)    ( * 2 3 t4)

(6)    (/ B C t5)

(7)    (+ t4 t5 t6)

(8)    (= t6 _ B)

(9)    ( * 2 3 t7)

(10) (/ B C t8)

(11) (+ t7 t8 t9)

(12) (= t9 _ C)

构造DAG，进行常值表达式节省、公共表达式节省和删除多余运算等优化，得到的优化的DAG为：

交换临时变量与非临时变量（t9与C，t3与A）后得到如下DAG：

 

2. 根据基本块内优化的DAG，重组四元式：

(1) (/ B C t2)

(2) (+ 6 t2 A)

(3) (= A _ B)

(4) (/ A C t8)

(5) (+ 6 t8 C)

第 9 章  目标代码及其生成

9.4 假设可用寄存器为R0和R1，试对以下四元式序列G给出目标代码的生成过程：

T1=B-C

T2=A*T1

T3=D+1

T4=E-F

T5=T3*T4

W=T2/T5

解：

四元式	目标代码	寄存器	内存
T1=B-C	①LD R0,B ②SUB R0,C	R0含T1
T2=A*T1	③MUL R0,A	R0含T2
T3=D+1	④LD R1,D ⑤ADD R1,1	R0含T2 R1含T3
T4=E-F	⑥ST R0,T2 ⑦LD R0,E ⑧SUB R0,F	R0含T4 R1含T3	M含T2
T5=T3*T4	⑨ MUL R1,R0	R0含T4 R1含T5	M含T2
W=T2/T5	⑩ LD R0,T2 ⑾ DIV R0,R1 ⑿ ST R0,W		M含W

 

补充题

已知下列语句：

① if(a+b<c) x=(a+b)/(c-d)+(a+b);

② while (A!=0){A=2+B/C;B=2+B/C;}

※ 试分别解答：

⑴ 写出优化的四元式序列；

⑵ 标记变量的活跃信息；

⑶ 描述单寄存器R下的目标代码生成过程。

解：① if(a+b<c) x=(a+b)/(c-d)+(a+b)优化的四元式序列：

(1)  (+, a, b, t₁)

(2)  (<, t₁, c, t₂)

(3)  (if, t₂ , _ , 9)     

(4)  (+, a, b, t₃)

(5)  (-, c, d, t₄)

(6)  (/, t₃, t₄, t₅)                    

(7)  (+, t₅, t₃, x)                     

(8)  (ie, _, _, _)                                                    

附有活跃信息的四元式序列：

(1)  (+, a(y), b(y), t₁(y))

(2)  (<, t₁(n), c(y), t₂(y))

(3)  (if, t₂(n) , _ , 9)     

(4)  (+,a(y), b(y), t₃(y))

(5)  (-, c(y), d(y), t₄(y))

(6)  (/, t₃(y), t₄(n), t₅(y))                    

(7)  (+, t₅(n), t₃(n), x(y))                     

(8)  (ie, _, _, _)                                                    

单寄存器R下的目标代码生成过程：

四元式	目标代码	SEM	RDV
(1)  (+, a(y), b(y), t1(y))	(1)LD R,a (2)ADD R,b		t1(y)
(2)  (<, t1(n), c(y), t2(y))	(3)LT R,c		t2(y)
(3)  (if, t2(n) , _ , 9)	(4)FJ R,?(15)	(4)
(4)  (+,a(y), b(y), t3(y))	(5)LD R,a (6)ADD R,b		t3(y)
(5)  (-, c(y), d(y), t4(y))	(7)ST R,t3 (8)LD R,c (9)SUB R,d		t4(y)
(6)  (/, t3(y), t4(n), t5(y))	(10)ST R,t4 (11)LD R,t3 (12)DIV R,t4		t5(y)
(7)  (+, t5(n), t3(n), x(y))	(13)ADD R,t3		x
(8)  (ie, _, _, _)	(14)ST R,x
	(15)

 

 

 

 

② while (A!=0){A=2+B/C;B=2+B/C;}优化的四元式序列：

(1)  (wh, _, _, _)

(2)  (!=, A, 0, t₁)

(3)  (do, t₁, _, 8)

(4)  (/, B, C, t₂)

(5)  (+, 2, t₂, A)

(6)  (=, A, _, B)

(7)  (we, _, _, 2)

附有活跃信息的四元式序列：

(1)  (wh, _, _, _)

(2)  (!=, A(y), 0, t₁(y))

(3)  (do, t₁(n), _, 8)

(4)  (/, B(y), C(y), t₂(y))

(5)  (+, 2, t₂(n), A(y))

(6)  (=, A(y), _, B(y))

(7)  (we, _, _, 2)

单寄存器R下的目标代码生成过程：

四元式	目标代码	SEM	RDV
(1)  (wh, _, _, _)	(1)	(1)
(2)  (!=, A(y), 0, t1(y))	(1)LD R,A (2)NE R,0		t1(y)
(3)  (do, t1(n), _, 8)	(3)FJ R,?(10)	(3)
(4)  (/, B(y), C(y), t2(y))	(4)LD R,B (5)DIV R,C		t2(y)
(5)  (+, 2, t2(n), A(y))	(6)ADD R,2		A
(6)  (=, A(y), _, B(y))	(7)ST R,B		A
(7)  (we, _, _, 2)	(8)ST R,A (9)JMP ?(1)
	(10)