asmpro
765
2019-03-27 21:50:25 작성 2019-03-31 18:39:19 수정됨
0
789

누구나 만들 수 있는 컴파일러 - 2


강좌 소스 코드 git : https://github.com/hybridcompiler/HybridCompiler

블로그 링크 : https://hybridcompiler.blogspot.com/2019/03/2.html


지난 강좌에서는 하나의 사칙 연산자만 허용하는 계산기 인터프리터를 구현했습니다.

이번 강좌에서는 사칙연산과 숫자 앞에 자유롭게 +,- 단항 연산자를 붙이고 괄호를 지원하는 계산기 인터프리터를 구현하겠습니다.


두 번째 프로젝트 Hybrid Interpreter 2 (HI2)

]3 * (2 + 6) - 3
21
]6 * (-3 - - 6) / 3 + 7
13
]
계속하려면 아무 키나 누르십시오 . . .
위는 H2의 실행 결과입니다.

기존의 HybridCompiler 솔루션에 HI2 프로젝트를 생성합니다.

솔루션 탐색기에서 솔루션을 오른쪽 클릭하여 속성을 선택한 후 시작 프로젝트로 HI2를 선택합니다.


Token.cs

    internal enum TokenType
    {
        Integer,

        // 사칙 연산

        Plus,
        Minus,
        Mul,
        Div,

        // 괄호

        LeftParens,
        RightParens,

        EOF,    // 토큰이 없을 때 반환하는 타입
    }
기존의 Token 타입에 좌측 괄호 타입과 우측 괄호 타입 2개의 타입이 추가되었습니다.


Lexer.cs

        // 문자열로부터 토큰을 가져온다.
        public Token GetNextToken()
        {
            while (CurrentChar != (char)0)
            {
                if (CurrentChar >= '0' && CurrentChar <= '9')
                {
                    return new Token { type = TokenType.Integer, integer = GetInteger() };
                }
                switch (CurrentChar)
                {
                    case ' ': SkipSpace(); continue;
                    case '+': MoveNext(); return new Token { type = TokenType.Plus };
                    case '-': MoveNext(); return new Token { type = TokenType.Minus };
                    case '*': MoveNext(); return new Token { type = TokenType.Mul };
                    case '/': MoveNext(); return new Token { type = TokenType.Div };
                    case '(': MoveNext(); return new Token { type = TokenType.LeftParens };
                    case ')': MoveNext(); return new Token { type = TokenType.RightParens };
                }
                throw new Exception($"{CurrentChar} : 유효하지 않은 문자입니다.");
            }
            return new Token { type = TokenType.EOF };
        }
GetNextToken 메서드에 좌측 괄호와 우측 괄호를 Token 타입으로 변환하는 코드가 추가되었습니다.


EBNF


HI1은 정해진 규칙의 3개의 Token을 이용하여 계산하는 인터프리터였기에 문법을 정의하지 않고 토큰을 차례대로 3개를 읽은 후 계산하였습니다.

하지만 HI2는 사칙 연산과 괄호를 자유롭게 사용할 있기 때문에 HI1에 사용한 방식으로는 복잡함을 해결할 수 없습니다.

따라서 프로그래밍언어의 문법을 정의하는데 가장 일반적으로 사용되는 EBNF을 이용하여 문법을 정의하고 정의된 문법을 바탕으로 강좌를 진행하겠습니다.


우선 간단하게 EBNF에 대해 설명하겠습니다.

BNF는 프로그래밍언어를 수학적인 수식으로 나타내기 위해 사용하는 도구로 언어의 모든 문법은 BNF로 정의할 수 있습니다.

EBNF는 BNF를 더 쉽게 사용할 수 있게 확장한 것입니다.

EBNF는 non-terminal을 terminal과 non-terminal을 조합하여 정의합니다.

terminal은 "a", "+" 등의 non-terminal로 정의할 수 없는 최소 단위로 일반적으로 문자를 뜻합니다.

terminal을 상수로 non-terminal을 함수로 대입하고 함수는 상수와 함수를 조합하여 정의한다고 생각하면 이해하기가 쉬울 겁니다.

EBNF에 대한 이해를 돕기 위해 우선 전 강좌의 HI1의 문법을 EBNF로 정의해 보겠습니다.

expression = integer, "+" | "-" | "*" | "/", integer ;
integer = digit, { digit } ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
일단 EBNF의 기호들에 대한 설명을 간단히 하겠습니다.
  • '=' : 정의
  • ',' : 연결, ex)"a","b" = "ab"
  • '|' : 또는
  • '(...)' : 그룹
  • '[...]' : 생략 가능
  • '{...}' : 생략 가능한 반복


