1第3章程序设计语言的语法描述2015.ppt

第3章 程序设计语言的语法描述 3.1 文法的引入 文法：对语言结构的定义和描述。 先讨论自然语言的文法。例： the big elephent ate a banana 3.1 文法的引入 ㈠语法树 根据英语的语法，上述句子的语法结构可用图（语法树）表示如下： 3.1 文法的引入 3.1 文法的引入 ①非叶结点称为语法单位，在形式语言中称为非终结符。 ②处于根结点位置的结点又称为开始符号。 ③叶结点称为单词符号，在形式语言中称为终结符。 3.1 文法的引入 ㈡规则 可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。上述英文句子可用下述规则来描述： 3.1 文法的引入 1.???????? 句子→主语谓语 2.???????? 主语→冠词形容词名词 3.???????? 冠词→the| a 4.???????? 形容词→big 5.???????? 名词→elephant| banana 6.???????? 谓语→动词直接宾语 7.???????? 直接宾语→冠词名词 8.???????? 动词→ate 3.1 文法的引入 ㈢由规则推导句子 可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。 3.1 文法的引入 句子 ? 主语谓语  ? 冠词形容词名词谓语 ?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 3.1 文法的引入 上述推导可简单表示为： 句子 ? the big elephant ate a banana。 3.1 文法的引入 值得注意的是用上述规则可推导出多个句子，因存在推导 句子 ? the big banana ate an elephant 故the big banana ate an elephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。 一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。 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 ? xVy,即V? xVy，称文法含有间接递归。 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|0 D→0|1|2|3|4|5|6|7|8|9|0 3.1 文法的引入 例1：无符号整数1 N ? D ? 1 例2：无符号整数23 N ? ND ? DD ? 2D ? 23 例3：无符号整数456 N ? ND ? NDD ? DDD ? 4DD ? 45D ? 456 3.2 上下文无关文法 文法是描述语言结构的形式规则（语法规则），这些规则必须是准确的，易于理解的，应当有较强的描述能力，足以描述各种不同的结构 3.2 上下文无关文法 形式语言的奠基人乔姆斯基将文法分为4种类型，它们是： l???????? 短语文法（0型文法） l???????? 上下文有关文法（1型文法） l???????? 上下文无关文法（2型文