同济大学编译原理第四章语法分析——自上而下分析

1、第四章 语法分析 自上而下分析内容线索n语法分析器的功能语法分析器的功能n自上而下分析方法概述自上而下分析方法概述nLL（1）分析方法）分析方法n递归下降分析程序递归下降分析程序n预测分析程序预测分析程序语法分析器n语法分析的任务语法分析的任务 ：对任一给定对任一给定 w VT*，判断，判断 w L(G)?n 语法分析器：按照产生式规则，做识别语法分析器：按照产生式规则，做识别w的工作的工作词法分析器词法分析器语法分析器语法分析器编译程序后续部分编译程序后续部分符号表符号表源程序源程序单词符号单词符号取下一个取下一个单词符号单词符号语法分析树语法分析树语法分析器在编译程序中的地位语法分析器在编

2、译程序中的地位语法分析方法n自上而下分析自上而下分析 LL（1）分析法）分析法 递归下降分析法递归下降分析法 预测分析法预测分析法n自下而上分析自下而上分析 算符优先分析法算符优先分析法 LR分析法分析法从文法的开始符号出发，反从文法的开始符号出发，反复使用各种产生式，寻找与复使用各种产生式，寻找与输入符号匹配的最左推导。输入符号匹配的最左推导。从输入符号串开始，逐步进从输入符号串开始，逐步进行归约（最右推导的逆过行归约（最右推导的逆过程），直至归约到文法的开程），直至归约到文法的开始符号。始符号。内容线索语法分析器的功能语法分析器的功能n自上而下分析方法概述自上而下分析方法概述nLL（1）分

3、析方法）分析方法n递归下降分析程序递归下降分析程序n预测分析程序预测分析程序自上而下分析n从文法的开始符号出发，向下推导，推出从文法的开始符号出发，向下推导，推出句子句子n对任何的输入串对任何的输入串(单词符号单词符号)，试图用一切可，试图用一切可能的办法能的办法, 从文法的开始符号出发，自上而从文法的开始符号出发，自上而下地为输入串建立一棵语法树，即为输入下地为输入串建立一棵语法树，即为输入串寻找一个最左推导。串寻找一个最左推导。语法分析示例GS: Sid:=E EE+E EE*E E-E E (E) Eidid:=-id+id+id 是否为是否为GS的句子？的句子？S id:=E id:=

4、 -E id:= - E+E id:= - id+E id:= - id+E+E id:= - id+id+E id:= - id+id+id例例. 设文法设文法GS： SxAy，A*SxA y* *推导过程：推导过程： S xAy x*y(回溯回溯) x*y(成功成功)用用A*用用A* (成功成功) (回溯回溯)判定输入串判定输入串 x * y是否为它的句子是否为它的句子?x * y用用SxAy SxA ySxA y*例例GS: Sid:=E EE+E EE*E E-E E (E) Eidid:=-id+id+id 是否为是否为GS的句子？的句子？S id:=E id:= -E id:= -

5、 E+E id:= - E+E +E id:= - E+E +E+E 。带回溯自上而下分析面临的问题n虚假匹配虚假匹配问题问题n回溯回溯回溯会引起时间和空间的大量消耗回溯会引起时间和空间的大量消耗n文法的文法的左递归左递归问题问题一个文法是含有左递归的，如果存在非终结符一个文法是含有左递归的，如果存在非终结符P P P含有左递归的文法将使自上而下的分析过程陷入无限循环含有左递归的文法将使自上而下的分析过程陷入无限循环n报告分析不成功时，难于知道输入串中出错的确切位置。报告分析不成功时，难于知道输入串中出错的确切位置。实际上采用了一种实际上采用了一种穷尽一切可能的试探法穷尽一切可能的试探法，因此

