Beispiele: rekursiver Abstieg

Vorzulegen ist eine Funktion ast (abstract syntax tree), die einen arithmetischen Ausdruck als Zeichenkette entgegennimmt und einen abstrakten Syntaxbaum aus Lisp-Ausdrücken zurückgibt. Der Syntaxbaum wird anschließend von der Funktion eval ausgewertet.

Die Aufgabe kann auf unterschiedlichste Art bewältigt werden. Als Musterlösung ist ein rekursiver Abstieg angegeben.

Formale Grammatik
Produktionsregeln in EBNF

atom = number | identifier | "(" expression ")";
power = atom ["^" negation];
negation = ["-"] power;
multiplication = negation {("*" | "/") negation};
addition = multiplication {("+" | "-") multiplication};
expression = addition;

Beispiel-Eingabe:
"2*(x+y)^2+4*x".

Musterlösung

#[derive(Debug)]
enum Symbol {
    Identifier(String),
    Number(f64),
    Symbol(char),
    None
}

#[derive(Debug)]
struct Token {
    symbol: Symbol,
    col: usize
}

#[derive(Debug)]
enum AST {
    Identifier(String),
    Number(f64),
    Symbol(char),
    List(Box<[AST]>)
}

struct SyntaxError {
    text: String,
    col: usize
}

fn syntax_error(col: usize, s: &str) -> SyntaxError {
    SyntaxError {col, text: format!("Syntax-Fehler: {}.", s)}
}

fn print_syntax_error(e: &SyntaxError, s: &str) {
    println!("\n{}", s);
    for _ in 0..e.col {
        print!(" ");
    }
    println!("^");
    println!("{}", e.text);
}

fn scan(s: &str) -> Result<Vec<Token>, SyntaxError> {
    let s: Vec<char> = s.chars().collect();
    let n = s.len();
    let mut acc: Vec<Token> = Vec::new();
    let mut i = 0;
    let mut col = 0;
    while i < n {
        let c = s[i];
        if let '+' | '-' | '*' | '/' | '^'
             | '(' | ')' | '[' | ']' | ',' | ';' = c
        {
            acc.push(Token {col, symbol: Symbol::Symbol(c)});
            i += 1; col += 1;
        } else if c.is_alphabetic() {
            let j = i;
            while i < n && s[i].is_alphanumeric() {
                i += 1; col += 1;
            }
            let id: String = s[j..i].iter().collect();
            acc.push(Token {col, symbol: Symbol::Identifier(id)});
        } else if c.is_digit(10) {
            let j = i;
            while i < n && (s[i] == '.' || s[i].is_digit(10)) {
                i += 1; col += 1;
            }
            let t: String = s[j..i].iter().collect();
            let x = match t.parse::<f64>() {
                Ok(x) => x,
                Err(_) => {
                    return Err(syntax_error(col, "invalide Zahl"));
                }
            };
            acc.push(Token {col, symbol: Symbol::Number(x)});
        } else if let ' ' | '\t' | '\n' = c {
            i += 1;
            if c == '\n' {col = 0} else {col += 1;}
        } else {
            return Err(syntax_error(col,
                &format!("unerwartetes Zeichen: '{}'", c)));
        }
    }
    acc.push(Token {col, symbol: Symbol::None});
    Ok(acc)
}

type SyntaxResult = Result<(AST, usize), SyntaxError>;

fn atom(a: &[Token], i: usize) -> SyntaxResult {
    match a[i].symbol {
        Symbol::Number(x) => Ok((AST::Number(x), i + 1)),
        Symbol::Identifier(ref x) => Ok((AST::Identifier(x.clone()), i + 1)),
        Symbol::Symbol(c) => {
            if c == '(' {
                let (x, i) = expression(a, i + 1)?;
                if let Symbol::Symbol(')') = a[i].symbol {
                    Ok((x, i + 1))
                } else {
                    Err(syntax_error(a[i].col,
                        "schließende Klammer wurde erwartet"))
                }
            } else {
                Err(syntax_error(a[i].col, &format!(
                    "das Symbol '{}' wurde nicht erwartet", c)))
            }
        },
        Symbol::None => {
            Err(syntax_error(a[i].col, "unerwartetes Ende der Eingabe"))
        }
    }
}

