形式语言简介.ppt

《形式语言简介.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章形式语言简介形式语言和自动机理论中的语言是一个广泛的概念。一个字母表上的语言就是该字母表的某些字符串的集合。语言中的字符串称为该语言的句子语言的的定义可以从两个方面进行：１）从产生语言的角度；２）从接收(或识别)语言的角度。产生一个语言，目的就是根据语言中的基本句子和句子的形成规则，得到(产生)该语言所包含的所有句子。这是形式语言所研究的问题。接收一个语言，目的就是使用某种自动机模型来接收句子，该模型所接收的所有句子，也形成一个语言。这是自动机所研究的问题。本章介绍形式语言的基本内容。语言的形式定义设是一个字

2、母表，L*,L称为字母表上的一个语言,wL,w称为语言L的一个句子。2.1例子语言括号匹配串的语言。该语言是指所有的左括号和右括号相匹配的串的集合；()，(())，()()等等都是该语言的句子)(，())等等不是该语言的句子。如何产生这个语言呢？即如何产生该语言所有句子呢？实际上，就是需要给出语言中句子的构造（形成）规则。递归定义提供了语言的良好的定义方式，使得语言中的句子的构造规律较明显。可以使用多种方法描述构造规则。自然语言的描述方式，采用如下的递归规则：①()是该语言的最基本的句子；②若S是句子,则

3、(S)是句子；③若S是句子,则SS是句子；这些规则称为形成规则，根据这些规则，可以(1)产生该语言的任意的句子；(2)判断某个串是否是该语言的句子。例如可以产生句子（（））而推断串（（）））不是句子。规则(的个数)是有限的，但可以产生无限个句子和长度无限的句子；因为规则是递归的。BNF的描述方式巴科斯和诺尔采用的巴科斯-诺尔范式（BNF--Backus-NaurForm）描述规则：<括号匹配串>::=()<括号匹配串>::=(<括号匹配串>)<括号匹配串>::=<括号匹配串><括号匹配串>使用尖括号“<”和“>”包括

4、起来的部分，作为一个整体来看待，表示某个语法成分需要使用字母表中的字母来定义其构成符号“::=”是BNF本身的符号（元符号），代表“定义为”或“是”。符号“(”和“)”是字母表的元素。Chomsky采用的符号化(形式化)的描述方式，运用如下的规则（这些规则被称为产生式）：①S→()②S→(S)③S→SS“→”代表“定义为”或者“是”，它的左边和右边分别称为该产生式的左边和右边根据产生式可以生成任意句子；可以判断一个串是否为句子(语法分析)产生句子的过程从S开始，利用产生式的右边代替产生式的左边（称之为推导过程）进行多

5、次推导，可以得到括号匹配的的句子。例:句子(())(()())的推导过程S=>SS=>(S)S=>(())S=>(())(S)=>(())(SS)=>(())(()S)=>(())(()())产生式的个数是有限的，规则是递归的，因而所有的小括号匹配的串，都可以由产生式产生；它们组成的集合就称为一个语言。S称为非终结符，在推导过程中，可以被代替的符号。(和)称为终结符，在推导过程中，不可以被代替的符号。→是产生式系统的元符号，不属于非终结符，也不属于非终结符。例2-1：由偶数个0组成的串的语言。规则的自然语言描述方式：

6、①00是该语言的基本的句子；②若S是句子,则00S是句子。形式化的描述方式：S→00S→00S问题：将产生式S→SS换成S→0S0或S→S00或S→SS是否还产生相同的语言？结论：一个语言，可以使用不同的产生式组合来产生。考虑由奇数个1组成串的语言（产生规则）例2-2高级程序设计语言中的算术表达式(的语言)的产生。自然语言的描述方式①单个变量是最基本的句子；②若E是一个句子，则EAE是一个句子（其中A代表运算符+、-、*、/）③若E是一个句子，则(E)是句子；形式语言的描述方式①E→i（i代表单个变量）②E→EAE③

7、E→(E)④A→+⑤A→-⑥A→*⑦A→/思考：字母表为？若以A开始推导，则产生？其中：A→+，A→-，A→*，A→/四个产生式的左边是相同的符号，可以合并为A→+

8、-

9、*

10、/+、-、*、/称为A的侯选式。E→iE→EAEE→(E)也可以记为：E→i

11、EAE

12、(E)注意：这组产生式没有表示出运算符的优先级。表示出运算符的优先级的产生式：E→E+T

13、E-T

14、TT→T*F

15、T/F

16、FF→(E)

17、i其中：E代表表达式，T代表项，F代表因子(E)代表的是带小括号的表达式。表示：先算因子，再*、/，最后+、-。如果使用%代表模

18、运算(即取余数运算)、使用^代表指数运算，则有E→E+T

19、E-T

20、TT→T*F

21、T/F

22、T%F

23、AA→F^A

24、FF→(E)

25、i注意需要考虑^运算的结合性：^是右结合的。例2-3标识符(以字母开头的字母、数字的串)的产生(仅考虑小写字母)。从标识符的形成角度考虑I→LI→ILI→IDL→a

26、b

27、c

28、d

29、e

30、f

31、g

32、h

33、i

34、j

35、k

36、l

37、m

38、n

39、o

40、