《编译原理》期末复习资料完整版(古月系列lol(2)

《编译原理》期末复习资料完整版(古月系列lolxy)

福建农林大学计算机与信息学院

编译原理期末复习资料

(1)A={1,2,3},B={4,5,6,7} Aa={2,4} × (2)A={1,3},B={2},C={4,5,6,7} Aa={2} B,Ab={3,5} × (3)A={1},B={2},C={3},D={4,5,6,7}(单元素可以不用看，必有，古先看 D) Da={4,7} D,Db={5,6} D,Aa={2} B,Ab={3} C,Ba={4} D,Bb={3} C,Ca={2} B, Cb={5} C,则有 a A B C D B D B D b C C D D

2.(a*|b*)b(ba)*的状态转换图。 ( 的状态转换图。 ) ( ) 的状态转换图

Ia ① 1,2,3,4 ② 2,4 ③ 3,4,5,6,8 ④ 5,6,8 ⑤ 3,4,5,6,7,8 ⑥ 7 ⑦ 6,8 2,4 2,4 ----6,8 6,8 --Ia 1 2 3 4 5 6 7古 ○

Ib 3,4,5,6,8 5,6,8 3,4,5,6,7,8 7 3,4,5,6,7,8 --7 Ib 3 4 5 6 5 --6月 ○

2 2 ----7 7 --共 20 页 第 2 页

《编译原理》期末复习资料完整版(古月系列lolxy)

福建农林大学计算机与信息学院

编译原理期末复习资料

新的状态转换图如下：

化简： (用终结状态与非终结状态，然后输出状态一致分一类) 。 (1)A={1,2,6},B={3,4,5,7} Aa={2} × (2)A={1,2},B={6},C={3,4,7},D={5} Cb={5,6} ×(只要有一个不属于任何一个集合，就不行) (3)A={1,2},B={6},C={3},D={4,7},E={5} Ab={3,4} × (4) A={1}, B={2}, C={6}, D={3}, E={4,7}, F={5} Aa={2} B, Ab={3} D, Ba={2} B, Bb={4} E, Ca={7} E,Db={5} F,Eb={6} C,Fa={7} E,Fb={5} F a A B C D E F [注意事项 ： 注意事项]: 注意事项 B B E ----E b D E --F C F

[知识要点]: 正则表达式： a * , a | b, ab, ( ab)* , ( a | b)* , a ( a | b)* , a | a *b, a | ab*

a * {ε , a, aa, aaa, a a} ; a | b(a或b) {a, b}; ab(a和b) {ab};古 ○ 共 20 页 第 3 页 月 ○

《编译原理》期末复习资料完整版(古月系列lolxy)

福建农林大学计算机与信息学院

编译原理期末复习资料

(ab )* {ε , ab, abab, ababab, } (a | b )* (a | b )(a | b ) (a | b ) {ε , a, b, aab, aabb, baba, }a (a | b ) 是最左边一个字母一定是 a ,其余字母为 a、b 的任意组合，不包括 ε 。*

;

a | a *b {a, b, ab, aab, aaab, aaaab, } {a 和若干个 a(包括 0 的情形)后跟一个 b 构成的符号串集合}

a | ab* {a (ε | b* )} a (ε | b ) ab* {a, ab, abb, abbb, abbbb, } {a 和 a 后跟若干个(包括 0*

{

}

的情形)b 构成的符号串集合} 状态转换图(有穷

状态自动机) :

aab

ac*b

a*

a|b

ab

a + = aa *

古 ○

共 20 页 第 4 页

月 ○

《编译原理》期末复习资料完整版(古月系列lolxy)

福建农林大学计算机与信息学院

编译原理期末复习资料

(a | b )*

(ab )*

Φ

ε

a

【题 2】 】1.求如下简单算术表达式文法 Genr 中语法变量的 FOLLOW 集。 求如下简单算术表达式文法

E → TE ' E → +TE ' | ε T → FT ' T ' → *FT ' | ε F → ( E ) | id[解答]: (1)求表达式文法的语法符号的 FIRST 集： FIRST(F)={(, id} FIRST(T)=FIRST(F)={(, id} FIRST(E)=FIRST(T)={(, id} FIRST(E')={+,ε} FIRST(T')={*,ε} FIRST(+)={+}, FIRST(*)={*} FIRST(()={(}古 ○ 共 20 页 第 5 页 月 ○

《编译原理》期末复习资料完整版(古月系列lolxy)

福建农林大学计算机与信息学院

编译原理期末复习资料

FIRST())={)} FIRST(id)={id} (2)求表达式文法的语法变量的 FOLLOW 集： FOLLOW(E) = { #, ) } FOLLOW(E')= FOLLOW( E ) = { #, ) } FOLLOW(T) = {FIRST(E')-{ε}}∪FOLLOW(E)∪FOLLOW(E')= {+,),#} FOLLOW(T')= FOLLOW(T)= {+,),#} FOLLOW(F) = FIRST(T’)∪FOLLOW(T)∪FOLLOW(T') ={*,+,),#} 6 [知识点] 知识点] 集合的求法： First 集合的求法： First 集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的 First 集合，由于终结 符的 First 集合就是它自己，所以求出非终结符的 First 集合后，就可很直观地得到每个字符串的 First 集合 1. 2. 直接收取：对形如 U->a…的产生式(其中 a 是终结符) ,把 a 收入到 First(U)中 反复传送：对形入 U->P1P2P3…Pn 的产生式(其中 P 是非终结符) ,应先把 First(P1)中的全部内容传

送到 First(U)中,如果 P1中有 ε,把 First(P2)中的内容传送到 First(U)中,类推直到 Pi 中无 ε。 集合的求法： Follow 集合的求法： Follow 集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符 U 所有可能的后随终结符 号的集合，特别地，“$”是识别符号的后随符,先直接加入到 S 中。 1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把 a 直接收入到 Follow(U)中。 2. 直接收取：对形如“…UP…”(P 是非终结符)的组合，把 First(P)中非 ε 收入到 Follow(U)中。 3. 反复传送：对形如 U->aP 的产生式(其中 P 是非终结符)或 U->aPQ(P,Q 为非终结符且 Q 中含 ε),应 把 Follow(U)中的全部内容传送到 Follow(P)中。 [例] 文法：S→ABc A→a|ε B→b|ε 集合求法: First 集合求法:能由非终结符号推出的所有的开头符号或可能的 ε,但要求这个开头符号是终结符号。 如此题 A 可以推导出 a 和 ε,所以 FIRST(A)={a,ε} ;同理 FIRST(B)={b,ε};S 可以推导出 aBc, 还可以推导出 bc,还可以推导出 c,所以 FIRST(S)={a,b,c} Follow 集合的求法 集合的求法:紧跟随其后面的终结符号或#。但文法的识别符号包含#,在求的时候还要考虑到 ε。 具体做法是把

所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow(S)={#}如求 A 的， 产生式：S→ABc A→a|ε ,但只有 S→ABc 有用。跟随在 A 后面的终结符号是 FIRST(B)={b,ε} ,当 FIRST(B)的元素为 ε 时，跟随在 A 后的符号就是 c,所以 Follow(A)={b,c}同理 Fo …… 此处隐藏：11084字，全部文档内容请下载后查看。喜欢就下载吧 ……