形式语言课件-2 考研的朋友过来看看吧

形式语言是计算机科学和编译原理中的核心概念，主要用于描述编程语言的语法结构或模拟自然语言的语法特性。Chomsky在1956年引入的形式语言理论为编译器设计提供了数学基础。本章主要关注与编译实现相关的形式语言理论的基本概念。 1. **形式语言**：形式语言是一种数学系统，它使用一组特定的符号和规则来描述语言。在计算机科学中，这些语言通常被用来描述编程语言的结构，有时也尝试模拟人类语言的语法，但不涉及语义。形式语言理论是研究符号串集合的性质和结构。 2. **符号串与符号串集合**：符号串是由字母表中的符号组成的有限序列。例如，如果字母表Σ={0,1}，那么"101"就是一个符号串。符号串的长度是其包含的符号数量，空串ε是长度为0的特殊符号串。符号串之间可以通过连接运算形成新的符号串，如"101"和"1"连接得到"1011"。此外，符号串还可以进行方幂运算，例如"x"的三次方幂"xxx"。 3. **文法**：文法是定义形式语言的一组规则，通常分为不同的类型，如Chomsky文法。其中，上下文无关文法是编译器设计中常见的，因为它能描述大多数高级编程语言的结构。文法的等价变换是指不同形式的文法可以描述相同的语言集合。 4. **句型分析**：句型分析，又称为语法分析，是从输入的符号串出发，根据文法规则推导出语法树的过程。这个过程对于理解程序的结构至关重要，是编译器前端的关键步骤。 5. **集合运算**：符号串集合包括符号串的乘积和闭包运算。符号串集合的乘积是将两个集合中的符号串逐一连接形成新集合的过程。闭包运算则考虑所有可能的符号串，包括空串，而正闭包排除了空串。 形式语言理论是构建编译器和解析器的基础，它帮助我们理解和描述编程语言的结构，从而能够将源代码转换为目标代码。在准备计算机科学考研的过程中，理解和掌握这些概念是至关重要的，因为它们构成了编译原理这门学科的核心。通过深入学习形式语言，我们可以更好地设计和理解编程语言，进而开发更高效、准确的编译工具。