Definition:Unique Parsability
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$.