new文法和语言.ppt

第三章第三章 文法和语言文法和语言 一个程序设计语言是一个记号系统，它的完整定义包括两个方面：一个程序设计语言是一个记号系统，它的完整定义包括两个方面：§语法语法－是指－是指一组规则一组规则，应用这组规则可以形成和产生一个合适的，应用这组规则可以形成和产生一个合适的程序通常用程序通常用上下文无关文法上下文无关文法作为描述语法的工具作为描述语法的工具.§语义语义：程序设计语言的语义分为两种：：程序设计语言的语义分为两种： 1）静态语义－－是一系列限定规则，并确定哪些合乎语法的）静态语义－－是一系列限定规则，并确定哪些合乎语法的程序是合适的；程序是合适的； 2）动态语义（运行语义或执行语义）－－表明程序要做什么）动态语义（运行语义或执行语义）－－表明程序要做什么，要计算什么，要计算什么. 主要内容：主要内容：文法和语言、上下文无关文法、句型分析等文法和语言、上下文无关文法、句型分析等例如：赋值语句：例如：赋值语句：A=B+C 合法；合法；A=B+  非法；语义则匹配类型非法；语义则匹配类型1§ 3.1 文法的直观概念文法的直观概念文法的直观认识：文法的直观认识：如何给出语言的有穷表示？如何给出语言的有穷表示？ 语言是由句子组成的，因此，可以用一些规则说明或定义句子的语言是由句子组成的，因此，可以用一些规则说明或定义句子的组成结构。

组成结构例如：我是大学生例如：我是大学生<句子句子>::=<主语主语><谓语谓语><主语主语>::=<代词代词>|<名词名词> <代词代词>::=我我|你你|他他<名词名词>::=王明王明|大学生大学生|工人工人|英语英语<谓语谓语>::=<动词动词><直接宾语直接宾语><动词动词>::=是是|学习学习<直接宾语直接宾语>::=<代词代词><名词名词>这些规则成为判别句这些规则成为判别句子结构合法与否的依子结构合法与否的依据据.这些规则看成是一这些规则看成是一种元语言，这样的语种元语言，这样的语言描述称为文法言描述称为文法.2应用规则推导句子：应用规则推导句子：<句子句子>=><主语主语><谓语谓语> =><代词代词><谓语谓语> =>我我<谓语谓语> =>我我<动词动词><直接宾语直接宾语> =>我是我是<直接宾语直接宾语> =>我是我是<名词名词> =>我是大学生我是大学生“=>”的含义是使用一条规则代的含义是使用一条规则代替替=>左边的某个符号并产生左边的某个符号并产生=>右右端的符号串端的符号串.应用这些规则可以产生很多句子应用这些规则可以产生很多句子.这样，使用文法作为工具，不仅定这样，使用文法作为工具，不仅定义了句子的结构，而且通过有穷的规则描述出语言的全部句子义了句子的结构，而且通过有穷的规则描述出语言的全部句子.3字母表是元素的非空有穷集合字母表是元素的非空有穷集合字母表中至少包含一个元素。

字母表中至少包含一个元素字母表中的元素，可以是字母、数字或其他符号字母表中的元素，可以是字母、数字或其他符号3.2 符号和符号串符号和符号串一一. .字母表字母表 alphabet alphabet【例如】【例如】∑∑ = {a,b,c}∑∑是字母表，由是字母表，由a,b,ca,b,c三个元素组成三个元素组成例如】【例如】∑∑’’ = {0,1}∑∑’’是字母表，由是字母表，由0,10,1两个元素组成两个元素组成不同的语言有不同的字母表不同的语言有不同的字母表英文的字母表是英文的字母表是26个字母、数字和标点符号的集合；个字母、数字和标点符号的集合；C语言的字母表是字母、数字和若干专用符号组成语言的字母表是字母、数字和若干专用符号组成任何语言的字母任何语言的字母表指出了该语言表指出了该语言中允许出现的一中允许出现的一切符号4二二.符号（字符）符号（字符）symbol字母表中的元素称为符号，或称为字符字母表中的元素称为符号，或称为字符例如】【例如】∑ = {a,b,c}a,b,c是字母表是字母表∑中的符号中的符号例如】【例如】∑’ = {0,1}0,1是字母表是字母表∑’中的符号中的符号。

