[Solved]: Is there any nongeneral CFG parsing algorithm that recognises EPAL?

Problem Detail: 

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.

Asked By : Alex ten Brink

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/102

 Ask a Question

 Download Related Notes/Documents