2．3 文法和语言的分类 一、Chomsky对文法的定义 Chomsky把文法定义为一四元组G=（VN ，VT ，P， S），其中VN 为非终结符号集合，VT 为终结结符号集合， P为规则的集合，S为识别符号。V= VN VT 二、Chomsky对文法的分类 （1）0型文法和0型语言 如果文法G每一条规则形如，其中V+且至少含 有一终结符号，V*，则G是一个0型文法，其对应的语 言为0型语言。 0型文法又称为短语文法。0型文法相当于图灵机，即0型 文法均是图灵可计算的（递归可计算的），反之亦然。
符号串的长度 符号串中包含符号的个数称为符号串的长 度，用表示。如abc=3，=0。 符号串连结 设和是字母表上的符号串，把的所有符 号依次写在之后所得的符号串称为和的连结，记为 。 如＝ａｂ，＝ｂｃ，则＝ａｂｂｃ。 显然字母表上的任一符号串与的连结仍然是，即 有 ＝＝ 符号串集合的乘积 设Ａ、Ｂ为两个符号串集合，其乘积 为ＡＢ＝｛Ａ，Ｂ｝ 如，若Ａ＝｛ ab，bc｝，Ｂ＝｛ ac，cb｝，则 AB={abac， abcb，bcac，bccb} 特别有：{}A=A{}=A
2．2 文法语言的形式定义 在给出文法和语言的形式定义之前，我们用自然 语言直观地理解一下文法的概念。 我们知道汉语是所有句子构成的集合，而句子又 是汉字构成的符号串，但人们无法列出所有的句子， 故我们必须给出构成句子的一些规则，用这些规则 来定义句子的组成结构，比如：“ young men like network”，是自然语言的一个句子。我们可以用下 列规则来定义该句子。 <句子><主语><谓语> <主语><形容词><名词><代词> <谓词><动词><宾语> <宾语><名词> <形容词>young
规范推导的形式定义如下： 定义：设有文法G，对于xUyxuy，若y VT*，则称这种 推导为规范推导，反之即为规范归约。 2. 2.2 文法和语言 1．句型、句子和语言 设G[S]是一文法，如果符号串x是从识别符号S推导出 来的，即有S*x，则称x是文法G[S]的句型； 若x仅有终结符号构成，即有S*x，xVT*，则称x为 G[S]的句子。 文法G产生的所有句子的集合，称为语言，定义为： L（G[S]）={x S*x，xVT*}
4．短语、简单短语和句柄 定义：设G是一文法，S是文法的开始符号，是文法G 的一个句型， 如果有S*A且A+，则称是句型相对于非终结 符号A的短语。 特别若有A则称是句型相对于非终结符号A的简 单短语（直接短语）。 一个句型的最左直接短语称为该句型的句柄。 例：已知文法G[E]：EE+TT TT*FF F（E）i， 根据定义求句型T+i的短语、直接短语和句柄。 E*E+T+i，所以T+i是句型T+i相对于E的短语； E*T+T+T+i，所以i是句型T+i相对于T的短语； E*T+FT+i，所以i是句型T+i相对于F的短语且为简单 短语； E*E+iT+i，所以T是句型T+i相对于E的短语且为简单 短语； T为句柄。
（7）规Be 对aeddb进行推导过程1如下： S aAbaBdAb aedAbaedBdAbaeddAb aeddBb aeddb 对aeddb进行推导过程2如下： S aAbaBdAb aBdBdAb aBdBdBb aBdBdbaBddbaeddb 其中第一个推导过程特点是推导中总是把当前串中最左 边的非终结符号用产生式替换，第二个推导过程恰好相 反是把当前串中最右边的非终结符号用产生式替换。如 果在推导过程中的任何一步，均是对中的最左 （右）非终结符号进行替换，则称这种推导为最左（右） 推导。形式语言中最右推导称为规范推导。
如：0型文法G=（VN ，VT ，P，S）其中 VN={S，A，B，C，D，E} VT={a} P={SAcaB CaaaC CBDBE aDDa ADAC aEEa AE} 其确定的0型语言为：L={a2 i0}
（2） 1型文法和1型语言 如果文法G每一条规则形如（或表示为xUyxuy）且 ，S除外，则称G为1型文法，其对应的语言 为1型语言。1型文法又称为上下文有关的文法。 1型语言可以被线性界限自动机（LBA）接受。 如： 1型文法G=（VN ，VT ，P，S）其中 VN={S，B，C，D} VT={a，b，c} P={SaSBCaBC CBDB DBDC DCBC aBab bBbb bCbc cCcc } 其确定的1型语言为：L={aibicii1}
（5）直接推导和直接归约 定义：对于文法G，有规则A，x和y是V上的符号串， 若有符号串v和w满足： v=xAy w=xy 则说v（应用规则A）直接推导出w，或称w直接归约到 v，记为vw。 由定义可知，所谓直接推导就是在推导过程中每次只替换 一条规则。 例如，设有文法G[S]： SaAb ABdAB Be 对aeddb进行直接推导如下： S aAbaBdAb aedAbaedBdAbaeddAb aeddBb aeddb
2 文法和形式语言 为了构造程序设计语言的编译程序，首先 要对程序设计语言有一个精确的定义，它的完整 定义应包括语法和语义两个方面，如同自然语言 定义一样。 语法涉及语言的构成规律，它由一组规则组成， 用它可产生一个正确的程序，通常用上下文无关 文法作为程序设计语言的描述工具。 语义是指语言所代表的含义，一般分为两类： 静态语义和动态语义。 静态语义是一系列限定规则，用来确定何种符 合文法的程序是正确的； 动态语义是用来表明程序需要做什么等。
（4）文法的BNF表示法 在BNF表示法中引进了符号“：：=”和“”，其中 “：：=”表示“定义为”，符号“”表示“或”，其 作用是把规则左部相同的规则合并成一条规则的形式。 为书写方便，本书用“”代替“：：=”。 例如，文法G[S]： S0S1 S01 可表示为：S0S101 又如，一组规则： D0 D1 …… D9 可表示为：D01…9
<名词>mennetworkmusic <动词>like <代词>IYouHe 同样由上述规则还可产生句子“young men like network”，“I like music”等句子。 2.2. 1文法和推导 （1）规则 规则也称为产生式，是形如A或A：：=的二元组， 其中 A是规则的左部，它是某字母表 V上的一个符号， 是规则的右部，它是某字母表 V 上的一个符号串。如前 面自然语言的句子定义就是一组规则。 （2）文法和字汇表 文法 G[Z] 是规则的非空有空集合。 Z 是开始符号或称 识别符号，它至少应在一条规则的左部出现。在所有规 则中，出现在规则左部和右部的所有符号组成的集合称 为字汇表，用V表示。
2．等价文法 设有两文法G1和G2，如果L（G1）=L（G2）， 则称G1和G2为等价文法。 3．文法和语言的关系 已知一文法可唯一确定一语言，如：文法G[S]： SaaSbaab，其对应的语言为： L（G[S]）={a2n bnn1} 已知一语言可以对应文法G1或G2或… 如：已知语言：L（G[S]）={am bnm，n1}可对 应文法 SAB SAB AaAa AAaa BbBb BBbb
2．1 符号和符号串 正如自然语言如汉语是由句子构成的集合，而句子又 由单词和标点符号组成的序列构成一样，程序设计语言 C 是由所有 C 程序构成的集合，而程序是由关键字如 IF, ELSE, DO, WHILE的符号，字母及数字等基本符号所组 成，从字面上看程序是一个基本符号串，因此，要正确 定义一程序，我们必须首先定义构成程序的基本符号及 符号串。 2．1．1字母表和符号串 字母表 字母表是符号的非空有穷集合。字母表中的元素 称为符号。字母表习惯上用大写字母、V等表示，如C 语言的字母表是由字母、数字、特殊符号及if、else之类 的关键字组成。又如字母表={+，-，*，/}，其元素+，-， *，/ 即为符号。
（6）推导和归约 定义：对于文法G，如果存在一直接推导序列： vw0 w1 w2…wn=w（n0） 则称v推导出w，或称w归约至v，记为v+w （7）规范推导和规范归约 先看一例子： 设有文法G[S]： SaAb ABdAB Be 对aeddb进行推导过程1如下： S aAbaBdAb aedAbaedBdAbaeddAb aeddBb aeddb 对aeddb进行推导过程2如下： S aAbaBdAb aBdBdAb aBdBdBb aBdBdbaBddbaeddb
符号串的幂 设 是一符号串，则 的幂运算为： 0 = ， 1=，…n=n-1（n0）。 如设=ab，则0=，1=ab，2=abab，3=ababab…。 符号串集合的幂 设A 为符号串集合，则符号串集合A的幂 运 算 定 义 如 下 ： A0={}，A1=A，…，An=AAn-1。 如 设 A={ab，cd}， 则 有 A0={}，A1={ab，cd}，A2={abab， abcd，cdab，cdcd}，…。 字母表的闭包和正闭包 字母表上的闭包是字母表的各 次 方 幂 之 并 ， 记 为 * ， 具 体 定 义 为 ： * = 0 ∪ 1 ∪ 2 ∪ …，其含义为 上所有有长的串的集 合。 正闭包记为+定义为：+=1∪2∪3∪…。显然有： *=0∪+ +=*=* 例如，若={0，1}，则有： *={，0，1，00，01，10，11，000…} +={0，1，00，01，10，11，000…}
（3） 2型文法和2型语言 如果文法G每一条规则形如且 VN ，V* ，则称 G为2型文法，又称为上下文无关的文法，其对应的语言 为2型语言。 2型语言被下推自动机（PDA）接受，一般用来描述程序 设计语言。 如：2型文法G=（VN ，VT ，P，S）其中 VN={S，A} VT={a，b，c} P={SAcSc AabaAb} 其对应的语言为：L={ aibicki，k1}