5三三.符号串（字）符号串（字）string符号的有穷序列称为字符串符号的有穷序列称为字符串例如】设有字母表【例如】设有字母表 ∑ = {a,b,c}，，则有符号串则有符号串 a,b,ab,ba,cba,abc,…(a,b,ab,ba,cba,abc等都是字母表等都是字母表∑上的符号串上的符号串)符号串总是建立在某个特定字母表上的且只能由字母表上符号串总是建立在某个特定字母表上的且只能由字母表上的的有穷有穷有穷有穷多个符号组成多个符号组成符号串中符号的顺序是很重要的，符号串中符号的顺序是很重要的，如如 ab 和和 ba 是字母表是字母表∑上的两个不同的符号串上的两个不同的符号串不包含任何符号的符号串，称为空符号串，用不包含任何符号的符号串，称为空符号串，用 (epsilon)表表示，即空符号串由示，即空符号串由 0 个符号组成，其长度个符号组成，其长度| |=06r符号串的头尾符号串的头尾：如果z＝xy是一符号串，那么x是z的头，y是z的尾Ø如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固有头r符号串集合：符号串集合：若集合若集合A A中的一切元素都是某字母表中的一切元素都是某字母表上的符号串，则称上的符号串，则称A A为该字母表上的为该字母表上的符号串集合符号串集合。

四四. .符号串的运算－－相关概念符号串的运算－－相关概念例如例如:z＝＝abc，那么，那么z的头是的头是 , a, ab, abc.Z的尾是的尾是 , c, bc, abc.7四四. .符号串的运算符号串的运算1.1.符号串的连接符号串的连接 connection connection设设 x 和和 y 是符号串，则串是符号串，则串 xy 称为它们的连接即称为它们的连接即 xy 是是将将 y 符号串写在符号串写在 x 符号串之后得到的符号串符号串之后得到的符号串例如】设【例如】设 x ＝＝ abc，，y = 10a，，则则 xy ＝＝ abc10a则则 yx ＝＝ 10aabc特别，对任意一符号串特别，对任意一符号串 x 有：有：  x ＝＝ x  ＝＝ x82.符号串的幂运算符号串的幂运算 power设设 x 是符号串，则是符号串，则 x 的幂运算定义为：的幂运算定义为：x0 ＝＝  x1 ＝＝ xx2 ＝＝ xx……xn ＝＝ xx…x = xxn-1 (n>0) n【例如】设【例如】设 x = abc,则则x0 ＝＝  x1 ＝＝ abcx2 ＝＝ abcabc……93.集合的乘积集合的乘积 product设设 A 和和 B 是符号串的集合，则是符号串的集合，则 A 和和 B 的乘积定义为：的乘积定义为：AB = {xy | x ∈ ∈ A, y ∈ ∈ B}即集合即集合 AB 中的符号串是由中的符号串是由 A 和和 B 的符号串连接而成的。

的符号串连接而成的例如】设【例如】设 A = {a,b},B = {c,d}则则 AB ＝＝ {ac,ad,bc,bd}因为对任意一符号串因为对任意一符号串 x 有：有：  x ＝＝ x  ＝＝ x所以，对任意集合所以，对任意集合 A，有，有{ }A = A{ } = A10空集空集Φ empty setΦ 表示不含任何元素的表示不含任何元素的空集空集 { }Φ = { }注意：注意：   是符号串，不是集合，是符号串，不是集合，{ }表示由空符号串表示由空符号串   所所组成的集合，但这样的集合不是空集组成的集合，但这样的集合不是空集Φ，， 即即Φ不包含空串不包含空串   ∈∈ Φ(不属于不属于)－－对任意集合对任意集合 A，有，有 ΦA = AΦ = Φ114.集合的幂运算集合的幂运算设设 A 是符号串的集合，则集合是符号串的集合，则集合 A 的幂运算定义为：的幂运算定义为：A0 ＝＝ { }A1 ＝＝ AA2 ＝＝ AA……An ＝＝ AA…A = AAn-1 (n>0) n【例如】设【例如】设 A = {a,b},则则A0 ＝＝ { }A1 ＝＝ {a,b}A2 ＝＝ AA = {aa,ab,ba,bb}A3 ＝＝ AAA = A2A = {aaa,aab,aba,abb,baa,bab,bba,bbb}……125.集合集合A的正闭包的正闭包A+与闭包与闭包A*设设 A 是符号串的集合，是符号串的集合，则集合则集合 A 的正闭包的正闭包A+和闭包和闭包A*分别定义为：分别定义为：A+ ＝＝ A1 U A2 U A3 U … U An U …A* ＝＝ A0 U A1 U A2 U A3 U … U An U … = { } U A+【例如】设【例如】设 A = {a,b},则则A+ ＝＝ {a,b,aa,ab,ba,bb,aaa,aab,…}A* ＝＝ { ,a,b,aa,ab,ba,bb,aaa,aab,…} 正闭包：正闭包：Positive closure闭包闭包：：Star closure（星闭包）（星闭包）13【例如】设【例如】设 A = {a},则则A+ ＝＝ {a,aa,aaa,……} = {an | n>=1}A* ＝＝ { , a,aa,aaa,……} = {an | n>=0}A* = A0   A1   A2   A3   … ，称，称 A* 是是 A 的的闭包闭包。

