编译原理-第四章

1、编译原理编译原理第四章第四章 语法分析语法分析(自上而下分析自上而下分析)王金伟计算机与信息工程学院天津师范大学TJNU-COCIE-WJW22022-3-18第四章第四章 语法分析语法分析(自上而下分析自上而下分析)n4.1 上下文无关文法上下文无关文法n4.2 带回溯的自上而下语法分析带回溯的自上而下语法分析n4.3 LL(1)分析法分析法n4.4 递归下降分析程序构造递归下降分析程序构造n4.5 预测分析程序预测分析程序TJNU-COCIE-WJW32022-3-18n语法分析的任务语法分析的任务在词法分析识别出单词符号串的基础上，分析并在词法分析识别出单词符号串的基础上，分析并判定程序

2、的语法结构是否符合语法规则。判定程序的语法结构是否符合语法规则。n语法分析器语法分析器执行语法分析的程序称为语法分析器执行语法分析的程序称为语法分析器其功能是其功能是n输入：由单词符号组成的有限序列输入：由单词符号组成的有限序列n输出：语法范畴输出：语法范畴(语法单位语法单位)TJNU-COCIE-WJW42022-3-18n语法分析的方法语法分析的方法自上而下分析法自上而下分析法(由文法开始符号推出句子由文法开始符号推出句子)n一般分析方法一般分析方法(穷举，带回溯穷举，带回溯)n递归下降分析法递归下降分析法(消除左递归，不带回溯消除左递归，不带回溯)n预测方法预测方法(LL(1)方法，一张

3、分析表和一个栈方法，一张分析表和一个栈)自下而上分析法自下而上分析法(由输入串开始逐步归约到文法由输入串开始逐步归约到文法开始符号开始符号)n算符优先分析法算符优先分析法nLR分析法分析法TJNU-COCIE-WJW52022-3-18语法分析器在编译程序中的核心地位语法分析器在编译程序中的核心地位语法分析器语法分析器词法分析器词法分析器编译程序编译程序后续部分后续部分符号表符号表单词符号单词符号取下一个取下一个单词符号单词符号语法分析树语法分析树 源程序源程序TJNU-COCIE-WJW62022-3-184.1 上下文无关文法上下文无关文法1.文法文法是描述语言的语法结构的形式规则（语法规

4、则）是描述语言的语法结构的形式规则（语法规则）：自然语言句子的主谓宾结构自然语言句子的主谓宾结构一、一、文法概述文法概述TJNU-COCIE-WJW72022-3-182.上下文无关文法上下文无关文法(1)它所定义的语法范畴（或语法单位）是完全独它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的（与它所在的上立于这种范畴可能出现的环境的（与它所在的上下文无关）下文无关）：程序设计语言中的一个算术表达式：程序设计语言中的一个算术表达式A*B(2)自然语言中不适合于上下文无关文法自然语言中不适合于上下文无关文法：汉语中的：汉语中的“打打”字是一个泛义动词字是一个泛义动词“打毛衣打

5、毛衣” “编织编织”“打篮球打篮球” “玩玩”“打水打水” “取得取得”(3)对于程序设计语言来说用上下文无关的文法来对于程序设计语言来说用上下文无关的文法来描述就足够了描述就足够了TJNU-COCIE-WJW82022-3-181.：有一个由英语单词组成的一个单词串：有一个由英语单词组成的一个单词串The boy sees the girl 用用表示表示“由由组成组成”或或“定义为定义为”，定义一些，定义一些语法规则语法规则theboygirlsees二、二、文法和语言的形式定义文法和语言的形式定义TJNU-COCIE-WJW92022-3-181.问题：问题：The boy sees th

6、e girl是不是一个语法上正确的句子？是不是一个语法上正确的句子？思想：是否可以利用我们定义的这些语法规则推思想：是否可以利用我们定义的这些语法规则推导出这个句子导出这个句子方法：从方法：从出发，反复把上述规则中的出发，反复把上述规则中的“”左边成分替换成右边成分左边成分替换成右边成分TJNU-COCIE-WJW102022-3-18推导过程推导过程：=The =The boy =The boy =The boy sees =The boy sees =The boy sees the=The boy sees the girltheboygirlseesTJNU-COCIE-WJW1120

7、22-3-18n也可以用语法分析树来表示这种推导也可以用语法分析树来表示这种推导 The boy sees the girlTJNU-COCIE-WJW122022-3-182. 引出几个概念引出几个概念(1)终结符号终结符号不带尖括号的部分，就是单词符号，语法分析角不带尖括号的部分，就是单词符号，语法分析角度是不可再分的基本符号度是不可再分的基本符号： the、 boy、 sees、 girl等等：基本字、标识符、常数、算符和界符等：基本字、标识符、常数、算符和界符等TJNU-COCIE-WJW132022-3-18(2)非终结符号非终结符号带尖括号的部分，代表一类语法成分带尖括号的部分，代

