编译原理第五章.ppt

《编译原理第五章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理第五章语法分析——自下而上分析第五章语法分析——自下而上分析自上而下分析法(Top-down)自下而上分析法(Bottom-up)南昌航空大学大学计算机应用系语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。南昌航空大学大学

2、计算机应用系语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约南昌航空大学大学计算机应用系G(E)：Ei

3、E+E

4、E-E

5、E*E

6、E/E

7、(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE南昌航空大学大学计算机应用系5.1.1归约采用“移进－归约”思想进行自

8、下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。南昌航空大学大学计算机应用系例：设文法G(S)：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进－归约”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae南昌航空大学大学计算机应用系南昌航空大学大学计算机应用系bdbaceSABA分析树和语法树不一定一致。自下

9、而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串南昌航空大学大学计算机应用系5.1.2规范归约定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有且则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。南昌航空大学大学计算机应用系考虑文法G(E)：ET

10、E+TTF

11、T*FF(E)

12、i和句型i1*i2+i3：EE+TE+FE+i3T+i3T*F+i3T*i2+i3F*i2+i3

13、i1*i2+i3短语：i1，i2，i3，i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i1南昌航空大学大学计算机应用系在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i2南昌航空大学大学计算机应用系可用句柄来对句子进行归约句型归约规则abbcde(2)AbaAbcde(3)AAbaAcde(4)BdaAcBe(1)SaAcBeS南昌航空大学大学计算机应用系定义：假定是

14、文法G的一个句子，我们称序列n，n-1，，0是的一个规范归约，如果此序列满足：1n=20为文法的开始符号，即0=S3对任何i，0in，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。南昌航空大学大学计算机应用系把上例倒过来写，则得到：SaAcBeaAcdeaAbcdeabbcde显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。南昌航空大学大学计算机应用系bdbaceSABAdbaceSABAdaceSABaceSABS南昌航空大

15、学大学计算机应用系5.1.3符号栈的使用和分析树的表示栈是语法分析的一种基本数据结构。’#’作为栈底符号考虑文法G(E)：ET

16、E+TTF

17、T*FF(E)

18、i输入串为i1*i2+i3，分析步骤为：南昌航空大学大学计算机应用系步骤符号栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i3#归，用F→i3#T*i2+i3#归，用T→F4#T*i2+i3#进G(E)：ET

19、E+TTF

20、T*FF(E)

21、i南昌航空大学大学计算机应用系步骤符号栈输入串动作4#T*i2+i3#进5#T*i2+i3#进6

22、#T*F+i3#归，用F→i7#T+i3#归，用T→T*F8#E+i3#归，用E→T9#E+i3#进G(E)：ET

23、E+TTF

24、T*FF(E)

25、i南昌航空大学大学计算机应用系步骤符号栈输入串动作9#E+i3#进10#E+i3#进11#E+F#归，用F→i12#E+T#归