EPAL, the language of even palindromes, is defined as the language generated by

Question

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

S?aa

S?bb

S?aSa

S?bSb

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.

Explanation / Answer

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?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?wBv and A?w?B?v? have w??pw? or v??sv?

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.