第四章 文法和语言 本章目的 为语言的语法描述寻求工具 第四章 文法和语言 本章目的 为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读） 形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述

本章知识点(内容) 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明 引言和预备知识 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明

文法的直观概念和语言概述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是 由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的EBNF来表示这种句子的构成规则：

“我是大学生”。是汉语的一个句子 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他 〈名词〉∷=王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉

有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成： 〈句子〉  〈主语〉〈谓语〉， 然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉， 那么得到：〈主语〉〈谓语〉  〈代词〉〈谓语〉， 重复做下去， 句子：“我是大学生”的全部动作过程是： 〈句子〉  〈主语〉〈谓语〉  〈代词〉〈谓语〉  我〈谓语〉 我〈动词〉〈直接宾语〉   我是〈直接宾语〉 我是〈名词〉 我是大学生

“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。

英语句子 sentence –> <subject> <verb-phrase> <object> subject –> This | Computers | I verb-phrase –> <adverb> <verb> | <verb> adverb –> never verb –> is | run | am | tell object –> the <noun> | a <noun> | <noun> noun –> university | world | cheese | lies This is a university. Computers run the world. I am the cheese. I never tell lies.

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

研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法 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为产生式(也称规则)的集合； VN，VT和P是 非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，其中α是字母表V的正闭包V+中的一个符号，β是V*中的一个符号。α称为规则的左部，β称作规则的右部。

Define a grammar VT is a set of terminals A grammar G is defined as a 4-tuple (VN，VT，P，S ) VN is a set of nonterminals VT is a set of terminals P is a set of productions，each production consists of a left side,an arrow(or ‘::=‘),and a right side S is a designation of one of the nonterminals as the start symbol V =VN ∪ VT is the alphabet of G

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

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

文法的写法 1 G：S→aAb A→ab A→aAb A→ε 2 G[S]： A→ab A→aAb A→ε S→aSb 3 G[S]： A→ab |aAb |ε S→aSb

元符号: → ∷= | < > 习惯表示 大写字母：终结符 小写字母：非终结符 S –> AB A –> Ax | y B –> z

推导的定义 直接推导“” α→β是文法G的产生式，若有v,w满足：v=γαδ,w= γβδ, 其中γ∈V*,δ∈V* 例：G： S→0S1， S→01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1

<程序><分程序>. <分程序>.  <变量说明部分> <语句>. VAR<标识符>;BEGIN READ(<标识符>)END.  VAR A;BEGIN READ(<标识符> ) END.

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

例：G： S→0S1， S→01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S =>+ 00001111 S =>* S 00S11 =>* 00S11

What are Derivations Derivation is a way that a grammar defines a language .In the process of derivation a production is treated as a rewriting rule in which the nonterminal on the left side is replaced by the string on the right side of the production A production u –> v is used by replacing an occurrence of u by v . Formally, if we apply a production p Î P to a string of symbols w in V to yield a new string of symbols z in V, we say that z derived from w using p, written as follows: w =>p z . We also use: w => z z derives from w (production unspecified) w =>* z z derives from w using zero or more productions w =>+ z z derives from w using one or more productions

句型、句子的定义 句型 句子 例：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的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01

例：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}

例 文法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生成

使用产生式(1)n-1次，得到推导序列： S =>* an-1S(BE)n-1，然后使用产生式(2)一次，得到：S =>* an-1S(BE)n-1  an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3, aaaBEBEBE  aaaBBEEBE  aaaBBEBEE  aaaBBBEEE。即有： S =>* anBnEn 接着，使用产生式(4)一次，得到S =>* anbBn-1En，然后使用产生式(5)n-1次得到： S =>* anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S =>* anbnen 也能证明，对于n≥1，串anbnen是唯一形式的终结符号串

文法的等价 若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

