编译原理(第5版）-课件（更新）2025第2章 文法和语言的基本知识.pptx

第2章文法和语言的基本知识;第2章文法和语言的基本知识;第2章文法和语言的基本知识;第2章文法和语言的基本知识;2.1概述;2.1概述;1.字母表(Alphabet)

元素的非空有穷集合。

例如，∑={a,b,c}

根据字母表的定义，Σ是字母表，它有a、b、c三个元素

例如，∑={0,1}组成。

∑‘是字母表，它有0、1两个元素

;2.符号（字符）Symbol

字母表中的元素称为符号或称为字符。;3.符号串(Stringorword)（字）

符号的有穷序列称为符号串。

设有字母表∑={a,b,c}

符号串a，b，ab，ba，cba，abc…

;2.2字母表和符号串;2.2字母表和符号串;2.集合的乘积

设A和B是符号串的集合,则A和B的乘积定义为：;例如：设A={a,b},B={c,d}

;2.2字母表和符号串;3.符号串的幂运算

;例如,设x＝abc则

;4.集合的幂运算

设A是符号串的集合，则集合A的幂运算定义为

A0={?}

A1=A

A2=AA

…

An=AA…A(n个)=AAn-1(n0)

;例如，设A={a,b}，则;5.集合A的正闭包A＋与闭包A*

;例如，设A={a,b},则：

;2.3.1形式语言(FormalLanguage);;例如，设有字母表A={a,b,c}，则

;例如，设字母表∑={0,1},则

;A→0;2.3.1形式语言;2.3.1形式语言;;2.3.2文法的形式定义;2.3.2文法的形式定义;2.3.2文法的形式定义;A→?1;2.3.2文法的形式定义;2.3.2文法的形式定义;当n＝1L={____};2.3.2文法的形式定义;2.3.2文法的形式定义;G是否是描述该语言的文法？;2.3.2文法的形式定义;2.3.2文法的形式定义;2.3.2文法的形式定义;2.3.2文法的形式定义;2.3.2文法的形式定义;2.3.2文法的形式定义;;2.3.2文法的形式定义;例5设字母表∑={(,)},

试设计一个文法描述语言L={(n)n|n≥0}

;2.3.3语言的形式定义;2.3.3语言的形式定义;S→01|0S1;2.推导;我们可记为;2.3.3语言的形式定义;4.句型和句子

;我们有:;试证明符号串(i*i+i)是文法G[E]的一个句子。;E;2.3.3语言的形式定义;2.3.3语言的形式定义;;;例5设有文法G[A]：;;2.3.4规范推导和规范归约;2.3.4规范推导和规范归约;2.3.4规范推导和规范归约;2.3.4规范推导和规范归约;若用?表示归约，设A→α是文法G中的一个规则，则我们有：;则有规范归约：;2.3.5递归规则与文法的递归性;2.3.5递归规则与文法的递归性;这三条规则都不是递归规则，但有;由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:;定义的语言为;课堂练习;2.4短语、直接短语和句柄;2.4短语、直接短语和句柄;2.4短语、直接短语和句柄;2.4短语、直接短语和句柄;2.5语法树与文法的二义性;2.5.1推导和语法树;2.5.1推导和语法树;2.5.1推导和语法树;2.5.1推导和语法树;2.5.1推导和语法树;2.5.1推导和语法树;2.5.1推导和语法树;文法的某个句型是否只对应唯一的一棵

语法树呢？

或者，它是否只有唯一的一个最左推导呢？

它是否只有唯一的一个最右推导呢？;2.5.2文法的二义性;2.5.2文法的二义性;2.5.2文法的二义性;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.5.3文法二义性的消除;2.6文法和语言的分类;2.6文法和语言的分类;2.6文法和语言的分类;2.6文法和语言的分类;2.6文法和语言的分类;其描述的语言为？

L2(G[S])={};2.6文法和语言的分类;2.6文法和语言的分类;2.6文法和语言的分类;2.6文法和语言的分类;2.6文法和语言