《教学课件第三章文法和语言》由会员分享，可在线阅读，更多相关《教学课件第三章文法和语言（74页珍藏版）》请在金锄头文库上搜索。
1、盛威网：专业的计算机学习网站第三章文法和语言v第一节第一节 文法的直观概念文法的直观概念v第二节第二节 符号和符号串符号和符号串v第三节第三节 文法和语言的形式定义文法和语言的形式定义v第四节第四节 文法的类型文法的类型v第五节第五节 上下文无关文法及其语法树上下文无关文法及其语法树v第六节第六节 句型分析句型分析v第八节第八节 典型例题及解答典型例题及解答v第七节第七节 有关文法实用中的一些说明有关文法实用中的一些说明盛威网：专业的计算机学习网站知知识识结结构构盛威网：专业的计算机学习网站3.1文法的直观概念第三章方法和语言v所谓一个语言的所谓一个语言的语法语法是指一组是指一组规则规则，用它
2、可以形成和产生，用它可以形成和产生一个合适的程序一个合适的程序v目前广泛使用的手段是目前广泛使用的手段是上下文无关文法上下文无关文法，即用上下文无关，即用上下文无关文法作为程序设计语言语法的描述工具文法作为程序设计语言语法的描述工具盛威网：专业的计算机学习网站v程序设计语言的描述：程序设计语言的描述：语法：语法：程序的程序的结构或形式结构或形式语义：语义：语言所代表的语言所代表的含义含义语用：语用：语言的实际语言的实际应用应用盛威网：专业的计算机学习网站例如，对于赋值语句例如，对于赋值语句 x : = a + b * c 的非形式描述是：的非形式描述是：语法：赋值语句变量语法：赋值语句变量:=
3、表达式表达式语义：先求右部，然后把结果给左部变量语义：先求右部，然后把结果给左部变量语用：赋值语句可用来计算和保存表达式的值语用：赋值语句可用来计算和保存表达式的值形式化方法：用一整套带有严格规定的符号体系来描述问形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法题的理论和方法形式语言：一种不考虑含义的符号语言形式语言：一种不考虑含义的符号语言盛威网：专业的计算机学习网站v程序设计语言的语义分成：程序设计语言的语义分成：静态语义：静态语义：是一系列是一系列限定规则限定规则，并确定哪些合乎语法的程，并确定哪些合乎语法的程序是合适的序是合适的动态语义动态语义（运行语义、执行语义）：表
4、明程序要（运行语义、执行语义）：表明程序要做什么做什么，要计算什么要计算什么盛威网：专业的计算机学习网站v以自然语言为例，人们无法列出全部句子，但是人们可以以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组给出一些规则，用这些规则来说明（或者定义）句子的组成结构：成结构：盛威网：专业的计算机学习网站v例如例如, 有一组规则有一组规则: : = : = : = the : = a : = big : = : = ate : = : = cat : = mouse 显然显然, 由这一组规则可以产生句子由这一组规则可以产生句子:The big cat
5、 / mouse ate a mouse / cat 盛威网：专业的计算机学习网站v这样的语言描述称为文法这样的语言描述称为文法v使用文法作为工具，不仅为了严格地定义句子的结构，使用文法作为工具，不仅为了严格地定义句子的结构， 也是为了适当条数的规则把语言的全部句子描述出来，也是为了适当条数的规则把语言的全部句子描述出来， 可以说可以说文法是文法是以有穷的集合刻画无穷的集合的一个以有穷的集合刻画无穷的集合的一个工具工具盛威网：专业的计算机学习网站3.2符号和符号串一.字母表和符号串1.语言语言可以看成在一个基本符号集上定义的，按一定规则可以看成在一个基本符号集上定义的，按一定规则构成的一切基本
6、符号串组成的构成的一切基本符号串组成的集合集合2.字母表字母表（符号集）：是一个（符号集）：是一个非空非空有穷集合有穷集合3.符号符号（字符）：字母表中的元素（字符）：字母表中的元素4.符号串符号串：符号的有穷：符号的有穷序列序列。注意：。注意： 表示空符号串！表示空符号串！5.符号串集合符号串集合：字母表：字母表 上若干个符号串组成的集合上若干个符号串组成的集合盛威网：专业的计算机学习网站v重要约定：重要约定： 小写字母小写字母 a, b, c, , r 表示符号表示符号 小写字母小写字母 s, t, u, , z 表示符号串表示符号串 大写字母大写字母 A, B, C, , Z 表示符号串
7、集合表示符号串集合盛威网：专业的计算机学习网站二.符号串的运算1.符号串相等：符号串相等：设设 x 、y 是字母表是字母表 上的两个符号串，若上的两个符号串，若 x 与与 y 的诸符号依次相等，则该两符号串相等，记为的诸符号依次相等，则该两符号串相等，记为 x = y盛威网：专业的计算机学习网站2.符号串长度：符号串长度：设设 x 是字母表是字母表 上的符号串，符号串中包含上的符号串，符号串中包含符号的个数称为符号串符号的个数称为符号串 x 的长度，用的长度，用 x 表示表示例例: (1). | | = 0 ; (2). | a x | = | x a | = | x | + 1 ( a )盛
8、威网：专业的计算机学习网站3. 符号串的连结：符号串的连结：设设 x 与与 y 是字母表是字母表 上的两个符号串，上的两个符号串，把把 y 的所有符号相继写在的所有符号相继写在 x 的符号之后所得到的符号串的符号之后所得到的符号串称为称为x 与与 y 的连结，用的连结，用 x y 表示表示注意注意: | x y | = | x | + | y | x = x = x x y y x ( 一般说来一般说来 )盛威网：专业的计算机学习网站4 .符号串的逆：符号串的逆：设设 x 是字母表是字母表 上的符号串，其逆为符号串上的符号串，其逆为符号串 x 的倒置，的倒置，记为记为 。(1) . 若若 x
9、= abcd , 则则 = dcba . (2). = 盛威网：专业的计算机学习网站5.符号串的前缀、后缀和子串：符号串的前缀、后缀和子串：设设 x、y、z 是字母表是字母表 上的上的符号串，则称符号串，则称 x 为符号串为符号串 x y 的前缀，的前缀，y 是符号是符号 串串 x y 的的后缀，后缀， x、y 、 z 、xy 、yz 是符号串是符号串 x y z 的子串的子串例例: abcd盛威网：专业的计算机学习网站6.符号串集合的乘积：符号串集合的乘积：设设A、B为两个符号串集合，其乘积为为两个符号串集合，其乘积为 AB=xy|x A,y B例例: (1). 若若 A = ab, cd
10、, B = ef, gh 则则: AB = abef, abgh, cdef, cdgh (2). x = x = x A = A = A盛威网：专业的计算机学习网站7.空集：空集：不含任何元素的集合，记为不含任何元素的集合，记为 注意注意: (1). A = A = ; (2). 盛威网：专业的计算机学习网站8.符号串的幂：符号串的幂：设设 x 是字母表是字母表 上的符号串，则上的符号串，则 x 的幂运算的幂运算为为x 0 = x 1=x x 2=xx x n=x n-1x (xx n-1)例例: 若若 x = ab 则则: x 0 = , x 1 = ab, x 2 = abab, , x
11、 n = abab ab盛威网：专业的计算机学习网站9.符号串集合的幂：符号串集合的幂：设设 A 是符号串集合，则符号串是符号串集合，则符号串 A 的幂运的幂运算为：算为： A0= A1=A A2=AA An=A n-1A (AA n-1)例例: 若若 A = ab, cd 则则: A 0 = , A 1 = ab, cd , A 2 = abab, abcd, cdab, cdcd , 盛威网：专业的计算机学习网站注意注意:A*=A0A+ A+=AA*=A*A 若若 A = a, b 则则: A*= , a, b, aa, ab, ba, bb, aaa, A+= a, b, aa, ab,
12、 ba, bb, aaa, 10.集合集合A的闭包与正闭包：的闭包与正闭包： 正闭包表示为正闭包表示为 A+ ，集合集合A 的闭包表示为的闭包表示为 A* ，盛威网：专业的计算机学习网站3.3文法和语言的形式定义v规则规则（重写规则、产生式、生成式）：（重写规则、产生式、生成式）： 一个规则是一个二元组一个规则是一个二元组,通常写作通常写作:= 或或 称称为规则的的左部左部，称称为规则的的右部右部， (:=)读作作“定定义为”，这是一条关于是一条关于的规则（产生式）的规则（产生式）盛威网：专业的计算机学习网站v定义定义3.1：文法文法G定义为四元组（定义为四元组（VN，VT，P，S）VN ：非
13、终结符（语法实体、变量）集非终结符（语法实体、变量）集VT ：终结符集终结符集P：规则规则（ ）集合，集合，(VNVT)*且至少包含且至少包含一个非一个非终结符，符， (VNVT)*VN、VT、P是非空有穷集是非空有穷集S：开始符开始符（识别符），它是一个非终结符，至少要在一（识别符），它是一个非终结符，至少要在一条规则中作为左部出现条规则中作为左部出现VNVT= V=VNVT，称为文法称为文法G的字母表（字汇表）的字母表（字汇表）盛威网：专业的计算机学习网站v例例3.1 文法文法G=（VN，VT，P，S），），其中其中VN = S ，VT = 0, 1 ，P= S0S1, S01 盛威网：专
14、业的计算机学习网站v例例3.2文法文法G=（VN，VT，P，S），），其中其中VN =标识符，字母，数字标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P a z 0 9 S=盛威网：专业的计算机学习网站v很多时候，不用将文法很多时候，不用将文法G的四元组显式地表示出来，而的四元组显式地表示出来，而只将产生式写出只将产生式写出盛威网：专业的计算机学习网站v一般约定：一般约定：第一条产生式的左部是识别符第一条产生式的左部是识别符用尖括号括起来的是非终结符（或者用大写字母表示）用尖括号括起来的是非终结符（或者用大写字母表示）不用尖括号括起来的是终结符（或者用小写字母表示）不用尖括号括起
15、来的是终结符（或者用小写字母表示）将将G也写成也写成GS，其中其中S是识别符是识别符盛威网：专业的计算机学习网站v推导：推导：定义定义V*中的符号之间的关系：中的符号之间的关系：直接推导：直接推导：长度为长度为n(n1)的推导：的推导：长度为长度为n(n 0)的推导：的推导：*+盛威网：专业的计算机学习网站v定义定义3.2：文法文法G（VN，VT，P，S），）， 是一条是一条规则，和和是是V*中的任意符号，若有符号串中的任意符号，若有符号串v，w满足：足：v=，w= ，则称则称v直接推导到直接推导到w， v w，或或w直接归约到直接归约到vv例：例：G： S0S1， S01S 0S1 00S1
16、1 000S111 00001111盛威网：专业的计算机学习网站v定义定义3.3：如果存在直接推导的序列：如果存在直接推导的序列：v=w0w1w2wn=w (n0)则称则称v推导出推导出w（推导长度为推导长度为n），），或称或称w归约到归约到V，记作记作+盛威网：专业的计算机学习网站v定义定义3.4：若有若有vw，或，或v=w，则记作：则记作：+*盛威网：专业的计算机学习网站v定义定义3.5：若有若有Sx，则称则称x是文法是文法GS的的句型句型，若，若x仅仅由终结符组成，则称由终结符组成，则称x为为GS的的句子句子*盛威网：专业的计算机学习网站v定义定义3.6：文法文法G所产生的语言定义为集合
17、所产生的语言定义为集合L(G)=x|Sx，其中其中S为文法识别符号，且为文法识别符号，且xVT*v文法描述的语言是该文法一切句子的集合文法描述的语言是该文法一切句子的集合v例：例：G： S0S1， S01L(G)=0n1n|n1*盛威网：专业的计算机学习网站例例3.3文法文法文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL（G）= anbnen | n1 思考：思考：a4b4e4怎么推导？怎么推导？盛威网：专业的计算机学习网站v定义定义3.7：若若L(G1)L(G2)，则称文法则称文法G1和和G2是等价的是等价的v例如文法例如
18、文法GA：A0RA01RA1和文法和文法GS： S0S1 S01等价等价L(G)=0n1n|n1盛威网：专业的计算机学习网站3.4文法的类型v乔姆斯基乔姆斯基(Chomsky)于于1956年建立形式语言的描述年建立形式语言的描述v他把文法分成：他把文法分成：0型、型、1型、型、2型、型、3型型v四个文法类的定义是逐渐增加限制的四个文法类的定义是逐渐增加限制的0型1型2型3型盛威网：专业的计算机学习网站v设设G（VN，VT，P，S），），如果它的如果它的每个每个产生式产生式是这样一种结构：是这样一种结构：(VNVT)*且且至少包至少包含一个含一个非终结符，非终结符， (VNVT)*，则，则G是一
19、个是一个0型文法型文法（短语文法、无限制文法短语文法、无限制文法）盛威网：专业的计算机学习网站v思考：这样定义可以吗？思考：这样定义可以吗？ 设设G（VN，VT，P，S），），如果它的如果它的每个每个产生式产生式是这样一种结构：是这样一种结构：(VNVT)+， (VNVT)*，则则G是一个是一个0型文法型文法盛威网：专业的计算机学习网站v重要的理论结果：重要的理论结果：0型文法的能力相当于图灵机（型文法的能力相当于图灵机（Turing）或者说，任何或者说，任何0型语言都是递归可枚举的型语言都是递归可枚举的反之，递归可枚举集必定是一个反之，递归可枚举集必定是一个0型语言型语言盛威网：专业的计算机
20、学习网站v设设G（VN，VT，P，S），），如果它的如果它的每个每个产生式产生式均满足：均满足：| |，仅仅仅仅S除外，除外，则文法文法G是是1型文法型文法（上下文有关文法上下文有关文法）例例3.1、3.2、3.3盛威网：专业的计算机学习网站例：例：文法文法GS： SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=w|wa,b*盛威网：专业的计算机学习网站v有些定义中，将上下文有关文法的产生式的形式描述为有些定义中，将上下文有关文法的产生式的形式描述为1A212，其中其中1、2和和都在都在V*中，中，A在在VN中中盛威网：专业的计算机学习网站v设设G（
21、VN，VT，P，S），），如果它的如果它的每个每个产生式产生式均满足：均满足：是是一个一个非非终结符，符，V*，则文法则文法G是是2型文法型文法（上下文无关文法上下文无关文法）盛威网：专业的计算机学习网站v有有时将将2型文法的型文法的产生式表示生式表示为A的形式，其中的形式，其中AVN，也就是用也就是用取代非取代非终结符符A时，与，与A所在的上下所在的上下文无关，因此取名文无关，因此取名为上下文无关上下文无关例例3.1、3.2盛威网：专业的计算机学习网站例例3.4：文法文法GS：SaB|bAAa|aS|bAABb|bS|aBB盛威网：专业的计算机学习网站v设设G（VN，VT，P，S），），如果
22、它的如果它的每个每个产生式产生式AB或或A ，其中其中A和和B都是非都是非终结符，符，VT*，则文法则文法G是是3型文法型文法（正规文法正规文法）例例3.5：文法：文法GS：S0A|1B|0A0A|1B|0SB1B|1|0你会忘记我吗？你会忘记我吗？盛威网：专业的计算机学习网站v4个文法类的定义是个文法类的定义是逐渐增加限制逐渐增加限制的，因此，每一种正规的，因此，每一种正规文法都是上下文无关的，每一种上下文无关文法都是上文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是下文有关的，而每一种上下文有关文法都是0型文法型文法v称称0型文法产生的语言为型文法产生
23、的语言为0型语言，上下文有关文法、上型语言，上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言关语言、上下文无关语言和正规语言盛威网：专业的计算机学习网站3.5上下文无关文法及其语法树上下文无关文法有足够的能力描述现今程序设计语言的上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式、描述各种语句等语法结构，比如描述算术表达式、描述各种语句等例例3.6：文法文法G=(E,+,*,i,(,),P,E)其中其中P为：为：EiEE+EEE*E E (E)ifthen| ifthen
24、else 盛威网：专业的计算机学习网站给定文法给定文法G=（VN，VT，P，S），），对于对于G的任何句型都的任何句型都能构造与之关联的语法树（推导树、语法分析树、分能构造与之关联的语法树（推导树、语法分析树、分析树）。析树）。这棵树满足下列这棵树满足下列4个条件：个条件：（1）每个结点都有一个）每个结点都有一个V中的符号作标记中的符号作标记（2）根的标记是开始符号）根的标记是开始符号S（3）若一结点若一结点n至少有一个它自己除外的子孙，并且有标记至少有一个它自己除外的子孙，并且有标记A，则，则AVN（4）如果结点如果结点n的直接子孙，从左到右的次序是结点的直接子孙，从左到右的次序是结点n1,
25、n2,nk，其标记分别为其标记分别为A1,A2,Ak，那么那么AA1A2Ak一定是一定是P中的一个产生式中的一个产生式盛威网：专业的计算机学习网站例例3.7：文法文法G=(S，A,a,b,P,E)其中其中P为：为：(1)SaAS(2)ASbA(3)ASS (4)S a (5)A ba图图3.1的推导树是文法的推导树是文法G的的句型句型aabbaa的推导过程的推导过程把把aabbaa叫做推导树的结果，叫做推导树的结果，把推导树叫做句型把推导树叫做句型aabbaa的语法树的语法树图图3.1 推导树推导树 盛威网：专业的计算机学习网站文法文法G的句型的句型aabbaa的推导过程：的推导过程：（1）S
26、aASaAaaSbAaaSbbaaaabbaa（2）SaASaSbASaabASaabbaSaabbaa（3）SaASaSbASaSbAaaabAaaabbaa如果在推导的任何一步如果在推导的任何一步 ，其中其中、是句型，都是句型，都是是对中的最左（最右）非中的最左（最右）非终结符符进行替行替换，则称称这种推种推导为最左（最右）推最左（最右）推导。在形式。在形式语言中，最右推言中，最右推导被称被称为规范推范推导，由，由规范推范推导所得的句型称所得的句型称为规范句型范句型盛威网：专业的计算机学习网站例：例：GE:E iE E+EE E*EE (E)句型句型 i*i+i 的两个：的两个：推导推导1
27、：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一个句型是否只对应唯一的一棵语法树？一个句型是否只一个句型是否只对应唯一的一棵语法树？一个句型是否只有唯一的一个最左（最右）推导？有唯一的一个最左（最右）推导？ 不是不是盛威网：专业的计算机学习网站图图3.2推导推导1的语法树的语法树图图3.3推导推导2的语法树的语法树盛威网：专业的计算机学习网站若一个文法存在某个句子对应两棵不同的语法树，则称这若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是个文法是二义的二义的。或者，若一个文法存在某个句子有两个或者，若一个
28、文法存在某个句子有两个不同的最左（右）推导，则称这个文法是不同的最左（右）推导，则称这个文法是二义的二义的注意，文法的二义性和语言的二义性是两个不同的概念。注意，文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法因为可能有两个不同的文法G和和G，其中其中G是二义的，但是二义的，但是却有是却有L(G)=L(G)产生某上下文无关语言的每一个文法都是二义的，则称此产生某上下文无关语言的每一个文法都是二义的，则称此语言是语言是先天二义的先天二义的盛威网：专业的计算机学习网站判定任给的一个上下文无关文法是否二义，或它是否产生判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义
29、的上下文无关语言，这两个问题是递归不可一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件解的。但可以为无二义性寻找一组充分条件二义文法改造为无二义文法二义文法改造为无二义文法例例3.8：GE：E T|E+T GE: E i T F|T*FE E+E F （E）|i E E*E 规定优先顺序和结合律规定优先顺序和结合律 E (E) 盛威网：专业的计算机学习网站3.6句型的分析句型分析是一个句型分析是一个识别识别输入符号是否为语法上正确的程序的输入符号是否为语法上正确的程序的过程过程在语言的编译实现中，把完成句型分析的程序称为分析程在语言的编译实现中，把完成句
30、型分析的程序称为分析程序（识别程序），分析算法又称为识别算法序（识别程序），分析算法又称为识别算法介绍的分析算法都称之为从左到右的分析算法介绍的分析算法都称之为从左到右的分析算法分析算法分为：分析算法分为：自上而下分析法：从文法的开始符号出发，反复使用各种自上而下分析法：从文法的开始符号出发，反复使用各种产生，寻找匹配于输入串的推导产生，寻找匹配于输入串的推导自下而上的方法：从输入符号串开始，逐步进行归约，直自下而上的方法：从输入符号串开始，逐步进行归约，直到归约到文法的开始符号到归约到文法的开始符号盛威网：专业的计算机学习网站一.自上而下分析方法例例3.9考虑文法考虑文法GS（1）ScAd（
31、2）Aab（3）Aa识别输入串识别输入串w=cabd是否该文法的句子是否该文法的句子所构造的推导过程为：所构造的推导过程为：ScAdcabd图图3.4自上而下的分析步骤自上而下的分析步骤盛威网：专业的计算机学习网站二.自下而上分析方法例例3.9考虑文法考虑文法GS（1）ScAd（2）Aab（3）Aa识别输入串识别输入串w=cabd是否该文法的句子是否该文法的句子所构造的推导过程为：所构造的推导过程为：ScAdcabd图图3.5自下而上的分析自下而上的分析盛威网：专业的计算机学习网站三.句型分析的有关问题在自上而下的分析中，对于例在自上而下的分析中，对于例3.9的文法，在扩展的文法，在扩展A时，
32、有时，有两个选择，如果选择另一个，推导序列为两个选择，如果选择另一个，推导序列为ScAdcad，语法树如图语法树如图3.6所示所示这时，就与这时，就与w=cabd不符，宣告失败不符，宣告失败应该用哪条规则去替换呢？一种解决办法从各种可能的选应该用哪条规则去替换呢？一种解决办法从各种可能的选择中随机挑选一种，并希望它是正确的，如果失败，退回择中随机挑选一种，并希望它是正确的，如果失败，退回去，再试另一种，这种方式称为去，再试另一种，这种方式称为回溯回溯。显然这种方式代价。显然这种方式代价极高，效率很低极高，效率很低图图3.6 cad的语法树的语法树 盛威网：专业的计算机学习网站在自下而上的分析中
33、，对于例在自下而上的分析中，对于例3.9的文法，在归约的时候，的文法，在归约的时候，也存在选择哪一条规则进行归约的问题，因此需要精确定也存在选择哪一条规则进行归约的问题，因此需要精确定义义“可归约串可归约串”。事实上，存在种种不同的方法刻画。事实上，存在种种不同的方法刻画“可可归归约串约串”。对这个概念的不同定义形成了不同的自下而上分。对这个概念的不同定义形成了不同的自下而上分析文法。在一种析文法。在一种“规范归约规范归约”的分析中，这种的分析中，这种“可归约串可归约串”称称作作“句柄句柄”盛威网：专业的计算机学习网站定义定义3.8令令G是一是一文法，文法，S是文法的开始符号，是文法的开始符号
34、，是文是文法法G的一个句型。如果有：的一个句型。如果有：S A且且A 则称则称是句型是句型相对于规则相对于规则A 的的直接短语直接短语（简单短语（简单短语）。一个句型的）。一个句型的最左最左直接短语直接短语称为该句型的称为该句型的句柄句柄*+盛威网：专业的计算机学习网站例例GE: E T|E+T T F|T*F F （E）|i句型句型i*i+i短语：短语：i1、i2 、i3 、i1*i2 、i1*i2+i3直接短语：直接短语：i1 、i2 、i3句柄：句柄：i1ETF*i3+ETTFFi1i2盛威网：专业的计算机学习网站3.7有关文法实用中的一些说明一一.有关文法的实用限制有关文法的实用限制有
35、害规则：形如有害规则：形如UU的产生式的产生式多余规则：文法中那些连一个句子的推导都多余规则：文法中那些连一个句子的推导都用不到用不到的规则的规则某些非终结符不在任何规则的右部出现（某些非终结符不在任何规则的右部出现（不可到达的不可到达的）不能够从这些非终结符推出终结符号串（不能够从这些非终结符推出终结符号串（不可终止的不可终止的）盛威网：专业的计算机学习网站例例3.10文法文法GS：（1） SBe（2） BCe（3） BAf（4）AAe（5）Ae（6）CCf（7） Df盛威网：专业的计算机学习网站对文法对文法G=(VN,VT,S,P)来说，为了保证其任一非终结符来说，为了保证其任一非终结符A
36、在在句子推导中出现，必须满足如下两个条件：句子推导中出现，必须满足如下两个条件：A必须在某句型中出现。即必须在某句型中出现。即SA,其中其中,属于属于V*必须能够从必须能够从A推出终结符号串推出终结符号串t。即。即At,其中其中tVT*+盛威网：专业的计算机学习网站二.上下文无关文法中的规则规则：形如规则：形如A 的产生式，其中的产生式，其中AVN某些著作和讲义中限制这种规则的出现。因为某些著作和讲义中限制这种规则的出现。因为规则会使规则会使有关文法的一些讨论和证明变得复杂有关文法的一些讨论和证明变得复杂两种定义的唯一差别是两种定义的唯一差别是句子在不在语言中句子在不在语言中如果语言如果语言L
37、有一个有穷的描述，则有一个有穷的描述，则L也同样有一个有也同样有一个有穷描述。并且可以证明，若穷描述。并且可以证明，若L是上下文有关语言、上下文是上下文有关语言、上下文无关语言或正规语言，则无关语言或正规语言，则L和和L-分别是上下文有分别是上下文有关语言、上下文无关语言和正规语言关语言、上下文无关语言和正规语言盛威网：专业的计算机学习网站定理定理3.1若若L是由文法是由文法G=(VN,VT,P,S)产生的语言，产生的语言，P中的中的每一个产生式的形式均为每一个产生式的形式均为A,其中其中AVN，V*，则则L能能由由这样这样的的一种文法产生，一种文法产生，即每一个即每一个产生式产生式或者为或者
38、为A形式，其中形式，其中AVN， V+,或者或者 S形式，形式，且且 S不出现在任何产生式右边不出现在任何产生式右边盛威网：专业的计算机学习网站定理定理3.2如果如果G是上下文有关文法，则存在另一个上下文是上下文有关文法，则存在另一个上下文有关文法有关文法G1，L(G)=L(G1)，且，且G1的开始符号不出现在的开始符号不出现在G1的任何产生式的右边的任何产生式的右边又如果又如果G是一个上下文无关文法，也能找到这样一个上下是一个上下文无关文法，也能找到这样一个上下 文无关文法文无关文法G1如果如果G是是一个正规文法，则也能找到这样一个正规文法是是一个正规文法，则也能找到这样一个正规文法 G1盛
39、威网：专业的计算机学习网站3.8典型例题及解答1.证明文法证明文法G=(E,O,(,),+,*,v,d,P,E)是二义的是二义的E EOE|(E)|v|dO+|*2.考虑下述两个语言考虑下述两个语言L1=anb2ncm|n,m=0L2=anbmc2m|n,m=0通过分别给出上述语言的文法来证明这些语言都是上通过分别给出上述语言的文法来证明这些语言都是上下文无关的下文无关的盛威网：专业的计算机学习网站【本章小结】【本章小结】 本章出现的概念较多本章出现的概念较多,应重点理解文法应重点理解文法,推导推导,句型句子及句型句子及语语言的定义等概念言的定义等概念.语法分析有关内容在后面章节会详细讨论语法
40、分析有关内容在后面章节会详细讨论. 文法作为程序语言的语法的描述工具文法作为程序语言的语法的描述工具,它用规则只能陈述它用规则只能陈述的是的是:语言的所有句子以什麽样的符号串能出现语言的所有句子以什麽样的符号串能出现.请记住文请记住文法和语言的形式定义中的法和语言的形式定义中的 “形式形式”的含义的含义-只涉及语言的只涉及语言的语语法不涉及语言的语义法不涉及语言的语义. 本章内容是形式语言理论的一部分本章内容是形式语言理论的一部分.形式语言理论是对符形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。言语法
41、分析研究的基础。 盛威网：专业的计算机学习网站考察本章知识点最典型的题目是：考察本章知识点最典型的题目是： 已知文法已知文法GA，写出它定义的语言描述，写出它定义的语言描述GA: A 0B|1CB 1|1A|0BBC 0|0A|1CC答案答案:GA定义的语言由定义的语言由0、1符号串组成，串中符号串组成，串中0和和1的个的个数相同。数相同。 给出语言描述，构造文法。给出语言描述，构造文法。构造一文法构造一文法,其定义的语言是由算符其定义的语言是由算符+, *, (,)和运算对象和运算对象a构成的算术表达式的集合构成的算术表达式的集合.答案答案1: GE EE+T|TTT* F|FF(E)|a答
42、案答案2: GE EE+E|E* E|(E)|a盛威网：专业的计算机学习网站编译原理第编译原理第3章习题章习题第第1题：题：写一文法，使其语言是偶正整数的集合。写一文法，使其语言是偶正整数的集合。 要求：要求：(1) 允许允许0打头；打头； (2)不允许不允许0打头。打头。 第第2题：题：证明下述文法证明下述文法G表达式表达式是二义的。是二义的。 表达式表达式 =a|(表达式表达式)|表达式表达式运算符表达式运算符表达式 运算符运算符 =+|-|*|/第第3题：题：令文法令文法GE为：为： ET|E+T|E-TTF|T*F|T/FF(E)|i 证明证明E+T*F是它的一个句型，指出这个句型的所
43、有短语、直是它的一个句型，指出这个句型的所有短语、直接短语和句柄。接短语和句柄。盛威网：专业的计算机学习网站第第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题：题：给出下述文法所对应的正规式：给出下述文法所对应的正规式： S0A|1BA1S|1 B0S|0盛威网：专业的计算机学习网站第3章作业题P47：1.6.(5)(6)8.9.13.14.
