形式语言与自动机理论-06-上下文无关语言

上下文无关文法与上下文无关语言

定义上下文无关文法(Context-free Grammar, CFG)为四元组

\[ G = (V, \Sigma, P, S) \]

其中

  1. 有限集合 \(V\) 中的元素为非终结符号

  2. 有限集合 \(\Sigma\) 中的元素为终结符号,其作用与前文中的 \(\Sigma\) 相同,即给定上下文无关文法定义了语言 \(L \subseteq \Sigma^*\)

    不失一般性地假设 \(\Sigma\)\(V\) 是不交的。

  3. \(P \subseteq V \times (V \cup \Sigma)^*\) 为重写规则集合。称二元组的第一个元素为左手,第二个元素为右手,约定记 \((N, w) \in P\)\(N \to w\),记 \((N, w_1), \dots, (N, w_n)\)

    \[ \begin{array}{rcl} N & \to & w_1 \\ & | & w_2 \\ & & \dots \\ & | & w_n \end{array} \]

    理论研究中,通常以一个大写英文字母表示 \(V\) 中元素,以一个小写英文字母表示 \(\Sigma\) 中元素。然而实际使用中,为了直接表示终端节点的意义,也有使用 \(<>\) 包围多字符字符串表示 \(V\) 中元素的做法。此时若用 \(::=\) 分隔 \(P\) 中元素的左右手,则称这样的形式为 Backus-Naur formalism (BNF)。仅在讨论一些实际例子的时候我们才会使用这样的形式。

  4. \(S \in V\) 为起始符号。

于是称集合 \((V \cup \Sigma)^*\) 中的字符串为句型(sentential form)。

若有 \(w_1 = uNv\), \((N \to w) \in P\), \(w, u, v \in (V \cup \Sigma)^*\),则有二元关系 \(w_1 \Rightarrow uwv =: w_2\)。即,若 \(w_2\) 为根据某条重写规则 \(N \to w\)\(w_1\) 中任何一个 \(N\) 替换为 \(w\),则称 \(w_1\) 一步导出 \(w_2\),或 \(w_2\) 可由 \(w_1\) 一步导出。

若有 \(u = v\) 或存在 \(w_1, w_2, \dots, w_k, k \ge 0\) 使得有推导

\[u \Rightarrow w_1 \Rightarrow w_2 \Rightarrow \dots \Rightarrow w_k \Rightarrow v\]

则有二元关系 \(u \Rightarrow^* v\),称 $u 可导出 \(v\)\(v\) 可由 \(u\) 导出。即 \(\Rightarrow^*\)\(\Rightarrow\) 的自反传递封闭。

于是由文法 \(G\) 定义的语言为

\[ L(G) := \{w\in\Sigma^* | S \Rightarrow^* w\} \]

即所有可以由起始符号经由任意步重写得到的仅包含终结符号的字符串集合。称由上下文无关文法定义的语言为上下文无关语言(Context-free Languages, CFL)

考虑文法 \(G = (\{S\}, \{0, 1\}, P, S)\),其中

\[ S \to 0S1 | \varepsilon \]

于是有推导

\[ S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow \dots \Rightarrow 0^iS1^1 \Rightarrow 0^i1^i \]

因此 \(L(G) = \{0^i1^i | i \ge 0\}\)

若给定上下文无关文法中的所有重写规则皆为如下形式:

\[ \begin{array}{rcl} B & \to & bC \\ & | & b \\ & | & \varepsilon \end{array} \]

\(P \subseteq V \times (\Sigma^*V?)\),则称这样的文法为正则文法。

不难看出所有正则文法定义的都是正则语言,并且所有正则语言都可以由某些正则文法定义。

因此我们看出,所有正则语言都是上下文无关的,而上例表明,存在不正则的上下文无关语言。

歧义

若一个语言中存在有多种推导的终止字符串,则称该语言是有歧义的。

考虑文法

1
2
3
4
<expr> ::= <expr> "+" <expr>
| <expr> "×" <expr>
| "(" <expr> ")"
| "a"

其中起始符号为 <expr>。该文法定义只由标识符 \(a\) 与中缀乘法,加法运算符组成的代数表达式语言。

于是字符串 a + a × a 可由两种方法推导出,分别以树的方式展示如下:

"<expr>":
  - "<expr>":
    - "a"
  - "+"
  - "<expr>":
    - "a"
    - "×"
    - "a"
"<expr>":
  - "<expr>":
    - "a"
    - "+"
    - "a"
  - "×"
  - "<expr>":
    - "a"

歧义问题会导致解析含有中缀二元运算符的表达式时结合顺序的优先度无法确定。如上例中我们按照约定俗成希望 × 的结合性优先于 +,而若根据文法的定义,解析器完全有理由选择另外的推导路径从而得出相反的结合优先度。因此我们通常认为,一个设计良好的文法应该是没有歧义的。

对于该例来说,可以有如下临时解决方案:定义文法

1
2
3
4
5
6
<expr> ::= <expr> "+" <term>
| <term>
<term> ::= <term> "×" <factor>
| <factor>
<factor> ::= "(" <expr> ")"
| "a"

同样地,起始符号为 <expr>

于是仅存在一种推导可以得到前例中的字符串 a + a × a

"<expr>":
  - "<expr>":
    - "<term>":
      - "<factor>":
        - "a"
  - "+"
  - "<term>":
    - "<term>":
      - "<factor>":
        - "a"
    - "×"
    - "<factor>":
      - "a"

若我们企图寻找使得 + 的结合性更优先的推导,将会不可避免地遇到如下情况:

"<expr>":
  - "<term>":
    - "<term>":
      - "不可能由 <term> 推导出 a+a"
    - "×"
    - "<factor>":
      - "a"