第3章 程序设计语言的语法描述

第3章程序设计语言的语法描述3.1文法的引入文法：对语言结构的定义和描述。先讨论自然语言的文法。例：thebigelephentateabanana3.1文法的引入㈠语法树根据英语的语法，上述句子的语法结构可用图（语法树）表示如下：3.1文法的引入3.1文法的引入①非叶结点称为语法单位，在形式语言中称为非终结符。②处于根结点位置的结点又称为开始符号。③叶结点称为单词符号，在形式语言中称为终结符。3.1文法的引入㈡规则可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。上述英文句子可用下述规则来描述：3.1文法的引入1.句子→主语谓语2.主语→冠词形容词名词3.冠词→the|a4.形容词→big5.名词→elephant|banana6.谓语→动词直接宾语7.直接宾语→冠词名词8.动词→ate3.1文法的引入㈢由规则推导句子可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。3.1文法的引入句子主语谓语冠词形容词名词谓语the形容词名词谓语thebig名词谓语thebigelephant谓语thebigelephant动词直接宾语thebigelephantate直接宾语thebigelephantate冠词名词thebigelephantatea名词thebigelephantateabanana3.1文法的引入上述推导可简单表示为：句子thebigelephantateabanana。3.1文法的引入值得注意的是用上述规则可推导出多个句子，因存在推导句子thebigbananaateanelephant故thebigbananaateanelephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。3.1文法的引入㈣递归规则和递归文法①递归定义定义某事物，又用到某事物。在规则的左部和右部有相同的非终结符U→xUyU为非终结符，xy为终结符。3.1文法的引入㈣递归规则和递归文法②递归规则（直接递归）在产生式的左部和右部都含有非终结符U，故U→xUy是递归规则。若x=ε,U→Uy称为左递归规则，若y=ε，U→xU称为右递归规则。3.1文法的引入㈣递归规则和递归文法③间接递归文法的递归性还可以在推导过程中由规则间接产生：V→Uy|z,U→Xv上述规则不是递归规则，但存在推导VUyxUy,即VxUy，称文法含有间接递归。3.1文法的引入㈣递归规则和递归文法④递归文法含有递归规则或间接递归的文法称为递归文法3.1文法的引入利用递归文法我们可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。3.1文法的引入例：定义无符号整数。①不采用递归规则，描述无符号整数全体就要使用无穷多条的规则。无符号整数→数字|数字数字|数字数字数字|…数字→0|1|2|3|4|5|6|7|8|9|0②采用递归规则，描述无符号整数全体仅需12条规则。无符号整数→无符号整数数字|数字N→ND|D数字→0|1|2|3|4|5|6|7|8|9|0D→0|1|2|3|4|5|6|7|8|9|03.1文法的引入例1：无符号整数1ND1例2：无符号整数23NNDDD2D23例3：无符号整数456NNDNDDDDD4DD45D4563.2上下文无关文法文法是描述语言结构的形式规则（语法规则），这些规则必须是准确的，易于理解的，应当有较强的描述能力，足以描述各种不同的结构3.2上下文无关文法形式语言的奠基人乔姆斯基将文法分为4种类型，它们是：l短语文法（0型文法）l上下文有关文法（1型文法）l上下文无关文法（2型文法）l正规文法（3型文法）这四种文法在形式语言中都有严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程序设计语言的语法结构。以后，“文法”一词若无特别说明，则指“上下文无关文法”。3.2上下文无关文法上下文无关文法所定义的语法单位和该语法单位可能出现的环境无关。自然语言中，一个句子或一个字，其意义和它们所处的上下文有密切关系，因此上下文无关文法不适合描述自然语言。3.2上下文无关文法㈠文法和语言一个文法G是一个四元式(VT,VN,S,VP)，其中lVT是一个终结符的非空有限集，终结符通常用小写字母表示。lVN是一个非终结符的非空有限集，非终结符通常用大写字母表示。lS是一个特殊的非终结符（S∈VN），称为开始符号。lVP是一个产生式（规则）的有限集合，每个产生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。3.2上下文无关文法终结符是语言的基本符号，就是源程序中的单词，是语言不可分割的最小单位。单词经过词法分析后，语法分析只使用单词二元式的种别code。语法分析关心的是：单词是标识符还是常数，不考虑是哪个标识符，常数是多少。3.2上下文无关文法因此，终结符用单词的种别表示。i表示标识符x表示整形或实形变量y表示无符号实常数单字符单词种别与单词本身相同+基本字借用原单词形式3.2上下文无关文法非终结符用来表示抽象的语法单位，算术表达式，赋值语句，说明语句，程序。通常用大写字母表示，也用汉字表示开始符号是特殊的非终结符，定义文法的出发点3.2上下文无关文法产生式是定义语法单位的一种书写规则。上下文无关文法产生式的左部必定是一个非终结符，该非终结符称为产生式的左部符号，简称左部符号。产生式的右部是终结符和非终结符经过有限次连接构成的文法符号串，可以是空字。3.2上下文无关文法为方便，若干个左部符号相同的产生式，如A→1A→2A→3A→4A→N合并：A→1|2|…|N3.2上下文无关文法例：G=（VT，VN，S，VP）VT={+，*，(，)，i}VN={E}S=EVP={E→E+E，E→E*E，E→(E)，E→i}可简记为：G：E→E+E|E*E|(E)|i根据上述文法，可推导出任何仅包含加乘的算术表达式。3.2上下文无关文法㈡基本术语①直接推出和直接归约②推导和归约③句型④句子⑤语言⑥等价文法⑦最左推导和最右推导3.2上下文无关文法㈢文法的二义性①语法树我们可以用一个有向图表示一个句型的推导，这种表示称为语法树。在一般情况下，某一句型不论其推导过程如何，其最终形成的语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进行最左（右）推导，则语法树和最左（右）推导等价。3.2上下文无关文法②二义文法某些文法的句型的推导可能对应一棵以上的语法树，或存在一个以上的最左（右）推导。3.2上下文无关文法例：已知文法G：E→E+E|E*E|(E)|i和句子i+i*i，该句子存在二个最左（右）推导，即二棵语法树。3.2上下文无关文法语法树1（先形成+后形成*）3.2上下文无关文法语法树2（先形成*后形成+）3.2上下文无关文法句子i+i*i的二个最左推导序列：EE+Ei+Ei+E*Ei+i*Ei+i*iEE*EE+E*Ei+E*Ei+i*Ei+i*i句子i+i*i的二个最右推导序列：EE+EE+E*EE+E*iE+i*ii+i*iEE*EE*iE+E*iE+i*ii+i*i3.2上下文无关文法二义文法：若一个文法所产生的语言中，只要存在一个句子，它有二个最左推导，或有二个最右推导，或句子的推导对应两棵语法树，则称该文法为二义文法。3.2上下文无关文法③二义文法的利用和处理l根据条件修改文法，语言不变。根据条件修改编译程序的某一部分，文法保持不变