第4章白底.

第4章语法分析本章讨论程序语言的语法分析方法，以及语法分析程序的设计原理和实现技术。第4章语法分析语法分析程序的功能和语法分析方法自顶向下语法分析法自底向上算符优先分析法LR分析法4.1语法分析程序的功能语法分析程序的功能语法分析器词法分析后的单词串语法成分构成的语法树或错误表4.1语法分析程序的功能语法分析的方法自顶向下语法分析法(自上而下语法分析法)自底向上语法分析法(自下而上语法分析法)4.1语法分析程序的功能1.自上而下的分析法从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。4.1语法分析程序的功能2.自下而上的分析法从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法开始符号的一种方法；或者说，从语法树的未端开始，步步向上归约，直至根结点的分析方法。4.2自上而下语法分析法非确定的自上而下分析法的基本思想是：对任何输入串W试图用一切可能的办法，从文法的开始符号出发，自上而下地为它建立一棵语法树。或者说，为输入串寻找一个最左推导。如果试探成功，则W为相应文法的一个句子，否则W就不是文法句子。4.2.1非确定的自上而下分析法的思想也就是说，这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。试探发生回溯。4.2.1非确定的自上而下分析法的思想例设有文法G[S]：S→aAbA→de|d输入串W=adbSaAbde匹配失败、这时应回溯,选择A的其它可能的规则重新匹配。4.2.1非确定的自上而下分析法的思想d匹配成功S→aAbA→de|dSaAb输入串W=adb4.2.1非确定的自上而下分析法的思想上述自上而下为输入串W建立语法树的过程，实际也是设法为输入串建立一个最左推导序列：SaAbadb。由于对输入串从左向右进行扫描，使用最左推导，才能保证按从左到右扫描顺序匹配输入串。4.2.1非确定的自上而下分析法的思想根据以上分析，不难看出，非确定的自上而下分析法即是带回溯的自上而下分析法,实际上是一种穷举的试探方法，其分析效率极低，代价很高，在实用的编译程序中是不常用的。我们通常使用确定的自上而下分析法进行语法分析。4.2.1非确定的自上而下分析法的思想但确定的自上而下分析法对语言的文法有一定的限制条件，那就是要求描述语言的文法是无左递归的和无回溯的。4.2.2文法的左递归性和回溯的消除文法左递归的消除当一个文法是左递归文法时，采用自上而下分析法会使分析过程进入无穷循环之中。文法左递归是指文法中的某个非终结符A存在推导AAα+4.2.2文法的左递归性和回溯的消除用非终结符A去匹配输入串时,使当前句型的最左非终结符仍然为A。也就是说，在没有读进任何输入符号的情况下，又重新要求A去进行新的匹配。于是，造成无穷循环。4.2.2文法的左递归性和回溯的消除对含直接左递归的规则进行等价变换，消除左递归(1)引进一个新的非终结符，把含左递归的规则改写成右递归。设关于非终结符A的直接左递归的规则为4.2.2文法的左递归性和回溯的消除对A的规则可改写成如下右递归形式：A'→αA'|εA→βA'A→Aα|β其中α、β是任意的符号串,α不等于ε,β不以A开头4.2.2文法的左递归性和回溯的消除改写以后的形式和原来形式是等价的。也就是说，从A推出的符号串的集合是相同的。4.2.2文法的左递归性和回溯的消除一般情况下，设文法中关于A的规则为A→Aα1|Aα2|…|Aαm|β1|β2|…|βn其中每个α都不等于ε，而每个都不以A开头，消除直接左递归后改写为:A'→α1A'|α2A'|…|αmA'|εA→β1A'|β2A'|…|βnA'4.2.2文法的左递归性和回溯的消除例1设有文法G[E]：E→E+T|E–T|TT→T*F|T/F|FF→(E)|id消去非终结符E,T的直接左递归后，文法G[E]改写为：F→(E)|idE→TE'E'→+TE'|–TE'|εT→FT'T'→*FT'|/FT'|ε4.2.2文法的左递归性和回溯的消除例2设有文法G[A]:A→Ac|Aad|bd|e消去直接左接左递归后文法G[A]改写为A'→cA'|adA'|εA→bdA'|eA'4.2.2文法的左递归性和回溯的消除(2)采用扩充BNF表示法改写含直接左递归的规则：在扩充的BNF表示中(a)使用花括号{α}表示符号串α的出现可0次或多次，即表示α*4.2.2文法的左递归性和回溯的消除例如定义标识符的文法(b)使用方括号[α]表示α的出现可有可无，它用来表示可供选择的符号串。标识符l标识符l标识符d使用扩充BNF表示可改写成标识符l{l|d}4.2.2文法的左递归性和回溯的消除例如，定义C语言中条件语句的文法是条件语句if布尔表达式语句if布尔表达式语句;else语句用扩充BNF表示可改写成如下形式条件语句if布尔表达式语句[;else语句]4.2.2文法的左递归性和回溯的消除(c)使用圆括号可在规则中提因子。例如A→xα1|xα2|…|xαm可写为A→x(α1|α2|…|αm)4.2.2文法的左递归性和回溯的消除例3对下列文法用扩充BNF表示法对其进行改写。E→E+T|E－T|TT→T*F|T/F|FF→(E)|id分析规则E→E+T|E－T|T表示了E所生成的符号串是T开头的后面跟0个或多个+T或－T组成,对T规则类似。4.2.2文法的左递归性和回溯的消除文法G[E]可以改写为：E→T{+T|－T}T→F{*F|/F}F→(E)|id4.2.2文法的左递归性和回溯的消除例4对下列文法用扩充BNF表示法对其进行改写。A→Ac|Aad|bd|e分析规则表示了A所生成的符号串是bd或e开头的后面跟0个或多个c或ad组成。A→Ac|Aad|bd|e4.2.2文法的左递归性和回溯的消除所以原文法可以改写成如下形式A→(bd|e){c|ad}4.2.2文法的左递归性和回溯的消除2.回溯的消除在自上而下分析过程中，由于回溯，需要推翻前面的分析，包括已做的一大堆语义工作，重新去进行试探，这样大大降低了语法分析器的工作效率，因此，需要消除回溯。4.2.2文法的左递归性和回溯的消除我们分析发现引起回溯的原因是:在文法中,当某个非终结符A有多个候选式时:遇到用A去匹配当前输入符号a时，无法确定选用唯一的一个候选式，而只能逐一进行试探，从而引起回溯。具体表现在下面两种情况。A→α1|α2|α3|∙∙∙∙∙∙|αn4.2.2文法的左递归性和回溯的消除第一种情况:文法中相同左部的规则，其右部左端第一个符号相同而引起回溯。S→aAbA→de|d例设有文法G[S]：4.2.2文法的左递归性和回溯的消除第二种情况:文法中相同左部的规则，其中某一右部能推出ε串，例如,文法G：A→BxB→x|ε其非终结符B有两个右部，第二个右部能推导出ε串且两个右部左端第一个符号不相同，但在分析符号串W＝x时出现回溯。4.2.2文法的左递归性和回溯的消除试探分析过程如下图所示：ABxxABxεA→BxB→x|εW＝x匹配失败匹配成功4.2.2文法的左递归性和回溯的消除综上所述，在自上而下分析过程中，为了避免回溯，对描述语言的文法有一定的要求:对文法的某个非终结符A,当它有多个侯选式时:若用A匹配输入串时,能根据当前读到的输入符号a唯一地选择一条规则去匹备输入串。或者说，能唯一地选择一条规则进行推导。4.2.2文法的左递归性和回溯的消除A→α1|α2|α3|∙∙∙∙∙∙|αn这也就是说，在自上而下分析过程中，为了避免回溯，要求描述语言的文法是LL(1)文法。4.2.2文法的左递归性和回溯的消除LL(1)文法的判断条件为了建立LL(1)文法的判断条件，需引进三个相关的集合：FIRST集FOLLOW集SELECT集LL(1)文法的判断条件(1)设α是文法G的任一符号串，定义文法符号串α的首符号集合。FIRST(α)={a|αa…且a∈VT}*,则规定ε∈FIRST(α)若αε*LL(1)文法的判断条件例设有文法G[S]:S→Ap|BqA→cA|aB→dB|bFIRST(Ap)={c,a}APcApAPapFIRST(Bq)=Bqbq{b,d}BqdBqLL(1)文法的判断条件(2)设文法G的开始符号为S，对于G的任何非终结符A，定义非终结符A的后继符号的集合FOLLOW(A)={a|S…Aa…且a∈VT}*若有S…A,*则规定$∈FOLLOW(A)。LL(1)文法的判断条件换句话说FOLLOW(A)是G的所有句型中紧接在A之后出现的终结符或$。这里我们用$作为输入串的结束符，例如，$输入串$。也可以用#作为输入串的结束符，例如，#输入串#。LL(1)文法的判断条件例设有文法G[A]:FOLLOW(B)=AaBAaBabBAabBdAaBabBAabBaB{$,d,a}A→aB|dB→bBA|ε*/若αεLL(1)文法的判断条件(3)定义规则的选择集合SELECT，设A→α是文法G的任一条规则，其中A∈VN,α∈(VN∪VT)*，定义SELECT(A→α)=FIRST(α)FIRST(α)\{ε}∪FOLLOW(A)*若αεLL(1)文法的判断条件例设有文法G[A]:A→aB|dB→bBA|εSELECT(A→aB)=FIRST(aB)={a}SELECT(A→d)=FIRST(d)={d}LL(1)文法的判断条件{b}SELECT(B→bBA)=FIRST(bBA)=={$,d,a}FOLLOW(B)SELECT(B→ε)=FIRST(ε)\{ε}∪FOLLOW(B)={$,d,a}A→aB|dB→bBA|εLL(1)文法的判断条件LL(1)文法定义一个上下文无关文法G是LL(1)文法,当且仅当对G中每个非终结符A的任何两个不同的规则A→α|β，满足SELECT(A→α)∩SELECT(A→β)=Φ其中α、β中至多只有一个能推出ε串。LL(1)文法的判断条件LL(1)中的第一个L表明自上而下的分析是从左到右扫描输入串，第二个L表明分析过程中使用最左推导，1表示分析时每一步只需向前看一个符号即可决定所选用的规则，而且这种选择是准确无误的。LL(1)文法的判断条件例1设有文法G[S]:S→aAbA→de|d∵SELECT(A→de)=FIRST(de)={d}SELECT(A→d)=FIRST(d)={d}∴SELECT(A→de)∩SELECT(A→d)≠Φ由LL(1)文法定义可知，该文法不是LL(1)文法，因此对输入串不能进行确定的自上而下分析。LL(1)文法的判断条件例2设有文法G[A]A→aB|dB→bBA|ε则SELECT(A→aB)=FIRST(aB)={a}SELECT(A→d)=FIRST(d)={d}SELECT(B→bBA)=FIRST(bBA)={b}SELECT(B→ε)=FIRST(ε)\{ε}∪FOLLOW(B)={a,d,$}LL(1)文法的判断条件所以SELECT(A→aB)∩SELECT(A→d)=ΦSELECT(B→bBA)∩SELECT(B→ε)=Φ由定义可知，G[A]是LL(1)文法，对任何输入串W可进行确定的分析。LL(1)文法的判断条件例3设有文法G[S]:S→aABA→bB|dA|εB→a|e∵SELECT(A→bB)=FIRST(bB)={b}SELECT(A→dA)=FIRST(dA)={d}SELECT(A→ε)=FIRST(ε)\{ε}∪FOLLOW(A)={a,e}试判断该文法是否LL(1)文法。LL(1)文法的判断条件SELECT(B→a)=FIRST(a)={a}SELECT(B→e)=FIRST(e)={e}SELECT(A→bB)∩SELECT(A→dA)=ΦSELECT(A→bB)∩SELECT(A→ε)=ΦSELECT(A→dA)∩SELECT(A→ε)=ΦSELECT(B→a)∩SELECT(B→e)=ΦS→aABA→bB|