Pratt 파싱을 기억하려고 정리해 보기

Pratt 파싱은 shunting yard의 명시적 연산자 스택을 호출 스택으로 바꿔 이해할 수 있음. 연산자가 요구하는 부분 표현식을 재귀 호출로 파싱하고, 결합력에 따라 복귀함 결합력(binding power) 으로 연산자 우선순위를 처리하며, 일반적인 재귀 하강 방식처럼 표현식마다 모든 우선순위 단계를 거치지 않고 부분 표현식에 진입할 때만 호출을 중첩함 shunting yard는 괄호에 별도 스택 처리가 필요하고 단항 연산자, 오른쪽 결합 표현식, 가변 인자 함수로 확장할수록 복잡해지지만, Pratt 파싱은 연산자별 처리 함수로 확장하기 쉬움 expr()를 접두 처리와 중위/후위 처리로 나누고, 각 연산자를 만났을 때 개별 코드를 실행함. 괄호도 내부 표현식을 재귀적으로 파싱하고 닫는 괄호를 확인하는 방식으로 추가할 수 있음 결합력과 처리 함수를 규칙 구조체로 묶으면 파서의 핵심 코드를 단순하게 유지할 수 있음. 공개된 구조화 예제는 단항 +, -와 후위 !까지 확장함 C 표현식 파서에서 출발한 Pratt 파싱 학습 C 표현식 파서를 만들면서, 이전 계산기에 사용했던 shunting yard 알고리듬 대신 Pratt 파싱을 살펴봄. 이 파서는 향후 컴파일러로 발전할 수도 있음 Pratt 파싱은 일반적인 컴퓨터 과학 학습 경로에서 접하기 어려움 파싱을 폭넓게 다루는 Dragon Book에도 등장하지 않음 학습 경험상 프로그래밍 언어 강의는 주로 LR이나 재귀 하강을 가르치는 것으로 보이며, Pratt 파싱은 대체로 컴파일러 개발과 프로그래밍 언어 이론 분야에서 접하게 됨 Crafting Interpreters에 관련 장이 있고, Wikipedia에도 다른 자료 링크가 있음 Crafting Interpreters로 기본을 익히고, 형식적인 논문 읽기를 연습하기 위해 Pratt의 원 논문 도 활용함. 재귀와 연산자 우선순위의 관계는 shunting yard에 대응시켜 보면서 이해하게 됨 Shunting yard의 작동 방식과 확장 한계 출력 스트림과 연산자 스택을 사용하며, 결합력이 높을수록 인자와 더 강하게 결합함. 산술 연산에서 *의 결합력은 +보다 높음 입력 토큰마다 다음 규칙으로 처리함 식별자나 숫자처럼 독립적인 토큰은 출력으로 바로 보냄 연산자의 결합력이 스택 맨 위 연산자보다 높으면 스택에 넣음 결합력이 같거나 낮으면, 스택에서 결합력이 더 높거나 같은 연산자를 모두 출력으로 꺼낸 뒤 새 연산자를 ...