Metadata-Version: 2.4
Name: scilex
Version: 2026.10.0
Summary: SciLex — a generic, ReDoS-safe maximal-munch lexer built on REAL
Author: René Chenard
License-Expression: MIT
Project-URL: Homepage, https://github.com/RECHE23/scilex
Project-URL: Repository, https://github.com/RECHE23/scilex
Project-URL: Documentation, https://reche23.github.io/scilex/
Project-URL: Issues, https://github.com/RECHE23/scilex/issues
Keywords: lexer,tokenizer,maximal-munch,scanner,redos-safe
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: C++
Classifier: Topic :: Software Development :: Compilers
Classifier: Topic :: Software Development :: Libraries
Classifier: Operating System :: OS Independent
Requires-Python: >=3.11
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# SciLex

**A small, header-only C++20 contextual lexer built on REAL.**

- ReDoS-safe by construction (via REAL): no rule backtracks, nothing is exponential. Linear on
  every rule a DFA takes and on grammars whose rules stop scanning near their tokens; quadratic in the
  worst case, through a rule left on Pike (see *Performance*).
- **Modes** — contextual lexing: the same byte lexes differently by context
  (f-strings, XML tag/content, YAML block/flow).
- **Layout Awareness** — mode-aware indentation (NEWLINE / INDENT / DEDENT).
- Eager `tokenize` or lazy `scan`; positioned errors with a context snippet.
- C++20 header-only + abi3 Python binding (CPython 3.11+).
- Zero dependencies beyond REAL headers.

Define an ordered set of token rules — each a `(kind, regex, skip)` triple — and
SciLex tokenizes by **maximal munch**: the longest anchored match wins, with rule
order breaking ties. A rule can also opt into **modes** (contextual lexing), so the
same byte lexes differently by context. Because it is a thin layer over REAL,
every rule match is linear in what it scans and ReDoS-safe by construction; tokenizing is linear
wherever the rules run on the DFA, and quadratic in the worst case only through a rule left on Pike
(see *Performance*).

What that covers today: significant indentation, plus contexts like f-strings, YAML
flow collections, and bracket continuation (modes + **Layout Awareness Level A**).
Cases that need a deeper lexing↔indentation coupling — YAML block scalars `|` / `>`,
heredocs — are **Level B**: documented, not in this version.

This follows the same design principles as REAL: purity, simplicity, and
measured optimality.

## Capabilities

- Ordered token rules: `(kind, real::regex, skip)`
- Maximal-munch matching (longest match wins, rule order for ties)
- **Contextual lexing (modes)** — per-rule `in_mode` + a push / pop / set mode stack
- **DFA fast path (automatic)** — every mode whose DFA reproduces the per-rule munch is accelerated with one `real::dfa` pass (5.7–18× on the example grammars, every one wholly on it); the decision is exact (Pike is the floor), the token stream identical; `dfa_policy::requested` restricts it to `dfa_modes`
- **Layout Awareness** — mode-aware indentation (NEWLINE / INDENT / DEDENT)
- Source positions (byte offset, line, column counted in bytes, code points or UTF-16 units); each token
  carries its start and its mode, and `lexer::end_of(source, token)` gives where it ends
- Eager (`tokenize`) and lazy (`scan`) APIs
- Optional `END_OF_INPUT` token
- Positioned errors with a context snippet
- ReDoS-safe (via REAL); linear wherever the rules run on the DFA, quadratic in the worst case only through a rule left on Pike
- Nine example grammars — three of them modal (f-strings, XML, YAML)

The three modal grammars differ in shape and each documents its own scope; modes
resolve the contexts above, but the one contextual case still outside the model —
lexing steered by *indentation* (block scalars, heredocs) — is Level B.

**Not yet:** block scalars / heredocs (Layout Awareness Level B), a compile-time
`static_lexer` (a baked DFA — the Phase-0 spike found this wants build-time codegen,
not constexpr).

See the [guided tour](docs/design.dox) for details.

## C++ API

