On Tue, Oct 14, 2014 at 2:11 PM, Geoffrey Irving <[email protected]> wrote:
> What is the best algorithm for parsing into a memoized parse forest > given an ambiguous grammar? Is Early still the state of the art? > Geoffrey: That's a little like asking what the best religion is. If the grammar is truly ambiguous, then I'd say GLR, but it depends on your application, so see below. If the grammar is ambiguous in a way that can be resolved by making preferences or priorities explicit, then I'd say PEG parsers, and more generally, packrat parsers. BUT What you want for something like an IDE is different from a lot of other applications. An IDE has to deal with partially valid input, so it's in the business of building parse *subtrees* interspersed with non-parseable stuff. It consequently does better using bottom-up techniques, and doing so in a way that may not result in a valid parse tree. If you're doing that sort of thing, have a look at the syntax coloring parser from IBM that's being used for C++ in Eclipse. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
