高级语言及其语法描述.ppt

第2章 高级语言及其语法描述,程序语言的定义 高级语言的一般特性 程序语言的语法描述 文法 形式语言鸟瞰,程序语言的定义,记号系统 = 语法 + 语义 +语用,语 法：,定义：是指规定如何由基本符号组成一个完整的程序的规则。可以分文一般的词法规则和语法规则（产生规则）。 例子：0.5 * X1 + C 语言的词法规则单词符号的形成规则 单词符号是语言中具有独立意义的最基本单位，包括各类型的常数、标识符、基本字、算符和界符等。 语言的语法规则语法单位的形成规则 规定如何从单词符号形成语法单位（包括：表达式、语句、分程序、函数、过程和程序等）的规则。 语法规则的描述上下文无关文法,词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确程序的依据。,语义单词符号和语法单位的意义。,语 义：,形式上完全相同的语法单位在不同的语言中语义是不相同的。,程序语言的基本功能：,描述数据和对数据运算。程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义。,高级语言的分类 程序结构 数据类型与操作 （P19）,高级语言的一般特性：,标识符由字母或数字组成的以字母为开头的一个字符串。它没有意义。 名 字是代表一个抽象的存储单元，存储单元的内容就是该名字的值，也是名字所表示的一个具体对象，名字还有明确的属性（包括类型和作用域）和意义。,数据类型与操作 （P19）：,赋值语句 （P24）：,A ：= B,右值，表示名字的值,左值，存储单元，地址,程序语言的语法形式描述(P25),：字母表有穷符号集合(注意：是“符号”，而不是“字符”) 符号字母表中的元素 例如： =a,b,c,d,e,.z =begin,end,if, for, while 符号串字母表中的符号构成的有穷序列 例如：aa,bb,cc,dd,（显然是一个无穷的集合） 空字：不包含任何符号的序列，记为 。 注意区分： ， ， ,连接积UV = | U 且 V （ U、V是 *的子集） 即UV中的符号串是 U 和 V中的符号串连接而成的。,用 * 表示*上的所有符号串的全体 例如： = a, b ，则 * = , a , b, aa , ab , ba ,bb , aaa , ,例如： U = a, b 、V = aa , bb 则UV = aaa, abb，baa，bbb ,Vn = V V V V 规定V0 = ,闭包：V* = V0 U V1 U V2 U V3 U 正则闭包：V+ = V V*,例如： 已知字母表X = 0,1,2,3,4,5,6,7 ，求X*和 X + 解答： X0 = ，X1 = X= 0,1,2,3,4,5,6,7 ， X2 = 00,01,02,03,04,05,06,07，77 X*= , 0,1,2,3,4,5,6,7, 00，77，000，777， X + = XX* =0,1,2,3,4,5,6,7, 00，77，000，777， ,上下文无关文法（P 27）：,1、概念 文法描述语言的语法结构的形式规则（即语法规则） 上下文无关文法文法所定义的语法单位是完全独立于这种语法单位可能出现的环境的。,2、上下文无关文法 G = 终结符VT，非终结符集VN ，开始符号S，产生式集P （P27） 文法的表示方法；G, GS,例子：给定如下子语言框架： - Program ； - |； -Integer |Real| |Bloolean |Procedure | ； - Begin End - | | ； - - - | | - | | - $, -A|B|Z|a|b|z -0|1|2|3|4|5|6|7|8|9| 该子语言文法的开始符号为（ ），终结符号为（ ）非终结符号为（ ）。,例子：he gave me a book. VT = he， gave， me， a ，book VN = , , , , , , , S = P= - , - - , - - he, ,语法树,3、推导（P 29）、最左推导和最右推导（P 30）,4、句型、句子 （P 29）,例如：文法2.1：E E+ E |E * E |（E）| i的推导 E（E）（E+E）（E*E+E）（i*E+E） （i*i +E） （i*i + i ） 句型有： （E）、（E+E）、（E*E+E）、（i*E+E）、 （i*i +E） 、 （i*i + i ） 句子有：（i*i + i ）,5、语法树（P 31） 可以用语法树表示一个句子的结构。语法树是以开始符号（识别符）为根，以句子的推导过程为依据，对每个非终结符，把它的推导所用产生式的右部的全部符号作为它的子结点。 语法树的全部叶子，从左到右就是这个句子。,语法树,6、语法树和语法的二义性（P 31） 某个文法的某个句子存在两个不同的语法树。 不能在有限的步骤中一般地证明一个文法是二义的,例如：文法2.1：E E+ E |E * E |（E）| i的句子 (i*i + i)的最右推导和最左推导就对应2棵不同的语法树,判定的额结果是针对文法的，但判定的关键是两棵不同的语法树对应同一个选定的句子。,形式语言鸟瞰：,文法的4种类型： 0型文法短语文法 1型文法上下文有关文法 2型文法上下文无关文法 3型文法左/右线性文法,复习总结,文法的使用限制,语法树与二义性,文法和语言 的形式定义,符号与符号串,文法 和语法,推导与规约,句型、句子和语言,短语与句柄,最左、最右推导与归约,语法树的构