asmpro
681
2019-05-04 20:03:55
6
1087

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


강좌 소스 코드 git : https://github.com/hybridcompiler/HybridCompiler
블로그 : https://hybridcompiler.blogspot.com/2019/05/6.html

여섯 번째 프로젝트 Hybrid Interpreter 6 (HI6)

]test
---------- Test.TestLexer 시작
========== Test.TestLexer 완료: 성공 29, 실패 0
---------- Test.TestParserLine 시작
========== Test.TestParserLine 완료: 성공 27, 실패 0
---------- Test.TestParser 시작
구구단 예제
2 * 2 = 4
2 * 3 = 6
2 * 4 = 8
2 * 5 = 10
2 * 6 = 12
2 * 7 = 14
2 * 8 = 16
2 * 9 = 18
3 * 2 = 6
3 * 3 = 9
3 * 4 = 12
3 * 5 = 15
3 * 6 = 18
...
생략
...
9 * 5 = 45
9 * 6 = 54
9 * 7 = 63
9 * 8 = 72
9 * 9 = 81
========== Test.TestParser 완료: 성공 14, 실패 0
]print("Test: ", 10)
Test: 10
10
]exit
계속하려면 아무 키나 누르십시오 . . .
위는 HI6의 실행 결과입니다.

HI6 프로젝트에는 함수의 선언, 호출 기능이 추가되었습니다.

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

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


EBNF 문법

program = function_statement, { function_statement } ;
function_statement = "def", identifier, "(", [ identifier, { ",", identifier } ], ")", block ;
block = "{", { statement }, "}"
statement = keyword_statement | expression ;
keyword_statement = variable_declaration | if_statement |
                    while_statement | for_statement | print ;
variable_declaration = "dim", identifier, [ "=", expression ] ;
if_statement = "if", "(", expression, ")", block,
               { "elif", "(", expression, ")", block }, [ "else", block ] ;
while_statement = "while", "(", expression, ")", block ;
for_statement = "for", [ [ "dim" ], identifier, "in" ], "range",
                "(", expression, [ ",", expression ], [ ",", expression ], ")", block ;
print = "print", "(", expression | string, { ",", expression | string } ")" ;

expression = [ identifier, ( "=" | "+=" | "-=" | "*=" | "/=" | "%=" |
             "<<=" | ">>=" | "&=" | "^=" | "|=" ) ], logical_or ;
logical_or = logical_and, { "||", logical_and } ;
logical_and = bitwise_or, { "&&", bitwise_or } ;
bitwise_or = bitwise_xor, { "|", bitwise_xor } ;
bitwise_xor = bitwise_and, { "^", bitwise_and } ;
bitwise_and = equality, { "&", equality } ;
equality = relational, { "==" | "!=", relational } ;
relational = shift, { "<" | ">" | "<=" | ">=", shift } ;
shift = additive, { "<<" | ">>", additive } ;
additive = multiplicative, { "+" | "-", multiplicative } ;
multiplicative = unary, { "*" | "/" | "%", unary } ;
unary = [ "+" | "-" | "!" ], factor ;
factor = integer | identifier | call_function | ( "(", expression, ")" ) ;

call_function = identifier, "(", [ expression, { ",", expression } ], ")" ;
identifier = ( alphabet | "_" ), { alphabet | "_" | integer } ;
string = '"', { all characters }, '"' ;
integer = digit, { digit } ;
alphabet = "A" | "B" | ...... | "z" ;
digit = "0" | "1" | ...... | "9" ;
파싱을 시작하는 문법이 block에서 program으로 변경되었습니다.

program은 하나 이상의 function_statement로 이루어져 있습니다.

function_statement는 함수의 인자와 block으로 이루어져 있습니다.

그 외에 print 문이 한 번에 여러 개의 문자열과 숫자를 출력할 수 있게 변경되었습니다.


SymbolTable

