new第四章 语法分析1(最后版本).ppt

编译原理CompilerPrinciples 蒋凌云jianglingyun 南京邮电大学 计算机学院 第四章语法分析 教材 编译技术原理及其实现方法 王汝传编著 第四章语法分析 4 1引言一 语法分析任务二 语法分析方法 4 2自顶向下语法分析一 自顶向下分析方法的问题及其解决办法二 递归子程序分析法 递归下降分析法 三 LL 1 分析法 4 3自底向上语法分析一 简单优先文法分析法二 算符优先分析法三 优先函数及其构造四 LR分析法五 二义性文法的应用 4 4语法分析程序的自动生成一 分析器的生成器YACC二 用YACC处理二义性文法 2 本章内容 第四章语法分析 4 1引言一 语法分析任务二 语法分析方法 4 2自顶向下语法分析一 自顶向下分析方法的问题及其解决办法二 递归子程序分析法 递归下降分析法 三 LL 1 分析法 4 3自底向上语法分析一 简单优先文法分析法二 算符优先分析法三 优先函数及其构造四 LR分析法五 二义性文法的应用 4 4语法分析程序的自动生成一 分析器的生成器YACC二 用YACC处理二义性文法 3 本章内容 4 1引言 本节内容 一 语法分析任务1 语法检查2 根据语法符号进行一定处理加工二 语法分析方法1 自顶向下语法分析方法2 自底向上语法分析方法 词法分析阶段 主要介绍了单词符号的结构 识别 用状态转换图 描述 通过正规式 以及有限自动机DFA和NFA 在一个编译程序对某个源程序完成了词法工作以后 就进入了语法分析阶段 由词法分析程序所产生的单词符号流 作为语法分析程序的输入串 按文法规则分析检查是否构成了合法的句子 首先来了解一下语法分析的任务 5 4 1引言 一 语法分析任务 一 语法分析任务1 语法检查2 根据语法符号进行一定处理加工二 语法分析方法1 自顶向下语法分析方法2 自底向上语法分析方法 6 4 1引言 一 语法分析任务 7 1 语法检查根据语法规则对各种语法成分进行分析 确定它们的语法关系以检查语法上的正确和错误 并指出错误的性质和出错位置 如 ifBthenS1elseS2若写成ifBthenelseS2就错了 then后少一个S1 4 1引言 一 语法分析任务 一 语法分析任务1 语法检查2 根据语法符号进行一定处理加工二 语法分析方法1 自顶向下语法分析方法2 自底向上语法分析方法 8 4 1引言 一 语法分析任务 9 2 根据语法符号进行一定语义处理加工如语法分析过程得到一个合法的句子时 往往同时进行必要的语义分析等如 当遇到处理表达式a b c时 若该表达式语法关系正确 就可以进行语义处理加工 可将该表达式变成中间语言 以便以后生成目标程序 4 1引言 一 语法分析任务 一 语法分析任务1 语法检查2 根据语法符号进行一定处理加工二 语法分析方法1 自顶向下语法分析方法2 自底向上语法分析方法 10 4 1引言 二 语法分析方法 语法分析方法很多 但能够产生计算机程序并能得到广泛应用的主要有两大类 按照生成语法树的顺序 分别称为自顶向下和自底向上分析方法 11 4 1引言 二 语法分析方法 一 语法分析任务1 语法检查2 根据语法符号进行一定处理加工二 语法分析方法1 自顶向下语法分析方法2 自底向上语法分析方法 12 4 1引言 二 语法分析方法 13 1 自顶向下语法分析方法 1 带回溯分析方法 2 不带回溯分析方法 3 递归子程序法 4 LL 1 分析法 4 1引言 二 语法分析方法 一 语法分析任务1 语法检查2 根据语法符号进行一定处理加工二 语法分析方法1 自顶向下语法分析方法2 自底向上语法分析方法 14 4 1引言 二 语法分析方法 15 2 自底向上语法分析方法 1 简单优先分析法 2 算符优先分析法 3 LR分析法 4 SLR分析法 5 LALR分析法 4 1引言 二 语法分析方法 第四章语法分析 4 1引言一 语法分析任务二 语法分析方法 4 2自顶向下语法分析一 自顶向下分析方法的问题及其解决办法二 递归子程序分析法 递归下降分析法 三 LL 1 分析法 4 3自底向上语法分析一 简单优先文法分析法二 算符优先分析法三 优先函数及其构造四 LR分析法五 二义性文法的应用 4 4语法分析程序的自动生成一 分析器的生成器YACC二 用YACC处理二义性文法 16 本章内容 第四章语法分析 4 1引言一 语法分析任务二 语法分析方法 4 2自顶向下语法分析一 自顶向下分析方法的问题及其解决办法二 递归子程序分析法 递归下降分析法 三 LL 1 分析法 4 3自底向上语法分析一 简单优先文法分析法二 算符优先分析法三 优先函数及其构造四 LR分析法五 二义性文法的应用 4 4语法分析程序的自动生成一 分析器的生成器YACC二 用YACC处理二义性文法 17 本章内容 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 18 4 2自顶向下语法分析 本节内容 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 19 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 20 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 1 消除回溯对于自顶向下语法分析来说 对于某些文法 可能会遇到 回溯 和 左递归 的问题 为了能有效地运用这种语法分析方法 应使文法不含左递归及避免回溯 1 回溯分析方法定义在进行自顶向下语法分析时 对于文法规则中具有同一左部而右部有不同规则时 在分析时按顺序一个个试探 若能分析下去则成 否则再退回到出错点换另一规则重新试探 这种方法称回溯分析方法 其实质就是使用不同规则反复试探 如 S cAdA ab a要判断 cad 是否为该文法的句子 可以分别用A ab和A a代入第一个产生式中试探 21 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 2 回溯问题的解决1 路标法定义 设有规则U a1V1 a2V2 anVn若ai为互不相同的终结符时 将ai作为路标 当被分析符号串为ai时 便可按规则U aiVi往下分析 这样可以消除回溯 如 ifthen当分析语句 ifA BthenA B时 我们可以根据第二个产生式以if开始直接选用它作判断 if在这里就是路标 22 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 因此 我们在设计程序设计语言时 要考虑语法规则各选择项开始符号互不相同 为了避免回溯 我们对文法要求是 FIRST i FIRST j i j 即对文法中的任意一个非终结符号 其规则右部有多个选择时 若由各个选择所推出的终结符号串首符号集合要两两不相交 这样 就可能根据当时读进的符号是属于哪个选择的FIRST i 来唯一地确定该选用哪个选择来匹配输入串 如 当前输入符号为b b 如果b FIRST i 则可以选择第i个产生式去匹配输入串 23 一般地 设U为文法 的任意非终结符号 若U有如下规则 U n i 若定义任一个选择 i的所有可能推出终结符号串的首符号集FIRST i 为 FIRST i a i a a 显然FIRST i 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 一般地说 如果有规则 U a a a n 则可以将这些规则写成 U aU U n 其中a称为左公因子 经过反复提取公因子即可将每个非终结符的所有选择首符号集变成两两不相交 24 2 提取左因子法当文法不满足上述路标法条件 即右部各规则首符号相同时 我们可以采用提取左因子法对文法进行改写 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 S xAy A 进一步改写成S xAy A A1 A1 为分析符号串x y 可以从开始符号出S xAy 下一待匹配符号为 所以用A A1 得S xAy x A1y 下一个待匹配的符号为y 所以用A1 若用A1 则意味着下一个为 不能匹配 得S xAy x A1y x y 即x y 匹配成功 可见没出现回溯现象 25 S x y A A1 如 有文法S xAy A 要分析x y 显然存在回溯 为避免分析时回溯 可以将文法改写成 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 26 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 2 消除左递归 27 1 问题的提出在自顶向下分析过程中 假定现在轮到要用非终结符U去匹配输入串 而在文法中第一条规则是 U U 它是一条直接左递归规则 这种左递归文法将使上述自顶向下的分析过程陷入无限循环 即 当试图用U去匹配输入串时会发现 在没有吃进任何输入符号的情况下 又得重新要求U去匹配 如此循环下去而无终止 若文法具有间接左递归 即有 U U 那么 也会发生上述问题 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 28 如 已知文法G S S ABA bB Aa 存在直接左递归 B Sb a现分析符号串baabaab是否是文法G的句子 其分析过程如下 S AB bBB bSbB bABbB bbBBbB 得第二个字符与输入串不匹配 S AB bBB bSbB bABbB bAaBbB 只能用A Aa推导 又遇A 出现了死循环 由于文法规则中有左递归A Aa 所以无法分析下去 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 29 2 消除左递归方法1 用重复表示法 扩充的 表示法 改写语法规则假定一个文法中有关于非终结符的规则为 其中 非空 不以 开头 则等价地改写为 例如 下述直接左递归规则 可改写为 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 30 E E T E T E T T 等价 E T T T T T T T T 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 31 同样 规则 等价于 可改写为 这样 改写后的文法消除了直接左递归 可以证明 改写前后的文法是等价的 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 32 2 消除直接左递归还可用另一种方法来改写形如文法规则 的直接左递归 对 引入一个新的非终结符 将 等价写成 由于 不以 开头 不以 开头 因此改写后两条规则不是直接左递归 同样可以证明这种形式和原来形式是等价的 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 33 A A A A 等价 A A A A A 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 就一般而言 关于 的规则具有下面形式 n n 这时可改写成如下形式 A n n 由消除直接左递归方法 得 n n 34 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 35 例如 A Ac Aad bd e等价于A A c ad bd e 所以可以改写成 A bd e A 即A bdA eA A c ad A 即A cA adA 例如 有文法 T i 用上述方法可改写成 i 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 上述两种方法可消除任意直接左递归 但不能消除两步或多步推导形成的左递归 例如 有文法 c c b b a a 该文法无直接左递归 但有间接左递归 例如有 c bc abc 即 abc 36 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 3 消除间接左递归对于间接左递归先将间接左递归变成直接左递归 然后消除直接左递归例如 A aB Bb 1 B Ac d 2 先将 1 代入 2 中 得B Bbc aBc d 3 由此将 3 改写为 B aBc d B B bcB 加入文法开始符号的产生式得消除左递归后的等价文法为 A aB BbB aBc d B B bcB 37 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 4 消除文法递归的一般算法要求 文法不含形如 的推导 也不存在 这样规则算法思想如下 将文法 的所有非终结符整理成某种顺序 n 从U1开始消除U1规则的直接左递归 用左部为U1的所有规则右部替换左部为U2 右部以U1开始的规则中的U1 并消除U2规则的直接左递归 用类似的方法把U1 U2的右部替换左部为U3 右部以U1 U2开始的规则中 消除U3规则中的直接左递归 重复上一步 直到最后把左部为U1 U2 Un 1的右部带入Un规则中 并消除Un中的直接左递归 消除多余规则 38 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 将文法 的所有非终结符整理成某种顺序 n 然后按此顺序执行下一步 执行循环语句 i n j i 1 把形如 i jy的规则改写成 Ui x y x y xky 其中Uj x x xk是Uj的所有规则 消除关于Ui规则中直接左递归 去掉多余规则 如果有的话 39 消除左递归算法 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 例4 2设有文法 a b c d e 应用上述算法 将非终结符排列 然后执行循环语句 i 2 j i 消除Ui规则中直接左递归 40 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 当i 时 上述语句对文法 不产生影响 当i 时 应改写规则 d 因为 a b 所以 ad bd 此时文法 变换成为 a b c ad bd e 消除关于 的直接左递归即可 该文法没有多余的规则 41 4 2自顶向下语法分析 一 自顶向下分析方法的问题及其解决办法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 42 4 2自顶向下语法分析 二 递归子程序分析法 1 递归子程序定义一个子程序以直接或间接方式调用本身 称为递归子程序 43 4 2自顶向下语法分析 二 递归子程序分析法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 44 4 2自顶向下语法分析 二 递归子程序分析法 2 递归调用子程序的处理 1 处理基本思想对于递归子程序调用 用栈存放返回地址 当调用该子程序时 由递归入口子程序将返回地址压入栈中 当返回时 用递归出口子程序从栈中取出返回地址 2 构造递归子程序的方法程序语言的许多语法成分是递归定义的 在对程序语言进行不带回溯自顶向下语法分析时 就可以采用递归子程序法 其方法步骤如下 45 4 2自顶向下语法分析 二 递归子程序分析法 1 对文法中每个非终结符号U 它们都分别代表一种语法成分 都编出一个子程序P U 2 对于递归出现的非终结符 其相应的子程序中应有递归入口部分 递归入口子程序 取名S 以便将返回地址压入栈中 此外 还应有递归出口部分 设此子程序取名S 以便从地址压入栈中取返回地址3 对于符号串x y y ym 如果yi 则 yi 为 ch yi ch 这就是说 如果当前文法中的符号与输入符号匹配 则继续读入下一个字符至ch中 否则表明源程序有错 如果yi 则 yi 就代表调用与yi相应的子程序 46 4 2自顶向下语法分析 二 递归子程序分析法 4 对于规则U x x xn 可用下列方法构造 U ch R ch E ch n n 其中全程变量ch中存放了当前输入字符 为出错信息 表示源程序中语法有错 当输入符号遇选择项为 时 就自动认为获得了匹配 47 4 2自顶向下语法分析 二 递归子程序分析法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 48 4 2自顶向下语法分析 二 递归子程序分析法 49 3 分析实例 设有文法 eBaA a bAcB dEd aC e dC 此文法共有四个非终结符 并且在规则中都是递归出现 故应该编写四个相应的递归子程序 E 在第一次执行前 ch中已存有输入串中首字符 4 2自顶向下语法分析 二 递归子程序分析法 1 构造递归子程序 E 50 SCIN ch e 1 2 READ P B ch a ERROR READ P A ERROR SCOUT eBaA 用方法3 3 4 5 6 7 8 1 构造递归子程序 A 51 a bAcB 用方法3 和4 1 构造递归子程序 B 52 SCIN ch d 1 2 READ P E ch d READ P C ERROR dEd aC 用方法3 和4 3 4 5 6 7 9 ERROR READ 8 ch a SCOUT 10 1 构造递归子程序 C 53 e dC 用方法3 和4 54 2 分析实例判别字符串eadeaa是否是文法 的句子 eadeaa 分析步骤从识别符号E开始 扫视字符串eadeaa 设一个全程变量ch用于存放输入串中的字符 并设一个返回地址栈用于存放返回地址 栈底 TOP 55 eadeaa 1 开始时 在全程变量ch中存放了输入串中的首字符e 故分析与识别从符号 e 开始 此时主程序调用子程序P E 子程序P E 栈底 TOP 56 eadeaa 2 进入P E 后 执行P E 子程序 首先通过递归入口子程序SCIN 将P E 在主程序中的返回地址送入返回栈中 子程序P E 主返 TOP 57 eadeaa 3 执行P E 子程序 首先判断ch e 现在ch e 接着读入下一个字符 子程序P E 主返 TOP 58 eadeaa 4 读入下一个字符a 即ch a 子程序P E 主返 TOP 59 eadeaa 5 P E 子程序调用子程序P B P B 调用递归入口子程序SCIN 将P B 在P E 中的返回地址P E 5送入返回栈中 子程序P E 主返P E 5 TOP 60 eadeaa 6 然后执行子程序P B 分析ch d 现在不是d 再判定ch a 现在ch a 接着读入下一个字符 子程序P B 主返P E 5 TOP 61 eadeaa 7 读入下一个字符d 即ch d 子程序P B 主返P E 5 TOP 62 eadeaa 8 P B 子程序调用子程序P C P C 调用递归入口子程序SCIN 将P C 在P B 中的返回地址P B 10送入返回栈中 子程序P B 主返P E 5P B 10 TOP 63 eadeaa 9 接着执行P C 分析ch e 现在不是字符e 再接着判定ch d 现在ch d 接着读入下一个字符 子程序P C 主返P E 5P B 10 TOP 64 eadeaa 10 读入下一个字符e 即ch e 子程序P C 主返P E 5P B 10 TOP 65 eadeaa 11 P C 子程序再调用子程序P C P C 调用递归入口子程序SCIN 将P C 在P C 中的返回P C 7地址送入返回栈中 子程序P C 主返P E 5P B 10P C 7 TOP 66 eadeaa 12 然后执行子程序P C 这时要判定ch e 现在ch e 接着读入下一个字符 子程序P C 主返P E 5P B 10P C 7 TOP 67 eadeaa 13 读入下一个字符a 即ch a 子程序P C 主返P E 5P B 10P C 7 TOP 68 eadeaa 14 P C 调用递归出口子程序SCOUT 将返回栈中返回地址P C 7取出 子程序P C 主返P E 5P B 10P C 7 TOP 69 eadeaa 15 P C 调用递归出口子程序SCOUT 将返回栈中返回地址P C 7取出 子程序P C 主返P E 5P B 10 TOP 70 eadeaa 16 P C 执行P C 7 即P C 调用递归出口子程序SCOUT 将返回栈中返回地址P B 10取出 子程序P C 主返P E 5P B 10 TOP 71 eadeaa 17 P C 执行P C 7 即P C 调用递归出口子程序SCOUT 将返回栈中返回地址P B 10取出 子程序P C 主返P E 5 TOP 72 eadeaa 18 P B 执行P B 10 即P B 调用递归出口子程序SCOUT 将返回栈返回地址P E 5取出 子程序P B 主返P E 5 TOP 73 eadeaa 19 P B 调用递归出口子程序SCOUT 将返回栈中P B 在P E 中的返回地址P E 5取出 子程序P B 主返 TOP 74 eadeaa 20 P E 执行P E 5 即P E 子程序判别ch a 现在是a 接着读入下一个字符 主返 TOP 子程序P E 75 eadeaa 21 读入下一个字符a 即ch a 主返 TOP 子程序P E 76 eadeaa 22 P E 子程序调用子程序P A P A 调用递归入口子程序SCIN 将P A 在P E 中的返回地址P E 8送入返回栈中 主返P E 8 TOP 子程序P E 77 eadeaa 23 现在执行子程序P A 判断ch a 现在ch a 接着读入下一个字符 主返P E 8 TOP 子程序P A 78 eadeaa 24 由于输入串eadeaa后面再也没有其他字符了 故读入的是句子的终结符 主返P E 8 TOP 子程序P A 79 eadeaa 25 P A 调用递归出口子程序SCOUT 将返回栈中中返回地址P E 8取出 主返P E 8 TOP 子程序P A 80 eadeaa 26 P A 调用递归出口子程序SCOUT 将返回栈中中返回地址P E 8取出 主返 TOP 子程序P A 81 eadeaa 27 P E 执行P E 8 即P A 调用递归出口子程序SCOUT 将返回栈中返回地址主返取出 主返 TOP 子程序P E 82 eadeaa 28 P E 执行P E 8 即P A 调用递归出口子程序SCOUT 将返回栈中返回地址主返取出 栈底 TOP 子程序P E 83 eadeaa 29 返回主程序 结束 栈底 TOP 子程序P E 84 也就是说 字符串eadeaa被语法分析程序所接受 这表明字符串 eadeaa 是文法 的句子 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 85 4 2自顶向下语法分析 二 递归子程序分析法 4 递归子程序法特点 1 优点1 程序结构和层次清晰 易于手工实现 2 子程序与文法规则一一对应 但要求对文法规则消除左递归和回溯 3 可以加入语义加工子程序 2 缺点1 编写程序和调试工作量大2 对上下文无关文法需要改写 86 4 2自顶向下语法分析 二 递归子程序分析法 要求 不含有左递归 并且每个非终结符的各个选择所推出的终结符号串首符号集合两两不相交 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 87 4 2自顶向下语法分析 三 LL 1 分析法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 88 4 2自顶向下语法分析 三 LL 1 分析法 1 定义LL 1 分析方法也是一种自顶向下不带回溯的分析方法 LL的意思是 从左 Left 到右扫描输入符号串并建立它的最左推导 Leftmostderivations 数字 是指向前看一个符号来决定选择同一个非终结符不同规则 如果向前查看K个符号 K 1 才能确定应选规则时 这种语法分析方法就称LL K 分析法 89 4 2自顶向下语法分析 三 LL 1 分析法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 90 4 2自顶向下语法分析 三 LL 1 分析法 91 2 LL 1 分析方法 1 基本思想借助于一张分析表及一个语法分析栈 在一个总控程序控制下实现 我们通常把按LL 1 方法执行语法分析任务的程序称为LL 1 分析程序或LL 1 分析器 它由一个总控程序 一张分析表和一个分析栈组成 如下图所示 a1a2 ai an 输入串 总控程序 分析表m X 分析栈 4 2自顶向下语法分析 三 LL 1 分析法 2 LL 1 方法分析过程考虑文法 FT i 1 建立文法LL 1 的分析表相应的分析表如下表所示 其构造方法 在后面叙述 92 4 2自顶向下语法分析 三 LL 1 分析法 93 4 2自顶向下语法分析 三 LL 1 分析法 94 由上述分析过程可以看出 在分析的每一时刻 当前已读过的符号与栈中的符号一起总是构成了当前的左句型 分析器确实构造了输入串的一个最左推导 2 分析过程现在以输入符号串i i i为例 列出利用上述算法对此符号串的分析过程如下 步骤分析栈余留输入串所用产生式 Ei i i E TE E Ti i i T FT E T Fi i i F i E T ii i i E T i i T E i i E TE E T i i E Ti i T FT E T Fi i F i E T ii i E T i T FT E T F i E T Fi F i E T ii E T T E E 成功 3 一般分析步骤其中 输入 就是待分析的符号串 它以右界符 作为结尾 分析表 可用一个矩阵 或二维数组 来表示 它概括了相应文法的全部信息 分析表的每一行与文法的一个非终结符 相关联 而每一列则与文法的一个终结符号或 相关联 分析表元素 a a U 或者指示了当前推导所应使用的产生式 或者指出了输入串中含有语法错误 分析器对每个输入串的分析在总控程序控制下进行 95 4 2自顶向下语法分析 三 LL 1 分析法 其步骤如下 1 分析开始时 首先将符号 及文法的开始符号 依次置于分析栈的底部 并把各指示器调整至起始位置 即分别指向分析栈的栈顶元素和输入串的首字符 然后反复执行第 2 步2 设在分析的某一步 分析栈及余留的输入符号串处于如下格局 X1X2 Xm 1Xmaiai 1 其中 m为分析过程中所得的文法符号 此时 可视栈顶符号 m的不同情况 分别做如下的动作 96 4 2自顶向下语法分析 三 LL 1 分析法 若 m 则以 m及ai组成符号对 m ai 查分析表 设 m ai 为一产生式 譬如说Xm 此时将 m从分析栈中退出 并将 按反序推入栈中 即用该产生式推导一步 从而得到新的格局 X1X2 Xm 1WVUaiai 1 但若 m ai 则调用出错处理程序进行处理 若 m ai 则表明栈顶符号已与当前正扫视的输入符号得到匹配 此时应将 m 即ai 从栈中退出 并将输入符号指示器向前推进一个位置 若 m ai 则表明输入串已完全得到匹配 此时即可宣告分析成功而结束分析工作 97 4 2自顶向下语法分析 三 LL 1 分析法 4 几点说明1 分析表M根据具体文法构造 文法不同M就不同2 LL 1 分析法的总控程序对于不同文法总是一样的 3 分析表M A a 或指出应选规则或指出错误 空白时 4 LL 1 语法分析程序的机器模型是一个下推自动机 98 构造一个LL 1 分析器问题 主要归结为构造LL 1 分析表的问题 4 2自顶向下语法分析 三 LL 1 分析法 一 自顶向下分析方法的问题及其解决办法1 消除回溯2 消除左递归二 递归子程序分析法 递归下降分析法 1 递归子程序定义2 递归调用子程序的处理3 分析实例4 递归子程序特点三 LL 1 分析法1 定义2 LL 1 分析方法3 构造分析表4 LL 1 文法 99 4 2自顶向下语法分析 三 LL 1 分析法 100 3 构造分析表 1 头终结符号集合和后继终结符号集合1 头终结符号集合 定义为了构造分析表 我们引进与文法有关的集合FIRST集和FOLLOW集 假定 是文法G的任一符号串 或者说 VT V 我们定义FIRST b b b 特别是 若 则规定 FIRST 即FIRST 是 的所有可能推导的开头终结符或可能的 4 2自顶向下语法分析 三 LL 1 分析法 101 例如 设文法GT ABA PQ BCP pP Q qQ B bB eC cC f求FIRST P FIRST Q FIRST PQ 由定义有PQ pPqQ p PQ Q Q qQ q PQ Q Q 所以FIRST PQ p q 同理FIRST BC b e 对于一个简单的文法我们用手工可以求得其FISRT集 对于复杂的文法我们通常使用下述算法求解 4 2自顶向下语法分析 三 LL 1 分析法 构造头终结符号集合FIRST的算法对于文法中的每一个文法符 构造 时 只要连续使用下列规则 直至每个 集不再扩大为止 a 若X 则 b 若 且有形如 b 规则 b 或 的规则 把b或 和 加入 中 c 设文法 中有形如 Y 的规则 若 则将FIRST 中一切非 符号加进 中 对于一切2 i k 若 则把 2中首符号集 除 外 也加进FIRST 中 如此继续下去 直到 k 1 则把YK中首符号集 除 外 也入FIRST X 中 d 若 每个非终结符号都可能推导出空符号串 即 则把 也加进 中 102 4 2自顶向下语法分析 三 LL 1 分析法 现在 可以对文法G的任何符号串 n 可按如下步骤构造FIRST 首先置FIRST 然后将FIRST X1 中一切非 的符号加进FIRST 若 FIRST 再将FIRST 的一切非 加进FIRST 中 如此等等 最后 若对于 i n i 则再将 加进 中 103 考虑文法 FT i 由算法步骤a 得FIRST FIRST FIRST FIRST FIRST i i 由算法步骤b 得FIRST E FIRST T FIRST F i 4 2自顶向下语法分析 三 LL 1 分析法 104 文法 FT i对于算法步骤c 和d 因为 FT 所以FIRST T FIRST F 又因为F不能推出 所以FIRST T 不能被加入FIRST T 4 2自顶向下语法分析 三 LL 1 分析法 105 利用该算法还能方便地得到如下的符号串头终结符号集 FIRST TE FIRST T FIRST F i FIRST TE FIRST FIRST FT FIRST F i FIRST FT FIRST FIRST E FIRST FIRST 4 2自顶向下语法分析 三 LL 1 分析法 2 后继终结符号集合 定义假定S是文法G的开始符号 对于G的任何非终结符A 我们定义FOLLOW A c S Ac c 特别是 若S A 则规定 FOLLOW A 即 FOLLOW A 是所有句型中出现在紧接A之后的终结符或 106 4 2自顶向下语法分析 三 LL 1 分析法 构造后继符号集合FOLLOW的算法对文法中每个非终结符B 为了构造 B 可反复应用如下规则 直到每个 集不再扩大为止 a 对于文法的开始符号 令 因为S S由定义 FOLLOW S b 若文法中有形如 的规则 且 则将FIRST 中一切非 符号加进 中 c 若文法中有形如 B或 B 的规则 且 则 中全部终结符均属于 其中 可以为 107 4 2自顶向下语法分析 三 LL 1 分析法 108 考虑文法 FT i1 求FOLLOW E 由算法步骤a 得 FOLLOW E E是文法开始符号 由算法步骤b 规则 得 FOLLOW E 所以FOLLOW E 2 求FOLLOW E 由算法步骤c 规则 得 FOLLOW E FOLLOW E 所以FOLLOW E 4 2自顶向下语法分析 三 LL 1 分析法 109 考虑文法 FT i3 求FOLLOW T 1 由算法步骤b 规则 得 FOLLOW T 因为FIRST E 2 由算法步骤c 规则 得 FOLLOW E FOLLOW T 即 FOLLOW T 由规则 得 所以由算法c 规则 得 FOLLOW E FOLLOW T 即 FOLLOW T 所以FOLLOW T 4 2自顶向下语法分析 三 LL 1 分析法 110 考虑文法 FT i4 求FOLLOW T 由算法步骤c 规则 得 FOLLOW T FOLLOW T 即 FOLLOW T 所以FOLLOW T 4 2自顶向下语法分析 三 LL 1 分析法 111 考虑文法 FT i5 求FOLLOW F 1 由算法步骤b 规则 得 FOLLOW F 因为FIRST T 2 由算法步骤c 规则 得 FOLLOW T FOLLOW F 即 FOLLOW F 由规则 得 所以由算法c 规则 得 FOLLOW T FOLLOW F 即 FOLLOW F 所以FOLLOW T 4 2自顶向下语法分析 三 LL 1 分析法 112 2 构造分析表M1 构造分析表M过程 以文法 为例 下面列出文法 符号串头终结符号集合和非终结符后继终结符号集合 文法 FT i 4 2自顶向下语法分析 三 LL 1 分析法 对下述文法 求出符号串头终结符号集合和非终结符后继终结符号集合整理得 文法 FT iFIRST TE i FIRST TE FIRST FT i FIRS