高级语言及其语法描述.ppt-得力文库

资源描述

《高级语言及其语法描述.ppt》由会员分享，可在线阅读，更多相关《高级语言及其语法描述.ppt（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二章第二章高级语言及其语法描述高级语言及其语法描述2.1 程序语言的定义程序语言的定义2.2 程序语言的语法描述程序语言的语法描述第二章第二章高级语言及其语法描述高级语言及其语法描述22022/10/28软件学院2.1 程序语言的定义程序语言的定义n一个程序设计语言是一个记号系统，其完整的定一个程序设计语言是一个记号系统，其完整的定义应包括语法和语义两个方面义应包括语法和语义两个方面语言的语法是指一组规则，用它可以形成和产生一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序合适的程序n上下文无关文法上下文无关文法语法只定义什么样的符号序列是合法的，与这些符号语法只定义什么样的符

2、号序列是合法的，与这些符号的含义毫无关系的含义毫无关系nPASCAL语言中：语言中：A:=B+C合乎语法规则，合乎语法规则，A:=B+不合乎不合乎语法规则语法规则n阐明语法的一个工具是文法，这是形式语言理论阐明语法的一个工具是文法，这是形式语言理论的基本概念之一的基本概念之一第二章第二章高级语言及其语法描述高级语言及其语法描述32022/10/28软件学院2.2 程序语言的语法描述程序语言的语法描述n基本概念基本概念字母表、符号、符号串、闭包等字母表、符号、符号串、闭包等n文法的定义文法的定义n文法的分类文法的分类Chromsky对文法的分类对文法的分类n文法和语言文法和语言推导、归约、句型

3、、句子、语言推导、归约、句型、句子、语言n语法分析树和二义性语法分析树和二义性第二章第二章高级语言及其语法描述高级语言及其语法描述42022/10/28软件学院基本概念基本概念n字母表字母表元素的非空有限集，记为元素的非空有限集，记为。例：例：=a，b，c字母表中的元素称为符号。例：字母表中的元素称为符号。例：a，b，c，字母表包含了语言中所允许出现的所，字母表包含了语言中所允许出现的所有符号有符号n符号串符号串符号的有穷序列。例：符号的有穷序列。例：a,aa,ac,abc，.，无任何符号的符号串称为空，无任何符号的符号串称为空符号串，记为符号串，记为第二章第二章高级语言及其语法描述高级语

4、言及其语法描述52022/10/28软件学院不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为用用*表示表示上的所有字的全体上的所有字的全体,包含空包含空字字例如例如:设设 =a=a，bb，则，则 *=,a,b,aa,ab,ba,bb,aaa,.,a,b,aa,ab,ba,bb,aaa,.注：约定用a,b,c,表示符号；用,表示符号串；用A,B,C,表示其集合。第二章第二章高级语言及其语法描述高级语言及其语法描述62022/10/28软件学院基本概念基本概念n符号串运算符号串运算符号串长度符号串长度nx为符号串为符号串,其长度其长度|x|等于组成该符号串等于组成该符号串的符

5、号个数。例：的符号个数。例：x=string，则，则|x|=6,|=0符号串连接符号串连接n若若x、y是定义在是定义在上的符号串，则上的符号串，则xy称为称为x和和y的的连连接，接，xy也是也是上的符号串上的符号串nxx=x第二章第二章高级语言及其语法描述高级语言及其语法描述72022/10/28软件学院基本概念基本概念符号串集合的乘积符号串集合的乘积n令令A、B为符号串集合，定义符号串集合乘积为符号串集合，定义符号串集合乘积 AB xy|x A,y B符号串集合的方幂符号串集合的方幂n符号串集合符号串集合A，定义，定义A0=,A1=A,A2=AA,A3=A2A,AnAn-1A=AAn-1，

6、n0符号串集合的正闭包符号串集合的正闭包nA+=A1 A2 An 符号串集合的自反闭包符号串集合的自反闭包nA*=A+第二章第二章高级语言及其语法描述高级语言及其语法描述n设：设：U a,aa n那么：那么：U*=,a,aa,aaa,aaaa,U=a,aa,aaa,aaaa,第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院2.3.1 2.3.1 上下文无关文法上下文无关文法n文法文法：描述语言的语法结构的形式规则描述语言的语法结构的形式规则nHe gave me a book.He He me me book book a a gave gave第二章第二章高级语言及

