编译原理第02章文法和语言的基本知识.ppt

《编译原理第02章文法和语言的基本知识.ppt》由会员分享，可在线阅读，更多相关《编译原理第02章文法和语言的基本知识.ppt（143页珍藏版）》请在装配图网上搜索。

1、第二章 文法和语言的基本知识,字母表和符号串,文法和语言的形式定义,短语、直接短语和句柄,语法树和文法的二义性,文法和语言的分类,2.0 概 述,对程序设计语言的描述是从语法、语义和语用三个因素来考虑。,语法是对语言结构的定义。,语用则是从使用的角度去描述语言。,语义是描述了语言的含义。,2.0 概 述,例如 赋值语句s2*3.1416*r*(r+h)的 非形式化的描述为：,语法：赋值语句由一个变量，后随一个赋值号“”，再在其后面跟一个表达式构成。,语义：首先计算语句右部表达式的值，再将结果送给左部变量中。,语用：赋值语句可用来计算和保存表达式的值。,形式语言理论是用来对程序设计语言三要素进行

2、形式化描述的方法。,2.1 字母表和符号串,元素的非空有穷集合。,例如，= a, b, c 是字母表,1. 字母表,程序设计语言的字母表 =x | x ASCII字符 =0, 1,字母表中的元素称为符号或称为字符。,例如，前述例子中,2. 符号（字符）,a、b、c 是字母表中的符号；,0、1 是字母表中的符号。,2.1 字母表和符号串,例如，设有字母表= a, b, c ,符号的有穷序列称为符号串。,符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。,则有符号串 a，b，ab，ba， cba， abc,3. 符号串（字）,2.1 字母表和符号串,说明:,不包含任何符号的符号串

3、, 称为空符号串，用表示。,符号串中符号的顺序是很重要的。,ab和ba是字母表上的两个不同的符号串。,空符号串由0个符号组成，其长度|=0,2.1 字母表和符号串,2.2 符号串的运算,设x和y是符号串，则串xy称为它们的连结。,则XYabc10a，YX10aabc,注意：对任意一个符号串x，,1. 符号串的连结,例如，设Xabc，Y10a,我们有 xxx,2.2 符号串的运算,2. 符号串集合的乘积,设A和B是符号串的集合, 则A和B的乘积定义为：,集合的乘积是满足于 xA, yB的所有符号串 xy 所构成的集合。,AB=xy | xA, yB,A=A=A,2.2 符号串的运算,例如：,设A

4、= aa, b , B= c, d ,则AB= aac, aad, bc, bd ,所以, 对任意集合A, 有:,2.2 符号串的运算,区分： 是符号串, 不是集合 表示由空符号串 所组成的集合 空集合= 。,2.2 符号串的运算,3. 符号串的幂运算,设x是符号串, 则x的幂运算定义为：,x0= ,x1= x,x2= xx,x3= xxx,注意：x0 1,2.2 符号串的运算,例如, 设 xabc 则,x0= ,x1=abc,x2=xx=abcabc,2.2 符号串的运算,4. 符号串集合的幂运算,设A是符号串的集合，则集合A的幂运算定义为：,A0=,A1=A,A2=AA,2.2 符号串的运

5、算,例如，设A= a, b ，则,A0=,A1=A= a, b ,A2=AA= aa, ab, ba, bb ,A3=AAA=A2A,= aaa, aab, aba, abb, baa, bab, bba, bbb ,2.2 符号串的运算,5. 集合A的正闭包A与闭包A*,设A是符号串的集合，则A的正闭包A和A的闭包A*的定义为:,A+=A1A2 An ,A*= A0 A1A2 An ,=A+,2.2 符号串的运算,例如，设A= a, b , 则：,A+= a, b, aa, ab, ba, bb, aaa, aab, ,A*=, a, b, aa, ab, ba, bb, aaa, aab,

