asmpro
681
2019-05-01 12:35:33 작성 2019-05-04 19:54:20 수정됨
0
558

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


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

다섯 번째 프로젝트 Hybrid Interpreter 5 (HI5)

]test
---------- Test.TestLexer 시작
========== Test.TestLexer 완료: 성공 29, 실패 0
---------- Test.TestParserLine 시작
========== Test.TestParserLine 완료: 성공 27, 실패 0
---------- Test.TestParser 시작
========== Test.TestParser 완료: 성공 11, 실패 0
]dim z = 0
0
]z += 5
5
]z -= 3
2
]z *= 10
20
]z <<= 2
80
]z >>= 2
20
]z || 3
1
]z | 3
23
]!z
0
]!0
1
]z
20
]z > 10
1
]z < 10
0
]if (z == 20) { print(5) }
5
5
]while (z > 0) { z -= 1 }
0
]dim y = 0
0
]for z in range(1,11) { y += z }
55
]exit
계속하려면 아무 키나 누르십시오 . . .
위는 HI5의 실행 결과입니다.

HI5 프로젝트에는 C#에서 지원하는 대부분의 연산자와 print, if, while, for 키워드가 추가되었습니다.

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

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


EBNF 문법

우선 C#의 모든 연산자를 우선순위가 높은 순서대로 나열해 보겠습니다.

SymbolType of Operation
[ ] ( ) . -> ++ -- (postfix)Expression
sizeof & * + - ~ ! ++ -- (prefix)Unary
typecastsUnary
* / %Multiplicative
+ -Additive
<< >>Bitwise shift
< > <= >=Relational
== !=Equality
&Bitwise-AND
^Bitwise-exclusive-OR
|Bitwise-inclusive-OR
&&Logical-AND
||Logical-OR
? :Conditional-expression
= *= /= %= += -= <<= >>= &= ^= |=Simple and compound assignment
,Sequential evaluation
위의 연산자 중 현재 사용할 수 없는 연산자들을 제외하고 EBNF문법에 추가합니다.

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 ], ")" ;
print = "print", "(", expression, ")" ;

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 | ( "(", expression, ")" ) ;

identifier = ( alphabet | "_" ), { alphabet | "_" | integer } ;
integer = digit, { digit } ;
alphabet = "A" | "B" | ...... | "z" ;
digit = "0" | "1" | ...... | "9" ;
복잡해 보이지만 expression 부터 factor 까지는 예전 강좌에서 보여준 것과 마찬가지로 연산자들의 우선 순위대로 EBNF 문법에 추가한 것입니다.

단지 연산자의 개수가 많아서 복잡해 보일 뿐입니다.

그 외에는 추가된 키워드에 해당하는 EBNF 문법이 추가되었습니다.


Token.cs

    // Token Type
    internal enum TT : byte
    {
        Invalid,

        LF = (byte)'\n',
        CR = (byte)'\r',
        Space = (byte)' ',

        LeftParens = (byte)'(',
        RightParens = (byte)')',

        Plus = (byte)'+',
        Minus = (byte)'-',
        Mul = (byte)'*',
        Div = (byte)'/',
        Remainder = (byte)'%',

        BitAnd = (byte)'&',

        BitOr = (byte)'|',
        BitXor = (byte)'^',

        LessThan = (byte)'<',
        GreaterThan = (byte)'>',

        Assign = (byte)'=',
        Not = (byte)'!',

        BeginBlock = (byte)'{',
        EndBlock = (byte)'}',

        Comma = (byte)',',

        EOF = 127,

        Equal,
        NotEqual,

        LessThanEqual,
        GreaterThanEqual,

        And,
        Or,

        LeftShift,
        RightShift,

        Integer,
        Identifier,
        Keyword,
    }
많은 연산자가 추가된 만큼 토큰 타입 열거자에 큰 변화가 있었습니다.

하나의 기호 문자인 토큰 타입은 기존과 마찬가지로 토큰 타입과 문자가 1:1 매칭이 이루어졌지만 두 개의 기호 문자인 토큰 타입은 EOF 타입 위에 따로 정의하였습니다.


이항 연산자

// Node.cs > BinaryNode Class

        public override long Visit
        {
            get
            {
                long leftValue = Left.Visit;
                long rightValue = Right.Visit;

                switch (Operator.Type)
                {
                    case TT.Plus: return leftValue + rightValue;
                    case TT.Minus: return leftValue - rightValue;
                    case TT.Mul: return leftValue * rightValue;

                    case TT.Div:
                        CheckDivisionByZero(rightValue, Operator);
                        return leftValue / rightValue;
                    case TT.Remainder:
                        CheckDivisionByZero(rightValue, Operator);
                        return leftValue % rightValue;

                    case TT.Equal: return leftValue == rightValue ? 1 : 0;
                    case TT.NotEqual: return leftValue != rightValue ? 1 : 0;
                    case TT.LessThan: return leftValue < rightValue ? 1 : 0;
                    case TT.LessThanEqual: return leftValue <= rightValue ? 1 : 0;
                    case TT.GreaterThan: return leftValue > rightValue ? 1 : 0;
                    case TT.GreaterThanEqual: return leftValue >= rightValue ? 1 : 0;

                    case TT.And: return (leftValue == 0 ? 0 : 1) & (rightValue == 0 ? 0 : 1);
                    case TT.Or: return (leftValue == 0 ? 0 : 1) | (rightValue == 0 ? 0 : 1);

                    case TT.BitAnd: return leftValue & rightValue;
                    case TT.BitOr: return leftValue | rightValue;
                    case TT.BitXor: return leftValue ^ rightValue;

                    case TT.LeftShift: return leftValue << (byte)rightValue;
                    case TT.RightShift: return leftValue >> (byte)rightValue;
                }
                HIDebug.Fail(Operator.Type, Id.InvalidOperator.ToText());
                return 0;
            }
        }
