루비의 파싱 알고리즘은 크게 세 가지 단계로 진행됩니다.
1. 식별 (Identify)
첫 번째 단계는 현재 토큰이 무엇을 의미하는지 식별하는 것입니다. 루비는 토큰의 유형과 뒤따르는 토큰들의 유형을 일련의 패턴과 비교하여 코드가 무엇을 의미하는지 파악합니다. 예를 들어, puts 식별자가 나타나면 루비는 이를 함수 호출 패턴과 매칭시킵니다. 이 매칭 결과는 추상 구문 트리(AST: Abstract Syntax Tree)라는 데이터 구조에 기록됩니다. AST는 프로그램의 중첩되고 재귀적인 구조를 표현하는 데 적합합니다.
2. 재귀 (Recurse)
두 번째 단계는 루비가 스스로를 호출하는 재귀(Recurse)입니다. 구문 패턴 내의 각 값은 루비가 파싱해야 할 하위 표현식(subexpression)일 수 있습니다. 예를 들어, puts "Hello World"에서 "Hello World"는 puts 함수의 인자로서 별도의 파싱이 필요한 하위 표현식입니다. 루비는 이 하위 표현식을 파싱하기 위해 재귀적으로 자신을 호출합니다. 이 과정에서 바인딩 파워(binding power)와 같은 수치 값이 전달됩니다.
3. 비교 (Compare)
세 번째 단계는 현재 토큰과 다음 토큰의 우선순위를 비교하는 것입니다. 이 비교를 통해 루비는 토큰들을 특정 순서로 처리하는 경로를 결정합니다.
puts "Hello World" 예시를 통한 파싱 과정
-
토큰화:
puts "Hello World"는PM_TOKEN_IDENTIFIER(puts),PM_TOKEN_STRING_BEGIN(“),PM_TOKEN_STRING_VALUE(Hello World),PM_TOKEN_STRING_END(“),PM_TOKEN_EOF토큰으로 변환됩니다. -
puts식별: 루비는PM_TOKEN_IDENTIFIER(puts)를 함수 호출로 식별하고, AST에 첫 번째 노드인 호출 노드를 생성합니다. -
인자 파싱 (재귀):
puts함수의 인자인"Hello World"를 파싱하기 위해 루비는 재귀적으로 자신을 호출합니다.PM_TOKEN_STRING_BEGIN토큰을 만나면 문자열의 시작을 인지합니다.- Prism 파서는
PM_TOKEN_STRING_VALUE와PM_TOKEN_STRING_END를 처리하여 문자열 내용을 직접 파싱합니다. - 더 복잡한 문자열(예:
#{}를 사용한 보간)은 추가적인 재귀 호출을 필요로 할 수 있습니다. - 문자열 파싱이 완료되면
PM_STRING_NODE라는 새로운 AST 노드가 생성됩니다.
루비의 파서는 재귀 하강 파서(recursive descent parser)이며, 이는 언어의 문법 규칙과 유사한 방식으로 중첩된 구조를 상향식으로 처리합니다. Ruby 3.3부터는 기존 파서 생성기 대신 수작업으로 작성된 C 코드를 사용하는 Prism 파서가 이 패턴 감지 역할을 수행합니다.