Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
1  
I am almost afraid to ask: what is wrong with LL(1) by recursive descent? – Raphael Mar 7 '12 at 17:16
3  
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. – Alex ten Brink Mar 7 '12 at 18:17
    
$O(N^2)$ is not exponential, it is quadratic. $O(2^N)$ is exponential. – Victor Stafusa Mar 7 '12 at 19:23
1  
@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. – Alex ten Brink Mar 7 '12 at 19:35
1  
@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. – Alex ten Brink Mar 8 '12 at 22:31
up vote 13 down vote accepted

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.
share|cite|improve this answer
1  
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. – Alex ten Brink Mar 8 '12 at 23:54
1  
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. – Alex ten Brink Mar 10 '12 at 19:12
    
@AlextenBrink Good catch. I edited to account for this. – Raphael Mar 11 '12 at 12:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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