ANTLR4로 AST를 만드는 방법은 무엇입니까?
나는 이것에 대해 많이 검색했지만 AST를 구축하는 데 정말로 도움이되는 유용한 것을 찾을 수 없었습니다. 나는 이미 ANTLR4가 ANTLR3처럼 AST를 빌드하지 않는다는 것을 알고 있습니다. 모두들 "이봐 요, 방문자를 이용하세요!"라고 말하지만, 어떻게 할 수 있는지에 대한 예나 자세한 설명을 찾을 수 없습니다 ...
문법은 C와 비슷하지만 모든 명령은 포르투갈어 (포르투가 프로그래밍 언어)로 작성됩니다. ANTLR4를 사용하여 쉽게 구문 분석 트리를 생성 할 수 있습니다. 내 질문은 : AST를 생성하려면 지금 무엇을해야합니까?
BTW, Java와 IntelliJ를 사용하고 있습니다 ...
EDIT1 : 내가 얻을 수있는 가장 가까운 것은이 주제의 대답을 사용하는 것입니다. antlr4를 사용하여 Java 소스 코드에서 AST를 만들고 메서드, 변수 및 주석을 추출하는 간단한 예가 있습니까? 하지만 방문한 메서드의 이름 만 인쇄합니다.
첫 번째 시도가 예상대로 작동하지 않았기 때문에 ANTLR3 에서이 튜토리얼 을 사용하려고했지만 ST 대신 StringTamplate를 사용하는 방법을 알 수 없었습니다.
The Definitive ANTLR 4 Reference 책 읽기 또한 AST와 관련된 내용을 찾을 수 없었습니다.
EDIT2 : 이제 DOT 파일을 생성 할 클래스가 하나 있습니다. 방문자를 올바르게 사용하는 방법 만 파악하면됩니다.
자, 간단한 수학 예제를 만들어 봅시다. AST를 구축하는 것은 그러한 작업에 대해 완전히 과잉이지만 원칙을 보여주는 좋은 방법입니다.
C #으로 할 것이지만 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())
};
}
}
보시다시피 방문자를 사용하여 CST 노드에서 AST 노드를 만드는 문제입니다. 코드는 매우 자명해야합니다 ( VisitFuncExpr물건을 제외하고는 아마도 델리게이트를 System.Math클래스 의 적절한 메서드에 연결하는 빠른 방법 일뿐입니다 ).
그리고 여기에 AST 건물이 있습니다. 그게 필요한 전부입니다. CST에서 관련 정보를 추출하여 AST에 보관하십시오.
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);
}
}
여기서는 C #의 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();
}
}
}
그리고 이제 우리는 그것을 가지고 놀 수 있습니다.
I have created a small Java project that allows you to test your ANTLR grammar instantly by compiling the lexer and parser generated by ANTLR in-memory. You can just parse a string by passing it to the parser, and it will automatically generate an AST from it which can then be used in your application.
For the purpose of reducing the size of the AST, you could use a NodeFilter to which you could add the production-rule names of the non-terminals that you would like to be considered when constructing the AST.
The code and some code examples can be found at https://github.com/julianthome/inmemantlr
Hope the tool is useful ;-)
ReferenceURL : https://stackoverflow.com/questions/29971097/how-to-create-ast-with-antlr4
'development' 카테고리의 다른 글
| Android에서 View Stub을 사용하는 방법 (0) | 2020.12.28 |
|---|---|
| Asp.Net VNext를 사용할 때 application / font-woff2가 작동하지 않음 (0) | 2020.12.28 |
| Docker가 변경된 경우에만 pip requirements.txt를 실행하는 방법은 무엇입니까? (0) | 2020.12.28 |
| jq를 사용하여 JSON 문자열 구문 분석 (0) | 2020.12.28 |
| PHP-MySQL에서 단일 레코드를 읽는 간단한 방법 (0) | 2020.12.28 |