Struct xxcalc::parser::Parser

pub struct Parser { /* fields omitted */ }

Parser takes Tokens in infix form and transforms them into Reverse Polish Notation. After such transformation tokens can be processed by TokensReducer.

Parser stores registered operators (with their precedence and associativity) between multiple executions. Furthermore an output buffer of Tokens is kept internally, so it can be reused without allocating new memory from the operating system. If Parser lives long enough this behaviour can greatly reduce time wasted on mallocs.

Examples

let mut tokenizer = Tokenizer::default();
let mut parser = Parser::default();

parser.register_operator('+', Operator::new(1, OperatorAssociativity::Left));

let tokenized = tokenizer.process("2+2");
let parsed = parser.process(tokenized).unwrap();

assert_eq!(parsed.tokens, [(0, Token::Number(2.0)),
                           (2, Token::Number(2.0)),
                           (1, Token::Operator('+'))]);

Extending

One could embed the parser inside another TokensProcessor and initialize it there with some default operators.

Methods

impl Parser

fn new() -> Parser

Creates an empty Parser with no defined operators.

fn register_operator(&mut self, name: char, operator: Operator) -> Option<Operator>

Registers operator identified by given name to the parser.

Each operator must be registered and associated with its precedence and associative to make parser capable of valid RPN transformation. As operators always require two arguments, no arity is needed.

If an operator with given name was already registered, it previous specification is returned.

Examples

let mut tokenizer = Tokenizer::default();
let mut parser = Parser::default();

let r = parser.register_operator('+', Operator::new(42, OperatorAssociativity::Left));
assert!(r.is_none());

let r = parser.register_operator('+', Operator::new(1, OperatorAssociativity::Left));
assert_eq!(r.unwrap(), Operator::new(42, OperatorAssociativity::Left));

Trait Implementations

impl Default for Parser

Creates a new default Parser.

Such parser is not ready to parse complex infix notation by default. No operators are registered by default, one must define operators with their precedence and associativity to be able of parsing complex mathematical expressions.

fn default() -> Parser

Returns the "default value" for a type.

impl TokensProcessor for Parser

This is a main processing unit in the parser. It takes a tokens in infix form and converts them to RPN using Dijsktra's shunting-yard algorithm.

Before processing expressions more complex than trivial identifiers or numbers, operators must be registered.

This parser supports two argument operators and multiple argument functions. Function arguments must be declared between opening and closing bracket tokens, with their arguments separated using separator token.

A popular Dijsktra's shunting-yard algorithm converts infix to postfix notation (RPN) in a linear time O(n). It pushes numbers and constants to the output, while using a stack to store temporary operands until they are needed to be pushed to the output as some other operator with smaller precedence is found.

Errors

An EmptyExpression error is returned when tokens represent no meaningful expression (no tokens or just brackets).

let mut parser = Parser::default();

let tokenized = &Tokens::new(None);
assert_eq!(parser.process(tokenized).unwrap_err(), ParsingError::EmptyExpression);

A MissingBracket error is returned when brackets are unbalanced, no matter if they were used to mark subexpression or an argument list.

let mut tokenizer = Tokenizer::default();
let mut parser = Parser::default();

{
  let tokenized = tokenizer.process("(2");
  assert_eq!(parser.process(tokenized).unwrap_err(), ParsingError::MissingBracket(0));
}

{
  let tokenized = tokenizer.process("2)");
  assert_eq!(parser.process(tokenized).unwrap_err(), ParsingError::MissingBracket(1));
}

{
  let tokenized = tokenizer.process("foo(2, (2), -1");
  assert_eq!(parser.process(tokenized).unwrap_err(), ParsingError::MissingBracket(3));
}

An UnexpectedToken error is returned when parser encounters a token with no meaning to the algorithm (such as Token::Unknown).

let mut tokenizer = Tokenizer::default();
let mut parser = Parser::default();

// note that @ is not a valid operator, so it results in Token::Unknown
let tokenized = tokenizer.process("(2)@2");
assert_eq!(parser.process(tokenized).unwrap_err(), ParsingError::UnexpectedToken(Token::Unknown('@'), 3));

An UnknownOperator error is returned when a parser encounters an operator token, but this operator is not registerd with the parser.

let mut tokenizer = Tokenizer::default();
let mut parser = Parser::default();

let tokenized = tokenizer.process("(2)+2");
assert_eq!(parser.process(tokenized).unwrap_err(), ParsingError::UnknownOperator('+', 3));

fn process(&mut self, tokens: &Tokens) -> Result<&Tokens, ParsingError>