第二章高级语言及其语法描述内容高级程序语言2.1程序语言的定义2.1程序语言的定义2.1.1语法2.1.1语法2.1.1语法2.1.2语义2.2高级语言的一般特性2.2.1高级语言的分类2.2.2程序结构2.2.2程序结构2.2.2程序结构2.2.2程序结构2.2.2程序结构2.2.3数据类型与操作2.2.3数据类型与操作2.2.3数据类型与操作2.2.3数据类型与操作2.2.3数据类型与操作数组元素地址计算2.2.3数据类型与操作2.2.3数据类型与操作2.2.4语句与控制结构2.2.4语句与控制结构2.2.4语句与控制结构2.2.4语句与控制结构2.2.4语句与控制结构2.2.5参数传递2.2.5参数传递2.2.5参数传递2.2.5参数传递2.2.5参数传递2.2.5参数传递2.2.5参数传递2.2.6存储管理2.2.6存储管理2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3程序语言的语法描述2.3.1文法2.3.1文法2.3.1文法2.3.1文法2.3.1文法2.3.1文法2.3.1文法2.3.1文法定义：称A直接推出，即A仅当A是一个产生式，且，(VTUVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。或称n归约到1。例：对文法(1)E(E)(E+E)(i+E)(i+i)通常，用表示：从1出发，经过一步或若干步，可以推出n。例：(i*i+i)是文法G3的一个句子。E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E，(E)，(E*E+E)，…，(i*i+i)是句型。例：G：S→0S1，S→01L(G)={0n1n|n≥1}例：文法G1(S)：SABAaA|aBbB|bG1(S)的语言?L(G1)={ambn|m，n>0}例：文法G[S]：S→aSBES→aBEEB→BEaB→abbB→bbbE→beeE→eeL（G）={anbnen|n≥1}2.3.1文法2.3.1文法2.3.1文法2.3.2文法的类型2.3.2文法的类型2.3.2文法的类型2.3.2文法的类型2.3.2文法的类型2.3.2文法的类型L5={anbn|n1}不能由正规文法产生，但可由上下文无关文法产生：G5(S)：SaSb|abL6={anbncn|n1}不能由上下文无关文法产生，但可由上下文有关文法产生：G6(S)：SaSBC|aBCCBBCaBabbBbbbCbccCcc程序设计语言不是上下文无关语言，甚至不是上下文有关语言。L7={c|(a|b)*}不能由上下文无关文法产生，也不可由上下文有关文法产生。标识符引用过程调用过程中，"形-实参数地对应性"(如个数，顺序和类型一致性)有的语言甚至连上下文有关文法也不能产生，只能由0型文法产生。但是现今程序设计语言的语言结构，用上下文无关文法描述就足够了。2.3.2文法的类型2.3.2文法的类型2.3.2文法的类型2.3.3上下文无关文法2.3.3上下文无关文法2.3.3上下文无关文法规范推导规范句型从一个句型到另一个句型的推导往往不唯一。E+Ei+Ei+iE+EE+ii+i最左（最右）推导：在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型2.3.4语法树2.3.4语法树2.3.4语法树2.3.4语法树2.3.4语法树上下文无关文法的语法树2.3.5二义文法2.3.5二义文法2.3.5二义文法文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。二义文法改造为无二义文法G[E]:E→iG[E]：E→T|E+TE→E+ET→F|T*FE→E*EF→（E）|iE→(E)规定优先顺序和结合律如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。二义文法：G(E)：Ei|E+E|E*E|(E))描述程序设计语言时，对于上下文无关文法的限制：1不含PP形式的产生式2每个非终结符P必须有用处即：小结练习练习练习