int $0x80

2. Kaleidoscope: Implementing a Parser and AST 한글 번역 본문

컴퓨터공부/엘엘비엠

2. Kaleidoscope: Implementing a Parser and AST 한글 번역

cd80 cd80 2017.07.20 17:27

2.1. Chapter 2 Introduction

이번장에서는, 저번장에서 구현한 Lexer를 이용해 Parser를 만들고, Parser를 이용해 소스코드의 AST를 만듭니다.


우리가 구현할 파서는 Recursive Descent Parsing과 Operator-Precedence Parsing을 같이 사용합니다.

수 연산식을 파싱할때는 Operator-Precedence Parsing을 이용하고, 그 외 모든 다른 구문들은 Recursive Descent Parsing방식으로 파싱합니다


파싱을 바로 구현하기전에 소스코드 파싱을 해서 만들고자 하는 AST에 대해 먼저 설명합니다




2.2. The Abstract Syntax Tree

컴파일러에서 소스코드에 대한 AST를 만드는 것은 AST를 구성함으로써 다른 컴파일 과정들이 더 수월해지기 때문입니다(code -> LLVM IR generation같은 작업들)

AST를 만들기 위해서 우선 AST의 노드로 들어갈 각 언어 요소들에 대한 클래스를 정의하는것부터 시작합니다.

다시말해, NumberExprAST, FunctionAST, BinaryExprAST등 각 요소별 클래스를 정의합니다.


Parser.h

ExprAST는 모든 표현식을 나타내는 베이스 클래스입니다. 다른 클래스들이 모두 ExprAST를 상속받습니다.

NumberExprAST는 1.0과 같은 숫자데이터를 처리하기 위한 클래스입니다


이렇게 클래스를 정의할땐, 각 노드의 타입뿐 아니라, 각 노드가 갖고 있는 실제 값을 저장해야 합니다. 따라서 NumberExprAST도 인스턴스 변수를 둬서 그 숫자노드의 실제 값이 뭔지 저장해둡니다.


약간은 지루하겠지만, 먼저 모든 AST클래스를 정의한 뒤에 그걸 처리하는 파서 메소드를 작성하겠습니다



NumberExprAST 선언부와 #endif 사이에 쓰시면 됩니다.

여기까지 하고 테스트 해보시려면 그냥 Parser.h -> Parser.cpp 로 바꾸고 clang++으로 컴파일 하면되는데, 그냥 컴파일하면 에러가 하나 납니다.

맨 마지막줄의 std::move(Args) 에서 나는데, clang++ -c Parser.cpp -std=c++11 로 컴파일하시면 해결됩니다.


여기까지해서, 우리 언어가 갖는 모든 표현식 종류를 정의했습니다. 예를들어 VariableExprAST는 변수명을 저장할거고, BinaryExprAST는 '+', '*' 등의 연산자를, CallExprAST는 함수 호출문을 정의해줍니다.

하지만 이 노드들로 언어 전체를 설명하기엔 부족함이 많죠, 지금 우리 언어에는 아직 조건분기가 없고, 따라서 튜링완전하지 않습니다. 이런 여러 언어의 요소들을 앞으로 더 추가해나가겠지만, 이번 글에서는 간단한 파서를 작성하는게 최종 목표이기 때문에 최대한 언어의 요소를 간단하게 한정합니다


그다음 클래스는 두개입니다.

지금 우리는 함수 호출하는거는 분석하지만 함수 자체는 관리하지 못합니다.

함수 자체를 관리하기 위한 클래스를 추가해줍니다

CallExprAST와 #endif사이에 쓰면 됩니다


여기까지, AST를 구성하는 모든 클래스의 정의를 마쳤습니다.

이제 이걸 바탕으로 파서를 구현할 수 있습니다



2.3. Parser Basics

소스코드를 파싱해 AST를 만든다는 것은, 예를들면 이런것입니다

