Clever Geek Handbook

Rustマクロを使用したLL（*）パーサー

わあそのような錆。多くのマクロ。

わあ そのような錆。 多くのマクロ。 ©Picture- TwitterアカウントServo







錆びた言語は急速に勢いを増しています。 誰かが彼にC / C ++の代わりになると預言し、誰かが彼を好きになります。 私はむしろ2番目のグループに属します。 開発者はそれを便利で安全にしようとしています。 委員会の慣性と他の多くの理由により、「プラス」にはまだ現れない構造と原則があります。 したがって、すべての個人プロジェクトでは、Rustを使用することを好みます。







さまざまな成功を収めながらコンパイラを作成しました。 単一のものを書く時間は本当にありませんでしたが、プロセス自体は結果よりも興味深いものです。







かつて、パーサー（別名「パーサー」）で再び立ち往生したとき、同じタイプのコードをたくさん書いていると思いました。 そして、この1対1のコードは、 バッカスナウア （BNF）の形式で 1対1の文法に適合します。







少し考えた後、文法ベースのコードジェネレータを記述する必要があると判断しました。 このタスクには、Rustのマクロが最適です。







この記事では、マクロを使用したLL（*）パーサーの実装について説明します。 そして、単純な数式のパーサーが実装されています。







その結果、BNF文法のパーサーは次のようになります。 







expr ::= sum sum ::= mul "+" sum | mul "-" sum | mul mul ::= atom "*" mul | atom "/" mul | atom atom ::= "(" expr ")" | number | neg; neg ::= "-" atom


一連のマクロを使用して生成できます： 







 rule!(expr, sum); rule!(sum, or![ and![(mul, token('+'), sum) => make_operator], and![(mul, token('-'), sum) => make_operator], mul ]); rule!(mul, or![ and![(atom, token('*'), mul) => make_operator], and![(atom, token('/'), mul) => make_operator], atom ]); rule!(atom, or![ and![(token('('), expr, token(')')) => |_lbrace, stat, _rbrace| Some(stat)], num, neg ]); rule!(neg, and![(token('-'), atom) => |_, number| Some(Box::new(expression::Expression::Negate(number)))]);


この記事では、コードの一部の実装を意図的に単純化し、Rustナイトアセンブリの不安定な機能を使用します。 これにより、理解が簡単になり、読みやすさが向上することを期待しています。







したがって、すでに述べたように、同じ名前の文法のファミリーを解析できるLL（*）パーサーを生成します。 パーサーのこのサブセットの特別な点を読むのが面倒な場合、要するに手で書くのは簡単ですが、左再帰の文法を解析することはできません（必要ありません）。







パーサーをテストするために、上記の文法を使用します。 彼女は算術式を解析する方法を知っています。彼女はLL（*）文法であり、テストには十分です。







字句アナライザー（別名「レクサー」）から始めましょう。







字句解析器



簡単にするために、レクサーはスペースをスキップして1行につき1文字を提供します。 別のタイプのトークンは使用しませんが、文字タイプを使用します。 同じ理由で、数字は1桁のみです。







LL（*）文法の場合、任意の数の文字にロールバックできる字句解析器が必要です。 字句解析器の入力に文字列を取り、文字を1つずつ与えます。 さらに、ポジションを取得し、レクサーをポジションにロールバックする機能があります。







字句解析器は文字列を遅延して動作できますが、簡単にするために文字列全体を文字ベクトルに変換します。 







 #[derive(Debug)] pub struct Lexer { /// Input string input: Vec<char>, /// Lexer position position: usize } type Position = usize; impl Lexer { pub fn new(input: &str) -> Self { // Compiler bug. Can't drain string inplace let mut string = String::from(input); let vec = string.drain(..).collect(); Lexer { input: vec, position: 0 } } pub fn position(&self) -> Position { self.position } pub fn next(&mut self) -> Option<char> { while let Some(result) = self.input.get(self.position).cloned() { self.position += 1; if result != ' ' { return Some(result) } } None } pub fn rollback(&mut self, position: Position) { self.position = position } }


バグのあるコメントについて

