automaton

An automaton library & basic programs written in Rust
git clone git://git.ethandl.dev/automaton
Log | Files | Refs | README

README (2740B)

      1 A toy finite state automaton library & utilities built with Rust
      2 ================================================================
      3 
      4 What is this?
      5 =============
      6 This is just a toy project that I've been working on to test my knowledge of
      7 COMP1600 topics (a course at the ANU). It's a very basic library for Rust that
      8 currently implements only the finite state automaton described in COMP1600.
      9 
     10 What is currently implemented:
     11 ==============================
     12  * ε-NFAs
     13  * NFAs
     14  * DFAs
     15  * Deterministic wildcard transitions for all automata, any input not in the
     16    alphabet (DFA) or with explicit transitions (NFA) follows the wildcard
     17    transition.
     18  * Regular expressions with a bit of sugar
     19    - Current operators are `*`, `+`, `?`, `.`, and `|`.
     20    - The following escape sequences: `\*`, `\+`, `\?`, `\.`, `\|`, `\(`, `\)`,
     21      and `\\` to map to the characters that are reserved.
     22    - Implemented with an LL(1) predictive recursive descent parser.
     23      + Correct me if I'm wrong on this
     24  * A WASM compilation target with accompanying TypeScript library for use with
     25    Node/Bun & in the browser.
     26  * A basic demo website of the regex engine and parser.
     27 
     28 Goals:
     29 ======
     30  - Publish demo to a static page. (Done!)
     31  - Rewrite the JSON parsing for DFA, NFA, and ENFA to accept wildcard transitions.
     32  - Write tests until I'm satisfied that everything is mostly okay.
     33  - Implement Turing automaton.
     34  - Implement step-through acceptance rendering.
     35 
     36 How do I run it?
     37 ================
     38 Currently there are no prebuilt binaries beyond the WASM/JavaScript package in `/web/pkg`.
     39 
     40 To build the project, you need cargo and rust. I suggest `rustup`.
     41 
     42     cargo build --release
     43 
     44 Then to run the binaries:
     45 
     46     cargo run --release --bin <BINNAME> <ARGS>
     47 
     48 For a quick start, just run the `regex` binary:
     49 
     50     cargo run --release --bin regex <REGEX> <INPUT>
     51 
     52 The regular expression engine will just build an automaton to match input
     53 strings, either accepting or rejecting the input string `<INPUT>`.
     54 
     55 If you want to work directly with the automaton binaries, they accept a path to
     56 a JSON file describing the automaton. See the `DFAs`, `ENFAs`, and `NFAs`
     57 directory. _NOTE: The JSON spec was made before a lot of changes involving the
     58 wildcard transition, so it doesn't yet support that._
     59 
     60 If you want to work with the automaton as a library, there is a simple
     61 `GraphENFA` with methods for building up an ε-NFA, which you can then convert to
     62 any of the other automaton.
     63 
     64 There is a web-demo available to build, this requires Bun for bundling, and
     65 cargo (note that this is already included pre-built in the repository):
     66 
     67       cd web && bun i && bun run build
     68 
     69 If you don't want to run the demo, simply go to
     70 http://ethandl.dev/projects/dfa-regex-engine/demo/