语法和语义分析课件.ppt

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

1、第6章语法和语义分析6.1常用的终结符号集6.2句子的分析6.3虚拟机6.4递归子程序方法6.5LL(k)分析方法6.6运算符优先数法6.7状态矩阵法语法分析是编译程序的核心部分，其主要任务是：根据语法规则逐一分析词法分析时得到的属性字，检查语法错误，若没有错误，则给出正确的语法结构。简单地说，就是确定语法结构，检查语法错误。语义分析的主要任务是，根据语法结构分析其含义，并用某种机器内部表示形式表示出来，或者直接生成目标指令。简单地说，就是分析语法结构含义，表示成中间语言或生成目标指令。语法分析的方法归结起来可分成两大类：自顶向下的分析方法和自底向上的分析方法。6.1常用的终结符号集为了

2、讨论各种语法分析方法，我们定义三种终结符号集：首符号集：First；向前看集：Follow；可选集：Select；1.首符号集定义：设有文法G[S]，字汇表为V，则符号串β的首符号集的定义为：First(β)={a

3、βay,a∈Vt,y∈V*}*特别地，若β为空串ε，则有First(β)=φ补充First集的计算：1).若XVt，则First(X)={X}；2).若XVn，且有产生式Xa…，则a∈First(X);若X也是一条产生式，则∈First(X)。调用返回例如：设有表达式文法G[E]:E::=E+T

4、TT::=T*F

5、FF::=(E)

6、i3).若XY…是一个产

7、生式，且YVn，则把First(Y)中的所有非元素都加到First(X)中；若XY1Y2…Yi是一个产生式，Y1,Y2,…,Y(i-1)都是非终结符，而且，对于任何j，1≤j≤i-1,First(Yj)都含有(即Y1..Y(i-1)),则把First(Yj)中的所有非元素都加到First(X)中；特别是，若所有的First(Yj),j=1,2,..,i均含有，则把加到First(X)中。+ETF(E)ETFi则有：First(E)={(,i}First(T*F)={(,i}First(i+i)={i}S→ABS→bCA→εA→bB→εB→aDC→AD

8、C→bD→aSD→c又例如，有如下的文法：则可求的First集如下：First(S)=(First(A)-{ε})∪(First(B)-{ε})∪{ε}∪{b}={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}First(AB)={a,b,ε}First(AD)={a,b,c}2.向前看集定义:设G=(Vt,Vn,S,P)是上下文无关文法，A∈Vn,S是开始符号。若紧跟在非终结符号U后的符号串为空时,则视U后面的符号为特殊符号“#”。由此可见，U的向前看集就是由所有含有U的Follow(U)=

9、{a

10、S…Ua…，a∈Vt∪{#}}*设有文法G[S]，非终结符号U的向前看集定义为:Follow(A)={a

11、SA且a∈First(),∈Vt*,∈V+}若SA,且ε,则规定#∈Follow(A)。***也可如下定义：调用返回例:设有表达式文法G[E]:E→E+T

12、TT→T*F

13、FF→(E)

14、i句型中紧跟在U之后的终结符号或“#”所组成的集合。∵EEEE+TE(E)故Follow(E)={#,+,)}***又∵ET,ET*T,E(T),ET+T故T的Follow(T)={#,+,*,)}同理F的Follow(F)={#,+,*,)}****

15、补充：Follow(A)集的计算1).对于文法的开始符号A,置#于Follow(A)中;2).若有产生式B→αAaβ,a是终结符，则把a加至Follow(A)中;4).若有产生式B→αA,或B→αAβ,但βε,则把Follow(B)加至Follow(A)中;*3).若有产生式B→αAXβ,X是非终结符，则把First(Xβ)加至Follow(A)中;S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c例如：∵D::=aS∴Follow(S)={#}∪Follow(D)Follow(A)={a}∪{a,c}∪Follow(S)Follow(B)=Follo

16、w(S)Follow(C)=Follow(S)Follow(D)=Follow(B)∪Follow(C)Follow(S)={#}Follow(A)={a,c,#}Follow(B)={#}Follow(C)={#}Follow(D)={#}Select(A→β)=First(β)当β不为空ε3.可选集:定义:设有文法G[S],并有规则A→β,则该规则的可选集定义为:Follow(A)当β为空ε例:设有文法G[S]:S→