// HI5 Symbol Class

    internal class Symbol
    {
        public long IntegerValue { get; set; }
        public Token Token { get; private set; }

        public Symbol(Token token)
        {
            HIDebug.AssertEqual(token.Type, TT.Identifier);
            if (symbols.TryGetValue(token.Text, out _))
            {
                throw new HIException(ET.NameError, Id.NameAlreadyDefined, token);
            }
            Token = token;
            symbols[token.Text] = this;
        }

        public static bool Find(Token token, out Symbol symbol) =>
            symbols.TryGetValue(token.Text, out symbol);

        private static readonly Dictionary symbols = new Dictionary();
    }

// HI6 Symbol Class

    internal class Symbol
    {
        public long IntegerValue { get; set; }
        public Token Token { get; private set; }
        public FunctionNode Function { get; set; }

        public Symbol(Token token) => Token = token;
    }
HI5 프로젝트에서는 심볼 테이블이 Symbol 클래스 내에 정적 symbols 맵으로 정의되어 있었기에 전역에서 단 하나의 심볼 테이블을 갖고 있었습니다.

HI6 프로젝트는 함수를 정의하고 호출할 수 있기 때문에 블록별로 변수를 따로 다룰 수 있어야 합니다.

따라서 심볼 테이블 또한 블록 별로 따로 존재해야 하죠.

그래서 Symbol 클래스에 Symbol의 속성만을 남겨 두고 심볼 테이블 관련 소스를 제외합니다.

새롭게 추가된 Function 속성은 Symbol의 타입은 HI5 프로젝트까지는 숫자 한 가지였는데 이제 함수가 정의 가능해지면서 함수 관련 속성이 추가되었습니다.


// Node.cs

    internal class BlockNode : Node
    {
        public override long Visit
        {
            get
            {
                long value = 0;
                foreach (var node in statements) { value = node.Visit; }
                return value;
            }
        }

        public void AddStatement(Node node) => statements.Add(node);

        public void AddSymbol(Token token, Symbol symbol)
        {
            if (GetSymbol(token, out _))
            {
                throw new HIException(ET.NameError, Id.NameAlreadyDefined, token);
            }
            symbols[token.Text] = symbol;
        }

        public bool GetSymbol(Token token, out Symbol symbol) =>
            symbols.TryGetValue(token.Text, out symbol);

        public bool GetSymbol(string name, out Symbol symbol) => symbols.TryGetValue(name, out symbol);

        private readonly List statements = new List();
        private readonly Dictionary symbols = new Dictionary();
    }
HI5의 Symbol 클래스에 있던 심볼 테이블이 BlockNode 클래스로 이동했습니다.

블록별로 다뤄야 하니 당연하죠.


// Symbol.cs

    internal class SymbolTable
    {
        public static void Init()
        {
            blockNodes.Clear();
            Open();
        }

        public static BlockNode Open()
        {
            var blockNode = new BlockNode();
            blockNodes.Push(blockNode);
            return blockNode;
        }

        public static void Close() => blockNodes.Pop();

        public static Symbol AddSymbol(Token token)
        {
            if (token.Type != TT.Identifier)
            {
                throw new HIException(ET.SyntaxError, Id.InvalidSyntax, token);
            }
            var symbol = new Symbol(token);
            blockNodes.Peek().AddSymbol(token, symbol);
            return symbol;
        }

        public static bool Find(Token token, out Symbol symbol) => Find(token.Text, out symbol);

        public static bool Find(string name, out Symbol symbol)
        {
            foreach(var blockNode in blockNodes)
            {
                if (blockNode.GetSymbol(name, out symbol)) { return true; }
            }
            symbol = null;
            return false;
        }

        public static Symbol GetSymbol(Token token)
        {
            if (Find(token, out Symbol symbol)) { return symbol; }
            throw new HIException(ET.NameError, Id.NameNotDefined, token);
        }

        public static Symbol GetVariable(Token token)
        {
            var symbol = GetSymbol(token);
            if (symbol.Function != null) { throw new HIException(ET.TypeError, Id.FunctionIdentifier, token); }
            return symbol;
        }

        public static Symbol GetFunction(Token token)
        {
            var symbol = GetSymbol(token);
            if (symbol.Function == null) { throw new HIException(ET.TypeError, Id.NotFunctionIdentifier, token); }
            return symbol;
        }

        private static readonly Stack blockNodes = new Stack();
    }