7、其语法描述高级语言及其语法描述软件学院软件学院 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n上下文无关文法的定义：上下文无关文法的定义：一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合(非空非空)V VN N：非终结符集合：非终结符集合(非空非空)，且，且V VT

8、T V VN N=S S：文法的开始符号，：文法的开始符号，S S V VN NP P：产生式集合：产生式集合(有限有限)，每个产生式形式为，每个产生式形式为P P，P P V VN N，(V VT T V VN N)*开始符开始符S S至少必须在某个产生式的左部出现至少必须在某个产生式的左部出现一次。一次。第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法 G=，其中，其中，P由下列产生式组成：由下列产生式组成：E iE E+EE E*EE (E)第二章第二章高级语言及其语法描述高级语言及其语法描述软件

9、学院软件学院n几点规定：几点规定：“”也可以用也可以用“:=表示，表示，这种表示称为这种表示称为巴科斯范式巴科斯范式(BNF)P 1 P 2 可缩写为可缩写为 P 1|2|n P n 其中，其中，“|”读成读成“或或”，称为，称为P的一个候选式。的一个候选式。表示一个文法时，通常只给出开始符号和产生式，表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：如上例，可表示为：G(E)：E i|E+E|E*E|(E)n例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法 G=，其中，其中，P由下列产生式组成：由下列产生式组成：E iE E+EE E*EE (E)第二章第二章

10、高级语言及其语法描述高级语言及其语法描述软件学院软件学院n定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式，且且，(VT VN)*。n如果如果 1 2 n，则我们称这个序列是从，则我们称这个序列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则的推导，则称称 1可以可以推导推导出出 n。n对文法对文法G(E)：E i|E+E|E*E|(E)E (E)(E+E)(i+E)(i+i)第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n通常，用通常，用表示：从表示：从 1 1出发，经过出发，经过一步或

11、若干步，可以推出一步或若干步，可以推出 n n。用用表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。所以所以：即即或或q定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果，则，则称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全体所产生的句子的全体是一个是一个语言语言，将它记为，将它记为 L(G)L(G)。第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n例：例：(i*i+i)是文法是文法G(E)

13、第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院q例：给出产生语言为例：给出产生语言为anbn|n 1的文法。的文法。G3(S)：S aSb S ab第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院q例：给出产生语言为例：给出产生语言为ambn|1 n m 2n的文法。的文法。G4(S)：S aSb|aaSb S ab|aab 第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n从一个句型到另一个句型的推导往往不唯从一个句型到另一个句型的推导往往不唯一。一。E+Ei+Ei+i E+EE+ii+in最左推导最左推导：任何一步：任何一步都

14、是对都是对中的中的最左非终结符进行替换。最左非终结符进行替换。最右推导最右推导：任何一步：任何一步都是对都是对中的中的最右非终结符进行替换。最右非终结符进行替换。第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院2.3.2 2.3.2 语法树与二义性语法树与二义性n用一张图表示一个句型的推导用一张图表示一个句型的推导,称为语法树。称为语法树。n(i*i+i)(i*i+i)的语法树的语法树E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E(E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)一棵语法树是不同推导过程的共性抽象。一棵

15、语法树是不同推导过程的共性抽象。G(E)：E i|E+E|E*E|(E)(i*i+i)第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n如果使用最左如果使用最左(右右)推导，则一个最左推导，则一个最左(右右)推导与语法树一一对应。推导与语法树一一对应。n一个句型是否只对应唯一一棵语法树？一个句型是否只对应唯一一棵语法树？第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n定义定义：如果一个文法存在某个句子对应两如果一个文法存在某个句子对应两颗不同的语法树颗不同的语法树，则说这个则说这个文法是二义的文法是二义的。G(E)：E i|E+E|E*E|(E)是

