意图
给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。
结构
解释器的结构图
动机
如果一种特定类型的问题出现的频率足够高，那么可能值得将问题的各个部分表述为一个简单语言中的句子。这样就可以构建一个解释器，该解释器通过解释这些句子来解决这类问题。
解释器模式描述了如何为简单的语言定义一个文法，如何在该语言中表示一个句子，以及如何解释这些句子。
适用性
当有一个语言需要解释执行，并且语言中的句子能表示为抽象语法树时，可以使用解释器模式。
注意事项
- 解释器模式并没有解释如何创建一个抽象语法树，也就是说，它不涉及到语法分析；
- 解释器表达式不一定要定义解释操作，或者也可以将解释操作委托给一个“访问者”（Visitor）对象，避免在各个表达式中繁琐地定义这些操作；
- 终结表达式可以用享元模式（Flyweight）共享。
示例一
问题
定义一个正则表达式，用于检查一个字符串是否匹配。正则表达式的文法定义如下：
- expression ::= liternal | alternation | sequence | repetition | '(' expression ')'
- alternation ::= expression '|' expression
- sequence ::= expression '&' expression
- **repetition := expression '*' **
- liternal := 'a' | 'b' | 'c'| ... { 'a' | 'b' | 'c' | ...}*
创建：
"raining" & ( "dogs" | "cats") *
输入：
rainingcatscats
输出：
true
实现（C#）
为了实现这个简易的正则表达式解析器，我们定义了如下几个表达式类：
正则表达式解析器
// 正则表达式的抽象基类
public abstract class RegularExpression
{
public abstract string Match(string input);
}
// 字面表达式
public sealed class LiternalExpression : RegularExpression
{
private readonly string liternal;
public LiternalExpression(string liternal)
{
this.liternal = liternal;
}
public override string ToString()
{
return "\""+ liternal + "\"";
}
public override string Match(string input)
{
if(!input.StartsWith(liternal))
return input;
else
return input.Substring(liternal.Length);
}
}
// 或操作表达式
public sealed class AlternationExpression : RegularExpression
{
private readonly RegularExpression left;
private readonly RegularExpression right;
public AlternationExpression(RegularExpression left, RegularExpression right)
{
this.left = left;
this.right = right;
}
public override string ToString()
{
return string.Format("({0} | {1})", left.ToString(), right.ToString());
}
public override string Match(string input)
{
var rest = left.Match(input);
return rest == input ? right.Match(input) : rest;
}
}
// 与操作表达式
public sealed class SequenceExpression : RegularExpression
{
private readonly RegularExpression left;
private readonly RegularExpression right;
public SequenceExpression(RegularExpression left, RegularExpression right)
{
this.left = left;
this.right = right;
}
public override string ToString()
{
return string.Format("({0} & {1})",left.ToString(),right.ToString());
}
public override string Match(string input)
{
var rest = left.Match(input);
if(rest != input) return right.Match(rest);
return rest;
}
}
// 重复操作表达式
public sealed class RepetitionExpression : RegularExpression
{
private readonly RegularExpression repetition;
public RepetitionExpression(RegularExpression repetition)
{
this.repetition = repetition;
}
public override string ToString()
{
return string.Format("{0} *", repetition.ToString());
}
public override string Match(string input)
{
var repetition2 = repetition;
var rest = repetition2.Match(input);
while(rest != input)
{
if(!(repetition2 is LiternalExpression))
{
repetition2 = new LiternalExpression(input.Substring(0,input.Length - rest.Length));
}
input = rest;
rest = repetition2.Match(input);
}
return rest;
}
}
// 测试！注意添加命名空间: using System;
public class App
{
public static void Main(string[] args)
{
// "raining" & ( "dogs" | "cats") *
LiternalExpression raining = new LiternalExpression("raining");
LiternalExpression dogs = new LiternalExpression("dogs");
LiternalExpression cats = new LiternalExpression("cats");
AlternationExpression dogsOrCats = new AlternationExpression(dogs,cats);
RepetitionExpression repetition = new RepetitionExpression(dogsOrCats);
SequenceExpression sequence = new SequenceExpression(raining,repetition);
//打印出正则表达式的结构
Console.WriteLine(sequence.ToString());
Console.WriteLine("input = \"{0}\", result = {1}",
"rainingcatscats",
sequence.Match("rainingcatscats") == string.Empty);
Console.WriteLine("input = \"{0}\", result = {1}",
"rainingdogsdogs",
sequence.Match("rainingdogsdogs") == string.Empty);
Console.WriteLine("input = \"{0}\", result = {1}",
"rainingCatsCats",
sequence.Match("rainingCatCats") == string.Empty);
}
}
// 控制台输出：
// ("raining" & ("dogs" | "cats") *)
// input = "rainingcatscats", result = True
// input = "rainingdogsdogs", result = True
// input = "rainingCatsCats", result = False
示例二
问题
实现对布尔表达式进行操作和求值。文法定义如下：
- boolean ::= Variable | Constant | Or | And | Not | '(' boolean ') '
- Or ::= boolean '|' boolean
- And ::= boolean '&' boolean
- Not := '!' boolean
- Constant := 'true' | 'false'
- **Variable := 'A' | 'B' | ... | 'X' | 'Y' | 'Z' **
创建：
( true & X ) | ( Y & ( !X ) )
输入：
X = fase, Y = true
输出：
true
实现（C#）
同样，我们先设计出相关表达式的结构图：
布尔表达式结构图
// 布尔表达式的抽象基类
public abstract class BooleanExpression
{
public abstract bool Evaluate(Context context);
}
// 常量表达式
public sealed class ConstantExpression : BooleanExpression
{
private readonly bool val;
public ConstantExpression(bool val)
{
this.val = val;
}
public override bool Evaluate(Context context)
{
return this.val;
}
public override string ToString()
{
return val.ToString();
}
}
// 与操作表达式
public sealed class AndExpression : BooleanExpression
{
private readonly BooleanExpression left;
private readonly BooleanExpression right;
public AndExpression(BooleanExpression left, BooleanExpression right)
{
this.left = left;
this.right = right;
}
public override bool Evaluate(Context context)
{
return this.left.Evaluate(context) && this.right.Evaluate(context);
}
public override string ToString()
{
return string.Format("({0} & {1})", left.ToString(), right.ToString());
}
}
// 或操作表达式
public sealed class OrExpression : BooleanExpression
{
private readonly BooleanExpression left;
private readonly BooleanExpression right;
public OrExpression(BooleanExpression left, BooleanExpression right)
{
this.left = left;
this.right = right;
}
public override bool Evaluate(Context context)
{
return this.left.Evaluate(context) || this.right.Evaluate(context);
}
public override string ToString()
{
return string.Format("({0} | {1})", left.ToString(), right.ToString());
}
}
// 非操作表达式
public sealed class NotExpression : BooleanExpression
{
private readonly BooleanExpression expr;
public NotExpression(BooleanExpression expr)
{
this.expr = expr;
}
public override bool Evaluate(Context context)
{
return !this.expr.Evaluate(context);
}
public override string ToString()
{
return string.Format("(!{0})", expr.ToString());
}
}
// 变量表达式
public class VariableExpression : BooleanExpression
{
private readonly string name;
public VariableExpression(string name)
{
this.name = name;
}
public override bool Evaluate(Context context)
{
return context.Lookup(this);
}
public string Name { get { return this.name;} }
public override string ToString()
{
return this.name;
}
}
// 操作上下文
public class Context
{
private readonly Dictionary<VariableExpression,bool> map = new Dictionary<VariableExpression,bool>();
public void Assign(VariableExpression expr,bool value)
{
if(map.ContainsKey(expr))
{
map[expr] = value;
}
else
{
map.Add(expr, value);
}
}
public bool Lookup(VariableExpression expr)
{
return map[expr];
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
foreach(KeyValuePair<VariableExpression,bool> kvp in map)
{
sb.AppendFormat("{0}={1},", kvp.Key.Name, kvp.Value);
}
return sb.ToString();
}
}
// 测试。注意添加命名空间：
// using system;
// using System.Text;
// using System.Collections.Generic;
public class App
{
public static void Main(string[] args)
{
Context context = new Context();
VariableExpression X = new VariableExpression("X");
VariableExpression Y = new VariableExpression("Y");
// ( true & X ) | ( Y & ( !X ) )
BooleanExpression expr = new OrExpression(
new AndExpression(new ConstantExpression(true), X),
new AndExpression(Y, new NotExpression(X))
);
context.Assign(X,false);
context.Assign(Y,true);
Console.WriteLine("Expression : {0}", expr.ToString());
Console.WriteLine(" Context : {0}", context.ToString());
Console.WriteLine(" Result : {0}", expr.Evaluate(context));
}
}
// 控制台输出：
// Expression : ((True & X) | (Y & (!X)))
// Context : X=False,Y=True,
// Result : True
网友评论