Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Certified Split Points for Parallel Lexing: Exact and Modulo Discarded Tokens

T0 review · 2 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Certified split bytes are points where a longest-match scanner is provably between tokens; chunks starting there concatenate to the exact serial token stream.

desk verdict The certificate is real and the theorems hold up; the only serious weakness is that the headline speedups rest on an incompletely archived benchmark. read the letter →

arxiv 2608.03473 v1 pith:GPPKZX2K submitted 2026-08-04 cs.FL cs.DCcs.PL

Nicklas Nidhögg This is my paper · ORCID
classification cs.FLcs.DCcs.PL MSC 68Q4568W10
keywords parallellexingDFAtokenizerlongestmatchcertifiedsplitsymbolresetwordsmodulodiscardedtokensstaticanalysisefficiency
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Serial lexing is a dependency chain: each table lookup needs the previous state, so scanning one input in parallel requires knowing each chunk's entry state. This paper establishes a static, input-independent property that removes that requirement for a useful class of scanners: a byte is a certified split symbol when the trimmed live automaton's only transitions on that byte leave the initial state, and the initial state cannot be re-entered mid-scan. Every occurrence of such a byte in fully tokenizable input begins a token, so chunks cut immediately before it reproduce the serial (token, length) stream by ordered concatenation—no speculation, prescanning, or overlap. The condition is both necessary and sufficient, so a token set that certifies no byte genuinely has no single-byte split symbol preserving the exact stream. Because the exact condition is fragile—one string literal, comment, or whitespace run can erase every useful certificate—the paper weakens the guarantee to equality after deleting declared discarded tokens, which recovers newline for conventional C-like and JSON tokenizations; on an out-of-cache corpus the exact certificate measures 92.6–95.3% parallel efficiency at eight threads.

What carries the argument

The load-bearing object is the trimmed live subautomaton A+ = (Q+, Σ, δ+, q0, τ), where Q+ contains only states that are reachable from the initial state and can still reach acceptance, and δ+ discards transitions whose targets leave Q+. Certification is defined over A+ rather than the full table: byte b is certified if every q ∈ Q+ with δ+(q,b) defined satisfies q = q0, and if δ+(q0,b) is defined, q0 is not re-entrant. The re-entrancy clause is the subtlety: without it, the nullable token set a* would certify a and split one emitted token into two, and cyclic re-entry through (ab)*c would certify c. The relaxed modulo-I condition adds a second constant-time one-bit query: a state q consumin

What would settle it

Compile any token set to a minimized DFA, compute Q+ and Definition 2, then exhaustively scan all strings over a three-byte alphabet up to length eight, recording whether each occurrence of each byte begins a token. Any byte certified by the definition but found inside a token—or rejected despite no such witness existing—refutes Theorem 2. The paper itself shows this kind of brute-force oracle is feasible for the modulo condition.

Watch

Extended reading notes

Core claim

Central claim: the question 'where may a parallel scanner cut without changing the answer?' can be settled per token set from the compiled transition table. Fix a longest-match scanner restarting at q0 after each token; let Q+ be the states both reachable from q0 and able to reach acceptance. Byte b is certified if every live b-transition in Q+ starts at q0, and if q0 consumes b, q0 is not re-entrant. Then every occurrence of b in completely tokenizable input begins a token, and conversely; chunks cut before certified bytes reproduce the serial stream. A second, conservative condition preserves equality only after deleting a declared discarded set, and it admits newline for conventional C-li

Load-bearing premise

The approach assumes the scanner is a table-driven automaton that restarts from one fixed start state at each token boundary, carries no other state, and emits no empty tokens; lexers with modes, indentation stacks, semantic predicates, or nullable tokens fall outside the model, and the exact guarantee additionally presumes completely tokenizable input.

Editorial extensions

