编译原理：第5章 自顶向下语法分析方法-2011

1、5.1 语法分析概述5.2 自顶向下语法分析概述5.3 LL分析法（预测分析法）5.4 递归子程序法 p413 附录A 第五章 自顶向下语法分析方法1第5章 自顶向下语法分析 5.1 语法分析概述1.语法分析器的作用 词法分析器语法分析器前端的其余部分源程序单词取下一个单词分析树中间表示符号表2第5章 自顶向下语法分析 5.1 语法分析概述1.语法分析器的作用语法分析器主要作用有两点：（1）根据词法分析器提供的单词流，为语法正确的输入构造分析树（或语法树）。（2）检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理。 例如，对于C程序语句“IF (a10) b=5；”，词法分析识

2、别出了IF、(、标识符、等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确。IF后面是否为(，(后面是否为正确的表达式等等。 3第5章 自顶向下语法分析 5.1 语法分析概述1.语法分析器的作用 语法分析是编译过程的核心部分，它的主要任务是按照程序语言的语法规则，在词法分析输出的单词符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成作准备。 执行语法分析任务的程序叫语法分析程序或语法分析器。语 法分析器wS w * l 语 法分析器w自顶向下分析自底向上分析S w * r 45.1 语法分析概述2. 两类语法分析方法（1）自顶向下分析方法 语法分析从顶部(树根、文法

3、的开始符号)到底部(叶子、语言的终结符号)为输入的符号串建立分析树。 确定的自顶向下分析方法对文法要求比较严格，必须无二义性、且消除左递归和回溯。典型的方法是递归下降分析方法和LL分析方法。递归下降分析方法便于手工构造语法分析器。LL分析法便于用语法分析器的自动构造工具，自动构造语法分析器。52. 两类语法分析方法（2）自底向上分析方法 语法分析从底部到顶部为输入的符号串建立分析树。最常见的LR分析方法采用的就是自底向上分析方法。 LR分析法能适应一大类文法，几乎所有能用上下文无关文法描述的程序设计语言的语法分析，都可以用LR分析法进行语法分析，LR分析法在实际中有较强的适用性和广泛的应用。

4、LR分析法便于用语法分析器的自动构造工具，自动构造语法分析器。当前应用最广泛的工具之一是YACC系列。 无论采用哪种分析方法，语法分析都是自左向右地读入符号。 5.1 语法分析概述63. 语法分析要点 （1）程序设计语言中的绝大部分语法特性属于上下文无关的，因此语法分析是以上下文无关文法（CFG）作为程序设计语言语法分析的基础。 属于上下文有关的语法特性在语义分析阶段检查。5.1 语法分析概述73. 语法分析要点 （2）任何一个二义性文法不存在与其对应的语法分析器，因此需要为程序设计语言选择能进行确定语法分析的非歧义文法。 对于自顶向下的语法分析而言，需要改造文法，使其无二义性、无左递归和回溯

5、，以便能进行确定的语法分析。 对于自底向上的LR语法分析方法，对某些二义性文法，可以人为地给出运算符的优先性和结合性的规定，可以构造出比相应非二义性文法更优越的LR分析器。 （3）语法分析最终为合法的输入串建立与之匹配的语法树。5.1 语法分析概述85.2 自顶向下语法分析概述 自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推出要分析的输入串。 自顶向下分析常用的方法有：递归下降分析： 利用程序设计语言的递归函数实现，每个函数对应文法的一个非终极符。LL( 1 )分析：由一张预测分析表和一个总控程序组成。预测分析表给出了当面临输入符号时，运用到非终极符的推导所选用的产

6、生式。95.2 自顶向下语法分析概述 自顶向下语法分析确定的自顶向下语法分析（消除左递归和回溯）递归下降分析预测分析法（ LL (1) ）非确定的自顶向下语法分析 （带回溯）105.2 自顶向下语法分析概述 递归下降分析方法实用性强，便于手工编写语法分析器。LL (1)分析法在实际中不常用，但给出了一些重要、形式化的定义，用于指导歧义文法的改造、文法左递归和回溯的消除。为学习更强大和复杂的LR分析法做准备。11构造推导的关键问题 在构造最左推导的过程中,面对当前读入的单词符号a和当前被替换的非终极符A两者,应该选择A的哪条候选式去替换它(推导)。主要找出选择一个非终极符号的候选式的方法; 在构

7、造最右推导的过程中,面对当前读入的单词符号a,已分析过的符号串中是否已构成一个产生式的右部，即句柄（可归约） 。如果已构成句柄，即用相应的产生式左部(非终结符号)去替换它(归约)，寻找句柄的方法。12构造最左推导（aabbaa) (1.自顶向下） SaASa A SbA SS baASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS S135.2.1 带回溯的自顶向下语法分析 1.带回溯的自顶向下语法分析实质 带回溯的自顶向下语法分析实质, 是一个反复使用不同的产生式, 进行试探以谋求匹配输入串的过程。 该方法分析效率低, 在实际中并不适用, 但给出了自顶向下语法

8、分析的思想。145.2.1 带回溯的自顶向下语法分析 1.带回溯的自顶向下语法分析实质例如： 文法GS S aAb A * | *利用自顶向下语法分析思想, 分析 a*b 是否是合法的句子。SaAb*(b) 试探失败SaAb(a)SaAb*(c) 试探成功155.2.1 带回溯的自顶向下语法分析 2.带回溯的自顶向下语法分析面临的问题问题(1): 出现回溯 由于文法中同一非终极符的各候选式有公共的左因子或隐含有公共的左因子，使得推导无法选择唯一的候选式，导致盲目试探。问题(2):左递归问题 无论是直接左递归的， 还是间接左递归的，都会使分析过程无法终止。例如 U U 用于最左推导:U U U

9、U 16思考 1、自上而下分析能否分析所有的上下文无关文法？一、上下文无关文法的特性自嵌入性：一个文法G是自嵌入的，若存在一个非终极符A，有A * A ， 、V+非空判断1：自嵌入文法描述的语言一定不是正则语言。 （错） 2：非自嵌入文法不可能产生2型语言。 （对）172、为何选用CFG描述编程语言的语法规则？ CFG作为语言的语法描述有明显的优点:1.CFG对程序可给出精确易懂的描述2.从描述语言的文法，可自动构造出可用的分析程序3.在语言的语法描述之中，可方便地插入相关的语义描述，进行语法制导的语义翻译思考18二、上下文无关语言的识别装置：Push Down Automata1 定义：下推

10、自动机 PDA（等价于带有下推栈的FA）PDA是一个六元组（K, , , f, S, Z0） 其中：K：状态的有穷非空集 ：有穷输入字母表 ：下推字母表，即栈符号的有穷集 f：K 到K的一个映射 SK是开始状态 Z0：栈中初始下推符号（可标记何时终止）19二、上下文无关语言的识别装置：Push Down Automata例1. PDA识别成对的括号串,可由 G: SS(S) | 产生。（确定）PDA定义如下：M = ( A, “(”, “)”, 0, I), f, A, I)其中：(1) f ( A,I,“(” ) =(A, I0)(2) f ( A,0,”(” ) =(A, 00)(3) f

11、 ( A,0,”)” ) =(A, )(4) f ( A, I, ) =(A, )20二、上下文无关语言的识别装置：Push Down AutomataCFL有一种等价的自动机记号，即“下推自动机”。它描述并且只描述所有的CFL，作为一种语言的定义机制是非常有用的（它与CFG等价性）()( () )控制I21例2. 识别语言XX-1 | X 0, 1*, X-1: X的逆串由下列文法产生：S 0S0 | 1S1 | PDA（该PDA是不确定PDA）如下定义：M=(A,B, 0,1, I,0,1, f, A, I)其中： (1) f(A, I, 0)=(A ,I0) (2) f(A, I, 1)

12、=(A, I1) (3) f(A, 0, 1)=(A, 01) (4) f(A, 1, 0)=(A, 10)(5) f(A,0,0)=(A,00), (B, ) (6) f(A, 1, 1)=(A, 11), (B, ) (7) f(B, 0, 0)=(B, ) (8) f(B, 1, 1)=(B, ) (9) f(B, I, )=(B, ) (10) f(A, I, )=(A, ) 状态A对应读串的前一半，状态B对应读串的后一半。读前一半时，将所读符号置于栈顶；读后一半时，边读边与栈顶符号比较，相等则移掉栈顶符号，否则出错。22二、上下文无关语言的识别装置：Push Down Automat

13、a 2.定理（1）每一个CFG，都对应一个PDA M，使L(M)=L(G)（2）存在一个PDA，它识别的语言不能被任何确定的PDA识别。 归纳：对上下文无关语言的分析，并不总是能以确定的方式进行，需要回溯。23二、上下文无关语言的识别装置：Push Down Automata 小 结 1.能够进行确定分析的语言称为确定语言。大多数的编程语言是确定的语法分析的任务：有效地模拟PDA2.固有歧义的语言：就是根本不存在非歧义文法的语言。文法的非歧义性是不可判定的只有文法是非歧义的，语法分析才可唯一进行虽然不存在算法能在有穷步内确定任意文法是否歧义，但对某些具体文法存在判定算法如：LL文法和LR文法，

14、可证是非歧义文法，并且存在算法，能检查一文法是否是LL或LR文法24三、自上而下的分析方法1.主旨：从文法的S出发，反复使用各种产生式，寻找”匹配”于输入符号串的推导（从S（根）出发，向下逐步建立语法树，最终：为输入串寻找一个最左推导）例1 GS: (1)ScAd | dBa (2) Aab (3) Aa (4) Bcd | c, 则cad是否为文法的句子SdScAScdAabScdAadcda dcdc 是不是分析过程是一个试探过程，必须一一试探所有候选式，直至与输入串匹配成功，或者判定输入串不是正确句子。25三、自上而下的分析方法2. 自上而下分析面临的主要问题 1） 如何选择候选式如果对

15、文法不做任何限制，对候选式的选择成为无根据的，只好一一试探所有候选式，直至成功或失败。致命弱点：不断地回溯，大大影响速度。2）左递归文法将使自上而下分析陷入无限循环例、S Sa | b，若推导baaSSaSaSa263. 自上而下分析法的问题及解决Q1: 回溯低效、耗时，对高度递归的语言，无法接受。解决方案： 对文法加以一定的限制，使每次对候选式的选择是唯一的，从而进行确定的自上而下分析。 如：LL（1）文法。（详见5.3节）273. 自上而下分析法的问题及解决Q2：左递归文法将使自上而下分析陷入无限循环 1.重排规则顺序 （解决方法1） 例S Sa | b, 改为： S b | Sa ，若推

16、导baaSb(不行)SSab（不行）SSabSa2.将左递归右递归（或迭代） （解决方法2） 如：上例生成语言 L = ba* 右递归文法：S bA A aA | 281.消除直接左递归AA|, , (VNVT)*, A VN, 不以A开头则：A A A A | 或 A 例 文法 E E+T | T 或 E T+T （迭代） T T*F | F T F*F F (E) | a F (E) | a 消除左递归，得 E TE E +TE | T FT T *FT | F (E) | a5.2.2 消除左递归291.消除直接左递归若关于A的全部规则为 A A1 | A2 | | Am | 1 | 2

17、 | | n 其中， 每个i都不等于 ，每个i都不以A开头则消除左递归，得 A (1 | 2 | | n )A A (1 | 2 | | m )A | 或 A (1 | 2 | | n )1 | 2 | | m 迭代 5.2.2 消除左递归302.消除间接左递归例 GS： S Qc | c Q Rb | b R Sa | a因 S Qc Rbc Sabc, 是左递归文法代入法： S (Rb | b)c | c S Rbc | bc | c S (Sa | a)bc | bc | c所以 S Sabc | abc | bc | c消除左递归，得 S abcS | bcS | cS S abcS

18、| 5.2.2 消除左递归315.3 LL分析法（预测分析法）5.3.1 概述5.3.2 LL(1)文法5.3.3 文法的变换5.3.4 LL(1)分析器325.3.1 LL分析概述两类确定的自顶向下分析方法（1）递归下降法 （2）LL (K)方法1. LL(K)含义 从左（L）到右（R）扫描输入串，并建立它的最左推导。 K：在选择同一非终极符的不同规则时，通过向前看K个符号决定。LL(K)文法： 是非歧义文法中能构造出确定的自顶向下分析器的最大文法类。LL分析器又称预测分析器，是PDA特例。332. 预测分析方法 自顶向下分析是从文法的开始符号出发，试构造出一个最左推导，从左至右匹配输入的单

19、词符号串。 如果在每步推导中，面对被替换的非终结符号A和当前从左至右读入输入串读到的单词符号a，如果A的定义（无-产生式） A1 |2 | |n 中，只有i（1in)推导出的第一个终极符号是a，那么，就可以用产生式Ai构造最左推导，即用i替换A。342. 预测分析方法一类简单文法的分析器工作过程：(1) 定义 G为S-文法，当且仅当它满足： 每条规则的右部都以VT开头 如果一个VN有多条规则，那么它们都以不同的VT开头例1 S aS | bA, A d | ccA 叫做预测分析矩阵（表），LL分析表Mabcd#SaSbAAccAd352. 预测分析方法对于上例，在推导过程中，完全可以根据当前的

20、向前看符号决定选择哪个产生式进行推导，因此，分析过程是完全确定的。这种分析称为自顶向下的预测分析。 原因在于，文法中，AVN, A12. n i,j (1i, j n ij)从 i推导出来的第一个终结符号集合（称为FIRST( i) ）和从 j推导出来的第一个终结符号集合（称为FIRST( j) ）是不相交的，即： FIRST( i) FIRST( j)=36（2）分析器（预测分析器PDA特例）分析器的动作总是由 栈顶元素X 当前输入符号aabccd#决定的S#控制（总控程序）预测分析表1 2 4 3预测分析器预分析串输入带下推栈初始：# S其中，#栈底 S开始符保存用过的文法规则（即：左分析

21、）输出带37（2）分析器（预测分析器PDA特例）分析器的动作有3种：1.若栈顶符号是一个非终极符，则去查分析表MX, aMX, a是一文法规则X ，则用去替换栈顶的X（ 逆序推入栈中），并输出文法规则编号MX, a无定义，则报错并转错误处理程序均不读下一符号（相当于进行了一次最左推导）2.若栈顶符号X是一个终极符且X=a，则将栈顶符号弹出，并读下一个符号，若XVT,且Xa，则err3.若X=“#”=a，则分析器停机，输入串被接受385.3.2 LL(1)文法对于LL(k)文法，K=1最常见，只需根据栈顶符号X和当前输入符号a，即可确定用哪条规则进行推导。（一）串(VNVT)*的FIRST集开头

22、符号集 FIRST()=a| *a, a VT, , V* 若 *, 则 FIRST()定义1：设G是不带规则的文法，若对所有 A 1 | 2 | | n的规则，有FIRST(i) FIRST(j)=,ij，则G为LL(1)文法。395.3.2 LL(1)文法下面讨论有规则的文法。LL(1)条件？例2: (1) S aA (2) S d (3) A bAS (4) A 若对abd串，S aA abAS abSabd何时选用A 的空规则？SaASaAbASSaAbASSaAbASd参见语法树 在分析时，只有见到它的后继符号才能决定使用这条规则引进跟随集405.3.2 LL(1)文法(二)每个非终

23、极符的Follow集规定 “#”属于开始符号S的Follow集，#是句子结束符。Follow集定义：若G=(VN,VT,P,S)是CFG，A VN，Follow(A)=a | S * A, aFirst(), V+，即: 句型中紧跟在A后面的那些终极符若 * ,则# Follow(A)；换句话说：若S * A，则规定# Follow(A)。415.3.2 LL(1)文法(二)每个非终极符的FOLLOW集定义2：一个文法G是LL(1)文法，当且仅当对文法中形如A 1 | 2 | | n都满足LL(1)条件，即(1) First(i) First(j)=, ij； 且如果i * ,则(2) Fir

24、st(j) Follow(A)=, ij为简化LL(1)条件，引进选择集 Select(A )42第5章 自顶向下语法分析 5.3.2 LL(1)文法（ 三）每条规则的select集 select( A)=First() , 当不能推出Follow(A) (First() ) , 当*利用select集判断LL(1)文法:定义3：一个文法G是LL(1)文法，当且仅当对文法中的所有形如 A1| 2| n 的产生式, 其各候选式都满足如下的条件： select( Ai) select( Aj) = (对所有ij)435.3.2 LL(1)文法 LL(1)条件： 一个上下文无关文法G，对其所有形如A

25、 1 | 2 | | n的规则： select(A i) select(A j) =, ij只要一个CFG满足LL(1)条件，就是LL(1)文法，能采用预测分析法进行确定的自顶向下分析。对不同的LL(1)文法，其预测分析器的总控程序完全一样。不同仅在于分析表不同。445.3.2 LL(1)文法 LL(1)文法的定义 LL(1)的含义： 按自左向右的顺序扫描输入符号串，并按最左推导的方式进行推导。 “1”表示选择同一非终极符的不同候选式时，是通过向前看一个输入符号（即待匹配指针所指向的当前符号）决定的。 455.3.2 LL(1)文法 怎样判断一个文法是否为LL（1）文法？这类问题可以直接根据L

26、L(1)文法定义判断，也可根据LL(1)分析表判断。若LL(1)分析表中每一项没有多重定义（即无二义性），就是LL(1) 文法。利用select集构造LL(1)分析表, 其元素MA,a按下述规则确定： (其中, AVN, aVT # ) 对于每个形如 A的产生式: 若 a select(A) , 则置 M A,a=“A” 否则置错，用空白表示。46第5章 自顶向下语法分析 例1： 给定文法 S0S| 1S |是否为 LL(1) 文法？解： 构造LL(1)分析表: 01#SS0SS1SS 因为表中无多重定义， 所以该文法是 LL(1) 文法。 47第5章 自顶向下语法分析 例2： 给定文法 S0

27、S0| 1S1 |是否为 LL(1) 文法？解： 构造LL(1)分析表: 01#SS0S0S S1S1S S 因为表中出现多重定义， 所以该文法不是 LL(1) 文法。 48第5章 自顶向下语法分析 例3: 左递归文法是LL（1）文法吗？解：因为左递归文法意味着有隐含的左公共因子，所以左递归文法不是LL（1）文法。 例如： AAa | b 因为：First(Aa=b，First(b)=b， 所以 First(Aa First(b)495.3.2 LL(1)文法 关键：如何计算FOLLOW集 FOLLOW集的计算 (a) 设S为G中开始符号，则#FOLLOW(S)(b) 若A B是一产生式，则把

28、FIRST()的非空元素加入到FOLLOW(B)中。 如果 * ，则把FOLLOW(A)也加入到FOLLOW(B)中(c) 反复使用(b)，直到每个VN的FOLLOW集不再增大为止。50例4 判断G是否是LL(1)文法，如果是，构造LL(1)分析表GS1. S AB2. S bC3. A 4. A b5. B 6. B aD7. C AD8. C b9. D aS10. D c(1)求VN的First集、 Follow集FIRSTFOLLOWSb,a, #Ab, #,a,cBa, #Cb,a, c#Da,c#(2) select(S AB)=b,a,# select(S bC)=b, 相交，不

29、是LL(1)文法同理：select(A )=#, a, c select(B )=# select(C AD)=b,a,c select(C b)=b相交教材P7951第5章 自顶向下语法分析 5.3.3 文法的变换 预测分析法是一种确定的自顶向下的语法分析，它要求文法必须是LL（1）形式。 某些非LL（1）文法，经过变换后，有可能改造成LL（1）文法。1.左递归文法的变换 左递归文法必然不是LL（1）文法。经过消除左递归的变换后，新的文法不一定是LL（1）文法，需进一步利用LL（1）文法的条件进行判断。 52第5章 自顶向下语法分析 5.3.3 文法的变换1.左递归文法的变换例：给定文法GS

30、： S i | (E) EE+S | E-S | S（1）求每一非终极符的First集和Follow集。（2）判断该文法是否为LL（1）文法，为什么？能否进行文法变 换成为LL（1）文法？若能，给出LL（1）分析表。53 1.左递归文法的变换例：给定文法GS： S i|(E) EE+S|E-S|S（1）求每一非终极符的 First集和Follow集。FirstFollowSi, (#, ), +, -Ei, ( ), +, -(2)因为该文法是左递归文法，所以不是LL(1）文法。 变换左递归文法：EE（+S | -S）| SE SE E（+S | -S）E | GS :S i|(E) E SE

31、 E+SE|-SE|54（3）求文法GS的每一非终极符的First集和Follow集。(4)文法GS的LL（1）分析表 FirstFollowSi,(#, ), +, -Ei,( )E+,-, )i+-()#Si(E)ESESEE+SE-SE GS :S i|(E) E SE E+SE|-SE|因为LL（1）分析表无多重定义，所以变换后的文法GS是LL（1）文法。55第5章 自顶向下语法分析 5.3.3 文法的变换2.提取左公共因子变换 含有左公共因子的文法肯定不是LL（1）文法，经过提取左公共因子变换后（可能这种变换需多次进行），新文法也不一定是LL（1）文法，还需进一步由LL（1）条件判定

32、。56 2.提取左公共因子变换 例：变换下列文法GS：S aSb|aSc|，并判断是否为LL(1)文法。解: 提取左公共因子变换: S aS（b|c）| 令: B b|c 变换后的文法: GS： S aSB| B b|c GS :Select(S aSB)=aSelect(S )=b,c,#Select(B b)=bSelect(B c)=c具有相同左部的产生式的Select集两两不相交，故GS 为LL（1）文法。 57 2.提取左公共因子变换 思考题：能否通过文法变换，将下面文法转换为LL(1)文法。 S iBtSeS | iBtS | a B b解：S iBtSS | a S eS | B

33、 b因为 select(S )=#, e ，与e是相交的，不满足LL（1）条件所以不是LL(1)文法itaeb#SiBtSSaSS eSS S 583. 角替换 角：一规则右部的最左出现，称为规则的角。如： ScS | Ac 角替换：对一规则的非终极符的角，用其规则右部去替换它。 非终极符角的出现意味着左公共因子可能是隐式的。消除隐式左公共因子的办法可采用角替换。角替换与提取左公共因子往往同时进行。 角替换是一种辅助手段,用于发现隐含的左递归、左公共因子。角替换本身不改变文法的LL（1）性质。593. 角替换 例: 下列文法是否可变换为LL（1）文法？ 文法GS：ScS | Ac AaS |

34、b解：产生式S Ac 中含有角A，角替换为：SaSc | bc 由于GS中非终极符A变成不可达符号，所以产生式 AaS|b应予以删除。 改造后的文法GS : ScS | aSc | bcSelect(ScS )=c Select(SaSc)=a Select(Sbc )=b 显然, 具有相同左部的产生式的Select集两两相交为空， 故为LL（1）文法。 60例：S Ap | Bq, A aAp | d, B aBq | e解：角替换 S (aAp | d)p | (aBq | e)q即： S aApp | aBqq | dp | eq A aAp | d, B aBq | e对S变换，S a

35、S | dp | eq S App | Bqq对S角替换， S (aAp | d)pp | (aBq | e)qq再提取左因式，S aS | dpp | eqq S Appp | Bqqq继续重复，仍然有左因式。61第5章 自顶向下语法分析 5.3.3 文法的变换 关于文法变换，有下面的结论： 存在某些文法，不能在有限步骤内提取完左公共因子。 一个文法经变换后，没有空产生式，且无左递归时，则改写后的文法是LL（1）文法，否则需进一步用LL(1)条件判断。 LL（1）文法通过角替换后，保留LL（1）性质。 文法变换可能会使某些产生式变成无用产生式，即伴随着对文法的化简。62第5章 自顶向下语法分

36、析 5.3.4 LL(1)分析器 LL（1）分析器是由一张LL（1）分析表，一个控制程序和一个分析栈组成。分析栈中存放文法符号。 LL（1）分析器模型如图所示： #S分析栈a1a2aian输入数据LL（1）分析器 LL（1）分析表输出最左推导规则序列63第5章 自顶向下语法分析 5.3.4 LL(1)分析器 # S分析器初态:如图所示, 分析栈中压入“#”和文法开始符号S，栈顶元素是S。待匹配指针指向输入串的第一个待匹配符. a1a2aian64 5.3.4 LL(1)分析器 例: 以输入串 i+i*i 为例,给出用LL(1)分析器识别符号串的过程.文法GE: ETE E+TE| TFT T*

37、FT| Fi|(E) 解:(1)求非终极符的First集和Follow集 FirstFollowEi, (#, )E+ , #, )Ti, (+, #, )T* , +, #, )Fi, (+, #, ), *65文法GE: ETE E+TE| TFT T*FT| Fi|(E) 解:(1)FirstFollowEi,(#, )E+,#, )Ti,(+, #, )T*,+, #, )Fi, (+, #, ), *(2) 求LL(1)分析表+*i（）#ETETEE+TETFTFTT*FTFi(E)66ETE E+TE| TFT T*FT| Fi|(E) 解:+*i（）#ETETEE+TETFTFT

38、T*FTFi(E)步骤分析栈余留输入串产生式子12345678#E# ET# E TF# E T i# E T# E#ET+#ETi+i*i #i+i*i #i+i*i #i+i*i # +i*i # +i*i # +i*i # i*i #ETETFTFi匹配TE+TE匹配TFT剩余过程自己完成67第5章 自顶向下语法分析 5.4 递归子程序法 递归子程序法，又称递归下降分析法。思想是：非终极符的文法规则可看成是识别该非终极符的过程定义，针对文法的每一非终极符，根据相应产生式各候选式的结构，为其编写一个递归函数，用来识别该非终极符所表示的语法范畴。 递归下降分析法是一种确定的自顶向下的语法分析

39、方法，其分析过程是从文法开始符号出发，执行一组递归过程，不断向下推导，直到推出句子。 68第5章 自顶向下语法分析 为了构造递归子程序，有如下的约定和要注意的问题：(1)文法必须是LL（1）文法。 (2)待匹配符号串是要被分析的源程序，是用助记符或整数码表示的单词类别串。 例如待匹配符号串“ ID:=ID+NUM# ”，按从左向右扫描输入串的顺序，开始的时候，当前匹配指针指向的输入符号是“ID”。 (3)设辅助函数getsym()的作用是读取当前指针指向的待匹配符，并使待匹配指针向前移，指向下一个待匹配符。变量sym用来存储当前匹配指针指向的输入符号。 (4)进入子程序时已经取到了当前的输入符

40、号；从子程序返回时，也已经取到了下一次准备匹配的输入符号。 69第5章 自顶向下语法分析 为了构造递归子程序，有如下的约定和要注意的问题：(5) 如果遇到非终极符，则直接调用该非终极符对应的子程序。如果非终极符A的右部只有一个候选式，则按从左向右的顺序依次构造A的识别过程。 如果遇到终极符，判断是否与输入的符号匹配。若匹配，则读取下一个待匹配符号；如果匹配失败，则意味着有语法错误。 (6)如果非终极符A的右部有多个候选式，则根据每个候选式的第一个符号确定识别非终极符A的流程控制转向。70例：文法Z(U)| aUb ，U dZ|e，为其构造递归下降分析子程序。并对输入串aeb进行语法分析 。第5

41、章 自顶向下语法分析 解： 文法中有两个非终结符号Z和U，需要分别编两个函数来完成Z和U规则的识别。 对于规则Z(U)|aUb，右部有两个候选式，因此，U的识别过程有两个分支，分别根据符号( 和 a 来判别。 同理对规则UdZ|e 设计的过程也分为两个分支。见图(a)和(b)所示。71Z (U)|aUb图(a) 非终结符号Z的分析程序 过程Zsym= getsym()U出口语法错误：输入串少) sym =aYNNNNYY语法错误：输入串少(、a语法错误：输入串少b sym =(sym =)sym =bsym= getsym()sym= getsym()UY对输入串aeb进行语法分析72U dZ

42、|e过程Usym= getsym()Z出口sym =eYNNY语法错误：输入串少d、esym= getsym()Y图(b) 非终结符号U的分析程序 sym =d对输入串aeb进行语法分析73U dZ|e 每个非终结符对应的函数设计好后，就可以对输入串进行语法分析。 假设输入串为aeb, 从Z函数开始识别，由于sym不等于(，等于a，所以选择Z函数的右边分支，表示选择了ZaUb规则。读下一个符号，使sym=e; 调U函数，因sym=e，表示使用Ue 规则, 读下一个符号，使sym=b，并返回调用程序Z函数右边分支U的下方，接着判断sym=b，读下一个符号，并退出Z. 在主函数中判断:若sym=#

43、,则分析过程结束，从而判定输入串aeb语法分析成功。 这个过程相当于构造了如下推导过程：Z=aUb=aeb Z (U)|aUb对输入串aeb#进行语法分析74例：为下列文法的每个非终极符构造相应的递归函数 文法GZ： Z(U) | aUb UdZ | e解： main( ) sym=getsym( ); /读取当前输入串的第一个符号 Z(); /从文法开始符号对应的子程序开始识别 if (sym=#) OK; /”#”是程序结束的标志 else error (“error in main”); 对输入串aeb#进行语法分析75 Z() / Z(U) | aUb if(sym=( ) sym=g

44、etsym(); U(); if (sym ) ) error ( “缺 )” ) ; exit(0); else sym=getsym( ); else if(sym=a) sym=getsym( ); U(); if (sym b ) error ( “缺b” ) ; exit(0); else sym=getsym(); else error ( “缺 ( 或 a” ) ; exit(0);对输入串aeb#进行语法分析76 U() / UdZ | e if(sym=d) sym=getsym(); Z(); else if(sym=e) sym=getsym( ); else error

45、 ( “缺 d 或 e” ) ; exit(0);对输入串aeb#进行语法分析77例： 为下列文法的每个非终极符构造相应的递归函数.文法GE： ETE E+TE| TFT T*FT| F i |(E)解： main( ) sym=getsym( ); /*读取当前输入串的第一个符号。*/ E( ); if(sym= =# ) OK; else error (“in main”); 78 E( ) / ETE if (sym= =i| sym= =( ) /* if (sym first (T) */ T(); E(); else error (“非法符号”, sym); exit(0);79

46、E() / E+TE| if (sym= =+) sym=getsym( ); T(); E(); else if (sym # sym ) ) /* if (sym follow (E) */ error (“非法符号”, sym); exit(0); /意味着用 E 推导80 T() / TFT if (sym= =i| sym= =( ) /* if (sym first (F) */ F(); T(); else error (“非法符号”, sym); exit(0);81 T() / T*FT| if (sym= =*) sym=getsym( ); F(); T(); else

47、if (sym# sym+sym)/ if (sym follow (T) error (“非法符号”, sym); exit(0); /意味着用T 推导82 F() / F i | (E) if (sym= =i) sym=getsym(); else if (sym= =() sym=getsym( ); E( ); if (sym= =) ) sym=getsym( ); else error ( “缺)” ); exit(0); else error( “缺（或i ”); exit (0);83例： 文法GE：EE+T | T TT*F | F Fi | (E)设计递归子程序。解: 对文法G消除左递归为G(E): E+|-T+T /考虑表达式有形如+5或-5的情况 TF*F Fi|(E) 84 E() /E +|- T+T if (sym = + | sym= -) sym=getsym(); if(sym = i | sym = ( ) T(); else error; exit(0); else if (sym