16、二义文是二义文法。法。n语言的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如，如果对它不存在无二义性的文法。果对它不存在无二义性的文法。可能存在可能存在G和和G，一个为二义的，一个为无二，一个为二义的，一个为无二义的。但义的。但L(G)=L(G)n二义性问题是不可判定问题，即不存在一二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。一个文法是否是二义的。n可以找到一组无二义文法的充分条件。可以找到一组无二义文法的充分条件。第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院二义文法

18、程序设计语言时，对于上下文无关文法的限制法的限制：1 1 不含不含P PP P形式的产生式形式的产生式2 2 每个非终结符每个非终结符P P必须有用处必须有用处即：即：第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院2.3.3 2.3.3 形式语言鸟瞰形式语言鸟瞰nChomsky于于1956年建立形式语言体系，年建立形式语言体系，他把文法分成四种类型：他把文法分成四种类型：0，1，2，3型。型。n与上下文无关文法一样，它们都由四部与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。分组成，但对产生式的限制有所不同。第二章第二章高级语言及其语法描述高级语

19、言及其语法描述软件学院软件学院0型型(短语文法，图灵机短语文法，图灵机)：产生式形如：产生式形如：其中：其中：(VT VN)*且至少含有一个非且至少含有一个非终结符；终结符；(VT VN)*1型型(上下文有关文法，线性界限自动机上下文有关文法，线性界限自动机)：产生式形如：产生式形如：其中：其中：|，仅，仅 S 例外。例外。第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)：产生式形如：产生式形如：A 其中：其中：A VN；(VT VN)*。3型型(正规文法，有限自动机正规文法，有限自动机)：产生式形

20、如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN 产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN右线性文法右线性文法左线性文法左线性文法第二章第二章高级语言及其语法描述高级语言及其语法描述312022/10/28软件学院文法举例文法举例n文法文法G=(S,A,B,a,b,c,d,e,S,P),其中，其中，P=S abcA|edB,A beB,B d文法文法G是右线性文法是右线性文法改写为正规文法改写为正规文法正规文法产生式只能有两种形式正规文法产生式只能有两种形式AB或或A 其中其中A,B VN,VTn相应的正规文法为：相应的正规文法为：G=(S

21、,A,B,A,B,C,D,a,b,c,d,e,S,P),P=S aA|eB,A bC,C cA,B dB,A bD,D eB,B d第二章第二章高级语言及其语法描述高级语言及其语法描述322022/10/28软件学院第二章第二章高级语言及其语法描述高级语言及其语法描述332022/10/28软件学院S=0A=010A=0(10)*A=0(10)*第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院四种类型描述能力比较四种类型描述能力比较0型1型2型3型第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院nL5=anbn|n 1 不能由正规文法产生，不能由

22、正规文法产生，但可由上下文无关文法产生：但可由上下文无关文法产生：G5(S)：S aSb|abnL6=anbncn|n 1不能由上下文无关文不能由上下文无关文法产生，但可由上下文有关文法产生：法产生，但可由上下文有关文法产生：G6(S)：S aSBC|aBC CB BC aB ab bB bb bC bc cC cc第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院n程序设计语言不是上下文无关语言，甚至程序设计语言不是上下文无关语言，甚至不是上下文有关语言不是上下文有关语言。nL7=c|(a|b)*不能由上下文不能由上下文无关文法产生，甚至连上下文有关文法也无关文法产生，甚

23、至连上下文有关文法也不能产生，只能由不能产生，只能由0 0型文法产生。型文法产生。标识符引用标识符引用过程调用过程中，过程调用过程中，形形-实参数地对应性实参数地对应性(如如个数，顺序和类型一致性个数，顺序和类型一致性)n现今程序设计语言的语言结构，用上下文现今程序设计语言的语言结构，用上下文无关文法描述就足够了。无关文法描述就足够了。第二章第二章高级语言及其语法描述高级语言及其语法描述L(G1)=ai(a|b)|i=0 例：设文法G2(S,a,b,P,S)其中P为:(0)S aSb (1)S abL(G2)=anbn|n=1例：设文法G1(S,a,b,P,S)其中P为:(0)S aS (1

24、)S a (2)S b第二章第二章高级语言及其语法描述高级语言及其语法描述注意：在词法分析和语法分析中对产生式有限注意：在词法分析和语法分析中对产生式有限制制不存在不存在P P产生式产生式,因为它的存在除了增加二因为它的存在除了增加二义性外没有任何用处义性外没有任何用处产生式中出现的任何非终结符产生式中出现的任何非终结符P必须是可达的，必须是可达的，并且能推出终结符串。并且能推出终结符串。n从开始符号从开始符号S出发，存在推导出发，存在推导S P nP必须能推导出终结符串。即必须能推导出终结符串。即:P ;VT*.*+第二章第二章高级语言及其语法描述高级语言及其语法描述例：设例：设L1=a

