编译原理 第05章课件.pptVIP

第五章 自顶向下语法分析方法;学习目标 ;学习指南 ;难重点 ;难重点 ;知识结构 ;5.1 确定的自顶向下语法分析思想 5.2 LL（1）文法的判别 5.3 某些非LL（1）文法到LL（1）文法的等价变换 5.4 不确定的自顶向下语法分析思想 5.5 确定的自顶向下语法分析思想;本章内容 ;5.1 确定的自顶向下分析思想;例 5.1 若有文法G1[S]: S → pA |qB　A →cAd|a　B →d B |c识别输入串w= pccadd是否是G1[S]的句子　试探推导过程：　S? pA ? pcAd ? pccAdd ? pccadd试探成功。　　相应语法树为图5.1。 图 5.1 确定的自顶向下语 法分析树(一);例 5.1 文法有以下两个特点： ;例 5.2?　若有文法G2[S]:　　S → Ap |Bq　　A →a|cA 　　B →b|dB　　识别输入串w=ccap是否是G2[S]的句子，那么试探推出输入串的推导过程为 ：　　S ? Ap ? cAp ? ccAp ? ccap　　试探推导成功。　　;例5.2 文法的特点是：;FIRST集;例1：设有文法G[S] ： S→AB|bC A→ε|b B→ε|aD C→AD|b D→aS|c 解：可产生空串的非终结符：A、B、S FIRST(S)=={b,a,ε} FIRST(A)={ε,b} FIRST(B)={ε,a} FIRST(C)={a,b,c} FIRST(D)={a,c};例 5.3?若有文法G3[S]:　　S → aA|d　　A →bAS|ε　　识别输入串w=abd是否是G3[S]的句子　　试探推导出abd的推导过程为：　　S ? aA ? abAS ? abS ? abd　　试探推导成功。 　　 相应语法树为下图 ;例5.3 文法的特点是：;FOLLOW集;SELECT集;LL(1) 文法的通俗定义;说明;LL(1)文法;本章内容 ;内容;例子分析;FIRST集;求解FIRST集的算法 对每个文法符号X，计算FIRST(X)过程如下： ① 若X∈VT ，则FIRST(X)={X}； ② 若X∈VN ，且有产生式X?a… ，a∈VT，则把a加入到FIRST(X)中； ③ 若X∈VN ，X??也是一条产生式，则把?也加到FIRST(X)中； ④ 若X∈VN ，有产生式X?Y1Y2…Yn ，Y1,…Yi都是非终结符，对于任何j(1≤j≤i-1)， FIRST(Yj)都含有ε，则把FIRST(Yj)中的所有非ε元素都加到FIRST(X)中；FIRST(Yi)的元素加入到FIRST(X) 特别地，若FIRST(Yj , j=1,2,…,n)均含有? ，则把? , FIRST(Yj)中的所有非ε元素都加到FRIST(X)中； ⑤ 反复使用①-④，直到FIRST(X)不再增大为止。 ???他求解方法：关系图法、矩阵法。;例1：设有文法G[S] ： S→AB|bC A→ε|b B→ε|aD C→AD|b D→aS|c 解：可产生空串的非终结符：A、B、S FIRST(S)={FIRST(A)-{ε}}∪{FIRST(B)-{ε}}∪{ε} ∪{b}={b,a,ε} FIRST(A)={ε} ∪{b}={ε,b} FIRST(B)={ε} ∪{a}={ε,a} FIRST(C)={FIRST(A)-{ε}}∪FIRST(D)={a,b,c} FIRST(D)={a} ∪{c}={a,c};例2：设有文法G[E] ： E→TE‘ E→+TE’|ε T→FT T→*FT’|ε F→(E)|id FIRST(F)={（,id} FIRST(T)=FIRST(F)={（, *, id} FIRST(E)=FIRST(T)={（,id} FIRST(E)={+，ε} FIRST(T)={*,ε} FIRST(+)={+}, FIRST(*)={*} FIRST(（)={（} FIRST(）)={）} FIRST(id)={id};例2：设有文法G[S] ： S→AB|bC A→ε|b B→ε|aD C→AD|b D→aS|c 解：可产生空串的非终结符：A、B、S FIRST(AB) ={FIRST(A)-{ε}}∪{FIRST(B)-{ε}}∪{ε}={b,a,ε} FIRST(bC)={b} FIRST(ε)={ε} FIRST(AD)={FIRST(A)-{ε}}∪FIRST(D)={b,a,c