第3章文法和语言第3章文法和语言第3章文法和语言第3章文法和语言第3章文法和语言3.1文法的直观概念3.1文法的直观概念3.1文法的直观概念第3章文法和语言3.2符号和符号串3.2符号和符号串3.2符号和符号串3.2符号和符号串3.2符号和符号串3.2符号串的运算3.2符号串的运算3.2符号串的运算3.2符号串的运算3.2符号串的运算2.2符号串的运算{}A=A{}=A2.2符号串的运算2.2符号串的运算2.2符号串的运算2.2符号串的运算2.2符号串的运算3.2符号和符号串第3章文法和语言第3.3章文法和语言的形式定义3.3文法和语言的形式定义3.3文法和语言的形式定义3.3文法的形式定义3.3文法的形式定义3.3文法的形式定义3.3文法的形式定义3.3文法的形式定义3.3文法的形式定义3.3文法的形式定义例文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a…<字母>→z<数字>→0…<数字>→9}S=<标识符>3.3文法的形式定义习惯大写字母表示非终结符小写字母表示终结符直接推导“”α→β是文法G的产生式，若有v,w满足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*则称v直接推导到w,记作vw也称w直接归约到v例：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S1推导推导的定义例：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S=>+00001111S=>*S00S11=>*00S11句型有文法G[S]，若S=>*x，则称x是文法G[S]的句型。句子有文法G，若S=>*x，且x∈VT*，则称x是文法G的句子。例：G：S→0S1，S→01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01例：G[E]：E→E+T|TT→T*F|FF→(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号a，+，*，(和)构成的算术表达式(文法生成的)语言的定义例文法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生成文法的等价推导和规则的区别3.3文法和语言的形式定义上节内容回顾第3章文法和语言3.4文法的类型文法的类型文法的类型文法的类型3型(正规)文法文法和语言文法和语言第3章文法和语言上下文无关文法及其语法树语法树语法树根据推导序列，对每步推导画相应分枝根据归约序列，对每步归约画相应分枝语法树语法树语法树语法树二义文法文法二义性的消除文法二义性的消除文法二义性的消除文法二义性的消除文法二义性的消除文法二义性的消除文法二义性的消除文法二义性的消除文法二义性的消除通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法G和G'，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G'),即这两个文法所产生的语言是相同的。文法二义性的消除第3章文法和语言（上下文无关文法）句型的分析句型的分析算法分类两种方法反映了两种语法树的构造过程。自上而下的语法分析自下而上的语法分析自上而下的语法分析自下而上的语法分析句型分析的有关问题短语、直接短语和句柄短语、直接短语和句柄短语、直接短语和句柄短语、直接短语和句柄短语、直接短语和句柄短语、直接短语和句柄短语、直接短语和句柄短语、直接短语和句柄子树简单子树直观解释：句型的短语、直接短语和句柄句型的短语、直接短语和句柄句型的短语、直接短语和句柄第3章文法和语言文法实用中的一些说明化简文法上下文无关文法中的ε规则第3章文法和语言3.8典型例题及解答(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。分析根据语言句子的结构特征，设计出相应规则分析根据语言句子的结构特征，设计出相应规则本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结本章小结