第5章自顶向下的语法分析方法.

第5章自顶向下的语法分析方法语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)。目前语法分析常用的方法有:1、自顶向下（自上而下）分析2、自底向上（自下而上）分析自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。句型、句子、语言的定义句型:有文法G[S]，若Sx，且x∈V*则称x是文法G[S]的句型。符号表示经过0步或若干步的推导。句子:有文法G[S]，若Sx，且x∈VT*，则称x是文法G[S]的句子。例：G[S]：S→0S1，S→01可有推导S0S100S11000S11100001111说明00001111是G[S]的句子。句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。最左（最右）推导：在推导的任何一步αβ，都是对α中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。句型分析的有关问题①如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：V→A1|A2|…|An，那么如何确定用哪个右部去替换V呢？②如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。5.1确定的自顶向下分析思想确定的自顶向下分析方法:首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.例5.1若有文法G1[S]:S→pA|qBA→cAd|aB→dB|c识别输入串w=pccadd是否是G1[S]的句子试探推导过程：SpApcAdpccAddpccadd试探成功。这个文法有以下两个特点：①每个产生式的右部都由终结符号开始。②如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。即每个产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。例5.2若有文法G2[S]:S→Ap|BqA→a|cAB→b|dB识别输入串w=ccap是否是G2[S]的句子，那么试探推出输入串的推导过程为：SApcApccApccap试探推导成功。文法的特点是：①产生式的右部不全是由终结符开始。②如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。③文法中无空产生式。对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例5.1文法那样直观，对于W=ccap为输入串时，其第一个符号是c，这时从S出发选择S→Ap还是选择S→Bq，需要知道，Ap或Bq它们的开始终结符号集合是什么？因为c是包含在Ap的开始终结符号集合中，且不包含在Bq的开始终结符号集合中，则选择S→Ap往下进行推导。S→Ap|BqA→a|cAB→b|dB一个文法符号串的终结符的首符集定义如下：定义5.1设G=(VT，VN，S，P)是上下文无关文法FIRST(α)={a|αaβ,a∈VT，α,β∈V*}若αε,则规定ε∈FIRST(α)．G2：S→Ap|BqA→a|cAB→b|dB不难求出在例5.2文法G2中FIRST(Ap)={a,c}FIRST(Bq)={b,d}因此有FIRST(Ap)∩(FIRST(Bq)=这样文法G中，两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。但它们右部的符号串可能推导出的First集不相交，因而可以根据当前的输入符号是属于哪个产生式的FIRST集而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。例5.3若有文法G3[S]:S→aA|dA→bAS|ε识别输入串w=abd是否是G3[S]的句子试探推导出abd的推导过程为：SaAabASabSabd试探推导成功。文法的特点是：文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始符号集合都不包含d，但有ε，因此对于d的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A→ε往下推导，而当前A后面的符号为S，S产生式右部的开始的终结符号集合包含了d，所以可匹配。当一个文法中相同左部非终结符的右部存在能ε的情况则必须知道该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个产生式。为此，我们定义一个文法非终结符的后跟符号的集合如下：定义5.2：设G=(VT，VN，S，P)是上下文无关文法，A∈VN，S是开始符号FOLLOW(A)=｛a|SμAβ,且a∈VT，a∈FIRST(β),μ∈VT*,β∈V+｝若SμAβ,且βε,则#∈FOLLOW(A)。也可定义为：FOLLOW(A)={a|S…Aa…,a∈VT}若有S…A，则规定#∈FOLLOW(A)这里我们用‘#’作为输入串的结束符，或称为句子括号，如：#输入串#。因此当文法中含有形如：A→αA→β的产生式时，其中A∈VN，α,β∈V*，当α,β不同时推导出空时，设αε,βε,则当FIRST(α)∩(FIRST(β)∪FOLLOW(A))=时，对于非终结符A的替换仍可唯一地确定候选。综合以上情况可定义选择集合SELECT如下：定义5.3给定上下文无关文法的产生式A→α,A∈VN,α∈V*,若αε,则SELECT(A→α)=FIRST(α)如果αε则：SELECT(A→α)=（FIRST(α)–{ε}）∪FOLLOW(A)是否所有的文法都能采用确定的自上而下的分析该文法的特点是：关于A的产生式的不同右部开始符号集合都含有a，因此要替换非终结符A时，对当前输入符为a的情况，不能确定用产生式A→ab的右部还是用A→a的右部去替换。所以导致必须用带回溯的自顶向下分析，这是一个不确定的分析文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向下分析文法含有左递归，一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出，例5.4～例5.6的文法不能用确定的自顶向下分析,可用带回溯的自顶向下分析。5.2LL(1)文法的定义和判别由前面的例题可知，一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当某个非终结符能推出ε时则与该非终结符的后跟符号集合也有关。综合以上两点，即一个文法能否用确定的自顶向下分析与产生式的Select集有关。定义5.4一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A→α,A→β,满足SELECT(A→α)∩SELECT(A→β)=其中α，β不同时能εLL(1)文法的定义LL(1)文法的含义：第一个L从左到右扫描输入串第二个L生成的是最左推导1向右看一个输入符号便可决定选择哪个产生式。例：判断下列文法是否是LL(1)文法G：S→aAS→dA→bASA→ε解：select(S→aA)={a}select(S→d)={d}select(S→aA)∩select(S→d)=Øselect(A→bAS)={b}select(A→ε)={First(ε)-{ε}}∪Follow(A)=Follow(A)={a,d,#}select(A→bAS)∩select(A→ε)=Ø所以，该文法是LL（1）文法。例：判断下列文法是否是LL(1)文法文法G[S]为：S→aASS→bA→bAA→ε例文法G[S]为：S→aASS→bA→bAA→ε则SELECT(S→aAS)={a}SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)={a,b}所以SELECT(S→aAS)∩SELECT(S→b)={a}∩{b}=SELECT(A→bA)∩SELECT(A→ε)={b}∩{a,b}≠因此，该文法不是LL(1)文法，因而也就不可能用确定的自顶向下分析。LL(1)文法的判别当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。根据定义计算对每一文法符号X∈V计算FIRST(X)(a)若X∈VT，则FIRST(X)＝{X}。(b)若X∈VN，且有产生式X→a…，a∈VT，则a∈FIRST(X)X→ε,则ε∈FIRST(X)。(c)XY…是一个产生式且Y∈VN则把FIRST中的所有非ε元素都加入到FIRST(X)中4、若X∈VN；Y1，Y2，…，Yi∈VN，且有产生式X→Y1Y2…Yn；当Y1Y2…Yn-1都ε时，则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yn-1)的所有非空元素和FIRST(Yn)都包含在FIRST(X)中。即:FIRST(X)=(FIRST(Y1)－{ε}）∪（FIRST(Y2)－{ε}）∪…∪（FIRST(Yn-1)－{ε}）∪{FIRST(Yn)}5、当(4)中所有Yiε,(i=1,2,…n)，则FIRST(X)=(FIRST(Y1)－{ε}）∪（FIRST(Y2)－{ε}）∪…∪（FIRST(Yn)－{ε}）∪{ε}反复使用上述(2)～(5)步直到每个符号的FIRST集合不再增大为止。例文法G[S]为：S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c求每个非终结符的First集。例文法G[S]为：S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→cFIRST(S)={FIRST(A)－{ε}}∪{FIRST(B)－{ε}}∪{ε}∪{b}={b,a,ε}FIRST(A)={b}∪{ε}={b,ε}FIRST(B)＝{ε}∪{a}＝{a,ε}FIRST(C)={FIRST(A)－{ε}}∪FIRST(D)∪FIRST(b)={b,a,c}FIRST(D)={a}∪{c}={a,c}也可以由关系图法求文法符号的FIRST集，可作为一种验证。其方法为：(a)每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。(b)如果文法中有产生式A→αXβ，且αε,则从对应A的结点到对应X的结点连一条箭弧。(c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d)由ε是否为某非终结符FIRST集的成员，若是则将ε加入该非终结符的FIRST集中。文法G[S]为：S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→cFIRST(S)={b,a,ε}FIRST(A)={b,ε}FIRST(B)={a,ε}FIRST(C)={a,b,c}FIRST(D)={a,c}根据定义计算对文法中每一A∈VN计算FOLLOW(A)(a)设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里“#”为句子括号)。(b)若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入FOLLOW(B)中。如果βε则把FOLLOW(A)也加入FOLLOW(B)中。(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。计算FOLLOW集例：文法G[S]为：S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c求每个非终结符的Follow集。解：FOLLOW(S)={#}∪FOLLOW(D)＝{#}FOLLOW(A)=(FIRST(B)－{ε})∪FOLLOW(S)∪FIRST(D)＝{a,#,c}FOLLOW(B)=FOLLOW(S)={#}FOLLOW(C)=FOLLOW(S)={#}FOLLOW(D)={#}判断它是否是LL(1)文法文法G[S]为：S→ABS→bCA→εA→bB→εB→aDC→