On Tue, Oct 14, 2014 at 2:31 PM, Jonathan S. Shapiro <[email protected]> wrote: > 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.
All the more reason to ask it in a forum that tolerates opinion. :) > 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. Perfect, that answers even the more detailed form of my question. Our grammar will be intentionally ambiguous since we'll be trying to detect and fix broken code. E.g., we want to do things like parsing f(x,y) as both applying f to two arguments and applying f to a single tuple, then disambiguating using types later on. Thus, GLR seems good, and the IBM Eclipse parser seems like a wonderful place to start. Thanks! Geoffrey _______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
