Построение пользовательских деревьев выражений при использовании операторов в С#

Ответ 1

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

Примечание I

• демонстрируют только индексированные ссылочные выражения (таким образом, игнорируя косвенную адресацию через регистры, вы можете добавить RegisterInderectReference, аналогичную классу SymbolicReference). Это также говорит о том, что вы предложили функцию $ (текущее смещение). Вероятно, вероятно, что регистр (?)
• явно не показывает унарный/двоичный operator-. Однако механики в основном одинаковы. Я не стал добавлять его, потому что не смог выработать семантику выборочных выражений в вашем вопросе
  _{(я бы подумал, что вычитание адреса известной строки не полезно, например)суб >}
• подход не устанавливает (семантические) пределы: вы можете компенсировать любые IRB-запросы, связанные с базой данных. На практике вам может потребоваться только один уровень индексации, и определение operator+ непосредственно на SymbolicReference было бы более уместным.

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

• Демонстрация явного оператора преобразования действительно вне темы. Я увлекся слайдом (?)

• Вы можете увидеть код работающий на IdeOne.com

.

using System;
using System.Collections.Generic;
using System.Linq.Expressions;
using System.Linq;


namespace Assembler
{
    internal class State
    {
        public readonly IDictionary<string, ulong> SymbolTable = new Dictionary<string, ulong>();

        public void Clear() 
        {
            SymbolTable.Clear();
        }
    }

    internal interface IReference
    {
        ulong EvalAddress(State s); // evaluate reference to address
    }

    internal abstract class ReferenceBase : IReference
    {
        public static IndexedReference operator+(long directOffset, ReferenceBase baseRef) { return new IndexedReference(baseRef, directOffset); }
        public static IndexedReference operator+(ReferenceBase baseRef, long directOffset) { return new IndexedReference(baseRef, directOffset); }

        public abstract ulong EvalAddress(State s);
    }

    internal class SymbolicReference : ReferenceBase
    {
        public static explicit operator SymbolicReference(string symbol)    { return new SymbolicReference(symbol); }
        public SymbolicReference(string symbol) { _symbol = symbol; }

        private readonly string _symbol;

        public override ulong EvalAddress(State s) 
        {
            return s.SymbolTable[_symbol];
        }

        public override string ToString() { return string.Format("Sym({0})", _symbol); }
    }

    internal class IndexedReference : ReferenceBase
    {
        public IndexedReference(IReference baseRef, long directOffset) 
        {
            _baseRef = baseRef;
            _directOffset = directOffset;
        }

        private readonly IReference _baseRef;
        private readonly long _directOffset;

        public override ulong EvalAddress(State s) 
        {
            return (_directOffset<0)
                ? _baseRef.EvalAddress(s) - (ulong) Math.Abs(_directOffset)
                : _baseRef.EvalAddress(s) + (ulong) Math.Abs(_directOffset);
        }

        public override string ToString() { return string.Format("{0} + {1}", _directOffset, _baseRef); }
    }
}

namespace Program
{
    using Assembler;

