解释器

说明

如果一个问题经常出现并且需要很多且重复的步骤来解决，那么问题应该被抽象为一个简单的语言并且一个解释器对象能通过解释这种语言的句子来解决问题。

基本上，对于我们定义的任何类型的问题有如下三点：

出发点

我们的目标是转换简单的数学表达式为后缀表达式。（逆波兰表达式）。 为简单起见，表达式包含十个数字0,…9和+,-两种操作。举例来说，2 + 4被翻译为2 4 +。

问题的上下文无关文法

我们的任务是将中缀表达式转为后缀表达式。我们对包含0,…9和+,-的中缀表达式定义上下文无关文法包括：

  • 终结符号: 0, …, 9, +, -
  • 非终结符号: exp, term
  • 开始符号 exp
  • 还有下述的生成规则
  1. exp -> exp + term
  2. exp -> exp - term
  3. exp -> term
  4. term -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

这个语法应该根据我们要用它做什么来进一步转换。举例来说，我们也许需要消除左递归。 更多细节请看Compilers: Principles,Techniques, and Tools

解决方案

我们只需实现一个递归下降解析器。为了简单起见，当表达式语法错误时，代码会恐慌。（例如根据语法定义，2-34或者2+5-是错误的）

  1. pub struct Interpreter<'a> {
  2.     it: std::str::Chars<'a>,
  3. }
  4. impl<'a> Interpreter<'a> {
  5.     pub fn new(infix: &'a str) -> Self {
  6.         Self { it: infix.chars() }
  7.     }
  8.     fn next_char(&mut self) -> Option<char> {
  9.         self.it.next()
  10.     }
  11.     pub fn interpret(&mut self, out: &mut String) {
  12.         self.term(out);
  13.         while let Some(op) = self.next_char() {
  14.             if op == '+' || op == '-' {
  15.                 self.term(out);
  16.                 out.push(op);
  17.             } else {
  18.                 panic!("Unexpected symbol '{}'", op);
  19.             }
  20.         }
  21.     }
  22.     fn term(&mut self, out: &mut String) {
  23.         match self.next_char() {
  24.             Some(ch) if ch.is_digit(10) => out.push(ch),
  25.             Some(ch) => panic!("Unexpected symbol '{}'", ch),
  26.             None => panic!("Unexpected end of string"),
  27.         }
  28.     }
  29. }
  30. pub fn main() {
  31.     let mut intr = Interpreter::new("2+3");
  32.     let mut postfix = String::new();
  33.     intr.interpret(&mut postfix);
  34.     assert_eq!(postfix, "23+");
  35.     intr = Interpreter::new("1-2+3-4");
  36.     postfix.clear();
  37.     intr.interpret(&mut postfix);
  38.     assert_eq!(postfix, "12-3+4-");
  39. }

讨论

可能有一种错误的看法，即解释器设计模式是关于形式语言的语法设计和语法分析器的实现。事实上，这个模式是用更具体的方式表达问题实例，并实现解决这些问题实例的函数/类/结构。Rust语言有macro_rules!支持定义特殊语法和如何展开这种语法为源代码的规则。

在下面的例子中我们创建了一个简单的宏来计算n维向量的欧式长度。写norm!(x,1,2)也许比打包x,1,2到Vec中然后调用函数计算要更有表达力和效率。

  1. macro_rules! norm {
  2.     ($($element:expr),*) => {
  3.         {
  4.             let mut n = 0.0;
  5.             $(
  6.                 n += ($element as f64)*($element as f64);
  7.             )*
  8.             n.sqrt()
  9.         }
  10.     };
  11. }
  12. fn main() {
  13.     let x = -3f64;
  14.     let y = 4f64;
  15.     assert_eq!(3f64, norm!(x));
  16.     assert_eq!(5f64, norm!(x, y));
  17.     assert_eq!(0f64, norm!(0, 0, 0)); 
  18.     assert_eq!(1f64, norm!(0.5, -0.5, 0.5, -0.5));
  19. }

See also