11 ms·

Which Parsing Approach? (2020)

52 points by tomas789 3y ago

fjfaase 3y ago
An interesting article about parsing techniques that were developed half a century ago when there were still severe memory limitations. It would be nice if it at least would mention that these techniques were developed because back-tracking was not considered as a valid option for parsing, because it was simply not feasible to store a whole file in memory. Nowadays the whole source code of the linux kernel easily fits in RAM. For many applications, using a back-tracking parser with some memorization/caching, is feasible. IParse Studio [1] is an example of an interpretting parser that parses a grammar and an input at each change on the input and demonstrates that it works for rather complex grammars [2] on realistic input [3]. [1] https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStudio.html https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStu... [2] https://fransfaase.github.io/MCH2022ParserWorkshop/C_grammar.txt https://fransfaase.github.io/MCH2022ParserWorkshop/C_grammar... [3] https://fransfaase.github.io/MCH2022ParserWorkshop/scan_pc.txt https://fransfaase.github.io/MCH2022ParserWorkshop/scan_pc.t...
- amelius 3y ago
  > works (...) on realistic input However, sometimes the input is generated by code. Think of e.g. huge switch statements. It's certainly not nice if a parser breaks down on that.
- mpweiher 3y ago
  "I suspect that parsing performance worries date back to the period when parsing techniques were under heavy development. LR parsing was invented in 1965, a time when computers were painfully slow [19] and resource poor. " "When combined with a couple of other techniques to squeeze the statetable’s memory footprint [22], even the most puny modern machine can run an arbitrary LR parser at impressive speeds."
- tgv 3y ago
  The source file isn't the main memory concern, it's the memoization.
  - fjfaase 3y ago
    There is no need for full memoization. The above JavaScript implmentation caches for each non-terminal the last location a parsing attempt was made and the out come of that: either false, or true with an abstract syntax tree and the next location after the part of the input that was parsed.
- practal 3y ago
  Here is another example of an LR parser that reads the grammar on the fly and immediately parses the input (which is, among other things, also defining its own grammar) with it: https://marketplace.visualstudio.com/items?itemName=Practal.practal https://marketplace.visualstudio.com/items?itemName=Practal.... But it seems the LR approach is just not flexible enough for my needs, so I am experimenting with replacing it with parser combinators + Earley parsing. The LR approach has also the disadvantage of having to precompute tables, which is fine for a single file, but if you want to deal with modules, then I am not sure how to compute these tables incrementally, which is kind of a prerequisite for a good user experience.
endorphine 3y ago
(2020)
- deleted 3y ago
  [deleted]
rsecora 3y ago
>>> Over time, I’ve come to view LR parsing as equivalent to static typing: occasionally annoyingly restrictive, but providing enough static guarantees to be worth the annoyance for important software. That's also one of the points of using parser tools instead of hand coded descendant parsers. The rule validation is also done by the tool. A lot of pitfalls can be avoided.
CipherThrowaway 3y ago
Generated lexers are still worth it but handwritten RD won on the parsing front. No other historical debate gets this Weekend at Bernie's treatment the way parser generators do. Is it from dated undergrad + research material? There must be a reason all the references and approaches in this article are decades old and parser combinators get a single dismissive footnote. Pretty sure that Guy Steele quote even predates PEGs. Bison and YACC are a mess. Sure, go and complicate your build by introducing code gen steps and ancient spaghetti DSLs with terrible tooling and an extra learning curve. Anything to avoid writing a readable parser in the same language as the rest of your compiler. The amount of ink spilled over parsing and parser generators is phenomenal when you consider how trivial parsing is compared to the other compilation phases. Look at source code for large compilers and you'll find the handwritten parser is some of the easiest code to understand in the project. Lack of left recursion is a trivial limitation in practice.
- supriyo-biswas 3y ago
  The front end of compilers gets a lot of attention because the problem looks complex, but is easy in practice, which is why there are a large number of materials trying to teach the topic. On that note, what resources would you suggest to become familiar with the backends of a compiler? The CS classes I had mostly had a frontend focus with the backend only being covered at a high level and without delving too deep into the implementation details.
  - CipherThrowaway 3y ago
    I have a similar struggle and find you are largely limited to learning piecemeal. I have found the best learning resources are the technical docs, specifications, proposals and source code of major language projects and VMs. Research languages and associated research papers. Conference talks by compiler authors (Rust has some good ones).
- simplotek 3y ago
  > Generated lexers are still worth it but handwritten RD won on the parsing front. Packrat parsers make a very compelling case. I'm not sure the debate is over.
_0ffh 3y ago
Personally, I swear by recursive descent parsing mixed with TDOP for expressions. Since I've tried that combination for the first time I haven't looked back.
- mncharity 3y ago
  And I. OP with partial-order precedence, mixfix ops, op predicates for white-space sensitivity, and op-fragment chains for n-ary mixfix. RD with backtracking, computed predicate rules, and backtracked "parse scoped" data. The thought of exploring a performance-oriented one in Julia (monomorphized multiple-dispatch jit) occasionally comes to mind - if I ever see a "get the rep right and the problem gets much easier" story for graph rewrite on an LLVM scale, I might try for an fully-extensible compiler bootstrap.
ceving 3y ago
Thank you! A very nice overview and plausible reasoning.
sunday_serif 3y ago
I think this may be one of the best overviews of parsing algorithms I’ve come across! It is concise, it points out the various approaches and their advantages/pitfalls in practice. In general, it seems like most articles on parsing are overly pushing one approach or another… either because people have cargo culted themselves into believing whatever they learned first is best, or because they only understand one approach. Parsers are just plain tough imo! It is a simple problem with a tricky solution space! Complete overviews with citations like this are hard to come by in my opinion.

