编译原理总复习市公开课一等奖百校联赛优质课金奖名师赛课获奖课件.pptVIP

复习纲领;一、基础知识

1、经典编译程序可划分为几部分？各部分主要功效是什么？

2、什么是句子和什么是句型？

3、文法和语言关系？

4、二义性文法？

5、语法分析惯用方法？

6、LL（1）文法、LR(0)文法、SLR(1)文法、LR(1)文法充分必要是什么？;7、属性文法中符号属性分为哪几个？怎样设计递归下降翻译？

8、栈式符号表工作过程。

9、程序运行时存放分配方法有哪些？动态存放分配包含两种方式？

10、代码优化惯用三种方法？

;二、针对语言结构文法

1、L(G)={奇正整数};

2、L(G)={anbm|n,m≥1};;三、针对文法结构语言

1、已知文法G[S]：

S∷=AB

A∷=aA︱ε

B∷=bBc︱bc,

写出该文法描述语言。;1、有正则文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a，画出该文法状态图，并检验句子abba是否正当。;五、求句型短语、简单短语以及句柄，依据文法推导句子或者句型。

1、已知文法

E∷=T∣E+T∣E-T

T∷=F∣T*F∣T/F

F∷=(E)∣x，

(1)给出句子x+(x*x)最左推导和最右推导。

（2）写出句型（E+T）–F*x短语、简单短语以及句柄;1、短语

(1)(E+T)-F*x

(2)(E+T)

(3)E+T(简单短语、句柄)

(4)F*x

(5)F(简单短语)

(6)x(简单短语）;六、以下文法G是左递归文法，试消除其左递归。;七、NFA确实定化;八、依据正则表示式结构对应NFA或DFA

1、1(1|0)*|0NFA

2、(ab)*(a*|b*)(ba)*等价DFA;;q0=ε-closure({0})={0,1,3,4,5,6,7,9};

q0a=ε-closure(δ(q0,a))=

ε-closure({2,,4})={2,4,6,7,9}=q1;

q0b=ε-closure(δ(q0,b))=

ε-closure({5,8})={5,6,7,8,9}=q2;

q1a=ε-closure(δ(q1,a))=

ε-closure({4})={4,6,7,9}=q3;

q1b=ε-closure(δ(q1,b))=

ε-closure({1,8})={1,3,4,5,6,7,8,9}=q4;

q2a=ε-closure(δ(q2,a))=ε-closure({7})={7,9}=q5;

q2b=ε-closure(δ(q2,b))=

ε-closure({5,8})={5,6,7,8,9}=q2;

q3a=ε-closure(δ(q3,a))=

ε-closure({4})={4,6,7,9}=q3;;q3b=ε-closure(δ(q3,b))=ε-closure({8})={8}=q6;

q4a=ε-closure(δ(q4,a))=

ε-closure({2,4})={2,4,6,7,9}=q1;

q4b=ε-closure(δ(q4,b))=

ε-closure({5,8})={5,6,7,8,9}=q2;

q5a=ε-closure(δ(q5,a))=ε-closure({φ})=φ;

q5b=ε-closure(??(q5,b))=ε-closure({8})={8}=q6

q6a=ε-closure(δ(q6,a))=

ε-closure({7})={7,9}=q5;

q6b=ε-closure(δ(q6,b))=ε-closure({φ})=φ；

计算到此，不再有新状态。;a;十、将右图DFA化简。;（4）对于s4={3,5}划分：

δ(3,a)=3;δ(3,b)=2;

δ(5,a)=5;δ(5,b)=4;

即S4不能划分，说明状态3和状态5等价.;;Y;十二、递归下降分析方法，对此文法来说，在分析过程中，能否防止回溯问题。

1、设有文法G[