第2章高级语言及其文法2.1语言概述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.2基本定义2.2基本定义2.2基本定义2.2基本定义2.3文法的定义<赋值语句><左部量>=<右部表达式><左部量><简单变量><左部量><下标变量><简单变量>a<简单变量>b<简单变量>c<下标变量>m[1]<下标变量>m[2]<下标变量>m[3]<右部表达式><简单变量><运算符><简单变量><右部表达式><简单变量><运算符><下标变量><右部表达式><下标变量><运算符><简单变量><右部表达式><下标变量><运算符><下标变量><运算符>+<运算符>-非终结符号集V={<赋值语句>，<左部量>，<右部表达式>，<简单变量>，<下标变量>，<运算符>}终结符号集T={a，b,c,m[1],m[2],m[3],+,-}语法规则集P={<赋值语句><左部量>=<右部表达式>，……}开始符号S=赋值语句文法G的形式定义文法G的形式定义例2.9赋值语句的文法例2.9赋值语句的文法（续）产生式的简写句子的派生(推导)-从产生语言的角度句子的归约-从识别语言的角度基于产生式的变换--推导或归约(多步)推导文法G产生的语言文法G产生的语言(续)推导/归约举例句型与句子句型与句子2.４文法的分类(Chomsky体系)1.上下文有关文法(CSG)2.上下文无关文法(CFG)例标识符的文法3.正规文法(RG)文法举例文法举例文法举例Chomsky体系——总结文法的类型ＢＮＦ范式——Backus-NaurFormBackus-NormalFormＢＮＦ范式——Backus-NaurFormBackus-NormalForm2.5CFG的语法树语法树语法树定义例句子结构的表示(文法E→E+E|E*E|(E)|id）短语(Phrase)例：(直接)短语句柄(Handle)：最左直接短语用子树解释短语，直接短语，句柄E例短语与分析树(文法E→E+E|E*E|(E)|id）id+id*id的不同推导E→E+E|E*E|(E)|id最左推导与最右推导2.6CFG的二义性文法的二义性E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文法的二义性二义性（ambiguity)的定义二义性的消除2.7本章小结