8、表一类语法成分(语法范畴语法范畴)：、 、 、等等：算数表达式、布尔表达式、赋值语句、：算数表达式、布尔表达式、赋值语句、分程序、过程等分程序、过程等TJNU-COCIE-WJW142022-3-18(3)开始符号开始符号(识别符号，纲符号识别符号，纲符号)A.指定一个非终结符号为开始符号，表示推导从它指定一个非终结符号为开始符号，表示推导从它开始开始B.代表所定义语言中我们最感兴趣的语法范畴代表所定义语言中我们最感兴趣的语法范畴C.是由其他语法范畴构造起来的是由其他语法范畴构造起来的： 句子句子句子是由主语、谓语、宾语这些语法范畴构成的句子是由主语、谓语、宾语这些语法范畴构成的前面说的前面说

9、的：程序：程序程序是由分程序、过程这些语法范畴构成的程序是由分程序、过程这些语法范畴构成的TJNU-COCIE-WJW152022-3-18(4)产生式产生式(产生规则、规则产生规则、规则)是定义语法范畴的一种书写规则，是定义语法范畴的一种书写规则，形式为：形式为： AA是某个非终结符号是某个非终结符号, 称为称为产生式的左部产生式的左部，可以是终结符号可以是终结符号,也可以是非终结符号，还可以是也可以是非终结符号，还可以是终结符号和非终结符号组成的任意符号串，称为终结符号和非终结符号组成的任意符号串，称为产生式的右部产生式的右部： the boy girl seesTJNU-COCIE-WJ

10、W162022-3-183.上下文无关文法的形式定义上下文无关文法的形式定义上下文无关文法上下文无关文法G G定义为定义为四元式四元式( (V VT T，V VN N，S S，P P) )V VT T是非空有限集，是终结符号集合，它的每个元素是非空有限集，是终结符号集合，它的每个元素称为终结符号，用小写字母表示。称为终结符号，用小写字母表示。V VN N是非空有限集，是非终结符号集合，它的每个元是非空有限集，是非终结符号集合，它的每个元素称为非终结符号，用大写字母表示，并且素称为非终结符号，用大写字母表示，并且V VN NVVT T=S S V VN N ，是一个开始符号，也称为是识别符号，是

11、，是一个开始符号，也称为是识别符号，是一个非终结符，至少在一个产生式作为左部出现一个非终结符，至少在一个产生式作为左部出现P P是一个产生式的集合是一个产生式的集合( (有限有限) )，它的每个元素称为，它的每个元素称为一条产生式一条产生式( (一条规则一条规则) )，形式：，形式：P其中其中P V VN N ， (V VN NV VT T)*TJNU-COCIE-WJW172022-3-18：设有文法：设有文法G (V(VT T，V VN N，S S，P)P)，其中，其中V VT T=i=i，+ +，* *，（，），（，） V VN N=E=ES = ES = EP P：E i E E +

12、E E E * E E (E)其中其中i代表变量代表变量描述了一类由变量和描述了一类由变量和+*运算组成的算数表达式文法运算组成的算数表达式文法TJNU-COCIE-WJW182022-3-18：(1)文法的核心是一组产生式，而开始符号文法的核心是一组产生式，而开始符号S是文法所要识别的语法范畴（语法单位）是文法所要识别的语法范畴（语法单位）(2)若有这样一些左部相同的产生式：若有这样一些左部相同的产生式：P1P2Pn可以合并为一个，缩写成可以合并为一个，缩写成P1 | 2 | | n其中每个其中每个i 称为称为P的一个候选式，的一个候选式，|读作读作“或或”：P P：E i | E+E |

13、E*E | (E)TJNU-COCIE-WJW192022-3-18：设有文法设有文法G (V(VT T，V VN N，S S，P)P)，其中，其中V VT T=i=i，+ +，* * V VN N=E=E，AAS = ES = EP P：E i | EAE A + | + | * *：这里：这里P P有有4 4条产生式规则。条产生式规则。TJNU-COCIE-WJW202022-3-184.推导推导(1)(1)直接直接( (一次一次) )推导推导 =设一个文法设一个文法G(V(VT T，V VN N，S S，P)P),(V VN NV VT T)* (,是终结符或是终结符或非终结符或终结符和

14、非终结符组非终结符或终结符和非终结符组成的任意符号串成的任意符号串)且，且， A是是G的一个产生式，如果有的一个产生式，如果有 A = 就称就称A直接推导出直接推导出：推导是用产生式的右部替换产生式的左部：推导是用产生式的右部替换产生式的左部TJNU-COCIE-WJW212022-3-18(2) (2) 1 到到n的推导的推导如果如果1 = 2 = = n则称这个序列是从则称这个序列是从1 到到n的一个推导的一个推导 1 n从从1 出发经过出发经过1步或若干步推出步或若干步推出n1 n从从1 出发经过出发经过0步或若干步推出步或若干步推出n：1 n1 = n1 n*TJNU-COCIE-WJ

15、W222022-3-18：设有文法：设有文法G P P：E i | E+E | E*E | (E)求从求从E到到( i * i + i )的推导的推导解：解：E = (E) = (E+E) = (E*E+E) = (i*E+E) = (i*i+E) = (i*i+i)TJNU-COCIE-WJW232022-3-18：常用的推导有两种：常用的推导有两种(1)最左推导最左推导任何一步任何一步 = 都对都对最左边最左边的那个的那个非终结符号非终结符号进行替换进行替换：E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)(2)最右推导最右推导任何一步任何一步 = 都