예전과는 다르게 블록별로 변수를 다루고 해당 블록에 찾는 변수가 없을 경우 위의 블록으로 올라가 다시 변수를 찾는 과정을 반복해야 합니다.

그러기 위해서 새롭게 생긴 클래스가 SymbolTable 클래스입니다.


// Test.cs > Test > TestParser > tests

def main() {
    print("구구단 예제")
    for dim i in range(2, 10) {
        for dim j in range(2, 10) {
            print(i, " * ", j, " = ", i * j)
        }
    }
}
맨 위의 실행 결과에 출력 결과가 나와 있는 유닛 테스트에 구현되어 있는 구구단 예제 소스 코드입니다.

main() 함수는 어떠한 블록 내에 있지 않으니 심볼 테이블도 없습니다.

따라서 Parser가 실행하기 전에는 반드시 SymbolTable.Init 메소드를 호출해야 하고 실제로 Parser.Init 메소드에 포함되어 있습니다.

그 이후는 위의 코드들을 쭉 보면 어렵지 않게 이해할 수 있을 겁니다.


EBNF : function_statement

// Parser.cs > Parser

        // EBNF : function_statement = "def", identifier, "(", [ identifier, { ",", identifier } ],
        //                             ")", block ;
        private void ParseFunction()
        {
            Match(KT.Def);
            var symbol = AddSymbol();
            var node = SymbolTable.Open();
            var function = new FunctionNode(node);
            symbol.Function = function;

            Match(TT.LeftParens);
            if (CurrentToken.Type != TT.RightParens)
            {
                function.AddSymbol(AddSymbol());
                while (CurrentToken.Type != TT.RightParens)
                {
                    Match(TT.Comma);
                    function.AddSymbol(AddSymbol());
                }
            }
            MoveNext();

            ParseBlockWithoutCreatingSymbolTable(node);
            SymbolTable.Close();
        }

// Node.cs

    internal class FunctionNode : Node
    {
        public List Symbols { get; } = new List();

        public override long Visit => block.Visit;

        public FunctionNode(Node block) => this.block = block;

        public void AddSymbol(Symbol symbol) => Symbols.Add(symbol);

        private readonly Node block;
    }
함수의 정의를 파싱하고 실행하는 부분으로 어렵지 않은 내용입니다.


EBNF : call_function

// Parser.cs > Parser

        // EBNF : call_function = identifier, "(", [ expression, { ",", expression } ], ")" ;
        private Node ParseCallfunciton(Token token)
        {
            var callFunction = new CallNode(token);

            Match(TT.LeftParens);
            if (CurrentToken.Type != TT.RightParens)
            {
                callFunction.AddExpression(ParseExpression());
                while (CurrentToken.Type != TT.RightParens)
                {
                    Match(TT.Comma);
                    callFunction.AddExpression(ParseExpression());
                }
            }
            Match(TT.RightParens);
            return callFunction;
        }

// Node.cs

    internal class CallNode : Node
    {
        public override long Visit
        {
            get
            {
                var function = SymbolTable.GetFunction(functionToken).Function;
                if (function.Symbols.Count != expressions.Count)
                {
                    throw new HIException(ET.TypeError, Id.InvalidArgumentsNumber, functionToken);
                }
                for (int i = 0;i < expressions.Count;i++)
                {
                    function.Symbols[i].IntegerValue = expressions[i].Visit;
                }
                foreach(var expression in expressions) {  }
                return function.Visit;
            }
        }

        public void AddExpression(Node expression) => expressions.Add(expression);

        public CallNode(Token token) => functionToken = token;

        private readonly List expressions = new List();
        private readonly Token functionToken;
    }
함수의 호출을 파싱하고 실행하는 부분으로 이 또한 어렵지 않은 내용입니다.

6번째 강좌를 마칩니다.

