理自顶向下语法分析.ppt

第5章自顶向下语法分析方法 教学目的 正确理解自上而下分析的基本思想 熟练掌握递归下降分析基本方法 消除左递归 消除回溯 构造递归下降子程序 掌握预测分析程序的基本原理和预测分析表构造 理解LL 1 方法的定义 教学重点 难点 LL 1 文法的判别 课时分配 6学时 本章知识点 内容 确定的自顶向下分析思想 LL 1 文法的判别 结束 自上而下分析面临的问题 确定的自顶向下分析方法 语法分析器的功能 语法分析是编译过程的核心部分 它的任务是在词法分析识别出单词符号串的基础上 分析并判定程序的语法结构是否符合语法规则 语法分析器的工作本质上就是按文法的产生式 识别输入符号串是否为一个句子 并建立一棵与输入串相匹配的语法分析树 按照语法分析树的建立方法 可以把语法分析方法分成两类 一类是自上而下分析法一类是自下而上分析法 不确定的自顶向下分析法递归下降分析法确定的预测分析法LL 1 语法分析方法简单优先分析法优先分析法算符优先分析法自底向上分析法LR 0 分析法LR分析法SLR 1 分析法LR 1 分析法LALR 1 分析法 语法分析技术概况 自上而下分析面临的问题 自上而下就是从文法的开始符号出发 向下推导 推出句子 其主旨是 对任何输入串 试图用一切可能的办法 从文法开始符号 根结 出发 自上而下地为输入串建立一棵语法树 或者说 为输入串寻找一个最左推导 这种分析过程本质上是一种试探过程 是反复使用不同产生式谋求匹配输入串的过程 要点 由根向下构造语法树 构造最左推导 推导出的终结符是否与当前输入符匹配SaaabABaA S ABA aA B b bB自上而下推导aaab S ABS AB aABA aA aaABA aA aaaABA aA aaa BA aaabB b 1 选择使用哪个产生式进行推导 2 假定要被代换的最左非终结符号是V 且有n条规则 V A1 A2 An 那么如何确定用哪个右部去替代V 思考 例 假定有文法 1 S xAy 2 A 以及输入串x y 记为 为了自上而下构造 的语法树 我们首先按文法的开始符号产生根结s 并让指示器IP指向输入串的第一个符号x 然后 用S的规则 此处关于S的规则仅有一条 把这棵树发展为 非终结符A有两个候选 试着用它的第一个候选去匹配输入串 于是把语法树发展为子树A的最左子结和IP所指的符号 相符 然后我们再把IP调为指向下一符号并让A的第二个子结进入工作 但A的第二子结 和当前所指的符号y不一致 因此 A告失败 这意味着A的第一个候选此刻不适用于构造 的语法树 这时应该回头 回溯 看A是否还有别的候选 为了这种回溯 我们一方面应把A的第一候选所发展的子树注销掉 另一方面应把IP恢复为进入A时的原值 也就是让它重新指向第二个输入符号 现在我们试探A的第二个候选 即考虑如下的语法树 由于子树A只有一个子结 而且它和IP所指的符号相一致 于是 A完成了匹配任务 在A获得匹配后 指示器IP应指向下一个未被触及符号y 在S的第二子结A完成匹配后 接着就轮到第三个子结y进行工作 由于这个子结和最后一个输入符号相符 于是 我们完成了为 构造语法树的任务 证明了 是一个句子 例 文法G0 S 1 S Sa 2 S b分析baa是不是文法的句子 按照自上而下的分析思想选用产生式 1 来推导S Sa语法树末端结点最左符号为非终结符 所以选用产生式 1 继续推导S Sa Saa此时语法树末端结点最左符号仍为非终结符 所以选用产生式 1 继续推导S Sa Saa Saaa问题 试图用S匹配输入串时 出现 在没有读入任何输入符号的情况下 又得重新要求S去进行新的匹配 原因 文法含有左递归 自上而下分析法存在的困难 不确定的自顶向下语法分析一 基本方法 从文法的开始符号出发 反复使用各种产生式 寻找与输入符号匹配的最左推导 二 结论1 在推导过程中出现了大量的回朔现象 2 推导过程出现了死循环 应消除左递归 3 难以知道输入串中出错的确切位置 自上而下分析方法不允许文法含有任何左递归 为构造不带回溯的自上而下分析算法 首先要消除文法的左递归性 并找出克服回溯的充分必要条件 消除回朔实际上就是提取左因子 提取公共左因子 A 1 2 n 1 2 m 其中每个 不以 开头 那末 可以把这些规则改写成 A A 1 2 mA 1 2 n 例 考虑条件语句的产生式stmt ifexprthenstmt ifexprthenstmtelsestmt other存在左因子ifexprthenstmt 妨碍自顶向下方法的使用 条件语句消除回朔后产生式的结果为 stmt ifexprthenstmtS otherS elsestmt 例 文法 Stm id Exp id ExpL ExpL Exp Exp ExpL Stm idStm Stm ExpStm ExpL ExpL ExpExpL ExpL ExpExpL ExpL 消除左公共因子的例子 1 左递归的定义对于某些字符串 如果存在推导A A 我们就称该文法含有左递归 左递归的消除 2 左递归的危害导致推导过程中出现大量的死循环 妨碍自顶向下的语法分析 3 左递归分类 直接左递归和间接左递归 直接左递归如果文法中含有如下形式的产生式 我们就称该文法含有直接左递归 A A 其中A VN VN VT 间接左递归如果文法中含有如下形式的产生式 我们就称该文法含有间接左递归 A B B A 其中A B VN VN VT 左递归的消除 直接消除产生式中的左递归是比较容易的 假定关于非终结符P的规则为 P P 其中 不以P开头 那么 我们可以把P的规则改写为如下的非直接左递归形式 P P P P 例 消除文法中左递归E E T TT T F FF E i 消除左递归后产生式为 E TE E TE T FT T FT F E i 假定P关于的全部产生式是P P 1 P 2 P m 1 2 n其中 每个 都不等于 而每个 都不以P开头那末 消除P的直接左递归性就是把这些规则改写成 P 1P 2P nP P 1P 2P mP 消除文法中左递归规则 例 试构造与下列文法G S 等价的无左递归文法 G S S Sa Nb c 1 N Sd Ne f 2 对于 1 我们引入新非终结符S 则 S NbS cS 1 S aS 2 将S代入 2 N Ne NbS d cS d f引入新非终结符N N cS dN fN 3 N eN bS dN 4 间接左递归 例如文法 S Qc cQ Rb bR Sa a虽不具有直接左递归 但S Q R都是左递归的 例如有S Qc Rbc Sabc 消除间接左递归算法 1 把文法G的所有非终结符按任一顺序排列成P1 P2 Pn 按此顺序执行 2 FORi 1TOnDOBEGINFORj 1TOi 1DO把形如Pi Pj 的规则改写成Pi 1 2 k 其中Pj 1 2 k是关于Pj的所有规则消除关于Pi规则的直接左递归性END 例 考虑文法 S Qc cQ Rb bR Sa a消除左递归 解 将终结符排序为R Q S 对于R不存在直接左递归 把R带入到Q中有关的候选式 Q Sab ab b现在Q同样不含直接左递归 把它带入S的有关候选式 S Sabc abc bc c经消除S的直接左递归后我们们得到整个文法S abcS bcS cS S abcS Q Sab ab bR Sa a由于关于Q R的规则式多余的则可化简得到 S abcS bcS cS S abcS 例 1 A B 1 a 2 B C 2 b 3 C A 3 c 2 ij1没有直接左递归 无须改写 1 非终结符排序 A B C 3 新文法中的产生式是 1 2 4 5 消除 3 中的直接左递归 引入新非终结符C 4 C b 1 3 a 3 c C 5 C 2 1 3C 2把 2 代入 3 得 3 C C 2 1 3 b 1 3 a 3 c 31把 1 代入 3 得 3 C B 1 a 3 c 21无须替换 没有直接左递归 无需改写 确定的自顶向下语法分析 问题 在改造文法 消除文法中的左递归和回朔现象 后 在最左推导众多产生式中应选择哪个产生式推导 例5 2 1 已知文法G S S pAS qbA cAdA a给出句子w pccadd的最左推导 分析 该文法有两个特点 1 每个产生式右部符号串以终结符开始 2 如果产生式有相同的左部 右部符号串以不同的终结符开始 因此该文法在推导过程中完全可以根据当前输入符号决定选择哪个产生式往下推导 因此推导过程是唯一的 为确定的自顶向下语法分析 例5 2 2 已知文法G S S ApS BqA aA cAB bB dB给出句子w ccap的最左推导 分析 该文法有两个特点 1 每个产生式右部符号串不全以终结符开始 2 如果产生式有相同的左部 右部符号串以不同的终结符或非终结符开始 3 文法中无空产生式 因此该文法在推导过程中根据当前输入符号决定选择哪个产生式往下推导就没有例5 1 1那么直观 比如对于第一个输入符号c 就无法确定到底是选择第一个产生式S Ap 还是选择第二个产生式S Bq往下推导 遇到这种情况 首先需要计算各文法右部符号串的开始符号集 首字符集 FIRST 计算FIRST集令G是一个不含左递归的文法 对G的所有非终结符的每个候选 定义它的终结首符集FIRST 为 FIRST a a a VT 若 则 FIRST 对每一文法符号X V 计算FIRST集的方法为 1 若X VT 则FIRST X X 2 若X VN 且有产生式X a a VT 则a FIRST X 3 若X VN X FIRST X 4 若X VN Y1 Y2 Yi VN 且有产生式X Y1 Y2 Yn 当Y1 Y2 Yi 1 时 其中1 i n 则FIRST Y1 FIRST Y2 FIRST Yi 1 FIRST Yi 都包含在FIRST X 中 5 当4 中所有Yi 则FIRST X FIRST Y1 FIRST Y2 FIRST Yi 反复使用方法1 到5 直到每个非终结符号的FIRST集不再扩大为止 解 FIRST Ap a c FIRST Bq b d 显然两个集合两两不相交 由于当前输入符号c FIRST Ap 所以我们选择第一个产生式q往下推导 由于推导过程是唯一的 因此为确定的自顶向下语法分析 例5 2 2 已知文法G S S ApS BqA aA cAB bB dB给出句子w ccap的最左推导 总结 如果遇到文法中产生式有相同的左部 右部符号串以不同的终结符或非终结符开始的情况 在推导过程中根据当前输入符号决定选择哪个产生式往下推导时 首先需要计算各文法右部符号串的开始符号集 要求具有相同的左部 不同右部符号串的各开始符号集必须两两不相交 当前输入符号属于哪个右部符号串的开始符号集 就选择哪个产生式往下推导 例5 2 3 已知文法G S S aAS dA bAsA 给出句子w abd的最左推导 1 每个产生式右部符号串不全以终结符开始 2 如果产生式有相同的左部 右部符号串以不同的终结符或非终结符开始 3 文法中有空产生式 因此该文法在推导过程中根据当前输入符号决定选择哪个产生式往下推导就没有例5 1 1那么直观 比如在由句型abAS推导出句型abd的这一步时 非终结符A对应的两个产生式都无法直接推导出终结符d 但是由于非终结符A可以推导出空产生式 所以遇到这种情况 我们还要看跟在非终结符A后面的非终结符S能不能推导出终结符d 如果可以 仍然可以实现句型abd的推导 为此 我们定义一个文法符号的后继符号集 总结 该文法有两个特点 定义 假定S是文法G的开始符号 对于任何非终结符A我们定义 FOLLOW A a S Aa a VT 特别是 若S A 则规定 FOLLOW A 后继符号集FOLLOW集 对每一文法符号A VN 计算FOLLOW集的方法为 1 设S为文法中开始符号 FOLLOW S 为句子的括号 2 若有A B 是一个产生式 则FIRST 包含在FOLLOW B 中 若 则FOLLOW A 也包含在FOLLOW B 中 3 反复使用方法2 直到每个非终结符号的FOLLOW集不再扩大为止 根据定义 我们求出文法G中 FOLLOW A a d 由于当前输入符号d FOLLOW A 所以我们选择第二个产生式往下推导 由于推导过程是唯一的 因此为确定的自顶向下语法分析 例5 2 3 已知文法G S S aAS dA bASA 给出句子w abd的最左推导 如果文法中有空产生式 产生式的选择就比较麻烦 在推导过程中根据当前输入符号决定选择哪个产生式往下推导时 必须由各文法右部符号串的开始符号集以及非终结符的后继符号集共同决定 要求具有相同的左部 不同右部符号串的各开始符号集以及后继符号集必须两两不相交 当前输入符号属于哪个集合 就选择哪个产生式往下推导 总结 通过刚才三个例题 我们发现在确定的自顶向下语法分析过程中 对每个产生式的选择是由输入符号决定的 同时对给定文法必须做一定的限制 才能保证每一次推导选择的产生式都是唯一的 保证整个推导的过程是一个唯一的过程 下面我们首先定义每一次推导选择的产生式的方法 通过可选集Select集的计算来实现 Select集的定义 Select A First 当 First Select A First Follow A 当 First 例 对于文法E TE E TE T FT T FT F E i构造每个非终结符的FIRST和FOLLOW集合 解 FIRST E i FOLLOW E FIRST E FOLLOW E FIRST T i FOLLOW T FIRST T FOLLOW T FIRST F i FOLLOW F FOLLOW F FIRST T 因为T 所以将FOLLOW T 加到FOLLOW F 中 由于T FT 则 FOLLOW F FOLLOW T FIRST E 练习 求出下面文法G4每个非终结符的FIRST和FOLLOW集 G B LB1B1 LB1 L KL1L1 KL1 K B t 解 FIRST B t FIRST B1 FIRST L t FIRST L1 FIRST K t FOLLOW B FOLLOW B1 FOLLOW B FOLLOW L FIRST B FOLLOW B1 t FOLLOW L1 FOLLOW L t FOLLOW K FIRST L1 FOLLOW L1 FOLLOW L t 使用自上而下的分析技术必须满足LL 1 文法LL 1 文法的含义是 第一个L表明自顶向下分析是从左向右扫描输入串 第二个L表明分析过程将用最左推导 1表明只需向右查看一个符号便可决定选择哪个产生式进行推导 LL K 文法指只需向右查看K个符号便可决定选择哪个产生式进行推导 LL 1 文法 判断某给定文法是否为LL 1 文法充分必要条件方法一 1 文法不含左递归 2 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交 即 若A 1 2 m 则FIRST i FIRST j i j 3 对文法中的每个非终结符A 若它存在某个候选首符集包含 则FIRST A FOLLOW A 一个文法若满足以上条件 称该文法G为LL 1 文法 判断某给定文法是否为LL 1 文法充分必要条件方法为二 1 文法不含左递归 2 对于U的任意两个不同的规则有 Select U Select U 其中 若 First 则Select A First 若 First 则Select A First Follow A 例 已知文法G S S aAS dA bASA 判别该文法是否为LL 1 文法 1 首先根据LL 1 文法的定义 计算该文法的可选集 Select S aA a Select S d d Select A bAs b Select A a d 2 看看具有相同的左部 不同右部符号串的各可选集是否两两不相交 Select S aA Select S d Select A bAs Select A 由于具有相同的左部 不同右部符号串的各可选集两两不相交 所以文法为LL 1 文法 能够实现确定的自顶向下语法分析 例题 已知文法G S S aASS bA bAA 判别该文法是否为LL 1 文法 1 首先根据LL 1 文法的定义 计算该文法的可选集 Select S aAs a Select S b b Select A bA b Select A a b 2 看看具有相同的左部 不同右部符号串的各可选集是否两两不相交 Select S aAs Select S b Select A bA Select A b 由于具有相同的左部 不同右部符号串的各可选集两两相交 所以文法不是LL 1 文法 不能够实现确定的自顶向下语法分析 递归下降法 Recursive DescentParsing 递归下降法是进行语法分析的一种方法 要求文法是LL 1 文法 递归下降法对每个非终结符按其产生式结构产生相应语法分析子程序 终结符产生匹配命令非终结符则产生调用命令文法递归相应子程序也递归 所以称这种方法为递归子程序方法或递归下降法 首页 确定的自顶向下分析方法 递归下降法对应每个非终结符 编一个独立的子程序 对应每个非终结符语法分析从读入第一个单词开始 沿语法描述图箭头所指出的方向进行分析 当遇到非终结符时 则调用相应的子程序 当遇到描述图中是终结符时 则判断当前读入的单词是否与图中的终结符相匹配 若匹配 再读取下一个单词继续分析 遇到分支点时 将当前的单词与分支点上多个终结符逐个相比较 若都不匹配时可能是进入下一个非终结符语法单位或是出错 递归下降法实现思想 例 Stm whileCondoStm则对应产生式右部的语法分析程序部分如下 procedureStm beginMatch while Con Match do Stm end 假设有文法Z aBaB bB c则相应的递归子程序可如下 procedureZ beginiftoken athenMatch a B Match a elseerr end procedureB beginiftoken bthenMatch b B elseiftoken cthenMatch c elseerr end 主程序 BeginReadToken Zend ReadToken 例 给定文法G 产生式如下 L为开始符号 L E E A L E A E LA a b z 演示文法的递归下降分析程序 例 递归下降分析程序演示 预测分析程序 predictiveparser 预测分析程序的结构 采用下推自动机这种数据模型 如右图 包括以下几个部分 1 输入带 2 分析栈 3 预测分析表其中输入带为一个存放输入符号串w的缓冲器 下推栈用来保存语法符号 控制程序对输入带进行控制分析 输出产生式序列 预测分析表为每步推导选择产生式提供依据 当下推自动机开始工作时 初始状态栈上只有语句括号 和文法的开始符号 输入缓冲区中有输入符号串w 当状态栈上只有语句括号 输入缓冲区也只有语句括号 时自动机结束 1 预测分析表的构造 2 预测分析算法 实现预测分析方法的关键 对于每一产生式A 作 2 和 3 2 对于FIRST 中的每一终结符a 将A 填入M A a 3 如果 属于FIRST 则将A 填入FOLLOW A 中任一元素b的M A b 4 将所有无定义的M A b 标上错误标志 预测分析表的构造算法 构造分析表M的算法是 BEGIN首先把 然后把文法开始符号推入栈 把第一个输入符号读进a FLAG TRUE WHILEFLAGDOBEGI