形式语言基础：Chomsky的符号串集合与文法定义

"本章深入探讨了形式语言的基础知识，包括其起源、定义以及与编译原理的关系。形式语言是符号串的集合，由特定的文法定义，并通过文法变换方法进行研究。此外，本章还介绍了形式语言的分类，如有限语言和无限语言，以及如何对符号串进行各种运算，如连接、方幂和闭包等。" 形式语言是计算机科学中用于描述计算过程和编程语言结构的一种数学工具，起源于1956年由诺姆·乔姆斯基（Noam Chomsky）创立。它主要关注语言的语法方面，即符号串的组织结构和规则。形式语言理论的核心是研究符号串集合的表示、结构特性以及它们之间的运算规律。 2.1 形式语言是符号串集合：形式语言是由一个字母表中的符号按照一定的规则组成的字符串集合。每个字符串称为一个句子。例如，L1={00,01,10,11}是一个形式语言，它的字母表是{0,1}，所有可能的符号串构成了这个语言。 2.2 形式语言由文法定义：文法是规定符号串构造方式的一组规则。它可以用来描述语言中的合法句子结构。例如，L2={abmc,bn|m>0,n≥0}，由两个规则定义，分别对应于句型"abmc"和"bn"。 2.3 语法成分的定义：文法通常包含四个基本成分：终端符号（语言中的基本符号）、非终端符号（代表更复杂的结构）、起始符号（文法生成的起点）和产生规则（描述符号如何组合成句子）。 2.4 两类特性文法：Chomsky将文法分为四种类型，从0型到3型，其中0型文法（无限制文法）最自由，3型文法（正规文法）最简单。不同类型的文法对应于不同复杂度的语言。 2.5 文法变换方法：文法可以通过不同的变换方法来简化或增强其表达能力，例如，上下文无关文法（Context-Free Grammar, CFG）可以通过LL解析或LR解析等方式进行变换。 2.6 形式语言的分类：形式语言可以是有限的，如L1，只包含有限个符号串；也可以是无限的，如L2，包含无限多个符号串。此外，根据其生成句子的能力，语言还可以被分类为递归可枚举语言、递归语言等。 符号串的运算对于理解形式语言至关重要： 1. 连接：两个符号串可以连接成一个新的符号串，例如"a.b"连接成"ab"。 2. 方幂：一个符号串的n次方幂表示该符号串自身连接n次，如"εn"表示n个空符号串的连接。 3. 闭包：正闭包表示所有可能的符号串连接，星闭包则包括空符号串和所有可能的连接。 4. 或运算：两个符号串的并集表示任选其中之一。 5. 固有头和固有尾：固有头是符号串的最开始部分，固有尾是其最后部分，两者都可能是空符号串。 这些基本概念和运算构成了形式语言理论的基础，对理解和设计编译器、解析器以及形式证明等领域具有重要意义。在编译原理中，形式语言被用来描述源代码的结构，而文法则是编译器理解程序的关键工具。通过文法，编译器可以识别和分析程序的结构，从而将其转换为目标代码。