4 ms·

Parser generators allow you to work on a higher level. The reason why you may want to use one is the same as the reason why you'd want to use a higher level lan

by jules 12y ago

Parser generators allow you to work on a higher level. The reason why you may want to use one is the same as the reason why you'd want to use a higher level language rather than assembly. Instead of repeating the same pattern to implement every rule in the grammar you simply write down the grammar and the parser generator expands that so that you don't have to. Unfortunately most parser generators are limited in the class of languages they parse, or they are limited in the languages that they can express conveniently. Even parser generators that support full context free grammars are not enough. You need some method to abstract common patterns. For example if you want to express operator parsing in a context free grammar you end up with a separate rule for each level of precedence. Parser combinator libraries do allow you to use the full abstraction facilities of the programming language, but they usually are weak in terms of which grammars they allow you to parse in polynomial time (usually LL), whereas ideally you would be able to parse regular languages in O(n), deterministic languages in O(n) and context free languages in O(n^3). Also parser combinators often do not support streaming & incrementality because their reliance on backtracking forces them to keep the entire input in memory. I don't know of any parser generator or parser combinator library that simultaneously supports abstraction and supports efficient streaming parsing. Does anybody know one?

sklogic 12y ago
There are parser generators based on PEG and Pratt, which are very flexible and efficient.
- jules 12y ago
  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 implemented a Pratt parser in the past but I thought it was just for parsing operators with precedence?
  - 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

by jules 12y ago

sklogic 12y ago

There are parser generators based on PEG and Pratt, which are very flexible and efficient.

jules 12y ago
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 implemented a Pratt parser in the past but I thought it was just for parsing operators with precedence?
- 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