2021年文法和语言讲授：上下文无关文法与小C语言

"cha02-1 文法和语言--讲授 2021.ppt" 这是一份关于文法和语言的讲授材料，主要关注计算机科学中的形式语言和文法理论，特别是上下文无关文法在编程语言中的应用。内容涵盖了从文法的基本概念到形式定义，再到文法的类型和句型分析，特别强调了小C语言源程序及其文法的实例。 在文法的直观概念部分，我们了解到文法是一种规则系统，用于定义语言中的合法构造，即句子的生成方式。这些规则描述了一组记号如何组合成有意义的表达形式。例如，在自然语言中，文法规则指导我们如何构建正确的句子；在计算机语言中，文法定义了程序的结构和语法。 符号和符号串的概念是文法的基础。符号是文法的基本构建块，可以是字母、数字或其他字符。符号串是由一个或多个符号组成的序列，它们按照文法规则组合在一起，形成更复杂的结构。 文法和语言的形式定义是理解这一领域的关键。形式上，文法由一组非终结符、终结符、起始符号和产生规则组成。语言则是文法所能生成的所有符号串的集合。在本资料中，这部分被视为重点内容。 文法的类型，特别是上下文无关文法（Context-Free Grammar, CFG），是编程语言设计中常用的一种形式。上下文无关文法通过产生式规则来定义语言，其中每个规则都描述了一个非终结符如何被其他符号串替换。语法树是上下文无关文法的可视化表示，它显示了符号串如何按照文法规则分解。 补充实例部分，以小C语言为例，展示了如何用上下文无关文法来描述编程语言的结构。这里给出了小C语言文法的一些规则，如程序、声明序列、声明语句和标识符表的定义，帮助学生理解文法的实际应用。 句型的分析是解析理论的一部分，它涉及到如何确定一个给定的符号串是否属于特定文法定义的语言。这部分内容虽然在本讲授中被标记为重点，但将在后续章节进一步讲解。 作业部分可能包含与上述概念相关的练习题，旨在帮助学生巩固所学知识，并提升他们对文法和语言的理解。 本章的主要目的是引入和探讨用于描述语言语法的工具，尤其是对于程序设计语言，这对于理解和创建编译器或解释器至关重要。通过学习这些概念，学生能够更好地理解计算机如何理解和处理我们编写的代码。