# Definition:Unique Parsability

Jump to navigation
Jump to search

## Definition

Let $\mathcal L$ be a formal language.

Let every WFF of $\mathcal L$ result from a unique rule of formation.

Then $\mathcal L$ has **unique parsability**.

### Bottom-Up Grammar

For a bottom-up grammar, a WFF $\phi$ results from a unique rule of formation iff:

- $\phi$ results from applying the rule of formation $\mathbf R$ to WFFs $\phi_1, \ldots \phi_n$
- $\phi$ results from applying the rule of formation $\mathbf R'$ WFFs $\psi_1, \ldots \psi_m$

imply that $\mathbf R = \mathbf R'$, $m = n$, and for $i = 1, \ldots, n$, $\phi_i = \psi_i$.

### Top-Down Grammar

For a top-down grammar, a WFF $\phi$ results from a unique rule of formation iff:

- $\phi$ results from applying the rule of formation $\mathbf R$, substituting the WFFs $\phi_1, \ldots, \phi_n$ for the metasymbols of $\mathbf R$
- $\phi$ results from applying the rule of formation $\mathbf R'$, substituting the WFFs $\psi_1, \ldots, \psi_n$ for the metasymbols of $\mathbf R'$

imply that $\mathbf R = \mathbf R'$, $m = n$, and for $i = 1, \ldots, n$, $\phi_i = \psi_i$.