Rust로 언어를 만드는 연재의 한 편으로, 파싱을 처음부터 구현한다. 오류에 강인한(Resilient) 동시에 원문 텍스트를 그대로 담아내는(Full Fidelity) CST 기반 파서를 손으로 작성하고, logos로 렉싱하고 rowan으로 CST를 구축한다. 앵커 집합을 이용한 오류 복구, 애플리케이션/원자 파싱, let 문법 설탕과 프로그램 엔트리까지 단계적으로 다룬다.
Making a Language
이 글은 making a language series의 일부입니다. Rust로 프로그래밍 언어를 구현하는 법을 가르치는 연재죠.
이번 글은 파싱을 다룹니다. 파싱은 컴파일러의 첫 번째 패스이기 때문에 이전 글들에 의존하지 않습니다.
고백하자면, 파싱 튜토리얼에 대해 약간의 경멸이 있습니다. 그것이 공정하거나 합리적이라고 가장하며 여러분을 모욕하지는 않겠습니다. 아마 놀랍지 않을 겁니다. Making a Language 시리즈가 파싱에 앞서 컴파일러의 everypartof thecompilerit can을 이미 다뤘다는 점을 떠올려보면요. 파싱 튜토리얼은 어쩐지 허망하게만 느껴집니다. 파싱에 관한 튜토리얼이 수천 개나 나와 있는데도 PL 프로젝트는 여전히 문법 자전거 보관대(bikeshedding)에서 죽곤 하니까요. 1001번째 튜토리얼이 그걸 바꿀 확률이 얼마나 될까요?
결국 파싱은 컴파일러에서 두 가지 역할을 수행합니다:
이론적으로는 간단합니다. 파싱하기 쉬운 문법을 고릅니다. 그다음 입력 문자열을 훑으면서 각 문자가 그 틀에 들어맞는지 확인하고, 그걸로 트리를 만들고, 필요하면 에러도 보고하죠. 뭐가 그리 어렵겠어요?
아마 그게 제 빈정의 일부일 겁니다. 파싱에 관해 할 수 있는 얘기는 이미 다 나온 것 같아요. 그런데도 파싱은 끝없이 갈래지는 선택지의 미로처럼 느껴져 진척을 방해하죠. 먼저 1차 선택지가 있습니다. 문법 자체에 대한 선택이죠:
벌써 어지러운데, 2차 선택지도 있습니다. 무엇을 파싱할지뿐 아니라, 어떻게 파싱할지도요:
각각 장단이 있고 어떤 문법은 더 쉽게, 어떤 문법은 더 어렵게 만듭니다. 결정할 게 많지만, 정답은 알 수 없습니다. 그래도 파서는 필요합니다. 사용자가 직접 AST 조각을 손으로 조립해 컴파일러에 먹여야 한다면, 우리가 그걸 언어라고 할 수도 없죠. 우리의 언어는 사용자가 소스 파일에 작성할 수 있는 인터페이스가 필요합니다. 즉 문법이 필요합니다. 못마땅하더라도, 파서는 있어야 합니다. 그래서 여기 있습니다. 제 파싱 격언들을 또 한 줌 보태러요.
파싱은 해야 합니다. 하지만 그 사실이 파싱 과정에서 남은 수많은 선택지를 헤쳐나가는 데 도움을 주지는 않죠. 우리의 목표는 소박합니다. 들어가서, 파서를 만들고, 나오자. 타르 웅덩이에 빠지지 말자. 최고의 문법을 설계하거나 최적의 파싱 전략을 찾으려는 게 아닙니다.
오늘의 목표는 “작동 가능하고 쓸 만한 것”입니다. 그 관점에서 제약을 몇 가지 세워 우리의 선호 파싱 플랫폼을 고르려 합니다. 첫째로, 파서는 수작업으로 작성합니다. 문법이나 설정 파일을 받아 파서를 뱉어주는 제너레이터와 라이브러리가 천지빼까리입니다. 하지만 제 경험상 이런 도구를 익히는 데 시간을 다 쓰고, 정작 파서를 쓰는 데는 시간을 충분히 쓰지 못합니다. 도움이 될 때도 있지만, 그 교환 비용이 늘 가치 있었던 건 아니었습니다. 우리는 그게 필요 없고, 처음부터 거르면 시간을 아낄 수 있습니다.
우리 언어의 목표가 알려주는 제약이 둘 더 있습니다. 요즘 언어(와 컴파일러)는 과거 배치 컴파일 시대보다 훨씬 상호작용적이길 기대받습니다. 요즘 나오는 언어라면 Language Server Protocol (LSP) 같은 방식으로 IDE 수준의 기능을 지원하는 게 기본이죠. 현대 언어인 우리도 이런 멋진 기능을 지원해야 합니다.
파서에게 그 요구사항은 두 가지로 구체화됩니다:
회복력이란 파서가 첫 번째 에러에서 멈추지 않는다는 뜻입니다. 언어가 상호작용적으로 쓰일 때는 사용자가 편집 중인 코드를 파서가 자주 보게 됩니다. 만약 파서가 첫 에러에서 멈춰버리면, 사용자가 함수 하나만 수정해도 파일 전체를 파싱하지 못하게 되죠. 우리는 첫 에러에서 멈추지 않고, 그 에러를 국소화해 최대한 많은 올바른 문법을 계속 파싱하길 바랍니다.
둘째 제약인 완전 충실도란, 파서가 구성한 트리에 소스 텍스트의 모든 문자를 표현해 둔다는 뜻입니다. 흔히 이것을 추상 구문 트리(AST)에 대응되는 구체 구문 트리(CST)라고 부릅니다. CST는 에러 복구에 도움이 되어 잘못된 문법도 트리로 표현하게 해줍니다. 또한 LSP 기능을 지원하는 데에도 유리합니다. LSP 작업의 상당수는 “커서가 가리키는 곳의 의미 정보를 달라”는 형태이고, CST는 소스 파일의 위치와 AST의 위치를 연결해 이를 쉽게 해줍니다.
이 제약들을 염두에 두고 우리의 파싱 전략은 재귀 하강(Recursive Descent)을 택합니다. 재귀 하강 파서는 서로를 호출하는 함수 집합입니다. 믿기 어렵겠지만, 재귀적으로 입력을 파싱합니다. 그냥 함수들이기 때문에 수작업으로 작성하기 쉽습니다. 각 함수는 남은 입력을 보고 다음에 뭘 할지 결정합니다. 정수를 파싱하고 싶다면, 이렇게 int 함수를 쓰면 됩니다:
fn int(
mut input: &str
) -> (Result<isize, std::num::ParseIntError>, &str) {
let mut integer = String::new();
while let Some(digit) = input.get(0).filter(|c| c.is_digit()) {
integer.push(digit)
input = input[1..];
}
(integer.parse::<isize>(), input)
}
int는 다음 문자가 숫자인 동안 입력을 소비합니다. 숫자가 더 이상 없으면, 모아둔 String을 isize로 파싱해 봅니다. 파싱 결과와 상관없이 남은 입력을 반환합니다. 이렇게 해야 다음 파서가 우리가 멈춘 지점부터 이어서 진행할 수 있습니다.
재귀 하강의 맛보기였습니다. 하지만 위 예시는 회복력도, 완전 충실도도 갖추지 못했습니다. int는 만나는 첫 에러에서 멈추고, 공백은 전혀 다루지 않죠. 다행히 재귀 하강은 그냥 함수이므로, 함수를 더 잘 쓰면 이 문제를 해결할 수 있습니다.
실제 파서는 완전 충실도의 트리를 만들어야 합니다. 그러려면 완전 충실도의 트리를 저장할 방법이 필요합니다. AST와 달리, CST는 enum으로 저장하지 않을 겁니다. CST 저장은 라이브러리에 맡기겠습니다. 우리도 만들 수는 있지만, union-find 때처럼, 우리는 CST를 효율적으로 저장하는 ‘방법’ 자체보다는 파싱에 관심이 있습니다. 라이브러리에 기대면 빨리 파싱으로 돌아갈 수 있고, 동시에 탄탄한 솔루션을 얻을 수 있죠.
우리가 택한 라이브러리는 rowan입니다. rowan은 rust-analyzer가 사용하므로 믿고 쓸 수 있습니다. 내부적으로 rowan은 Red-Green Tree를 사용합니다. CST에 흔한 선택이며(Swift, C#, Kotlin도 이 방식을 씁니다), 자세한 내용은 rust-analyzer 책에서 볼 수 있습니다.
rowan은 우리의 목적에 충분합니다. 우리가 알아야 할 것은 rowan이 균질한 n-항 트리를 저장한다는 점뿐입니다. 트리의 각 노드는 태그와 임의 개수의 자식을 가집니다. 태그를 표현할 enum을 Syntax라는 이름으로 정의합시다:
enum Syntax {
Identifier,
Integer,
Functions,
// ... 나머지 구문 노드들
}
enum은 AST와 달리 연관 데이터를 갖지 않습니다. 각 노드는 태그와 상관없이 임의 개수의 자식이라는 동일한 데이터를 가집니다. 내부적으로 rowan은 Syntax를 u16으로 바꾸므로, 원해도 데이터를 붙일 수 없습니다.
이 유연성이 회복력을 가능케 합니다. 우리의 CST는 이항 식을 다음처럼 기꺼이 표현합니다:
하지만 이렇게 표현해도 마찬가지로 행복합니다:
사용자가 알 수 없는 연산자를 줬다면, 이항 식을 이렇게도 두 팔 벌려 받아줍니다:
동적 타이핑처럼, 이런 자유에는 대가가 따릅니다. CST는 트리에 무엇이든 넣게 해 주지만, 곧 무엇이든 넣을 수 있게 해 준다는 말이기도 하죠. CST는 잘못된 입력을 우아하게 처리하는 데 필요한 잘못된 트리를 표현하게 해 주지만, 우리가 만든 버그 또한 똑같이 표현합니다. 트레이드오프가 있습니다. CST가 대신 타입이 있는 노드를 제공하게 할 수도 있습니다. Swift가 이 방식을 택했지만, 그러려면 코드 생성과 모든 실패 상태를 표현하려는 거대 노드들이 필요합니다.
rowan 덕분에 완전 충실도로, 회복력 있게 파싱할 수 있습니다. 이제 뭘 파싱할지 정하기만 하면 됩니다. 이건 위험한 게임입니다. 문법 고르기는 Wadler’s Law의 최악의 사례 같거든요. 다행히 아직 주석은 없습니다.
이전 패스들이 우리를 위한 가드레일을 제공합니다. 어떤 문법을 고르든 AST에 매핑되어야 합니다:
enum Ast<V> {
/// 지역 변수
Var(NodeId, V),
/// 정수 리터럴
Int(NodeId, i32),
/// 함수 리터럴(람다, 클로저)
Fun(NodeId, V, Box<Ast<V>>),
/// 함수 적용
App(NodeId, Box<Ast<V>>, Box<Ast<V>>),
/// 타입 홀
Hole(NodeId, V),
}
이 노드 각각에 해당하는 문법이 필요합니다. 반대로, 이 노드 중 하나로 매핑되지 않는 문법은 강한 의심을 품고 바라보겠습니다. 타르 웅덩이로 빠질 위험이 크거든요. 먼저 변수부터, 식별자(identifier)로 표현됩니다. 우리에게 식별자란 키워드가 아닌 영숫자(alphanumeric) 문자의 연속입니다.
정수는 숫자(0-9)의 연속입니다. 아직 숫자 리터럴을 화려하게 꾸미지는 않겠습니다. 아까 보았듯, 정수는 입력에서 숫자가 나오는 동안 문자를 계속 먹어 파싱할 수 있습니다. 실전에서는 그만큼의 손품을 들일 가치가 별로 없습니다. 각 문자를 개별적으로 다루는 대신, 문자들을 묶어서 쓰기 쉽게 만들 겁니다. 이런 묶음은 입력 문자열에 대한 초기 패스인 렉싱(lexing)으로 이뤄집니다.
렉싱의 목표는 입력 문자열을 빠르게 한 번 훑어 문자를 토큰으로 묶는 것입니다. 예컨대 문자열 "let"이 키워드 let이라는 걸 알아내고, 문자열 "1234"가 숫자 리터럴이라는 걸 알아내죠. 그러면 파서는 더 높은 수준의 토큰을 소비하면서 일을 쉽게 합니다. 다음 문자가 숫자인지, 영숫자인지 확인하는 대신 다음 토큰이 정수인지 식별자인지만 확인하면 됩니다.
렉싱은 필수가 아닙니다. 파서는 문자 자체를 직접 다룰 수도 있는데, 이런 기법을 스캐너 없는 파싱(scannerless parsing)이라 부릅니다. 꼭 필요하지는 않으니, 우리는 렉싱 라이브러리를 써서 삶을 편하게 하렵니다. 타르 웅덩이만 피할 수 있다면요.
우리가 고른 렉싱 라이브러리는 logos입니다. 내부적으로 렉싱을 빠르게 하려고 꽤 험한 일을 해 주지만, 우리는 그걸 모두 무시하고 쾌적한 API만 쓰면 됩니다. Syntax에 Logos 프로시저 매크로를 붙이면 렉서가 생성됩니다:
#[derive(Logos)]
enum Syntax {
#[token("(")]
LeftParen = 0,
#[token(")")]
RightParen,
#[token("|")]
VerticalBar,
#[token("=")]
Equal,
#[token(";")]
Semicolon,
#[token("let")]
LetKw,
#[regex("[\\p{alpha}_]\\w*")]
Identifier,
#[regex("\\d+")]
Int,
#[regex("\\s+")]
Whitespaces,
#[end]
EndOfFile,
// ...
}
Logos는 variant에 token과 regex 지시어를 붙여 어떻게 렉싱할지 정의하게 해 줍니다. token은 문자열 리터럴을 받아 입력 스트림에서 그 토큰을 인식합니다. 내용이 고정된 구두점과 키워드에는 이걸로 충분합니다.
식별자는 유효한 문자열의 집합이 무한하므로 #[regex]가 필요합니다. regex는 정규식(regular expression)을 받아, 그 정규식과 매치되는 텍스트를 해당 토큰으로 봅니다. 식별자의 경우 선행 문자는 알파벳이나 "_"이고, 그 뒤로 단어 클래스 \w에 속하는 문자가 0회 이상 옵니다. 선행 문자를 [a-zA-Z_]로 기대할 수도 있겠지만, 우리는 유니코드를 지원하기 위해 좀 더 낯선 \p{alpha}를 씁니다.
정보
사용자가 변수 이름을 "let_keyword"로 짓고 싶다면 어떻게 할까요? 그게 식별자인지, 아니면 키워드 let 뒤에 식별자 _keyword인지 어떻게 구분할까요? Logos는 우리가 제공한 토큰들 중에서 가장 긴 매치를 선택합니다. 식별자는 let_keyword 전체를 매치할 수 있으므로, LetKw의 let 매치보다 더 긴 식별자 매치가 이깁니다.
정수와 공백도 정규식으로 인식합니다. 정수는 하나 이상의 숫자 \d+이고, 공백은 하나 이상의 공백 문자 \s+입니다.
마지막 토큰 EndOfFile에는 인식기가 없습니다. #[end]로 표시하는데, 텍스트가 따로 붙지 않기 때문입니다. Logos는 입력이 다 떨어졌을 때만 이 토큰을 내보냅니다. 우리는 이를 이용해 프로그램이 소스 파일 전체를 파싱했는지 확인합니다.
눈치챘겠지만, 토큰이 유니코드 전 범위를 다 덮지 않고 아주 일부만 포함합니다. 하지만 사용자들은 소스 파일에 원하는 걸 무엇이든 쓸 수 있습니다. 심지어 “+”나 “{” 같은, 우리에게 유효한 토큰이 없는 텍스트도 집어넣을 수 있죠.
이 문자들이 유효한 구문이 아니라 해도, 우리는 여전히 처리해야 합니다. 알 수 없는 문자에서 막히면, 에러 회복을 달성할 수 없죠. Syntax에 variant 하나를 더 추가해 문제를 해결합니다:
enum Syntax {
// 앞서 정의한 토큰들...
Error,
// ...
}
Error는 잘못된 토큰과 잘못된 노드를 모두 표현하는 이중 역할을 합니다:
Error 토큰으로 만듭니다.Error 노드로 감쌉니다.렉싱이 끝났으니, 이제 문법을 설계해 봅시다.
모든 Var는 식별자지만, 모든 식별자가 Var는 아닙니다. 함수는 매개변수로 쓸 식별자를 포함하지만, 그건 Var 노드가 아니죠. 식별자를 봤을 때 그게 Var인지 Fun인지 어떻게 알까요?
답은 문법의 중요한 성질에 있습니다. 우리는 항상, 다음 입력 토큰 하나만 보고 무엇을 파싱 중인지 알아야 합니다. 두 개 이상의 토큰을 미리 봐야 하는 것은 우리의 문법 요구를 만족하지 못합니다. 그렇다고 모든 토큰을 똑같이 취급해야 한다는 뜻은 아닙니다. 함수와 변수는 식별자를 다르게 쓰죠. 다만 그 둘을 구별할 만큼의 문법적 실마리를 토큰 하나만으로 얻어야 합니다.
식별자를 봤을 때 그게 변수인지 함수인지 파서에게 알려줄 문법을 추가합시다:
|(VerticalBar)를 보면, 함수 파싱이며 뒤따르는 식별자는 함수 매개변수다.| 다음에는 반드시 식별자가 따라와야 한다고 강제하고, 아니면 무효 문법으로 처리하겠습니다. 매개변수에서 함수 본문으로의 전환도 또 다른 |로 표시해, 전체 함수 문법은 다음과 같습니다:
|x| x
다른 언어의 함수 문법을 떠올리게 하는 부분이 있어도 모른 척합시다. 우리의 독창적이고 아주 특별한 언어거든요! 토큰 스트림 VerticalBar Identifier VerticalBar Identifier가 살짝 마음에 걸립니다. 마지막 Identifier가 바로 앞에 VerticalBar가 있어도 Var임을 어떻게 알까요? 이미 소비한 토큰에는 의존할 수 있기 때문입니다.
첫 VerticalBar를 보면, 우리는 언제나 VerticalBar Identifier VerticalBar를 파싱하게 됩니다. 여러 파싱 분기점 중 하나를 고를 때만 다음 토큰을 고려하면 됩니다. 함수 본문이 그런 분기점입니다. 함수가 |x| x가 아니라 |x| |y| x였다면, |x|를 파싱한 뒤에 오는 |가 새로운 함수를 시작한다는 걸 알려줍니다.
마지막 노드 App에는 아직 문법이 없습니다. 함수형 언어로서 우리는 함수를 정말 자주 적용할 것으로 기대합니다. 그래서 적용 문법은 가벼워야 하죠. 공백으로 나란히 둔 어떤 두 것도 적용으로 간주합니다: f x, x 1 등.
이로써 모든 AST 노드를 덮었습니다. 하지만 실제로 쓰기에는 아직 부족합니다. 반드시 필요한 문법을 조금 더 추가하고, 있으면 좋은 ‘귀염둥이’ 문법도 약간 넣겠습니다.
남은 문제는 어디서 하나의 식이 끝나고 다른 식이 시작하는지 어떻게 구분하느냐입니다. 문자열 |f||x| f x g를 생각해 봅시다. 이게 몸체가 f x g인 하나의 함수일까요, 아니면 함수 |f||x| f x에 인자 g를 적용한 것일까요? 둘 다 쓸 수 있어야 합니다.
괄호는 이 둘을 구별해 줍니다. 기본적으로 |f||x| f x g는 하나의 함수로 파싱됩니다. 다른 해석은 괄호로 함수를 경계 지어 적습니다: (|f||x| f x) g. 괄호는 중첩된 적용을 구별하는 데에도 쓰입니다. x z y z는 “x에 세 인자를 적용”으로 읽고, x z (y z)는 “x에 z와 중첩 적용 y z를 적용”으로 읽습니다.
마지막으로, 언어를 더 좋게 만들어 주는 문법 몇 가지를 끼워 넣겠습니다. 이 문법도 여전히 Ast로 매핑되어야 합니다. 종국에는 모든 것이 Ast가 되어야 하니까요. 다만 지금까지의 문법처럼 1:1 매핑되지는 않습니다. 이 문법은 디슈가링(desugaring) 패스를 통해 Ast 노드로 바뀌고, 실질적으로는 사라집니다. 이런 문법을 문법 설탕(syntax sugar)이라 부르는데, 파서와 표면 문법에만 존재하기 때문입니다.
여기서 타르 웅덩이에 빠질 위험이 있습니다. 문법 설탕은 설계상 필수가 아니고, 대응되는 Ast 노드도 없어서 발판이 없습니다. 그래도 다루고 싶은 이유는, 실전에서 문법 설탕이 전혀 없는 언어를 찾기 어렵기 때문입니다. 구현과 LSP 지원 방법을 다루는 건 중요하니까요. 다만 조심스럽게 걸어가겠습니다.
우리의 문법 설탕은 let 식입니다. 짐작했겠지만, 유일한 키워드 let에서 나왔죠. let 식은 식별자 하나와, 그 식별자를 정의하는 식 하나, 그리고 이제 막 정의된 식별자에 접근하는 식 하나로 구성됩니다. 예를 들어 let two = add 1 1; add two two. let은 중첩될 수 있으므로, 다음도 유효합니다:
let two = add 1 1;
let four = add two two;
add two four
let이 문법 설탕인 이유는, 어디서든 대신 함수를 적용하는 식으로 쓸 수 있기 때문입니다: (|two| add two two) (add 1 1). 동작은 완전히 같지만, 저는 let을 쓰고 싶습니다. 이제 모든 문법을 덮었습니다. 드디어 파싱을 시작할 준비가 됐군요.
문법을 정했으니 파서를 만들기 시작합시다. 파싱 함수들 사이에 가변 상태를 공유하고 싶습니다. 타입 추론 때와 같은 방법을 씁니다. Parser 구조체를 도입하고 각 함수를 메서드로 만듭니다:
struct Parser<'a> {
input: Input<'a>,
builder: GreenNodeBuilder<'static>,
errors: Vec<ParseError>,
in_error: bool,
}
errors와 in_error는 에러 보고를 담당합니다. errors는 발견한 모든 에러를 모읍니다. in_error는 같은 텍스트 구간에 대해 에러를 중복 보고하는 걸 막습니다. 한 에러를 보고하기 시작했다면, 그 에러가 끝날 때까지 새 에러를 보고하지 않으려는 겁니다.
builder는 rowan에서 와서 CST를 유지합니다. 완성된 GreenNode는 불변이므로, 파싱 중에는 가변 빌더가 필요합니다. 마지막으로 input은 소스 텍스트를 관리하는 도우미 구조체입니다:
struct Input<'a> {
content: &'a str,
lexer: Peekable<logos::SpannedIter<'a, Syntax>>
}
content는 사용자가 제공한, 우리가 파싱할 소스입니다. 토큰에 대응하는 소스 텍스트를 얻기 위해 참조를 붙잡아 둡니다. lexer는 logo::SpannedIter로, Syntax 토큰과 그 토큰의 소스 문자열 상의 스팬을 함께 내보내는 이터레이터입니다.
참고
스팬(span)은 소스 텍스트에 대한 오프셋 범위로, Range<usize>로 표현됩니다.
해당 이터레이터에 .peekable을 호출해 완성된 lexer 타입을 얻습니다. 피킹(미리 보기) 덕분에 한 토큰을 앞서 볼 수 있습니다. Input은 소스 텍스트를 탐색하는 데 도움이 되는 메서드들을 제공합니다. 첫 번째는 다음 토큰을 볼 수 있는 peek입니다:
fn peek(&mut self) {
self
.lexer
.peek()
.map(|(tok, _)| match tok {
Ok(tok) => *tok,
Err(_) => Syntax::Error,
})
.unwrap_or(Syntax::EndOfFile)
}
Logos가 많은 일을 해 주어 tok(Result)를 만들어 줍니다. 그 결과가 Err이면 Error 토큰을 만듭니다. 전체 이터레이터가 None을 반환했다면 입력이 끝난 것이므로 EndOfFile을 반환합니다. 특정 토큰 위에 있는지 확인하고 싶은 일은 아주 흔합니다. 도우미 at을 만들어 확인합니다:
fn at(&mut self, token: Syntax) -> bool {
self.peek() == token
}
이 메서드들은 입력을 실제로 앞으로 진행시키지 않습니다. 다음 토큰은 마음껏 들여다볼 수 있지만, 어디까지나 한 개뿐입니다. 앞으로 나아가는 일은 advance가 맡습니다:
fn advance(&mut self) -> Option<Range<usize>> {
let (_, span) = self.lexer.next()?;
Some(span)
}
advance는 방금 지나간 토큰의 스팬을 반환합니다. 의외겠지만, 실제 토큰 자체는 반환하지 않고 스팬만 돌려줍니다. advance 호출은 항상 at 호출에 이어지므로, 우리는 이미 지금 ‘어떤’ 토큰 위에 있었는지 알고 있습니다. 사실상 at 다음 advance는 너무 흔해서, eat 도우미로 묶었습니다:
fn eat(&mut self, token: Syntax) -> Option<&str> {
if self.at(token) {
self.advance().map(|span| &self.content[span])
} else {
None
}
}
eat은 우리가 Input에서 가장 자주 부르게 될 메서드입니다. 주어진 token 위에 있다면 입력을 한 칸 전진합니다. eat은 행복 경로에서는 무엇을 해야 할지 압니다. 하지만 토큰이 없을 때 뭘 해야 하는지는 말하지 않습니다. 기대한 토큰 위에 있지 않다면 그냥 None을 반환합니다. 에러 처리는 Parser의 소관입니다.
파싱 상태를 익혔으니, 이제 진짜로 뭔가를 파싱해 봅시다. 잎사귀(leaf)에 해당하는 파싱 함수부터 시작해 최상위 program 파서까지 완성하겠습니다. 파서의 척추는 expect 함수입니다:
impl Parser<'_> {
fn expect(
&mut self,
token: Syntax,
anchor_set: HashSet<Syntax>
);
}
expect는 현재 입력 토큰이 특정 token일 것을 ‘기대’합니다. Input의 eat과 닮은 점이 눈에 띄죠. 다만 expect는 anchor_set을 받습니다. 에러 복구에 사용됩니다. 행복 경로는 간단합니다:
fn expect(&mut self, token: Syntax, mut anchor_set: HashSet<Syntax>) {
if let ControlFlow::Break(_) = self.ate(token) {
// `ate`가 Break를 반환하면, 기대한 토큰을 소비했고 끝입니다.
return;
}
// 기대한 토큰을 보지 못함
}
기대한 토큰을 봤을 때의 상태 관리는 ate가 맡습니다:
fn ate(&mut self, token: Syntax) -> ControlFlow<()> {
let Some(str) = self.input.eat(token) else {
// 올바른 토큰을 소비하지 못했으니 계속 진행합니다.
return ControlFlow::Continue(());
};
self.in_error = false;
self.builder.token(token.into(), str);
self.whitespace();
// 기대한 토큰을 소비했으니 일찍 반환합니다.
ControlFlow::Break(())
}
올바른 토큰을 먹었다면 in_error를 false로 설정합니다. 기대한 입력을 소비했으니, 진행 중이던 에러는 해결되었고 새 에러를 시작할 준비가 된 겁니다. 또한 토큰과 소스 텍스트를 담은 잎 노드를 트리에 추가합니다.
마지막으로 이 토큰 뒤의 공백을 먹습니다. 우리의 문법은 공백에 민감하지 않으니, 공백이 어디에 나타나든 크게 신경 쓰지 않아도 됩니다. 기대한 토큰을 먹을 때에만 처리하는 게 중요할 뿐, 그 외에는 공백을 눈에 띄지 않는 편리한 곳에서 처리하면 됩니다.
참고
ate는 bool을 반환해도 되지만, 이 용례에서는 ControlFlow<()>의 의미 있는 이름들이 더 잘 어울립니다.
올바른 token을 보지 못했다면, expect는 anchor_set으로 에러 복구를 수행합니다:
fn expect(&mut self, token: Syntax, mut anchor_set: HashSet<Syntax>) {
// 위의 행복 경로...
// 아니면 에러 복구 시작
// 기대한 토큰으로도 복구할 수 있으니, 앵커 집합에 반드시 넣어 둡니다.
anchor_set.insert(token);
self.recover_until(anchor_set, vec![token]);
// ...
}
우리의 에러 복구 전략은, anchor_set에 들어 있는 토큰을 만날 때까지 토큰을 버리는 것입니다. “앵커 집합에는 뭐가 들어갈까?”라는 질문이 적절합니다. 앵커 집합은 우리가 파싱을 재개할 줄 아는 구문들의 집합입니다. 따라서 무엇을 파싱하느냐에 따라 문맥적으로 달라집니다.
EndOfFile만 들어갑니다. 파일 전체 수준에서 파싱을 재개할 수 있는 점은 거기뿐이니까요.let이 포함됩니다.let 뒤에는 언제든 또 다른 let이 올 수 있습니다. let 내부에서 에러를 만나면, 현재 let 식을 에러로 마무리하고 다음 let 키워드에서 파싱을 재개할 수 있습니다. 현재의 예기치 않은 토큰부터 앵커 집합의 복구 토큰 중 하나를 만날 때까지의 토큰들은 버립니다:
fn recover_until(&mut self, anchor: HashSet<Syntax>, expected: Vec<Syntax>) {
let mut discard_toks = vec![];
while !self.input.at_any(anchor.clone()) {
let tok = self.input.peek();
let Some(span) = self.input.advance() else {
break;
};
discard_toks.push((tok, span));
}
// ...
}
여기서 ‘버린다’는 말은 액면 그대로가 아닙니다. 여전히 트리에 추가하되 Error로 표시할 겁니다. 왜 이렇게 가변 개수의 토큰을 버릴까요? 토큰을 그대로 두면 안 될까요? 뒤이은 파싱이 제대로 해석할 수도 있잖아요.
입력 let = foo 1; 2를 생각해 봅시다. let에 식별자가 빠졌습니다. 에러 복구를 하지 않으면, 식별자를 기대하는 첫 expect 호출이 실패하고 Input은 공백 위에 머물 겁니다:
let █= foo 1; 2
이후의 =에 대한 expect도 실패합니다. 현재 입력은 공백이지 =가 아니니까요. 빠진 식별자가 let 식 전반에 연쇄적으로 영향을 주면서, 파스 트리는 거대한 에러 하나가 됩니다.
그건 입력을 전혀 소비하지 않았기 때문입니다. 에러가 나면 항상 한 토큰만 건너뛰어, 언제나 전진하도록 만들면 어떨까요? 첫 예시에서 공백을 없애면 실패 지점이 드러납니다: let = foo 1; 2. 지금 식별자를 기대하다가 실패하면, =를 에러로 보고 건너뜁니다:
let =█foo 1; 2
그런데 이런, 이제 =에 대한 expect는 공백(혹은 foo)을 보게 됩니다. 또 실패하고, 다시 에러의 연쇄입니다.
우리는 파싱을 제꽤로 되돌릴 ‘딱 좋은 만큼’의 건너뛰기가 필요합니다. 정해진 개수의 토큰을 건너뛰는 방식으로는 좋은 에러 복구를 얻을 수 없습니다. 그래서 앵커 집합이 필요합니다. 앵커 집합은 우리가 어디까지 건너뛰어도 안전한지 알려 주고, 에러의 연쇄를 막아 줍니다. 앵커 집합을 쓰면, let = foo 1; 2에서 빠진 식별자를 마주쳤을 때 =가 앵커 집합에 있음을 보고, =까지의 모든 것을 에러로 표시합니다.
이제 let 파서는 다음 expect 호출을 위해 올바르게 동기화됩니다. 식별자가 없는 let 하나를, 대부분은 올바른 트리로 만들되 식별자만 눈에 띄게 빠진 형태로 만들죠. 다행히 식별자가 없다는 건 Parser의 문제가 아닙니다. 그건 이름 해석(name resolution)의 문제죠. 이 동기화가 바로 회복력의 비결입니다.
왜 토큰을 버리는지 더 잘 이해했으니, 에러를 어떻게 내보내는지 봅시다:
fn recover_until(&mut self, anchor: HashSet<Syntax>, expected: Vec<Syntax>) {
// 토큰 버리기...
// 이미 앵커 위라면 할 일이 없습니다.
if discard_toks.is_empty() {
if !self.in_error {
self.in_error = true;
self.errors.push(ParseError {
expected,
span: self
.input
.lexer
.peek()
.map(|(_, span)| span.clone())
.unwrap_or_else(|| {
let len = self.input.content.len();
len..len
}),
});
}
return;
}
// ...
}
토큰을 버리지 않았고, 아직 에러 중이 아니라면, 기대한 구문이 없었다는 사실을 사용자에게 알려주기 위해 여전히 에러를 내보내고 싶습니다. 에러에는 우리가 기대했던 토큰들(이 문맥의 expect라면 항상 하나)과, 진단을 표시할 스팬이 들어갑니다. 에러는 ‘빠진 토큰’ 때문에 생기므로, 당연히 스팬이 빠져 있을 겁니다. 그래서 입력의 다음 토큰 위에 에러를 걸어 둡니다. 토큰을 버렸다면, 보고는 더 흥미로워집니다:
fn recover_until(&mut self, anchor: HashSet<Syntax>, expected: Vec<Syntax>) {
// 토큰 버리기...
// 빈 에러 내보내기...
// discard_toks가 비어 있지 않으니 안전합니다.
let mut err_span = discard_toks[0].1.clone();
self.with(Syntax::Error, |this| {
for (tok, span) in discard_toks {
err_span.end = span.end;
this.builder.token(tok.into(), &self.input.content[span]);
}
});
if !self.in_error {
self.in_error = true;
self.errors.push(ParseError {
expected,
span: err_span,
});
}
}
버린 모든 토큰을 덮는 스팬을 만듭니다. 그러는 동안 버린 토큰들을 담은 Error 노드도 트리에 추가합니다. 이미 에러 중이 아니라면, 그 스팬으로 에러를 내보냅니다. 트리의 노드에는 항상 에러를 표시하지만, 사용자에게 에러를 내보내는 것은 에러 중이 아닐 때만 합니다. expect에는 마지막 남은 조각이 하나 더 있습니다:
fn expect(&mut self, token: Syntax, mut anchor: HashSet<Syntax>) {
// 행복 경로...
// 에러 복구...
let _ = self.ate(token);
}
expect의 끝에서 체크 없이 ate를 한 번 더 호출합니다. 에러 복구가 우리를 기대한 토큰 위에 올려놓았을 수도 있습니다. 그런 경우에는 여기서 그 토큰을 소비해야, 뒤이은 expect 호출이 에러를 내지 않습니다. 우리의 풍성한 let 예시로 돌아가 "let x | = foo 1; 2"를 떠올려 봅시다. 유효한 식 하나가 들어 있긴 한데, |가 하나 더 끼어 있죠. =에 대한 expect 호출은 |를 보고 에러로 버린 뒤, 성공적으로 =까지 복구합니다. 하지만 여기서 =를 다시 확인해 주지 않으면, 파싱을 계속하면서 현재 입력을 =에 그대로 남겨 두게 됩니다.
이제 expect를 활용해 파싱 앙상블을 맞춰나갈 수 있습니다. 우리의 최종 목표는 프로그램을 파싱하는 것이고, 우리에게 프로그램이란 식(expression)입니다. 식을 파싱하는 방향으로, 함수 적용(application)부터 파싱해 봅시다. 순진한 적용 파서는 이렇게 생겼을 수 있습니다:
fn application(&mut self) -> {
self.with(Syntax::App, |this| {
this.expr();
this.expr()
})
}
여기서 expr()은 곧 작성할 식 파서입니다. 보기 좋습니다. AST의 적용 노드와 1:1로 대응하고, 필요한 일을 정확히 합니다. 문제는, 이건 결코 돌아오지 않는다는 겁니다. 재귀 하강의 ‘재귀’가 여기서 거칠게 고개를 듭니다. 우리가 일찍이 말했듯, 식을 파싱하려면 적용을 파싱해야 하고, 방금 본 것처럼 적용을 파싱하려면 식을 파싱해야 합니다.
이런 상호 재귀는 재귀 하강의 본령입니다. 하지만 여기서는 ‘벌거벗은 재귀’가 되어 버립니다. 호출 체인의 어느 지점에서도 입력을 소비하지 않거든요. 파서가 expr() -> application() -> expr() -> application() -> ...처럼 영원히 호출을 이어가는 건 전혀 이상하지 않습니다. 이를 피하려면, expr에 대한 재귀 호출은 입력을 소비한 뒤에만 일어나도록 보장해야 합니다.
적용을 두 개의 식이 아니라, 두 개의 ‘원자(atom)’로 보겠습니다. 원자란 기본적으로 적용이 아닌 모든 식입니다. 우리에게 원자란 변수, 정수, 함수, 그리고 괄호식입니다. 원자는 적용일 수 없으므로 무한 재귀에 빠질 수 없습니다. 순진한 application을 고쳐, 실제 app에서는 임의 개수의 원자를 파싱합니다:
fn app(&mut self, anchor: HashSet<Syntax>) {
let checkpoint = self.builder.checkpoint();
let ControlFlow::Continue(()) = self.atom(anchor.clone()) else {
// 적용은 최소 한 개의 원자를 포함해야 합니다
self.recover_until(anchor, vec![Syntax::Expr]);
return;
};
let ControlFlow::Continue(()) = self.atom(anchor.clone()) else {
return;
};
self.builder.start_node_at(checkpoint, Syntax::App.into());
self.builder.finish_node();
while let ControlFlow::Continue(()) = self.atom(anchor.clone()) {
self.builder.start_node_at(checkpoint, Syntax::App.into());
self.builder.finish_node();
}
}
하나 이상의 atom을 파싱하는 건 좌재귀를 피하는 또 다른 전술입니다. x y z w 같은 일련의 적용을 (((x y) z) w)처럼 중첩된 적용으로 파싱하고 싶습니다. 하지만 x를 파싱할 때는 그 뒤에 몇 번의 적용이 더 중첩될지 알 수 없습니다. 그래서 재귀 대신 루프에서 모든 원자를 파싱하며, 진행하면서 적용을 중첩시킵니다.
app은 먼저 최소 한 개의 atom이 있음을 보장합니다. 다음으로 두 번째 원자가 있는지 확인합니다. 하나만 있으면 그대로 반환합니다. 우리는 app을 “하나의 식 + 임의 개수의 적용”을 파싱하는 데 사용할 겁니다. 두 개의 원자를 확보하면, app 맨 앞에서 만든 체크포인트를 사용합니다.
체크포인트는 이름이 암시하듯, 트리 안의 한 지점을 저장해 둔 뒤 나중에 거기에 노드를 추가하게 합니다. 지금은 두 원자가 있다는 걸 알기 전까지 App 노드를 만들지 못합니다. 하지만 App 노드가 필요하다는 걸 알게 되면, 이미 파싱한 두 원자를 그 노드가 감싸야 합니다.
아직 원자를 어떻게 파싱할지 알아내야 합니다. atom은 네 가지 경우를 파싱해야 하며, 다른 파서들과 달리 그 네 가지는 모두 선택적입니다. atom이 처리법을 모르는 토큰을 보면, 그 토큰을 소비하지 않고 그냥 반환합니다. 이 덕분에 app은 임의 개수의 원자를 파싱하되, 적용이 끝나면 멈춥니다. atom은 현재 입력 토큰을 매칭하는 것으로 시작합니다:
fn atom(&mut self, anchor: HashSet<Syntax>) -> ControlFlow<()> {
match self.input.peek() {
Syntax::Identifier => {
self.with(Syntax::Var,
|this| this.expect(Syntax::Identifier, anchor));
}
Syntax::Int => {
self.with(Syntax::IntegerExpr,
|this| this.expect(Syntax::Int, anchor));
}
// 함수와 괄호 케이스...
_ => {
return ControlFlow::Break(());
}
};
ControlFlow::Continue(())
}
처음 두 케이스는 간단합니다:
Identifier는 변수입니다.Int는 정수입니다.두 경우 모두 토큰을 자체 구문 노드로 감쌉니다. 순전히 편의를 위해서인데, 의미 있는 토큰을 노드로 감싸 두면 CST를 순회할 때 공백 사이에서 찾기 쉬워집니다. 다음으로 함수 문법을 봅시다:
fn atom(&mut self, anchor: HashSet<Syntax>) -> ControlFlow<()> {
match self.input.peek() {
// ...
Syntax::VerticalBar => {
self.with(Syntax::Fun, |this| {
this.expect(Syntax::VerticalBar, anchor.clone());
this.with(Syntax::FunBinder, |this| {
this.expect(Syntax::Identifier, anchor.clone())
});
this.expect(Syntax::VerticalBar, anchor.clone());
this.expr(anchor);
});
}
// ...
}
// ...
}
함수 문법 | <identifier> | <expr>가 코드에 곧장 매핑되는 걸 볼 수 있습니다. 함수 본문은 식입니다. 순진한 적용과 달리, 여기서는 항상 |를 소비한 뒤에 expr로 재귀하므로 순환 호출이 문제가 되지 않습니다. 괄호식도 비슷한 전술을 씁니다:
fn atom(&mut self, anchor: HashSet<Syntax>) -> ControlFlow<()> {
match self.input.peek() {
// ...
Syntax::LeftParen => {
self.with(Syntax::ParenthesizedExpr, |this| {
this.expect(Syntax::LeftParen, anchor.clone());
this.expr(unioning(&anchor, [Syntax::RightParen]));
this.expect(Syntax::RightParen, anchor);
});
}
// ...
}
// ...
}
괄호식은 이름 그대로입니다. 식이 괄호로 둘러싸여 있습니다. 식은 (로 보호되므로, 여기서 재귀해도 무한을 걱정할 필요가 없습니다.
앵커 집합도 수정합니다. 지금까지는 앵커 집합을 그대로 이어서 전달했지만, 이제 바뀝니다. 괄호식 ‘안에’ 있을 때, 오직 그때만, 뒤따르는 )로 복구할 수 있어야 합니다.
이제 원자와 적용을 파싱했습니다. 식 전체를 파싱하는 일의 반을 했습니다. 나머지 반은 let 바인딩을 파싱하는 let_입니다:
fn let_(&mut self, anchor: HashSet<Syntax>) {
self.with(Syntax::Let, |this| {
this.expect(
Syntax::LetKw,
unioning(
&anchor,
[Syntax::Identifier, Syntax::Equal, Syntax::Semicolon],
),
);
this.with(Syntax::LetBinder, |this| {
this.expect(
Syntax::Identifier,
unioning(&anchor, [Syntax::Equal, Syntax::Semicolon]),
)
});
this.expect(Syntax::Equal, unioning(&anchor, [Syntax::Semicolon]));
this.expr(unioning(&anchor, [Syntax::Semicolon]));
this.expect(Syntax::Semicolon, &anchor);
})
}
정확히 말하면, 아직 완전한 let 바인딩은 아닙니다. 완전한 let은 let <identifier> = <expr>; <expr>입니다. 하지만 우리는 let <identifier> = <expr>;까지만, 뒤따르는 식 없이 파싱합니다. 하나의 식에는 let 바인딩이 0개 이상 올 수 있습니다. app과 비슷하게, 재귀적으로 _let을 호출하지 않고 루프에서 임의 개수의 let 바인딩을 파싱한 다음, 스코프가 올바르게 되도록 트리를 정리합니다.
let 파싱은 앵커 집합을 더 무겁게 사용하며, 광범위하게 수정합니다. 각 기대 토큰마다, 그 위치에서 남은 동기화 지점들이 앵커 집합에 포함되길 원합니다.
<identifier> = <expr> ;)이 그것들이니까요.<expr> ;이니까요.식(expression)에서 온 것은 앵커 집합에 포함하지 않습니다. 식은 우리의 전 문법을 포괄하므로, 좋은 동기화 지점이 아닙니다. let_이 식 한가운데(예: |)에서 복구해 버리면, 거기서 어떻게 파싱을 이어가야 할지 알 수 없을 겁니다.
=가 빠진 것을 만나면, <expr> 전체를 에러로 간주하고 다음 ;에서 파싱을 재개하겠습니다. 이건 트레이드오프이고 과학보다는 예술에 가깝습니다. 실전에서 이런 방식이 적은 노력으로 꽤 그럴싸한 에러를 내준다고 느꼈지만, 더 정교한 복구를 시도해 볼 수도 있습니다.
솔직히, 이 앵커 집합 관리는 반복적이고 판에 박혔습니다. 이걸 쉽게 추상화할 수도 있을 겁니다. 각 토큰에서, 앵커 집합은 자기 다음에 올 토큰들을 포함하길 원합니다. 자동으로 계산할 수 있습니다. 각 파싱 함수는 다음에 무엇이 따라올지 알고 있으니까요. 각 파싱 함수마다 이런 간단한 구조체를 만들 수 있습니다:
struct Let(Vec<Syntax>);
이 벡터를 vec![Syntax::LetKw, Syntax::Identifier, Syntax::Equal, Syntax::Expr, Syntax::Semicolon]로 설정해 두고, 그걸 이용해 앵커 집합에 ‘공짜로’ 무엇을 넣을지 정할 수 있습니다. 가만 보니, 이 벡터로 각 파서의 시작(first) 토큰도 구할 수 있겠네요. atom은 수동으로 match를 유지하지 않고, peek이 네 경우의 first 집합 안에 있는지만 확인하면 되겠죠! 가만 보니 또, first만 구할 필요도 없네요. 구조체로부터 아예 전체 parse 함수를 유도할 수도 있겠군요. 이를 위해서는 각 구문마다 몇 가지 연관 타입을 가진 Parse 트레잇만 있으면—
이러다 보면 곧 파서를 “만드는” 라이브러리(차마 파서 제너레이터라곤 말하지 않겠습니다)를 쓰게 될 테지만, 정작 ‘파서’는 쓰지 못하게 됩니다. 우리의 코드는 반복적이고 판에 박혔지만, 동시에 이미 ‘완성’되었습니다. 웅덩이가 더 밀려오기 전에 빨리 다음으로 넘어갑시다. let을 처리했으니 이제 식을 파싱할 모든 조각을 모았습니다:
fn expr(&mut self, anchor: HashSet<Syntax>) {
self.with(Syntax::Expr, |this| {
while this.input.at(Syntax::LetKw) {
this.let_(unioning(&anchor, [Syntax::LetKw]));
}
this.app(anchor);
});
}
식은 임의 개수의 let 바인딩 뒤에 하나의 app(기억하세요, app은 원자 하나일 수도 있습니다)으로 이뤄집니다. app과 let_에서 겪은 온갖 곡절과 달리, expr은 놀랍도록 단도직입적입니다. 너무 직설적이기까지 합니다. 이게 정말 제대로 작동할까요? 다음 같은 식을 보면:
let one = |s||z| s z;
let add = |m||n||s||z| m s (n s z);
add one one
우리는 이를 다음 트리로 파싱합니다:
Let
Let
App
App
add…
세부는 생략했지만, 요지는 이렇습니다. let의 본문은 표현식에서 뒤따르는 무언가로 암시됩니다. 그리고 표현식은 적용으로 끝나는 평평한(let들의 나열) 구조입니다. 스코핑과 이름 해석에서는 let이 서로 안에 중첩되어 있음을 기억해야 하지만, 파스 트리에서는 평평하게 깔려 있어도 충분합니다. 중요한 건, 이 나열이 app으로 끝난다는 점입니다. 모든 let 바인딩이 본문을 갖게 보장하거든요. 예컨대 다음은 잘못된 문법입니다:
let one = |s||z| s z;
add one one
let add = |m||n||s||z| m s (n s z);
expr이 만들어낼 수 있는 파스는 거기서 끝이 아닙니다. expr은 3도 기꺼이 파싱합니다. let 키워드가 없으니 let 바인딩은 하나도 파싱하지 않고, app은 원자 하나만 보았으므로 그대로 반환합니다. 3은 다음 트리로 바뀝니다:
3와! expr은 정말 다 합니다. expr이 맡는 또 하나의 중요한 역할이 있습니다. 바로 program입니다. 우리의 기초 언어에서 프로그램은 곧 식입니다. 다른 게 있을 수가 없거든요. 표현식이 곧 프로그램이라는 사실 덕분에 program 파서도 간단해집니다:
fn program(&mut self) {
self.with(Syntax::Program, |this| {
this.whitespace();
this.expr(hashset![Syntax::EndOfFile]);
if !this.input.at(Syntax::EndOfFile) {
this.recover_until(hashset![], vec![Syntax::EndOfFile]);
}
});
}
음, 생각만큼 간단하지는 않군요. 왜 expr() 한 번만 호출하면 안 될까요?
각 expect 호출은 토큰을 소비할 때 뒤따르는 공백을 먹습니다. 하지만 expect를 호출하기 전의 ‘선행’ 공백을 먹어 주는 곳은 없습니다. 모든 표현식에서 선행 공백을 먹을 필요는 없습니다. 대부분의 표현식은 앞에 ‘무언가’가 있으니까요. 하지만 program은 정의상 앞에 아무것도 없습니다. 따라서 선행 공백을 처리해야 합니다. 그렇지 않으면 "\n 3" 같은 입력에서 파서는 완전히 멈춰버릴 겁니다.
프로그램은 입력 문자열 전체를 소비해야 합니다. 하지만 expr은 하나의 유효한 표현식만 소비합니다. 그 이후 남는 것은 프로그램의 문제입니다. 다행히 답은 쉽습니다. 남는 것을 에러로 처리하면 됩니다. 그러면 이전의 잘못된 예시도 처리됩니다:
let one = |s||z| s z;
add one one
let add = |m||n||s||z| m s (n s z);
우리는 유효한 표현식 let one = |s||z| s z; add one one까지 파싱한 뒤, EndOfFile이 아니라 LetKw 위에 서 있음을 알게 됩니다. recover_until 호출이 남은 입력을 에러로 소비합니다.
program은 최상위 파서이지만, 여전히 Parser 구조체의 메서드입니다. 파싱의 진입점은 최상위 parse 함수로, 문자열을 받아 CST와 발생한 에러들을 반환합니다:
fn parse(input: &str) -> (GreenNode, Vec<ParseError>) {
let mut parser = Parser::new(input);
parser.program();
(parser.builder.finish(), parser.errors)
}
우리는 회복력을 위해 항상 트리와 에러를 함께 반환합니다. 성공적으로 파싱되면 errors는 비어 있을 뿐이고, 그것으로 충분합니다. 해냈습니다! 우리는 파싱하고 있으며, 타르 웅덩이에 그다지 깊이 빠지지도 않았습니다. 다음 편에서는 문법 설탕을 디슈가링으로 처리하겠습니다.