语法与语义分析剖析课件.ppt

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

1、(四)语法与语义分析常用的终结符号集自顶向下分析自底向上分析虚拟机递归子程序方法逆波兰表达式1语法与语义分析1.编译程序逻辑图表格管理错误处理源程序词法分析语法分析中间代码生成中间代码优化目标代码生成目标程序2一、常用的终结符号集文法定义：文法G是一个四元组，G=（VT，VN，S，P），其中VT为终结符号集，这是个非空有限集。VN为非终结符号集合，它也是非空有限集。S为一文法开始符，是一个特殊的非终结符。SVNP是产生式的非空有限集，其中每个产生式（或称规则）是一序偶（U，x）通常写作U——〉x或U::=x;——

2、〉（或::=）意为“由……组成”或“产生”；字汇表:V=(VTVN)VTVN=31、首符号集定义：设有文法G=（VT，VN，S，P），字汇表为V，则符号串的首符号集定义为First（）={

3、y，VT，yV*}特别，若为空串，则有First（）=例如：文法：G=({i，+，*，(，)}，{T，E，F}，E，P)一、常用的终结符号集（续一）*4P：E::=E+T

4、TT::=T*F

5、FF::=i

6、(E)则First（E）={i,(};First(T*F)={I,(};First((i))=

7、{(};First(i+i)={i};一、常用的终结符号集（续二）52、向前看集定义：设有文法G=（VT，VN，S，P），非终结符号U的向前看集定义为Follow（U）={a

8、S…Ua…,aVTU{#}}#:非终结符号U后面的符号串为空,则将U后的符号记作特殊符号#;Follow(U)={所有含有U的句型中紧跟U之后的终结符}U{#}例如：文法：G=({i，+，*，(，)}，{T，E，F}，E，P)一、常用的终结符号集（续三）*6P：E::=E+T

9、TT::=T*F

10、FF::=i

11、(E)则因:EE;EE+T;E

12、(E)Follow（E）={#,+,)};一、常用的终结符号集（续四）***7P：E::=E+T

13、TT::=T*F

14、FF::=i

15、(E)则因:EF;ET*F+T;EF*F;E(F)Follow（E）={#,+,*,)};一、常用的终结符号集（续五）****8一、常用的终结符号集（续六）3、可选集定义：设有文法G=（VT，VN，S，P），规则P中A=::a,则该规则的可选集定义为:First(a),当a不为空Follow(A),当a为空Select(A=::a)=9一、常用的终结符号集（续七）例如：

16、文法：G=(a,b,c,d,}，{S,B},S,P)其中P:S=::aBc

17、bBB=::bB

18、d

19、Select(S=::aBc)=First(aBc)={a}Select(S=::bB)=First(bB)={b}Select(B=::bB)=First(bB)={b}Select(B=::d)=First(d)={d}Select(B=::)=Follow(B)={c,#,}10二、自顶向下分析自顶向下分析的思路：对于文法G=（VT，VN，S，P），待分析的句子（符号串）a，分析思路就是从S出发，试图推导出

20、符号串a.从推导角度看，分析思路即为从文法的开始符开始根据规则试图建立一个推导序列，若得到所给的字符串则字符串得到识别，其结构符合文法，否则不符合文法。（参见第二章）11二、自顶向下分析（续一）例：文法：G=({i，+，-，/，*，(，)}，{T，E，F}，E，P)P：E::=T

21、E+T

22、E-T(1)T::=F

23、T*F

24、T/F(2)F::=i

25、(E)(3)分析句子(i+i)-i是否符合文法：符合文法EE-TE-FE-iT-iF-i(E)-i(E+T)-i(E+F)-i(E+i)-i(T+i)-i

26、(F+i)-i(i+i)-i12二、自顶向下分析（续二）自顶向下分析的难点：如果规则中含有一条或者多条类似（1）的规则，则在推导过程中很难确定到底选用那一条规则，如果采用遍历全部规则的方法则最明显的缺点就是效率低。E::=T1

27、T2

28、T3

29、T4

30、…...

31、Tn(1)13二、自顶向下分析（续二）难点解决：候选式：如有规则A::=T1

32、T2

33、T3

34、T4

35、…...

36、Tn，则Ti称为A的后选式。思路：通过当前的输入字符a来决定对后选式的选择。First(),当不为空Follow(A),当为空Select(A=

37、::)=方法：1、首先对文法的每个规则A=::求可选集。14二、自顶向下分析（续三）3、如果非终结符有n个后选式，即A::=T1

38、T2

39、T3

40、T4

41、…...

42、Tn，则要分（I）(II)两种情况：(I)首符号不相同对于文法中有规则A::=T1

43、T2

44、T3

45、T4

46、…...

47、Tn，若n个后选式的首符号均不相同即First(Ti)First(Tj)=(ij