On Tue, Jun 18, 2013 at 5:07 PM, Toby Goodwin <t...@paccrat.org> wrote:
> S -> a S a | a S b | b S a | b S b |a > > "This CFG describes a language consisting of odd-length strings of 'a's > and 'b's, in which the middle character is always an 'a'. The problem here > is that in TDPL [i.e. PEGs] there is no way to "find the middle" of a > homogeneous string containing no distinguishable syntactic "signposts", > but the middle character must be found in this case in order to reject > strings that have a 'b' at that position." > Toby, I think that a PEG grammar can tackle that language, but Could the parsing take exponential time? A PEG grammar for the same language could be: S -> E $ E -> (a/b) E (a/b) E -> a Mmmm. That actually seems to produce correct parsing with O(N) space and O(N^2) time... Regards, -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