```cpp
#include <scilex/scilex.hpp>

std::vector<scilex::rule> rules {
  {.kind = 0, .pattern = real::regex(R"(\s+)"), .skip = true}, // whitespace, skipped
  {.kind = 1, .pattern = real::regex("if")},                   // keyword: listed before the identifier
  {.kind = 2, .pattern = real::regex("[a-z_][a-z0-9_]*")},     // identifier
  {.kind = 3, .pattern = real::regex("[0-9]+")},               // number
  {.kind = 4, .pattern = real::regex(R"([-+*/=])")},           // operator
};
const scilex::lexer lexer {std::move(rules)};

// Lazy: one token per step (tokenize() returns them all at once).
for (const scilex::token& tok : lexer.scan("if x + 42")) {
  std::printf("%d %.*s\n", tok.kind, static_cast<int>(tok.lexeme.size()), tok.lexeme.data());
}
```

See [`docs/design.dox`](docs/design.dox) for the complete C++ API (`lexer`, `token`, `position`, `layout`, `lex_error`).

## Python binding

An abi3 CPython extension (CPython 3.11+, Limited API).

```python
import scilex

lx = scilex.Lexer([
    (0, r"\s+", True),                 # whitespace (skip)
    (1, r"[0-9]+", False),             # number
    (2, r"[A-Za-z_][A-Za-z0-9_]*", False),
])
# Every mode whose DFA is exact is accelerated (5.7–18×): lx.dfa_modes_active names them;
# scilex.Lexer([...], dfa="requested") keeps the per-rule path.

# Eager
tokens = lx.tokenize("foo 42", eof=True)

# Lazy (generator)
for tok in lx.scan("foo 42"):
    print(tok.kind, tok.lexeme, tok.position)

# Text in pieces: exactly tokenize's tokens, each once no text to come can change it
stream = lx.stream()
for chunk in ("fo", "o 4", "2"):
    for tok in stream.feed(chunk):
        print(tok.lexeme)
tail = stream.finish()

# Errors with context
try:
    lx.tokenize("foo @")
except scilex.error as e:
    e.position
    e.context
```

For significant indentation:

```python
laid = scilex.Layout().apply(lx.tokenize(src, eof=True))
```

`pip install scilex` (wheels + sdist). Use `scilex.get_include()` to compile C++ code against the installed headers.

Build locally: `make python && make python-test`.

## Contextual lexing — modes

A flat rule list can't separate contexts where the *same* byte means different
things — `{` opens a Python f-string interpolation but a dict elsewhere; `<` opens
an XML tag in content but is just a character inside CDATA. SciLex handles this with
an opt-in **mode stack**: a rule may be restricted to named modes (`in_mode`) and
may push / pop / set the mode when it wins. The engine is unchanged — maximal munch
and the exact first-byte dispatch simply run *per mode*.

This unlocks, with no engine change:

- **f-strings** — `f"sum={a+b}"`: code ↔ string body ↔ interpolation, nesting
  through the stack;
- **XML** — `content ↔ tag` (a shallow two-mode flip; CDATA and comments are single
  regex tokens, so an inner `<` is literal);
- **YAML** — `block ↔ flow` (significant indentation plus flow collections).

```cpp
using op = scilex::mode_action::op;
scilex::rule open {.kind = OPEN, .pattern = real::regex("f\"")};
open.in_mode = {"default", "interp"};                      // active in code
open.action  = {.operation = op::push, .target = "fstr"};  // enters the f-string body
// "{" pushes "interp"; the closing quote pops "fstr"; the stack tracks nesting.
```

```python
NAME, OPEN, TEXT, LB, RB, CLOSE = range(6)
fstr = scilex.Lexer([
    (NAME, r"[a-z]+", False, ["default", "interp"]),               # code, shared
    (OPEN, r'f"', False, ["default", "interp"], ("push", "fstr")),
    (TEXT, r'[^{}"]+', False, ["fstr"]),
    (LB, r"\{", False, ["fstr"], ("push", "interp")),         # "{" opens it from the body
    (CLOSE, r'"', False, ["fstr"], ("pop",)),
    (RB, r"\}", False, ["interp"], ("pop",)),
])
[t.kind for t in fstr.tokenize(r'f"hi {name}"')]   # OPEN TEXT LB NAME RB CLOSE
```

An action is `None` | `("push", mode)` | `("set", mode)` | `("pop",)`; a plain
`(kind, pattern, skip)` rule needs neither field, so existing grammars are
unaffected. See `examples/python.hpp`, `examples/xml.hpp`, `examples/yaml.hpp` for
the three modal profiles in full. The stack is bounded: a push past
`scilex::max_mode_depth` (65 536 frames, ~2 MiB) is a lexical error under either error
policy, so an input made only of openers cannot grow it without end.