6、效率很低，因此效率很低，代价很高代价很高+内容线索n语法分析器的功能语法分析器的功能n自上而下分析方法概述自上而下分析方法概述LL（1）分析方法）分析方法n递归下降分析程序递归下降分析程序n预测分析程序预测分析程序nLL（1）分析中的错误处理）分析中的错误处理LL(1)分析法n从左从左(Left)到右扫描输入串；构造最左到右扫描输入串；构造最左(Leftmost)推导；分析时每步向前看一个推导；分析时每步向前看一个(1)字符。字符。n目的：构造不带回溯的自上而下分析算法目的：构造不带回溯的自上而下分析算法左递归的消除左递归的消除消除回溯，提左因子消除回溯，提左因子FIRST集合，集合，FOLL

7、OW集合集合LL(1)分析条件分析条件LL(1)分析方法分析方法左递归文法n一个文法含有下列形式的产生式时，一个文法含有下列形式的产生式时， a)直接递归直接递归 AA A VN, V* b)间接递归间接递归 AB B A A,B VN, ， V* 称为称为左递归文法左递归文法。n 如果一个如果一个 文法是左递归时，则不能采用自顶向下分析法。文法是左递归时，则不能采用自顶向下分析法。例例2. 文法文法 P1aP2 P1P2b P2P1c P2d是间接左递归是间接左递归例例1. 文法文法S Sa S b 是直接左递归是直接左递归 语言是：语言是：L ban | n0消除直接左递归P P（，不以不

8、以P开头）开头）P PP P 例例. 文法文法EE+TT TT*FF F(E)i ETEE TE TFT T *FT F(E)i n一般地一般地, 假定假定P关于的产生式是关于的产生式是 PP1P2 Pm 1 2 n 其中：其中：i，i不以不以P开头，开头， 则改写为则改写为: P 1 P 2 P .n P P 1 P 2 P m P 消除左递归的算法思想P2P1P3 P1P3d文法文法 P2P1b P3P2c P3P2c P1bc P3dbc文法文法 P1P3d P2P1b P2P1P3消除左递归算法（1） 排序排序: P1、P2、 、Pn（2） FOR i := 1 TO n DO BEG

9、IN FOR j:= 1 TO i -1 DO 把形如把形如PiPj的规则改写为：的规则改写为： Pi12 k 其中：其中： Pj 1 2 k 是关于是关于Pj 的所有规则的所有规则; 消除关于消除关于Pi 规则的直接左递归。规则的直接左递归。 END（3） 化简化简: 删除永不使用的产生式删除永不使用的产生式算法示意P2P1P3 P1P3d文法文法 P2P1b P3P2c P3P2c P3dbc文法文法 P1P3d P2P1b P3db P2P1P3例例.文法文法GP3: P3P2c|c P2P1b|b P1P3a|a有推导：有推导：P3 P2c P1bc P3abc, 存在左递归。存在左递

10、归。按按P1(1)、P2(2)、P3(3)排序，执行算法得：排序，执行算法得：i=1，j从从1至至0，P1的产生式的产生式P1P3a|a无直接左递归，无需消除直接左递无直接左递归，无需消除直接左递归。归。i=2，j从从1至至1，P2的候选式含的候选式含P1，P1的产生式代入的产生式代入P2的产生式得：的产生式得：P2P3ab|ab|b，无直接左递归。，无直接左递归。i=3，j从从1至至2: j=1，P3的候选式不含的候选式不含P1，所以无需替换；，所以无需替换； j=2，P3的候选式含的候选式含P2，将，将P2P3ab|ab|b代入代入S的候选式得：的候选式得：P3P3abc|abc|bc|c

11、 再消除直接左递归得：再消除直接左递归得：P3abcP3| bcP3| cP3P3abcP3|消除无用产生式：消除无用产生式：P2P3ab|ab|b，P1P3a|a，得文法：得文法： P3abcP3| bcP3| cP3 P3abcP3|文法对应的正规式：文法对应的正规式：V1=(abc|bc|c)(abc)* 。例例.文法文法GS: S Qc|c QRb|b RSa|a有推导：有推导：S Qc Rbc Sabc, 存在左递归。存在左递归。按按R(1)、Q(2)、S(3)排序，执行算法得：排序，执行算法得：i=1，j从从1至至0，R的产生式的产生式RSa|a无直接左递归，无需消除直接左递归。无

