23
$\begingroup$

EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:

$S \rightarrow a a$

$S \rightarrow b b$

$S \rightarrow a S a$

$S \rightarrow b S b$

EPAL is the 'bane' of many parsing algorithms: I have yet to encounter any parsing algorithm for unambiguous CFGs that can parse any grammar describing the language. It is often used to show that there are unambiguous CFGs that cannot be parsed by a particular parser. This inspired my question:

Is there some parsing algorithm accepting only unambiguous CFGs that works on EPAL?

Of course, one can design an ad-hoc two-pass parser for the grammar that parses the language in linear time. I'm interested in parsing methods that have not been designed specifically with EPAL in mind.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ I am almost afraid to ask: what is wrong with LL(1) by recursive descent? $\endgroup$
    – Raphael ♦
    Mar 7, 2012 at 17:16
  • 3
    $\begingroup$ Non-backtracking recursive descent can't handle EPAL as the language is not LL(k) for any k. Recursive descent with backtracking can handle the grammar in $O(n^2)$ time, but that is a general algorithm with exponential worst-case behavior, which is not what I'm looking for. $\endgroup$
    – Alex ten Brink
    Mar 7, 2012 at 18:17
  • $\begingroup$ $O(N^2)$ is not exponential, it is quadratic. $O(2^N)$ is exponential. $\endgroup$
    – Victor Stafusa - BozoNaCadeia
    Mar 7, 2012 at 19:23
  • 1
    $\begingroup$ @Victor: backtracking has exponential behavior on some grammars, just not on this particular grammar. Still, it being an algorithm that works on ambiguous grammars discounts it as an answer to my question. $\endgroup$
    – Alex ten Brink
    Mar 7, 2012 at 19:35
  • 1
    $\begingroup$ @jmad: my intent is not to parse the language (you can do that trivially in linear time), but rather to satisfy my curiosity: I've seen it being used as an example of a language that cannot be parsed by a parsing method so many times that I'm curious if there is some parsing method that does recognize it. $\endgroup$
    – Alex ten Brink
    Mar 8, 2012 at 22:31

1 Answer 1

Reset to default
14
$\begingroup$

Consider the following sketch of a parsing strategy at your own risk.

Instead of reading the input only from one end, we read from both sides and look for matching rules. We can do this in recursive descent style; in a call to $A()$, find prefix $w$ and suffix $v$ to the input such that there is a rule $A \to wBv$, descend to $B()$ on the remaining word. If there is no matching rule, reject the word.

This algorithm parses all linear, unambiguous grammars. It takes linear time if all rule pairs $A \to wBv$ and $A \to w'B'v'$ have $w \not\equiv_p w'$ or $v \not\equiv_s v'$¹. This includes EPAL. Otherwise we need to look ahead so we might take $\Theta(n^2)$ time.

The idea does not work for non-linear grammars at all. Linear but ambiguous grammars can in general not be parsed without backtracking (for negative inputs at least).

  1. $w \not\equiv_p v$ means here that $w \not\sqsubseteq v$ and $v \not\sqsubseteq w$, i.e. neither word is a prefix of the other. $\not\equiv_s$ is similar for suffixes.
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Excellent! Exactly what I was looking for. It's great that a language that is not $NLR(k)$ for any $k$ is parseable by such a simple algorithm. $\endgroup$
    – Alex ten Brink
    Mar 8, 2012 at 23:54
  • 1
    $\begingroup$ After giving this some more thought, I discovered a minor error in your description: the linear grammar $S \rightarrow a A b | a B b, A \rightarrow a, B \rightarrow b$ is unambiguous, but there is no such unique prefix as you describe it. There still is a unique prefix, but you may have to look inside the nonterminal to get it, and your running time becomes $O(n^2)$. Your algorithm does work on $EPAL$ though. $\endgroup$
    – Alex ten Brink
    Mar 10, 2012 at 19:12
  • $\begingroup$ @AlextenBrink Good catch. I edited to account for this. $\endgroup$
    – Raphael ♦
    Mar 11, 2012 at 12:47

Your Answer

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

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