## DFA fast path (automatic)

Every mode is accelerated by a `real::dfa` where that is exact: instead of trying each candidate rule at
every position, one DFA pass recognizes the winning rule — the same maximal munch,
with the order tie-break baked into the automaton. On a mode where many rules share
leading bytes that is **5.7–18× the regular path** on the full token path of the example grammars.

```cpp
scilex::lexer lexer(std::move(rules));   // dfa_policy::automatic: every mode is tried
lexer.dfa_modes_active();                // the modes actually accelerated
// Only some modes, or none: dfa_policy::requested with the names (empty = the per-rule path).
scilex::lexer pike(std::move(other_rules), {}, {}, scilex::error_policy::raise,
                   scilex::column_unit::bytes, scilex::dfa_policy::requested);
```

It is **best-effort and invisible**: a rule that needs a zero-width assertion no DFA can
represent, or whose DFA would change an answer, silently stays on the regular Pike engine
beside its mode's DFA (`pike_rules(mode)` names it). A DFA takes each rule's *longest* match
while Pike takes the match the rule's priority order prefers, and which rules keep the
two equal is not visible in the syntax: `as|assert` stops at `as` on "assert" and so
stays on Pike, while the lazy `x*?y` agrees on every input and keeps it. The
constructor **decides** this for every rule with `real::dfa_faithful` — exactly, not by
sampling — so the **token stream is byte identical** either way (Pike is the floor) and
`layout` is unchanged. The DFA is built once, in the
constructor, and that is its cost: measured 2026-09-27 (arm64, `-O2`, minimum of 7, REAL
`2026.9.9`), building the example grammars' lexers takes 0.06–2.9 ms instead of 0.01–0.12 ms, and the
Python grammar's five modes ~13.5 ms (~26 ms against REAL `2026.9.8` and ~140 ms against `2026.9.6`,
whose DFA constructions were slower). A caller that builds many short-lived lexers can pass
`dfa_policy::requested`. From Python: `Lexer(..., dfa="requested")`.

## Unicode identifiers vs DFA speed — the grammar author's choice

A real trade-off worth stating plainly. Write an identifier rule as `\w+` (or `[^\W\d]\w*`)
with the default flags and it reads **Unicode identifiers** — `café`, `変数` — the faithful
behaviour for a language like Python 3. But a Unicode `\w` expands into more UTF-8 byte
transitions than a DFA is built from, and `\b` is a zero-width assertion no DFA represents, so a
rule holding either **stays on the general engine** beside its mode's DFA (same tokens, visible via
`pike_rules(mode)`). The narrower Unicode `\d` and `\s` expand and stay on the DFA. Concretely the
general engine runs at **~7–14 MB/s** while every shipped grammar runs wholly on the DFA at **5.7–18×
that** on arm64 (8.6–27.5× on x86-64, where Pike reads lower); the `python-unicode` grammar, whose
identifier rule stays on Pike, runs at 34.7 MB/s against 10.4 MB/s for Pike alone (3.3×; 2026-09-24,
arm64, `-O2`, 256 KiB, BENCHMARKS.md) — the Unicode identifier costs part of the DFA.

So: if your identifiers are ASCII by specification (JSON, SQL, C), pin **`(?a)`** inline in the
pattern (or pass `real::flags::ascii`) to keep `\w \d \s \b` ASCII, small, and DFA-representable —
what the `examples/` grammars do. If you want Unicode identifiers, write `\w+` and accept that its
rule runs on the general engine. The two tokenize ASCII input identically; they differ only on non-ASCII input
and on whether the mode can be a DFA. The **`python-unicode`** example (`scilex --example
python-unicode`) is the faithful-Python-3 variant of `python`, identical but for that one rule.

## Thread safety

A lexer is immutable once built. Its DFAs are built in the constructor, and every
`tokenize` call and every `scan` range keeps its own mode stack and walk memos, so one
`const` lexer can be shared by any number of threads, each lexing its own text —
checked under ThreadSanitizer with eight threads over four grammars, the hybrid ones
included. An iterator from `scan` and a stream from `stream()` are cursors: drive each
from a single thread. Rules left on Pike (`pike_rules(mode)`) call `real::regex`, whose
lazy DFAs each thread leases from the regex's own pool, so they take no lock. In Python,
`scan` and a stream's `feed` hold the GIL for each call while `tokenize` releases it
around inputs of 4 KB or more.

