《编译原理课程教案》第4章：自上而下语法分析

《《编译原理课程教案》第4章：自上而下语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自上而下语法分析方法第四章（1）本章要求主要内容：语法分析的任务和设计，自上而下语法分析方法及其相关概念，Sample语言语法分析程序的设计重点掌握：语法分析的任务和接口设计，自顶向下语法分析面临的问题及解决方法，掌握First集和Follow集的概念和求解方法，掌握LL(1)文法的判定方法，能够使用递归下降分析方法和预测分析方法实现编写语法分析器，并对一个输入串进行分析。高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程

2、序的语法结构是否符合语法规则。4.1语法分析的任务问题：在上一章词法分析中讲解了如何判断源程序中单词的正确性，并输出了正确的单词符号。那么如何知道这些正确的单词是否能构成正确的表达式、语句或程序呢？这就是语法分析的任务。语法分析的任务在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析在编译系统中所处的位置语法分析器的输入Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列语法分析器的输出分析树：表示方法？见教材P89错误处理信息：定位、继续编译4.2语法分析的接口设

3、计语法分析器的功能按照语言的语法构成规则,识别输入的符号串能否构成一个句子。这些规则是用文法的产生式来定义的。问题对给定的一个输入串，如何判定它是不是一个句子？方法根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。G=({E},{i,+,*,(,)},P,E)P：EE+EEE*EE(E)Ei解：使用最左推导：EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i例：判定输入串(i+i)*i是否是下述文法的句子？结论：能够从开始符号出发

4、推导出给定的输入串，因此，是句子。常用的语法分析方法：自顶向下分析法：从文法的开始符号出发，向下推导(使用最左推导)，尽可能使用各种产生式，推导出与输入串匹配的句子，从而建立语法树。自底向上分析法：从输入符号串开始，逐步进行归约(最右推导的逆过程)，直至归约到文法的开始符号，从而建立语法树。具体分类：自顶向下分析递归下降分析预测分析(LL)自底向上分析算符优先分析LR分析4.3自顶向下语法分析及面临的问题自上而下分析主要是：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。从推导的角度看，从开始

5、符号出发，使用最左推导，试图推导出与输入符号串相同的句子。从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。需要反复试探。例1：设有文法(1)SxAy(2)A**

6、*现有输入串：x*y其分析过程如右：SxAy**失败，需要退回，重新选取A的侯选式，这时使得分析器的动作不稳定思考：产生回溯的原因？x*y输入符号串：问题1：回溯(P67)真正原因是：文法的产生式有问题。左递归：文法中存在某个AVn，有AA。直接左递归：有产生式AA间接左递归：例2：

7、设有文法G(E)：(1)EE+T

8、T(2)TT*F

9、F(3)F(E)

10、i现有输入串i*i+i,分析过程是：EE+TE+TE+T…失败：对左递归文法使用最左推导，出现死循环。思考：产生左递归的原因？问题2：左递归(P68)真正原因是：文法的产生式有问题。结论1.左递归和回溯问题的产生直接与描述语言的文法有关2.应该改造文法，使其不含左递归和回溯，才能进行确定的自顶向下分析4.3问题的解决方法消除左递归消除回溯消除左递归1.直接左递归的消除P69：假定产生式为：P→Pα

11、β，将其替换为形式等价的产生式组：例2：文法EE+T

12、TTT

13、*F

14、FF(E)

15、i消去左递归后为：TFT'T'*FT'

16、εP→βP'P'→αP'｜εETE'E'+TE'

17、εF(E)

18、i一般而言，若产生式形式为：A→Aα1

19、Aα2

20、…

21、Aαn

22、β1

23、β2

24、…

25、βm将其替换为：Aβ1B

26、β2B

27、…

28、βmBBα1B

29、α2B

30、…

31、αnB

32、ε练习消去文法G[S]的左递归S(T)

33、a+S

34、aTT,S

35、SS(T)

36、a+S

37、aTST'T’,ST'

38、ε答案：例：给定间接左递归文法，请消除左递归(1)代入(2)消除直接左递归SQc

39、cQRb

40、bRSa

41、a解：第1步：为R、S、Q排序第2

42、步：代入：将R代入Q,Q代入S，得到新的文法产生式组：RSa

43、aQSab

44、ab

45、bSSabc

46、abc

47、bc

48、c第3步：消去S的直接左递归，得到SabcS'

49、bcS'

50、cS'S'abcS'

51、ε2.间