第2章 高级语言及其语法描述 2.1 程序语言的定义及特性 2.2 形式语言基础 2.3 文法的直观理解 2.4 文法和语言的定义 2.5 文法的类型 2.6 语法树与二义性 2.7 有关文法的限制2.1 程序语言的定义及特性显然，用高级语言编程比用低级语言来得方便，但要解决两个问题： (1).计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。 (2).用什么方法来精确定义高级语言，即怎样精确描述高级语言。要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法） 及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理 论或什么方法来描述的。1 程序语言的定义语法 语义 语用任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集 （字母表）上的一个符号串。对于自然语言来说，它们是定义在某个字母表上的句子的集合。对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。 这些语法成分统称为单词或单词符号。单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法 规则所确定的，即词法规则规定了单词符号的形成规则。当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有 穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言 来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则 ，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主 语后随谓语而成，构成谓语的是动词和直接宾语。“我是大学生”。是汉语的一个句子用语法来描述：句子=主语谓语 主语=代词名词 代词=我你他 名词=王明大学生工人英语 谓语=动词直接宾语 动词=是学习 直接宾语=代词名词 有了一组规则以后，按照如下方式用它们导出句子：开始去找=左 端的带有句子的规则并把它由=右端的符号串代替，这个动作表示 成： 句子 主语谓语，然后在得到的串主语谓语 中，选取主语或谓语，再用相应规则的=右端代替之。比如 ，选取了主语，并采用规则主语=代词，那么得到：主语谓语 代词谓语，重复做下去，句子：“我是大学生”的全部动作过程是： 句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则 ，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据 ，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉 及汉语句子的结构描述。其中一种描述元语言称为文法。语言概述 语言是由句子组成的集合，是由一组符号所构成的集合。 汉语所有符合汉语语法的句子的全体 英语所有符合英语语法的句子的全体 程序设计语言所有该语言的程序的全体每个句子构成的规律研究语言 每个句子的含义每个句子和使用者的关系 研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法 Syntax语义 Semantics语用 Pragmatics语法 表示构成语言句子的各个记号之间的组合规律。 语义 表示各个记号的特定含义。即是一组规则，使用它 可以定义语言的意义。（各个记号和记号所表示的对象之间 的关系） 语用 表示在各个记号所出现的行为中，它们的来源、使用 和影响。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看， 其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义 。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义 。幽默、双关语和谜语就是利用这两方面意义间的差异。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的 语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样 的事实：语言的所有规则只以符号串能出现的方式来陈述。形式语言理论是 对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研 究的基础。2 高级语言的分类 强制式语言 (Imperative Language) / 过程式语言FORTRAN , C, Pascal 应用式语言(Applicative Language) / 函数式语言LISP 基于规则的语言(Rule-based Language)Prolog 面向对象语言(Object-oriented Language)2.2 形式语言基础一、字母表和符号串字母表：符号的非空有限集合 例：=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|等于组成该符 号串的符号个数。例： xSTV ， |x|=3例：Aa,b,B=c,d, AB= ？ 4. 符号串集合的乘积运算：令A、B为符号串集合，定义AB xy |xA,yBac，ad，bc，bd因为xxx，所以A=A=A3.符号串的联接：若x、y是定义在是上的符号串，且 xXY，yYX，则x和y的联接 xyXYYX也是上的符号 串。注意：一般xyyx，而xx6.符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。A* A0 A 称为集合A的闭包。 例：A=x,yA？A* ？5. 符号串集合的幂运算：有符号串集合A，定义A0 =,A1=A,A2=AA,A3=AAA, AnAn-1A=AAn-1 ，n0x,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 * , 程序 C2.3 文法的直观理解1.什么是文法：文法是对语言结构的定义与描述。即从形式上 用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：“我是大学生” 。这是一个在语法、语 义上都正确定句子，该句子的结构（称为语法结构）是由它 的语法决定的 。在本例中它为“主谓结构”。如何定义句子的合法性？ 有穷语言 无穷语言2.语法规则：我们通过建立一组规则（产生式），来描述句子 的语法结构。规定用“:=”表示“由组成”。:=:=|:=你|我|他:= 王民|大学生|工人|英语:=:=是|学习:=|3. 由产生式推导句子：有了一组产生式之后，可以按照一定的 方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。= = 这种推导一直进行下去，直到所有带的符号都由终结符号 替代为止。= = = 我=我=我是=我是=我是大学生:=:=|:=你|我|他:= 王民|大学生|工人|英语:=:=是|学习:=|推导方法：从一个要识别的符号 开始推导，即用相应产生式的 右部来替代产生式的左部，每 次仅用一条产生式去进行推导。例：有一英语句子：The big elephant ate the peanut.:=:=:=the:=big:=elephant:=:=ate:=:=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:=上述推导可写成 = the big elephant ate the peanut+说明：(1) 有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2) 从一组产生式可推出不同的句子，如以上产生式还可推 出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它们 在语法上都正确，但在语义上都不正确。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。4.语法树：我们用语法树来描述一个句子的语法结构。Thebigelephantatethepeanut语法成分（在形式 语言中又称“非终 结符”）单词符号（在形 式语言中又称 “终结符号”)2.4.1文法的定义2.4 文法和语言的形式定义定义1: 文法G=（VN，VT，P，Z）VN ：非终结符号集VT ：终结符号集P：产生式或规则的集合Z：开始符号（识别符号） ZVNVVNVT 称为文法的字汇表产生式：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有些产生式具有相同的左部，可以合在一起例、 ； | ；0 | 1 | 2 | 3 | | 9文法的BNF表示给定一个 文法，实际只需给出产生式集合，并指定识别符号 例、 G ； | ；0 | 1 | 2 | 3 | | 92.4.2 推导与归约定义2： 直接推导：文法G：vx Uy