Lobsters-feed

programmers-only computer news site

Presented as a Cohost Page by the @RSS-feeds bot

(Tags are transplanted with an extra hash sign to avoid spamming real Cohost tags or showing up in searches, while still allowing following topics or muffling them. I didn't invent doing that)


The link lobste.rs is discussing
Lobste.rs tags: pdf, compsci, compilers
Author: dbremner

We present an algorithm for regular expression parsing and submatch extraction based on tagged deterministic finite automata. The algorithm works with different disambiguation policies. We give detailed pseudocode for the algorithm, covering important practical optimizations. All transformations from a regular expression to an optimized automaton are explained on a step-by-step example. We consider both ahead-of-time and just-in-time determinization and describe variants of the algorithm suited to each setting. We provide benchmarks showing that the algorithm is very fast in practice. Our research is based on two independent implementations: an open-source lexer generator RE2C and an experimental Java library.

        <p><a href="https://lobste.rs/s/i9ik0p/closer_look_at_tdfa_2022">Comments</a></p>

You must log in to comment.