Re:Yacc is Not Dead (2010)
by sklogic on Tuesday December 23, 2014 @06:04AM
(#8787673)
> PEG parsers are not streaming.
PEG is a superset of recursive descent. You can structure you grammar in a way that backtracking is not required at all or minimised.
> They have to keep the entire input in memory in case backtracking happens.
Not necessarily. You only need to keep something like around a current statement (or other small syntax entity), discarding everything you've already streamed.
> I've actually implemented a Pratt parser in the past but I thought it was just for parsing operators with precedence?
Exactly. And it's really easy to mix it into an otherwise PEG-based parser, eliminating the need to backtrack for the worst backtracking case (binary expressions).
For example, there is a very efficient implementation of such an approach (pure PEG+Pratt, no memoisation and no backtracking) in Nemerle.
PEG is a superset of recursive descent. You can structure you grammar in a way that backtracking is not required at all or minimised.
> They have to keep the entire input in memory in case backtracking happens.
Not necessarily. You only need to keep something like around a current statement (or other small syntax entity), discarding everything you've already streamed.
> I've actually implemented a Pratt parser in the past but I thought it was just for parsing operators with precedence?
Exactly. And it's really easy to mix it into an otherwise PEG-based parser, eliminating the need to backtrack for the worst backtracking case (binary expressions).
For example, there is a very efficient implementation of such an approach (pure PEG+Pratt, no memoisation and no backtracking) in Nemerle.
There is also a Packrat+Pratt parser used in https://github.com/combinatorylogic/mbase