《高级语言及其语法描述.ppt》由会员分享，可在线阅读，更多相关《高级语言及其语法描述.ppt（44页珍藏版）》请在金锄头文库上搜索。
1、第二章 高级语言及其语法描述主要内容2.1 2.1 程序语言的定义程序语言的定义2.2 2.2 高级语言的分类高级语言的分类2.3 2.3 程序语言的语法描述程序语言的语法描述2.1 程序语言的定义程序语言的定义v一个程序语言是一个记号系统。程序语言主一个程序语言是一个记号系统。程序语言主要由语法和语义两个方面定义。要由语法和语义两个方面定义。语法语法v任何语言程序都可看成是一定字符集（称为字母表）任何语言程序都可看成是一定字符集（称为字母表）上的一字符串（有限序列）。但是，什么样的字符上的一字符串（有限序列）。但是，什么样的字符串才算是一个合式的程序呢？串才算是一个合式的程序呢？v所谓一个所
2、谓一个语言的语法语言的语法是指这样的一组规则，用它可是指这样的一组规则，用它可以形成和产生一个合式的程序。以形成和产生一个合式的程序。v这些规则的一部分称为词法规则，另一部分称为语这些规则的一部分称为词法规则，另一部分称为语法规则（或产生规则）。法规则（或产生规则）。v词法规则词法规则是指单词符号的形成规则。是指单词符号的形成规则。v语言的单词符号是由词法规则所确定的。语言的单词符号是由词法规则所确定的。词法规则规定了字母表中哪样的字符串是词法规则规定了字母表中哪样的字符串是一个单词符号。一个单词符号。v单词符号一般包括：各类型的常数、标识单词符号一般包括：各类型的常数、标识符、基本字、算符和
3、界符等。符、基本字、算符和界符等。v语言的语言的语法规则语法规则规定了如何从单词符号形成更大的规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单结构（即语法单位），换言之，语法规则是语法单位的形成规则。位的形成规则。v一般程序语言的语法单位有：表达式、语句、分程一般程序语言的语法单位有：表达式、语句、分程序、函数、过程和程序等等。序、函数、过程和程序等等。v语言的词法规则和语法规则定义了程序的形式结构，语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确（即合是判断输入字符串是否构成一个形式上正确（即合式）程序的依据。式）程序的依据。 语
4、义语义v一个语言的一个语言的语义语义是指这样的一组规则，使用是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为它可以定义一个程序的意义。这些规则称为语义规则语义规则。2.2 高级语言的分类高级语言的分类一、强制式语言一、强制式语言二、应用式语言二、应用式语言三、基于规则的语言三、基于规则的语言四、面向对象语言四、面向对象语言2.3 程序语言的语法描述程序语言的语法描述v重点讨论上下文无关文法、语法分析树，以重点讨论上下文无关文法、语法分析树，以及文法的二义性问题。最后还将对形式语言及文法的二义性问题。最后还将对形式语言进行简单概述。进行简单概述。 v设设是一个有穷字母表，它的每个元
5、素称为是一个有穷字母表，它的每个元素称为一个一个符号符号。 1 1、上的一个符号串：上的一个符号串：是指由是指由中的符号所构中的符号所构成的一个有穷序列。不包含任何符号的序列成的一个有穷序列。不包含任何符号的序列称为称为空字，空字，记为记为。用。用表示表示上的所有上的所有符号串的全体，空字符号串的全体，空字也包括在其中。也包括在其中。v例如，例如，a,ba,b，则则 =, ,a,b,aa,ab,ba,bb,aaaa,b,aa,ab,ba,bb,aaa,。表示不含任何元素的空集。表示不含任何元素的空集。注意：要注意空字注意：要注意空字、和和 的区别。的区别。2 2、的子集的子集U U和和V V的
6、（连接）积的（连接）积 UVUV| |U U& &V V 即集合即集合UVUV中的符号串是由中的符号串是由U U和和V V的符号串连接的符号串连接而成的。而成的。 注意，一般而言，注意，一般而言，UVVUUVVU，但，但(UV)W=U(VW(UV)W=U(VW）。）。3 3、V V自身的自身的n n次（连接）积：次（连接）积： 记为记为 V V=VVV=VVV 规定：规定：V=V= 令令 V V= V= V0 0VVVV V V 称称V V* *是是V V的闭包。记的闭包。记V V=V=VV V* *，称称V V+ +是是V V的正则闭的正则闭包。包。上下文无关文法上下文无关文法v文法文法是描
7、述语言的语法结构的形式规则是描述语言的语法结构的形式规则（即（即语法规则语法规则）。）。v上下文无关文法上下文无关文法所定义的语法范畴（或语所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现法单位）是完全独立于这种范畴可能出现的环境的。的环境的。v上下文无关文法不宜于描述任何自然语言，上下文无关文法不宜于描述任何自然语言，但对于现今的程序语言来说，上下文无关但对于现今的程序语言来说，上下文无关文法基本上是够用了。文法基本上是够用了。v从一个具体英文例句的分析出发，引进有关上下文无关文法的从一个具体英文例句的分析出发，引进有关上下文无关文法的基本概念。比如，我们写了这样一个句子：基本概念
8、。比如，我们写了这样一个句子： He gave me a bookHe gave me a book这是一个语法上正确的句子，因为它满足英语中的基本语法规则。这是一个语法上正确的句子，因为它满足英语中的基本语法规则。有下面语法规则：有下面语法规则：句子句子主语谓语间接宾语直接宾语主语谓语间接宾语直接宾语主语主语 谓语谓语 间接宾语间接宾语代词代词直接宾语直接宾语冠词名词冠词名词 gavegave名词名词bookbook句子句子 = = 主语谓语间接宾语直接宾主语谓语间接宾语直接宾语语= = 代词谓语间接宾语直接宾语代词谓语间接宾语直接宾语= He= He谓语间接宾语直接宾语谓语间接宾语直接宾语
9、= He= He动词间接宾语直接宾语动词间接宾语直接宾语= He gave= He gave间接宾语直接宾语间接宾语直接宾语=He gave=He gave代词直接宾语代词直接宾语= He gave me= He gave me直接宾语直接宾语= He gave me= He gave me冠词名词冠词名词= H gave me a= H gave me a名词名词= He gave me a book= He gave me a book语法分析树语法分析树:用一种图示化的方法来表示这种推导用一种图示化的方法来表示这种推导句子主语谓语间接宾语直接宾语代词动词冠词名词Hegavemeabook
10、代词上下文无关文法描述上下文无关文法描述v一个上下文无关文法一个上下文无关文法G G包括四个组成部分：包括四个组成部分：一一组终结符号组终结符号，一组非终结符号一组非终结符号，一个开始符一个开始符号号，以及，以及一组产生式一组产生式。v终结符号终结符号乃是组成语言的基本符号，在程序乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。从语本字、标识符、常数、算符和界符等。从语法分析的角度来看，终结符号是一个语言的法分析的角度来看，终结符号是一个语言的不可再分的基本符号。不可再分的基本符号。v非终结符号（也称语
11、法变量）非终结符号（也称语法变量）用来代表语法用来代表语法范畴。例如，范畴。例如，“算术表达式算术表达式”、“布尔表达布尔表达式式”、“赋值句赋值句”、“分程序分程序”、“过程过程”等。等。v开始符号开始符号是一个特殊的非终结符号，它代表是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为这个语法范畴通常称为“句子句子”v产生式（也称产生规则或简称规则）产生式（也称产生规则或简称规则） 是定义语法范畴的一种书写规则。一个产生式的是定义语法范畴的一种书写规则。一个产生式的形式是形式是A A 其中，箭头（有时也用：）左边
12、的其中，箭头（有时也用：）左边的A A是一是一个非终结符，称为产生式的左部符号；箭头右边个非终结符，称为产生式的左部符号；箭头右边的是由终结符号或的是由终结符号或/ /与非终结符号组成的一符号与非终结符号组成的一符号串，称为产生式的右部。串，称为产生式的右部。v例：例：“变量是一个算术表达式；若变量是一个算术表达式；若E E和和E2E2是算术表达式，是算术表达式，则则E1E1E2,E1*E2E2,E1*E2和（和（ElEl）也是算术表达式。也是算术表达式。”对于这个定义，若用产生式来描述，则可将它写成：对于这个定义，若用产生式来描述，则可将它写成：E Ei iE EE EE EE EE * E
13、E * EE E（E)E)E E：表示：表示“算术表达式算术表达式”i i：表示：表示“变量变量”v一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式（V VT T,V,VN N,S,S,) )，其中其中V VT T是一个非空有限集，它的每个元素称为终结符号；是一个非空有限集，它的每个元素称为终结符号；V VN N是一个非空有限集，它的每个元素称为非终结符是一个非空有限集，它的每个元素称为非终结符号，号，V VT TV VN NS S是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号；是一个产生式集合（有限），每个产生式的形式是一个产生式集合（有限），每个产生式的形
14、式是是P P，其中，其中，P VP VN N， (V(VT TVVN N) )* * 。开开始符号始符号S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。v对于多个左部相同的产生式：对于多个左部相同的产生式：P P11PP22PPnn可写为：可写为： PP11| | 22 nn其中每个其中每个ii称为是称为是P P的一个候选式。的一个候选式。 读为读为“定义为定义为”，| | 读为读为“或或”。v一般，用大写字母一般，用大写字母A,B,CA,B,C或汉语词组或汉语词组（如，算术表达式）代表非终结符号，（如，算术表达式）代表非终结符号，用小写字母用小写字母a,b,ca
15、,b,c代表终结符，用代表终结符，用、等代表由终结符和非终结符组成等代表由终结符和非终结符组成的符号串。的符号串。v上下文无关文法定义一个语言的中心思想是上下文无关文法定义一个语言的中心思想是：从文法的开始符号出发，反复连续使用产生式，从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。对非终结符施行替换和展开。v我们称我们称AA直接推出直接推出， 即即A A= = 仅当仅当AA是一个产生式，且是一个产生式，且、(V(VT TV VN N) )* *。如果如果l = l = 2 = . = 2 = . = n n，则我们称这个则我们称这个序列是从序列是从l l至至nn的一个推导
16、。的一个推导。若存在一个从若存在一个从l l至至n n的推导，则称的推导，则称l l可推导可推导出出n.n.v假定假定G G是一个文法，是一个文法，S S是它的开始符号。是它的开始符号。如果如果S = S = ，则称则称是一个是一个句型句型。仅含。仅含终结符号的句型是一个终结符号的句型是一个句子句子。v文法文法G G所产生的句子的全体是一个所产生的句子的全体是一个语言语言，将它记为将它记为L(G) L(G) L(G) =L(G) =| |S = S = & &VVT T E =(E) =(EE) =(E*EE） = （i*EE) =(iiE) =(iii) 是从开始符号是从开始符号E到到(i*
17、ii）的一个推导。的一个推导。而而E，（，（E），（），（EE），（），（E*EE），），（，（i*ii）都是这个文法的句型。都是这个文法的句型。下面介绍几个简单文法的例子：下面介绍几个简单文法的例子：例例2.1考虑一个文法考虑一个文法G1:SbA AaA|a 它定义了一个什么语言呢它定义了一个什么语言呢？ 从开始符从开始符S出发，我们可以推出如下句子：出发，我们可以推出如下句子： SbA ba SbA baA baa . SbA baA baaa可以写为：可以写为： L(G1)=baL(G1)=ban n|n1|n1v例例2.2 2.2 设有文法设有文法G G SP|aPPbSP|aPPb
18、P P ba|bQaba|bQa Q Q abab 求语言求语言L(G).L(G). 解：解： L(G)=L(G)=ba,baba,abab,abababba,baba,abab,ababab 例例2 2。3 3 构造一个文法构造一个文法G3G3使使 L(G3)=aL(G3)=an nb bn n|n1|n1 解解; ; SaSb|abSaSb|ab最左最左( (最右最右) )推导推导所谓所谓最左推导最左推导指：任何一步指：任何一步a = a = 都是对都是对中中的最左非终结符进行替换的。的最左非终结符进行替换的。同样，可定义最右推导。同样，可定义最右推导。v（i*ii*ii)i)的最右推导：
19、的最右推导： E =(E) =(EE) =(Ei) =(E*Ei) =(E*ii) =(i*ii) 例：例： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子句子 ( i * i + i)的语法树：的语法树：(1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i)(2) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i)语法分析树与二义性语法分析树与二义性v用一张图表示一个句型的推导，这种表示用一张图表示一个句型的推导，这
20、种表示称为称为语法分析树，语法分析树，或简称为语法树。或简称为语法树。v一棵语法树表示了一个句型种种可能的一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括（但未必是所有的）不同推导过程，包括最左（最右）推导。最左（最右）推导。v如果一个文法存在某个句子对应两棵不同如果一个文法存在某个句子对应两棵不同的语法树，则称这个的语法树，则称这个文法是二义文法是二义的。也就的。也就是说，若一个文法中存在某个句子，它有是说，若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文两个不同的最左（最右）推导，则这个文法是二义的。法是二义的。v注意，注意，文法的二义性文法的二义性
21、和和语言的二义性语言的二义性是是两个不同的概念。我们可能有两个不同两个不同的概念。我们可能有两个不同的文法的文法G G和和GG其中一个是二义的而另其中一个是二义的而另一个是无二义的，但是却有一个是无二义的，但是却有L(G)=L(GL(G)=L(G），），也就是说，这两个文法也就是说，这两个文法所产生的语言是相同的。所产生的语言是相同的。v在文法在文法(2.1)(2.1)中，假若规定了运算符中，假若规定了运算符十十与与*的优先顺序和结合规则比方的优先顺序和结合规则比方说，让说，让*的优先性高于的优先性高于，且它，且它们都服从左结合，那么，就可以构造出们都服从左结合，那么，就可以构造出一个无二义文
22、法：一个无二义文法： E ET T | | E E十十T T T T F | T*F F | T*F F F（E) | iE) | i作为描述程序语言的上下文无关文法，对它有几点限作为描述程序语言的上下文无关文法，对它有几点限制。制。第一，第一，文法中不含任何下面形式的产生式文法中不含任何下面形式的产生式 P PP P 因为，这种产生式除了引起二义性外没有任何用处。因为，这种产生式除了引起二义性外没有任何用处。第二，第二，每个非终结符每个非终结符P P必须都有用处。这一方面意味着，必须都有用处。这一方面意味着，必须存在含必须存在含P P的句型；也就是，从开始符号的句型；也就是，从开始符号S S
23、出发，出发，存在推导存在推导 S =S =P P 另一方面意味着，必须存在终结符串另一方面意味着，必须存在终结符串V VT T* *，使得使得P P =, ,也就是，对于也就是，对于P P不存在永不终结的回路。不存在永不终结的回路。形式语言鸟瞰形式语言鸟瞰v乔姆斯基把文法分成四种类型，即乔姆斯基把文法分成四种类型，即0 0型、型、l l型、型、2 2型和型和3 3型。型。v0 0型强于型强于1 1型，型，l l型强于型强于2 2型，型，2 2型强于型强于3 3型。型。v这几类文法的差别在于对产生式施加不同的限这几类文法的差别在于对产生式施加不同的限制。制。v我们说我们说G=(G=(V VT T
24、 , ,V VN N ,S , ,S , ) ) 是一个是一个0 0型文法，如果它型文法，如果它的每个产生式的每个产生式 是这样的结构是这样的结构 (V(VN N V VT T) )* * 且至少有一个非终结符，而且至少有一个非终结符，而 (V(VN N V VT T) )* * 。0 0型文法也称短语文法。型文法也称短语文法。如果如果对对0 0型文法分别施加以下的第型文法分别施加以下的第i i条限制条限制，则我们就，则我们就得到第得到第i i型文法型文法: :(1)G(1)G的任何产生式的任何产生式 均满足均满足| | | | | | |（其中（其中| | | |和和| | | |分别为分别
25、为 和和 的长度；仅的长度；仅S S例外，但例外，但S S不得出现在任何产生式的右部。不得出现在任何产生式的右部。(2)G(2)G的任何产生式为的任何产生式为A A, A, A V VN N，(V(VN N V VT T) )* * 。(3)G(3)G的任何产生式为的任何产生式为A AB B或或 A A，其中其中V VT T* *，A A、B B V VN N 。v其中其中1 1型文法也称上下文有关文法型文法也称上下文有关文法。这种文法。这种文法意味着，对非终结符进行替换式务必考虑上意味着，对非终结符进行替换式务必考虑上下文并且一般不允许替换成空串下文并且一般不允许替换成空串 。2 2型文法也
26、称上下文无关文法型文法也称上下文无关文法，注意其语言定，注意其语言定义：义：G G的任何产生式为的任何产生式为AA，AVAVN N， （V VN NVVT T) )* *表明凡出现在产生式左边的符号都是表明凡出现在产生式左边的符号都是非终结符。非终结符。3 3型文法也称右线性文法。型文法也称右线性文法。 3 3型文法还有另一种形式，称左线性文法：一型文法还有另一种形式，称左线性文法：一个文法个文法G G为左线性文法，如果为左线性文法，如果G G的任何产生式的任何产生式为为 ABAB 或或AA ，其中，其中 V VT T* * , , A A、B VB VN N 由于由于3 3型文法等价于正规式
27、所以型文法等价于正规式所以也称正规文法。也称正规文法。例题与习题解答例题与习题解答例例2.1： 试构造生成语言试构造生成语言L=anbnci|n 1, i 0的文法的文法分析：要求分析：要求a和和b的个数一样多，并至少为一个，而的个数一样多，并至少为一个，而c的个数为的个数为0个以上即可，所以可以用一个终结符去生个以上即可，所以可以用一个终结符去生成成anbn串，用另一个非终结符去生成串，用另一个非终结符去生成ci 。G(Z): ZAB A aAb|ab B cB| 例例2.2： 已知语言已知语言L=anbbn| n 1, 写出产生写出产生L的文法。的文法。解解： GS: S aAb A aA
28、b|b例例2.3： 已知文法已知文法G=(A,B,C,a,b,c,A,P)其中产生式其中产生式P由以下组成：由以下组成： A abc A aBbc Bb bB Bc Cbcc bC Cb aC aaB aC aa 问：此文法表式的语言是什么？问：此文法表式的语言是什么？解解：由于：由于A为开始符。为开始符。 由于由于AaBbc abBc abCbcc aCbbcc aabbcc 语言为：语言为： anbncn, n0 例例2.4：试写一文法，使其描述的语言试写一文法，使其描述的语言L(G) 是能被是能被5整除的整数集合。整除的整数集合。解：解： G(Z): Z (+|- )A(0|5) A 0|1|2|3|4|5|6|7|8|9|AA ， 例例2.5： 已知语言已知语言L=x | x a,b,c*,且且x重重复排列是对称的（复排列是对称的（aabcbaa,aabbaa,等等) 写写出该语言的文法。出该语言的文法。 例例2.5：解：解： G(Z)： Z aZa|bZb|cZc|a|b|c|