대입 연산자를 제외한 모든 이항 연산자들은 위의 코드에서 처리합니다.

위의 코드를 보면 비교 연산자와 논리 연산자는 조건을 만족할 경우 1, 아닐 경우 0으로 처리하는 것을 볼 수 있습니다.

이 강좌의 궁극적인 목표는 빠르고 가벼운 컴파일러를 만드는 것이고 boolean을 어셈블리어로 변환할 때 가장 빠르고 가벼운 방법은 0 또는 1로 변환하는 것입니다.


Lexer.cs

        public Token GetNextToken()
        {
            while (true)
            {
                var type = CurrentTokenType;
                var column = currentColumn;
                switch (type)
                {
                    case TT.Invalid:
                        throw new HIException(ET.SyntaxError, Id.InvalidCharacter, column, currentLine);

                    // 줄바꿈은 CR+LF, CR, LF 중에 하나가 사용되는데 CR 단독은 과거 8비트 시절 사용되었고
                    // 현재는 CR+LF 또는 LF가 사용된다. CR은 공백처럼 스킵하고 LF를 줄바꿈으로 처리한다.
                    // CR은 실제 화면에 출력되는 문자가 아니기 때문에 currentColumn은 증가시키지 않기 위해
                    // MoveNext()를 사용하지 않는다.
                    case TT.LF: currentPos++; currentLine++; currentColumn = 0; continue;
                    case TT.CR: currentPos++; continue;

                    case TT.Space: SkipSpace(); continue;

                    case TT.Integer: return new Token(GetInteger(), column, currentLine);

                    case TT.Identifier: return new Token(GetIdentifier(), column, currentLine);

                    case TT.Assign:
                    case TT.Not:
                    case TT.LessThan:
                    case TT.GreaterThan:
                    case TT.BitAnd:
                    case TT.BitOr:
                        MoveNext();
                        var nextType = CurrentTokenType;
                        for(int i = 0;i <= twoCharOperators.GetUpperBound(0);i++)
                        {
                            if (twoCharOperators[i,0] == type && twoCharOperators[i, 1] == nextType)
                            {
                                type = twoCharOperators[i, 2];
                                MoveNext();
                                break;
                            }
                        }
                        return new Token(type, column, currentLine);

                    default: MoveNext(); return new Token(type, column, currentLine);
                }
            }
        }

        private readonly TT[,] twoCharOperators =
        {
            { TT.Assign, TT.Assign, TT.Equal },
            { TT.Not, TT.Assign, TT.NotEqual },
            { TT.LessThan, TT.Assign, TT.LessThanEqual },
            { TT.GreaterThan, TT.Assign, TT.GreaterThanEqual },
            { TT.BitAnd, TT.BitAnd, TT.And },
            { TT.BitOr, TT.BitOr, TT.Or },
            { TT.LessThan, TT.LessThan, TT.LeftShift },
            { TT.GreaterThan, TT.GreaterThan, TT.RightShift },
        };
GetNextToken() 메소드는 소스 코드를 토큰 타입으로 변환하는 함수입니다.

배열을 이용하여 두 개의 기호 문자를 하나의 토큰 타입으로 변환합니다.


EBNF : expression

// Parser.cs > Parser Class

        private Node ParseExpression()
        {
            if (CurrentToken.Type == TT.Identifier && currentPos < tokens.Count - 2 &&
                (tokens[currentPos + 1].Type == TT.Assign ||
                tokens[currentPos + 2].Type == TT.Assign))
            {
                var symbol = GetSymbol(CurrentToken);
                MoveNext();
                var token = CurrentToken;
                if (token.Type != TT.Assign) { MoveNext(); }
                MoveNext();
                return new AssignNode(symbol, token, ParseLogicalOr());
            }

            return ParseLogicalOr();
        }

