《编译原理（第三版）课后答案解析》

定义：上下文无关文法是一种描述形式语言的数学模型，由四元组 G=(V,Σ,R,S) 构成。其中，V 是非终结符集合，Σ 是终结符集合，R 是产生式规则集合，S 是起始符号。 示例：在文档中，有 G(E) 和 G(S) 等上下文无关文法，用于描述表达式的结构。例如，G(E) 的定义如下： E→T∣E+T∣E−T T→F∣T∗F∣T/F F→(E)∣i 这里，E、T、F 是非终结符，而 +、−、∗、/、(、) 和 i 是终结符。该文法用于描述算术表达式的构造方式。 推导是根据文法规则从起始符号逐步生成句子的过程，分为两种类型： 最左推导：始终扩展当前最左边的未展开非终结符。 最右推导：始终扩展当前最右边的未展开非终结符。 例如，在 G(N) 的上下文无关文法中，数字串的最左推导过程可以表示为： N⇒ND⇒NDD⇒⋯⇒DDD⇒0DDD⇒01DD⇒012D⇒0127 语法树是通过图形方式展示字符串如何根据文法规则进行推导的结构。它清晰地反映了推导过程中的层次关系。例如，对于表达式 i+i∗i，其语法树可以直观地展示操作符和操作数之间的层次结构。 如果一个句子存在多个不同的语法树，即可以通过多种推导过程生成，那么这个文法就被认为是二义性的。例如，句子 iiiei 有两个可能的语法树，这表明该文法存在二义性。 在自动机理论中，确定化是指将非确定有限自动机（NFA）转换为确定有限自动机（DFA），以确保每个状态在读取输入符号时只有一个确定的转移路径。最小化则是指去除 DFA 中的冗余状态，以获得更简洁的模型。文档中提供了 DFA 确定化和最小化的详细步骤示例。 正则表达式是一种用于匹配字符串模式的工具。文档中给出了许多正则表达式的例子，例如 (0∣1)∗01，用于匹配所有以“01”结尾的由 0 和 1 组成的字符串。正则表达式在文本处理和模式匹配中具有广泛应用。 综上所述，编译原理不仅涉