跳转至

第四章：上下文无关文法与下推自动机1

概览

一段话总结

本章聚焦上下文无关文法与下推自动机。上下文无关文法（2型文法）产生式形如\(A \to \alpha\)（\(A \in N\)，\(\alpha \in(N \cup T)^{*}\)），用于定义程序设计语言等。介绍了归约、推导（最左、最右推导）及推导树概念，三者相互等价。文法二义性指对句子存在两棵不同边缘为该句子的推导树，且消除二义性无一般算法。还讲述了上下文无关文法的变换、范式及下推自动机构成，最后布置了相关作业。

exported_image.png

详细总结

  1. 上下文无关文法概述
    • 定义与用途：上下文无关文法（2型文法）的产生式形式为\(A \to \alpha\)，其中\(A \in N\)（非终结符集合），\(\alpha \in(N \cup T)^{*}\)（终结符和非终结符组成的字符串集合）。它可用于定义程序设计语言、进行语法分析以及简化语言翻译等。
    • 回顾示例：对于语言\(L = \{ 0^n1^n | n \geq 1\}\)，存在上下文无关文法\(S \to 01\)，\(S \to 0S1\)，但该语言无法被有限自动机接受。
  2. 归约与推导
    • 概念：归约是自下而上的递归推理过程，将产生式的右部替换为左部；推导是自上而下的过程，将产生式的左部替换为右部。
    • 举例：以文法\(G_{exp }=(\{E, O\},\{(),+, *, v, d\}, P, E)\)为例，对字符串\(v *(v+d)\)进行归约和推导。
    • 最左推导与最右推导：最左推导是每一步总是替换最左边的非终结符，用\(\underset{lm}{\Rightarrow}\)表示推导关系，传递闭包用\(\underset{lm}{\stackrel{*}{\Rightarrow}}\)表示；最右推导是每一步总是替换最右边的非终结符，用\(\underset{rm}{\Rightarrow}\)表示推导关系，传递闭包用\(\underset{rm}{\stackrel{*}{\Rightarrow}}\)表示。
  3. 推导树
    • 定义：用图的方法表示一个句型的推导，称为推导树。文法的起始符为根，枝结点标记是非终结符，叶结点标记为终结符或\(\varepsilon\)。若枝结点有直接子孙\(x_{1}\)，\(x_{2}\)，…，\(x_{k}\)，则文法中有生成式\(A \to x_{1}x_{2}...x_{k}\)。
    • 举例：对于文法\(S \to S+S | S*S |(S)| a\)，句子\((a*a+a)\)有相应的推导树。
    • 与归约、推导的关系：字符串\(w \in T^{*}\)可以归约到非终结符\(A\)、\(A \stackrel{*}{\Rightarrow} w\)、\(A \underset{lm}{\stackrel{*}{\Rightarrow}} w\)、\(A \underset{rm}{\stackrel{*}{\Rightarrow}} w\)以及存在一棵根结点为\(A\)的分析树且边缘为\(w\)，这些命题相互等价。
  4. 二义性
    • 定义：2型文法是二义的，当且仅当对于句子\(\omega \in L(G)\)存在两棵不同的具有边缘为\(\omega\)的推导树，即某个句子能从不同的最左（右）推导推出。
    • 示例：句子\((a*a+a)\)对于文法\(S \to S+S | S*S |(S)| a\)有两棵不同的推导树，分别对应先算乘法和先算加法。
    • 消除问题：存在两个文法，一个有二义，一个无二义，但产生相同的语言，目前消除二义性无一般算法。
  5. 设计上下文无关文法
    • 例5：定义语言\(\{0^{n}1^{n} | n \geq 0\} \cup \{1^{n}0^{n} | n \geq 0\}\)的文法为\(S \to S_{1} | S_{2}\)，\(S_{1} \to 0S_{1}1 | \varepsilon\)，\(S_{2} \to 1S_{2}0 | \varepsilon\)。
    • 例6：定义语言\(L=\{\omega | \omega\)中\(a\)的个数和\(b\)的个数相同\(\}\)的文法为\(S \to ab|ba|\varepsilon\)，\(S \to SaSbS | SbSaS\)。

关键问题

  1. 归约和推导过程的本质区别是什么？
    • 答案：归约是自下而上的递归推理过程，将产生式的右部替换为左部；推导是自上而下的过程，将产生式的左部替换为右部。归约从字符串出发，逐步归约到非终结符；推导从起始符号出发，逐步推导出目标字符串。
  2. 如何判断一个上下文无关文法是否具有二义性？
    • 答案：若对于文法所产生的语言中的某个句子，存在两棵不同的具有边缘为该句子的推导树，或者该句子能从不同的最左（右）推导推出，则该文法具有二义性。例如，对于文法\(S \to S+S | S*S |(S)| a\)，句子\((a*a+a)\)有两棵不同的推导树，所以该文法是二义的。
  3. 设计上下文无关文法时，如何确保生成的语言符合要求？
    • 答案：首先要明确目标语言的特征，对于像\(\{0^{n}1^{n} | n \geq 0\}\)这样具有规律的语言，可通过递归的方式定义产生式，如\(S_{1} \to 0S_{1}1 | \varepsilon\)。对于复杂语言，如\(L=\{\omega | \omega\)中\(a\)的个数和\(b\)的个数相同\(\}\)，需要先考虑基础情况，再递归构造归纳情况，同时要保证新的生成式不改变语言的关键特征 。

