形式语言基础

形式语言基础1第一页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.1引言一、形式语言提出二、语言描述方法§2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树§2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法

五、推导和归约六、句型和句子七、语言

八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性

§2.4语法分析初步

一、自顶向下语法分析二、自底向上语法分析

§2.5文法和语言分类

一、文法分类二、文法和自动机三、压缩过文法

§2.6文法其他表示法

一、扩充巴科斯范式二、语法图

2第二页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.1引言一、形式语言提出二、语言描述方法§2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树§2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法

五、推导和归约六、句型和句子七、语言

八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性

§2.4语法分析初步

一、自顶向下语法分析二、自底向上语法分析

§2.5文法和语言分类

一、文法分类二、文法和自动机三、压缩过文法

§2.6文法其他表示法

一、扩充巴科斯范式二、语法图

3第三页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.1引言

一、形式语言提出

二、语言描述方法

4第四页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.1引言

一、形式语言提出

二、语言描述方法

5第五页，共一百四十三页，2022年，8月28日§2.1引言

一、形式语言提出

形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义即用数学方法（主要是代数方法）对语言进行形式化描述。一开始，我们介绍了什么是语言，那是非形式描述，是人们交流思想的工具，从语言学本身来说也是一门古老的科学，但是在很早以前人们就用数学方法开始对语言学进行研究。

1847年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言历史比较研究。

1904年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要掌握高等数学。

1931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。特别是1946年电子计算机问世以来更加促使数学和语言学结合研究。6第六页，共一百四十三页，2022年，8月28日

