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

第2章 高级语言及其语法描述 程序语言的定义 高级语言的一般特性 程序语言的语法描述 文法 形式语言鸟瞰 程序语言的定义 记号系统 = 语法 + 语义 +语用 词法规则语法规则 语 法 ： n定义：是指规定如何由基本符号组成一个完整的程序的 规则。可以分文一般的词法规则和语法规则（产生规则） 。 例子：0.5 * X1 + C n语言的词法规则单词符号的形成规则 单词符号是语言中具有独立意义的最基本单位，包括各类型的常数 、标识符、基本字、算符和界符等。 n语言的语法规则语法单位的形成规则 规定如何从单词符号形成语法单位（包括：表达式、语句、 分程序、函数、过程和程序等）的规则。 n语法规则的描述上下文无关文法 词法规则和语法规则定义了程序的形式结构，是判断 输入字符串是否构成一个形式上正确程序的依据。 n n 语义语义单词符号和语法单位的意义。单词符号和语法单位的意义。 语语 义义 ： 形式上完全相同的语法单位在不同的形式上完全相同的语法单位在不同的 语言中语义是不相同的。语言中语义是不相同的。 程序语言的基本功能：程序语言的基本功能： 描述数据数据和对数据运算运算。程序语言的 每个组成成分都有（抽象的）逻辑逻辑和计 算机实现实现两方面的意义。 高级语言的分类 程序结构 数据类型与操作 （P19） 高级语言的一般特性高级语言的一般特性 ： 类 别特 点语法形式示 例 类 别特 点示 例备 注 标识符标识符由字母或数字组成的以字母为开头的一个字符串。 它没有意义。 名名 字字是代表一个抽象的存储单元，存储单元的内容就是 该名字的值值，也是名字所表示的一个具体对象 具体对象，名字还有明确 的属性（属性（包括类型类型和作用域作用域） ）和意义意义。 数据类型与操作数据类型与操作 （P19P19） ： 类 别数据运 算示 例 初等数据类型 数据结构 抽象数据类型 赋值语句赋值语句 （P24P24）：）： A A ：= B= B 右值，表示名字 的值 左值，存储单元， 地址 程序语言的语法形式描述程序语言的语法形式描述( (P25)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 闭包：V* = V0 U V1 U V2 U V3 U v正则闭包：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 27P 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, 语法树 he gave me abook 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） 可以用语法树表示一个句子的结构。 语法树是以开始符号（识别符）为根， 以句子的推导过程为依据，对每个非终 结符，把它的推导所用产生式的右部的 全部符号作为它的子结点。 语法树的全部叶子，从左到右就是这个 句子。 语法树 he gave me abook 6、语法树和语法的二义性（P 31） 某个文法的某个句子存在两个不同的语法树。 不能在有限的步骤中一般地证明一个文法是二义的 例如：文法2.1：E E+ E |E * E |（E）| i的句子 (i*i + i)的最右推导和最左推导就对应2棵不同的语法树 ）E（ E + E E E * E ii i ）E（ E * E E E + E ii i 判定的额结果是针对文 法的，但判定的关键是 两棵不同的语法树对应 同一个选定的句子。 形式语言鸟瞰：形式语言鸟瞰： 文法的文法的 4 4 种类型：种类型： 0型文法短语文法 1型文法上下文有关文法 2型文法上下文无关文法 3型文法左/右线性文法 复习总结 文法的使用限制 语法树与二义性 文法和语言 的形式定义 符号与符号串 文法 和语法 字母表与符号串 符号串集合的运算（闭包） 文法的形式定义 语法分析的基本术语 语言的形式定义 推导与规约 句型、句子和语言 短语与句柄 最左、最右推导与归