A hierarchy of grammars Type 0: free or unrestricted grammars These are the most general. Productions are of the form u –> v where both u and v are arbitrary strings of symbols in V, with u non-null. There are no restrictions on what appears on the left or right-hand side other than the left-hand side must be non-empty. Type 1: context-sensitive grammars Productions are of the form uXw –> uvw where u , v and w are arbitrary strings of symbols in V, with v non-null, and X a single nonterminal. In other words, X may be replaced by v but only when it is surrounded by u and w . (i.e. in a particular context).

Type 2: context-free grammars Productions are of the form X–> v where v is an arbitrary string of symbols in V, and X is a single nonterminal. Wherever you find X, you can replace with v (regardless of context). Type 3: regular grammars Productions are of the form X–> a or X–> aY where X and Y are nonterminals and a is a terminal. That is the left-hand side must be a single nonterminal and the right-hand side can be either a single terminal by itself or with a single nonterminal. These grammars are the most limited in terms of expressive power.

文法的类型 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD

文法的类型 例：2型（上下文无关）文法 文法G[S]： S→AB A→BS|0 B→SA|1

3型文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 G[I]： I → lT I → l T → lT T → dT T → l T → d

文法的类型 四种文法之间的逐级“包含”关系 0型文法 2型文法 1型文法 3型文法

文法和语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为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型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合

3型文法产生的语言是有穷自动机（FA）所接受的集合. 定理 设G=（VN，VT，P，S）是3型文法，则存在一个有穷自 动机 M=(K, ∑ , f, A, Z)，使得L(M)=L(G) 有穷自动机NFA M 这样构造： · ∑= VT · K= VN ∪{N}, N为一个新状态,它不在VN中 · A=S · Z={N} · 对G中的形如 D→tB的产生式,t为终结符或ε,有f(D,t)=B； 对G中形如D→t的产生式， t为终结符或ε,有f(D,t)=N;   对VT中的每一个a ,有f(N,a)=φ

G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b  D→aD|bD|a|b a a A a S b a a b D Z

定理 已知一有穷自动机M= (K, ∑ , f, A, Z),存在有一个3型文法G = （VN，VT，P，S）,使得L(G)=L(M) · VT =∑ · VN= K · S = A · 若 f(D,t)=B ，则D→tB在P中 若 f(D,t)=B ，且B在Z中，则D→t在P中

G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b  a A a a S b b B D b

正规文法和正规式 对上的正规式r ,存在一个RG=(VN,VT,P,S)：L(G)=L(r) 初始， VT= ,S  VN ，生成正规产生式 Sr (R.1) 对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R 2)对形如Arr1的正规产生式： ArB Ar1 BrB Br1 BVN (R 3)对形如Ar1r2的正规产生式: Ar1 A r2 不断应用R做变换，直到每个产生式右端至多有一个VN

例 r=a(ad) Sa(ad) SaA A(ad) A(ad)B A B(ad)B B G[s]: SaA A VT={a,d} AaB VN={S,A,B} AdB BaB BdB B

正规文法和正规式 对G=(VN,VT,P,S),存在一个 =VT上的正规式r : L(r)=L(G) AxB , By ≈ A=xy AxAy ≈ A=xy Axy ≈ A=xy

正规文法和正规式 G[s]:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a =a((ad)(ad)) =a((ad)) R=a(ad)

上下文无关文法及其语法树 上下文无关文法有足够的能力描述程序设计语言的语法结构 语法树---句型推导的直观表示

例文法G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P为： {E→i , E→E+E , E→E*E , E→(E) } E表示算术表达式, i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即： 变量是算术表达式；若E1和E2是算术表达式，则E1+ E2，E1*E2和(E1)也是算术表达式 描述一种简单赋值语句的产生式： 〈赋值语句〉→i∶=E 描述条件语句的产生式： 〈条件语句〉→if〈条件〉then〈语句〉｜ if〈条件〉then〈语句〉else〈语句〉

句型、推导 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 EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a

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

语法树 设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）： 3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN 4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式 语法树的结果： 从左到右读出叶子的标记而构成的行谓之  

语法树---句型推导的直观表示 给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树) 定理：

构造语法树 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 E E E + T E + T T E E + T F

EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a E E + T T T * F F F a a a 看不出句型中的符号被替代的顺序

用于描述上下文无关文法句型推导的直观方法 上下文无关文法的语法树的用处 用于描述上下文无关文法句型推导的直观方法 句型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[S]的句型。也把该推导树称为该句型的语法树。

上下文无关文法的语法树 推导过程中施用产生式的顺序 例: 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 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。 二义文法改造为无二义文法 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 cAd  cabd

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

(1)S → cAd (2) A → ab (3)A → a 识别输入串w=cabd是否为该文法的句子 自上而下的语法分析 若S  cAd 后选择(3)扩展A，S  cAd  cad 那将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配 ？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子） -显然是错误的结论。 导致失败的原因是在分析中对A的选择不是正确的。 S c A d a

(1)S → cAd (2) A → ab (3)A → a 识别输入串w=cabd是否为该文法的句子 自下而上的语法分析 对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道cabd是一个句子 c a b d c A b d a

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

刻画“可归约串” 文法G[S] 句型的短语 S =>* αAδ且 A =>+ β，则称β是句型αβδ相对于非终结符A的短语 句型的直接短语 若有A  β，则称β是句型αβδ相对于非终结符A 的直接短语 句型的句柄 一个句型的最左直接短语称为该句型的句柄

例i*i+i 例 ：i*i+i 的短语、直接短语和句柄 G[E]：E→E+T|T T→T*F|F F→(E)|i 句型：i*i+i E E + T T F T * F i3 短语：i1* i2+ i3， i1* i2 ， F i2 i1 ， i2 ， i3 。 i1 直接短语： i1 ， i2 ， i3 。句柄： i1

左递归规则-- G[S]: S→Sa   S→b L={ban | n≥0} W=baaa S b S S a

左递归 关于非终结符P的规则 直接左递归 若 P → P α| β α、β ∈V*且β不以P开头 一般 左递归 若 P =>* P α S→Aa A→Sb …

消除左递归 消除直接左递归 形如：P → P α| β α非，不以P打头 改写为：P → βQ Q → αQ| 

消除左递归 例:E → E+T|T T →T*F|F F →(E)| a G[ E]: (1) E → TE’ (2) E’ → +TE’ (3) E’ →  (4) T → FT’ (5) T’ → *FT’ (6) T’ →  (7) F → (E) (8) F →a

消除一般左递归要求文法: 1.无回路(A(=>+(A) 2.无空产生式 （1） .以某种顺序将文法非终结符排列A1 ,A2 …An （2） for i:=1 to n do begin for j:=1 to i-1 do 用Ai-->1| 2r…|  k r替代 形如Ai--> Ajr的规则,其中 Aj--> 1| 2…| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; （3）化简由2得到的文法

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

对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件： 1. A必须在某句型中出现 即有S =>* αAβ，其中α，β属于V* 2. 必须能够从A推出终结符号串t来 即A =>* t，其中t∈VT*

产生式 2），6），7）为多余规则应去掉。 化简文法 例：G[S] ： 1) S→Be 2) B→Ce D为不可到达 3) B→Af C为不可终止 4) A→Ae 5) A→e 6) C→Cf 7) D→f 产生式 2），6），7）为多余规则应去掉。

上下文无关文法中的ε规则 上下文无关文法中某些规则可具有形式A→ε，称这种规则为ε规则 因为ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现 两种定义的唯一差别是ε句子在不在语言中 文法构思的启示是要找出语言的有穷描述，而如果语言L有一个有穷的描述，则L1=L∪｛ε｝也同样有一个有穷的描述，并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L∪｛ε｝和L-｛ε｝分别是上下文有关语言、上下文无关语言和正规语言。

思考 本章目的为语言的语法描述寻求工具,以便： 1.什麽是文法,什麽是它的语言? 2.我们为什麽关注上下文无关文法? 对源程序给出精确无二义的语法描述。（严谨、简洁、易读） 根据语言文法的特点来进行语法分析 从描述语言的文法可以自动构造出可用的分析程序 制导语义翻译 1.什麽是文法,什麽是它的语言? 2.我们为什麽关注上下文无关文法? 3.语法分析方法的分类?

