编译原理第二章

1、第二章第二章 高级语言及其语法描述高级语言及其语法描述 n常用的高级语言常用的高级语言 FORTRANFORTRAN数值计算数值计算 COBOLCOBOL事务处理事务处理 PASCALPASCAL结构程序设计结构程序设计 ADAADA大型程序、嵌入式实时系统大型程序、嵌入式实时系统 PROLOGPROLOG逻辑程序设计逻辑程序设计 ALGOLALGOL算法语言算法语言 C/C+C/C+系统程序设计系统程序设计 JavaJavaInternetInternet程序设计程序设计n与机器语言或汇编语言比较与机器语言或汇编语言比较，高级语言高级语言的优点：的优点：较接近于数学语言和工程语言较接近于数学

2、语言和工程语言，比较直观、比较直观、自然和易于理解自然和易于理解; ;便于验证其正确性便于验证其正确性，易于改错易于改错; ;编写效率高编写效率高; ;易于移植易于移植. .2.3 2.3 程序语言的语法描述程序语言的语法描述 n几个概念几个概念: :考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集其中每一个元素称为一个其中每一个元素称为一个字符字符上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所构中的字符所构成的一个有穷序列成的一个有穷序列不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为用用* *表示表示上的所有字的全体上的所有字的全体, ,包含空

3、字包含空字例如例如: : 设设 =a=a， bb，则，则 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n表示不含任何元素的空集。表示不含任何元素的空集。n、和和区别：区别： 是一个空字，是集合中的一个元素；是一个空字，是集合中的一个元素； 是一个空集合，即是一个空集合，即 ； 是一个有一个元素的集合。是一个有一个元素的集合。n*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V n设：设：U a, aa V b, bb n那么：那么：UV= ab, abb, aab, aabb nV自身的自身的 n次积记为次

4、积记为Vn=VV Vn规定规定V0= ，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包;n记记 V+VV* ，称，称V+是是V的正规闭包。的正规闭包。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 He me book a gave He He He gave He

5、 gave He gave me He gave me He gave me a He gave me a bookn一个上下文无关文法一个上下文无关文法G包括四个部分包括四个部分n一组终结符号：组成语言的基本符号一组终结符号：组成语言的基本符号n一组非终结符号：代表语法范畴一组非终结符号：代表语法范畴n一个开始符号：特殊的非终结符号一个开始符号：特殊的非终结符号n一组产生式：语法范畴的一种书写规则一组产生式：语法范畴的一种书写规则 如：如： An上下文无关文法的定义：上下文无关文法的定义： 一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN

6、N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合( (非空非空) )V VN N：非终结符集合：非终结符集合( (非空非空) )，且，且V VT 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例，变量例，变量E E是一个算术表达式；若是一个算术表达式；若E E1 1和和E E2 2是算

7、术表达式，则是算术表达式，则E E1 1+E+E2 2、E E1 1* *E E2 2和（和（E E）也是算术表达式。也是算术表达式。 定义只含定义只含+ +，* *的算术表达式的文法的算术表达式的文法 G=iG=P， 其中，其中，P P由下列产生式组成：由下列产生式组成：E E i iE E E+E E+EE E E E* *E EE E (E) (E)n几点规定：几点规定：“ “ ” ”也可以用也可以用“:=:=表示，表示， 这种表示称为这种表示称为巴科斯范式巴科斯范式(BNF)(BNF) P P1 1 P P2 2 可缩写为可缩写为 P P1 1| | 2 2| | | n n P Pn

8、 n 其中，其中，“|”|”读成读成“或或”，称为，称为P P的一个候选式。的一个候选式。表示一个文法时，通常只给出开始符号和产生式，表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：如上例，可表示为：G(E)G(E)： E E i | E+E | E i | E+E | E* *E | (E)E | (E)n例，例，G=iG=P，E E i iE E E+E E+EE E E E* *E EE E (E) (E)n定义：称定义：称 A A 直接推出直接推出，即，即 A A 仅当仅当A A 是一个产生式，是一个产生式， 且且 ， ( (V VT T V VN N) )* * 。n如

9、果如果 1 1 2 2 n n，则我们称这个，则我们称这个序列是从序列是从 1 1到到 n n的一个的一个推导推导。若存在一个。若存在一个从从 1 1到到 n n的推导，则称的推导，则称 1 1可以可以推导推导出出 n n 。n例，对文法例，对文法G(E)G(E)：E Ei | E+E | Ei | E+E | E* *E |(E)E |(E)E E (E)(E)( (E+EE+E) )(i(i+E+E) )(i(i+i+i) )n通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过一步或若干步，可以推出一步或若干步，可以推出 n n。1n 用用 表示：从表示：从 1 1出发，经过出

10、发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。 所以所以 ： 即即 或或+ +1n* * *+ +S*()|&TL GSVq定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。 仅含终结符号的句型是一个仅含终结符号的句型是一个句子句子。文法。文法G G所所产生的句子的全体是一个产生的句子的全体是一个语言语言，将它记为，将它记为 L(G)L(G)。* *+ +n例：证明例：证明 (i(i* *i+i)i+i)是文法是文法G(E)G(E)： E E i | E+E | E i | E+E

11、| E* *E | (E)E | (E)的一个句子。的一个句子。 证明：证明：E E (E)(E)( (E+EE+E) )( (E E* *E+EE+E) ) (i(i* *E+EE+E) )(i(i* *i+Ei+E) ) (i(i* *i+ii+i) )q例：文法例：文法G G1 1(A)(A)：A A c|Ab c|Ab 定义定义的语言的语言? ?A A c cA A Ab Ab cbcbA A Ab Ab Abb Abb cbbcbbA A Ab Ab Abb Abb Abbb Abbb cbbbcbbb所以所以 L(G L(G1 1)=c)=c，cbcb，cbbcbb，cbbbcbb

