Видео курс Шаблоны проектирования

Основные темы, рассматриваемые на уроке:
01:32 1 Назначение паттерна
03:06 2 Структура паттерна на языке UML
08:24 3 Структура паттерна на языке C#
18:34 4 Применимость Паттерна
20:51 5 Достоинства и недостатки паттерна
22:17 6 Назначение паттерна
24:42 7 Использование паттерна

Видео урок посвящен шаблону проектирования Interpreter (интерпретатор), который позволяет сформировать объектно-ориентированное представление грамматики для заданного языка, а также описывает правила создания механизма интерпретации (толкования) предложений этого языка.

Для просмотра полной версии видеокурса и получения доступа к дополнительным учебным материалам Вам необходимо оформить подписку
Оформить подписку

Паттерн Interpreter

Название

Интерпретатор

Также известен как

-

Классификация

По цели: поведенческий

По применимости: к классам

Частота использования

Низкая                  -   1 2 3 4 5

Назначение

Паттерн Interpreter – позволяет сформировать объектно-ориентированное представление грамматики для заданного языка, а также описывает правила создания механизма интерпретации (толкования) предложений этого языка.

Введение

Паттерн Interpreter описывает способы и правила построения объектно-ориентированного представления грамматики для заданного формального языка. Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Грамматики классифицируются по иерархии Хомского, согласно которой они разделяются на четыре категории. Иерархия Хомского классифицирует грамматические формальные системы по их порождающей способности – то есть по тому множеству языков, которые они позволяют представить.

Список типов грамматик по классификации Хомского:

  • Рекурсивно перечислимые грамматики.

Эти грамматики имеют неограниченные правила и по своей выразительной мощи эквивалентны машинам Тьюринга. Практического применения в силу своей сложности такие грамматики не имеют.

  • Контекстно-зависимые грамматики.

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

  • Контекстно-свободные грамматики.

Эти грамматики широко применяются для описания синтаксиса компьютерных языков.

  • Регулярные грамматики.

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

Первые две грамматики в иерархии Хомского имеют большую выразительную мощь, но алгоритмы для работы с такими грамматиками являются сложными и малоэффективными. Долгое время усилия лингвистов, в том числе и Аврама Ноама Хомского были в основном направлены на исследование контекстно-свободных и контекстно-зависимых языков. Но в итоге стали чаще применяться регулярные грамматики в силу простоты обращения с ними. Все регулярные грамматики могут быть разделены на два эквивалентных класса: леволинейные и праволинейные регулярные грамматики.

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

Важной особенностью регулярных грамматик является то, что регулярные грамматики эквивалентны по своей вычислительной мощи конечным автоматам (КА).

Определим язык формально. Есть и другие определения, но мы остановимся на этом.

ОПРЕДЕЛЕНИЕ: Конечное множество элементов будем называть словарем, элементы словаря – символами, а последовательности символов словаря – цепочками или предложениями. Множество предложений назовем языком. Язык над словарем V будем обозначать LV, или просто L, если V очевидно.

Пусть V – словарь. Обозначим V* - множество всех возможных цепочек, составленных из символов словаря V. Если V= {a, b, c}, то V*= {ε, a, b, c, aa, ab, ac, … aaa, aab, … abacbcaacbcacb..., …}, где ε – пустая цепочка, не содержащая символов. Очевидно, что хотя V конечно, V* - бесконечное счетное множество. Всего языков над словарем V (как подмножеств, счетного множества V*), бесконечное число: это множество мощности континуум.

Один из распространенных методов задания языка использует «определитель множества» вида: {ω|утверждение о цепочке ω}, где ω – это обычно выражение с параметрами, а утверждение о цепочке ω – определяет некоторые условия, налагаемые на параметры. Во многих случаях использовать этот метод трудно или невозможно. Например, как задать L - множество правильных скобочных выражений, как определить множество всех идентификаторов языка программирования, как задать сам язык программирования? Для упрощения решения большинства таких задач существует два типа грамматик: порождающие и распознающие. Эти два типа грамматик аналогичны двум формам речи человека: распознающая грамматика аналогична импрессивной речи, а порождающая грамматика аналогична экспрессивной речи. Импрессивная (сенсорная) речь — это восприятие и понимание речи (В коре головного мозга имеется зона сенсорной речи, которая называется зоной Вернике.). Экспрессивная (моторная) речь — произнесение звуков речи самим человеком (В области второй и третьей лобной извилины головного мозга имеется зона моторной речи, которая называется зоной Брока. У правшей зона Брока находится в левом полушарии мозга, а у левшей в большинстве случаев — в правом.).

Под порождающей грамматикой языка L понимается конечный набор правил, позволяющий строить все «правильные» предложения языка L и ни одного «неправильного».

