Appetizer #2 Before Parsing: CFG Disambiguation (with intro to Parse Tree & Ambiguity)

June 22, 2025 8 分钟阅读

Parse TreePermalink

DefinitionPermalink

Derivation Tree is a better name

Parse Tree 的另一个名字 – Derivation Tree – 明显是一个更好的名字，因为这样一来我们就很能自然地把 derivation 和 tree 联系起来。

我们在 parsing 的时候，parse tree 一般都是 $S \overset{*}{\Rightarrow} w$ where $w$ is a sentence 的情形；但更 general 的 $A \overset{*}{\Rightarrow} w^{'}$ where $w^{'}$ is a sentential form 的情况，我们构建的 tree 也算是 parse tree。换句话说，不要把 parse tree 限定成 $S \overset{*}{\Rightarrow} w$ 这么一种形式。

Characteristics: For CFG $G = (V, T, P, S)$ , a parse tree (or derivation tree) of $G$ is a tree satisfying the following conditions:

Every interior/internal node is labeled by a non-terminal $A \in V$
Every leaf node is labeled by $x$ which is either a terminal, a terminal, or $ε$ , i.e. $x \in V \cup T \cup {ε}$
- A leaf labeled by $ε$ must be the only child of its parent.
If an internal node is labeled by $A$ with children labeled by (from left to right) $X_{1}, X_{2}, \dots, X_{n}$ ，then $A \to X_{1} X_{2} \dots X_{n}$ must be a production $\in P$ .
- Or it represents the application of production $A \to X_{1} X_{2} \dots X_{n}$ in the corresponding derivation.

Definition: Yield (产物) or frontier of a parse tree is the concatenated string of leaf labels (left–right).

Derivation $⟺$ Parse Tree $∣$ Sentential Form $⟺$ YieldPermalink

Theorem: CFG $G$ has a derivation $A \overset{*}{\Rightarrow} α$ $⟺$ $\exists$ a parse tree with root labeled $A$ and a yield of $α$ . $◼$

Proof: ( $\Rightarrow$ ) Proof by induction on the number of steps $k$ in the derivation $A \overset{k}{\Rightarrow} α$ .

Base Case: $k = 1$ . If $A \to α_{1} α_{2} \dots α_{n}$ , then $\exists$ a parse tree with height 1:

Induction Step: suppose the assumption holds for all $\leq k$ -step derivation $A \overset{\leq k}{\Rightarrow} β$ .

For $k + 1$ -step derivation $A \overset{k}{\Rightarrow} β \Rightarrow α$ , there $\exists$ a parse tree with height $k$ , root labeled $A$ , and a yield of $β$ .

There must be a non-terminal $X$ in $β$ and a production $X \to γ$ , who together derive $β \Rightarrow α$ . We can add $X \to γ$ to the above parse tree. The new tree is valid.

( $\Leftarrow$ ) Proof by induction on the number of internal nodes $k$ of the parse tree.

Base Case: If the parse tree has only $1$ internal node, then it must be the root, and the height of the parse tree must be $1$ . This means $A \to α_{1} α_{2} \dots α_{n}$ must be a production, and the derivation holds.

Induction Step: suppose the assumption holds for all parse tree with $\leq k$ internal nodes.

Now if we have a parse tree with $k + 1$ internal nodes 的 parse tree like this:

It’s certain that the parse tree for $A \Rightarrow X_{1} X_{2} \dots X_{n}$ has $\leq k$ internal nodes
Similarly the parse tree for $\forall X_{i} \Rightarrow α_{i}$ has $\leq k$ internal nodes

Therefore there exist derivation $A \overset{*}{\Rightarrow} X_{1} X_{2} \dots X_{n}$ and $\forall i, X_{i} \overset{*}{\Rightarrow} α_{i}$ , and the combined derivation $A \overset{*}{\Rightarrow} α_{1} α_{2} \dots α_{n}$ holds. $◼$

这个定理再结合 “任何 derivation 都有等价的 leftmost derivation 和 rightmost derivation”，我们可以认为意下 5 个命题等价：