    public static class Program
    {
        public static void Main(string[] args)
        {
            var myBaseRef1 = new SymbolicReference("mystring1");

            Expression<Func<IReference>> anyRefExpr = () => 64 + myBaseRef1;
            Console.WriteLine(anyRefExpr);

            var myBaseRef2 = (SymbolicReference) "mystring2"; // uses explicit conversion operator

            Expression<Func<IndexedReference>> indexedRefExpr = () => 64 + myBaseRef2;
            Console.WriteLine(indexedRefExpr);

            Console.WriteLine(Console.Out.NewLine + "=== show compiletime types of returned values:");
            Console.WriteLine("myBaseRef1     -> {0}", myBaseRef1);
            Console.WriteLine("myBaseRef2     -> {0}", myBaseRef2);
            Console.WriteLine("anyRefExpr     -> {0}", anyRefExpr.Compile().Method.ReturnType);
            Console.WriteLine("indexedRefExpr -> {0}", indexedRefExpr.Compile().Method.ReturnType);

            Console.WriteLine(Console.Out.NewLine + "=== show runtime types of returned values:");
            Console.WriteLine("myBaseRef1     -> {0}", myBaseRef1);
            Console.WriteLine("myBaseRef2     -> {0}", myBaseRef2);
            Console.WriteLine("anyRefExpr     -> {0}", anyRefExpr.Compile()());     // compile() returns Func<...>
            Console.WriteLine("indexedRefExpr -> {0}", indexedRefExpr.Compile()());

            Console.WriteLine(Console.Out.NewLine + "=== observe how you could add an evaluation model using some kind of symbol table:");
            var compilerState = new State();
            compilerState.SymbolTable.Add("mystring1", 0xdeadbeef); // raw addresses
            compilerState.SymbolTable.Add("mystring2", 0xfeedface);

            Console.WriteLine("myBaseRef1 evaluates to     0x{0:x8}", myBaseRef1.EvalAddress(compilerState));
            Console.WriteLine("myBaseRef2 evaluates to     0x{0:x8}", myBaseRef2.EvalAddress(compilerState));
            Console.WriteLine("anyRefExpr displays as      {0:x8}",   anyRefExpr.Compile()());
            Console.WriteLine("indexedRefExpr displays as  {0:x8}",   indexedRefExpr.Compile()());
            Console.WriteLine("anyRefExpr evaluates to     0x{0:x8}", anyRefExpr.Compile()().EvalAddress(compilerState));
            Console.WriteLine("indexedRefExpr evaluates to 0x{0:x8}", indexedRefExpr.Compile()().EvalAddress(compilerState));
        }
    }
}

Ответ 2

С# поддерживает назначение лямбда-выражения для Expression<TDelegate>, что заставит компилятор испускать код для создания дерева выражений, представляющего выражение лямбда, которое вы затем можете манипулировать. Например:.

Expression<Func<int, int, int>> times = (a, b) => a * b;

Затем вы могли бы взять сгенерированное дерево выражений и преобразовать его в свое дерево синтаксиса ассемблера, но это, похоже, не совсем то, что вы ищете, и я не думаю, что вы сможете для использования компилятора С# для этого для произвольного ввода.

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

Ответ 3

Опять же, не совсем уверен, что это именно то, что вы ищете, но из начальной точки захотелось создать какое-то дерево выражений с помощью синтаксиса С#, я придумал...

public abstract class BaseExpression
{
    // Maybe a Compile() method here?
}

public class NumericExpression : BaseExpression
{
    public static NumericExpression operator +(NumericExpression lhs, NumericExpression rhs)
    {
        return new NumericAddExpression(lhs, rhs);
    }

    public static NumericExpression operator -(NumericExpression lhs, NumericExpression rhs)
    {
        return new NumericSubtractExpression(lhs, rhs);
    }

    public static NumericExpression operator *(NumericExpression lhs, NumericExpression rhs)
    {
        return new NumericMultiplyExpression(lhs, rhs);
    }

    public static NumericExpression operator /(NumericExpression lhs, NumericExpression rhs)
    {
        return new NumericDivideExpression(lhs, rhs);
    }

    public static implicit operator NumericExpression(int value)
    {
        return new NumericConstantExpression(value);
    }

    public abstract int Evaluate(Dictionary<string,int> symbolTable);
    public abstract override string ToString();
}

public abstract class NumericBinaryExpression : NumericExpression
{
    protected NumericExpression LHS { get; private set; }
    protected NumericExpression RHS { get; private set; }

    protected NumericBinaryExpression(NumericExpression lhs, NumericExpression rhs)
    {
        LHS = lhs;
        RHS = rhs;
    }

    public override string ToString()
    {
        return string.Format("{0} {1} {2}", LHS, Operator, RHS);
    }
}