이제 HI1의 문법 정의를 풀어서 설명하겠습니다.

  • digit(숫자)는 "0"부터 "9"까지의 문자 중 하나입니다.
  • integer(정수)는 하나의 digit 또는 여러 개의 digit입니다.
  • expression(표현식)은 정수와 정수 간의 사칙 연산자의 결과입니다.


HI1의 실제 코드와 비교해 보겠습니다.

// Lexer.cs

// GetNextToken 메서드 중 digit 정의 구현
if (CurrentChar >= '0' && CurrentChar <= '9')
{
    return new Token { type = TokenType.Integer, integer = GetInteger() };
}

// integer 정의 구현
private long GetInteger()
{
    long integer = 0;
    do
    {
        integer = integer * 10 + CurrentChar - '0';
        MoveNext();
    } while (CurrentChar >= '0' && CurrentChar <= '9');
    return integer;
}

// Interpreter.cs

// expression 정의 구현
public long Run()
{
    if (tokens.Count != 3) { throw new Exception($"{tokens.Count} : 3개의 토큰이 필요합니다."); }

    var integer1 = tokens[0];
    if (integer1.type != TokenType.Integer) { throw new Exception($"{integer1.type} : 정수가 필요합니다."); }

    var integer2 = tokens[2];
    if (integer2.type != TokenType.Integer) { throw new Exception($"{integer2.type} : 정수가 필요합니다."); }

    var op = tokens[1].type;
    switch (op)
    {
        case TokenType.Plus: return integer1.integer + integer2.integer;
        case TokenType.Minus: return integer1.integer - integer2.integer;
        case TokenType.Mul: return integer1.integer * integer2.integer;
        case TokenType.Div: return integer1.integer / integer2.integer;
    }
    throw new Exception($"{op} : 사칙 연산자가 필요합니다.");
}
digit의 정의를 구현한 부분은 Lexer 클래스의 GetNextToken 메소드에서 찾을 수 있습니다.

integer의 정의를 구현한 부분은 Lexer 클래스의 GetInteger 메소드입니다.

expression의 정의를 구현한 부분은 Interpreter 클래스의 Run 메소드입니다.


일반적으로 integer는 하나의 Token으로 분류가 되고 digit는 integer의 하위이기 때문에 Lexer에서 integer와 digit의 정의를 처리합니다.

integer 이상의 정의는 HI1처럼 문법이 단순하지 않은 이상 Parser에서 정의를 처리합니다.

Parser의 구현은 다음 강좌에서 진행하고 이번 강좌에서는 HI1과 동일하게 Interpreter에서 처리하겠습니다.


이제 HI2의 문법을 EBNF로 정의해 보겠습니다.

expression = term, { "+" | "-", term } ;
term = factor, { "*" | "/", factor } ;
factor = ( [ "+" | "-" ], integer ) | ( "(", expression, ")" ) ;
digit와 integer정의는 HI1의 정의와 동일하기에 생략합니다.

HI2의 문법 정의를 풀어서 설명하겠습니다.

  • factor는 앞에 더하기, 빼기 부호를 붙이거나 생략할 수 있는 정수이거나 (expression) 입니다.
  • term은 하나의 factor 또는 factor와 factor 간의 연속되는 곱셈, 나눗셈 연산의 결과입니다.
  • expression은 하나의 term 또는 term과 term 간의 연속되는 덧셈, 뺄셈 연산의 결과입니다.
특별히 이해하기 어려운 부분은 없을 거라 생각합니다.

하지만 왜 사칙연산들 중 곱셈, 나눗셈은 term에 정의되고 덧셈, 뺄셈은 expression에 정의되었을까 의문이 생긴 분들도 있을 거라 생각합니다.

이해를 돕기위해 예를 하나 들어보겠습니다.

]5 * (4 - 7) + 6
Begin expression
    Begin term
        Begin factor
            factor = 5
        End factor
        Begin factor
            Begin expression
                Begin term
                    Begin factor
                        factor = 4
                    End factor
                    term = 4
                End term
                Begin term
                    Begin factor
                        factor = 7
                    End factor
                    term = 7
                End term
                expression = 4 - 7
                expression = -3
            End expression
            factor = -3
        End factor
        term = 5 * -3
        term = -15
    End term
    Begin term
        Begin factor
            factor = 6
        End factor
        term = 6
    End term
    expression = -15 + 6
    expression = -9
End expression
-9
HI2에 문자열을 EBNF문법으로 변환하는 과정을 출력하는 기능을 추가한 실행결과 입니다.

항상 가장 아래 단계에 있는 factor 부터 결과가 나온 후 term, expression으로 거슬러 올라가면서 계산이 되는 것을 볼 수 있습니다.

한마디로 EBNF 문법은 항상 우선순위가 높은 연산일수록 아래 단계에 정의해야 한다는 것입니다.

덧셈, 뺄셈보다 곱셈, 나눗셈이 우선순위가 높으니 덧셈, 뺄셈은 expression에, 곱셈, 뺄셈은 term에 정의가 된 것이죠.