1956年N.Chomsky(乔姆斯基）在研究自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础。7第七页，共一百四十三页，2022年，8月28日数学家Kleene（克林）在研究神经细胞时建立了自动机模型，使用该模型来识别一个语言。

控制部件输入文件存储输出8第八页，共一百四十三页，2022年，8月28日乔姆斯基1959将形式语言的研究成果和自动机的研究成果结合形式语言与自动机理论正式诞生，成为计算机科学理论一个重要分支，迅速在计算机科学技术领域的得到了应用。9第九页，共一百四十三页，2022年，8月28日

形式语言理论研究的对象不仅是自然语言，也有人工语言（包括计算机编程的高级语言）。乔姆斯基的形式语言理论得到了多重验证，于是才为语言学界和计算机科学界所折服，

“引发了语言学中的伽利略式的科学革命的开端”10第十页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.1引言

一、形式语言提出

二、语言描述方法

11第十一页，共一百四十三页，2022年，8月28日§2.1引言

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

1.枚举法：如果一个语言仅含有有限个句子，就可以采用枚举法来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大多数重要语言都有无穷多个语句，因此枚举法显然失效。

12第十二页，共一百四十三页，2022年，8月28日

2.文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。

3.自动机识别法：用自动机对语言中的句子进行识别，自动机是描述离散变量的一个系统（数学模型），因在形式语言中称为识别器，也可看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动机能接受该语言句子，否则不接受。

下面我们着重讨论用文法生成法来描述语言。13第十三页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.1引言一、形式语言提出二、语言描述方法§2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树§2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法

五、推导和归约六、句型和句子七、语言

八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性

§2.4语法分析初步

一、自顶向下语法分析二、自底向上语法分析

§2.5文法和语言分类

一、文法分类二、文法和自动机三、压缩过文法

§2.6文法其他表示法

一、扩充巴科斯范式二、语法图

14第十四页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.2用文法生成法对语言进行描述

一、巴科斯范式二、语法和语义

1.语法

2.语义三、语法树

15第十五页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.2用文法生成法对语言进行描述

一、巴科斯范式二、语法和语义

1.语法

2.语义三、语法树

16第十六页，共一百四十三页，2022年，8月28日§2.2用文法生成法对语言进行描述

一、巴科斯范式

巴科斯范式BNF--BackusNormalFormThebigelephantatethepeanut.(大象吃花生）

Thelittleboyranquickly.(小男孩跑得快）

Themanhasapig.(这人有一只猪）以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立的句子。如何描述一个给定的句子在给定规则下是否成立呢？我们以“∷=”符号(或“→”符号)表示定义为，以“|”符号表示“或”，以“〈〉”符号表示语法实体(语法单位)，这些符号是元语言符号，那么上面叙述<句子>的语法规则可写为：17第十七页，共一百四十三页，2022年，8月28日①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=<冠词><形容词>〈名词〉③〈冠词〉∷=the④<形容词>∷=big⑤〈谓语〉∷=〈动词〉〈宾语〉⑥〈动词〉∷=ate⑦〈宾语〉∷=〈冠词〉〈名词〉⑧〈名词〉∷=elephant|peanut我们把这种描述语法规则方法称巴科斯范式，也称巴科斯--瑙尔范式(BackusNormalForm)，简称BNF。根据以上规则，可以推导出句子Thebigelephantatethepeanut.过程如下：18第十八页，共一百四十三页，2022年，8月28日步骤推导所用规则1<句子><主语>〈谓语〉①2<冠词>〈形容词〉〈名词〉〈谓语〉②3the〈形容词〉〈名词〉〈谓语〉③4thebig〈名词〉〈谓语〉④5thebigelephant〈谓语〉⑧6thebigelephant〈动词〉<宾语>⑤7thebigelephantate<宾语>⑥8thebigelephantate〈冠词〉<名词>⑦9thebigelephantatethe<名词>③10thebigelephantatethepeanut⑧可见句子thebigelephantatethepeanut成立。当然我们还可以推导出其它的句子，如thebigpeanutatetheelephant，在这里，我们只考虑句子的语法，而不考虑句子的语义。19第十九页，共一百四十三页，2022年，8月28日巴科斯范式是描述语法规则一种表示方法,它是由巴科斯为了在ALGOL60报告中来描述ALGOL语言首先提出的。采用这种形式体系方式定义语法规则,可以用简洁的公式把各种语法规则严格而清晰描述出来。例如,在高级语言中大家所熟知的〈标识符〉这种语法成分,它用巴科斯范式描述为:〈标识符〉∷=〈字母〉|〈标识符〉〈字母〉|〈标识符〉〈数字〉而〈字母〉∷=A|B|C|D|…|Z〈数字〉∷=0|1|2|…|9

这样便刻画出了〈标识符〉是以字母开始的一串字母和数字任意组合这种特点。20第二十页，共一百四十三页，2022年，8月28日用巴科斯范式描述语言能给研究问题带来很大方便。如下面9个句子都是正确的：①Weran②Heran③Iran④Weate⑤Heate⑥Iate⑦Wesat⑧Hesat⑨Isat如果我们用巴科斯范式来描述上面9个句子只要几条规则就行了。①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=We|He|I③〈谓语〉∷=ran|ate|sat可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。21第二十一页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.2用文法生成法对语言进行描述

一、巴科斯范式二、语法和语义

1.语法

2.语义三、语法树

22第二十二页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.2用文法生成法对语言进行描述

一、巴科斯范式二、语法和语义

1.语法

2.语义三、语法树

23第二十三页，共一百四十三页，2022年，8月28日§2.2用文法生成法对语言进行描述二、语法和语义

1.语法

用类似巴科斯范式来描述某种语言，称为该语言的语法（也称文法）。

实际上语法是在字母表上构造句子的一组规则。对于自然语言就是造句的规则；对于程序设计语言就是书写程序规则。24第二十四页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.2用文法生成法对语言进行描述

一、巴科斯范式二、语法和语义

1.语法

2.语义三、语法树

25第二十五页，共一百四十三页，2022年，8月28日§2.2用文法生成法对语言进行描述

二、语法和语义

2.语义

语义是按照语法规则所构成结构的含义。对于自然语言，语义是所要表达的意思；对于程序设计语言，语义是一个程序所要完成工作，或者某个语法成分的含义。显然，一个句子语法上正确不等于语义上也是正确的。例如，“人吃石头”在语法上是正确，在语义上是荒谬的。在PASCAL语言中，标识符以字母开头是语法，而标识符使用必须加以说明则是语义。对于语法目前研究比较成熟，可以进行形式描述，但对语义的描述还没能形式化，还得借助于自然语言。

26第二十六页，共一百四十三页，2022年，8月28日编译程序如何将源程序变成目标程序？第一：就是语法分析，看源程序是否符合该语言的语法关系第二：就是语义分析，根据该语言语义生成目标代码这是两个核心问题。27第二十七页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.2用文法生成法对语言进行描述

一、巴科斯范式二、语法和语义

1.语法

2.语义三、语法树

28第二十八页，共一百四十三页，2022年，8月28日§2.2用文法生成法对语言进行描述

三、语法树

除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

29第二十九页，共一百四十三页，2022年，8月28日

句子themanhasabook

①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=<冠词><形容词>〈名词〉③〈冠词〉∷=the④<形容词>∷=big⑤〈谓语〉∷=〈动词〉〈宾语〉⑥〈动词〉∷=ate⑦〈宾语〉∷=〈冠词〉〈名词〉⑧〈名词〉∷=elephant|peanut30第三十页，共一百四十三页，2022年，8月28日

句子themanhasabook

①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=<冠词><形容词>〈名词〉|

<冠词>〈名词〉③〈冠词〉∷=the|a④<形容词>∷=big⑤〈谓语〉∷=〈动词〉〈宾语〉⑥〈动词〉∷=ate|has⑦〈宾语〉∷=〈冠词〉〈名词〉⑧〈名词〉∷=elephant|peanut|man|book31第三十一页，共一百四十三页，2022年，8月28日

句子themanhasabook

的推导过程及对应的语法树<句子>32第三十二页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语>33第三十三页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><冠词>34第三十四页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词>the<冠词>35第三十五页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词>manthe<冠词>36第三十六页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manthe<冠词>37第三十七页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhasthe<冠词>38第三十八页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>the<冠词>39第三十九页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语>the<名词><动词><宾语>manhas<名词><冠词>a<冠词>40第四十页，共一百四十三页，2022年，8月28日三、语法树除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。

（句子themanhasabook的推导过程及对应的语法树）<句子><主语><谓语><名词><动词><宾语>manhas<名词><冠词>abookthe<冠词>其中：<句子>称为语法树根带<>和不带<>的都称为语法树的结点一个结点以及向下射出部分称为子树没有向下射出部分的结点称为末端结点41第四十一页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.1引言一、形式语言提出二、语言描述方法§2.2用文法生成法对语言进行描述一、巴科斯范式二、语法和语义三、语法树§2.3形式语言基本概念和术语一、元语言二、符号和符号串三、产生式（规则）四、文法

五、推导和归约六、句型和句子七、语言

八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性

§2.4语法分析初步

一、自顶向下语法分析二、自底向上语法分析

§2.5文法和语言分类

一、文法分类二、文法和自动机三、压缩过文法

§2.6文法其他表示法

一、扩充巴科斯范式二、语法图

42第四十二页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法

五、推导和归约

六、句型和句子七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明43第四十三页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明44第四十四页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明45第四十五页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

一、元语言

1.元语言下面给大家介绍一些与编译有关的形式语言基本概念和术语。用来描述其它语言的语言，称元语言。而被描述语言称对象语言。

例如：英语教科中，英语是对象语言，汉语是元语言。元语言与被描述语言可以是相同的，也可以是不同的。

46第四十六页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明47第四十七页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

一、元语言

2.元语言变量

元语言的词汇称为元语言的变量(或元语言的符号)。例如：在上一节中描述句子，我们用了<句子><主语><谓语><宾语>等，这些符号的引入完全是为了描述英语句子thebigelephantatethepeanut.而这些引入符号并未出现在句子中，对于这种用尖括号括起来的词汇就是元语言变量或语法单位。48第四十八页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明49第四十九页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明50第五十页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

二、符号和符号串

1.字母表

有限个元素的非空集合称字母表，也称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。习惯上用V、Σ或其它大写字母表示。例如V={a,b,c}，V={α,β…ω}等都是字母表。|V|表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表={0,1}，

PASCAL语言的字母表由字母、数字以及一些特殊符号，如+，-，*，/，·，(，)，=，…等组成。

注意：在一个语言中不能出现字母表以外的符号。51第五十一页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明52第五十二页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

二、符号和符号串

2.符号串

（1）定义

符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号行或字)

例如：设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）符号串长度

符号串中所含符号个数称为该符号串的长度，设符号串为x，则用|x|来表示x的长度。例如：x=abc，则|x|=3,显然,|ε|=0。53第五十三页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

二、符号和符号串关于符号串的几种运算

（1）符号串的联结设有符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即

x=x1x2x3…xm,y=y1y2y3…yn则

xy

=x1x2x3…xmy1y2y3…yn

显然εx=x，xε=x

（2）符号串的方幂

设有符号串x,则x的n次联结称为x的n次方幂

则x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n个）如x=abc则x0=ε,x1=abc,x2=abcabcx3=abcabcabc

54第五十四页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

二、符号和符号串关于符号串的几种运算

（3）符号串的头、尾、子串

设有符号串x,把x的尾部去掉若干符号（包括0个符号）之后所余下部分称为x的头设有符号串x,把x的头部去掉若干符号（包括0个符号）之后所余下部分称为x的尾若x的头（尾）不是x本身，则称x的真头（尾）

从一个符号串中删去一个头和尾后所余下的部分称为此符号串的子串，如果删去的头和尾不同时为ε，则该子串是真子串。如x=abcx的头：abc、ab、a、ε55第五十五页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明56第五十六页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

二、符号和符号串

3.行集合

符号串集合：若集合A中的一切元素都是字母表上符号串，则称A为该字母表上的符号串集合。用大写字母A、B、C……来表示字母表上符号串集合。例如：设V={0，1},则符号串集合

A={ε，0，1，01}B={0，11，00，111}

对于符号串集合不可能穷尽一切元素时，可以用集合中符号串所应满足的条件来刻画一个符号串集合，即{x|x满足条件C}:例如：{x|x全由1组成}57第五十七页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

二、符号和符号串

3.行集合

字母表V上各种长度符号串构成行集合，记为V*，不包括空符号串的集合记为V+

即V*={x|x是V上符号串且包括空符号串}V+={x|x是V上符号串且不包括空符号串}V+=V*-{ε}

如：V={a,b}，则

V*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}V+={a,b,aa,ab,ba,bb,aaa,…bbb,…}58第五十八页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明59第五十九页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

二、符号和符号串

4.关于行集合V*上几种运算

（1）符号串的联结设有符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即

x=x1x2x3…xm,y=y1y2y3…yn则

xy

=x1x2x3…xmy1y2y3…yn

显然εx=x，xε=x

60第六十页，共一百四十三页，2022年，8月28日（2）符号串集合乘积设A和B为两个符号串集合，并包含于V*，则A和B的乘积定义为

AB={xy|x∈A且y∈B}由此定义，乘积AB是满足x∈A且y∈B的所有符号串xy所组成的集合。如：V={0，1}V*={ε,0,1,00,01,10,11,000,001，010，011，100,101…}A={0，101}B={10，11，110}则AB={010，011，0110，10110，10111，101110}

61第六十一页，共一百四十三页，2022年，8月28日符号串是字母表中的符号所组成的任何有穷序列空符号串：εεx=x，xε=x

若集合A中的一切元素都是字母表上符号串，则称A为该字母表上的符号串集合空集：ΦΦA=AΦ=Φ含有空符号串的集合：{ε}

{ε}A=A{ε}=A

62第六十二页，共一百四十三页，2022年，8月28日（3）符号串的方幂

设有符号串x∈V*,则x的n次联结称为x的n次方幂

则x0=ε，x1=x，x2=xx，x3=xxx，…xn=xx…x(n个）如x=abc则x0=ε,x1=abc,x2=abcabcx3=abcabcabc（4）符号串集合的方幂设符号串集合AV*则A0={ε},A1=A,A2=AA,A3=AAA,…An=AAA…A(n个）如：设A={a,b}，则A0={ε},A1={a,b}，A2={a,b}{a,b}={aa,ab,ba,bb}A3={aaa,aab,aba,abb,baa,bab,bba,bbb}∩63第六十三页，共一百四十三页，2022年，8月28日(5)符号串集合的闭包和正闭包

设A为符号串集合，则A的正闭包定义为

A+=A1∪A2∪…∪An∪…

符号串集合A的闭包定义为

A*=A0∪A+={ε}∪A+

如A={a,b}则A+={a,b}∪{aa,ab,ba,bb}∪…={a,b,aa,ab,ba,bb,aaa,…,bbb,…}A*={ε,a,b,aa,ab,ba,bb,aaa,…bbb,…}我们可以证明：A+=AA*=A*AAA*=A（A0∪A1∪A2∪…An∪…

）

=A1∪A2∪…An∪…

=A+64第六十四页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明65第六十五页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明66第六十六页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语三、产生式（规则）

1.定义

产生式(规则)就是一个符号与另一个符号串的有序偶

(U,x),通常记为

U→x或U∷=x

其中：U是符号,x是有限非空符号串。U称为规则的左部,x

称为规则的右部如果U→x1，U→x2，U→x3，…，U→xn

可以写成U→x1|x2|…|xn,并称xi是U的一个候选式。67第六十七页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明68第六十八页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语三、产生式（规则）

2.字汇表

（1）定义用于规则左部和右部中所有符号形成集合为字汇表，

记为V。

69第六十九页，共一百四十三页，2022年，8月28日又如：在PASCAL中，对标识符的定义规则为：〈标识符〉∷=<字母>|<标识符><字母>|<标识符><数字>〈字母〉∷=a|b|…|z〈数字〉∷=0|1|…|9（2）分类

1）非终结符号

出现在规则左部,且能派生出符号或符号串的那些符号称为非终结符,也称语法实体或语法单位,它们的全体构成一个非终结符的集合,记为VN2）终结符

规则中不属于VN的那些符号,称为终结符,它们的全体组成终结符的集合,记为VT

。终结符一般出现在规则的右部。显然,V=VN∪VT,VN∩VT=ø由此得：VN={〈字母〉,〈数字〉,〈标识符〉}VT={a,b,…,z,0,1,…9}70第七十页，共一百四十三页，2022年，8月28日例如：有产生式:S∷=0S1S∷=01

则VN={}VT={}V={}例如：有产生式:S∷=0S1S∷=01

则VN={S}VT={0,1}V={S,0,1}71第七十一页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明72第七十二页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

四、文法为研究方便，下面给出文法的形式定义定义：文法是规则的有穷集合,形式定义为四元组形式为

G=(VN,VT,P,Z)其中：VN是非终结符集合,

VT是终结符集合,

P代表产生式集,

Z∈VN是文法G开始符号,也称识别符号,它至少要在一条产生式左部出现。文法G通常记为G［Z］。73第七十三页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

四、文法对于前面例子中用8条文法规则来描述英语句子,其文法可表示为

G=(VN,VT,P,〈句子〉)其中:VN={<句子>，<主语>，<谓语>，<宾语>，<冠词>，<动词>，<形容词>,<名词>}VT={the,big,elephant,peanut,ate}P是前述8条规则Z=〈句子〉①〈句子〉∷=〈主语〉〈谓语〉②〈主语〉∷=<冠词><形容词>〈名词〉③〈冠词〉∷=the④<形容词>∷=big⑤〈谓语〉∷=〈动词〉〈宾语〉⑥〈动词〉∷=ate⑦〈宾语〉∷=〈冠词〉〈名词〉⑧〈名词〉∷=elephant|peanut74第七十四页，共一百四十三页，2022年，8月28日又例如：标识符文法可定义如下:G［Z］=(VN,VT,P,Z)VN={〈字母〉,〈数字〉,〈标识符〉}VT={a,b,…,z,0,1,…9}P由下列规则组成:〈标识符〉∷=<字母>|<标识符><字母>|<标识符><数字>〈字母〉∷=a|b|…|z〈数字〉∷=0|1|…|9Z=〈标识符〉75第七十五页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法

五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明76第七十六页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

五、推导和归约定义1

设G为一个文法，U∷=u是G中一个规则，x和y是V*上符号串，使得

v=xUy与w=xuy则称符号串v直接推导出符号串w，或称w直接归约到v，并把w叫做v直接派生式，记作vw

注意三点：1）v，w是两个不同符号串

2）有一规则U∷=u3）直接推导vw

若x=y=ε，则v=xUy=U，w=xuy=u

可见vw即Uu说明一个规则就是一个直接推导例如〈句子〉直接推导到<主语><谓语>，而<主语><谓语>直接归约到<句子>。

77第七十七页，共一百四十三页，2022年，8月28日例如:

G=(VN,VT,P,Z)VN={S},VT={0,1}P:S∷=0S1S∷=01Z=S

令v=xSy,w=x01y,因S

∷=01(U∷=u)

即vwxSyx01y

若x=y=ε则S01(一个规则就是一个直接推导)同样S

∷=0S1

v=00S11，w=000S111Uu

即vw00S11

000S11178第七十八页，共一百四十三页，2022年，8月28日又如：标识符文法定义如下:G［Z］=(VN,VT,P,Z)VN={〈字母〉,〈数字〉,〈标识符〉}VT={a,b,…,z,0,1,…9}P由下列规则组成:

〈标识符〉∷=<字母>|<标识符><字母>|<标识符><数字>

〈字母〉∷=a|b|…|z〈数字〉∷=0|1|…|9Z=〈标识符〉则有：〈标识符〉<标识符><字母>

<标识符>a

从v出发应用规则U∷=u,把v=xUy中U替换为右部u,即v直接推导到w,这时长度可能增加,至少不会缩小:|w|≥|v|。从w出发应用规则U∷=u,把w=xuy中u替换为左部U,即w直接归约为v,这时长度可能缩小,至少不会变长:|v|≤|w|。

79第七十九页，共一百四十三页，2022年，8月28日定义2

设u0,u1,u2,…,un均为V*上符号串,若w是v经过一系列直接推导得到的,即

v=u0

u1

u2

…

un-1

un=w(n>0)则称v推导到w,或称w归约到v,记作

v+w称这个直接推导序列为长度为n的推导。如果v+w或者v=w(表示0步推导),则记作

v*w称v广义推导到w或称w广义归约到v。

显然,直接推导的长度为1,推导

+的长度≥1,而广义推导

*的长度≥0例如在前面的例子中,因S∷=0S1

S∷=01

0S100S11000S11100001111所以0S1+00001111(n=3)80第八十页，共一百四十三页，2022年，8月28日例2.16设有文法G［〈整数〉］:(1)<整数>∷=<数字串>(2)<数字串>∷=<数字串><数字>(3)<数字串>∷=<数字>(4)<数字>∷=0(5)<数字>∷=1(6)<数字>∷=2(7)<数字>∷=3(8)<数字>∷=4(9)<数字>∷=5(10)<数字>∷=6(11)<数字>∷=7(12)<数字>∷=8(13)<数字>∷=9VwXUyxuyε〈整数〉εε〈数字串〉ε规则1ε<数字串>εε<数字串><数字>ε规则2ε<数字串><数字>ε〈数字〉〈数字〉规则3ε〈数字〉〈数字〉ε2〈数字〉规则62〈数字〉ε23ε规则7由此建立下列推导:<整数><数字串><数字串><数字><数字><数字>2<数字>23因此,<整数>+23,其推导长度为5。显而易见,在推导时,任意地选取规则(4)到(13),就可以推导得到任意整数。81第八十一页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导

十一、文法二义性

1.定义

2.文法二义性消除

3.几点说明82第八十二页，共一百四十三页，2022年，8月28日§2.3形式语言基本概念和术语

六、句型和句子在上述推导过程中产生了一系列的符号串，它们或全由终结符组成（如：23），或全由非终结符组成（如：<数字串>，<数字串><数字>，<数字><数字>），或由终结符和非终结符混合组成（如：2<数字>）。为了区别这些组成不同的符号串，我们引入句型和句子两个概念。定义：设G［Z］是一文法,若符号串x是由识别符Z推导而得,即

Z*xx∈V*则称符号串x为该文法G的一个句型。如果一个句型x仅由终结符组成,即

Z*xx∈VT*则称句型x为该文法一个句子。例如在例2.16中,〈整数〉,〈数字〉〈数字〉,2〈数字〉,23等都是文法G[<整数>]的句型，其中仅23是句子。

可见：句子一定是句型，而句型未必是句子。一个正确的源程序是句子。83第八十三页，共一百四十三页，2022年，8月28日第二章形式语言基础知识§2.3形式语言基本概念和术语

一、元语言

1.元语言

2.元语言变量

二、符号和符号串

1.字母表

2.符号串

3.行集合

4.关于行集合V*上几种运算

三、产生式（规则）

1.定义

2.字汇表

四、文法五、推导和归约

六、句型和句子

七、语言八、递归文法

1.定义

2.说明

九、短语和简单短语

1.短语和简单短语

2.柄短语

3.再谈语法树

十、最左推导和最右推导