如何用antlr4创建ast?

pgpifvop  于 2021-07-06  发布在  Java
关注(0)|答案(3)|浏览(559)

我已经找了很多关于这个的东西,但是我找不到任何有用的东西来帮助我建立一个ast。我已经知道antlr4不像antlr3那样构建ast。每个人都说:“嘿,利用访客!”,但我找不到任何例子或更详细的解释,我如何才能做到这一点。。。
我的语法一定很像c,但是每一个命令都是用葡萄牙语(葡萄牙编程语言)写的。我可以使用antlr4轻松地生成解析树。我的问题是:我现在需要做什么来创建ast?
顺便说一句,我正在使用java和intellij。。。
edit1:我能得到的最接近的答案是使用这个主题的答案:有没有一个简单的例子使用antlr4从java源代码创建ast并提取方法、变量和注解?但它只打印访问的方法的名称。。
由于第一次尝试并没有像我预期的那样对我有效,我尝试使用antlr3的这个教程,但是我不知道如何使用stringtamplate而不是st。。。
阅读这本书的权威antlr4参考我也找不到任何与asts有关的东西。
edit2:现在我有一个类来创建点文件,我只需要弄清楚如何正确使用访问者

cx6n0qe3

cx6n0qe31#

好的,让我们建立一个简单的数学例子。构建一个ast对于这样的任务来说是完全多余的,但是这是一个很好的展示原理的方法。
我会用c语言来做,但是java版本会非常相似。

语法

首先,让我们编写一个非常基本的数学语法:

  1. grammar Math;
  2. compileUnit
  3. : expr EOF
  4. ;
  5. expr
  6. : '(' expr ')' # parensExpr
  7. | op=('+'|'-') expr # unaryExpr
  8. | left=expr op=('*'|'/') right=expr # infixExpr
  9. | left=expr op=('+'|'-') right=expr # infixExpr
  10. | func=ID '(' expr ')' # funcExpr
  11. | value=NUM # numberExpr
  12. ;
  13. OP_ADD: '+';
  14. OP_SUB: '-';
  15. OP_MUL: '*';
  16. OP_DIV: '/';
  17. NUM : [0-9]+ ('.' [0-9]+)? ([eE] [+-]? [0-9]+)?;
  18. ID : [a-zA-Z]+;
  19. WS : [ \t\r\n] -> channel(HIDDEN);

很基本的东西,我们有一个 expr 处理一切的规则(优先规则等)。

ast节点

然后,让我们定义一些我们将使用的ast节点。这些都是完全定制的,你可以用你想要的方式来定义它们。
下面是我们将用于此示例的节点:

  1. internal abstract class ExpressionNode
  2. {
  3. }
  4. internal abstract class InfixExpressionNode : ExpressionNode
  5. {
  6. public ExpressionNode Left { get; set; }
  7. public ExpressionNode Right { get; set; }
  8. }
  9. internal class AdditionNode : InfixExpressionNode
  10. {
  11. }
  12. internal class SubtractionNode : InfixExpressionNode
  13. {
  14. }
  15. internal class MultiplicationNode : InfixExpressionNode
  16. {
  17. }
  18. internal class DivisionNode : InfixExpressionNode
  19. {
  20. }
  21. internal class NegateNode : ExpressionNode
  22. {
  23. public ExpressionNode InnerNode { get; set; }
  24. }
  25. internal class FunctionNode : ExpressionNode
  26. {
  27. public Func<double, double> Function { get; set; }
  28. public ExpressionNode Argument { get; set; }
  29. }
  30. internal class NumberNode : ExpressionNode
  31. {
  32. public double Value { get; set; }
  33. }

将cst转换为ast

