Шаблон "интерпретатор"

@Kujivunia · Регистрация: 12.01.2017

Студворк — интернет-сервис помощи студентам

Я захотел написать небольшой интерпретатор логических выражений, используя шаблон, собственно, "интерпретатор".

Как я понял, этот шаблон состоит из интерфейса АбстрактногоВыражения, от которого наследуются ПравилаГрамматики и Терминалы. В интерфейсе определён метод Интерпретация(контекст).
Дерево такого выражения создаётся в Клиенте, и Клиент же отправляет в качестве контекста то, что нужно проинтерпретировать.

Получается, что дерево Выражения это формула, а Контекст - это подставляемые в формулу значения? Я правильно всё понимаю?

У меня получилось так:
ДеревоВыражения состоит из операторИ, операторИЛИ, операторНЕ и Терминал.
Логические значения терминалов -- это найдено ли слово, сохранённое в поле Терминала, среди всех слов подаваемого в дерево Контекста.

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public class TerminalExpression : IBinaryExpression
    {
        public TerminalExpression(string Token)
        {
            this.Token = Token;
        }
        public string Token { get; set; }
        public bool Search(List<string> Tags)
        {
            if (Tags.Contains(Token)) 
                return true; 
            else 
                return false;
 
        }
    }

А это диаграмма классов того, что я считаю своей реализацией шаблона: ссылка на изображение

Ну и, соответственно, все правила просто вызывают Интерпретация(контекст) своих детей.
В итоге корень возвращает, соответствует ли набор меток формуле. Что-то в духе
Выражение, из которого строится дерево: a && (b || !c)
Контекст/ответ: a/false (a,b)/true (a,c,e)/false

Меня всё вроде бы устраивает, ведь эта штука делает то, чего я от неё добивался.
Но потом я поговорил с одним человеком, и меня заставили сомневаться. Я так и не понял, что именно не так, но из того что я понял следовало, что я понимаю Контекст неправильно, что это должно быть чем-то иным.

Так что вопрос: правильно ли я понял этот шаблон в целом, и значение (Контекст) в нём в частности?

@Shamil1 · 21.12.2020, 11:48

Не похоже на Интерпретатор.

@Kujivunia · 21.12.2020, 15:52 **[ТС]**

Почему? Что я не так то сделал?
https://i.ya-webdesign.com/ima... ram-19.png

@vantfiles · 21.12.2020, 17:47

Сообщение от Kujivunia

небольшой интерпретатор логических выражений

Мне кажется это вот тот самый пример неверного применения ООП и шаблонов.

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

https://ru.wikipedia.org/wiki/... кая_запись

@Kujivunia · 21.12.2020, 21:30 **[ТС]**

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

Так что вопрос из поста остаётся в силе: правильно ли я понял этот шаблон в целом, и значение (Контекст) в нём в частности?

@Shamil1 · 22.12.2020, 10:57

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

@Kujivunia · 22.12.2020, 11:12 **[ТС]**

И? К чему эта ссылка вообще?

@vrm2 · 22.12.2020, 20:00

Сообщение от Kujivunia

Но потом я поговорил с одним человеком, и меня заставили сомневаться. Я так и не понял, что именно не так, но из того что я понял следовало, что я понимаю Контекст неправильно, что это должно быть чем-то иным.
Так что вопрос: правильно ли я понял этот шаблон в целом, и значение (Контекст) в нём в частности?

Зависит от того, что это за логические выражения. Похоже, ты делаешь интерпретатор логических выражений для поиска слов в тексте. Если это так, то ты все понял правильно.

Терминальное выражение ищет конкретное слово (у тебя это Token) в списке всех слов (у тебя это список тегов Tags). Контекст в данном случае - список всех слов, среди которых производится поиск (List<string> Tags).

Ну и надо написать интерпретаторы для других выражений - операторИ, операторИЛИ, операторНЕ.

@Kujivunia · 22.12.2020, 21:54 **[ТС]**

