commit 7c0cd0f61d3dfd0412fc5217634b75d2cd7627dd
Author: Ethan Long <ethan@Ethans-MacBook-Pro.local>
Date: Sun, 26 Nov 2023 23:22:53 +1100
Got a basic DFA engine working!
Diffstat:
5 files changed, 316 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/Cargo.lock b/Cargo.lock
@@ -0,0 +1,89 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "automaton"
+version = "0.1.0"
+dependencies = [
+ "serde",
+ "serde_json",
+]
+
+[[package]]
+name = "itoa"
+version = "1.0.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "af150ab688ff2122fcef229be89cb50dd66af9e01a4ff320cc137eecc9bacc38"
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.70"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "39278fbbf5fb4f646ce651690877f89d1c5811a3d4acb27700c1cb3cdb78fd3b"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.33"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5267fca4496028628a95160fc423a33e8b2e6af8a5302579e322e4b520293cae"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "ryu"
+version = "1.0.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1ad4cc8da4ef723ed60bced201181d83791ad433213d8c24efffda1eec85d741"
+
+[[package]]
+name = "serde"
+version = "1.0.193"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "25dd9975e68d0cb5aa1120c288333fc98731bd1dd12f561e468ea4728c042b89"
+dependencies = [
+ "serde_derive",
+]
+
+[[package]]
+name = "serde_derive"
+version = "1.0.193"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "43576ca501357b9b071ac53cdc7da8ef0cbd9493d8df094cd821777ea6e894d3"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "serde_json"
+version = "1.0.108"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3d1c7e3eac408d115102c4c24ad393e0821bb3a5df4d506a80f85f7a742a526b"
+dependencies = [
+ "itoa",
+ "ryu",
+ "serde",
+]
+
+[[package]]
+name = "syn"
+version = "2.0.39"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "23e78b90f2fcf45d3e842032ce32e3f2d1545ba6636271dcbf24fa306d87be7a"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
+[[package]]
+name = "unicode-ident"
+version = "1.0.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b"
diff --git a/Cargo.toml b/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "automaton"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+serde = "1.0.193"
+serde_json = "1.0.108"
+\ No newline at end of file
diff --git a/DFAs/even_ones.dfa b/DFAs/even_ones.dfa
@@ -0,0 +1,10 @@
+{
+ "alphabet": [0, 1],
+ "states": [0, 1],
+ "initial_state": 0,
+ "final_states": [0],
+ "transition_table": [
+ [0, 0, 1],
+ [1, 1, 0]
+ ]
+}
diff --git a/src/main.rs b/src/main.rs
@@ -0,0 +1,205 @@
+use std::{collections::{HashMap,HashSet}, env, error::Error, fmt::Display, fs};
+
+struct DFA {
+ alphabet: HashSet<char>,
+ state_ids: HashSet<u64>,
+ initial_state_id: u64,
+ final_state_ids: HashSet<u64>,
+ transition_table: HashMap<(u64, char), u64>
+}
+
+#[derive(Debug)]
+struct DFAParseError {
+ reason: String
+}
+
+impl Display for DFAParseError {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "{}", self.reason)
+ }
+}
+
+impl DFAParseError {
+ fn cause(reason: &str) -> Self {
+ DFAParseError {
+ reason: reason.to_owned()
+ }
+ }
+}
+
+impl Error for DFAParseError {}
+
+#[derive(Debug)]
+struct CommandLineError {
+ reason: String
+}
+
+impl Display for CommandLineError {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "{}", self.reason)
+ }
+}
+
+impl CommandLineError {
+ fn cause(reason: &str) -> Self {
+ CommandLineError {
+ reason: reason.to_owned()
+ }
+ }
+}
+
+impl Error for CommandLineError {}
+
+fn usage(prog_name: &str) -> String {
+ format!("Usage: {prog_name} <DFA filename> <input string>")
+}
+
+fn main() -> Result<(), Box<dyn Error>> {
+ let args: Vec<String> = env::args().collect();
+ println!("Number of args: {}", args.len());
+ for arg in args.clone() {
+ println!("{}", arg);
+ }
+ if args.len() != 3 {
+ return Err(Box::new(CommandLineError::cause(&usage(args.get(0).map_or("automaton", |s| s)))));
+ }
+ let dfa_json = fs::read_to_string(args.get(1).unwrap_or(&"".to_owned()))?;
+ let input_string = args.get(2).ok_or(Box::new(CommandLineError::cause("No input string provided!")))?;
+ match DFA::parse_dfa(&dfa_json) {
+ Ok(dfa) => {
+ println!("DFA: {dfa}");
+ println!("Running on the following input:\n{input_string}");
+ println!("Accepts: {}", dfa.run_dfa(input_string));
+ },
+ Err(e) => return Err(Box::new(CommandLineError::cause(&format!("DFA was unable to be parsed: {e}"))))
+ }
+ return Ok(());
+}
+
+
+impl Display for DFA {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ let alphabet_str: String = self.alphabet.clone().into_iter().enumerate().fold("[".to_owned(), |str, (index, c)| {
+ let ending = if index == self.alphabet.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{c}{ending}")
+ });
+
+ let state_str: String = self.state_ids.clone().into_iter().enumerate().fold("[".to_owned(), |str, (index, n)| {
+ let ending = if index == self.state_ids.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{n}{ending}")
+ });
+
+ let initial_state_str: String = self.initial_state_id.to_string();
+
+ let final_state_str: String = self.final_state_ids.clone().into_iter().enumerate().fold("[".to_owned(), |str, (index, n)| {
+ let ending = if index == self.final_state_ids.len() - 1 {
+ "]"
+ } else {
+ ", "
+ };
+ format!("{str}{n}{ending}")
+ });
+
+ //let transition_table_hdr: String = "from\t|\tinput\t|\tto\n".to_owned();
+ let alphabet_vec: Vec<char> = self.alphabet.clone().into_iter().collect();
+ let alphabet_map: HashMap<char, usize> = alphabet_vec.clone().into_iter().enumerate().map(|(index, char)| {
+ (char, index)
+ }).collect();
+
+ let mut transition_table_hdr: String = alphabet_vec.into_iter().fold("\t|".to_owned(), |str, c| {
+ format!("{str}\t{c}\t|")
+ });
+ transition_table_hdr.push('\n');
+
+ let mut transition_map: HashMap<u64, Vec<u64>> = HashMap::new();
+
+ for ((from, input), to) in self.transition_table.clone().into_iter() {
+ let mut new_vec: Vec<u64> = transition_map.get(&from).unwrap_or(&vec![0 as u64; self.alphabet.len()]).to_owned();
+ match alphabet_map.get(&input) {
+ Some(new_index) => {
+ new_vec[*new_index] = to;
+ transition_map.insert(from, new_vec);
+ },
+ None => return write!(f, "ERROR!")
+ }
+ }
+
+ let transition_table_str: String = transition_map.into_iter().fold(transition_table_hdr, |str, (input, states)| {
+ let dests = states.into_iter().fold("".to_owned(), |str, dst| {
+ format!("{str}{dst}\t|\t")
+ });
+ format!("{str}{input}\t|\t{dests}\n")
+ });
+
+ write!(f, "Alphabet: {alphabet_str}\nStates: {state_str}\nInitial State: {initial_state_str}\nFinal States: {final_state_str}\nTransition Table:\n{transition_table_str}")
+ }
+}
+
+
+impl DFA {
+ fn parse_dfa(dfa_json: &str) -> Result<DFA, Box<dyn Error>> {
+ let json: serde_json::Value = serde_json::from_str(dfa_json)?;
+
+ let alphabet_vec: Vec<char> = json["alphabet"].as_array().map_or(vec![], |arr| {
+ arr.iter().filter_map(|v| v.to_string().chars().next()).collect()
+ });
+
+ let alphabet: HashSet<char> = json["alphabet"].as_array().map_or(HashSet::new(), |arr| {
+ arr.iter().filter_map(|v| v.to_string().chars().next()).collect()
+ });
+
+ let state_ids: HashSet<u64> = json["states"].as_array().map_or(HashSet::new(), |arr| {
+ arr.iter().filter_map(|v| v.as_u64()).collect()
+ });
+
+ let initial_state_id: u64 = json["initial_state"].as_u64().ok_or(Box::new(DFAParseError::cause("Initial state incorrectly formatted")))?;
+
+ let final_state_ids: HashSet<u64> = json["final_states"].as_array().map_or(HashSet::new(), |arr| {
+ arr.iter().filter_map(|v| v.as_u64()).collect()
+ });
+
+ let mut transition_table: HashMap<(u64, char), u64> = HashMap::new();
+ for row in json["transition_table"].as_array().iter().flat_map(|opt| opt.iter()) {
+ let v: Option<(u64, Vec<(u64, char)>)> = row.as_array().map_or(None, |arr| {
+ let from: u64 = arr[0].as_u64()?;
+ let to: Vec<(u64, char)> = arr[1..].into_iter().filter_map(|v| v.as_u64()).zip(alphabet_vec.clone()).collect();
+ Some((from, to))
+ });
+ match v {
+ Some((from, to)) => {
+ for (dest, input) in to.into_iter() {
+ transition_table.insert((from, input), dest);
+ }
+ },
+ None => {return Err(Box::new(DFAParseError::cause("Unable to parse DFA, incorrect types in the JSON")));}
+ }
+ }
+
+ Ok(DFA {
+ alphabet,
+ state_ids,
+ final_state_ids,
+ transition_table,
+ initial_state_id
+ })
+ }
+
+ fn run_dfa(&self, input: &str) -> bool {
+ let mut current_state_id: u64 = self.initial_state_id;
+ for c in input.chars() {
+ match self.transition_table.get(&(current_state_id, c)) {
+ Some(state) => current_state_id = state.to_owned(),
+ None => return false
+ }
+ }
+ self.final_state_ids.contains(¤t_state_id)
+ }
+}