16、对都对最右边最右边的那个的那个非终结符号非终结符号进行替换进行替换： E=(E)=(E+E)=(E+i)=(E*E+i)=(E*i+i)=(i*i+i)TJNU-COCIE-WJW242022-3-185.句型句型设设G G是一个文法，是一个文法，S S是它的开始符号，如果是它的开始符号，如果S S ，且，且(V VN NV VT T)* 则称则称是是G的一个句型的一个句型6.句子句子设设G G是一个文法，是一个文法，S S是它的开始符号，如果是它的开始符号，如果S S ，且，且 V VT T* 则称则称是是G的一个句子的一个句子：(1)句子实际上是仅含有终结符号的句型句子实际上是仅含有终结符

17、号的句型(2)从一个句型到另一个句型的推导过程不唯一从一个句型到另一个句型的推导过程不唯一*TJNU-COCIE-WJW252022-3-18：设有文法：设有文法G (V(VT T，V VN N，S S，P)P)，其中，其中P P：E i | E+E | E*E | (E)V VT T=i=i，+ +，* *，（，），（，） ； V VN N=E=E； S = ES = E推导推导( i * i + i )解解：E = (E) = (E+E) = (E*E+E) = (i*E+E) = (i*i+E) = (i*i+i)(句型句型)(句型句型)(句型句型)(句型句型)(句型句型)(句型句型)(

18、句型句型,句子句子)TJNU-COCIE-WJW262022-3-187.语言语言文法文法G G所产生的句子的全体就是一个语言，记为所产生的句子的全体就是一个语言，记为L(G)L(G)L(G)=L(G)= | S & V VT T* 8.8.文法和语言的关系文法和语言的关系(1)(1)给定一个文法，就能从结构上唯一确定其语言给定一个文法，就能从结构上唯一确定其语言G-G-L(G)L(G)( (唯一的唯一的) )(2)(2)给定一种语言，能找到其文法，但该文法不是唯一给定一种语言，能找到其文法，但该文法不是唯一的，即的，即L-L-G1 G1 或或 G2 G2 或或 TJNU-COCIE-WJW2

19、72022-3-18：设有文法：设有文法G (V(VT T，V VN N，S S，P)P)，其中，其中V VT T=a ,b=a ,b； V VN N=Z=Z； S = ZS = ZP P：Z aZb Z ab试构造其语言试构造其语言解解：因为因为Z = aZb = a2Zb2 = a3Zb3 = = an-1Zbn-1 = anbn所以所以L(G) = anbn | n1TJNU-COCIE-WJW282022-3-18：已知语言：已知语言L(G) = abna | n1可构造文法可构造文法G1：P P：S aBa B bB | b还可构造文法还可构造文法G2：P P：S aBa B Bb

20、| bTJNU-COCIE-WJW292022-3-181.语法分析树语法分析树用一棵树来表示句型的推导，简称语法树用一棵树来表示句型的推导，简称语法树三、三、语法分析树与二义性语法分析树与二义性TJNU-COCIE-WJW302022-3-18：设有文法：设有文法G 为为E i | E+E | E*E | (E)推导推导： (i*i+i)解：解： E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i) E第第1代代 ( E )第第2代代 E + E第第3代代 E * E第第4代代第第5代代iiiTJNU-COCIE-WJW312022-3-182. 句子的二义

21、性句子的二义性若一个文法的一个句子对应两棵不同的语法树，若一个文法的一个句子对应两棵不同的语法树，则称该句子是二义性句子则称该句子是二义性句子：有个句子：手提包：有个句子：手提包 手手 提提 包包TJNU-COCIE-WJW322022-3-183.文法的二义性文法的二义性如果一个文法含有二义性的句子，则称该文法是如果一个文法含有二义性的句子，则称该文法是二义性文法二义性文法TJNU-COCIE-WJW332022-3-18E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i) E ( E ) E + EE * Eiii：设有文法：设有文法G 为为E i | E

22、+E | E*E | (E)推导推导： (i*i+i)E=(E)=(E*E)=(i*E)=(i*E+E)=(i*i+E)= (i*i+i)E ( E ) E * E E + EiiiTJNU-COCIE-WJW342022-3-18对于上例，规定对于上例，规定*比比+优先级高，且都服从左结合优先级高，且都服从左结合构造无二义性的文法构造无二义性的文法G 为为E T | E + T，T F | T * F ，F (E) | i，推导，推导： (i*i+i)E=T=F=(E)=(E+T)=(T*F+T)=(F*F+T)=(i*F+T)=(i*i+T)=(i*i+F)=(i*i+i)ETF( E )

23、E + TT * FFiiiFTJNU-COCIE-WJW352022-3-18n乔姆斯基形式语言理论：乔姆斯基形式语言理论：19561956年建立，发展至今，年建立，发展至今，对产生式加以不同限制得到对产生式加以不同限制得到4 4种类型的文法：种类型的文法：0 0型型1 1型型2 2型型3 3型型四、四、文法分类文法分类TJNU-COCIE-WJW362022-3-180 0型文法型文法也称为短语结构文法也称为短语结构文法l定义：设定义：设G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每个产生式，如果它的每个产生式是这样一种结构：是这样一种结构：(V(VN NVVT T)

24、 )* *且至少含有且至少含有一个非终结符，而一个非终结符，而(V(VN NVVT T) )* * ，则，则G G是一个是一个0 0型型文法文法l任何任何0 0型语言都是递归可枚举的，而递归可枚举集型语言都是递归可枚举的，而递归可枚举集必定是一个必定是一个0 0型语言型语言l其它三类文法都是对其它三类文法都是对0 0型文法产生式的形式作某些型文法产生式的形式作某些限制得到的限制得到的TJNU-COCIE-WJW372022-3-181 1型文法型文法：也称为上下文有关文法也称为上下文有关文法l定义：设定义：设G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每个产生式有如，如果

