Making a Math Interpreter: Parser
Tags: algorithms, csharp
Published: 2021-09-22 10:05:20

---
title: Making a Math Interpreter: Parser
published: true
series: Making a Math Interpreter using C#
description: Making the Parser
tags: algorithms, csharp
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2um78ah24581l3l3ll1s.jpg
---
#### Resources
- Find the Github link [here](https://github.com/j0nimost/calcy)

## 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.
```csharp
    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`.
```csharp
    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.

```csharp
    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`.

```csharp
     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
```csharp
    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;
```csharp
      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.

```csharp
    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