第三章 文法和语言 本章目的为语言的语法描述寻求工具,以便： 对源程序给出精确无二义的语法描述。（严谨、简洁、易读） 第三章 文法和语言 本章目的为语言的语法描述寻求工具,以便： 对源程序给出精确无二义的语法描述。（严谨、简洁、易读） 根据语言文法的特点来指导语法分析的过程 从描述语言的文法可以自动构造出可用的分析程序 制导语义翻译

文法和语言 预备知识 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明 有关文法的一些关系

预备知识 -----语言概述 语言是由句子组成的集合，是由一组记号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 每个句子构成的规律 研究语言 每个句子的含义 每个句子和使用者的关系

预备知识 -----语言概述 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics

预备知识 -----语言概述 语法 -- 表示构成语言句子的各个记号之间的组合规律 语义 -- 表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。

预备知识 -----语言概述 每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。

预备知识 -----形式语言 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。

预备知识 -----有关定义和记号 符号：可以相互区别的记号（元素）。 字母表：符号（元素）的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3. y是上的符号串,当且仅当它可以由1和2导出。 例如： Σ={a,b} ε,a,b,aa,ab,aabba…都是上的符号串

预备知识 -----有关定义和记号 符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串. 如： b是符号串banana的一个前缀. 符号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串. 如:nana是符号串banana的一个后缀. 符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串. 如:ana是符号串banana的一个子串.

符号串的运算 对于每个符号串s， s和ε两者都是符号串s的前缀，后缀和子串。 符号串s的真前缀，真后缀，真子串：任何非空符号串 x,相应地，是s的前缀，后缀或子串，并且 s  x 符号串的运算 符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 ε的长度为0 连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有εa = aε 方幂：符号串自身连接n次得到的符号串 an 定义为 aa…aa n个a a1=a, a2=aa则a0=ε

符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 两个符号串集合A和B的乘积定义为 AB =xy|xA且yB 若 集合A=ab,cde B = 0,1 则 AB =ab1,ab0,cde0,cde1 使用 * 表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。 上的除ε外的所有符号串组成的集合记为+ 。 Σ+称为Σ的正闭包。

例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

语言：字母表上的一个语言是上的一些符号串的集合 (上的每个语言是*的一个子集)。 例如： Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} 集合{ab,aabb,aaabbb,…,anbn,…} 或{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。 集合{a,aa,aaa,…} 或{w|w∈Σ*且w=an,n≥1} 为字母表上的一个语言。 ε是一个语言。 即 是一个语言。

语言上的运算 设L是（上的）一个语言,M是（上的）一个语言, 语言L和M的并，交，差，补是一个语言。 如语言L和M的并为 LM，是一个语言: {w|w is in L or is in M} 如： L1 ={a,b,…y,z} M1 ={1,2…8,9 } L1M1={a,b,… y,z，1,2…8,9 } 语言L和M的连接是一个语言，记为 LM LM={st |s∈L且 t∈M} 如： L1M1 ={a1,b1,…y1,z1,a2,b2…a9…z9} 有L ε= εL=L。 L的n次连接Ln= LL...L

语言上的运算 语言L的 闭包记为 L*， L*= L0  L1  L2  ... L0= ε ， Ln= L Ln-1= Ln-1 L,n1 语言L的正 闭包记为 L+， L+= L1  L2  L3 ... L+= LL*= L*L L*= L+  ε 如： L1 ={a,b,…y,z} M1 ={1,2…8,9 } （L1M1）={a,b,… y,z，1,2…8,9 } （L1M1）*={a,b,… y,z，1,2…8,9 ，aa,1a,…xyz,6789st..} L1（L1M1）*={所有字母打头的字母和数字符号串}

语言的描述 如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。两个途经： 生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）

文法 数学系统 一个形式数学系统可由下列基本成分来刻画：一组基本符号，一组形成规则，一组公理，一组推理规则。

文法和语言的形式定义 文法的定义 推导的定义 句型、句子、语言的定义

文法的定义 文法G定义为四元组（VN，VT，P，S） VN ：非终结符集 VT ：终结符集 P：产生式（规则）集合 S：开始符号 VN∩VT= φ， S∈VN V=VN∪VT，称为文法G的文法符号集合

规则的定义 规则（重写规则、产生式或生成式），是形如α→β或α∷=β的（α，β）有序对，且α∈V+，β∈V*。 α称为规则的左部(或生成式的左部)。 β称为规则的右部(或生成式的右部)。

文法的定义 例3.1 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 }

文法的定义 习惯上只将产生式写出。并有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 G可写成G[S]，S是开始符号 G：S→aAb A→ab A→aAb A→ε G[S]： A→ab A→aAb A→ε S→aSb 缩写形式 G[S]： A→ab |aAb |ε S→aSb 注意：元符号和源符号

例3.2 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9 } S=<标识符>