6、 ,即：闭包为集合中元素的任意组合。 闭包比正闭包多含一个空符号串。,2.3 文法和语言的形式定义,用A表示+,A0,A1,AA0,AA1,+=123,= 0, 1, 00, 10, 11, 01, 000, 100, ,2.3.1 文法的形式定义,规则是一个符号与一个符号串的有序对（A,），通常写作：,A（或A ),1. 规则 也称产生式,规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。,2.3.1 文法的形式定义,例如，前述例中一组规则,描述的语言序列只可能是由0和1组成的符号串。,A0,A1,AA0,AA1,2.3.1 文法的形式定义,规则中符号 非终结符号：出现在规则左部能派

7、生出符号或符号串的那些符号，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。 终结符号：不属于非终结符号的那些符号，通常用小写字母表示。 例如，上例中的0和1。,2.3.1 文法的形式定义,规则的非空有穷集合，通常表示成四元组,VN是规则中非终结符号的集合。,VT是规则中终结符号的集合。,P 是文法规则的集合。,2. 文法,G=VN,VT, P, S ,2.3.1 文法的形式定义,S 是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言。,由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集

8、合。,2.3.1 文法的形式定义,缩写为：A1 | 2 | | n,A1,A2,An,对于若干个左部相同的规则，如,i称为A的一个候选式。,2.3.1 文法的形式定义,我们约定：, 第一条规则的左部是识别符号。,对文法G不用四元式显示表示，仅 只将规则写出。,2.3.1 文法的形式定义,G=(VN，VT，P，S ),VN=A,VT=0，1,P: A 0 | 1 | A0 | A1,S=A,前例中描述+的文法是:,2.3.1 文法的形式定义,求其VN、VT,S A A B| if A then A else A B C|B+C|+C C D|C*D|*D D x|(A)|-D,设文法G产生式为:

9、,2.3.2 推导和归约,推导：从文法开始符号开始，通过产生式的右部取代左部的过程，最终产生句子。,规约：从给定源语言的句子开始，通过产生式的左部取代右部的过程，最终到达开始符号。,由终结符组成的字符串,2.3.2 推导和归约,最左推导，每次使用一个规则以其右部取代符号串的最左非终结符,最右推导也称为规范推导，最左规约又称为规范规约。,最右推导，每次使用一个规则以其右部取代符号串的最右非终结符,注：推导和规约的每一步只能用一个产生式进行替换。,2.3.2 规范推导和规范归约,例 设有文法GS:,请给出句子101001的最右、最左推导。,SAB,AA0 | 1B,B0 | S1,2.3.2 规范

10、推导和规范归约,S,AB,AS1,AAB1,AA01,A1B01,A1001,1B1001,101001,句子101001的最右推导为:,SAB,AA0 | 1B,B0 | S1,2.3.2 推导和归约,句子101001的最左推导为：,SAB,AA0 | 1B,B0 | S1,S,AB,1BB,10B,10S1,10AB1,101BB1,1010B1,101001,2.3.2 语言的形式定义,(1) 形式上的区别，推导用“”表示，规则用“”表示 。,(2) 对文法G中任何规则A，我们有A，即推导的依据是规则。,注意推导和规则的区别：,即表示从0 出发，经一步或若干步 可推导出 n。,2.3.2

11、 语言的形式定义,如果存在一个推导序列：,则可表示为,0 1 2 n,2.3.2 语言的形式定义,例如 设有文法GE=(E,T,F,i,+,*,(,),P,E),对 i+i*i 有如下推导序列:,我们可记为,其中P为：EE+T | T,TT*F | F,F(E) | i,E,E+T,T+T,F+T,i+T,i+T*F,i+F*F,i+i*F,i+i*i,2.3.2 语言的形式定义,广义推导,我们有：,对上例 EE+T | T TT*F | F F(E) | i,2.3.2 语言的形式定义,4. 句型和句子,设有文法GS（S是文法G的开始符号）,2.3.2 语言的形式定义,例1 设有文法GS：,

