Ok, lassen Sie uns ein einfaches Mathe Beispiel bauen. Der Aufbau eines AST ist völlig übertrieben für eine solche Aufgabe, aber es ist eine gute Möglichkeit, das Prinzip zu zeigen.
Ich werde es in C# tun, aber die Java-Version wäre sehr ähnlich.
Die Grammatik
Lassen Sie uns zunächst eine sehr grundlegende mathematische Grammatik schreiben, mit zu arbeiten:
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);
Ziemlich einfach Sachen, wir eine einzige expr Regel, die alles (Vorrangregeln usw.) behandelt.
Die AST-Knoten
Dann lassen Sie uns einige AST-Knoten definieren wir verwenden. Diese sind völlig benutzerdefiniert und Sie können sie so definieren, wie Sie es möchten.
Hier sind die Knoten wir für dieses Beispiel verwendet werden:
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; }
}
Konvertieren eines CST mit einem AST
ANTLR die CST-Knoten für uns erzeugt (die MathParser.*Context Klassen). Wir müssen diese nun in AST-Knoten umwandeln.
Dies ist leicht mit einem Besucher getan, und ANTLR bietet uns eine MathBaseVisitor<T> Klasse, also lasst uns damit arbeiten.
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())
};
}
}
Wie Sie sehen, es ist nur eine Frage von einem AST-Knoten aus einem CST-Knoten zu schaffen, indem einen Besucher verwendet.Der Code sollte ziemlich selbsterklärend sein (gut, vielleicht außer für die VisitFuncExpr Sachen, aber es ist nur eine schnelle Möglichkeit, einen Delegaten zu einer geeigneten Methode der System.Math Klasse zu verdrahten).
Und hier haben Sie die AST Gebäude Zeug. Das ist alles was benötigt wird. Extrahieren Sie einfach die relevanten Informationen aus dem CST und behalten Sie sie im AST.
Der AST Besucher
Nun lassen Sie uns mit dem AST ein bisschen spielen. Wir müssen eine AST-Besucherbasisklasse erstellen, um sie zu durchlaufen. Lassen Sie uns etwas tun, das dem von ANTLR bereitgestellten AbstractParseTreeVisitor<T> ähnlich ist.
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);
}
}
Hier nutzte ich C# 's dynamic Schlüsselwort eine Doppel Versand in einer Zeile Code auszuführen. In Java, werden Sie die Verkabelung selbst mit einer Folge von if Aussagen wie diese zu tun haben:
if (node is AdditionNode) {
return Visit((AdditionNode)node);
} else if (node is SubtractionNode) {
return Visit((SubtractionNode)node);
} else if ...
Aber ich ging nur für die Verknüpfung für dieses Beispiel.
Die Arbeit mit dem AST
Also, was können wir mit einem mathematischen Ausdrucksbaum zu tun? Bewerten Sie es natürlich! Lassen Sie sich einen Ausdrucksauswerter implementieren:
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;
}
}
ziemlich einfach, sobald wir einen AST haben, ist es nicht?
setzen sie alle zusammen
Last but not least, müssen wir eigentlich das Hauptprogramm schreiben:
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();
}
}
}
Und jetzt können wir endlich mit ihm spielen:
Könnten Sie einige was Sie versucht haben? –
@SandyGifford Ich habe meinen Beitrag bearbeitet und versucht zu erklären ... Ich habe meinen Code gerade nicht, weil ich gerade gelöscht habe, was ich gemacht habe. Im Moment habe ich nur die generierten Codes von ATNLR4 (Parser, Lexer und Base Besucher und Listener) –
Leider weiß ich nichts über ANTLR (Sie kamen in meine Warteschlange), aber Sie haben die Qualität des Beitrags erhöht! –