《第2章高级语言及其语法描述.ppt》由会员分享，可在线阅读，更多相关《第2章高级语言及其语法描述.ppt（60页珍藏版）》请在三一文库上搜索。
1、第2章 高级语言及其语法描述,2.1 程序语言的定义及特性 2.2 形式语言基础 2.3 文法的直观理解 2.4 文法和语言的定义 2.5 文法的类型 2.6 语法树与二义性 2.7 有关文法的限制,2.1 程序语言的定义及特性,显然，用高级语言编程比用低级语言来得方便，但要解决两个问题： (1).计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目 标程序的转换。 (2).用什么方法来精确定义高级语言，即怎样精确描述高级语言。 要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法） 及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理 论或什么方法来描
2、述的。 1 程序语言的定义 语法 语义 语用,任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集 （字母表）上的一个符号串。 对于自然语言来说，它们是定义在某个字母表上的句子的集合。 对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里 的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。 这些语法成分统称为单词或单词符号。 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法 规则所确定的，即词法规则规定了单词符号的形成规则。,当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷
3、集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。,“我是大学生”。是汉语的一个句子 用语法来描述：,句子=主语谓语 主语=代词名词 代词=我你他 名词=王明大学生工人英语 谓语=动词直接宾语 动词=是学习 直接宾语=代词名词,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成： 句子 主语谓语，然后在得到的串主语谓语中，选取主语
4、或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词， 那么得到：主语谓语 代词谓语， 重复做下去， 句子：“我是大学生”的全部动作过程是： 句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,语言概述,研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语
5、法 Syntax 语义 Semantics 语用 Pragmatics,语法 表示构成语言句子的各个记号之间的组合规律。 语义 表示各个记号的特定含义。即是一组规则，使用它可以定义语言的意义。（各个记号和记号所表示的对象之间的关系） 语用 表示在各个记号所出现的行为中，它们的来源、使用和影响。,语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下
6、的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,2 高级语言的分类,强制式语言 (Imperative Language) / 过程式语言 FORTRAN , C, Pascal 应用式语言(Applicative Language) / 函数式语言 LISP 基于规则的语言(Rule-based Language) Prolog 面向对象语言(Object-oriented Language),2.2 形式语言基础,一、字母表和
7、符号串 字母表：符号的非空有限集合 例：=a，b，c 符号：字母表中的元素 例： a，b，c 符号串：符号的有穷序列 例：a, aa, ac, abc， 空符号串：无任何符号的符号串(),符号串的形式定义 有字母表，定义： （1）是上的符号串； （2）若x是上的符号串，且a ，则ax或xa是上的符号串； （3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。,符号串集合：由符号串构成的集合。,二、符号串和符号串集合的运算 1.符号串相等：若x、y是集合上的两个符号串，则xy iff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。 2.符号串的长度：x为符号串，其长度|x
8、|等于组成该符 号串的符号个数。 例： xSTV ， |x|=3,例：Aa,b,B=c,d, AB= ？,4. 符号串集合的乘积运算：令A、B为符号串集合，定义 AB xy |xA,yB,ac，ad，bc，bd 因为xxx，所以A=A=A,3.符号串的联接：若x、y是定义在是上的符号串，且xXY，yYX，则x和y的联接 xyXYYX也是上的符号串。 注意：一般xyyx，而xx,6.符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。 A* A0 A 称为集合A的闭包。,例：A=x,y A？ A* ？,5. 符号串集合的幂运算：有符号串集合A，定义 A0
9、 =, A1=A, A2=AA, A3=AAA, AnAn-1A=AAn-1 ，n0,x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A1 A2 A3 , x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A0 A1 A2 A3,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？ 若A为某语言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), = B为单词集 B =begin, end, if, then,else,for, 则B A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C B * , 程序 C,2.3
10、文法的直观理解,1.什么是文法：文法是对语言结构的定义与描述。即从形式上 用于描述和规定语言结构的称为“文法”（或称为“语法”）。,例：有一句子：“我是大学生” 。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的 。在本例中它为“主谓结构”。,如何定义句子的合法性？ 有穷语言 无穷语言,2.语法规则：我们通过建立一组规则（产生式），来描述句子 的语法结构。规定用“:=”表示“由组成”。,:= :=| :=你|我|他 := 王民|大学生|工人|英语 := :=是|学习 :=|,由产生式推导句子：有了一组产生式之后，可以按照一定的 方式用它们去推导或产生句子。 推
11、导方法：从一个要识别的符号开始推导，即用相应产生式 的右部来替代产生式的左部，每次仅用一条产生式去进行推导。, = = 这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。, = ,= ,= 我,=我,=我是,=我是,=我是大学生,:= :=| :=你|我|他 := 王民|大学生|工人|英语 := :=是|学习 :=|,推导方法：从一个要识别的符号 开始推导，即用相应产生式的 右部来替代产生式的左部，每 次仅用一条产生式去进行推导。,例：有一英语句子：The big elephant ate the peanut. := := :=the :=big :=elephant := :=a
12、te := :=peanut, = ,= ,= the ,= the big ,= the big elephant ,= the big elephant ,= the big elephant ate ,= the big elephant ate ,= the big elephant ate the ,= the big elephant ate the peanut,:= := :=the :=big :=elephant | peanut := :=ate :=,说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推
13、 导）。 (2) 从一组产生式可推出不同的句子，如以上产生式还可推 出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它们 在语法上都正确，但在语义上都不正确。,所谓文法是在形式上对句子结构的定义与描述，而未 涉及语义问题。,4.语法树：我们用语法树来描述一个句子的语法结构。,语法成分（在形式 语言中又称“非终 结符”）,单词符号（在形 式语言中又称 “终结符号”),2.4.1文法的定义,2.4 文法和语言的形式定义,定义1: 文法G=（VN，VT，P，Z） VN ：非终结符号集 VT ：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） ZVN,VVNVT 称为文法的字汇表
14、,产生式：U : x U VN, xV*,其中: A.产生式：产生式是一个有序对(U, x), 通常写为: U : x 或U x； | U| = 1 |x| 0 B.非终结符号：出现在产生式的左部,且能推出符号或符号串的 那些符号。其全体构成非终结符号集，记为VN 。 C.终结符号：不出现在产生式的左部,且不能推出符号或符号串 的那些符号。其全体构成终结符号集，记为VT 。,P = ； ； ； 0； 1； 9； Z = ；,例：无符号整数的文法： G=（VN，VT，P，E） VN, VT = 0,1,2,3,9,几点说明：,产生式左边符号构成集合VN，且 Z VN,文法的BNF表示,2.4.2
15、 推导与归约,定义2： 直接推导：文法G：vx Uy，wxuy, 其中x、y V* ，UVN, u V*, 若U : uP，则v w。 若xy，有U : u，则U u,换句话说，x和y是符号串，若使用一次产生式可以从x变换出y，则称x直接推导出y(或者说y是x的直接推导），记为x y。,当符号串已没有非终结符号时，推导就必须终止。因为 终结符不可能出现在产生式左部，所以将在产生式左部出现的 符号称为非终结符号。,例如：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6| 7| 8| 9, N=109,例：,则：,* N=109,则：,* N=N,直观意义：规范推导最右推导,定
16、义5： 最右推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最右非终结符进行替换，称为最右推导。 最左推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最左非终结符进行替换，称为最左推导。,定义6： 推导的逆过程称之为归约。,例：x =y,可称为x直接推导出y，也可称为y直接归约出x。, x =y ,可称为x推导出y，也可称为y归约出x。,2.4.3 语言的形式定义,文法GZ所产生的 所有句子的集合,例：abna|n1,构造其文法 G1Z： ZaBa, Bb|bB G2Z： ZaBa, Bb|Bb,定义7. G和G是两个不同的文法，若 L(G) = L(G) ,
17、则G和G为等价文法。,编译感兴趣的问题是:,给定终极符x, 文法G, 求x L(G) ?,x,算法1,算法2,x L(G) ?,G,y,n,出错处理,停机,2.4.4 递归文法,1.递归产生式：产生式右部有与左部相同的符号 对于 U xUy 若x=,即U Uy，左递归； 若y=,即U xU，右递归；,4. 递归文法的优点：可用有穷条产生式，定义无穷语言,例：对于前面给出的无符号整数的文法是有递归文法，用13条产生式就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条产生式呢？,!,3. 左递归文法的缺点：不能用自顶向下的方法来进行语法分析,会造成死循环（后面将详细论述）,2.5 文法分
18、类,形式语言：用文法和自动机所描述的没有语义的语言。,文法定义：乔姆斯基将所有文法都定义为一个四元组： G=（VN，VT，P，Z） VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） ZVN,文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。,定义8：0型文法： P： u v 其中uV，vV*,0型语言：L0 这种语言可以用图灵机(Turing)接受.,0型文法称为短语结构文法。产生式的左部和右部都可 以是符号串，一个短语可以产生另一个短语。,定义9： 1型文法： P： xUy xuy 其中 UVN， x、y、uV*,1型语
19、言：L1 这种语言可以由一种线性界限自动机接受.,称为上下文敏感或上下文有关。也即只有在x、y这样的 上下文中才能把U改写为u,定义10：2型文法： P： U u 其中 UVN， uV*,2型语言：L1 这种语言可以由下推自动机接受.,称为上下文无关文法。也即把U改写为u时，不必考虑上下文。 注意：2型文法与BNF表示相等价。,（右线性） P： U T 或 U Tw 其中 U、wVN TVT,3型语言：L3 又称正则语言、正则集合 这种语言可以由有穷自动机接受.,3型文法称为正则文法。它是对2型文法进行进一步限制。,（左线性） P： U T 或 U wT 其中 U、wVN TVT,定义11：
20、3型文法：,2.6 语法树与二义性文法,2.6.1 推导与语法树,（1）语法树：句子结构的图示表示法，它是一种有向图，由 结点和有向边组成。,结点：符号 根结点：识别符号 中间结点：非终结符 叶结点：终结符或非终结符,有向边：表示结点间的派生关系。,注意一个重要事实：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法树的生成规律不同，但最终生成的语 法树形状完全相同。某些文法有此性质，而某些文法 不具此性质。,( 2 ) 句型的推导及语法树的生成（自顶向下）,一般推导：,( 3 ) 子树与简单子树,子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成
21、。,简单子树：只有单层分枝的子树称为简单子树。,( 4 ) 树与推导,句型推导过程 句型语法树的生长过程,P = ； ； ； 0； 1； 9； Z = ；,例：无符号整数的文法： G=（VN，VT，P，E） VN, VT = 0,1,2,3,9,例：G 句型10,规范推导,定义 对句型中最左简单短语（句柄）进行的归约称为 规范归约。,10,规范归约与规范推导互为逆过程,定义 通过规范推导或规范归约所得到的句型称为规范句型。,不是规范推导,2.6.2 文法的二义性,定义 若对于一个文法的某一句子存在两棵不同的语法树， 则该文法是二义性文法，否则是无二义性文法。,换而言之，无二义性文法的句子只有一
22、棵语法树，尽管推导过程可以不同。,下面举一个二义性文法的例子： GE: E:= E+E | E*E | (E) | i VN =E VT = +, * , ( , ) , i ,对于句子Sii * i L（GE ），存在不同的规范推导：,这两种不同的推导对应了两种不同的语法树,(2) E= E*E = E*i = E+E*i = E+i*i = ii * i,定义 若一个文法的某句子存在两个不同的规范推导，则 该文法是二义性的，否则是无二义性的。,以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。上例中，规范句型E+E*i 是由ii * i通过两步规范规约得到的，但对于同一个
23、句型 E+E* i，它有两个不同的句柄（对应上述两棵不同的语法树）：i 和 EE。因此语法的二义性意味着句型的句柄不唯一。,句柄：i,句柄：EE,定义 若一个文法的某规范句型的句柄不唯一，则该文法 是二义性的，否则是无二义性的。,若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。,现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。,由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种编译算
24、法，使该算法满足无二义性充分条件。,例:算术表达式的文法,E:= E+E | E*E | (E) | i,E:= E+T | T T := T*F | F F := (E) | i,例:Pascal 条件语句的文法,:= If then | If then else := | |.,2.7 有关文法的实用限制,1 若文法中有如U:=U的产生式，则这就是有害产生式，它会引 起二义性。,多余产生式：（1）在推导文法的所有句子中，始终用不到的 产生式。即该产生式的左部非终结符不出现在任何句型中。 （2）在推导句子的过程中，一旦使用了该产生式，将推不出 任何终结符号串。即该产生式中含有推不出任何终结符号串的 非终结符。,例如给定GZ，若其中关于U的产生式只有如下一条： U xUy 该产生式是多余产生式。,若还有U a，则此产生式 并非多余,2、语法图,2 文法的其它表示法,1、扩充的BNF表示 BNF的元符号： , , | 扩充的BNF的元符号： , :=, |, , , , (, ),小 结,掌握符号串、文法、句型、句子和语言的定义 几个重要概念：递归、语法树、文法的二义性、文法的实用限制等。 掌握文法的表示：BNF、扩充的BNF范式、语法图。 了解文法分类。,本 章 作 业,P36：6#，7#，8#，10#,