A+ = AA* ，称，称 A+ 是是A的的正则闭包正则闭包∑*表示表示∑上的上的所有符号串的全体所有符号串的全体143.3 文法和语言的形式定义1、规则、规则规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如→或 ∷=的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号  称为规则的左部，  称作规则的右部→ 或或 ::= 表示表示“定义为定义为”或或“生成生成”，意，意思是左部符号用右部符号串定义或左部符思是左部符号用右部符号串定义或左部符号生成右部符号串号生成右部符号串152 、文法定义定义文法G定义为四元组(VN，，VT，，P，，S )其中VN:非终结符号(或语法实体，或变量)集；VT:终结符号集；P: 规则的集合；     VN，，VT和P是 非空有穷集  S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现 VN和VT不含公共的元素，即VN ∩ VT = φφ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如→或 ∷=的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。

  称为规则的左部，  称作规则的右部16例例 文法文法G=（（VN，，VT，，P，，S））VN = { S }, VT ={ 0, 1 }P={ S→→0S1, S→→01 }S为开始符号为开始符号17例例 文法文法G=（（VN，，VT，，P，，S））VN ={标识符，字母，数字标识符，字母，数字}VT ={a,b,c,…x,y,z,0,1,…,9}P={<标识符标识符>→→<字母字母> <标识符标识符>→→<标识符标识符><字母字母> <标识符标识符>→→<标识符标识符><数字数字> <字母字母>→→a … <字母字母>→z→z <数字数字>→0→0 … … <数字数字>→9→9 }S=<标识符标识符>18文法的写法文法的写法 元元符号: → ∷= | → ∷= | < > 习惯习惯 大写字母表示非终结符大写字母表示非终结符 小写字母表示终结符小写字母表示终结符(1) G(1) G：：S→aAS→aAb A→ab A→ab A→aA A→aAb A→ε A→ε (2) G[S] (2) G[S]：： A→ab A→ab A→aA A→aAb A→ε A→ε S→aS S→aSb (3) G[S]:A→ab |aA(3) G[S]:A→ab |aAb |ε |ε S→aSS→aSb19推导的定义推导的定义直接推导直接推导“”α→βα→β是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=γαδ,w= γβδ, v=γαδ,w= γβδ, 其中其中γ∈Vγ∈V* *,δ∈V,δ∈V* * 则称则称v v直接直接推导推导到到w,w,记作记作 v v  w w 也称也称w w直接直接归约归约到到v v例：例：G G：： S→→0S1，， S→→01    0S1 00S11    00S11 000S111    000S111 00001111 S 0S120推导推导<程序程序><分程序分程序>. (<程序程序>  <分程序分程序>. )<分程序分程序>.  <变量说明部分变量说明部分>     <语句语句>.                                (<分程序分程序>  <变量说明部分变量说明部分>     <语句语句>) VAR<标识符标识符>;BEGIN READ(<标识符标识符>)END.                                VAR A;BEGIN READ(<标识符标识符> ) END.                               (<标识符标识符> A)VAR A;BEGIN READ(<标识符标识符> ) END.                                VAR A;BEGIN READ( A) END.                               (<标识符标识符> A)21 若存在若存在v =w0 w1 ... wn=w,(n>0)  则记为则记为v    w，称作，称作v推导出推导出w，或，或w归约到归约到v  若有若有v     w 或或 v=w，，  则记为则记为v     w推导的定义推导的定义+=>+=>*=>22例：例：G G：： S→→0S1，， S→→010S1 00S1100S11 000S111000S111 00001111  S 0S1 00S11 000S111 00001111  S 00001111 S S 00S11 00S11+=>*=>*=>23句型、句子的定义句型、句子的定义z句型句型有文法有文法G，若，若S =>* x，则称，则称x是文法是文法G的句型。

