Consider the following context-free grammar:
$T \to (*) \mid (T*) \mid (*T) \mid (T*T)$
This effectively forms a notation for binary trees: A binary tree is a $*$, with optional children on either side, all surrounded by $()$. This is clearly unambiguous, because you can distinguish between the presence and absence of a tree, and you can determine where a tree begins and ends.
Now consider the same grammar, except that it does not distinguish between opening and closing parenthesis:
$T \to aba \mid aTba \mid abTa \mid aTbTa$
Here, we have replaced both $($ and $)$ with $a$ (and $*$ with $b$).
After trying several examples, I believe that this grammar is unambiguous. For example, the string $aaabababaabaababaa$ parses as $(a(a(aba)b(aba)a)b(a(aba)ba)a)$.
However, I don't see an efficient way to parse it. The general idea I had was to go as follows:
- The string must start and end with $a$.
- If the second character from the start is $b$, recursively parse the part after it, all the way to the second character from the end.
- If the second character from the end is $b$, recursively parse the part before it, all the way to the second character from the start.
- If the second character from both the start and end is $b$, we have a malformed expression.
- If both characters from the start and end are $a$, then... what?
Here it seems that we would have to create a choice point and use a backtracking method to find it. However, this method would have exponential runtime for many pathological inputs, such as $aababababababababababaa$.
Is this grammar unambiguous? If so, is there a way to parse this grammar that avoids pathological exponential runtime for most inputs?