12、我们有:,GS的句型：01、0S1、00S11和000111 GS的句子:01和000111,S01 | 0S1,2.3.2 语言的形式定义,例2 设有文法GE：,试证明符号串 (i*i+i) 是文法GE的一个句子。,EE+E | E*E | (E) | i,2.3.2 语言的形式定义,EE+E | E*E | (E) | i,E,(E),(E+E),(E*E+E),(i*E+E),(i*i+E),(i*i+i),（2）L(G)是VT* 的子集。即属于VT* 的符 号串 x 不一定属于L(G)。,2.3.2 语言的形式定义,5语言,文法GS产生的所有句子的集合称为文 法G所定义的语言,记为L(

13、GS)：,由语言定义可知：,（1）一旦文法给定，语言也就确定。,2.3.2 语言的形式定义,例3 设有文法GS ：S01 | 0S1,求该文法所描述的语言是什么？,由文法推出语言,2.3.2 语言的形式定义,S,0S1,00S11,0n-1S1n-1,0n1n,可见，此文法定义的语言为,L(GS)= 0n1n | n1,S01 | 0S1,2.3.2 语言的形式定义,例4 设有文法GS：S0S | 1S |,该文法所定义的语言是什么？,由该文法所确定的语言为,L(GS)=, 0, 1, 00, 01, 10, 11, = x | x0,1* ,2.3.2 语言的形式定义,例5 设有文法GA：,

14、该文法所定义的语言是什么？,AyB B xB | x,L(GA)= yxn | n1,2.3.2 语言的形式定义,该文法所定义的语言是什么？,例6 文法G:(S,A,B,a,b,c,P,S) P:SAB AaA| BbBc|bc,L(G)=anbmcm,n=0,m=1,2.3.2 语言的形式定义,该文法所定义的语言是什么？,例7 文法G:(S,A,B,a,b,c,P,S) P:SaSAB SabB BAAB bAbb bBbc cBcc,L(G)=anbncn,n1,2.3.2 语言的形式定义,由文法确定语言的方法： 从文法的开始符号出发，反复使用规则替换、展开非终结符，找出句子的规律，用式子

15、或自然语言描述出来。,2.3.3 文法的形式定义,例1 设字母表=a, b，试设计一个文法，描述语言 L= a2n , b2n | n1 ,由语言构造文法,2.3.3 文法的形式定义,当n1 L=aa, bb, ,L=aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, ,即语言L是由偶数个a，偶数个b这样的符号串组成的集合。,L=a2n, b2n | n1,当n2 L=aaaa, bbbb,当n3 L=aaaaaa, bbbbbb,2.3.3 文法的形式定义,因此，定义语言L的文法,G=( VN，VT，P，S ),其中：,VN=A, B, D,VT=a, b,P= Aaa,

16、S=A,Baa,Dbb | bbD ,| bb | bbD,注意: VTaa,bb,| aaB,| aaB,2.3.3 文法的形式定义,问题: 描述该语言的文法是否唯一呢？,显然，G不同于G。由此可见，对于一个给定的语言，描述该语言的文法是不唯一的。,P : AB | D,Baa | aBa,Dbb | bDb,等价文法:若G和G是两个不同的文法，如果它们描述的语言相同，那么，称G和G 为等价文法。,2.3.3 文法的形式定义,描述上例语言的文法是否G？,2.3.3 文法的形式定义,G=( A, a, b, P, A ),P= Aaa | bb | Aaa | Abb ,2.3.3 文法的形式

17、定义,例2 试设计一个表示所有标识符的文法,用I代表标识符；L代表字母；D代表数字; 则定义标识符的文法为：,标识符的结构:,2.3.3 文法的形式定义,G=(VN，VT，P，S),其中：,VN=I, L, D,VT=a,b,c, x,y,z,0,1,2, ,9,P= IL,S=I,La | b | c | | x | y | z,D0 | 1 | 2 | 3 | | 9 ,| I L,| I D,2.3.3 文法的形式定义,用I代表标识符；L代表字母；D代表数字；T代表字母数字串；则定义标识符的文法还可写为：,2.3.3 文法的形式定义,P: IL | LT TL | D | LT | DT

18、 La | b | c | |x|y|z D0 | 1 | 2 | 3 | | 9,2.3.3 文法的形式定义,若将定义标识符的文法设计成：,其中 VN，VT ，S 同上,G=(VN，VT，P，S ),P= IL | I D,La | b | c | |x|y|z,D0 | 1 | 2 | 3 | |9 ,2.3.3 文法的形式定义,该文法不能定义ab，abc 仅由字母串组成的标识符，缩小了所定义语言的范围。,P= IL | I D,La | b | c | |x|y|z,D0 | 1 | 2 | 3 | |9 ,2.3.3 文法的形式定义,例3 用文法定义一个含、*的算术表达式，定义用下述自

