无回溯的自顶向下分析技术 先决条件: 无递归 既没有规则左递归,也没有文法左递归 无回溯性 对于任一非终结符号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 ()