12、直接左递归，无需消除直接左递归。i=2，j从从1至至1，Q的候选式含的候选式含R，R的产生式代入的产生式代入Q的产生式得：的产生式得：QSab|ab|b，无直接左递归。，无直接左递归。i=3，j从从1至至2: j=1，S的候选式不含的候选式不含R，所以无需替换；，所以无需替换； j=2，S的候选式含的候选式含Q，将，将QSab|ab|b代入代入S的候选式得：的候选式得：SSabc|abc|bc|c 再消除直接左递归得：再消除直接左递归得：SabcS| bcS| cSSabcS|消除无用产生式：消除无用产生式：QSab|ab|b，RSa|a，得文法：得文法： SabcS| bcS| cS Sab

13、cS|文法对应的正规式：文法对应的正规式：V1=(abc|bc|c)(abc)* 。例例. 文法文法GS: S Qc|c QRb|b RSa|a解：解： 1）排序：）排序：S(1)、Q(2)、R(3) 2）代入得：）代入得： S Q cc Q R bb R Rbcabca | ca | a 消除直接左递归：消除直接左递归： S Q cc Q R bb R bcaR caR | aR R bcaR 消除隐含的左递归算法与非终极符排序方法无关消除隐含的左递归算法与非终极符排序方法无关回溯问题例如，有产生式：例如，有产生式：语句语句 if 条件条件 then 语句语句 else 语句语句 | whi

14、le 条件条件 do 语句语句 | begin 语句表语句表 end 若要寻找一个语句，那么关键字若要寻找一个语句，那么关键字 if，while，begin就提示某个替换式是唯一的替换式。就提示某个替换式是唯一的替换式。无回溯！无回溯！回溯问题例如，有产生式：例如，有产生式：语句语句 if 条件条件 then 语句语句 else 语句语句 | if 条件条件 then 语句语句 | while 条件条件 do 语句语句 | begin 语句表语句表 end 产生回溯！产生回溯！回溯原因若当前符号若当前符号 = a，下一步要展开，下一步要展开A ，而而 A 1|2|n ，怎样选择怎样选择i？（1

15、）以）以a为头的为头的i如果只有一个，则替换唯一；如果只有一个，则替换唯一；（2）若以）若以a为头有多个为头有多个i的，则替换不唯一，可的，则替换不唯一，可能需要回溯，这是文法的问题，应该变换文法。能需要回溯，这是文法的问题，应该变换文法。无回溯n对任何非终结符号对任何非终结符号A，用它匹配输入串时能够根，用它匹配输入串时能够根据当前输入，准确地指派一个候选式据当前输入，准确地指派一个候选式若匹配成功，则不虚假；若匹配成功，则不虚假；若匹配不成功，则其它的候选式也不会成功。若匹配不成功，则其它的候选式也不会成功。n 即当即当A执行匹配时，执行匹配时， A12 n 若若A面临的第一个输入符号为面

16、临的第一个输入符号为a，则应该准确地指派，则应该准确地指派某一个某一个i，其成败完全代表，其成败完全代表A，无需进行试探和回溯。，无需进行试探和回溯。文法的要求（1）不含左递归）不含左递归（2）对每个非终结符的候选式，其任何推导的头符号（终）对每个非终结符的候选式，其任何推导的头符号（终结符）集合两两不相交。结符）集合两两不相交。n以上条件（以上条件（2）可表示为：对文法的任一非终结符号）可表示为：对文法的任一非终结符号A，若，若 A12 n 则应有则应有 FIRST(i)FIRST(j) = ，i jn符号串符号串的的终结首符集终结首符集FIRST () 定义为：定义为：FIRST() =

17、a a , aVT 特别地，若特别地，若 ，则规定，则规定FIRST ()。*回溯解决方法n提取公共左因子，将文法改造成任何非终结符的所有候选提取公共左因子，将文法改造成任何非终结符的所有候选首符集两两不相交。首符集两两不相交。A 12 n 1 2 m （其中（其中1 、 2 、 、 m不以不以开头）开头）A A 1 2 mA 12 n例例. 文法文法G：SaSb|aS| 解：提取：解：提取：S aS( b|) S引入新符：引入新符：S aSA|A b|例例. 对文法对文法G2： A ad A Bc B aA B bB解：先替换为：解：先替换为：A adA aAcA bBcB aAB bB再提

