西北工业大学：《编译原理》课程教学资源（PPT课件）第4章 语法分析和语法分析程序（4.1）自顶向下的语法分析

第四章语法分析和语法分析程序 ·对象：单词流形式的源程序 ·任务：根据语法规则，分析源程序的语法结构， 同时进行语法检查 ·输出：语法树 假定：先不考虑语义问题 ·常见分析方法：自顶向下()和自底向上（个） ·↓：递归下降法，预测分析法(LL分析法) ·个：优先分析法，LR分析法

第四章 语法分析和语法分析程序 • 对象：单词流形式的源程序 • 任务：根据语法规则，分析源程序的语法结构， 同时进行语法检查 • 输出：语法树 • 假定：先不考虑语义问题 • 常见分析方法：自顶向下()和自底向上() • :递归下降法,预测分析法(LL分析法) • :优先分析法,LR分析法

4.1自顶向下的语法分析 ·↓：对已给的输入串w,试图自 例：E→TIEAT 上而下地建立一棵语法树；或 T-→FITMF F→(E)iA-→+- 者说，从S出发，为w构造一个 M->*|1(4.1) 最左推导若成功，则w∈L(G), 。 设w=j+i*i,每个产生式从左 否则拒绝. 至右试验.从E出发： 一般说来，在为W寻求最左推 导的每一步，都涉及使用何产 E→T→F→(E) 生式进行替换的问题.最简单 →i 的方法是，逐一试探！ →TMF→FMF→(E)MF 遗憾的是，逐一试探也不能完 →iMF→i*F 全解决问题.例如，在含有左 →i/F 递归的文法中，就会出现不能 →TMFMF→.. 终止的替换现象. →TMFMFMF

4.1 自顶向下的语法分析 • :对已给的输入串w,试图自 上而下地建立一棵语法树;或 者说,从S出发,为w构造一个 最左推导.若成功,则wL(G), 否则拒绝. • 一般说来,在为w寻求最左推 导的每一步,都涉及使用何产 生式进行替换的问题.最简单 的方法是,逐一试探. • 遗憾的是,逐一试探也不能完 全解决问题.例如,在含有左 递归的文法中,就会出现不能 终止的替换现象. • 例:E→T|EAT T→F|TMF F→(E)|i A→+|- M→* | / (4.1) • 设w=i+i*i,每个产生式从左 至右试验.从E出发: ETF(E) i TMFFMF(E)MF iMF i*F i/F TMFMF … TMFMFMF

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

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

4.1.1消除文法的左递归 设文法是已简化的若文法含直 一般地，设文法中全部A-产 接左递归式： A-→Aa|B 生式为 (a∈V+),则类似正规式求解 A→Ac1Ao2.JAanl 方法，我们有A→B{o}(Ba*). 引入新的非终结符A',令其产生 BBm,其中，β不以A打 ou*,则有： 头，则消除直接左递归后的 产生式为A-→BA引.|BmA A→BA' A'→aAlE 由于 及A→C1A||CnA B不以A打头，A非左递归. 对P105的文法(4.1)，可改写为 上述方法可消除直接去递 归，但对于间接左递归的文 E→TE'E'→ATEl8T→FT T'-→MFT'8 F→(E) 法来说，需将原文法进行变 A→+ M-→*W 换后才适用.例如，S→ Ablc A→Sa,可将其变换为 S→Sablc,再使用上述方 法，得 S→cS S'-→abS

4.1.1 消除文法的左递归 • 设文法是已简化的.若文法含直 接左递归式: A→A |  (V+) , 则类似正规式求解 方法,我们有A→  {} ( *). • 引入新的非终结符A’,令其产生 * ,则有: • A→ A’ A’→ A’| 由于 不以A打头,A非左递归. • 对P105的文法(4.1),可改写为 E→TE’ E’→ATE’| T→FT’ T’→MFT’| F→(E)|i A→+|- M→ *|/ • 一般地,设文法中全部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’

消除文法左递归的矩阵方法 设文法的非终结符为X1, 该方程有解：X=BA* X2,,Xn,其中，X的产生式 为得到A*,由 可分为以Vw符和V-符打头 的两类.类似正规式方法，将 A*=I+A+A+A3+…=I+AA* 改写为‘+’，有 Z X=X1a1tX2a2rt+XnCni+B1其中 其中，1= 令A*= B:是以V符打头的产生式 之和，0可以为中 则有：X=BZ Z-I+AZ 这样，文法G可表示为 其中X的产生式以V符打头，而Z的 41C2u 产生式以@∈V*打头，因此将不含 0210202m 左递归. (X,X2,,X)=(X,X2,,Xn +,β2，βn) 注意，由此所得的文法含有无用符 0n0n2Cnm 号和无用产生式需化简 或：X=XA+B

消除文法左递归的矩阵方法 • 设文法的非终结符为 X1, X2, …, Xn, 其中,Xi的产生式 可分为以VN符和VT符打头 的两类.类似正规式方法,将 ‘|’改写为‘+’ ,有 Xi=X11i+X22i+…+Xnni+ i 其中,  i 是以VT符打头的产生式 之和, ki 可以为 这样,文法G可表示为 该方程有解: X=BA* 为得到A*,由 ( , , , ) ( , , , ) ( , , , ) 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           =               = = + + + + = + n n n n Z Z Z Z I A A I A A A I AA        1 1 1 1 2 3 , , * * * 其中 令 则有: X=BZ Z=I+AZ 其中X的产生式以VT符打头,而Z的 产生式以ijV*打头,因此将不含 左递归. 注意,由此所得的文法含有无用符 号和无用产生式,需化简