第2章1文法和语言课件

第二章文法和语言一、文法的概念二、符号和符号串三、文法和语言的定义四、文法的类型五、上下文无关文法及其语法树7/23/20231莆田学院许振和本章要求主要内容：符号串，文法的概念及分类，语言的定义过程重点掌握：上下文无关文法、推导、句型、句子、语言，语法树、二义性文法、文法的语言生成过程7/23/20232莆田学院许振和构结识知文法和语言符号和符号串字母表和符号串符号串集合的运算文法和语言的形式定义文法的形式定义语言的形式定义语法分析的基本术语规则文法推导和规约句型/句子/语言短语和句柄最左最右推导和规约语法树和二义性语法树的构造语法树与短语文法的二义性文法的实用限制7/23/20233莆田学院许振和语言是由单词按一定规则（文法）组成句子来表达特定意思。故对语言的分析集中于对句子的分析。而句子的分析依据语言的文法规则。程序设计语言可以通过描述以下两个要素来定义：

第一方面是程序模式，即语言的语法；第二方面是程序含义，即语言的语义。文法与语言语义分为两类：

静态语义动态语义7/23/20234莆田学院许振和一、文法的概念所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。由单词符号按照一定的规则构成各种类型的表达式、语句、分程序（程序），即不同的语法范畴。不同的语法范畴具有不同的构成规律。单词符号的构成规则称为词法规则。各种语法范畴构成规则称为语法规则。描述词法规则和语法规则的工具是文法。文法表示用语法图(语法树)和EBNF(巴科斯-诺尔)描述。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。7/23/20235莆田学院许振和语言语法：是一组规则,定义符号如何排列，排列与符号含义无关。即程序的结构或形式语义：研究语言所代表的含义语用：语言的实际应用语言的表示方法1、用识别的观点表示语言，这种方法是给出一种算法由它判定一个句子是否在语言中。2、用产生的观点表示语言7/23/20236莆田学院许振和〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|大学生|工人|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|<名词>先举个例子：用EBNF表示7/23/20237莆田学院许振和推导：你是大学生

〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉你〈谓语〉你〈动词〉〈直接宾语〉你是〈名词〉你是大学生由上一组规则可以产生句子：你是大学生

这样的语言描述称为文法“=>”表示由某条规则的右部替换该规则的左部，把它称之为推导。7/23/20238莆田学院许振和语句“小八哥吃大花生”分析的语法树上下〈句子〉〈主语〉〈谓语〉〈形容词〉〈名词〉〈动词〉〈宾语〉小八哥吃〈形容词〉〈名词〉

大 花生7/23/20239莆田学院许振和句子的推导

<句子>⇒<主语><谓语>

⇒<形容词><名词><谓语>

⇒<小><名词><谓语>

⇒<小><八哥><谓语>

⇒<小><八哥><动><宾语>

⇒小八哥吃<宾语>

⇒小八哥吃<形容词><名词>

⇒小八哥吃大<名词>

⇒小八哥吃大花生7/23/202310莆田学院许振和〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈宾语〉小八哥吃花生大

下〈形容词〉〈名词〉上

〈句子〉句子的归约7/23/202311莆田学院许振和二、符号和符号串

任何一种语言，都是由该语言的基本字符所组成的字符串的集合。1、语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。2、字母表(符号集)：是字母的有穷非空集合。用希腊字母∑或大写英文字母等表示字母表。3、符号（字符）：字母表中的元素。因此字母表也称为符号集。用集合元素表示形式枚举字母表中的符号。符号是该语言能识别的符号，字母表是该语言能识别的所有符号的全体（字符集）

4、符号串(字符串)：字母表的符号组成任何有穷序列。例：∑={0，1}—符号集符号串有：0，1，00，01，10，117/23/202312莆田学院许振和例：∑={a，b，c}—符号集符号串有：a，b，c，ab，aaca

在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。

【注】不同排列顺序表示不同的含义。5、符号串集合：字母表上若干个符号串组成的集合。6、符号串的长度：符号串x有m个符号，则长度就为m，表示|x|=m。

如：ababa

则长度是5。定义在字母表Σ={x,，y，z，=，0，1，+，;}

上的符号串|x=y++；z=0;|=107、空符号串：用ε表示，长度为0，||=0

