编译原理复习重点详解.doc

编译原理复习重点 1. 闭包概念 用 S* 表示S上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。 S上的除ε外的所有符号串组成的集合记为S+ 。 Σ+称为Σ的正闭包。 2. 文法概念 文法G[S]=（ VN ， VT， P ，S） VT ：终极符集合，即不可再分的基本符号集合； VN：非终极符集合，表示语法成分； S：开始符，是语言定义的目标； P：规则式集合。 3. 句子句型推导 句型：若由S广义推导出x，则称x是文法的一个句型 句子：若x是终极符号串，则称x是文法的一个句子 例： 文法G[E] E → E + T| T T → T * F|F F → ( E )|a 句子a+a*a的最左推导: ETE+T TT+T TF+T Ta+T Ta+T*F Ta+F*F Ta+a*F Ta+a*a句子：用符号a，+，*，(和)构成的算术表达式 (T+a)*a+F是一个句型； （a+a）*a是一个句子。 句子a+a*a的最右推导: ETE+T TE+T*F TE+T*a TE+F*a TE+a*a TT+a*a TF+a*a Ta+a*a 4. 正规文法构造 1)已知字母表?1={a}，L1[G]={a2n|n=1},构造G1； S→ Saa | aaS | aSa 2)已知字母表?2={a,b}，L2[G]={abna|n=1},构造G2； S→aBa B→b | bB | Bb 3)已知字母表?3={0,1}，L3[G]={0n1n|n=1},构造G3； S→0S1 | 01 4)已知字母表?4={a,b,c}，L4[G]={aibjck | i,j,k=1},构造G4； S→ABC A→a | aA | Aa B→b | bB | Bb C→c | cC | Cc 5. 语法树和推导 例: G[S]: S→aAS A→SbA A→SS S→a A→ba 最左推导：STaASTaSbASTaabASTaabbaSTaabbaa 最右推导：STaASTaAaTaSbAaTaSbbaaTaabbaa 若一个句子对应两棵结构不同的语法树，则该句子具有二义性。 6. 单词类型 （1）关键字（2）标识符（3）常数（4）运算符（5）界符 7. 构造状态转化图 （左线性正规文法G【Z】-进，右线性正规文法G【S】-出） 右线性： 1.以每个非终结符为状态结点，开始符号对应初态S ； 2.增设一个终态 Z； 3.对于规则 A→aB，画从状态 A 到 B 的弧，标为 a； 4.对于规则 A→a，画从状态 A 到终态 Z 的弧，标为 a。 左线性。。。 例： G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b 8. 非有限自动机——有限自动机（状态转换矩阵） DFA定义： 一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中 1.K是一个有穷集，它的每个元素称为一个状态； 2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表； 3.f是转换函数，是在K×Σ→K上的映 4.S∈K是唯一的一个初态； 5.ZìK是一个终态集，终态也称可接受状态或结束状态。 例： DFA M=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为： f（S，a）=U f（V，a）=U f（S，b）=V f（V，b）=Q f（U，a）=Q f（Q，a）=Q f（U，b）=V f（Q，b）=Q 矩阵表示： 由NFA构造DFA： 令DFA的初态是NFA的全部初态，即S=[S1 ’,S2 ’,……Sn ’] 设DFA的状态Q=[Q1’,Q2’…….Qk’] 令δ（ Q，a）=[δ’(Qi’ ,a)i=1,2,3………k] 重复，直到无新状态出现。 若DFA状态Q中包含NFA终态，则Q是DFA的终态。 例： 9. 自顶向下的语法分析——LL(1)文法 定义：（也用于判别） 对于 G 的每个非终结符 A 的任何两个不同的候选式 A→α|β 1)文法不含左递归 2) FIRST(α)∩FIRST(β)=φ 3) 如果βT*ε，则 FISRT(α)∩FOLLOW(A)=φ ——文法Ｇ是 LL(1) 的充要条件 性质： LL(1)文法是无二义的 LL(1)文法不含左递归 LL(1)文法不含公共左因子 10. 求First（）集，Follow（）集 首终结符集First（a）定义和计算：（书p82）（书p83例4.6） FIRST（a）={a|a =* ab,a∈VT, a, b∈V*} 若a=* ε则规定ε∈FRIST(a) 后随符号集