There are four main parts to this parser: The REPL shell, the lexer/tokenizer, the parser itself, and the interpreter. The role/implementation of each of these parts is explained in detail in the corresponding section below.
The REPL (short for read evaluate print loop) shell is responsible for taking in user input, sending it to the lexer/tokenizer, sending the result from the lexer/ tokenizer to the parser, sending the results from the parser to the interpreter, then printing the results of the interpreter for the user. It is also responsible for catching and printing any exceptions raised by the other components, whether those be caused by syntax errors in user input, or bugs.
The simplified logic loop for the REPL shell is this:
- Read from user input
- Send user input to lexer
- Send output of lexer to parser
- Send output of parser to interpreter
- Send output of interpreter to output
- Repeat
The lexer is responsible for splitting its input into a list of discrete tokens to be parsed by the parser. In this process, it will remove any whitespace and raise an exception if the token is invalid.
The parser works based on a set of grammatical rules to build a parse tree that will then be sent to the interpreter for evaluation. The parser works by implementing the following context-free grammar rules:
command := expr
expr := term {add term}
add := + | -
term := factor {mul factor}
mul := * | /
factor := paren {expo paren}
expo := ^
paren := (expr) | number
number := digit {digit}
digit := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
For this grammar, command is the start variable, and expressions in curly brackets indicate that an arbitrary amount of that expression can be appended, and the rule would still be valid.
The interpreter takes the parse tree from the parser as input and evaluates it. By evaluating both children before evaluating the parent node of the parse tree, the interpreter enforces PEMDAS order of operations.
To compile and run the mathematical parser, GNU's C++ compiler should be installed, as well as C++ 11 or later. This utility was designed to be used on Linux/Unix machines, and installation requirements/instructions will not be listed for other systems. It is recommended to also install GNU's make utility, in order to make compilation easier. Once both the compiler and make are installed, simply run "make" in this directory to compile the code for your machine.
To invoke the utility, either run the command "./calcutil" or "make run"