若符号串x,则有εx=xε=x7/23/202313莆田学院许振和8、符号串的运算：(1)符号串的头(前缀)和尾(后缀)

若z=xy,则x是z的头，y是z的尾。例：设z=abc,则z的头是ε，a，ab，abc

则z的尾是ε，c，bc，abc（2）符号串的固有头(真前缀)和固有尾(真后缀)

若z=xy符号串，x非空，则y固有尾；若y非空，则x是固有头。例：设z=abc，则z的固有头是ε，a，ab

则z的固有尾是ε，c，bc7/23/202314莆田学院许振和（3）子符号串（子串）

从一个符号串中删去它的一个前缀或(和)一个后缀之后剩余的部分称为该符号串的子符号串或子串。例如:x=abcd

则ε,a,b,c,ab,bc,cd,abc,bcd及abcd都是

x的子字符串。 而ac，ad，cb，bd，ba

等都不是x的子字符串。7/23/202315莆田学院许振和（4）符号串的连接：

设x，y是符号串，连接xy是y符号写在x符号之后。记作xy。例如，设有字符串j=abc，k=xyz

则jk=abcxyz，kj=xyzabc。连接运算是有序的。一般来说xy≠yx，仅当x=y 或其中之一为ε时,有xy=yx。显然：εx=xε=x(5)符号串的方幂：设x是符号串，则z=xx……xx，称z为x的方幂,记z=xn。因此x0=ε,x1=x,x2=xx,x3=xxx

显然n>0时,有xn

=x·xn-1＝xn-1·xn个7/23/202316莆田学院许振和

(6)符号串的集合：

若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。两个符号串集合A、B乘积定义：

AB={xy|x∈A且y∈B}

例：A={a,b}，B={c,d}

则AB={ac，ad，bc，bd}注意：有{ε}A=A{ε}=A,∅A=A∅=∅

，其中∅为空集。 ∅≠{ε} ∅={}≠{ε}

。7/23/202317莆田学院许振和

(7)闭包（∑*）字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的闭包。例：字母表∑={0,1}

则∑*={ε,0,1,00,01,10,11,000,001,010……}=∑0∪∑1∪∑2∪.…∪∑n

(8)正闭包(∑+)∑+=∑1∪∑2∪.…∪∑n

∑+称∑的正闭包。显然：∑*＝∑0∪∑+∑+＝∑∑*＝∑*∑根据集合乘积的定义7/23/202318莆田学院许振和如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：

三、文法和语言的形式定义生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）7/23/202319莆田学院许振和

1、规则（产生式、生成式）

形如→β或

::=β是字母表V的正闭包V+的一个符号；

β是字母表V的闭包V*的一个符号；称规则的左部，β称规则的右部。2、文法的定义〈1〉文法G定义为四元组（VN，VT，P，S）文法中规则P的第一种表示法7/23/202320莆田学院许振和其中：VN——非终结符号集

VT——终结符号集

P——产生式（规则）

S——开始符号或称作识别符号，它是一个非终结符，至少要在一条规则中作为左部出现。规定：（1）VN，VT，P是有穷非空集合；（2）VN∩VT＝

（不含公共元素）V=VN∪VT，称为文法G的字母表（字汇表）7/23/202321莆田学院许振和例1文法G=（VN，VT，P，S），其中VN={S}，VT={0，1}，

P={S→0S1，S→01}。非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。明显求出：S＝{01，0011，000111，…}7/23/202322莆田学院许振和例2文法G=（VN，VT，P，S）其中VN={标识符，字母，数字}VT={a,b,c,…,x,y,z,0,1,…,9}

