Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|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
2  
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 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
    
Why do you want the algorithm to recognize only unambiguous grammars? What is wrong with the CYK algorithm? It's in $O(n^3)$ (well, $O(n^{2.38})$) but I'm sure it's not your point) Do you mean it's exponential in the size of the grammar and not the length of the words? –  jmad Mar 8 '12 at 22:26
show 4 more comments

1 Answer

up vote 10 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 $\cal{O}(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|improve this answer
    
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
add comment

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.