Making a Math Interpreter: Parser
John Nyingi
Posted on September 22, 2021
Resources
- Find the Github link here
Parser
The parser is the engine of the interpreter, and so it will consist of 3 main methods;
- Expression
- Factor
- Term
The three methods will be tightly coupled. Expression method will call the Factor method and the Factor method will call the Term method and the return value is passed back to the Expression method.
Let's start by creating the Parser.cs let's initialize it with the following.
public class Parser
{
private List<Token> TermItems = new List<Token>() { Token.ADD, Token.MINUS };
private List<Token> FactorItems = new List<Token>() { Token.MULTIPLY, Token.DIVISION };
private readonly List<Tokens> _tokens;
private int pos = 0;
private Tokens curr_token = null;
public Parser(List<Tokens> tokens)
{
this._tokens = tokens;
// set the current token
Get_Next();
}
private void Get_Next()
{
if(pos < this._tokens.Count)
{
curr_token = this._tokens[pos];
pos++;
}
}
}
Our parser class has a constructor that sets the List of tokens and gets the first token curr_token. The Get_Next method will allow us to get the next token.
Expression
Let's add a ParseExp method right below the Get_Next.
public AST ParseExp()
{
AST result = Factor();
while(curr_token._tokenType != Token.EOF && result != null && TermItems.Contains(curr_token._tokenType))
{
if(curr_token._tokenType == Token.ADD)
{
Get_Next();
AST rigthNode = Factor();
result = new ASTPlus(result, rigthNode);
}
else if(curr_token._tokenType == Token.MINUS)
{
Get_Next();
AST rigthNode = Factor();
result = new ASTMinus(result, rigthNode);
}
}
return result;
}
The Expression method first calls the factor method which we will define. The while loop iterates through the ADD and MINUS tokens. The if statement checks the token type and the body creates nested objects for either Minus or Add AST.
Factor
Let's create the Factor method right below the Expression method.
public AST Factor()
{
AST factor = Term();
while (curr_token._tokenType != Token.EOF && factor != null && FactorItems.Contains(curr_token._tokenType))
{
if (curr_token._tokenType == Token.MULTIPLY)
{
Get_Next();
AST rigthNode = Term();
factor = new ASTMultiply(factor, rigthNode);
}
else if (curr_token._tokenType == Token.DIVISION)
{
Get_Next();
AST rigthNode = Term();
factor = new ASTDivide(factor, rigthNode);
}
}
return factor;
}
Similar to the expression method we iterate through the MULTIPLY and DIVISION tokens. In this method we also call Term method which we will define.
Term
Let's add our final method Term right after the Factor.
public AST Term()
{
AST term = null;
if(curr_token._tokenType == Token.LBRACE)
{
Get_Next();
term = ParseExp();
if(curr_token._tokenType != Token.RBRACE)
{
throw new FormatException("Missing )");
}
}
else if(curr_token._tokenType == Token.NUMBER)
{
term = new ASTLeaf((decimal)curr_token._value);
}
Get_Next();
return term;
}
In our Term method, we check if the curr_token is a LBRACE(left brace). We get the next token, which we expect is a number or another left brace. We then recursively call the ParseExp. Right after we check if there exists an RBRACE if not it throws an exception.
In the else if statement, we create an ASTLeaf and we get the next token and return the result.
So the whole Parser.cs looks like this
public class Parser
{
private List<Token> TermItems = new List<Token>() { Token.ADD, Token.MINUS };
private List<Token> FactorItems = new List<Token>() { Token.MULTIPLY, Token.DIVISION };
private readonly List<Tokens> _tokens;
private int pos = 0;
private Tokens curr_token = null;
public Parser(List<Tokens> tokens)
{
this._tokens = tokens;
// set the current token
Get_Next();
}
private void Get_Next()
{
if(pos < this._tokens.Count)
{
curr_token = this._tokens[pos];
pos++;
}
}
public AST ParseExp()
{
AST result = Factor();
while(curr_token._tokenType != Token.EOF && result != null && TermItems.Contains(curr_token._tokenType))
{
if(curr_token._tokenType == Token.ADD)
{
Get_Next();
AST rigthNode = Factor();
result = new ASTPlus(result, rigthNode);
}
else if(curr_token._tokenType == Token.MINUS)
{
Get_Next();
AST rigthNode = Factor();
result = new ASTMinus(result, rigthNode);
}
}
return result;
}
public AST Factor()
{
AST factor = Term();
while (curr_token._tokenType != Token.EOF && factor != null && FactorItems.Contains(curr_token._tokenType))
{
if (curr_token._tokenType == Token.MULTIPLY)
{
Get_Next();
AST rigthNode = Term();
factor = new ASTMultiply(factor, rigthNode);
}
else if (curr_token._tokenType == Token.DIVISION)
{
Get_Next();
AST rigthNode = Term();
factor = new ASTDivide(factor, rigthNode);
}
}
return factor;
}
public AST Term()
{
AST term = null;
if(curr_token._tokenType == Token.LBRACE)
{
Get_Next();
term = ParseExp();
if(curr_token._tokenType != Token.RBRACE)
{
throw new FormatException("Missing )");
}
}
else if(curr_token._tokenType == Token.NUMBER)
{
term = new ASTLeaf((decimal)curr_token._value);
}
Get_Next();
return term;
}
}
Wrap Up
In our Program.cs we can add the following code;
Parser parser = new Parser(tokens);
AST astObj = parser.ParseExp();
if(astObj == null)
{
continue;
}
Console.WriteLine(">> {0}", astObj.Eval());
We generate a parser object and then we create the AST. We check if it's null if it is continue else print the Eval. You can also generate the evaluation structure using the astObj.ToString()
Unit Test
In our Unit Tests Project let's create a ParserTest.cs class and lets add the following tests.
public class ParserTest
{
[Fact]
public void TestASTString()
{
string expected = "((56 - (64 / 8)) + 4)";
Lexer lexer = new Lexer("56 - 64/8 +4");
List<Tokens> tokens = lexer.Get_Tokens();
Assert.NotEmpty(tokens);
Parser parser = new Parser(tokens);
AST astObj = parser.ParseExp();
Assert.NotNull(astObj);
string actual = astObj.ToString();
Assert.Equal(expected, actual);
}
[Fact]
public void TestASTTermOperations()
{
decimal expected = 45;
Lexer lexer = new Lexer("25+25 -5");
List<Tokens> tokens = lexer.Get_Tokens();
Assert.NotEmpty(tokens);
Parser parser = new Parser(tokens);
AST astObj = parser.ParseExp();
Assert.NotNull(astObj);
decimal actual = astObj.Eval();
Assert.Equal(expected, actual);
}
[Fact]
public void TestASTFactorOperations()
{
decimal expected = 5.5m;
Lexer lexer = new Lexer("121/11*0.5");
List<Tokens> tokens = lexer.Get_Tokens();
Assert.NotEmpty(tokens);
Parser parser = new Parser(tokens);
AST astObj = parser.ParseExp();
Assert.NotNull(astObj);
decimal actual = astObj.Eval();
Assert.Equal(expected, actual);
}
[Fact]
public void TestASTBraces()
{
decimal expected = 0;
Lexer lexer = new Lexer("10-5*(25/5)+15");
List<Tokens> tokens = lexer.Get_Tokens();
Assert.NotEmpty(tokens);
Parser parser = new Parser(tokens);
AST astObj = parser.ParseExp();
Assert.NotNull(astObj);
decimal actual = astObj.Eval();
Assert.Equal(expected, actual);
}
[Fact]
public void TestASTBraceMissing()
{
Lexer lexer = new Lexer("(25/5");
List<Tokens> tokens = lexer.Get_Tokens();
Assert.NotEmpty(tokens);
Parser parser = new Parser(tokens);
Assert.Throws<FormatException>(() => parser.ParseExp());
}
}
In our next series, we're going to;
- Setup Travis-CI Build and Test Pipeline
Posted on September 22, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