的句型z句子句子有文法有文法G，若，若S =>* x，且，且x∈V∈VT T* *，则称，则称x是文法是文法G的句子例：例：G G：： S→→0S1，， S→→01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001111G的句子00001111, 0124句型、句子句型、句子例：例：G[E E]：： E→E+T|TE→E+T|T T→T*F|F T→T*F|F F→(E)|a F→(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符号句子：用符号a，，+，，*，，(和和)构成的算术表达式构成的算术表达式25(文法生成的文法生成的)语言的定义语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的的一切句子的集合一切句子的集合: L(G)={x|S =>* x，其中，其中S为文法的开始为文法的开始符号，且符号，且x ∈V∈VT T* *} 例：例：G G：： S→→0S1，， S→→01 L(G)={0n1n|n≥≥1}26例例 文法文法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 } G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成根据1式进行n-1次得到an-1 S（（BE））n-1 由2式an(BE)n由3式得到anBnEn由4式得anbBn-1En由5式n-1次得到anbnEn由6式1次，7式n-1次得到anbnen27文法的等价文法的等价z若若L（（G1））=L（（G2），则称文法），则称文法G1和和G2是是等价的。

等价的如文法如文法G G1[A][A]：：A→DB A→DB 与与G G2[S][S]：：S→0S1 S→0S1 等价等价 A→DE S→01 A→DE S→01 E→AB E→AB D→0 D→0 B→1 B→128【例】设计一个表示所有标识符的文法【例】设计一个表示所有标识符的文法分析：标识符的定义是字母或以字母开头的字母数字串，分析：标识符的定义是字母或以字母开头的字母数字串，其结构如下：其结构如下：字母字母字母或数字字母或数字串串用用 I 表示标识符，表示标识符，L 代表字母，代表字母，D 代表数字，则定义标代表数字，则定义标识符的文法为：识符的文法为：G =（（VN，，VT，，P，，S））其中：其中：VN = {I,L,D}VT = {a,b,…,x,y,z,0,1,2,…,9}P = { I→L | IL |ID L→ a | b | … | x | y | z D→ 0 | 1 | … |9 }S = I29【例】用文法定义一个含【例】用文法定义一个含+、、*的算术表达式。

的算术表达式变量是表达式；变量是表达式；若若 E1 和和 E2 是算术表达式，则是算术表达式，则 E1+E2，，E1*E2，，(E) 也是算也是算术表达式术表达式算术表达式的文法为：算术表达式的文法为：G =（（VN，，VT，，P，，S））其中：其中：VN = {E}VT = {i,+,*,(,)}P = { E →i | E+E | E*E |(E) }S = E30【例】设字母表【例】设字母表∑＝＝{a,b}，设计一个文法，描述，设计一个文法，描述语言语言 L={abna | n 0}分析：该语言中符号串的结构特征是：分析：该语言中符号串的结构特征是：当当 n=0L = {aa}(b0= )当当 n=1L = {aba}当当 n=2L = {abba}…L = {aa,aba,abba,abbba,…}语言的文法为：语言的文法为：G =（（{A,B}，，{a,b}，，P，，A））其中其中P为：为：A→aBaB→   |Bb31【例】描述语言【例】描述语言L={abna | n 0}的的等价文法等价文法（（1））A→aBaB→   |Bb（（2））A→aBaB→   |bB（（3））A→aBB→ a |bB（（4））A→BaB→ a |Bb32【例】设有文法【例】设有文法G[S]: S→01 | 0S1→01 | 0S1求该文法所描述的语言求该文法所描述的语言分析：分析：问题归结为由识别符号问题归结为由识别符号 S 出发，将推导出什么样的句子，出发，将推导出什么样的句子，也就是说也就是说 L(G{S])是由一些什么样的符号串所组成的集合，是由一些什么样的符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。

