编译原理第三版第五章自下而上语法分析课件.ppt

,第5章语法分析一自下而上分析本章要点自下而上分析方法概述算符优先分析方法LR分析方法语法分析器的自动生成,51自下而上语法分析概述语法分析的任务:按文法的产生式分析输入串(单词串)是否是句子。语法分析的方法自上而下分析法开始符号S多输入串a(推导)自下而上分析法输入串开始符号S(归约),1、归约与分析树(1)移进-归约法:使用符号栈,把输入符号逐一移进栈,栈顶出现某个产生式右部时归约为左部例:给定文法G(1)S aacBe2)Ab3)AAb(4)Bd输入串 abbcde是否为句子?归约过程如下:3.4.5.6.7.8.9.10.动作:进涉进图进进进田d BBAAA,(2)分析树:用树表示“移进一归约”过程这是一个自下而上地构造树的过程,故称为自下而上语法分析。关键何时归约:一旦栈顶出现可归约串,就立即进行归约。(最左归约、规范归约)找到构成产生式右部的符号串(即可归约串)。,2、规范归约简述定义短语:对于文法G(S),设aB是一个句型,若有SaA8且A,则称是句型aB6关于非终结符A的短语。例:设文法G(S):(1)S aAcBe(2)A_b(3)AAb(4)Bd给出句型 aBode的短语。由S= aAcBe= aAcde= abode,因为S= aacde a=Ab所以Ab是短语;,