语法分析和语法分析

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

1、编译原理第四章语法分析及语法分析程序东华大学计算机学院本章内容自顶向下分析和自底向上分析围绕分析器的自动生成展开东华大学计算机学院难重点语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。东华大学计算机学院自顶向下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自底向上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。东华大学

2、计算机学院自底向上的语法分析例：文法G：S→cAdA→abA→a识别输入串w=cabd是否是该文法的句子SAAcabdcabdcabd关键：句柄的确定东华大学计算机学院自顶向下分析的语法分析例：文法SaCbCcd

3、c为输入串w=acb建立分析树SSSaCbaaCCbbcdc试探的过程问题：会产生回溯东华大学计算机学院自顶向下分析法的另一问题若有文法G6[S]:(1)S→Sa(2)S→b推导baa#问题：左递归SbSSaSSabSSaSaSSaSab东华大学计算机学院自顶向下分析法需要解决的问题左递归对文法进

4、行改造回溯如何唯一地确定所采用的产生式？－LL(1)文法当拒绝w时,只能知道w不是句子,不知出何错及出在何处东华大学计算机学院本节将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文法满足LL(1)文法。本节主要介绍内容为：◇LL(1)文法的定义和判别◇非LL(1)文法的等价变换◇确定的自顶向下分析方法◇递归子程序法◇预测分析方法东华大学计算机学院4.1自顶向下的语法分析消除文法的左递归带回溯的递归子程序回溯的消除及LL(1)文法东华大学计算机学院4.1.1消除文法的左递归例：AA

5、A的

6、解是：*引入新的非终结符A’,令其产生*,则有:AA’A’A’

7、对于AA1

8、A2

9、…

10、An

11、1

12、…

13、m消除直接左递归A1A’

14、…

15、mA’及A’1A’

16、…

17、nA’

18、东华大学计算机学院消除文法左递归的矩阵方法设文法的非终结符为X1,X2,…,Xn,Xi的产生式分为以VN符和VT符打头的两类.将‘

19、’改写为‘+’,有Xi=X11i+X22i+…+Xnni+i其中,i是以VT符打头的产生式之和,ki可以为这样,文法G可表示为X=XA+B。东华大学计算机学院消除文法左递

20、归的矩阵方法该方程有解:X=BA*为得到A*,由于则有:X=BZ，Z=I+AZ其中X的产生式以VT符打头,而Z的产生式以ijV*打头,因此将不含左递归.注意,由此所得的文法含有无用符号和无用产生式,需化简东华大学计算机学院消除文法左递归的例子例4.1SSa

21、Ab

22、aASc相应的矩阵为展开矩阵,得SaZ11AaZ12Z11aZ11

23、cZ21

24、Z12aZ12

25、cZ22Z21bZ11Z22

26、bZ12消除文法中无用产生式SaZ11Z11aZ11

27、cZ21

28、Z21bZ11东华大学计算机学院消除

29、回溯的条件候选式的终结首符集FIRST()={a

30、*a,aVT,V*}*时,FIRST()若A-产生式的各候选式i(i=1,2,…,m)都推不出，且FIRST(i)互不相交，则当扫描当前输入符号aiFIRST(j)时,唯一可用于推导的产生式只能是Aj。东华大学计算机学院消除回溯的条件例如,文法G1[S]:SAAAaAb

31、*,A-产生式有两个候选式,两集不相交FIRST(aAb)={a}FIRST(*)={*}设输入串为aa*bb*,最左推导SAA(a)aAbA(a)

32、aaAbbA(*)aa*bbA(*)aa*bb*(#)无回溯的条件:FIRST(i)FIRST(j)=东华大学计算机学院消除回溯的条件存在某候选式i,i*,即FIRST(i),有两种选择匹配当前扫描符号a：存在某j,使j推导出以a打头的符号串选择i,让跟随在后的符号串推导出以a打头的符号串。东华大学计算机学院消除回溯的条件若两种选择都可行,则回溯不可避免。因此,要求当i*时,跟在后的符号串不能推导出其它j所能推导出的首终结符符号串。定义：A后的所有终结符之集FOLLOW(

33、A)={a

34、S#*Aa,aVT{#},,V*}当A为一句型的尾符号时,#FOLLOW(A)。东华大学计算机学院消除回溯的条件无回溯的条件为:若i*,则FOLLOW(A)与其它j互不相交FOLLOW(A)FIRST(j)=.东华大学计算机学院First&Follow文法为：0）S→MH1）S→a2）H→LSo3）H→ε4）K→