automaton

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

README.org (2729B)

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