17 Sep 2005 13:51:16 -0400

Related articles |
---|

Parsing fully context-free grammars lowell@coasttocoastresearch.com (Lowell Thomas) (2005-09-17) |

Re: Parsing fully context-free grammars haberg@math.su.se (2005-09-18) |

Re: Parsing fully context-free grammars lowell@coasttocoastresearch.com (Lowell Thomas) (2005-09-22) |

Re: Parsing fully context-free grammars haberg@math.su.se (2005-09-23) |

Re: Parsing fully context-free grammars paul@parsetec.com (Paul Mann) (2005-10-02) |

Re: Parsing fully context-free grammars haberg@math.su.se (2005-10-02) |

Re: Parsing fully context-free grammars drikosv@otenet.gr (Evangelos Drikos) (2005-10-03) |

[4 later articles] |

From: | "Lowell Thomas" <lowell@coasttocoastresearch.com> |

Newsgroups: | comp.compilers |

Date: | 17 Sep 2005 13:51:16 -0400 |

Organization: | Compilers Central |

Keywords: | parse, question |

Hi All,

A few months ago I completed a generator for recursive-decent parsers

from ABNF-defined grammars (APG - an ABNF Parser Generator). It was

done in an ad hoc way with no concern at all for reinventing the

wheel. I'm now backtracking a little and trying to find out which

wheel it is that I might have reinvented. The only other fully

context-free algorithms that I've been able to find so far are the

CYK, Earley and GLR algorithms. Are there any recursive-decent or

otherwise algorithms for fully context-free grammars that I should

know about?

Also, APG always disambiguates to a single parse tree. However,

looking at the "dangling else", I've found that is easy to get either

translation from the single parse tree. That is,

if(expr) then {if(expr) then {stmt} else {stmt}}

or

if(expr) then {if(expr) then {stmt}} else {stmt}.

It seems to me that this could be generalized to say, in effect, that

any tree from the forest can be emulated by any other. Does anyone

know of a contradiction to this?

A more complete examination of this problem and others with working

examples is available from my web site (www.coasttocoastresearch.com)

Comments and discussion would be welcome.

Lowell Thomas

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.