If this is right

  • Delimiter safety stops being a language-specific folklore assumption: for any compiled token set, the certificate is decided from the transition table, and a row that certifies nothing is a statement about the tokenization, not about the test.
  • Because the condition is necessary as well as sufficient, no token set that certifies no byte admits any single-byte split symbol that preserves the exact stream; regaining a split point requires changing the tokenization, weakening the guarantee, or framing the input.
  • Declaring discarded tokens extends the method to conventional grammars as written: the relaxed certificate recovers newline for a C-like tokenization and tab, newline, and carriage return for JSON, with no change to their token definitions.
  • In the measured implementation, exact-certificate splitting reaches 92.6–95.3% parallel efficiency at eight threads and a 3.46–3.94× end-to-end speedup at four threads on a 512 MiB corpus beyond last-level cache, with chunks guaranteed to reproduce the serial stream.
  • A producer that reserves a byte excluded from all token interiors and escapes it in content can make any grammar chunkable, including grammars with block comments.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the necessity theorem holds, a token set that certifies nothing is not a failure of the test but a fact about the grammar; a natural untested engineering response is to automate the tokenization refactoring the paper describes by hand, such as making newline its own token.
  • The relaxed certificate is shipped only as a query—planner and benchmarks use the exact map—so the practical throughput gain from modulo-I splitting for conventional grammars remains unmeasured; building a planner on the relaxed map is a concrete next experiment.
  • Because certified bytes are one-letter reset words of the partial live automaton, searching for multi-letter reset words or short windows such as ')' followed by newline could yield conditional certificates for grammars with no single certified byte; the paper lists this as future work rather than a result.
  • The measured scaling comes from a corpus free of strings and comments and a grammar that certifies 13 of 14 candidate bytes, so extrapolating those efficiency numbers to typical source code would require the relaxed planner the paper does not ship.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies a table-driven longest-match DFA lexer that resets to a single initial state q0 at every token boundary. It defines a byte b to be a certified split symbol when, in the live reachable/co-accessible subautomaton A+, no state other than q0 has a b-transition whose target can reach acceptance, and q0 is not re-entrant if it consumes b. Lemma 1 and Theorem 1 show every occurrence of such a byte in completely tokenizable input is a token boundary, so ordered concatenation of per-chunk token streams reproduces the serial stream. Theorem 2 proves the converse. Definition 3 and Theorem 3 weaken equality to equality after deleting a declared discarded-token set, via a conservative local condition. The paper contributes a linear-time derivation, a planner, an applicability study over eleven token sets, and an evaluation in the munch library. The theoretical core is sound; the main weakness is reproducibility of the headline empirical numbers.

Significance. The result, if correct, is a genuinely useful static characterization: safe split points for a class of parallel lexers become a decidable per-symbol property of the compiled transition table rather than a language-specific assumption. The proofs are explicit and checkable; the paper goes beyond folklore by giving necessity, by identifying the re-entrancy condition, and by handling discarded tokens. The artifact includes property tests, an exhaustive oracle on small alphabets, regression tests for the counterexamples, and archived benchmark summaries. These are real strengths. The scope is carefully limited to the Section 3 scanner model, and the paper's own limitations section names what falls outside (modes, predicates, non-regular constructs). The empirical speedup claims, however, are not yet on the same footing as the theory.

major comments (2)
  1. [§8 / Table 2 / §11] The headline quantitative claims—92.6–95.3% parallel efficiency and 3.46–3.94× end-to-end speedup—are not reproducible from the archived artifact. As the text itself discloses, the two Environment B collections are two benchmark revisions at different commits, each placement has a single run, the launch command and core mask were not archived, the machine was not quiesced, and the clock on Environment B is observable but not fixed. Since these numbers are the paper's main empirical evidence that the technique pays for itself, this is load-bearing rather than cosmetic. I request either an archived pinned run with exact command, mask, and commit plus interleaved repeats, or a clear demotion of the quantitative claims to illustrative/pilot status in the abstract and conclusion.
  2. [§8.1] The end-to-end ratio is dominated by an unstable denominator. The paper reports that the plain-scan row rose 14.3% (pinned) and 17.4% (unpinned) between revisions at 512 MiB, while the multi-chunk rows moved by at most about 1.4%, and that the plain-scan versus one-chunk comparison changed sign across collections. The 3.46–3.94× range therefore mostly reflects revision-to-revision baseline movement, not a stable treatment effect. Because the paper uses ratio-of-medians as a single estimator and does not report paired per-round ratios except for win counts, the reader cannot separate the parallel gain from the baseline drift. Please report per-round paired ratios and/or a controlled repeat with the same commit and interleaved conditions.
