Definition:Unique Parsability

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\LL$ be a formal language.

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


Then $\LL$ has unique parsability.


Bottom-Up Grammar

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

$\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 if and only if:

$\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$.