インタープリター
説明
ある問題が非常に頻繁に発生し、それを解決するために長く反復的な手順が必要な場合、 その問題インスタンスは単純な言語で表現でき、インタープリターオブジェクトが この単純な言語で書かれた文を解釈することで解決できるかもしれません。
基本的に、どのような種類の問題についても、次のものを定義します。
- ドメイン固有言語
- この言語の文法
- 問題インスタンスを解決するインタープリター
動機
私たちの目標は、単純な数式を後置記法の式（または
逆ポーランド記法）
に変換することです。単純化のため、式は 10 個の数字 0, …, 9 と 2 つの
演算 +, - で構成されます。たとえば、式 2 + 4 は
2 4 + に変換されます。
この問題の文脈自由文法
私たちのタスクは、中置記法の式を後置記法の式に変換することです。0, …, 9, +,
および - 上の中置記法の式の集合について、文脈自由文法を定義しましょう。ここで、
- 終端記号:
0,...,9,+,- - 非終端記号:
exp,term - 開始記号は
exp - そして以下が生成規則です
exp -> exp + term
exp -> exp - term
exp -> term
term -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
注: この文法は、これを使って何を行うかに応じてさらに変換する必要があります。 たとえば、左再帰を取り除く必要があるかもしれません。詳細については、 Compilers: Principles,Techniques, and Tools （別名 Dragon Book）を参照してください。
解決策
単純に再帰下降パーサーを実装します。簡単にするため、式が構文的に誤っている場合
（たとえば 2-34 や 2+5- は文法定義に従うと誤りです）、コードはパニックします。
pub struct Interpreter<'a> {
it: std::str::Chars<'a>,
}
impl<'a> Interpreter<'a> {
pub fn new(infix: &'a str) -> Self {
Self { it: infix.chars() }
}
fn next_char(&mut self) -> Option<char> {
self.it.next()
}
pub fn interpret(&mut self, out: &mut String) {
self.term(out);
while let Some(op) = self.next_char() {
if op == '+' || op == '-' {
self.term(out);
out.push(op);
} else {
panic!("Unexpected symbol '{op}'");
}
}
}
fn term(&mut self, out: &mut String) {
match self.next_char() {
Some(ch) if ch.is_digit(10) => out.push(ch),
Some(ch) => panic!("Unexpected symbol '{ch}'"),
None => panic!("Unexpected end of string"),
}
}
}
pub fn main() {
let mut intr = Interpreter::new("2+3");
let mut postfix = String::new();
intr.interpret(&mut postfix);
assert_eq!(postfix, "23+");
intr = Interpreter::new("1-2+3-4");
postfix.clear();
intr.interpret(&mut postfix);
assert_eq!(postfix, "12-3+4-");
}議論
インタープリターデザインパターンは、形式言語の文法を設計し、それらの文法のパーサーを
実装することに関するものだという誤解があるかもしれません。実際には、このパターンは
問題インスタンスをより具体的な方法で表現し、それらの問題インスタンスを解決する
関数/クラス/構造体を実装することに関するものです。Rust 言語には macro_rules! があり、
これにより特殊な構文と、その構文をソースコードへ展開する方法のルールを定義できます。
次の例では、n 次元ベクトルの
ユークリッド距離を計算する
単純な macro_rules! を作成します。norm!(x,1,2) と書くことは、x,1,2 を
Vec に詰めて長さを計算する関数を呼び出すよりも、表現しやすく効率的かもしれません。
macro_rules! norm {
($($element:expr),*) => {
{
let mut n = 0.0;
$(
n += ($element as f64)*($element as f64);
)*
n.sqrt()
}
};
}
fn main() {
let x = -3f64;
let y = 4f64;
assert_eq!(3f64, norm!(x));
assert_eq!(5f64, norm!(x, y));
assert_eq!(0f64, norm!(0, 0, 0));
assert_eq!(1f64, norm!(0.5, -0.5, 0.5, -0.5));
}