Rust のギモン その 2
前回、Point3D と Vector3D を実装するにあたって演算子オーバーロードを使用したのだけれど、std::ops::Add 等の trait で実装すべきメソッドは
fn add(self, rhs: Rhs) -> Self::Output
とあるように self も rhs も move してしまう。なので、そのまま Vector3D に対して実装すると、
let a: = Vector3D::new(1.0, 2.0, 3.0); let b: = Vector3D::new(4.0, 5.0, 6.0); let c = a + b;
とした場合に a と b は move out してしまい、以降使用できなくなる。実際のところ、この計算では a, b のどちらも変更しないから、後でまた a, b を使っても問題ないし、使いたくなることもあり得る。なので代わりに &Vector3D に対して Add trait を実装した。
impl Add<&Vector3D> for &Vector3D { type Output = Vector3D; fn add(self, v: &Vector3D) -> Self::Output { Vector3D::new(self.x + v.x, self.y + v.y, self.z + v.z) } }
これなら
let a: = Vector3D::new(1.0, 2.0, 3.0); let b: = Vector3D::new(4.0, 5.0, 6.0); let c = &a + &b;
とすることにより c を得てからも a, b 双方とも利用できる。ただ、これだと毎回 & を付けなければならないのが面倒だし、何より 3 つ以上 add したいなら
&(&a + &b) + &c;
のように書かなければならず、可読性が著しく低下する。これを回避しようとすると、型 T に対して
- &T + &T (使用例: &a + &b)
- &T + T (使用例: &a + (&b + &c))
- T + &T (使用例: (&a + &b) + &c)
- T + T (使用例: (&a + &b) + (&c + &d))
の 4 つの add を実装しなければならない。これはこれで面倒な上、誤って move out させてしまう可能性も生じる。
何か良い方法はないのだろうか。Copy を derive する以外で。
Vector3D/Point3D
相変わらず作りたいものはないのだけれど、少し前に "The Ray Tracer Challenge: A Test-Driven Guide to Your First 3D Renderer" という本を買った。
The Ray Tracer Challenge: A Test-Driven Guide to Your First 3D Renderer (Pragmatic Bookshelf)
- 作者: Jamis Buck
- 出版社/メーカー: Pragmatic Bookshelf
- 発売日: 2019/03/08
- メディア: ペーパーバック
- この商品を含むブログを見る
この本はテストケースのみを提示して、特定の言語を対象とせずにシンプルな Raytracer を実装することを目的としている。Rust を使ってこの本を読んでいけば良い経験になる... といいなあ。
とにかくやってみよう。
リポジトリはここ github.com
Tuples, Points, and Vectors
Chapter1 は Point と Vector の実装。本では Point と Vector を tuple を使った 4 つ組みで表現しているが、x, y, z の添字でアクセスしたいこと、Point と Vector の区別ができるなら w 成分は不要なことから、struct で表現する。
各成分には float として f32 を用いる。使用者が f32 と f64 の好きな方を使えるようにしたいけれど、あまり良い方法が思いつかない。
type Float = f32;
とでもしておいた方が良かったか。
浮動小数点関連は誤差はつきもののため、誤差を考慮した比較用関数も用意しておく。
const EPSILON: f32 = 0.0001; fn approx_eq(a: f32, b: f32) -> bool { (a - b).abs() < EPSILON }
また、Vector という名前にすると Vec と間違えそうなので、それぞれ Point3D, Vector3D という名前にした。
Point3D
struct の定義は非常に簡単。
#[derive(Debug, Clone)] pub struct Point3D { pub x: f32, pub y: f32, pub z: f32, }
x, y, z の各メンバに直接アクセスしたいので、pub を付けて公開している。
Vector3D
基本的には Point3D と変わらない。
#[derive(Debug, Clone)] pub struct Vector3D { pub x: f32, pub y: f32, pub z: f32, }
こちらも x, y, z の各メンバに直接アクセスしたいので、pub を付けて公開している。
Operation
Point3D と Vector3D に関する演算を定義する。実装自体に難しいところはないから、ソースを見るだけで何をしているのか分かるはず。
Rust のギモン その 1
Rust を使ってまだ日が浅いということもあって、ある処理を Rust でどう書くのが普通なのかよくわからないことが多々ある。ここに記しておけば誰か親切な人が教えてくれるかもしれない。
なお、「その 1」とあるけれど、「その 2」以降があるかは未定。
疑問
Linked List を考える。ここでは簡単のため、以下のように Node を定義する。
struct Node { value: i32, next: Option<Box<Node>>, }
この Node を連ねた LinkedList を用意する。
struct LinkedList { head: Option<Box<Node>>, }
LinkedList に新しく Node を追加する処理を書きたい。その際、追加する value が既に含まれている場合には何もせず、value が存在しなかった時のみ最後尾に Node を追加する。
そのため、先頭から Node を順に見て、value が見つかったらその Node への reference を、見つからなかったら新しい Node の挿入場所を返す LinkedList のメソッド locate_mut() を作る。
fn locate_mut(&mut self, value: i32) -> &mut Option<Box<Node>> { let mut n = &mut self.head; loop { match { n } { Some(ref mut node) if node.value != value => n = &mut node.next, other @ _ => return other, } } }
そして、この locate_mut() を利用して実際の挿入を行う add_node() を実装する。
fn add_node(&mut self, value: i32) { match self.locate_mut(value) { Some(_) => {} p @ None => { *p = Some(Box::new(Node::new(value))); } } }
で、これをコンパイルすると怒られる。
warning[E0505]: cannot move out of `_` because it is borrowed
--> ./hoge.rs:31:17
|
25 | fn locate_mut(&mut self, value: i32) -> &mut Option<Box<Node>> {
| - let's call the lifetime of this reference `'1`
...
30 | Some(ref mut node) if node.value != value => n = &mut node.
| ------------ borrow of value occurs here
31 | other @ _ => return other,
| ^^^^^^^^^ ----- returning this value requires tha
| |
| move out of value occurs here
|
= warning: this error has been downgraded to a warning for backwards compatib
= warning: this represents potential undefined behavior in your code and this
warning のメッセージを読む限りでは Some(ref mut node) で node として borrow した値を other @ _ => return other, で other として move out しているのが問題っぽい。
Some の arm で borrow すると _ の arm に入っても borrow しっぱなしなのかとも考えたのだけれど、どうも違うよう。というのも、同一の処理で Some(ref node) だと怒られないから。mut が付くと問題になるみたい。
また、guard の if node.value != value がなくても warning は出ない。
mut で guard がある時に問題になるということは guard の中で値を変えられる可能性があるのが原因なのだろうか。だとするとちょっと warning のメッセージからは読み取れない。
もちろん他の方法で実装すれば良いし、何だかんだいってそれが一番楽な解決法だというものわかる。ただ、素直に実装しただけのつもりなのに良く分からない怒られ方をしたのが不思議で、何故なのかを知っておきたい。
Compiler/Virtual Machine Interpreter
Compiler/Virtual Machine Interpreter
タスク概要
Code Generator で得られたアセンブリ出力を読み込み、Virtual Machine 用バイトコードに変換、実行する。
実装
Virtual Machine の実装はタスクのページにある "A simple example virtual machine" をそのまま Rust に持ってくるだけで何の問題もなく動いてしまう。
結果、"Virtual Machine Interpreter" というタスク名のくせに最も実装に時間がかかるのはバイトコードを生成するアセンブラの部分になってしまった。とはいえ、疑似命令やラベルすら存在しないこともあって、アセンブラ作成タスクとして見た場合にも特筆することがない。基本的に一行ずつ読み込んで一命令ずつ出力していくだけ。
ところで、このタスクにはバイトコードに関する仕様がない。タスク内で完結する表現であるため、ある程度好きに決めてしまっても影響を及ぼさないからだろうか。守るべきは
- オペコードは 1 バイト
- 各オペランドは 4 バイト
くらい。分岐命令におけるジャンプ先アドレスは "A simple example virtual machine" を見ると PC 相対になっているが、それに従わずに絶対アドレスでも Virtual Machine の側の仕様を合わせさえすれば普通に動くはず。
余談
実際のところ、バイトコードの仕様を決めた上で Code Generator タスク の出力をバイトコードにしても良かった気がする。そうすればこのタスクは純粋に Virtual Machine の実装になったのだけれど。
そうしなかったのは、バイトコードを出力させるようにするとエンディアンの問題などが出てしまうからかもしれない。
何にしろ、これで一連の Compiler タスクは全て実装したことになる。実装した言語は足りない機能がたくさんあって実用には耐えないが、これを足がかりにしていくのも一つの方法だろう。次にやるなら
- 関数
- 整数以外の変数
あたりの実装になるのかな。または下まわりを自前 VM から LLVM にしてみるとか。 今のところどちらもやるつもりはないが。
Compiler/Code Generator
タスク概要
構文解析で得られた Abstract Syntax Tree(AST) から次のタスクで作成する Virtual Machine 用アセンブリを出力する。
入力は Compiler/Syntax Analyzer での出力形式に基づいたテキスト。
実装
意味解析や最適化等は行わないため、基本的には Compiler/AST Interpreter でやったことと変わらない。違いはその場で計算を実行する代わりにアセンブリを出力するくらい。
なので、以降は Code Generation において注意すべき点を挙げるにとどめる。
while, if の扱い
while 文の制御は大まかに以下の図のようになる。
まず cond を評価し、それが True(0 以外) の間は body を実行し続ける。よって、出力すべき code は
- cond の code
- jz body の次
- body の code
- jmp cond へ戻る
という順に code が並ぶ。ここには 2 種類の分岐命令があり、青で示したものは backward 、赤は forward 方向へ飛ぶ。ここで問題になるのは赤の forward 方向の jz 命令で、jz の出力時点では body のサイズが不明なために jump 先アドレスがわからない。
なので、一時的な code を出力しておき、bodyの code 出力後、つまり飛び先のアドレスが確定してから置き換える。
if 文も同様。ただしこちらの方が少し複雑になる。
cond が偽であれば if 節をジャンプする。真であれば、if 節実行後に else 節があればそれをジャンプする。よって置き換え対象が最大 2 つ存在する。
変数、文字列の扱い
定数に関してはスタックマシンということもあって push するだけなので楽。一方で変数と文字列はもう少し考えることがある。
今回、変数はグローバル変数しか存在しない。また、その値は常に i32 になる。よって何種類の変数が使われているかだけで必要なメモリを算出できる。実現には code generation 時に出現した変数を数えておくだけで良い。
CodeGenerator の data_addr が現れた変数をおぼえておくためのもので、変数名 -> アドレス の HashMap になっている。
pub struct CodeGenerator<'a> { data_addr: HashMap<&'a str, u32>, string_pool: Vec<&'a str>, pc: u32, instructions: Vec<Instruction>, }
アドレスは変数の出現順に 0, 1, 2, ... としているため、新しい変数に出会う度にその時点での data_addr のサイズを用いる。処理内容は以下の通りで、None の Arm 部分が新規の変数に出会った時の処理になる。
fn intern(&mut self, name: &'a str) -> u32 { match self.data_addr.get(name) { Some(addr) => *addr, None => { let addr = self.data_addr.len() as u32; self.data_addr.insert(name, addr); addr } } }
文字列は出現順に string_pool へ push する。今回は Vec として実装したが、こちらも HashMap にして同一文字列が現れた場合には以前のアドレスを参照するようにした方が良かったかもしれない。実装対象の言語では String は必ず immutable になるから、それで問題が生じることもない。
その他
特に注意すべき点もないのでソースを見ればわかるはず。
余談
出力するアセンブリの仕様がちゃんと書かれていなくて、主に分岐(ジャンプ)命令で少し難儀した。アセンブリだから当然ターゲットとなる virtual machine の仕様と密接な関連があるのだけれど、virtual machine の仕様がソース以外に見当たらない。
問題になったのは分岐命令で、
- 命令フェッチ
- pc <- pc + 1
- (jz の場合条件判定)
- jump 先アドレス計算
- (ジャンプ しなかった場合)pc <- pc + 4
という順序で処理を行う。よって PC 相対で jump 先アドレスを表現する際には pc が 1 増えた状態での相対アドレスになる。オペランドに含まれるアドレス部の 4 bytes はこの時点ではまだ pc に加えられていないことに注意。
Compiler/AST Interpreter
タスク概要
構文解析で得られた Abstract Syntax Tree(AST) のインタプリタを作る。
入力は Compiler/Syntax Analyzer での出力形式に基づいたテキスト。
実装
基本的には AST をトラバースしながら各ノードを評価していく。評価することで得られる値は
- String
- Integer
- なし
の 3 種類がある。なので、return value 用に
pub enum Value<'a> { Integer(i32), String(&'a str), }
という enum を用意した。String の値は AST が所有しているため、reference を用いる。また、これだけだと return value なしの場合が扱えないため、Option にする。
pub fn interpret(node: &'a ASTNode, writer: &mut Write) -> Result<Option<Value<'a>>>
enum Value に None を加えても良かったかもしれない。
変数
インタプリタに変数名と値をむすびつけるための HashMap を用意する。今回実装している言語はグローバル変数しか持たないため、これだけで ok。
pub struct ASTInterpreter<'a> { global: HashMap<&'a str, Value<'a>>, }
リーフの評価
AST のリーフ(葉) になるのは終端記号である String, Identifier, Integer。String と Integer はそのままの値が評価結果になる。
NodeKind::String(value) => Ok(Some(Value::String(value))), NodeKind::Integer(value) => Ok(Some(Value::Integer(*value))),
一方で Identifier は変数へのアクセスになるため、前述の HashMap へのアクセスを行う。
fn interpret_identifier(&mut self, identifier: &'a str) -> Result<Option<Value<'a>>> { Ok(Some(self.global[identifier])) }
なお、変数への代入では左辺の Identifier を評価しないことに注意。
中間ノードの評価
2 項演算
add や equal などが該当する。処理は非常に単純で、両辺を評価してから対応する演算を適用するだけ。ソース内では interpret_binary_op() で行っている。
ところで、2 項演算の中には equal 等の関係演算が含まれる。一方で今回実装している言語に boolean を直接表すデータ型というものは存在しない。rosetta code のサイトではちゃんとした言語の仕様が見つからず、代わりに "C 言語と Python による実装を参照実装として考えていいよ"。とある。それによると、C 言語同様 0 を false とし、それ以外を true と見なすようだ。
よって false 時には 0 を true 時には 1 を評価結果とした。
単項演算
2 項演算とほとんど変わらない。違いは子ノードが片方しかない点のみ。interpret_unary_op() を参照。
代入
Identifier の評価のところでも書いたけれど、代入先になる左辺の Identifier は評価せず、右辺のみを評価し、評価結果を global の HashMap に Identifer 名をキーとして記憶させる。
fn interpret_assign( &mut self, node: &'a ASTNode, writer: &mut Write, ) -> Result<Option<Value<'a>>> { let variable = node.lhs().unwrap(); let value = self.interpret_body(node.rhs().unwrap(), writer)?.unwrap(); match variable.kind() { NodeKind::Identifier(ref identifier) => { self.global.insert(identifier, value); Ok(None) } _ => Err(CompileError::new( ErrorKind::InterpretationError, "Identifier is expected.", )), } }
if
条件文にあたる paren_expr を評価し、その結果により実行対象が変わる。else 節は存在しない場合もある。
fn interpret_if(&mut self, node: &'a ASTNode, writer: &mut Write) -> Result<Option<Value<'a>>> { let condition = self.interpret_body(node.lhs().unwrap(), writer)?.unwrap(); let statement_node = node.rhs().unwrap(); if condition != Value::Integer(0) { self.interpret_body(statement_node.lhs().unwrap(), writer)?; } else { if let Some(else_clause) = statement_node.rhs() { self.interpret_body(else_clause, writer)?; } } Ok(None) }
while
条件の評価と本体の評価を繰り返す。条件の評価結果が 0 になったらループ終了。
fn interpret_while( &mut self, node: &'a ASTNode, writer: &mut Write, ) -> Result<Option<Value<'a>>> { let condition = node.lhs().unwrap(); let statement = node.rhs().unwrap(); while self.interpret_body(condition, writer)? != Some(Value::Integer(0)) { self.interpret_body(statement, writer)?; } Ok(None) }
その他
特に注意すべき点もないのでソースを見ればわかるはず。
余談
AST Interpreter というタスク名だったから interpret() という関数名にしたけど、個人的には eval の方がしっくりくる。
Compiler/Syntax Analysis
タスク概要
シンプルなプログラミング言語用の Syntax Analyzer を作る。
入力は Compiler/Lexical Analyzer での出力形式に基づいたトークン列のテキスト。
実装
yacc 使おうぜ、yacc。と言いたくなる気も少しあるけど、真面目に実装する。そもそも C 言語じゃないしね。
Rosetta Code のページには pseudo code があって、それでは再帰下降パーザと演算子優先順位パーザの組み合わせが使われていたので、それに倣うことにする。Rosetta Code は同じ問題を色々な言語で実装して比較できるようにするのも目的だし、あえて本流に逆らう必要もない。
エラー
Lexical Analyzer のときに用意したエラーを拡張する。具体的には ErrorKind に SyntaxError を追加する。
#[derive(Debug)] pub enum ErrorKind { LexicalAnalyzerError, }
本来ならタスクの独立性を高めるためにこのタスク専用にコードを用意すべきなのだろうが、面倒なのでやめておく。Token に関しても同様。
これにともない、Cargo.toml の [dependency] に lexical_anzlyer を追加。
[dependencies]
lexical_analyzer = {path="../lexical_analyzer"}
pub struct ASTNode { pub(crate) kind: NodeKind, pub(crate) lhs: Option<Box<ASTNode>>, pub(crate) rhs: Option<Box<ASTNode>>, }
メンバを見ればわかると思うが、ごく普通の二分木。lhs と rsh はそれぞれ Left Hand Side, Right Hand Side を意味しているが、left, right の方がわかりやすかったかもしれない。
NodeKind は task のページで定義されているノードの種類をそのまま持ってきた。
pub enum NodeKind { Identifier(String), String(String), Integer(i32), Sequence, If, Prtc, Prts, Prti, While, Assign, Negate, Not, Multiply, Divide, Mod, Add, Subtract, Less, LessEqual, Greater, GreaterEqual, Equal, NotEqual, And, Or, None, }
唯一 "None" を加えたが、これは演算子優先順位構文解析でのみ使用する。
解析部
今回のタスクでは与えられたトークン列に対して一度に解析を行い、AST を出力することから、SyntaxAnalyzer::parse() のみを pub にして構造体としての SyntaxAnalyzer は見えないようにする。
SyntaxAnalyzer::parse() の signature は
pub fn parse(mut token_iter: IntoIter<Token>) -> Result<ASTNode>
で、入力としてのトークン列は内部で Iterator の形でアクセスする。本来はエラーを起こす可能性のある Lexical Analyzer からトークンを得るため Iterator はふさわしくないが、このタスクでは Lexical Analyzer による字句解析は済んで問題がなかったトークン列のみを扱うため、この形で入力を受けるようにした。
結果として SyntaxAnalyzer は
pub struct SyntaxAnalyzer { token_iter: IntoIter<Token>, next_token: Token, }
のようになった。next_token に関しては次項を参照。
トークン先読み
前述のように、このタスクでは全てのトークン列が生成済みの状態で構文解析を行うため、解析時には全トークンが既知になっている。よってこのようにする意味はあまりないのだけれど、 1 トークン先読みを行う。
SyntaxAnalyzer の next_token はこの先読みをしたトークン。先読みの処理は以下の通り。
fn read_token(&mut self) -> Result<Token> { let next_token = self.token_iter.next(); match next_token { Some(t) => Ok(std::mem::replace(&mut self.next_token, t)), None => Err(CompileError::new(ErrorKind::SyntaxError, "unexpected EOF")), } }
Lexical Analyzer での一文字先読みと大体似た感じだが、大きな違いとしてトークン先読み時に replace で前に先読みしていたトークンを返すようにしている。これは Lexical Analyze では Copy を実装した char のみを扱っていたため不要だったことによる。
Syntax Analyer で扱うのはトークン列で、その店には Identifier のように String の値を持っている場合がある。そして、その値は AST でも使用する。そのため、一旦 Syntax Analyzer から ownership を手放して ASTNode に渡したい。
というわけで、トークンを消費時に read_token() を呼ぶと、先読みをすると同時に replace で消費したトークンの ownership を手放して return している。
再帰降下構文解析
task の文法を見ると、左再帰がないことが簡単に確認できることから、再帰降下構文解析による解析が可能だとわかる。
再帰降下構文解析では生成規則にのっとってコードを書き下ろすだけで良いため、手書きでもそんなに苦労せずに書ける。一例として stmt から生成される if 文
'if' paren_expr stmt ['else' stmt]
の解析部の概形を示すと、
// 'if' if *self.next_token.kind() != TokenKind::KeywordIf { return Err(CompileError::new( ErrorKind::ParseError, "\"if\" is expected.", )); } self.read_token()?; // paren_expr let condition = self.parse_paren_expr()?; // stmt let if_clause = Some(Box::new(self.parse_stmt()?)); // 'else' let else_clause = if *self.next_token.kind() == TokenKind::KeywordElse { self.read_token()?; // stmt Some(Box::new(self.parse_stmt()?)) } else { None }; }
というように生成規則に則って、順に解析をしているだけとわかる。
後はこれに AST を構築する部分を付け加えていく。そのためには各文でどのような部分木を構築すべきかを理解しておく必要がある。二分木ということもあってか タスクのページでは S 式で書かれているため、Lisp 等を知らないと少し読みにくいかもしれない。というわけで図示すると、
となる。解析時にこの形の部分木を構築する。よって if 文を解析する parse_if_stmt() は以下の通り。
fn parse_if_stmt(&mut self) -> Result<ASTNode> { if *self.next_token.kind() != TokenKind::KeywordIf { return Err(CompileError::new( ErrorKind::ParseError, "\"if\" is expected.", )); } self.read_token()?; let condition = self.parse_paren_expr()?; let mut node = ASTNode { kind: NodeKind::If, lhs: Some(Box::new(condition)), rhs: None, }; let if_clause = Some(Box::new(self.parse_stmt()?)); let else_clause = if *self.next_token.kind() == TokenKind::KeywordElse { self.read_token()?; Some(Box::new(self.parse_stmt()?)) } else { None }; node.rhs = Some(Box::new(ASTNode { kind: NodeKind::If, lhs: if_clause, rhs: else_clause, })); Ok(node) }
他も似た感じで解析を行っている。特殊なことはやっていないので難しくはないけれど、print のみは見た目と構築される AST の間に少し開きがある。例として
print("abc", 42, "def");
を考える。このとき、String である "abc" と "def" に対しては Prts のノードを作り、42 に対しては Prti ノードを作る。よって、print トークンを見た時点ではどのような部分木を構築するかを決められず、prt_list の解析時に構築することになる。
そして、先述の print を解析して得られるべき AST は
である。つまりは print を解析しているというよりも ptr_list を解析している感覚になる。
実際の処理は
fn parse_prt_list(&mut self) -> Result<ASTNode> { let node = match self.next_token.kind() { TokenKind::String(_) => ASTNode { kind: NodeKind::Prts, lhs: Some(Box::new(self.make_string_node()?)), rhs: None, }, _ => ASTNode { kind: NodeKind::Prti, lhs: Some(Box::new(self.parse_expr()?)), rhs: None, }, }; let mut lhs = ASTNode { kind: NodeKind::Sequence, lhs: None, rhs: Some(Box::new(node)), }; while *self.next_token.kind() == TokenKind::Comma { self.read_token()?; let node = match self.next_token.kind() { TokenKind::String(_) => ASTNode { kind: NodeKind::Prts, lhs: Some(Box::new(self.make_string_node()?)), rhs: None, }, _ => ASTNode { kind: NodeKind::Prti, lhs: Some(Box::new(self.parse_expr()?)), rhs: None, }, }; lhs = ASTNode { kind: NodeKind::Sequence, lhs: Some(Box::new(lhs)), rhs: Some(Box::new(node)), }; } Ok(lhs) }
となり、先読みしたトークンを基に Prts と Prti のどちらのノードを作るかを決めている。
他の非終端記号も同様の処理をしているだけなので、ソースを参照。
終端記号の扱いにおいて注意すべきは Identifier、もしくは String トークン。両者とも String 型の値を持っており、AST 構築時にその値をトークンから ASTNode に move させる必要がある。
Identfier の処理を以下に示す。
let Token { kind, .. } = self.read_token()?; match kind { TokenKind::Identifier(identifier) => Ok(ASTNode { kind: NodeKind::Identifier(identifier), lhs: None, rhs: None, }),
read_token() で SyntexAnalyzer に現在のトークン(Identifier トークン)の ownership を手放させてから ASTNode に move している。同様の処理は String トークンでも行っており、そちらは make_string_node() を参照。
演算子優先順位構文解析
expr の解析では演算子優先順位構文解析を使う。これはその名前の通り各演算子が持つ優先順位に基づいて解析を行う。そのため、事前に優先順位の値を決めておく。
解析対象となるのは expr, and_expr, equality_expr, relational_expr, additional_expr および multiplication_expr。そして後に書いたものほど優先順位が高い。よって、各 expr で用いる演算子に優先順位を割り当てると、
// or const OR: Operator = Operator { kind: NodeKind::Or, right_associative: false, precedence: 10, }; // and const AND: Operator = Operator { kind: NodeKind::And, right_associative: false, precedence: 20, }; // equality const EQUAL: Operator = Operator { kind: NodeKind::Equal, right_associative: false, precedence: 30, }; const NOT_EQUAL: Operator = Operator { kind: NodeKind::NotEqual, right_associative: false, precedence: 30, }; // relational const LESS: Operator = Operator { kind: NodeKind::Less, right_associative: false, precedence: 40, }; const LESS_EQUAL: Operator = Operator { kind: NodeKind::LessEqual, right_associative: false, precedence: 40, }; const GREATER: Operator = Operator { kind: NodeKind::Greater, right_associative: false, precedence: 40, }; const GREATER_EQUAL: Operator = Operator { kind: NodeKind::GreaterEqual, right_associative: false, precedence: 40, }; // addition const ADD: Operator = Operator { kind: NodeKind::Add, right_associative: false, precedence: 50, }; const SUBTRACT: Operator = Operator { kind: NodeKind::Subtract, right_associative: false, precedence: 50, }; // multiplication const MULTIPLY: Operator = Operator { kind: NodeKind::Multiply, right_associative: false, precedence: 60, }; const DIVIDE: Operator = Operator { kind: NodeKind::Divide, right_associative: false, precedence: 60, }; const MOD: Operator = Operator { kind: NodeKind::Mod, right_associative: false, precedence: 60, }; // sentinel として使うため、 precedence -1 const NOT_OPERATOR: Operator = Operator { kind: NodeKind::None, right_associative: false, precedence: -1, };
となる。優先順位を示す値は precedence で、大きい値になるほど優先順位が高くなる。優先順位の値が 10 刻みであることに深い意味はない。ただ、なんとなく。
right_associative は演算子の結合規則が右結合であることを示すためのものだが、今回対象とする言語において全ての演算子は左結合であるため何の意味も持たない。
/// 演算子優先順位パーザで式を解析する fn parse_expr(&mut self) -> Result<ASTNode> { let lhs = self.parse_primary()?; self.parse_expr_body(lhs, 0) } fn parse_expr_body(&mut self, node: ASTNode, min_precedence: i32) -> Result<ASTNode> { let mut lhs = node; let mut next_op = operator(self.next_token.kind()); while next_op.precedence >= min_precedence { let op = next_op; self.read_token()?; let mut rhs = self.parse_primary()?; next_op = operator(self.next_token.kind()); while next_op.precedence > op.precedence || ((next_op.precedence == op.precedence) && next_op.right_associative) { rhs = self.parse_expr_body(rhs, next_op.precedence)?; next_op = operator(self.next_token.kind()); } lhs = ASTNode { kind: op.kind.clone(), lhs: Some(Box::new(lhs)), rhs: Some(Box::new(rhs)), }; } Ok(lhs) }
parse_expr_body() が解析本体。
処理は二重ループを基本としている。まず、外側のループのみを考える。
let mut lhs = node; let mut next_op = operator(self.next_token.kind()); while next_op.precedence >= min_precedence { let op = next_op; self.read_token()?; let mut rhs = self.parse_primary()?; next_op = operator(self.next_token.kind()); lhs = ASTNode { kind: op.kind.clone(), lhs: Some(Box::new(lhs)), rhs: Some(Box::new(rhs)), }; }
このループでは以下のような木を構築する。
一方、内側のループ
while next_op.precedence > op.precedence || ((next_op.precedence == op.precedence) && next_op.right_associative) { rhs = self.parse_expr_body(rhs, next_op.precedence)?; next_op = operator(self.next_token.kind()); }
では逆に以下のような木を構築する。
つまり、外側のループで左結合を、内側のループで右結合を実現している。とはいえ、それだと右結合の中でさらに左結合といったケースを扱えない。それを処理しているのが、内側のループにある parse_expr_body() の再帰呼出しになっている。
余談
ここで生成した AST が続く Compiler/AST interpreter と Compiler/Code Generator の中心的役割を果たす...はず。
