Ответ 1
Хорошо, пусть построит простой пример математики. Построение АСТ полностью переборщило с такой задачей, но это хороший способ показать принцип.
Я сделаю это на С#, но версия Java будет очень похожа.
Грамматика
Во-первых, напишите очень основную математическую грамматику для работы с:
grammar Math;
compileUnit
: expr EOF
;
expr
: '(' expr ')' # parensExpr
| op=('+'|'-') expr # unaryExpr
| left=expr op=('*'|'/') right=expr # infixExpr
| left=expr op=('+'|'-') right=expr # infixExpr
| func=ID '(' expr ')' # funcExpr
| value=NUM # numberExpr
;
OP_ADD: '+';
OP_SUB: '-';
OP_MUL: '*';
OP_DIV: '/';
NUM : [0-9]+ ('.' [0-9]+)? ([eE] [+-]? [0-9]+)?;
ID : [a-zA-Z]+;
WS : [ \t\r\n] -> channel(HIDDEN);
Довольно простой материал, у нас есть одно правило expr, которое обрабатывает все (правила приоритета и т.д.).
Узлы AST
Затем определим некоторые AST-узлы, которые мы будем использовать. Они полностью настраиваются, и вы можете определить их так, как вы хотите.
Вот узлы, которые мы будем использовать для этого примера:
internal abstract class ExpressionNode
{
}
internal abstract class InfixExpressionNode : ExpressionNode
{
public ExpressionNode Left { get; set; }
public ExpressionNode Right { get; set; }
}
internal class AdditionNode : InfixExpressionNode
{
}
internal class SubtractionNode : InfixExpressionNode
{
}
internal class MultiplicationNode : InfixExpressionNode
{
}
internal class DivisionNode : InfixExpressionNode
{
}
internal class NegateNode : ExpressionNode
{
public ExpressionNode InnerNode { get; set; }
}
internal class FunctionNode : ExpressionNode
{
public Func<double, double> Function { get; set; }
public ExpressionNode Argument { get; set; }
}
internal class NumberNode : ExpressionNode
{
public double Value { get; set; }
}
Преобразование CST в AST
ANTLR создал для нас узлы CST (классы MathParser.*Context). Теперь нам нужно преобразовать их в узлы AST.
Это легко сделать с посетителем, и ANTLR предоставляет нам класс MathBaseVisitor<T>, поэтому давайте работать с ним.
internal class BuildAstVisitor : MathBaseVisitor<ExpressionNode>
{
public override ExpressionNode VisitCompileUnit(MathParser.CompileUnitContext context)
{
return Visit(context.expr());
}
public override ExpressionNode VisitNumberExpr(MathParser.NumberExprContext context)
{
return new NumberNode
{
Value = double.Parse(context.value.Text, NumberStyles.AllowDecimalPoint | NumberStyles.AllowExponent)
};
}
public override ExpressionNode VisitParensExpr(MathParser.ParensExprContext context)
{
return Visit(context.expr());
}
public override ExpressionNode VisitInfixExpr(MathParser.InfixExprContext context)
{
InfixExpressionNode node;
switch (context.op.Type)
{
case MathLexer.OP_ADD:
node = new AdditionNode();
break;
case MathLexer.OP_SUB:
node = new SubtractionNode();
break;
case MathLexer.OP_MUL:
node = new MultiplicationNode();
break;
case MathLexer.OP_DIV:
node = new DivisionNode();
break;
default:
throw new NotSupportedException();
}
node.Left = Visit(context.left);
node.Right = Visit(context.right);
return node;
}
public override ExpressionNode VisitUnaryExpr(MathParser.UnaryExprContext context)
{
switch (context.op.Type)
{
case MathLexer.OP_ADD:
return Visit(context.expr());
case MathLexer.OP_SUB:
return new NegateNode
{
InnerNode = Visit(context.expr())
};
default:
throw new NotSupportedException();
}
}
public override ExpressionNode VisitFuncExpr(MathParser.FuncExprContext context)
{
var functionName = context.func.Text;
var func = typeof(Math)
.GetMethods(BindingFlags.Public | BindingFlags.Static)
.Where(m => m.ReturnType == typeof(double))
.Where(m => m.GetParameters().Select(p => p.ParameterType).SequenceEqual(new[] { typeof(double) }))
.FirstOrDefault(m => m.Name.Equals(functionName, StringComparison.OrdinalIgnoreCase));
if (func == null)
throw new NotSupportedException(string.Format("Function {0} is not supported", functionName));
return new FunctionNode
{
Function = (Func<double, double>)func.CreateDelegate(typeof(Func<double, double>)),
Argument = Visit(context.expr())
};
}
}
Как вы можете видеть, это просто вопрос создания AST node из CST node с помощью посетителя. Код должен быть довольно понятным (ну, может быть, за исключением материала VisitFuncExpr, но это просто быстрый способ подключить делегат к подходящему методу System.Math).
И здесь у вас есть строительный материал AST. Это все, что нужно. Просто извлеките соответствующую информацию из КНТ и сохраните ее в АСТ.
Посетитель AST
Теперь давайте немного поиграем с АСТ. Нам нужно создать базовый класс посетителя AST, чтобы пройти его. Позвольте просто сделать что-то похожее на AbstractParseTreeVisitor<T>, предоставленное ANTLR.
internal abstract class AstVisitor<T>
{
public abstract T Visit(AdditionNode node);
public abstract T Visit(SubtractionNode node);
public abstract T Visit(MultiplicationNode node);
public abstract T Visit(DivisionNode node);
public abstract T Visit(NegateNode node);
public abstract T Visit(FunctionNode node);
public abstract T Visit(NumberNode node);
public T Visit(ExpressionNode node)
{
return Visit((dynamic)node);
}
}
Здесь я использовал ключевое слово С# dynamic, чтобы выполнить двойную отправку в одной строке кода. В Java вам нужно будет сделать проводку самостоятельно с помощью следующих выражений if:
if (node is AdditionNode) {
return Visit((AdditionNode)node);
} else if (node is SubtractionNode) {
return Visit((SubtractionNode)node);
} else if ...
Но я просто пошел на ярлык для этого примера.
Работа с AST
Итак, что мы можем сделать с деревом математического выражения? Оцените это, конечно! Пусть реализует средство оценки выражений:
internal class EvaluateExpressionVisitor : AstVisitor<double>
{
public override double Visit(AdditionNode node)
{
return Visit(node.Left) + Visit(node.Right);
}
public override double Visit(SubtractionNode node)
{
return Visit(node.Left) - Visit(node.Right);
}
public override double Visit(MultiplicationNode node)
{
return Visit(node.Left) * Visit(node.Right);
}
public override double Visit(DivisionNode node)
{
return Visit(node.Left) / Visit(node.Right);
}
public override double Visit(NegateNode node)
{
return -Visit(node.InnerNode);
}
public override double Visit(FunctionNode node)
{
return node.Function(Visit(node.Argument));
}
public override double Visit(NumberNode node)
{
return node.Value;
}
}
Довольно просто, когда у нас есть AST, не так ли?
Объединяя все это
И последнее, но не менее важное: мы должны написать основную программу:
internal class Program
{
private static void Main()
{
while (true)
{
Console.Write("> ");
var exprText = Console.ReadLine();
if (string.IsNullOrWhiteSpace(exprText))
break;
var inputStream = new AntlrInputStream(new StringReader(exprText));
var lexer = new MathLexer(inputStream);
var tokenStream = new CommonTokenStream(lexer);
var parser = new MathParser(tokenStream);
try
{
var cst = parser.compileUnit();
var ast = new BuildAstVisitor().VisitCompileUnit(cst);
var value = new EvaluateExpressionVisitor().Visit(ast);
Console.WriteLine("= {0}", value);
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
Console.WriteLine();
}
}
}
И теперь мы можем, наконец, сыграть с ним:
