形式语言基础.ppt

《形式语言基础.ppt》由会员分享，可在线阅读，更多相关《形式语言基础.ppt（143页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现在学习的是第1页，共143页2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法2.2 2.2 用文法生成法对语言用文法生成法对语言 进行描述进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 2.3 形式语言基本概念和形式语言基本概念和 术语术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性 2.4 2.4 语法分析初步语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 2.5 文法和语言分类文法和语言分类 一、文法分类 二、文法和

2、自动机 三、压缩过文法 2.6 2.6 文法其他表示法文法其他表示法 一、扩充巴科斯范式 二、语法图 现在学习的是第2页，共143页2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法2.2 2.2 用文法生成法对语言用文法生成法对语言 进行描述进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 2.3 形式语言基本概念和形式语言基本概念和 术语术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性 2.4 2.4 语法分析初步语法分析初步 一、自顶向下

3、语法分析 二、自底向上语法分析 2.5 2.5 文法和语言分类文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 2.6 文法其他表示法文法其他表示法 一、扩充巴科斯范式 二、语法图 现在学习的是第3页，共143页2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法 现在学习的是第4页，共143页2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法 现在学习的是第5页，共143页2.1 2.1 引言引言 一、形式语言提出一、形式语言提出 形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义即用数

4、学方法（主要是代数方法）对语言进行形式化描述。即用数学方法（主要是代数方法）对语言进行形式化描述。一开始，我们介绍了什么是语言，那是非形式描述，是人们交流思想一开始，我们介绍了什么是语言，那是非形式描述，是人们交流思想的工具，从语言学本身来说也是一门古老的科学，但是在很早以前人们就的工具，从语言学本身来说也是一门古老的科学，但是在很早以前人们就用数学方法开始对语言学进行研究。用数学方法开始对语言学进行研究。18471847年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言历史比较研究。历史比较研究。19041904年，波兰语言学家指出，

