语法分析——自顶向下分析技术 1引言 自顶向下分析的过程是从识别符号出发,试 图构造一个推导,该推导得出的符号串与输 入符号串相同 这种推导是最左推导 从语法的角度看,自顶向下是从根节点构造 语法树的过程。 在进行语法分析的时候不再考虑具体的符号 是怎么构成的 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 • 自顶向下分析的过程是从识别符号出发，试 图构造一个推导，该推导得出的符号串与输 入符号串相同。 • 这种推导是最左推导。 • 从语法的角度看，自顶向下是从根节点构造 语法树的过程。 • 在进行语法分析的时候不再考虑具体的符号 是怎么构成的。 1引言
语法分析-自顶向下分析技术 1引言(续) 由于自顶向下分析技术是一个从识别符号开 始逐步构造最左推导的过程。每一步都将最 左的非终结符号替换为其相应规则的右部。 开始时,句型就是由一个识别符号组成的。 每次选择规则之后,替换最左非终结符号, 得到一个新的句型 由于在一般的情况下,一个非终结符号对应 有多个规则。具体选择哪个规则将是自顶向 下分析技术所需要解决的主要问题。 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 1引言（续） • 由于自顶向下分析技术是一个从识别符号开 始逐步构造最左推导的过程。每一步都将最 左的非终结符号替换为其相应规则的右部。 • 开始时，句型就是由一个识别符号组成的。 每次选择规则之后，替换最左非终结符号， 得到一个新的句型。 • 由于在一般的情况下，一个非终结符号对应 有多个规则。具体选择哪个规则将是自顶向 下分析技术所需要解决的主要问题
语法分析-自顶向下分析技术 1引言(续) 自顶向下分析技术的基础是定理27。在不停 构造推导的过程中,所得到的句型中最长的 不包含非终结符号的头必须也是输入符号串 的头。 如果在构造到某一步时,没有办法得到满足 上面要求的规则。那么当前得到的句型就不 能推倒出输入符号串。这个时候有两个处理 办法:或回溯并重新构造前面的推倒,或者 认为输入符号串不是句型 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 1引言（续） • 自顶向下分析技术的基础是定理2.7。在不停 构造推导的过程中，所得到的句型中最长的 不包含非终结符号的头必须也是输入符号串 的头。 • 如果在构造到某一步时，没有办法得到满足 上面要求的规则。那么当前得到的句型就不 能推倒出输入符号串。这个时候有两个处理 办法：或回溯并重新构造前面的推倒，或者 认为输入符号串不是句型
语法分析 自顶向下分析技术 2带回溯的自顶向下分析技术 现在我们考虑在推导构造不下去的时候进行 回溯的分析技术技术。基本方法是,推导的 时候从候选的规则中任意取一个规则。当发 现这个规则不能继续推导的时候,在选一个 新的规则从新做起。 ·在进行回溯的时候,主要要做的事情就是将 状态恢复到上一次选择时的状态。 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 2 带回溯的自顶向下分析技术 • 现在我们考虑在推导构造不下去的时候进行 回溯的分析技术技术。基本方法是，推导的 时候从候选的规则中任意取一个规则。当发 现这个规则不能继续推导的时候，在选一个 新的规则从新做起。 • 在进行回溯的时候，主要要做的事情就是将 状态恢复到上一次选择时的状态
语法分析 自顶向下分析技术 带回溯的自顶向下分析技术的算法实现 这里我们采用和书上的描述不同的算法。利 用递归技术来实现这个算法。这里描述的方 法不考虑细节的问题 算法的输入参数是:一个包含非终结符号的 符号和一个终结符号串(它必然是输入符号 串的尾)。当从第一个符号推倒出输入符号 串的头的时候,输出是剩余的符号串。否则 输出错误信息。这是一个递归调用自己的程 序 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 带回溯的自顶向下分析技术的算法实现 • 这里我们采用和书上的描述不同的算法。利 用递归技术来实现这个算法。这里描述的方 法不考虑细节的问题。 • 算法的输入参数是：一个包含非终结符号的 符号和一个终结符号串（它必然是输入符号 串的尾）。当从第一个符号推倒出输入符号 串的头的时候，输出是剩余的符号串。否则 输出错误信息。这是一个递归调用自己的程 序