编译原理课件chap4

《编译原理课件chap4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析——自上而下分析高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的基础。本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法4.1语法分析器功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。下图表明了语法分析器在编译程序中的地位。第四章语法分析--自上而下分析源程序编译前端中间代码代码优化中间代码代码生成器目标程序符号表代码生成器的位置第四章语法分析--自上而下分析按照语法分析树的建立方法，我们可以粗略地把语法分析方法分为两类：一类是自上而下分析法，另一类为自下而

2、上分析法。4.2自上而下分析面临的问题本节主要是通过例子使我们认识到，作自上而下分析所遇到的主要困难是语法的左递归性使分析陷入无限循环；回溯的不确定性，要求我们将已经完成工作推倒从来，为解决这些问题我们要消除左递归和消除回溯。4.3LL(1)分析法4.3.1左递归的消除一般而言，假定P关于的全部产生式是PP1

3、P2

4、…

5、P1m

6、1

7、2

8、…

9、n其中，每个都不等于，而每个都不以P开头，那末，消除P的直接左递归性就是把这些规则改写成：P

10、1P’

11、2P’

12、…

13、nP’P’1P’

14、2P’

15、…

16、mP’

17、第四章语法分析--自上而下分析直接左递归，和非直接左递归的消

18、除方法均在必须掌握之列。这里我们切不可被形式描述消除左递归的算法吓倒，多做几个例题后再来理解是很有好处的：[例4。3]：考虑文法：SQc

19、cQRb

20、bRSa

21、a消除左递归。解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入到Q中有关的候选式：QSab

22、ab

23、b现在Q同样不含直接左递归，把它带入S的有关候选式：SSabc

24、abc

25、bc

26、c经消除S的直接左递归后我们们得到整个文法SabcS’

27、bcS’

28、cS’S’abcS’

29、QSab

30、ab

31、bRSa

32、a由于关于Q,R的规则式多余的则可化简第四章语法分析--自上而下分析得到：SabcS’

33、bcS’

34、cS’S’a

35、bcS’

36、4.3.2消除回溯、提左因子我们首先来看一下在不得回溯的情况下对于文法有什么要求。前面已经说过，欲实行自上而下的分析，文法不得含左递归。令G是一个不含左递归的文法，对G的所有的非终结符号的每个候选定义它的终结首符集FIRST()为：FIRST()={a

37、*a…,aVT}特别是，若*，则规定FIRST()。换句话说FIRST(）是的所有可能推导的开头终结符或可能的。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同的候选i和jFIRST(i)FIRST(j)=那么，当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确

38、地指派某个候选前去执行任务。这个候选就是那个终结首符集含a的。如何把一个文法改造成任何终结首符集的所有候选首符集两两不相交呢？其办法是提取公共左因子。例如，假定关于A的规则是A1

39、2

40、。。。

41、n

42、1

43、2

44、…

45、m（其中每个不以开头）那末，可以把这些规则改写成：AA’

46、1

47、2

48、…

49、mA’

50、1

51、2

52、…

53、n第四章语法分析--自上而下分析[例]有产生式BbBcA

54、b由于FIRST(bBcA)FIRST(b)={b}则需要提取公共左因子将产生式改写成：BbCCBcA

55、4.3.3LL（1）分析条件假定S是文法G的开始符号，对于任何非终结符A我们定

56、义：FOLLOW(A)={a

57、S*…Aa…,aVT}特别是，若S*…A，则规定#FOLLOW(A).也就是说，FOLLOW(A)是所有举行中出现在紧接A之后的终结符活‘#’。判断某给定文法是否为LL(1)文法其条件为：（1）文法不含左递归。（2）对于文法中每个非终结符A的各个产生式的候选首符集两两不相交。即，若A1

58、2

59、。。。

60、n则：FIRST(i)FIRST(j)=（ij)(3)对文法中每一个终结符A，若它存在某个候选首符集包含，则FIRST(A)FLLOW(A)=一个文法若满足以上条件，责称该文法G为LL(1)文法第四章语法分析--自上而下分析本节特别注

61、意：如果空字ε属于某个非终结符的候选首府集的情况。4.4递归下降分析程序构造当一个文法满足LL(1)条件时，我们就可以构造一个不带回溯的自上而下分析程序，这个分析程序由一组第归过程组成，每个过程对应文法的一个非终结符。这样一个分析程序称为递归下降分析器。在本节中我们对巴科斯范式进行了扩充：（1）用花括号{}表示闭包运算*(2）用{}0n表示可以任意重复0次至n次，{}00=。（3）用方括号[]表示{}01