25、它的每个产生式有如下形式：下形式：x xAyxyAyxy，AVAVN N，(V(VN NVVT T) )+ +， x x、y(Vy(VN NVVT T) )* *，则，则G G是一个是一个1 1型文法型文法l对非终结符进行替换时必须考虑上下文，对非终结符进行替换时必须考虑上下文，A A只有在只有在x x和和y y这样的上下文环境中才能替换为这样的上下文环境中才能替换为l另一种定义：设另一种定义：设G=(VG=(VN N,V,Vt t,P,S),P,S)，如果它的每个产生，如果它的每个产生式式满足满足|=|=|，则，则G G是一个是一个1 1型文法；把型文法；把产生式产生式SS作为产生式的特例加

26、入作为产生式的特例加入1 1型文法的产生型文法的产生式集合中，但式集合中，但S S不能出现在产生式的右部不能出现在产生式的右部l1 1型文法对程序设计语言的应用来说一般太复杂了，型文法对程序设计语言的应用来说一般太复杂了，难于应用难于应用TJNU-COCIE-WJW382022-3-182 2型文法型文法也称为上下文无关文法也称为上下文无关文法l定义：设定义：设G=(VG=(VN N,V,VT T,P,S),P,S)，如果它的每个产生式，如果它的每个产生式有如下形式：有如下形式：A A，AVAVN N，(V(VN NVVT T) )* *，则，则G G是一个是一个2 2型文法型文法l2 2型文

27、法等价于下推自动机（语法分析）型文法等价于下推自动机（语法分析）l2 2型文法有足够能力来描述现今的多数程序设计型文法有足够能力来描述现今的多数程序设计语言的语法结构语言的语法结构l我们今后主要讨论我们今后主要讨论2 2型文法，就是上下文无关的型文法，就是上下文无关的文法，今后所说的文法，如无特别声明，就是指文法，今后所说的文法，如无特别声明，就是指上下文无关的文法上下文无关的文法TJNU-COCIE-WJW392022-3-183 3型文法型文法也称为正规文法、正则文法、线性文法也称为正规文法、正则文法、线性文法l定义：设定义：设G=(VG=(VN N,V,VT T,P,S),P,S)，如果

28、它的每个产生式，如果它的每个产生式有如下形式：有如下形式：AaBAaB或或AaAa，其中，其中A A、BVBVN N，aVaVT T，则，则G G是一个是一个3 3型文法型文法l3 3型文法等价于有限自动机型文法等价于有限自动机l上述定义给出的定义是右线性文法，如果产生式上述定义给出的定义是右线性文法，如果产生式的形式是：的形式是： ABaABa或或AaAa，则称为左线性文法，则称为左线性文法l3 3型文法常用于编译器的词法分析程序的构造型文法常用于编译器的词法分析程序的构造TJNU-COCIE-WJW402022-3-184.2 带回溯的自上而下语法分析带回溯的自上而下语法分析就是从文法开始

29、符号出发，向下推导，最后推导就是从文法开始符号出发，向下推导，最后推导出句子出句子一、自上而下语法分析一、自上而下语法分析TJNU-COCIE-WJW412022-3-181.基本思想基本思想对任何一个输入串，试图用一切可能的办法，从对任何一个输入串，试图用一切可能的办法，从文法的开始符号文法的开始符号(根节点根节点)出发，根据文法自上而出发，根据文法自上而下地为输入串建立一棵语法树，即为输入串寻找下地为输入串建立一棵语法树，即为输入串寻找一个最左推导。一个最左推导。思想本质思想本质：是一种试探过程，是反复使用不同产：是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。生式谋求匹配输入串

30、的过程。二、带回溯的自上而下语法分析二、带回溯的自上而下语法分析TJNU-COCIE-WJW422022-3-182.设有文法设有文法(1) S xAy(2) A * | *分析输入串分析输入串x*y。分析过程如下：分析过程如下：利用规则利用规则输入串输入串语法树语法树TJNU-COCIE-WJW432022-3-183.构造方法构造方法让每个非终结符号对应一个让每个非终结符号对应一个递归子程序递归子程序。每个子。每个子程序可以作为一个程序可以作为一个布尔过程布尔过程(返回返回“真真”或或“假假”)：(1)一旦发现该非终结符的某个候选式与输入串相一旦发现该非终结符的某个候选式与输入串相匹配，就