[本章小结] 3.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。 1.本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论. 2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的 “形式”的含义—只涉及语言的语法不涉及语言的语义. 3.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。

[本章小结] 考察本章知识点最典型的题目是 1.已知文法G[A]，写出它定义的语言描述 如：G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 答案:G[A]定义的语言由0、1符号串组成，串中0和1的个数相同. 2.给出语言描述，构造文法. 如：构造一文法,其定义的语言是由算符+, *, (,)和运算对象a构成的算术表达式的集合. 答案1: G[E] E→E+T|T T→T*F|F F→(E)|a 答案2: G[E] E→E+E|E*E|(E)|a

相关术语的回顾（英文版） 上下文无关文法 A context free grammar(grammar for short) consists of terminals ,nonterminals,a start symbol,and productions. Terminals are the basic symbols from which strings are formed. Nonterminals are syntactic variables that denote sets of strings that help define the language generated by the grammar. In a grammar,one nonterminal is distinguished as the start symbol,and the set of strings it denotes is the language defined by the grammar. The productions of a grammar specify the manner in which the terminals and nonterminals can be combined to form string.

句型句子和语言 Given a grammar G with start symbol S,we can use the =>* relation to define L(G),the language generated by G. Strings in L(G) may contain only terminal symbols of G. We say a string of terminals w is in L(G) if and only if S =>* w .The string w is called a sentence of G. If S =>* α,wher α may contain nonterminals then we say that α is a sentential form of G

验证文法生成的语言 A proof that a grammar G generates a language L has two parts:we must show that every string generated by G is in L,and coversely that every string in L can indeed be generated by G.

语法树和推导 A parse tree may be viewed as a graphical representation for a derivation that filt out the choice regarding replacement order. The leaves of the parse tree are labeled by nonterminals or terminals and ,read from left to right,they constitute a sentential form,called the yield or frontier of the tree.

句型分析，语法分析 Parsing is the process of determing if a string of token can be generated by a grammar. Most parsing methods fall into one of two classes,called the top-down and bottom-up methods. These terms refer to the order in which nodes in the parse tree are constructed.In the former,construction starts at the root and proceeds towards the leaves,while,in the later,construction starts at the leaves and proceeds towards the root.

二义性 A grammar that produces more than one parse tree for some setence is said to be ambiguous. Put another way, an ambiguous grammar is one that produces more than one leftmost or more than rightmost derivation for the same sentence. Sometimes an ambiguous grammar can be rewritten to eliminate the ambiguity. For exmple suitable grammars for expression can often be constructed using associativity and precedence information ,as in the slide74

消除左递归规则 A grammar is left recursive if it has a nonterminal A such that there is a derivation A =>+ Aα for some string α. A left-recursive production is like:A →Aα in which the leftmost symbol on the right side is the same as the nonterminal on the left side. The general case is that a nonterminal A with two productions A →Aα| β where αand β are sequences of terminals and nonterminals that do not start with A. And the left recursive pair of productions A →Aα| β could replaced by the non-left-recursive productions: A →β A’ A’ →αA’| ε Here A’ is a new nonterminal. The production A’ →αA’ is right recursive.

练习 1. 写一文法，使其语言是偶正整数的集合。 要求： 允许0打头 (2) 不允许0打头 2.证明下述文法G［〈表达式〉］是二义的。 允许0打头 (2) 不允许0打头  2.证明下述文法G［〈表达式〉］是二义的。 〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/   3. 令文法G［E］为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

练习 4. 给出生成下述语言的上下文无关文法： （1）{ anbnambm| n，m>=0} (2) { 1n0m 1m0n| n，m>=0} 5. 给出生成下述语言的三型文法： (1) { anbm|n,m>=1 } (2){anbmck|n,m,k>=0 }   6. 给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0