minor comments (4)
  1. [§9] The paper's own limitation statement is accurate and should perhaps be moved earlier: the certificate is sound only for the Section 3 scanner model (restart from q0, positive-length tokens, no carried state). Lexer modes, indentation stacks, and semantic predicates are outside scope. This is a disclosed scope limit rather than an internal inconsistency, but it should be reflected on the first page.
  2. [§2] Typos/formatting: 'DF A' should be 'DFA', and 'n n' / '2 n2' should be mathematical notation for n^n and 2^{n^2}.
  3. [§6.1] The phrase 'Condition 3' is ambiguous; it should refer to Definition 3 or to clause C(3). Also, the statement 'the relaxation is free at scan time' should be qualified by the fact that the planner does not use the relaxed map; no runtime measurement of the relaxed path is reported.
  4. [Table 3] Formatting in the first row ('0.1µs<1 KiB') is unclear; state that the median bytes scanned is below 1 KiB.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the certificate is a syntactic condition and the equivalence theorems are proven from the scanner model, not assumed.

full rationale

The derivation chain is self-contained. Definition 2 is a purely syntactic property of the live subautomaton (Q+, δ+, re-entrancy), and Theorem 2 proves — rather than presupposes — its equivalence with the semantic condition "every occurrence of b in every completely tokenizable input begins a token": sufficiency is Lemma 1, and necessity constructs explicit witnesses w = u b v from the two ways Definition 2 can fail. Theorem 1 composes Lemma 1 with Lemma 2, and Theorem 3 handles the modulo-I relaxation by a case analysis whose load-bearing clause is the row equality δ+(q0,b) = δ+(q,b) together with T(q) ⊆ I; the proof does not rely on the conclusion. No parameter is fitted: the relaxed condition is explicitly conservative, and its strictness is established by a named witness rather than by tuning. The only self-citation is to the author's own munch library [22], used for implementation, property tests, and benchmark measurements; the theorems are proven in the text independently of that citation, so the self-citation is not load-bearing. The empirical speedup claims are disclosed as machine-, corpus-, and token-set-dependent and are not presented as derived predictions. The paper even identifies the would-be circular move in §7.1 — read-time normalization cannot manufacture certified bytes because deciding which occurrences lie inside tokens is the sequential problem — and explicitly disclaims it. The §9 scanner-model limitation is a scope statement, not a circularity; the §8 environmental caveats are reproducibility concerns, not circular reasoning. Accordingly there are no circular steps.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim is a first-principles derivation from the defined scanner semantics. The certificate is computed from the transition table, and Theorem 2 proves its equivalence to the semantic condition, so the derivation introduces no fitted constants, no hand-tuned thresholds, and no input-dependent quantities. The caller-chosen discarded set I is an input to the relaxed analysis, not a fitted parameter. The load-bearing premises are the scanner model (q0 reset, positive-length tokens, no auxiliary state) and the correctness of the compiled table; both are stated explicitly in the paper.

