DEV Community

Cover image for Making a Math Interpreter: Parser
John Nyingi
John Nyingi

Posted on

Making a Math Interpreter: Parser

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++;
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
        }

    }
Enter fullscreen mode Exit fullscreen mode

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());
Enter fullscreen mode Exit fullscreen mode

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());
        }
    }
Enter fullscreen mode Exit fullscreen mode

In our next series, we're going to;

  • Setup Travis-CI Build and Test Pipeline

Discussion (0)