第2篇 形式语言概论.ppt

第2章 形式语言概论;第2章 形式语言概论; 概 述;概 述;概 述;字母表和符号串;字母表和符号串;字母表和符号串;字母表和符号串;字母表和符号串;符号串的运算;符号串的运算;{?}A=A{?}=A;符号串的运算;符号串的运算;符号串的运算;符号串的运算;符号串的运算;符号串的运算;符号串的运算;文法和语言的形式定义;文法和语言的形式定义;文法和语言的形式定义;文法和语言的形式定义;文法和语言的形式定义;文法和语言的形式定义;文法的形式定义 ;文法的形式定义 ;文法的形式定义 ;文法的形式定义 ;文法的形式定义 ;文法的形式定义 ;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义; 若G和G是两个不同的文法，如果它们描述的语言相同，那么，称G和G 为等价文法。;描述该语言的文法是否G？; 对于文法G来说，它所产生的有些符号串，如aabb，bbaa，…… 不属于语言L，即设计的文法超出了所定义语言的范围。 ;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;文法的形式定义;语言的形式定义 ;语言的形式定义;语言的形式定义;语言的形式定义 ;即表示从?0 出发，经 一步或若干步 或者说 使用若干次规则可推导出 ?n。 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;（2）L(G)是VT* 的子集。即属于VT* 的符 号串 x 不一定属于L(G)。;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;语言的形式定义 ;规范推导和规范归约;规范推导和规范归约;规范推导和规范归约;规范推导和规范归约;规范推导和规范归约;规范推导和规范归约;规范推导和规范归约;规范推导和规范归约;规范推导和规范归约;递归规则与文法的递归性;递归规则与文法的递归性;递归规则与文法的递归性;递归规则与文法的递归性;递归规则与文法的递归性;递归规则与文法的递归性;短语、直接短语和句柄;短语、直接短语和句柄;短语、直接短语和句柄;短语、直接短语和句柄;短语、直接短语和句柄;短语、直接短语和句柄;短语、直接短语和句柄;短语、直接短语和句柄;短语、直接短语和句柄;语法树与文法的二义性 ;推导和语法树;推导和语法树;推导和语法树 ;E?E+T ?E+F ?E+i ?T+i ?T*F+i ?T*i+i ?F*i+i ?i*i+i;推导和语法树 ;推导和语法树 ;推导和语法树 ;推导和语法树 ;推导和语法树;推导和语法树 ;推导和语法树;文法的二义性;文法的二义性 ;文法的二义性 ;文法的二义性 ;文法二义性的消除 ;文法二义性的消除;文法二义性的消除;文法二义性的消除 ;文法二义性的消除 ;文法二义性的消除 ;文法二义性的消除;文法二义性的消除;文法二义性的消除; 通常我们只说文法的二义性, 而不说语言的二义性, 这是因为可能有两个不同的文法G和G ，而且其中一个是二义性的，另一个是无二义性的, 但却有L(G)=L(G), 即这两个文法所产生的语言是相同的。;文法二义性的消除 ;文法和语言的分类 ;文法和语言的分类 ;文法和语言的分类 ;文法和语言的分类 ;文法和语言的分类 ;文法和语言的分类 ;例如前面描述算术表达式的文法G[E]:; 其描述的语言为 L2(G[S])={x | x ? {a, b}+ 且x中a和b的个数相同} ;文法和语言的分类 ; 例如，用左线性正规文法和右线性正规文法定义标识符 ; 例如，用左线性正规文法和右线性正规文法定义无符号整数;文法和语言的分类 ;有关文法的实用限制和变换 ;有关文法的实用限制和变换 ;有关文法的实用限制和变换 ;有关文法的实用限制和变换 ;; (2) 分析已知语言句子的结构特征, 设计 出相应的一组规则，但不唯一。; 分析 根据语言句子的结构特征，设计出相 应规则; 分析 根据语言句子的结构特征，设计出相 应规则 ;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结