第三章程序设计语言的语法描述.ppt

第3章 程序设计语言的语法描述;3.1 文法的引入;㈡规则 可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。; 句子主语谓语 冠词 形容词名词谓语 the 形容词名词谓语 the big 名词谓语 the big elephant 谓语 the big elephant 动词直接宾语 the big elephant ate 直接宾语 the big elephant ate 冠词名词 the big elephant ate a 名词 the big elephant ate a banana 上述推导可简单表示为： 句子the big elephant ate a banana。 值得注意的是用上述规则可推导出多个句子，因存在推导 句子a big banana ate the elephant 所以，a big banana ate the elephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。 一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。 综上所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结符、开始符号（特殊非终结符）及产生式四个要素构成。从开始符号出发，根据产生式能推导出的句子全体称为文法所规定的语言;㈣递归规则和递归文法 递归是编译技术中的一个重要概念。 ①递归定义：定义某事物，又用到该事物本身。 ②递归规则（直接递归）：在规则的左部和右部有相同的非终结符。 例：U→xUy，通常用大写字母表示非终结符，用小写字母表示终结符。 ⑴左递归规则：x=ε，U→Uy（ε表示空串） ⑵右递归规则：y=ε，U→xU ③间接递归：由规则推导产生。 例：V→Uy|Z，U→xV 因存在推导VUyxVy，故存在间接递归。 ⑴间接左递归：若x=ε，则VVy。 ⑵间接右递归：若y=ε，则VxU。 ④递归文法：含有递归规则和间接递归的文法，称为递归文法。 利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。;3.2 上下文无关文法;;②非终结符表示抽象的语法单位. 例“算术表达式”、“布尔表达式”、“赋值语句”、“说明语句”和“程序”等。非终结符通常用大写字母表示，也可以用带尖括号的汉字表示。 ③开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法单位。 例如讨论算术表达式，那么描述算术表达式文法的开始符号就是算术表达式。在程序设计语言中，我们最感兴趣的语法单位是“程序”。 ④产生式是定义语法单位的一种书写规则。 上下文无关文法产生式的左部必定是一个非终结符，该非终结符称为左部符号。 产生式的右部是终结符和非终结符经有限次连接构成的文法符号串，可以是空字ε。 四种文法的区别主要是对产生式的左部和右部的限制不同。 若干个左部符号相同的产生式，可合并为一个，例： A→α1|α2|……|αn，其中αi 称为A的候选式(1≤i≤n)。; 例1：描述算术表达式文法G=(VT,VN,S,P)，其中 VT={+,-,*,/,i,x,y,(,)} VN ={算术表达式,项,因子} S = 算术表达式 P = { 算术表达式→算术表达式+项 算术表达式→算术表达式-项 算术表达式→项 项→项*因子 项→项/因子 项→因子 因子→(算术表达式) 因子→i //标识符 因子→x //无符号整常数 因子→y //无符号实常数 } 根据上述文法，可推导出任何仅包含加减乘除的算术表达式。; 因已约定非终结符和终结符的书写方式，非终结符和终结符在产生式中一目了然，故终结符集VT和非终结符集VN无需再显式列出。 若规定左部符号为开始符号的产生式写在所定义文法的第一行，上述文法G又可简单表示为如下形式： 算术表达式→算术表达式+项 算术表达式→算术表达式-项 算术表达式→项 项→项*因子 项→项/因子 项→因子 因子→(算术表达式) 因子→i 因子→x 因子→y 若用E表示算术表达式、T表示项、F表示因子，借助符号|，算术表达式文法G可表示成如下最简形式： E→E+T︱E–T︱T T→T*F︱T /F︱F F→(E)︱i︱x︱y; 例2：描述算术表达式文法G=(VT,VN,S,P)，其中 VT={+,-,*,/,i,x,y,(,)} VN