Распознающая грамматика задает критерий принадлежности произвольной цепочки данному языку. Это алгоритм, принимающий в качестве входа символ за символом произвольную цепочку над словарем V и дающий на выходе один из двух возможных ответов: «данная цепочка принадлежит языку L» либо «данная цепочка НЕ принадлежит языку L». В действительности этот алгоритм должен разделить все возможные входные цепочки на два класса: один – принадлежащие языку L, а другой – не принадлежащие языку L

Роль распознающей грамматики может выполнить конечный автомат (КА) без выхода. Если связать с некоторыми состояниями автомата метку «ДА», а с остальными метку «НЕТ», тогда все множество входных цепочек автомата разобьется на два класса: одни - приводящие автомат в одно из состояний, помеченных «ДА», а все другие в одно из состояний, помеченных «НЕТ».

Определим автомат-распознаватель формально.

ОПРЕДЕЛЕНИЕ: Конечным автоматом-распознавателем называется пятерка объектов:

ОПРЕДЕЛЕНИЕ: Конечный автомат-распознаватель 

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

Реализация распознающей и порождающей грамматик не ограничивается использованием конечных автоматов. Паттерн Interpreter дает возможность реализации распознающих и порождающих грамматик без использования «конечно-автоматного» подхода. Объектная структура грамматики, составленная и реализованная по правилам паттерна Interpreter «теоретически» эквивалентна по своей вычислительной мощи конечным автоматам (КА). В большинстве случаев предпочтительно использовать КА, но для очень (!) простых грамматик есть смысл использовать подход описываемый паттерном Interpreter. Для сложных грамматик иерархия классов становится слишком громоздкой и практически неуправляемой.

Важно помнить, что не все языки представимы конечными автоматами, а если язык не автоматный, то такой язык практически невозможно реализовать при помощи паттерна Interpreter. Поэтому прежде чем преступить к реализации грамматики определенного языка, требуется проверить, является ли этот язык автоматным. «Лемма о накачке», является важным «теоретическим инструментом» позволяющим во многих случаях проверить является ли язык автоматным (Лемма – это готовое доказательство теоремы, использующееся для доказательства других теорем). Термин «накачка» в названии леммы оттеняет возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.

Более формально лемма о накачке формулируется так:

Другая форма леммы о накачке, которую иногда удобно применять чтобы показать «неавтоматность» некоторого языка, записывается так:

Предлагается рассмотреть пример доказательства теоремы, устанавливающей неавтоматность конкретного языка, с помощью леммы о накачке:

Зададим для примера простой автоматный язык:

и построим для него конечный автомат.   Построим граф переходов автомата, распознающего L. Входные цепочки  и  (и только они) переводят автомат из начального, в одно из заключительных состояний S5  или S3

Структура паттерна на языке UML

См. пример к главе: \015_Interpreter\001_Interpreter

Структура паттерна на языке C#

См. пример к главе: \015_Interpreter\001_Interpreter

Участники

  • AbstractExpression - Абстрактное выражение:

Предоставляет абстрактный метод Interpret, который будет реализован во всех узлах абстрактного синтаксического дерева.

  • TerminalExpression - Терминальное выражение:

Реализует абстрактный метод Interpret для анализа терминальных символов грамматики, которые входят в словарь V. Для каждого терминального символа в предложении (буквы или слова) требуется создавать отдельный класс TerminalExpression.

  • NonterminalExpression - Нетерминальное выражение:

Представляет собой объектно-ориентированное представление правила R (Rule). Для каждого правила R = {R1, R2, … Rn} требуется создавать отдельный класс NonterminalExpression. Реализует абстрактный метод Interpret для работы с правилами (нетерминальными символами грамматики).

  • Context - Контекст:

Содержит в себе цепочки определенного языка и другую вспомогательную информацию требуемую для работы интерпретатора.

  • Client - Клиент:

Строит (или получает в готовом виде) абстрактное синтаксическое дерево, представляющее собой отдельное предложение на языке заданном определенной грамматикой. Дерево составляется из экземпляров классов TerminalExpression и NonterminalExpression.

Отношения между участниками

Отношения между классами

  • Класс Client связан связями отношения ассоциации с классами Context и AbstractExpression.
  • Класс TerminalExpression связан связью отношения наследования с абстрактным классом AbstractExpression.
  • Класс NonterminalExpression связан связью отношения наследования и связью отношения агрегации с абстрактным классом AbstractExpression.

Отношения между объектами

  • Клиент строит (или получает в готовом виде) абстрактное синтаксическое дерево, представляющее собой отдельное предложение на языке заданном определенной грамматикой. Дерево составляется из экземпляров классов TerminalExpression и NonterminalExpression

© 2017 ITVDN, все права защищены