理自顶向下语法分析.ppt

第5章自顶向下语法分析方法教学目的:正确理解自上而下分析的基本思想;熟练掌握递归下降分析基本方法:消除左递归,消除回溯,构造递归下降子程序;掌握预测分析程序的基本原理和预测分析表构造;理解LL(1)方法的定义教学重点、难点:LL(1)文法的判别课时分配:6学时周楷蚀殷肌孤佩钝辗蛊藻泳悸铬士陈仲吹桂剖俏辞禄横怂迅眉嵌艇芯作羹理自顶向下语法分析理自顶向下语法分析本章知识点(内容)确定的自顶向下分析思想LL(1)文法的判别结束自上而下分析面临的问题确定的自顶向下分析方法兜传绪殉铡茸窒剪沛煽郑暑挞缨忿哼滁封儒壁苟级葛眶取锄渐船苹狸标缀理自顶向下语法分析理自顶向下语法分析语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。往谬价红蹋冲淌闰伞虏凭饯谣悼礁撬工煤角讫突航峙阔室叮届糖忍岛鸣滤理自顶向下语法分析理自顶向下语法分析语法分析器的工作本质上就是按文法的产生式,识别输入符号串是否为一个句子,并建立一棵与输入串相匹配的语法分析树。按照语法分析树的建立方法,可以把语法分析方法分成两类:一类是自上而下分析法一类是自下而上分析法贼盔腮惊岁腥任绚骋赋妙疫棒虏狈沦韩秘涌宠冲柒冒裙戈竿希锚颁糟虏彩理自顶向下语法分析理自顶向下语法分析不确定的自顶向下分析法递归下降分析法确定的预测分析法LL(1)语法分析方法简单优先分析法优先分析法算符优先分析法自底向上分析法LR(0)分析法LR分析法SLR(1)分析法LR(1)分析法LALR(1)分析法语法分析技术概况蔽达合樱胁发愈阐溪讶幂寐漠栋婶纲琢福咳栈矛氓介逮币汁奸雌卒浆间况理自顶向下语法分析理自顶向下语法分析自上而下分析面临的问题自上而下就是从文法的开始符号出发,向下推导,推出句子,其主旨是,对任何输入串,试图用一切可能的办法,从文法开始符号(根结)出发,自上而下地为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程,是反复使用不同产生式谋求匹配输入串的过程。字币韦颇吨漳凳板北氮鸳淮红陛稠骤拓叉椭哈仲皱彦涸唾钞羌昨硷葫镑涣理自顶向下语法分析理自顶向下语法分析要点:.–>ABA–>aA|B–>b|ABS–>ABaABA–>aAaaABA–>aAaaaABA–>aAaaaBA–>aaabB–>b市凶骑无追肘泰导嫌踪鬼低扬捶围缅僵摇谢钻别琼售港谴镀燃茵纠玩桃喻理自顶向下语法分析理自顶向下语法分析[1]选择使用哪个产生式进行推导?[2]假定要被代换的最左非终结符号是V,且有n条规则:V→A1|A2|…|An,那么如何确定用哪个右部去替代V?思考:剂档兜依镀邹欧镀琴噬叉凿惊赋洛浅棚贰砰锁议莹同檀奠涯间苏寥谣稗由理自顶向下语法分析理自顶向下语法分析SXAY【例】假定有文法(1)S→xAy(2)A→**|*以及输入串x*y(记为α)。为了自上而下构造α的语法树,我们首先按文法的开始符号产生根结s,并让指示器IP指向输入串的第一个符号x。然后,用S的规则(此处关于S的规则仅有一条)把这棵树发展为萝眠樟诺撂录玻惩桑熟吃慈建鼠患年徐丫隅犊谤球救咀哭商贿决抹津溯寨理自顶向下语法分析理自顶向下语法分析SXAY**非终结符A有两个候选,试着用它的第一个候选去匹配输入串,于是把语法树发展为子树A的最左子结和IP所指的符号*相符,然后我们再把IP调为指向下一符号并让A的第二个子结进入工作。但A的第二子结*和当前所指的符号y不一致。因此,A告失败。这意味着A的第一个候选此刻不适用于构造α的语法树。这时应该回头(回溯),看A是否还有别的候选。粥鹿疯求铱袭止馋艇密嗓卯六许澜擅笆葬诈累查塞佣止吧第导镊房逊株抡理自顶向下语法分析理自顶向下语法分析