编译原理语法(自顶向下语法分析：递归下降).pptVIP

* 第 6 讲 西北农林科技大学本科教程 主讲教师：赵建邦 第三章 语法分析 3.1 文法和语言 3.2 推导与语法树 3.3 自顶向下的语法分析 3.4 自底向上的语法分析 3.5 规范规约的自底向上语法分析方法 第三章《语法分析》 3.3 自顶向下的语法分析 递归下降分析法 LL(1)分析法（下一讲内容） 重点掌握 消除左递归 消除回溯 构建递归下降子程序 本讲目标 3.3 自顶向下的语法分析 算法思想： 从文法的开始符号出发，向下推导，如果推导出的句子恰好为输入符号串，则输入符号串为符合该文法的句子； 或者：开始符号作为根节点，向下生长出一棵语法树，其叶子节点组成的句子恰好为输入符号串。这里的每一步“生长”对应一次直接推导。 自顶向下分析方法: 1、不确定的自顶向下分析 2、确定的自顶向下分析 递归下降分析法 LL(1)分析法 1、不确定的自顶向下分析方法 假定文法G[S]为 　　 S?→?xAy　　?? A?→?ab | a 若输入串为xay，则其分析过程如下： (1)建立根节点S； (2)关于S的产生式只有一个，则生长语法树, 匹配语法树的第一个终结符x； (3) A?→?ab | a 有两个候选式，选择第一个, 并且匹配语法树的第二个叶子节点a； (4)输入串xay期待匹配y,而语法树中的b与之匹配失败； S A y a b x 3.3 自顶向下的语法分析 1、不确定的自顶向下分析方法 假定文法G[S]为 　　 S?→?xAy　　?? A?→?ab | a 若输入串为xay，则其分析过程如下： (5)撤销匹配a， 注销A所生成的子树，回溯； (6)选择产生式A?→?a，重新匹配a； (7) 匹配输入串的字符y；而语法树的最后 一个叶子节点也是y,因此语法树和输入串xay匹配成功。 S A y a b x a 3.3 自顶向下的语法分析 小结：关于不确定的自顶向下分析方法 这种自顶向下的分析是一个不断试探的过程；即，在分析过程中，如果出现多个产生式(即候选式)可供选择，则逐一试探每一候选式进行匹配，每当一次试探失败，就选取下一候选式再进行试探； 此时，必须回溯到这一次试探的初始现场，包括注销已生长的子树及将匹配指针调回到失败前的状态。 这种带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低，在实用的编译程序中很少使用。 3.3 自顶向下的语法分析 2、确定的自顶向下分析方法 确定的自顶向下分析要求文法满足两个条件： (1) 文法不含左递归：即不存在这样的非终结符号A：有A→A…存在或者有 ； 原因：左递归的文法使自顶向下分析工作陷入无限循环 E→E+T 3.3 自顶向下的语法分析 (2) 无回溯，对文法的任一非终结符号，当其产生式右部有多个候选式可供选择时，各候选式所推出的终结符号串的首字符集合要两两不相交 原因：会导致先前做的一大堆语法工作和语义工作(指中间代码产生工作和各种表格的簿记工作)推倒重来 3、消除左递归 方法： 引入一个新的非终结符，把含有左递归的产生式改写为右递归。 设关于非终结符A的直接左递归的产生式形如　　 A?→?Aα | β　　其中，α、β是任意的符号串且β不以A开头。该产生式所能推导的句子如下： … 3.3 自顶向下的语法分析 再看下面不含A的直接左递归的产生式： A?→?βA A →?α A | ε 这两个产生式所能推导的句子如下：　 可见，两种产生式所推导的结果相同：都能描述正规表达式βα*　 3.3 自顶向下的语法分析 3、消除左递归 规则：将产生式 A?→?Aα | β 改写为： A?→?βA‘ A’ →?α A‘ | ε其中， A’是新引入的非终结符。ε 不可缺少，否则推导过程无法结束。 3.3 自顶向下的语法分析 例如，含有直接左递归的表达式文法G[E]为　　 　　 G[E]:E?→?E+T | T ? T?→?T*F | F F?→?(E) | i E?→?TE E?→?+TE | ε (3.2) 经过消去直接左递归后得到文法G[E]为 T?→?FT T?→?*FT | ε? ? G[E]: F?→?(E) | i 3.3 自顶向下的语法分析 3、消除左递归 一般情况下，设文