$w \in L (A)$ ，或者说 $w$ 是一个 sentential form (derived from $A$ )
$\exists$ parse tree 以 $A$ 为 root 且 yield 为 $w$
$A \overset{*}{\Rightarrow} w$
$A \overset{*}{\underset{lm}{\Rightarrow}} w$
$A \overset{*}{\underset{rm}{\Rightarrow}} w$

AmbiguityPermalink

DefinitionPermalink

Definition: A grammar $G = (V, T, P, S)$ is said to be ambiguous (歧义的) if $\exists w \in L (G)$ for which derivation $S \overset{*}{\Rightarrow} w$ two different parse trees.

“判定任意给定的 CFG $G$ 是否歧义” 是一个不可判定问题。

Definition: Given a language $L$ , if every CFG of $L$ is ambiguous, then $L$ is inherently ambiguous (固有歧义)

Example: $L = {a^{i} b^{j} c^{k} ∣ i = j or j = k}$

$L$ 中任何形为 $a^{n} b^{n} c^{n}$ 的串，总会有两棵 parse tree，所以 $L$ 是固有歧义的

Sentential Form 与 Derivation 与 Parse Tree 的数量关系Permalink

我们先区分一下 derivation:

我们把 $S \overset{*}{\Rightarrow} w$ 这样省略了中间步骤的 derivation 称为 abstract derivation，用 $D (S, w)$ 表示
我们把 $S \Rightarrow \dots \Rightarrow w$ 这样列出了中间每一步的 derivation 称为 concrete derivation，用 $d_{i} (S, w)$
abstract derivation 的本质是 a set of concrete derivations, i.e. $D (S, w) = {d_{1} (S, w), d_{2} (S, w), \dots, d_{n} (S, w)}$

同时，考虑到：

An abstract derivation cannot reveal the order of production application, just like a parse tree cannot reveal the order of its node expansion/creation.
A concrete derivation shows a fixed order of production application, while a topological sort of a parse tree is also a fix order of its node expansion/creation.

我们也区分一下 “parse tree” 和 “parse tree 上的 topological sort”:

我们用 $T (S, w)$ 表示一棵具体的 parse tree
我们用 $t_{i} (S, w)$ 表示 $T (S, w)$ 上的一个 topological sort

考虑 Sentential Form 与 Derivation 的关系时不需要考虑 grammar $G$ 的 ambiguity，因为一个 sentential form $w$ 一定只可能有一个 abstract derivation，且一定可以有多个 concrete derivation，无论 $G$ 是否 ambiguous:

考虑 Derivation 与 Parse Tree 的数量关系时需要考量 grammar $G$ 的 ambiguity.

When $G$ is unambiguous:

flowchart LR
    W@{ shape: braces, label: $$w$$ }
    W --- DA@{ shape: tag-rect, label: "$$𝔇(S,w)$$" }
    DA --- DC1@{ shape: div-rect, label: "$$𝔡_1(S,w)$$" }
    DA --- DC2@{ shape: div-rect, label: "$$𝔡_2(S,w)$$" }
    DA --- DC3@{ shape: div-rect, label: "$$\\cdots$$" }
    DA --- DC4@{ shape: div-rect, label: "$$𝔡_n(S,w)$$" }

    DC1 --- T1[/"$$𝔱_1(S,w)$$"\]
    DC2 --- T2[/"$$𝔱_2(S,w)$$"\]
    DC3 --- T3[/"$$\\cdots$$"\]
    DC4 --- T4[/"$$𝔱_n(S,w)$$"\]

    T1 --- T@{ shape: tri, label: "$$𝔗(S,w)$$" }
    T2 --- T
    T3 --- T
    T4 --- T

When $G$ is ambiguous (suppose there are 2 parse trees for the abstract derivation below):