25、2nbn|n=1 且且a,b VT试试构造生成构造生成L1的文法的文法G1设设n=1，L1=aab n=2，L1=aaaabb n=3，L1=aaaaaabbb所以得：所以得：S aaSb S aab一、由语言构造文法一、由语言构造文法第二章第二章高级语言及其语法描述高级语言及其语法描述一、由语言构造文法一、由语言构造文法例：设例：设L2=aibjck|i,j,k=1 且且a,b,c VT试构造生成试构造生成L2的文法的文法G2S aS S aBB bB B bCC cC|c第二章第二章高级语言及其语法描述高级语言及其语法描述一、由语言构造文法一、由语言构造文法例：设例：设L3=|(a,b

26、)*且且中含有中含有相同个数的相同个数的a和和b试构造生成试构造生成L3的文法的文法G3S S bB，S aAA bS|b,A aAAB aS|a|bBB(0)S S aSbSS bSaS 第二章第二章高级语言及其语法描述高级语言及其语法描述一、由语言构造文法一、由语言构造文法例：设例：设L4=|(0,1)*且且中中1的的个数为偶数个数为偶数试构造生成试构造生成L4的文法的文法G4S S 0S，S 1AA 0A,A 1S第二章第二章高级语言及其语法描述高级语言及其语法描述二、文法简化二、文法简化 1、由于同一语言可以用不同的文法来描述，、由于同一语言可以用不同的文法来描述，显然应当选择

27、产生式的个数最少，最符合语显然应当选择产生式的个数最少，最符合语言特征的来描述。言特征的来描述。2、在文法中，有些产生式对推导不起作用，、在文法中，有些产生式对推导不起作用，要删除掉。要删除掉。如某个产生式在推导过程中永远不会被用到，即如某个产生式在推导过程中永远不会被用到，即由开始符号推导，永远推不到它左部的非终结符。由开始符号推导，永远推不到它左部的非终结符。再如永远导不出终结符串的产生式。再如永远导不出终结符串的产生式。如形如如形如PP的产生式。的产生式。第二章第二章高级语言及其语法描述高级语言及其语法描述二、文法简化二、文法简化3、简化步骤：、简化步骤：n查找有无形如查找有无形如PP

28、的产生式，若有则删除；的产生式，若有则删除；n若某个产生式在推导过程中永远不会被用若某个产生式在推导过程中永远不会被用到，删除它；到，删除它；n若某个产生式在推导过程中不能从中导出若某个产生式在推导过程中不能从中导出终结符，删除它。终结符，删除它。n最后，整理所有剩余产生式，就得到简化最后，整理所有剩余产生式，就得到简化的文法。的文法。第二章第二章高级语言及其语法描述高级语言及其语法描述二、文法简化二、文法简化例：化简下面的文法。例：化简下面的文法。(0)S Be (1)S Ec (2)A Ae (3)A e (4)A A (5)B Ce (6)B Af (7)C Cf (8)D f(0)S

29、 Be (1)A Ae (2)A e (3)B Af 第二章第二章高级语言及其语法描述高级语言及其语法描述三、构造无三、构造无产生式的上下文无关文法产生式的上下文无关文法1、无、无产生式的上下文无关文法要满足条件产生式的上下文无关文法要满足条件若若P中含中含S ，则，则S不出现在任何产生式右部，不出现在任何产生式右部，其中其中S为文法的开始符号；为文法的开始符号；P中不再含有其它任何中不再含有其它任何产生式。产生式。2、构造无、构造无产生式的上下文无关文法变换算法：产生式的上下文无关文法变换算法：G=(VN,VT,P,S)G=(VN,VT,P,S)（1）由文法）由文法G找出所有经过若

