It is known that given a Context Free Grammar $G$, checking that it is ambiguous or not is undecidable. But, if I have a string $s \in L(G)$, does there exist an algorithm to check whether $s$ particularly can be derived unambiguously in $G$?
gnasher's comment more or less answers this. A sketch of an algorithm would be:
- enumerate all derivations of the grammar that do not generate strings longer than $s$. This can be done, because CFGs do not have deleting rules (or if yours do, they can be converted for example to Chomsky Normal Form)
- check how many of the strings generated are equal to $s$.
This takes a long time, of course. But I doubt that there is a fundamentally better way.
The CYK algorithm can be modified in a straightforward way to solve this problem. In particular, the problem is not only decidable -- there is a reasonably efficient algorithm to solve it.
The standard CYK algorithm uses dynamic programming to compute $P[i,j,X]$, a boolean that indicates whether $s[i..j]$ is a member of $L(X)$, for each pair of indices $i,j$ and each non-terminal $X$. I suggest you also compute $Q[i,j,X]$, which indicates whether $s[i..j]$ can be derived unambiguously from $X$. It is easy to adjust the recursion to compute both $P$ and $Q$ simultaneously.
This achieves a $O(n^3 \cdot |G|)$ running time, i.e., polynomial time.
You can probably do the same with Earley parsing or any method of GLR parsing.