程序设计语言的语法描述

PAGE第1页共4页第3章程序设计语言的语法描述（Tsu版电子教案）第3章程序设计语言的语法描述文法：对语言结构的定义和描述。3.1文法的引入先讨论自然语言的文法。例：thebigelephentateabanana㈠语法树根据英语的语法，上述句子的语法结构可用图（语法树）表示如下：<句子><主语><谓语><冠词><形容词><名词><动词><直接宾语>thebigelephant ate<冠词><名词> abanana①非叶结点称为语法单位，在形式语言中称为非终结符。②处于根结点位置的结点又称为开始符号。③叶结点称为单词符号，在形式语言中称为终结符。㈡规则可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。上述英文句子可用下述规则来描述：<句子>→<主语><谓语> <主语>→<冠词><形容词><名词><冠词>→the|a<形容词>→big<名词>→elephant|banana<谓语>→<动词><直接宾语><直接宾语>→<冠词><名词><动词>→ate㈢由规则推导句子可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。 <句子><主语><谓语><冠词><形容词><名词><谓语> the<形容词><名词><谓语>thebig<名词><谓语> thebigelephant<谓语>thebigelephant<动词><直接宾语> thebigelephantate<直接宾语>thebigelephantate<冠词><名词> thebigelephantatea<名词>thebigelephantateabanana上述推导可简单表示为：<句子>thebigelephantateabanana。值得注意的是用上述规则可推导出多个句子，因存在推导<句子>thebigbananaateanelephant故thebigbananaateanelephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。㈣递归规则和递归文法=1\*GB3①递归定义=2\*GB3②递归规则（直接递归）=3\*GB3③间接递归=4\*GB3④递归文法利用递归文法我们可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。例：定义无符号整数。=1\*GB3①不采用递归规则，描述无符号整数全体就要使用无穷多条的规则。 <无符号整数>→<数字>|<数字><数字>|<数字><数字><数字>|…<数字>→0|1|2|3|4|5|6|7|8|9|0=2\*GB3②采用递归规则，描述无符号整数全体仅需12条规则。 <无符号整数>→<无符号整数><数字>|<数字> N→ND|D <数字>→0|1|2|3|4|5|6|7|8|9|0 D→0|1|2|3|4|5|6|7|8|9|0例1：无符号整数1 ND1例2：无符号整数23 NNDDD2D23例3：无符号整数456 NNDNDDDDD4DD45D4563.2 上下文无关文法形式语言的奠基人乔姆斯基将文法分为4种类型，它们是：短语文法（0型文法）上下文有关文法（1型文法）上下文无关文法（2型文法）正规文法（3型文法）这四种文法在形式语言中都有严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程序设计语言的语法结构。以后，“文法”一词若无特别说明，则指“上下文无关文法”。㈠文法和语言 一个文法G是一个四元式(VT,VN,S,VP)，其中VT是一个终结符的非空有限集，终结符通常用小写字母表示。VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。S是一个特殊的非终结符（S∈VN），称为开始符号。VP是一个产生式（规则）的有限集合，每个产生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。例：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根据上述文法，可推导出任何仅包含加乘的算术表达式。㈡基本术语①直接推出和直接归约②推导和归约③句型④句子⑤语言⑥等价文法⑦最左推导和最右推导㈢文法的二义性①语法树我们可以用一个有向图表示一个句型的推导，这种表示称为语法树。在一般情况下，某一句型不论其推导过程如何，其最终形成的语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进行最左（右）推导，则语法树和最左（右）推导等价。②二义文法某些文法的句型的推导可能对应一棵以上的语法树，或存在一个以上的最左（右）推导。

例：已知文法G：E→E+E|E*E|(E)|i和句子i+i*i，该句子存在二个最左（右）推导，即二棵语法树。语法树1（先形成+后形成*） E E + E E * E i i i语法树2（先形成*后形成+） E E * E i E + E i i句子i+i*i的二个最左推导序列：EE+Ei+Ei+E*Ei+i*Ei+i*iEE*EE+E*Ei+E*Ei+i*Ei+i*i句子i+i*i的二个最右推导序列：EE+EE+E*EE+E*iE+i*ii+i*i EE*EE