Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

If you value parser performance you should use a parser generator. Handwritten parsers rarely approach the performance of a fast table-based generated parser.


A hand-written lexer should beat most table-based lexers. Hand-written lexers encode the automaton state in the program counter and encode the transitions in code branches, whereas table-based need to use a separate variable and encode the transitions through an indirection followed by a loop.

Parsers are a different kettle of fish entirely though. You hypothetically compare a handwritten parser with a "fast" generated parser. Presumably a handwritten parser will be faster than a "slow" generated parser?

If the language to be parsed is simple and has no ambiguities that need semantic information to resolve (this is not the case for C, for example, never mind C++), a generated parser may save time. Would it be faster than a handwritten parser? I have my doubts, for similar reasons as lexers. The automaton state is stored implicitly via the program counter, and state transitions are in code: similar arguments apply. If the handwritten parser is doing more busywork, such as a lot of recursion to handle precedence in expressions, then it may be slower. But if it uses precedence parsing just for operators, it can get that back, while not losing the benefits of recursive descent style.

OTOH, if you're trying to parse a fairly ambiguous language, you can save a substantial amount of effort with a parallelized LR parser, something that builds a forest of parse trees and discards options that are no longer feasible when more information comes in: a Tomita or GLR parser. Parsing such languages with recursive descent typically involves a lot of extra work building up semantic info as you go, or parsing a simpler form of the language and rewriting with disambiguation later, after further analysis. But GLR parsing is O(n^3) in the worst case. Hand-written may be a lot more work, but it might also be faster. It depends.


The example I was thinking of when I mentioned performance was Lua. Instead of generating a syntax tree the recursive descent parser directly spits out bytecode as it goes, which ends up being a big performance win on large source files.


Taking the other side of the argument in my sibling comment to yours: using a parser generator does not preclude directly spitting out bytecode. You can do that in the parse actions instead of building an AST.

A bottom-up parser like that produced by LALR parser generator could make this slightly more awkward, depending on what you need to generate the bytecode, but an LL(k) parser generator (e.g. Antlr) should let you do most of what you'd do with recursive descent, and in a similar way.


I wonder if exists other ways, and find a obscure reference to "slim binaries":

(Asked here)

https://www.reddit.com/r/Compilers/comments/2o78hd/exist_a_s...

Also, I wonder how NOT lost the info that already have the AST in the bytecode conversion, I even have the crazy idea to store everything in a sqlite database, but I suspect will be slow (to read later in the VM...)


Evaluate code for a stack machine symbolically, and you'll end up with an expression tree. RPN bytecode is a post-order traversal of the underlying expression.

Things get a bit more wrinkly with control flow, but you can design bytecode to make it easier to rehydrate that too.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: