Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В компьютерном программировании , то картина интерпретатора является шаблоном дизайна , который определяет , как оценивать предложения в языке. Основная идея состоит в том, чтобы иметь класс для каждого символа ( терминального или нетерминального ) на специализированном компьютерном языке . Синтаксическое дерево из предложения языка является экземпляром составного узора , и используется для оценки (интерпретации) предложения для клиента. [1] : 243 См. Также Составной узор .

Обзор [ править ]

Шаблон проектирования Interpreter [2] - один из двадцати трех хорошо известных шаблонов проектирования GoF, которые описывают, как решать повторяющиеся проблемы проектирования для разработки гибкого и многократно используемого объектно-ориентированного программного обеспечения, то есть объектов, которые легче реализовать, изменить, тестирование и повторное использование.

Какие проблемы может решить шаблон проектирования Interpreter? [3]

  • Грамматика для простого языка должен быть определен
  • так что предложения на языке можно интерпретировать.

Когда проблема возникает очень часто, ее можно представить как предложение на простом языке ( предметно-зависимые языки ), чтобы интерпретатор мог решить проблему, интерпретируя предложение.

Например, когда необходимо указать много разных или сложных поисковых выражений. Реализация (жесткое подключение) их непосредственно в класс негибкая, потому что она связывает класс с определенными выражениями и делает невозможным определение новых выражений или изменение существующих независимо от (без необходимости изменения) класса.

Какое решение описывает шаблон проектирования Interpreter?

  • Определите грамматику для простого языка, определив Expressionиерархию классов и выполнив interpret()операцию.
  • Представляйте предложение на языке абстрактным синтаксическим деревом (AST), состоящим из Expressionэкземпляров.
  • Интерпретируйте предложение, позвонив interpret()в AST.

Объекты выражения рекурсивно составляются в составную / древовидную структуру, которая называется абстрактным синтаксическим деревом (см. Составной шаблон ).
Шаблон интерпретатора не описывает, как построить абстрактное синтаксическое дерево. Это может быть сделано либо вручную клиентом, либо автоматически парсером .

См. Также схему классов и объектов UML ниже.

Использует [ редактировать ]

  • Специализированные языки запросов к базам данных, такие как SQL .
  • Специализированные компьютерные языки, которые часто используются для описания протоколов связи.
  • Большинство компьютерных языков общего назначения фактически включают в себя несколько специализированных языков.

Структура [ править ]

Схема классов и объектов UML [ править ]

Пример класса UML и диаграммы объектов для шаблона проектирования интерпретатора. [4]

В приведенной выше UML - диаграмме класса , то Clientкласс относится к общему AbstractExpressionинтерфейсу для интерпретации выражения interpret(context). Класс не имеет детей и интерпретирует выражение непосредственно. Класс поддерживает контейнер дочерних выражений ( ) и форвардов интерпретировать запросы на них .
TerminalExpression
NonTerminalExpressionexpressionsexpressions

Диаграмма взаимодействия объектов показывает взаимодействия во время выполнения: Clientобъект отправляет запрос интерпретации абстрактному синтаксическому дереву. Запрос направляется (выполняется) ко всем объектам вниз по древовидной структуре.
Эти NonTerminalExpressionобъекты ( ntExpr1,ntExpr2) направить запрос на их детях выражения.
Эти TerminalExpressionобъекты ( tExpr1,tExpr2,…) выполняют интерпретацию непосредственно.

Диаграмма классов UML [ править ]

Примеры [ править ]

BNF [ править ]

Следующий пример формы Бэкуса – Наура иллюстрирует шаблон интерпретатора. Грамматика

выражение :: = плюс | минус | переменная | номерплюс :: = выражение выражение '+'минус :: = выражение выражение '-'переменная :: = 'a' | 'b' | 'c' | ... | 'z'цифра = '0' | '1' | ... | '9'число :: = цифра | цифровой номер

определяет язык, который содержит выражения обратной польской нотации, например:

ab +abc + -ab + ca - -

C # [ править ]