推导的定义 直接推导“” 例：G： S→0S1， S→01 α→β是文法G的产生式，若有v,w满足： v=γαδ,w= γβδ, 其中γ∈V*,δ∈V* 则称v直接推导到w,记作 v  w 或w直接归约到v 例：G： S→0S1， S→01 S 0S1 00S11 000S111 00001111 <程序><分程序>.  <变量说明部分> <语句>. ... VAR<标识符>;BEGIN READ(<标识符>)END.  VAR A;BEGIN READ(A) END.

推导的定义 若存在v w0 w1 ... wn=w,(n>0) 则称v w，v推导出w，或w归约到v 若有v w，或v=w，

文法的句型、句子的定义 句型 句子 例：G： S→0S1， S→01 S 0S1 00S11 000S111 00001111 有文法G，若S x，则称x是文法G的句型。 句子 有文法G，若S x，且x∈VT*，则称x是文法G的句子。 例：G： S→0S1， S→01 S 0S1 00S11 000S111 00001111

例：G[E]：E→E+T|T T→T. F|F F→(E)|a EE+T T+T F+T a+T a+T. F a+F 例：G[E]：E→E+T|T T→T*F|F F→(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 表示一切能用符号a，+，*，(和)构成的算术表达式

文法，语言的定义 由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)={x|S x，其中S为文法的开始符号，且x ∈VT*} 例：G： S→0S1， S→01 L(G)={0n1n|n≥1}

例3.3 文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee L（G）={ anbnen | n≥1 }

S a S BE (S→aSBE) a aBEBE (S→aBE) aabEBE ( aB→ab ) aabBEE ( EB→BE ) aabbEE （bB→bb) aabbeE （bE→be) aabbee （eE→ee) G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成

已知语言描述，写出文法 已知文法，写出语言描述 例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法。 A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 已知文法，写出语言描述 例：G[E]：E→E+T|T T→T*F|F F→(E)|a

语法 Syntax 语义 Semantics 偶正整数的集合{0,2,4,…2n ,…} dd...0(2，4，6，8)

文法的等价 若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1[A]：A→0R 与G2[S]：S→0S1 等价 A→01 S→01 R→A1

文法的类型 通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法：对任一产生式α→β，都有α∈(VN∪VT)+， β∈(VN∪VT)* 1型文法：对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε除外 2型文法：对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)* 3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT

文法的类型 例：1型（上下文有关）文法 文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee

文法的类型 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD L(G)={ww|w∈{a,b}*}

文法的类型 例：2型（上下文无关）文法 文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB A→0A|1B|0S B→1B|1|0

文法的类型 例：定义标识符的3型（正规）文法 文法G[I]： I → lT I → l T → lT T → dT T → l T → d

文法和语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFL ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）

文法和语言 四种文法之间的关系 是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。

文法和识别系统 0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。

图灵机 带 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an-1 an 磁头 有限控制器

文法的类型 2型文法（上下文无关文法、CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法（正规文法、右线性文法）：产生的语言是有穷自动机（FA）所接受的集合

上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程序设计语言的语法结构 算术表达式 语句 赋值语句 条件语句 读语句 ……

算术表达式上下文无关文法表示 文法G=({E}, {+,*,I,(,)}, P, E} P: E → i E → E+E E → E*E

条件语句上下文无关文法表示 <条件语句>→if<条件>then<语句> | if<条件>then<语句>else <语句>

上下文无关文法的语法树 用于描述上下文无关文法的句型推导的直观方法 S 例: G[S]: a A S S→aAS S b A a A→SbA 句型aabbaa的语法树（推导树） S a A S S b A a a b a 例: G[S]: S→aAS A→SbA A→SS S→a A→ba 叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。

上下文无关文法的语法树 给定文法G，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件： 1、每个结点都有一个V中的符号作标记 2、根的标记是开始符号S 3、若一结点n至少有一个它自己除外的子孙，并且n有标记A，则A∈VN 4、如果结点n的直接子孙，从左到右的次序是结点n1,n2,…,nk，其标记分别为A1,A2,…,Ak，那么A→A1A2,…,Ak一定是P中的一个产生式

上下文无关文法的语法树 定理：G为上下文无关文法， 对于α≠ε，有S α，当且仅当 文法G有以α为结果的一棵推导树。

上下文无关文法的语法树 推导过程中施用产生式的顺序 例: G[S]: S→aAS S a A S A→SbA S b A a A→SS A→ba S a A S S b A a a b a SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa

最左（最右）推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型

问题：一个句型是否对应唯一的一棵语法树？

例：G[E]: E → i E → E+E E → E*E E → (E) E E + E E * E i i i E E * E 推导1：E  E+E  E*E+E  i*E+E  i*i+E  i*i+i 推导2：E  E*E  i*E  i*E+E  i*i+E i*i+i

二义文法 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。

