高级语言及其语法描述

1、第二章第二章 高级语言及其语法描述高级语言及其语法描述程序语言的定义程序语言的定义( (语法、语义语法、语义) )高级语言的一般特性（标识符、数组等）高级语言的一般特性（标识符、数组等）程序语言的语法描述程序语言的语法描述程序语言的定义程序语言的定义n程序语言主要由两方面定义：程序语言主要由两方面定义：n语法语法：一组规则，用来形成和产生一个合式：一组规则，用来形成和产生一个合式(well-formed)的程序的程序n词法规则词法规则n语法规则语法规则n语义语义: :一组规则，用来定义一个程序的意义一组规则，用来定义一个程序的意义单词符号的形成规则。单词符号的形成规则。单词符号：常数、标识符、

2、基本字、单词符号：常数、标识符、基本字、算符、界符。算符、界符。描述及分析：正规式和有穷自动机描述及分析：正规式和有穷自动机词法规则词法规则语法单位的形成规则。语法单位的形成规则。语法单位：表达式、语句、分程序、语法单位：表达式、语句、分程序、函数、过程、程序等。函数、过程、程序等。描述及分析：上下文无关文法描述及分析：上下文无关文法语法规则语法规则用来定义一个程序的意义的规则。用来定义一个程序的意义的规则。描述：属性文法描述：属性文法分析：语法制导翻译分析：语法制导翻译语义语义n程序语言的基本功能：描述数据和对数据的运算。程序语言的基本功能：描述数据和对数据的运算。n所谓程序，本质上说是描述

3、一定数据的处理过程。所谓程序，本质上说是描述一定数据的处理过程。程序程序| |子程序或分程序、过程、函数子程序或分程序、过程、函数| |语句语句| |表达式表达式| |数据引用数据引用 算符算符 函数调用函数调用高级语言的一般特性高级语言的一般特性标识符与名字标识符与名字n标识符标识符：以字母开头的，由字母数字：以字母开头的，由字母数字组成的字符串。组成的字符串。n标识符标识符与与名字名字两者有本质区别：两者有本质区别：n标识符标识符是语法概念是语法概念n名字名字有确切的意义和属性有确切的意义和属性标识符与名字标识符与名字n名字：名字：n值：左值指存储单元，右值指单元中的内值：左值指存储单元，

4、右值指单元中的内容容n属性：类型和作用域属性：类型和作用域n名字的性质的说明方式：名字的性质的说明方式：n由说明语句来明确规定的由说明语句来明确规定的n隐含说明：隐含说明：FORTRAN FORTRAN 以以I,J,K,NI,J,K,N为首的名为首的名字代表整型，否则为实型。字代表整型，否则为实型。n动态确定：走到哪里，是什么，算什么动态确定：走到哪里，是什么，算什么 数组数组n逻辑上，数组是由同一类型数据所组成逻辑上，数组是由同一类型数据所组成的某种的某种n n维矩形结构，沿着每一维的距维矩形结构，沿着每一维的距离，称为离，称为下标下标。n数组可变与不可变：编译时能否确定其存数组可变与不可变

5、：编译时能否确定其存贮空间的大小。贮空间的大小。n访问：给出数组名和下标值访问：给出数组名和下标值n存放方式存放方式: : 按行存放按行存放, ,按列存放按列存放数组元素地址计算数组元素地址计算n地址计算与存储方式密切相关地址计算与存储方式密切相关n数组数组A10,20A10,20的的A1A1，11为为a a，各维下标各维下标为为1 1，按行存放，那么，按行存放，那么AiAi，jj地址为：地址为：a+(i-1)a+(i-1)* *20+(j-1)20+(j-1)n数组元素地址计算公式数组元素地址计算公式编译时对数组处理编译时对数组处理n把数组有关信息记录在一个把数组有关信息记录在一个“内情向量

6、内情向量”中中n每个数组的内情向量必须包括：维数，各维每个数组的内情向量必须包括：维数，各维的上、下限，首地址，以及数组（元素）的的上、下限，首地址，以及数组（元素）的类型。类型。l1 u1 d1 l2 u2 d2 ln un dn n C type a 程序语言的语法描述程序语言的语法描述2.3 2.3 程序语言的语法描述程序语言的语法描述 n几个概念几个概念: :n考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集n其中每一个元素称为一个其中每一个元素称为一个字符字符n上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所中的字符所构成的一个有穷序列构成的一个有穷序列n不包