30、干步推导能推出找出所有经过若干步推导能推出的非的非终结符，放在终结符，放在V0集合中。集合中。第二章第二章高级语言及其语法描述高级语言及其语法描述三、构造无三、构造无产生式的上下文无关文法产生式的上下文无关文法2、构造无、构造无产生式的上下文无关文法变换算法产生式的上下文无关文法变换算法 2）按下列步骤构造）按下列步骤构造G的产生式集合的产生式集合P A)若若V0集合中的某元素出现在某产生式的右端，则集合中的某元素出现在某产生式的右端，则将它变成两个产生式：分别以将它变成两个产生式：分别以和其原型代入；将新产和其原型代入；将新产生式加入生式加入P B)不满足上一条的不满足上一条的P中

32、(2)S baS|bSaS|bSa|ba第二章第二章高级语言及其语法描述高级语言及其语法描述软件学院软件学院作业作业nP36-6，7，8，9，10，11第二章第二章高级语言及其语法描述高级语言及其语法描述502022/10/28软件学院文法的分类文法的分类n对产生式施加不同的限制得到不同类型的文法对产生式施加不同的限制得到不同类型的文法0型（无限制文法）:G=(VN,VT,S,P)规规则形式则形式：;(VN VT)+,(VN VT)*且且中至少含有一个非终结符中至少含有一个非终结符1型（上下文有关）:规则规则有有 1,其中其中=1A2,=12;A VN,(VN VT)+,1,2 (VN

33、 VT)*.规规则形则形式式 1A 2 12;2型（上下文无关）:规规则形式则形式:A,A VN，(VN VT)+3型（右线性和正规文法）:规则形式规则形式:AB或或A（右右线性）线性）A,B VN,(VT)*.第二章第二章高级语言及其语法描述高级语言及其语法描述512022/10/28软件学院左线性文法n规则形式规则形式:AB 或或A（左左线性）线性）A,B VN,(VT)*.正规文法n规则形式规则形式:AB或或A 其中其中A,B VN,VT，如果，如果S P，则，则S不能出现在任何产生式右边不能出现在任何产生式右边n正规文法中只能出现单个终结符，右线性文法中可能正规文法中只能出现单个终结

34、符，右线性文法中可能出现若干个终结符组成的串出现若干个终结符组成的串2型文法扩充型文法扩充nA,A VN，(VN VT)*n允许有空产生式：允许有空产生式：A n不改变描述能力不改变描述能力第二章第二章高级语言及其语法描述高级语言及其语法描述522022/10/28软件学院n四个文法类的定义是逐渐增加限制的，因四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是而每一种上下文有关文法都是0型文法。型文法。n称称0型文法产生的语言为型文法产生

35、的语言为0型语言。上下文型语言。上下文有关文法、上下文无关文法和正规文法产有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下生的语言分别称为上下文有关语言、上下文无关语言和正规语言文无关语言和正规语言n现今大多数高级程序设计语言采用上下文现今大多数高级程序设计语言采用上下文无关文法来描述其语法已经足够了无关文法来描述其语法已经足够了第二章第二章高级语言及其语法描述高级语言及其语法描述532022/10/28软件学院文法和语言文法和语言n上下文无关文法定义的语言上下文无关文法定义的语言从文法的开始符号出发，反复使用产生式，对非终结从文法的开始符号出发，反复使用产生式，对非

36、终结符进行替换和展开，直至推导出语言的各种句子来符进行替换和展开，直至推导出语言的各种句子来n推导与归约的概念推导与归约的概念推导、最左推导、最右推导、规范推导推导、最左推导、最右推导、规范推导归约、最左归约、最右归约、规范归约归约、最左归约、最右归约、规范归约n句型、句子、语言的形式定义句型、句子、语言的形式定义n语法分析树与二义性语法分析树与二义性第二章第二章高级语言及其语法描述高级语言及其语法描述542022/10/28软件学院推导和归约推导和归约第二章第二章高级语言及其语法描述高级语言及其语法描述552022/10/28软件学院n最左推导和最右推导最左推导和最右推导n规范推导规范推