x + y 라는 코드를 파싱해서, 여기에는 두개의 VariableExprAST가 있고, 이 두개가 BinaryExprAST에 의해 서로 연결되어 있다는 것을 분석하는 작업입니다.

이러한 코드로 x+y라는 텍스트를 분석하겠다는 것입니다.


이 작업을 자동으로 하기 위해, Lexer에서 구현했던 gettok함수를 이용해 텍스트에서 토큰을 파싱합니다


Parser.cpp

CurTok이라는 임시변수를 선언했습니다. 파서에서 구현할 모든 함수들에서 CurTok이 '현재' 파싱되고 있는 토큰이라는 것을 모두 전제한 상태에서 작동합니다.



파서에서는 AST를 구성하면서, 소스코드 문법에 대한 검사도 함께 진행합니다. 따라서 문법오류가 발생했을 때 에러를 띄워줄 함수를 정의해줍니다


이제 실제로 토큰을 파싱하는 코드들을 작성해봅시다



2.4. Basic Expression Parsing

먼저, 가장 처리하기 쉬운 숫자부터 처리해보겠습니다


갑자기 NumVal이 나왔는데, 이건 Lexer에서 선언한 전역변수 입니다. 



Parser.cpp의 위에 extern으로 선언해줍니다.


ParseNumberExpr함수는 현재 토큰이 tok_number일때 호출될것이기 때문에, Lexer에서 NumVal에 값이 설정된단것도 알고 있어서 바로 NumberExprAST 클래스를 생성합니다


여기서 파서의 한가지 특징이 나오는데, 각 타입에 대한 파서는 현재 타입에 대해 처리하고(eat한다고 표현합니다), 다음 파서 함수가 잘 작동할 수 있게 다음 토큰을 읽어들여줍니다.

예를들어 identifier를 처리한다면 identifier의 문자열 길이만큼 token을 처리하고 그 다음 문자를 가르키게 설정하고 종료하겠죠

이런 파싱 방식은 재귀하향파싱 방식에서 표준처럼 사용되는 방식입니다.

한가지 더 보죠


괄호식을 파싱하는 코드입니다. 현재 토큰이 '(' 일때 출력될것이고, 괄호 안의 표현식을 ParseExpression함수를 호출해 분석합니다.

func(arg1, arg2)

for(haha = 1; haha < 10; haha++) 이런 괄호는 이걸로 분석 안되는거 아니냐는 의문을 가지실 수 있는데 함수호출이나 for문등의 괄호는 따로 처리되고, 이건 연산식에서 사용되는 괄호를 처리합니다.


3가지를 짚고 넘어가겠습니다.

1. 이 함수에서는 LogError를 이용해 에러를 출력하고, 그 에러메세지는 원래 문법상 현재 와야하는 문자가 뭔지를 알려줍니다. 이런식으로 각각 파서에서는 잘못된 문법을 잡아 출력해줍니다.

2. 모든걸 한번에 분석하는 것이 아닌, ParseExpression함수를 이용해 작업을 분담합니다. 하나 재밌는것은 ParseExpression함수에서도 ParseParanExpr을 호출할수 있다는 겁니다.

예를들어

(haha == 1 && (hoho == 2 || hehe == 3)) 등과 같은 코드를 처리하기 위해서죠

3. 괄호는 단순 텍스트로 처리되고, AST에는 추가되지 않습니다. 괄호는 단순히 표현식들의 그룹핑을 위해 존재하는것이고 그 자체로 큰 의미가 있지 않기 떄문입니다. 그래서 파서가 AST를 구성하고 나면 괄호는 필요하지 않습니다



다음으로 변수 참조와 함수 호출을 처리합니다


지금까지 작성한 함수들과 전체적인 스타일이 비슷한 루틴입니다. 재귀호출을 하고, 예외처리를 하고, 토큰 하나를 더 읽어들여 현재 식별자가 변수참조인지 함수호출인지 알아냅니다

