Использование шаблона интерпретатора на композитной структуре

Меня попросили сделать оценщика выражений, используя Composite, Recursive Descendent Parser и Interpreter.

Здесь грамматика:

<cond> → <termb> [OR <termb>]*
<termb>→<factb>[AND <factb>]*
<factb>→<expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → [PLUS | MINUS] <term> [(PLUS <term>) | (MINUS <term>)]*
<term> → <termp> [(MULT <termp>) | (DIV <termp>) | (REM <termp>)]*
<termp> → <fact> [POWER <fact>]*
<fact> → ID | NUM | OPAR1 <expr> CPAR1
----TERMINALS----
ID → ("A" | ... | "Z" | "a" | ...| "z") [("A"| ... | "Z" | "a" | ...| "z" | "0" | ... | "9")]*
NUM → ("0" | ... | "9") [("0" | ... | "9")]*
OPAR → "("
CPAR → ")"
OPAR1 → "["
CPAR1 → "]"
RELOP → EQ | NEQ | GT | GE | LT | LE
EQ → "= ="
NEQ → "!="
GT → ">"
GE → ">="
LT → "<"
LE → "<="
POWER → "^"
DIV → "/"
REM → "%"
MULT → "*"
MINUS → "−"
PLUS → "+"
AND → "and" or "&&"
OR → "or" or "||"
NOT → "not" or "!"

Назначение:

Цель проекта, основанная на Composite, Recursive Builder и Интерпретатор, должен получить условное выражение, выполнить синтаксический анализ и построить его составное дерево. Начиная с дерева, вы должны оценивать результат условия на основе внешнего контекста (чтение из файла свойств), который содержит значение внутреннего Переменные

Теперь первое, что я заметил, это то, что Interpreter использует композитную структуру, поэтому было бы неплохо расширить мою структуру Composite с помощью метода оценки (: Контекст).

Я спросил, но мне сказали, что это не способ выполнить задание. Похоже, что у меня построено дерево интерпретаторов, начиная с Composite (что для меня совершенно бессмысленно, поскольку у меня уже есть дерево для работы!).

Итак, я построил свое дерево с помощью Composite + Recursive Builder, он распознает вход и строит дерево без каких-либо проблем.

Но возникает вопрос: как применить интерпретатор к моей структуре?

Здесь моя диаграмма классов (что-то итальянское, но это вполне понятно)

Если я правильно понял, Interpreter использует класс для каждого правила грамматики, поэтому мне нужно сделать cond-класс, затем termb и т.д.

Но я привязываю их к своему композиту?

Ответ 1

Не знаю, почему вам сказали не использовать одну и ту же древовидную структуру. Я думаю, что я бы добавил метод compare() в свой интерфейс выражения. Это имеет смысл для меня. Выражение должно знать, как оценивать себя.

Я бы сказал, что ваш текущий интерфейс выражения слишком много (например, операнды). Как клиент выражения, мне нужно только 1) вызвать его и 2) прочитать результат, и я думаю, возможно 3) напечатать его. На самом деле, я бы предпочел использовать toString() для прямой печати.

Вы, наверное, уже заметили, но не все выражения принимают 2 операнда (например, NOT или NEGATE). Это уже создает своего рода несоответствие с вашим интерфейсом. Я бы упростил это:

 public interface Expression {
   int evaluate();
 }

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

Таким образом, я мог бы иметь конкретные операции, например:

 public class Terminal implements Expression {
   private final int value;

   public Terminal(int value) { this.value = value; }

   public int evaluate() { return value; }

   public String toString() { return String.valueOf(value); }
 }

 public class Add implements Expression {
   private final Expression left;
   private final Expression right;

   public Add(Expression left, Expression right) {
     this.left = left;
     this.right = right;
   }

   public String toString() {
     return left.toString() + " + " + right.toString();
   }

   // leave the rest for you
 }

Теперь я могу легко построить дерево

Expression expr = new Add(new Terminal(1), new Subtract(new Terminal(2), new Terminal(3)));

int result = expr.evaluate();
System.out.print(expr.toString() + " = " + result);

И мне даже не нужен прямой доступ к отдельным операндам.

Ответ 2

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

Если выражение является основным составным, тогда:

Выражение: срок Выражение: OperandTerm

Условие: Term BinOperand Expression Условие: UnaryOperand Expression

Срок: Int | Foat | ...

. , .

Ответ 3

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

Возможно, вам не нужно создавать один класс для терминального и конечного элементов, использовать атрибуты типа (operatorType, expressionType) в терминах NonTerminal/Terminal, чтобы отличаться от ваших символов грамматики.

Учитывая и выраженное с вашей грамматикой выражение [A = 0], дерево объектов, сформированное с помощью классов шаблонов интерпретатора, будет выглядеть так (прошу простить за плохое качество и ошибки UML sintax, но у меня нет подходящего редактора UML ):

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

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

Надеюсь на эту помощь.