tree-sitter는 github에서 사용하는 파서 만들기 도구로 110여가지 이상의 프로그래밍 언어들의 파서를 현재 지원 가능하다. tree-sitter로 파서를 만들면 프로그래밍 환경(IDE)에서 구문 종류를 구분하는 색깔 입히기(syntax highlighting)와 같은 기능을 자동으로 제공한다. tree-sitter는 GLR 파서 방식으로 에러가 포함된 구문도 쉽게 넘어가도록 고려되어 있다. 참고로 YAPB은 LR 파서 방식으로 에러가 포함된 구문의 경우 파서를 진행하지 않는다.
tree-sitter를 사용하여 새로운 프로그래밍 언어의 파서를 만들어본다. tree-sitter는 웹 기반 구문 트리 뷰어를 제공한다. (난이도 하-중)
tree-sitter가 C와 WebAssembly 파서를 생성하는데 ZIG로 작성된 파서를 생성하도록 수정. (난이도 상)
YAPB을 사용한 파서 템플릿 생성(난이도 중): YAPB을 이용하여 파서를 만들려면 기본적으로 Token.hs, Lexer.hs, Parser.hs, Expr.hs, Run.hs를 만들어야 한다. 현재는 YAPB을 이용한 다른 파서 프로젝트에서 이 5개의 파일을 복사하고 적절히 편집해서 준비한다. YAPB에 이러한 초기 파일을 생성하는 기능을 추가하는 프로젝트를 제안한다.
YAPB의 어휘 분석(lexical analysis) 성능 향상(난이도 상): YAPB에서 어휘 분석 구현 방법이 아주 비효율적인 방식 으로 구현되어 있다. 각 어휘에 대한 정규식을 모두 합하여 하나의 오토마톤을 구성하는 방식이 아니라 각 정규식에 대해 각 오토마톤을 매번 생성하고 테스트하는 방식이다. 아마도 YAPB에서 사용하는 tdfa-regex를 수정해서 YAPB의 어휘 분석 명세에서 지정한 여러 정규식을 하나로 모아서 오토마톤을 구성하는 방식으로 수정해야한다.
YAPB 파서를 작성할 때 모든 액션의 타입이 RHS (생산규칙의 오른편에 해당하는 심볼들의 파싱 결과 서브 AST 리스트) -> AST 타입으로 정의해야하는 문제점 해결. 불필요한 AST 타입을 정의해야하고, 더욱 불편한 점은 fromASTExpression이나 toASTExpression과 같이 서브 AST를 만들때마다 매번 AST 타입의 생성자로 감싸거나 풀어주어야 하며, 심지어는 실행시간에 이 과정에서 런타임 에러가 발생하곤 한다!
이 문제를 해결하기 위하여 메타프로그래밍을 적용하여 파서 코드를 생성하는 접근 방법으로 YAPB의 구조를 바꾸어야 한다. 다만 이 해결책의 우려되는 점은 파서를 사용하기 위해 하스켈 메타프로그래밍을 알아야하는 부가적으로 복잡한 상황이 발생할 수 있다.
YAPB 파서를 작성할 때 모든 액션의 타입이 RHS (생산규칙의 오른편에 해당하는 심볼들의 파싱 결과 서브 AST 리스트) -> AST 타입으로 정의하는데, 이 리스트의 RHS의 i번째 위치 심볼에 대한 서브 AST를 가져올 때 get rhs i를 사용한다. i의 범위는 1부터 RHS 심볼 길이 사이이다. 지정한 i의 값이 이 범위에 있는지를 실행 시점에 확인하는 문제점이 있다. 컴파일 시점에 알수 없을지. 더우기 실행 시점에 범위를 벗어나는 에러가 발생하면 파서의 어느 액션에서 그 에러가 발생했는지 알기 어렵다. 최소한 에러 메시지에서 어떤 파싱 액션을 수행하다 발생한 것인지 알려주면 파서 개발자가 쉽게 디버깅할 수 있을 것이다.
현재 이 문제를 해결하는 요령은 stack ghci로 파서를 실행하여 파싱 결과 AST를 프린트하는 프로그램을 실행하는 것이다. ghci 명령어 :set args 프로그램 텍스트 파일을 지정한 다음 파서를 실행하면 문제없이 파싱된 부분은 AST가 프린트 되지만 범위 에러가 발생하는 부분에서 AST대신 에러 메시지가 프린트된다. 그 위치를 통해 어디에서 범위 에러가 발생했는지 파악할 수 있다.
Updated: 3 September, 2023