연산자보다 더 우선순위가 높은 괄호나 숫자 앞에 붙는 부호는 factor에 포함되는 것이구요.

HI2에서 간단한 연산부터 복잡한 연산까지 테스트하면서 출력 결과와 EBNF 문법을 비교해 보면 완전히 이해하는데 도움이 될 겁니다.


Interpreter.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace HI2
{
    internal class Interpreter
    {
        public Interpreter(List tokens) => this.tokens = tokens;

        public long Run()
        {
            return InterpreteExpression();
        }

        private readonly List tokens;

        private int currentPos;

        private Token CurrentToken => tokens.Count > currentPos ? tokens[currentPos] : new Token { type = TokenType.EOF };

        // EBNF : expression = term, { "+" | "-", term } ;
        private long InterpreteExpression()
        {
            using (var tracer = new Tracer("expression"))
            {
                long expression = InterpreteTerm();

                while (CurrentToken.type == TokenType.Plus || CurrentToken.type == TokenType.Minus)
                {
                    var op = CurrentToken;
                    MoveNext();
                    var term = InterpreteTerm();
                    if (op.type == TokenType.Plus)
                    {
                        tracer.Print($"{expression} + {term}");
                        expression += term;
                    }
                    else
                    {
                        tracer.Print($"{expression} - {term}");
                        expression -= term;
                    }
                }
                tracer.Print(expression);
                return expression;
            }
        }

        // EBNF : factor = ( [ "+" | "-" ], integer ) | ( "(", expression, ")" ) ;
        private long InterpreteFactor()
        {
            using (var tracer = new Tracer("factor"))
            {
                var token = CurrentToken;
                MoveNext();

                long factor;
                switch (token.type)
                {
                    case TokenType.Plus:
                    case TokenType.Minus:
                        var integer = CurrentToken;
                        Match(TokenType.Integer);
                        factor = token.type == TokenType.Plus ? integer.integer : -integer.integer;
                        break;

                    case TokenType.Integer:
                        factor = token.integer;
                        break;

                    case TokenType.LeftParens:
                        var expression = InterpreteExpression();
                        Match(TokenType.RightParens);
                        factor = expression;
                        break;

                    default: throw new Exception($"{token.type} : 알 수 없는 토큰 타입입니다.");
                }
                tracer.Print(factor);
                return factor;
            }
        }

        // term = factor, { "*" | "/", factor } ;
        private long InterpreteTerm()
        {
            using (var tracer = new Tracer("term"))
            {
                long term = InterpreteFactor();

                while (CurrentToken.type == TokenType.Mul || CurrentToken.type == TokenType.Div)
                {
                    var op = CurrentToken;
                    MoveNext();
                    var factor = InterpreteFactor();
                    if (op.type == TokenType.Mul)
                    {
                        tracer.Print($"{term} * {factor}");
                        term *= factor;
                    }
                    else
                    {
                        tracer.Print($"{term} / {factor}");
                        term /= factor;
                    }
                }
                tracer.Print(term);
                return term;
            }
        }

        private void Match(TokenType type)
        {
            if (CurrentToken.type != type) { throw new Exception($"{CurrentToken.type} : {type} 타입 토큰이 필요합니다."); }
            MoveNext();
        }

        private void MoveNext() => currentPos++;
    }

    internal class Tracer : IDisposable
    {
        public Tracer(string text)
        {
            name = text;
            Console.WriteLine($"{indent}Begin {name}");
            indent += "    ";
        }

        public void Dispose()
        {
            Debug.Assert(!string.IsNullOrEmpty(name));

            indent = indent.Remove(0, 4);
            Console.WriteLine($"{indent}End {name}");
            name = null;
        }

        public void Print(object text) => Console.WriteLine($"{indent}{name} = {text}");

        private static string indent;

        private string name;
    }
}
Interpreter에 terminal 정의별로 메소드를 정의했습니다.

지금까지의 강좌내용을 이해하셨으면 코드 또한 쉽게 이해할 수 있을 겁니다.

Tracer 클래스는 EBNF의 문법이 실제로 어떻게 적용되는지를 출력하기 위한 클래스로 이번 강좌에서만 이해를 돕기 위해 추가하였습니다.


이번 강좌까지는 이해를 돕기 위해 의도적으로 최적화를 하지 않은 코드를 사용하였습니다.

앞으로 진행될 수록 프로젝트의 복잡도는 계속해서 증가할 것이기 때문에 다음 강좌에서는 에러, 메세지, 전체 프로젝트에서 사용할 공용 라이브러리 구성 등 최적화를 진행하도록 하겠습니다.

2
2
  • 댓글 0

  • 로그인을 하시면 댓글을 등록할 수 있습니다.