解释器（Interpreter）

2017-06-09 本文已影响0人非空白

意图

给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。

结构

解释器的结构图

动机

如果一种特定类型的问题出现的频率足够高，那么可能值得将问题的各个部分表述为一个简单语言中的句子。这样就可以构建一个解释器，该解释器通过解释这些句子来解决这类问题。

解释器模式描述了如何为简单的语言定义一个文法，如何在该语言中表示一个句子，以及如何解释这些句子。

适用性

当有一个语言需要解释执行，并且语言中的句子能表示为抽象语法树时，可以使用解释器模式。

注意事项

解释器模式并没有解释如何创建一个抽象语法树，也就是说，它不涉及到语法分析；
解释器表达式不一定要定义解释操作，或者也可以将解释操作委托给一个“访问者”（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

解释器（Interpreter）

意图

结构

动机

适用性

注意事项

示例一

问题

实现（C#）

示例二

问题

实现（C#）

猜你喜欢

热点阅读