找出其中的规律，用式子或自然语言描述出来应用第二个规则应用第二个规则 n-1 次，然后再使用第一个规则次，然后再使用第一个规则 1 次，次，有有S=>0S1=>00S11=>000S111=>…=>0n－－1S1n－－1=>0n1n即即S > 0n1n所以此文法定义的语言为所以此文法定义的语言为 L(G[E]) = {0L(G[E]) = {0n n1 1n n | | n n   0 0} }+=33【例】设有文法【例】设有文法G[S]: S→0S|1S|→0S|1S|  求该文法所定义的语言求该文法所定义的语言该文法所确定的语言为该文法所确定的语言为L(G[S]) = { ,0,1,00,01,10,11,…} = { x | x∈{0,1}∈{0,1}* * }34【例】设有文法【例】设有文法G[A]: A→yB,B→xB|x→yB,B→xB|x求该文求该文法所定义的语言法所定义的语言从从开始符号开始符号 A 出发，我们可以推出如下句子：出发，我们可以推出如下句子：A => yB => yxA => yB => yxB =>yxx ……A => yB => yxB => … => yx…x归纳得出从归纳得出从 A 出发可推导出所有以出发可推导出所有以 y 开头后跟一个或任开头后跟一个或任意多个意多个 x 得字符串，即得字符串，即L(G[A]) = { yxn | n 1 }35【例】考虑文法【例】考虑文法 G1:S → A BA → a A | aB → b B | b 我们可以分析得出我们可以分析得出 L(G1) = { am bn | m, n≥1}【例】构造一个文法【例】构造一个文法 G2 使使L(G2) = { an bn | m, n≥1}G2 和和 G1 的区别在于，的区别在于，G2 的每个句子中的每个句子中 a 和和 b 的个数的个数必须相同。

必须相同我们可以写出文法我们可以写出文法 G2:S →a S b | a b【例】【例】36【例】设字母表【例】设字母表∑＝＝{a,b},试设计文法，描述语试设计文法，描述语言言 L={a2n,b2n | n 1}分析：设计文法来描述一个语言，关键是设计一组规则生分析：设计文法来描述一个语言，关键是设计一组规则生成语言中的符号串成语言中的符号串设计语言的文法，必须分析这个语言是由怎样一些符号串设计语言的文法，必须分析这个语言是由怎样一些符号串组成，即首先分析语言中符号串的结构特征：组成，即首先分析语言中符号串的结构特征：当当 n=1L = {aa,bb}当当 n=2L = {aaaa,bbbb}当当 n=3L = {aaaaaa,bbbbbb}…L = {aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}语言语言 L 是由偶数个是由偶数个 a，偶数个，偶数个 b 这样的符号串组成的集这样的符号串组成的集合373.4 文法的类型文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将将文法分为四种类型：文法分为四种类型：0型文法：对任一产生式型文法：对任一产生式α→βα→β，都有，都有α∈(Vα∈(VN N∪V∪VT T) )+ +，， β∈(V β∈(VN N∪V∪VT T) )* *1 1型文法：型文法：对任一产生式对任一产生式α→βα→β，都有，都有|β|≥|α||β|≥|α|，， 仅仅仅仅 S→ε S→ε除外除外2 2型文法：型文法：对任一产生式对任一产生式α→βα→β，都有，都有α∈Vα∈VN N 3 3型文法：型文法：任一产生式任一产生式α→βα→β的形式都为的形式都为A→aBA→aB或或A→aA→a，其中，其中A∈VA∈VN N ，，B∈VB∈VN N ，，a∈Va∈VT T * *38文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法G[S]G[S]：： S→CD S→CDAb→bAAb→bA C→aCA C→aCABa→aBBa→aB C→bCB C→bCBBb→bBBb→bBAD→aDAD→aD C→a C→aBD→bDBD→bD D→b D→bAa→bDAa→bD39文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法G[S]：： S→AB→ABA→BS|0→BS|0B→SA|1→SA|1403 3型文法型文法G[S]：： S→0A|1B|0→0A|1B|0A→0A|1B|0S→0A|1B|0SB→1B|1|0→1B|1|0G[I]：：I → lT→ lTI → l→ lT → lT→ lTT → dT→ dTT → l→ lT → d→ d41文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四类四类文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法42文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG ））产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL））2 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG ））产生的语言产生的语言称为称为2型语言型语言或上下文无关或上下文无关语言（语言（ CF L ）） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG ））产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（正规）语言（语言（ RL ）） 43文法和语言文法和语言 四种文法之间的关系四种文法之间的关系 是将产生式做进一步是将产生式做进一步限制而定义的。

