第04章语法-自顶向下合编.ppt

* 1－2）消除间接左递归 1.把G的非终结符整理成某种顺序A1，A2，……An 2. For i:=1 to n do { for j :=1 to i-1 do 把每个形如Ai∷=Ajr的规则用Aj的右部带入替换成 　 Ai ∷=(δ1|δ2|……δk)r 　其中Aj ∷=δ1|δ2|……δk是当前全部Aj 的规则 消除Ai规则中的直接左递归 } 3.去掉无用的产生式 * 2）解决局部二义性问题 对于局部二义性问题，即右部多个侯选式的第一个符号相同时，可通过提取公因子、加入新的非终结符号来实现。 假设文法中有规则为：U::=xV|xW ，解决办法如下： 1)???提取公因子，将规则变成：U::=x(V|W) 2）加入一个新的非终结符号A，令A=V|W，则将规则改为： U::=xA ，A::=V|W * 3）右部侯选式的第一个符号是非终结符号 对于这种问题，我们首先要求出每个侯选式的首符号集，然后根据各侯选式的首符号集内容来选择侯选式。 设文法G是没有左递归的文法，规则形式为： U∷=α|β 首先，求出每个侯选式的首符号集，即FIRST(α)、FIRST(β)，且FIRST(α)∩FIRST(β)=φ。 若ε∈FIRST(β)，那么，FIRST(α)∩FOLLOW(U)=φ * 求出首符号集后，并保证满足上述的不相交条件，那么，对于规则U∷=α|β，就可以根据下列规则来选择侯选式： 设当前的输入符号是a ，a∈Vt 若a∈FIRST(α) 或ε∈FIRST(α)且a∈FOLLOW(U)，则用α侯选式。 若a∈FIRST(β) 或ε∈FIRST(β)且a∈FOLLOW(U)，则用β侯选式。 若a∈FIRST(α) 且a∈FIRST(β) ，则语法错，转出错处理。 * 4.3.2 递归下降分析中存在的问题及解决方法 要实现没有回溯的自顶向下分析，文法必须满足两个条件： 文法是非左递归的。 对文法的任一非终结符号，若其规则右部有多项选择，那么各选项所推出的终结符号串的头符号集合要两两不相交。 * 例4.6，有文法G[Z]： Z::=AcB|Bd A::=AaB|c B::=aA|a 设计递归下降分析程序。 解:首先将左递归去掉， 将规则 A::=AaB|c 改成 A::=c{aB} 提取公因子， 将规则 B ::= aA|a 改成 B ::= a(A|ε) 改后的文法为： Z ::= AcB|Bd , A ::= c{aB} , B ::= a(A|ε) 对于规则Z ::= AcB|Bd，要求出每个选项的头符号集， 即FIRST(AcB)={c}，FIRST(Bd)={a}，分析程序如图所示。 * INPUTSYM=‘c’ A INPUTSYM=‘c’ INPUTSYM=下一个符号 INPUTSYM=‘d’ ERR INPUTSYM=‘a’ ERR INPUTSYM=下一个符号 z 出口 B B N Y Y Y Y N N N * 对于规则A ::= c{aB},分析程序如图4.3(b)所示。 对于规则B ::= a(A|ε),FIRST(A)={c}，分析程序如图4.3(c)所示。 INPUTSYM=‘c’ INPUTSYM=‘a’ INPUTSYM=下一个符号 ERR INPUTSYM=下一个符号 A 出口 B Y Y N N INPUTSYM=‘a’ INPUTSYM=‘c’ ERR INPUTSYM=下一个符号 B 出口 A Y Y N N 图4.3(c)B分析程序 图4.3(b)A分析程序 * 4.4 LL(1)分析方法 基本思想： 自左向右扫描分析输入符号串 从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式 预测分析法 第一个L表示自左向右顺序扫描输入符号串; 第二个L表示分析过程产生一个句子的最左推导 * 4.4.1 LL(1)分析的基本方法 LL(1)分析器由一个总控程序、一张分析表和一个分析栈组成 输入符号串： 分析栈 # an … … … … a2 a1 # S Z X LL（1） 总控程序 分析表 输出流 根据栈顶符号X和当前输入符号a来决定分析器的动作 * 输入符号串:指要分析的输入符号串。 为了分析算法