Parsing fully context-free grammars

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

Return to the comp.compilers page.
Search the comp.compilers archives again.