52 points by tomas789 3y ago

An interesting article about parsing techniques that were developed half a century ago when there were still severe memory limitations. It would be nice if it at least would mention that these techniques were developed because back-tracking was not considered as a valid option for parsing, because it was simply not feasible to store a whole file in memory. Nowadays the whole source code of the linux kernel easily fits in RAM. For many applications, using a back-tracking parser with some memorization/caching, is feasible. IParse Studio [1] is an example of an interpretting parser that parses a grammar and an input at each change on the input and demonstrates that it works for rather complex grammars [2] on realistic input [3]. [1] https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStudio.html https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStu... [2] https://fransfaase.github.io/MCH2022ParserWorkshop/C_grammar.txt https://fransfaase.github.io/MCH2022ParserWorkshop/C_grammar... [3] https://fransfaase.github.io/MCH2022ParserWorkshop/scan_pc.txt https://fransfaase.github.io/MCH2022ParserWorkshop/scan_pc.t...

amelius 3y ago
> works (...) on realistic input However, sometimes the input is generated by code. Think of e.g. huge switch statements. It's certainly not nice if a parser breaks down on that.
mpweiher 3y ago
"I suspect that parsing performance worries date back to the period when parsing techniques were under heavy development. LR parsing was invented in 1965, a time when computers were painfully slow [19] and resource poor. " "When combined with a couple of other techniques to squeeze the statetable’s memory footprint [22], even the most puny modern machine can run an arbitrary LR parser at impressive speeds."
tgv 3y ago
The source file isn't the main memory concern, it's the memoization.
- fjfaase 3y ago
  There is no need for full memoization. The above JavaScript implmentation caches for each non-terminal the last location a parsing attempt was made and the out come of that: either false, or true with an abstract syntax tree and the next location after the part of the input that was parsed.
practal 3y ago
Here is another example of an LR parser that reads the grammar on the fly and immediately parses the input (which is, among other things, also defining its own grammar) with it: https://marketplace.visualstudio.com/items?itemName=Practal.practal https://marketplace.visualstudio.com/items?itemName=Practal.... But it seems the LR approach is just not flexible enough for my needs, so I am experimenting with replacing it with parser combinators + Earley parsing. The LR approach has also the disadvantage of having to precompute tables, which is fine for a single file, but if you want to deal with modules, then I am not sure how to compute these tables incrementally, which is kind of a prerequisite for a good user experience.

endorphine 3y ago

(2020)

deleted 3y ago
[deleted]

rsecora 3y ago

>>> Over time, I’ve come to view LR parsing as equivalent to static typing: occasionally annoyingly restrictive, but providing enough static guarantees to be worth the annoyance for important software. That's also one of the points of using parser tools instead of hand coded descendant parsers. The rule validation is also done by the tool. A lot of pitfalls can be avoided.

CipherThrowaway 3y ago

Generated lexers are still worth it but handwritten RD won on the parsing front. No other historical debate gets this Weekend at Bernie's treatment the way parser generators do. Is it from dated undergrad + research material? There must be a reason all the references and approaches in this article are decades old and parser combinators get a single dismissive footnote. Pretty sure that Guy Steele quote even predates PEGs. Bison and YACC are a mess. Sure, go and complicate your build by introducing code gen steps and ancient spaghetti DSLs with terrible tooling and an extra learning curve. Anything to avoid writing a readable parser in the same language as the rest of your compiler. The amount of ink spilled over parsing and parser generators is phenomenal when you consider how trivial parsing is compared to the other compilation phases. Look at source code for large compilers and you'll find the handwritten parser is some of the easiest code to understand in the project. Lack of left recursion is a trivial limitation in practice.

supriyo-biswas 3y ago
The front end of compilers gets a lot of attention because the problem looks complex, but is easy in practice, which is why there are a large number of materials trying to teach the topic. On that note, what resources would you suggest to become familiar with the backends of a compiler? The CS classes I had mostly had a frontend focus with the backend only being covered at a high level and without delving too deep into the implementation details.
- CipherThrowaway 3y ago
  I have a similar struggle and find you are largely limited to learning piecemeal. I have found the best learning resources are the technical docs, specifications, proposals and source code of major language projects and VMs. Research languages and associated research papers. Conference talks by compiler authors (Rust has some good ones).
simplotek 3y ago
> Generated lexers are still worth it but handwritten RD won on the parsing front. Packrat parsers make a very compelling case. I'm not sure the debate is over.

_0ffh 3y ago

Personally, I swear by recursive descent parsing mixed with TDOP for expressions. Since I've tried that combination for the first time I haven't looked back.

mncharity 3y ago
And I. OP with partial-order precedence, mixfix ops, op predicates for white-space sensitivity, and op-fragment chains for n-ary mixfix. RD with backtracking, computed predicate rules, and backtracked "parse scoped" data. The thought of exploring a performance-oriented one in Julia (monomorphized multiple-dispatch jit) occasionally comes to mind - if I ever see a "get the rep right and the problem gets much easier" story for graph rewrite on an LLVM scale, I might try for an fully-extensible compiler bootstrap.

ceving 3y ago

Thank you! A very nice overview and plausible reasoning.

sunday_serif 3y ago

I think this may be one of the best overviews of parsing algorithms I’ve come across! It is concise, it points out the various approaches and their advantages/pitfalls in practice. In general, it seems like most articles on parsing are overly pushing one approach or another… either because people have cargo culted themselves into believing whatever they learned first is best, or because they only understand one approach. Parsers are just plain tough imo! It is a simple problem with a tricky solution space! Complete overviews with citations like this are hard to come by in my opinion.