北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（PPT课件讲稿）第四章 语法分析和语法分析程序（4.1）自顶向下的语法分析

消除文法左递归的例子 例41S→>Sa|Aba;A→>Sc 相应的矩阵为 a C (S,A)=(S,A2+(a19) 展开矩阵,得 S=aZu: A=aZ1 令Z Zu=aZu ca1 +E Zu2= a12 c2 (S,A)=(a,d) 721 bZ a C 722 bZ12te 12 21222

11 消除文法左递归的例子 例4.1 S→Sa|Ab|a；A→Sc 相应的矩阵为                  +            =                =          =          = +           = 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 * ( , ) ( , ) , ( , ) ( , ) ( , ) Z Z Z Z b a c Z Z Z Z Z Z Z Z S A a Z Z Z Z b a c Z a b a c S A S A 令 则 展开矩阵,得 S =aZ11；A=aZ12 Z11=aZ11 + cZ21 +  Z12 = aZ12 + cZ22 Z21 = bZ11 Z22 = bZ12 + 

消除文法左递归的例子(续) 写成产生式,有 s→→aZA→aZ12 Zn→) aZu cz] E Z12→> aZ1 cZ22 za→bZmz→8|bZ 文法中含有无用产生式消除之最后有 S→>aZnZ-→> aZu czar8 Z21→)bZ1 将A→>Sc代入S→>Sa|Aba可得:S→>Sa|Scba 消除直接作递归,有S→aS'S→ ascs|E更简 单

12 消除文法左递归的例子（续） 写成产生式，有 S →aZ11 A →aZ12 Z11→aZ11 |cZ21| Z12→ aZ12 |cZ22 Z21 → bZ11 Z22 →  | bZ12 文法中含有无用产生式,消除之.最后,有 S →aZ11 Z11→aZ11 |cZ21| Z21 →bZ11 将 A→Sc 代入S→Sa|Ab|a可得：S→Sa|Scb|a 消除直接作递归，有S→aS’ S’ → aS’|cbS’|  更简 单

4.12回溯的消除及LL(1)文法 设G=(v,VrPS)为一CFG,w=a1a2.a是V上的符号 串现需判明w是否是LG中的句子为此,从S开始进 行最左推导设经若干步推导后我们得到 S→W1ABA∈B∈(4.17) 且 W1=a1··a i-1 i≤n 由假设可知,到目前为止,w的前缀w已匹配现在需对 Aβ进行推导,以匹配w的剩余部分aa1,an

13 4.1.2 回溯的消除及LL(1)文法 设G=(VN,VT,P,S) 为一CFG, w=a1a2…an是VT上的符号 串,现需判明w是否是L(G)中的句子.为此,从S开始进 行最左推导.设经若干步推导后我们得到 w a a a i n S w A A V V i N =      − ,1 (4.17) 1 1 2 1 * 1 * 且    由假设可知,到目前为止,w的前缀w1已匹配,现在需对 A进行推导，以匹配w的剩余部分aiai+1…an