2項演算子の優先度と結合性だけで作るパーサ
「Rustで作るプログラミング言語」関連のトピック、第2弾です。
前回は Rustack の話題でしたが、今回は Ruscal の構文解析の中で紹介できなかったトピックです。
Ruscalについては、拙著「Rustで作るプログラミング言語」で作り方を説明していますので、興味のある方は是非買って読んでみてください！（宣伝）
本書では再帰下降パーサを構文解析に使っていますが、再帰下降パーサには複数のマッチする構文の候補を繰り返し適用し、失敗したらバックトラックするという無駄があります。これは現代のCPUでは現実的な問題になることは少ないと思いますが、最適化できる無駄であることは事実です。本稿では2項演算子に特化した最適化手法である Precedence climbing method について紹介したいと思います[1]。
この手法は、一つのパーサを書くだけでいかなる2項演算の優先順位や結合性の組み合わせでも対応できるという利点がありますが、それだけではなく、演算子の実行時カスタマイズも可能になります。これは、例えば Haskell のようにユーザー定義の演算子に好きな優先順位や結合性を定義できる言語で役に立ちます。
Wikipedia には疑似コードが載っているのですが、これがえらく抽象的で読みにくく、これを動作する Rust コードに書き換えるのに難儀しました。
最終的には、こちらに置いたようなコードで実現しました。
優先度を辿るコード
肝となるのは次の bin_op 関数です(次のコード断片ではデバッグ用出力を取り除いてあります)。優先度を示す prec: usize を引数に取り、パーサ関数を返す高階関数となっていますが、これは nom を使ってパーサコンビネータに組み込むことを目論んでのことです[2]。しかしながら、実際のコードでは結局高階関数としての使い方はしませんでした。
fn bin_op<'src>(
prec: usize,
) -> impl Fn(Lexer<'src>) -> Option<(Lexer<'src>, Expression<'src>)> + 'src {
use std::convert::TryInto;
move |mut lexer: Lexer| {
let (next, mut ret) = term(lexer)?;
lexer = next;
let Some(mut lookahead) = lexer.peek() else {
return Some((lexer, ret));
};
while let Token::Op(op) = lookahead {
if precedence(&op) < prec {
break;
}
lexer.next()?;
let inner_next = lexer;
let (outer_next, rhs) = term(lexer)?;
lexer = outer_next;
let mut rhs: Expression = rhs.try_into().ok()?;
let Some(p_lookahead) = lexer.peek() else {
return Some((lexer, Expression::bin_op(op, ret, rhs)));
};
lookahead = p_lookahead;
while let Token::Op(next_op) = lookahead {
if precedence(&next_op) <= precedence(&op)
&& (precedence(&next_op) != precedence(&op)
|| associativity(&op) != Associativity::Right)
{
break;
}
let next_prec = precedence(&op)
+ if precedence(&op) < precedence(&next_op) {
1
} else {
0
};
(lexer, rhs) = bin_op(next_prec)(inner_next)?;
let Some(p_lookahead) = lexer.peek() else {
return Some((lexer, Expression::bin_op(op, ret, rhs)));
};
lookahead = p_lookahead;
}
ret = Expression::bin_op(op, ret, rhs);
}
Some((lexer, ret))
}
}
一目見て思うのは、やたら長いということではないでしょうか。これにはいくつか理由があります。まず、 Precedence climbing method は2重のループを持つので、パーサコンビネータを使った構文解析で見かける普通の関数よりも長くなりがちです。もう一つは、トークンの先読みを必要とするので、入力ソースが字句解析済みだという前提であることです。字句解析器は Lexical analyzer を略して Lexer という型に抽象化していますが、それでも長いです。さらに、無駄に高階関数にしようとして move したラムダを返していますが、これも複雑度を増しています(これはせいぜい3行程度ですが)。
それでも、全ての2項演算子に使いまわせるという点は利点です。
字句解析器 Lexer
Lexer の実体はただの文字列スライスです。本来はトークンの配列などに一度変換すれば、先読みから戻ってきたときの手戻りがなくなるとは思いますが、2項演算以外にも構文が存在するので、全ての構文要素にトークン化を施す必要があり、影響範囲が大きくなります。
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Lexer<'src> {
cur: &'src str,
}
Lexer には、トークンを切り出したうえで自分自身を次のトークンへ前進させる next というメソッドと、自分自身を変更させずに次のトークンを返す peek というメソッドを持ちます。
それぞれの実装は下記のとおりです。
impl<'src> Lexer<'src> {
fn next(&mut self) -> Option<Token<'src>> {
if let Some((r, res)) = token(self.cur) {
self.cur = r;
return Some(res);
}
None
}
fn peek(&self) -> Option<Token<'src>> {
if let Some((_, res)) = token(self.cur) {
return Some(res);
}
None
}
}
token という関数は、文字列スライスを入力に取り、入力の残りと認識したトークンを返す次のようなもので、 nom のコンビネータと互換性を持たせています。
fn token(input: &str) -> Option<(&str, Token)> {
if let Some(r) = lparen(whitespace(input)) {
return Some((r, Token::LParen));
}
if let Some(r) = rparen(whitespace(input)) {
return Some((r, Token::RParen));
}
if let Some(res) = ident(whitespace(input)) {
return Some(res);
}
if let Some(res) = number(whitespace(input)) {
return Some(res);
}
if let Some(res) = operator(whitespace(input)) {
return Some(res);
}
None
}
演算子の種類と優先順位と結合性の定義
では、どうやって2項演算子の種類と優先順位と結合性を区別するのでしょうか。それは別途定義した OpCode 列挙型で決まります。
#[derive(Debug, PartialEq, Clone, Copy)]
enum OpCode {
Add,
Sub,
Mul,
Div,
}
これは字句解析器が出力するトークンの一種になります。トークン自体は次のような列挙にしておきます。
#[derive(Debug, PartialEq, Clone, Copy)]
enum Token<'src> {
Ident(&'src str),
NumLiteral(f64),
Op(OpCode),
LParen,
RParen,
}
演算子の字句解析は次のようなロジックになります。まだ一文字の演算子だけなので簡単です。
fn operator(input: &str) -> Option<(&str, Token)> {
match peek_char(input) {
Some('+') => Some((advance_char(input), Token::Op(OpCode::Add))),
Some('-') => Some((advance_char(input), Token::Op(OpCode::Sub))),
Some('*') => Some((advance_char(input), Token::Op(OpCode::Mul))),
Some('/') => Some((advance_char(input), Token::Op(OpCode::Div))),
_ => None,
}
}
演算子の優先度は次のように関数で定義しておきます。
fn precedence(op: &OpCode) -> usize {
match op {
OpCode::Add => 1,
OpCode::Sub => 1,
OpCode::Mul => 2,
OpCode::Div => 2,
}
}
結合性は今のところ左結合しかありませんので、次のような定数関数になります。
#[derive(Clone, Copy, PartialEq, Eq)]
enum Associativity {
Left,
Right,
}
fn associativity(_op: &OpCode) -> Associativity {
Associativity::Left
}
式 (Expression) の修正
式 (Expression) は Ruscal の定義と似ていますが、任意の2項演算子を構文木のノードとして持てるようにするため、 BinOp バリアントの定義が OpCode を引数として持つようになります。
#[derive(Debug, PartialEq)]
enum Expression<'src> {
Ident(&'src str),
NumLiteral(f64),
BinOp {
op: OpCode,
lhs: Box<Expression<'src>>,
rhs: Box<Expression<'src>>,
},
}
2項演算子から式を作るコンストラクタを次のように用意しておきます。これは冒頭の bin_op 関数とは異なるので注意してください。
impl<'src> Expression<'src> {
fn bin_op(op: OpCode, lhs: Self, rhs: Self) -> Self {
Self::BinOp {
op,
lhs: Box::new(lhs),
rhs: Box::new(rhs),
}
}
}
また、トークンは構文木の葉になるはずですので(構文解析の世界では終端記号とも呼ばれます)、この変換を行う TryFrom トレイトを実装しておきます。 From トレイトにしない理由は、全てのトークンが葉になるわけではないからです。例えば + や - といったトークンは2項演算のノードになりますが、葉にはなりませんので、変換は失敗します。
impl<'src> TryFrom<Token<'src>> for Expression<'src> {
type Error = ();
fn try_from(value: Token<'src>) -> Result<Self, Self::Error> {
match value {
Token::Ident(id) => Ok(Expression::Ident(id)),
Token::NumLiteral(num) => Ok(Expression::NumLiteral(num)),
_ => Err(()),
}
}
}
エントリポイントとテスト
式のエントリポイントとなる全体のパーサは次のようになります。 bin_op を最低優先度 0 で呼び出しているところが肝です。
fn expr(lexer: Lexer) -> Option<(Lexer, Expression)> {
if let Some(res) = bin_op(0)(lexer) {
return Some(res);
}
None
}
いくつかの式の例でテストしてみましょう。まずは次のようなテスト用のヘルパー関数を用意しておきます。
fn test_case(input: &str) {
let lexer = Lexer::new(input);
match expr(lexer) {
Some((_, res)) => {
println!("source: {:?}, parsed: {}", input, res);
}
_ => {
println!("source: {input:?}, failed");
}
}
}
また、式を Debug トレイトの実装で出力すると、余計な情報が多くて非常に見にくいので、簡潔にフォーマットする Display トレイトの実装をしておきます。
impl<'src> std::fmt::Display for Expression<'src> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Ident(id) => write!(f, "{id}"),
Self::NumLiteral(num) => write!(f, "{num}"),
Self::BinOp { op, lhs, rhs } => {
write!(f, "(")?;
lhs.fmt(f)?;
write!(f, " {op} ")?;
rhs.fmt(f)?;
write!(f, ")")
}
}
}
}
これで次のようにテストしてみます。
fn main() {
// ...
test_case("123");
test_case("Hello + world");
test_case("1 * 3");
test_case("1 + 2 + 3");
test_case("1 - 2 + 3");
test_case("10 + 1 * 3");
test_case("10 * 1 + 3");
test_case("10 + 1 * 3 + 100");
test_case("9 / 3 / 3");
test_case("(123 + 456 ) + world");
test_case("car + cdr + cdr");
test_case("((1 + 2) + (3 + 4)) + 5 + 6 * 7");
}
結果は次のように出力されます。入力に明示的に括弧がついて優先順位が明確になったような出力で、合っていることは容易に見て取れます。
source: "123", parsed: 123
source: "Hello + world", parsed: (Hello + world)
source: "1 * 3", parsed: (1 * 3)
source: "1 + 2 + 3", parsed: ((1 + 2) + 3)
source: "1 - 2 + 3", parsed: ((1 - 2) + 3)
source: "10 + 1 * 3", parsed: (10 + (1 * 3))
source: "10 * 1 + 3", parsed: ((10 * 1) + 3)
source: "10 + 1 * 3 + 100", parsed: ((10 + (1 * 3)) + 100)
source: "9 / 3 / 3", parsed: ((9 / 3) / 3)
source: "(123 + 456 ) + world", parsed: ((123 + 456) + world)
source: "car + cdr + cdr", parsed: ((car + cdr) + cdr)
source: "((1 + 2) + (3 + 4)) + 5 + 6 * 7", parsed: ((((1 + 2) + (3 + 4)) + 5) + (6 * 7))
実行時に優先順位の変更を可能にする
ここまでは演算子の優先順位と結合性はハードコードされていましたが、実行時に変更を可能にするにはどうしたらいいでしょうか。単純に考えれば、 OpCode に優先順位などの情報を含めれば良いはずですが、パーサが常に演算子のリストにアクセスできないと構文解析ができないので、少々ややこしくなります。
結論から言えば、こちらに示すコードのように書けば可能です。
演算子の定義のデータ構造への変更
まずは OpCode を次の OpDef で置き換えます。ハードコードされた列挙型の代わりに文字列でコードを持ち、優先順位と結合性をフィールドに持ちます。
#[derive(Debug, PartialEq, Eq, Clone)]
struct OpDef {
code: String,
prec: usize,
assoc: Associativity,
}
また、演算子の定義を単純な Vec で定義しておきます。
type OpDefs = Vec<OpDef>;
パーサへの変更
さらに、演算子の字句解析器は次のように変わります。複数文字の演算子にも対応できるよう、文字列スライスの長さを考慮した比較にしています。この関数の注意点は、先にマッチする演算子があった場合、後の演算子のほうがより正しい構文であっても、早い者勝ちになってしまう点です。例えば、 op_defs に + と ++ という演算子が含まれていた場合、 + が先にチェックされると ++ はチェックの対象にすらなりません。
ここでもコンビネータ向けに高階関数にしていますが、やはり活用はできていません。
fn operator(op_defs: &OpDefs) -> impl Fn(&str) -> Option<(&str, Token)> + '_ {
move |input: &str| {
for op_def in op_defs {
if op_def.code.len() <= input.len() && &input[..op_def.code.len()] == op_def.code {
return Some((&input[op_def.code.len()..], Token::Op(op_def.clone())));
}
}
None
}
}
これを使っている token 関数も同じように op_defs を引数に取り、無駄に高階関数です。
fn token(op_defs: &OpDefs) -> impl Fn(&str) -> Option<(&str, Token)> + '_ {
move |input: &str| {
// ...
if let Some(res) = operator(op_defs)(whitespace(input)) {
return Some(res);
}
None
}
}
さらに、これを使っている Lexer に定義された演算子のリストへの参照を持たせます。
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Lexer<'src> {
op_defs: &'src OpDefs,
cur: &'src str,
}
impl<'src> Lexer<'src> {
fn new(op_defs: &'src OpDefs, input: &'src str) -> Self {
Self {
op_defs,
cur: input,
}
}
fn next(&mut self) -> Option<Token<'src>> {
if let Some((r, res)) = token(self.op_defs)(self.cur) {
self.cur = r;
return Some(res);
}
None
}
fn peek(&self) -> Option<Token<'src>> {
if let Some((_, res)) = token(self.op_defs)(self.cur) {
return Some(res);
}
None
}
}
テストハーネス再び
テスト用の関数には次のような標準の演算子を使います。ここでは最初のハードコードされた OpCode 列挙との違いを持たせるため、 ^ という演算子も追加しています。これは右結合です。
fn test_case(input: &str) {
let op_defs = standard_ops();
let lexer = Lexer::new(&op_defs, input);
match expr(lexer) {
Some((_, res)) => {
println!("source: {:?}, parsed: {}", input, res);
}
_ => {
println!("source: {input:?}, failed");
}
}
}
fn standard_ops() -> Vec<OpDef> {
vec![
OpDef::new("+", 1, Associativity::Left),
OpDef::new("-", 1, Associativity::Left),
OpDef::new("*", 2, Associativity::Left),
OpDef::new("/", 2, Associativity::Left),
OpDef::new("^", 3, Associativity::Right),
]
}
再びテストします。
fn main() {
// ...
test_case("123");
test_case("Hello + world");
test_case("1 * 3");
test_case("1 + 2 + 3");
test_case("1 - 2 + 3");
test_case("10 + 1 * 3");
test_case("10 * 1 + 3");
test_case("10 + 1 * 3 + 100");
test_case("9 / 3 / 3");
test_case("(123 + 456 ) + world");
test_case("car + cdr + cdr");
test_case("((1 + 2) + (3 + 4)) + 5 + 6 * 7");
test_case("5 ^ 6 ^ 7");
}
次のような結果が得られました。
source: "123", parsed: 123
source: "Hello + world", parsed: (Hello + world)
source: "1 * 3", parsed: (1 * 3)
source: "1 + 2 + 3", parsed: ((1 + 2) + 3)
source: "1 - 2 + 3", parsed: ((1 - 2) + 3)
source: "10 + 1 * 3", parsed: (10 + (1 * 3))
source: "10 * 1 + 3", parsed: ((10 * 1) + 3)
source: "10 + 1 * 3 + 100", parsed: ((10 + (1 * 3)) + 100)
source: "9 / 3 / 3", parsed: ((9 / 3) / 3)
source: "(123 + 456 ) + world", parsed: ((123 + 456) + world)
source: "car + cdr + cdr", parsed: ((car + cdr) + cdr)
source: "((1 + 2) + (3 + 4)) + 5 + 6 * 7", parsed: ((((1 + 2) + (3 + 4)) + 5) + (6 * 7))
source: "5 ^ 6 ^ 7", parsed: (5 ^ (6 ^ 7))
まとめ
Precedence climbing method は、比較的簡単な再帰下降パーサへの変更で、再帰のネストを減らすと同時に任意の2項演算子を定義できる、なかなか魅力的な手法です。特に、2項演算以外のパーサには大きな変更が必要ないところが再帰下降パーサとの相性がよさそうです。
ただし、素直な再帰下降パーサでは左結合の2項演算子は無限再帰を起こすので、その対策として fold_many0 を使ったループへの書き直しなどは結局必要になるため、実行速度に違いが出てくるかどうかはわかりません。
いずれにせよ言語設計者のツールボックスに持っておく価値のある技術でしょう。
参考文献
Precedence climbing method は、 Pratt parsing と呼ばれる構文解析手法の特殊な例らしいです。とはいっても Pratt parsing の方が古く、 1973 年の次の論文で説明されています。
Discussion