程序设计语言的语法描述.ppt

《程序设计语言的语法描述.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章程序设计语言的语法描述3.1文法的引入文法：对语言结构的定义和描述。先讨论自然语言的文法。例：thebigelephentateabanana3.1文法的引入㈠语法树根据英语的语法，上述句子的语法结构可用图（语法树）表示如下：3.1文法的引入3.1文法的引入①非叶结点称为语法单位，在形式语言中称为非终结符。②处于根结点位置的结点又称为开始符号。③叶结点称为单词符号，在形式语言中称为终结符。3.1文法的引入㈡规则可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。上述英文句子可用下述规则来描述：3.1文法的引入1.<句子>→<主语><谓语>2.<

2、主语>→<冠词><形容词><名词>3.<冠词>→the

3、a4.<形容词>→big5.<名词>→elephant

4、banana6.<谓语>→<动词><直接宾语>7.<直接宾语>→<冠词><名词>8.<动词>→ate3.1文法的引入㈢由规则推导句子可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。3.1文法的引入<句子><主语><谓语><冠词><形容词><名词><谓语>the<形容词><名词><谓语>thebig<名词><谓语>thebigelephant<谓语>thebigelephant<动词>

5、<直接宾语>thebigelephantate<直接宾语>thebigelephantate<冠词><名词>thebigelephantatea<名词>thebigelephantateabanana3.1文法的引入上述推导可简单表示为：<句子>thebigelephantateabanana。3.1文法的引入值得注意的是用上述规则可推导出多个句子，因存在推导<句子>thebigbananaateanelephant故thebigbananaateanelephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。一个语法正确的句子不能

6、保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。3.1文法的引入㈣递归规则和递归文法①递归定义定义某事物，又用到某事物。在规则的左部和右部有相同的非终结符U→xUyU为非终结符，xy为终结符。3.1文法的引入㈣递归规则和递归文法②递归规则（直接递归）在产生式的左部和右部都含有非终结符U，故U→xUy是递归规则。若x=ε,U→Uy称为左递归规则，若y=ε，U→xU称为右递归规则。3.1文法的引入㈣递归规则和递归文法③间接递归文法的递归性还可以在推导过程中由规则间接产生：V→Uy

7、z,U→xV上述规则不是递归规则，但存在推导VUyxVy,即VxVy，

8、称文法含有间接递归。3.1文法的引入㈣递归规则和递归文法④递归文法含有递归规则或间接递归的文法称为递归文法3.1文法的引入利用递归文法我们可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。3.1文法的引入例：定义无符号整数。①不采用递归规则，描述无符号整数全体就要使用无穷多条的规则。<无符号整数>→<数字>

9、<数字><数字>

10、<数字><数字><数字>

11、…<数字>→0

12、1

13、2

14、3

15、4

16、5

17、6

18、7

19、8

20、9

21、0②采用递归规则，描述无符号整数全体仅需12条规则。<无符号整数>→<无符号整数><数字>

22、<数字>N→ND

23、D<数字>→0

24、1

25、

26、2

27、3

28、4

29、5

30、6

31、7

32、8

33、9

34、0D→0

35、1

36、2

37、3

38、4

39、5

40、6

41、7

42、8

43、9

44、03.1文法的引入例1：无符号整数1ND1例2：无符号整数23NNDDD2D23例3：无符号整数456NNDNDDDDD4DD45D4563.2上下文无关文法文法是描述语言结构的形式规则（语法规则），这些规则必须是准确的，易于理解的，应当有较强的描述能力，足以描述各种不同的结构3.2上下文无关文法形式语言的奠基人乔姆斯基将文法分为4种类型，它们是：l短语文法（0型文法）l上下文有关文法（1型文法）l上下文无关文法（2型文法）l正规文法（3型文法）这四种文法在形式语言中都有

45、严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程序设计语言的语法结构。以后，“文法”一词若无特别说明，则指“上下文无关文法”。3.2上下文无关文法上下文无关文法所定义的语法单位和该语法单位可能出现的环境无关。自然语言中，一个句子或一个字，其意义和它们所处的上下文有密切关系，因此上下文无关文法不适合描述自然语言。3.2上下文无关文法㈠文法和语言一个文法G是一个四元式(VT,VN,S,VP)，其中lVT是一个终结符的非空有限集，终结符通常用小写字母表示。lV