새로운 종류의 파서 메서드

Source: Dev.to

소개

Pratt 파싱은 강력한 기법이지만, 바인딩 파워와 NUD와 같은 개념은 이해하기 어려울 수 있습니다.
다음은 비슷한 기능을 제공하면서도 더 간단해지도록 설계된 대체 파싱 방법을 설명합니다.

일반적인 접근 방식

1. 표현식을 토큰화하여 항, 연산자, 그룹화 기호의 평면 리스트로 만든다.
2. 연산자 우선순위 식별 (예: *와 /는 +와 -보다 높은 우선순위를 가진다).
3. 우선순위에 따라 인접한 항들을 반복적으로 결합하여 트리 구조를 만든다.
4. 특수 토큰 유형 (단항 vs. 이항 연산자, 숫자 리터럴, 멤버 접근, 함수 호출)을 메인 트리 구성 전에 별도의 병합 단계에서 처리한다.

예시

다음 식을 고려해 보세요:

2 + foo(4, 5) * 4 / 23

토큰 리스트

2, foo(4, 5), *, 4, /, 23, +

트리 구성

1. 첫 번째 패스 (곱셈)

   • foo(4, 5)와 4를 *로 결합 → [foo(4, 5), 4]{*}

2. 두 번째 패스 (나눗셈)

   • 1단계 결과와 23을 /로 결합 → [[foo(4, 5), 4]{*}, 23]{/}

3. 마지막 패스 (덧셈)

   • 2와 2단계 결과를 +로 결합 → [2, [[foo(4, 5), 4]{*}, 23]{/}]{+}

결과 AST (의사코드)

add(
    2,
    divide(
        multiply(
            foo(4, 5),
            4
        ),
        23
    )
)

단항/이항 연산자 및 특수 토큰 처리

이 방법은 여러 핵심 토큰 유형을 구분합니다:

병합 단계

AST를 만들기 전에 인접 토큰을 결합하여 더 높은 수준의 구조를 형성한다:

• 단항 마이너스와 피연산자: -u x → -x
• 멤버 접근: a .m b → a.b
• 멤버 접근이 포함된 함수 호출: foo .m bar (c 23, 24 ) → foo.bar(23, 24)

이 미니 파서는 함수와 몇 가지 혼합형 연산자만을 다루며, 나머지 표현식은 메인 트리 구축 알고리즘에 맡긴다.

최종 정리

병합 단계가 끝난 후 파서는 항, 연산자, 그룹화 기호가 포함된 리스트를 대상으로 작업한다.
괄호에 대한 재귀 파싱을 통해 완전한 추상 구문 트리(AST)를 생성하고, 이를 평가, 코드 생성 또는 추가 분석에 활용할 수 있다.