commit 90495df5b4ba97eb181a956c2d3d070ae701651b
parent 7c0cd0f61d3dfd0412fc5217634b75d2cd7627dd
Author: Ethan Long <ethandavidlong@gmail.com>
Date: Mon, 27 Nov 2023 21:17:31 +1100
Yeah the boys
We're reworking the structure of this to add more finite automaton.
Diffstat:
4 files changed, 204 insertions(+), 205 deletions(-)
diff --git a/src/bin/dfa.rs b/src/bin/dfa.rs
@@ -0,0 +1,201 @@
+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();
+
+ 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!")))?;
+
+ let dfa: DFA = DFA::parse_dfa(&dfa_json)?;
+ println!("DFA: {dfa}");
+ println!("Running on the following input:\n{input_string}");
+ println!("Accepts: {}", dfa.run_dfa(input_string));
+
+ Ok(())
+}
+
+
+impl Display for DFA {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ let alphabet_str: String = self.alphabet.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.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.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.iter().cloned().collect();
+ let alphabet_map: HashMap<char, usize> = alphabet_vec.iter().enumerate().map(|(index, char)| {
+ (char.to_owned(), index)
+ }).collect();
+
+ let mut transition_table_hdr: String = alphabet_vec.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.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.to_owned();
+ transition_map.insert(from.to_owned(), new_vec);
+ },
+ None => return write!(f, "ERROR!")
+ }
+ }
+
+ let transition_table_str: String = transition_map.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)
+ }
+}
diff --git a/src/bin/nfa.rs b/src/bin/nfa.rs
@@ -0,0 +1,3 @@
+fn main() {
+ println!("Hello world")
+}
diff --git a/src/lib/DFA.rs b/src/lib/DFA.rs
diff --git a/src/main.rs b/src/main.rs
@@ -1,205 +0,0 @@
-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)
- }
-}