## Layout Awareness (Level A)

The layout pass is positional, and by default mode-blind. **Layout Awareness Level
A** lets a mode be marked *insignificant* (`Lexer(insignificant_modes=…)`), so its
tokens pass through without shaping indentation — and every token carries its `mode`
(`Token.mode`) for the pass to read.

That lifts two real cases a decoupled positional pass otherwise gets wrong:

- **YAML multi-line flow** — `[\n  1,\n  2\n]` adds no spurious INDENT/DEDENT;
- **Python implicit continuation** — a call/list/dict wrapped across lines inside
  `()` `[]` `{}` reads as continuation, not a new block.

```python
laid = lexer.layout(lexer.tokenize(src, eof=True))   # uses the lexer's own policy
```

Two invariants hold: with **no** insignificant mode the result is byte-for-byte the
positional pass (zero cost); and the **mode** is the single source of the policy (no
per-rule flag).

**Honest scope.** Level A covers multi-line flow and implicit continuation. **Block
scalars** (`|` / `>`) and heredocs need a reference indent carried in the mode frame
— that is **Level B**, a designed next step, not yet built. The bundled grammars
*demonstrate* the features; each `examples/<lang>.hpp` header documents its own scope.

## CLI

`scilex` is a command-line lexer — `make cli` builds it, `make install` puts it on
your `PATH` (`PREFIX=`/`BINDIR=` to choose where). It has two input modes.

**Built-in grammars** — a showcase over the nine example languages (JSON, Python,
C++, SQL, CSS, Lisp, math, XML, YAML):

```console
$ scilex --list                       # the built-in grammars
$ scilex --version                    # SciLex's version and the REAL it was built with
$ scilex --example json file.json     # lex a file …
$ scilex --example python --layout    # … or its bundled sample, with INDENT/DEDENT
```

**Your own grammar** — the universal mode: bring a `.lex` file and lex anything.
A grammar is one rule per line — `name`, a tab, `regex`, then an optional tab and
space-separated options: `skip`, `in=m1,m2` (the modes the rule is active in), and
one of `push=m`, `set=m`, `pop` (`#` comments and blank lines are ignored):

```console
$ cat my.lex
WS	\s+	skip
NUMBER	[0-9]+(\.[0-9]+)?
IDENT	[A-Za-z_][A-Za-z0-9_]*
OP	<=|>=|==|!=|[-+*/%=<>]

$ echo 'x = 41 + 1' | scilex my.lex        # stdin when no file is given
IDENT	x	1:1
OP	=	1:3
NUMBER	41	1:5
OP	+	1:8
NUMBER	1	1:10
```

Output is one token per line — the kind, a tab, the lexeme, a tab, then `line:col`;
`--layout` adds the indentation tokens. A malformed grammar is reported with a
clear, positioned error (`my.lex:3: invalid regex: …`) — never a crash. See
`examples/sample.lex` for a worked file.