antlr为我们生成cst节点( MathParser.*Context 类)。我们现在必须将这些节点转换为ast节点。
这对于访问者来说是很容易做到的,antlr为我们提供了一个 MathBaseVisitor<T> 同学们,让我们一起来。

  1. internal class BuildAstVisitor : MathBaseVisitor<ExpressionNode>
  2. {
  3. public override ExpressionNode VisitCompileUnit(MathParser.CompileUnitContext context)
  4. {
  5. return Visit(context.expr());
  6. }
  7. public override ExpressionNode VisitNumberExpr(MathParser.NumberExprContext context)
  8. {
  9. return new NumberNode
  10. {
  11. Value = double.Parse(context.value.Text, NumberStyles.AllowDecimalPoint | NumberStyles.AllowExponent)
  12. };
  13. }
  14. public override ExpressionNode VisitParensExpr(MathParser.ParensExprContext context)
  15. {
  16. return Visit(context.expr());
  17. }
  18. public override ExpressionNode VisitInfixExpr(MathParser.InfixExprContext context)
  19. {
  20. InfixExpressionNode node;
  21. switch (context.op.Type)
  22. {
  23. case MathLexer.OP_ADD:
  24. node = new AdditionNode();
  25. break;
  26. case MathLexer.OP_SUB:
  27. node = new SubtractionNode();
  28. break;
  29. case MathLexer.OP_MUL:
  30. node = new MultiplicationNode();
  31. break;
  32. case MathLexer.OP_DIV:
  33. node = new DivisionNode();
  34. break;
  35. default:
  36. throw new NotSupportedException();
  37. }
  38. node.Left = Visit(context.left);
  39. node.Right = Visit(context.right);
  40. return node;
  41. }
  42. public override ExpressionNode VisitUnaryExpr(MathParser.UnaryExprContext context)
  43. {
  44. switch (context.op.Type)
  45. {
  46. case MathLexer.OP_ADD:
  47. return Visit(context.expr());
  48. case MathLexer.OP_SUB:
  49. return new NegateNode
  50. {
  51. InnerNode = Visit(context.expr())
  52. };
  53. default:
  54. throw new NotSupportedException();
  55. }
  56. }
  57. public override ExpressionNode VisitFuncExpr(MathParser.FuncExprContext context)
  58. {
  59. var functionName = context.func.Text;
  60. var func = typeof(Math)
  61. .GetMethods(BindingFlags.Public | BindingFlags.Static)
  62. .Where(m => m.ReturnType == typeof(double))
  63. .Where(m => m.GetParameters().Select(p => p.ParameterType).SequenceEqual(new[] { typeof(double) }))
  64. .FirstOrDefault(m => m.Name.Equals(functionName, StringComparison.OrdinalIgnoreCase));
  65. if (func == null)
  66. throw new NotSupportedException(string.Format("Function {0} is not supported", functionName));
  67. return new FunctionNode
  68. {
  69. Function = (Func<double, double>)func.CreateDelegate(typeof(Func<double, double>)),
  70. Argument = Visit(context.expr())
  71. };
  72. }
  73. }

如您所见,这只是使用访问者从cst节点创建ast节点的问题。代码应该是非常自解释的(除了 VisitFuncExpr 但这只是一种将委托连接到合适的方法的快速方法 System.Math 类)。
这里是ast建筑材料。这就是所需要的。只需从cst中提取相关信息并保存在ast中。

最后的来访者

现在,让我们玩一下ast。我们必须构建一个ast visitor基类来遍历它。让我们做一些类似于 AbstractParseTreeVisitor<T> 由antlr提供。

  1. internal abstract class AstVisitor<T>
  2. {
  3. public abstract T Visit(AdditionNode node);
  4. public abstract T Visit(SubtractionNode node);
  5. public abstract T Visit(MultiplicationNode node);
  6. public abstract T Visit(DivisionNode node);
  7. public abstract T Visit(NegateNode node);
  8. public abstract T Visit(FunctionNode node);
  9. public abstract T Visit(NumberNode node);
  10. public T Visit(ExpressionNode node)
  11. {
  12. return Visit((dynamic)node);
  13. }
  14. }

在这里,我利用了c dynamic 关键字在一行代码中执行双重分派。在java中,您必须自己用一系列 if 像这样的陈述:

  1. if (node is AdditionNode) {
  2. return Visit((AdditionNode)node);
  3. } else if (node is SubtractionNode) {
  4. return Visit((SubtractionNode)node);
  5. } else if ...

但我只是选择了这个例子的捷径。

与ast合作

那么,我们能用数学表达式树做什么呢?当然,评估一下!让我们实现一个表达式计算器:

  1. internal class EvaluateExpressionVisitor : AstVisitor<double>
  2. {
  3. public override double Visit(AdditionNode node)
  4. {
  5. return Visit(node.Left) + Visit(node.Right);
  6. }
  7. public override double Visit(SubtractionNode node)
  8. {
  9. return Visit(node.Left) - Visit(node.Right);
  10. }
  11. public override double Visit(MultiplicationNode node)
  12. {
  13. return Visit(node.Left) * Visit(node.Right);
  14. }
  15. public override double Visit(DivisionNode node)
  16. {
  17. return Visit(node.Left) / Visit(node.Right);
  18. }
  19. public override double Visit(NegateNode node)
  20. {
  21. return -Visit(node.InnerNode);
  22. }
  23. public override double Visit(FunctionNode node)
  24. {
  25. return node.Function(Visit(node.Argument));
  26. }
  27. public override double Visit(NumberNode node)
  28. {
  29. return node.Value;
  30. }
  31. }

