#[macro_use]
extern crate pest;
#[macro_use]
extern crate pest_derive;
extern crate rand;
use std::cell::RefCell;
use std::rc::Rc;
use std::fs::File;
use std::io::prelude::*;
use std::fmt;
use std::fmt::Write;
use std::collections::HashMap;
use pest::Parser;
use pest::error::Error;
use pest::iterators::Pair;
use rand::prelude::*;
#[derive(Parser)]
#[grammar = "grammar.pest"]
pub struct PseudocodeParser;
pub struct Program {
instructions: Vec<Instruction>
}
impl Program {
fn new(insts: Vec<Instruction>) -> Self {
Program{
instructions: insts,
}
}
}
#[derive(Clone, Debug)]
pub enum Op {
NEQ,
EQ,
GT,
LT,
GTE,
LTE,
MULT,
DIV,
PLUS,
MINUS,
MOD
}
#[derive(Clone, Debug)]
pub enum Expr {
ProcedureCall(String, Vec<Expr>),
Number(f64),
String(String),
Boolean(bool),
Identifier(String),
BinaryExpr(Box<Expr>, Op, Box<Expr>),
Negate(Box<Expr>),
Not(Box<Expr>),
}
#[derive(Clone, Debug)]
pub enum Instruction {
ProcedureDef(String, Vec<String>, Vec<Instruction>),
RepeatUntilBlock(Expr, Vec<Instruction>),
RepeatTimes(Expr, Vec<Instruction>),
ForEach(String, Expr, Vec<Instruction>),
IfSelection(Expr, Vec<Instruction>),
IfElseSelection(Expr, Vec<Instruction>, Vec<Instruction>),
ReturnStmt(Expr),
DisplayStmt(Expr),
ProcedureCall(String, Vec<Expr>),
Assignment(String, Expr)
}
#[derive(Clone, Debug)]
pub enum Value {
Number(f64),
String(String),
Boolean(bool)
}
impl fmt::Display for Value {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Value::Number(val) => write!(f, "{}", val),
Value::String(val) => write!(f, "{}", val),
Value::Boolean(val) => write!(f, "{}", val),
}
}
}
pub struct Procedure {
arglist: Vec<String>,
body: Vec<Instruction>,
native: Option<Box<dyn Fn(Rc<RefCell<Scope>>) -> Result<Vec<Instruction>, String>>>
}
impl Procedure {
fn new(arglist: Vec<String>, body: Vec<Instruction>, native: Option<Box<dyn Fn(Rc<RefCell<Scope>>) -> Result<Vec<Instruction>, String>>>) -> Self {
Procedure { arglist: arglist, body: body, native: native}
}
}
fn call_proc(scope: Rc<RefCell<Scope>>, name: String, args: Vec<Expr>, output: Rc<RefCell<String>>) -> Result<Option<Value>, String> {
if let Some(proc) = scope.clone().borrow().procedures.get(&name) {
let func_scope = Rc::new(RefCell::new(Scope::new(scope.clone())));
for (idx, varname) in proc.arglist.iter().enumerate() {
let expr = &args[idx];
func_scope.borrow_mut().variables.insert(varname.to_string(), expr.eval(scope.clone(), output.clone())?);
}
if let Some(native_impl) = &proc.native {
let instructions = native_impl(func_scope.clone())?;
run_instructions(instructions, func_scope, output.clone())
} else {
run_instructions(proc.body.clone(), func_scope, output.clone())
}
} else {
Err(format!("No procedure named {}", name))
}
}
pub struct Scope<'a> {
variables: HashMap<String, Value>,
procedures: HashMap<String, Procedure>,
parent: Option<Rc<RefCell<Scope<'a>>>>,
}
impl<'a> Scope<'a> {
fn new(parent: Rc<RefCell<Scope<'a>>>) -> Self {
Scope {
variables: HashMap::new(),
procedures: HashMap::new(),
parent: Some(parent),
}
}
fn new_base_scope() -> Self {
let mut s = Scope {
variables: HashMap::new(),
procedures: HashMap::new(),
parent: None,
};
let random_func = Procedure::new(vec!["a".to_string(), "b".to_string()], vec![], Some(Box::new(|scope| {
let mut rng = rand::thread_rng();
let a = scope.borrow().resolve("a".to_string()).ok_or("a is undefined")?;
let b = scope.borrow().resolve("b".to_string()).ok_or("a is undefined")?;
let val = match (a, b) {
(Value::Number(a), Value::Number(b)) => {
rng.gen_range(a as i64, (b as i64)+1)
},
_ => {
return Err("a and b most both be integers".to_string())
}
};
Ok(vec![
Instruction::ReturnStmt(Expr::Number(val as f64)),
])
})));
s.procedures.insert("RANDOM".to_string(), random_func);
let concat_func = Procedure::new(vec!["a".to_string(), "b".to_string()], vec![], Some(Box::new(|scope| {
let a = scope.borrow().resolve("a".to_string()).ok_or("a is undefined")?;
let b = scope.borrow().resolve("b".to_string()).ok_or("a is undefined")?;
let val = match (a, b) {
(Value::String(a), Value::String(b)) => {
format!("{}{}", a, b)
},
_ => {
return Err("a and b most both be strings".to_string())
}
};
Ok(vec![
Instruction::ReturnStmt(Expr::String(val)),
])
})));
s.procedures.insert("CONCAT".to_string(), concat_func);
return s
}
fn define_proc(&mut self, name: String, arglist: Vec<String>, body: Vec<Instruction>) {
self.procedures.insert(name, Procedure::new(arglist, body, None));
}
fn defined_in_parent(&self, ident: &String) -> bool {
if let Some(parent_scope) = &self.parent {
if parent_scope.borrow().variables.contains_key(ident) {
return true
} else {
parent_scope.borrow().defined_in_parent(ident)
}
} else {
false
}
}
fn assign(&mut self, ident: String, value: Value) {
if self.defined_in_parent(&ident) {
if let Some(parent_scope) = &self.parent {
parent_scope.borrow_mut().assign(ident, value);
}
} else {
self.variables.insert(ident, value);
}
}
fn resolve(&self, ident: String) -> Option<Value> {
match self.variables.get(&ident) {
Some(val) => Some(val.clone()),
None => match &self.parent {
Some(parent_scope) => parent_scope.borrow().resolve(ident),
None => None
}
}
}
fn dump(&self) {
println!("### DUMPING SCOPE ###");
for (var, val) in self.variables.iter() {
println!("{} => {:?}", var, val);
}
}
}
impl Expr {
fn eval(&self, scope: Rc<RefCell<Scope>>, output: Rc<RefCell<String>>) -> Result<Value, String> {
match self {
Expr::Number(val) => Ok(Value::Number(*val)),
Expr::String(val) => Ok(Value::String(val.clone())),
Expr::Boolean(val) => Ok(Value::Boolean(val.clone())),
Expr::Identifier(ident) => match scope.borrow().resolve(ident.to_string()) {
Some(val) => Ok(val),
None => Err(format!("Variable {} is not defined", ident))
},
Expr::Negate(expr) => {
let val = expr.eval(scope.clone(), output.clone())?;
match val {
Value::Number(n) => Ok(Value::Number(-n)),
_ => Err(format!("Value {} must be a number", val))
}
},
Expr::Not(expr) => {
let val = expr.eval(scope.clone(), output.clone())?;
match val {
Value::Boolean(n) => Ok(Value::Boolean(!n)),
_ => Err(format!("Value {} must be a boolean value but was a {:?}", val, val))
}
},
Expr::BinaryExpr(lhs, op, rhs) => {
let lhsval = lhs.eval(scope.clone(), output.clone())?;
let rhsval = rhs.eval(scope.clone(), output.clone())?;
match op {
Op::PLUS => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Number(f1 + f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must both be numbers", lhsval, rhsval))
}
}
},
Op::MINUS => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Number(f1 - f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must both be numbers", lhsval, rhsval))
}
}
},
Op::MULT => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Number(f1 * f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must both be numbers", lhsval, rhsval))
}
}
},
Op::DIV => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Number(f1 / f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must both be numbers", lhsval, rhsval))
}
}
},
Op::MOD => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Number(f1 % f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must both be numbers", lhsval, rhsval))
}
}
},
Op::EQ => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Boolean(f1 == f2))
},
(Value::String(f1), Value::String(f2)) => {
Ok(Value::Boolean(f1 == f2))
},
(Value::Boolean(f1), Value::Boolean(f2)) => {
Ok(Value::Boolean(f1 == f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must be same type", lhsval, rhsval))
}
}
},
Op::NEQ => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Boolean(f1 != f2))
},
(Value::String(f1), Value::String(f2)) => {
Ok(Value::Boolean(f1 != f2))
},
(Value::Boolean(f1), Value::Boolean(f2)) => {
Ok(Value::Boolean(f1 != f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must be same type", lhsval, rhsval))
}
}
},
Op::GT => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Boolean(f1 > f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must be same type", lhsval, rhsval))
}
}
},
Op::LT => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Boolean(f1 < f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must be same type", lhsval, rhsval))
}
}
},
Op::GTE => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Boolean(f1 >= f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must be same type", lhsval, rhsval))
}
}
},
Op::LTE => {
match (&lhsval, &rhsval) {
(Value::Number(f1), Value::Number(f2)) => {
Ok(Value::Boolean(f1 <= f2))
},
(_, _) => {
Err(format!("{:?} and {:?} must be same type", lhsval, rhsval))
}
}
},
}
},
Expr::ProcedureCall(procname, arglist) => {
let value = call_proc(scope.clone(), procname.to_string(), arglist.clone(), output.clone())?;
if let Some(value) = value {
Ok(value)
} else {
Ok(Value::Number(-1.0))
}
}
}
}
}
pub fn parse_op(pair: Pair<Rule>) -> Op {
let op = pair.into_inner().next().unwrap();
match op.as_rule() {
Rule::neq => Op::NEQ,
Rule::eq => Op::EQ,
Rule::gt => Op::GT,
Rule::lt => Op::LT,
Rule::gte => Op::GTE,
Rule::lte => Op::LTE,
Rule::mult => Op::MULT,
Rule::div => Op::DIV,
Rule::plus => Op::PLUS,
Rule::minus => Op::MINUS,
Rule::modop => Op::MOD,
_ => { panic!("{:#?} is unknown", op); }
}
}
fn parse_value_inner(val: Pair<Rule>) -> Expr {
match val.as_rule() {
Rule::procedure_call => {
let mut block = val.into_inner();
let ident = block.next().unwrap().as_str().to_string();
let arg_list: Vec<Expr> = block.next().unwrap().into_inner().map(parse_expr).collect();
Expr::ProcedureCall(ident, arg_list)
},
Rule::number => {
let val: f64 = val.as_str().parse().unwrap();
Expr::Number(val)
},
Rule::string => {
Expr::String(val.into_inner().next().unwrap().as_str().to_string())
},
Rule::boolean => {
Expr::Boolean(val.as_str() == "true")
},
Rule::identifier => {
Expr::Identifier(val.as_str().trim().to_string())
},
Rule::expression => {
parse_expr(val)
},
_ => {
println!("other value {:?}", val);
Expr::Number(0.0)
}
}
}
pub fn parse_value(pair: Pair<Rule>) -> Expr {
let mut block = pair.into_inner();
let val = block.next().unwrap();
match val.as_rule() {
Rule::prefix_op => {
let inner_val = parse_value_inner(block.next().unwrap());
match val.into_inner().next().unwrap().as_rule() {
Rule::minus => Expr::Negate(Box::new(inner_val)),
Rule::not => Expr::Not(Box::new(inner_val)),
_ => unreachable!()
}
}
_ => parse_value_inner(val)
}
}
pub fn parse_expr(pair: Pair<Rule>) -> Expr {
match pair.as_rule() {
Rule::value => parse_value(pair),
Rule::expression => {
let mut parts = pair.into_inner();
let mut lhs = parse_expr(parts.next().unwrap());
while let Some(_) = parts.peek() {
let op = parse_op(parts.next().unwrap());
let rhs = parse_expr(parts.next().unwrap());
lhs = Expr::BinaryExpr(Box::new(lhs), op, Box::new(rhs));
}
return lhs;
},
_ => {
println!("other {:?}", pair);
Expr::Number(0.0)
}
}
}
pub fn parse_block(block: Pair<Rule>) -> Vec<Instruction> {
let mut instructions: Vec<Instruction> = Vec::new();
for inst in block.into_inner() {
let bi = inst.into_inner().next().unwrap();
match bi.as_rule() {
Rule::selection_block => {
if let Some(sel_block) = parse_selection(bi) {
instructions.push(sel_block);
}
},
Rule::assignment => {
let mut block = bi.into_inner();
let ident = block.next().unwrap().as_str().trim().to_string();
block.next();
let expr = block.next().unwrap();
instructions.push(Instruction::Assignment(ident, parse_expr(expr)));
},
Rule::return_statement => {
let expr = parse_expr(bi.into_inner().next().unwrap());
instructions.push(Instruction::ReturnStmt(expr));
}
Rule::display => {
let expr = parse_expr(bi.into_inner().next().unwrap());
instructions.push(Instruction::DisplayStmt(expr));
}
_ => {
println!("other {:?}", bi);
}
}
}
return instructions;
}
pub fn parse_selection(sel: Pair<Rule>) -> Option<Instruction> {
let inst = sel.into_inner().next().unwrap();
match inst.as_rule() {
Rule::if_expr => {
let mut block = inst.into_inner();
let cond_expr = parse_expr(block.next().unwrap());
let cond_inst = parse_block(block.next().unwrap());
Some(Instruction::IfSelection(cond_expr, cond_inst))
},
Rule::if_else_expr => {
let mut block = inst.into_inner();
let cond_expr = parse_expr(block.next().unwrap());
let cond_inst = parse_block(block.next().unwrap());
let else_inst = parse_block(block.next().unwrap());
Some(Instruction::IfElseSelection(cond_expr, cond_inst, else_inst))
},
_ => { None }
}
}
pub fn parse_prog(prog: &str) -> Result<Program, Error<Rule>> {
let parsed = PseudocodeParser::parse(Rule::program, prog)?;
let mut instructions: Vec<Instruction> = Vec::new();
for inst in parsed {
match inst.as_rule() {
Rule::selection_block => {
if let Some(sel_block) = parse_selection(inst) {
instructions.push(sel_block);
}
},
Rule::iteration_block => {
let block = inst.into_inner().next().unwrap();
match block.as_rule() {
Rule::repeat_until => {
let mut ib = block.into_inner();
let expr = parse_expr(ib.next().unwrap());
let inst = parse_block(ib.next().unwrap());
instructions.push(Instruction::RepeatUntilBlock(expr, inst));
},
Rule::repeat_times => {
let mut ib = block.into_inner();
let times = parse_expr(ib.next().unwrap());
let inst = parse_block(ib.next().unwrap());
instructions.push(Instruction::RepeatTimes(times, inst));
},
Rule::for_each => {
let mut ib = block.into_inner();
let ident = ib.next().unwrap().as_str().trim().to_string();
let expr = parse_expr(ib.next().unwrap());
let inst = parse_block(ib.next().unwrap());
instructions.push(Instruction::ForEach(ident, expr, inst));
},
_ => {
println!("other {:?}", block);
}
}
},
Rule::procedure_def => {
let mut block = inst.into_inner();
let proc_name = block.next().unwrap().as_str().to_string();
let arg_list: Vec<String> = block.next().unwrap().into_inner().map(|pair|
pair.as_str().to_string()
).collect();
let proc_list = parse_block(block.next().unwrap());
instructions.push(Instruction::ProcedureDef(proc_name, arg_list, proc_list));
},
Rule::assignment => {
let mut block = inst.into_inner();
let ident = block.next().unwrap().as_str().trim().to_string();
block.next();
let expr = block.next().unwrap();
instructions.push(Instruction::Assignment(ident, parse_expr(expr)));
},
Rule::display => {
let inner = inst.into_inner().next().unwrap();
let expr = parse_expr(inner);
instructions.push(Instruction::DisplayStmt(expr));
}
Rule::expression => {
let inner = inst.into_inner().next().unwrap().into_inner().next().unwrap();
match inner.as_rule() {
Rule::procedure_call => {
let mut call = inner.into_inner();
let ident = call.next().unwrap().as_str().trim().to_string();
let arg_list: Vec<Expr> = call.next().unwrap().into_inner().map(parse_expr).collect();
instructions.push(Instruction::ProcedureCall(ident, arg_list));
},
_ => {}
}
println!("other");
},
_ => {
println!("skipping {:?}", inst);
}
}
}
Ok(Program::new(instructions))
}
fn run_instructions(instructions: Vec<Instruction>, scope: Rc<RefCell<Scope>>, output: Rc<RefCell<String>>) -> Result<Option<Value>, String> {
let mut return_value: Option<Value> = None;
for instruction in instructions.iter() {
match instruction {
Instruction::ProcedureDef(name, arglist, block) => {
scope.borrow_mut().define_proc(name.to_string(), arglist.to_vec(), block.to_vec());
},
Instruction::RepeatUntilBlock(expr, block) => {
loop {
if let Value::Boolean(doloop) = expr.eval(scope.clone(), output.clone())? {
if !doloop {
run_instructions(block.to_vec(), scope.clone(), output.clone())?;
} else {
break
}
}
}
},
Instruction::RepeatTimes(expr, block) => {
if let Value::Number(ntimes) = expr.eval(scope.clone(), output.clone())? {
for _ in 0..(ntimes as u64) {
run_instructions(block.to_vec(), scope.clone(), output.clone())?;
}
}
},
Instruction::IfSelection(cond, block) => {
if let Value::Boolean(expr) = cond.eval(scope.clone(), output.clone())? {
if expr {
run_instructions(block.to_vec(), scope.clone(), output.clone())?;
}
}
},
Instruction::IfElseSelection(cond, block, elseblock) => {
if let Value::Boolean(expr) = cond.eval(scope.clone(), output.clone())? {
if expr {
run_instructions(block.to_vec(), scope.clone(), output.clone())?;
} else {
run_instructions(elseblock.to_vec(), scope.clone(), output.clone())?;
}
}
},
Instruction::ProcedureCall(procname, arglist) => {
return_value = call_proc(scope.clone(), procname.to_string(), arglist.clone(), output.clone())?;
}
Instruction::DisplayStmt(expr) => {
let value = expr.eval(scope.clone(), output.clone())?;
write!(&mut output.borrow_mut(), "{} ", value);
},
Instruction::Assignment(ident, expr) => {
let value = expr.eval(scope.clone(), output.clone())?;
scope.borrow_mut().assign(ident.to_string(), value);
},
Instruction::ReturnStmt(expr) => {
let value = expr.eval(scope.clone(), output.clone())?;
return_value = Some(value);
}
_ => {
println!("ignoring {:?}", instruction)
}
}
}
Ok(return_value)
}
pub fn eval(prog: &str) -> Result<String, String> {
let output = Rc::new(RefCell::new(String::new()));
match parse_prog(prog) {
Ok(program) => {
let scope = Rc::new(RefCell::new(Scope::new_base_scope()));
run_instructions(program.instructions, scope.clone(), output.clone())?;
(*scope.borrow()).dump();
Ok(output.borrow().to_string())
},
Err(err) => Err(err.to_string())
}
}
pub fn eval_file(filename: &str) -> Result<String, String> {
let mut file = File::open(filename).expect("Problem opening file");
let mut prog = String::new();
file.read_to_string(&mut prog).expect("Problem reading file");
eval(&prog)
}
#[cfg(test)]
mod tests {
use super::*;
use pest::parses_to;
macro_rules! map(
{ $($key:expr => $value:expr),+ } => {
{
let mut m = ::std::collections::HashMap::new();
$(
m.insert($key, $value);
)+
m
}
};
);
#[test]
fn test_parse() {
let success = PseudocodeParser::parse(Rule::program, "abc 🠐 3.0").unwrap();
println!("{:?}", success);
}
#[test]
fn test_parse_binary_expr() {
let success = PseudocodeParser::parse(Rule::expression, "(3 * 2) < (4 * 10.3)").unwrap();
println!("{:?}", success);
}
#[test]
fn test_parse_assignment_expr() {
let success = PseudocodeParser::parse(Rule::expression, "a 🠐 1 + 2").unwrap();
println!("{:#?}", success);
}
#[test]
fn test_file_output() -> Result<(), String> {
let file_output = map!(
"test_programs/assignment.ap" => "a is 3 b is 10.5 string_val is hello",
"test_programs/expr.ap" => "1 2 3 4 5 6 7 8 9 10",
"test_programs/loops.ap" => "1 2 3 x is even 2 x is odd 3 x is even 4 x is odd 5",
"test_programs/procedure.ap" => "inside did func work? true",
"test_programs/negate.ap" => "-1 -3 -6 -6 false true false true",
"test_programs/ops.ap" => "true false true"
);
for (file, expected_output) in file_output.iter() {
let output = eval_file(file).unwrap().trim().to_string();
assert!(output.eq(expected_output))
}
Ok(())
}
#[test]
fn test_parses_to() {
parses_to! {
parser: PseudocodeParser,
input: "my_variable",
rule: Rule::identifier,
tokens: [identifier(0, 11)]
}
parses_to! {
parser: PseudocodeParser,
input: "\"hello world\"",
rule: Rule::string,
tokens: [string(0, 13, [inner(1, 12)])]
}
}
}