《第3章 程序设计语言的语法描述》由会员分享，可在线阅读，更多相关《第3章 程序设计语言的语法描述（18页珍藏版）》请在金锄头文库上搜索。
1、1,第3章 程序设计语言的语法描述,3.1 文法的引入 3.2 上下文无关文法 3.3 文法举例（略）,使用文法对程序设计语言的结构进行定义和描述。,2,3.1 文法的引入,先讨论自然语言的文法。例：the big elephent ate a banana 语法树 根据英语的语法，上述句子的语法结构可用图（语法树）表示如下：,非叶结点称为语法单位，在形式语言中称为非终结符。 处于根结点位置的结点又称为开始符号。 叶结点称为单词符号，在形式语言中称为终结符。,3,规则 可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。, the|a big elephant|bana
2、na ate,由规则推导句子 可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。,上述英文句子可用下述规则来描述：,4, 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。 值得注意的是用上述规则可推导出多个句子，因存在推
3、导 a big banana ate the elephant 所以，a big banana ate the elephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。 一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。 综上所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结符、开始符号（特殊非终结符）及产生式四个要素构成。从开始符号出发，根据产生式能推导出的句子全体称为文法所规定的语言,5,递归规则和递归文法 递归是编译技术中的一个重要概念。 递归定义：定义某事物，又用到该事物本身。 递归规则（直接递归）：在
4、规则的左部和右部有相同的非终结符。 例：UxUy，通常用大写字母表示非终结符，用小写字母表示终结符。 左递归规则：x=，UUy（表示空串） 右递归规则：y=，UxU 间接递归：由规则推导产生。 例：VUy|Z，UxV 因存在推导VUyxVy，故存在间接递归。 间接左递归：若x=，则VVy。 间接右递归：若y=，则VxU。 递归文法：含有递归规则和间接递归的文法，称为递归文法。 利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。,6,3.2 上下文无关文法,形式语言的奠基人乔姆斯基（Chomsky）将文法分为4种类型，它们是： 短语文法
5、（0型文法） 上下文有关文法（1型文法） 上下文无关文法（2型文法） 正规文法（3型文法） 这四种文法在形式语言中都有严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程序设计语言的语法结构。以后，“文法”一词若无特别说明，则指“上下文无关文法”。,7,文法和语言 一个文法G是一个四元式(VT,VN,S,P)，其中 VT是一个终结符的非空有限集，终结符通常用小写字母表示。 VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。 S是一个特殊的非终结符（SVN），称为开始符号。 P是一个产生式（规则）的有限集合，每个产生式的形式是A
6、 ，其中AVN，(VTVN)*。,终结符是语言的基本符号，即程序设计语言的单词。语法分析时，终结符用单词的种别表示。 根据前面约定： 标识符（简单变量）： i 无符号整常数： x 无符号实常数： y 单字符单词： 用单词本身表示（例单词“+”的 种别用+表示） 多字符单词： 需特别指定（例“+”用$表示）,8,非终结符表示抽象的语法单位. 例“算术表达式”、“布尔表达式”、“赋值语句”、“说明语句”和“程序”等。非终结符通常用大写字母表示，也可以用带尖括号的汉字表示。 开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法单位。 例如讨论算术表达式，那么描述算术表达式文法的开始符号就是。在程序
7、设计语言中，我们最感兴趣的语法单位是。 产生式是定义语法单位的一种书写规则。 上下文无关文法产生式的左部必定是一个非终结符，该非终结符称为左部符号。 产生式的右部是终结符和非终结符经有限次连接构成的文法符号串，可以是空字。 四种文法的区别主要是对产生式的左部和右部的限制不同。 若干个左部符号相同的产生式，可合并为一个，例： A1|2|n，其中i 称为A的候选式(1in)。,9,例1：描述算术表达式文法G=(VT,VN,S,P)，其中 VT=+,-,*,/,i,x,y,(,) VN =, S = P = + - * / () i /标识符 x /无符号整常数 y /无符号实常数 根据上述文法，可
8、推导出任何仅包含加减乘除的算术表达式。,10,因已约定非终结符和终结符的书写方式，非终结符和终结符在产生式中一目了然，故终结符集VT和非终结符集VN无需再显式列出。 若规定左部符号为开始符号的产生式写在所定义文法的第一行，上述文法G又可简单表示为如下形式： + - * / () i x y 若用E表示、T表示、F表示，借助符号|，算术表达式文法G可表示成如下最简形式： EE+TETT TT*FT /FF F(E)ixy,11,例2：描述算术表达式文法G=(VT,VN,S,P)，其中 VT=+,-,*,/,i,x,y,(,) VN = P = + - * / () i /标识符 x /无符号整常
9、数 y /无符号实常数 根据上述文法，同样可推导出任何仅包含加减乘除的算术表达式。 用E表示，上述文法可简记为： EE+E|E-E|E*E|E/E|(E)|i|x|y,12,基本术语 以文法G： EE+E|E*E|(E)|i 为例，进行下述讨论。 直接推出和直接归约 推导和归约 若12n，则称该直接推出序列是从1到n的一个推导，记作1n或1n。 1n：从1始，经一步或一步以上可推导出n。 1n：从1始，经步或步以上可推导出n，即 1n或1=n。 也可称直接归约序列n,n-1,1为n到1的一个归约。 句型 若存在推导S（S为文法的开始符号），则称是文法的一个句型。 句子 仅包含终结符的句型称为句
10、子。,13,语言 文法所能推导出的句子全体称为该文法的语言，记为： L(G)=|(S)(VT *) 等价文法 1和2是二个不同的文法，若L(G1)=L(G2)， 则称G1和G2是等价文法。 等价文法的存在，使我们能够在不改变文法所规定的语言的前提下，为了某种目的改造文法。 最左推导和最右推导 在各种推导中，考虑今后语法分析的需要，我们仅对两种推导感兴趣。 1）最左推导 在推导过程中始终对最左面的非终结符进行替换，记为。 2）最右推导 在推导过程中始终对最右面的非终结符进行替换，记为。,14,文法的二义性 语法树 我们可以用一个有向图表示一个句型的推导，这种表示称为语法树。语法树有助于理解一个句
11、子语法结构的层次。 在一般情况下，某一句型不论其推导过程如何，其最终形成的语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进行最左（右）推导，则语法树和最左（右）推导等价。 二义文法 若一个文法所产生的语言中，只要存在一个句子，它有二个最左推导，或有二个最右推导，或句子的推导对应两棵语法树，则称该文法为二义文法。 二义文法的利用和处理 1)根据条件修改文法，语言不变。 算符优先性：规定*优先于+，i+i*i等价于i+(i*i)。 算符结合性：规定同级运算服从左结合，i+i+i等价于 (i+i)+i。 2)根据条件修改编译程序的语法分析表，文法保持不变（详见第四、五章）。,15,1）根据条
12、件修改文法，语言不变。 算符优先性：规定*优先于+，i+i*i等价于i+(i*i)。 算符结合性：规定同级运算服从左结合，i+i+i等价于(i+i)+i。 例文法G G：EE+E|E*E|(E)|i 是一个二义文法。 根据上述条件将文法G修改成G，如下所示 G：EE+T|T TT*F|F F(E) |i 显然G不是二义文法，但L(G)=L(G)，故G和G等价。 例句子i+i*i的最右推导： EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i ETT*F?+?*? 先形成+，才有可能形成*。若先形成*，只有带括号才可能形成+。,16,2）根据条件修改编译程序的语法分析
13、表，文法保持不变。 例文法G： if 标识符 then else SfitSeS if 标识符 then SfitS 标识符= Si=E 无符号整常数 Ex 程序段 a=2 if x then if y then a=4 else a=6 相应的语法结构表示为 i=x fitfiti=xei=x 句子fitfiti=xei=x的最左推导序列有二个，如下所示： SfitSeSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efitfiti=xei=x SfitSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efifii=xei=x 因句子fitfiti=xei=x存在二个最左推导，故文法G为二义文法。,17,这样对于该程序段有二个解释： 假设else和最近的if结合，即 a=2 if x then begin if y then a=4 else a=6 end,当x和y为下列值时，相应a的值为：,假设else和最远的if结合，即 a=2 if x then begin if y then a=4 end else a=6,实际的编译程序不可能、也不允许有两种解释，通常按第一种方式进行翻译执行，即“else和最近的if结合”。,18,结 束,
