形式语言基础讲稿.ppt

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

1、形式语言基础1 1第一页，讲稿共一百四十三页哦第二章 形式语言基础知识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 2第二页，讲稿共一百四十三页哦第二章 形式语言基础知识2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法2.2 2.2 用文法生成法对语言用文法生成法对语言 进行描述进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 2.3 形式语言基本概念和形式语言基本概念和 术语术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一

3、、文法二义性 2.4 2.4 语法分析初步语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 2.5 文法和语言分类文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 2.6 文法其他表示法文法其他表示法 一、扩充巴科斯范式 二、语法图 3 3第三页，讲稿共一百四十三页哦第二章 形式语言基础知识2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法 4 4第四页，讲稿共一百四十三页哦第二章 形式语言基础知识2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法 5 5第五页，讲稿共一百四十三页哦2.1 2.1 引言引言 一、形式语言提出一、形式语言

4、提出 形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义即用数学方法（主要是代数方法）对语言进行形式化描述。即用数学方法（主要是代数方法）对语言进行形式化描述。一开始，我们介绍了什么是语言，那是非形式描述，是人们交流思想一开始，我们介绍了什么是语言，那是非形式描述，是人们交流思想的工具，从语言学本身来说也是一门古老的科学，但是在很早以前人们就的工具，从语言学本身来说也是一门古老的科学，但是在很早以前人们就用数学方法开始对语言学进行研究。用数学方法开始对语言学进行研究。18471847年，俄国数学家布拉库夫斯基就用概率论进行语法词