4.1 推导树和二义性

归约与推导

该部分内容主要介绍了上下文无关文法中归约与推导的概念、过程示例，以及最左推导和最右推导的定义与示例。

  1. 归约与推导的概念：在判断字符串是否属于文法所定义的语言时，有两种方法。归约是自下而上的递归推理过程，将产生式的右部替换为左部；推导是自上而下的过程，将产生式的左部替换为右部。
  2. 归约与推导过程举例：以文法\(G_{exp}=(\{E,O\},\{(,),＋, *, v, d\},P,E)\)为例，其中\(P\)包含\(E \to EOE\)、\(E \to (E)\)等产生式。
    • 归约过程：如对字符串\(v*(v + d)\)进行归约，从\(v*(v + d)\)开始，依据产生式逐步替换，\(v*(v + d)\stackrel{(4)}{\Rightarrow} v*(v + E)\stackrel{(6)}{\Rightarrow} vO(v + E)\stackrel{(3)}{\Rightarrow} vO(E + E)\stackrel{(5)}{\Rightarrow} vO(EOE)\stackrel{(1)}{\Rightarrow} vO(E)\stackrel{(2)}{\Rightarrow} vOE\stackrel{(3)}{\Rightarrow} EOE\stackrel{(1)}{\Rightarrow} E\) ，最终归约到非终结符\(E\)。
    • 推导过程：从开始符号\(E\)推导到字符串\(v*(v + d)\) ，\(E\stackrel{(1)}{\Rightarrow} EOE\stackrel{(6)}{\Rightarrow} E*E\stackrel{(2)}{\Rightarrow} E*(E)\stackrel{(3)}{\Rightarrow} v*(E)\stackrel{(1)}{\Rightarrow} v*(EOE)\stackrel{(5)}{\Rightarrow} v*(E + E)\stackrel{(3)}{\Rightarrow} v*(v + E)\stackrel{(4)}{\Rightarrow} v*(v + d)\)。
  3. 最左推导和最右推导：
    • 最左推导：推导过程每一步总是替换最左边的非终结符，推导关系用\(\underset{lm}{\Rightarrow}\)表示，传递闭包用\(\underset{lm}{\stackrel{*}{\Rightarrow}}\)表示。如对于\(v*(v + d)\) ，最左推导为\(E\underset{lm}{\Rightarrow} EOE\underset{lm}{\Rightarrow} vOE\underset{lm}{\Rightarrow} v*E\underset{lm}{\Rightarrow} v*(E)\underset{lm}{\Rightarrow} v*(EOE)\underset{lm}{\Rightarrow} v*(vOE)\underset{lm}{\Rightarrow} v*(v + E)\underset{lm}{\Rightarrow} v*(v + d)\)。
    • 最右推导：推导过程每一步总是替换最右边的非终结符，推导关系用\(\underset{rm}{\Rightarrow}\)表示，传递闭包用\(\underset{rm}{\stackrel{*}{\Rightarrow}}\)表示。如对于\(v*(v + d)\) ，最右推导为\(E\underset{rm}{\Rightarrow} EOE\underset{rm}{\Rightarrow} EO(E)\underset{rm}{\Rightarrow} EO(EOE)\underset{rm}{\Rightarrow} EO(EOd)\underset{rm}{\Rightarrow} EO(E + d)\underset{rm}{\Rightarrow} EO(v + d)\underset{rm}{\Rightarrow} E*(v + d)\underset{rm}{\Rightarrow} v*(v + d)\) 。

推导树

该部分内容主要介绍了推导树的定义、构造方式以及在归约和推导过程中的体现。

  1. 推导树定义：推导树是用图的方法表示一个句型的推导，也叫语法树或语法分析树，有助于理解语法结构的层次。它以文法的起始符为根，枝结点标记是非终结符，叶结点标记为终结符或\(\varepsilon\) 。若枝结点有直接子孙\(x_1,x_2,\cdots,x_k\)，则文法中有生成式\(A \to x_1x_2\cdots x_k\)。
  2. 推导树举例：对于文法\(S \to S + S | S * S | (S) | a\)，句子\((a * a + a)\)可有相应推导树，这体现了推导树是对文法中特定句子形式派生过程的自然描述。同时，叶子从左向右组成的字符串称为推导树的边缘。
  3. 推导树与归约、推导的关系：
    • 归约过程与推导树：以文法\(G_{exp}\)为例，对字符串\(v*(v + d)\)的归约过程可看作自下而上构造一棵树。从字符串出发，依据产生式逐步向上归约，每一步替换对应树的构建，最终归约到起始符，构建出完整的推导树。
    • 推导过程与推导树：同样对于\(v*(v + d)\)，推导过程是自上而下构造一棵树。从起始符开始，根据产生式逐步向下推导，每次推导的结果构成树的不同层次，直至推导出目标字符串，完成推导树的构建。