flowchart LR
    W@{ shape: braces, label: $$w$$ }
    W --- DA@{ shape: tag-rect, label: "$$𝔇(S,w)$$" }
    DA --- DC1@{ shape: div-rect, label: "$$𝔡_1(S,w)$$" }
    DA --- DC2@{ shape: div-rect, label: "$$\\cdots$$" }
    DA --- DC3@{ shape: div-rect, label: "$$𝔡_k(S,w)$$" }
    DA --- DC4@{ shape: div-rect, label: "$$𝔡_{k+1}(S,w)$$" }
    DA --- DC5@{ shape: div-rect, label: "$$\\cdots$$" }
    DA --- DC6@{ shape: div-rect, label: "$$𝔡_n(S,w)$$" }

    DC1 --- T1[/"$$𝔱_1(S,w)$$"\]
    DC2 --- T2[/"$$\\cdots$$"\]
    DC3 --- T3[/"$$𝔱_k(S,w)$$"\]
    DC4 --- T4[/"$$𝔱_{k+1}(S,w)$$"\]
    DC5 --- T5[/"$$\\cdots$$"\]
    DC6 --- T6[/"$$𝔱_n(S,w)$$"\]

    T1 --- TT1@{ shape: tri, label: "$$𝔗_1(S,w)$$" }
    T2 --- TT1
    T3 --- TT1
    T4 --- TT2@{ shape: tri, label: "$$𝔗_2(S,w)$$" }
    T5 --- TT2
    T6 --- TT2

Ambiguous Grammar Example #1: arithmetic operator precedencePermalink

假设我们有这么个语法：

\begin{aligned} E & \to E + E ∣ E * E ∣ I \\ I & \to a \end{aligned}

这个语法对句型 $a + a * a$ 就是歧义的（体现为运算优先级的不同）

%%{init: { 'fontFamily': 'monospace' } }%%
flowchart TD
    subgraph #2
        E'[$$E$$]
        E' --- E1'[$$E$$]
        E' --- Times'@{ shape: dbl-circ, label: $$\ast$$ }
        E' --- E2'[$$E$$]
    
        E1' --- E3'[$$E$$] --- I1'[$$I$$] --- a1'@{ shape: dbl-circ, label: $$a$$ }
        E1' --- Plus'@{ shape: dbl-circ, label: $$+$$ }
        E1' --- E4'[$$E$$] --- I2'[$$I$$] --- a2'@{ shape: dbl-circ, label: $$a$$ }
    
        E2' --- I3'[$$I$$] --- a3'@{ shape: dbl-circ, label: $$a$$ }
    end

    subgraph #1
        E[$$E$$]
        E --- E1[$$E$$]
        E --- Plus@{ shape: dbl-circ, label: $$+$$ }
        E --- E2[$$E$$]
    
        E1 --- I1[$$I$$] --- a1@{ shape: dbl-circ, label: $$a$$ }
    
        E2 --- E3[$$E$$] --- I2[$$I$$] --- a2@{ shape: dbl-circ, label: $$a$$ }
        E2 --- Times@{ shape: dbl-circ, label: $$\ast$$ }
        E2 --- E4[$$E$$] --- I3[$$I$$] --- a3@{ shape: dbl-circ, label: $$a$$ }
    end

Ambiguous Grammar Example #2: dangling ELSE problemPermalink

假设我们有这么个语法：

\begin{aligned} ⟨ s t m t ⟩ \to & if ⟨ e x p r ⟩ then ⟨ s t m t ⟩ \\ ∣ & if ⟨ e x p r ⟩ then ⟨ s t m t ⟩ else ⟨ s t m t ⟩ \\ ∣ & ⟨ o t h e r_s t m t ⟩ \end{aligned}

那么句子 $w = if E_{1} then if E_{2} then S_{1} else S_{2}$ 就是歧义的。

用 python 更好理解一些：

# Block #1
if E1:
    if E2:
        S1
    else:
        S2

# Block #2
if E1:
    if E2:
        S1
else:
    S2

换言之就是以下二式的区别：

\begin{aligned} w & = if E_{1} then \underset{⟨ s t m t ⟩}{\underset{⏟}{if E_{2} then S_{1} else S_{2}}} \\ w & = if E_{1} then \underset{⟨ s t m t ⟩}{\underset{⏟}{if E_{2} then S_{1}}} else \underset{⟨ s t m t ⟩}{\underset{⏟}{S_{2}}} \end{aligned}

你写成 python 有 indent 保证，但是输入给 parser 的时候往往是 $if E_{1} then if E_{2} then \dots$ 这种 flattened 的形式。

DisambiguationPermalink

Method #1: Rewrite the GrammarPermalink

有些文法的歧义性，可以通过重新设计文法来消除。

比如 Example #1 的文法可以修改为：