public class NumericAddExpression : NumericBinaryExpression
{
    protected override string Operator { get { return "+"; } }

    public NumericAddExpression(NumericExpression lhs, NumericExpression rhs)
        : base(lhs, rhs)
    {
    }

    public override int Evaluate(Dictionary<string,int> symbolTable)
    {
        return LHS.Evaluate(symbolTable) + RHS.Evaluate(symbolTable);
    }
}

public class NumericSubtractExpression : NumericBinaryExpression
{
    protected override string Operator { get { return "-"; } }

    public NumericSubtractExpression(NumericExpression lhs, NumericExpression rhs)
        : base(lhs, rhs)
    {
    }

    public override int Evaluate(Dictionary<string, int> symbolTable)
    {
        return LHS.Evaluate(symbolTable) - RHS.Evaluate(symbolTable);
    }
}

public class NumericMultiplyExpression : NumericBinaryExpression
{
    protected override string Operator { get { return "*"; } }

    public NumericMultiplyExpression(NumericExpression lhs, NumericExpression rhs)
        : base(lhs, rhs)
    {
    }

    public override int Evaluate(Dictionary<string, int> symbolTable)
    {
        return LHS.Evaluate(symbolTable) * RHS.Evaluate(symbolTable);
    }
}

public class NumericDivideExpression : NumericBinaryExpression
{
    protected override string Operator { get { return "/"; } }

    public NumericDivideExpression(NumericExpression lhs, NumericExpression rhs)
        : base(lhs, rhs)
    {
    }

    public override int Evaluate(Dictionary<string, int> symbolTable)
    {
        return LHS.Evaluate(symbolTable) / RHS.Evaluate(symbolTable);
    }
}

public class NumericReferenceExpression : NumericExpression
{
    public string Symbol { get; private set; }

    public NumericReferenceExpression(string symbol)
    {
        Symbol = symbol;
    }

    public override int Evaluate(Dictionary<string, int> symbolTable)
    {
        return symbolTable[Symbol];
    }

    public override string ToString()
    {
        return string.Format("Ref({0})", Symbol);
    }
}

public class StringConstantExpression : BaseExpression
{
    public string Value { get; private set; }

    public StringConstantExpression(string value)
    {
        Value = value;
    }

    public static implicit operator StringConstantExpression(string value)
    {
        return new StringConstantExpression(value);
    }
}

public class NumericConstantExpression : NumericExpression
{
    public int Value { get; private set; }

    public NumericConstantExpression(int value)
    {
        Value = value;
    }

    public override int Evaluate(Dictionary<string, int> symbolTable)
    {
        return Value;
    }

    public override string ToString()
    {
        return Value.ToString();
    }
}

Теперь очевидно, что ни один из этих классов фактически ничего не делает (вам, вероятно, понадобится метод Compile() там среди других), и не все операторы реализованы, и вы можете, очевидно, сократить имена классов, чтобы сделать его более кратким и т.д., но это позволяет вам делать такие вещи, как:

var result = 100 * new NumericReferenceExpression("Test") + 50;

После чего result будет:

NumericAddExpression
- LHS = NumericMultiplyExpression
        - LHS = NumericConstantExpression(100)
        - RHS = NumericReferenceExpression(Test)
- RHS = NumericConstantExpression(50)

Это не совсем идеально - если вы используете неявные преобразования числовых значений в NumericConstantExpression (вместо явного их литья/построения), то в зависимости от упорядочения ваших условий некоторые вычисления могут выполняться встроенным в операторы, и вы получите только полученный результат (вы можете просто назвать это "оптимизацией времени компиляции"!)

Чтобы показать, что я имею в виду, если вы должны были запустить это:

var result = 25 * 4 * new NumericReferenceExpression("Test") + 50;

в этом случае 25 * 4 оценивается с использованием встроенных целочисленных операторов, поэтому результат фактически идентичен приведенному выше, вместо того, чтобы создавать дополнительный NumericMultiplyExpression с двумя NumericConstantExpression (25 и 4) на LHS и RHS.