12、b， 以以c c开头，后继若干个开头，后继若干个b bn例：文法例：文法G G2 2(S)(S)：S S AB ABA A aA|a aA|aB B bB|b bB|bG G2 2(S)(S)的语言的语言? ?L(GL(G2 2)=a)=am mb bn n|m|m，n0n0q例：给出产生语言为例：给出产生语言为aan nb bn n|n|n 1 1 的文法。的文法。 G G3 3(S)(S)： S S aSb aSb S S ab abn从一个句型到另一个句型的推导往往不从一个句型到另一个句型的推导往往不唯一。唯一。 E+E E+E i+E i+E i i+i +i E+E E+E E+i

13、E+i i i+i+in最左推导最左推导：任何一步：任何一步 都是对都是对 中的中的最左非终结符进行替换。最左非终结符进行替换。例，例，G(E)G(E)：E E i | E+E | E i | E+E | E* *E |(E)E |(E)的一个句子的一个句子(i(i* *i+ii+i) ) 。E E (E)(E) ( (E+EE+E) ) ( (E E* *E+EE+E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )n最右推导最右推导：任何一步：任何一步 都是对都是对 中中的最右非终结符进行替换。的最右非终结符进行替换。例，例，G(E

14、)G(E)：E E i | E+E | E i | E+E | E* *E |(E)E |(E)的一个句子的一个句子(i(i* *i+ii+i) ) 。E E (E)(E) ( (E+EE+E) ) ( (E+iE+i) ) (E(E* *E+iE+i) ) (E(E* *i+ii+i) ) (i(i* *i+ii+i) )2.3.2 2.3.2 语法树与二义性语法树与二义性n用一张图表示一个句型的推导用一张图表示一个句型的推导, ,称为语法树。称为语法树。 E i + * ( ) E i i E E E E （ E E ）E EE E (E)(E) ( (E+EE+E) ) ( (E E*

15、*E+EE+E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )E E + + E EE E * * E Ei ii ii in如果使用最左如果使用最左( (右右) )推导，则一个最左推导，则一个最左( (右右) )推导与语法树一一对应的。推导与语法树一一对应的。（ E E ）E EE E (E)(E) ( (E+EE+E) ) ( (E E* *E+EE+E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )E E + + E EE E * * E Ei ii ii iE E (

16、E)(E) ( (E+EE+E) ) ( (E+iE+i) ) (E(E* *E+iE+i) ) (E(E* *i+ii+i) ) (i(i* *i+ii+i) )n如果使用最左如果使用最左( (右右) )推导，则一个最左推导，则一个最左( (右右) )推导与语法树一一对应的。推导与语法树一一对应的。 一棵语法树是不同推导过程的共性抽象。一棵语法树是不同推导过程的共性抽象。n一个句型是否只对应唯一一棵语法树？一个句型是否只对应唯一一棵语法树？（ E E ）E EE E (E)(E) ( (E E* *E E) ) ( (i i* *E E) ) (i(i* *E+EE+E) ) (i(i* *

17、i+Ei+E) ) (i(i* *i+ii+i) )E E * * E EE E + + E Ei ii ii in一个句型是否只对应唯一一棵语法树？一个句型是否只对应唯一一棵语法树？ 最左推导最左推导 最左推导最左推导（ E E ）E EE E + + E EE E * * E Ei ii ii i（ E E ）E EE E * * E EE E + + E Ei ii ii in一个句型是否只对应唯一最左一个句型是否只对应唯一最左( (右右) )推导？推导？ 最左推导最左推导 最左推导最左推导E E (E)(E) ( (E+EE+E) ) ( (E E* *E+EE+E) ) (i(i*

18、*E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )E E (E)(E) ( (E E* *E E) ) ( (i i* *E E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )n定义定义：如果一个文法存在某个句子对应两如果一个文法存在某个句子对应两棵不同的语法树棵不同的语法树，或者有两个不同的最左或者有两个不同的最左（右）推导，则称这个（右）推导，则称这个文法是二义的文法是二义的。G(E)G(E)： E E i|E+E|E i|E+E|E* *E|(E) E|(E) 是二义文法。是二义文法。n语言

19、的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如，如果对它不存在无二义性的文法。果对它不存在无二义性的文法。可能存在可能存在G和和G，一个为二义的，一个为无二，一个为二义的，一个为无二义的。但义的。但L(G)=L(G)n二义性问题是不可判定问题，即不存在一二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。一个文法是否是二义的。n可以找到一组无二义文法的充分条件。可以找到一组无二义文法的充分条件。二义文法：二义文法：G(E)G(E)： E E i|E+E|E i|E+E|E* *E|(E)E|(E)表

20、达式表达式 项项|表达式表达式+项项项项 因子因子 | 项项*因子因子因子因子 (表达式表达式) | i无二义文法：无二义文法： G(E)G(E)：E E T | E+T T | E+T T T F | T F | T* *F F F F (E) | i (E) | iE ET TF F) )( (E EE ET T+ +T TF Fi iF FT T* *F Fi ii iE E T T F F (E)(E) ( (E+TE+T) ) ( (T+TT+T) ) (T(T* *F F+T+T) ) (F(F* *F+TF+T) ) (i(i* *F+TF+T) ) (i(i* *i+T)i+T) (i(i* *i+F) i+F) (i(i* *i+i)i+i)考虑句子考虑句子(i(i* *i+i)i+i)n描述程序设计语言时，对于上下文无关文描述程序设计语言时，对于上下文无关文法的限制法的限制 ：1 1 不