字句解析プログラムの作成中に、文字列を所定のベクトルに変換したかったため、コンパイラは文字列が範囲外であることを示すエラーをスローしました。 しかし、実際にはcollect



がイテレーターcollect



吸収するため、問題は発生しませんでした。







#rust-beginners



IRCチャンネルに行ったところ、言語開発者の一人がこれはバグだと言っていました。 そのため、突然問題が発生した場合は、チャンネルにアクセスして、お気軽にお問い合わせください。 非常にフレンドリーな人々がRust IRCチャンネルに座っており、彼らは常にあなたを助けようとします。







レクサーを使用するシナリオは次のとおりです。







  1. レクサーの位置を覚えておいてください。
  2. 文字を読み取り、ルールに従ってチェックします。
  3. 文字がルールで受け入れられない場合、初期状態にロールバックしてエラーを返します。


SDAの式のタイプを実装する時間です。







表現



式については、いくつかの単純化を行いました。







  1. 式のタイプを列挙にしましたが、実際のコンパイラーで行うことは強くお勧めします。 深刻な文法により、統一された式タイプのサポートは非​​常に複雑なプロセスになります。 特性と実装を使用する方が良い。
  2. 数値については、タイプf32



    を使用しました。 浮動小数点数が常に最良の選択とは限りませんが、目的にはf32



    で十分です。
  3. 不安定な機能#![feature(box_patterns)]



    。 この構文では、パターンマッチングはよりきれいに見えます。


eval



式を評価するための関数がすぐに追加されました。







数値の表現、算術演算子、否定をサポートします。 







 #[derive(Debug)] pub enum Expression { Operator { op: Box<Expression>, left: Box<Expression>, right: Box<Expression> }, Number(f32), Token(char), Negate(Box<Expression>) } impl Expression { pub fn eval(self) -> f32 { match self { Expression::Operator { op: box Expression::Token('+'), left, right } => left.eval() + right.eval(), Expression::Operator { op: box Expression::Token('-'), left, right } => left.eval() - right.eval(), Expression::Operator { op: box Expression::Token('/'), left, right } => left.eval() / right.eval(), Expression::Operator { op: box Expression::Token('*'), left, right } => left.eval() * right.eval(), Expression::Number(val) => val, Expression::Negate(exp) => -exp.eval(), token => panic!("Got token inside an expression {:?}", token) } } }


そして、トークンを提供する字句解析プログラムがあり、ある種の式があります。 パーサーを起動して、文字のシーケンスを式に変換します。







パーサー



パーサーの実装が主な関心事です。







すべての解析関数はレクサーを受け取り、レクサーの出力がルールに一致する場合はOption<Box<expression::Expression>>



： Some(expression)



を返し、そうでない場合はNone



を返します。







まず、補助機能が私たちの注意をそらさないように考慮してください。 実装をネタバレの下に隠し、リポジトリのリンクでそれらを見ることができます。







2つの関数を使用して、数値を解析し、端末を比較します（文字()+-.*



）：







数値と端末を解析するための関数 
 fn num(lexer: &mut lexer::Lexer) -> Option<Box<expression::Expression>> { let parser_pos = lexer.position(); let result = lexer .next() .map(|c| c as char) .and_then(|c| { if c.is_numeric() { Some(Box::new(expression::Expression::Number(c.to_string().parse::<f32>().unwrap()))) } else { lexer.rollback(parser_pos); None }}); result } fn token(token_char: char) -> impl FnMut(&mut lexer::Lexer) -> Option<Box<expression::Expression>> { move |ref mut lexer| { let parser_pos = lexer.position(); lexer .next() .map(|c| c as char).and_then(|c| if c == token_char { Some(Box::new(expression::Expression::Token(c))) } else { lexer.rollback(parser_pos); None }) } }


算術演算の式を作成するためのもう1つの関数。 この機能はいくつかのルールで使用されるため、別の関数に配置することをお勧めします。







算術演算を作成する関数 
 fn make_operator(left: Box<expression::Expression>, op: Box<expression::Expression>, right: Box<expression::Expression>) -> Option<Box<expression::Expression>> { Some(Box::new(expression::Expression::Operator{ op, left, right })) }


