递归下降法.ppt

递归下降分析法 递归下降分析法是确定的自上而下分析法 这种分析法要求文法是LL 1 文法 递归下降分析法 基本思想 对文法中的每个非终结符编写一个函数 或子程序 每个函数 或子程序 的功能是识别由该非终结符所表示的语法成分 由于描述语言的文法常常是递归定义的 因此相应的这组函数 或子程序 必然以相互递归的方式进行调用 所以将此种分析法称为递归下降分析法 递归下降分析法 构造递归下降分析程序的方法 为每个非终结符编制一个递归下降分析函数 每个函数名是相应的非终结符 函数体则是根据规则右部符号串的结构和顺序编写 A 1 2 n i VT i VN 1 2 n 递归下降分析法 1 当遇到终结符a时 则编写语句 if 当前读来的输入符号 a 读下一个输入符号 2 当遇到非终结符A时 则编写语句调用A 4 当某个非终结符的规则有多个候选式时 按LL 1 文法的条件能唯一地选择一个候选式进行推导 3 当遇到规则A 时 则编写语句 递归下降分析法 if 当前读来的输入符号 FOLLOW A error E E T TT T F FF E id 例设有文法G E 试构造一个识别该文法句子的递归下降分析程序 递归下降分析法 分析首先消去文法左递归 得到文法G E E TE E TE T FT T FT F E id E E T TT T F FF E id 递归下降分析法 经过验证 文法G E 是LL 1 文法 递归下降分析法 分析程序中定义两个函数 1 函数GetSym 功能 读进源程序的下一个单词符号并将它放在全程变量sym 2 函数error 功能 出错处理程序 递归下降分析法 对文法G E 可写出相应的递归下降分析程序如下 E TE E TE T FT T FT F E id main GetSym E if sym printf success elseprintf fail 递归下降分析法 E T E E if sym GetSym T E elseif sym 递归下降分析法 E TE E TE T FT T FT F E id T F T E TE E TE T FT T FT F E id T if sym GetSym F T elseif sym follow T error 递归下降分析法 练习 编写T F if sym id GetSym elseif sym GetSym E if sym GetSym elseerror elseerror E TE E TE T FT T FT F E id 递归下降分析法 递归下降分析法 main GetSym E if sym printf success elseprintf fail id id E T E T F T 见F 见E 见T 返回下一页 F if sym id GetSym elseif sym GetSym E if sym GetSym elseerror elseerror 递归下降分析法 返回T 递归下降分析法 T if sym GetSym F T elseif sym follow T error follow T 返回T 递归下降分析法 E if sym GetSym T E elseif sym 返回E 见T 返回E 对这个例子 若采用扩充的BNF表示法改写文法 得到G E E T T T F F F E id 递归下降分析法 E E T TT T F FF E id 该文法是LL 1 文法 其递归下降分析程序中主函数和函数F 同上 对函数E 和函数T 用while语句描述如下 递归下降分析法 E T while sym GetSym T T F while sym GetSym F E T T T F F F E id