4 ms·
Yeah tape-based algorithms are an anachronism, but the idea of eliminating bounds checking via a terminal value is very powerful. An example of this in action
by ridiculous_fish 8y ago
Yeah tape-based algorithms are an anachronism, but the idea of eliminating bounds checking via a terminal value is very powerful.
An example of this in action is LLVM's MemoryBuffer [1], which is input to a parser. How to write a parser? Perhaps it performs bounds checking at each production. However LLVM guarantees that the MemoryBuffer is NUL (0) terminated. A parser can then arrange for NUL to be a terminating character, and handle it uniformly.
The resulting parsers are faster, and also significantly clearer and easier to write, because there's no need for bounds checking at all.
http://llvm.org/doxygen/classllvm_1_1MemoryBuffer.html http://llvm.org/doxygen/classllvm_1_1MemoryBuffer.html
- magicalhippo 8y agoHowever it requires that the terminal value does not occur in the input. For a parser that's probably not a problem (it can transform NULs in the input to a different token), in other situations it's not so easy.