Arithmetic Parser

A simple parser for arithmetic expressions. Evaluates expressions from the command line given a string of characters (eg. "1-2+3*4/5").

There are three main components:

Source -> Lexer -> Parser

Source - Manages the input buffer of characters.
Lexer - Reads in characters from the source and outputs tokens. Tokens are read from right to left to maintain a left grouping. White space is skipped.
Parser - Reads tokens from the lexer using recursive descent parsing to follow the precedence and associativity of the CFG. It produces an AST data structure, where the expression it represents can then be evaluated.

Context-free Grammar

The following CFG describes all possible arithmetic strings that can be parsed. It uses PEMDAS order of operations and associates to the left. For an example, a chain of minus operations would be evaluated like (((((9-8)-7)-6)-5)).

Expression -> Expression - Add
Expression -> Add

Add -> Add + Div
Add -> Div

Div -> Div / Mul
Div -> Mul

Mul -> Mul * Exp
Mul -> Exp

Exp -> Exp ^ Term
Exp -> Term

Term -> (Expression)
Term -> n

Examples

Each of the following are valid input strings:

9
9 + 9
9+9
9.33 - 10.44
6 - 3 - 2
(78) / (2-1)
5^8
(4/6+8)^(2^2)
(4-(6/2+1)-2-(3)+9+(45-6))