语法分析和语法分析程序课件.ppt

《语法分析和语法分析程序课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析和语法分析程序自上而下分析自下而上分析分析器的自动生成§4.1前言词法分析器记号取下一个记号源程序分析树前端的其余部分语法分析器分析树符号表§4.1.1语法与语法分析作用语法作用:语言设计者：提供语言的精确构成，形式化规定语言语法单位组成部分间的关系。语言使用者：使用语言，根据语法来构造合法句子。编译程序设计者：语法是进行编译程序的依据，用来构造识别语言所有句子的语法分析器。语法分析作用：识别由词法分析给出的单词序列是否是给定文法的正确句子（程序）。即根据语言的语法规则分析源程序的语法结构（单词如何构成各种语法范畴）。§4.1.2语法

2、分析的方法句型分析就是识别一个符号串是否为某文法的句型，是某个推导（归约）的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，为待识别句子建立一个最左推导，以寻找与输入符号串匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，从叶子节点，由底上向上逐步建立一棵完整的语法树，直至归约到文法的开始符号（树根）。分析算法分

3、为：§4.2自上而下分析算法一般方法要点：由根向下构造语法树；构造最左推导；推导出的终结符是否与当前输入符匹配？例如：文法G[S]:S–>ABA–>aA

4、B–>bB

5、b判定符号串aaab是否合法.SABaAaAaABSABS–>ABaABA–>aAaaABA–>aAaaaABA–>aAaaaBA–>aaabB–>bb自顶向下分析一般方法特点：1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切办法(选用不同规则)设法建立语法树的过程，由于是试探过程

6、，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。3.最左推导可以编出程序来实现，但在实际上价值不大，效率低。自顶向下分析方法的基本缺点：不能处理具有左递归性的文法为什么自顶向下分析不能处理左递归文法？文法G，存在U∈VN，ifU==>U…,则G为左递归文法+1.左递归文法左递归文法回溯问题§4.2.1一般方法面临问题及解决在匹配输入串过程中，如果当前需要用非终结符U直接匹配输入串，即要用U的右部符号串U¨¨去推导，没有对当前串匹配即进行递归调用，从而陷入死循环。例：G[S]:S→Sa

7、bL={ba

8、n

9、n≥1}W=baaaSbSSaSa如果文法具有间接左递归，则也将发生上述问题。要实行自顶向下分析，必须要消除文法的左递归，不仅消除直接左递归，而且消除间接左递归。直接左递归若P→Pα

10、βα、β∈V*且β不以P开头串的特点βα...α间接左递归若P=>Pα例如：S→AaA→Sb

11、b*2．回溯问题什么是回溯?分析工作要部分地或全部地退回去重做叫回溯。文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。严重的效率低，只有在理论上的意义而无实际意义。U::=aβ1

12、aβ2

13、aβ3造成回溯的条

14、件?回溯带来的问题?1)语法分析要重做2)语法处理工作要推倒重来因此自顶向下的一般分析方法不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低。欲采用此方法，必须：1、消除左递归；2、消除回溯效率低的原因§4.2.2消除文法的左递归产生式方法：改写产生式，使产生式不含左递归。法一：P→Pα

15、β产生式的符号串为βα...α引入一元语言符号｛｝，{x}表示x可出现任意次。则：P→Pα

16、β改写为P→β{α}例1：S→AcA→Aa

17、b改为：S→AcA→b{a}例2：E→E+T

18、TT→T*F

19、F消除左递归：E→T{+T}T

20、→F{*F}1、消除直接左递归法二：对左递归A→Aα

21、β的非终结符A，引入一个新的非终结符A’，使得：A→Aα

22、β等价写成：一般地：若其中βi均不以A打头，则：A→βA’A’→αA’

23、ε规则一（提因子）i)已知U→xy

24、xw

25、…

26、xz解：U→x(y

27、w

28、…

29、z)得：U→xU’U’→y

30、w

31、…

32、z使用提因子法，不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。ii)已知U→x

33、xy解：U→x(y

34、ε)规则二将左递归规则改为右递归规则若：P→P

35、则可改写为：P→P’P’→P’

36、ε例EE+T

37、TTT*F

38、FF(E

39、)

40、id消除左递归后文法ETEE+TE

41、TFTT*FT

42、F(E)

43、id注意：此方法只能消除出现在