Что входит
Паттерн Интерпретатор относится к Поведенческим паттернам проектирования. Данный паттерн позволяет реализовать свой язык программирования, путем работы с AST древом, вершины которого представляют из себя терминальные и нетерминальные выражения, реализующие метод Interpret, обеспечивающий функционал языка.
- Терминальное выражение – например константа строки – “Hello World”
- Нетерминальное выражение – например Print(“Hello World”), содержит Print и аргумент из Терминального выражения “Hello World”
В чем разница? Разница в том что интерпретирование на терминальных выражениях заканчивается, а для нетерминальных продолжается вглубь по всем входящим вершинам/аргументам. Если бы AST древо состояло только из нетерминальных выражений, то выполнение приложения никогда бы не завершилось, т.к. требуется некая конечность любого процесса, этой конечность и выступают терминальные выражения, они обычно содержат данные, например строки.
Пример AST древа ниже:
Dcoetzee, CC0, via Wikimedia Commons
Как можно увидеть, терминальные выражения – constant и variable, нетерминальные – остальные.
Что не входит
В реализацию Интерпретатора не входит парсинг строкового ввода языка в AST-древо. Достаточно реализовать классы терминальных, нетерминальных выражений, методы Interpret с аргументом Контекст на входе, оформить AST древо из выражений, запустить у корневого выражения метод Interpret. Контекст можно использовать для того чтобы хранить состояние приложения во время выполнения.
Реализация
В паттерне участвуют:
- Клиент – отдает AST-древо и запускает Interpret(context) для корневой вершины (Client)
- Контекст – содержит состояние приложения, передается выражениям при интерпретации (Context)
- Абстрактное выражение – абстрактный класс содержащий метод Interpret(context) (Expression)
- Терминальное выражение – конечное выражение, потомок абстрактного выражения (TerminalExpression)
- Нетерминальное выражение – не конечное выражение, содержит указатели на вершины вглубь AST-древа, подчиненные вершины обычно влияют на результат интерпретации нетерминального выражения (NonTerminalExpression)
Пример Клиента на C#
class Application {
static void Main(string[] args)
{
var context = new Context();
var initialProgram = new PerformExpression(
new IExpression[] {
new SetExpression("alpha", "1"),
new GetExpression("alpha"),
new PrintExpression(
new IExpression[] {
new ConstantExpression("Hello Interpreter Pattern")
}
)
}
);
System.Console.WriteLine(initialProgram.interpret(context));
}
}
Пример Абстрактного выражения на C#
interface IExpression
{
String interpret(Context context);
}
Пример Терминального выражения на C# (Строковая константа)
class ConstantExpression : TerminalExpression
{
private String constant;
public ConstantExpression(String constant) {
this.constant = constant;
}
override public String interpret(Context context) {
return constant;
}
}
Пример Нетерминального выражения на C# (Запуск и конкатенация результатов подчиненных вершин, с использованием разделителя «;»
class PerformExpression : NonTerminalExpression
{
public PerformExpression(IExpression[] leafs) : base(leafs) {
this.leafs = leafs;
}
override public String interpret(Context context) {
var output = "";
foreach (var leaf in leafs) {
output += leaf.interpret(context) + ";";
}
return output;
}
}
Функционально сможешь?
Как известно все Тьюринг-полные языки эквивалентны. Можно ли перенести Объектно-Ориентированный паттерн на язык Функционального программирования?
Можно, для эксперимента возьмем ФП язык для веба под названием Elm. В Elm нет классов, но есть Записи (Records) и Типы (Types) поэтому в реализации участвуют следующие записи и типы:
- Выражение – перечисление всех возможных выражений языка (Expression)
- Подчиненное выражение – выражение являющееся подчиненным по отношению к Нетерминальному выражению (ExpressionLeaf)
- Контекст – запись хранящая состояние приложения (Context)
- Функции реализующие методы Interpret(context) – все необходимые функции реализующие функционал Терминальных, Нетерминальных выражений
- Вспомогательные записи состояния Интерпретатора – необходимы для корректной работы Интерпретатора, хранят состояние Интерпретатора, контекст
Пример функции реализующей интерпретацию для всего набора возможных выражений на Elm:
run input =
case input.expression of
Constant text ->
{
output = text,
context = input.context
}
Perform leafs ->
let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
{
output = (runExpressionLeaf outputExpressionInput).output,
context = input.context
}
Print printExpression ->
run
{
expression = printExpression,
context = input.context
}
Set key value ->
let variables = Dict.insert key value input.context.variables in
{
output = "OK",
context = { variables = variables }
}
Get key ->
{
output = Maybe.withDefault ("No value for key: " ++ key) (Dict.get key input.context.variables),
context = input.context
}
А парсить?
Парсинг исходного кода в AST-древо не входит в паттерн Интерпретатор, существует несколько подходов для парсинга исходного кода, но об этом как-нибудь в другой раз.
В реализации Интерпретатора для Elm я написал простейший парсер в AST-древо, состоящий из двух функций – парсинг вершины, парсинг подчиненных вершин.
parseLeafs: ParseLeafsState -> ParseLeafsState
parseLeafs state =
let tokensQueue = state.tokensQueue in
let popped = pop state.tokensQueue in
let tokensQueueTail = tail state.tokensQueue in
if popped == "Nothing" then
state
else if popped == "Perform(" then
{
tokensQueue = tokensQueue,
result = (state.result ++ [Node (parse tokensQueue)])
}
else if popped == ")" then
parseLeafs {
tokensQueue = tokensQueueTail,
result = state.result
}
else if popped == "Set" then
let key = pop tokensQueueTail in
let value = pop (tail tokensQueueTail) in
parseLeafs {
tokensQueue = tail (tail tokensQueueTail),
result = (state.result ++ [Node (Set key value)])
}
else if popped == "Get" then
let key = pop tokensQueueTail in
parseLeafs {
tokensQueue = tail tokensQueueTail,
result = (state.result ++ [Node (Get key)])
}
else
parseLeafs {
tokensQueue = tokensQueueTail,
result = (state.result ++ [Node (Constant popped)])
}
parse tokensQueue =
let popped = pop tokensQueue in
let tokensQueueTail = tail tokensQueue in
if popped == "Perform(" then
Perform (
parseLeafs {
tokensQueue = tokensQueueTail,
result = []
}
).result
else if popped == "Set" then
let key = pop tokensQueueTail in
let value = pop (tail tokensQueueTail) in
Set key value
else if popped == "Print" then
Print (parse tokensQueueTail)
else
Constant popped
Ссылки
https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/csharp
Источники
https://en.wikipedia.org/wiki/Interpreter_pattern
https://elm-lang.org/
https://docs.microsoft.com/en-us/dotnet/csharp/