语法分析(课件)

《语法分析(课件)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、语法分析一IT顶向下分析第四章语法分析自顶向下分析(P61)4.1自顶向下分析方法4.2FIRST集合和集合和FOLLOW集合集合和集合4.3递归下降分析4.4LL(1)分析方法分析方法学习重点FIRST集合和集合和FOLLOW集合的求法集合和集合的求法递归子程序的构造方法LL(1)文法及其分析表的构造方法文法及其分析表的构造方法语法分析一IT顶向下分析第四章语法分析自顶向下分析语法：语法：是指如何由语言基本符号组成程序中各个语法成分（包描程序）的一组规则。成分（包括程序）的一组规则。语法分析任务：检查源程序语法上是否正确，语法分析任务：检查源程序语法上是否正确，并生成相应的内部表示（如分析树

2、）供下一阶段使用。相应的内部表示（如分析树）供卜•一阶段使用。语法分析与词法分析的区别：语法分析与词法分析的区别：语法分析和词法分析都是对输入符号串的识别,语法分析和词法分析都是对输入符号串的识别，但词法分析的输入符号串是一个单词，但词法分析的输入符号串是一个单词，而语法分析的输入符号串是一个句子或者说是一个程序。的输入符号串是一个句子或者说是一个程序。对于c程序语句程序语句“例对于程序语句“if（a<10）b=5；”，词法分析识；别出了if、、、等单词符号等单词符号，别出了、（、a、...等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确，例如if后面是否这些单词之间的搭配

3、、结构是占正确，例如后面是否后面是否为正确的表达式等等。为（，（后面是否为正确的表达式等等。，后面是否为正确的表达式等等语法分析方法的分类(语法分析方法的分类(分类标准是按照识别句语法分析一自顶向下分析笫四章语法分析)：自顶向下分析子时建立语法树的方法)：子吋建立语法树的方法？？？自顶向下？？？？？？？？自底向上????????不带回溯？？？带回溯？？优先分析法??????LR分析法？？？？LL(K)分析法7??递归卜•降分析法7?简单优先分析法？？算符优先分析法？LR(O)分析法V??SLR(1)分析法？？LR(1)分析法？LALR(1)分析法？语法分析回溯示例4.1自顶向下的分析方法(P6

4、1)自顶向下的分析方法P61)自顶向下的分析方法就是从文法的开始符号出发，自顶向下的分析方法就是从文法的开始符号出发，就是从文法的开始符号出发按最左推导方式向下推导，试图推导出要分析的输按最左推导方式向下推导，入串。入串。即：+输入符号串开始符号？自底向上的分析方法从输入符号串开始，口底向上的分析方法从输入符号串开始,按最左从输入符号串开始归约方式向上归约到文法的开始符号。归约方式向上归约到文法的开始符号。即：开始符号归约输入符号串<—输入串图示：图示:下分析与自底向上分析自上而下开始符号自底向上S?aAS?aAa?aSbAa?aSbbaa?aabbaa?????4.2FIRST集合和集合和F

5、OLLOW集合(P62)集合和集合P62)FIRST集合定义：集合定义：集合定义假定(X是文法的任一符号串，是文法G的任一符号串假定是文法的任一符号串，贝U：FIRST(a)={a

6、a*,a^Vt}a...,丘?*8,则规定ee若a?则规定GFIRST(a)。。实际上，就是从a口J能推导出的所有开实际上，FIRST(a)就是从可能推导出的所有开就是从头终结符号或肌头终结符号或。文法符号的FIRST集合构造方法：集合构造方法：文法符号的集合构造方法对于文法中的符号e,符号集合可反复对于文法中的符号XGV,其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为应用下列规

7、则计算，直到其集合不再增大为止：1)若Xevt,则若e,贝ijFIRST(X)={X}o。,,均为非终结符则将FIRST(Yi)中的一；但若对一切IMSk,e,则将s符号加进。2)若Xevn,且具有形如若e,且具有形如X—aoi的产生式evt),或的产生式(ae,或的产生式具冇形如X->w的产生式，则把或w加进的产生式，则把a或加进加进FIRST(X)。具有形如的产生式，则把o3)设G中有形如设中有形如中有形如X—Y1Y2…Yk的产生式，若YieVn,的产生式，则把FIRST(Yl)中的一切非符号加进中的一切非£符号加进则把中的一切非符号加进FIRST(X)；对于；一切2

8、,Yi・l均为非终结符号，且一切号，8GFIRST(Yj),l