Pratt Parsing의 직관 파악하기
(louis.co.nz)
이 기사는 복잡한 연산자 우선순위와 결합 규칙을 포함하는 표현식을 추상 구문 트리(AST)로 변환하는 'Pratt parsing'의 직관적인 원리를 설명합니다. 연산자 우선순위의 증감에 따라 트리가 왼쪽 또는 오른쪽으로 기울어지는 패턴을 분석하고, 이 전환 과정에서 트리를 효과적으로 재구성하는 방법을 제시하여 파싱 과정을 단순화합니다.
이 글의 핵심 포인트
- 1Pratt parsing은 표현식을 추상 구문 트리(AST)로 변환하는 과정을 연산자 우선순위 및 결합성에 기반하여 직관적으로 단순화합니다.
- 2연산자 우선순위 변화에 따라 AST의 구조가 왼쪽 기울어짐(감소/동일 우선순위) 또는 오른쪽 기울어짐(증가 우선순위) 패턴을 보입니다.
- 3핵심 아이디어는 우선순위가 전환될 때, 오른쪽 기울어진 트리의 '척추'를 거슬러 올라가 필요한 연산자들을 새로운 왼쪽 자식으로 재구성하는 것입니다.