また、コードにはマクロdebug_parser!



。 パーサーのデバッグに使用されます（Captainに感謝）。







3つのマクロを定義します。







  1. rule!



    ルール関数を生成します。
  2. or!



    選択関数"|"



    を生成する ;
  3. and!



    フォロー関数","



    を生成します。


ルール！



ルールから始めましょう。 このマクロは、上記の署名に対応する指定された名前の関数を生成します。したがって、別のルールまたは関数で使用できます。







マクロは非常に単純です。関数を作成し、レクサーで呼び出されると、渡された関数の結果を返します（実際よりも複雑に聞こえます）。 







 macro_rules! rule { ($name: ident, $parse_func:expr) => { fn $name(lexer: &mut lexer::Lexer) -> Option<Box<expression::Expression>> { debug_parser!("Executing rule {}", stringify!($name)); $parse_func(lexer) } }; }


または！



次のマクロor!



。 ルールのリストを受け入れ、名前のない関数（ラムダ関数であり、クロージャーでもあります）を返します。パーサーで呼び出されると、渡されたルールを1つずつ呼び出し、呼び出しの最初の肯定的な結果があればそれを返します。 それ以外の場合は、 None



返します。 リターンクロージャの署名は、ルールの署名と同じです。







Rustのマクロに慣れていない場合は、マクロの本文でルールのリストがどのように展開されるかに注意を払う必要があります。 ルールごとに、式$(...),+



1回展開されます。 私たちの場合、これは関数呼び出しと結果のチェックを伴うブロックです。 その結果、渡された各ルールは1回呼び出されます。







クロージャーは、各ルールを呼び出す前にレクサーの位置を記憶し、ルールが実行されない場合は初期状態にロールバックすることに注意してください。 







 macro_rules! or { [$($parse_funcs: expr),+] => { |lexer: &mut lexer::Lexer| -> Option<Box<expression::Expression>> { $( let parser_pos = lexer.position(); let result = $parse_funcs(lexer); if result.is_some() { debug_parser!("Or statement rule {} accepted expression {:?}. Lexer state {:?}", stringify!($parse_funcs), result, lexer); return result } else { lexer.rollback(parser_pos); debug_parser!("Or statement rule {} didn't accept lexer input {:?}", stringify!($parse_funcs), lexer); } )+; debug_parser!("Or statement fails"); None } } }


そして！



そして最後に、マクロand!



。 その署名はまたはとわずかに異なりor!



。 ルールのリストと関数ハンドラーを受け入れます。 マクロは、渡された規則をレクサーで呼び出し、すべてが何らかの式を返すことをチェックするクロージャーを返します。 レクサーに対してすべてのルールが実行されると、結果のタプルが形成され、ハンドラー関数に渡されます。 少なくとも1つのルールが失敗した場合、または関数ハンドラーがNone



返した場合、レクサーは初期位置にロールバックします。 クロージャーの署名は、伝統的に、ルールと同じです。







ハンドラー関数は、使いやすさのために渡されます。 式のシーケンスを処理し、さらに処理するために必要な形式に変換します。 例として、角かっこを使用してルールを表示できます。これにより、角かっこが破棄され、角かっこ内の式が返されます（角かっこは、計算の順序を正しく分析するためにのみ必要です）。







ハンドラー関数は、マクロ呼び出しの可読性を向上させるために=>



演算子によって裏切られています。 







 macro_rules! and { [($($parse_funcs: expr),+) => $nandler_func: expr] => { |lexer: &mut lexer::Lexer| -> Option<Box<expression::Expression>> { let parser_pos = lexer.position(); let results = ($(match $parse_funcs(lexer) { Some(expression) => { debug_parser!("And statement rule {} accepted expression {:?}. Lexer state {:?}", stringify!($parse_funcs), expression, lexer); expression } _ => { debug_parser!("And statement rule {} didn't accept lexer input {:?}", stringify!($parse_funcs), lexer); lexer.rollback(parser_pos); return None } }), +); match std::ops::Fn::call(&$nandler_func, results) { expression @ Some(_) => { debug_parser!("And handling function successfully handled expression and returned {:?}", expression); expression } _ => { debug_parser!("And handling function failed to process expressions"); lexer.rollback(parser_pos); return None } } } }; }


