2
$\begingroup$

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.

$\endgroup$
0

0

Your Answer

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