自顶向下语法分析方法.ppt

第五章自顶向下语法分析方法 学习目标 掌握 LL 1 文法的判别 预测分析法 递归子程序的构造方法理解 LL 1 文法了解 不确定的自顶向下分析 语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子分类 自顶向下的基本思想 从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子 5 1确定的自顶向下分析思想5 2LL 1 文法的判别5 3某些非LL 1 文法到LL 1 文法的等价变换5 4不确定的自顶向下分析思想5 5确定的自顶向下分析方法 5 1确定的自顶向下分析思想 1确定分析的条件2开始符号集FIRST 的定义3后跟符号集FOLLOW A 的定义4选择集合SELECT A 的定义5LL 1 文法的定义 1确定分析的条件 从文法的开始符出发 如能根据当前的输入符号 单词符号 唯一地确定选用哪个产生式进行推导 则分析是确定的 例1设有文法G1 S S pA qBA cAd aB dB b若输入串W pccadd 自顶向下的推导过程为 S S pA pcAd pccAdd pccadd G1 S 有如下特点 1 每个产生式的右部由终结符开头 2 同一非终结符的不同产生式的右部由不同的终结符开头 对于这种文法 在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导 即分析过程是确定的 例2 设有文法G2 S 为 S Ap BqA a cAB b dB S ccap S cAp ccAp Ap 该例说明 当 1 产生式右部以终结符或非终结符开头 无空产生式 2 同一非终结符的不同产生式的右部由不同的符号开头 对于这种文法 在推导过程选用哪个产生式不直观 关键是判断产生式右部推出的开始符号 集 分析过程可能是确定 若输入串W ccap 自顶向下的推导过程为 例3 设有文法G3 S S aA dA bAS 若输入串W abd 自顶向下的推导过程为 S abd S abAS abS 文法的特点是 包含空产生式对于空产生式左部的非终结符 关键是判断该非终结符的后跟符号 集 分析过程可能是确定的 aA 要进行确定的自顶向下的分析 文法要满足一定的限制 即文法是LL 1 文法 先研究三个定义开始符号集FIRST后跟符号集FOLLOW选择集合SELECT 2开始符号集FIRST 的定义 定义 设G VN VT P S 是上下文无关文法 VN VT FIRST a VT a 若 则规定 FIRST 直观上说文法符号串 的开始符号集是由 推导出的开头的终结符 包括 组成 例文法G2 S S ApS BqA aA cAB bB dB FIRST Ap a c FIRST Bq b d FIRST a a FIRST cA c FIRST b b FIRST dB d 由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交 因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导 可以进行确定的自顶向下分析 3后跟符号集FOLLOW A 的定义 定义设G VT VN P S 是上下文无关文法 A VN FOLLOW A a S Aa a VT 若有S A 则规定 FOLLOW A 注 输入串 做为输入串的结束符 直观上说 非终结符A的后跟符号集是由句型中紧跟A后的那些终结符 包括 组成 例文法G3 S S aA dA bAS 由S S得 FOLLOW S 由S aA abAS abbASS abbASaA abbASdFOLLOW S a d 由S aA得 FOLLOW A 由S abAS abAaA得a FOLLOW A abAd得d FOLLOW A FOLLOW A a d 说明 对于非终结符A的两个产生式A bAS和A 当输入符号 FIRST bAS b 时 选A bAS推导 当输入符号 FOLLOW A a d 时 选A 推导 由于FIRST bAS FOLLOW A 所以可进行确定的自顶向下分析 4选择集合SELECT A 的定义 定义对给定的上下文无关文法的产生式A A VN V 若 则SELECT A FIRST 若 则SELECT A FIRST FOLLOW A 解释当A面对应输入符a 在自顶向下的分析中应选择这样的产生式A 进行推导 First 中包含a 此外若 可能导出空串 A自动获得匹配 输入符a有可能与A后的一个符号匹配 所以当a应属于Follow A 时 选择产生式A 也是可以的 直观上说某产生式A 的选择集合是指遇到哪些输入符号 包括 时选用该产生式向下推导 例G3 S S aAS dA bASA SELECT S aA FIRST aA a SELECT S d FIRST d d SELECT A bAS FIRST bAS b SELECT A FOLLOW A a d 若 则SELECT A FIRST 若 则SELECT A FIRST FOLLOW A 说明 同一非终结符的不同产生式A 与A 若SELECT A SELECT A 则一定可以进行确定的自顶向下分析 5LL 1 文法的定义 定义 一个上下文无关文法是LL 1 文法的充分必要条件是 对每个非终结符A的两个不同产生式A 与A 满足SELECT A SELECT A LL 1 文法的含义是 第一个L表示从左到右扫描输入串第二个L表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式进行推导 类似地LL k 文法需要向前看K个符号才可以确定选用哪个产生式 例有文法G S 为 S aASS bA bAA SELECT S aAS a SELECT S b b SELECT A bA b SELECT A Follow A a b 由于SELECT A bA SELECT A b 所以文法G S 不是LL 1 文法 当A遇输入符b时 不能确定选A bA还是A 去推导 5 2LL 1 文法的判别 要判别一个上下文无关文法是否是LL 1 文法分为五步 1 求能推出 的非终结符集2 计算每个产生式右部 的FIRST 集3 计算每个非终结符A的FOLLOW A 集4 计算每个产生式A 的SELECT A 集5 按LL 1 文法的定义判别 1 求出能推出 的非终结符集 算法 用S表示能推出 的非终结符集第一步令S Aj Aj 产生式集 对每个产生式p Ap X1 Xn 若X1 Xn S 则S S Ap 重复第二步的循环 直至S收敛 不再变化 为止 例G S S AB bCA b B aD C AD bD aS c 非终结符集S 能推出 的非终结符集为 A B S 2 计算每个产生式右部 的FIRST 集 首先对每一文法符号X X VT VN 求FIRST X 的算法 对每个a VT First a a 对每个A VN 若A 则First A 否则First A 对每个产生式A X1 Xj Xn做 First A First A SectionFirst X1 Xj Xn 其中SectionFirst X1 Xj Xn First X1 First X2 First Xj First Xj 1 Xj 1是产生式右部中第一个不能推出 的符号若X1 则SectionFirst X1 Xj Xn First X1 若X1 Xn全可推出 则SectionFirst X1 Xn FIRST X1 FIRST Xn 重复3直到每个符号的FIRST集合都不再增大为止 例G S S AB bCA b B aD C AD bD aS c First集 3 First集 2 First集 1 A B C D a b S First集 0 已求出能推出 的非终结符集为 A B S b b a b ac a ac 利用求出每个文法符号的FIRST集求符号串的FIRST集 设 X1X2 Xn当X1不能 则FIRST FIRST X1 若对任何j 1 j n 都有 FIRST Xj 则FIRST FIRST X1 FIRST Xj FIRST Xj 1 若对所有i 1 i n 都有 FIRST Xi 则FIRST FIRST X1 FIRST Xn 例G S S AB bCA b B aD C AD bD aS c 已求出非终结符的First集合如下 First S a b First A b First B a First C a b c First D a c 产生式右部符号串的开始符集合为 S ABFIRST AB FIRST A FIRST B a b S bCFIRST bC b A FIRST A bFIRST b b C ADFIRST AD FIRST A FIRST D b a c D aSFIRST aS a 3 计算每个非终结符A的FOLLOW A 集 1 对所有A VN令Follow A 对开始符S 令Follow S 因为S S 显然 FOLLOW S 2 对每条产生式A xBy 考察产生式右部的每一非终结符B x y V 如果y不能推出 Follow B Follow B First y 否则Follow B Follow B First y Follow A 3 重复2 直至对所有A VN Follow A 收敛为止 若a FOLLOW A 则表明S Aa 由于A xBy 且y 则有S Aa xBya xBa 即S xBa 所以a FOLLOW B 例G S 1 S AB 2 S bC 3 A b 4 A 5 B aD 6 B 7 C AD 8 C b 9 D aS 10 D c 已求出非终结符的First集合如下 First S a b First A b First B a First C a b c First D a c D C B a A S Follow集 2 Follow集 1 Follow集 0 c 4 计算每个产生式A 的SELECT A 集 按定义计算SELECT A 若 则SELECT A FIRST 若 则SELECT A FIRST FOLLOW A 例G S S AB bCA b B aD C AD bD aS c 部分产生式的select集合SELECT S AB FIRST AB FOLLOW S b a SELECT S bC FIRST bC b SELECT A FIRST FOLLOW A a c SELECT A b FIRST b b SELECT B aD FIRST aD a SELECT C AD FIRST AD b a c 5 按LL 1 文法的定义判别 产生式的select集如下 SELECT S AB b a SELECT S bC b SELECT A a c SELECT A b b SELECT B SELECT B aD a SELECT C AD b a c SELECT C b b SELECT D aS a SELECT D c c 由于SELECT S AB SELECT S bC b SELECT C AD SELECT C b b 所以文法G S 不是LL 1 文法 5 3某些非LL 1 文法到LL 1 文法的等价变换 非LL 1 文法含有左公共因子的文法若文法中含有形如 A r的产生式 称文法含有左公共因子 显然 SELECT A SELECT A r 文法不是LL 1 文法 含有左递归的文法文法中只要含有下列形式的产生式 含有a或含有b或二者皆有 则称文法含有左递归 A A A B B A 在a 中含有左递归的产生式 称为直接左递归 在b 中虽然没有含左递归的产生式 但A B A 即A A 称为间接左递归 以直接左递归为例 若有如下产生式A A A 其中 和 为任意语法符号串 不难证明有下面关系式 Select A A First A First Select A First 故A A 和A 的Select集相交 不是LL 1 文法 对非LL 1 文法进行等价变换提取左公共因子消除左递归注意 变换后的文法不一定是LL 1 文法 文法不含左递归和左公共因子只是LL 1 文法的必要条件 1提取左公共因子 将产生式A r等价变换为 A r 将括号内用一新引入的非终结符A 表示 得A A A r一般形式 若A 1 2 n 提取左公共因子后变为A A A 1 2 n若在 i中仍含有左公共因子 可再次提取 例文法G1 S aSb aS 提左因子得 S aS b 引进新的非终结符得 S aSS S b 2 消除左递归 消除直接左递归文法G S Sa b可改写成S bS S aS 一般情形 含直接左递归的文法G A A 1 A 2 A m 1 2 n消除左递归后改写成 A 1A 2A nA A 1A 2A mA 消除间接左递归将间接左递归变成直接左递归 再消除算法步骤 把文法的所有非终结符按任一顺序排列 如 A1 A2 An从A1开始 按以下顺序处理Ai 首先 消除左部为Ai的产生式的直接左递归然后 若左部为Ai的产生式的右部为非终结符Aj j i 开头 即Ai Aj 则用左部为Aj的所有产生式的右部分别代替Ai Aj 中的Aj最后 得到的左部为Ai的产生式若有直接左递归 则消除之去掉无用产生式 例文法G 1 S Qc c 2 Q Rb b 3 R Sa a 将非终结符排序 R Q S对R 产生式 3 不含直接左递归 所以保持不变对Q 把 3 代入 2 得 2 Q Sab ab b 无直接左递归对S 把 2 代入 1 得 1 S Sabc abc bc c 有直接左递归 消除直接左递归得S abcS bcS cS S abcS 处理结果为 R Sa aQ Sab ab bS abcS bcS cS S abcS 由于Q R是不可到达的非终结符 其产生式应删除 最终得文法G S abcS bcS cS S abcS 示例说明 当非终结符顺序为R Q S 消除左递归的最终结果为 S abcS bcS cS S abcS 若非终结符顺序为S Q R 则消除左递归的最终结果为 S Qc cQ Rb bR bcaR caR aR R bcaR 结论 当非终结符的排序不同时 结果的产生式形式不同 但它们是等价的 5 4不确定的自顶向下分析思想 不确定的自顶向下分析也称带回溯的自顶向下分析定义 不确定是指某个非终结符有多条产生式 而面临当前输入符无法唯一确定选用哪条产生式进行推导 只好逐个试探 当分析不成功时 则推翻分析退回到适当位置重新试探其余候选可能的推导 直到把所有可能的推导序列都试完仍不成功 才能确认输入串不是该文法的句子 例1设有文法S xAyA ab a 对输入串w xay 推导树为 由于A的两条产生式 A ab和A a右部First集交集不为空 从而引起回溯 例2文法G S aASS bA bASA 输入串w ab 推导树为 由于A的产生式A 右部能 且Follow A First bAS b 从而引起回溯 例3文法G S SaS b输入串w baa 推导树为 由于文法含有左递归而引起回溯 5 5确定的自顶向下分析方法 确定的自顶向下分析方法有 递归子程序法 recursive descentparser 预测分析法 predictiveparser 两种方法都要求文法是LL 1 文法 5 5 1递归子程序法 实现思想 对文法中的每个非终结符编写一个递归过程 识别由该非终结符推出的串 当非终结符有多条产生式时 按当前输入符属于哪条产生式的SELECT集可唯一确定选择哪个产生式进行匹配 当识别到终结符时 与当前输入符号匹配 并读取下一输入符 当识别到非终结符时 则调用该非终结符相应的过程 例算术表达式文法GE E T TT T F FF E i 1 消除左递归得G E TE E TE T FT T FT F E i 2 求出G 的选择集合SELECT E TE i SELECT E TE SELECT E SELECT T FT i SELECT T FT SELECT T SELECT F E SELECT F i i G 是LL 1 文法 1判断是否可以应用递归子程序法 表达式的正规式E T T 转换成正则文法E TB B T 即B T B T B B 即B T B 与E E T T消除左递归所得E TE E TE 一致 2构造文法G 的递归下降分析器定义 当一个文法满足LL 1 条件时 就为它构造一个不带回溯的自顶向下的分析程序 这个分析程序由一组递归过程组成 每个过程对应文法的一个非终结符 这样的一个分析程序称为递归下降分析器 组成 递归下降分析器由一个主程序MAIN和每个非终结符对应的一个递归过程组成 用到的一些子过程 过程GETNEXT负责读入下一个TOKEN字过程ERROR负责报告语法错误约定 变量TOKEN存放已读入的TOKEN字过程进入时变量TOKEN存放了一个待匹配的TOKEN字退出过程时 变量TOKEN中仍存放着一个待匹配的TOKEN字 非终结符相应的分析子程序的构造方法对于每个非终结符U 编写一个相应的子程序P U 对于产生式U x1 x2 xn x1 xn都 关于U的子程序P U 按如下方法构造 ifTOKENinfirst x1 thenp x1 elseifTOKENinfirst x2 thenp x2 else ifTOKENinfirst xn thenp xn elseERROR 如果U还有空产生式U 则算法中的语句 ifTOKENinfirst xn thenp xn elseERROR改写为ifTOKENinfirst xn thenp xn elseifTOKENnotinfollow U thenERROR对于符号串x y1y2 yn p x 的含义为 beginp y1 p y2 p yn end如果yi VN 则P yi 就代表调用yi的子程序 yi VT 则P yi 为形如下述语句的一段程序ifTOKEN yithenGETNEXT TOKEN elseERROR 1 programMAIN 主程序 匹配E E beginGETNEXT TOKEN E TOKEN 转匹配E TE ifTOKEN thenERRORend 构造文法G E TE E TE T FT T FT F E i的递归下降分析器 2 procedureE TOKEN 匹配E TE beginT TOKEN 转匹配T FT E TOKEN 转匹配E TE end 3 procedureE TOKEN 匹配E TE beginifTOKEN then 选择产生式E TE beginGETNEXT TOKEN 匹配 读下一个TOKEN字 T TOKEN 转匹配T FT E TOKEN 转匹配E TE endelse E 对应的语句 ifTOKEN andTOKEN thenERROR 构造方法3 求follow E follow E end 5 procedureT TOKEN 匹配T FT beginifTOKEN then 选择产生式T FT beginGETNEXT TOKEN 匹配 读下一TOKEN字 F TOKEN 转匹配F E i T TOKEN 转匹配T FT endelse T 对应的语句 ifTOKEN andTOKEN andTOKEN thenERRORend follow T follow T first E follow E 4 procedureT TOKEN 匹配T FT beginF TOKEN 转匹配F E i T TOKEN 转匹配T FT end 6 procedureF TOKEN 匹配F E i beginifTOKEN then 选择产生式F E beginGETNEXT TOKEN 匹配 读下一TOKEN字 E TOKEN 转匹配E TE ifTOKEN thenGETNEXT TOKEN 匹配 读下一TOKEN字 elseER