编泽原理 语法分折-自上而下分析 消除左递归方法： (2)消除直接左递归 P-Pa Pa2l...Paml Bl B21...Bn 消除P的左递归 P→BP'|BP.|BP P'-a P'a2 P...am P' (3)化简改写后的文法，即去除那些从开始符号出发却永远 无法到达的非终结符的产生规则。 最终得到无左递归的文法。 第6列
编译原理 第16页 语法分析-自上而下分析 消除左递归方法： （2）消除直接左递归 P→Pα1|Pα2|...|Pα m|β1| β2|...| βn 消除P的左递归 P→ β1P'| β2P'|...| βnP' P'→ α1 P'| α2 P'|...|α m P'| ε （3）化简改写后的文法，即去除那些从开始符号出发却永远 无法到达的非终结符的产生规则。 最终得到无左递归的文法
编译原理 语法分析-自上而下分析 消除回溯（方法：提取左公共因子） A→δBlδB2l8BnlδY1Y2lWm(每个Y不以8开头) 改写为 A→δA'lYlY2l.Ym A'→β1lβ2l.16E 第7觉
编译原理 第17页 语法分析-自上而下分析 消除回溯（方法：提取左公共因子） A → δβ1 |δβ2 |...|δβn |δ|γ1 | γ2 |..|γm (每个γ不以δ开头) 改写为 A → δ A' |γ1 | γ2 |..|γm A' →β1 |β2 |...|βn |ε
编泽原理 语法分折-自上而下分析 LL（1)分析条件 首符集 令G是一个不含左递归的文法，对G的所有非终结 符的每个候选a定义它的终结首符集FIRST(α)为： FIRST(a)={aa>…,a∈VT} 若a>,则e∈FIRST(a) 也即，FRST(a)是a的所有可能推导的开头终结符或 可能的E。 第8列
编译原理 第18页 语法分析-自上而下分析 首符集 令G是一个不含左递归的文法，对G的所有非终结 符的每个候选α定义它的终结首符集FIRST(α)为： FIRST(α)={a| α a...,a∈VT } 若α ε,则ε ∈ FIRST(α) 也即, FIRST(α)是α的所有可能推导的开头终结符或 可能的ε。 LL（1）分析条件
编译原理 语法分析-自上而下分析 如果非终结符A的所有候选首符集两两不相交，即 A的任何两个不同候选a和a,有 FTRST(a)∩FIRST(a)=Φ 那么，当要求A匹配输入串时，A就能根据它所面 临的第一个输入符号a,准确地指派某一个候选前 去执行任务。这个候选就是那个终结首符集含a的a。 第19页
编译原理 第19页 语法分析-自上而下分析 如果非终结符A的所有候选首符集两两不相交，即 A的任何两个不同候选αi和αj，有 FTRST(αi）∩FIRST(αj）=Φ 那么，当要求A匹配输入串时，A就能根据它所面 临的第一个输入符号a，准确地指派某一个候选前 去执行任务。这个候选就是那个终结首符集含a的α