ANTLR를 이용한 tinyPython to Jasmin 컴파일러 만들기. - 2

* 본 내용은 충남대학교 조은선 교수님의 컴파일러 개론을 수강하고 작성한 글입니다.

 

저번 글에서는 전체적으로 Run 버튼을 누르고 나서 어떻게 프로그램이 실행되는지 과정을 살펴보았다.

요약하자면, 프로그램이 실행됨과 동시에 디렉토리 내부의 'Test.tpy'를 찾아와 g4 rule 파일에 정의된 최소 토큰 단위로 문자열을 파싱하는 구조였다. 그래서 우리가 해야할 일은 파싱된 해당 문자열에 도착했을 때 어떤 일을 해줄 것인지를 정의해주는 것이다.

 

그렇다면 어떻게, 어디서 우리가 해야할 일을 정의할 수 있을까?

ANTLR의 기능을 이용하면, 가지고 있는 g4 파일을 기반으로 파싱하기 위한 BaseListener, Visitor, Lexer 등 기본 추상 클래스를 자동 생성이 가능하다.

가지고 있는 g4 파일을 우클릭하면 Generate ANTLR Recognizer라는 항목이 있는데, 이것을 클릭하면 디렉터리에 gen 폴더가 생기며 이 안에 해당 g4 rule을 파싱하기 위한 클래스들이 생긴다.

해당 클래스들 중, 본 수업에서는 Listner만을 이용하였다. 따라서 src 폴더 내에 BaseListener, Lexer, Listener(인터페이스), Parser 클래스만 가져온다.

MyComp 파일은 구현한 컴파일러 파일이다.

그 후, 가져온 클래스들에서 Visitor를 사용하는 모든 것들을 지워준다. 어짜피 src 디렉토리로 이동할 때 Visitor 관련 클래스들은 가져오지 않았으니 빨간 줄로 오류가 나있을 것이다.

 

이제 가져온 Listener의 작동에 대해 알아보자.

가져온 BaseListener의 모습

함수의 이름은 enter/exit + (파싱된 문자열의 이름) 으로 구성된다.

ANTLR가 그리는 파스트리를 보면 해당 함수들의 동작의 이해가 쉽게 된다.

해당 파스트리의 일부분을 보자. ANTLR는 파스트리를 DFS로 탐색한다.

따라서 파싱되는 순서는 defs - def_stmt - def - NAME - OPT_PAREN... 일 것이다. 

ANTLR는 이렇게 문자열들을 토큰 단위로 나누어 파스트리를 그리고, DFS로 탐색하며 한 node에 방문 시 enter function을, 그 node를 떠날 시 exit function을 실행한다.

그러므로 우리는 enter나 exit중 하나를 골라 어떤 스타일로 작성을 하든 해당 토큰에 방문하였을 때 할 일을 작성하면 되는 것이다. 예를 들어, enterDefs에 defs 토큰 방문시 수행할 일을 정의한다고 가정해보자.

그러면 자연스럽게 top down 방식으로 트리를 바라보게 된다. 우선 사진에 따르면 defs node가 가장 먼저 방문될 것이다.

defs node가 방문되면 어떤 일을 해야할까? 우리 마음대로 해서는 당연히 안될 것이다.

tinyPython g4 파일의 일부

이를 정의해주기 위해 작성된 것이 g4 rule이다. 

이 rule을 보면 defs가 파싱될 경우 NEWLINE or def_stmt가 0~n번 반복됨을 알 수 있다. 

그러면 defs는 어떤 토큰에서 call될 수 있을까? 본 tinyPython g4 rule의 경우 file_input 이라는 토큰이 인식되었을 때만 defs 가 등장한다.

이 file_input은 program이라는 토큰에서 실행되며, program은 프로그램이 실행시 파싱되는 첫 토큰이다.

즉 프로그램이 실행이 되면 file_input에서 가장 먼저 등장하는 것이 defs 토큰이다. 이후 어떤 경우에서도 defs 토큰은 재등장하지 않는다.

 

결론, 프로그램이 실행되면 defs를 처음에 먼저 실행한 뒤, main문으로 이동하는 것으로 이해할 수 있다.

defs는 개행 or def_stmt를 계속 실행한다. def_stmt의 경우 함수를 정의하는 규칙을 정의한다.

(파스트리를 보면 어떤 형태를 하고 있는지 알 수 있다.)

-> 이를 통해 '프로그램이 실행되면 가장 먼저 defs 토큰을 인식해 프로그램에 사용되는 모든 함수들을 정의하고 시작한다.'

라는 사실을 알 수 있다.

이 규칙에 맞춰 작성된 Test.tpy 파일을 보면 역시 sum(a,b)를 먼저 정의하고 시작하는 것을 볼 수 있다.

 

그러면 enterDefs()의 경우는 어떻게 정의될까?

enterDefs

ctx는 현재 노드부터 하위 트리들을 담고있는 파스트리 자료형이다.

인자로 넘어온 ctx. 즉, 파스 트리의 Child 갯수를 센다. 0보다 크다는 뜻은 적어도 한 개 이상의 처리해야할 요소를 가지고 있는 것을 의미한다.

이후 해당 defs subtree로부터 스캔해나가며 def_stmt를 마주칠 경우 enter 해준다. 그 외 세부적인 구현은 주석을 참조.

 

여기까지 어떻게 ANTLR가 파스트리를 그리며 접근하는지, 그리고 어떻게 우리가 해당 토큰이 파싱되었을 때 해야할 일을 정의해줘야 하는지를 알아보았고, 예시로 Defs 토큰이 파싱되었을 때 정의하는 과정을 살펴보았다.

 

다음 포스팅은 이어서 컴파일러를 구현하는 과정 중 따로 인스턴스들을 저장을 해둘 자료구조도 필요하고 여러가지 세부적인 디테일이 있는데, 이를 설명하며 계속 구현해나가겠다.