How c0stya/trre works
Project Type and Purpose
• TRRE is a command‐line tool in C that extends regular expressions into “transductive” regexes (pattern‐to‐pattern transformations).
• It ships two main executables:
– trre (non‐deterministic FST engine, from trre_nft.c)
– trre_dft (deterministic FST engine, from trre_dft.c)
• It compiles with a simple Makefile; has a man page (trre.1), examples, test script (test.sh), and supporting theory docs.
File Structure
• Top‐level artifacts:
– Source: trre_nft.c, trre_dft.c
– Build: Makefile, test.sh
– Documentation: README.md, trre.1, docs/
– License: LICENSE
• No separate “lib” or “frontend/backend”—this is a monolith CLI but with two modes (NFT vs DFT).
• Key runtime config: command‐line flags (-m, -a) drive “match” vs “scan” modes and “all outputs” vs “first output.”
Extract Architectural Insights from README
• Core engine constructs a Finite State Transducer (FST) from a TRRE grammar.
• Two paths:
– NFT path: build non‐deterministic transducer and execute directly (backtracking).
– DFT path: optionally determinize to a DFT (exponential in worst case) then execute in linear time.
• Grammar processing uses a Shunting‐Yard‐style parser (implied), then FST builder, then execution engine.
Main Components and Their Relationships
a. CLI Interface (main entry point)
• Parses arguments, loads TRRE expression and input stream.
b. Parser / GRAMMAR Engine
• Lexes & parses the TRRE expression into an AST or intermediate form.
c. FST Builder
• Translates parsed TRRE AST into an FST (NFT).
d. Determinizer (optional)
• Runs the NFTs through the DFT conversion algorithm (Allauzen–Mohri style).
e. Execution Engine
• Feeds input text (stdin or file) through the selected FST/DFT to produce output(s).
f. Output Formatter
• Applies modes: scan vs full-match, first vs all results, writes to stdout.
g. Test Harness (test.sh) & Docs (docs/, trre.1)
• Not runtime components, but important for CI/build.
Interactions:
CLI → Parser → FST Builder → {Determinizer?} → Execution Engine → Output
Key Architectural Patterns / Principles
• Pipeline Pattern: clear stages—parse → build → (determinize) → execute.
• Strategy Pattern: switchable execution strategies (NFT vs DFT).
• Modular Monolith: distinct C modules but compiled into two binaries.
• Single Responsibility: parser only handles grammar, builder only constructs automata.
Elements
• stdin / regex expression → CLI
• CLI
– Argument Parser (flags: −m, −a)
– Dispatch to Parser.
• Parser Module
– Outputs AST
• FST Builder Module
– Produces NFT
• Determinization Module (optional)
– Consumes NFT, outputs DFT
• Execution Engine
– NFT Executor or DFT Executor
– Modes: scan vs match, first vs all
• stdout (result strings)