37、导最右直接推导又称为规范直接推导，最右最右直接推导又称为规范直接推导，最右推导又称为规范推导推导又称为规范推导第二章第二章高级语言及其语法描述高级语言及其语法描述562022/10/28软件学院n最右归约和最左归约的定义最右归约和最左归约的定义第二章第二章高级语言及其语法描述高级语言及其语法描述572022/10/28软件学院句型、句子、语言的定义句型、句子、语言的定义n定义定义2.6 设设S是文法是文法G的识别符号，如果的识别符号，如果S u,则称符号串则称符号串u为文法为文法G的句型的句型n定义定义2.7 设设S是文法是文法G的识别符号，如果的识别符号，如果S u,u VT*,则称符号

38、串则称符号串u为文法为文法G的句子的句子n定义定义2.7 设设S是文法是文法G的识别符号，文法的识别符号，文法G的的语言语言L(G)=u|S u且且u VT*,即即文法的语言是文法所有句子的集合文法的语言是文法所有句子的集合*第二章第二章高级语言及其语法描述高级语言及其语法描述582022/10/28软件学院例例n文法文法G=(VN,VT,S,P)，其中，其中VN=S，VT=0，1，P=S0S1，S01。这。这里，非终结符集中只含一个元素里，非终结符集中只含一个元素S；终结符；终结符集由两个元素集由两个元素0和和1组成；有两条产生式；组成；有两条产生式；开始符号是开始符号是S第二章第二章高

39、级语言及其语法描述高级语言及其语法描述592022/10/28软件学院直接推导示例直接推导示例n对于例的文法对于例的文法G，有如下直接推导示例，有如下直接推导示例u=0S1,w=0011,直接推导：直接推导：0S1=0011，使用的规则：使用的规则：S01，这里，这里=0，=1。u=S,w=0S1，直接推导：，直接推导：S=0S1使用的规使用的规则：则：S0S1，这里，这里=，=u=0S1,w=00S11,直接推导：直接推导：0S1=00S11，使用的规则：，使用的规则：S0S1，这里，这里=0，=1。第二章第二章高级语言及其语法描述高级语言及其语法描述602022/10/28软件学院n对例

40、的文法，存在直接推导序列对例的文法，存在直接推导序列v=0S1=00S11=000S111=00001111=w，即，即0S1=+00001111，也可记作也可记作0S1=*00001111nS，0S1，000111都是例文法都是例文法G的句型，其的句型，其中中000111是是G的句子的句子第二章第二章高级语言及其语法描述高级语言及其语法描述612022/10/28软件学院n考虑例的文法考虑例的文法G，有两条产生式，有两条产生式(规则规则)：(1)S0S1和和(2)S01，通过对第一个产，通过对第一个产生式使用生式使用n-1次，然后使用第次，然后使用第2个产生式一个产生式一次，得到：次，得到

41、：S=0S1=00S11=0n-1S1n-1=0n1n可以推知可以推知L(G)中的元素仅是这样的串中的元素仅是这样的串(0n1n)。从而可证明。从而可证明L(G)=0n1n|n1.第二章第二章高级语言及其语法描述高级语言及其语法描述622022/10/28软件学院文法等价文法等价n若若L(G1)=L(G2)，则称，则称文法G1和和G2是是等价的。的。也就是说，如果两个文法定义的语言也就是说，如果两个文法定义的语言一样，则称这两个文法是等价的。一样，则称这两个文法是等价的。例如文法例如文法GA：A0RA01RA1和例的文法等价。和例的文法等价。第二章第二章高级语言及其语法描述高级语言及其语法