Ну и надо написать интерпретаторы для других выражений - операторИ, операторИЛИ, операторНЕ.

Ага, есть такие:

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    public class Disjunction : IBinaryExpression //ИЛИ
    {
        public Disjunction(IBinaryExpression l = null, IBinaryExpression r = null)
        {
            this.l = l;
            this.r = r;
        }
        public IBinaryExpression l { get; set; }
        public IBinaryExpression r { get; set; }
        public bool Search(List<string> Tags)
        {
            return l.Search(Tags) || r.Search(Tags);
        }
    }

Я в основном посте написал только код терминала, потому что он "ближе" всего к теме Контекста -- остальное только оперирует тем, что получено снизу (от терминалов и других низ лежащих операторов).

Терминальное выражение ищет конкретное слово (у тебя это Token) в списке всех слов (у тебя это список тегов Tags). Контекст в данном случае - список всех слов, среди которых производится поиск (List<string> Tags).

Получается, что Контекст -- это нечто вроде словаря того языка, на который я пытаюсь интерпретировать, операторы это грамматика, операнды/терминалы это слова на чужом языке, а выход -- это перевод?
Т.е.
Зависимость
/ \
Blue water
|
v
Для токенов поиск в словаре пары eng/рус (голубой/вода)
Токены возвращают голубой/вода
Оператор зависимости выставляет их в правильном виде: голуб-ая вода
И если я в качестве контекста подам вместо аглорусского словаря англокитайский, то будет перевод на китайский язык (допустим, что грамматика у них одинаковая)

@vrm2 · 22.12.2020, 22:12

Сообщение от Kujivunia

И если я в качестве контекста подам вместо аглорусского словаря англокитайский, то будет перевод на китайский язык (допустим, что грамматика у них одинаковая)

Да.

@vantfiles · 23.12.2020, 00:13

Насколько я помню теорию формальных языков... Поясню как сам понимаю...

Есть терминальные выражения - это такие элементарные выражения/слова из которых в дальнейшем строятся нетерминальные выражения - то есть составные.

Например слова 'мама', 'мыла', 'раму' + пробел - это терминальные выражения, а предложение 'мама мыла раму' - нетерминальное выражение.

Зачем нужен контекст. Затем что как правило нетерминалы могут менять ход дальнейшей интерпретации.

Например:

int aaa bbb ccc -- объявление трех переменных
str abc "aaa bbb ccc" -- объявление строки.

здесь терминал "кавычка" изменил контекст интерпретации входного текста

Добавлено через 2 минуты
Причем контекстов может быть много, более того, они еще и вложенными могут быть. Вот для этого в этом паттерне и нужен целый класс для управления контекстами.

Добавлено через 1 час 19 минут
простой пример двойного переключения контекста - строки с экранирующими символами:

"Шла\nШура\nПо\nШоссе"

@vrm2 · 23.12.2020, 14:15

Сообщение от vantfiles

int aaa bbb ccc -- объявление трех переменных
str abc "aaa bbb ccc" -- объявление строки.

здесь терминал "кавычка" изменил контекст интерпретации входного текста

В этих примерах речь идет не про интепретацию, а про парсинг.

На этапе парсинга мы превращаем выражение (исходный текст программы, поисковый запрос) в абстрактное синтаксическое дерево (AST) на основе грамматики.

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

Хотя, наверное, можно рассматривать парсинг как интерпретацию списка токенов, и получить в результате AST.

Добавлено через 10 минут

Сообщение от Kujivunia

Получается, что Контекст -- это нечто вроде словаря того языка, на который я пытаюсь интерпретировать, операторы это грамматика, операнды/терминалы это слова на чужом языке, а выход -- это перевод?

Вообще, это верно только для задачи "перевода". В другой задаче контекст будет иной.

Например, для интерпретатора языка python контекстом будет являться значения и типы переменных, список функций и т.п.
Более того, этот контекст может менять по ходу интепретации, например, добавляться и удаляться переменные.

Контекст должен содержать текущую информацию для правильной интерпретации выражения.