A modal grammar reads the same way — a string mode entered by a double quote and
left by the next one:

    WS	\s+	skip
    STRING	"	push=str
    TEXT	[^"\\]+	in=str
    ESCAPE	\\.	in=str
    END	"	in=str pop
    IDENT	[A-Za-z_]\w*

The format has one parser, in the optional header `scilex/grammar.hpp`
(`scilex::parse_grammar(text, origin)`, `scilex::load_grammar(path)`, errors as
`scilex::grammar_error` with a line and column); `scilex.hpp` does not include it,
so the lexer itself stays plain C++ rule lists (`std::vector<scilex::rule>`).
Python reaches the same parser: `scilex.parse_grammar(text)` and
`scilex.load_grammar(path)` return a `Grammar` whose `.rules` feed `Lexer`,
`.names` name each kind and `.lexer(...)` builds one; a malformed grammar raises
`scilex.GrammarError` with `.line`, `.column` and `.cause`.

## Dependencies

SciLex is header-only and depends only on REAL's headers (the package
`real-regex` on PyPI / https://github.com/RECHE23/real-regex).

By default the build looks for them in a sibling checkout:

```
~/Projects/
├── real-regex/   # REAL (https://github.com/RECHE23/real-regex)
└── scilex/       # SciLex  (uses ../real-regex/include by default)
```

Point the build elsewhere with `REAL_INCLUDE` (Makefile) or
`-DSCILEX_REAL_INCLUDE=...` (CMake) — for instance at the path printed by
`python -c "import real; print(real.get_include())"` when REAL is installed via
pip.

For CI or a reproducible build — where no on-disk layout can be assumed — fetch
REAL with CMake FetchContent instead (`make build FETCH=1`, or
`-DSCILEX_FETCH_DEPS=ON`); point it at a remote and pin a tag with
`-DSCILEX_REAL_REPO=https://… -DSCILEX_REAL_TAG=v2026.9.6`.

## Development

```bash
make test        # build and run the test suite
make coverage    # line-coverage summary + HTML report
make sanitize    # tests under AddressSanitizer + UndefinedBehaviorSanitizer
make lint        # clang-tidy
make format      # uncrustify, in place
make doc         # API reference (Doxygen) with embedded coverage
make fuzz        # libFuzzer + ASan/UBSan over the property oracle (FUZZ_TIME seconds)
make full-local-gate  # every gate, cheap first; the pre-push check
make sabotage-help    # the sabotage harness: break one thing, run one check, put it back
```

The API reference is published at <https://reche23.github.io/scilex/>.

Override the compiler with `make test CXX=g++-14`.

**Coverage bar.** SciLex holds the SciLang-stack gate — **100% on all four
dimensions** (lines, functions, regions and branches) of `include/`, enforced by
`make coverage-gate`: locally by `make full-local-gate` (Apple clang), and in CI under
Linux clang 18 on every push.

`scilex::scilex` is the CMake target — `add_subdirectory`, `FetchContent`, or an
installed config package. The config calls `find_dependency(real)`, so installing
REAL's config package alongside (on the same prefix) makes the whole chain
resolve from one `find_package`:

```cmake
# With REAL and SciLex installed under <prefix>:
find_package(scilex CONFIG REQUIRED)   # pulls in real:: transitively
target_link_libraries(app PRIVATE scilex::scilex)
```

## Releasing

`make release` computes the next calendar version `YYYY.M.PATCH` (the patch resets
each month; PEP 440 drops leading zeros). The pushed tag drives the release workflow
— wheels + sdist + the API-reference tarball + a GitHub Release, published via Trusted
Publishing — while `docs.yml` deploys the reference to GitHub Pages.

## Design

A guided tour of how SciLex works (maximal munch, REAL foundation, layout,
C++/Python API, current scope) lives in
[`docs/design.dox`](docs/design.dox) (also rendered by `make doc`).

## Performance

See [BENCHMARKS.md](BENCHMARKS.md). In C++ the example grammars lex at 66–134 MB/s on their DFAs
(arm64, `-O2`); through the Python binding SciLex is 1.3–1.9× faster than `re` on the benign case
measured there, and ahead of Pygments and tree-sitter on the two corpora of the cross-tool table; on
a ReDoS pattern SciLex stays linear while `re` explodes. flex, a code generator, remains ~5–7× faster.

**Linear on the DFA; the worst case is quadratic, and only on Pike.** Every rule match is linear in
the text it scans, but at each token start every candidate rule is tried, and a rule may scan far past
the token that finally wins: `a*b` and `a` on `aaa…` scan to the end looking for `b` at every
position, then lose to `a`. On the DFA each walk is memoized over the whole source (Reps, 1998): a
state a walk proved leads to no accept stops every later walk that reaches it, so the rules on the DFA
cost O(n × states) in total. A rule the DFA cannot take (see *DFA fast path*) keeps the per-position
scan, and the worst case with it. Measured on 2026-09-24 (arm64, Apple clang 16, `-O2`): `a*b` and `a` on `aaa…`, both on the DFA, lex 256 KiB in 8.8 ms and double with the input; the same pair kept on Pike (`dfa_policy::requested`) still quadruples per doubling, 266 ms at 4 000 bytes and 16.9 s at 32 000 (2026-09-23). The shipped grammars stay linear (flat MB/s in
[BENCHMARKS.md](BENCHMARKS.md)); a grammar fed by users (`.lex` files) reaches the worst case only
through a rule left on Pike (`pike_rules(mode)` names them). See [`docs/spec.dox`](docs/spec.dox).

## License

MIT — see [LICENSE](LICENSE).

## Author

René Chenard