二义文法 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。 二义文法改造为无二义文法 G[E]: E → i G[E]：E → T|E+T E → E+E T → F|T*F E → E*E F → （E）|i E → (E) 规定优先顺序和结合律

句型的分析 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。

句型的分析 分析算法可分为： 自上而下分析法： 从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 自下而上分析法： 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程

自上而下的语法分析 例：文法G：S → cAd A → ab A → a 识别输入串w=cabd是否该文法的句子 S S S c A d c A d a b 推导过程：S  cAd  cabd

自下而上的语法分析 例：文法G：S → cAd A → ab A → a 识别输入串w=cabd是否该文法的句子 S A A c a b d c a b d c a b d 规约过程：S  cAd  cabd

句型分析的有关问题 1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：V→A1|A2|…|An，那么如何确定用哪个右部去替代V？ 2）如何识别可归约的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”

句型分析 短语、直接短语、句柄的定义：文法G[S]， S αAδ且A b则称b是句型αbδ相对于非终结符A的短语。若有A  b则称b是句型αbδ相对于该规则A → b的直接短语。一个句型的最左直接短语称为该句型的句柄。

句型分析 E F T T F F i1 * i2 + i3 短语： 直接短语： 句柄： G[E]：E→E+T|T T→T*F|F F→(E)|i 句型：i*i+i

有关文法实用中的一些说明 有关文法的实用限制 上下文无关文法中的ε规则

有关文法的实用限制 文法中不得含有有害规则和多余规则 有害规则：形如U→U的产生式。会引起文法的二义性 多余规则：指文法中任何句子的推导都不会用到的规则 1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达 2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的

有关文法的实用限制 对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件： 1）A必须在某句型中出现。 2）必须能从A推出终结符号串t来。 即1）文法G[S]，对 某两个符号串α和δ： S αAδ 2）A t ,t∈VT

化简文法 例：G[S] 1) S→Be S→Be 2) B→Ce B→Af 3) B→Af A→Ae 4) A→Ae A→e 5) A→e 6) C→Cf 7) D→f

上下文无关文法中的ε规则 具有形式A→ε的规则称为ε规则，其中A∈VN 某些著作和讲义中限制这种规则的出现。因为ε规则会使有关文法的一些讨论和证明变得复杂 两种定义的唯一差别是ε句子在不在语言中。

上下文无关文法中的ε规则 如果语言L有一个有穷的描述，则L∪{ε}也同样有一个有穷描述。并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L∪{ε}和L-{ε}分别是上下文有关语言、上下文无关语言和正规语言

上下文无关文法中的ε规则 定理3.1 文法G，任一P中的产生式A→α，都有A∈VN，α∈(VN ∪VT)*,(即α可能为ε)，则L(G)也能这样一种文法产生，任一产生式A→β，只有如下两种形式： A∈VN， β ∈(VN ∪VT)+,(即β≠ε) 或者 S→ε且 S不出现在任何产生式右边

上下文无关文法中的ε规则 定理3.2 G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边。 若G为上下文无关文法或正规文法，类似结论成立。

有关文法的一些关系 一般来说，一个集合上的（二目）关系就是某一性质，此性质对集合中的任意两个有序符号来说，或者满足，或者不满足。所定义的符号和 是符号串之间的两个关系。 我们习惯采用中缀表示法表示关系，即如果在集合中的两个元素c和d之间满足某一关系，我们就记作cRd。

R+， R* 集合A上的一关系R,a,b,c是A的元素。 若 cRc,称R为自反的.若由aRb能得到 bRa 则称R为对称的。若由aRb和 bRc能得到 aRc 则称R为传递的。 给定任一关系R，我们定义一个新的关系 R+，称为R的传递闭包。 aR1b  aRb aR+b c:aRc且 cRi-1b,i1 R*，称为R的自反传递闭包

FIRST集和FOLLOW集 设G=(VN , VT , S,P)是上下文无关文法 FIRST（）={a| a,a∈VT, , ∈V*} 若 ε则规定ε∈FRIST（）。 FOLLOW（A）={aS  A 且a ∈ FRIST（）， ∈V*， ∈V+ } 若S u A  ,且 ε，则#∈FOLLOW(A)。

1.若XV,则FIRST(X)={X}. 2.若XVN,且有产生式Xa…，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中. 3.若XY…是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X  Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且对于任何j,1≤j ≤i-1,FIRST(Yj)都含有(即Y1..Y(i-1)  ),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,…,K)均含有,则把加到FRIST(X)中.

FOLLOW 1.对于文法的开始符号S,置#于FOLLOW(S) 中; 2.若Ａα B β是一个产生式,则把  FIRST(β)\{}加至FOLLOW(B)中; 3.若Ａα B是一个产生式,或ＡαBβ是  一个产生式而β (即FIRST(β)），  则把FOLLOW（A），加至FOLLOW（B）中．

作业 3。8练习 题5 ，8，9，14，16 验证L(G)是匹配的括号串 G: S→ (S)S| 