P={<标识符>→〈字母〉<标识符>→<标识符><字母〉<标识符>→<标识符><数字〉<字母>→a

<字母>→b…<字母>→z<数字>→1…<数字>→9｝S＝<标识符>“<>”表示非终结符7/23/202323莆田学院许振和<2>文法中规则P的第二种表示法：上例1改为：G:S→0S1S→01<3>文法中规则P的第三种表示法：上例1改为：G[S]:S→0S1S→01一般约定，第一条产生式的左部是识别符号；用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。7/23/202324莆田学院许振和<1>→

是文法G=（VN，VT，P，S）的规则，和是V*中的任意符号，若有符号V，W满足：

V=

，W＝

则说V是直接产生W

或W是V的直接推导或W直接规约到V记作VW3、直接推导“=>”

从识别符号开始，不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。7/23/202325莆田学院许振和若有VW，或V=W，则记作VW(0步或若干步)

例子：在例1中存在序列：V＝0S100S11000S11100001111＝W记作：0S1000011110S100001111+＋+*若存在直接推导的序列：

V=W0

W1W2…Wn

＝W(n>0)则称V推导W(或W规约到V)，记VW(至少一步)

*一样的7/23/202326莆田学院许振和4、句型的定义设G[S]是文法，如果符号串x是从识别符号（开始符号）推导出来的（即Sx）则称x是文法G[S]的句型。若x仅由终结符号组成（SxxVT*）则称x为G[S]的句子。**例：S，0S1，000111都是文法G的句型，000111是G的句子。〖结论〗句子一定是句型，句型不一定是句子。7/23/202327莆田学院许振和5、语言的定义：

L(G)表示文法G产生的语言定义为：集合｛xSx，S为文法开始符号，

xVT*

｝该集合为语言，用L(G)表示。从定义可知：x是句型且x是文法G的句子。注：语言是文法所产生的所有句子组成的集合。例：例1的句子表示为：

L(G)＝｛0n1n

n1｝因为S0S100S11…0n1n重复利用规则S0S1*7/23/202328莆田学院许振和四、文法的类型：科学家Chomsky把文法分成以下四种类型：0型短语文法1型上下文有关文法2型上下文无关文法3型正规文法文法类型逐渐增加限制如果文法是正规文法一定也是上下文无关文法7/23/202329莆田学院许振和文法的类型2型文法1型文法0型文法四种文法之间的逐级“包含”关系3型文法7/23/202330莆田学院许振和设G=(VN,VT,P,S)，如果它的每一个产生式满足：(VN∪VT)*且至少包含一个非终结符，(VN∪VT)*，则G是0型文法。

0型文法又称为无限制文法，有时也称为短语文法。0型文法对应的语言称为0型语言或称递归可枚举集，它们的识别系统为图灵机（Turing机）。设G=(VN,VT,P,S)，如果它的每一个产生式满足：||≥||，仅仅S除外，则文法G是1型文法。7/23/202331莆田学院许振和下文只讲上下文无关文法和正规文法

4个文法类的定义是逐渐增加限制的，因此，每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。1型文法相对应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。7/23/202332莆田学院许振和1、上下文无关文法：设G=（VN，VT，P，S），若P中的每一个产生式→满足：

是一非终结符，(VN∪VT)*，则此文法称为上下文无关文法(2型文法)。

2型文法相对应的语言称为2型语言或上下文无关语言，它的识别系统为下推自动机(PDA)。例6：G＝({S,A,B},{a,b},P,S)，P的产生式如下：S→aB

S→bAA→bAA

A→aA→aSB→bB→bSB→aBB上下文无关文法7/23/202333莆田学院许振和该文法可以写成：S→aB

|bAA→a

|aS|bAAB→b|Bs|aBB2、正规文法：设G=（VN，VT，P，S），若P中的每一个产生式都是A→aB或A→a，A,B都是非终结符，a是终结符，则G是正规文法（也称右线性文法）。

3型文法对应的语言称为3型语言或正规语言（正则语言，或正则集）。7/23/202334莆田学院许振和例6：G＝({S,A,B},{0,1},P,S)，P的产生式如下：S→0AS→1BS→0A→0SA→0AA→1BB→1B→0B→1B正规文法该文法可以写成：S→0|0A|1BA→0S|0A|1BB→0|1|1B7/23/202335莆田学院许振和

Chomsky语言层，对应的文法、语言和自动机关系如图2-2所示。图2-2Chomsky文法、语言及自动机关系7/23/202336莆田学院许振和五、上下文无关文法及其语法树1、语法树（推导树）的定义：给定文法G=（VN，VT，P，S），对于G的任何句型都能构造与之关联的语法树，须满足条件为：

每个结点都有一个标记，此标记是V的一个符号。

根的标记是S。

若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中。

如果结点n的直接子孙，从左到右的次序是结点n1,n2,…,nK，其标记分别为A1,A2,…,AK

，那么AA1A2…AK一定是P中的一个产生式。描述上下文无关文法的句型推导的直观方法。7/23/202337莆田学院许振和例8：G=({S,A},{a,b},P,S)，其中P为：SaASASbAASSSaAba语法树：SaASaSbAaab说明语法树满足：树根是S。每个节点的标记都是V的一个符号。A有自己的子孙(S,b,A)，AVN中。SbA是A

SbA的产生式，aAS是S

aAS的产生式。7/23/202338莆田学院许振和结点：每个树的结点对应于一个符号。结点的名字就是该符号。边：两个结点之间的连线。根结点：没有边进入的结点。分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）子树：语法树的某个结点和它向下射出的部分。末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号语法树的相关概念7/23/202339莆田学院许振和叶子结点：树中没有子孙的结点。

从左到右读出推导树的叶子标记连接成的文法符号串，为G[S]的句型。也把该推导树称为该句型的语法树。语法树的结果：从左到右读出叶子的标记而构成的行谓之句子7/23/202340莆田学院许振和语法树的理解：语法树表示了在推导过程中用到什么样的产生式和用到哪些非终结符，并没有表明采用的顺序。例9：上式推导树是aabbaa句型的语法树。推导如下：

SaASaAaaSbAaaSbbaaaabbaa

SaASaSbASaSbAaaabAaaabbaa

SaASaSbASaabASaabbaSaabbaa都是同一个语法树7/23/202341莆田学院许振和2、最左推导（或最右推导）：若β（任何一条），、β是句型，都是对中的最左（最右）非终结符进行替换，则称为最左（最右）推导。在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。

一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?7/23/202342莆田学院许振和3、文法的二义性的定义：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义的。一个句型是否只对应唯一的一棵语法树？一个句型是否只有唯一的一个最左（最右）推导？不是7/23/202343莆田学院许振和例10：文法G＝({E},{+，×，i，(，)}，P，E)，其中P为：EiEE+EEE×EE(E)则句型i×i+i的推导：推导1：EE+EE×E+Ei×E+Ei×i＋Ei×i＋i推导2：EE×Ei×Ei×E＋Ei×i＋Ei×i＋i产生两个不同的语法树：7/23/202344莆田学院许振和iEEE×iEE＋iEE＋EEE×iii该文法为二义性7/23/202345莆田学院许振和[例]句子abaabb的两棵语法树

为什么？

对于一个文法G而言，如果L(G)中存在一个句子对应两棵或两棵以上的语法树，那么该文法就称为二义性的。

7/23/202346莆田学院许振和二义文法改造为无二义文法如果规定“×”和“＋”的优先性，并服从左结合，上式就可以构出无二义性。例如：文法G[E]:ET|E+TTF|T×FF(E)|i注意，文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G`，其中G是二义的，但是却有L(G)=L(G`)。