7、含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为n用用* *表示表示上的所有上的所有字的全体字的全体, ,包含空字包含空字n用用 表示不含任何元素的表示不含任何元素的空集空集例如例如: : 设设 =a=a， bb，则，则 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V n设：设：U a, aa V b, bb n那么：那么：UV= ab, abb, aab, aabb n*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U &

8、amp; V nV自身的自身的 n次积记为次积记为Vn=VVVn规定规定V0= ，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包;n记记 VVV* ，称，称V+是是V的正规闭包。的正规闭包。n设：设：U a, aa n那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, n字母表包含了语言中所允许出现的一切符号。字母表包含了语言中所允许出现的一切符号。n一个语言的句子总是它的字母表的符号串。一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合这个符号串的组成必须是按照文法规则组合而成的。而成的。n在本课程

9、中，语言被认为是句子的集合。所在本课程中，语言被认为是句子的集合。所以，一个语言就是对应于它的字母表上的一以，一个语言就是对应于它的字母表上的一个符号串集合个符号串集合n语法分析的一个重要任务就是：判断一个符语法分析的一个重要任务就是：判断一个符号串的组成是否满足某个文法的规定。号串的组成是否满足某个文法的规定。文法文法通俗地讲，文法是用来精确而无歧义地通俗地讲，文法是用来精确而无歧义地描述语言的语法结构的形式规则（语法描述语言的语法结构的形式规则（语法规则）。规则）。文法描述语言的时候不考虑语言的含义。文法描述语言的时候不考虑语言的含义。一般采用一般采用上下文无关文法上下文无关文法来描述程序

10、设来描述程序设计语言的语法规则。计语言的语法规则。HeHe swims in river. swims in river.有关语法规则：有关语法规则：句子句子 主语谓语状语主语谓语状语主语主语 代词代词谓语谓语 动词动词状语状语 介词介词 名词名词代词代词HeHe动词动词swimsswims介词介词inin名词名词riverriver推导过程：句子推导过程：句子=主语谓语状语主语谓语状语=名词谓语状语名词谓语状语= = = He swims in river= He swims in river一个英文句子的例子一个英文句子的例子推导过程的图示化：推导过程的图示化：句子句子主语主语谓语谓语状语

11、状语代词代词动词动词界词界词名词名词Heswimsinriver上下文无关文法上下文无关文法一组一组终结符号终结符号V VT T：组成语言的基本符号组成语言的基本符号。即单词符号。如：基本字，标识符，。即单词符号。如：基本字，标识符，常数，算符，界符等。常数，算符，界符等。一个上下文无关文法一个上下文无关文法G G包括四部分：包括四部分：一组一组非终结符号非终结符号V VN N：也称语法变量，用来代表语法范畴也称语法变量，用来代表语法范畴。如。如“算术表达式算术表达式”、“布尔表达式布尔表达式”、“赋值句赋值句”、“子程序子程序”、“函数函数”等。等。从语法分析的角度看，终结符是一个语言的不可

12、再分的基本从语法分析的角度看，终结符是一个语言的不可再分的基本符号。符号。一个非终结符代表一个一定的语法概念，是一个一个非终结符代表一个一定的语法概念，是一个类（集类（集合）合）记号，而不是一个个体记号。记号，而不是一个个体记号。一个一个开始符号开始符号S S：一个一个特殊的非终结符号特殊的非终结符号，代表我们最终感兴趣的，代表我们最终感兴趣的语法范畴，通常为语法范畴，通常为“句子句子”。一组一组产生式产生式P P：定义语法范畴的一种书写规则定义语法范畴的一种书写规则。一个产生式形如一个产生式形如A A 或或A A :=:= 。左。左部部A VA VN N ；右部；右部A A （V VN NV

13、VT T）* *又称为重写规则。又称为重写规则。产生式的简写：产生式的简写： , , 可以可以简化为：简化为： | | 产生式的例子产生式的例子定义含定义含+ +、* *运算和（、）的算术表达运算和（、）的算术表达式这一语法范畴的产生式。式这一语法范畴的产生式。上下文无关文法的形式化上下文无关文法的形式化G=(VG=(VN N,V,VT T, S, P), S, P)其中：其中：V VN N 非空有限的非终结符号集非空有限的非终结符号集V VT T 非空有限的终结符号集，非空有限的终结符号集， V VN N V VT T = = S S 开始符号开始符号/ /识别符号，识别符号，S VS VN

