第三章文法和语言§3.1文法的直观概念二.符号（字符）symbol三.符号串（字）string符号串的头尾：如果z＝xy是一符号串，那么x是z的头，y是z的尾。如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固有头。符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。四.符号串的运算1.符号串的连接connection2.符号串的幂运算power3.集合的乘积product空集Φemptyset4.集合的幂运算5.集合A的正闭包A+与闭包A*【例如】设A={a},则A+＝{a,aa,aaa,……}={an|n>=1}A*＝{,a,aa,aaa,……}={an|n>=0}3.3文法和语言的形式定义2、文法定义例文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a…<字母>→z<数字>→0…<数字>→9}S=<标识符>文法的写法元符号:→∷=|<>习惯大写字母表示非终结符小写字母表示终结符推导的定义推导若存在v=w0w1...wn=w,(n>0)则记为vw，称作v推导出w，或w归约到v若有vw或v=w，则记为vw句型、句子的定义句型、句子(文法生成的)语言的定义例文法G[S]：（1）S→aSBE（2）S→aBE（3）EB→BE（4）aB→ab（5）bB→bb（6）bE→be（7）eE→eeL（G）={anbnen|n≥1}G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成文法的等价【例】设计一个表示所有标识符的文法【例】用文法定义一个含+、*的算术表达式。【例】设字母表∑＝{a,b}，设计一个文法，描述语言L={abna|n0}【例】描述语言L={abna|n0}的等价文法【例】设有文法G[S]:S→01|0S1求该文法所描述的语言【例】设有文法G[S]:S→0S|1S|求该文法所定义的语言【例】设有文法G[A]:A→yB,B→xB|x求该文法所定义的语言【例】考虑文法G1:S→ABA→aA|aB→bB|b我们可以分析得出L(G1)={ambn|m,n≥1}【例】构造一个文法G2使L(G2)={anbn|m,n≥1}G2和G1的区别在于，G2的每个句子中a和b的个数必须相同。我们可以写出文法G2:S→aSb|ab【例】设字母表∑＝{a,b},试设计文法，描述语言L={a2n,b2n|n1}3.4文法的类型文法的类型文法的类型3型文法文法的类型文法和语言文法和语言根据形式语言理论,文法和识别系统间有这样的关系带a0a1a2a3a4a5a6a7a8…an-1an3型文法产生的语言是有穷自动机（FA）所接受的集合.3型文法和有穷自动机（FA）3型文法和有穷自动机（FA）3型文法和有穷自动机（FA）正规文法和正规式对上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r)例r=a(ad)正规文法和正规式对G=(VN,VT,P,S),存在一个=VT上的正规式r:L(r)=L(G)正规文法和正规式3.5上下文无关文法及其语法树语法树---句型推导的直观表示(句型、推导)语法树上下文无关文法的语法树语法树---句型推导的直观表示规范推导规范句型二义文法文法的二义性和语言的二义性3.6句型的分析（上下文无关文法）句型的分析算法分类两种方法反映了两种语法树的构造过程。1、自上而下的语法分析2、自下而上的语法分析自上而下的语法分析(1)S→cAd(2)A→ab(3)A→a识别输入串w=cad是否为该文法的句子(1)S→cAd(2)A→ab(3)A→a识别输入串w=cabd是否为该文法的句子自下而上的语法分析3、句型分析的有关问题句型aabbaa的语法树3.7文法实用中的一些说明化简文法2、上下文无关文法中的ε规则练习练习