31、用这个候选式去扩展语法树，并返回匹配，就用这个候选式去扩展语法树，并返回“真真”值；值；(2)该候选式和输入串不匹配，则保持原来的语法该候选式和输入串不匹配，则保持原来的语法树和树和IP值不变值不变(IP回溯回溯)，并返回，并返回“假假”值值TJNU-COCIE-WJW442022-3-181.文法左递归文法左递归一个文法存是含有左递归的，如果存在非终结符一个文法存是含有左递归的，如果存在非终结符P，有有PP当试图用当试图用P P去匹配输入串时，在没有识别任何输入去匹配输入串时，在没有识别任何输入符号的情况下，又得重新要求符号的情况下，又得重新要求P P去进行新的匹配去进行新的匹配，这样一来，

32、这样一来，使推导无限循环下去。使推导无限循环下去。2.回溯问题回溯问题匹配不成功，需要回溯。但已经走了一大段错路，匹配不成功，需要回溯。但已经走了一大段错路，最后又必须回头，就需要把已经做过的一大堆工最后又必须回头，就需要把已经做过的一大堆工作作( (各种表格工作、语义分析等各种表格工作、语义分析等) )推倒重来，既费推倒重来，既费时又费力时又费力三、存在的困难和问题三、存在的困难和问题TJNU-COCIE-WJW452022-3-183.虚假匹配虚假匹配设有文法设有文法(1) S xAy(2) A * | *分析输入串分析输入串x*y。分析过程如下：分析过程如下：利用规则利用规则输入串输入串

33、语法树语法树x*y不能被识别不能被识别TJNU-COCIE-WJW462022-3-184.不易知道错误位置不易知道错误位置当最终报告分析不成功时，难于知道输入串中出当最终报告分析不成功时，难于知道输入串中出错的确切位置错的确切位置5.效率极低效率极低由于带回溯，实际上才用了一种穷尽一切可能的由于带回溯，实际上才用了一种穷尽一切可能的试探法，因此，效率很低，代价极高。该方法只试探法，因此，效率很低，代价极高。该方法只有理论意义，在实践上价值不大有理论意义，在实践上价值不大TJNU-COCIE-WJW472022-3-184.3 LL(1)分析法分析法目的目的：构造不带回溯的自上而下分析算法构造

34、不带回溯的自上而下分析算法要求要求：(1)消除文法的左递归性消除文法的左递归性(自上而下分析方法不允许文法含有左递归自上而下分析方法不允许文法含有左递归)(2)找出克服回溯的充分必要条件找出克服回溯的充分必要条件(不要回溯不要回溯)TJNU-COCIE-WJW482022-3-181.直接左递归直接左递归直接见于产生式的左递归称为直接左递归直接见于产生式的左递归称为直接左递归. .：产生式：产生式UU2.间接左递归间接左递归若有若有UU: :文法文法SAa|bSAa|bAAc|Sd|AAc|Sd|S=Aa=SdaS=Aa=Sda一、消除文法的左递归一、消除文法的左递归TJNU-COCIE-WJ

35、W492022-3-183.消除直接左递归消除直接左递归：设有产生式设有产生式PP|(1)其中其中不以不以P开头，开头，不为不为。那么，我们可以把。那么，我们可以把P的规则改为如下的非直接左递归形式：的规则改为如下的非直接左递归形式：PPPP|(2)(1)式和式和(2)式是等价的式是等价的TJNU-COCIE-WJW502022-3-18(续续)PP|(1)PPPP|(2)对于对于(1)式：式：P=P=P=P=对于对于(2)式：式：P=P=P=P=P= TJNU-COCIE-WJW512022-3-18：设有文法：设有文法GE E + T | T T T * F | F F (E) | i 消

36、除其产生式的直接左递归消除其产生式的直接左递归解：对于解：对于E E + T | T (P=E，=+T，=T)变成变成ETEE+TE|PP|-PP PP|同理：同理：ETEE+TE|TFTT*FT|F(E)|iTJNU-COCIE-WJW522022-3-18：设有文法：设有文法GE E + T | T T T * F | F F (E) | i E=E+T= E+T+T= E+T+T=T+T+TE=TE= T+TE= T+T+TE=T+T+TE =T+T+TETEE+TE|TFTT*FT|F(E)|iTJNU-COCIE-WJW532022-3-18消除直接左递归方法消除直接左递归方法：设有

37、产生式设有产生式PP1|P2|Pm|1|2|n其中每个其中每个i不以不以P开头，每个开头，每个i不为不为消除消除P的直接左递归性就是把这些规则改写成：的直接左递归性就是把这些规则改写成：P1P|2P|nPP1P| 2P|mP| TJNU-COCIE-WJW542022-3-18：消除直接左递归的代价是引进了若干非终结符和消除直接左递归的代价是引进了若干非终结符和产生式产生式用上述办法实际上把直接左递归变成直接右递归用上述办法实际上把直接左递归变成直接右递归PP|PPPP|上述办法不意味着可以消除整个文法的左递归性上述办法不意味着可以消除整个文法的左递归性：有文法：有文法 SQc | cQRb

38、| bRSa | a已经不具有直接左递归，但却是间接左递归的已经不具有直接左递归，但却是间接左递归的因为：因为：S=Qc =Rbc =SabcTJNU-COCIE-WJW552022-3-184.消除整个文法的左递归的算法消除整个文法的左递归的算法如果文法不含回路（形如如果文法不含回路（形如 的推导），也不含有以的推导），也不含有以为右部的产生式，则下面算法可以消除左递归为右部的产生式，则下面算法可以消除左递归(1)(1)把文法把文法G G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P P1 1,P,P2 2, ,P,Pn n；按此顺序执行；按此顺序执行(2)for i =

