プログラミング
Prattパーサーはブラックボックスである
Pratt parsing is a black box (vinipsmaker.github.io)
要約
この記事は、Prattパーサーの学習において、その実装の詳細よりも、根本的な考え方（「トークンの左側に何が期待されるか？」という問い）を理解することの重要性を強調しています。このアプローチは、左再帰の回避、セマンティックアクションでの副作用の許容、文法設計の簡素化といった利点をもたらします。
全文翻訳
Prattパーサーはブラックボックスである
Prattパーサーに関する多くのチュートリアルが、そのアルゴリズムの実装に多くの時間を費やしているにもかかわらず、Prattパーサーの真に重要な特性についてはほとんど説明していないことに気づきました。Prattパーサーは、Rhombusのような高水準言語でプログラミングする場合、わずか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が2013年のGOTOカンファレンスで行った講演です¹。Douglas Crockfordは次のように述べており、的確でした。
Prattは、非常に複雑な処理である解析を、一つの簡単な質問に還元します。「トークンの左側に何があることを期待しますか？」
— Douglas Crockford, GOTO 2013
一見すると、意味のない神秘的な声明のように聞こえるかもしれませんが、それが解析の問題に立ち向かう上でのフレームワークとなる質問であり、Prattパーサーの考え方を内面化するようにあなたの脳を再配線します。これが理解すべき最も重要なことです。あなたは2つのカテゴリに意味的なアクションを登録します：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>
);
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>
);
テーブルの左側にあるすべての値は、終端記号のレキサーコードです。右側の値はテーブルの種類によって異なります。
Nudテーブル
ExprPtr(Context&,reader,reader&)のシグネチャに一致する関数。
Ledテーブル
ExprPtr(Context&,reader,reader&,ExprPtr)のシグネチャに一致する関数。
バインディングパワーテーブル
正の整数。
これらのテーブルのほとんどの意味アクションは、本体が最大で1つのセミコロンで構成されるコードを持っています。以下は parse_unary_plus() のコードです。
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
表面上は、単に異なるが非常に似たコード整理方法のように見えるかもしれませんが、その影響は実際には計り知れません。この単一の出発点から派生する、従来の解析手法とのいくつかの違いを以下に示します。
- LL(k)のような従来の解析手法で発生する左再帰の問題を心配する必要がありません。トークンがストリームから既に消費された状態で意味アクションへのディスパッチが行われるため、左再帰は発生しません。これは問題になりません。
- 解析エンジンは代替案をテストしたり、バックトラックしたりする必要がありません。一部のパーサー（例：PEG対packrat）に見られる速度対メモリの通常の二分法はなくなりました。Prattは高速であり、莫大なメモ化を必要としません。Prattは単に数値を比較し、反復または再帰するだけです。
- 前のポイントに関連していますが、それ自体で考慮する価値があります：意味アクションは正確に1回実行されます！つまり、マッチが失敗した場合に以前の状態にロールバックする必要はありません。言い換えれば、アクションには副作用を含めることができます。私のパーサーでは、このプロパティを使用して、レイヤー間でやり取りされる共有コンテキストオブジェクトを通じて、レキシカルスコープでの名前の予約/解放を行います。ただし、副作用を乱用してスパゲッティコードにならないように注意してください。
- 同様に：意味アクションは常に正しいマッチであることを認識しています。したがって、必要であれば任意の距離を先読みできます。つまり、PEGパーサー（またはレイヤー化されたPrattパーサー）を意味アクションでさらに使用できます。Pratt自体は一度に1つのトークンしか消費しませんが、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_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::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_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::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_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::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_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::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_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
Prattは単なる優先度クライミングではありません。Prattはコードを整理する方法です。まずPrattをブラックボックスとして学ぶことは、この違いを理解するのに役立ちます。ブラックボックスにアクセスできない場合、Prattを優先度クライミングに還元しようと誘惑されることはありません。希望としては、抽象化を取り除いて内部を見たいと思ったときには、Prattを単なる優先度クライミングのバリエーションとして扱う間違いを犯さないでしょう。なぜなら、その時には既にPrattパーサーによって解き放たれたすべての力に触れているからです。Andy ChuのPrattパーサーに関するブログ記事は、Prattパーサーを書く2つの対立するスタイルを対比しているため、読む価値があります²。以下は、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())
#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は高速です。アルゴリズムは数値を比較し、反復または再帰するだけです。1トークン先を見ているだけで、それ以上のことは何もしていません。代替案をテストしたり、失敗したプロダクションルールをバックトラックしたりするために戻ることはありません。単に、決して戻りません。1トークンずつ消費する、フルスピードの機関車です。
- Pratt自体が既に高速であるため、何かを最適化したい場合、残された唯一のことは、nudとledのディスパッチコードです。私の場合は、グローバルな読み取り専用ディスパッチテーブルを使用していますが、一般的に見られるチュートリアルのほとんどは、非常に動的なスクリプト言語で動的なオブジェクトを使用しています。
- Prattはステートメントを解析できません。ステートメントを持つ言語を解析するには、他の手法と組み合わせる必要があります。これは、前回のブログ記事で既に説明しており、解決策を見つけることができます。
- Prattは再帰下降解析の一種であり、意味アクションのためにカスタムユーザーコード（つまり、チューリング完全な言語のコード）を実行しますが、それがすべてではありません。意味アクションはさらに解析の選択/方向を駆動するため、コードはコンテキスト（例：以前の宣言）を見て、次の入力テキストの断片をどのように解析するかを決定する可能性があります。要約すると、文脈依存解析の一形態を持つことができ、より多くのクラスの言語への扉を開きます。
- ワイルドな言語のいくつかを解析するには、モーダルレキシングに頼る必要がありますが、このトピックについてはブログ記事の後半で触れることにします。
- Prattは、GLR解析で行われるようなインクリメンタル解析には使用できません。しかし、それはほとんどの解析アルゴリズムには見られない機能です（アルゴリズムのプロパティについて話すことが少なくなってきました）。インクリメンタル解析は、tree-sitterのようなツールで使用されます。
今日の私の主張は、Prattはブラックボックスの抽象化であるということです。この主張に従って、Prattを使用するために尊重する必要のある契約を以下に示します。
- ledに関連付けられたトークンのみが、バインディングパワーテーブルに値を持つ必要があります。一般的に見られるチュートリアルは、このプロパティが明白ではない書き方をしています。静的なテーブルを使用してパーサーを記述する場合、スクリプト言語で高度に動的なオブジェクトを使用する場合よりも、これがより明白になります。
- 前のポイントに関連しています：プレフィックス演算子のバインディングパワーにも値が必要ですが、この値はPrattループでは一切使用されません。したがって、プレフィックス演算子のバインディングパワーをテーブルに含めることは必須ではありませんが、一般的に見られるコードのほとんどはそうしています。プレフィックス演算子のバインディングパワーを同じテーブルに詰め込む方が簡単だと思うなら、ご自由にどうぞ。ただし、この一般的な配置が必須要件ではないことを覚えておいてください。プレフィックス演算子のバインディングパワーを知る必要があるのは、プレフィックス演算子自体を実装するnudだけです。
- ledにゼロのバインディングパワーを割り当てないでください。
- カンマのような区切り文字や、パーサーが停止しなければならない未知/エラー/EOFトークンは、バインディングパワーをゼロにする必要があります。これらはバインディングパワーテーブルに存在する必要はありません。
- 人間が書くように10進数で書く場合、バインディングパワーテーブルで10の増分を採用してください。これらの値を読み取るときは、最後のゼロを無視するだけでよいですが、演算子間の余分なスペースはいくつかのトリックを可能にします。
Prattパーサーで右から左への結合演算子を実装するにはどうすればよいでしょうか？まず、一般的な左から右への結合のインフィックス演算子を見てみましょう。以下は、led + の私のコードです。
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
演算子を右から左へ結合させたい場合、bpの代わりにbp - 1を使用するだけで済みます。
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
bp /* ここが違いです: */ - 1
);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
bp /* ここが違いです: */ - 1
);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
bp /* ここが違いです: */ - 1
);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
bp /* ここが違いです: */ - 1
);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
これはPrattパーサーの分野における標準的なトリックです。いわば、業界のトリックです。知っておくべきトリックです。なぜうまくいくのか？それは重要ではありません。今日はブラックボックスです。明日は重要になるかもしれませんが、今日はPrattの使い方に焦点を当てるべきであり、なぜうまくいくのかではありません。
なぜマクロのセクションを書くのか、多くの言語設計者はマクロを追加しないのに？Prattマクロは、コードが解析および解釈している言語で実装されたnud/ledにすぎません。したがって、あなた自身のnud/ledができることはすべて、マクロでも可能であるべきであり、その逆も同様です。Prattマクロから学んだ教訓は、Prattパーサー自体から学んだ教訓です。
これは単なる原則であり、厳格な真実ではありません。私の言語のPrattマクロでは、確かに真実ではありませんが、この原則は私（そしておそらくあなた）の指針であり続けます。
Lisp以外の言語でのマクロの実装は、伝統的に多くの点で非常に制限されています。Cのような言語では、マクロは単なるテキスト置換テンプレートであり、プリプロセッサのテキスト展開環境で機能します（したがって、レキシング層で機能します）。Lispで行われているようなAST/解析層で機能するマクロを設計することも可能です。しかし、Prattマクロは、これら2つの以前に分離されていた世界を統合します。手続き型Prattマクロを実装している場合、マクロがレキサーまたはパーサーのいずれかを交互に呼び出すAPIを使用できる可能性があります。私自身のマクロシステムにはまだ十分なAPIがないため、実際の例を示すことはできませんが、どのように機能するかを以下に示します。
macro passthrough(ctx) {
// "read"で始まる関数
// レキサーを駆動します（つまり、トークンを消費するだけです）。
ctx.read("(");
// "parse"で始まる関数
// パーサーを駆動します（つまり、解析された式を消費して返します）。
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// Rustと同様に、私自身のマクロシステムでは、
// 何か面白いことが起こっている可能性を示す親切な視覚的なヒントとして、
// マクロ呼び出しは感嘆符で終わる必要があります。
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// "read"で始まる関数
// レキサーを駆動します（つまり、トークンを消費するだけです）。
ctx.read("(");
// "parse"で始まる関数
// パーサーを駆動します（つまり、解析された式を消費して返します）。
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// Rustと同様に、私自身のマクロシステムでは、
// 何か面白いことが起こっている可能性を示す親切な視覚的なヒントとして、
// マクロ呼び出しは感嘆符で終わる必要があります。
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// "read"で始まる関数
// レキサーを駆動します（つまり、トークンを消費するだけです）。
ctx.read("(");
// "parse"で始まる関数
// パーサーを駆動します（つまり、解析された式を消費して返します）。
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// Rustと同様に、私自身のマクロシステムでは、
// 何か面白いことが起こっている可能性を示す親切な視覚的なヒントとして、
// マクロ呼び出しは感嘆符で終わる必要があります。
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// "read"で始まる関数
// レキサーを駆動します（つまり、トークンを消費するだけです）。
ctx.read("(");
// "parse"で始まる関数
// パーサーを駆動します（つまり、解析された式を消費して返します）。
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// Rustと同様に、私自身のマクロシステムでは、
// 何か面白いことが起こっている可能性を示す親切な視覚的なヒントとして、
// マクロ呼び出しは感嘆符で終わる必要があります。
passthrough!(std.puts("hello world"));
これらのAPIは、Prattパーサーを使用する多くのパーサーのコアnudで既に実際に使用されているものとほぼ同じです。マクロシステムは、それらをマクロにも公開するだけで、ここまで到達できます。この部分は実際には簡単です。マクロシステムで実際に挑戦的なタスクは、ここではなく、他の場所にあります。マクロシステムの最も難しい部分は、ハイジーン³⁴であり、解析ではありません（まあ…少なくともPrattパーサーを使用すれば、解析は簡単になります）。しかし、このブログ記事は（Pratt）解析についてであり、マクロシステムについてはではありません。そのため、ハイジーンやその他のマクロシステムの問題（私が既に戦い、最終的に勝利した問題）には深入りしません。
ここでの要点は、Prattパーサーが強力なマクロを持つ言語を可能にし、美しい制約のないeDSLを実装できるということです。Prattマクロは、マクロが展開される時点でレキサーとパーサーにアクセスできる、言語の単なるインタープリターです。nudとledで使用するパターンは、Prattマクロでよく見られるパターンです。解析されているコードは、解析しているパーサー自体にその方法を教えています（メタについて語ってください！）。
通常、レキサーはコンパイラの最も無視されがちな部分です。これは解決済みの問題です。その設計に時間を無駄にする理由はありません。レキサー生成を使用して効率的なレキサーを実装し、二度と振り返らないようにします。しかし、Pratt（アルゴリズム）はRhombusコードのわずか9行です。あなたのレキサーは、おそらく既にパーサーよりも大きいです。この点だけで、レキサーは（たとえ重要でないとしても）少なくとも1つの尺度でプロジェクトにおいてより大きな役割を果たしています。
しかし、それはさらに進みます。コード内のすべてのnudとledは、ある種のサブパーサーです。パーサーを組み合わせることは、さらに多くのクラスの言語を解析する力を解き放つ鍵です。レキサーは、すべてのサブパーサー間の壁を越える共通の単一点になります。良いレキサー設計は、パーサーの合成性を向上させます。
Pratt学派の実践者として、あなたが学ぶべき最も重要なレキシング技術はモーダルレキシングです。この技術は、Prattを使用していなくても単独で役立ちますが、私たちにとってはさらに役立ちます。Andy Chuが簡潔に説明しているように⁵、モーダルレキシングは、レキサーに余分なパラメータを追加することで可能になります。
// 従来のレキサー
Token Read();
// モーダルレキサー
// 各モードが異なるレキシングルールをトリガーします
Token Read(lex_mode_t mode);
// 従来のレキサー
Token Read();
// モーダルレキサー
// 各モードが異なるレキシングルールをトリガーします
Token Read(lex_mode_t mode);
// 従来のレキサー
Token Read();
// モーダルレキサー
// 各モードが異なるレキシングルールをトリガーします
Token Read(lex_mode_t mode);
// 従来のレキサー
Token Read();
// モーダルレキサー
// 各モードが異なるレキシングルールをトリガーします
Token Read(lex_mode_t mode);
この単純なモーダルレキシングの定義上の特徴は、各サブ言語が競合するトークン定義を持つ可能性がある（例：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() 関数は、型注釈サブ言語に使用されます。その後、それぞれ parse_expr() と parse_type() というPrattパーサーがあります。これはあまり説明を必要としない簡単なトリックですが、非常に遠くまで到達できます。アイデアが掴めれば、コードはほとんど独りでに書かれます。
唯一の注意点は、レキサーがプッシュ設計ではなくプル設計に従う必要があることです。なぜか人々は、実行フローを完全に奪うプッシュAPIのみを設計することを好み、これらの人々は、すべての作業を事前にレキシングするレキサーを実装することに中毒になっています。これは一般的な配置ですが、モーダルレキシングには適していません。Pratt自体はプッシュ設計なので、最終的には設計の混合になります。
次のトピックに移りますが、共有すべきレキサーのトリックは他にもありますが、今日は1つの提案だけです：IO（システムコール）を行ったり、バッファリングしたりしないようにレキサーを設計してください。レキサーのコピーで作業しても、元のオブジェクトに観測可能な副作用があってはなりません。コピーは安価であるべきで、奨励されるべきです。レキサーのコピーで作業すると、一部のサブパーサーに必要な任意のルックアヘッドが可能になります。固定量のルックアヘッド（例：3トークン）しか必要としない場合でも、この設計は同じように穴を埋めます。
この設計を満たすのは簡単です：ファイル全体を一度に読み込む（またはmmapを使用する）だけで、レキサーがこの共有領域を指すようにして作業を行います。ASTだけでも、入力ファイル全体よりも多くのメモリを使用する可能性が高いので、メモリはここでは問題にならないはずです。
さて、私の + のnudに戻りましょう。
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
世間で見かけるコードの多くは、カスタムトークン型を持ち、それをnudとledの引数として使用していますが、私はレキサー自体を格納/渡すだけです。私のレキサーはコピーが安価なので、トークンを渡すためのクラスを作成する必要はありません。トークンを期待するレイヤーは、マッチしたレキサーリテラルから直接デコードできるため、レキサーは元の入力テキストへのいくつかのポインタを格納するだけで済みます。以下は、私のプロジェクトで10進数リテラルを解析して、デコード・フロム・レキサー・ダイレクトリーのトリックを示す例です。
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, reader tok, reader& /*r*/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, reader tok, reader& /*r*/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, reader tok, reader& /*r*/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, reader tok, reader& /*r*/)
{
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
}
さらに、この設計により、< のnudで私が使用しているもののような、1トークンのロールバックが可能になります。
// このnudはparse_expr()（したがってexpr-scope）によって呼び出されます
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; // <--- ここで1トークンロールバックが発生します
// ここで、type-scope（異なるトークンを持つ別のサブ言語）のルールを使用して、
// 次のトークン（上記のロールバックの直後）を再レキシングします。
r.next_on_type_scope();
// 次にparse_type()（parse_expr()の代わりに）を呼び出します。
auto& type = parse_type(context, r, parse_until_end);
// ...
}
// このnudはparse_expr()（したがってexpr-scope）によって呼び出されます
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; // <--- ここで1トークンロールバックが発生します
// ここで、type-scope（異なるトークンを持つ別のサブ言語）のルールを使用して、
// 次のトークン（上記のロールバックの直後）を再レキシングします。
r.next_on_type_scope();
// 次にparse_type()（parse_expr()の代わりに）を呼び出します。
auto& type = parse_type(context, r, parse_until_end);
// ...
}
// このnudはparse_expr()（したがってexpr-scope）によって呼び出されます
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; // <--- ここで1トークンロールバックが発生します
// ここで、type-scope（異なるトークンを持つ別のサブ言語）のルールを使用して、
// 次のトークン（上記のロールバックの直後）を再レキシングします。
r.next_on_type_scope();
// 次にparse_type()（parse_expr()の代わりに）を呼び出します。
auto& type = parse_type(context, r, parse_until_end);
// ...
}
// このnudはparse_expr()（したがってexpr-scope）によって呼び出されます
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; // <--- ここで1トークンロールバックが発生します
// ここで、type-scope（異なるトークンを持つ別のサブ言語）のルールを使用して、
// 次のトークン（上記のロールバックの直後）を再レキシングします。
r.next_on_type_scope();
// 次にparse_type()（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;