实验2递归下降语法分析.ppt

Zhou, Erqiang 编译技术实验(2) 递归下降语法分析 周尔强 2015年10月 exp: factor | exp + factor | exp - factor ; factor: term | factor * term | factor / term ; term: NUMBER | - term ; 递归下降分析举例 Zhou, Erqiang * School of Information and Software Engineering exp: factor | exp + factor | exp - factor ; 递归下降分析举例 Zhou, Erqiang * School of Information and Software Engineering 语言：factor +/- factor +/- factor ... 程序： void exp(){ factor(); while( tok == + || tok == -){ advance(); factor(); } } +/- factor +/- factor ... 重复出现的部分 factor: term | factor * term | factor / term ; 递归下降分析举例 Zhou, Erqiang * School of Information and Software Engineering 语言：term */ term */ term ... 程序： void factor(){ term(); while( tok == * || tok == /){ advance(); term(); } } */ term */ term ... 重复出现的部分 term: NUMBER | - term ; 递归下降分析举例 Zhou, Erqiang * School of Information and Software Engineering 语言：NUMBER、 - NUMBER - - NUMBER、- - - NUMBER 程序： void term(){ if( tok == NUMBER ); advance(); else if ( tok == -){ advance(); term(); } else error(); } 纯粹的语法分析只分析 词法记号序列是否符合语言的文法 如 -5+20*5-3 实际的编译器 需要找出词法记号序列的结构 即语法树 递归下降分析举例 Zhou, Erqiang * School of Information and Software Engineering exp: factor | exp + factor | exp - factor ; factor: term | factor * term | factor / term ; term: NUMBER | - term ; 递归下降文法举例 Zhou, Erqiang * School of Information and Software Engineering - 5 + 20 * 5 - 3 term term term term factor factor exp term factor exp factor exp 递归下降文法举例 Zhou, Erqiang * School of Information and Software Engineering - 5 + 20 * 5 - 3 term term term term factor factor exp term factor exp factor exp null 5 20 5 - * + 3 - 抽象的语法树 （Abstract Syntax Tree, AST） while b ≠ 0 if a b a := a ? b else b := b ? a return a 抽象语法树 Zhou, Erqiang * School of Information and Software Engineering 抽象语法树结点设计 所有树结点统一为 一个 结构类型 如何区别结点：赋值语句？选择语句？ 结点内需要 用标志位