3 ms·
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 co
by barrkel 12y ago
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.