第4章+自顶向下语法分析方法PPT.ppt

自顶向下语法分析方法;4.1 确定的自顶向下分析思想;例4.1设文法G1[S]：S ? pA | qBA ? cAd | aB ? dB | b考虑对输入串w=pccadd的分析。;这个文法有以下两个特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 ;例4.2设文法G2[S]：S ? ApS ? BqA ? aA ? cAB ? bB ? db考虑对输入串w= ccap的分析。 ;例4.3设文法G[S]：S?aAS?dA?bASA??考虑对输入串w= abd的分析。 ;结论 当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交则仍可构造确定的自顶向下分析。;定义4.2设G=(VT,VN,P,S)是上下文无关文法, 对A∈VN定义FOLLOW(A)={a?S ?A? 且a∈VT ，a∈FRIST(?)，?∈V*，?∈V+ }若S uA?，且? ε，则规定#∈FOLLOW(A)如： FOLLOW(A)=FIRST(S) ?{#}={a,d,#} ;定义4.3给定上下文无关文法的产生式A??， A?VN，? ?V*, 若? ?，则SELECT(A?? ) = FIRST(?)若如果? ?，则SELECT(A?? ) = (FIRST(?)-{?})?FOLLOW(A) ;定义4.4一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式，A??， A??，满足SELECT(A??) ? SELECT(A? ?) = ?其中?、?不能同时 ?。 ;LL(1)文法的含义 第1个“L”指的是由左向右地处理输入。 第2个“L”指的是它为输入串描绘出一个最左推导。 括号中的数字1意味着它只需向右看1个符号便可决定如何推导即选择哪个产生式（规则）进行推导。 ;4.2 LL(1)文法的判别;例：设文法G[S] 为:S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c判断它是否是LL(1)文法。 ;1.求出能推出ε的非终结符;2.计算FIRST集;用关系图法求文法符号的FIRST集(自学);3.计算FOLLOW集;用关系图法求非终结符的FOLLOW集(自学) ;4.计算SELECT集;5. 判别是否是LL(1)文法;4.3 某些非LL(1)文法到LL(1)文法的等价变换;1. 提取左公共因子;A→αβ1|αβ2|…|αβn 变换为 A→α(β1|β2|…|βn) ，即 A→αA A → β1|β2|…|βn ;例4.7文法G2[A]:A→adA→BcB→aAB→bB;例4.8文法G3[S] :S→aSdS→AcA→aSA→b ;例4.9文法G4[S] :S→Ap|BqA→aAp|dB→aBq|e;结论 不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。 一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。;2. 消除左递归;例4.10G5[S]:S→SaS→b考虑对输入串baaaa#的分析 例4.11G6[A]：A→aBA→BbB→AcB→d考虑对输入串adbcbcbc#的分析;消除直接左递归;消除间接左递归;消除文法中一切左递归的算法;例;4.5 LL(1)分析的实现;4.5.2表驱动LL(1)分析程序;预测分析表;例文法G[E]：E →TE’E’ →+TE’| εT →FT’T’ →*FT’| εF → i | ( E )构造过程： 1.判断文法是否为LL(1)文法 2.构造预测分析表;预测分析程序算法;分析栈 #E #ET #ETF #ETi #ET #E #ET+ #ET #ETF #ETi #ET #ETF* #ETF #ETi #ET #E #;4.5.1递归下降LL(1)分析程序（自学）