19、然语言描述： 变量是一个表达式； 若 E1和 E2是算术表达式, 则 E1E2、E1*E2、(E1) 也是算术表达式。,2.3.3 文法的形式定义,定义算术表达式的文法为：,G=(E, i, +, *, (, ) , P, E ),P为：Ei | E+E | E*E | (E), i, i+i, i*i, i+i*i, (i+i), ,注意：是符号串的集合,2.3.3 文法的形式定义,例4 设字母表 = a, b , 试设计一个文法，描述语言 L= abna | n0 ,所以定义语言的文法为：,G=( A, B, a, b, P, A ),P= AaBa BBb | ,L= aa, aba,

20、abba, ,2.3.3 文法的形式定义,例5 设字母表= (, ) ,试设计一个文法描述语言 L= (n )n | n0,P: S | ( S ),定义语言的文法为：,2.3.4 递归规则与文法的递归性,递归规则,如果文法中有规则 AA 称为规则左递归。,如果文法中有规则 A A 称为规则右递归。,如果文法中有规则 A A 称为规则递归。,2.3.4 递归规则与文法的递归性,文法的递归性,2.3.4 递归规则与文法的递归性,例1 文法中有如下规则：,这三条规则都不是递归规则，但有,UVx,VUy | z,UVx Uyx ,则该文法是左递归的。,2.3.4 递归规则与文法的递归性,例2 考虑文

21、法GA：,由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:,AaB | bB,Ba | b,L(GA)= aa, ab, ba, bb ,文法递归的意义：,2.3.4 递归规则与文法的递归性,例3 考虑文法GN1,该文法有直接左递归规则 NND, 则称该文法为左递归文法或说文法左递归，其定义的语言为0,1,2+。,N1N,NND | D,D0 | 1 | 2,2.3.4 递归规则与文法的递归性,在文法中使用递归规则，使得我们能用有限的规则去定义无穷集合的语言。,若不用递归规则，则 NND 需要用 ND | DD | DDD | 即无穷多条规则来定义由数字0,1,2 组成的所有

22、无符号整数。,2.4 语法树,推导和语法树,1. 语法树,对句型的推导过程给出一种图形表示, 这种表示称为语法树，也称推导树。,2.4 语法树,例如 设有文法GE:,构造句型i*i+i的语法树。,推导过程 (最左推导) ：,EE+T | ET | T,TT*F | T/F | F,F(E) | i,EE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+i,2.4 语法树,根据推导过程构造句型i*i+i的语法树如下：,EE+T,E,E,+,T,T+T,T,T*F+T,T,*,F,F*F+T,F,i*F+T,i,i*i+T,i,i*i+F,F,i*i+i,i,2.4 语法树,因

23、为文法的每一个句型 (句子) 都存在一 个推导，所以文法的每个句型(句子) 都存在一棵对应的语法树。,EE+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i,2.4 语法树,对句型i*i+i，还可给出最右推导：,2.4 语法树,这也就是说，一棵语法树表示了 一个句型的种种可能的(但未必是所 有的)不同推导过程, 包括最左(最右) 推导。,2.4 语法树,2. 子树,语法树的子树是由某一结点连同其所有分枝组成的部分。,2.4 语法树,3. 简单子树,语法树的简单子树是指只有单层分枝的子树。(即一步推导),2.4 语法树,句型的短语、直接短语和句柄的 直观解释是：,短语：

24、子树的末端结点形成的符号串是 相对于子树根的短语。,直接短语：简单子树的末端结点形成的 符号串是相对于简单子树根的直接短语。 或者：某子树根经过1步推导而获得的短语。,句柄：句型中最左直接短语。,2.4 语法树,短语:,i*i+i,i*i,第一个i,第二个i,第三个i,三个i都是直接短语,第一个i是句柄,注意:i+i不是句型的短语,句子 i*i+i,2.4 语法树,前例 对文法GS=(S,A,B,a,b,P,S),其中P为：,求出句型baSb的全部短语，直接短语和句柄。,SAB,AAa | bB,Ba | Sb,2.4 语法树,句型baSb的推导过程如下：,Sb 为句型的相对于B的短语、直接短