限制而定义的 语言之间的关系依次：有不是上下文有关语言之间的关系依次：有不是上下文有关语言的语言的0型语言，有不是上下文无关语言的型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语型语言，有不是正则语言的上下文无关语言44根据形式语言理论根据形式语言理论,文法和识别系文法和识别系统间有这样的关系统间有这样的关系 0型文法（短语结构文法）的能力相当于图型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且灵机，可以表征任何递归可枚举集，而且任何任何0型语言都是递归可枚举的型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形型文法（上下文有关文法）：产生式的形式为式为αα1 1AαAα2 2→α→α1 1βαβα2 2，即只有，即只有A A出现在出现在αα1 1和和αα2 2的上下文中时，才允许的上下文中时，才允许ββ取代取代A A其识别系统是线性界限自动机别系统是线性界限自动机45 带带     a0   a1   a2     a3    a4    a5   a6    a7    a8    …   an-1  an    有限控制器有限控制器磁头磁头任何能用图灵机描述的计算都能机械实现，任何能在现任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述代计算机上实现的计算都能用图灵机描述46 2型文法（上下文无关文法型文法（上下文无关文法CFG）：产生式）：产生式的形式为的形式为A→βA→β，，ββ取代取代A A时与时与A A的上下文无的上下文无关。

其识别系统是不确定的下推自动机其识别系统是不确定的下推自动机 3型文法（正规文法型文法（正规文法RG）：产生的语言是）：产生的语言是有穷自动机（有穷自动机（FA）所接受的集合）所接受的集合47 3型文法产生的语言是有穷自动机（型文法产生的语言是有穷自动机（FA）所接）所接受的集合受的集合.定理定理 设设G=（VN，VT，P，S）是3 3型文法，则存在一个有穷自型文法，则存在一个有穷自 动机动机 M=(K, ∑ , f, A, Z) M=(K, ∑ , f, A, Z)，使得，使得L(M)=L(G)L(M)=L(G)有穷自动机有穷自动机NFA M NFA M 这样构造：这样构造：· ∑= · ∑= VT· K= · K= VN ∪{N}, NN}, N为一个新状态为一个新状态, ,它不在它不在VN中· A=S · A=S · Z={N} · Z={N} · · 对对G G中的形如中的形如 D→tB D→tB的产生式的产生式,t,t为终结符或为终结符或ε,ε,有有f(D,t)=Bf(D,t)=B；； 对对G G中形如中形如D→tD→t的产生式，的产生式， t t为终结符或为终结符或ε,ε,有有f(D,t)=N;f(D,t)=N;    对对VT中的每一个a ,有有f(N,a)=f(N,a)=φφ483型文法型文法 和 有穷自动机（有穷自动机（FA））G［Ｓ］：       S→aA|bB      A→bB|aD|a      B→aA|bD|b      D→aD|bD|a|bBASaaabbba,bDZabab493型文法型文法 和 有穷自动机（有穷自动机（FA））定理定理 已知一有穷自动机M= (K, ∑ , f, A, Z),存在有一个3型文法G = （VN，VT，P，S）,使得L(G)=L(M)G 的定义：· VT =∑ · VN= K· S = A· 若 f(D,t)=B ，则D→tB在P中 若 f(D,t)=B ，且B在Z中，则D→t在P中503型文法型文法 和 有穷自动机（有穷自动机（FA））G［Ｓ］：       S→aA|bB      A→bB|aD|a      B→aA|bD|b      D→aD|bD|a|bDBASaaabba,bb51正规文法和正规式 对上的正规式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.x)做变换，直到每个产生式右端至多有一个VN52例 r=a(ad)(1) Sa(ad)(2) SaA A(ad) (3)A(ad)B A(4) B(ad)B(5) B G[s]: SaA A VT={a,d} AaBVN={S,A,B} AdB BaB BdB B53正规文法和正规式 对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y54正规文法和正规式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)553.5 上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的上下文无关文法有足够的能力描述程序设计语言的语法结构语法结构语法树语法树---句型推导句型推导的的直观表示直观表示56语法树语法树---句型推导句型推导的的直观表示直观表示 (句型、推导)G[E E]：： E→E+T|TE→E+T|T T→T*F|F T→T*F|F F→(E)|a F→(E)|aE 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*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a57语法树语法树设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1. 每个结点都有一个标记，此标记是V的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成的行谓之 58上下文无关文法的语法树上下文无关文法的语法树z句型句型aabbaa的可能的可能推导序列和语法树推导序列和语法树  例例: G[S]:S→→aASA→→SbAA→→SSS→→aA→→ba                         S             a          A             S               S        b      A      a               a             b      aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa59语法树语法树---句型推导句型推导的的直观表示直观表示给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何句型都能的任何句型都能构造与之关联的语法树构造与之关联的语法树(推导树推导树)定理：定理：   G为上下文无关文法，对于α≠ε，有S =>* α，当且仅当文法G有以α为结果的一棵语法树(推导树)60规范推导规范推导 规范句型规范句型z最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步ααββ，其中，其中αα、、ββ是句型，都是对是句型，都是对αα中中的最左（右）非终结符进行替换的最左（右）非终结符进行替换z最右推导被称为规范推导。

