编译原理演示文稿2.ppt

《编译原理演示文稿2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章文法和语言2.1文法的基本概念一个程序设计语言是一个记号系统，如自然语言一样，它的完整的定义应包括语法和语义两方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序，目前在程序设计语言的识别中广泛使用的是上下文无关的文法。在这理主要介绍文法和语言的概念。例：设有文法：<句子>→<主语><谓语><主语>→<冠词><形容词><名词><冠词>→the<形容词>→big<谓语>→<动词><直接宾语><动词>→ate

2、caught<直接宾语>→<冠词><名词><名词>→mouse

3、cat则：<句子>=><主语

4、><谓语>=><冠词><形容词><名词><谓语>=>the<形容词><名词><谓语>=>thebig<名词><谓语>=>thebigcat<谓语>=>thebigcat<动词><直接宾语>=>thebigcatate<直接宾语>=>thebigcatate<冠词><名词>=>thebigcatatethe<名词>=>thebigcatatethemouse2.1.1符号和符号串定义2.1字母表是有穷非空集合。用Σ表示。例：无符号二进制数的字母表为{0，1}C语言的字母表为字母、数字和若干专用符号组成的符号集定义2.2符号

5、串是由字母表中的符号组成的有穷序列，又称字符串、串。例：a,b,c,ba,bbac,caacb,···等都是字母表{a,b,c}上的符号串定义2.3不包含任何字符串的空符号串用ε表示定义2.4符号串x的长度，即符号串x中的字符用

6、x

7、表示(读作x的长度)例：

8、abc

9、=3

10、a

11、=1

12、ε

13、=0定义2.5设非空符号串u=xvy,其中v≠ε,则称v为u的子串,若

14、u

15、>

16、v

17、则称v为u的真子串定义2.6如果z=xy是一个符号串，则x是z和头，而y是z的尾。如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。例：设z

18、=abc，那么z的头是ε,a，ab，abc。除abc外，其它都是固有头。z的尾是ε,c，bc，abc。z的固有尾是ε,c，bc定义2.7设x、y是同一字母表上的两个符号串，把y的符号写在X的符号之后得到的符号串，称为的连接。记为xy例：x=ab，y=wabu则z=xy=abywabu显然：

19、x

20、+

21、y

22、=

23、z

24、εx=xε=x定义2.8设x是符号串，把x自身连接n次得到符号串z,即z=xx···xx(n个x)，称为符号串x的方幂,记为z=xn例：x0=εx1=xx2=xxx3=xxx···定义2.9符号串集合若集合A中的一

25、切元素都是其字母表上的符号串，则称A为该字母表上的符号串集合。注意：ε、{ε}和Φ（表示空集）的区别定义2.10两个符号串集合A和B的乘积AB定义为：AB={xy

26、x∈A且y∈B}例：设A={a,bc}，B=｛b,c,da｝则集合AB={ab,ac,ada,bcb,bcc,bcda｝。注意：由于εx=xε=x因此{ε}A=A{ε}=A，但ΦA=AΦ=Φ则：A0={ε}A1=AA2=AAAn=An-1A=AAn-1（n>0）显然：Σ1是字母表中的所有单个字符组成的字符串Σ2是所有由字母表中二个的字符组成的字符串Σ3是所有由

27、字母表中三个的字符组成的字符串Σn是所有由字母表中长度为n的字符串集合定义2.11A的闭包A*=A0∪A1∪A2∪···A的正闭包A+=A1∪A2∪A3∪···显然A+=AA*=A*AA*=A0∪A+由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上的某些符号串的集合，因此，某个字母表上的语言是这个字母表上的正闭包的子集，而且通常是真子集。例：若Σ={0,1},则Σ*=｛ε,0,1，00,01，10,11,000，001，010,···｝例：令L={A,B,C,···,Z,a,b,··

28、·,z},D={0,1,···9}1.L∪D2.LD3.L44.L(L∪D)*5.D+6.D+∪L*则分别代表什么集合？1.字母或数字（包括ε）的集合2.由字母开头后面跟一个数字的集合3.由４个字母组成的字符串的集合4.由字母开头后面是字母数字（可省略）的集合5.数字串集合6.数字串和字母串集合（包括ε）约定：当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，可以采用省略写法：z=x···；如果只是为了强调x在符号串z中的某处出现，则可表示为:z=···x···；如果只是为了强调x在符号串z中的末尾出现，则可表示为:z

29、=···x；2.1.2文法和语言的形式定义语言是字母表上的某些符号串集合，在这集合中的每个符号串都是按一定规则生成的。其规则最常用的是重写规则（又称产生式或生成式），它是形如α→β或α：：=β（α，β）的有序对，（读作α定义为β），其中α称为规则的左部，β称为规则的右部。定义2.12文法G定义为四元组（Vn,Vt，P