5、源及语言年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言历史比较研究。历史比较研究。19041904年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要掌握高等数学。掌握高等数学。19311931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。特别是特别是19461946年电子计算机问世以来更加促使数学和语言学结合研究。年电子计算机问世以来更加促使数学和语言学结合研究。6 6第六页，讲稿共一百四十三页哦 1956年年N.Chomsky(乔姆斯基）在研究乔姆斯基）在研

6、究自然语言过程中提出一种文法数学模型自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础。，为形式语言理论打下了基础。7 7第七页，讲稿共一百四十三页哦 数学家Kleene（克林）在研究神经细胞时建立了自动机模型，使用该模型来识别一个语言。控制部件控制部件输入文件输入文件存存储储输出输出8 8第八页，讲稿共一百四十三页哦 乔姆斯基乔姆斯基1959将形式语言的研究成果和自将形式语言的研究成果和自动机的研究成果结合动机的研究成果结合 形式语言与自动机理论正式诞生，成为形式语言与自动机理论正式诞生，成为计算机科学理论一个重要分支，迅速在计计算机科学理论一个重要分支，迅速在计算机科学技术领域的

7、得到了应用。算机科学技术领域的得到了应用。9 9第九页，讲稿共一百四十三页哦 形式语言理论研究的对象不仅是自然语形式语言理论研究的对象不仅是自然语言，也有人工语言（包括计算机编程的高言，也有人工语言（包括计算机编程的高级语言）。乔姆斯基的形式语言理论得到级语言）。乔姆斯基的形式语言理论得到了多重验证，于是才为语言学界和计算机了多重验证，于是才为语言学界和计算机科学界所折服，科学界所折服，“引发了语言学中的伽利略式的科学革引发了语言学中的伽利略式的科学革命的开端命的开端”1010第十页，讲稿共一百四十三页哦第二章 形式语言基础知识2.1 2.1 引言引言 一、形式语言提出 二、语言描述方法 11

8、11第十一页，讲稿共一百四十三页哦2.1 2.1 引言引言 二、语言描述方法二、语言描述方法无论是自然语言或者是程序设计语言，都是由许多句子组成，当然无论是自然语言或者是程序设计语言，都是由许多句子组成，当然这些句子是由本语言字母表上符号并按照一定规则组成的符号串。对这些句子是由本语言字母表上符号并按照一定规则组成的符号串。对一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的句子，哪些句子是不属于该语言的句子。句子，哪些句子是不属于该语言的句子。我们可以用三种方法来描述语言，枚举法、文法生成法和自动机我们可以用三种方法来描述

9、语言，枚举法、文法生成法和自动机识别法识别法 。1.1.枚举法枚举法 ：如果一个语言仅含有：如果一个语言仅含有有限有限个句子，就可以采用枚举法个句子，就可以采用枚举法来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大多数重要语言都有无穷多个语句，因此枚举法显然失效。多数重要语言都有无穷多个语句，因此枚举法显然失效。1212第十二页，讲稿共一百四十三页哦 2.2.文法生成法：就是用有限个规则来产生出语言中无限个句子，文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。这种规则集合称文法。3.自动机识别法：

10、用自动机对语言中的句子进行识别，自动机是描述自动机识别法：用自动机对语言中的句子进行识别，自动机是描述离散变量的一个系统（数学模型），因在形式语言中称为识别器，也可离散变量的一个系统（数学模型），因在形式语言中称为识别器，也可看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动机能接受该语言句子，否则不接受。机能接受该语言句子，否则不接受。下面我们着重讨论用文法生成法来描述语言。下面我们着重讨论用文法生成法来描述语言。1313第十三页，讲稿共一百四十三页哦第二章 形式语言基础知识2.1 2.1 引言引言 一、形式语言提出

11、二、语言描述方法2.2 2.2 用文法生成法对语言用文法生成法对语言 进行描述进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 2.3 形式语言基本概念和形式语言基本概念和 术语术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性 2.4 2.4 语法分析初步语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 2.5 文法和语言分类文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 2.6 文法其他表示法文法其他表示法 一、

12、扩充巴科斯范式 二、语法图 1414第十四页，讲稿共一百四十三页哦第二章 形式语言基础知识2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 1515第十五页，讲稿共一百四十三页哦第二章 形式语言基础知识2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 1616第十六页，讲稿共一百四十三页哦2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式一、巴科斯范式 巴科斯范式巴科斯范式 BNF-Backus

13、 Normal Form The big elephant ate the peanut.(大象吃花生）大象吃花生）The little boy ran quickly.(小男孩跑得快）小男孩跑得快）The man has a pig.(这人有一只猪）这人有一只猪）以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立 的句子。的句子。如何描述一个给定的句子在给定规则下是否成立呢？如何描述一个给定的句子在给定规则下是否成立呢？我我们们以以“=”符号符号(或或“”符号符号)表示定表示定义为义为，以，以“|”符号表示符号表示“或或”

14、，以以“”符号表示符号表示语语法法实实体体(语语法法单单位位)，这这些符号是元些符号是元语语言符号，言符号，那么上面叙述那么上面叙述的的语语法法规则规则可写可写为为：1717第十七页，讲稿共一百四十三页哦句子句子=主语主语谓语谓语主语主语=名词名词冠词冠词=the =big谓语谓语=动词动词宾语宾语 动词动词=ate 宾语宾语=冠词冠词名词名词 名词名词=elephant|peanut 我我们们把把这这种种描描述述语语法法规规则则方方法法称称巴巴科科斯斯范范式式，也也称称巴巴科科斯斯-瑙瑙尔尔范范式式(Backus Normal Form)，简称，简称BNF。根据以上规则，可以推导出句子根据以

15、上规则，可以推导出句子The big elephant ate the peanut.过程如下过程如下：1818第十八页，讲稿共一百四十三页哦步骤步骤 推导推导 所用规则所用规则1 1 谓语谓语 2 2 形容词形容词 名词名词 谓语谓语 3 3 the the 形容词形容词 名词名词 谓语谓语 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 ele

16、phant 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 ate the peanut the big elephant ate the peanut 可见句子可见句子the big elephant ate the peanutthe big elephant ate the peanut成立。当然我们还可以成立。当然我们还可以推导出其它的句子，如推导出其它的句子，如the b

17、ig peanut ate the elephantthe big peanut ate the elephant，在这里，我们，在这里，我们只考虑只考虑句子的语法，而不句子的语法，而不考虑考虑句子的语义句子的语义。1919第十九页，讲稿共一百四十三页哦 巴巴科科斯斯范范式式是是描描述述语语法法规规则则一一种种表表示示方方法法,它它是是由由巴巴科科斯斯为为了了在在ALGOLALGOL6060报报告告中中来来描描述述ALGOLALGOL语语言言首首先先提提出出的的。采采用用这这种种形形式式体体系系方方式式定定义义语语法法规规则则,可可以以用用简简洁洁的的公公式式把把各各种种语语法法规规则则严严格

18、格而而清清晰晰描描述述出出来来。例例如如,在在高高级级语语言言中中大大家家所所熟熟知知的的标标识识符符这这种种语法成分语法成分,它用巴科斯范式描述为它用巴科斯范式描述为:标识符标识符=字母字母|标识符标识符字母字母|标识符标识符数字数字而而字母字母=A|B|C|D|Z数字数字=0|1|2|9 这样便刻画出了这样便刻画出了标识符标识符是以字母开始的一串字母和数字任意组合这种特点。是以字母开始的一串字母和数字任意组合这种特点。2020第二十页，讲稿共一百四十三页哦用用巴科斯范式描述语言能给研究问题带来很大方便。如下面巴科斯范式描述语言能给研究问题带来很大方便。如下面9 9个句子都是个句子都是正确的

19、：正确的：We ran He ran I ran We ran He ran I ran We ate He ate I ateWe ate He ate I ateWe sat He sat I satWe sat He sat I sat如果我们用巴科斯范式来描述上面如果我们用巴科斯范式来描述上面9 9个句子只要几条规则就行了。个句子只要几条规则就行了。句子句子=主语主语谓语谓语主语主语=We|He|I 谓语谓语=ran|ate|sat可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义意义.它用一组规则来代替枚举

20、法，用有穷来描述无限。它用一组规则来代替枚举法，用有穷来描述无限。2121第二十一页，讲稿共一百四十三页哦第二章 形式语言基础知识2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 2222第二十二页，讲稿共一百四十三页哦第二章 形式语言基础知识2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 2323第二十三页，讲稿共一百四十三页哦2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 二、语法和语义二、语法和语义

21、 1.语法 用类似用类似巴科斯范式来描述某种语言，称为该语言的语法（也称巴科斯范式来描述某种语言，称为该语言的语法（也称文法）文法）。实际上实际上语语法是在字母表上构造句子的一法是在字母表上构造句子的一组规则组规则。对对于自然于自然语语言就是造句的言就是造句的规则规则；对对于程序于程序设计语设计语言言就是书写程序规则。就是书写程序规则。2424第二十四页，讲稿共一百四十三页哦第二章 形式语言基础知识2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 2525第二十五页，讲稿共一百四十三页哦2.2 2.2 用文法生

22、成法对语言进行描述用文法生成法对语言进行描述 二、语法和语义二、语法和语义 2.语义 语义是按照语法规则所构成结构的含义语义是按照语法规则所构成结构的含义。对于自然语言，语义是所要表达的意思；对于程序设计语言，语义对于自然语言，语义是所要表达的意思；对于程序设计语言，语义 是是一一个个程程序序所所要要完完成成工工作作，或或者者某某个个语语法法成成分分的的含含义义。显显然然，一一个个句句子子语语法法上上正正确确不不等等于于语语义义上上也也是是正正确确的的。例例如如，“人人吃吃石石头头”在在语语法法上上是是正正确确，在在语语义义上上是是荒谬的。荒谬的。在在PASCAL语语言言中中，标标识识符符以以

23、字字母母开开头头是是语语法法，而而标标识识符符使使用用必必须须加加以以说说明明则则是是语语义义。对对于于语语法法目目前前研研究究比比较较成成熟熟，可可以以进进行行形形式式描描述述，但但对对语语义义的的描描述述还还没没能能形形式化，还得借助于自然语言。式化，还得借助于自然语言。2626第二十六页，讲稿共一百四十三页哦 编译程序如何将源程序变成目标程序？编译程序如何将源程序变成目标程序？第一：就是语法分析，看源程序是否符合该语言的语法关系第一：就是语法分析，看源程序是否符合该语言的语法关系第二：就是语义分析，根据该语言语义生成目标代码第二：就是语义分析，根据该语言语义生成目标代码这是两个这是两个核

24、心问题核心问题。2727第二十七页，讲稿共一百四十三页哦第二章 形式语言基础知识2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树 2828第二十八页，讲稿共一百四十三页哦2.2 2.2 用文法生成法对语言进行描述用文法生成法对语言进行描述 三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称表示。以图解（树）形式来描述句子语法结构关系，称语法树语法树语法树语法树。2929第二十九页，讲

25、稿共一百四十三页哦 句子 the man has a book 句子句子=主语主语谓语谓语主语主语=名词名词冠词冠词=the =big谓语谓语=动词动词宾语宾语 动词动词=ate 宾语宾语=冠词冠词名词名词 名词名词=elephant|peanut3030第三十页，讲稿共一百四十三页哦 句子 the man has a book 句子句子=主语主语谓语谓语主语主语=名词名词|名词名词 冠词冠词=the|a =big谓语谓语=动词动词宾语宾语 动词动词=ate|has 宾语宾语=冠词冠词名词名词 名词名词=elephant|peanut|man|book3131第三十一页，讲稿共一百四十三页哦

26、句子 the man has a book 的推导过程及对应的语法树 3232第三十二页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称解（树）形式来描述句子语法结构关系，称语法树语法树语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）3333第三十三页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示

27、。除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称以图解（树）形式来描述句子语法结构关系，称语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）3434第三十四页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称解（树）形式来描述句子语法结构关系，称语法树语法树语法树语法树。（句子（句子the man h

28、as a book的推导过程及对应的语法树）的推导过程及对应的语法树）thethe 3535第三十五页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称示。以图解（树）形式来描述句子语法结构关系，称语法树语法树语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）manmanthethe 3636第三十六页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法

29、规则来推导出句子，还可以用图解形式来表除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称示。以图解（树）形式来描述句子语法结构关系，称语法树语法树语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）manmanthethe 3737第三十七页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称以图解（树）形式来描

30、述句子语法结构关系，称语法树语法树语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）manmanhashasthethe 3838第三十八页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称解（树）形式来描述句子语法结构关系，称语法树语法树语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）manma

31、nhashas thethe 3939第三十九页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称（树）形式来描述句子语法结构关系，称语法树语法树语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）thethe manmanhashas a a 4040第四十页，讲稿共一百四十三页哦三、语法树三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式

32、来表示。以图除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称解（树）形式来描述句子语法结构关系，称语法树语法树。（句子（句子the man has a book的推导过程及对应的语法树）的推导过程及对应的语法树）manmanhashas a abookbookthethe 其中：其中：称为语法树称为语法树根根 带带和不带和不带的都称为语法树的的都称为语法树的结点结点 一个结点以及向下射出部分称为一个结点以及向下射出部分称为子树子树 没有向下射出部分的结点称为没有向下射出部分的结点称为末端结点末端结点4141第四十一页，讲稿共一百四十三

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

34、动机 三、压缩过文法 2.6 2.6 文法其他表示法文法其他表示法 一、扩充巴科斯范式 二、语法图 4242第四十二页，讲稿共一百四十三页哦第二章 形式语言基础知识2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短

35、语和简单短语 1.短语和简单短语 2.柄短 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明4343第四十三页，讲稿共一百四十三页哦第二章 形式语言基础知识2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语

36、言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明4444第四十四页，讲稿共一百四十三页哦第二章 形式语言基础知识2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四

37、、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明4545第四十五页，讲稿共一百四十三页哦2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 一、元语言一、元语言 1.元语言下面给大家介绍一些与编译有关的形式语言基本概念和术语。下面给大家介绍一些与编译有关的形式语言基本概念和术语。用来描述其它

38、语言的语言，称用来描述其它语言的语言，称元语言元语言。而被描述语言称而被描述语言称对象语言。对象语言。例如：英语教科中，英语是对象语言，汉语是元语言。例如：英语教科中，英语是对象语言，汉语是元语言。元语言与被元语言与被描述语言可以是相同的，也可以是不同的。描述语言可以是相同的，也可以是不同的。4646第四十六页，讲稿共一百四十三页哦第二章 形式语言基础知识2.3 2.3 形式语言基本概形式语言基本概念和术语念和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（

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

40、符号)。例例如如：在在上上一一节节中中描描述述句句子子，我我们们用用了了 等等，这这些些符符号号的的引引入入完完全全是是为为了了描描述述英英语语句句子子the the big big elephant elephant ate ate the the peanut.peanut.而而这这些些引引入入符符号号并并未未出出现现在在句句子子中中，对于这种用尖括号括起来的词汇就是元语言变量或语法单位。对于这种用尖括号括起来的词汇就是元语言变量或语法单位。4848第四十八页，讲稿共一百四十三页哦第二章 形式语言基础知识2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1

41、.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明4949第四十九页，讲稿共一百四十三页哦第二章 形式语言基础知识2

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

43、消除 3.几点说明5050第五十页，讲稿共一百四十三页哦2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 1.字母表 有限个元素的非空集合称有限个元素的非空集合称字母表字母表，也称符号集也称符号集。它是组成一个语言最。它是组成一个语言最基本的成分。字母表中元素称基本的成分。字母表中元素称符号符号。习惯上用习惯上用V、或其它大写字母表示。例如或其它大写字母表示。例如V=a,b,c，V=,等都是字母表。等都是字母表。|V|表示字母表中符号的个数。表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表对于不同程序设计语言有不同字母

44、表。例如，机器语言字母表=0,1，PASCAL语言的字母表语言的字母表由字母、数字以及一些特殊符号，如由字母、数字以及一些特殊符号，如+，-，*，/，(，)，=，等组成。等组成。注意：在一个语言中不能出现字母表以外的符号。注意：在一个语言中不能出现字母表以外的符号。5151第五十一页，讲稿共一百四十三页哦第二章 形式语言基础知识2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表

45、四、文法四、文法 五、推导和归约五、推导和归约 六、句型和句子六、句型和句子 七、语言七、语言 八、八、递归文法递归文法 1.定义 2.说明 九、短语和简单短语九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树 十、最左推导和最右推导十、最左推导和最右推导 十一、文法二义性十一、文法二义性 1.定义 2.文法二义性消除 3.几点说明5252第五十二页，讲稿共一百四十三页哦2.3 2.3 形式语言基本概念和形式语言基本概念和术语术语 二、符号和符号串二、符号和符号串 2.符号串 （1）定义）定义 符号串符号串是字母表中的符号所组成的任何有穷序列是字母表中的符号所组成的任何有穷序列

46、(有时也称为符号有时也称为符号 行或字行或字)例如：例如：设设V=a,b,c,则符号串有则符号串有 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）符号

47、串长度）符号串长度 符号串中所含符号个数称为该符号串中所含符号个数称为该符号串的长度符号串的长度，设符，设符 号串为号串为x，则用，则用|x|来表示来表示x的长度。例如：的长度。例如：x=abc，则，则|x|=3,显然显然,|=0。5353第五十三页，讲稿共一百四十三页哦2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 关于符号串的几种运算 （1）符号串的符号串的联结联结 设有符号串设有符号串x和和y，则它们的联结，则它们的联结xy是将符号串是将符号串y直接直接 拼接在符号串拼接在符号串x之后，之后，即即 x=x x1 1x x2 2x x3 3x

48、 xm m,y=y y1 1y y2 2y y3 3y yn n 则则 x y =x x1 1x x2 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=ab

49、cabcabc=abcabcabc 5454第五十四页，讲稿共一百四十三页哦2.3 2.3 形式语言基本概念和术语形式语言基本概念和术语 二、符号和符号串二、符号和符号串 关于符号串的几种运算 （3）符号串符号串的的头、尾、子串头、尾、子串 设有符号串设有符号串x,把把x的的尾部尾部去掉若干符号（包括去掉若干符号（包括0个符号）之后所余下部分个符号）之后所余下部分称为称为x的的头头设有符号串设有符号串x,把把x的的头部头部去掉若干符号（包括去掉若干符号（包括0个符号）之后所余下部分称为个符号）之后所余下部分称为x的的尾尾若若x的头（尾）不是的头（尾）不是x本身，则称本身，则称x的的真头（尾）真

50、头（尾）从一个符号串中删去一个头和尾后所余下的部分称为此符号串的从一个符号串中删去一个头和尾后所余下的部分称为此符号串的子串子串，如果删去的头和尾不同时为，如果删去的头和尾不同时为，则该则该子串是真子串。子串是真子串。如如x=abcx的头：的头：abc、ab、a、5555第五十五页，讲稿共一百四十三页哦第二章 形式语言基础知识2.3 2.3 形式语言基本概念形式语言基本概念和术语和术语 一、元语言一、元语言 1.元语言 2.元语言变量 二、符号和符号串二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算 三、产生式（规则）三、产生式（规则）1.定义 2.字汇表 四