最右推导被称为规范推导z由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型61z一棵一棵语法法树表示了一个句型的种种可能的表示了一个句型的种种可能的( (但未必是所有的但未必是所有的) )不同推不同推导过程，包括最左程，包括最左( (最右最右) )推推导z但是，一个句型是否只但是，一个句型是否只对应唯一的一棵唯一的一棵语法法树呢呢? ?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左( (最右最右) )推推导呢呢? ?62例：例：G‘[E]:G‘[E]:E → iE → iE → E+EE → E+EE → E*EE → E*EE → (E)E → (E) E E E + E E + E E * E i E * E i i i i i E E E * E E * E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导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+i63二义文法二义文法z若一个文法存在某个句子对应两棵不同的若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是语法树，则称这个文法是二义二义的的z若一个文法存在某个句子有两个不同的最若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是左（右）推导，则称这个文法是二义二义的的z判定任给的一个上下文无关文法是否二义，判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件以为无二义性寻找一组充分条件 64文法的二义性和语言的二义性文法的二义性和语言的二义性文法的二义性和语言的二义性是两个不同的概念。

因为可能有两个不同文法的二义性和语言的二义性是两个不同的概念因为可能有两个不同的文法的文法G G和和G′G′，其中，其中G G是二义的，但是却有是二义的，但是却有L(G)=L(G′)L(G)=L(G′)，也就是说，，也就是说，这两个文法所产生的语言是相同的这两个文法所产生的语言是相同的二义文法改造为无二义文法二义文法改造为无二义文法G‘[E]:E → i G[E]G‘[E]:E → i G[E]：： E → T|E+T E → T|E+T E → E+E T → F|T*F E → E+E T → F|T*F E → E*E F → E → E*E F → （（E E））|i|i E → (E) E → (E) 规定算符优先性和结合性规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。

对于一个程序设计语言来说，常常希望它的文法是无二义天二义的对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的的，因为希望对它的每个语句的分析是唯一的653.6 3.6 句型的分析（句型的分析（上下文无关文法）上下文无关文法）z句型分析句型分析就是就是识别识别一个符号串是否为某文法的一个符号串是否为某文法的句型句型，是某个，是某个推导推导的构造过程的构造过程z在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程序程序称为称为分析程序分析程序或或识别程序识别程序分析算法又称分析算法又称识别识别算法算法z从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识别识别输入符号串输入符号串，首先识别符号串中的，首先识别符号串中的最左最左符号，符号，进而进而依次识别右边依次识别右边的一个符号，的一个符号，直到分析结束直到分析结束66句型的句型的分析算法分类分析算法分类分析算法可分为：分析算法可分为：z自上而下分析法自上而下分析法：：从文法的开始符号出发从文法的开始符号出发，反复使用文法的，反复使用文法的产生式，产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导，推导，或者说，为输入串寻找一个最左推导。

或者说，为输入串寻找一个最左推导z自下而上分析法自下而上分析法：：从从输入符号串输入符号串开始开始，，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号   67两种方法反映了两种语法树的构造过程两种方法反映了两种语法树的构造过程y自上而下方法自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串y自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树681、自上而下的语法分析、自上而下的语法分析例：文法例：文法G：：   S → → cAd                       A → → ab                       A → → a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd        a        b推导过程：推导过程：S  cAd         cAd  cabd692、自下而上的语法分析、自下而上的语法分析例：文法例：文法G：：   S → → cAd                       A → → ab                       A → → a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAA  c    a      b     d  c     a      b     d  c      a        b      d 规约规约过程构造的推导：过程构造的推导： cAd  cabd      S  cAd70自上而下的语法分析自上而下的语法分析(1)S → → cAd   (2) A → → ab (3) A → → a 识别输入串识别输入串w=cad是否为该文法的是否为该文法的句子句子若S  cAd 后选择(2)扩展A，S  cAd  cabd那将会？ w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。