\begin{aligned} E & \to E + T ∣ T ∣ I \\ T & \to T * T ∣ I \\ I & \to a \end{aligned}

flowchart TD
    E[$$E$$]
    E --- E1[$$E$$]
    E --- Plus@{ shape: dbl-circ, label: $$+$$ }
    E --- T[$$T$$]

    E1 --- I1[$$I$$] --- a1@{ shape: dbl-circ, label: $$a$$ }

    T --- T1[$$T$$] --- I2[$$I$$] --- a2@{ shape: dbl-circ, label: $$a$$ }
    T --- Times@{ shape: dbl-circ, label: $$\ast$$ }
    T --- T2[$$T$$] --- I3[$$I$$] --- a3@{ shape: dbl-circ, label: $$a$$ }

比如 Example #2 的文法可以修改为：

\begin{aligned} ⟨ s t m t ⟩ \to & ⟨ m a t c h e d_s t m t ⟩ \\ ∣ & ⟨ u n m a t c h e d_s t m t ⟩ \\ ⟨ m a t c h e d_s t m t ⟩ \to & if ⟨ e x p r ⟩ then ⟨ m a t c h e d_s t m t ⟩ else ⟨ m a t c h e d_s t m t ⟩ \\ ∣ & ⟨ o t h e r_s t m t ⟩ \\ ⟨ u n m a t c h e d_s t m t ⟩ \to & if ⟨ e x p r ⟩ then ⟨ s t m t ⟩ \\ ∣ & if ⟨ e x p r ⟩ then ⟨ m a t c h e d_s t m t ⟩ else ⟨ u n m a t c h e d_s t m t ⟩ \end{aligned}

Method #2: Syntactic Predicates / Alternative PrecedencePermalink

指像 ANTLR 之类的有 special instructions 或者 rules 可以指定优先匹配哪个 alternative production.

比如 ANTLR 有 “First Written, Fist Match” 原则 (i.e. greedy choice)，比如：

expr: expr '+' expr   # Add
    | expr '*' expr   # Mul
    | INT             # Int
    ;

INT: [0-9]+;

当输入为 INT + INT * INT 时，因为 expr '+' expr 写在 expr '*' expr 前面，所以 expr '+' expr 的优先级更高，于是会优先匹配 INT + INT.

X Facebook LinkedIn Bluesky

Appetizer #2 Before Parsing: CFG Disambiguation (with intro to Parse Tree & Ambiguity)

Parse TreePermalink

DefinitionPermalink

Derivation $⟺$ Parse Tree $∣$ Sentential Form $⟺$ YieldPermalink

AmbiguityPermalink

DefinitionPermalink

Sentential Form 与 Derivation 与 Parse Tree 的数量关系Permalink

Ambiguous Grammar Example #1: arithmetic operator precedencePermalink

Ambiguous Grammar Example #2: dangling ELSE problemPermalink

DisambiguationPermalink

Method #1: Rewrite the GrammarPermalink

Method #2: Syntactic Predicates / Alternative PrecedencePermalink

分享

留下评论

猜您还喜欢

LR Parsing #1: Intuition

LL(0) vs. LL(1) Grammars: From Single-String to Flexible Repetition

Lark’s implementation of computing FIRST and FOLLOW sets

LL(1) Parsing

Parse TreePermalink

DefinitionPermalink

Derivation ⟺ Parse Tree ∣ Sentential Form ⟺ YieldPermalink

AmbiguityPermalink

DefinitionPermalink

Sentential Form 与 Derivation 与 Parse Tree 的数量关系Permalink

Ambiguous Grammar Example #1: arithmetic operator precedencePermalink

Ambiguous Grammar Example #2: dangling ELSE problemPermalink

DisambiguationPermalink

Method #1: Rewrite the GrammarPermalink

Method #2: Syntactic Predicates / Alternative PrecedencePermalink

分享

留下评论

猜您还喜欢

LR Parsing #1: Intuition

LL(0) vs. LL(1) Grammars: From Single-String to Flexible Repetition

Lark’s implementation of computing FIRST and FOLLOW sets

LL(1) Parsing

Derivation $⟺$ Parse Tree $∣$ Sentential Form $⟺$ YieldPermalink