语法分析——自顶向下分析技术 1引言 自顶向下分析的过程是从识别符号出发,试 图构造一个推导,该推导得出的符号串与输 入符号串相同 这种推导是最左推导 从语法的角度看,自顶向下是从根节点构造 语法树的过程。 在进行语法分析的时候不再考虑具体的符号 是怎么构成的 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 • 自顶向下分析的过程是从识别符号出发，试 图构造一个推导，该推导得出的符号串与输 入符号串相同。 • 这种推导是最左推导。 • 从语法的角度看，自顶向下是从根节点构造 语法树的过程。 • 在进行语法分析的时候不再考虑具体的符号 是怎么构成的。 1引言
语法分析-自顶向下分析技术 1引言(续) 由于自顶向下分析技术是一个从识别符号开 始逐步构造最左推导的过程。每一步都将最 左的非终结符号替换为其相应规则的右部。 开始时,句型就是由一个识别符号组成的。 每次选择规则之后,替换最左非终结符号, 得到一个新的句型 由于在一般的情况下,一个非终结符号对应 有多个规则。具体选择哪个规则将是自顶向 下分析技术所需要解决的主要问题。 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 1引言（续） • 由于自顶向下分析技术是一个从识别符号开 始逐步构造最左推导的过程。每一步都将最 左的非终结符号替换为其相应规则的右部。 • 开始时，句型就是由一个识别符号组成的。 每次选择规则之后，替换最左非终结符号， 得到一个新的句型。 • 由于在一般的情况下，一个非终结符号对应 有多个规则。具体选择哪个规则将是自顶向 下分析技术所需要解决的主要问题
语法分析-自顶向下分析技术 1引言(续) 自顶向下分析技术的基础是定理27。在不停 构造推导的过程中,所得到的句型中最长的 不包含非终结符号的头必须也是输入符号串 的头。 如果在构造到某一步时,没有办法得到满足 上面要求的规则。那么当前得到的句型就不 能推倒出输入符号串。这个时候有两个处理 办法:或回溯并重新构造前面的推倒,或者 认为输入符号串不是句型 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 1引言（续） • 自顶向下分析技术的基础是定理2.7。在不停 构造推导的过程中，所得到的句型中最长的 不包含非终结符号的头必须也是输入符号串 的头。 • 如果在构造到某一步时，没有办法得到满足 上面要求的规则。那么当前得到的句型就不 能推倒出输入符号串。这个时候有两个处理 办法：或回溯并重新构造前面的推倒，或者 认为输入符号串不是句型
语法分析 自顶向下分析技术 2带回溯的自顶向下分析技术 现在我们考虑在推导构造不下去的时候进行 回溯的分析技术技术。基本方法是,推导的 时候从候选的规则中任意取一个规则。当发 现这个规则不能继续推导的时候,在选一个 新的规则从新做起。 ·在进行回溯的时候,主要要做的事情就是将 状态恢复到上一次选择时的状态。 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 2 带回溯的自顶向下分析技术 • 现在我们考虑在推导构造不下去的时候进行 回溯的分析技术技术。基本方法是，推导的 时候从候选的规则中任意取一个规则。当发 现这个规则不能继续推导的时候，在选一个 新的规则从新做起。 • 在进行回溯的时候，主要要做的事情就是将 状态恢复到上一次选择时的状态
语法分析 自顶向下分析技术 带回溯的自顶向下分析技术的算法实现 这里我们采用和书上的描述不同的算法。利 用递归技术来实现这个算法。这里描述的方 法不考虑细节的问题 算法的输入参数是:一个包含非终结符号的 符号和一个终结符号串(它必然是输入符号 串的尾)。当从第一个符号推倒出输入符号 串的头的时候,输出是剩余的符号串。否则 输出错误信息。这是一个递归调用自己的程 序 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 带回溯的自顶向下分析技术的算法实现 • 这里我们采用和书上的描述不同的算法。利 用递归技术来实现这个算法。这里描述的方 法不考虑细节的问题。 • 算法的输入参数是：一个包含非终结符号的 符号和一个终结符号串（它必然是输入符号 串的尾）。当从第一个符号推倒出输入符号 串的头的时候，输出是剩余的符号串。否则 输出错误信息。这是一个递归调用自己的程 序
语法分析-—自顶向下分析技术 带回溯的自顶向下分析技术的算法实现续 Match(X,X,.Xn, X) var Input: array [1. Max] of SymbolStrings b flag =0 while (1 >=0 and k<=n) do begin fx1是终结符号 then begin fx1l=lnpu的首符号 or flag=1; then begin :l-1; flag =1; end else begin Input(I+1]=tail(Input[ID; I=I+1; flag =0; end; 选取新的关于Ⅺ的规则,设其右部为Y1Y2.Ym Input[1+1]=Match(Y 1Y2.Ym, Input[D); if (Input([I+1]=ERROR) then begin f没有更多X的规则 then begin I=l-1;fag=l;end flag =0 else begin I: l+l; flag=0; end end of while) then return Input(n+1]: 南京大学计算机系赵建华 else return erRo
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 带回溯的自顶向下分析技术的算法实现续 Match(X1X2…Xn , X) var Input:array [1..Max] of SymbolStrings; begin I=1; Input[I]:= X; flag = 0; while (I >= 0 and In) then return Input[n+1]; else return ERROR; end
语法分析-自顶向下分析技术 回溯自顶向下技术的问题 效率问题 语义处理问题 ·语法错误的显示 左递归问题 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 回溯自顶向下技术的问题 •效率问题 •语义处理问题 •语法错误的显示 •左递归问题
语法分析-自顶向下分析技术 3.无回溯的自顶向下分析技术 先决条件: 1:无左递归,既不能有规则左递归,又不能 有文法左递归。否则自顶向下技术就可能 进入死循环 2:无回溯,要求对任何一个非终结符号对应 的规则,其右部的符号串所能推导出来的 终结符号串的头部是两两不相交的。回顾 在带回溯的算法,可以知道这使得在选择 规则的时候唯一确定适合的规则 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 3. 无回溯的自顶向下分析技术 先决条件： 1：无左递归，既不能有规则左递归，又不能 有文法左递归。否则自顶向下技术就可能 进入死循环。 2：无回溯，要求对任何一个非终结符号对应 的规则，其右部的符号串所能推导出来的 终结符号串的头部是两两不相交的。回顾 在带回溯的算法，可以知道这使得在选择 规则的时候唯一确定适合的规则
语法分析 自顶向下分析技术 预测分析技术 预测分析技术是一种无回溯的分析技术。 它使用一个预测分析表和一个栈来完成对 输入符号串的分析 预测分析表是一个二维数组。它给出了当 需要对A进行推导,并且当前输入符号是T 的时候,应该选择哪个规则。没有规则可 选,此时输入符号串不是句子 在输入符号串后面都跟有一个# 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 预测分析技术 • 预测分析技术是一种无回溯的分析技术。 • 它使用一个预测分析表和一个栈来完成对 输入符号串的分析。 • 预测分析表是一个二维数组。它给出了当 需要对A进行推导，并且当前输入符号是T 的时候，应该选择哪个规则。没有规则可 选，此时输入符号串不是句子。 • 在输入符号串后面都跟有一个#
语法分析 自顶向下分析技术 预测分析过程 在这个过程中,设已经扫描过的字符串u而 栈中的符号串(自顶向下)为v那么uv联 合起来就是一个句型。 整个过程就是要试图将这个句型推导到输 入符号串 当栈顶符号为X的时候,过程的下一步动作 就是要对这个符号选取一个规则进行推导。 过程使用预测分析表,以及当前的输入符 号来确定选取哪个规则。 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自顶向下分析技术 预测分析过程 • 在这个过程中，设已经扫描过的字符串u而 栈中的符号串（自顶向下）为v, 那么uv联 合起来就是一个句型。 • 整个过程就是要试图将这个句型推导到输 入符号串。 • 当栈顶符号为X的时候，过程的下一步动作 就是要对这个符号选取一个规则进行推导。 • 过程使用预测分析表，以及当前的输入符 号来确定选取哪个规则