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

自顶向下分析方法的特点 若G有左递归,则分析不能正常进行因此,自顶向下分 析必须先消除文法的左递归 2.分析过程是反复进行试探的过程因此难免会出现大 量的回溯特别是当形红LO时,只有在穷举完所有的 试探后才能拒绝ν 由于回溯就需将从出错点到迄今为止已做过的大量 工作废弃,显然会大大降低分析的效率特别是在语法 分析阶段还往往要进行同步的语义分析和处理这些 工作也就白做了因此消除回溯是自顶向下分析的另 目标 3.当拒绝w时,只能知道v不是句子不知出错的性质及 位置

6 自顶向下分析方法的特点 1. 若G有左递归,则分析不能正常进行.因此,自顶向下分 析必须先消除文法的左递归; 2. 分析过程是反复进行试探的过程,因此,难免会出现大 量的回溯.特别是当wL(G)时,只有在穷举完所有的 试探后才能拒绝w. 由于回溯,就需将从出错点到迄今为止已做过的大量 工作废弃,显然会大大降低分析的效率.特别是在语法 分析阶段还往往要进行同步的语义分析和处理,这些 工作也就白做了.因此,消除回溯是自顶向下分析的另 一目标. 3. 当拒绝w时,只能知道w不是句子,不知出错的性质及 位置

4.1.1消除文法的左递归 设文法是已简化的若文法含直接左递归式 A→Aa|B(a∈V+),β不以A打头,则类似正规 式求解方法有A→β{a}(βx*,{a表示中{}的符号 串α可以出现0次或多次。 引入新的非终结符A,令其产生α则有: A→βA;A→aA'E消除直接左递归 对文法:E→TEAT;T→FTMF;F→(E)i;A→+; M→>*|/ 可改写为:E→TE’;E→ATE'e;T→FT T”→MFTE:F>(E);A→+:M

7 4.1.1 消除文法的左递归 设文法是已简化的.若文法含直接左递归式: A→A |  (V+) , 不以A打头，则类似正规 式求解方法,有A→ {} (*). {} 表示中{ }的符号 串可以出现0次或多次。 引入新的非终结符A’,令其产生* ,则有: A→ A’；A’→ A’| 消除直接左递归. 对文法：E→T|EAT; T→F|TMF; F→(E)|i; A→+|-; M→* | / 可改写为：E→TE’；E’→ATE’|；T→FT’ T’→MFT’|；F→(E)|i；A→+|-；M→ *|/

消除文法的左递归 一般地设文法中全部A产生式为 A→Aa|Aa-.1Aanlβ1…JBm,其中,β不以A打头, 则消除直接左递归后的产生式为 A→>B1A-.|BmA;A→A'…,anA’e 消除文法的间接左递归: 将原文法进行代入变换后,再应用上述方法 例如,S→Abc;A→Sa,可将其变换为S→Sabc,再 使用上述方法得S→cS;S→abS|e 消除过程:找出具有左递归(包括间接左递归)的所 有非终结符,对相关的产生式进行代入变换,逐步转 变为直接左递归的产生式,最后统一进行消除

8 消除文法的左递归 一般地,设文法中全部A-产生式为 A→A1|A2|…|An| 1|…| m,其中, i不以A打头, 则消除直接左递归后的产生式为 A→1A’|…| mA’；A’→ 1A’|…| nA’|  消除文法的间接左递归： – 将原文法进行代入变换后，再应用上述方法 – 例如, S → Ab|c；A→Sa,可将其变换为S →Sab|c,再 使用上述方法,得S →cS’；S’ →abS’ |  消除过程：找出具有左递归（包括间接左递归）的所 有非终结符，对相关的产生式进行代入变换，逐步转 变为直接左递归的产生式，最后统一进行消除

消除文法左递归的矩阵方法 设文法的非终结符为X,X2,…,Xn,其中,的产生式 可分为以非终结符和终结符打头的两类类似正规式 方法将“改写为‘+’,有 XiX1O1H+x202+…+Xn+pi 其中,β是以终结符打头的产生式之和,aki(a∈V+) 可以为φ,这样,文法G可表示为 1112 (x12X2…;Xn)=(X12X2…Xn +(β12,…Bn) C, d 或写成向量和矩阵形式:X=XA+B

9 消除文法左递归的矩阵方法 设文法的非终结符为 X1, X2, …, Xn, 其中,Xi的产生式 可分为以非终结符和终结符打头的两类.类似正规式 方法,将‘|’改写为‘+’ ,有 Xi=X11i+X22i+…+Xnni+i 其中, i 是以终结符打头的产生式之和, ki (kiV+) 可以为 ，这样,文法G可表示为 ( , , , ) ( , , , ) ( , , , ) 1 2 1 2 2 1 2 2 2 1 1 1 2 1 1 2 1 2 n n n n n n n X X Xn X X Xn +                         =         或写成向量和矩阵形式: X=XA+B

矩阵求解 该方程有解:X=BA*。而 A*=I+A+A2+A3+ I+AA> 其中,I 则有:X=BZ;Z=IHAZ 其中X的产生式以终结符打头,因此无直接左递归和 间接左递归;而Z的产生式以ak∈V+打头,因此不含直 接左递归,又因B以终结符打头,也不含间接左递归 由此所得的文法含有无用符号和无用产生式需化简

10 矩阵求解 该方程有解: X=BA*。而 则有: X=BZ; Z=I+AZ 其中X的产生式以终结符打头，因此无直接左递归和 间接左递归；而Z的产生式以kiV+打头,因此不含直 接左递归，又因B以终结符打头， 也不含间接左递归. 由此所得的文法含有无用符号和无用产生式,需化简           = =           = = + + + + = + n n n n Z Z Z Z I A Z A I A A A I AA        1 1 1 1 2 3 , , * * * 其中 令    