25、语,baSb 为句型的相对于S的短语,ba 为句型的相对于A的短语,a 为句型的相对于B的短语、直接短语和句柄,SABbBBbaBbaSb,SABASbbBSbbaSb,由语法树可知,2.5.1 文法的二义性,文法的某个句型是否只对应唯一的一棵 语法树呢？也就是，它是否只有唯一的一 个最左(最右)推导呢？,例如 设有文法GE：,句子 i*i+i 有两个不同的最左推导，对应两棵不同的语法树。,E E+E | E*E | (E) | i,2.5.1 文法的二义性,最左推导1 EE+EE*E+E i*E+Ei*i+E i*i+i,最左推导2 EE*Ei*E i*E+Ei*i+E i*i+i,2.5.

26、1 文法的二义性,如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。 或者说，若一个文法中存在某个句子，它有两个不同的最左 (最右) 推导，则这个文法是二义性的。,E E+E | E*E | (E) | i,2.5.2 文法二义性的消除,1. 不改变文法中原有的语法规则, 仅加 进一些非形式的语法规定。,2.5.2 文法二义性的消除,2. 构造一个等价的无二义性文法。即把排除二义性的规则合并到原有文法中, 改写原有的文法。,例如，对于上例文法GE，将运算符的 优先顺序和结合规则：*优先于; 、* 左结合加到原有文法中, 可构造出无二义 性文法如下 ：,2.5.2 文法二义性