18、取再提取A a（Ac|d)A bBcB aAB bB引入新符引入新符A aAA bBcA Ac|d B aAB bB一般地，经过反复提取左因子可把每一个非终一般地，经过反复提取左因子可把每一个非终结符的所有候选首符集变成两两不相交。结符的所有候选首符集变成两两不相交。LL（1）分析条件n若文法已经消除了左递归，且对每个非终结符满若文法已经消除了左递归，且对每个非终结符满足足FIRST(i)FIRST(j) = 是否就解决了是否就解决了虚假匹配虚假匹配和和回溯回溯的问题？的问题？n对某个输入符号对某个输入符号a，及待匹配的非终结符，及待匹配的非终结符A（A12 n）a属于某个候选式的属于某个候选

19、式的FIRST集合集合a不属于任何候选式的不属于任何候选式的FIRST集合，即对任意集合，即对任意i，a FIRST (i) S aA abAS abS abd这是因为这是因为A有产生式有产生式A,而从开始符号而从开始符号S可以得出可以得出 S Ad *示例例例. G(S):S aA|d输入符号串输入符号串abd是否为句子？是否为句子？ A bAS|d| SaAbASdFIRST(S)=a, dFIRST(A) =b, d，S aA abAS abdS 。FOLLOWn设设S是文法是文法G的开始符号，对的开始符号，对G的任何非终结符的任何非终结符A，定义定义A的后继终结符号集的后继终结符号集为

20、：为：FOLLOW（A） aS Aa , aVT n特别地特别地,若若S A，则规定，则规定FOLLOW(A)。FOLLOW(A)是所有句型中出现在紧接是所有句型中出现在紧接A之后的终结之后的终结符或符或“”。*结论n当非终结符当非终结符A面临输入符号面临输入符号a，且，且a FIRST(i) (对任意对任意i)时，如果时，如果A的某个候选首符集包含的某个候选首符集包含（即（即FIRST（A），那么，当），那么，当aFOLLOW（A）时，就允许）时，就允许A自动自动匹配（即选用匹配（即选用A工作），否则，认为工作），否则，认为a的出现是一种语的出现是一种语法错误。法错误。n要正确进行不带回溯的

21、语法分析，文法应满足的第三个条要正确进行不带回溯的语法分析，文法应满足的第三个条件可表示为：若件可表示为：若A的候选首符集中包含的候选首符集中包含，则，则 FIRST (A) FOLLOW (A) = LL（1）文法n如果文法如果文法G满足以下条件：满足以下条件：（1）文法消除了左递归；文法消除了左递归；（2）文法中每个非终结符）文法中每个非终结符A的各个产生式的候选首符集两两的各个产生式的候选首符集两两不相交，即不相交，即 若若 A12 n ， 则则 FIRST(i)FIRST(j) = ，（，（i j）；）；（3）对文法中的每个非终结符）对文法中的每个非终结符A，若它存在某个候选首符集，若

22、它存在某个候选首符集中包含中包含，则，则FIRST(A) FOLLOW(A) = ，则称该文法则称该文法G为为LL(1)文法文法。LL（1）分析方法n对一个对一个LL（1）文法，可以对某个输入串进行有效的无回）文法，可以对某个输入串进行有效的无回溯的自上而下分析。溯的自上而下分析。n设面临的输入符号为设面临的输入符号为a，要用非终结符，要用非终结符A进行匹配，且进行匹配，且A12 n ，则可如下分析，则可如下分析: （1）若）若aFIRST (i) ，则指派，则指派i执行匹配任务；执行匹配任务； （2）否则）否则 1）若）若FIRST(A)，且，且aFOLLOW (A)，则让，则让A 与与自动匹配；自动匹配； 2）否则，）否则，a的出现是一种语法