第五章
2．对下面的文法G：
E→TE/
E/→+E|ε
T→FT/
T/→T|ε
F→PF/
F/→*F/|ε
P→(E)|a|b|^
(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。
(2)证明这个方法是LL(1)的。
(3)构造它的预测分析表。
(4)构造它的递归下降分析程序。
解：
（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(E/)={+,ε}
FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(T/)=FIRST(T)∪{ε}={(,a,b,^,ε};
FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(F/)=FIRST(P)={*,ε};
FIRST(P)={(,a,b,^};
FOLLOW集合有：
FOLLOW(E)={),#};
FOLLOW(E/)=FOLLOW(E)={),#};
FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};//不包含ε
FOLLOW(T/)=FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};
FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F/)=FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};
FOLLOW(P)=FIRST(F/)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)证明这个方法是LL(1)的。
各产生式的SELECT集合有：
SELECT(E→TE/)=FIRST(T)={(,a,b,^};
SELECT(E/→+E)={+};
SELECT(E/→ε)=FOLLOW(E/)={),#}
SELECT(T→FT/)=FIRST(F)={(,a,b,^};
SELECT(T/→T)=FIRST(T)={(,a,b,^};
SELECT(T/→ε)=FOLLOW(T/)={+,),#};
SELECT(F→PF/)=FIRST(P)={(,a,b,^};
SELECT(F/→*F/)={*};
SELECT(F/→ε)=FOLLOW(F/)={(,a,b,^,+,),#};
SELECT(P→(E))={(}
SELECT(P→a)={a}
SELECT(P→b)={b}
SELECT(P→^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。
(3)构造它的预测分析表。
文法G[E]的预测分析表如下：
(4)构造它的递归下降分析程序。
对每个非终结符写出不带回溯的递归子程序如下：
char CH;//存放当前的输入符号
void P_E()//非终结符E的子程序
{
if(IsIn(CH,FIRST_TEP)) //FIRST_TEP为T→TE/ 的右部的FIRST集合，产生式E→TE/
{
P_T();
P_EP();
}
else ERR;
}
void P_EP()//非终结符E/的子程序
{
if(CH==’+’) //产生式E/→+E
{
READ(CH);
P_E();
}
else//产生式E/→ε
{
if(IsIn(CH,FOLLOW_EP)) //FOLLOW_EP为E/的FOLLOW集合
return ;
else ERR;
}
}
void P_T()//非终结符T的子程序
{
if(IsIn(CH,FIRST_FTP)) //FIRST_TEP为T→FT/ 的右部的FIRST集合，产生式T→FT/
{
P_F();
P_TP();
}
else ERR;
}
void P_TP()//非终结符T/的子程序
{
if(IsIn(CH,FIRST_T)) //FIRST_T为产生式T/→T的右部的FIRST集合，产生式T/→T
{
P_T();
}
else//产生式T/→ε
{
if(IsIn(CH,FOLLOW_TP)) //FOLLOW_TP为T/的FOLLOW集合
return ;
else ERR;
}
}
void P_F()//非终结符F的子程序
{
if(IsIn(CH,FIRST_PFP)) //FIRST_PFP为F→PF/ 的右部的FIRST集合，产生式F→PF/
{
P_P();
P_FP();
}
else ERR;
}
void P_FP()//非终结符F/的子程序
{
if(CH==’*’) //产生式F/→*F/
{
READ(CH);
P_FP();
}
else//产生式F/→ε
{
if(IsIn(CH,FOLLOW_FP)) //FOLLOW_FP为F/的FOLLOW集合
return ;
else ERR;
}
}
void P_P()//非终结符P的子程序
{
if(CH==’(‘)
{
READ(CH);
P_E();
if(CH==’)’) READCH(CH);
else
ERR;
}
else if(CH==’a’) READ(CH);
else if(CH==’b’) READ(CH);
else if(CH==’^’) READ(CH);
else ERR;
}
4证明下述文法不是LL（1）的。
S->C$ C->bA|aB A->a|aC|bAA B->b|bC|aBB 你能否构造一等价的文法，使其是LL （1）的，并给出判断过程。
【解】因为SELECT(A->a)∩SELECT(A->aC)≠Ф,根据LL（1）文法的判定条件：(1)文法不含左递归(2)对于文法U的任意两个不同的规则有: Select(U→α) ∩Select(U→ )=Φ一个文法若满足以上条件，称该文法G为LL(1)文法。得出该文法不是LL（1）文法。该文法含公共因子，消除后的文法为：S->C$ C-> bA|aB A->aA'|bAA A’->C|εB->bB'| aBB
B’->C|ε【证明】因为SELECT(C-> bA) ∩SELECT(C->aB)= ΦSELECT(A->Aa) ∩SELECT(A->bAA) = ΦSELECT(A’->C) ∩SELECT(A’->ε)=(FIRST(C)-{ ε})∩FOLLOW(A’) ≠Ф因此消除公共因子后得到文法也不是LL（1）文法。
第五章 练习5.1.1： 对于图5-1中的SDD，给出下列表达式对应的注释语法分析树： 1）（3+4）*（5+6）n 练习5.2.4： 这个文法生成了含“小数点”的二进制数： S->L.L|L L->LB|B B->0|1 设计一个L属性的SDD来计算S.val，即输入串的十进制数值。比如，串101.101应该被翻译为十进制的5.625。提示：使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。 答： 元文法消除左递归后可得到文法： S->L.L|L L->BL’ L’->BL’|ε B->0|1 使用继承属性L.side指明一个二进制位数在小数点的哪一边,2表示左边，1表示右边 使用继承属性m记录B的幂次 非终结符号L和L’具有继承属性inh、side、m和综合属性syn
练习5.3.1：下面是涉及运算符+和整数或浮点运算分量的表达式文法。区分浮点数的方法是看它有无小数点。 E-〉E+T|T T-〉num.num|num 1）给出一个SDD来确定每个项T和表达式E的类型 2）扩展（1）中得到的SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数 答： 练习5.4.4：为下面的产生式写出一个和例5.10类似的L属性SDD。这里的每个产生式表
示一个常见的C语言中的那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个标号L，此时你可以生成语句goto L 1）S->if (C) S1 else S2 2）S->do S1 while (C) 3）S->’{’ L ‘}’; L -> LS|ε 请注意，列表中的任何语句都可以包含一条从它的内部跳转到下一个语句的跳转指令，因此简单地为各个语句按序生成代码是不够的。 第六章 练习6.1.1：为下面的表达式构造DAG （（x+y）-（（x+y）*（x-y）））+（（x+y）*（x-y）） 答：DAG如下
P532.8 构建一个语法制导翻译模式，将算术表达式从后缀表示翻译成中缀表示。给出输入95-2*和952*-的注释分析树。（仅供参考一定要保证转换后的中缀表达式与原后缀表达式的优先级相同） 1 后缀算术表达式的文法如下： expr →expr expr + | expr expr – | expr expr * | expr expr / |digit digit →0 | 1 | 2 | 3 | … | 9 2 将后缀表达式翻译成中缀表达式的语法制导定义（文法+语义规则）
4 95-2*和952*-的翻译成后缀形式的语义动作与注释分析树。 expr expr expr * print(‘(‘) print(‘)‘) expr expr - 5 9 digit 2 print(‘-’) ‘9’) print(‘5’) print(‘2’) print(‘*’) 95-2*的深度优先遍历语义动作 expr expr expr - print(‘(‘) print(‘)‘) expr expr digit 2 digit 5 digit 9 print(‘*’) ‘5’) print(‘2’) print(‘9’) print(‘-’) 952*-的深度优先遍历语义动作
expr.t=(9-5)*2 expr=(9-5) expr.t=2 * expr.t=9 expr.t=5 - digit.t=5 5 digit.t=9 9 digit.t=2 2 输入为95-2*的注释分析树 expr.t=(9-5*2) expr.t=5*2 expr.t=9 - expr.t=5 expr.t=2 * digit.t=2 2 digit.t=5 5 digit.t=9 9 输入为952*-的注释分析树
第5章自顶向下语法分析方法 第1题 对文法G[S] S→a||(T)∧ T→T,S|S (1) 给出(a,(a,a))和(((a,a),,(a)),a)∧的最左推导。 (2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 答案：
也可由预测分析表中无多重入口判定文法是LL(1)的。 可见输入串（a,a）#是文法的句子。 第3题 已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。
第7题 对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。 (１)A→baB|ε
B→Abb|a (2) A→aABe|a B→Bb|d (3) S→Aa|b A→SB B→ab 答案： (１)先改写文法为： 0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a 再改写文法为： 0) A→baB 1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b （2）文法：A→aABe|a B→Bb|d 提取左公共因子和消除左递归后文法变为： 0) A→a N 1) N→A B e 2) N→ε 3) B→d N1 4) N1→b N1 5) N1→ε
（3）文法：S→Aa|b A→SB B→ab 第1种改写： 用A的产生式右部代替S的产生式右部的A得：S→SBa|b B→ab 消除左递归后文法变为： 0) S→b N 1) N→B a N 2) N→ε 3) B→a b
第七章作业 练习7.2.5：在一个通过引用传递参数的语言中，有一个函数f(x,y)完成下面的计算：x=x+1;y=y+2;return x+y; 如果将a赋值为3，然后调用f(a,a)，那么返回值是什么？ 解：执行语句x=x+1，则a=a+1=4， 再执行语句y=y+2，则a=a+2=5， 最后返回x+y，则返回a+a=9。 练习7.2.6：C语言函数f的定义如下： int f(int x,*py,**ppz) { **ppz+=1;*py+=2;x+=3;return x+*py+**ppz; } 变量a是一个指向b的指针；变量b是一个指向c的指针，而c是一个当前值为4的整数变量。如果我们调用f(c,b,a)，返回值是什么？ 解：先执行语句**ppz+=1，则c=*b=**a=5， 再执行语句*py+=2，则*b=*b+2=7，c=*b=**a=7, 接着执行语句x+=3，则x=4,x=x+3=7,而c=*b=**a=7， 最后执行语句return x+*py+**ppz，则返回7+7+7=21。 练习7.3.2：假使我们使用显示表来实现下图中的函数。请给出对fib0(1)的第一次调用即将返回时的显示表。同时指明那时在栈中的各个活动记录中保存的显示表条目。 计算Fibonacci数的嵌套函数 解：
第八章练习 练习8.2.1：假设所有的变量都存放在内存中，为下面的三地址语句生成代码： 5）两个语句的序列 x=b*c y=a+x 解：生成的代码如下： LD R1, b LD R2, c MUL R1, R1, R2 ST x, R1 LD R2, a ADD R1, R2, R1 ST y, R1 练习8.2.6：确定下列指令序列的代价。 1）LD R0,y LD R1,z ADD R0,R0,R1 ST x,R0 解：2+2+1+2=7 2）LD R0,i MUL R0,R0,8 LD R1,a(R0) ST b,R1 main() fib0(4) 保存的d[2] fib1(4) 保存的d[3] fib2(4) 保存的d[4] fib1(3) 保存的d[3] fib0(2) 保存的d[2] fib1(2) 保存的d[3] fib0(1) 保存的d[2] d[1] d[2] d[3] d[4]
第五章语法分析—自下而上分析 本章要点 1. 自下而上语法分析法的基本概念： 2. 算符优先分析法； 3. LR分析法分析过程； 4. 语法分析器自动产生工具Y ACC； 5. LR分析过程中的出错处理。 本章目标 掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。 本章重点 1．自下而上语法分析的基本概念：归约、句柄、最左素短语； 2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理；3．LR分析器： （1）LR(0)项目集族，LR(1)项目集簇； （2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造； （3）LR分析的基本原理，分析过程； 4．LR方法如何用于二义文法； 本章难点 1. 句柄的概念； 2. 算符优先分析法； 3. LR分析器基本； 作业题 一、单项选择题： 1. LR语法分析栈中存放的状态是识别________的DFA状态。 a. 前缀； b. 可归前缀； c. 项目； d. 句柄； 2. 算符优先分析法每次都是对________进行归约： (a)句柄（b）最左素短语(c)素短语(d)简单短语
3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。 a. LL(1)文法； b.二义性文法； c.算符优先文法； d.SLR(1)文法； 4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LL(1)分析法属于自顶向下分析； a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 5. 自底向上语法分析采用分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。 a. 递归 b. 回溯 c. 枚举 d. 移进－归约 6. 一个LR(k)文法，无论k取多大，。 a. 都是无二义性的； b. 都是二义性的； c. 一部分是二义性的； d. 无法判定二义性； 7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LR分析法属于自底向上分析。 a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 8. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为输入符号串构造一个； a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 9. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为输入符号串构造一个。 a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 10. 采用自顶向下分析方法时，要求文法中不含有。 a. 右递归 b. 左递归 c. 直接右递归 d. 直接左递归 11. LR分析是寻找右句型的；而算符优先分析是寻找右句型的。 a. 短语； b. 素短语； c. 最左素短语； d. 句柄 12. LR分析法中分析能力最强的是；分析能力最弱的是。 a. SLR(1)； b. LR(0)； c. LR(1)； d. LALR(1) 13. 设有文法G： T->T*F | F F->F↑P | P P->(T) | a 该文法句型T*P↑(T*F)的最左直接短语是下列符号串________。 a. (T*F)， b. T*F， c. P， d. P↑(T*F) 14. 在通常的语法分析方法中，（）特别适用于表达式的分析。 a．算符优先分析法b．LR分析法c．递归下降分析法d．LL(1)分析法 15. .运算符的优先数之间有几种关系。 a.3种 b. 2种 c. 4种 d. 1种 16. 算符优先法属于（） a.自上而下分析法 b.LR分析法 c.ＳLR分析法 d.自下而上分析法 17. 在LR分析法中，分析栈中存放的状态是识别规范句型的DFA状态。 a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目 一．答案： 1. b； 2. b； 3. b； 4. d； 5. d； 6. a； 7. c； 8. c； 9. d；10. b；11. d，c；12. c，b；13. a；14. a 15. a；16. d；17. c；
1) What is the difference between a compiler and an interpreter? A compiler is a program that can read a program in one language - the source language - and translate it into an equivalent program in another language – the target language and report any errors in the source program that it detects during the translation process. Interpreter directly executes the operations specified in the source program on inputs supplied by the user. 2) What are the advantages of: (a) a compiler over an interpreter a. The machine-language target program produced by a compiler is usually much faster than an interpreter at mapping inputs to outputs. (b) an interpreter over a compiler? b. An interpreter can usually give better error diagnostics than a compiler, because it executes the source program statement by statement. 3) What advantages are there to a language-processing system in which the compiler produces assembly language rather than machine language? The compiler may produce an assembly-language program as its output, because assembly language is easier to produce as output and is easier to debug. 4.2.3 Design grammars for the following languages: a) The set of all strings of 0s and 1s such that every 0 is immediately followed by at least 1. S -> SS | 1 | 01 | 4.3.1 The following is a grammar for the regular expressions over symbols a and b only, using + in place of | for unions, to avoid conflict with the use of vertical bar as meta-symbol in grammars: rexpr -> rexpr + rterm | rterm rterm -> rterm rfactor | rfactor rfactor -> rfactor * | rprimary rprimary -> a | b a) Left factor this grammar. rexpr -> rexpr + rterm | rterm rterm -> rterm rfactor | rfactor rfactor -> rfactor * | rprimary rprimary -> a | b
第五章 2．对下面的文法G： E→TE/ E/→+E|ε T→FT/ T/→T|ε F→PF/ F/→*F/|ε P→(E)|a|b|^ (1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。 (2)证明这个方法是LL(1)的。 (3)构造它的预测分析表。 (4)构造它的递归下降分析程序。 解： （1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(E/)={+,ε} FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(T/)=FIRST(T)∪{ε}={(,a,b,^,ε}; FIRST(F)=FIRST(P)={(,a,b,^}; FIRST(F/)=FIRST(P)={*,ε}; FIRST(P)={(,a,b,^}; FOLLOW集合有： FOLLOW(E)={),#}; FOLLOW(E/)=FOLLOW(E)={),#}; FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};//不包含ε FOLLOW(T/)=FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F/)=FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F/)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)证明这个方法是LL(1)的。 各产生式的SELECT集合有： SELECT(E→TE/)=FIRST(T)={(,a,b,^}; SELECT(E/→+E)={+}; SELECT(E/→ε)=FOLLOW(E/)={),#} SELECT(T→FT/)=FIRST(F)={(,a,b,^}; SELECT(T/→T)=FIRST(T)={(,a,b,^}; SELECT(T/→ε)=FOLLOW(T/)={+,),#}; SELECT(F→PF/)=FIRST(P)={(,a,b,^}; SELECT(F/→*F/)={*}; SELECT(F/→ε)=FOLLOW(F/)={(,a,b,^,+,),#}; SELECT(P→(E))={(} SELECT(P→a)={a}
第四章部分习题解答 Aho：《编译原理技术与工具》书中习题 （Aho）4.1 考虑文法 S →( L ) | a L →L, S | S a)列出终结符、非终结符和开始符号 解： 终结符：(、)、a、， 非终结符：S、L 开始符号：S b)给出下列句子的语法树 i)(a, a) ii)(a, (a, a)) iii)(a, ((a, a), (a, a))) c)构造b)中句子的最左推导 i)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, a) ii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, (a, S) ?(a, (a, a)) iii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, ((L), S)) ?(a, ((L, S), S)) ?(a, ((S, S), S)) ?(a, ((a, S), S)) ?(a, ((a, a), S)) ?(a, ((a, a), (L))) ?(a, ((a, a), (L, S))) ?(a, ((a, a), (S, S))) ?(a, ((a, a), (a, S))) ?(a, ((a, a), (a, a))) d)构造b)中句子的最右推导
i)S?(L)?(L, S) ?(L, a) ?(S, a) ?(a, a) ii)S?(L)?(L, S) ? (L, (L)) ?(L, (L, S)) ?(L, (L, a)) ?(L, (S, a)) ?(L, (a, a)) ?(S, (a, a)) ?(a, (a, a)) iii)S?(L)?(L, S) ?(L, (L)) ?(L, (L, S)) ?(L, (L, (L))) ?(L, (L, (L, S))) ?(L, (L, (L, a))) ?(L, (L, (S, a))) ?(L, (L, (a, a))) ?(L, (S, (a, a))) ?(L, ((L), (a, a))) ?(L, ((L, S), (a, a))) ?(L, ((L, a), (a, a))) ?(L, ((S, a), (a, a))) ?(L, ((a, a), (S, S))) ?(S, ((a, a), (a, a))) ?(a, ((a, a), (a, a))) e)该文法产生的语言是什么 解：设该文法产生语言（符号串集合）L，则 L = { (A1, A2, …, A n) | n是任意正整数，A i=a，或A i∈L，i是1～n之间的整数} （Aho）4.2考虑文法 S→aSbS | bSaS | ε a)为句子构造两个不同的最左推导，以证明它是二义性的 S?aSbS?abS?abaSbS?ababS?abab S?aSbS?abSaSbS?abaSbS?ababS?abab b)构造abab对应的最右推导 S?aSbS?aSbaSbS?aSbaSb?aSbab?abab S?aSbS?aSb?abSaSb?abSab?abab c)构造abab对应语法树 d)该文法产生什么样的语言？ 解：生成的语言：a、b个数相等的a、b串的集合 （Aho）4.3 考虑文法 bexpr→bexpr or bterm | bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor | ( bexpr ) | true | false a)试为句子not ( true or false)构造分析树 解：
第五章代码优化 5.1 完成以下选择题： (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. 满足对称性 【解答】 (1) d (2) c (3) b (4) d (5) d 5.2 何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？ 【解答】优化根据涉及的程序范围可分为三种。 (1) 局部优化是指局限于基本块范围内的一种优化。一个基本块是指程序中一组顺序执行的语句序列(或四元式序列)，其中只有一个入口(第一个语句)和一个出口(最后一个语句)。对于一个给定的程序，我们可以把它划分为一系列的基本块，然后在各个基本块范围内分别进行优化。通常应用DAG方法进行局部优化。 (2) 循环优化是指对循环中的代码进行优化。例如，如果在循环语句中某些运算结果不随循环的重复执行而改变，那么该运算可以提到循环外，其运算结果仍保持不变，但程序运行的效率却提高了。循环优化包括代码外提、强度削弱、删除归纳变量、循环合并和循环展开。 5.3 将下面程序划分为基本块并作出其程序流图。 read(A,B) F=1 C=A*A D=B*B if C 第四章 习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解 1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3)消除左递归后的文法 rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归，适合于自顶向下的语法分析 习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③ (5) ①消除该文法的左递归得到文法 S->(L)|a 第五章自顶向下语法分析方法 1．对文法G[S] S→a|∧|(T) T→T,S|S (1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。 (2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3)经改写后的文法是否是LL(1)的？给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 解： (1) (a,(a,a))的最左推导为S→(T)→(T,S)→(S,S)→(a,(T))→(a,(T,S))→(a,(S,a))→(a,(a,a)) (((a,a),∧,(a)),a)的最左推导为 S→(T)→(T,S)→(S,a)→((T),a)→((T,S),a)→((T,S,S),a)→((S,∧,(T)),a)→(((T),∧,(S)),a) →(((T,S),∧,(a)),a)→(((S,a),∧,(a)),a)→(((a,a),∧,(a)),a) (2)由于有T→T,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/[S]: S→a|∧|(T) T→SU U→，SU|ε 分析子程序的构造方法 对满足条件的文法按如下方法构造相应的语法分析子程序。 (1) 对于每个非终结号U，编写一个相应的子程序P(U)； (2) 对于规则U::=x1|x2|..|xn,有一个关于U的子程序P(U),P(U)按如下方法构造： IF CH IN FIRST(x1) THEN P(x1) ELSE IF CH IN FIRST(x2) THEN P(x2) ELSE ... . . . IF CH IN FIRST(xn) THEN P(xn) ELSE ERROR 其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序； P(xj)为相应的子程序。 (3) 对于符号串x=y1y2...yn;p(x)的含义为： BEGIN P(y1); P(y2); ... P(yn); END 如果yi是非终结符，则P(yi)代表调用处理yi的子程序； 如果yi是终结符，则P(yi)为形如下述语句的一段子程序 IF CH=yi THEN READ(CH) ELSE ERROR 即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中， 否则表明出错。 (4) 如果文法中有空规则U::=EPSILON,则算法中的语句 IF CH IN FIRST(xn) THEN P(xn) P1774.14 为练习4.3的文法构造一个预测语法分析器 bexpr→bexpr or bterm|bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor|(bexpr)|true |false 解1 非递归方法 1)消除左递归 ①bexpr→bterm A ②A→or bterm A ③A→ε ④bterm→bfactor B ⑤B→and bfactor B ⑥B→ε ⑦bfactor→not bfactor ⑧bfactor→(bexpr) ⑨bfactor→true ⑩bfactor→false 2)求first集与follow集 针对以同一非总结符开头的产生式右部求first集如果该非终结符能产生ε则需要求其follow集 ①bexpr→bterm A first(bterm A)= {not,(,true,false} ②A→or bterm A first(or bterm A)={or} ③A→εfollow(A）=follow(bexpr)= {$, )} ④bterm→bfactor B first(bfactor B)={not,(,true,false} ⑤B→and bfactor B first(and bfactor B)={and} ⑥B→εfollow(B）=follow(bterm)=first(A) 因为first(A)= {or , ε} 包含ε 所以follow(B）=follow(bterm) =first(A)∪follow(A）-{ε}={or, $, )} ⑦bfactor→not bfactor first(not bfactor)={not} ⑧bfactor→(bexpr)first((bexpr))={(} ⑨bfactor→true first(true)={true} ⑩bfactor→false first(false)={false} 表中空白处填error，表示调用错误处理程序 4)根据步骤3）编写预测分析程序 下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。 repeat 6.1 假如有下面的Pascal说明 TYPE atype=ARRAY [0..9,-10..10] OF integer; cell=RECORD a,b:integer END; pcell=↑cell; foo=ARRAY [1..100] OF cell; FUNCTION bar(r:integer;y:cell):pcell; BEGIN……END; 写出atype,cell,pcell,foo和bar的类型表达式。 解答: atype: ARRAY(0..9, ARRAY(-10..10, integer)); cell: RECORD((a× integer)× (b×integer)); pcell: POINTER(cell); 或 : POINTER(RECORD((a ×integer)× (b× integer))); foo: ARRAY(1..100, cell); 或 : ARRAY(1..100, RECORD((a ×integer)× (b× integer))); bar: integer× cell→pcell; 或 : integer× cell→POINTER(RECORD((a×integer) ×(b×integer))); 6.4 假定类型定义如下: TYPE link=↑cell; cell=RECORD info:integer; next: link END; 下面哪些表达式结构等价？哪些名字等价？ （1）Link （2）pointer(cell) （3）pointer(Link) （4）pointer(record(info?integer)?(next ? pointer(cell))) 解答:(1)(2)(4)结构等价，无名字等价。 第五章部分习题解答 Aho：《编译原理技术与工具》书中习题 （Aho）5.3 为下面表达式构造有向无环图，标出结点（子表达式）编号，+是左结合的 a + a + (a + a + a + (a + a + a + a)) 解： （Aho）5.5 设计语法制导定义，实现多项式（包含+和*，如x*(3*x+x*x)）的求导，结果无需化简，如3*x直接翻译为3*1+0*x即可。（思路：(xy)?=x?y+y?x，(x+y)?=x?+y?） 解： 综合属性diff为求导后的表示形式，val为原多项式表示形式 E→E1 + T { E.val = E1.val || “+” || E.val; E.diff = E1.diff || “+” || E.diff; } | T { E.val = T.val; E.diff = T.diff; } T→T1 * F { T.val = T1.val || “*” || F.val; T.diff = “(” || T1.diff || “*” || F.val || “+” || T1.val || “*” || F.diff || “)”; } | F { T.val = F.val; T.diff = F.diff; } F→( E ) { F.val = “(” || E.val || “)”; F.diff = “(” || E.diff || “)”; } | num { F.val = num.val; F.diff = 0; } | x { F.val = “x”; F.diff = 1; } 此题和后面两题均可编写Lex&Yacc程序进行验证。 （Aho）5.4 设计翻译模式，实现将中缀表达式翻译为无多余括号形式 解：所谓“多余括号”，可以理解为： 本该是表达式E，写成了(E)的形式， 本该是项T，写成了(T)的形式， 本该是因式F，写成了(F)的形式，因此，可写出文法和翻译模式： E→( E1 ) { E.s = E1.s; } | E1 + T { E.s = E1.s || …+? || T.s; } | T { E.s = T.s; } T→( T1 ) { T.s = T1.s; } | T1 + F { T.s = T1.s || …*? || F.s; } | F { T.s = F.s; } 文法G3: S→A[B] A→[B]|Aa B→a 1.求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括符号'#'在内的算符优先表; 2.给出语句#[a][a]#的算符优先分析过程。 给定以下拓广了的文法G[S’]： (0)S’->A (1)A->Ab (2)A->bBa (3)B->aAc (4)B->a (5)B->aAb 1.构造LR(0)项目集规范族，证明它是SLR(1)的，而不是LR(0)的。 2.构造SLR(1)分析表。（按题中的产生式编号填写） 3.用你构造的SLR(1)分析表分析串baab是否为该文法的句子。 因为FOLLOW(B)={a},和{b}不相交，所以可以解决I5中的移进和归约冲突；FOLLOW(A)={#,b,c}和FOLLOW(B)={a}也不相交，所以可以解决I9中的归约和归约冲突；因此该文法是SLR(1)文法。 1. LR(0)项目集规范族: 从LR(0)项目集规范族中可以看出： 由于在状态I5中有移进和归约冲突，在状态I9中有归约和归约冲突，所以它而不是LR(0)文法。 所以，符号串baab是该文法的一个句子。 文法G[S]为（VT,VN,S,P），其中VT={a,b,c},VN={S,L,R}，P为如下产生式： S->LaR|R L->bR|c R->L 该文法是否SLR(1)文法？ 该文法是否LR(1)文法？ 如果是LR(1)文法，请给出用LR(1)分析表对句子bcac#的分析过程；如果不是LR(1)文法，请给出句子bcac的规范推导。 答：（过程略） 该文法的lr(0)项目集中出现了移进和归约冲突，所以不是SLR文法， 该文法的lr(1)项目集中没有冲突，所以是LR(1)文法 用LR(1)分析表对句子bcac#的分析过程： 编译原理第二版第 五章答案 本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March 第五章 第5章自顶向下语法分析方法 练习（P99） 1.文法 S->a|^|(T) T->T,S|S (1) 对(a,(a,a)和(((a,a),^,(a)),a)的最左推导。 (3)经改写后的文法是否为LL（1）的给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 (1) 对(a,(a,a)的最左推导为： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a)) 对(((a,a),^,(a)),a) 的最左推导为： S=>(T) =>(T,S) =>(S,S) =>((T),S) =>((T,S),S) =>((T,S,S),S) =>((S,S,S),S) =>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S) =>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a) (3)改写文法为： 0) S->a 1) S->^ 2) S->( T ) 3) T->S N 4) N->, S N 5) N->ε 第5章习题 6-1 将下列中缀式改写为逆波兰式。 (1) -A*(B+C)/(D-E) (2) ((a*d+c)/d+e)*f+g (3) a+x≤4∨(c>d*3) (4) a∨b∧c (3) ax+4≤cd3*>∨ (4) abcde*f/<∧∨ 6-2 解： (1) a+b*c (2) a*(b-c)-(c+d)/e (3) a≤b+c∧a>0∨a+b≠0∧a<0 6-3 解： (1) (1) (+,B,C,T1) (2) (*,A,T1 ,T2) (3) (+,T2 ,D,T3) (4) (=,T3 ,0,X) (2) 如下所示： (1) (jnz,A,0,3); (2) (j,0,0,p+1); (3) (jnz,B,0,9); (4) (j,0,0,5); (5) (jnz,C,0,9); (6) (j,0,0,7); (7) (jnz,D,0,9); (8) (j,0,0,p+1); (9) 与S1相应的四元式序列 (p) (j,0,0,q) (p+1) 与S2相应的四元式序列 (q) … (3) 假设所产生的四元式序列编号从1开始 (1) (j 编译原理第五章答案本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March 第5章自顶向下语法分析方法 第1题 对文法G[S] S→a||(T)∧ T→T,S|S (1) 给出(a,(a,a))和(((a,a),,(a)),a)∧的最左推导。 (2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 答案： 也可由预测分析表中无多重入口判定文法是LL(1)的。 可见输入串（a,a）#是文法的句子。 第3题 已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 第7题 对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法试对下面文法进行改写，并对改写后的文法进行判断。 (１)A→baB|ε B→Abb|a (2) A→aABe|a B→Bb|d (3) S→Aa|b A→SB B→ab 答案： (１)先改写文法为： 0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a 再改写文法为： 0) A→baB 1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b （2）文法：A→aABe|a B→Bb|d 提取左公共因子和消除左递归后文法变为： 0) A→a N 1) N→A B e 2) N→ε 3) B→d N1 4) N1→b N1 5) N1→ε编译原理第4章作业答案
编译原理第五章 作业参考答案
龙书 第四章课后作业答案
编译原理龙书第六章课后作业答案
编译原理 龙书答案
编译原理第五章 参考答案
编译原理第二版第五章答案
蒋立源编译原理第三版 第五章 习题与答案
编译原理第五章答案
相关主题
文本预览