ここで、 std::ops::Fn::call



を呼び出すことは支払う価値がありstd::ops::Fn::call



。 これは不安定な機能ですが、それがなければ、タプルを渡す必要があり、著しく便利ではありません。







これで、マクロを使用して文法を表現できるようになりました。 記事の冒頭にあったコードは次のとおりです。 







 // expr = sum // sum = mul "+" sum | mul "-" sum | mul // mul = atom "*" mul | atom "/" mul | atom // atom = "(", expr , ")" | number | neg; // neg = "-" atom rule!(expr, sum); rule!(sum, or![ and![(mul, token('+'), sum) => make_operator], and![(mul, token('-'), sum) => make_operator], mul ]); rule!(mul, or![ and![(atom, token('*'), mul) => make_operator], and![(atom, token('/'), mul) => make_operator], atom ]); rule!(atom, or![ and![(token('('), expr, token(')')) => |_lbrace, stat, _rbrace| Some(stat)], num, neg ]); rule!(neg, and![(token('-'), atom) => |_, number| Some(Box::new(expression::Expression::Negate(number)))]);


結果はかなり良く見えます。 パーサーのみを考慮する場合、65行のコードに投資しました。 これで、テストコードを記述して実行することができます（はい、テストコードを書くことは特に好きではありません）。 







 fn main() { let result0 = expr(&mut lexer::Lexer::new("1 + 2")); let result1 = expr(&mut lexer::Lexer::new("(1 + -2)")); let result2 = expr(&mut lexer::Lexer::new("(1 + 2) * 3")); let result3 = expr(&mut lexer::Lexer::new("1 * (2 - 3)")); let result4 = expr(&mut lexer::Lexer::new("1 * -2 + 3 * 4")); let result5 = expr(&mut lexer::Lexer::new("(1 * 2 + (-3 + -4))")); println!("0. Result {:?}", result0); println!("1. Result {:?}", result1); println!("2. Result {:?}", result2); println!("3. Result {:?}", result3); println!("4. Result {:?}", result4); println!("5. Result {:?}", result5); assert_eq!(result0.unwrap().eval(), 1f32 + 2f32); assert_eq!(result1.unwrap().eval(), 1f32 - 2f32); assert_eq!(result2.unwrap().eval(), (1f32 + 2f32) * 3f32); assert_eq!(result3.unwrap().eval(), 1f32 * (2f32 - 3f32)); assert_eq!(result4.unwrap().eval(), 1f32 * -2f32 + 3f32 * 4f32); assert_eq!(result5.unwrap().eval(), 1f32 * 2f32 + (-3f32 + -4f32)); }


結論： 







 0. Result Some(Operator { op: Token('+'), left: Number(1), right: Number(2) }) 1. Result Some(Operator { op: Token('+'), left: Number(1), right: Negate(Number(2)) }) 2. Result Some(Operator { op: Token('*'), left: Operator { op: Token('+'), left: Number(1), right: Number(2) }, right: Number(3) }) 3. Result Some(Operator { op: Token('*'), left: Number(1), right: Operator { op: Token('-'), left: Number(2), right: Number(3) } }) 4. Result Some(Operator { op: Token('+'), left: Operator { op: Token('*'), left: Number(1), right: Negate(Number(2)) }, right: Operator { op: Token('*'), left: Number(3), right: Number(4) } }) 5. Result Some(Operator { op: Token('+'), left: Operator { op: Token('*'), left: Number(1), right: Number(2) }, right: Operator { op: Token('+'), left: Negate(Number(3)), right: Negate(Number(4)) } })


ポストスクリプト



Rustのマクロは良い印象を残します。 時々、真実にはいくつかの基本的なデザインが欠けているようです。 たとえば、パラメーターを挿入せずにブロックをN回展開します。Nは引数の数です。







しかし、開発者は必要な機能をすぐに追加するので、希望があります（すぐに、たとえば、HKTおよび非語彙スコープを追加します）。







すべてのコードはGitHubで表示できます。







More articles:


All Articles