4 ms·

PEG parsers are not streaming. They have to keep the entire input in memory in case backtracking happens. I'll look into Pratt parsing. I've actually implemente

• sklogic 12y ago
  > 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. There is also a Packrat+Pratt parser used in https://github.com/combinatorylogic/mbase https://github.com/combinatorylogic/mbase