高级语言及其语法描述

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第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,V,n,=V,V,V,V,规定,V,0,=,闭包：,V*=V,0,U,V,1,U,V,2,U,V,3,U,正则闭包：,V,+,=V V*,例如：已知字母表X,=0,1,2,3,4,5,6,7，求X,*和,X,+,解答：X,0,=,，,X,1,=,X=,0,1,2,3,4,5,6,7，,X,2,=,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=终结符V,T,，非终结符集V,N,，开始符号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.,V,T,=he，gave，me，a，book,V,N,=,S=,P=,-,-,-,-,-,he,语法树,he,gave,me,a,book,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,a,book,6、语法树和语法的二义性（P,31,）,某个文法的某个句子存在两个不同的语法树。,不能在有限的步骤中一般地证明一个文法是二义的,例如：文法2.1：E,E+E|E*E|（E）|i的句子,(i*i+i)的最右推导和最左推导就对应2棵不同的语法树,）,E,（,E,+,E,E,E,*,E,i,i,i,）,E,（,E,*,E,E,E,+,E,i,i,i,判定的额结果是针对文法的，但判定的关键是两棵不同的语法树对应,同一个选定,的句子。,形式语言鸟瞰：,文法的4种类型：,0型文法,短语文法,1型文法,上下文有关文法,2型文法,上下文无关文法,3型文法,左/右线性文法,复习总结,文法的使用限制,语法树与二义性,文法和语言,的形式定义,符号与符号串,文法,和语法,字母表与符号串,符号串集合的运算（闭包）,文法的形式定义,语法分析的基本术语,语言的形式定义,推导与规约,句型、句子和语言,短语与句柄,最左、最右推导与归约,语法树的构造,语法的二义性,语法树与短语,作业：P,36,6（1）、8,文法：E E+T|E-T|T,T T*F|T/F|F,F i|(E),的（1）,句型:,i+i*i的最,左,推导,和,句型:,i*（i+i）的最右推导。,