Parsing fully context-free grammars

"Lowell Thomas" <lowell@coasttocoastresearch.com>
17 Sep 2005 13:51:16 -0400

          From comp.compilers

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]
| List of all articles for this month |

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.