产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。7/23/202347莆田学院许振和本章重点：1、符号、符号串、句型、句子、语言2、理解有关文法、闭包、正闭包、规则、推导3、文法的类型7/23/202348莆田学院许振和课堂习题与练习：1、假设G是一个文法，S是文法的开始符号，如果Sx，则称x是__________。*句型2、文法G产生的_________的全体是该文法描述的语言。句子3、乔姆斯基定义的四种形式语言文法分别为:(1)文法(又"称

(2)文法)、

(3)文法(又称

(4)文法)、

(5)文法(又称

(6)文法)、

(7)文法(又称

(8)文法)。答案：(1)0型(2)短语结构(3)1型(4)上下文有关

(5)2型(6)上下文无关(7)3型(8)正规7/23/202349莆田学院许振和4、如果一个文法满足

，则称该文法是二义文法。①文法的某一个句子存在两棵（包括两棵）以上的语法树②文法中存在某个句子，它有两个（包括两个）以上的最右（最左）推导③文法中存在某个句子，它有两个（包括两个）以上的最右（最左）归约④在进行归约时，文法的某些规范句型的句柄不惟一可选项有：a.①b.②c.③d.④e.②③f.①②③g.①②③④答案：gg7/23/202350莆田学院许振和5、一个语言的文法是【

】。

a.唯一