Pratt 파싱을 블랙박스 추상화로 활용하기 위해 알아야 할 nuds, leds, 결합력, 매크로, 모달 렉싱의 핵심 원리를 설명합니다.
우연히 접한 Pratt 파싱 튜토리얼 대부분이 거의 모든 시간을 Pratt의 알고리즘을 설명하는 데 쓰고, 정작 중요한 Pratt의 근본 속성은 전혀 설명하지 않는다는 점이 눈에 띄었다. Rhombus 같은 고수준 언어로 프로그래밍한다면 Pratt는 겨우 9줄의 코드에 들어맞는다:
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
그리고 비밀 하나가 있다. 이것은 Pratt를 이해하기 위해 알아야 할 것 중 가장 중요하지 않은 부분이다. 사실 이 조각을 전혀 이해할 필요도 없다! 구현을 이해해야만 quicksort를 쓸 수 있다고 상상해 보라. 파일시스템을 처음부터 구현하는 법을 알아야만 파일을 쓸 수 있다고 상상해 보라. 여기에서도 같은 논리다. 추상화할 능력이 없다면 컴퓨터 과학에서는 아무 데도 갈 수 없다. 이 분야 전체가 그렇게 작동하기 때문이다. 실제로 나는 작년부터 작성해 온 컴파일러를 위해 Pratt에 크게 기반한 파싱 장치의 뼈대를, 위 코드 조각을 자세히 이해하려는 수고조차 들이지 않고 작성했다.
아직 납득하지 못했는가? 전통적인 파싱 기법에서 어떻게 하는지 잠시 생각해 보라. 컴파일러 컴파일러다! 실제로 파싱 엔진이 무엇을 하는지 배우려는 사람은 극소수뿐이므로, 이들은 코드 생성기로 파싱 알고리즘을 뱉어 내게 한다. Pratt도 다르지 않다. 하지만 Pratt는 아주 작아서 프로젝트에 복잡한 새 의존성을 추가하는 대신 이 9줄의 코드를 그냥 복사해 붙여 넣고 끝낼 수 있다. 알고리즘은 1973년 이래로 바뀌지 않았으며, 지금 바뀔 일도 없다.
이 글에서는 Pratt 파싱에서 실제로 염두에 두어야 할 점을 다룬다. 하지만 이것을 외우는 것이 목적은 아니다. 목적은 사고방식을 갖추는 것이다. 그 사고방식만 갖추면, 여기서 내가 하는 말 한마디조차 기억하려 애쓸 필요가 없다.
Pratt 파싱을 한 번도 접해 보지 않은 사람에게 확실히 추천할 수 있는 유일한 튜토리얼은 사실 Douglas Crockford가 GOTO 2013 컨퍼런스에서 한 발표다¹. Douglas Crockford는 다음과 같이 말했을 때 핵심을 정확히 짚었다.
Pratt는 정말 복잡한 파싱을 하나의 단순한 질문으로 줄인다. 토큰의 왼쪽에 무엇이 있을 것이라 기대하는가?
— Douglas Crockford, GOTO 2013
처음에는 의미 없는 신비로운 말처럼 보일 수 있지만, 이 질문은 파싱 문제를 대하는 방식의 틀이 되며 Pratt 파싱 사고방식을 내면화하도록 뇌를 재구성할 것이다. 이것이 이해해야 할 가장 중요한 것이다. 의미 동작은 nud와 led라는 두 범주에 등록한다. nud는 왼쪽에 아무것도 기대하지 않는 토큰이며(nud는 null denotation의 약자), led는 무언가를 기대한다(led는 left denotation의 약자).
전통적인 파싱 기법은 의미 동작을 생성 규칙에 등록한다. 다음은 GNU Bison 매뉴얼에서 그대로 가져온 예시다:
expr: expr '+' expr { $$ = $1 + $3; } ;
expr: expr '+' expr { $$ = $1 + $3; } ;
expr: expr '+' expr { $$ = $1 + $3; } ;
expr: expr '+' expr { $$ = $1 + $3; } ;
중괄호 사이의 텍스트는 왼쪽의 BNF 유사 문법이 일치할 때 실행되는 코드다. 정말 중요하므로 반복하겠다. 전통적인 파싱 기법은 의미 동작을 _생성 규칙_에 등록한다(생성 규칙은 정의상 비단말 기호다). 반면 Pratt 파싱은 의미 동작을 _단말 자체_에 등록한다. 이것은 파싱 문제를 대하는 방식의 근본적인 전환이다.
다음은 현재 내 컴파일러에 있는 테이블 코드의 간소화된 버전이다:
static constinit const auto nud_table = make_dispatch_table(
rule_c<token::lparen, token::nud::parse_lparen>,
rule_c<token::lbrace, token::nud::parse_lbrace>,
rule_c<token::code::exclamation_mark, token::nud::parse_negation>,
rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>,
rule_c<token::code::plus_sign, token::nud::parse_unary_plus>,
rule_c<token::code::minus_sign, token::nud::parse_unary_minus>,
rule_c<token::code::dplus_sign, token::nud::parse_preincrement>,
// ...
rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>,
rule_c<token::code::identifier, token::nud::parse_identifier>
);
static constinit const auto led_table = make_dispatch_table(
rule_c<token::lparen, token::led::parse_function_call>,
rule_c<token::lbrack, token::led::parse_array_indexing>,
rule_c<token::code::dvertical_bar, token::led::parse_logical_disjunction>,
rule_c<token::code::dampersand, token::led::parse_logical_conjunction>,
rule_c<token::code::dequals_sign, token::led::parse_equality>,
// ...
rule_c<token::code::dminus_sign, token::led::parse_postdecrement>,
rule_c<token::code::asterisk, token::led::parse_multiplication>
);
enum : unsigned
{
parse_until_end = 0,
prefix_operator_binding_power = 120,
};
static constexpr auto binding_power = make_dispatch_table(
rule_c<token::code::dvertical_bar, 10>,
rule_c<token::code::dampersand, 20>,
rule_c<token::code::dequals_sign, 30>,
// ...
rule_c<token::code::lparen, 130>,
rule_c<token::code::lbrack, 130>,
rule_c<token::code::dplus_sign, 130>,
rule_c<token::code::dminus_sign, 130>,
rule_c<token::code::dot_asterisk, 130>,
rule_c<token::code::rarrow, 130>,
rule_c<token::code::dot, 130>
);
static constinit const auto nud_table = make_dispatch_table(
rule_c<token::lparen, token::nud::parse_lparen>,
rule_c<token::lbrace, token::nud::parse_lbrace>,
rule_c<token::code::exclamation_mark, token::nud::parse_negation>,
rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>,
rule_c<token::code::plus_sign, token::nud::parse_unary_plus>,
rule_c<token::code::minus_sign, token::nud::parse_unary_minus>,
rule_c<token::code::dplus_sign, token::nud::parse_preincrement>,
// ...
rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>,
rule_c<token::code::identifier, token::nud::parse_identifier>
);
static constinit const auto led_table = make_dispatch_table(
rule_c<token::lparen, token::led::parse_function_call>,
rule_c<token::lbrack, token::led::parse_array_indexing>,
rule_c<token::code::dvertical_bar, token::led::parse_logical_disjunction>,
rule_c<token::code::dampersand, token::led::parse_logical_conjunction>,
rule_c<token::code::dequals_sign, token::led::parse_equality>,
// ...
rule_c<token::code::dminus_sign, token::led::parse_postdecrement>,
rule_c<token::code::asterisk, token::led::parse_multiplication>
);
enum : unsigned
{
parse_until_end = 0,
prefix_operator_binding_power = 120,
};
static constexpr auto binding_power = make_dispatch_table(
rule_c<token::code::dvertical_bar, 10>,
rule_c<token::code::dampersand, 20>,
rule_c<token::code::dequals_sign, 30>,
// ...
rule_c<token::code::lparen, 130>,
rule_c<token::code::lbrack, 130>,
rule_c<token::code::dplus_sign, 130>,
rule_c<token::code::dminus_sign, 130>,
rule_c<token::code::dot_asterisk, 130>,
rule_c<token::code::rarrow, 130>,
rule_c<token::code::dot, 130>
);
static constinit const auto nud_table = make_dispatch_table(
rule_c<token::lparen, token::nud::parse_lparen>,
rule_c<token::lbrace, token::nud::parse_lbrace>,
rule_c<token::code::exclamation_mark, token::nud::parse_negation>,
rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>,
rule_c<token::code::plus_sign, token::nud::parse_unary_plus>,
rule_c<token::code::minus_sign, token::nud::parse_unary_minus>,
rule_c<token::code::dplus_sign, token::nud::parse_preincrement>,
// ...
rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>,
rule_c<token::code::identifier, token::nud::parse_identifier>
);
static constinit const auto led_table = make_dispatch_table(
rule_c<token::lparen, token::led::parse_function_call>,
rule_c<token::lbrack, token::led::parse_array_indexing>,
rule_c<token::code::dvertical_bar, token::led::parse_logical_disjunction>,
rule_c<token::code::dampersand, token::led::parse_logical_conjunction>,
rule_c<token::code::dequals_sign, token::led::parse_equality>,
// ...
rule_c<token::code::dminus_sign, token::led::parse_postdecrement>,
rule_c<token::code::asterisk, token::led::parse_multiplication>
);
enum : unsigned
{
parse_until_end = 0,
prefix_operator_binding_power = 120,
};
static constexpr auto binding_power = make_dispatch_table(
rule_c<token::code::dvertical_bar, 10>,
rule_c<token::code::dampersand, 20>,
rule_c<token::code::dequals_sign, 30>,
// ...
rule_c<token::code::lparen, 130>,
rule_c<token::code::lbrack, 130>,
rule_c<token::code::dplus_sign, 130>,
rule_c<token::code::dminus_sign, 130>,
rule_c<token::code::dot_asterisk, 130>,
rule_c<token::code::rarrow, 130>,
rule_c<token::code::dot, 130>
);
static constinit const auto nud_table = make_dispatch_table(
rule_c<token::lparen, token::nud::parse_lparen>,
rule_c<token::lbrace, token::nud::parse_lbrace>,
rule_c<token::code::exclamation_mark, token::nud::parse_negation>,
rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>,
rule_c<token::code::plus_sign, token::nud::parse_unary_plus>,
rule_c<token::code::minus_sign, token::nud::parse_unary_minus>,
rule_c<token::code::dplus_sign, token::nud::parse_preincrement>,
// ...
rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>,
rule_c<token::code::identifier, token::nud::parse_identifier>
);
static constinit const auto led_table = make_dispatch_table(
rule_c<token::lparen, token::led::parse_function_call>,
rule_c<token::lbrack, token::led::parse_array_indexing>,
rule_c<token::code::dvertical_bar, token::led::parse_logical_disjunction>,
rule_c<token::code::dampersand, token::led::parse_logical_conjunction>,
rule_c<token::code::dequals_sign, token::led::parse_equality>,
// ...
rule_c<token::code::dminus_sign, token::led::parse_postdecrement>,
rule_c<token::code::asterisk, token::led::parse_multiplication>
);
enum : unsigned
{
parse_until_end = 0,
prefix_operator_binding_power = 120,
};
static constexpr auto binding_power = make_dispatch_table(
rule_c<token::code::dvertical_bar, 10>,
rule_c<token::code::dampersand, 20>,
rule_c<token::code::dequals_sign, 30>,
// ...
rule_c<token::code::lparen, 130>,
rule_c<token::code::lbrack, 130>,
rule_c<token::code::dplus_sign, 130>,
rule_c<token::code::dminus_sign, 130>,
rule_c<token::code::dot_asterisk, 130>,
rule_c<token::code::rarrow, 130>,
rule_c<token::code::dot, 130>
);
각 테이블 왼쪽의 모든 값은 단말 기호에 대한 렉서 코드다. 오른쪽 값은 테이블 종류에 따라 달라진다:
Nud 테이블
서명 ExprPtr(Context&,reader,reader&)에 맞는 함수.
Led 테이블
서명 ExprPtr(Context&,reader,reader&,ExprPtr)에 맞는 함수.
결합력 테이블 양의 정수.
이 테이블의 의미 동작 대부분은 본문 구현이 많아야 세미콜론 하나 정도에 해당하는 코드다. 다음은 parse_unary_plus() 코드다:
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
겉으로는 코드를 구성하는 방식이 다르지만 여전히 매우 비슷해 보일 수 있으나, 실제 영향은 엄청나다. 이 한 가지 차이만으로 생기는 전통적 파싱 기법과의 차이 몇 가지는 다음과 같다:
LL(k) 같은 전통적 파싱 기법에서 발생하는 좌재귀 문제를 걱정할 필요가 없다. 연결된 토큰이 이미 스트림에서 소비된 뒤에 의미 동작으로 디스패치하므로 좌재귀는 아예 발생하지 않는다. 문제가 아니다.
파싱 엔진은 대안을 시험하거나 되돌아갈 필요가 없다. 일부 파서에서 보이는 속도와 메모리 사이의 통상적 양분법(예: PEG 대 packrat)은 사라진다. Pratt는 빠르며 터무니없는 양의 메모이제이션에 굶주리지 않는다. Pratt는 숫자를 비교하고, 반복하거나 재귀할 뿐이다.
앞선 항목과 관련 있지만 별도로 고려할 가치가 있다. 의미 동작은 정확히 한 번 실행된다! 즉, 일치에 실패했을 때 이전 상태로 롤백할 필요가 없다. 다시 말해 동작에 부수 효과가 포함될 수 있다. 내 파서에서는 각 계층을 통과하며 주고받는 공유 컨텍스트 객체를 통해 어휘 스코프에서 이름 예약과 해제를 수행하는 데 이 속성을 쓴다. 다만 부수 효과를 남용하여 스파게티가 되지 않도록 주의하라.
역시 관련 있다. 의미 동작은 항상 자신이 올바른 일치임을 안다. 따라서 원한다면 임의로 멀리 앞을 볼 수 있다. 다시 말해 의미 동작에서 PEG 파서 또는 계층형 Pratt 파서를 더 사용할 수 있다. Pratt 자체는 한 번에 토큰 하나만 먹지만, nud와 led 자체는 한 라운드에 더 많은 토큰을 먹을 수 있다. 이제 파서 조합자의 힘을 얻었다.
문법 모호성 대부분은 테이블 충돌이 되므로 더 단순한 모호성 사례에 시간을 덜 낭비한다. 여러 파서를 결합한다면 문법 모호성이 여전히 가능하다. 따라서 문법 설계자로서 할 일은 남지만, 내 경험상 훨씬 적다. 파서를 결합할 때 실제로 결합하는 것은 문법이다. 파싱 알고리즘으로서 Pratt는 모든 것을 보는 신탁이 되어 전체 문법 결합체의 가능한 모든 모호성을 탐지하지 않는다. Pratt는 PEG처럼 이 경우 가능한 첫 번째 일치를 반환할 뿐이다.
테이블의 비어 있는 틈은 문법의 사소한 확장 지점이 된다. 지금까지 파싱한 텍스트에 반응하여 이 틈을 채울 수 있다. 다시 말해 매크로를 구현할 수 있고, 심지어 자신의 연산자를 확장하는 언어도 파싱할 수 있다. 반면 생성 규칙 기반의 기존 문법을 확장하는 일(정통 파싱 학파)은 박사 연구급의 복잡성을 감수할 만한 작업이다.
전통적 학파에서도 이 속성 몇 가지를 찾을 수는 있겠지만, 어느 정도까지만 가능하거나 엄청난 복잡성 대가를 치러야 한다.
그럼에도 앞서 이 구성이 사고방식의 _전환_이라고 했지만, 지금까지는 Pratt를 채택함으로써 사용할 수 있는 속성만 언급했다. 그렇다면 전환은 정말 어디에 있는가? 함수 호출을 파싱하는 보통의 EBNF 규칙을 생각해 보자:
function_call = identifier, "(", [ argument_list ], ")" ;
argument_list = expression, { ",", expression } ;
function_call = identifier, "(", [ argument_list ], ")" ;
argument_list = expression, { ",", expression } ;
function_call = identifier, "(", [ argument_list ], ")" ;
argument_list = expression, { ",", expression } ;
function_call = identifier, "(", [ argument_list ], ")" ;
argument_list = expression, { ",", expression } ;
생성 규칙 대신 도구 상자에 nud와 led만 있을 때 이 문제에 어떻게 접근하는가? 핵심 관찰은 여는 괄호가 언제나 왼쪽에 무언가를 기대한다는 것이므로 led라는 점이다. 끝이다. lparen에 led를 등록하고 거기서 함수 호출을 파싱하라. 전통적 파싱 학파만 접했다면 이는 즉시 명백하지 않다. 그래서 Douglas Crockford가 다음과 같이 말했을 때 핵심을 정확히 짚은 것이다:
Pratt는 정말 복잡한 파싱을 하나의 단순한 질문으로 줄인다. 토큰의 왼쪽에 무엇이 있을 것이라 기대하는가?
— Douglas Crockford, GOTO 2013
배열 인덱싱용 led는 함수 호출용 led와 매우 비슷하다. 다음은 내 파서에서 사용하는 변형이다:
std::shared_ptrast::Expr parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
std::vector<std::shared_ptrast::Expr> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eatcode::comma()) {
throw unexpected_token{r, /expected=/"]"};
}
indexes.emplace_back(parse_expr(context, r, parse_until_end));
}
}
assert(r.code() == rbrack);
r.next_on_expr_scope();
return ast::make_exprast::ArrayIndexing(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptrast::Expr parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
std::vector<std::shared_ptrast::Expr> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eatcode::comma()) {
throw unexpected_token{r, /expected=/"]"};
}
indexes.emplace_back(parse_expr(context, r, parse_until_end));
}
}
assert(r.code() == rbrack);
r.next_on_expr_scope();
return ast::make_exprast::ArrayIndexing(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptrast::Expr parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
std::vector<std::shared_ptrast::Expr> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eatcode::comma()) {
throw unexpected_token{r, /expected=/"]"};
}
indexes.emplace_back(parse_expr(context, r, parse_until_end));
}
}
assert(r.code() == rbrack);
r.next_on_expr_scope();
return ast::make_exprast::ArrayIndexing(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptrast::Expr parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
std::vector<std::shared_ptrast::Expr> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eatcode::comma()) {
throw unexpected_token{r, /expected=/"]"};
}
indexes.emplace_back(parse_expr(context, r, parse_until_end));
}
}
assert(r.code() == rbrack);
r.next_on_expr_scope();
return ast::make_exprast::ArrayIndexing(
tok.line(), tok.column(), left, std::move(indexes));
}
Pratt는 단순히 우선순위 오르기가 아니다. Pratt는 코드를 구성하는 방식이다. 먼저 Pratt를 블랙박스로 학습하면 이 차이를 이해하는 데 실제로 도움이 된다. 블랙박스에 접근할 수 없다면 Pratt를 우선순위 오르기로 축소하고 싶은 유혹을 받지 않을 것이다. 추상화를 걷어 내고 내부를 보고 싶어질 때쯤이면, Pratt 파싱으로 열리는 모든 힘을 이미 접했을 것이므로 Pratt를 단순한 우선순위 오르기의 변형으로 취급하는 실수를 하지 않기를 바란다. 프로토타입 상속 없이 Pratt 파싱을 다룬 Andy Chu의 블로그 글은 Pratt 파서를 작성하는 상반된 두 스타일을 대비하므로 읽을 가치가 있다². 다음은 Andy Chu가 보여 준 스타일보다 프로토타입 상속을 사용하는 버전에 문체상 더 가까운, Rhombus로 작성한 최소 계산기다:
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
method nud(): nud_impl(this)
method led(lhs): led_impl(this, lhs)
method prefix(): expression(30)
method rhs(): expression(this.lbp)
class RParen(): extends Token
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
println(expression())
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
method nud(): nud_impl(this)
method led(lhs): led_impl(this, lhs)
method prefix(): expression(30)
method rhs(): expression(this.lbp)
class RParen(): extends Token
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
println(expression())
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
method nud(): nud_impl(this)
method led(lhs): led_impl(this, lhs)
method prefix(): expression(30)
method rhs(): expression(this.lbp)
class RParen(): extends Token
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
println(expression())
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
method nud(): nud_impl(this)
method led(lhs): led_impl(this, lhs)
method prefix(): expression(30)
method rhs(): expression(this.lbp)
class RParen(): extends Token
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
fun expression(rbp = 0):
let mutable t = token
advance()
let mutable left = t.nud()
while rbp < token.lbp:
t := token
advance()
left := t.led(left)
left
println(expression())
앞 절은 이 블로그 글 전체에서 가장 밀도 높은 부분이었을지도 모르므로, Pratt 사고방식을 숙성시키는 동안에는 속도를 늦추고 당분간은 사소한 것들을 살펴보겠다:
Pratt에는 별도의 렉서가 필요하다. 일부 현대 파싱 엔진은 스캐너리스 방식으로 작동하거나(예: PEG), 렉서 정의를 파서 자체에 직접 포함하기도 하지만 Pratt에는 별도의 렉서가 필요하다. 크게 우려할 일은 아니지만 기억해 둘 사항이다.
Pratt는 빠르다. 알고리즘은 숫자를 비교하고 반복하거나 재귀할 뿐이다. 한 토큰만 앞을 보며, 실제로 다른 일은 하지 않는다. 대안을 시험하기 위해 되돌아가거나 실패한 생성 규칙에서 백트래킹하지 않는다. 전혀 되돌아가지 않는다. 한 번에 토큰 하나를 먹으며 앞만 바라보는 전속력 기관차다.
Pratt 자체가 이미 빠르므로 무언가를 최적화하고 싶다면 남은 것은 nud와 led용 디스패치 코드뿐이다. 내 경우에는 전역 읽기 전용 디스패치 테이블을 사용하지만, 지금까지 본 대부분의 튜토리얼은 고도로 동적인 스크립팅 언어에서 동적 객체를 사용한다.
Pratt는 문을 파싱할 수 없다. 문이 있는 언어를 파싱하려면 다른 기법과 결합해야 한다. 지난 블로그 글에서 이미 이 제약을 다루었으며, այնտեղ에서 해결책을 찾을 수 있다.
Pratt는 재귀 하강 파싱의 한 형태이므로 의미 동작에 사용자 정의 코드, 즉 튜링 완전 언어의 코드를 실행한다. 하지만 그것이 전부는 아니다. 의미 동작이 파싱 선택과 방향을 추가로 이끌기 때문에, 다음 입력 텍스트 조각을 어떻게 파싱할지 결정하기 위해 코드가 컨텍스트(예: 이전 선언)를 살펴볼 수 있다. 요약하면 일부 형태의 문맥 의존 파싱이 가능하며, 이는 더 많은 언어 부류의 문을 연다.
실제 세계에서 발견되는 일부 복잡한 언어를 파싱하려면 모달 렉싱을 써야 하지만, 이 주제는 이 글의 뒤 절에서 다루겠다.
Pratt는 GLR 파싱에서 하듯 증분 파싱에 쓸 수 없다. 하지만 이는 어차피 대부분의 파싱 알고리즘에는 없는 능력이다(알고리즘적 속성으로 말할 것이 바닥나고 있다). 증분 파싱은 tree-sitter 같은 도구에서 사용된다.
오늘 내 주장은 Pratt가 블랙박스 추상화라는 것이므로, 이 주장을 따라 Pratt를 사용하기 위해 지켜야 할 계약을 정리해 보자:
연결된 led가 있는 토큰에만 결합력 테이블 값이 필요하다. 실제의 튜토리얼은 보통 이 속성이 분명하지 않은 방식으로 작성되어 있다. 고도로 동적인 스크립팅 언어의 객체 대신 정적 테이블로 파서를 작성하면 더 명확해진다.
앞 항목과 관련하여, 접두 연산자의 결합력 값은 여전히 필요하지만 이 값은 Pratt 루프에서 전혀 쓰이지 않는다. 따라서 접두 연산자 값을 결합력 테이블에 채워 넣을 필요는 없지만, 실제에서 본 대부분의 코드는 어쨌든 그렇게 한다. 접두 연산자의 결합력을 같은 테이블에 넣는 편이 더 쉽다고 생각한다면 그렇게 하라. 다만 이 흔한 구성은 엄격한 요구사항이 아니라는 점을 기억하라. 접두 연산자 자체를 구현하는 nud만 접두 연산자의 결합력을 알면 된다.
led에 결합력 0을 절대 할당하지 마라.
쉼표 같은 구분자와 파서가 멈춰야 하는 알 수 없음/오류/EOF 토큰은 결합력이 0이어야 한다. 이들은 결합력 테이블에 존재할 필요가 없다.
모든 사람이 그러하듯 십진수로 작성한다면, 결합력 테이블에서는 10 단위의 증가폭을 채택하라. 이 값을 읽을 때 마지막 0은 무시해도 되지만, 연산자 사이의 여유 공간은 몇 가지 기법을 가능하게 한다.
그렇다면 Pratt에서 오른쪽에서 왼쪽으로 결합하는 연산자는 어떻게 구현하는가? 먼저 흔한 왼쪽에서 오른쪽으로 결합하는 중위 연산자를 보자. 다음은 led +용 내 코드다:
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptrast::Expr parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(context, r, bp);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptrast::Expr parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(context, r, bp);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptrast::Expr parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(context, r, bp);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptrast::Expr parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(context, r, bp);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
연산자를 오른쪽에서 왼쪽으로 결합하게 만들고 싶다면 bp 대신 bp - 1을 쓰기만 하면 된다:
std::shared_ptrast::Expr parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(
context,
r,
bp /* HERE'S THE DIFFERENCE: */ - 1
);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
std::shared_ptrast::Expr parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(
context,
r,
bp /* HERE'S THE DIFFERENCE: */ - 1
);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
std::shared_ptrast::Expr parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(
context,
r,
bp /* HERE'S THE DIFFERENCE: */ - 1
);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
std::shared_ptrast::Expr parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptrast::Expr left)
{
auto right = parse_expr(
context,
r,
bp /* HERE'S THE DIFFERENCE: */ - 1
);
return ast::make_exprast::Addition(tok.line(), tok.column(), left, right);
}
이는 Pratt 파싱 분야의 표준 기법이다. 말하자면 실무 비결이다. 알아야 하는 기법이다. 왜 작동하는가? 중요하지 않다. 오늘은 블랙박스다. 내일은 중요해질 수 있지만, 오늘은 작동 이유가 아니라 Pratt를 사용하는 법에만 집중해야 한다.
대부분의 언어 설계자가 매크로를 추가하지 않을 텐데 굳이 매크로 절을 쓰는 이유는 무엇인가? Pratt 매크로는 코드가 파싱하고 해석하는 언어로 구현된 nud/led일 뿐이다. 따라서 자체 nud/led가 할 수 있는 모든 일은 매크로에서도 가능해야 하며, 그 반대도 마찬가지다. Pratt 매크로에서 얻은 교훈은 Pratt 파싱 자체에서 얻은 교훈이다.
이는 원칙일 뿐 엄격한 진실은 아니다. 예를 들어 내 언어의 Pratt 매크로에서는 분명히 사실이 아니지만, 그 원칙은 여전히 내 지침이며, 바라건대 당신의 지침이기도 하다.
Lisp 이외 언어에서 매크로 구현은 전통적으로 여러 면에서 매우 제한적이다. C 같은 언어에는 텍스트 확장을 수행하는 전처리기 환경에서 작동하는, 단순한 텍스트 치환 템플릿 매크로가 있다. 따라서 렉싱 계층에서 작동한다. Lisp처럼 AST/파싱 계층에서 작동하는 매크로를 설계하는 것도 가능하다. 하지만 Pratt 매크로는 이전에 분리되어 있던 이 두 세계를 통합한다. 절차적 Pratt 매크로를 구현한다면 매크로는 렉서나 파서를 번갈아 호출하는 API를 사용할 수 있다. 내 매크로 시스템에는 아직 API가 충분하지 않아 실제 예시를 보일 수는 없지만, 다음과 같이 작동할 것으로 구상한다:
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
이 API들은 Pratt를 사용하는 많은 파서의 핵심 nud에서 이미 사용되는 것과 거의 같다. 매크로 시스템은 여기까지 오기 위해 이들을 매크로에도 노출하기만 하면 된다. 이 부분은 사실 쉽다. 매크로 시스템에서 진정 어려운 과제는 여기가 아니라 다른 곳에 있다. 매크로 시스템에서 가장 어려운 부분은 파싱이 아니라 위생성이다³⁴(적어도 Pratt 파싱을 쓰면 파싱은 쉬워질 것이다). 하지만 이 글은 매크로 시스템이 아니라 Pratt 파싱에 관한 글이므로, 위생성이나 다른 매크로 시스템의 어려움은 깊이 다루지 않겠다. 나는 이미 그런 문제들과 싸웠고 결국 이겼다.
여기서 얻어야 할 점은 Pratt 파싱이 아름답고 제약 없는 eDSL을 구현할 수 있는 강력한 매크로를 갖춘 언어를 가능하게 한다는 것이다. Pratt 매크로는 매크로가 확장되는 시점에 렉서와 파서에 접근할 수 있는 언어용 인터프리터일 뿐이다. nud와 led에서 쓰는 패턴은 Pratt 매크로에서도 보게 될 법한 패턴이다. 파싱되는 코드는 자신을 파싱하는 바로 그 파서에게 어떻게 파싱해야 하는지 가르친다. 메타에 대해 말해 보라!
대개 렉서는 컴파일러에서 가장 소홀히 다뤄지는 부분이다. 해결된 문제다. 설계에 시간을 낭비할 이유가 없다. 렉서 생성기를 써서 효율적인 렉서를 구현하고, 다시는 돌아보지 않고 넘어간다. 하지만 Pratt 알고리즘은 Rhombus 코드 9줄에 불과하다. 렉서는 이미 파서보다 클 가능성이 높다. 이것만 보더라도 렉서는 적어도 어떤 척도에서는 프로젝트에서 더 큰 역할을 한다.
하지만 그 이상이다. 코드의 모든 nud와 led는 일종의 하위 파서다. 하위 파서를 결합하는 것은 더 많은 언어 부류를 파싱할 힘을 여는 열쇠다. 렉서는 모든 하위 파서 사이의 벽을 넘나드는 유일한 공통 지점이 된다. 좋은 렉서 설계는 파서 조합성을 향상한다.
Pratt 학파의 실무자로서 배워야 할 가장 중요한 단일 렉싱 기법은 모달 렉싱이다. Pratt를 사용하지 않더라도 이 기법 자체로 유용하지만, 우리에게는 더욱 그렇다. Andy Chu가 간결하게 설명했듯이⁵, 모달 렉싱은 렉서에 추가 매개변수를 더함으로써 가능해진다:
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
같은 패턴을 표현하는 다른 방법도 있다. 내 프로젝트에서는 열거형 대신 별도 함수를 선호한다. C++ 프로그래머로서 정적 다형성과 동적 다형성의 경우를 구분하도록 잘 훈련받았고, 여기서는 디스패치 정보가 컴파일 시점에 완전히 정적으로 알려지는 사례다. 그러므로 열거형을 쓸 이유조차 없다. 다만 고도로 동적인 매크로 지원 언어에서는 이야기가 달라질 수 있다.
class reader
{
public:
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
// ...
};
class reader
{
public:
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
// ...
};
class reader
{
public:
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
// ...
};
class reader
{
public:
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
// ...
};
단순하지만, 모달 렉싱의 이 한 가지 정의적 특성은 렉서가 파서로부터 피드백을 받을 방법을 제공하여 훨씬 더 복잡한 많은 언어 부류를 파싱할 능력을 연다. 렉서는 문법 구조를 결코 알지 못하지만 파서는 언제나 안다. 이 정보를 파서에서 렉서로 되먹임으로써, 각 하위 언어가 충돌하는 토큰 정의를 가지거나(예: C++11의 오른쪽 시프트 연산자는 템플릿 문맥에서 서로 다른 토큰을 만들어 낸다) 완전히 다른 의미의 토큰을 가진 언어 조합 형태를 가능하게 한다. Andy Chu는 이것이 유용할 수 있는 곳의 포괄적인 예시를 이미 제시했으므로⁶, 여기서는 예시 하나만 보태겠다.
Rust에는 타입을 표현하기만 위한 별도의 하위 언어가 있다. 이 타입 주석은 주 언어 안에서 깔끔하게 구분된 위치에 나타난다. 보통 콜론 뒤에 오며 등호 또는 쉼표나 닫는 괄호 같은 구분자에서 끝난다:
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
내 언어 문법은 Rust에서 큰 영향을 받았다. 당연히 이러한 구조를 파싱하기 위해 모달 렉싱에 의존한다. 앞서 보인 함수 reader::next_on_type_scope()는 타입 주석 하위 언어에 쓰인다. 그리고 각각에 대한 Pratt 파서인 parse_expr()와 parse_type()가 있다. 그다지 설명이 필요한 복잡한 기법은 아니지만 아주 멀리 갈 수 있게 해 준다. 아이디어를 얻으면 코드는 거의 저절로 작성된다.
유일한 주의점은 렉서가 모든 토큰을 미리 렉싱하는 대신 풀 설계를 따라야 한다는 것이다. 어째서인지 사람들은 실행 흐름을 완전히 가로채는 푸시 API만 설계하기를 좋아하며, 모든 작업을 미리 수행하는 렉서를 구현하는 데 중독되어 있다. 흔한 구성이나 모달 렉싱에는 작동하지 않는다. Pratt 자체는 푸시 설계이므로 결국 설계가 혼합된다.
다음 주제로 넘어가면 공유할 렉서 기법이 더 있지만, 오늘은 제안 하나만 하겠다. 렉서가 I/O(시스템 호출)를 수행하거나 무엇이든 버퍼링하도록 설계하지 마라. 렉서의 복사본에서 작업해도 원래 객체에 관찰 가능한 부수 효과가 있어서는 안 된다. 복사는 저렴해야 하며 권장되어야 한다. 렉서 복사본에서 작업하면 일부 하위 파서에 필요할 수 있는 임의의 앞보기 기능이 가능해진다. 고정된 양의 앞보기만 필요하더라도(예: 토큰 3개) 이 설계는 똑같이 적합하다.
이 설계를 충족하기는 쉽다. 파일 전체를 한 번에 읽거나 mmap을 사용하고, 렉서가 이 공유 영역을 가리키며 작업하게 하면 된다. 어차피 AST만으로도 전체 입력 파일보다 더 많은 메모리를 쓸 가능성이 높으므로 여기서 메모리는 걱정거리가 되어서는 안 된다.
이제 +용 내 nud를 다시 보자:
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptrast::Expr parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_exprast::UnaryPlus(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
실제에서 보는 대부분의 코드는 토큰용 사용자 정의 타입을 두고 이를 nud와 led의 인수로 쓰지만, 나는 그 대신 렉서 자체를 저장하고 전달한다. 내 렉서는 복사 비용이 낮으므로 토큰을 전달할 클래스를 만들 필요가 없다. 토큰을 기대하는 계층은 어차피 일치한 렉심에서 직접 디코드할 수 있으므로, 렉서는 원본 입력 텍스트를 가리키는 포인터 몇 개만 저장하면 된다. 다음은 렉심에서 직접 디코드하는 기법을 보여 주기 위한, 내 프로젝트의 십진 리터럴 파싱 코드다:
std::shared_ptrast::Expr parse_declit(
ParsingContext& /context/, reader tok, reader& /r/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_exprast::IntegerValue(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
std::shared_ptrast::Expr parse_declit(
ParsingContext& /context/, reader tok, reader& /r/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_exprast::IntegerValue(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
std::shared_ptrast::Expr parse_declit(
ParsingContext& /context/, reader tok, reader& /r/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_exprast::IntegerValue(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
std::shared_ptrast::Expr parse_declit(
ParsingContext& /context/, reader tok, reader& /r/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_exprast::IntegerValue(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
게다가 이 설계는 토큰 1개를 롤백할 수 있게 하며, 나는 이를 <용 nud에서 사용한다:
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptrast::Expr parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = parse_type(context, r, parse_until_end);
// ...
}
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptrast::Expr parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = parse_type(context, r, parse_until_end);
// ...
}
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptrast::Expr parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = parse_type(context, r, parse_until_end);
// ...
}
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptrast::Expr parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = parse_type(context, r, parse_until_end);
// ...
}
이 기법은 오류가 발생했을 때 예외를 던지는 대신 오류를 전용 토큰 코드로 표현하는 렉서도 요구한다. 오류가 모든 하위 언어에서 치명적일 때는 여전히 예외를 쓰고 싶을 수 있다(예: 스트림에서 비 ASCII 문자가 발견된 경우).
이제 이 nud가 도대체 무엇을 파싱하는지 묻는 것은 타당하므로, 정확히 무엇을 하는지 살펴보자. 내 언어 문법에 큰 영향을 준 Rust는 타입의 필드 접근을 허용한다. 여기서 필드 접근은 :: 연산자로 수행한다. 예를 들면 다음과 같다:
use std::time::SystemTime;
let now = SystemTime::now();
use std::time::SystemTime;
let now = SystemTime::now();
use std::time::SystemTime;
let now = SystemTime::now();
use std::time::SystemTime;
let now = SystemTime::now();
하지만 제네릭의 경우처럼 타입을 참조하는 데 타입 주석 언어에 접근해야 한다면 어떻게 되는가? 그러면 주 언어에서 타입 주석 언어에 명시적으로 접근할 탈출구가 필요하며, 이는 <용 nud를 통해 수행된다:
// Inside the outer <>, we don't interpret
// Vec < u32 as Vec less-than u32.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the outer <>, we don't interpret
// Vec < u32 as Vec less-than u32.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the outer <>, we don't interpret
// Vec < u32 as Vec less-than u32.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the outer <>, we don't interpret
// Vec < u32 as Vec less-than u32.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
이제 이러한 종류의 문법을 Pratt로 파싱하는 방법을 알게 되었다. Simon Ochsenreither는 한때 제네릭에 <>를 사용하는 것은 나쁜 설계라고 주장했으므로⁷, 이것이 내 프로젝트에서 롤백 기법을 실제로 써야 했던 유일한 경우라는 점은 우연이 아닐지도 모른다. 나는 이를 해킹으로 여긴다. 그럼에도 찾을 수 있는 최선의 타협안이었기에 사용했다. 언어 설계는 어렵다.
공유할 렉서 기법은 훨씬 더 많지만, 나중 글로 미루어야 할 것 같다. 그중 일부는 이미 내 프로젝트에서 쓰고 있다. 어쩌면 아이러니하게도, 이런 렉서 기법을 고안할 수 있게 한 사고방식은 프로그래밍 언어 파싱에 쓰는 기법과 아무 관계가 없는 HTTP와 JSON 파싱 경험에서 얻었다.
Pratt는 파싱 사고방식의 전환이다. 문법 구조를 nud와 led로 분해하는 데 익숙해져야 한다. Douglas Crockford가 한 것처럼⁸ 접두, 중위, 접미 연산자 구현의 공통 부분을 인수분해하여 상용구를 제거하는 단축기를 작성하는 것은 완전히 괜찮다. 하지만 Alex Kladov가 2020년에 한 것처럼⁹(나도 한때 같은 실수를 했다) nud와 led 관점으로 추론하기를 거부해서든 다른 이유에서든 편의를 위해 Pratt 알고리즘 자체를 바꾸고 있다면, 중요한 것을 놓치고 있는 것이므로 처음부터 다시 시작해야 한다. Pratt 파싱을 블랙박스 추상화로 사용하면 Pratt 알고리즘을 바꿀 능력이 사라지며, 사고방식을 적응시키는 데 도움이 될 수 있다. 이것이 시작을 위한 내 조언이다.
공유할 파싱 기법은 더 많다(예: Pratt-walk 인터프리터, 완벽한 자동 완성이 있는 REPL). 하지만 더 고급 내용이므로 이후 글로 미루겠다.
