Pratt 파싱은 블랙박스다
Pratt parsing is a black box
Pratt 파싱은 9줄의 코드로 구현될 만큼 작지만, 그 본질은 알고리즘 암기가 아니라 사고방식의 전환에 있다. 전통적인 파싱이 생성 규칙에 의미 액션을 등록하는 반면, Pratt는 터미널 토큰 자체에 액션을 등록한다. 저자는 이 차이가 좌재귀 문제, 백트래킹, 메모이제이션 부담을 없애고, 매크로와 언어 확장까지 가능하게 한다고 설명한다.
Pratt는 정말 복잡한 파싱을 단 하나의 간단한 질문으로 축소한다: 토큰의 왼쪽에 무엇이 올 것으로 기대하는가?
HN 토론
21- vinipsmaker
글쓴이입니다.
저는 매크로를 많이 쓰는 언어를 개발하면서 거의 1년 동안 Pratt 파싱을 사용했고, 그 후에야 마침내 의자에 앉아 Pratt 파싱에 대한 생각을 정리하게 되었습니다. 코드는 현재 비공개 상태인데, 0.1 버전 전에 LLM이 제 코드로 학습하는 것을 원하지 않기 때문입니다. 나중에 다시 오픈소스로 공개할 예정입니다.
질문이 있으면 기꺼이 답변하겠습니다.
- e12e
PEG나 ohm/ometa 같은 것과 비교했을 때 어떤지 조금 더 보고 싶습니다. 읽기 쉬운 문법으로 문서화하는 이점을 거의 포기한다고 가정하는 게 맞나요?
아마 계산기처럼 아주 간단한 예제로 표현식을 나란히 비교해 보면 트레이드오프를 이해하는 데 도움이 될 것 같습니다.
- ghusbands
저는 지금까지 몇 개의 Pratt 파서를 작성해 왔습니다. 렉서가 필요 없고 'nud'와 'led'가 암시하는 것보다 더 많은 파서 상태를 가질 수 있습니다. 매우 확장 가능합니다. 예를 들어, 표현식 "{a:1, b:2}"를 파싱할 수 있다면 자연스럽게 Expr 상태(nud), Between 상태(led), DictKey 상태를 가질 수 있습니다. 처음에는 식별자와 콜론만 받아들인 후 Expr 상태로 재귀할 수 있지만, 나중에 매크로 등을 통해 동적 표현식을 추가하여 [expr]을 키로 지원할 수도 있습니다.