RE: Other General Parsing Algos like Earley's

Quinn Tyler Jackson <>
9 May 2004 22:25:02 -0400

          From comp.compilers

Related articles
Other General Parsing Algos like Earley's (2004-05-08)
RE: Other General Parsing Algos like Earley's (Quinn Tyler Jackson) (2004-05-09)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 9 May 2004 22:25:02 -0400
Organization: Compilers Central
References: 04-05-027
Keywords: parse
Posted-Date: 09 May 2004 22:25:02 EDT

> 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.


Post a followup to this message

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