6
1
  • 댓글 6

  • asmpro
    681
    2019-05-04 20:05:37

    설명을 디테일하게 하지 않는 이유는 불특정 다수를 상대로 자세한 설명보다는 소스 코드의 가독성을 높인 후 질답을 통하여 설명하는 것이 좀 더 효율적이라고 생각했기 때문인데 질문이 없다 보니 별 의미가 없게 돼버렸네요.

    어찌 됐든 강좌 중 인터프리터 편은 이걸로 마칩니다.
    이 강좌의 목표는 컴파일러를 만드는 것이고 인터프리터 편은 컴파일러를 개발하기 전에 이해를 돕기 위한 몸풀기의 용도였기에 구구단이나 팩토리얼을 실행할 수 있는 수준에서 마무리를 짓고 다음 편부터는 컴파일러를 만드는 강좌를 시작하겠습니다.

    2
  • BlackJ
    12
    2019-05-07 11:16:18 작성 2019-05-07 11:16:53 수정됨

    내용이 어렵다보니 질문할 거리도 생각이 안 난게 아닐까 싶네요^^;; 쉽지 않은 내용일 텐데 감사드립니다.

    0
  • asmpro
    681
    2019-05-07 12:56:06

    @BlackJ

    이미 컴파일러 이론은 책이나 인터넷 강좌들이 흔하게 있어서 실제 어떤 식으로 구현을 할 수 있는지 보여주는 것에 초점을 맞췄는데 아무래도 설명이 많이 부족했던 것 같습니다.

    0
  • Signo
    81
    2019-05-08 22:00:23

    컴파일러 이론을 1도 몰랐지만 많은 도움이 되었습니다.


    컴파일러는 특정 텍스트 파일을 읽어,

    미리 정의된 문법규칙에 맞게 파싱하여 구문트리를 생성하고(lexer),

    그 구문 트리에 맞게 인터프리터에서 연산이 이루어진다 정도로 이해하고 있는데요.


    자바스크립트 엔진의 경우도 이와 유사한 구조일까요?(물론 무지하게 복잡하겠지만요)

    가령 자바스크립트에서 Lexical Scoping을 가진다는 의미가,

    something.js란 텍스트 파일을 한줄씩 순회하며 Lexer가 구문트리를 형성할때, 함수가 선언되는 곳 주변 구문을 보고 그함수의 scope를 컴파일러가 메모리 로 관리한다고 이해하면 일리가 있는 말일까요?

    미리 고맙습니다.





    0
  • asmpro
    681
    2019-05-08 23:24:13 작성 2019-05-08 23:28:17 수정됨

    @Signo

    lexer는 코드를 토큰으로 변환하고 parser에서 구문 트리를 생성합니다.

    Lexical Scoping는 간단하게 설명하기 힘들기에 설명이 길어질 것 같아 링크를 남깁니다.

    https://bestalign.github.io/2015/07/12/Lexical-Scope-and-Dynamic-Scope/

    https://meetup.toast.com/posts/86


    일반적인 Lexical Scoping방식 언어들은 변수, 함수가 선언될 때 해당 변수, 함수가 사용될 수 있는 scope가 결정이 됩니다.

    보통 Parser에서 이루어 지는데 동일한 심볼 테이블에 속성으로 scope를 정의할 수도 있고 제가 올린 강좌처럼 scope마다 심볼 테이블을 생성하여 scope 속성을 사용하지 않을 수도 있겠죠.

    심볼 테이블을 분리하던 하나의 심볼 테이블 내에 scope 속성으로 구별을 하던 간에 실행 파일이나 중간 코드로 완전히 컴파일이 끝나기 전에는 컴파일러가 메모리로 관리한다는 표현도 틀린 말은 아닙니다.

    1
  • Signo
    81
    2019-05-09 00:03:54

    @asmpro

    와 환상적인 레퍼런스 정말 감사합니다. 

    C#을 몰라 대충 눈대중으로 코드를 봤는데

    반성하고 정독한 다음, 궁금한 것 나중에 답글로 남겨도 될까요?


    감사합니다. 좋은 밤 되세요.

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