Wed, 19 Apr 1995 15:14:41 GMT

Related articles |
---|

a yacc grammar for palindromes? ted@mayfield.hp.com (1995-03-31) |

Re: a yacc grammar for palindromes? oracle@mch.sni.de (1995-04-04) |

Re: a yacc grammar for palindromes? dodd@csl.sri.com (1995-04-14) |

Re: a yacc grammar for palindromes? torbenm@diku.dk (1995-04-10) |

Re: a yacc grammar for palindromes? caibmnfx@ibmmail.com (Parag V. Tijare) (1995-04-12) |

Re: a yacc grammar for palindromes? hbaker@netcom.com (1995-04-12) |

Re: a yacc grammar for palindromes? will@ccs.neu.edu (1995-04-19) |

Newsgroups: | comp.compilers |

From: | will@ccs.neu.edu (William D Clinger) |

Keywords: | yacc, parse |

Organization: | College of CS, Northeastern University |

References: | 95-04-031 95-04-113 |

Date: | Wed, 19 Apr 1995 15:14:41 GMT |

hbaker@netcom.com (Henry Baker) writes:

*>Vaughan Pratt's 'Lingol' parsing system (quite different from his parser*

*>which was used in Macsyma) is an O(n^3) algorithm.*

In 1970, Earley's algorithm proved that all context-free languages

could be parsed in O(n^3) time:

Earley, J. An efficient context-free parsing algorithm.

CACM 13(2), 1970, pages 94--102.

I think Earley's algorithm runs in O(n^2) for unambiguous grammars,

and runs in O(n) time for LR(0) grammars. The palindrome grammar is

unambiguous, so palindromes are recognizable in quadratic time using

Earley's algorithm (if I recall correctly).

For general context-free grammars, the fastest known parsing

algorithm seems to run in O(n^a) time, where a = log_2(7) is

approximately 2.807354922057604:

Valiant, L. General context-free recognition in less than

cubic time. Journal of Computer and System Sciences 10(2),

1975, pages 308--315.

William Clinger

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.