归约､推导与分析树之间关系

这部分内容主要阐述了在上下文无关文法（CFG）中归约、推导与分析树之间的等价关系，并对相关定理进行了证明，具体如下：

  1. 三者的等价关系：对于上下文无关文法\(G = (N, T, P, S)\) ，以下五个命题相互等价：
    • 字符串归约：字符串\(w\in T^{*}\)可以归约（递归推理）到非终结符\(A\)。这意味着通过将产生式的右部替换为左部的方式，能从字符串\(w\)逐步得到非终结符\(A\)。
    • 推导关系1：\(A \stackrel{*}{\Rightarrow} w\)，即从非终结符\(A\)出发，经过若干次推导可以得到字符串\(w\)。推导是将产生式的左部替换为右部的过程。
    • 推导关系2：\(A \underset{lm}{\stackrel{*}{\Rightarrow}} w\)，表示从非终结符\(A\)开始，每次总是替换最左边的非终结符，经过若干次最左推导得到字符串\(w\) 。
    • 推导关系3：\(A \underset{rm}{\stackrel{*}{\Rightarrow}} w\)，是指从非终结符\(A\)开始，每次总是替换最右边的非终结符，经过若干次最右推导得到字符串\(w\)。
    • 分析树存在：存在一棵根结点为\(A\)的分析树，其边缘为\(w\)。分析树（推导树）以文法起始符为根，枝结点是非终结符，叶结点是终结符或\(\varepsilon\)，若枝结点有直接子孙\(x_1,x_2,\cdots,x_k\)，则文法中有生成式\(A \to x_1x_2\cdots x_k\) 。
  2. 定理及证明：
    • 定理内容：设2型文法\(G=(N,T,P,S)\)，存在\(S \stackrel{*}{\Rightarrow} \omega\)，当且仅当文法\(G\)中有一棵边缘为\(\omega\)的推导树。
    • 证明过程：
      • 从树到推导：假设\(\omega\)是\(B\)树边缘，对树中枝结点数目\(m\)作归纳证明。当\(m = 1\)时，分析树只有一个枝结点，必定有产生式\(B \to w\)，所以\(B \stackrel{*}{\Rightarrow} w\) 。当\(m\gt1\)时，分析树有产生式\(B \to X_1X_2\cdots X_k\) ，\(w = w_1w_2\cdots w_k\)，\(w_i\)是\(X_i\)子树的边缘，由归纳假设\(X_i \stackrel{*}{\Rightarrow} w_i\)，进而可证\(B \stackrel{*}{\Rightarrow} w\) 。
      • 从推导到树：设有\(B \stackrel{*}{\Rightarrow} \omega\) ，对推导步数作归纳。当步数为\(1\)时，一定有产生式\(B \to w\)，\(w\)可归约到\(B\) 。当步数大于\(1\)时，第一步使用产生式\(B \to X_1X_2\cdots X_k\) ，\(w = w_1w_2\cdots w_k\)，若\(X_i\)为终结符，则\(w_i = X_i\)；若\(X_i\)为非终结符，由归纳假设\(w_i\)可归约到\(X_i\)，所以\(w\)可以归约到\(B\) ，也就存在一棵边缘为\(\omega\)的\(B\)树。

二义性

这部分内容主要介绍了2型文法二义性的定义、实例、相关注意事项，具体如下：

  1. 二义性定义：2型文法是二义的，当且仅当对于句子\(\omega\in L(G)\)，存在两棵不同的具有边缘为\(\omega\)的推导树。这意味着如果一个文法是二义的，那么该文法产生的某个句子能够通过不同的最左推导或最右推导得出。推导树是以文法起始符为根，枝结点是非终结符，叶结点是终结符或\(\varepsilon\)的树状结构，其叶子从左向右组成的字符串就是边缘。
  2. 二义性实例：以书中P94例1的句子\((a*a + a)\)为例，它有两棵不同的推导树，这两种推导树分别对应了不同的运算顺序，一种是先算乘法，一种是先算加法，这清晰地展示了该文法的二义性。
  3. 二义性相关注意事项：存在这样的情况，有两个文法，其中一个有二义性，另一个没有二义性，但它们产生的语言是相同的。并且，目前不存在能普遍适用于消除二义性的算法，即对于具有二义性的文法，难以找到通用方法将其转变为无二义性的文法。

设计上下文无关文法