《编译原理第二章》ppt课件

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

1、第二章语法描述定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。对文法G(E)：Ei

2、E+E

3、E*E

4、(E)E(E)(E+E)(i+E)(i+i)即表示从0出发，经一步或若干步或者说使用若干次规则可推导出n。2.3.2语言的形式定义如果存在一个直接推导序列：则我们称这个序列是一个从0至n的长度为n的推导，记为2．推导α0α1α2…αn+α0

5、αn2.3.2语言的形式定义设有文法G[E]=({E,T,F},{i,+,*,(,)},P,E)对i+i*i有如下直接推导序列:我们可记为其中P为：E→E+T

6、TT→T*F

7、FF→(E)

8、iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEi+i*i+2.3.2语言的形式定义3．广义推导我们有：0n表示从0出发，经0步或若干步，可推导出n。*也就是说0n意味着0n或者0=n。*+EE*Ei+i*i*对上例E→E+T

9、TT→T*F

10、FF→(E)

11、i2.3.2语言的形式

12、定义区别:直接推导的长度大于等于1，而广义推导的长度大于等于0。2.3.2语言的形式定义4.句型和句子设有文法G[S]（S是文法G的开始符号）如果Sx,x∈(VN∪VT)*则称符号串x为文法G[S]的句型。*如果Sx,x∈VT*则称符号串x为文法G[S]的句子。即：仅含终结符号的句型是一个句子。*2.3.2语言的形式定义例1设有文法G[S]：我们有:显然，符号串01、0S1、00S11和000111都是文法G[S]的句型，而01和000111又是文法G[S]的句子。S→01

13、0S1S01*S0S1*S00S11*S000

14、111*2.3.2语言的形式定义例2设有文法G[E]：试证明符号串(i*i+i)是文法G[E]的一个句子。分析只要证明符号串(i*i+i)对文法G存在一个推导，就可证明符号串(i*i+i)是文法G[E]的一个句子。E→E+E

15、E*E

16、(E)

17、i2.3.2语言的形式定义E→E+E

18、E*E

19、(E)

20、iE(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)即有E(i*i+i),所以符号串(i+i*i)是文法G[E]的一个句子。*（2）L(G)是VT*的子集。即属于VT*的符号串x不一定属于L(G)。2.3

21、.2语言的形式定义5．语言文法G[S]产生的所有句子的集合称为文法G所定义的语言,记为L(G[S])：由语言定义可知：（1）当文法给定，语言也就确定。L(G[S])={x

22、Sx且x∈VT*}*2.3.2语言的形式定义例3设有文法G[S]：S→01

23、0S1求该文法所描述的语言是什么？分析由识别符号S出发，将推出一些什么样的句子，也就是说，L(G[S])将由什么样的一些符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。2.3.2语言的形式定义我们应用第二个规则n－1次，然后再应用第一个规则1次，有：S0S100S11…

24、0n-1S1n-10n1n即S0n1n*可见，此文法定义的语言为L(G[S])={0n1n

25、n≥1}S→01

26、0S12.3.2语言的形式定义例4设有文法G[S]：S→0S

27、1S

28、ε该文法所定义的语言是什么？由该文法所确定的语言为L(G[S])={ε,0,1,00,01,10,11,…}={x

29、x∈{0,1}*}2.3.2语言的形式定义例5设有文法G[A]：该文法所定义的语言是什么？分析从文法开始符号A出发可推导出以y开头后面跟一个或多个x结尾的符号串，所以该文法定义的语言为A→yBB→xB

30、xL(G[A])={yxn

31、n≥1}

32、2.3.2语言的形式定义由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则替换、展开非终结符，找出句子的规律，用式子或自然语言描述出来。2.3.2语言的形式定义形式语言理论可以证明如下两点：(1)给定一种语言，能确定其文法，但这种文法不是唯一的，即：L→G1或G2或…(2)给定一个文法，就能从结构上唯一确定其语言，即：G→L(G)；文法和语言是密切相关的，文法所定义的任一句型和句子,都可以根据文法推导出来。我们提出一个问题：这种推导过程是否唯一？同一个句型(句子)可以通过不同的推导序列推导出来，这是因

33、为在推导过程中与所选择非终结符的次序有关。例如，设有文法G[N1]N1→NN→ND

34、DD→0

35、1

36、2①N1NNDN2D212②N1NNDDD1D12③N1NNDDDD212句子12有下列三种不同的推导序列