assumptions (4)
  • domain assumption Scanner model: longest-match loop restarting in q0 at every token boundary, partial transition function, positive-length tokens.
    Section 3: 'The scanner is the usual longest-match loop... restarts at that position in q0'; 'Tokens are positive-length: acceptance counts only after at least one symbol has been consumed... Without that rule the loop is undefined exactly where Section 4.2 needs it.' Every theorem is stated over this model; lexers with modes, nullable tokens, or auxiliary state are out of scope, as Section 9 concedes.
  • domain assumption q0 in Q+, the token set accepts at least one word.
    Section 4: 'If q0 not in Q+ the token set accepts nothing, and no symbol is useful; we assume q0 in Q+ throughout.' Degenerate empty token sets are excluded from the characterization.
  • standard math Standard DFA facts: reachability, co-accessibility, determinism; the match path of any emitted token lies in A+.
    Section 4: 'the match path of any emitted token lies in A+ throughout, since every transition along it leads to that token's accepting position.' Used in the proofs of Lemmas 1 and 2 and Theorems 1-3.
  • domain assumption The compiled transition table faithfully represents the token definitions (compiler correctness).
    Section 6 derives the certificate from the compiled table; a buggy compilation would feed a wrong table to the analysis. The paper notes the analysis is exposed on a simulator that accepts any transition table, so the assumption is about the compiler, not the analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Certified Split Points for Parallel Lexing: Exact and Modulo Discarded Tokens." pith.science (2026). https://pith.science/paper/GPPKZX2K

@misc{pith2026260803473,
  author       = {Pith},
  title        = {Pith review of: Certified Split Points for Parallel Lexing: Exact and Modulo Discarded Tokens},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GPPKZX2K}},
  note         = {Machine review of arXiv:2608.03473}
}
read the original abstract

Table-driven DFA lexing is sequential: each transition depends on the previous byte's state. Scanning one input in parallel needs each chunk's entry state, which existing methods recover by simulation, speculation, prescanning, or overlap. We give two conditions under which none is needed. For a longest-match scanner restarting from q0 at every token boundary, a byte b is a certified split symbol when no reachable state other than q0 has a b-transition whose target can reach acceptance, and q0 is not re-entrant if it has one. Every occurrence of such a byte in completely tokenizable input begins a token, so chunks starting there reproduce the serial sequence of kinds and lengths by ordered concatenation. The condition is necessary as well as sufficient, and fragile: one string, comment, or whitespace run can eliminate every useful certificate, and comments and whitespace are usually discarded. We therefore weaken the guarantee to equality after deleting a declared discarded set, and give a second condition, sound and strictly more permissive but conservative rather than exact, decided from the same tables, answered by a second constant-time one-bit query. It recovers newline for a conventional C-like tokenization and tab, newline and carriage return for JSON, without altering their token definitions, and refuses it where block comments are unrestricted. It ships as a query only: the library's planner and every measurement here use the exact condition, so a caller must plan boundaries itself. Splitting at exact certificates in the munch library reaches 92.6-95.3% parallel efficiency at eight threads on a restricted CPU set, on a 512 MiB dense corpus beyond last-level cache, and a 3.46-3.94x end-to-end speedup at four threads, across two benchmark revisions on one machine. It turns delimiter-based parallel lexing from a language-specific assumption into a property a compiler checks.

Figures

Figures reproduced from arXiv: 2608.03473 by the authors.