지금까지 처리한 토큰들은 IdentifierExpr, NumberExpr, ParenExpr이고, 이 세가지를 primary expression이라고 부르겠습니다.이렇게 나누는 이유는 나중에 user defined operator들을 처리하기 수월해지기 때문입니다.


이제 수식을 파싱해보겠습니다. 수식파싱은 조금더 복잡합니다



2.5. Binary Expression Parsing

수식을 파싱하려면 수식 안에 있는 연산자들과 표현식들의 우선순위를 판별해야 합니다.

연산자가 한두개는 아니기 때문에 범용적으로 여러 우선순위의 연산자들을 잘 처리해줘야 합니다

우선순위를 처리하기 위한 방법들은 많지만 깔끔하고 효율적인 방식인 Operator-Precedence Parsing을 사용하겠습니다

Operator-Precedence Parsing은 각 연산자 우선순위에 맞게 재귀적으로 수식을 처리합니다

먼저, 연산자들과 각각의 우선순위의 맵을 생성합니다

BinOpPrecedence라는 맵을 전역변수로 선언했고, 현재 토큰을 BinOpPrecedence의 키로 써서 우선순위를 가져오는 함수를 작성했습니다.

이 BinOpPrecedence는 main함수에서 후에 초기화 됩니다.


Kaleidoscope는 기본적으로 연산자가 4개입니다. 직접 있으면 좋겠다 싶은 연산자들도 구현해보세요

이렇게 맵을 만들어서 우선순위를 관리하면, 새로운 연산자를 추가하기도 쉽고 파싱 알고리즘이 특정 연산자들에 의존하지 않는, 즉 범용적인 파싱이 가능합니다.


Operator-Precedence Parsing은 우선 수식 전체를 일정 단위로 잘라냅니다

예를들어

a+b+(c+d)*e*f+g 라는 식이 있다면

(binary operator, primary expression) 의 단위로 잘라냅니다

a 는 첫 시작이니 그대로 냅두고

a (+, b) (+, (c+d)) (*, e) (*, f) (+, g) 이런식으로 나눕니다

괄호식은 그 자체로 primary expression이기 때문에 그 안에 있는것은 ParsePrimary함수에 의해 재귀적으로 파싱됩니다


전체 표현식은 우선 처음에 primary expression하나가 있고, 그다음에 (binop, primaryexpr)가 올수도 있고 안올수도 있습니다

x 도 expression이고

x+y+z 도 expression입니다

이걸 코드로 분석해봅시다


ParseBinOpRHS는 parse binop, rhs 입니다

(binop, primaryexpr) 에서 primaryexpr이 RHS라고 보시면 됩니다(Right Hand Side, 우항)

ParseBinOpRHS는 수식을 모두 파싱할때까지 재귀적으로 호출됩니다


ParseBinOpRHS함수의 첫 번째 인자는 현재 파싱된 식 중에 제일 높은 우선순위를 갖고 있습니다

GetTokPrecedence함수가 현재 토큰이 연산자가 아니면 -1을 리턴하기 때문에 if (TokPrec < ExprPrec)에서 파싱은 종료됩니다


그리고 우선순위가 높은것부터 먼저 처리해야 하기 때문에, ExprPrec보다 우선순위가 낮은것은 일단 스킵하고 높거나 같은것부터 먼저 처리합니다


위의 조건문에 의해서 현재 CurTok은 무조건 연산자입니다.

연산자를 BinOp에 저장하고 그다음 토큰을 읽어들이고, primary expression을 파싱합니다.

이 때 RHS에 nullptr이 리턴될경우 expression이 없다는 것이고, 이는 문법오류기 때문에 nullptr를 리턴해줍니다.


여기까지 딱 한번 도달했다고 치면, 아까 예로 든 식 a+b+(c+d)*e*f+g 에서

a + b 까지 분석했고 BinOp='+' RHS='b' 가 된 상태입니다

여기서 이걸 바로 처리하느냐 아니면 나중에 처리하느냐는 RHS의 다음 operator 우선순위와 현재 BinOp의 우선순위를 비교해야 알 수 있습니다

