ch自顶向下语法分析方法实用.pptx

1 语法分析就是识别由词法分析给出的单词符号序列语法分析就是识别由词法分析给出的单词符号序列是否是给定文法的正确句子是否是给定文法的正确句子(程序程序).).语法分析常用的方法语法分析常用的方法:n自顶向下分析自顶向下分析n自底向上分析自底向上分析 自底向上分析分为自底向上分析分为:算符优先分析算符优先分析LRLR分析分析第五章 自顶向下语法分析第1页/共74页2自顶向下分析（面向目标的分析方法）自顶向下分析（面向目标的分析方法）从文法的开始符号出发企图推导出与输入的单词串完从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子全相匹配的句子.自顶向下分析方法分为自顶向下分析方法分为:l确定的分析方法对文法有一定的限制。确定的分析方法对文法有一定的限制。l不确定的分析方法回溯的分析方法，一种穷举的不确定的分析方法回溯的分析方法，一种穷举的试探方法。试探方法。第五章 自顶向下语法分析第2页/共74页35.1 确定的自顶向下分析若有文法G1S：S-pA|qB A-cAd|a B-dB|b构造输入串W=pccadd的语法树。确定的自顶向下分析方法是从文法的开始符号确定的自顶向下分析方法是从文法的开始符号出发，如何根据当前的输入符号唯一确定选用出发，如何根据当前的输入符号唯一确定选用哪个产生式替换相应非终结符往下推导，或构哪个产生式替换相应非终结符往下推导，或构造一颗相应的语法树。造一颗相应的语法树。文法的特点：文法的特点：1 1）每个产生式的右部都）每个产生式的右部都由终结符号开始；由终结符号开始；2 2）若两个产生式有相同）若两个产生式有相同的左部，则它们的右部由不同的左部，则它们的右部由不同的终结符开始。的终结符开始。第3页/共74页4 文法文法G2SG2S为：为：S-Ap|BqS-Ap|Bq A-a|cA A-a|cA B-b|dB B-b|dB 给出输入串给出输入串W=ccapW=ccap的推导过的推导过程。程。文法的特点：文法的特点：1 1）产生式的右部不全是由终结符开始；）产生式的右部不全是由终结符开始；2 2）若两个产生式有相同的左部，则它们的右部是由不同）若两个产生式有相同的左部，则它们的右部是由不同的终结符或非终结符开始；的终结符或非终结符开始；3 3）文法中无空产生式。）文法中无空产生式。5.1 确定的自顶向下分析第4页/共74页5文法文法G3SG3S为：为：S-aAS-aA S-d S-d A-bAS A-bAS A-A-给出给出W=abdW=abd的推导过程。的推导过程。5.1 确定的自顶向下分析文法的特点：文法的特点：1 1）文法中有空产生式。）文法中有空产生式。第5页/共74页6【FIRST 集定义定义】设设G=(VN,VT,S,P)是上下文无关文法是上下文无关文法,又设又设 是文法是文法 G 的的任一字符串，定义任一字符串，定义 的首符集的首符集FIRST()=a|a,a VT 若若，FIRST()FIRST()就是从就是从 可推导出的所有首终结符或可能的可推导出的所有首终结符或可能的构成构成的集合。的集合。*5.1 确定的自顶向下分析第6页/共74页7【FOLLOW 集定义定义】假设假设 S 是文法是文法 G 的开始符号，对于的开始符号，对于 G 的任何非终结符的任何非终结符 A，定义非终结符定义非终结符 A 的的后继符号后继符号的集合：的集合：FOLLOW(A)=a|S.Aa.，aVT。若若 S.A，则规定，则规定#FOLLOW（A）。）。FOLLOW(A)是是 G 的所有句型中紧接在的所有句型中紧接在 A 之后出现的终结符或之后出现的终结符或#构成的集合。构成的集合。其中其中#作为输入串的结束符。作为输入串的结束符。*5.1 确定的自顶向下分析第7页/共74页8当文法中含有形如当文法中含有形如:A-A-的产生式时的产生式时,其中其中A VN,V*。若若 和和 不同时推导出空时不同时推导出空时,假定假定 ，则当，则当FIRST（）（FIRST（）FOLLOW（A）时，对于非终结符时，对于非终结符A的替换仍可唯一确定候选。的替换仍可唯一确定候选。*5.1 确定的自顶向下分析第8页/共74页9【SELECT集定义集定义】假设假设 A 是文法是文法 G 的任一规则，定义规则的任一规则，定义规则 A 的的选选择集合择集合 SELECT 为为：SELECT(A)=其中其中 AVN，(VN VT)*，FIRST()若若 (FIRST()-)FOLLOW(A)若若 =*/*5.1 确定的自顶向下分析第9页/共74页101 1、第一个、第一个 L L 表示从左到右扫描字符串；表示从左到右扫描字符串；2 2、第二个、第二个 L L 表示最左推导；表示最左推导；3 3、1 1 表示每一步只需向前看一个符号。表示每一步只需向前看一个符号。LL(1)文法：一一个个上上下下文文无无关关文文法法 G 是是 LL(1)文文法法，当当且且仅仅当当对对 G 中中每每个个非非终终结结符符 A 的的任任何何两两个个不不同同的的规规则则 A|，满足，满足:SELECT(A)SELECT(A)=其中其中、中至多只有一个能推导出中至多只有一个能推导出 串。串。5.1 确定的自顶向下分析第10页/共74页11例题分析：判断该文法是否LL(1)LL(1)文法？分析输入串分析输入串W Wabab的推导过程。的推导过程。1）S=aAS=abAS=abS2）S=aAS=aS=ab第11页/共74页125.2 LL(1)文法的判别判断判断LL(1)LL(1)文法的步骤文法的步骤:1.1.求出能够推出求出能够推出 的非终结符的非终结符 1)1)初始化初始化 设置一个数组，并初始化为设置一个数组，并初始化为“未定未定”值。值。GS:S-AB|bCA-b|B-aD|C-AD|bD-aS|c第12页/共74页135.2 LL(1)文法的判别 2)2)扫描文法的产生式扫描文法的产生式 a)a)删删除除所所有有右右部部含含有有终终结结符符的的产产生生式式,若若以以某某一一非非终终结结符符为为左左部部的的所所有有产产生生式式都都被被删删除除,则则将将数数组组中中对对应应该该非非终终结结符的标记修改为符的标记修改为“否否”。b)b)若若某某一一非非终终结结符符的的某某一一产产生生式式右右部部为为,则则将将数数组组中中对对应应该该非非终终结结符符的的标标志志置置为为“是是”,并并从从文文法法中中删删除除该该非非终终结符的所有产生式。结符的所有产生式。GS:S-AB|bCA-b|B-aD|C-AD|bD-aS|c第13页/共74页143)3)扫描产生式右部的每一符号扫描产生式右部的每一符号 a)a)若若所所扫扫描描到到的的非非终终结结符符号号在在数数组组中中的的对对应应标标志志是是“是是”,则则删删去去该该非非终终结结符符,若若这这使使得得产产生生式式右右部部为为空空,则则对对产产生生式式左左部部的的非非终终结结符符在在数数组组中中对对应应的的标标志志改改为为“是是”,并删去该非终结符为左部的所有产生式。并删去该非终结符为左部的所有产生式。b)b)若若所所扫扫描描到到的的非非终终结结符符号号在在数数组组中中的的对对应应标标志志是是“否否,则则删删去去该该产产生生式式,若若这这使使得得产产生生式式左左部部非非终终结结符符的的有有关关产产生生式式都都被被删删去去,则则将将数数组组中中该该非非终终结结符符对对应应的的标标志志改改成成”否否“。4)4)重重复复3),3),直直到到扫扫描描完完一一遍遍文文法法的的产产生生式式,数数组组中中非非终终结结符符对应的特征再没有改变为止。对应的特征再没有改变为止。GS:S-AB|bCA-b|B-aD|C-AD|bD-aS|c第14页/共74页152.计算FIRST集 1)1)计算每一文法符号计算每一文法符号X X的的FIRSTFIRST集集-FIRST(X)-FIRST(X)(a)(a)若若X X V VT T,则则FIRST(X)=X;FIRST(X)=X;(b)(b)若若X X V VN N且有产生式且有产生式X-aX-a.,a.,a V VT T,则则a a FIRST(X);FIRST(X);(c)(c)若若X X V VN N且有产生式且有产生式X-X-,则则 FIRST(X);FIRST(X);第一种方法：根据定义计算第一种方法：根据定义计算第15页/共74页162.计算FIRST集(d)若若X,Y1,Yn VN,且且有有产产生生式式X-Y1 Yn.当当 Y1,Yi-1=(其其中中1 i n),则则FIRST(Y1)-,FIRST(Yi-1)-,FIRST(Yi)都包含在都包含在FIRST(X)中中;(e)若若(d)中中所所有有Yi=(i=1,n),则则FIRST(X)=FIRST(Y1)FIRST(Y2)FIRST(Yn)反反复复使使用用(b)-(e)步步直直至至每每个个符符号号的的FIRST集集合合不不再再增增大大为为止。止。*第16页/共74页17计算FIRST集(续)2)求每个符号串的求每个符号串的FIRST集集 a)若符号串若符号串 V*,=X1Xn,当当X1不能不能=,则则 FIRST()=FIRST(X1);b)若对任何若对任何j(1 j i-1,2 i n),FIRST(Xj),FIRST(Xi）,则则FIRST()=(FIRST(Xj)-)FIRST(Xi);c)当所有当所有FIRST(Xj)都含有都含有 时时,则则 FIRST()=(FIRST(Xj)。*第17页/共74页18GS:S-AB|bC A-b|B-aD|C-AD|b D-aS|c例题分析：求文法中符号与符号串的FIRST集。FIRST(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,cFIRST(D)=a c=a,c第18页/共74页19FIRST(AB)=a,b,FIRST(bC)=bFIRST()=FIRST(b)=bFIRST(aD)=aFIRST(b)=bFIRST(aS)=aFIRST(c)=cFIRST(AD)=a,b,cGS:S-AB|bCA-b|B-aD|C-AD|bD-aS|c产生式右部符号串的FIRST集：第19页/共74页20第二种方法：第二种方法：GS:S-AB|bCA-b|B-aD|C-AD|bD-aS|c第20页/共74页213.计算FOLLOW集 对文法中每一对文法中每一A VN计算计算FOLLOW(A)a)设设 S为为 文文 法法 中中 开开 始始 符符 号号,将将“#”加加 入入FOLLOW(S)中。中。b)若若A-B 是是一一个个产产生生式式,则则将将FIRST()的的非空元素加入非空元素加入FOLLOW(B)中中;若若=,则则将将FOLLOW(A)也也加加入入FOLLOW(B)中。中。c)重重复复使使用用(b)直直到到每每个个非非终终结结符符的的FOLLOW集集不再增大为止。不再增大为止。*方法方法1：根据定义计算：根据定义计算第21页/共74页223.计算FOLLOW集因为当有因为当有为什么将FOLLOW(A)FOLLOW(A)加入FOLLOW(B)FOLLOW(B)呢？第22页/共74页23GS:S-AB|bCA-b|B-aD|C-AD|bD-aS|c第23页/共74页24方法方法2：第24页/共74页25FOLLOWGS:S-AB|bCA-b|B-aD|C-AD|bD-aS|c第25页/共74页264.计算计算SELECT集集第26页/共74页27第27页/共74页285.3 5.3 非LL(1)LL(1)文法到LL(1)LL(1)文法的等价变换 在在确确定定的的自自顶顶向向下下分分析析中中,要要求求对对给给定定语语言言的的文文法法必必须须是是LL(1)LL(1)文法文法,然而不一定每个语言都有然而不一定每个语言都有LL(1)LL(1)文法。文法。如如何何对对一一个个语语言言的的非非LL(1)LL(1)文文法法变变换换为为等等价价的的LL(1)LL(1)形形式式?由由LL(1)LL(1)文文法法的的定定义义知知道道,当当文文法法中中含含有有直直接接或或间间接接左左递递归归,或含有左公共因子时或含有左公共因子时,这样的文法肯定不是这样的文法肯定不是LL(1)LL(1)文法。文法。因因此此，首首先先设设法法消消除除文文法法中中的的左左递递归归与与提提取取左左公公共共因因子子对文法进行等价变换。在某些情况下对文法进行等价变换。在某些情况下,使其变换为使其变换为LL(1)LL(1)文法。文法。第28页/共74页29 提取提取左公共因子左公共因子是指当文法中含有形如是指当文法中含有形如：AA 1 1|2 2|.|.|n n|1 1|2 2|.|.|m m 的规则，的规则，可以把它修改成：可以把它修改成：A A A A A A A A|1 1 1 1|2 2 2 2|.|.|.|.|m m m m A A A A 1 1 1 1|2 2 2 2|.|.|.|.|n n n n 经过反复提取左公共因子，就能够做到使每个非终结符的所有候选首符经过反复提取左公共因子，就能够做到使每个非终结符的所有候选首符集变成两两不相交。集变成两两不相交。该做法的代价是大量引进非终结符和该做法的代价是大量引进非终结符和-产生式。产生式。1.提取左公共因子第29页/共74页30【例例】文法文法GS:SaAb Ade|d利用提取公共左因子的方法对其进行改写，得到：利用提取公共左因子的方法对其进行改写，得到：SaAbAdAAe|这是一个这是一个 LL(1)文法文法第30页/共74页31【例例】文法文法GS:Sad|Ae AaS|bA对于非终结符对于非终结符 S 的规则，因为有：的规则，因为有：SELECT(Sad)SELECT(SAe)=a a,b 故它不是故它不是一个一个 LL(1)文法。文法。因为非终结符因为非终结符 S 的两个右部的公共左因子是隐式的，因此，的两个右部的公共左因子是隐式的，因此，在提取公共左因子之前，对在提取公共左因子之前，对 S 右部以非终结符右部以非终结符 A 开头的规则开头的规则（两条规则）进行相应替换，得到：（两条规则）进行相应替换，得到：Sad|aSe|bAeAaS|bA对对 S 提取公共左因子得提取公共左因子得SaS|bAeSd|Se AaS|bA第31页/共74页32【例例】文法文法GS:GS:SAe|BdAaAe|bBaBd|b对于非终结符对于非终结符 S 的规则，因为有：的规则，因为有：SELECT(SAe)SELECT(SBd)=a,b a,b 故它不是故它不是一个一个 LL(1)文法。文法。对对 S 规则，用规则，用A，B的两条规则进行相应替换，得到：的两条规则进行相应替换，得到：SaAee|be|aBdd|bdAaAe|bBaBd|b对对 S 提取公共左因子得提取公共左因子得SaS|bS”SAee|Bdd S”e|dAaAe|bBaBd|b它还不是它还不是 LL(1)文法，但无论重复上述步骤多少次都无法改文法，但无论重复上述步骤多少次都无法改写为写为 LL(1)文法。文法。第32页/共74页33可以看到：可以看到：1 1）不一定每个文法的左公共因子都能在有限的步骤内替）不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。换成无左公共因子的文法。2 2）一个文法提取了左公共因子后，只解决了相同左部产）一个文法提取了左公共因子后，只解决了相同左部产生式右部的生式右部的FIRSTFIRST集不相交问题，当改写后的文法不含空集不相交问题，当改写后的文法不含空产生式且无左递归时，则改写后的文法是产生式且无左递归时，则改写后的文法是LLLL（1 1）文法，）文法，若还有空产生式时，还需用若还有空产生式时，还需用LLLL（1 1）文法的判别方式进行）文法的判别方式进行判断才能确定是否为判断才能确定是否为LLLL（1 1）文法。）文法。第33页/共74页34假定文法中含有关于非终结符号假定文法中含有关于非终结符号 A A 的产生式，其形如的产生式，其形如 AA|AA|，其中，其中 不等于不等于 ，不以不以 A A 开头，称该文开头，称该文法为直接左递归或规则左递归文法。法为直接左递归或规则左递归文法。2.消除左递归消除左递归 1)消除直接左递归消除直接左递归产生式产生式 AA|AA|定义的是重复定义的是重复 串且以串且以 开头的串。开头的串。修改的思路是用修改的思路是用右递归代替左递归右递归代替左递归实现句子中某子串的重复。实现句子中某子串的重复。一个文法含有下列形式的产生式一个文法含有下列形式的产生式:a)A-A a)A-A 直接左递归直接左递归 b)A-B,B-A b)A-B,B-A 间接左递归间接左递归称为左递归文法称为左递归文法.第34页/共74页35引进一个新的非终结符，把左递归规则改写成等价的非左递引进一个新的非终结符，把左递归规则改写成等价的非左递归形式：归形式：AA AAAA AA A A A AAA|一般地，对于一般地，对于 A A 的全部产生式（其中每个的全部产生式（其中每个i i不等于不等于 ，每，每个个j j不以不以 A A 开头）：开头）：AAAA1 1|A|A2 2|.|A|.|Am m|1 1|2 2|.|.|n n可等价地改写成如下非左递归可等价地改写成如下非左递归(右递归右递归)形式：形式：AA1 1A A|2 2A A|.|.|n nA AA A1 1A A|2 2A A|.|.|m mA A|第35页/共74页36【例例】文法文法GE:EE+T|E-T|TTT*F|T/F|FF（E）|id消除非终结符消除非终结符 E，T 的直接左递归，可等价地改写成如下非的直接左递归，可等价地改写成如下非左递归形式：左递归形式：ETEE+TE|-TE|TFTT*FT|/FT|F(E)|id第36页/共74页37【例例】文法文法GA:AAc|Aad|bd|e消除非终结符消除非终结符 A 的直接左递归，可等价地改写成如下非左递的直接左递归，可等价地改写成如下非左递归形式：归形式：AbdA|eAAcA|adA|第37页/共74页382）消除间接左递归）消除间接左递归如果一个文法含有形如如果一个文法含有形如 A A的推导，称该文法为间接的推导，称该文法为间接左递归或左递归文法。左递归或左递归文法。消除方法：消除方法：先通过产生式非终结符置换，将间接左递归变为直接左先通过产生式非终结符置换，将间接左递归变为直接左递归，然后再按照直接左递归消除方法消除。递归，然后再按照直接左递归消除方法消除。+第38页/共74页392）消除间接左递归）消除间接左递归【例例】文法文法GS：SQc|cQRb|bRSa|a是间接左递归文法。是间接左递归文法。因为存在着如下推导：因为存在着如下推导：SQcRbcSabc。修改的思路是用修改的思路是用代入法代入法，使其出现直接左递归，按前述，使其出现直接左递归，按前述方法消除直接左递归，然后化简文法，去掉无用的产生式，方法消除直接左递归，然后化简文法，去掉无用的产生式，即消除那些从开始符号出发，永远无法到达的非终结符的产即消除那些从开始符号出发，永远无法到达的非终结符的产生式规则。生式规则。第39页/共74页40例如：例如：第40页/共74页41如果一个文法不含回路（形如如果一个文法不含回路（形如 PP的推导），则下述算法将的推导），则下述算法将保证消除左递归（改写后的文法可能含有以保证消除左递归（改写后的文法可能含有以 为右部的产生为右部的产生式）式）:消除文法中一切左递归的算法消除文法中一切左递归的算法:+1）把文法把文法 G 的所有非终结符按某一顺序排序的所有非终结符按某一顺序排序P1，P2.Pn；2）FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如 Pi Pj 的规则改写成：的规则改写成：Pid1|d2|dk 。其中其中 Pjd1|d2|dk 是关于是关于 Pj 的所有规则；的所有规则；END 消除消除 Pi 的直接左递归的直接左递归END3）删除无用产生式删除无用产生式.第41页/共74页42令非终结符顺序为令非终结符顺序为 R、Q、SR 代入代入 Q 得：得：QSab|ab|bQ 不含左递归，代入不含左递归，代入 S 得：得：SSabc|abc|bc|c消除消除S的直接左递归得文法：的直接左递归得文法：SabcS|bcS|cSSabcS|QRb|bR Sa|a其中，关于其中，关于 Q、R 的产生式多余，删除之，得文法：的产生式多余，删除之，得文法：Sa bcS|bcS|CSSabcS|由于对非终结符排序的任意性，可能使变换后的文法不唯一。由于对非终结符排序的任意性，可能使变换后的文法不唯一。【例例】文法文法GS：SQc|cQRb|bRSa|a第42页/共74页435.4 5.4 非确定的自上而下分析法的思想 当文法不满足当文法不满足LL(1)LL(1)时时,则不能用确定的自顶向下分析则不能用确定的自顶向下分析,但可用不确定的自顶向下分析方法但可用不确定的自顶向下分析方法,也就是带回溯的自顶向也就是带回溯的自顶向下分析法下分析法,适合上下文无关文法适合上下文无关文法.非确定的自上而下分析的基本思想：非确定的自上而下分析的基本思想：对任意给定的输入串，从文法的开始符号出发，寻找一对任意给定的输入串，从文法的开始符号出发，寻找一个最左推导过程或自上而下地建立一棵语法树，试图产生一个最左推导过程或自上而下地建立一棵语法树，试图产生一个和输入串相同的句子。或者说，为输入串寻找一个最左推个和输入串相同的句子。或者说，为输入串寻找一个最左推导。如果试探成功，则输入串为相应文法的句子，否则不是导。如果试探成功，则输入串为相应文法的句子，否则不是文法句子。文法句子。不确定的自上而下分析法的分析过程本质：是一种穷举不确定的自上而下分析法的分析过程本质：是一种穷举试探过程；是反复使用不同规则，谋求匹配输入串的过程。试探过程；是反复使用不同规则，谋求匹配输入串的过程。第43页/共74页44【例例】设有文法设有文法G SG S：SaAbSaAbAde|d Ade|d 若若输输入入串串为为 W=adb#W=adb#，则则其其自自上上而而下下的的分分析析过过程程是是，从从文法的开始符号出发，从左至右地匹配整个输入串文法的开始符号出发，从左至右地匹配整个输入串 W W。以以文文法法开开始始符符号号 S S 为为树树根根，对对输输入入串串从从左左到到右右扫扫描描，输输入入串串指指针针 IP IP 总总是是指指向向当当前前正正在在识识别别的的符符号号,当当一一个个符符号号识识别别后后，IP IP 总总是是指指向向下下一一个个未未处处理理的的符符号号。自自上上而而下下地地建建立输入串的语法树。立输入串的语法树。问题一：产生式的多个候选式有相同首符即问题一：产生式的多个候选式有相同首符即相同左部的产生式的右部相同左部的产生式的右部FIRSTFIRST集交集不为空集交集不为空.自上而下分析过程可能遇到的问题：第44页/共74页45开始时，开始时，IP 指向指向 a，可使用产生式，可使用产生式 SaAb 推导，使推导，使 IP 指向指向的的 a 与产生式与产生式 SaAb 右端的右端的 a 匹配。如图。匹配。如图。SaAba d bIP第二步第二步，IP 指向指向 d，让，让 A 去匹配，非终结符去匹配，非终结符 A 有两个选择：有两个选择：Ade 或或 Ad，试着用第一个选择去匹配输入串。如图。试着用第一个选择去匹配输入串。如图。a d bIPSaAbdeS第45页/共74页46第三步第三步，IP 指向指向 b，子树，子树 A 的第二个结点是终结符的第二个结点是终结符 e，与当前输入符号与当前输入符号 b 不一致，不一致，匹配失败匹配失败。A 的一个选择不适合用于构造的一个选择不适合用于构造 W 的语法树。的语法树。应回溯，必须应回溯，必须退回到出错点，选择退回到出错点，选择 A 的其它可能的规则重新匹配。的其它可能的规则重新匹配。a d bIPSaAbde为了实现回溯，应把为了实现回溯，应把 A 的第一个选择所构造的子树删除，输的第一个选择所构造的子树删除，输入指针回退，重新指向入指针回退，重新指向 d。SaAba d bIP第46页/共74页47第四步第四步，IP 指向指向 d，重新试探用，重新试探用 A 的的第二个第二个规则去匹配，子规则去匹配，子树树 A 只有一个子结点，而且和输入符号匹配，也是只有一个子结点，而且和输入符号匹配，也是 A 完成匹完成匹配，如图。配，如图。a d bIPSaAbd第五步第五步，IP 指向指向 b，在，在 S 的第二个结点完成匹配后，进行的第二个结点完成匹配后，进行 S 的第三个结点去匹配，由于的第三个结点去匹配，由于 b 这个子结点和当前输入一致，这个子结点和当前输入一致，完成了为完成了为 W 构造语法树的任务。构造语法树的任务。所以输入串所以输入串 Wadb是文法是文法 GS的一个句子。的一个句子。a d bIPSaAbd第47页/共74页48这种解决办法是使用一种穷举的试探方法，即当后面这种解决办法是使用一种穷举的试探方法，即当后面的匹配无法进行时，输入指针回退，刚刚产生的语法的匹配无法进行时，输入指针回退，刚刚产生的语法树删去，这样的过程称之为树删去，这样的过程称之为回溯回溯。有时。有时回溯回溯要进行多要进行多步。步。缺点：分析方法分析效率较低，代价较高。缺点：分析方法分析效率较低，代价较高。第48页/共74页49问题二：文法含有左递归问题二：文法含有左递归【例例】有文法有文法GB：BBb|a以及输入串以及输入串 abb#，要求证明输入串是文法的一个句子。，要求证明输入串是文法的一个句子。开始时，开始时，IP 指向指向 a，如果使用产生式，如果使用产生式Ba推导，推导，IP指向的指向的a 与与 产生式产生式 Ba 右端的右端的 a 匹配，但无法推导出整个输入串；匹配，但无法推导出整个输入串；如果使用产生式如果使用产生式 BBb 推导，则如图所示。推导，则如图所示。BBba b bIP第49页/共74页50第二步，第二步，IP 仍指向仍指向 a，在不知道后面的字符的情况下，用产，在不知道后面的字符的情况下，用产生式生式 BBb 推导则如图所示推导则如图所示.a b bIPBBbBb第三步，使用产生式第三步，使用产生式Ba推导推导,匹配成功匹配成功.第50页/共74页51问题三：由于相同左部非终结符的右部存在能推出问题三：由于相同左部非终结符的右部存在能推出(星星号推出号推出)产生式产生式,且该非终结符且该非终结符FOLLOW集中含有其集中含有其它产生式右部它产生式右部FIRST集的元素集的元素.【例例】有文法有文法GS：SaAS,S-b,AbAS|以及输入串以及输入串 ab#，要求证明输入串是文法的一个句子。，要求证明输入串是文法的一个句子。开始时开始时，IP 指向指向 a，使用产生式，使用产生式 SaAS 推导，推导，则如图。则如图。第二步第二步，IP 指向指向 b，b 与产生式与产生式 AbAS 右端的右端的 b 匹配，匹配，则如图。则如图。SaSSaSAAbAS第51页/共74页52第三步第三步 输入指针向右移动输入指针向右移动,输入符结束。但输入符结束。但ASSASS并不并不能推出能推出,因此推导失败。因此推导失败。第四步第四步 回溯使输入指针退回到回溯使输入指针退回到b,b,对对A A的推导改为选用的推导改为选用下一个产生式下一个产生式A-A-,对对b b用用A A的后跟符匹配。继续用的后跟符匹配。继续用S S的的产生式和产生式和b b匹配匹配,S,S的两个产生式只能选用的两个产生式只能选用S-b,S-b,则最终得到匹配则最终得到匹配,成功。成功。第52页/共74页535.5 确定的自顶向下分析方法1.1.递归子程序法递归子程序法 当一个文法满足当一个文法满足 LLLL（1 1）条件时，就可以为它构造一个）条件时，就可以为它构造一个不带回溯的自上而下的分析程序，它由一组递归过程组成，不带回溯的自上而下的分析程序，它由一组递归过程组成，每个过程对应文法的一个非终结符，这样的一个分析程序称每个过程对应文法的一个非终结符，这样的一个分析程序称递归下降分析器递归下降分析器。在在开开始始工工作作前前，输输入入串串指指示示器器 IP IP 指指向向第第一一个个输输入入符符号号，当每个子程序工作完毕后当每个子程序工作完毕后 IP IP 总是指向下一个未处理的符号。总是指向下一个未处理的符号。递递归归过过程程的的功功能能是是识识别别由由该该非非终终结结符符推推出出的的串串,当当某某非非终终结结符符的的产产生生式式有有多多个个候候选选时时能能够够唯唯一一确确定定某某个个产产生生式式进进行行推导推导.第53页/共74页54构造递归下降分析程序时，每个函数名是相应的非终结符，构造递归下降分析程序时，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。函数体则是根据规则右部符号串的结构编写。构造方法构造方法1)当遇到终结符当遇到终结符 a 时，则编写语句时，则编写语句if(当前读到的输入符号当前读到的输入符号=a)，则读入下一个输入符号。则读入下一个输入符号。2)当遇到非终结符当遇到非终结符 A 时，则编写调用语句时，则编写调用语句 A().3)当遇到当遇到 A 规则时，则编写语句规则时，则编写语句if(当前读到的输入符号当前读到的输入符号 FOLLOW(A)error()。4)当某个非终结符的规则有多个候选式时，按当某个非终结符的规则有多个候选式时，按LL(1)文法的条文法的条件唯一确定一个候选式进行推导。件唯一确定一个候选式进行推导。第54页/共74页55【例例】设有文法设有文法GS：Sa|(T)TT,S|S试构造一个识别该文法句子的下降分析程序。试构造一个识别该文法句子的下降分析程序。第一步：消除文法左递归，得到文法第一步：消除文法左递归，得到文法GSSa|(T)TSTT,ST|第二步：判断文法第二步：判断文法 G 是否为是否为 LL(1)文法，文法，如果不是，需要进行转换。如果不是，需要进行转换。SELECT(Sa)SELECT(S)=SELECT(Sa)SELECT(S(T)=SELECT(S)SELECT(S(T)=SELECT(T，ST)SELECT(T)=FIRST(,ST)(FIRST()FOLLOW(T)=,)=所以文法所以文法 GS 是是 LL(1)文法。文法。第55页/共74页56第三步：构造相应的下降分析程序第三步：构造相应的下降分析程序v分析程序中函数分析程序中函数 Scaner()的功能：读进源程序的下的功能：读进源程序的下一个单词符号并将它放在全程变量一个单词符号并将它放在全程变量 sym 中。中。v函数函数 error()：出错处理程序。：出错处理程序。主程序主程序main()Scaner();S();if(sym=#)printf(“success”);else printf(“fail”);第56页/共74页S()/Sa|(T)if(sym=a|sym=)Scaner();else if(sym=()Scaner();T();if(sym=)Scaner();else error();T()/TS T S();T();T()/T,S T|if(sym=,)Scaner();S();T();else if(sym!=)error();第57页/共74页582.2.预测分析法 预测分析方法自顶向下分析的另一种方法预测分析方法自顶向下分析的另一种方法.预测分析器由三部分组成预测分析器由三部分组成:预测分析程序（总控程序）预测分析程序（总控程序）先进后出栈先进后出栈预测分析表预测分析表第58页/共74页59预测分析器的工作模型a1a2aian#X#Tj分分析析栈栈Sk总控程序总控程序预测分析表预测分析表输出v输入缓冲区输入缓冲区 Tj 中存放待分析的输入符号串，它以右界符中存放待分析的输入符号串，它以右界符#作为结束。作为结束。v分析栈分析栈 Sk 中存放替换当前非终结符的某种规则右部符号串，句子括号中存放替换当前非终结符的某种规则右部符号串，句子括号#存入栈存入栈底。底。v预测分析表预测分析表 M 是预测分析法的关键，通常是一个是预测分析法的关键，通常是一个MA，a 形式的矩阵，其中形式的矩阵，其中 A VN，aVT 或或#。元素。元素 MA，a 中存放着一条关于中存放着一条关于 A 的产生式，指出当的产生式，指出当 A 面临输入符号面临输入符号 a 时应采用的候选式；时应采用的候选式；MA，a 中也可能存放出错标志中也可能存放出错标志(有时用空白有时用空白表示表示)，指出，指出 A 面临面临 a 是一种错误。是一种错误。第59页/共74页60预测分析程序工作过程#第60页/共74页总控程序在分析过程中对于任何文法来说作用都是一样的，它根总控程序在分析过程中对于任何文法来说作用都是一样的，它根据栈顶符号据栈顶符号 X X 和当前输入指针和当前输入指针 IP IP 指向的符号指向的符号 a a 来决定下一步来决定下一步动作。每一步都将执行下列三种动作之一：动作。每一步都将执行下列三种动作之一：1)若若X=a=#，则宣布分析成功；，则宣布分析成功；2)若若X=a#，则则将将栈栈顶顶符符号号 X（终终结结符符）弹弹出出，让让 IP 指指针针指指向下一个输入符号；向下一个输入符号；3)若若 X 是是一一个个非非终终结结符符，则则查查看看分分析析表表 M。如如果果分分析析表表的的 MA,a 中中是是一一条条产产生生式式，则则先先将将栈栈顶顶符符号号 X（非非终终结结符符）弹弹出出，然然后后把把该该产产生生式式右右端端符符号号串串按按反反序序（从从右右到到左左）压压入入栈栈中中（串串不不入入栈栈），同同时时可可能能还还要要执执行行一一系系列列的的动动作作，比比如如建建立立语语法法树树、进进行行语语义义计计算算等等；如如果果分分析析表表的的 MA,a 中中是是出出错错标标志或空白，则执行相应的出错处理程序。志或空白，则执行相应的出错处理程序。栈栈 STACK 用于存放文法符号。分析开始时，将用于存放文法符号。分析开始时，将#压入栈底，压入栈底，然后压入文法开始符。还假定输入串以然后压入文法开始符。还假定输入串以#符号结尾。分析工作符号结尾。分析工作结束的标志是，栈中只有结束的标志是，栈中只有#符号，符号，IP 指针也指向指针也指向#符号。符号。第61页/共74页总控程序总控程序：包括三种动作：成功、出栈且读下一符号、出栈且：包括三种动作：成功、出栈且读下一符号、出栈且产生式右部入栈。产生式右部入栈。BEGIN 首先把首先把#和文法开始符号依次推进和文法开始符号依次推进 STACK 栈；栈；把第一个输入符号读进把第一个输入符号读进 a；FLAG=TRUE;WHILE FLAG DO BEGIN 把把 STACK 栈顶符号弹出放进栈顶符号弹出放进X中；中；IF XVT THEN IF X=a THEN 把下一个符号读进把下一个符号读进 a ELSE ERROR ELSE IF X=#THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MA,a=XX1 X2.XK THEN 把把 Xk,Xk-1,X1 一一压入一一压入 STACK 栈栈 /*若若X1 X2.XK=，什么也不压栈，什么也不压栈*/ELSE ERROR END OF WHILE STOPEND第62页/共74页63预测分析表的构造输入：文法输入：文法 G G输出：预测分析表输出：预测分析表方法：方法：假假设设a表表示示每每个个终终结结符符或或#号号。若若a SELECT(A-),则则将将A放放入入MA，a中中。将将所所有有无无定定义义的的