// Node.cs > AssignNode Class

        public override long Visit
        {
            get
            {
                long value = Expression.Visit;

                switch (AssignOperator.Type)
                {
                    case TT.Assign: Identifier.IntegerValue = value; break;
                    case TT.Plus: Identifier.IntegerValue += value; break;
                    case TT.Minus: Identifier.IntegerValue -= value; break;
                    case TT.Mul: Identifier.IntegerValue *= value; break;

                    case TT.Div:
                        CheckDivisionByZero(value, AssignOperator);
                        Identifier.IntegerValue /= value;
                        break;
                    case TT.Remainder:
                        CheckDivisionByZero(value, AssignOperator);
                        Identifier.IntegerValue %= value;
                        break;

                    case TT.LeftShift: Identifier.IntegerValue <<= (byte)value; break;
                    case TT.RightShift: Identifier.IntegerValue >>= (byte)value; break;
                    case TT.BitAnd: Identifier.IntegerValue &= value; break;
                    case TT.BitXor: Identifier.IntegerValue ^= value; break;
                    case TT.BitOr: Identifier.IntegerValue |= value; break;

                    default: throw new HIException(ET.SyntaxError, Id.InvalidSyntax, AssignOperator);
                }
                return Identifier.IntegerValue;
            }
        }
expression EBNF 문법의 대입 연산자들은 "=" 연산자 또는 산술, 비트 연산자와 "=" 연산자의 혼합 연산자입니다.

따라서 첫 번째 토큰이 식별자, 두 번째 또는 세 번째 토큰이 "=" 연산자이면 대입 연산자가 됩니다.


EBNF : if_statement

// Parser.cs > Parser Class

        private Node ParseIfStatement()
        {
            var ifNodes = new List();
            Match(TT.LeftParens);
            ifNodes.Add(ParseExpression());
            Match(TT.RightParens);
            ifNodes.Add(ParseBlock());

            while (IsKeyword(KT.Elif))
            {
                MoveNext();
                Match(TT.LeftParens);
                ifNodes.Add(ParseExpression());
                Match(TT.RightParens);
                ifNodes.Add(ParseBlock());
            }
            Node elseNode = null;
            if (IsKeyword(KT.Else))
            {
                MoveNext();
                elseNode = ParseBlock();
            }
            return new IfNode(ifNodes, elseNode);
        }

// Node.cs > IfNode Class

        public override long Visit
        {
            get
            {
                for (int i = 0;i < IfNodes.Count; i += 2)
                {
                    if (IfNodes[i].Visit != 0) { return IfNodes[i + 1].Visit; }
                }
                if (ElseNode != null) { return ElseNode.Visit; }
                return 0;
            }
        }
if, elif, else의 구현은 생각보다 단순합니다. 위의 코드를 보면 이해할 수 있을 겁니다.


EBNF : while_statement

// Parser.cs > Parser Class

        private Node ParseWhileStatement()
        {
            Match(TT.LeftParens);
            var expression = ParseExpression();
            Match(TT.RightParens);
            return new WhileNode(expression, ParseBlock());
        }

// Node.cs > WhileNode Class

        public override long Visit
        {
            get
            {
                long value = 0;
                while (Expression.Visit != 0) { value = Block.Visit; }
                return value;
            }
        }
if 보다 더 간단한 while 입니다.


EBNF : for_statement

// Parser.cs > Parser Class

        // EBNF : for_statement = "for", [ [ "dim" ], identifier, "in" ], "range",
        //                        "(", expression, [ ",", expression ], [ ",", expression ], ")" ;
        private Node ParseForStatement()
        {
            Symbol identifier = null;
            if (IsKeyword(KT.Dim))
            {
                MoveNext();
                identifier = new Symbol(CurrentToken);
                Match(TT.Identifier);
                Match(KT.In);
            }
            else if (CurrentToken.Type == TT.Identifier)
            {
                identifier = GetSymbol(CurrentToken);
                MoveNext();
                Match(KT.In);
            }

            Match(KT.Range);
            Match(TT.LeftParens);

            Node end = null;
            Node step = null;
            var start = ParseExpression();
            
            if (CurrentToken.Type == TT.Comma)
            {
                MoveNext();
                end = ParseExpression();
                if (CurrentToken.Type == TT.Comma)
                {
                    MoveNext();
                    step = ParseExpression();
                }
            }
            Match(TT.RightParens);
            return new ForNode(identifier, start, end, step, ParseBlock());
        }

// Node.cs > ForNode Class

        public override long Visit
        {
            get
            {
                long step = Step == null ? 1 : Step.Visit;
                long value = 0;
                if (Identifier == null)
                {
                    for (long i = Start; i < End.Visit; i += step) { value = Block.Visit; }
                }
                else
                {
                    for (Identifier.IntegerValue = Start;
                        Identifier.IntegerValue < End.Visit; Identifier.IntegerValue += step)
                    {
                        value = Block.Visit;
                    }
                }
                return value;
            }
        }

        public ForNode(Symbol identifier, Node start, Node end, Node step, Node block)
        {
            Identifier = identifier;
            if (end == null)
            {
                Start = 0;
                End = start;
            }
            else
            {
                Start = start.Visit;
                End = end;
            }
            Step = step;
            Block = block;
        }

for 문은 파이썬의 for 문과 유사하나 다른 점은 for와 range 사이를 생략할 수 있다는 겁니다.

for 문에서 반복을 위해 사용하는 변수가 for 문 내의 블록에서 사용되지 않을 경우 인터프리터 내부의 변수를 이용하는 것이죠.

감안하고 위의 코드를 보면 쉽게 이해할 수 있을 겁니다.


5번째 강좌를 마칩니다.

1
1
  • 댓글 0

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