编译原理：文法和语言
📌目录
- ⚖️ 文法和语言：形式语言理论的基石
- 🎯 一、基本概念
- （一）字母表与字符串
- （二）语言
- 📦 二、文法的形式化定义
- （一）文法的定义
- （二）产生式
- （三）文法示例
- 🌐 三、推导与归约
- （一）推导
- （二）归约
- （三）句型与句子
- 📊 四、语法树与二义性
- （一）语法树
- （二）二义性
- （三）消除二义性
- 🔍 五、乔姆斯基文法体系
- （一）文法分类
- （二）各类型文法详解
- （三）文法体系对比
- 📝 六、文法的化简与变换
- （一）无用符号消除
- （二）空产生式消除
- （三）单产生式消除
- （四）乔姆斯基范式（CNF）
- （五）格雷巴赫范式（GNF）
- 📝 总结
⚖️ 文法和语言：形式语言理论的基石
文法和语言是编译原理的形式化基础。从乔姆斯基文法体系的建立，到上下文无关文法在编程语言中的广泛应用，文法理论为编译程序的设计提供了坚实的数学基础。什么是文法？如何精确定义一门语言？不同等级的文法有何区别？推导、归约、语法树之间是什么关系？本文将系统介绍文法和语言的核心概念，帮助您深入理解形式语言理论的精髓。
🎯 一、基本概念
（一）字母表与字符串
字母表（Alphabet）是符号的非空有穷集合，通常用Σ表示。
字母表示例: Σ₁ = {a, b} 二元字母表 Σ₂ = {0, 1} 二进制字母表 Σ₃ = {a, b, c, ..., z} 小写字母表 Σ₄ = {a, b, ..., z, A, B, ..., Z, 0, 1, ..., 9} 字母数字表 编程语言的字母表: Σ = {a-z, A-Z,