东北大学秦皇岛分校编译原理课件 第五章.ppt

1 第5章自顶向下语法分析 语法分析程序的任务语法分析的方法及自顶向下分析法上下文无关文法与正规式确定的自顶向下分析思想及问题相关集合及计算方法LL 1 分析法LL 1 文法的判定如何计算FOLLOW集合LL 1 分析表M的构造递归子程序法构造给定文法的递归子程序分析法 2 语法分析程序的任务 语法分析程序的任务是将单词符号串分解成各类语法单位 即确定一个程序的结构 语法单位即 短语 句子 子程序 函数 程序等 语法分析是一种在不同层次上的层次结构分析 语法分析与词法分析所基于的理论和方式都是相同的 但语法分析的算法和实现要比词法分析复杂得多 3 语法分析的方法及自顶向下分析法 根据语法分析树的建立方法 可以将语法分析分成自顶向下分析法和自底向上分析法两大类 自顶向下分析法也称面向目标的分析法 自顶向下分析法又可分为确定的自顶向下分析法和不确定的自顶向下分析法 自顶向下分析法中的问题及解决方法 确定的自顶向下分析法的分析思想 4 自上而下分析算法 要点 由根向下构造语法树 构造最左推导 推导出的终结符是否与当前输入符匹配SaaabABaA S ABA aA B b bBaaab S ABS AB aABA aA aaABA aA aaaABA aA aaa BA aaabB b 5 带回溯的自顶向下分析 S ABA aA B b bBaaabb S 1 A S AB 2 aA A aA 3 aaA A aA 4 aaaA A aA 5 aaa B A 6 aaabB b aaabb S 1 A S AB 2 aA A aA 3 aaA A aA 4 aaaA A aA 5 aaa BA 6 aaabBB bB 7 aaabbB b 6 确定的自顶向下分析思想及问题 确定的自顶向下分析方法要求所分析的文法满足一定的条件 关于递归问题 1 规则左 右 递归 1 规则左递归 规则呈U U 形式 2 规则右递归 规则呈U U形式2 文法左 右 递归 1 文法左递归 如果有推导 U U 2 文法右递归 如果有推导 U U 7 LL 1 分析法 LL 1 分析法是一种确定的自顶向下语法分析方法 满足下列条件的文法可以采用LL 1 分析法 经过压缩 无左递归 无回溯LL 1 分析法的基本思想是 从左到右扫描源程序 同时从识别符号开始生成句子的最左推导 并只要向前查看一个输入符号 便能唯一确定当前应当选择的规则 当需要向前查看K个输入符号 才能唯一确定当前应当选择的规则时 称为LL K 分析法 LL 1 分析法分析程序的结构 分析程序由一张分析表M 一个符号栈S和一个总控程序构成 不同的文法有不同的分析表M 但所有LL 1 分析方法的总控程序是相同的 8 FIRST集和FOLLOW集的定义设G VT VN P S 是上下文无关文法FIRST a a a VT V 若 则规定 FRIST FOLLOW A a S A 且a FRIST V V 若S uA 且 则 FOLLOW A LL 1 文法 9 计算FIRST集 1 若X V 则FIRST X X 2 若X VN 且有产生式X a 则把a加入到FIRST X 中 若X 也是一条产生式 则把 也加到FIRST X 中 3 若X Y 是一个产生式且Y VN 则把FIRST Y 中的所有非 元素都加到FIRST X 中 若X Y1Y2 YK是一个产生式 Y1 Y2 Y i 1 都是非终结符 而且 对于任何j 1 j i 1 FIRST Yj 都含有 即Y1 Y i 1 则把FIRST Yj 中的所有非 元素都加到FIRST X 中 特别是 若所有的FIRST Yj j 1 2 K 均含有 则把 加到FRIST X 中 10 如何计算FOLLOW集合 FOLLOW U 是由文法的所有句型U的后继终结符或 组成的 求FOLLOW U 的算法为 1 如果U为文法的识别符号 令 FOLLOW U 2 如有形如A U 的规则 则FIRST 中非 的元素属于FOLLOW U 3 如有形如A U或A U 而FIRST 含有 元素这样的规则 则FOLLOW A 的元素属于FOLLOW U 注 2 3 即为规则A U 中 可为 或有 的情况 利用关系图求FOLLOW集合 11 一个文法G是LL 1 的 当且仅当对于G的每一个非终结符 的任何两个不同产生式 下面的条件成立 FIRST FIRST 也就是 和 推导不出以同一个终结符a为首的符号串 它们不应该都能推出空字 假若 那么 FIRST FOLLOW A 也就是 若 则 所能推出的串的首符号不应在FOLLOW A 中 12 例 判断文法G E 是否是LL 1 文法 G E E TBB TB T FDD FD F E i 只有3个非终结符 B D F右部有多于一条规则 对于B 由于 FIRST 因此 需要分别考查FIRST集合和FOLLOW集合 FIRST x1 FIRST x2 FIRST TB FIRST 求 FOLLOW B 此时 满足A B 的规则有两个 E TB B TB 观察发现 都为 为 的情况 可知 需要求FOLLOW E 和FOLLOW B 即 现在只需要求FOLLOW E 此时 对于E 满足A B 的规则只有一条 F E 而E为识别符号 因此 FOLLOW B FOLLOW E FIRST FD FOLLOW D FOLLOW T FIRST B FOLLOW B 对于F 只需要考虑FIRST集合 FIRST E FIRST i i 交为空 是LL 1 文法 13 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 各非终结符的FIRST集合如下 FIRST E i FIRST E FIRST T i FIRST T FIRST F i 各非终结符的FOLLOW集合为 FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F 14 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a E TE FIRST TE FOLLOW E T FT FIRST FT FOLLOW T F E aFIRST E FIRST a a 所以G E 是LL 1 的 15 课堂练习 判断文法G S 是否为LL 1 文法 G S S ABA bBCC aC B a Sb 16 用程序实现LL 1 文法的判定 教材74 78相关内容 17 LL 1 分析表M的构造 LL 1 分析方法依靠LL 1 分析表M和一个符号栈进行控制 称为 表驱动 LL 1 分析表结构 分析表与所给定的文法G Z 有关 其行标题为文法G的各非终结符号U 列标题为文法G的终结符号a和输入结束符 分析表M的元素M U a 为一条关于该非终结符号的规则 18 LL 1 分析表M的构造 构造分析表M的算法为 1 对FIRST x 中每一终结符号a 置M U a U x 2 如果 FIRST x 则对于属于FOLLOW U 的每一个终结符号b或 分别置M U b U x 和M U U x 3 将M中所有不能按规则 1 与 2 构造的元素置出错标志err 常用空表示 上算法可用于构造任何文法的分析表 但非LL 1 文法的分析表中有些元素可能有多条规则 19 例 构造文法G S 的分析表M G S S iCtSB aB eS C b其分析表M为 20 LL 1 文法的性质 LL 1 文法是无二义的LL 1 文法不含左递归非LL 1 文法的改造消除左递归提左公因子将产生式 变换为 BB 21 左递归规则 G S S Sa S bL ban n 0 W baaaSbSSaSa 22 左递归关于非终结符P的规则 直接左递归若P P V 且 不以P开头一般左递归若P P S AaA Sb 23 如何消除规则左递归 引入元符号 将形如U y1 y2 ym Ux1 Ux2 Uxn的规则改写成 U y1 y2 ym x1 x2 xn 增加新的非终结符号将形如U y1 y2 ym Ux1 Ux2 Uxn的规则改写成 U y1A y2A ymAA x1A x2A xnA 24 消除左递归 例 E E T TT T F FF E aG E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 25 表驱动予测分析程序模型 Input 总控程序 预测分析表 stack 26 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 27 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 28 予测分析表构造算法 1 对文法G的每个产生式 执行第二步 和第三步 2 对每个终结符a FIRST 把 加 至 A a 中 3 若 FIRST 则对任何b FOLLOW A 把 加至 A b 中 4 把所有无定义的 A a 标上 出错标志 可以证明 一个文法G的予测分析表不含多重入口 当且仅当该文法是LL 1 的 29 分析输入串 a a 栈内容栈顶符号当前输入余留串M X b 1 EEa a E TE 2 E TTa a T FT 3 E T FFa a F a4 E T aaa a 5 E T T a T 6 E E a E TE 7 E T a 8 E TTa T FT 9 E T FFa F a10 E T aaa 11 E T T T 12 E E E 13 30 LL 1 分析中的一种错误处理办法 发现错误1栈顶的终结符与当前输入符不匹配2非终结符A于栈顶 面临的输入符为a 但分析表M的M A a 为空 应急 恢复策略跳过输入串中的一些符号直至遇到 同步符号 为止 同步符号的选择1把FOLLOW A 中的所有符号作为A的同步符号 跳过输入串中的一些符号直至遇到这些 同步符号 把A从栈中弹出 可使分析继续2把FIRST A 中的符号加到A的同步符号集 当FIRST A 中的符号在输入中出现时 可根据A恢复分析 31 递归子程序法 递归子程序法是又一种广为流行的不带回溯的自顶向下语法分析方法 递归子程序法又叫面向目标的分析方法 递归子程序法的基本思想是 在源程序的编译过程中 对于每一个语法成分 用非终结符号代表 用相应的子程序来处理 而子程序又可进一步分为简单子程序 嵌套子程序 递归子程序 递归子程序法是由该分析程序是一些递归子程序的集合而得名的 不同的文法的递归子程序完全不相同 因此对于每一个文法都得编写其分析程序 32 构造给定文法的递归子程序分析法 1 对每一个非终结符号U 编写一个相应子程序P U 2 对于递归出现的非终结符 其相应子程序中应有递归入口部分 及完成如下功能 K K 1 S K 返回地址 命名为 SCIN 另外 还应有递归出口部分 即完成如下功能 K K 1 GOTOS K 1 命名为SCOUT 3 对于规则U x1 x2 xn 显然 应有一个关于非终结符号U的相应子程序P U 构造P U 的方法是 IFchINFIRST x1 THENP X1 ELSEIFchINFIRST x2 THENP X2 ELSE IFchIN