Этот структурный код демонстрирует шаблоны интерпретатора, которые, используя определенную грамматику, предоставляют интерпретатор, обрабатывающий проанализированные операторы.

используя  Систему ; using  System.Collections.Generic ;пространство имен  ООП {  класс  Программа  {  статическая  недействительность  Main ()  {  var  context  =  new  Context ();  var  input  =  new  MyExpression (); var  expression  =  new  OrExpression  {  Left  =  new  EqualsExpression  {  Left  =  input ,  Right  =  new  MyExpression  {  Value  =  "4"  }  },  Right  =  new  EqualsExpression  {  Left  =  input ,  Right  =  new  MyExpression  {  Value  =  "четыре"  }  }  } ;  ввод . Значение  =  «четыре» ;  выражение . Интерпретировать ( контекст );  // Вывод: "true"  Консоль . WriteLine ( context . Result . Pop ()); ввод . Значение  =  «44» ;  выражение . Интерпретировать ( контекст );  // Вывод: "false"  Консоль . WriteLine ( context . Result . Pop ());  }  } класс  Context  {  публичный  стек < строка >  Результат  =  новый  стек < строка > ();  } интерфейс  Expression  {  void  Interpret ( контекстный  контекст );  } абстрактный  класс  OperatorExpression  :  Expression  {  public  Expression  Left  {  private  get ;  набор ;  }  общественное  право выражения  { частное получение ; набор ; }       public  void  Interpret ( Context  context )  {  Left . Интерпретировать ( контекст );  строка  leftValue  =  context . Результат . Поп (); Верно . Интерпретировать ( контекст );  строка  rightValue  =  context . Результат . Поп (); DoInterpret ( контекст ,  leftValue ,  rightValue );  } защищенная  абстрактная  пустота  DoInterpret ( контекст  контекста ,  строка  leftValue ,  строка  rightValue );  } class  EqualsExpression  :  OperatorExpression  {  защищенное  переопределение  void  DoInterpret ( контекст  контекста ,  строка  leftValue ,  строка  rightValue )  {  контекст . Результат . Push ( leftValue  ==  rightValue  ?  "True"  :  "false" );  }  } class  OrExpression  :  OperatorExpression  {  защищенное  переопределение  void  DoInterpret ( контекст  контекста ,  строка  leftValue ,  строка  rightValue )  {  контекст . Результат . Push ( leftValue  ==  "true"  ||  rightValue  ==  "true"  ?  "True"  :  "false" );  }  } класс  MyExpression  :  Выражение  {  общедоступная  строка  Значение  {  частное  получение ;  набор ;  } public  void  Interpret ( Context  context )  {  context . Результат . Нажать ( Значение );  }  } }

Java [ править ]

Следуя шаблону интерпретатора, нам нужно реализовать интерфейс Expr с лямбда (это может быть класс) для каждого правила грамматики.

открытый  класс  Interpreter  {  @FunctionalInterface  открытый  интерфейс  Expr  {  int  интерпретация ( контекст Map < String ,  Integer >  );  Статическая  Expr  номер ( INT  номер )  {  возвращение  контекста  ->  номер ;  }  static  Expr  plus ( Expr  left ,  Expr  right )  {  return  context  ->  left . интерпретировать ( контекст )  +  право . интерпретировать ( контекст );  }  static  Expr  minus ( Expr  left ,  Expr  right )  {  return  context  ->  left . интерпретировать ( контекст )  -  правильно . интерпретировать ( контекст );  }  статическая  переменная Expr  ( имя строки ) { контекст возврата -> контекст . getOrDefault ( имя , 0 ); } }

Хотя шаблон интерпретатора не обращается к синтаксическому анализу, [1] : 247 синтаксический анализатор предоставляется для полноты.

 частный  статический  Expr  parseToken ( String  token ,  ArrayDeque < Expr >  stack )  {  Expr  left ,  right ;  switch ( token )  {  case  "+" :  // Сначала необходимо удалить правый операнд из стека  right  =  stack . pop ();  // ... а потом левый  left  =  stack . pop ();  return  Expr . плюс (слева ,  справа );  case  "-" :  right  =  stack . pop ();  left  =  стек . pop ();  return  Expr . минус ( слева ,  справа );  по умолчанию :  вернуть  Expr . переменная ( токен );  }  }  Общественности  статической  Expr  синтаксического анализа ( Строка  выражение )  {  ArrayDeque < Expr > стек  =  новый  ArrayDeque < Выражение > ();  for  ( Строковый  токен  :  выражение . split ( "" ))  {  стек . push ( parseToken ( токен ,  стек ));  }  стек возврата  . pop (); }

Наконец, вычисляем выражение «wxz - +» с w = 5, x = 10 и z = 42.

 public  static  void  main ( final  String []  args )  {  Expr  expr  =  parse ( "wxz - +" );  Карта < String ,  Integer >  context  =  Map . of ( "w" ,  5 ,  "x" ,  10 ,  "z" ,  42 );  int  result  =  expr . интерпретировать ( контекст );  Система .из . println ( результат );  // -27  } }

PHP (Пример 1) [ править ]

/ ** * AbstractExpression * / interface  Expression {  интерпретация публичной  функции  ( массив $ context ) : int ; }  
/ ** * TerminalExpression * / class  TerminalExpression  реализует  Expression {  / ** @var string * /  private  $ name ; публичная  функция  __construct ( строка  $ name )  {  $ this -> name  =  $ name ;  }  интерпретация публичной функции  ( массив $ context ) : int { return intval ( $ context [ $ this -> name ]); } }      
/ ** * NonTerminalExpression * / абстрактный  класс  NonTerminalExpression  реализует  Expression {  / ** @var Expression $ left * /  protected  $ left ; / ** @var? Выражение $ right * /  protected  $ right ; общественная  функция  __construct ( Expression  $ влево ,  ? Выражение  $ право )  {  $ это -> влево  =  $ влево ;  $ это -> право  =  $ право ;  } абстрактная  публичная  интерпретация функции  ( массив $ context ) : int ;    публичная  функция  getRight ()  {  return  $ this -> right ;  } публичная  функция  setRight ( $ right ) :  void  {  $ this -> right  =  $ right ;  } }
/ ** * NonTerminalExpression - PlusExpression * / class  PlusExpression  расширяет  NonTerminalExpression {  интерпретация публичной  функции  ( массив $ context ) : int { return intval ( $ this -> left -> интерпретировать ( $ context ) + $ this -> right -> интерпретировать ( $ context )); } }        
/ ** * NonTerminalExpression - MinusExpression * / class  MinusExpression  расширяет  NonTerminalExpression {  интерпретацию публичной  функции  ( массив $ context ) : int { return intval ( $ this -> left -> интерпретировать ( $ context ) - $ this -> right -> интерпретировать ( $ context )); } }        
/ ** * Клиент * / class  InterpreterClient {  защищенная  функция  parseList ( массив  и $ стек ,  массив  $ list ,  int  & $ index )  {  / ** @var string $ token * /  $ token  =  $ list [ $ index ]; переключатель ( $ токен )  {  case  '-' :  list ( $ left ,  $ right )  =  $ this -> fetchArguments ( $ stack ,  $ list ,  $ index );  вернуть  новое  MinusExpression ( $ left ,  $ right );  case  '+' :  list ( $ left ,  $ right )  =  $ this -> fetchArguments ( $ stack ,  $ list , $ index );  return  new  PlusExpression ( $ left ,  $ right );  по умолчанию :  вернуть  новое  выражение TerminalExpression ( $ token );  }  } защищенная  функция  fetchArguments ( массив  & $ stack ,  array  $ list ,  int  & $ index ) :  array  {  / ** @var Expression $ left * /  $ left  =  array_pop ( $ stack );  / ** @var Выражение $ right * /  $ right  =  array_pop ( $ stack );  если  ( $ right  ===  null )  {  ++ $ index ;  $ this -> parseListAndPush ( $ stack,  $ список ,  $ индекс );  $ right  =  array_pop ( $ стек );  } вернуть  массив ( $ left ,  $ right );  } защищенная  функция  parseListAndPush ( массив  & $ stack ,  массив  $ list ,  int  & $ index )  {  array_push ( $ stack ,  $ this -> parseList ( $ stack ,  $ list ,  $ index ));  }  синтаксический анализ защищенной функции  ( строка $ data ) : Выражение { $ stack = []; $ list = explode ( ' , $ данные ); for ( $ index = 0 ; $ index < count ( $ list ); $ index ++ ) { $ this -> parseListAndPush ( $ stack , $ list , $ index ); }                    вернуть  array_pop ( $ stack );  } публичная  функция  main ()  {  $ data  =  "u + v - w + z" ;  $ expr  =  $ this -> parse ( $ data );  $ context  =  [ 'u'  =>  3 ,  'v'  =>  7 ,  'w'  =>  35 ,  'z'  =>  9 ];  $ res  =  $ expr -> интерпретировать ( $ context );  echo  "результат: $ res "  .  PHP_EOL ; } }
// test.phpфункция  loadClass ( $ className ) {  require_once  __DIR__  .  "/ $ className .php" ; }spl_autoload_register ( 'loadClass' );( новый  InterpreterClient ()) -> main (); // результат: -16

PHP (Пример 2) [ править ]

На основе приведенного выше примера с другой реализацией клиента.

/ ** * Клиент * / class  InterpreterClient {  публичная  функция  parseToken ( строка  $ token ,  массив  и $ stack ) :  Expression  {  switch ( $ token )  {  case  '-' :  / ** @var Expression $ left * /  $ left  =  array_pop ( $ стек );  / ** @var Выражение $ right * /  $ right  =  array_pop ( $ stack );  вернуть  новое  MinusExpression ($ влево ,  $ вправо );  case  '+' :  / ** @var Выражение $ left * /  $ left  =  array_pop ( $ stack );  / ** @var Выражение $ right * /  $ right  =  array_pop ( $ stack );  return  new  PlusExpression ( $ left ,  $ right );  по умолчанию :  вернуть  новое  выражение TerminalExpression ( $ token );  }  }  синтаксический анализ публичной функции  ( строка $ data ) : Выражение { $ notinishedData = null ; $ stack = []; $ list = explode ( ' , $ данные ); foreach ( $ list as $ token ) { $ data = $ this -> parseToken ( $ token , $ stack ); if ( ( $ notinishedData instanceof NonTerminalExpression )                            &&  ( $ data  instanceof  Терминального выражения )  )  {  $ UnfinishedData -> setRight ( $ data );  array_push ( $ stack ,  $ unfinishedData );  $ undefinishedData  =  ноль ;  продолжить ;  }  if  ( $ data  instanceof  NonTerminalExpression )  {  if  ( $ data -> getRight ()  ===  null )  {  $  notinishedData =  $ data ; продолжить ;  }  }  array_push ( $ stack ,  $ data );  } вернуть  array_pop ( $ stack );  } публичная  функция  main ()  {  $ data  =  "u + v - w + z" ;  $ expr  =  $ this -> parse ( $ data );  $ context  =  [ 'u'  =>  3 ,  'v'  =>  7 ,  'w'  =>  35 ,  'z'  =>  9 ];  $ res  =  $ expr -> интерпретировать ( $ context );  echo  "результат: $ res "  .  PHP_EOL ; } }

JavaScript [ править ]

Поскольку JavaScript не поддерживает реальную объектную ориентацию, мы не реализуем интерфейс.

// Нетерминальное выражение class  Plus  {  a ;  б ;  конструктор ( а ,  б )  {  это . а  =  а ;  это . б  =  б ;  }  интерпретировать ( контекст )  {  вернуть  это . а . интерпретировать ( контекст )  +  это . б . интерпретировать ( контекст );  } }// Нетерминальное выражение class  Minus  {  a ;  б ;  конструктор ( а ,  б )  {  это . а  =  а ;  это . б  =  б ;  }  интерпретировать ( контекст )  {  вернуть  это . а . интерпретировать ( контекст )  -  это . б . интерпретировать ( контекст );  } }// Нетерминальное выражение class  Times  {  a ;  б ;  конструктор ( а ,  б )  {  это . а  =  а ;  это . б  =  б ;  }  интерпретировать ( контекст )  {  вернуть  это . а . интерпретировать ( контекст )  *  this . б . интерпретировать ( контекст );  } }// Нетерминальное выражение class  Divide  {  a ;  б ;  конструктор ( а ,  б )  {  это . а  =  а ;  это . б  =  б ;  }  интерпретировать ( контекст )  {  вернуть  это . а . интерпретировать ( контекст )  /  это . б . интерпретировать ( контекст );  } }// Терминальное выражение class  Number  {  a ;  конструктор ( а ,  б )  {  это . а  =  а ;  }  интерпретировать ( контекст )  {  вернуть  это . а ;  } } // Терминальное выражение class  Variable  {  a ;  конструктор ( а )  {  это . а  =  а ;  }  интерпретировать (context )  {  return  context [ this . а ]  ||  0 ;  } } // Клиентский класс  Parse  {  context ;  конструктор ( контекст )  {  это . context  =  context ;  }  parse ( выражение )  {  let  tokens  =  expression . сплит ( "" );  пусть  очередь  =  [];  для ( Пусть  маркер  из  лексем )  {  переключатель  ( маркер )  {  случай  «+» :  вар  б  =  очередь . pop ();  var  a  =  очередь . pop ();  var  exp  =  new  Plus ( a ,  b );  очередь . push ( exp );  перерыв ;  case  "/" :  var  b  =  очередь .pop ();  var  a  =  очередь . pop ();  var  exp  =  new  Divide ( a ,  b );  очередь . push ( exp );  перерыв ;  case  "*" :  var  b  =  queue . pop ();  var  a  =  очередь . pop ();  var  exp  =  новое  время ( a ,  b );  очередь. push ( exp );  перерыв ;  case  "-" :  var  b  =  queue . pop ();  var  a  =  очередь . pop ();  var  exp  =  новый  минус ( a ,  b );  очередь . push ( exp );  перерыв ;  по умолчанию :  if ( isNaN ( токен ))  {  var  exp  =  new Переменная ( токен );  очередь . push ( exp );  }  Иначе  {  вар  число  =  ParseInt ( маркер );  var  exp  =  новое  число ( число );  очередь . push ( exp );  }  перерыв ;  }  }  let  main  =  queue . pop ();  вернуть  main . интерпретировать ( this .контекст );  } } var  res  =  new  Parse ({ v :  45 }). синтаксический анализ ( "16 v * 76 22 - -" ); консоль . журнал ( res ) // 666

См. Также [ править ]

  • Форма Бэкуса – Наура
  • Комбинаторная логика в вычислениях
  • Шаблоны проектирования
  • Доменный язык
  • Переводчик (вычислитель)

Ссылки [ править ]

  1. ^ а б Гамма, Эрих ; Хелм, Ричард ; Джонсон, Ральф; Влиссидес, Джон (1994). Шаблоны проектирования: элементы объектно-ориентированного программного обеспечения многократного использования . Эддисон-Уэсли. ISBN 0-201-63361-2.
  2. ^ Эрих Гамма, Ричард Хелм, Ральф Джонсон, Джон Влиссидес (1994). Шаблоны проектирования: элементы объектно-ориентированного программного обеспечения многократного использования . Эддисон Уэсли. стр.  243ff . ISBN 0-201-63361-2.CS1 maint: несколько имен: список авторов ( ссылка )
  3. ^ «Шаблон проектирования интерпретатора - проблема, решение и применимость» . w3sDesign.com . Проверено 12 августа 2017 .
  4. ^ "Шаблон проектирования интерпретатора - структура и сотрудничество" . w3sDesign.com . Проверено 12 августа 2017 .

Внешние ссылки [ править ]

  • Реализация интерпретатора в Ruby
  • Реализация интерпретатора на C ++
  • SourceMaking руководство
  • Описание паттернов интерпретатора из Портлендского репозитория паттернов