fn power(a: &[Token], i: usize) -> SyntaxResult {
    let (x, i) = atom(a, i)?;
    if let Symbol::Symbol('^') = a[i].symbol {
        let (y, i) = negation(a, i + 1)?;
        Ok((AST::List(Box::new([AST::Symbol('^'), x , y])), i))
    } else {
        Ok((x, i))
    }
}

fn negation(a: &[Token], i: usize) -> SyntaxResult {
    if let Symbol::Symbol('-') = a[i].symbol {
        let (x, i) = power(a, i + 1)?;
        Ok((AST::List(Box::new([AST::Symbol('~'), x])), i))
    } else {
        power(a, i)
    }
}

fn multiplication(a: &[Token], i: usize) -> SyntaxResult {
    let (mut x, mut i) = negation(a, i)?;
    while let Symbol::Symbol(op)= a[i].symbol {
        if op == '*' || op == '/' {
            let (y, j) = negation(a, i + 1)?;
            x = AST::List(Box::new([AST::Symbol(op), x, y]));
            i = j;
        } else {
            break;
        }
    }
    Ok((x, i))
}

fn addition(a: &[Token], i: usize) -> SyntaxResult {
    let (mut x, mut i) = multiplication(a, i)?;
    while let Symbol::Symbol(op) = a[i].symbol {
        if op == '+' || op == '-' {
            let (y, j) = multiplication(a, i + 1)?;
            x = AST::List(Box::new([AST::Symbol(op), x, y]));
            i = j;
        } else {
            break;
        }
    }
    Ok((x, i))
}

fn expression(a: &[Token], i: usize) -> SyntaxResult {
    addition(a, i)
}

fn full_expression(a: &[Token]) -> Result<AST, SyntaxError> {
    let (x, i) = expression(a, 0)?;
    if let Symbol::None = a[i].symbol {
        Ok(x)
    } else {
        Err(syntax_error(a[i].col,
            "Ende der Eingabe wurde erwartet"))
    }
}

fn eval(t: &AST) -> Result<f64, String> {
    match *t {
        AST::List(ref a) => {
            let op = match a[0] {
                AST::Symbol(c) => c,
                _ => return Err(String::from("Unbekanntes Symbol"))
            };
            let y = match op {
                '+' => eval(&a[1])? + eval(&a[2])?,
                '-' => eval(&a[1])? - eval(&a[2])?,
                '*' => eval(&a[1])? * eval(&a[2])?,
                '/' => eval(&a[1])? / eval(&a[2])?,
                '^' => eval(&a[1])?.powf(eval(&a[2])?),
                '~' => -eval(&a[1])?,
                _ => return Err(format!("Unbekannter Operator: '{}'", op))
            };
            Ok(y)
        },
        AST::Number(x) => {
            Ok(x)
        },
        AST::Identifier(_) => {
            Err(String::from("Kann Buchstabe nicht auswerten"))
        },
        AST::Symbol(_) => {
            Err(String::from("Operator nicht erwartet"))
        }
    }
}

fn ast(s: &str) -> Result<AST, SyntaxError> {
    let a = scan(s)?;
    full_expression(&a)
}

fn input(prompt: &str) -> String {
    use std::{io, io::Write};
    let mut buffer = String::new();
    print!("{}", prompt);
    io::stdout().flush().unwrap();
    io::stdin().read_line(&mut buffer).unwrap();
    if buffer.ends_with('\n') {
        buffer.pop();
        if buffer.ends_with('\r') {buffer.pop();}
    }
    buffer
}

fn main() {
    loop {
        let line = input("> ");
        if line.is_empty() {continue;}
        let t = match ast(&line) {
            Ok(x) => x,
            Err(e) => {
                print_syntax_error(&e, &line);
                continue;
            }
        };
        println!("{:?}\n", t);
        match eval(&t) {
            Ok(y) => println!("Ergebnis: {}\n", y),
            Err(e) => println!("Auswertungsfehler: {}.\n", e)
        }
    }
}