Forth

Предадени решения

Краен срок:
27.01.2019 17:00
Точки:
20

Срокът за предаване на решения е отминал

Целта на задачата е да се имплементира интерпретатор за стеков език. В такъв вид език за подаване на параметри на функции се използва структурата стек. Функциите не приемат аргументи, вместо това директно работят със стойностите записани върху стека.

Например операцията 2 * 3 написана на стеков език би се представила като 3 2 mul - 3 - добави 3 към стека, стека вече съдържа 3 - 2 - добави 2 към стека, стека вече съдържа 3, 2 - mul - извади два елемента от върха на стека (първият аргумент е 2, вторият аргумент е 3), умножи ги и постави резултата в стека. Стека вече съдържа 6

Език

Граматиката на езика с който ще работим съдържа два елемента:

  • число - цяло число със знак в границите на i32.
  • дума - всичко останало. По-точно поредица от символи, не съдържаща whitespace, която не може да се интерпретира като число.

Горе дефинираните елементи са разделени с произволен брой whitespace символи помежду им.

Числата директно се добавят към върха на стека. Думите могат да са вградени оператори или оператори дефинирани от потребителя.

Вградени оператори

Трябва да имплементирате следните вградени оператори

  • ADD, SUB, MUL, DIV - математическите операции събиране, изваждане, умножение и деление върху две числа
  • DUP - push-ва дупликат на елемента на върха на стека
  • POP - премахва елемента на върха на стека
  • SWAP - разменя двата елемента на върха на стека

Оператори дефинирани от потребителя

Потребителя може да дефинира три вида оператори.

Променлива - при срещане в програмата в стека се добавя стойността и. Пример:

interpreter.def_var("THREE", 3);
interpreter.run("1 2 THREE");
// стека съдържа 1, 2, 3

Едноместен оператор - потребителя предоставя closure, който трябва да се извика когато се срещне думата. Аргумента се взима от стека и резултата се добавя в стека.

interpreter.def_unary_op("NEG", |x| -x);
interpreter.run("3 NEG");
// стека съдържа -3

Двуместен оператор - същото като едноместния, но с два аргумента.

interpreter.def_binary_op("PLUS", |x, y| x + y);
interpreter.run("2 3 PLUS");
// стека съдържа 5

Имплементация

Очаква се да напишете интерпретатор със следния интерфейс

/// Грешки, които могат да се срещнат по време на изпълнение на програмата
///
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum RuntimeError {
    DivideByZero,
    StackUnderflow,
    UnknownWord,
}

pub struct Interpreter { ... }

impl Interpreter {
    /// Създава нов интерпретатор
    ///
    pub fn new() -> Self {
        unimplemented!()
    }

    /// Дефинира нова дума за променлива.
    ///
    /// При срещане на думата `name` се добавя стойността `val`
    /// на върха на стека.
    ///
    pub fn def_var(&mut self, name: &str, val: i32) {
        unimplemented!()
    }

    /// Дефинира нова дума за едноместен оператор
    ///
    /// При срещане на думата `name` се изважда най-горният елемент
    /// от стека, изпълнява се `op` и резултатът се добавя в стека.
    ///
    pub fn def_unary_op<F>(&mut self, name: &str, op: F)
    where
        F: Fn(i32) -> i32 + 'static,
    {
        unimplemented!()
    }

    /// Дефинира нова дума за едноместен оператор
    ///
    /// При срещане на думата `name` се изваждат най-горните два елемента
    /// от стека, изпълнява се `op` и резултатът се добавя в стека.
    ///
    pub fn def_binary_op<F>(&mut self, name: &str, op: F)
    where
        F: Fn(i32, i32) -> i32 + 'static,
    {
        unimplemented!()
    }

    /// Изпълнява програмата `input` в този интерпретатор.
    ///
    /// Ако програмата се изпълни успрешно се връща `Ok(top)`, където
    /// `top` е елемента на върха на стека, или `None` ако стекът е празен.
    ///
    /// Ако по време на изпълнението се срещне грешка се връща `Err`.
    ///
    pub fn run(&mut self, input: &str) -> Result<Option<i32>, RuntimeError> {
        unimplemented!()
    }

    /// Връща итератор по текущото съдържание на стека.
    ///
    /// Първият елемент на итератора е върха на стека.
    ///
    pub fn stack<'a>(&'a self) -> impl Iterator<Item = i32> + 'a {
        unimplemented!()
    }
}

Примерният тест се намира тук.