From AST to Lossless Syntax Tree
Source
Evernote/Inbox/From AST to Lossless Syntax Tree.md
Summary
Oil 프로젝트는 OSH(Bash 변종)를 Oil 언어로 번역할 때, 실행만 고려한 기존 AST(Abstract Syntax Tree)의 한계를 지적한다. 인간이 편집할 코드를 생성하려면 주석, 포맷팅, 불필요한 괄호 등 실행에는 무관하지만 가독성과 스타일 유지에 중요한 문법적 세부사항을 보존해야 한다. 이를 위해 저자는 ‘Lossless Syntax Tree’ 개념을 도입한다. 이는 원본 소스 코드로 완전히 복원 가능한 표현 방식으로, 순서 있는 ASDL 트리와 원본 텍스트의 라인 스팬(line spans) 배열을 결합하여 구현한다. 이는 실행 정보만 담은 AST나 모든 문법 노드를 포함하는 Parse Tree와 구별되며, Clang이나 Python의 2to3 도구에서 유사한 접근을 사용함을 언급한다.
Key Points
- Oil 프로젝트는 OSH를 Oil로 번역하는 과정에서 실행용 AST가 아닌 ‘Lossless Syntax Tree’를 사용한다.
- 번역된 코드는 인간이 편집하므로, 주석, 들여쓰기, 불필요한 괄호 등 실행에는 영향이 없는 문법적 세부사항을 보존해야 한다.
- Lossless Syntax Tree는 원본 소스 코스로 손실 없이 복원 가능한 표현 방식이다.
- 구현은 순서 있는 ASDL 트리와 원본 텍스트의 라인 스팬 배열을 조합하여 이루어진다.
- AST(실행 중심, 정보 손실)와 Parse Tree(문법 중심, 노드 과다)의 중간 형태로 정의된다.
- Clang(물리적 괄호 보존)과 Python 2to3가 유사한 문제를 해결하기 위해 비슷한 접근을 사용한다.