高级语言及其文法2.1语言概述2.2基本定义2.3文法(Grammar)的定义2.4CFG的分析树（ParseTree）2.5文法的分类2.6文法的构造2.1语言概述2.1语言概述2.1语言概述2.1语言概述2.1语言概述2.1语言概述2.1语言概述形式语言于自动机理论的产生与作用形式语言于自动机理论的产生与作用形式语言于自动机理论的产生与作用计算思维能力的培养过程2.2基本定义2.2基本定义2.2基本定义2.2基本定义2.2基本定义2.2基本定义2.2基本定义2.2基本定义2.2基本定义2.3文法的定义考虑一个句子——文法要素的提取句子主语谓语（1）主语冠词形容词名词（2）冠词the形容词grey谓语动词直接宾语（5）动词助动词动词原形（6）助动词will动词原形eat直接宾语冠词名词（9）名词wolf名词goat终结符号集VT={the，grey,wolf,will,eat,goat}非终结符号集VN={句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形}语法规则集P={句子主语谓语，……}开始符号S=句子句子主语谓语冠词形容词名词谓语the形容词名词谓语thegrey名词谓语thegreywolf谓语thegreywolf动词直接宾语…...thegreywolfwilleatthegoat句子thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthegreywolf符合语法且符合语义的句子仅是：thegreywolfwilleatthegoat文法G的形式定义文法G的形式定义例2-1算术表达式的文法例2-1算术表达式的文法产生式的简写基于产生式的变换--推导或归约直接推导与归约（多步）推导推导/归约举例句型与句子文法G产生的语言id+id*id的不同推导E→E+E|E*E|(E)|id最左推导与最右推导短语(Phrase)例：(直接)短语句柄(Handle)：最左直接短语例2-2标识符的文法12.４文法的分类(Chomsky体系)上下文有关文法(CSG)上下文无关文法(CFG)例2-3标识符的文法2正规文法(RG)例非CFL的文法在我们使用的程序设计语言中,有些语言结构不能用上下文无关文法来描述。例2.9L1={wcw|w∈{a,b}+}。例,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。例2.10L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。Chomsky体系——总结文法的类型ＢＮＦ范式——Backus-NaurFormBackus-NormalFormＢＮＦ范式——BackusNormalForm例2-5句子结构的表示(文法E→E+E|E*E|(E)|id）2.5CFG的分析树短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。E例短语与分析树(文法E→E+E|E*E|(E)|id）二义性文法与先天二义性语言1.描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。考虑表达式下面的文法G[E],其产生式如下：EE+EE*E(E)a对于句子a+a*a,有如下两个最左推导：EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*aEE+Ea+Ea+E*Ea+a*Ea+a*aEE+EE+E*EE+E*aE+a*aa+a*a如果一个文法的句子存在两棵分析树,那么,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是二义性的。对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother