例:消去下列文法的左递归: s→AabA→ Ac Sda 解:设A1=SA2=A则 s→AabA→Ac(Aab)dle s→AabA→A(clad)|bde s→AabA→ baJA A→ caldAra 2.回溯性 在自顶向下的语法分析中,当前面临非终结符P如存在规则 P→α1|a2la3…|an,当前输入符号为a时,究竟选用哪一个候选式 如采用回溯则效率太低,现如能改变文法使每个候选式没有相 同的“头符号”,则就能根据当前输入符号a决定选用那一个 产生式
例：消去下列文法的左递归： S→Aa|b A→Ac|Sd|ε 解：设A1=S A2=A 则 S→Aa|b A→Ac|（ Aa|b）d|ε S→Aa|b A→A（c|ad）|bd|ε S→Aa|b A→bdA’|A’ A’→cA’|adA’|ε 2.回溯性 在自顶向下的语法分析中，当前面临非终结符P如存在规则 P→α1 |α2 |α3 |···|αn，当前输入符号为a时,究竟选用哪一个候选式， 如采用回溯则效率太低，现如能改变文法使每个候选式没有相 同的“头符号”，则就能根据当前输入符号a决定选用那一个 产生式
F51: Sif E then Sif E then S else Sb 改写成: Sif E then S sb S’- else s|e 般地 A→>β16β2163…|6βnY 改写成 A→>6AN A→112|13…| 例:消去文法G[S] s→aBCB→ibbC→ DEFGC D-→> d eeh F→deG→t 的回溯性 解:S→aBCB-ib|bC→ dCc C’→eE'EhGG→t
例：S→if E then S|if E then S else S|b 改写成： S→if E then S S’|b S’→else S|ε 一般地 A→δβ1 |δβ2 |δβ3 |···|δβn |γ 改写成： A→δA’|γ A’→β1 |β2 |β3 |···|βn 例：消去文法G[S]: S→aBC B→ib|b C→DE|FG|c D→d E→eh F→de G→t 的回溯性 解：S→aBC B→ib|b C→dC’|c C’→eE’ E’→h|G G→t
例:若有文法G[S]: s→aSds→AcA→→asAb 解:S→asdS→ aSc sbc s→ass's→bcS-dc 但要注意不是所有的文法都能通过提左公因子消去回溯性的 例:若有文法G[S]: s→ ApBq A→ aApd B-→ aBle 解:上述文法的语言: LIG]andon+1EXameqm+1m, n201 由于不知道具体句子中m和n那一个大,也就无法知道应提多少 个a作为左因子
例：若有文法G[S]： S→aSd S→Ac A→aS A→b 解：S→aSd S→aSc S→bc S→aSS’ S→bc S’→d|c 但要注意不是所有的文法都能通过提左公因子消去回溯性的。 例：若有文法G[S]： S→Ap|Bq A→aAp|d B→aBq|e 解：上述文法的语言： L[G]={andpn+1或a meqm+1|m,n≥0} 由于不知道具体句子中m和n那一个大，也就无法知道应提多少 个a作为左因子
递归下降分析法 递归下降分析法又称递归子程序法简称递归下降法,它是 种无回溯的自顶向下分析技术,它的实现思想是让一个识别 程床胄组过(或数)组成某中每盒棍对富在交绩的 归的,相应的程序称为递归下识别程序。 例:对于文法G[E] E→E+TT→T*F→(E) 消去左递归和提左共因子后: E→忙E汁+T→F节节→*TεF→(E 其递归子程序的流程图为:
递归下降分析法 递归下降分析法又称递归子程序法简称递归下降法，它是 一种无回溯的自顶向下分析技术，它的实现思想是让一个识别 程序由一组过程（或函数）组成，其中每个过程对应于文法的 一个非终结符号，由于文法的递归定义，故这些过程 往往是递 归的，相应的程序称为递归下识别程序。 例：对于文法G[E]： E→E+T|T T→T*F F→（E）|i 消去左递归和提左共因子后： E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i 其递归子程序的流程图为：
①-[T-[E-○ 个T-[Ex○ 否个号 ①-[F-[r:-○ ①<[F-[T 否个符号 政下一 个符号 是 E 否 政下 否 个碎号