14、 N P P 产生式集产生式集 ，每个产生式形如，每个产生式形如A A 。A VA VN N ；A A （V VN NVVT T）* *例子：例子：2929（2.12.1）由文法定义语言由文法定义语言 文法的作用是描述某种语言的句子的构成文法的作用是描述某种语言的句子的构成方式。使用文法我们可以产生对应语言的句子。方式。使用文法我们可以产生对应语言的句子。所有句子就构成了文法所定义的语言。所有句子就构成了文法所定义的语言。基本思想：基本思想：从识别符号开始，不断利用产生式，将从识别符号开始，不断利用产生式，将当前符号串中的非终结符号替换为该符当前符号串中的非终结符号替换为该符号的某个规则的右部

15、。直到当前的符号号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。串中所有的符号都是终结符号为止。例子：例子：i+ii+i推导和直接推导推导和直接推导直接推导：直接推导： A A = ，其中其中A A 是文法中的一个是文法中的一个 产生式，且产生式，且 、 （V VN NVVT T）* * 。推推 导：导：若若1 1 = =2 2 = = = = n n, ,则称这个则称这个序列为符号串序列为符号串1 1到到n n的一个推导。的一个推导。若若n=2,n=2,记为记为1 1 =+ =+ n n若若n=1,n=1,记为记为1 1 = =* * n n语言的定义语言的定义对于文法对于

16、文法GSGS， 称为称为G G的一个句型的一个句型, ,如果：如果： S =S =* * 识别符号是最简单的句型。识别符号是最简单的句型。GSGS的一个句型的一个句型被称为句子，被称为句子，如果：如果： V VT T* *也就是说句子是全部由终结符号也就是说句子是全部由终结符号组成的句型。组成的句型。句型句型: :句子句子: :语言的定义语言的定义文法的语言：文法的语言：文法所产生的句子的全体是文法所产生的句子的全体是一个语言，记为一个语言，记为L(G).L(G).L(G) = | S =+ L(G) = | S =+ 并且并且 V VT T* * 一个文法的语言就是该文一个文法的语言就是该文

17、法的所有的句子的集合。法的所有的句子的集合。例子例子G1G1：A bA|aA bA|a；L(G1)=bL(G1)=bi ia|i=0a|i=0G2G2：Z AbZ Ab；A aaA A aaA aaA A aaL(G2) = aL(G2) = a2n2nb|n=1b|n=1构造一个文法，使得它识别语言构造一个文法，使得它识别语言a an nb bn np.30.p.30.例子例子文法等价：文法等价：设设G G和和GG是两个文法，如果是两个文法，如果L(G)L(G)等于等于L(G)L(G)，那么我们说，那么我们说G G和和GG等价。等价。例例 子：子：G S SABC AAa|a BBb|b C

18、Cc|cG S SABC AAa|a BBb|b CCc|cGS SSc|Bc BBb|Ab AAa|aGS SSc|Bc BBb|Ab AAa|a两个两个CFGCFG文法是否等价是不可判定的。文法是否等价是不可判定的。语言的定义语言的定义从一句型到另一句型的推导往往从一句型到另一句型的推导往往不唯一不唯一。最左推导：最左推导：最右推导：最右推导： 在一个推导的过程中，如果每一步在一个推导的过程中，如果每一步直接推导所被替换的总是最左（右）直接推导所被替换的总是最左（右）的非终结符号，那么这种推导称为的非终结符号，那么这种推导称为最左（右）推导。最左（右）推导。最右推导又称为规范推导。最右推导

19、又称为规范推导。语言的定义语言的定义例如：例如：i+ii+i最左推导的例子最左推导的例子标识符文法标识符文法GS:GS:S L|SD|SL, S L|SD|SL, L a|b|c|x|y|z,L a|b|c|x|y|z,D 0|1|2|7|8|9D 0|1|2|7|8|9最左推导：最左推导：S= SD= SDD= S= SD= SDD= LDD= aDD= a6D= a69LDD= aDD= a6D= a69最右推导的例子最右推导的例子最右推导：最右推导：S= SD= S9= S= SD= S9= SD9= S69= D69= a69SD9= S69= D69= a69标识符文法标识符文法GS