27、的消除,则句子i*i+i只有唯一一棵语法树：,EE+T | T,TT*F | F,F(E) | i,2.5.2 文法二义性的消除,例2 定义某程序语言条件语句的文法G为:,试证明该文法是二义性的并消除之。,分析 该文法的句子 if b if b A else A 对应下面两棵不同的语法树：,Sif b S,| if b S else S,| A (其它语句）,2.5.2 文法二义性的消除,所以该文法是二义的。,Sif b S | if b S else S | A,句子 if b if b A else A,2.5.2 文法二义性的消除,消除文法的二义性可采用下面两种方法：,不改变已有规则，仅

28、 加进一非形式的语法规 定：else与前面最接近 的不带else的 if 配对。,文法G的句子 if b if b A else A 只对应唯一的一棵语法树，消除了二义。,2.5.2 文法二义性的消除,2. 改写文法G为G,S S1 | S2,S1 if b S1 else S1 | A,S2 if b S | if b S1 else S2,G:,Sif b S,| if b S else S,| A (其它语句）,G:,2.5.2 文法二义性的消除,这是因为通过分析，得知引起二义性的原因是: ifelse 语句的 if 后可以是if句型，因此改写文法时规定: if else之间只能是ife

29、lse语句或其他语句。,2.5.2 文法二义性的消除,S S1 | S2,S1 if b S1 else S1 | A,S2 if b S | if b S1 else S2,对改写后的文法，句子 if b if b A else A 只对应唯一的一棵语法树。,通常我们只说文法的二义性, 而不说语言的二义性, 这是因为可能有两个不同的文法G和G ，而且其中一个是二义性的，另一个是无二义性的, 但却有L(G)=L(G), 即这两个文法所产生的语言是相同的。,2.5.2 文法二义性的消除,应该指出的是文法的二义性和语言的二义性是两个不同的概念。,2.5.2 文法二义性的消除,将一个语言说成是二义性

30、的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。 例如 L= ai bj ck | i=j 或 j=k 且 i, j, k1 便是这种语言。,2.6 文法和语言的分类,著名的语言学家乔姆斯基(Chomsky) 将文法和语言分为四大类，即0型、1型、2型、3型。划分的依据是对文法中的规则施加不同的限制。,2.6 文法和语言的分类,0型文法（无限制文法）,若文法G=(VN,VT, P, S)中的每条规则 是这样一种结构：,而且中至少含一个非终结符, 则称G 是0型文法。,(VNVT)+ ,(VNVT)*,0型文法描述的语言是0型语言。,0型文法没有加任何限制条件，又称为 无限制性

31、文法，相应的语言称为无限制 性语言。,0型语言由图灵机识别。,2.6 文法和语言的分类,例如，有0型文法G=(VN,VT, P, S),其中：VN=A,B,S , VT=0,1,其描述的 0 型语言为 L0(GS)= ,P: S 0AB,1B 0,B SA | 01,A1 SB1,A0 S0B,2.6 文法和语言的分类,1型文法（上下文有关文法）,1型文法也称为上下文有关文法， 相应 的语言又称为上下文有关语言。,若文法G=(VN,VT, P, S)中的每一条规则的 形式为 A , 其中：, (VNVT)* ,AVN ,则称G是1型文法。,1型文法描述的语言是1型语言。,1型语言由线性界限自动

32、机识别。,(VNVT)+,2.6 文法和语言的分类,例如，有1型文法G=(VN,VT, P, S),其中：VN=S,A,B , VT=a,b,c,P: S aSAB | abB,BA BA,BA AA,AA AB,bA bb,bB bc,cB cc,其描述的1型语言为L1(GS)=anbncn | n1,2.6 文法和语言的分类,2型文法（上下文无关文法）,2型文法又称上下文无关文法，其产生的 语言又称为上下文无关的语言。,若文法G=(VN,VT, P, S)中的每一条规则的 形式为 A , 其中：,AVN ,(VNVT)*,则称G是2型文法。,2型文法描述的语言是2型语言。,2型语言由下推自

33、动机识别。,例如前面描述算术表达式的文法GE:,EE+E | E*E | (E) | i,2.6 文法和语言的分类,其描述的语言为 L2(GS)=x | x a, b+ 且x中a和b的个数相同,例如，有2型文法G=(VN,VT, P, S),其中：VN=S, A, B , VT=a, b,P= S aB | bA,A a | aS | bAA,B b | bS | aBB ,2.6 文法和语言的分类,2.6 文法和语言的分类,3型文法（正规文法）,右线性文法和左线性文法都称为3型文法。,若文法G=(VN,VT, P, S)中的每一条规则的形式 为A aB 或 A a , 其中：,A , BVN

34、, a VT*, 则称G是右线性文法。,若文法G=(VN,VT, P, S)中的每一条规则的形式 为A Ba 或 A a , 其中：,A , BVN , a VT*, 则称G是左线性文法。,3型文法描述的语言是3型语言。,3型语言由有穷自动机识别。,3型文法也称正规文法。正规文法产生的语言 称为正规语言。,例如，用左线性正规文法和右线性正规文法定义标识符,2.6 文法和语言的分类,用I代表标识符; l代表任意一个字母; d代表任意一个数字; 则定义标识符的文法为：,左线性文法: P: I l | Il | Id,右线性文法: P: I l | lT Tl | d | lT| dT,例如，用左线

35、性正规文法和右线性正规文法定义无符号整数,2.6 文法和语言的分类,用N代表无符号整数; d代表任意一个数字；则定义无符号整数的文法为：,左线性文法: P: N Nd | d,右线性文法: P: N dN | d,2.6 文法分类总结,0型文法： 左部： VN和VT组成(可以由多个VN多个VT组成,但至少一个VN) 右部： VN和VT组成(可以由多个VN多个VT组成)。 1型文法： 左部： VN和VT组成(可以由多个VN多个VT组成,且至少一个VN) 右部： VN和VT组成(可以由多个VN多个VT组成)。 |左部|=|右部|,2.6 文法分类总结,2型文法：左部：只有一个VN 。 右部：VN和

36、VT组成(可以由多个VN多个VT组成)。 3型文法：左部：只有一个VN 。 右部：最多一个VN ，且在最左或最右。,2.6 文法和语言的分类,从0型文法到3型文法, 是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法。 四类文法描述语言的关系： L0 L1 L2 L3 。,2.7 有关文法的实用限制和变换,1. 文法中不能含有形如A A 的规则。这种规则我们称之为有害规则。,对文法的实用限制有两点：,2.7 有关文法的实用限制和变换,2. 文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：,(1) 某条规则 A 的左部符号A(除S外)不在所属文法的任何其他规

37、则右部出现。,(2) 对文法中的某个非终结符A，无法从它推出任何终结符号串来。,2.7 有关文法的实用限制和变换,例如 设有文法GS:,P: S Bd,A Ad | d,B Cd | Ae,C Ce,D e,删除多余规则后的文法变换为:,P: S Bd,A Ad | d,B Ae,2.7 有关文法的实用限制和变换,若程序设计语言的文法含有多余规则， 其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。,作业,第1章,1、编译过程包括哪几个主要阶段及每个阶段的功能。,第2章,1、写一上下文无关文法G，它能产生配对的圆括号串（如：(),(),()()等，甚至包括0对括号） 2、

38、已知文法G：EE+T|E-T|T TT*F|T/F|F F(E) |i （1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。 （2）i-i+i 哪个算符优先。,第2章,3、文法G: EET+|T TTF*|F FFP|P PE|i （1）试证明符号串TET+*i是G的一个句型(要求画出语法树). （2）写出该句型的所有短语,直接短语和句柄. 4、已知文法G：SiSeS|iS|i ，该文法是二义文法吗？为什么？,本章重点介绍了语言的语法结构的形式描 述、语法树以及文法的二义性, 主要内容有：,1. 设计一个文法定义一个已知的语言,(1) 文法是一个四元组 G=(VN,VT, P,

39、 S)， 文法四大要素中，关键是一组规则, 它定义（或描述）了一个语言的结构。,从文法定义可知, 文法对于程序设计者来 说，文法给出了语言的精确定义和描述。,本章小结,本小结花时45分钟,(2) 分析已知语言句子的结构特征, 设计 出相应的一组规则，但不唯一。,(4) 若语言是无穷集合, 设计该语言的文 法一定是递归的。,本章小结,(3) 设计的文法必须能定义已知的语言, 不能超出或缩小所定义语言的范围。,分析 根据语言句子的结构特征，设计出相 应规则,例1. 给出语言 L2=an bm| mn1 的文法,P2: SAB,L2=ab,abb,abbb, aabb,aabbb,aabbbb, a

40、aabbb, aabbbb，,AaAb | ab,BbB |,本章小结,分析 根据语言句子的结构特征，设计出相 应规则,例2. 给出语言 L1=a2n+1|n0 的文法,P1: AaB | a,P1：AaAa | a,或,L1=a, aaa, aaaaa, aaaaaaa, aaaaaaaaa，,Baa | aBa,本章小结,本章小结,分析 根据语言句子的结构特征，设计出相应规则,例3. 给出语言L3=anbmck| n,m,k0的文法,P3: AaA | bB | cC |,P3: AaA | B,或,L3=,a,aa,aaa,b,bb,bbb,c,cc,ccc, , ab,abb, ,bc

41、,bcc，,CcC |,BbB | cC |,CcC |,BbB | C,本章小结,L4=0 ,2,4,6,8,10,12,14,16,18,20,22,24,26,例4. 写一个 文法,使其语言是正偶数的集合,每个偶数不以0开头。,P4: NE | AE,N0 | 2 | 4 | 6 | 8 |BN,或,分析 不以0开头的偶数集合中串的结构特征:,AD | AD,E0 | 2 | 4 | 6 | 8,D1 | 2 | 3 | | 9,D0 | 1 | 2 | 3 | 9,B1 | 2 | 3 | | 9 |B0,P4:,本章小结,A 0A1 | ,P : S 1S0 | 0A1 | ,例5.

42、 给出语言L=1n0m1m0n | n,m0的 文法。,分析 根据语言句子的结构特征, 设计 出相应规则,L=,01,0011,10,1100,1010,100110, 110100,11001100,本章小结,P : S a | 0S0 | 1S1,例6. 给出语言L=WaWt | W0|1*,Wt 表示W的逆的文法。,分析 根据语言句子的结构特征，设计 出相应规则,L=a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11, 101a101, 110a011, 100a001, ,W=,0, 1 ,01, 10, 00, 11, 101, 110, 100, 111

43、, ,本章小结,2. 已知一个文法，确定该文法所定义的 语言。,(2) 给定一个文法，可根据语言和推导定 义推导出文法的句子，从而确定出该文法 所定义的语言。,本章小结,自然语言描述。 例如, L=x|xa,b+且x中a,b个数相同,式子描述。例如 L=a2nbb | n0。,正规式描述。,(3) 语言可用,本章小结,例1 文法GA=(A,a,b,AbA | a, A) 所生成的语言是什么？,分析 AbAbbAbbbAbnAbna, L(GA)= bna | n0 ,本章小结,例2 文法GN为:,N ND | D D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,

44、(1) GN所生成的语言是什么？,(2) 给出句子0127的最左、最右推导。,本章小结,L(GN)= | 0,1,2, 9+,= | 为可带前导0的正整数,= | 为数字串,最左推导:,NNDN7ND7N27ND27 N127D1270127,最右推导:,NNDNDDNDDDDDDD 0DDD01DD012D0127,N ND | D D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,本章小结,例3. 已知文法GS=( A,B,a,b,c,d, P, S ) , 其中 P 为:,分析 SABaAbBa2Ab2B an-1Abn-1BanbnBanbncBd anb

45、nc2Bd2 anbncm-1Bdm-1anbncmdm, L(GS)=anbncmdm | n ,m1 ,该文法 所生成的语言是什么？,A aAb | ab,B cBd | cd,S AB,本章小结,3. 求句型的短语、直接短语和句柄,(1) 短语、直接短语和句柄是对某句 型而言的。,(2) 短语总是句型的某个子串，它对应 子树未端结点形成的符号串。,(3) 直接短语是某条规则右部，它对应 简单子树未端结点形成的符号串。,(4) 最左边的直接短语是句柄。,本章小结,例1 已知文法GE：,证明 E+T*F是它的一个句型,指出这个句型的短语直接短语和句柄。, EE+TE+T*F,短语: E+T*

46、F、T*F, E+T*F是它的一个句型。,画出该句型的语法树:,句柄: T*F,直接短语: T*F,EE+T | E-T | T,TT*F | T/F | T,T(E) | i,本章小结,例2 已知文法GS：,试找出符号串(a)和(A(SaA)(b)的短语 直接短语和句柄(如果有的话)。,S(AS) | (b),A(SaA) | (a), 符号串(a)不是文法的句型，因此 它没有短语直接短语和句柄。,本章小结,S(AS)(A(AS)(A(A(b) (A(SaA)(b),符号串(A(SaA)(b)是文法的句型，画出该句型的语法树如下图：,S(AS) | (b),A(SaA) | (a),本章小结

47、,从句型的语法树求 短语: (A(SaA)(b) (SaA)(b) (SaA) (b),直接短语：(SaA)、(b),句柄：(SaA),S(AS) | (b),A(SaA) | (a),对于句型(A(SaA)(b),本章小结,4文法二义性的判断,一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左（最右）推导，则该文法是二义性的。,本章小结,例1 设有文法GS: SiSeS| iS | i,试证明文法GS有二义性。,分析 因为对文法的句子 iiiei 有如下两 棵不同的语法树与之对应，所以该文法 是二义的,本章小结,SiSeS| iS | i,句子 iiiei 对应下面两颗语法树：,本

48、章小结,NSE | E SSD | D E0 | 2 | 4 | 6 | 8 | 10 D0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,1.试证明文法GN有二义性。,2.此文法所描述的语言是什么？,3. 试写出另一文法G使L(G)=L(G)且 G是无二义性的。,例2 设有文法GN:,本章小结,分析 因为对文法的句子10有两棵不同的语法树与之对应，所以该文法是二义的,NSE | E SSD | D E0 | 2 | 4 | 6 | 8 | 10 D0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,本章小结,该文法所描述的语言是所有无符号偶数 的集合(可以0开头)。,改写后的文法GS为: NSE | E SSD | D E0 | 2 | 4 | 6 | 8 D0 | 1 | 2 | 3 | 4 | 5| 6 | 7 | 8 | 9,NSE | E SSD | D E0 | 2 | 4 | 6 | 8 | 10 D0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,