一旦我们有了ast就很简单了,不是吗?

把它们放在一起

最后但同样重要的是,我们必须实际编写主程序:

  1. internal class Program
  2. {
  3. private static void Main()
  4. {
  5. while (true)
  6. {
  7. Console.Write("> ");
  8. var exprText = Console.ReadLine();
  9. if (string.IsNullOrWhiteSpace(exprText))
  10. break;
  11. var inputStream = new AntlrInputStream(new StringReader(exprText));
  12. var lexer = new MathLexer(inputStream);
  13. var tokenStream = new CommonTokenStream(lexer);
  14. var parser = new MathParser(tokenStream);
  15. try
  16. {
  17. var cst = parser.compileUnit();
  18. var ast = new BuildAstVisitor().VisitCompileUnit(cst);
  19. var value = new EvaluateExpressionVisitor().Visit(ast);
  20. Console.WriteLine("= {0}", value);
  21. }
  22. catch (Exception ex)
  23. {
  24. Console.WriteLine(ex.Message);
  25. }
  26. Console.WriteLine();
  27. }
  28. }
  29. }

现在我们终于可以玩了:

展开查看全部
owfi6suc

owfi6suc2#

我创建了一个小的java项目,通过编译antlr在内存中生成的lexer和parser,您可以立即测试antlr语法。您可以通过将字符串传递给解析器来解析它,它将自动从中生成ast,然后可以在应用程序中使用它。
为了减小ast的大小,可以使用nodefilter,向其中添加在构造ast时要考虑的非终端的产生式规则名称。
代码和一些代码示例可以在https://github.com/julianthome/inmemantlr
希望工具有用;—)

ubbxdtey

ubbxdtey3#

我发现了两种简单的方法,重点是antlr4的testrig.java文件中提供的功能。
通过终端
这是我用相应的cpp14.g4语法文件解析c的示例 java -cp .:antlr-4.9-complete.jar org.antlr.v4.gui.TestRig CPP14 translationunit -tree filename.cpp . 如果省略filename.cpp,装备将从stdin读取。“translationunit”是我使用的cpp14.g4语法文件的开始规则名称。
通过java
我使用了testrig.java文件中的部分代码。让我们再次假设我们有一个c
源代码字符串,我们希望从中生成ast(您也可以直接从文件中读取)。

  1. String source_code = "...your cpp source code...";
  2. CodePointCharStream stream_from_string = CharStreams.fromString(source_code);
  3. CPP14Lexer lexer = new CPP14Lexer(new ANTLRInputStream(source_code));
  4. CommonTokenStream tokens = new CommonTokenStream(lexer);
  5. CPP14Parser parser = new CPP14Parser(tokens);
  6. String parserName = "CPP14Parser";
  7. ClassLoader cl = Thread.currentThread().getContextClassLoader();
  8. Class<? extends Parser> parserClass = null;
  9. parserClass = cl.loadClass(parserName).asSubclass(Parser.class);
  10. String startRuleName = "translationunit"; //as specified in my CPP14.g4 file
  11. Method startRule = parserClass.getMethod(startRuleName);
  12. ParserRuleContext tree = (ParserRuleContext)startRule.invoke(parser, (Object[])null);
  13. System.out.println(tree.toStringTree(parser));

我的进口是:

  1. import java.lang.reflect.Method;
  2. import org.antlr.v4.runtime.CommonTokenStream;
  3. import org.antlr.v4.runtime.CharStreams;
  4. import org.antlr.v4.runtime.CodePointCharStream;
  5. import org.antlr.v4.runtime.ANTLRInputStream;
  6. import org.antlr.v4.runtime.ParserRuleContext;
  7. import org.antlr.v4.runtime.Parser;

所有这些都要求您使用命令生成必要的文件(lexer、parser等) java -jar yournaltrfile.jar yourgrammar.g4 然后编译所有的*.java文件。

展开查看全部

相关问题