5、语言学家不仅要掌握初等数学而且还要年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要掌握高等数学。掌握高等数学。19311931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。特别是特别是19461946年电子计算机问世以来更加促使数学和语言学结合研究。年电子计算机问世以来更加促使数学和语言学结合研究。现在学习的是第6页，共143页 1956年年N.Chomsky(乔姆斯基）在研究乔姆斯基）在研究自然语言过程中提出一种文法数学模型自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础。，为形式语言理论打下了基础。现在学

6、习的是第7页，共143页 数学家Kleene（克林）在研究神经细胞时建立了自动机模型，使用该模型来识别一个语言。控制部件控制部件输入文件输入文件存存储储输出输出现在学习的是第8页，共143页 乔姆斯基乔姆斯基1959将形式语言的研究成果和自将形式语言的研究成果和自动机的研究成果结合动机的研究成果结合 形式语言与自动机理论正式诞生，成为形式语言与自动机理论正式诞生，成为计算机科学理论一个重要分支，迅速在计计算机科学理论一个重要分支，迅速在计算机科学技术领域的得到了应用。算机科学技术领域的得到了应用。现在学习的是第9页，共143页 形式语言理论研究的对象不仅是自然语形式语言理论研究的对象不仅是自然

7、语言，也有人工语言（包括计算机编程的高言，也有人工语言（包括计算机编程的高级语言）。乔姆斯基的形式语言理论得到级语言）。乔姆斯基的形式语言理论得到了多重验证，于是才为语言学界和计算机了多重验证，于是才为语言学界和计算机科学界所折服，科学界所折服，“引发了语言学中的伽利略式的科学革引发了语言学中的伽利略式的科学革命的开端命的开端”现在学习的是第10页，共143页2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法 现在学习的是第11页，共143页2.1 2.1 引言引言 二、语言描述方法二、语言描述方法无论是自然语言或者是程序设计语言，都是由许多句子组成，当然无论是自然语言或者是程序设计

8、语言，都是由许多句子组成，当然这些句子是由本语言字母表上符号并按照一定规则组成的符号串。对这些句子是由本语言字母表上符号并按照一定规则组成的符号串。对一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的句子，哪些句子是不属于该语言的句子。句子，哪些句子是不属于该语言的句子。我们可以用三种方法来描述语言，枚举法、文法生成法和自动机我们可以用三种方法来描述语言，枚举法、文法生成法和自动机识别法识别法 。1.1.枚举法枚举法 ：如果一个语言仅含有：如果一个语言仅含有有限有限个句子，就可以采用枚举法个句子，就可以采用枚举法来描述此语言

9、，即把语言中全部句子一一列举出来即可。然而，绝大来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大多数重要语言都有无穷多个语句，因此枚举法显然失效。多数重要语言都有无穷多个语句，因此枚举法显然失效。现在学习的是第12页，共143页 2.2.文法生成法：就是用有限个规则来产生出语言中无限个句子，文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。这种规则集合称文法。3.自动机识别法：用自动机对语言中的句子进行识别，自动机是描述自动机识别法：用自动机对语言中的句子进行识别，自动机是描述离散变量的一个系统（数学模型），因在形式语言中称为识别器，也可离散变量的一个系统（

10、数学模型），因在形式语言中称为识别器，也可看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动机能接受该语言句子，否则不接受。机能接受该语言句子，否则不接受。下面我们着重讨论用文法生成法来描述语言。下面我们着重讨论用文法生成法来描述语言。现在学习的是第13页，共143页2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法2.2 2.2 用文法生成法对语言用文法生成法对语言 进行描述进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 2.3 形式语言基本概念和形式语言基本概念和 术语术语 一、元语言 二、符号

11、和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性 2.4 2.4 语法分析初步语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 2.5 文法和语言分类文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 2.6 文法其他表示法文法其他表示法 一、扩充巴科斯范式 二、语法图 现在学习的是第14页，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 现在学习的是第15页

12、，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 现在学习的是第16页，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式一、巴科斯范式 巴科斯范式巴科斯范式 BNF-Backus Normal Form The big elephant ate the peanut.(大象吃花生）大象吃花生）The little boy ran quickly.(小男孩跑得快）小男孩跑得快）The man has a pig.(这人有一只猪）这人有一只猪）以上都是符合英

13、语语法规则的句子，即它们是在英语语法规则中成立以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立 的句子。的句子。如何描述一个给定的句子在给定规则下是否成立呢？如何描述一个给定的句子在给定规则下是否成立呢？我们以我们以“=”符号符号(或或“”符号符号)表示定义为，以表示定义为，以“|”符号表示符号表示“或或”，以以“”符号表示语法实体符号表示语法实体(语法单位语法单位)，这些符号是元语言符号，这些符号是元语言符号，那么上面叙述那么上面叙述的语法规则可写为的语法规则可写为：现在学习的是第17页，共143页句子句子 =主语主语谓语谓语主语主语 =名词名词冠词冠词 =the =big谓语谓

14、语 =动词动词宾语宾语 动词动词 =ate 宾语宾语 =冠词冠词名词名词 名词名词 =elephant|peanut 我们把这种描述语法规则方法称我们把这种描述语法规则方法称巴科斯范式巴科斯范式，也称巴科斯，也称巴科斯-瑙尔范式瑙尔范式(Backus Normal Form)，简称，简称BNF。根据以上规则，可以推导出句子根据以上规则，可以推导出句子The big elephant ate the peanut.过程如下过程如下：现在学习的是第18页，共143页步骤步骤 推导推导 所用规则所用规则1 1 谓语谓语 2 2 形容词形容词 名词名词 谓语谓语 3 3 the the 形容词形容词

15、名词名词 谓语谓语 4 4 the big the big 名词名词 谓语谓语 5 5 the big elephant the big elephant 谓语谓语 6 6 the big elephant the big elephant 动词动词 7 7 the big elephant ate the big elephant ate 8 8 the big elephant ate the big elephant ate 冠词冠词 9 9 the big elephant ate the the big elephant ate the 10 10 the big elephant

16、ate the peanut the big elephant ate the peanut 可见句子可见句子the big elephant ate the peanutthe big elephant ate the peanut成立。当然我们还可以成立。当然我们还可以推导出其它的句子，如推导出其它的句子，如the big peanut ate the elephantthe big peanut ate the elephant，在这里，我们，在这里，我们只考虑只考虑句子的语法，而不句子的语法，而不考虑考虑句子的语义句子的语义。现在学习的是第19页，共143页 巴科斯范式是描述语法规则一

17、种表示方法巴科斯范式是描述语法规则一种表示方法,它是由巴科斯为了在它是由巴科斯为了在ALGOLALGOL6060报告中来描述报告中来描述ALGOLALGOL语言首先提出的。采用这种形式体语言首先提出的。采用这种形式体系方式定义语法规则系方式定义语法规则,可以用简洁的公式把各种语法规则严格而清可以用简洁的公式把各种语法规则严格而清晰描述出来。例如晰描述出来。例如,在高级语言中大家所熟知的在高级语言中大家所熟知的标识符标识符这种语这种语法成分法成分,它用巴科斯范式描述为它用巴科斯范式描述为:标识符标识符 =字母字母|标识符标识符字母字母|标识符标识符数字数字而而字母字母 =A|B|C|D|Z数字数

18、字 =0|1|2|9 这样便刻画出了这样便刻画出了标识符标识符是以字母开始的一串字母和数字任意组合这种特点。是以字母开始的一串字母和数字任意组合这种特点。现在学习的是第20页，共143页用用巴科斯范式描述语言能给研究问题带来很大方便。如下面巴科斯范式描述语言能给研究问题带来很大方便。如下面9 9个句子都是个句子都是正确的：正确的：We ran We ran He ran He ran I ran I ran We ate We ate He ate He ate I ateI ateWe sat We sat He sat He sat I satI sat如果我们用巴科斯范式来描述上面如果我

19、们用巴科斯范式来描述上面9 9个句子只要几条规则就行了。个句子只要几条规则就行了。句子句子 =主语主语谓语谓语主语主语 =We|He|I 谓语谓语 =ran|ate|sat可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义意义.它用一组规则来代替枚举法，用有穷来描述无限。它用一组规则来代替枚举法，用有穷来描述无限。现在学习的是第21页，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 现在学习的是第22页，共143页2.2

20、2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 现在学习的是第23页，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 二、语法和语义二、语法和语义 1.语法 用类似用类似巴科斯范式来描述某种语言，称为该语言的语法（也称文法巴科斯范式来描述某种语言，称为该语言的语法（也称文法）。实际上实际上语法是在字母表上构造句子的一组规则语法是在字母表上构造句子的一组规则。对于自然语。对于自然语言就是造句的规则；对于程序设计语言言就是造句的规则；对于程序设计语言就是书写程序规则。就是书写程序规则。现在

21、学习的是第24页，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 现在学习的是第25页，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 二、语法和语义二、语法和语义 2.语义 语义是按照语法规则所构成结构的含义语义是按照语法规则所构成结构的含义。对于自然语言，语义是所要表达的意思；对于程序设计语言，语义对于自然语言，语义是所要表达的意思；对于程序设计语言，语义 是一个程序所要完成工作，或者某个语法成分的含义。显然，一个句子语法上正确不等于语是一个程序所要完成工作，或者

22、某个语法成分的含义。显然，一个句子语法上正确不等于语义上也是正确的。例如，义上也是正确的。例如，“人吃石头人吃石头”在语法上是正确，在语义上是荒谬的。在语法上是正确，在语义上是荒谬的。在在PASCAL语言中，标识符以字母开头是语法，而标识符使用必须加以说明则是语义。语言中，标识符以字母开头是语法，而标识符使用必须加以说明则是语义。对于语法目前研究比较成熟，可以进行形式描述，但对语义的描述还没能形式化，还得借助对于语法目前研究比较成熟，可以进行形式描述，但对语义的描述还没能形式化，还得借助于自然语言。于自然语言。现在学习的是第26页，共143页 编译程序如何将源程序变成目标程序？编译程序如何将源

23、程序变成目标程序？第一：就是语法分析，看源程序是否符合该语言的语法关系第一：就是语法分析，看源程序是否符合该语言的语法关系第二：就是语义分析，根据该语言语义生成目标代码第二：就是语义分析，根据该语言语义生成目标代码这是两个这是两个核心问题核心问题。现在学习的是第27页，共143页2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 现在学习的是第28页，共143页 三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述

24、句子语法结构关系，称形式来表示。以图解（树）形式来描述句子语法结构关系，称。现在学习的是第29页，共143页 句子 the man has a book 句子句子 =主语主语谓语谓语主语主语 =名词名词冠词冠词 =the =big谓语谓语 =动词动词宾语宾语 动词动词 =ate 宾语宾语 =冠词冠词名词名词 名词名词 =elephant|peanut现在学习的是第30页，共143页 句子 the man has a book 句子句子 =主语主语谓语谓语主语主语 =名词名词|名词名词 冠词冠词 =the|a =big谓语谓语 =动词动词宾语宾语 动词动词 =ate|has 宾语宾语 =冠词冠词

25、名词名词 名词名词 =elephant|peanut|man|book现在学习的是第31页，共143页 句子 the man has a book 的推导过程及对应的语法树现在学习的是第32页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称图解（树）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）现在学习的是第33页，共143页三、语法树三、语法树 除

26、了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称。以图解（树）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）现在学习的是第34页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称）形式来描述句子语法结构关系，称。（句子（句子

27、the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）现在学习的是第35页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称。以图解（树）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）现在学习的是第36页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解除了上面可以根

28、据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称（树）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）现在学习的是第37页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称（树）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法

29、树）现在学习的是第38页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）现在学习的是第39页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，

30、称。以图解（树）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）现在学习的是第40页，共143页三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称。以图解（树）形式来描述句子语法结构关系，称。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）其中：其中：称为语法树称为语法树根根 带带和不带和不带的都称为语法树的的都称为语

31、法树的结点结点 一个结点以及向下射出部分称为一个结点以及向下射出部分称为子树子树 没有向下射出部分的结点称为没有向下射出部分的结点称为末端结点末端结点现在学习的是第41页，共143页2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法2.2 2.2 用文法生成法对语言用文法生成法对语言 进行描述进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 2.3 形式语言基本概念和形式语言基本概念和 术语术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性 2.

32、4 2.4 语法分析初步语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 2.5 文法和语言分类文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 2.6 文法其他表示法文法其他表示法 一、扩充巴科斯范式 二、语法图 现在学习的是第42页，共143页2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归

33、约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第43页，共143页2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字

34、汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第44页，共143页2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三

35、、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第45页，共143页2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 一、元语言一、元语言 1.元语言下面给大家介绍一些与编译有关的形式语言基本概念和术语。下面给大家介绍一

36、些与编译有关的形式语言基本概念和术语。用来描述其它语言的语言，称用来描述其它语言的语言，称元语言元语言。而被描述语言称而被描述语言称对象语言。对象语言。例如：英语教科中，英语是对象语言，汉语是元语言。例如：英语教科中，英语是对象语言，汉语是元语言。元语言与被元语言与被描述语言可以是相同的，也可以是不同的。描述语言可以是相同的，也可以是不同的。现在学习的是第46页，共143页2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（

37、规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第47页，共143页2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 一、元语言一、元语言 2.元语言变量 元语言的词汇称为元语言的词汇称为元语言的变量元语言的变量(或元语言的符号

38、或元语言的符号)。例如：在上一节中描述句子，我们用了例如：在上一节中描述句子，我们用了 等，这些符号的引入完全是为了描述英语句子等，这些符号的引入完全是为了描述英语句子the big the big elephant ate the peanut.elephant ate the peanut.而这些引入符号并未出现在句子中而这些引入符号并未出现在句子中，对于这种用尖括号括起来的词汇就是元语言变量或语法单，对于这种用尖括号括起来的词汇就是元语言变量或语法单位。位。现在学习的是第48页，共143页2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.

39、元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第49页，共143页2.3 2.3 形式语言基本概念形式语言基本概念

40、和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第50页，共14

41、3页2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 1.字母表 有限个元素的非空集合称有限个元素的非空集合称字母表字母表，也称符号集也称符号集。它是组成一个语言最。它是组成一个语言最基本的成分。字母表中元素称基本的成分。字母表中元素称符号符号。习惯上用习惯上用V、或其它大写字母表示。例如或其它大写字母表示。例如V=a,b,c，V=,等都是字母表。等都是字母表。|V|表示字母表中符号的个数。表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表对于不同程序设计语言有不同字母表。例如，机器语言字母表=0,1，PASCAL语言的

42、字母表语言的字母表由字母、数字以及一些特殊符号，如由字母、数字以及一些特殊符号，如+，-，*，/，(，)，=，等组成。等组成。注意：在一个语言中不能出现字母表以外的符号。注意：在一个语言中不能出现字母表以外的符号。现在学习的是第51页，共143页2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语

43、言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第52页，共143页2.3 2.3 形式语言基本概念和形式语言基本概念和术语术语 二、符号和符号串二、符号和符号串 2.符号串 （1）定义）定义 符号串符号串是字母表中的符号所组成的任何有穷序列是字母表中的符号所组成的任何有穷序列(有时也称为符号有时也称为符号 行或字行或字)例如：例如：设设V=a,b,c,则符号串有则符

44、号串有 a,b,c,aa,ab,ac,ba,abc 又如：又如：设设V=0,1,则符号串有则符号串有 0，1，00，01，10，11，000 由上例可以看出，符号串与符号组成顺序有关，如符号串由上例可以看出，符号串与符号组成顺序有关，如符号串ab不同于不同于ba，符号串符号串01不同于不同于10，今后我们常用，今后我们常用t,u,v,x,y,z等小写字母表示符号串。等小写字母表示符号串。（2）空符号串）空符号串 不包含任何符号的符号串称为不包含任何符号的符号串称为空符号串，记为空符号串，记为。（3）符号串长度）符号串长度 符号串中所含符号个数称为该符号串中所含符号个数称为该符号串的长度符号串的

45、长度，设符，设符 号串为号串为x，则用，则用|x|来表示来表示x的长度。例如：的长度。例如：x=abc，则，则|x|=3,显然显然,|=0。现在学习的是第53页，共143页2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 关于符号串的几种运算 （1）符号串的符号串的联结联结 设有符号串设有符号串x和和y，则它们的联结，则它们的联结xy是将符号串是将符号串y直接直接 拼接在符号串拼接在符号串x之后，之后，即即 x=x x1 1x x2 2x x3 3x xm m,y=y y1 1y y2 2y y3 3y yn n 则则 x y =x x1 1x x

46、2 2x x3 3x xm m y y1 1y y2 2y y3 3y yn n 显然显然 x=x，x =x （2）符号串符号串的的方幂方幂 设有符号串设有符号串x,则则x的的n次联结称为次联结称为x的的n次次方幂方幂 则则x x0 0=，x x1 1=x=x，x x2 2=xx=xx，x x3 3=xxx=xxx，x xn n=xx=xxx(nx(n个）个）如如x=abc x=abc 则则x x0 0=,x x1 1=abc,x=abc,x2 2=abcabc=abcabc x x3 3=abcabcabc=abcabcabc 现在学习的是第54页，共143页2.3 2.3 形式语言基本概念

47、和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 关于符号串的几种运算 （3）符号串符号串的的头、尾、子串头、尾、子串 设有符号串设有符号串x,把把x的的尾部尾部去掉若干符号（包括去掉若干符号（包括0个符号）之后所余下部分称为个符号）之后所余下部分称为x的的头头设有符号串设有符号串x,把把x的的头部头部去掉若干符号（包括去掉若干符号（包括0个符号）之后所余下部分称为个符号）之后所余下部分称为x的的尾尾若若x的头（尾）不是的头（尾）不是x本身，则称本身，则称x的的真头（尾）真头（尾）从一个符号串中删去一个头和尾后所余下的部分称为此符号串的从一个符号串中删去一个头和尾后所余下的部分称

48、为此符号串的子串子串，如，如果删去的头和尾不同时为果删去的头和尾不同时为，则该子串是真子串。，则该子串是真子串。如如x=abcx的头：的头：abc、ab、a、现在学习的是第55页，共143页2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明

49、 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明现在学习的是第56页，共143页2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 3.行集合 符号串集合：符号串集合：若集合若集合A中的一切元素都是字母表上符号串，则称中的一切元素都是字母表上符号串，则称A为该字母表为该字母表上的符号串集合。上的符号串集合。用大写字母用大写字母A、B、C来表示字母表上符号串集合。来表示字母表上符号串集合。例如

50、：例如：设设V=0，1,则符号串集合则符号串集合 A=，0，1，01 B=0，11，00，111 对于符号串集合不可能穷尽一切元素时，可以用集合中符号串所应满对于符号串集合不可能穷尽一切元素时，可以用集合中符号串所应满足的条件来刻画一个符号串集合，即足的条件来刻画一个符号串集合，即x|x满足条件满足条件C:例如：例如：x|x全由全由1组成组成现在学习的是第57页，共143页2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 3.行集合 字母表字母表V上各种长度符号串构成行集合，记为上各种长度符号串构成行集合，记为 V*，不包括空符号串的，不包括空符号