즉, a + b * 처럼 RHS다음 operator가 *라면 +보다 우선순위가 높은것이기 때문에 현재 식은 처리하지 않고 다음 식부터 처리합니다.(재귀적으로 그다음 항에 대해 ParseBinOpRHS를 호출하면 함수가 끝나고 돌아와서 다시 a+b 와 그 식을 처리해줄 수 있겠죠.)


설명이 조금 어려울 수도 있지만 그렇게 어려운 내용은 아닙니다. 그럼 코드로 보죠


ParsePrimary함수는 현재 토큰들을 모두 처리한뒤 getNextToken함수를 호출해 다음토큰까지 읽어들입니다.

따라서 이 위의 코드까지 실행된 뒤에는 CurTok은 RHS다음 연산자를 갖게 됩니다

그래서 바로 GetTokPrecedence를 하면 RHS다음 연산자 우선순위를 가져오게 됩니다

이걸 현재 Precedence와 비교합니다


우선 if문 안에는 현재 처리하고 있는 식보다 다음식이 우선순위가 더 높은경우이고,

if문 밖에는 항상 LHS가 RHS보다 우선순위가 더 높습니다(우선순위가 더 높으면 if문안에서 모두 처리되기 때문에)

그런데 한가지 재밌는것은 TokPrec + 1 을 Precedence로 설정해서 함수를 호출한다는 것입니다

RHS들을 쭉 돌면서, 현재 TokPrec과 같거나 작은 Precedence가 발견되면 거기서 멈추겠다는 겁니다

a+b+(c+d)*e*f+g

a+를 빼고 b + (c+d) * e *f + g 여기부터 봅시다

b + (c+d) * e * f + g 가 있을 때

b 가 LHS라고 한다면

RHS는 (c+d) * e * f 까지만 이어야 합니다

즉 TokPrec과 같은 우선순위를 갖는 연산자까지 RHS로 묶어버릴 필요는 없다는 겁니다

이를 위해서 TokPrec + 1 을 인자로 넣어줍니다


이렇게까지 처리가 끝나면, 그 다음 루프에서 + g 까지 모두 처리가 됩니다

어렵긴 했지만, 재귀호출만 잘 이해한다면 이해할 수 있는 처리입니다

여기까지해서 모든 expression에 대한 파싱이 끝났습니다


여기까지 한걸 컴파일해보려면 우선 map헤더파일을 추가해주고

#include <map>


이렇게 함수 선언부를 코드 맨위쪽에 추가합니다


cd80@Sungui-MacBook-Pro ~/study/Kaleidoscope » clang -c Parser.cpp -std=c++14

cd80@Sungui-MacBook-Pro ~/study/Kaleidoscope »

오류 없이 잘 컴파일됩니다.




2.6. Parsing the Rest

마지막으로 함수 프로토타입과 구현부를 파싱해봅시다

표현식 파싱을 제대로 이해하셨다면 딱히 다를게 없습니다. 수식 파싱보다도 훨씬 쉽습니다


참고로 Kaleidoscope에서의 함수는 

def f(a, b) <Expression> 의 형태입니다.

그래서 함수 구현체를 파싱하려면 먼저 Prototype을 파싱하고, ParseExpression을 한번만 호출해주면됩니다



추가로, 외부함수나 c언어에서와 같은 forward declaration을 지원하기 위한 extern을 처리합니다

extern은 프로토타입만 있는 함수 선언입니다


마지막으로, 파이썬이나 자바스크립트에서처럼 함수 없이 그냥 있는 코드들을 처리해줍니다

이 코드들을 인자가 없는 익명함수 안에 있는 코드로 만들어 처리합니다



이제 다 완성됐습니다. 고생하셨습니다

저번장에서 만든 메인함수를 수정해서 이번 글에서 작성한 코드를 테스트해봅시다.


main.cpp


Parser.h


Parser.cpp




0 Comments
댓글쓰기 폼