导致失败的原因是在分析中对A的选择不是正确的 S c A d a b 这时应该回溯回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）71(1)S → → cAd   (2)  A → → ab  (3)A → → a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子自下而上的语法分析自下而上的语法分析对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在c A b d中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子c a b d c A b d a723、句型分析的有关问题、句型分析的有关问题1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式进产生式进行推导行推导？？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条规则：条规则：B→→A1|A2|…|An，那么如何确定用哪个右部去替代，那么如何确定用哪个右部去替代B？？2）在自下而上的分析方法中）在自下而上的分析方法中如何如何识别可归约的串识别可归约的串？？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一个选择一个子子串串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可归约可归约串串”733、句型分析的有关问题、句型分析的有关问题z若若G是一文法，是一文法，S是文法的开始符号，是文法的开始符号，αβδαβδ是文法是文法的一个句型。

如有的一个句型如有S S =>* αAδαAδ且且A A=>+ β, β,则称则称ββ是句型是句型 αβδ αβδ相对于非终结符相对于非终结符A A的的短语短语z如果如果A A=>ββ，则称，则称ββ是句型是句型 αβδ αβδ相对于规则相对于规则A-A->β>β的的直接短语直接短语或简单短语简单短语））z一个句型的一个句型的最左直接短语最左直接短语称为称为句柄句柄 74z句型句型aabbaa的的语法树语法树  例例: G[S]:S→→aASA→→SbAA→→SSS→→aA→→ba                         S             a          A             S               S        b      A      a               a             b      a•从语法树中的子树找到短语若子树只有一个分支，则为直接短语短语：a，ba，a，abba，aabbaa直接短语：a，ba，a753.7 文法实用中的一些说明文法实用中的一些说明1、限制、限制化简文法文法中文法中不含有不含有有害规则有害规则和和多余规则多余规则有害规则有害规则：形如：形如U→→U的产生式。

会的产生式会引起引起文法的文法的二义性二义性多余规则多余规则：指文法中：指文法中任何句子的推导任何句子的推导都都不会用到的规则不会用到的规则        文法中文法中不含有不含有不可到达和不可终止的不可到达和不可终止的非终结符非终结符1）文法中某些）文法中某些非终结符不在任何规则的右部出现非终结符不在任何规则的右部出现，该非终，该非终结符称为结符称为不可到达不可到达2）文法中某些）文法中某些非终结符非终结符，由它，由它不能推出终结符号串不能推出终结符号串，该非，该非终结符称终结符称为为不可终止不可终止76  对于文法对于文法G[S]，为了保证任一非终结符，为了保证任一非终结符A在在句子句子推导中出现，必须满足如下两个条件：推导中出现，必须满足如下两个条件：1. A必须在某句型中出现必须在某句型中出现     即有即有S =>* αAβ，其中，其中α，，β属于属于V V* *    2. 必须能够从必须能够从A推出终结符号串推出终结符号串t来来    即即A =>* t，其中，其中t∈∈VT*77化简文法z例：例：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）为）为多余规则多余规则应去应去掉。

掉782、上下文无关文法中的、上下文无关文法中的ε规则规则z上下文无关文法中某些规则可具有形式上下文无关文法中某些规则可具有形式A→ε，称，称这种规则为这种规则为ε规则规则因为因为ε规则会使得有关文法的一些讨论和证明变得复杂规则会使得有关文法的一些讨论和证明变得复杂,有时会限有时会限制这种规则的出现制这种规则的出现z两种定义的唯一差别是两种定义的唯一差别是ε句子在不在语言中句子在不在语言中z文法构思的启示是要找出语言的有穷描述，而如文法构思的启示是要找出语言的有穷描述，而如果语言果语言L有一个有穷的描述，则有一个有穷的描述，则L1=L∪∪｛｛ε｝也同｝也同样有一个有穷的描述，并且可以证明，若样有一个有穷的描述，并且可以证明，若L是上下是上下文有关语言、上下文无关语言或正规语言，则文有关语言、上下文无关语言或正规语言，则L∪∪｛｛ε｝和｝和L-｛｛ε｝分别是上下文有关语言、上下｝分别是上下文有关语言、上下文无关语言和正规语言文无关语言和正规语言79练习练习 1. 写一文法，使其语言是偶正整数的集合要求：(1)允许0打头   (2) 不允许0打头 2.证明下述文法G［〈表达式〉］是二义的。

〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/ 3. 令文法G［E］为：E→T|E+T|E-T(1)T→F|T*F|T/F(2)F→(E)|i(3)证明E+T*F是它的一个句型80练习练习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|1BA→1S|1B→0S|081。