39、 1 to n do(2)for i = 1 to n do for j = 1 to i-1 do for j = 1 to i-1 do把形如把形如P Pi iPPj j的规则改写成的规则改写成: :P Pi i 1 1|2 2|k k。其中其中P Pj j1 1|2 2| |k k是关于是关于P Pj j的所有产生式的所有产生式 EndforEndfor 消除关于消除关于P Pi i的直接左递归的直接左递归EndforEndfor(3)(3)化简由化简由(2)(2)得到的文法：除去从开始符号无法达到的得到的文法：除去从开始符号无法达到的非终结符的产生式非终结符的产生式PPTJNU-COC

40、IE-WJW562022-3-18：考虑以下文法，消除其左递归性：考虑以下文法，消除其左递归性SQc | cQRb | bRSa | a解解：(1)把该文法的非终结符排列为把该文法的非终结符排列为R、Q、S.(2)对于对于R，不存在直接左递归，不用消除，不存在直接左递归，不用消除对于对于Q，把，把R代入到代入到Q的有关候选式后，把的有关候选式后，把Q的产生式改写为的产生式改写为QSab| ab | b现在现在Q不存在直接左递归，不用消除不存在直接左递归，不用消除对于对于S，把，把Q代读到代读到S的有关候选式后，把的有关候选式后，把S的产生式改写为的产生式改写为SSabc | abc | bc

41、| cS有直接左递归，消除有直接左递归，消除S的直接左递归为的直接左递归为SabcS | bcS | cSSabcS | TJNU-COCIE-WJW572022-3-18得到消除左递归性的文法为得到消除左递归性的文法为SabcS | bcS | cSSabcS | QSab| ab | bRSa | a(3)显然，显然，Q和和R的产生式已经是多余的，将它们去掉的产生式已经是多余的，将它们去掉化简后的文法是：化简后的文法是：SabcS | bcS | cSSabcS | ：由于对非终结符排序的不同，最后所得的文法在形式：由于对非终结符排序的不同，最后所得的文法在形式上可能不一样，但它们都是等价

42、的上可能不一样，但它们都是等价的TJNU-COCIE-WJW582022-3-18：考虑刚才的文法，消除其左递归性：考虑刚才的文法，消除其左递归性SQc | cQRb | bRSa | a解解：(1)把该文法的非终结符排列为把该文法的非终结符排列为S、Q、R(2)对于对于S，不存在直接左递归，不用消除，不存在直接左递归，不用消除对于对于Q，不存在直接左递归，不用消除，不存在直接左递归，不用消除对于对于R，把，把S代入到代入到R的有关候选式后，把的有关候选式后，把R的产生式改写为的产生式改写为RQca| ca | a把把Q代入到代入到R的有关候选式后，把的有关候选式后，把R的产生式改写为的产生式

43、改写为RRbca| bca | ca | aTJNU-COCIE-WJW592022-3-18RRbca| bca | ca | aR有直接左递归，消除有直接左递归，消除S的直接左递归为的直接左递归为RbcaR | caR | aRRbcaR | 得到消除左递归性的文法为得到消除左递归性的文法为SQc | cQRb | bRbcaR | caR | aRRbcaR | TJNU-COCIE-WJW602022-3-181.消除回溯的要求消除回溯的要求对文法的任何非终结符，当要它去匹配输入串时，对文法的任何非终结符，当要它去匹配输入串时，能够根据该非终结符所面临的输入符号准确地指派能够根据该非终

44、结符所面临的输入符号准确地指派它的一个候选式去匹配，并且此候选式匹配后得到它的一个候选式去匹配，并且此候选式匹配后得到的工作结果应该是确信无疑的，即：的工作结果应该是确信无疑的，即：(1)若该候选式匹配成功，那么该匹配不是虚假匹配若该候选式匹配成功，那么该匹配不是虚假匹配(2)若该候选式无法完成最终的匹配任务，则其他任若该候选式无法完成最终的匹配任务，则其他任何候选式肯定也无法完成何候选式肯定也无法完成二、消除回溯二、消除回溯TJNU-COCIE-WJW612022-3-18：假设当前轮到非终结符假设当前轮到非终结符A去匹配输入串，去匹配输入串，A的产生的产生式为式为A1|2|nA所面临的第一

45、个输入符号为所面临的第一个输入符号为a，如果，如果A指派指派i去匹去匹配，那么就肯定没有回溯。配，那么就肯定没有回溯。：这里这里A不再是让某个不再是让某个i去试探匹配，而是根据所面去试探匹配，而是根据所面临的输入符号的不同准确制定一个临的输入符号的不同准确制定一个i去匹配，若匹去匹配，若匹配到最后没能识别整个字串，则该字串一定不是该配到最后没能识别整个字串，则该字串一定不是该文法中的句子。文法中的句子。TJNU-COCIE-WJW622022-3-182.消除回溯的条件消除回溯的条件定义定义FIRSTFIRST集集令文法令文法G G是不含左递归的文法，对是不含左递归的文法，对G G的非终结符的