Figure 1
Figure 1. Minimized automata drawn by the library described here; double circles are accepting [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. A certified byte is a point where the serial scan is provably between tokens: no state [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies

    cs.FL 2026-08 accept novelty 7.0 of 10

    Certified split windows generalize split-point certificates to bounded byte strings, recovering the origin of the covering token for token sets where no single byte certifies.

Reference graph

Works this paper leans on

36 extracted references · 27 canonical work pages · cited by 1 Pith paper

  1. [1]

    Parallel parsing made practical.Science of Computer Programming, 112:195–226, 2015

    Alessandro Barenghi, Stefano Crespi Reghizzi, Dino Mandrioli, Federica Panella, and Matteo Pradella. Parallel parsing made practical.Science of Computer Programming, 112:195–226, 2015. doi:10.1016/j.scico.2015.09.002

    doi:10.1016/j.scico.2015.09.002 2015

  2. [2]

    Parallel lexical analysis of multiple files on multi-core machines.International Journal of Computer Applications, 96(16):22–24, 2014.doi:10.5120/ 16879-6879

    Amit Barve and Brijendra Kumar Joshi. Parallel lexical analysis of multiple files on multi-core machines.International Journal of Computer Applications, 96(16):22–24, 2014.doi:10.5120/ 16879-6879

    work page 2014

  3. [3]

    Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szyku la

    Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szyku la. Synchronizing strongly connected partial DF As. In38th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 187 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:16, 2021.doi:10.4230/LIPIcs.STACS.2021.12

    work page doi:10.4230/lipics.stacs.2021.12 2021

  4. [4]

    Minimizing speculation overhead in a parallel recognizer for regular texts

    Angelo Borsotti, Luca Breveglieri, Angelo Morzenti, and Stefano Crespi Reghizzi. Minimizing speculation overhead in a parallel recognizer for regular texts. In30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 569–572, 2025. doi:10.1145/3710848.3710866. Preprint: arXiv:2412.14975

    arXiv 2025

  5. [5]

    The JavaScript object notation (JSON) data interchange format

    Tim Bray, Ed. The JavaScript object notation (JSON) data interchange format. Request for Comments 8259, RFC Editor, December 2017. STD 90.doi:10.17487/RFC8259

    doi:10.17487/rfc8259 2017

  6. [6]

    Cameron, Kenneth S

    Robert D. Cameron, Kenneth S. Herdy, and Dan Lin. High performance XML parsing using parallel bit stream technology. InConference of the Center for Advanced Studies on Collaborative Research (CASCON), pages 222–235, 2008.doi:10.1145/1463788.1463811. Article 17

    work page arXiv 2008

  7. [7]

    ASCII format for network interchange

    Vint Cerf. ASCII format for network interchange. RFC 20, Network Working Group, 1969.doi: 10.17487/RFC20

    work page doi:10.17487/rfc20 1969

  8. [8]

    Formally Verified Linear-Time Invertible Lexing

    Samuel Chassot and Viktor Kunˇ cak. Formally verified linear-time invertible lexing. In38th In- ternational Conference on Computer Aided Verification (CA V), volume 16683 ofLecture Notes in Computer Science, pages 141–164, 2026.doi:10.1007/978-3-032-32526-6_7. Extended version with the separator-token appendix: arXiv:2510.18479

    work page Pith review arXiv 2026

Show all 36 references
  1. [9]

    Speculative distributed CSV data parsing for big data analytics

    Chang Ge, Yinan Li, Eric Eilebrecht, Badrish Chandramouli, and Donald Kossmann. Speculative distributed CSV data parsing for big data analytics. InACM SIGMOD International Conference on Management of Data, pages 883–899, 2019.doi:10.1145/3299869.3319898

    2019

  2. [10]

    Daniel Hillis and Guy L

    W. Daniel Hillis and Guy L. Steele, Jr. Data parallel algorithms.Communications of the ACM, 29 (12):1170–1183, 1986.doi:10.1145/7902.7903

    1986

  3. [11]

    On parallel implementations of deterministic finite automata

    Jan Holub and Stanislav ˇStekr. On parallel implementations of deterministic finite automata. In14th International Conference on Implementation and Application of Automata (CIAA), volume 5642 of Lecture Notes in Computer Science, pages 54–64, 2009.doi:10.1007/978-3-642-02979-0_9

    2009 doi

  4. [12]

    A generator of incremental divide-and-conquer lexers: A tool to generate an incremental lexer from a lexical specification

    Jonas Hugo and Kristofer Hansson. A generator of incremental divide-and-conquer lexers: A tool to generate an incremental lexer from a lexical specification. Master’s thesis, Chalmers University of Technology, 2015

    2015

  5. [13]

    Combining SIMD and many/multi-core parallelism for finite state machines with enumerative speculation

    Peng Jiang and Gagan Agrawal. Combining SIMD and many/multi-core parallelism for finite state machines with enumerative speculation. In22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 179–191, 2017.doi:10.1145/3018743.3018760

    2017

  6. [14]

    Paral- lelizing the web browser

    Christopher Grant Jones, Rose Liu, Leo Meyerovich, Krste Asanovi´ c, and Rastislav Bod ´ ık. Paral- lelizing the web browser. In1st USENIX Workshop on Hot Topics in Parallelism (HotPar), 2009

    2009

  7. [15]

    Parsing gigabytes of JSON per second.The VLDB Journal, 28 (6):941–960, 2019.doi:10.1007/s00778-019-00578-5

    Geoff Langdale and Daniel Lemire. Parsing gigabytes of JSON per second.The VLDB Journal, 28 (6):941–960, 2019.doi:10.1007/s00778-019-00578-5

    2019 doi

  8. [16]

    Li and Konstantinos Mamouras

    Angela W. Li and Konstantinos Mamouras. Efficient algorithms for the uniform tokenization problem.Proceedings of the ACM on Programming Languages, 9(OOPSLA1):1492–1518, 2025. doi:10.1145/3720498. 27

    2025 doi

  9. [17]

    Li, Yudi Yang, and Konstantinos Mamouras

    Angela W. Li, Yudi Yang, and Konstantinos Mamouras. Static analysis for efficient streaming tokenization. In31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Volume 2, pages 1880–1896, 2026.doi:10.1145/ 3779212.3790227

    2026

  10. [18]

    Plex: Scaling parallel lexing with backtrack- free prescanning

    Le Li, Shigeyuki Sato, Qiheng Liu, and Kenjiro Taura. Plex: Scaling parallel lexing with backtrack- free prescanning. InIEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 693–702, 2021.doi:10.1109/IPDPS49936.2021.00079

    2021

  11. [19]

    Katsipoulakis, Badrish Chandramouli, Jonathan Goldstein, and Donald Koss- mann

    Yinan Li, Nikos R. Katsipoulakis, Badrish Chandramouli, Jonathan Goldstein, and Donald Koss- mann. Mison: A fast JSON parser for data analytics.Proceedings of the VLDB Endowment, 10 (10):1118–1129, 2017.doi:10.14778/3115404.3115416

    2017

  12. [20]

    Multi-byte regular expression matching with speculation

    Daniel Luchaup, Randy Smith, Cristian Estan, and Somesh Jha. Multi-byte regular expression matching with speculation. In12th International Symposium on Recent Advances in Intrusion Detection (RAID), volume 5758 ofLecture Notes in Computer Science, pages 284–303, 2009.doi: 10.1...

    2009 doi

  13. [21]

    Data-parallel finite-state machines

    Todd Mytkowicz, Madanlal Musuvathi, and Wolfram Schulte. Data-parallel finite-state machines. In 19th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 529–542, 2014.doi:10.1145/2541940.2541988

    2014

  14. [22]

    munch: a lexical analysis library based on automata theory, version 1.2.0, 2026

    Nicklas Nidh¨ ogg. munch: a lexical analysis library based on automata theory, version 1.2.0, 2026. Release tagv1.2.0, archived atdoi:10.5281/zenodo.21752997

    2026 doi

  15. [23]

    Ramalingam, and Kapil Vaswani

    Prakash Prabhu, G. Ramalingam, and Kapil Vaswani. Safe programmable speculative parallelism. In31st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 50–61, 2010.doi:10.1145/1806596.1806603

    2010

  16. [24]

    Added warning: -Wsentinel-in-midrule

    re2c project. re2c documentation. Warnings,https://re2c.org/manual/basics/warnings/ warnings.html; Changelog,https://re2c.org/releases/changelog/changelog.html, 2026. Accessed 3 August 2026. Release 1.3, 14 December 2019, records “Added warning: -Wsentinel-in-midrule”

    2026

  17. [25]

    Maximal-munch

    Thomas Reps. “Maximal-munch” tokenization in linear time.ACM Transactions on Programming Languages and Systems, 20(2):259–273, 1998.doi:10.1145/276393.276394

    1998

  18. [26]

    Common format and MIME type for comma-separated values (CSV) files

    Yakov Shafranovich. Common format and MIME type for comma-separated values (CSV) files. Request for Comments 4180, RFC Editor, October 2005.doi:10.17487/RFC4180

    2005 doi

  19. [27]

    LoPT: Lossless parallel tokenization acceleration for long context inference of large language model

    Wei Shao, Lingchao Zheng, Pengyu Wang, Peizhen Zheng, Jun Li, and Yuwei Fan. LoPT: Lossless parallel tokenization acceleration for long context inference of large language model. In64th Annual Meeting of the Association for Computational Linguistics (ACL), Volume 1: Long Paper...

    2026

  20. [28]

    Simultaneous finite automata: An efficient data-parallel model for regular expression matching

    Ryoma Sin’ya, Kiminori Matsuzaki, and Masataka Sassa. Simultaneous finite automata: An efficient data-parallel model for regular expression matching. In42nd International Conference on Parallel Processing (ICPP), pages 220–229, 2013.doi:10.1109/ICPP.2013.31. Preprint: arXiv:1405.0562

    2013 arXiv

  21. [29]

    ParPaRaw: Massively parallel parsing of delimiter-separated raw data.Proceedings of the VLDB Endowment, 13(5):616–628, 2020.doi:10.14778/3377369

    Elias Stehle and Hans-Arno Jacobsen. ParPaRaw: Massively parallel parsing of delimiter-separated raw data.Proceedings of the VLDB Endowment, 13(5):616–628, 2020.doi:10.14778/3377369. 3377372

    2020 doi

  22. [30]

    RE2C: A lexer generator based on lookahead-TDF A.Software Impacts, 6:100027, 2020.doi:10.1016/j.simpa.2020.100027

    Ulya Trofimovich. RE2C: A lexer generator based on lookahead-TDF A.Software Impacts, 6:100027, 2020.doi:10.1016/j.simpa.2020.100027

    2020

  23. [31]

    Parallel lexing, parsing and semantic analysis on the GPU

    Robin Voetter. Parallel lexing, parsing and semantic analysis on the GPU. Master’s thesis, Leiden University, 2021

    2021

  24. [32]

    Mikhail V. Volkov. Synchronizing automata and the ˇCern´ y conjecture. In2nd International Con- ference on Language and Automata Theory and Applications (LATA), volume 5196 ofLecture Notes in Computer Science, pages 11–27, 2008.doi:10.1007/978-3-540-88282-4_4. 28

    2008 doi

  25. [33]

    Wagner and Susan L

    Tim A. Wagner and Susan L. Graham. General incremental lexical analysis. Manuscript, Univer- sity of California, Berkeley.https://harmonia.cs.berkeley.edu/papers/twagner-lexing.pdf, 1997

    1997

  26. [34]

    JavaScript Object Notation (JSON) text sequences

    Nicolas Williams. JavaScript Object Notation (JSON) text sequences. RFC 7464, 2015.doi: 10.17487/RFC7464

    2015 doi

  27. [35]

    Mealy machines are a better model of lexical analyzers.Computer Languages, 22(1): 27–38, 1996.doi:10.1016/0096-0551(96)00003-3

    Wuu Yang. Mealy machines are a better model of lexical analyzers.Computer Languages, 22(1): 27–38, 1996.doi:10.1016/0096-0551(96)00003-3

    1996 doi

  28. [36]

    On the applicability of the longest-match rule in lexical analysis.Computer Languages, Systems & Structures, 28(3):273–288, 2002.doi:10.1016/ S0096-0551(02)00014-0

    Wuu Yang, Chey-Woei Tsay, and Jien-Tsai Chan. On the applicability of the longest-match rule in lexical analysis.Computer Languages, Systems & Structures, 28(3):273–288, 2002.doi:10.1016/ S0096-0551(02)00014-0. 29

    2002

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.