20、:GS:S L|SD|SL, S L|SD|SL, L a|b|c|x|y|z,L a|b|c|x|y|z,D 0|1|2|7|8|9D 0|1|2|7|8|9语法树的概念语法树的概念作为识别句子的辅助工具，语法树有助于理解句子的语法作为识别句子的辅助工具，语法树有助于理解句子的语法结构。这一点对于其后的语义分析有非常重要的意义。结构。这一点对于其后的语义分析有非常重要的意义。语法树语法树：设文法设文法G=(VG=(VN N,V,VT T,P,S ),P,S ),对于文法对于文法G G的任意的任意一个一个句型句型都存在一棵相应的都存在一棵相应的语法树语法树：结点由符号组成。结点由符号组成。根结

21、点对应于识别符号。根结点对应于识别符号。只有非终结符号对应的结点有子结点。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。于文法中的一个规则的左部和右部。语法树的相关概念语法树的相关概念对应于一个符号。结点的名字就是该符号。对应于一个符号。结点的名字就是该符号。结结 点：点：没有边进入的结点。没有边进入的结点。没有向下射出的边的结点称为叶结点。没有向下射出的边的结点称为叶结点。在相对于句型的语法树中，可能是非终结符号。在相对于句型的语法树中，可能是非终结符号。又称末端结点。又称末端结点。两个结点之间的连线。两

22、个结点之间的连线。某个结点向下射出的边和其结点称为分支。父子结点某个结点向下射出的边和其结点称为分支。父子结点兄弟结点兄弟结点根结点：根结点：叶结点：叶结点：边：边：分分 支：支：子子 树：树：语法树的某个结点和它向下射出的部分。语法树的某个结点和它向下射出的部分。从推导构造语法树从推导构造语法树步骤步骤1 1：根结点为识别符号。：根结点为识别符号。步骤步骤2 2：对于每一次推导使用的规则：对于每一次推导使用的规则A A ，找出，找出A A对应的结点（此时对应的结点（此时应该是末端结点），从该结点向下应该是末端结点），从该结点向下画分支，子结点从左到右分别是画分支，子结点从左到右分别是中从左到

23、右的符号。中从左到右的符号。重复步骤重复步骤2 2直到推导的最后一步。直到推导的最后一步。语法树的例子语法树的例子P.31.P.31.图图2.22.2SABabcBdcdS=AB=abB=abcBd=abccdd语法树的例子语法树的例子语法语法GS:GS:S ABS ABA aAb | abA aAb | abB cBd | cdB cBd | cd语法树与推导的关系语法树与推导的关系一棵语法树表示了一个句型种种可能（但一棵语法树表示了一个句型种种可能（但未必是所有的）的不同推导过程。未必是所有的）的不同推导过程。一棵语法树等价于一个最左（右）推导。一棵语法树等价于一个最左（右）推导。一个句型

24、不一定只对应唯一的一棵语法树。一个句型不一定只对应唯一的一棵语法树。例如：例如：i i* *i+Ii+I的另一棵语法树。的另一棵语法树。P32P32图图2.32.3文法的二义性文法的二义性如果一个文法如果一个文法存在某个句子存在某个句子对应对应两棵不同两棵不同的语法树的语法树，则该文法是二义性的。，则该文法是二义性的。这里的二义性是指这里的二义性是指语法结构上语法结构上的。的。如果一个句子具有二义性，那么对这个句子的结如果一个句子具有二义性，那么对这个句子的结构可能有多种构可能有多种正确正确的解释。通常情况下，句的解释。通常情况下，句子的语义要通过其语法结构来定义，所以，二义子的语义要通过其语

25、法结构来定义，所以，二义性一般是有害的。性一般是有害的。文法的二义性是不可判定的。文法的二义性是不可判定的。文法的二义性不等于语言的二义性。文法的二义性不等于语言的二义性。EEE+E*EEE+EE*E文法二义性例子文法二义性例子文法文法GEGE：E E + E | E E E + E | E * * E | (E) | i E | (E) | i文法的句子文法的句子: : i+ii+i* *i i，其语法树如下：，其语法树如下：二义性二义性一般来讲，二义性是一般来讲，二义性是针对文法针对文法而言的，说语言而言的，说语言二义性是无意义的。二义性是无意义的。如果某个语言对应的文如果某个语言对应的文法都是二义性的，那么法都是二义性的，那么这个语言被称为先天二这个语言被称为先天二义性的。义性的。即使文法是无二义性的，其句子对应的语义仍即使文法是无二义性的，其句子对应的语义仍然必须有严格的定义，才可以避免然必须有严格的定义，才可以避免语义语义的二义的二义性。性。语言语言的二义性：的二义性：作业作业3 3、7 7、8 8、9 9补充作业：补充作业：1 1、构造、构造L=aL=an nbbbbn n|