Эти выражения могут быть напечатаны с использованием ToString() и оценены, если вы предоставили таблицу символов (здесь просто Dictionary<string, int>):

var result = 100 * new NumericReferenceExpression("Test") + 50;
var symbolTable = new Dictionary<string, int>
{
    { "Test", 30 }
};
Console.WriteLine("Pretty printed: {0}", result);
Console.WriteLine("Evaluated: {0}", result.Evaluate(symbolTable));

Результаты в:

Pretty printed: 100 * Ref(Test) + 50
Evaluated: 3050

Надеюсь, несмотря на упомянутый недостаток, это что-то приближается к тому, что вы искали (или я просто потратил впустую последние полчаса!)

Ответ 4

Вы реализуете двухэтапный (pass?) ассемблер? Назначение двухпроходного ассемблера - обрабатывать прямые ссылки (например, символ undefined при первом обнаружении).

Тогда вам в значительной степени не нужно создавать дерево выражений.

В фазе (проход 1) вы анализируете исходный текст (любыми способами: ad hoc parser, рекурсивный спуск, генератор парсера) и собираете значения символов (в частности, относительные значения меток относительно кода или данных, в которых они содержатся.Если вы сталкиваетесь с выражением, вы пытаетесь оценить его с помощью экспресс-проверки на лету, как правило, с использованием стека push down для подвыражений и получения окончательного результата. Если вы столкнулись с символом значение которого undefined, вы распространяете неопределенность как результат выражения. Если оператору/команде сборки требуется значение выражения для определения символа (например, X EQU A + 2) или для определения смещений в секцию кода/данных (например, DS X + 23), тогда значение должно быть определено или сборщик выдает ошибку. Это позволяет работать с ORG A + BC. Другие операторы сборки, которые не нуждаются в значении во время прохождения, просто игнорируют undefined результат (например, LOAD ABC не волнует, что такое ABC, но может определить удлинение h инструкции LOAD).

В фазе (проход II) вы повторно разбираете код таким же образом. На этот раз все символы имеют значения, поэтому все выражения должны оцениваться. Те, которые должны были иметь значение в Фазе I, проверяются на значения, полученные в Фазе II, чтобы убедиться, что они идентичны (иначе вы получите ошибку PHASE). Другие операторы/инструкции для сборки теперь имеют достаточную информацию для генерации фактических машинных инструкций или инициализаций данных.

Дело в том, что вам никогда не нужно строить дерево выражений. Вы просто оцениваете выражение, когда сталкиваетесь с ним.

Если вы построили однопроходный ассемблер, вам может потребоваться смоделировать выражение, чтобы позднее было переоценено. Мне было легче создать обратный полиш в виде последовательности "значение PUSH" и арифпопа и сохранить последовательность (эквивалентную дереву выражения), поскольку она плотная (деревья нет) и тривиальна для оценки путем выполнения линейного сканирования с использованием ( как указано выше) небольшой пакет выталкивания.

Фактически то, что я сделал, это создать обратный польский, который фактически действовал как сам стек выражения; во время линейного сканирования, если бы операнды могли быть оценены, они были заменены командой "PUSH value", а оставшаяся обратная полировка была сжата для удаления пузыря. Это не дорого, потому что большинство выражений на самом деле крошечные. И это означало, что любое выражение, которое нужно было сохранить для последующей оценки, было как можно меньше. Если вы пронумеровали команды идентификатора PUSH через таблицу символов, тогда, когда в качестве символа станет определено, вы можете заполнить все частично оцененные выражения и переоценить их; те, которые производят одно значение, затем обрабатываются и их пространство перерабатывается. Это позволило мне собрать гигантские программы в 4-килобайтном слове, 16-битной машине, еще в 1974 году, потому что большинство прямых ссылок на самом деле не очень далеко.