수학 해석기 만들기: 파서

36822 단어 algorithmscsharp

자원


  • Github 링크 찾기 here

  • 파서



    파서는 인터프리터의 엔진이므로 3가지 주요 방법으로 구성됩니다.
  • 표현
  • 팩터
  • 기간

  • 세 가지 방법이 밀접하게 결합됩니다. Expression 메서드는 Factor 메서드를 호출하고 Factor 메서드는 Term 메서드를 호출하고 반환 값은 다시 Expression 메서드로 전달됩니다.
    Parser.cs 생성부터 시작해 보겠습니다. 다음과 같이 초기화해 보겠습니다.

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


    파서 클래스에는 토큰 목록을 설정하고 첫 번째 토큰curr_token을 가져오는 생성자가 있습니다. Get_Next 메서드를 사용하면 다음 토큰을 얻을 수 있습니다.

    표현


    ParseExp 바로 아래에 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;
        }
    


    Expression 메소드는 먼저 우리가 정의할 factor 메소드를 호출합니다. while 루프는 ADDMINUS 토큰을 반복합니다. if 문은 토큰 유형을 확인하고 본문은 마이너스 또는 AST 추가에 대한 중첩 개체를 생성합니다.

    요인


    Factor 메서드 바로 아래에 Expression 메서드를 만들어 봅시다.

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


    표현식 방법과 유사하게 MULTIPLYDIVISION 토큰을 반복합니다. 이 메소드에서 정의할 Term 메소드도 호출합니다.

    용어


    Term 바로 뒤에 최종 메소드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;
        }
    

    Term 메서드에서 curr_tokenLBRACE(왼쪽 중괄호)인지 확인합니다. 숫자 또는 다른 왼쪽 중괄호로 예상되는 다음 토큰을 얻습니다. 그런 다음 재귀적으로 ParseExp 를 호출합니다. 존재하는지 확인한 직후RBRACE 없으면 예외가 발생합니다.

    else if 문에서 ASTLeaf를 만들고 다음 토큰을 가져와 결과를 반환합니다.

    따라서 전체Parser.cs는 다음과 같습니다.

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


    마무리


    Program.cs에서 다음 코드를 추가할 수 있습니다.

          Parser parser = new Parser(tokens);
          AST astObj = parser.ParseExp();
          if(astObj == null)
          {
               continue;
          }
          Console.WriteLine(">> {0}", astObj.Eval());
    


    파서 객체를 생성한 다음 AST 를 생성합니다. 계속인 경우 null인지 확인하고 그렇지 않으면 Eval을 인쇄합니다. astObj.ToString()를 사용하여 평가 구조를 생성할 수도 있습니다.

    단위 테스트



    단위 테스트 프로젝트에서 ParserTest.cs 클래스를 만들고 다음 테스트를 추가해 보겠습니다.

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


    다음 시리즈에서는 다음을 수행할 것입니다.
  • Travis-CI 빌드 및 테스트 파이프라인 설정
  • 좋은 웹페이지 즐겨찾기