理解高级语言设计：文法二义性与上下文无关文法

本章内容主要涉及编译原理，特别是关于高级语言设计的基础知识，包括符号串、文法和语言的概念、分类，以及上下文无关文法、语法树、二义性等方面的讨论。同时，强调了对C和PASCAL等高级语言设计过程的理解，通过这两个语言的比较来阐述语言的基本构建块，如字符集定义、单词定义、数据类型、表达式、语句和程序定义。 在高级语言设计中，首先介绍的是符号和符号串的概念。字母表（Σ）是构成高级语言程序的字符集合，它可能包括字母、数字和特殊符号。符号是字母表中的单个元素，而符号串是由这些符号组成的有限序列。符号串的顺序至关重要，因为它决定了字符串的含义。例如，"ab"不同于"ba"。符号串的运算包括计算长度、定义空符号串（ε）、连接符号串以及集合的乘积运算。 接着，讨论了文法和语言的相关概念。上下文无关文法是一种形式化的规则系统，用于定义语言的结构。推导是文法中的一个重要操作，它描述了如何从开始符号生成句子的过程。语法树是这种推导的图形表示，每个节点都代表一个符号，根节点通常由开始符号标记，非终结符的替换产生下一层节点。二义性是指一个文法可以有多种解释，导致相同的输入字符串可以有多个不同的语法树，这在语言设计中是需要避免的。 此外，文法的语言生成过程涉及到句型和句子。句型是文法中由非终结符推导出的符号串，而句子是最终没有非终结符的句型，即语言中的有效构造。语言是文法所能生成的所有句子的集合。 高级语言设计过程包括定义基本字符集、单词（如标识符、关键字、常量等）、数据类型、表达式规则、语句结构以及程序结构。以C和PASCAL为例，它们的字符集、单词定义、数据类型、表达式、语句和程序结构都有各自的特点。例如，C语言的字符集包括字母、数字和专用符号，而PASCAL在数据类型和程序结构上可能有所不同。 最后，提到了集合的方幂和闭包运算，这些概念在描述语言和文法的可能构造时非常有用。Σ的闭包Σ*包含了所有可能的符号串，包括空符号串，而Σ+排除了空符号串，只包含非空符号串。 总结来说，本章内容涵盖了编译原理的基础，包括符号串的性质、上下文无关文法的推导和二义性问题，以及高级语言设计的关键要素，如字符集、单词、数据类型和表达式。对于理解和设计高级编程语言具有重要意义。