编译原理复习大纲lk.doc

1、 理解编译器的概念，掌握编译器的功能，熟练掌握编译器的主要翻译步骤。了解与编译器相关的程序及其功能 2、 扫描器功能,理论依据，它完成任务是什么？ @@ 符号表用法如、符号表中的信息栏中登记了每个名字的有关的性质，它有那些内容？ 6.能画出程序框图，了解其功能，能叙述编译的基本结构 文法的集中类型和主要特点.如文法有几种类型 各自特点？掌握正则表达式及其生成语言的定义，熟练掌握正则表达式的三种基本运算，会根据语言写出正则表达式，或者反过来写出指定的正则表达式生成的语言的特征。 从各选择对象中选择，用元字符｜表示。比如： a|b 2. 连结，由并置表示。比如： ab 3. 重复或“闭包”，由元字符*表示。比如： a* 例题：给出下面语言的相应文法: L1={an bn | n≥1} L2={anbm+nam | n≥1，m≥0} 掌握DFA及其可接受的语言的定义，会根据语言画DFA图，或者反过来写出指定的DFA图可接受的语言的特征。 @@ 掌握用代码实现DFA的两种算法，熟练掌握基于转换表的算法。 @@ 掌握正则表达式和DFA图，了解词法分析程序。 例题：给定文法G[S]： S→aA|bQ； A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF F→bD|aE|b 构造相应的最小的DFA 。 解：先构造其NFA： 用子集法将NFA确定化： a b S A Q A A BZ Q Q DZ BZ Q D DZ A B D A B B Q D 将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。 a b 0 1 2 1 1 3 2 2 4 3 2 5 4 1 6 5 1 6 6 2 5 令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割： P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割： P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。 再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。 最小化为右上图。 @@ 掌握文法的二义性概念，会识别和消除文法的二义性。 S S S ( S ) S S ( S ) S ε ε S ( S ) S S ( S ) S ε ε ε ε ε ε ε ε @@消除下列文法G[E]的左递归。 E→E-T∣T T→T/F∣F F→( E )∣i 解答： 消除文法G[E]的左递归后得到： E→TE’ E’→ -TE’∣ε T→FT’ T’→/FT’∣ε F→( E )∣i @@ 说明下面文法G[S]是二义性文法：S→SaS|SbS|cSd|eS|f 例子：fafbf是文法G[S]的一个句子，并且有两个不同的最右推导。 （1）S = SaS = SaSbS = SaSbf= Safbf= fafbf （2）S = SbS = Sbf= SaSbf = Safbf= fafbf 因此说明此文法有二义性。 @@ 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左递归及提取公共左因子。 解：消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε @@ b) 计算First集合和Follow集合的算法；对文法G(S)：S → a | ^ | (T)； T → T，S | S S’-#S#; )lastvt(T) (firstvt(T) 答：(1) a ^ ( ) , a ^ ( = ) , # = (2) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系(3) 给出输入串(a,a)#的算符优先分析过程。 栈 当前输入字符 剩余输入串 动作 1 # ( a,a# #( 移进 2 #( a ,a)#