42、描述632022/10/28软件学院证明证明(i*i+i)是算术表达式是算术表达式n文法文法G=(VN,VT,S,P)VN=EVT=i,+,*,(,)S=EE i|E+E|E*E|(E)描述了算术表达式描述了算术表达式n证明证明(i*i+i)是算术表达式是算术表达式如果能从文法如果能从文法G中推导出中推导出(i*i+i),则可证明则可证明它是算术表达式它是算术表达式第二章第二章高级语言及其语法描述高级语言及其语法描述642022/10/28软件学院n推导过程推导过程E=(E)产生式：产生式：E(E)=(E+E)产生式：产生式：E E+E =(E*E+E)产生式：产生式：E E*E =(i*E

43、+E)产生式：产生式：E i =(i*i+E)产生式：产生式：E i =(i*i+i)产生式：产生式：E i存在一个从存在一个从E到到(i*i+i)的推导，证明了的推导，证明了(i*i+i)是文法是文法G所定义的一个算术表达式所定义的一个算术表达式第二章第二章高级语言及其语法描述高级语言及其语法描述652022/10/28软件学院语法分析树语法分析树n我们用一张树型结构的图来描述一个句子的推导，这种表我们用一张树型结构的图来描述一个句子的推导，这种表示称为语法树。示称为语法树。n语法树的根结由文法开始符号标记。随着推导的进行，当语法树的根结由文法开始符号标记。随着推导的进行，当某个非终结符被

44、它的候选式所替换时，此非终结符生出其某个非终结符被它的候选式所替换时，此非终结符生出其下一代新结，候选式中自左至右没有符号对应着一个新结。下一代新结，候选式中自左至右没有符号对应着一个新结。n性质：在语法树生长的任何时候，所有那些没有性质：在语法树生长的任何时候，所有那些没有后代的端末结自左至右的排列起来，就是一个句后代的端末结自左至右的排列起来，就是一个句型。型。n语法分析树的生成过程：书中第语法分析树的生成过程：书中第31页页第二章第二章高级语言及其语法描述高级语言及其语法描述662022/10/28软件学院n(i*i+i)的语法树的语法树E=(E)产生式：E(E)=(E+E)产生式：E

45、 E+E =(E*E+E)产生式：E E*E =(i*E+E)产生式：E i =(i*i+E)产生式：E i =(i*i+i)产生式：E iE=(E)产生式：E(E)=(E*E)产生式：E E*E =(i*E)产生式：E i =(i*E+E)产生式：E E+E =(i*i+E)产生式：E i =(i*i+i)产生式：E i第二章第二章高级语言及其语法描述高级语言及其语法描述672022/10/28软件学院文法的二义性文法的二义性n一个文法，如果它的一个句子有两棵或两一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性。棵以上的语法树，则称此句子具有二义性。如果一个文法含有

46、二义性的句子，则该文如果一个文法含有二义性的句子，则该文法具有二义性。法具有二义性。n换一个说法：如果一个文法存在某个句子换一个说法：如果一个文法存在某个句子对应两棵或两棵以上不同的语法树，则称对应两棵或两棵以上不同的语法树，则称该文法是二义的该文法是二义的第二章第二章高级语言及其语法描述高级语言及其语法描述682022/10/28软件学院n例例1 n注：文法的二义性是不可判定的，但可以通过约注：文法的二义性是不可判定的，但可以通过约定加以改造。定加以改造。n例例2文法文法G1：A AN|N N0|1|9 则则L(G1)为无符号整数为无符号整数n例例3文法文法G2：BaBb|ab,求求L(G

48、其语法描述高级语言及其语法描述712022/10/28软件学院n习题习题2.6 文法文法G的产生式的产生式 P=N ND|D,D 0|1|2|3|4|5|6|7 写出下列符号串的最左推导和最右推导写出下列符号串的最左推导和最右推导 (1)3274;(2)65173 3274的最左推导的最左推导 N=ND=NND=NNND=DNND =3NND=3DND=32ND =32DD=327D=3274 3274的最右推导的最右推导 N=ND=N4=ND4=N74=ND74 =N274=D274=3274第二章第二章高级语言及其语法描述高级语言及其语法描述722022/10/28软件学院n习题习题判定下列文法是否是歧义的判定下列文法是否是歧义的 (1)文法的产生式如下文法的产生式如下 P=S AB,A a|ab,B c|bc 解答：该文法是歧义的，因为存在一解答：该文法是歧义的，因为存在一个句子个句子abc，它对应两棵不同的语法树。，它对应两棵不同的语法树。（也可以说：存在一个句子（也可以说：存在一个句子abc，它有两种，它有两种不同形式的最左推导，即不同形式的最左推导，即S=AB=aB=abc和和S=AB=abB=abc）

展开阅读全文