2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @rici Err, other way around, actually. $\endgroup$ – Noncontextual Spelling Dec 31 '17 at 22:47
3
$\begingroup$

The grammar is ambiguous: (I used | for a and * for b because I find it easier to read.)

||*|*||*|*||
((*(*))*(*))
((*)*((*)*))

However, you can use an Earley grammar to find all possible parses in worst-case cubic time. (As long as you are satisfied with a graph representation of "all possible parses" since the maximum number of parses of a string of a given size is exponential.)


I found this example by using a bison GLR grammar and iterating over inputs until I found one which produced an ambiguity. Out of laziness, I produced the list of inputs by generating all strings consisting of $n$ | and $n$ *| where the first element is |. Most of these inputs are syntax errors, but for small $n$ it doesn't matter.

Here's a simpler approach, using Python to generate valid inputs:

def gen(s, n):
  """Generate left-most derivations of 's' with maximum length 'n'"""
  if n > 0:
    i = s.find('T')
    if i == -1:
      yield s
    else:
      yield from gen(s[:i]+'|*|'+s[i+1:], n)
      yield from gen(s[:i]+'|T*|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|*T|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|T*T|'+s[i+1:], n-2)

If this function generates the same string twice, that string is ambiguous since it has two left-most derivations.

$\endgroup$
  • $\begingroup$ I was considering using | and *, but | doesn't work well for the grammar specification since it's already part of the notation. $\endgroup$ – Noncontextual Spelling Jan 1 '18 at 0:27
  • $\begingroup$ Fair enough. Is there anything more you need to consider the question answered? $\endgroup$ – rici Jan 1 '18 at 1:34
  • $\begingroup$ Would the CFG be ambiguous if I changed the production $a \to aTbTa$ to $a \to aTcbcTa$? $\endgroup$ – Noncontextual Spelling Jan 1 '18 at 6:39
  • $\begingroup$ @noncontextual: that's a different question :-) $\endgroup$ – rici Jan 1 '18 at 8:22
  • $\begingroup$ However, it is still ambiguous. Here I use + to represent cbc (since cbc could be a single symbol without changing anything); the shortest ambiguous string is |||*|*||*|+|*||||*|+|*||*|*||| $\endgroup$ – rici Jan 1 '18 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.