RE: Other General Parsing Algos like Earley's

> Hi,Can somebody point out uptodate survey of general CFG parsing
> algorithms? Is Earley's algorithm the only general one that parses all
> CFGs? If possible can anyone refer to online material? Thanks in
> advance.
> [Look for Tomita. -John]


When you is it "the only general [algorithm] that parses all CFGs" are you
precluding type 1 and type 0 parsers? If not, then I would think that
something that can parse input based upon a van Wijngaarden grammar would be
able to parse all CFGs as well, since vW grammars are TP. Also, the
adaptive(k) algorithm is TP, and although it theoretically can parse more
than just CFGs, by a similar argument, it would also parse all CFGs.
However, at least in the case of adaptive(k) (and very likely also in the
case of a vW-grammar based parser), I wouldn't claim that it's possible to
automatically detect whether an arbitrary $-grammar (or vW-grammar) parses
"only all CFGs and definitely no CSGs" -- which may not be sufficient to
answer your question.


--
Quinn

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