46、候的非终结符的候选选，定义它的开始符号（终结首符）集合：，定义它的开始符号（终结首符）集合：特别地，如果特别地，如果 ，则，则FIRST()FIRST()如果非终结符如果非终结符A A的任意两个候选式的任意两个候选式i i和和j j的开的开始符号集满足始符号集满足FIRST(FIRST(i i)FIRST()FIRST(j j)=)=，则，则A A可以根据所面临的第一个输入符号，准确地可以根据所面临的第一个输入符号，准确地指派一个候选式指派一个候选式去执行任务，去执行任务，是那个是那个FIRSTFIRST集含集含a a的候选式，即的候选式，即 a a FIRST()FIRST()Vaa., |

47、 a)FIRST(T*TJNU-COCIE-WJW632022-3-18：假设假设A的产生式为的产生式为A1|2|n当前输入符号为当前输入符号为b b，b bVT如果如果b b FIRST(FIRST(1 1) )，则用，则用1 1去匹配去匹配b b如果如果b b FIRST(FIRST(2 2) )，则用，则用2 2去匹配去匹配b b如果如果b b FIRST(FIRST(n n) )，则用，则用n n去匹配去匹配b bFIRST(FIRST(1 1)FIRST()FIRST(2 2)FIRST(FIRST(n n)=)=TJNU-COCIE-WJW642022-3-183.改造文法改造文法

48、 问题问题：对于许多程序设计语言的文法，都有产生式对于许多程序设计语言的文法，都有产生式语句语句if 条件条件 then 语句语句 else 语句语句| if 条件条件 then 语句语句这两个候选式的这两个候选式的FIRSTFIRST集合相交不为集合相交不为 TJNU-COCIE-WJW652022-3-183.改造文法改造文法(续续)改造方法改造方法：提取公共左因子：提取公共左因子假设假设A的产生式为的产生式为A1|2|n|1| | 2|m其中每个其中每个不以不以开头开头那么把这些产生式改写为那么把这些产生式改写为: :AA |1| | 2|mA1|2|n反复提取左因子反复提取左因子( (

49、包括对新引进的非终结符，例如包括对新引进的非终结符，例如A A) )TJNU-COCIE-WJW662022-3-18问题：问题：当一个文法不含左递归，并且满足每个非终结当一个文法不含左递归，并且满足每个非终结符的所有候选首符集两两不相交的条件，是不符的所有候选首符集两两不相交的条件，是不是一定能进行有效的自上而下分析了呢？是一定能进行有效的自上而下分析了呢？若空字若空字属于某个非终结符的候选式的首符集，属于某个非终结符的候选式的首符集，就会有问题就会有问题三、三、LL(1)分析条件分析条件TJNU-COCIE-WJW672022-3-181.引例引例对于消除左递归的文法对于消除左递归的文法E

50、TEE+TE|TFTT*FT|F(E)|i对输入串对输入串i+i进行分析进行分析FIRST(TE) = ( ，i FIRST(+TE) = + FIRST() = FIRST(FT) = ( ，i FIRST(*FT) = * FIRST() = FIRST(E) = ( FIRST(i) = i T自动匹配自动匹配 ，IP不动不动TJNU-COCIE-WJW682022-3-181.引例引例对于消除左递归的文法对于消除左递归的文法ETEE+TE|TFTT*FT|F(E)|i对输入串对输入串i ( 进行分析进行分析FIRST(TE) = ( ，i FIRST(+TE) = + FIRST()

51、= FIRST(FT) = ( ，i FIRST(*FT) = * FIRST() = FIRST(E) = ( FIRST(i) = i T自动匹配自动匹配 ，IP不动不动TJNU-COCIE-WJW692022-3-182.定义定义FOLLOW集集 对文法对文法G G的任何非终结符的任何非终结符A A，定义它的后继符号集合：，定义它的后继符号集合：特别地，如果特别地，如果S S A，则，则#FOLLOW(A)FOLLOW(A)FOLLOW(A)FOLLOW(A)集合是所有句型中出现在紧接集合是所有句型中出现在紧接A A之后之后的终结符号或的终结符号或# #所组成的集合所组成的集合当非终结符

52、当非终结符A A面临输入符号面临输入符号a a，且，且a a不属于不属于A A的任的任意候选式的意候选式的FIRSTFIRST集但集但A A的某个候选式的的某个候选式的FIRSTFIRST集集包含包含时，只有当时，只有当a FOLLOW(A)FOLLOW(A)，才可能允许，才可能允许A A自动匹配自动匹配Va.Aa.,S | aFOLLOW(A)T*TJNU-COCIE-WJW702022-3-183.不带回溯的自上而下分析的文法条件（不带回溯的自上而下分析的文法条件（LL(1)LL(1)文法）文法）(1)文法不含左递归文法不含左递归(2)对于文法中每一个非终结符对于文法中每一个非终结符A的各

53、个产生式的候选的各个产生式的候选式的式的FIRST集两两不相交。即，若集两两不相交。即，若A1|2|n则则FIRST(FIRST(i i)FIRST()FIRST(j j)=)= (i (ij) )(3)对于文法中的每个非终结符对于文法中的每个非终结符A，若它的某个候选首，若它的某个候选首符集包含符集包含,则则FIRST(A)FOLLOW(A)=FIRST(A)FOLLOW(A)=如果一个文法如果一个文法G G满足以上条件，则称该文法满足以上条件，则称该文法G G为为LL(1)LL(1)文文法法( (第第1 1个个L L代表从左到右扫描输入串，第代表从左到右扫描输入串，第2 2个个L L代表最

54、左代表最左推导，推导，1 1表示分析时每一步只看表示分析时每一步只看1 1个符号个符号) )TJNU-COCIE-WJW712022-3-184.不带回溯的自上而下分析的方法不带回溯的自上而下分析的方法对于对于LL(1)LL(1)文法，假设要用非终结符文法，假设要用非终结符A A进行匹配，进行匹配，面临输入符号为面临输入符号为a a，A A的所有产生式为的所有产生式为A1|2|n(1)若若a FIRST(FIRST(i i) ) ，则指派，则指派i i去匹配去匹配(2)若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则：若若属于某个属于某个 FIRST(FIRST(i i) )且

55、且aFOLLOW(A)FOLLOW(A)，则让则让A A与与自动匹配；自动匹配；否则，否则，a的出现是一种语法错误的出现是一种语法错误TJNU-COCIE-WJW722022-3-184.4 递归下降分析程序构造递归下降分析程序构造文法满足文法满足LL(1)条件（是条件（是LL(1)文法）文法）对文法的每个非终结符号编写一个递归子程序对文法的每个非终结符号编写一个递归子程序一、构造条件一、构造条件二、构造方法二、构造方法TJNU-COCIE-WJW732022-3-18：对于：对于LL(1)文法文法ETEE+TE|TFTT*FT|F(E)|i构造其递归下降分析程序构造其递归下降分析程序TJNU

56、-COCIE-WJW742022-3-18ETEPROCEDURE E;BEGINT;EEND;E+TE|PROCEDURE E;IF SYM=+ THENBEGINADVANCE;T;EEND;TFTPROCEDURE T;BEGINF;TEND;T*FT|PROCEDURE T;IF SYM=* THENBEGINADVANCE;F;TEND;F(E)|IPROCEDURE F;IF SYM=i THEN ADVANCEELSEIF SYM=( THENBEGINADVANCE;E;IF SYM=) THEN ADVANCEELSE ERRORENDELSE ERRORADVANCE把输入

57、串指示器把输入串指示器IP指向下一指向下一个输入符号个输入符号SYM是指是指IP当前所指的那个输入符号当前所指的那个输入符号ERROR为出错处理程序为出错处理程序TJNU-COCIE-WJW752022-3-18第第2次上机作业次上机作业根据根据编译原理编译原理P69页文法页文法4.2，构造其递归下，构造其递归下降分析程序降分析程序n参考参考P74伪代码伪代码n要求加入输入输出，用要求加入输入输出，用C编写编写n输入使用前面词法分析程序的结果，其中输入使用前面词法分析程序的结果，其中i代代表标识符或常数表标识符或常数n输入符号串，输出递归过程输入符号串，输出递归过程(非终结符号序非终结符号序列

58、列)和识别结果和识别结果(是否正确句子是否正确句子)TJNU-COCIE-WJW762022-3-184.5 预测分析程序预测分析程序用高级语言的递归过程描述递归下降分析器只有用高级语言的递归过程描述递归下降分析器只有当具有实现这种过程的编译系统时才有意义当具有实现这种过程的编译系统时才有意义实现实现LL(1)分析的另一种有效方法是使用分析的另一种有效方法是使用一张分析表一张分析表一个栈一个栈本节介绍预测分析程序本节介绍预测分析程序TJNU-COCIE-WJW772022-3-181.总体结构总体结构 a #预测分析表预测分析表M总控程序总控程序输出输出X.#一、预测分析程序的结构一、预测分析

59、程序的结构TJNU-COCIE-WJW782022-3-181.总体结构总体结构( (续续1)1)总控程序总控程序控制分析表和分析栈的工作控制分析表和分析栈的工作分析栈分析栈用于存放文法符号。分析开始时先放一个用于存放文法符号。分析开始时先放一个#，然后放进文法开始符号。同时假定输入串之后也然后放进文法开始符号。同时假定输入串之后也总有一个总有一个#，标志输入串的结束，标志输入串的结束TJNU-COCIE-WJW792022-3-181.总体结构总体结构( (续续2)2)一张分析表一张分析表M用一个矩阵来表示，即用一个矩阵来表示，即MA , a(1)A为非终结符为非终结符(2)a是终结符或者是

60、终结符或者#(这里这里#不是文法的终结不是文法的终结符，我们把它作为输入串的结束符号符，我们把它作为输入串的结束符号)(3)矩阵的元素矩阵的元素MA , a中存放着一条关于中存放着一条关于A的产的产生式，指出当生式，指出当A面临输入符号面临输入符号a时所应采用的候选时所应采用的候选式。也可能放一个式。也可能放一个“出错标志出错标志”，指出，指出A根本不根本不该面临输入符号该面临输入符号a。TJNU-COCIE-WJW802022-3-18：有文法：有文法ETEE+TE|TFTT*FT|F(E)|iE#i + i * i #IPTJNU-COCIE-WJW812022-3-181.分析开始时，各