hh第5章自顶向下语法分析方法.pptx

第5章 自顶向下语法分析方法 语法分析是编译过程的核心部分, 其 基本任务是在词法分析识别出单词 符号串的基础上, 分析判断程序的语 法结构是否符合语法规则。 对于文法GS: SxAy Aab | a 考虑输入串为xay, 其分析过程如下: 1. 自上而下分析的不确定性 ab yAx S a yAx S 在上述分析过程中, 若有多个候选 式可供选择, 则需逐一试探每个候 选式。当试探失败时, 必须回溯到 该试探的初始现场, 包括注销已生 长子树、输入串指针回退到试探 前状态。这种带回溯的自上而下 分析法是一种穷举法, 效率很低。 为了实现确定的自上而下分析, 要求 文法满足下述条件: (1)文法不含左递归。 左递归: AA 或 A A 左递归的存在使自上而下分析过 程陷入无限循环, 因此, 使用自上 而下分析法必须消除左递归。 + 2. 确定的自上而下分析 (2) 分析过程无回溯 回溯的存在可能使已做的大量分析 工作推倒重来, 这会严重影响效率, 因此, 使用自上而下分析法必须消 除回溯。 直接左递归的消除: 方法: 引入一个新非终结符, 把含有左 递归的产生式改写为右递归形式。 考虑产生式: AA | 其中,是任意串且不以A开头. A的产生式可改写为: (1) 左递归的消除 AA AA| 例如, 算术表达式文法GE为: GE: EE+T | T TT*F | F F(E) | i 消去直接左递归后得到文法GE: GE: E TE E +TE | T FT T*FT | F(E) | i 一般地, 设文法中A的产生式为: AA1|A2|Am| 1|2|n 其中, 每个都不等于 每个都不以A开头 消除A的直接左递归, 文法可改写为: A1A | 2A | nA A1A | 2A |mA | 例如 消除EE+T|ET|T的左递归 解: 消除左递归后变为 ETE E+TE | TE | 间接左递归的消除 考虑GS: SQc | c QRb | b RSa | a 间接左递归的存在是由于非终结符 之间形成了循环推导, 只要把循环 推导中的某个连接切断, 间接左递 归就消除了。 切断循环推导中某个连接的方法: Step1. 对n个产生式中的某一个进 行至多n-1次替换, 使间接左递归变 成直接左递归, 再消除之。 例如, 消除GS中S,Q之间的连接: S Qc|c Rbc|bc|c Sabc|abc|bc|c 改写为: SabcS|bcS|cS SabcS| Step2. 对其余n-1个产生式中的某 一个进行至多n-2次替换, 再消除其 直接左递归。 若后两个产生式改为: QRb | b RSa | a | Qa 则还需消除Q,R之间的连接: Q Rb|b Sab|ab|Qab|b 再消除其直接左递归。 考虑后两个产生式: QRb | b RSa | a 消除左递归算法: (1) 文法所有非终结符排序为A1,An; (2) 把间接左递归改为直接左递归, 并 消除之, 方法如下: for (i=1; i 终结首符集FIRST() 对于文法G的所有非终结符的每个 候选式, 定义 FIRST()a | a, aVT 若 , 则FIRST() * * 即FIRST()是由所能推出的所有 终结符串的首字符或 。 若A的产生式为A1| 2|n 则FIRST(A)=FIRST(1)FIRST(2) 若A有多个候选式的终结首符集含a, 则仍需进行试探。 可见, 要消除回溯, 准确指派一个候 选式去执行匹配任务, 则各候选式的 终结首符集应互不相交, 即 FIRST(i)FIRST(j)= (ij) 如何使候选式的终结首符集互不 相交? 方法是提取公共左因子。 提取公共左因子 考虑产生式: AabA | aB | ab 改写文法: AaA AbA | B | b 改写第2式: AbA | B AA | 一般地, 假设文法中A的产生式为 A1| 2| i | i+1|j 提取公共左因子后, 改写为 A A | i+1| j A1| 2| | i 经反复提取公共左因子, 可使每个 非终结符的终结首符集互不相交。 消除左递归和提取公共左因子后, 任一非终结符的终结首符集互不相 交。此时, 若不属于任一非终结符 的终结首符集, 则可进行有效的自 上而下分析, 如LL(1)分析。 然而, 由于消除左递归和提取公共 左因子后, 文法中引进了大量-生成 式, 这就引出了自动匹配问题。 对于文法GE: ETE E+TE | TFT T*FT | F(E) | i 考虑输入串i+i # E ET FT i +ET F T i (3) 自动匹配问题 当A面临输入符a时, 若 aFIRST(A)且FIRST(A), 则需 要考虑自动匹配问题。 对于上述算术表达式文法, 若输入 串为i/i, 即使让T进行自动匹配, /也 不能与后面的符号匹配, 此时就没 必要进行自动匹配。 因此, 只有当前输入符能与A后第 一个终结符匹配成功时, 才让A自 动得到匹配。 这就要求分析前先求出紧跟在A后 的终结符, 即FOLLOW(A)。 FOLLOW(A)的定义 对文法GS的任一非终结符A, 定义 FOLLOW(A)=a | S Aa,aVT 若S A, 则规定 #FOLLOW(A) * 即FOLLOW(A)是所有句型中紧跟在 A之后的终结符 或 # 。 因S S, 故 #FOLLOW(S) * 0 自动匹配条件 当非终结符A面临输入符a时, 若aFIRST(A)且FIRST(A), 则 仅当aFOLLOW(A)时, 才使A自 动匹配。 缺少任一条件, 均不自动匹配。 若输入符aFIRST(A)且a FOLLOW(A), 则当FIRST(A) 时仍需回溯。 因此, 对于存在-生成式的非终 结符A, 若要进行无回溯的自上 而下分析, 则FIRST(A)与 FOLLOW(A)应互不相交。 确定的自上而下分析的文法条件: LL(1)文法条件 (1)文法不含左递归; (2)文法中每个非终结符的各个候选 式的终结首符集互不相交; (3)对文法的任一非终结符A, 若A的 终结首符集包含, 则 FIRST(A)FOLLOW(A)= 递归下降分析法是一种自上而下分 析法, 文法的每个非终结符对应一 个递归过程。 分析过程从文法开始符出发, 执行 一组递归过程, 这样向下推导直到 推出句子。 3. 递归下降分析器 若文法不含左递归且每个非终结符 的候选式无公共左因子, 则可构造 不带回溯的递归下降分析程序。 该程序由一组过程组成, 每个过程 对应文法的一个非终结符。这样的 分析程序也称为递归下降分析器。 例如, 对于不含左递归的算术表达式 文法, 其对应的递归下降分析器如下 : void E( ) T( ); E( ); void E( ) if (lookahead = = +) match (+); T( ); E( ); void T( ) F( ); T( ); void T( ) if (lookahead = =*) match (*); F( ); T( ); void F( ) if (lookahead = = i) match (i); else if (lookahead = =() match (); E( ); if (lookahead = =) match (); else error ( ); else error ( ); 说明: 考虑E的产生式: E+TE | E有两个候选式, E面临输入符+时 第一个候选式工作, 面临其它符号 时E自动匹配。 假定递归函数的调用以栈的形式模 拟, 下面分析输入串 # i1*(i2+i3) # 的 语法分析过程: 首先, 将#和文法开始符E压入栈中。 当语法分析进行到栈中仅剩#而输入 串指针已指向输入串尾部的#时, 则 语法分析成功。 分析过程如下图所示: E # T E # F T E # T E # iF T E # * E ) T E # T E ) T E # ( F T E ) T E # T E ) T E # i E ) T E # T E ) T E # +F T E ) T E # T E ) T E # i E ) T E # T E # E # # 输入串i1*(i2+i3)的语法分析过程 ) 递归程序法的优缺点: 优点: (1) 易于处理递归成分 (2) 易于写出程序 (3) 易懂 缺点: (1) 需要编写的程序是可递归的 (2) 程序量大 (3) 出错处理定位不准确 LL(1)分析法又称预测分析法, 是一 种无回溯的非递归自上而下分析法. LL(1)的含义: 第一个L表明自左至 右扫描输入串; 第二个L表明最左推 导; 1表明向右查看1个符号。 LL(k)文法: 向前查看k个符号才能确 定选用哪个产生式。 4. LL(1)分析法 (预测分析法) 4.1 表驱动的LL(1)分析器 LL(1)分析法的基本思想: 根据输入串 的当前输入符确定选用某一个产生式 进行推导, 当该输入符与推导的第一个 符号相同时, 再取输入串的下一个符号, 继续确定下一步推导应选的产生式, 如 此下去, 直到推出输入串为止。 一个LL(1)分析器由一张LL(1)分析表( 预测分析表)、一个先进后出分析栈和 一个控制程序(表驱动程序)组成。 a1a2 aian # 分析表M 控制程序 输入串: 栈顶 # x1 xj输出 分析栈 图3-14 LL(1)分析器 对LL(1)分析器的几点说明: (1)输入串是待分析的符号串, 它以# 作为结束标志。(注: #VT但不是 文法符号) (2)分析栈存放分析过程的文法符 号。分析开始时栈底先放一个#, 再压入文法开始符。当分析栈中 仅剩#且输入串指针指向串尾#时, 分析成功。 (3)分析表用一个矩阵M表示。矩阵M 的每一行与文法的一个非终结符相 关联, 每一列与文法的一个终结符 或#关联。 MA,a中的内容为一条A的产生 式, 表示当A面临输入符a时应采用 的候选式。当MA,a中的内容为 空时, 表示A不应面临输入符a, 即 输入串含语法错误。 (4)控制程序根据分析栈栈顶符号x和 当前输入符a决定分析器的动作: 若xa“#”, 则分析成功。 若xa “#”, 即栈顶符号x与当前 输入符a匹配, 则将x从栈顶弹出, 输 入串指针后移, 继续对下一个字符进 行分析。 若x为非终结符A, 则查分析表元 素A,a: i. 若MA,a为一产生式, 则A自栈顶 弹出, MA,a中产生式的右部符号 逆序入栈; 若MA,a为A, 则只 将A自栈顶弹出。 ii.若MA,a为空, 则发现语法错误, 调用出错处理程序进行处理。 控制程序描述如下: 把#和文法开始符依次入栈; 把第一个输入符读入a; do 把栈顶符号弹出并放入x中; if (xVT) if (x= =a) 读入下一输入符a; else error( ); else if (Mx,a= = “xy1y2yk”) 把y1y2yk按逆序入栈; 输出“xy1y2yk”; else error( ); while(x!=“#”) 例 一个文法的LL(1)分析表如下所示, 试给出输入串aadl的分析过程。 输入串aadl的分析过程如下: abld# A AaA A AABlAA BBdB BBbB B 符号栈 当前输入符输入串 说明 #Aa adl# 弹出栈顶符,将AaA右部逆序入栈 #Aaa adl# 匹配,弹出栈顶符a,读入下一输入符a #Aa dl# 弹出栈顶符, AABl右部逆序入栈 #lBAa dl# 弹出栈顶符, AaA右部逆序入栈 #lBAaa dl# 匹配,弹出栈顶符a,读入下一输入符d #lBAd l# 由A仅弹出栈顶符号A #lBd l# 弹出栈顶符, BdB右部逆序入栈 #lBdd l# 匹配, 弹出栈顶符d, 读下一输入符l #lBl # 由B仅弹出栈顶符号B #ll # 匹配, 弹出栈顶符l, 读下一输入符# # 匹配, 分析成功 LL(1)分析器中除了分析表不同外, 分 析栈、控制程序都相同, 故构造一个 LL(1)分析器实际上就是构造文法的 LL(1)分析表。 为了构造分析表M, 需要预先定义 FIRST集和FOLLOW集。 4.2 LL(1)分析表的构造 假定是文法GS的任一符号串, (VTVN)*, FIRST()a | a, aVT 若 , 则规定FIRST(), 即FIRST()是的所有可能推出的首 终结符或。 * * (1) FIRST集的构造方法 对任一终结符a, FIRST(a)=a。 对每个非终结符X连续使用下述规则, 直到FIRST集不再增大为止。 若有Xa, 则把a加入FIRST(X); 若有X, 则把加入FIRST(X); 若有XY, YVN, 则把FIRST(Y) 的所有非元素都加入FIRST(X); 若有XY1Y2Yk, 而Y1Yi1都有, 则把FIRST(Yj) (j=1,2,i)的所有非 元素都加入FIRST(X); 若Y1Yk均有, 把加入FIRST(X). 例 试构造文法GE的FIRST集。 GE: ETE, E+TE | TFT, T*FT | F(E)i 解: FIRST(E)=+, ; FIRST(T)=*, ; FIRST(F)(, i ; 由TF知, 把FIRST(F)的所有非元素 加入FIRST(T), 故FIRST(T)=(,i; 由ET知, 把FIRST(T)的所有非元素 加入FIRST(E), 故FIRST(E)=(,i。FIRST(E)=(,i FIRST(E)=+, FIRST(T)=(,i FIRST(T)=*, FIRST(F)(, i 对文法GS的任何非终结符A, 定义 FOLLOW(A)=a|S Aa, aVT 若S A, 则规定#FOLLOW(A) 即FOLLOW(A)是所有句型中出现在 紧随A之后的终结符 或 # 。 * * (2) FOLLOW集构造方法 方法: 对每个非终结符A, 连续使用下述 规则, 直到FOLLOW(A)不再增大止. 对文法开始符S, 把#加入FOLLOW(S) 若有AB (可为空), 则将FIRST()加入FOLLOW(B); 若有AB或AB且 , 则把 FOLLOW(A)加入到FOLLOW(B)。 * 例 试构造文法GE的FOLLOW集。 GE: ETE E+TE | TFT T*FT | F(E) | i 解法1: 1) FOLLOW(E)=# 2) 对于产生式 ETE, 因 FIRST(E)FOLLOW(T), 故 FOLLOW(T)=+ 因 FOLLOW(E)FOLLOW(E), 故 FOLLOW(E)=# 由ETE且E知, FOLLOW(E)FOLLOW(T), 故 FOLLOW(T)=+,# FIRST(E)=(,i FIRST(E)=+, FIRST(T)=(,i FIRST(T)=*, FIRST(F)(, i 对于产生式 E+TE, FIRST(E)FOLLOW(T) FOLLOW(E)FOLLOW(E) 由E+TE且E知, FOLLOW(E)FOLLOW(T), 故 FOLLOW(T)=+,# 对于产生式 TFT, 因 FIRST(T)FOLLOW(F), 故 FOLLOW(F)=* 因 FOLLOW(T)FOLLOW(T), 故 FOLLOW(T)=+,# 由TFT且T知, FOLLOW(T)FOLLOW(F), 故 FOLLOW(F)=*, +,# FIRST(E)=(,i FIRST(E)=+, FIRST(T)=(,i FIRST(T)=*, FIRST(F)(, i 对于产生式 T*FT, FIRST(T)FOLLOW(F) FOLLOW(T)FOLLOW(T) 由T*FT且T知, FOLLOW(T)FOLLOW(F), 故 FOLLOW(F)=*,+,# 对于产生式 F(E) 因 FIRST()FOLLOW(E), 故 FOLLOW(E)=#,) 第一轮结束, FOLLOW集如下: FOLLOW(E)= ), # FOLLOW(F)=*, + , # FOLLOW(T)=+,# FOLLOW(T)=+,# FOLLOW(E)= # 第二轮循环： 3) 对于产生式 ETE, 因 FOLLOW(E)FOLLOW(E), 故 FOLLOW(E)=#,) 由ETE且E知, FOLLOW(E)FOLLOW(T), 故 FOLLOW(T)=+,#,) 对于产生式 E+TE, FOLLOW(E)FOLLOW(E) 由E+TE且E知, FOLLOW(E)FOLLOW(T), 故 FOLLOW(T)=+,#,) 第一轮结束: FOLLOW(E)= ), # FOLLOW(F)=*, + , # FOLLOW(T)=+,# FOLLOW(T)=+,# FOLLOW(E)= # 对于产生式 TFT, 因 FOLLOW(T)FOLLOW(T), 故 FOLLOW(T)=+,#,) 由TFT且T知, FOLLOW(T)FOLLOW(F), 故 FOLLOW(F)=*, +,#, ) 对于产生式 T*FT, FOLLOW(T)FOLLOW(T) 由T*FT且T知, FOLLOW(T)FOLLOW(F), 故 FOLLOW(F)=*,+,#,) 对于产生式 F(E), 第二轮无需考虑。 第二轮结束: FOLLOW(F)=*,+,#,) FOLLOW(T)=+,#,) FOLLOW(T)=+,#,) FOLLOW(E)= #,) FOLLOW(E)= ), # 第三轮循环：(略) 最终的FOLLOW集如下: FOLLOW(E)= ), # FOLLOW(E)= ), # FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=*, +, ), # 例 试构造文法GE的FOLLOW集。 GE: ETE E+TE | TFT T*FT | F(E) | i 解2: 1)FOLLOW(E)=# 2)由ETE知, FIRST(E)FOLLOW(T), FOLLOW(T)=+ 由E+TE, FIRST(E)属 由TFT知, FIRST(T)FOLLOW(F), FOLLOW(F)=* 由T*FT知, FIRST(T)属 由F(E) | i知, FIRST( ) )FOLLOW(E), FOLLOW(E)=),# FIRST(E)=(,i FIRST(E)=+, FIRST(T)=(,i FIRST(T)=*, FIRST(F)(, i 3)由ETE知, FOLLOW(E)FOLLOW(E), FOLLOW(E)=),# 由ETE且E知, FOLLOW(E)F.(T), FOLLOW(T)=+,),# 由E+TE知, FOLLOW(E)属于 由E+TE且E知, FOLLOW(E)F.(T), FOLLOW(T)=+,),# 由TFT知, FOLLOW(T)FOLLOW(T), FOLLOW(T)=+,),# 由TFT且T知, FOLLOW(T)F.(F), FOLLOW(F)=*,+,),# 由T*FT知, FOLLOW(T)属 由T*FT且T知, FOLLOW(T)F.(F), FOLLOW(F)=*,+,),# 考虑F(E)|i FOLLOW(T)=+ FOLLOW(F)=* FOLLOW(E)= ),# FOLLOW集如下: FOLLOW(E)= ), # FOLLOW(E)= ), # FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=*, +, ), # (3) 构造分析表M 1) 对每个产生式A1|n执行i),ii): i)对FIRST(A)中每个终结符a, 把 Ai加到MA,a中, 其中i为终结 首符集含a的候选式或唯一候选式; ii)若FIRST(A), 则对任何属于 FOLLOW(A)的终结符b, 将A 加入MA,b; 2) 把所有无定义的MA,a标记为出 错。 例 试构造文法GE的LL(1)分析表 GE: ETE, E+TE | TFT, T*FT | F(E)i 解:首先构造FIRST集: FIRST(E)=+, FIRST(T)=*, FIRST(F)=(, i FIRST(T)=(, i FIRST(E)=(, i 其次构造FOLLOW集: FOLLOW(E)= ), # FOLLOW(E)= ), # FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=*, +, ), # 最后构造文法GE的LL(1)分析表: i+ * () # EETEETE E E+TEE E TTFT TFT TTT*FT T T FFi F(E ) 若一个文法的LL(1)分析表