JParser (12) 결론 2 future works

jparser와 관련해서 아직 하고 싶은 일이 몇가지 더 남아서 정리해 보았다. 다만 이 일들을 언제쯤 할 수 있을지는 잘 모르겠다.

논문 작성

원래 나의 계획은 CDG와 naive 파싱, 마일스톤 및 마일스톤 그룹 파싱 알고리즘, AST 프로세서, JParser에 대한 이야기를 총망라한 논문을 써서 출판하는 것이었는데 만만치가 않았다. 딱 CDG와 naive 파싱에 대한 이야기만 담은 논문을 써 본적이 있는데 CDG와 naive 파싱 알고리즘에 대한 수학적 논의를 적으려다 보니 쉽지는 않았다. 그리고 그 논문을 한 학회에 보내봤는데 거절당했다. 거절 사유의 요지는 관련 연구 조사가 부족하다는 것이었다. 이해할만 한 이유였다. 수십년 전에 선배 연구자들이 파싱과 관련해서 이미 가볼 수 있는 길은 다 가 봤을 것 같은데, 논문을 내려면 그들이 가보지 않은 길을 발견했다는 것을 증명해야 할 일이었는데 그 부분이 부족했다.

그래서 한동안 접어두고 혼자서만 jparser를 이런저런 프로젝트에 쓰고 있다가, 아쉬운 마음에 대신 쓴 것이 이 블로그 포스팅 시리즈였다. 논문을 쓸 때처럼 형식을 잘 맞추고, 정제된 표현만 쓰고, 수학적인 이야기가 반드시 들어가야 하는 것도 아니고, 언제든 내 맘대로 다시 수정할 수도 있으니 부담도 적고 좋겠다 싶었다. 그리고 적어놓고 나니 jparser 프로젝트는 일단 이렇게 일단락해도 되겠다는 생각이다.

어쨌거나 논문은 기고했다 거절당한 것이 가장 최근 상태이고 언젠가는 그럴싸하게 엮어서 논문으로 출판할 수 있으면 좋긴 하겠다. 그런데 그 역시 많은 공력이 들어가는 일이라 언제가 될 지는 알 수 없다.

멀티 마일스톤 그룹 파싱

앞서 마일스톤 파싱과 마일스톤 그룹 파싱에 대한 논의를 하면서 멀티 마일스톤 그룹 파싱에 대해서 언급했었다. 사실 naive 파싱 알고리즘을 개선한 알고리즘을 생각하면서 처음 생각했던 것이 멀티 마일스톤 그룹 파싱처럼 동작하는 알고리즘이었는데, 생각을 할수록 너무 어려워서 머리가 뽀개질 것 같았다. 그래서 문제를 쪼개고 단순화하다보니 세 단계로 나뉘어지게 되었다. 그리고 현재는 그 중 첫 두 단계인 마일스톤 파서와 마일스톤 그룹 파서만 만들어진 상태이다. 사실 마일스톤 파싱 알고리즘만으로도 꽤나 쓸만해서 머리를 뽀개가면서까지 멀티 마일스톤 그룹 파싱 알고리즘을 만들 동인이 없는게 사실이다.

하지만 언젠가는 멀티 마일스톤 그룹 파싱 알고리즘도 구현해보고 싶다. 그리고 이렇게 되면 시간복잡도가 달라지는지도 분석해보고 싶다. 언제가 될진 모르겠다. 시간이 남는 똑똑한 분이 와서 대신 해주셔도 좋을 것 같다.

더 빠른 AST 재구성

지금 jparser로 만든 파서를 돌리면 속도가 만족스럽지 않다. 파싱 알고리즘 자체의 한계도 있지만, 가장 느린 부분은 파스 트리를 재구성하는 부분이다.

하지만 사실 파스 트리 전체를 재구성할 필요는 없다. 어차피 사용자가 필요한건 AST이기 때문에, 파싱 컨텍스트 히스토리로부터 파스 트리를 거치지 않고 바로 AST로 갈 수 있으면 전체적인 파싱 속도를 개선할 수 있을 것이다. 그러려면 파싱 컨텍스트 히스토리를 받아서 AST를 반환하는 코드를 생성해주어야 할 듯 하다.

이 부분은 파싱 속도에 있어서 상당한 병목이기 때문에 왠지 곧 작업을 하게 될 수도 있을 것 같지만 역시 시점은 미지수다.

파이썬 파싱

파이썬 프로그램을 파싱하는건 쉽지 않다. 들여쓰기로 블럭을 정의하기 때문이다. 파이썬 문법 정의에서는 “INDENT”와 “DEDENT”라고 하는 가상의 토큰을 두고, 들여쓰기가 되는 지점(일반적인 다른 언어에서 {가 있을만 한 지점)에 INDENT를, 내어쓰기가 되는 지점(다른 언어에서 }가 있을만 한 지점)에 DEDENT를 넣어두었다.

단순하게 생각하면 개행문자 단위로 쪼개서 INDENT와 DEDENT 토큰을 넣어주는 전처리를 하면 되지 않을까? 라고 생각할 수도 있지만 그렇게 할 수도 없다. 다음의 코드를 보면 바로 이해가 될 것이다.

hello = [
        "python",
"parsing",
                    "is",
            "difficult"
        ]

world = ("python"
    "parsing"
            "is"
"really"
            "difficult")

INDENT나 DEDENT를 적절히 whitespace처럼 처리하는 방법도 고민해 봤지만, 그것도 간단치 않을 것 같다. 필요한 자리에 INDENT나 DEDENT가 나오지 않아버릴 수 있기 때문이다.

파이썬 문법 정의에서 Lexical analysis 부분을 보면 문법 정의에 NEWLINE이라는 토큰이 등장하는 지점에서 INDENT나 DEDENT 토큰이 나타날 수 있다고 한다. 그렇다면 혹시 파싱을 진행하면서 파싱 컨텍스트에 NEWLINE 토큰이 나오면 다음 문장의 들여쓰기 레벨을 확인해서 INDENT나 DEDENT 토큰을 만들어서 파싱 컨텍스트에 넣어주는 방식으로 파이썬 코드를 파싱할 수 있지 않을까? 현재로썬 그럴싸한 아이디어 같은데 좀 더 검토하고 실험해봐야 알 것 같다. 물론 언제쯤 하게 될 지는 알 수 없다.

스칼라 외의 다른 언어 지원

파싱 알고리즘들이 모두 스칼라로 구현되어 있고, AST 프로세서 코드가 스칼라로 생성되도록 되어있다보니 JVM 기반 언어에서만 jparser를 사용할 수 있다. 이 기능들을 다른 언어로 구현하면 유용하게 쓸 데가 있을 것 같다. 다른 언어를 지원한다면 Rust같은 언어가 좋지 않을까?

전체 목차:

이제 거의 다 왔다. 다음 포스팅에서는 지금까지 설명한 CDG, naive 파싱, 마일스톤 파싱, AST 코드 생성 기능 등을 구현하면서 느낀 점, 배운 점 등에 대한 소회를 풀어보려고 한다.

이 페이지에서 오류나 문제점을 발견하시면 이메일로 알려주시면 감사하겠습니다.
뒤로