程序设计语言的语法描述

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

1、第3章程序设计语言的语法描述3.1文法的引入3.2上下文无关文法3.3文法举例（略）使用文法对程序设计语言的结构进行定义和描述。8/13/20213.1文法的引入先讨论自然语言的文法。例：thebigelephentateabanana㈠语法树根据英语的语法，上述句子的语法结构可用图（语法树）表示如下：非叶结点称为语法单位，在形式语言中称为非终结符。处于根结点位置的结点又称为开始符号。叶结点称为单词符号，在形式语言中称为终结符。8/13/2021㈡规则可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。<句子>→<主语><谓语><主语>→<冠词><形容

2、词><名词><冠词>→the

3、a<形容词>→big<名词>→elephant

4、banana<谓语>→<动词><直接宾语><直接宾语>→<冠词><名词><动词>→ate㈢由规则推导句子可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。上述英文句子可用下述规则来描述：8/13/2021<句子><主语><谓语><冠词><形容词><名词><谓语>the<形容词><名词><谓语>thebig<名词><谓语>thebigelephant<谓语>thebigelephant<动词><直接宾语>thebigeleph

5、antate<直接宾语>thebigelephantate<冠词><名词>thebigelephantatea<名词>thebigelephantateabanana上述推导可简单表示为：<句子>thebigelephantateabanana。值得注意的是用上述规则可推导出多个句子，因存在推导<句子>abigbananaatetheelephant所以，abigbananaatetheelephant也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。综上

6、所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结符、开始符号（特殊非终结符）及产生式四个要素构成。从开始符号出发，根据产生式能推导出的句子全体称为文法所规定的语言8/13/2021㈣递归规则和递归文法递归是编译技术中的一个重要概念。①递归定义：定义某事物，又用到该事物本身。②递归规则（直接递归）：在规则的左部和右部有相同的非终结符。例：U→xUy，通常用大写字母表示非终结符，用小写字母表示终结符。⑴左递归规则：x=ε，U→Uy（ε表示空串）⑵右递归规则：y=ε，U→xU③间接递归：由规则推导产生。例：V→Uy

7、Z，U→xV因存在推导VUyxVy，故存在间接递

8、归。⑴间接左递归：若x=ε，则VVy。⑵间接右递归：若y=ε，则VxU。④递归文法：含有递归规则和间接递归的文法，称为递归文法。利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。8/13/20213.2上下文无关文法形式语言的奠基人乔姆斯基（Chomsky）将文法分为4种类型，它们是：短语文法（0型文法）上下文有关文法（1型文法）上下文无关文法（2型文法）正规文法（3型文法）这四种文法在形式语言中都有严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程序设

9、计语言的语法结构。以后，“文法”一词若无特别说明，则指“上下文无关文法”。8/13/2021㈠文法和语言一个文法G是一个四元式(VT,VN,S,P)，其中VT是一个终结符的非空有限集，终结符通常用小写字母表示。VN是一个非终结符的非空有限集，非终结符通常用大写字母表示。S是一个特殊的非终结符（S∈VN），称为开始符号。P是一个产生式（规则）的有限集合，每个产生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。①终结符是语言的基本符号，即程序设计语言的单词。语法分析时，终结符用单词的种别表示。根据前面约定：标识符（简单变量）：i无符号整常数：x无符号实常数：y单字符单词：用

10、单词本身表示（例单词“+”的种别用+表示）多字符单词：需特别指定（例“++”用$表示）8/13/2021②非终结符表示抽象的语法单位.例“算术表达式”、“布尔表达式”、“赋值语句”、“说明语句”和“程序”等。非终结符通常用大写字母表示，也可以用带尖括号的汉字表示。③开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法单位。例如讨论算术表达式，那么描述算术表达式文法的开始符号就是<算术表达式>。在程序设计语言中，我们最感兴趣的语法单位是“程序”。④产生式是定义语法单位的一种书写规则。上下文无关文法产生式