📄 pat5c.htm
字号:
<HTML><HEAD> <TITLE>Interpreter</TITLE></HEAD>
<BODY BGCOLOR = #FFFFFF
>
<A NAME="top"></A>
<A NAME="Interpreter"></A>
<A NAME="intent"></A>
<H2><A HREF="#motivation"><IMG SRC="gifsb/down3.gif" BORDER=0></A> Intent</H2>
<A NAME="auto1000"></A>
<P>Given a language, define a represention for its grammar along with an
interpreter that uses the representation to interpret sentences in the
language.</P>
<A NAME="motivation"></A>
<H2><A HREF="#applicability"><IMG SRC="gifsb/down3.gif" BORDER=0></A> Motivation</H2>
<A NAME="auto1001"></A>
<P>If a particular kind of problem occurs often enough, then it might be
worthwhile to express instances of the problem as sentences in a
simple language. Then you can build an interpreter that solves the
problem by interpreting these sentences.</P>
<A NAME="pattern-matching"></A>
<A NAME="regexp"></A>
<P>For example, searching for strings that match a pattern is a common
problem. Regular expressions are a standard language for specifying
patterns of strings. Rather than building custom algorithms to match
each pattern against strings, search algorithms could interpret a
regular expression that specifies a set of strings to match.</P>
<A NAME="auto1002"></A>
<P>The Interpreter pattern describes how to define a grammar for simple
languages, represent sentences in the language, and interpret these
sentences. In this example, the pattern describes how to define a
grammar for regular expressions, represent a particular regular
expression, and how to interpret that regular expression.</P>
<A NAME="auto1003"></A>
<P>Suppose the following grammar defines the regular expressions:</P>
<A NAME="auto1004"></A>
<PRE>
expression ::= literal | alternation | sequence | repetition |
'(' expression ')'
alternation ::= expression '|' expression
sequence ::= expression '&' expression
repetition ::= expression '*'
literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*
</PRE>
<A NAME="auto1005"></A>
<P>The symbol <CODE>expression</CODE> is the start symbol, and <CODE>literal</CODE>
is a terminal symbol defining simple words.</P>
<A NAME="auto1006"></A>
<P>The Interpreter pattern uses a class to represent each grammar rule.
Symbols on the right-hand side of the rule are instance variables of
these classes. The grammar above is represented by five classes: an
abstract class RegularExpression and its four subclasses
LiteralExpression, AlternationExpression, SequenceExpression, and
RepetitionExpression. The last three classes define variables that
hold subexpressions.</P>
<A NAME="abssynclass"></A>
<A NAME="244co"></A>
<P ALIGN=CENTER><IMG SRC="Pictures/inter043.gif"></P>
<A NAME="abssyntree"></A>
<P>Every regular expression defined by this grammar is represented by an
abstract syntax tree made up of instances of these classes. For
example, the abstract syntax tree</P>
<A NAME="abssync"></A>
<P ALIGN=CENTER><IMG SRC="Pictures/inter042.gif"></P>
<A NAME="auto1007"></A>
<P>represents the regular expression</P>
<A NAME="auto1008"></A>
<PRE>
raining & (dogs | cats) *
</PRE>
<A NAME="auto1009"></A>
<P>We can create an interpreter for these regular expressions by defining
the Interpret operation on each subclass of RegularExpression.
Interpret takes as an argument the context in which to interpret the
expression. The context contains the input string and information on
how much of it has been matched so far. Each subclass of
RegularExpression implements Interpret to match the next part of the
input string based on the current context. For example,</P>
<UL>
<A NAME="auto1010"></A>
<LI>LiteralExpression will check if the input matches the literal it
defines,</LI>
<A NAME="auto1011"></A>
<P></P>
<A NAME="auto1012"></A>
<LI>AlternationExpression will check if the input matches any of its
alternatives,</LI>
<A NAME="auto1013"></A>
<P></P>
<A NAME="auto1014"></A>
<LI>RepetitionExpression will check if the input has multiple copies of
expression it repeats,</LI>
</UL>
<A NAME="auto1015"></A>
<P>and so on.</P>
<A NAME="applicability"></A>
<H2><A HREF="#structure"><IMG SRC="gifsb/down3.gif" BORDER=0></A> Applicability</H2>
<A NAME="auto1016"></A>
<P>Use the Interpreter pattern when there is a language to interpret, and
you can represent statements in the language as abstract syntax trees.
The Interpreter pattern works best when</P>
<UL>
<A NAME="auto1017"></A>
<LI>the grammar is simple. For complex grammars, the class hierarchy for
the grammar becomes large and unmanageable. Tools such as parser
generators are a better alternative in such cases. They can interpret
expressions without building abstract syntax trees, which can save
space and possibly time.</LI>
<A NAME="auto1018"></A>
<P></P>
<A NAME="auto1019"></A>
<LI>efficiency is not a critical concern. The most efficient interpreters
are usually <EM>not</EM> implemented by interpreting parse trees directly
but by first translating them into another form. For example, regular
expressions are often transformed into state machines. But even then,
the <EM>translator</EM> can be implemented by the Interpreter pattern, so
the pattern is still applicable.</LI>
</UL>
<A NAME="structure"></A>
<H2><A HREF="#participants"><IMG SRC="gifsb/down3.gif" BORDER=0></A>
Structure</H2>
<P ALIGN=CENTER><IMG SRC="Pictures/inter041.gif"></P>
<A NAME="participants"></A>
<H2><A HREF="#collaborations"><IMG SRC="gifsb/down3.gif" BORDER=0></A>
Participants</H2>
<UL>
<A NAME="auto1020"></A>
<LI><B>AbstractExpression</B> (RegularExpression)</LI>
<A NAME="auto1021"></A>
<P></P>
<UL>
<A NAME="auto1022"></A>
<LI>declares an abstract Interpret operation that is common to
all nodes in the abstract syntax tree.</LI>
</UL>
<A NAME="auto1023"></A>
<P></P>
<A NAME="terminal-symbol"></A>
<A NAME="terminal-expr"></A>
<LI><B>TerminalExpression</B> (LiteralExpression)</LI>
<A NAME="auto1024"></A>
<P></P>
<UL>
<A NAME="auto1025"></A>
<LI>implements an Interpret operation associated with terminal
symbols in the grammar.</LI>
<A NAME="auto1026"></A>
<P><!-- extra space --></P>
<A NAME="auto1027"></A>
<LI>an instance is required for every terminal symbol in a
sentence.</LI>
</UL>
<A NAME="auto1028"></A>
<P></P>
<A NAME="auto1029"></A>
<LI><B>NonterminalExpression</B> (AlternationExpression,
RepetitionExpression, SequenceExpressions)</LI>
<A NAME="auto1030"></A>
<P></P>
<UL>
<A NAME="auto1031"></A>
<LI>one such class is required for every rule <I>R</I> ::=
<I>R</I><SUB>1</SUB> <I>R</I><SUB>2</SUB> ... <I>R</I><SUB>n</SUB></I>
in the grammar.</LI>
<A NAME="auto1032"></A>
<P><!-- extra space --></P>
<A NAME="auto1033"></A>
<LI>maintains instance variables of type AbstractExpression
for each of the symbols <I>R</I><SUB>1</SUB> through
<I>R</I><SUB>n</SUB>.</LI>
<A NAME="auto1034"></A>
<P><!-- extra space --></P>
<A NAME="auto1035"></A>
<LI>implements an Interpret operation for
nonterminal symbols in the grammar. Interpret typically calls itself
recursively on the variables representing <I>R</I><SUB>1</SUB> through
<I>R</I><SUB>n</SUB>.</LI>
</UL>
<A NAME="auto1036"></A>
<P></P>
<A NAME="auto1037"></A>
<LI><B>Context</B></LI>
<A NAME="auto1038"></A>
<P></P>
<UL>
<A NAME="auto1039"></A>
<LI>contains information that's global to the interpreter.</LI>
</UL>
<A NAME="auto1040"></A>
<P></P>
<A NAME="auto1041"></A>
<LI><B>Client</B></LI>
<A NAME="auto1042"></A>
<P></P>
<UL>
<A NAME="auto1043"></A>
<LI>builds (or is given) an abstract syntax tree representing a
particular sentence in the language that the grammar defines. The
abstract syntax tree is assembled from instances of the
NonterminalExpression and TerminalExpression classes.</LI>
<A NAME="auto1044"></A>
<P><!-- extra space --></P>
<A NAME="auto1045"></A>
<LI>invokes the Interpret operation.</LI>
</UL>
</UL>
<A NAME="collaborations"></A>
<H2><A HREF="#consequences"><IMG SRC="gifsb/down3.gif" BORDER=0></A> Collaborations</H2>
<UL>
<A NAME="auto1046"></A>
<LI>The client builds (or is given) the sentence as an abstract syntax
tree of NonterminalExpression and TerminalExpression instances. Then
the client initializes the context and invokes the Interpret
operation.</LI>
<A NAME="auto1047"></A>
<P></P>
<A NAME="auto1048"></A>
<LI>Each NonterminalExpression node defines Interpret in terms of
Interpret on each subexpression. The Interpret operation of each
TerminalExpression defines the base case in the recursion.</LI>
<A NAME="auto1049"></A>
<P></P>
<A NAME="auto1050"></A>
<LI>The Interpret operations at each node use the context to
store and access the state of the interpreter.</LI>
</UL>
<A NAME="consequences"></A>
<H2><A HREF="#implementation"><IMG SRC="gifsb/down3.gif" BORDER=0></A> Consequences</H2>
<A NAME="auto1051"></A>
<P>The Interpreter pattern has the following benefits and liabilities:</P>
<OL>
<A NAME="auto1052"></A>
<LI><EM>It's easy to change and extend the grammar.</EM>
Because the pattern uses classes to represent grammar rules, you can
use inheritance to change or extend the grammar. Existing expressions
can be modified incrementally, and new expressions can be defined as
variations on old ones.</LI>
<A NAME="auto1053"></A>
<P></P>
<A NAME="parser-247"></A>
<LI><EM>Implementing the grammar is easy, too.</EM>
Classes defining nodes in the abstract syntax tree have similar
implementations. These classes are easy to write, and often their
generation can be automated with a compiler or parser generator.</LI>
<A NAME="auto1054"></A>
<P></P>
<A NAME="auto1055"></A>
<LI><EM>Complex grammars are hard to maintain.</EM>
The Interpreter pattern defines at least one class for every rule
in the grammar (grammar rules defined using BNF may require multiple
classes). Hence grammars containing many rules can be hard to
manage and maintain. Other design patterns can be applied to
mitigate the problem (see <A HREF="#implementation">Implementation</A>).
But when the grammar is very complex, other techniques such as
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -