对自上而下分析来说,能否找到从文法开始符 开始的推导序列,使得推导出的句子恰为输入 串。或者说,能否从根结点出发,向下生长出 棵语法分析树,其叶结点组成的句子恰为输 入串。显然语法分析树的每一步生长每一步推 导)都以能否与输入串匹配为准。 对自下而上分析来说,能否从输入串出发找到 个归约序列,能最终地归约为文法开始符。 或者说,能否从叶结点出发,向上归结出以文 法开始符为根结点的语法分析树,每一步的归 约,都以待处理的字符串是否已形成句柄(或最 左素短语)为准
6 •对自上而下分析来说，能否找到从文法开始符 开始的推导序列，使得推导出的句子恰为输入 串。或者说，能否从根结点出发，向下生长出 一棵语法分析树，其叶结点组成的句子恰为输 入串。显然语法分析树的每一步生长(每一步推 导)都以能否与输入串匹配为准。 •对自下而上分析来说，能否从输入串出发找到 一个归约序列，能最终地归约为文法开始符。 或者说，能否从叶结点出发，向上归结出以文 法开始符为根结点的语法分析树，每一步的归 约，都以待处理的字符串是否已形成句柄(或最 左素短语)为准。
§4,2递归下降分析方法 递归下降分析法是一种自顶向下的分 析方法,文法的每个非终结符,对应于 个递归过程。分析就是从方法开始符出发 执行一组递归过程,向下推导,直到推导 出句子。或者说从根结点出发,自上而下 为输入串寻找一个最左匹配序列,建立 棵语法分析树
7 §4.2 递归下降分析方法 递归下降分析法是一种自顶向下的分 析方法，文法的每个非终结符，对应于一 个递归过程。分析就是从方法开始符出发 执行一组递归过程，向下推导，直到推导 出句子。或者说从根结点出发，自上而下 为输入串寻找一个最左匹配序列，建立一 棵语法分析树。
试探分析法 「例41文法 S->XAy A→>ab|la 若输入串为xy时,分析过程为: (1)首先建立根结点S (2)文法关于S的产生式只有一个,所以从S生 长分析树如图4l(a)。它的第一个终结符x与输 入串待分析字符x匹配,于是下一待分析字符 为a,期待与分析树中x右的叶结点A匹配。 8
8 一、试探分析法 [例4.1] 文法 S->xAy A->ab |a 若输入串为xay时，分析过程为： (1) 首先建立根结点S。 (2) 文法关于S的产生式只有一个，所以从S生 长分析树如图4.1(a)。它的第一个终结符x与输 入串待分析字符x匹配，于是下一待分析字符 为a，期待与分析树中x右的叶结点A匹配。
(3)非终结符A有两个候选式,先选用第一个候 选式。生长分析树如图4.1(b),这时分析树第 二叶结点a恰与待分析字符a匹配 (4)输入串中下一待分析字符为y,期待与第三 叶结点b匹配。此时发觉这两个字符是不同的, 即匹配失败。问题在于在生成A的子树时选用 的是第一个候选式。 (5)于是将A的这棵子树注销,把匹配指针退回 到输入串的第二字符,也即恢复与A匹配时的 现场,即(3)之前
9 (3) 非终结符A有两个候选式，先选用第一个候 选式。生长分析树如图4.1(b)，这时分析树第 二叶结点a恰与待分析字符a匹配。 (4) 输入串中下一待分析字符为y，期待与第三 叶结点b匹配。此时发觉这两个字符是不同的， 即匹配失败。问题在于在生成A的子树时选用 的是第一个候选式。 (5) 于是将A的这棵子树注销，把匹配指针退回 到输入串的第二字符，也即恢复与A匹配时的 现场，即(3)之前。
(6)A选用第二候选式,生长分析树如图 41(c),这时第二叶结点a与输入串第二字 符匹配。 (⑦)输入串下一待分析字符指向y,分析树 指向a右叶结点y。两者恰匹配,所以,分 析树41(c)即为输入串xay语法分析树。 10
10 (6) A选用第二候选式，生长分析树如图 4.1(c)，这时第二叶结点a与输入串第二字 符匹配。 (7) 输入串下一待分析字符指向y，分析树 指向a右叶结点y。两者恰匹配，所以，分 析树4.1(c)即为输入串xay语法分析树。