第三章复习重点：1.文法与语言的对应关系思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的“切割”？例：已知语言：L1 = {a x b2x c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。
提示：该题实际上要求为相应语言设计上下文无关文法。
一个文法设计好后，严格来说应当证明此文法是否对应于该语言。
解：G[S]：S →AB A →ε | aAbb B →ε | cB推导过程：S ⇒ AB +⇒ a x Ab2x B /*使用A →aAbb x次*/⇒ a x b2x B /*使用A →ε一次*/⇒ a x b2x c x B /*使用B →cB x次*/⇒ a x b2x c x/*使用B →ε一次*/举一反三：已知语言L2 = {a x b2y c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。
解：G[S]：S →AB A →ε | aA B →ε | bBcc练习：14：写出下列语言对应的文法(1).{a n b n a m b m|n,m≥0}2. {1n 0m 0m 0n |n,m ≥0}3. {1n 0m 0m 0n |n ≥0,m>0}4. { a n b m c k |n,m,k ≥0}G1: S —>AA G2: S —>ABA —>aAb|ε A —>aAb|εB —>aBb|ε G: S —>1S0 S —>A A —>0A1 A —>εG: S →1S0|A S →1S0|0A1 A →0A1|01 A →0A1|ε2. 给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。
1. 令文法G ［E ］为：Z →bMb M →a|(L L →Ma ）① 符号串b(Ma)b 是否为该文法的一个句型，并证明。
② 若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。
1）（5分）证明：S=> bMb=>b(Lb=>b(Ma)b所以，符号串b(Ma)b 是该文法的一个句型。
（2）（5分）短语: Ma)， (Ma)， b(Ma)b直接短语: Ma) 句柄: Ma)练习：（10分）已知文法G[T]： T →T*F | F ；F →F ↑P | P ； P →(T) | i（1）用最右推导法证明β：T*P ↑(T*F) 是G[T]的一个句型； （2）画出β的语法树；（3）写出β的全部短语、直接短语和句柄。
(1) T=>T*F=>T*F ↑P=>T*F ↑(T)=> T*F ↑(T*F) =>T*P ↑(T*F) 证毕。
(2) 如图T T* F F ↑PPT* TF()第3题 语法树（3）短语：T*P ↑(T*F) ；P ↑(T*F) ；(T*F) ；T*F ；P 直接短语：T*F ；P句柄： P3. 证明一个文法是二义性文法。
证明下述文法G ［S ］是二义的。
（5分） S->iSeS|iS|i解：S Si S e S i Si S i S e S可见，句型iises 有两种不同的语法树，所以G[S]是二义的。
练习：证明下述文法G ：S →aSbS|aS|d 是二义性文法。
解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。
句子aadbd 有两棵语法树。
如下图：(1) (2)由此可知，S →aSbS|aS|d 定义的文法是二义性文法。
第四章: 重点：1. NFA DFA 的确定化及DFA 的最小化。
2. 试写出描述语言L 的正规式，构造能识别该语言L 等价的NFA ，再确定化 将下图所示的NFA 确定化，再最小化。
(2010年出过)d SS a b S S a d S a SS a bS ddB B{1,2,3,4} B {1,2,3,4} C{1,2,4,Y}CC{1,2,4,Y} B {1,2,3,4} C{1,2,4,Y}由于对于非终态的状态A 和B 来说，它们输入a 、b 的下一个状态都是一样的，故状态A 和B 可以合并，将合并后的状态重命名为A ，而终态则重命名为B ，则合并后的状态转换矩阵为：S a b A A B BAB由此可以得到最小化的DFA ，如下图所示：练习1：给出接受字母表 ={a ，b}，语言为以b 开头，以aa 结尾的字符串集合的正规表达式，并构造与之等价状态的DFA 。
（2010年出过）答：依题意，以b 开头，以aa 结尾的字符串集合的正规表达式可写为： b(a|b)*aa画NFA ，如下图所示用子集法确定化如下表II aI b{X}A {1} B {1,2}C {1,2,Y}D - {1,2}C {1,2,Y}D {1,2,Y}D . {1}B {1} B {1} B {1} B（10分）将下图的NFA 确定化为DFA 。
（2011年重修卷A 出过）X 12baY abaABCba Da ba bABa b答：用子集法确定化如下表用子集法对所给图的确定化I Ia Ib状态{X,1,2} {1,2}.. {1,2,3} {1,2,Y}{1,2}..{1,2}..{1,2,Y}{1,2}..{1,2,3}{1,2,3}{1,2,3}{1,2,3}X123确定化后如下图第五章重点：1.LL(1)的判别要点：（1）计算First\Follow\Select集，然后判断是否是LL(1)文法。
（2）如果是LL(1)文法，则构造预测分析表。
（消除左递归和左公共因子也要了解）例：（10分）已给文法G[S] ：S → PS'S' → aP S'| fS' |εP → qP'P' → bP |ε（1）该文法是否是LL（1）文法，并说明理由。
（2）给出该文法的预测分析表。
答：（10 分）（1）Select（S → PS'）=first(P)={q}Select(S’→ aPS')={a}Select(S’→ fS')={f}Select(S' →ε)=follow(S’)=follow(S)={#}Select(P→ qP')={q}Select(P' → bP)={b}Select（P' →ε）=follow(P’)=follow(P)={first(S’)-{ ε}}⋃follow(S)={a,f}⋃{#}={a,f,#}Select(S’→ aPS')⋂ Select(S’→ fS') ⋂ Select(S' →ε)=∅Select(P' → bP) ⋂ Select（P' →ε）=∅所以文法是LL（1）文法。
（7分）（2a b f q #S PS’S’aPS’fS’εP qP’(15分)LL （1）分析表，并说明它是否为LL（1）文法。
（2011年重修卷A出过）S →aA|BAA→cB|εB →bB|ε各候选式的FIRST集(4分)FIRST（aA）={a} FIRST（BA）={ b，c，ε } FIRST（cB）={c}FIRST（ε）={ε} FIRST（bB）={ b } FIRST（ε）={ε}各非终结符的FOLLOW集(4分)FOLLOW(S)= {#} FOLLOW(A)= {#} FOLLOW(B)= { c，#}LL（1）分析表(5分)a b c #S S →aA S →BA S →BA S →BAA A→cB A →εB B →bB B →ε B →ε说明它是否为LL（1）文法(2分) 判断1分，理由1分因为LL（1）分析表无冲突，所以该文法是LL（1）文法。
2. 设文法G(S):S→^ | a | (T)T→T,S | S⑴消除左递归；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表解：(1)消除左递，文法变为G’[S]：S→^ | a | (T)'T→ST’ | ST’→,ST’ |ε此文法无左公共左因子。
(2)构造相应的FIRST和FOLLOW集合：FIRST(S)={a, ^, (}，FOLLOW(S)={#, ,, )}FIRST(T)={a, ^, (} ，FOLLOW(T)={}}FIRST(T’)={,, ε} ，FOLLOW(F)={)}(3)第七章重点：1. 识别活前缀的有限自动机的构造，判断某个文法是否是LR(0)文法，或SLR （1）文法或LR（1）文法，若不是，请说明理由，若是，构造相应的LR分析表。
2. 查LR分析表，进行句子的识别。
典型例题：文法G[S]及其LR分析表如下，请给出串baba#的LR分析过程。
(1) S → DbB(2) D → d(3) D → ε(4) B → a(5) B → Bba(6) B → ε(注：答案格式为步骤状态栈符号栈输入串ACTION GOTO)答案：步骤状态符号输入串 ACTION GOTO0 0 # baba# r3 21 02 #D baba# S42 024 #Db aba# S53 0245 #Dba ba# r4 64 0246 #DbB ba# S75 02467 #DbBb a# S86 024678 #DbBba # r5 67 0246 #DbB # r1 18 01 #S # acc2. （8分）已知拓广文法G[S’]：S’→S S→AS∣εA→aA∣b （1）试构造以LR（1）项目集为状态的识别活前缀的有穷自动机；（2）试判断文法是否是LR(1)文法，并说明理由。
( 1 ) I0: I2: I6:（2）有穷自动机所有的状态都不含有“移进－归约”、“归约－归约”冲突，因而该文法是LR(1)文法。
练习：. (20 分 ) 给定文法 G[S] ： S → SaA|a A → AbS|b⑴ (8 分 ) 请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。
⑵ (4 分 ) 请构造该文法的 LR(0) 分析表。
⑶ (4 分 ) 什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷ (4 分 ) 什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 答：⑴拓广文法 1 分 G[S ′ ]: S ′→ S ⑴ S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸该文法的以LR(0) 项目集为状态的识别规范句型活前缀的DFA ：⑵该文法的LR(0) 分析表：状态ACTION GOTOa b # S A0 S 2 11 S 3 acc2 r3 r 3 r 33 S 5 44 r 2 r 2 /S 6 r 25 r 5 r 5 r 56 S 2 77 r 4 /S 3 r 4 r 4⑶ LR(0) 文法：该文法的以LR(0) 项目集为状态的识别规范句型活前缀的DFA 中没有冲突状态。