@Shamil1 · 23.12.2020, 17:05

Сообщение от Kujivunia

Почему? Что я не так то сделал?

Согласно паттерну у Вас должны быть классы-интерпретаторы, реализующие метод Интерпретировать (этот метод принимет Контекст). У Вас же совсем другие методы.

Сообщение от Kujivunia

И? К чему эта ссылка вообще?

По ссылке можно посмотреть, как должен выглядеть паттерн Интерпретатор.

Вот это можно прямо скопировать в свой код и взять за основу:

C#
1
2
3
4
5
6
7
8
class Context
{
}
 
abstract class AbstractExpression
{
    public abstract void Interpret(Context context);
}

Можно (но не обязательно) так же добавить абстрактные классы NonterminalExpression и TerminalExpression просто для удобства чтения кода.

@vantfiles · 23.12.2020, 17:10

Сообщение от Shamil1

классы NonterminalExpression и TerminalExpression

А разве они не наследуются от AbstractExpression в обязательном порядке?

@Shamil1 · 24.12.2020, 11:53

Сообщение от vantfiles

А разве они не наследуются от AbstractExpression в обязательном порядке?

В примере по ссылке NonterminalExpression и TerminalExpression - это конкретные классы. В реальном примере вместо них могли, например, быть AdditionExpression и ConstantExpression. Но можно добавить дополнительный слой - абстрактные классы NonterminalExpression и TerminalExpression (наследники AbstractExpression), от которых наследовать все терминалы и все нетерминалы соответственно.

@vrm2 · 24.12.2020, 12:09

Сообщение от Shamil1

Согласно паттерну у Вас должны быть классы-интерпретаторы, реализующие метод Интерпретировать (этот метод принимет Контекст). У Вас же совсем другие методы.

Не согласен. Суть (идея) паттерна сохранилась, несмотря на названия методов и классов.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,884
	21.12.2020, 11:48
	Не похоже на Интерпретатор. 0

@Kujivunia 0 / 0 / 1 Регистрация: 12.01.2017 Сообщений: 104
	21.12.2020, 15:52 [ТС]
	Почему? Что я не так то сделал? https://i.ya-webdesign.com/ima... ram-19.png 0

@Kujivunia 0 / 0 / 1 Регистрация: 12.01.2017 Сообщений: 104
	21.12.2020, 21:30 [ТС]
	Это замечательный способ, и я его даже видел, но я пишу лабу, и обязательно использование шаблона. Услышав про поисковый запрос, препод сразу сказал, что можно использовать Интерпретатора. Так что вопрос из поста остаётся в силе: правильно ли я понял этот шаблон в целом, и значение (Контекст) в нём в частности? 0

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,884
	22.12.2020, 10:57
	Интерпретатор 1

@Kujivunia 0 / 0 / 1 Регистрация: 12.01.2017 Сообщений: 104
	22.12.2020, 11:12 [ТС]
	И? К чему эта ссылка вообще? 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	23.12.2020, 00:13
	Насколько я помню теорию формальных языков... Поясню как сам понимаю... Есть терминальные выражения - это такие элементарные выражения/слова из которых в дальнейшем строятся нетерминальные выражения - то есть составные. Например слова 'мама', 'мыла', 'раму' + пробел - это терминальные выражения, а предложение 'мама мыла раму' - нетерминальное выражение. Зачем нужен контекст. Затем что как правило нетерминалы могут менять ход дальнейшей интерпретации. Например: int aaa bbb ccc -- объявление трех переменных str abc "aaa bbb ccc" -- объявление строки. здесь терминал "кавычка" изменил контекст интерпретации входного текста Добавлено через 2 минуты Причем контекстов может быть много, более того, они еще и вложенными могут быть. Вот для этого в этом паттерне и нужен целый класс для управления контекстами. Добавлено через 1 час 19 минут простой пример двойного переключения контекста - строки с экранирующими символами: "Шла\nШура\nПо\nШоссе" 1

Шаблон "интерпретатор"

Решение