编译原理讲义 (第四章:语法分析 自顶向下分析技术) 南京大学计算机系 赵建华
编译原理讲义 (第四章:语法分析-- 自顶向下分析技术) 南京大学计算机系 赵建华
在词法分析完成之后,进入语法分析阶 段 ·语法分析阶段的任务是:检查程序的语 法是否正确,并生成内部中间表示形式 语法分析的 输入:属性字序列。 输出:程序的内部中间表示形式
引言 • 在词法分析完成之后，进入语法分析阶 段。 • 语法分析阶段的任务是：检查程序的语 法是否正确，并生成内部中间表示形式。 • 语法分析的 – 输入：属性字序列。 – 输出：程序的内部中间表示形式
自顶向下分析技术与识别算法 从推导的角度看,从识别符号出发,试 图推导出与输入符号串相同的符号串。 般来讲,构造出的推导是最左推导。 从语法树的角度看,从根节点,试图向 下一个语法树,其末端节点正好与输入 符号串相同
自顶向下分析技术与识别算法 • 从推导的角度看，从识别符号出发，试 图推导出与输入符号串相同的符号串。 一般来讲，构造出的推导是最左推导。 • 从语法树的角度看，从根节点，试图向 下一个语法树，其末端节点正好与输入 符号串相同
讨论前提 输入的是符号序列,不对符号构造情况 感兴趣。 语法分析的文法是上下文无关文法。 自顶向下分析技术的理论基础是定理2.7: 如果z:=X1X2.Xn且y为句子。那么如 果X1X2Xn→>y,必然存在y1y2…yn使 得X→>*y且
讨论前提 • 输入的是符号序列，不对符号构造情况 感兴趣。 • 语法分析的文法是上下文无关文法。 • 自顶向下分析技术的理论基础是定理2.7： 如果Z::=X1X2…Xn且y为句子。那么如 果X1X2…Xn=>y，必然存在y1 ,y2 ,…,yn使 得Xi=>*yi且y=y1y2… yn
要解决的基本问题 对于特定的终结符号,实用那个重写规 则来替换?
要解决的基本问题 • 对于特定的终结符号，实用那个重写规 则来替换？
无回溯的自顶向下分析技术 先决条件: 无递归 既没有规则左递归,也没有文法左递归 无回溯性 对于任一非终结符号U的规则右部x1x2|xn, 其对应的字的头终结符号两两不相交
无回溯的自顶向下分析技术 • 先决条件： • 无递归 – 既没有规则左递归，也没有文法左递归。 • 无回溯性 – 对于任一非终结符号U的规则右部x1 |x2 |…|xn， 其对应的字的头终结符号两两不相交
递归下降分析技术(实现思想) 实现思想: 识别程序由一组过程组成。每个过程对 应于一个非终结符号。 ·每一个过程的功能是:选择正确的右部, 扫描完相应的字。在右部中有非终结符 号时,调用该终结符号对应的过程来完 成
递归下降分析技术（实现思想） • 实现思想： • 识别程序由一组过程组成。每个过程对 应于一个非终结符号。 • 每一个过程的功能是：选择正确的右部， 扫描完相应的字。在右部中有非终结符 号时，调用该终结符号对应的过程来完 成
基本架构(1) 对于每个非终结符号U:=u1u2|un处理的方法如下: ch=当前符号 f(ch可能是ul字的开头)处理ul的程序部分 else if(ch可能是u2字的开头) 处理u2的程序部分 else error) ·对于无回溯的文法保证选择是唯一的。 当存在空规则的时候,可以把eror(替代为 return;}这样的处 理使发现错误的情况比较晚。 约定:进入这个过程时,对于U的第一个符号已经被读到当 前符号。离开这个程序的时候,下一个符号已经被读到当前 符号
基本架构(1) • 对于每个非终结符号U::=u1 |u2 |…|un处理的方法如下： U(){ ch=当前符号 if(ch可能是u1字的开头) 处理u1的程序部分 else if(ch可能是u2字的开头) 处理u2的程序部分 … else error() } • 对于无回溯的文法保证选择是唯一的。 • 当存在空规则的时候，可以把error()替代为{return;}这样的处 理使发现错误的情况比较晚。 • 约定：进入这个过程时，对于U的第一个符号已经被读到当 前符号。离开这个程序的时候，下一个符号已经被读到当前 符号
基本架构(2) 对于每个右部u-x1x2xn的处理架构如 处理x1的程序; 处理x2的程序; 处理xn的程序; 如果右部为空,则不处理
基本架构(2) • 对于每个右部u1=x1x2…xn的处理架构如 下： 处理x1的程序； 处理x2的程序； … … … 处理xn的程序； • 如果右部为空，则不处理
基本架构(3) 对于右部中的每个符号x1 如果ⅹ为终结符号: f(x=当前的符号) (NextCho; return; else 出错处理 如果x为非终结符号,直接调用相应的过 程:
基本架构(3) • 对于右部中的每个符号xi • 如果xi为终结符号： if(x== 当前的符号) {NextCh()；return;} else 出错处理 • 如果xi为非终结符号，直接调用相应的过 程： xi ()