?? pat5c.htm
字號:
<HTML><HEAD> <TITLE>Interpreter</TITLE><SCRIPT>function setFocus() { if ((navigator.appName != "Netscape") && (parseFloat(navigator.appVersion) == 2)) { return; } else { self.focus(); }}</SCRIPT></HEAD><BODY BGCOLOR = #FFFFFFonLoad="setFocus()";><A NAME="top"></A><A NAME="Interpreter"></A><A NAME="intent"></A><H2><A HREF="#motivation"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: Motivation"></A> Intent</H2> <A NAME="auto1000"></A><P>Given a language, define a represention for its grammar along with aninterpreter that uses the representation to interpret sentences in thelanguage.</P><A NAME="motivation"></A><H2><A HREF="#applicability"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: Applicability"></A> Motivation</H2> <A NAME="auto1001"></A><P>If a particular kind of problem occurs often enough, then it might beworthwhile to express instances of the problem as sentences in asimple language. Then you can build an interpreter that solves theproblem 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 commonproblem. Regular expressions are a standard language for specifyingpatterns of strings. Rather than building custom algorithms to matcheach pattern against strings, search algorithms could interpret aregular 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 simplelanguages, represent sentences in the language, and interpret thesesentences. In this example, the pattern describes how to define agrammar for regular expressions, represent a particular regularexpression, 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 ofthese classes. The grammar above is represented by five classes: anabstract class RegularExpression and its four subclassesLiteralExpression, AlternationExpression, SequenceExpression, andRepetitionExpression. The last three classes define variables thathold 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 anabstract syntax tree made up of instances of these classes. Forexample, 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 definingthe Interpret operation on each subclass of RegularExpression.Interpret takes as an argument the context in which to interpret theexpression. The context contains the input string and information onhow much of it has been matched so far. Each subclass ofRegularExpression implements Interpret to match the next part of theinput string based on the current context. For example,</P><UL><A NAME="auto1010"></A><LI>LiteralExpression will check if the input matches the literal itdefines,</LI><A NAME="auto1011"></A><P></P><A NAME="auto1012"></A><LI>AlternationExpression will check if the input matches any of itsalternatives,</LI><A NAME="auto1013"></A><P></P><A NAME="auto1014"></A><LI>RepetitionExpression will check if the input has multiple copies ofexpression 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 ALT="next: Structure"></A> Applicability</H2> <A NAME="auto1016"></A><P>Use the Interpreter pattern when there is a language to interpret, andyou 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 forthe grammar becomes large and unmanageable. Tools such as parsergenerators are a better alternative in such cases. They can interpretexpressions without building abstract syntax trees, which can savespace and possibly time.</LI><A NAME="auto1018"></A><P></P><A NAME="auto1019"></A><LI>efficiency is not a critical concern. The most efficient interpretersare usually <EM>not</EM> implemented by interpreting parse trees directlybut by first translating them into another form. For example, regularexpressions are often transformed into state machines. But even then,the <EM>translator</EM> can be implemented by the Interpreter pattern, sothe pattern is still applicable.</LI></UL><A NAME="structure"></A><H2><A HREF="#participants"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: Participants"></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 ALT="next: Collaborations"></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 ALT="next: Consequences"></A> Collaborations</H2><UL><A NAME="auto1046"></A><LI>The client builds (or is given) the sentence as an abstract syntaxtree of NonterminalExpression and TerminalExpression instances. Thenthe client initializes the context and invokes the Interpretoperation.</LI><A NAME="auto1047"></A><P></P><A NAME="auto1048"></A><LI>Each NonterminalExpression node defines Interpret in terms ofInterpret on each subexpression. The Interpret operation of eachTerminalExpression 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 tostore and access the state of the interpreter.</LI></UL><A NAME="consequences"></A><H2><A HREF="#implementation"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: Implementation"></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 canuse inheritance to change or extend the grammar. Existing expressionscan be modified incrementally, and new expressions can be defined asvariations 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 similarimplementations. These classes are easy to write, and often theirgeneration can be automated with a compiler or parser generator.</LI><A NAME="auto1054"></A><P></P>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -