形式语言基础：符号串集合和规则

编译原理与形式语言基础 本文主要介绍了编译原理中的形式语言基础知识，包括形式语言的定义、基本观点、符号串集合、规则、文法定义、语法成分、文法变换方法、形式语言的分类等。通过对形式语言的研究，可以更好地理解编译原理中的语言处理和计算机科学。 1. 形式语言的定义 形式语言是符号串集合，符号串是符号的有限序列，符号串集合是有限个或者无限个符号串组成的集合。形式语言是由文法定义的，文法是指符号串的组成规则。 2. 形式语言的基本观点 形式语言的基本观点是：语言是符号串集合。形式语言理论研究的基本问题是研究符号串集合的表示方法、结构特性和运算规律。 3. 符号串集合 符号串集合是有限个或者无限个符号串组成的集合。例如，L1={00,01,10,11}是一个有限语言，L2={abmc,bn|m>0,n≥0}是一个无限语言。 4. 规则 规则是以某种形式表达的在一定范围内共同遵守的章程和制度。这里，指符号串的组成规则。 5. 文法定义 文法定义是指符号串的组成规则，例如，S->aBS,S->b,B->cS,B->ε。 6. 语法成分 语法成分是指符号串的组成部分，例如，句子、短语、词等。 7. 文法变换方法 文法变换方法是指将一个文法变换为另一个文法的方法，例如，S->aBS|aS,S->b,B->cS。 8. 形式语言的分类 形式语言可以分为有限语言和无限语言两类，例如，L1={00,01,10,11}是有限语言，L2={abmc,bn|m>0,n≥0}是无限语言。 9. 符号串的运算 符号串的运算包括连接、方幂、闭包等，例如，ε.ε=ε，εn=εε…ε=εεn-1=εn-1ε。 10. 固有头、固有尾 固有头、固有尾是指符号串的前缀、后缀和子串，例如，z=xy,x是z的头，y是z的尾，如果x非空则y是固有尾，如果y非空则x是固有头。 通过本文的学习，可以更好地理解编译原理中的形式语言基础知识，对计算机科学和语言处理有重要意义。