Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending symbols can alter the parse forest of $\alpha$? In other words, we want a function $F: (\mathbb{G} \times \Sigma^\ast) \rightarrow \mathbb{B}$ that returns whether $\alpha$'s parse forest according to $G$ is unique over $\beta\alpha\gamma$, for all $\beta, \gamma: \Sigma^\ast$.

Specifically, let $T_\alpha$ denote the set of all parse trees that are generated by the string $\alpha$ using $G$, and consider $\mathbf{T}_{\alpha}$, the union of all parse trees and their subtrees that (1) can be generated by $\beta\alpha\gamma$ using $G$ for arbitrary $\beta, \gamma \in \Sigma^\ast$, and (2) have a leaf in $\alpha$. The parse forest $T_\alpha$ is unique iff $\forall t \in \mathbf{T}_{\alpha}\exists t' \in T_\alpha$, such that $t$ is either a subtree of $t'$, or $t'$ is a proper subtree of $t$.

Some context: effectively, we want the necessary and sufficient conditions for when a substring can be replaced by a single nonterminal (or set of nonterminals, in the case of ambiguity) without affecting parse trees of surrounding or adjacent strings.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.