第2章形式语言概论(新)ppt课件.ppt

《第2章形式语言概论(新)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前述内容回顾·编译程序·编译方式与解释方式的根本区别·编译程序的工作过程·编译程序的结构·编译程序的组织方式·编译程序的构造第二章文法和语言的基本知识本章主要介绍形式语言理论中的一些最基本的概念和基础知识，它是学习以后各章节的基石。本章内容简介·文法的形式定义·语言的形式定义·为语言构造文法与由文法推出语言·语法树及文法的二义性·文法和语言的分类·文法的实用限制形式语言理论由Chomsky于1956年首先提出。是指由数学方法——形式化方法研究自然语言（如英语）和人工语言（如程序设计语言）的语法的理论。目前在自然语言的翻译、计算机语言的描述和转换、编译程序的构造、模式识别等方面有广泛的应

2、用。2.1语言成分的基本概念一个语言的成分包括字母表（Alphabet）,文法（Ｇrammar)以及它的语义。字母表是符号的有穷集，而符号构成了语言中的句子。语法是结构规则的有穷集，这些规则定义了句子中符号的合法上下文。语义通常是操作规则的有穷集，这些规则定义了用该语言编写的任何程序在某个计算机上执行的操作性效果。字母表中的元素称为符号。1.字母表字母表是元素的有穷非空的集合。例如{a，b，……，y，z}，{0，1}等。2.2.1字母表与符号串常用∑来表示。注意：字母表中至少包含一个元素。元素可以是字母、数字或其他符号。字母表中的元素称为符号。符号串是字母表中的符号所组成的任何有穷序列

3、，通常用小写的字母表示。例：∑＝{0,1}则00，11，01，10，010......是符号串。注意：1）不包含任何符号的符号串为空串，记为ε。2）符号串中的符号顺序很重要。ab≠ba3）符号串x中有m个符号，则

4、x

5、=mm是长度。字母表与符号串2.符号、符号串及其运算(P9)2.2.2符号串运算符号串的连接设x和y是符号串，则称xy是他们的连接。例如：x=abc,y=1a则xy=abc1a,yx=1aabc即

6、x

7、=3,

8、y

9、=2,

10、xy

11、=3+2=5注意：对任意一个符号串x我们有εx=xε=x符号串集合的乘积设A和B是符号串的集合，则A和B的乘积定义为AB={xy

12、x∈A,y∈B}

13、例如：A={a,b}B={c,d}则AB={ac,ad,bc,bd}集合的乘积是满足于x∈A,y∈B的所有符号串xy所构成的集合。注意：1、对于任何集合A,有{ε}A=A{ε}=A2、{ε}=ØØ≠{}符号串的方幂设x是符号串，xn是x自身连结n次。并且x0＝ε则x1＝xx2＝xxxn＝xx……x=xxn-1n个例如,设x=abc，则x1＝abcx2＝abcabc……符号串集合的方幂A是符号串的集合，An是集合A自身n次相乘，并且A0＝{ε}则A1＝AA2＝AAAn＝AA……A=AAn-1(n>0)n个A例1A={a,b}A0＝{ε}A1＝{a,b}A2＝{aa,ab,ba,bb}A3

14、＝{aa,ab,ba,bb}·{a,b}＝{aaa,aab,aba,abb,baa,bab,bba,bbb}符号串集合的正闭包A+与闭包A*A是集合A的正闭包A＋＝A1∪A2∪……∪AnA的闭包A*＝A0∪A1∪A2∪……∪An＝{ε}∪A+A={a,b}A＋＝{a,b,aa,ab,ba,bb,aaa,aab,…..}A*＝{ε,a,b,aa,ab,ba,bb,aaa,aab,…..}A＋表示A上元素a,b构成的所有符号串的集合。VT∩VN=2.3.1文法的有关概念2．非终结符号非终结符号用来表示语言的语法成分（或语法范畴、语法单位），例如“赋值语句”。非终结符号所形成的集合记为VN

15、。一般用大写字母来表示。1．终结符号终结符号是组成语言的基本符号，如保留字、标识符、常数、运算符、界限符等。终结符号是语言的不可再分的基本符号。终结符号形成的集合记为VT。一般用小写字母表示。2.3文法和语言的形式定义假如有若干条规则有相同的左部，通常写作：α→β1

16、β2

17、…

18、βnβn称为α的候选式产生式是用来定义一个语法成分的。它描述了一个语法成分的形成规则。例如标识符的构成规则可描述为：<标识符>→<字母>

19、<标识符><字母>

20、<标识符><数字>3．产生式：产生式（规则）是一个有序对（α,β），通常写作α→β（或α∷=β）其中α称为产生式的左部，β称为产生式的右部。α(VT∪VN

21、)+，β(VT∪VN)*。2.3文法和语言的形式定义例如：1）<句子>→<主语><谓语>2）<主语>→<冠词><名词>3）<谓语>→<动词><宾语>4）<宾语>→<冠词><名词>5）<名词>→man

22、car6）<冠词>→the7）<名词>→driveThemandrivethecarThecardrivetheman一组规则规定一个语言Thecardrivethecar的语法结构ThemandrivethemanVT——终结符号集。文法G是一