1、22.8.9copyright/1 陕西理工学院 计算机系 编译原理1第第4 4章章 语法分析语法分析自上而下分析自上而下分析 4.1 4.1 语法分析器的功能语法分析器的功能 4.2 4.2 自上而下分析面临的问题自上而下分析面临的问题 4.3 LL4.3 LL（1 1）分析法）分析法4.4 4.4 递归下降分析程序构造递归下降分析程序构造4.5 4.5 预测分析程序预测分析程序第第4 4章章 语法分析语法分析自上而下分析自上而下分析 22.8.9copyright/2 陕西理工学院 计算机系 编译原理2句型、句子和语言的定义句型、句子和语言的定义 句型句型有文法有文法GSGS，若，若S=S
2、=*，且，且*,则称是则称是是文法是文法G G的一个句型的一个句型 句子句子有文法有文法GSGS，若，若S=S=*，且，且T T*,则称是则称是是文法是文法G G的一个句子的一个句子 语言语言由文法由文法 G G 产生的所有句子的集合产生的所有句子的集合 L(G)=|S=L(G)=|S=+,且且T T*内容回顾内容回顾 22.8.9copyright/3 陕西理工学院 计算机系 编译原理3 最左最左(最右最右)推导推导在推导的任何一步在推导的任何一步=*(其中其中和和是句型是句型)，都对都对中的最左中的最左(最右最右)非终结符进行替换非终结符进行替换 句型分析句型分析(句子分析句子分析)识别一
3、个符号串是否为某文法的句型识别一个符号串是否为某文法的句型(句子句子)的过程的过程也就是某文法的某个推导的构造过程也就是某文法的某个推导的构造过程内容回顾内容回顾 22.8.9copyright/4 陕西理工学院 计算机系 编译原理4 分析算法分析算法(分析器、识别算法分析器、识别算法)在语言的编译实现中，把完成句型在语言的编译实现中，把完成句型(句句 子子)分析的程序称为分析程序或识别程序分析的程序称为分析程序或识别程序 从左到右的分析算法从左到右的分析算法即总是从左到右地识别输入符号串，首即总是从左到右地识别输入符号串，首 先识别符号串中的最左符号，进而依次先识别符号串中的最左符号，进而依
4、次 识别右边的一个符号识别右边的一个符号内容回顾内容回顾 22.8.9copyright/5 陕西理工学院 计算机系 编译原理5 任务任务分析并判定输入的单词符分析并判定输入的单词符 号串是否符合该语言的语号串是否符合该语言的语 法规则法规则(上下文无关文法上下文无关文法)实质实质就是按照文法的产生式，就是按照文法的产生式，识别输入符号串是否为一识别输入符号串是否为一 个句子个句子(合法程序，语句，合法程序，语句，表达式等表达式等)4.14.1语法分析的功能语法分析的功能 22.8.9copyright/6 陕西理工学院 计算机系 编译原理6 设计思想设计思想判断是否能从文法的开始符号出发推导
5、出这个输入串判断是否能从文法的开始符号出发推导出这个输入串或者或者,判断能否建立一棵与输入串匹配的语法分析树判断能否建立一棵与输入串匹配的语法分析树 输入输入 单词符号串单词符号串 输出输出 语法分析树语法分析树格式化的程序格式化的程序合法的表达式、语句、函数合法的表达式、语句、函数 出错处理要求出错处理要求尽快发现错误，准确定位尽快发现错误，准确定位可能时进行恢复处理，继续语法分析可能时进行恢复处理，继续语法分析4.14.1语法分析的功能语法分析的功能 22.8.9copyright/7 陕西理工学院 计算机系 编译原理7根据建立方法，语法分析算法可分为根据建立方法，语法分析算法可分为两大类
6、两大类:自上而下分析法自上而下分析法从文法的开始符号出发，反复使用各种产生式向从文法的开始符号出发，反复使用各种产生式向 下推导，寻找与输入符号串匹配的推导下推导，寻找与输入符号串匹配的推导 自下而上分析法自下而上分析法从输入串开始，逐步进行归约，直至归约到文法从输入串开始，逐步进行归约，直至归约到文法 的开始符号的开始符号 两种方法反映了两种不同的语法树的构造过程两种方法反映了两种不同的语法树的构造过程自上而下自上而下从树根推导到树叶从树根推导到树叶自下而上自下而上从树叶归约到树根从树叶归约到树根4.14.1语法分析的功能语法分析的功能 22.8.9copyright/8 陕西理工学院 计算
7、机系 编译原理84.2 4.2 自上而下分析面临的问题自上而下分析面临的问题 基本方法基本方法对任何输入串对任何输入串,试图从文法的开始符号出发，试图从文法的开始符号出发，自上而下地为输入串建立一棵语法树自上而下地为输入串建立一棵语法树或者说，为输入串寻找一个最左推导或者说，为输入串寻找一个最左推导 过程本质过程本质是一种试探过程，是反复使用不同产生式是一种试探过程，是反复使用不同产生式 谋求匹配输入串的过程谋求匹配输入串的过程如何选择哪个产生式进行推导如何选择哪个产生式进行推导?4.24.2自上而下分析面临的问题自上而下分析面临的问题 22.8.9copyright/9 陕西理工学院 计算机
8、系 编译原理9 例例 文法文法GS SxAy Aab|aGS SxAy Aab|a 判断输入串判断输入串 w=x a yw=x a y是否为该文法的句子？是否为该文法的句子？4.24.2自上而下分析面临的问题自上而下分析面临的问题 22.8.9copyright/10 陕西理工学院 计算机系 编译原理10 公共左因子公共左因子产生回溯产生回溯例例 文法文法G:S xAyG:S xAy A A a ab|b|a a无法确定非终结符无法确定非终结符A A面临输入符面临输入符 号号a a时选用哪个关于时选用哪个关于A A的候选式的候选式 左递归左递归无限循环无限循环例例 文法文法G:G:S S S
9、Sa|abaa|aba4.24.2自上而下分析面临的问题自上而下分析面临的问题 22.8.9copyright/11 陕西理工学院 计算机系 编译原理11为了构造不带回溯的自上而下分析算法为了构造不带回溯的自上而下分析算法 消除文法的左递归消除文法的左递归 消除回溯、提取左因子消除回溯、提取左因子 LL(1)LL(1)分析条件分析条件LL(1)LL(1)文法文法4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/12 陕西理工学院 计算机系 编译原理12关于非终结符关于非终结符P P的规则的规则 直接左递归定义直接左递归定义：若：若P PP P 、*例如例如 E
10、E E E+T+TT T（含有（含有E E的左递归）的左递归）T T T T*F FF F（含有（含有T T的左递归）的左递归）F (E)F (E)i i 4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/13 陕西理工学院 计算机系 编译原理13 间接左递归定义：间接左递归定义：若若P=P=+P P *例如例如 间接左递归间接左递归 S AaS Aa A Sb|b A Sb|b S=Aa=Sba S=Aa=Sba 即即S=S=+SbSb 用用S S的产生式右部替换的产生式右部替换A A右部的右部的S S得：得：A Aab|bA Aab|b 变成变成A A的产生
11、式含有直接左递归的产生式含有直接左递归4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/14 陕西理工学院 计算机系 编译原理14改写为等价的右递归改写为等价的右递归 形如：形如：P PP P 非非，不以不以P P开始开始 改写为：改写为：PPP P（P P为新增加的非终结符）为新增加的非终结符）PPPP 改写前产生式可产生短语改写前产生式可产生短语 P=PP=P=改写后产生式可产生短语改写后产生式可产生短语 P=P=P P =PP =4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/15 陕西理工学院 计算机系 编译原理15E
12、E E E+T+TT TT T T T *F FF FF (E)F (E)i iE E T ET EE +T EE +T ET T F TF TT T *F T F TF F (E)(E)i i4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/16 陕西理工学院 计算机系 编译原理16 若有多个左递归的产生式如：若有多个左递归的产生式如：PPPP1 1|P|P2 2|P|Pm m|1 1|2 2|n n4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/17 陕西理工学院 计算机系 编译原理17练习练习 例如有文法：例如有文法：KK
13、a|Kb|Kc|d|eKKa|Kb|Kc|d|e 4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/18 陕西理工学院 计算机系 编译原理18间接左递归消除举例间接左递归消除举例 S Qc S Qcc c Q Rb Q Rbb b R R SaSaa aS=Qc=Rbc=Sabc S=Qc=Rbc=Sabc 是间接左递归是间接左递归消除方法消除方法1 1：将非终结符排序：将非终结符排序：R Q SR Q S 将将R R的右部的右部代入代入Q Q，S S：Q Q SaSab ba ab bb b S Qc S Qcc c（不变）（不变）4.3 LL4.3 LL（1
14、 1）分析法）分析法 22.8.9copyright/19 陕西理工学院 计算机系 编译原理19 S S Qc Qcc c Q Rb Q Rbb b R R SaSaa a消除方法消除方法2 2：将非终结符排序：将非终结符排序：S Q RS Q R 将将S S的右部的右部代入代入Q Q，R R：Q RbQ Rbb b（不变）（不变）R R QcQca ac ca a|a a4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/20 陕西理工学院 计算机系 编译原理20消除左递归算法消除左递归算法 1.1.以某种以某种S S顺序将文法的非终结符排列顺序将文法的非终结符
15、排列 P P1 1，P P2 2，,P,Pn n 2.FOR i:=1 TO n DO2.FOR i:=1 TO n DO BEGIN BEGIN FOR j:=1 TO i-1 DO FOR j:=1 TO i-1 DO 把形如把形如P Pi iPPj j的规则改写成的规则改写成 P Pi i1 1|2 2|k k,其中其中 P Pj j1 1|2 2|是关于是关于P Pj j的所有规则的所有规则;消除消除P Pi i的直接左递归的直接左递归 ENDEND 3.3.化简由化简由2 2所得的文法，即去除那些从开始符号所得的文法，即去除那些从开始符号 出发永远无法到达的非终结符的产生式出发永远无
16、法到达的非终结符的产生式4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/21 陕西理工学院 计算机系 编译原理21 消除回溯目的消除回溯目的对文法的任何非终结符，当它去匹配输入串对文法的任何非终结符，当它去匹配输入串 时，能够根据输入符号，时，能够根据输入符号，准确地准确地选择合适的选择合适的 候选式去候选式去匹配匹配若需要若需要非终结符非终结符A A去匹配输入串，去匹配输入串，A A的候选式的候选式 为为AA1 1|2 2|n n ，A A所面临的第一所面临的第一 个个输入符号为输入符号为a a时，时，A A能准确地选择能准确地选择i i去执行去执行 匹配任
17、务，则无需回溯匹配任务，则无需回溯4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/22 陕西理工学院 计算机系 编译原理22 对于所有形如对于所有形如 AA1 12 2.n n的规则的规则 其中，其中，为左因子，为左因子，不以不以开头开头 改写为改写为AAAA 其中其中A A为新增加的非终结符为新增加的非终结符 AA1 12 2.n n 例如例如 S xAyS xAy A A a ab|b|a a4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/23 陕西理工学院 计算机系 编译原理234.3.3 LL(1)4.3.3 LL(1
18、)分析条件分析条件 FIRSTFIRST集合的定义集合的定义 FOLLOWFOLLOW集合的定义集合的定义 LL(1)LL(1)分析条件分析条件 LL(1)LL(1)文法的定义文法的定义4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/24 陕西理工学院 计算机系 编译原理24设设G=(G=(T T，N N，S S，P P）*FIRST(FIRST()=a|)=a|=*a a，aaT T 若若=*，则，则FIRST(FIRST()FIRST(FIRST()是是的所有可能推导的首遇的所有可能推导的首遇 终结符号或终结符号或，是选择产生式的依据，是选择产生式的依据4
19、.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/25 陕西理工学院 计算机系 编译原理25 A A N N FOLLOW(FOLLOW(A A)=)=a aS=S=*A Aa a，a aT T 若若S=S=*A A，则，则#FOLLOWFOLLOW（A A）#输入串的结束符输入串的结束符 也可看作是句子的括号也可看作是句子的括号#S#S#FOLLOW(A)FOLLOW(A)表示了句型中可能紧跟在表示了句型中可能紧跟在A A后面的终结符号后面的终结符号4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/26 陕西理工学院 计算机系 编
20、译原理26 非终结符非终结符A A的所有候选首符集两两不相交，的所有候选首符集两两不相交，即即A A的任何两个不同候选的任何两个不同候选和和，满足：，满足：FIRST(FIRST()FIRST()FIRST()=)=当要求当要求 A A 匹配输入串时，匹配输入串时，A A就能根据它所面就能根据它所面 临的第一个输入符号临的第一个输入符号 a a，准确地指派某一个，准确地指派某一个 候选去执行任务，这个候选就是那个候选去执行任务，这个候选就是那个终结首终结首 符集含符集含 a a 的的4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/27 陕西理工学院 计算机系
21、编译原理27 当非终结符当非终结符 A A 面临输入符号面临输入符号a a，但，但a a不属于不属于A A 的任何候选首符集，如果的任何候选首符集，如果A A有候选式有候选式AA(A(A 的某个候选首符集包含的某个候选首符集包含)，可以，可以让让A A自动得自动得 到匹配到匹配，即，即A A匹配于空字匹配于空字，但输入符号不读，但输入符号不读 进进 要想让要想让A A自动匹配成功，需要考察自动匹配成功，需要考察FOLLOW(A)FOLLOW(A)4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/28 陕西理工学院 计算机系 编译原理284.3 LL4.3 LL（
22、1 1）分析法）分析法 22.8.9copyright/29 陕西理工学院 计算机系 编译原理29 输入输出输入输出输入：符号串输入：符号串(有序的有序的)输出：结构化的符号串输出：结构化的符号串(树结构树结构)产生式的选择产生式的选择根据当前符号（单词）根据当前符号（单词）语法分析树的表示语法分析树的表示按照使用序列排列的产生式序列按照使用序列排列的产生式序列4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/30 陕西理工学院 计算机系 编译原理30 文法不含左递归文法不含左递归 对于文法的每个非终结符对于文法的每个非终结符 A A 的任何两的任何两 个不同的
23、产生式个不同的产生式 A|A|1)FIRST()FIRST()=1)FIRST()FIRST()=2)=2)=*和和=*不能同时成立不能同时成立3)3)如果如果=*，则，则 FISRT(/FISRT(/A A)FOLLOW(A)=)FOLLOW(A)=满足以上条件的文法称为满足以上条件的文法称为LL(1)LL(1)文法文法4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/31 陕西理工学院 计算机系 编译原理31 含义含义第一个第一个 L L 表示从左向右扫描输入符号串表示从左向右扫描输入符号串第二个第二个 L L 表示生成最左推导表示生成最左推导1 1 表示读
24、入一个符号可确定下一步推导表示读入一个符号可确定下一步推导对于对于LLLL（1 1）文法，可以对输入串进行有效的无回）文法，可以对输入串进行有效的无回溯的自上而下分析。溯的自上而下分析。对于文法对于文法G G，当面临的输入符号为，当面临的输入符号为a a，要用非终结符，要用非终结符A A进行匹配时，假设进行匹配时，假设A A的所有产生式为的所有产生式为 AA1 1|2 2|n n1)1)若若aFIRST(aFIRST(i i )，则指派，则指派i i去执行任务去执行任务2)2)若若a a不属于不属于任何任何候选首符集，则：候选首符集，则：若若属于某个属于某个FIRST(FIRST(i i )且
25、且 aFOLLOW(A)aFOLLOW(A)，则让，则让A A与与自动匹配自动匹配 否则，否则，a a的出现是一种语法错误的出现是一种语法错误4.3 LL4.3 LL（1 1）分析法）分析法 22.8.9copyright/32 陕西理工学院 计算机系 编译原理32不带回溯的自上而下分析程序不带回溯的自上而下分析程序4.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/33 陕西理工学院 计算机系 编译原理334.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/34 陕西理工学院 计算机系 编译原理34C C语言语言 E
26、 E（）T;T;E E;22.8.9copyright/35 陕西理工学院 计算机系 编译原理35E E()()if(c=if(c=+)p+;p+;T T;E E;4.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/36 陕西理工学院 计算机系 编译原理36C C语言练习语言练习T()T()F F;T T;4.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/37 陕西理工学院 计算机系 编译原理374.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/38 陕西理工学院 计算机系 编
27、译原理38procedure F;procedure F;begin begin if sym=(then if sym=(then begin advance;E;begin advance;E;if sym=if sym=)then advance then advance else error else error括号不匹配括号不匹配 end end else if sym=else if sym=i i then advance then advance else error F else error F面临非（，面临非（，i i输入符号，语法错误输入符号，语法错误 end end4.
28、4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/39 陕西理工学院 计算机系 编译原理394.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/40 陕西理工学院 计算机系 编译原理40i+ii+i的递归下降分析过程的递归下降分析过程 i ii i生成语法分析树生成语法分析树i+i#i+i#匹配成功返回，指针下移匹配成功返回，指针下移自动匹配，返回自动匹配，返回自动匹配，返回自动匹配，返回自动匹配，返回自动匹配，返回匹配成功继续，指针下移匹配成功继续，指针下移匹配成功返回，指针下移匹配成功返回，指针下移分析成分析成功结束
29、功结束4.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/41 陕西理工学院 计算机系 编译原理41 优点：优点：1 1）直观、简单、可读性好）直观、简单、可读性好2 2）便于扩充）便于扩充 缺点：缺点：1)1)递归算法的实现效率低递归算法的实现效率低2)2)处理能力相对有限处理能力相对有限3)3)通用性差，难以自动生成通用性差，难以自动生成4.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/42 陕西理工学院 计算机系 编译原理424.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyrigh
30、t/43 陕西理工学院 计算机系 编译原理434.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/44 陕西理工学院 计算机系 编译原理444.4 4.4 递归下降分析程序构造递归下降分析程序构造 22.8.9copyright/45 陕西理工学院 计算机系 编译原理45 实现实现LL(1)LL(1)分析的另一种有效方法使用一张二维分分析的另一种有效方法使用一张二维分析表（析表（预测分析表预测分析表）和一个分析栈（）和一个分析栈（文法符号栈文法符号栈）联合进行控制来实现自上而下分析技术联合进行控制来实现自上而下分析技术4.5 4.5 预测分析程序预测分析程
31、序 22.8.9copyright/46 陕西理工学院 计算机系 编译原理4622.8.9copyright/47 陕西理工学院 计算机系 编译原理47输入符号（终结符和输入符号（终结符和#）非终非终结符结符 i i +*()#E E E ETETE E ETETE E E E E+TE+TE E E E E T T T TFTFT T TFTFT T T T T*FT*FT T T T T F Fi i F F(E)(E)22.8.9copyright/48 陕西理工学院 计算机系 编译原理48 分析栈用于存放分析过程中的文法符号分析栈用于存放分析过程中的文法符号22.8.9copyrigh
32、t/49 陕西理工学院 计算机系 编译原理494.5 4.5 预测分析程序预测分析程序 22.8.9copyright/50 陕西理工学院 计算机系 编译原理50对于任何（对于任何（X X，a a）X X是栈顶符号是栈顶符号 a a是面临输入符号是面临输入符号(1)X(1)XT T 且且X Xa a#，分析成功结束，输入串是，分析成功结束，输入串是 一个合法句子一个合法句子(2)X(2)XT T 且且X Xaa#，X X出栈，输入指针指向下一出栈，输入指针指向下一 输入符号输入符号(3)X(3)XN N，查分析表，查分析表MXMX，aa 若若MXMX，a=a=XXi i，X X出栈，出栈，i
33、i逆序入栈，输入指针逆序入栈，输入指针 不动不动 若若MXMX，a=a=空空，则调用，则调用errorerror程序，进行错误处理程序，进行错误处理4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/51 陕西理工学院 计算机系 编译原理51 栈栈 输入缓冲区输入缓冲区 所用产生式所用产生式0#0#E E i i*i+i#i+i#E TE ETE TE ET入栈入栈1#ET i1#ET i*i+i#i+i#T FTT FT 2#ET2#ETF F i i*i+i#F i+i#F i i3#ETi i3#ETi i*i+i#i+i#i i出栈，出栈，a a下移下移4#E4#
34、ETT *i+i#Ti+i#T*FT FT 5#ETF5#ETF*i+i#i+i#*出栈，出栈，a a下移下移6#ET6#ETF F i i+i#F +i#F i i 7#ETi i+i#7#ETi i+i#i i出栈，出栈，a a下移下移4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/52 陕西理工学院 计算机系 编译原理52 栈栈 输入缓冲区输入缓冲区 所用产生式所用产生式8#E8#ET T +i#T i#T 9#E +i#E +TE9#E +i#E +TE10#ET10#ET+i#i#11#ET i#T FT11#ET i#T FT12#ET12#ETF F i
35、 i#F i#F i13#ETi i#13#ETi i#14#E14#ETT#T T 15#E#E 15#E#E 16 16#=#=#分析成功结束分析成功结束4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/53 陕西理工学院 计算机系 编译原理53栈栈 输入缓冲区输入缓冲区 所用产生式所用产生式0#0#E E i i+i#E TE+i#E TE1#ET i+i#T FT1#ET i+i#T FT2#ET2#ETF F i i+i#F i+i#F i 3#ETi i+i#3#ETi i+i#4#E4#ET +T +i#T i#T 5#E +i#E +TE5#E +i#E
36、 +TE6#ET6#ET+i#i#7#ET i#T FT 7#ET i#T FT 4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/54 陕西理工学院 计算机系 编译原理54i+i i+i 分析分析过程过程续续栈栈 输入缓冲区输入缓冲区 所用产生式所用产生式8#ET8#ETF F i i#F i#F i9#ETi i#9#ETi i#10#E10#ETT#T T 11#E#E 11#E#E 12 12#=#=#分析成功分析成功4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/55 陕西理工学院 计算机系 编译原理55栈栈 输入缓冲区输入缓冲区 所
37、用产生式所用产生式0#E i+i0#E i+i*i#E TEi#E TE1#E1#ET T i i+i+i*i#i#T FT T FT2#ETF i+i2#ETF i+i*i#F ii#F i3#ET3#ETi i i i+i+i*i#i#4#ET +i4#ET +i*i#T i#T 5#5#EE +i i*i#E +TEi#E +TE6#ET+i6#ET+i*i#i#7#E7#ET T i i*i#T FT i#T FT 4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/56 陕西理工学院 计算机系 编译原理56栈栈 输入缓冲区输入缓冲区 所用产生式所用产生式8#ET
38、F i8#ETF i*i#F i i#F i 9#ET9#ETi ii i*i#i#10#ET 10#ET *i#T i#T *FTFT11#ETF11#ETF*i#i#12#ETF i#F i12#ETF i#F i13#ET13#ETi ii i#14#ET#T 14#ET#T 15#15#E#E#E E 16#16#4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/57 陕西理工学院 计算机系 编译原理57BEGINBEGIN PUSH(STACK,PUSH(STACK,#)；PUSH(STACK,PUSH(STACK,开始符号开始符号););a=a=第一个输入符
39、号；第一个输入符号；FLAG:=TRUEFLAG:=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN X=POP(STACK);X=POP(STACK);IF X IF XT T THEN THEN IF X=a THEN a=IF X=a THEN a=下一个符号下一个符号 终结符匹配终结符匹配 ELSE ERROR ELSE ERROR与当前输入符号不匹配与当前输入符号不匹配 4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/58 陕西理工学院 计算机系 编译原理58ELSE IF X=ELSE IF X=#THEN THEN
40、IF X=a FLAG:=FALSE ELSE ERROR IF X=a FLAG:=FALSE ELSE ERROR4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/59 陕西理工学院 计算机系 编译原理594.5.2 4.5.2 预测分析表的构造预测分析表的构造设有文法设有文法G G，预测分析表构造过程：，预测分析表构造过程：计算计算所有候选式所有候选式的首符集的首符集 FIRSTFIRST（）计算计算所有非终结符所有非终结符A A的后继符集的后继符集 FOLLOWFOLLOW（A A）构造构造预测预测分析表分析表 M M4.5 4.5 预测分析程序预测分析程序 2
41、2.8.9copyright/60 陕西理工学院 计算机系 编译原理60 FIRST(FIRST()=)=a a=*a a ，aaT T 若若=*，则，则 FIRST()FIRST()计算文法符号计算文法符号X X的的FIRSTFIRST（X X）计算文法符号串计算文法符号串=X=X1 1X X2 2X Xn n的的FIRST()FIRST()4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/61 陕西理工学院 计算机系 编译原理61重复以下计算，直到重复以下计算，直到FIRSTFIRST（X X）不再增大为止：）不再增大为止：1)1)若若 X XT T，则，则 FIR
42、ST(FIRST(X X)=)=X X 。例例 FIRSTFIRST（+）=+FIRST FIRST（i i）=i i 2)2)若若 XXN N，若有若有XaXa，则将，则将 a a 加入加入FIRST(X)FIRST(X)；例例 E+TE +FIRSTE+TE +FIRST（E E）FF（E E）|i|i （，（，iFIRSTiFIRST（F F）若有若有X X，则将，则将加入加入FIRST(X)FIRST(X)。例例 E E FIRST FIRST（E E）4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/62 陕西理工学院 计算机系 编译原理6222.8.9cop
43、yright/63 陕西理工学院 计算机系 编译原理63 若有文法若有文法G为：为：X YX Y1 1 Y Y2 2 Y Y3 3 Y Y4 4 Y Y5 5 Y Y1 1 a a Y Y2 2 b b Y Y3 3 c c Y Y4 4 d d Y Y5 5 e ef f4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/64 陕西理工学院 计算机系 编译原理64文法文法G为：为：E T EE T EE+T EE+T ET F T T F T TT*F T F T F(E)F(E)i i4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/65 陕西
44、理工学院 计算机系 编译原理65=a=a，c c，d d，q q 4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/66 陕西理工学院 计算机系 编译原理66候选式的候选式的FIRSTFIRST集集FIRST(FIRST(T TE E)=)=FIRST(FIRST(T T)=(,i)=(,iFIRST(FIRST(+TETE)=)=+FIRST(FIRST(F FT T)=)=FIRST(FIRST(F F)=(,i)=(,iFIRST(FIRST(*FTFT)=)=*FIRST(FIRST(E)E)=)=(FIRST(FIRST(i i)=)=i i FIRST()=
45、FIRST()=4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/67 陕西理工学院 计算机系 编译原理67候选式的候选式的FIRSTFIRST集集FIRST(FIRST(A Ap p)=FIRST()=FIRST(A A)=a,c)=a,cFIRST(FIRST(BqBq)=FIRST()=FIRST(B B)-)-FIRST(FIRST(q q)=d,q =d,qFIRST(FIRST(a a)=a)=aFIRST(FIRST(c cA A)=c)=cFIRST(FIRST(d dB B)=d)=dFIRST()=FIRST()=4.5 4.5 预测分析程序预测分析
46、程序 22.8.9copyright/68 陕西理工学院 计算机系 编译原理68 FOLLOW(FOLLOW(A A)=a)=aS=S=*A Aa a，aaT T 若若S=S=*A A，则，则#FOLLOW#FOLLOW（A A）重复以下计算，直到每个重复以下计算，直到每个FOLLOW(A)FOLLOW(A)不再增大为止：不再增大为止：1)1)将将#加入到加入到 FOLLOW(FOLLOW(S S)中中 例例#FOLLOW(FOLLOW(E E)2)2)若若AAB B,则将则将FIRST()-FIRST()-加入加入FOLLOW(FOLLOW(B B)4.5 4.5 预测分析程序预测分析程序
47、22.8.9copyright/69 陕西理工学院 计算机系 编译原理69 3)3)若若 A A B B ，或，或 A A B B，且且 =*，即即 FIRST()FIRST()，ABAB 则将则将FOLLOW(A)FOLLOW(A)所有元素加入所有元素加入FOLLOW(FOLLOW(B B)4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/70 陕西理工学院 计算机系 编译原理7022.8.9copyright/71 陕西理工学院 计算机系 编译原理71非终结符非终结符FOLLOWFOLLOW集集FOLLOW(S)=#FOLLOW(S)=#FOLLOW(A)=FIRS
48、T(p)-FOLLOW(A)=FIRST(p)-=p =pFOLLOW(B)=FIRST(q)-FOLLOW(B)=FIRST(q)-=q =q4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/72 陕西理工学院 计算机系 编译原理72 满足条件（满足条件（3 3）：）：E E FIRST(+TE FIRST(+TE)=+FOLLOW(E)=+FOLLOW(E)=),#)=),#T T FIRST(FIRST(*FTFT)=)=*FOLLOW(FOLLOW(T T)=)=+,),#+,),#文法文法G G是是LLLL（1 1）文法）文法 22.8.9copyright/
49、73 陕西理工学院 计算机系 编译原理73(4)(4)把所有无定义的把所有无定义的 MA,aMA,a标上标上“出错标志出错标志”4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/74 陕西理工学院 计算机系 编译原理74预测分析表的构造算法举例预测分析表的构造算法举例4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/75 陕西理工学院 计算机系 编译原理75 1)1)编写文法，消除二义性；编写文法，消除二义性；2)2)消除左递归、提取左因子；消除左递归、提取左因子；3)3)求求 FIRST FIRST 集合和集合和 FOLLOW FOLLOW 集
50、合集合 4 4）检查是不是）检查是不是 LL(1)LL(1)文法文法若不是若不是 LL(1),LL(1),说明文法的复杂性超过自上说明文法的复杂性超过自上 而下方法的分析能力而下方法的分析能力 5 5）按照）按照 LL(1)LL(1)文法构造预测分析表文法构造预测分析表 6 6）实现预测分析器）实现预测分析器4.5 4.5 预测分析程序预测分析程序 22.8.9copyright/76 陕西理工学院 计算机系 编译原理76语法错误：语法错误：栈顶终结符与当前输入符不匹配栈顶终结符与当前输入符不匹配 栈顶非终结符栈顶非终结符A A面临输入符面临输入符a a，但分，但分 析表析表M M中中MA,a
