![]() ![]() In 1989, I compared the parsing speed of LRSTAR parsers to "yacc" and found that they are 2 times the speed of "yacc" parsers. The problem is that real-world compilers usually need to do more than pattern recognition, such as symbol-table look-up for incoming symbols, error recovery, provide an expecting list (statement completion information), and build an abstract-syntax tree while parsing. However, if all you want is a pattern recognizer, then it may be the perfect solution for you. ![]() Tom Pennello's paper is very interesting, but is more of an academic exercise than a real-world solution for compilers. I have studied the speed of LALR parsers and DFA lexers for many years. Because people are showing interest in it, I have put the product back online here LRSTAR. I am the author of LRSTAR, an open-source LR(k) parser generator. I give up some performance, but I can build dozens of parsers for many languages without a lot of trouble.). I don't do that anymore instead I use GLR parsers which are linear time in practice but handle arbitrary context-free grammmars. (I used to build LALR parser generators and corresponding parsers. Optimize that (your bio says you are), and the parser speed won't matter much. My money is strongly on L(AL)R.Īn observation: most language front-ends don't spend most of their time "parsing" rather, they spend a lot of time in lexical analysis. If you care about the answer, read the basic technical papers closely if you really care, then implement one of each and check out the overhead constants. The YACC and Bison implementations from what I hear are pretty good. If packrat parsers are storing/caching results as they go, they may be linear time, but I'd guess the constant overhead would be pretty high, and then L(AL)R parsers in practice would be much faster. ![]() (Machines are now 20 years faster than when he wrote the paper!). By "compiling" L(AL)R parsing to machine code, you can end up with lightning fast parsers, as shown by this 1986 Tom Pennello paper on Very Fast LR parsing. L(AL)R state transitions can be executed in very few machine instructions ("look token code up in vector, get next state and action") so they can be extremely fast in practice. What matters, in practice, of course, is implementation. So in theory, neither packrat nor L(AL)R parsers are "faster". L(AL)R parsers are linear time parsers too. I haven't dug into it so I'll assume the linear-time characterization of packrat parsing is correct. I'm not an expert at packrat parsing, but you can learn more at Parsing expression grammar on Wikipedia. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |