编译原理-西安交通大学(冯博琴)4_自上而下语法分析__3.0ppt课件

第四章语法分析 自上而下分析 本章内容语法分析的任务与分类自上而下分析面临的问题递归下降分析程序构造预测分析程序LL 1 文法 1 一 语法分析的任务与分类语法分析的任务 对任一给定w VT 判断w L G 语法分析器 是一个程序 它按照P 做识别w的工作 词法分析器 语法分析器 编译程序后续部分 符号表 图4 1语法分析器在编译程序中的地位 2 二 自上而下分析面临的问题 1 主旨 从文法开始符号出发 自上而下的为输入串建立一棵语法树 3 S c A d a b a S cAd A ab A a 输入串w 文法G IP 分析过程 1 w 输入串 IP c S 扩充 cad 2 cAd 与IP c 匹配 3 IP a A扩展 第一式ab IP a 与ab匹配 IP d 但d与b不匹配 4 报告失败 撤销A的子树 回到A 指针回退到IP a A还有替换式未试过 而又可能匹配 语法树的形成 4 上述分析方法的实现 每一非终结符对应一个递归子程序 在只生成两个串的文法 过程无须递归 而对生成无数个串的文法 递归是不可避免的 递归子程序 是一个布尔过程 一旦发现它的某个候选式与输入串匹配 它就按此式扩充语法树 并返回true 指针移过已匹配子串 否则 返回false 保持原来的语法树和指针不变 5 程序实现 使用记号 input symbol 当前符号内容input pointer 输入字符指针使用过程 ADVANCE 把input pointer移到下一输入符号位置 置input symbol是当前符号内容 使用两个过程 S 和A 它们送回trueorfalse 决定于它们是否在输入串中找到相应的非终结符所构成的串 6 procedureS beginifinput symbol c thenbeginADVANCE ifA thenifinputSymbol d thenbeginADVANCE returntrueendend returnfalse end procedureA beginisave input pointer ifinput symbol a thenbeginADVANCE ifinputSymbol b thenbeginADVANCE returntrue endend failuretofindab input pointer isave ifinputSymbol a thenbeginADVANCE returntrue endelsereturnfalse end 7 2 困难和问题 文法的左递归回溯用替换符的顺序会影响所接受的语言如 A ab a改为A a ab难以报告出错的确切位置穷举试探法 低效的分析方法 8 三 自上而下分析的问题解决 消除文法的左递归克服回溯问题 9 1 区分三种类型的左递归 直接左递归即形如 N N 间接左递归即形如 N A A B B N 潜在左递归即形如 N N而 10 2 直接左递归的消除 候选式 A A A A A A 消除方法 若 A A 其中 不以A开头则修改规则为 A A A A 11 消去直接左递归后 E TE E TE T FT T FT F E i 例4 2文法 E E T TT T F FF E i 消除方法 若 A A 不以P开头 则修改规则为 A A A A 12 3 间接和潜在左递归的消除 代入法将一个产生式规则右部的 中的非终结符N替换为N的候选式 如果N有n个候选式 右边的 重复n次 而且每一次重复都有N的不同候选式来代替N 例4 3N a Bc 在S pNq中的代入结果为S paq pBcq pq 间接和潜在左递归通常通过代入能转换为直接左递归 13 4 消除一个文法的一切左递归算法 对文法G的所有非终结符进行排序按上述顺序对每一个非终结符Pi依次执行 for j 1 j i 1 j 将Pj代入Pi的产生式 若可代入的话 消除关于Pi的直接左递归 化简上述所得文法 14 5 消除回溯 提左因子 回溯原因 若当前符号 a 对A展开 而A 1 2 m 那么 要知道哪一个 i是获得以a开头的串的唯一替换式 即 选择哪一个 i 亦即通过查看第一个 当前 符号来发现合适的替换式 i 怎样选择 i 以a为头的 i 如有多个 i以a为头的 这是文法的问题 15 例如 有产生式 语句 if条件then语句else语句 while条件do语句 begin语句表end 若要寻找一个语句 那么关键字if while begin就提示我们哪一个替换式是仅有可能成功的替换式 抽象地看问题 若要求不得回溯 文法G 当然G不含左递归 的必要条件是什么 也即对文法有什么要求 16 若由 ia 选该 必中 但若 ja 就会导致无法百发百中 解决办法是对文法本身提出要求 不会出现以上情况 把这些阐明清楚是用一个FIRST 定义FIRST FIRST a a a VT 若 规定 FIRST 17 定理 若一个A VN 就有许多FIRST i 如果A的任何两个候选式 i和 j 均有FIRST i FIRST j 意味着 A的每一候选式 推导后所得的字符串第一个VT均不同 于是 对输入符号a 如果a FIRST i 则anot FIRST j j i 因此 对A的展开无疑应选候选式 i 才有可能命中 18 消除回溯目的 非终结符A的所有侯选式的首符集两两不相交方法 提取公共左因子 若 A 1 2 n 1 2 m 其中 每个 不以 开头 那么 可以把这些规则改写成A A 1 2 mA 1 2 n 19 四 递归下降分析程序构造 在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件下 构造一个不带回溯的自上而下分析程序 该分析程序由一组递归过程组成 每个过程对应文法的一个非终结符 这样的一个分析程序称为递归下降分析器 20 1例4 4文法G 21 PROCEDUREE BEGINT E END PROCEDURET BEGINF T END PROCEDUREE IFSYM THENBEGINADVANCE T E END E TE E TE T FT 22 PROCEDURET IFSYM THENBEGINADVANCE F T END PROCEDUREF IFSYM i THENADVANCEELSEIFSYM THENBEGINADVANCE E IFSYM THENADVANCEELSEERRORENDELSEERROR 面临输入 i1 i2 i3时的分析步骤如下 T FT F E i 23 i1 i2 i3分析过程 E T E F T i1 PROCEDUREE BEGINT E END PROCEDURET BEGINF T END PROCEDUREF IFSYM i THENADVANCEELSEIFSYM THENBEGINADVANCE E IFSYM THENADVANCEELSEERRORENDELSEERROR PROCEDURET IFSYM THENBEGINADVANCE F T END 24 i1 i2 i3分析过程 E T E F T E T F T F T i1 i2 i3 PROCEDUREE IFSYM THENBEGINADVANCE T E END PROCEDURET IFSYM THENBEGINADVANCE F T END 25 2 注意 有 自动匹配 不会失败无成功 失败消息返回出错位置不确切 26 五 预测分析程序 问题 用递归子程序描写递归下降分析器 要求实现该编译系统的语言允许递归 改进 使用一张分析表和一个栈同样可实现递归下降分析 用这种方法实现的语法分析程序叫预测分析程序 27 1 预测分析程序的工作过程 28 预测分析程序有四部分 29 分析程序的动作 程序测定栈顶有X和当前输入符a 由 X a 决定程序动作 三种可能 1 若X a 分析停止 宣告成功地完成分析 2 若X a 则X弹出栈 下移输入指针 3 若X VN 则去查分析表M的元素M X a 该元素或为X的产生式 或为一个出错元素 30 如 M X a X UVW 就用WVU U在顶 替换栈顶的X作为输出 如 M X a error 则调用error程序 对第3 条 X VN 查分析表M的元素M X a 31 分析表格式 E TE E TE T FT T FT F E i 32 例4 5按预测分析程序 对于输入id id id所作动作如下所示 1 Eid id id 2 E Tid id id E TE 3 E T Fid id id T FT 4 E T idid id id F id5 E T id id 6 E id id T 7 E T id id E TE E Tid id E T Fid id T FT M E id E TE M T id T FT M F id F id 匹配 id出栈输入串指针后移 E id T id F id id id 33 10 E T idid id F id11 E T id 12 E T F id T FT 13 E T Fid 14 E T idid F id15 E T 16 E T E 有 X a 分析成功 id id T id F id id id T E 34 结论 输出的产生式就是最左推导的产生式 栈中放右部 等待与 匹配 表指出 栈顶 a 时 如何扩充树 出错马上发现 实质 栈 残缺规范句型表 指出VN按哪一条扩充 依赖于VT 上述分析过程生成的语法树 35 F E F id F T T T FT T T T FT T FT T E E E TE E E TE E TE E id id id id E T F T F T id id E T E F T id 36 2 分析表的构造 分析表格式 思路 1 把产生式填到何处 2 按 将产生式分为两种 一种是 a 另种是 37 先要构造两个与G有关的集合 FIRST 和FOLLOW A 1 定义 若G V S A VN 38 2 构造FIRST 先构造FIRST X X V 连续使用以下规则 直至再无终结符 或 加入任一FIRST集为止 39 若X VT 则FIRST X 是 X 若X VN 且X a 则 a FIRST X X 则 FIRST X 若X VN X Y Y VN 则FIRST Y FIRST X 进而 X Y1Y2 Yi 1Yi Yk Yj VN 1 j i 1 FIRST Yj 即Y1Y2 Yi 1 则当 则 FIRST X 40 再进而构造FIRST X1X2 Xn FIRST X1 的非 终结符加入FIRST 若 FIRST X1 则FIRST X2 的所有非 终结符加入FIRST 若 FIRST X1 FIRST X2 则FIRST X3 的所有非 终结符加入FIRST 最后 若 FIRST Xi i 1 n 则 加入FIRST 41 3 构造FOLLOW A 应用下列规则 直到再没有什么加进任一FOLLOW为止 属于FOLLOW S 若存在A B 则FIRST FOLLOW B 除 外 若有A B 或A B 且 FIRST 则FOLLOW B FOLLOW A 42 4 例4 6已知文法G E TE T FT E TE F E iT FT 求它的FIRST FOLLOW A FIRST集的构造 FIRST E FIRST T FIRST F i FIRST E FIRST T 43 属于FOLLOW S 若存在A B 则FIRST FOLLOW B 除 外 由 得 FOLLOW E 由 得 E TE 则FIRST E FOLLOW T 即FOLLOW T T FT 则FIRST T FOLLOW F 即FOLLOW F F E 则FIRST FOLLOW E 即FOLLOW E FOLLOW集的构造 FIRST T FIRST E 44 即FOLLOW F 若有A B 或A B 且 FIRST 则FOLLOW B FOLLOW A FOLLOW E FOLLOW T FOLLOW F 由 得 E TE 得FOLLOW E FOLLOW E 即FOLLOW E E TE 且E 得FOLLOW E FOLLOW T 即FOLLOW T T FT 得FOLLOW T FOLLOW T 即FOLLOW T T FT 且T 得FOLLOW T FOLLOW F 45 FIRST E FIRST T FIRST F i FIRST E FIRST T FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F 最终构造结果 注意 FIRST集针对终结符 非终结符 候选式而构造 FOLLOW集只对非终结符构造 46 5 构造分析表算法 输入 G1文法 输出 分析表M 对文法的每一个A 做 和 对于任a FIRST 把A 加进M A a 若 FIRST 则把A 加进M A b b FOLLOW A 若 FIRST FOLLOW A 则把A 加进M A 47 6 例4 7算法应用于文法G E TE 填法 FIRST TE FIRST T id M E E TE M E id E TE E TE 填法 M E E TE 48 E 填法 FOLLOW E M E E M E E 49 六 LL 1 分析法 LL 第一个L表示从左到右扫描输入串 第二个L表示最左推导 1 表示分析时每一步只需向前查看一个符号 50 2 LL 1 文法的条件 1 LL 1 文法一个文法G 若它的分析表M不含多重定义入口 则称它是一个LL 1 文法 1 FIRST FIRST 2 若 则FIRST FOLLOW A 文法G是LL 1 的 则对于G的每一个非终结符A的任何两个不同产生式A 有 51 说明 使用LL 1 文法 一定可以实现不带回溯的自上而下分析 对A 若条件 1 不成立 则FIRST FIRST 假设 FIRST FIRST a 52 那么 当A面临输入符号a 而a同时属于FIRST 和FIRST 则分析无法继续进行下去 因为不能确定用哪一个候选式可以保证一定能够得到匹配而不进行回溯 实质就是分析表的M A a 中包含两条候选式A A 反之 分析表的M A a 中只包含一条候选式则意味着可以进行确定性的无回溯的分析 53 对A 若 且条件 2 不成立 则FIRST FOLLOW A 假设 FIRST FOLLOW A a 那么 当A面临输入符号a时 若选候选式A 则由于a FIRST 可以使a一定得到匹配 同时 若选候选式A 也可以满足要求 这是由 而a FOLLOW A 54 实质同样是