सवाल एएनटीएलआर 4 के साथ एएसटी कैसे बनाएं?


मैं इसके बारे में बहुत कुछ खोज रहा हूं और मुझे कुछ भी उपयोगी नहीं मिला जो वास्तव में मुझे एएसटी बनाने में मदद करता है। मुझे पहले से ही पता है कि एएनटीएलआर 4 एएसटीएलआर 3 की तरह एएसटी नहीं बनाता है। हर कोई कहता है: "अरे, आगंतुकों का उपयोग करें!", लेकिन मुझे कोई उदाहरण या अधिक विस्तृत स्पष्टीकरण नहीं मिला कि मैं यह कैसे कर सकता हूं ...

मेरे पास व्याकरण सी की तरह होना चाहिए, लेकिन पुर्तगाली (पोर्तुगा प्रोग्रामिंग भाषा) में लिखे गए प्रत्येक आदेश के साथ। मैं आसानी से एएनटीएलआर 4 का उपयोग कर पार्स पेड़ उत्पन्न कर सकता हूं। मेरा सवाल है: एएसटी बनाने के लिए मुझे अब क्या करना है?

बीटीडब्ल्यू, मैं जावा और इंटेलिजे का उपयोग कर रहा हूं ...

EDIT1: निकटतम मैं प्राप्त कर सकता था इस विषय का जवाब उपयोग कर रहा था: जावा स्रोत कोड से एएसटी बनाने और विधियों, चर और टिप्पणियों को निकालने के लिए antlr4 का उपयोग करने का एक सरल उदाहरण है? लेकिन यह केवल देखी गई विधियों के नाम को प्रिंट करता है ..

चूंकि मेरा प्रयास मेरे लिए काम नहीं करता था क्योंकि मैंने अपेक्षा की थी, मैंने उपयोग करने की कोशिश की यह ट्यूटोरियल एएनटीएलआर 3 से, लेकिन मैं यह नहीं समझ सका कि एसटी के बजाय स्ट्रिंगटैम्पलेट का उपयोग कैसे करें ...

पुस्तक पड़ रहे है परिभाषित एएनटीएलआर 4 संदर्भ मुझे एएसटी से संबंधित कुछ भी नहीं मिला।

EDIT2: अब मेरे पास डीओटी फ़ाइल बनाने के लिए एक वर्ग है, मुझे बस आगंतुकों का सही तरीके से उपयोग करने के बारे में जानकारी चाहिए


44
2018-04-30 14:58


मूल


क्या आप कुछ कोशिश कर सकते हैं जो आपने कोशिश की है? - Sandy Gifford
@ सैंडीफिफोर्ड मैंने अपनी पोस्ट को समझाने की कोशिश कर संपादित किया ... मेरे पास अभी मेरा कोड नहीं है क्योंकि मैंने अभी जो किया है उसे हटा दिया है। अभी मेरे पास केवल एटीएनएलआर 4 (पार्सर, लेक्सर और बेस विज़िटर और श्रोताओं) से जेनरेट कोड हैं - Leandro_GS
दुर्भाग्यवश, मुझे एएनटीएलआर के बारे में कुछ नहीं पता (आप मेरी कतार में आए थे) लेकिन आपने पोस्ट की गुणवत्ता बढ़ा दी है! - Sandy Gifford
"सीएसटी" बनाम "एएसटी" की चर्चा के लिए यह उत्तर देखें: stackoverflow.com/a/29456792/120163  अंत में टिप्पणी में चर्चा की जाती है कि कैसे एक और वास्तव में एएसटी प्राप्त करता है (अनिवार्य रूप से सीएसटी चलकर और एएसटी का निर्माण करके वह चाहता है)। - Ira Baxter
मैं आपके जैसी ही स्थिति में था, जब मैं एएनटीएलआर का उपयोग कर एक सुपर सरल एएसटी उदाहरण खोजने में विफल रहा, मैंने खुद को बनाया है github.com/adamsiemion/antlr-java-ast - Adam Siemion


जवाब:


ठीक है, चलिए एक साधारण गणित उदाहरण बनाते हैं। एक एएसटी बनाना इस तरह के कार्य के लिए पूरी तरह से अधिक है लेकिन सिद्धांत दिखाने के लिए यह एक अच्छा तरीका है।

मैं इसे सी # में करूँगा लेकिन जावा संस्करण बहुत समान होगा।

व्याकरण

सबसे पहले, चलिए काम करने के लिए एक बहुत ही बुनियादी गणित व्याकरण लिखते हैं:

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 नियम जो सबकुछ संभालता है (प्राथमिकता नियम आदि)।

एएसटी नोड्स

फिर, आइए कुछ एएसटी नोड्स को परिभाषित करें जो हम उपयोग करेंगे। ये पूरी तरह से कस्टम हैं और आप उन्हें जिस तरह से चाहते हैं उसे परिभाषित कर सकते हैं।

यहां नोड्स हैं जिनका हम इस उदाहरण के लिए उपयोग करेंगे:

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; }
}

एक सीएसटी को एक एएसटी में परिवर्तित करना

एएनटीएलआर ने हमारे लिए सीएसटी नोड्स उत्पन्न किए हैं (द MathParser.*Context वर्ग)। अब हमें इन्हें एएसटी नोड्स में बदलना है।

यह आसानी से एक आगंतुक के साथ किया जाता है, और एएनटीएलआर हमें एक प्रदान करता है 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())
        };
    }
}

जैसा कि आप देख सकते हैं, यह केवल एक आगंतुक का उपयोग करके एक सीएसटी नोड से एएसटी नोड बनाने का मामला है। कोड बहुत आत्म-व्याख्यात्मक होना चाहिए (ठीक है, शायद इसके अलावा VisitFuncExpr सामान, लेकिन यह एक प्रतिनिधि को एक उपयुक्त विधि के लिए तार करने का एक त्वरित तरीका है System.Math कक्षा)।

और यहां आपके पास एएसटी बिल्डिंग सामान है। यही सब कुछ जरूरी है। बस सीएसटी से प्रासंगिक जानकारी निकालें और इसे एएसटी में रखें।

एएसटी आगंतुक

अब, एएसटी के साथ थोड़ा सा खेलते हैं। हमें इसे चलाने के लिए एक एएसटी विज़िटर बेस क्लास बनाना होगा। आइए बस कुछ ऐसा ही करें AbstractParseTreeVisitor<T> एएनटीएलआर द्वारा प्रदान किया गया।

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 कोड की एक पंक्ति में डबल-प्रेषण करने के लिए कीवर्ड। जावा में, आपको स्वयं को एक अनुक्रम के साथ तारों को करना होगा ifइन तरह के बयान:

if (node is AdditionNode) {
    return Visit((AdditionNode)node);
} else if (node is SubtractionNode) {
    return Visit((SubtractionNode)node);
} else if ...

लेकिन मैं बस इस उदाहरण के लिए शॉर्टकट के लिए चला गया।

एएसटी के साथ काम करें

तो, हम गणित अभिव्यक्ति पेड़ के साथ क्या कर सकते हैं? निश्चित रूप से इसका मूल्यांकन करें! आइए अभिव्यक्ति मूल्यांकनकर्ता को लागू करें:

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;
    }
}

एक बार हमारे पास एएसटी होने के बाद बहुत आसान है, है ना?

यह सब एक साथ डालें

अंतिम लेकिन कम से कम नहीं, हमें वास्तव में मुख्य कार्यक्रम लिखना होगा:

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();
        }
    }
}

और अब हम अंत में इसके साथ खेल सकते हैं:

enter image description here


107
2018-05-01 22:41



बहुत धन्यवाद! इससे मुझे बहुत मदद मिलेगी... - Leandro_GS
@Waschbaer आईएमओ नोड्स ठीक-ठीक करने के लिए मैन्युअल रूप से रखरखाव में सुधार करता है और इसके लायक है, लेकिन आप असहमत हो सकते हैं। एएनटीएलआर 3 में एएसटी आउटपुट मोड था, इसलिए यदि आप पुराने उपकरण के उपयोग से सहज हैं, तो आप इसका उपयोग कर सकते हैं। या शायद आप कुछ बॉयलरप्लेट कोड उत्पन्न करने के लिए मेटाप्रोग्रामिंग / टेम्पलेटिंग का उपयोग कर सकते हैं, लेकिन आप अंत में अधिक काम के साथ समाप्त हो सकते हैं। एक अन्य विकल्प सीएसटी के साथ सीधे काम करना है। - Lucas Trzesniewski
@Trejkaz इस वर्ग को एएनटीएलआर द्वारा उत्पन्न किया गया है, बस श्रोता की तरह - आपके पास होना चाहिए QueryBaseVisitor (जब तक आपका व्याकरण नाम न हो शामिल उस Parser भाग, लेकिन उस मामले में आपके पास भी होगा QueryParserParser)। आईआईआरसी NuGet पैकेज स्वचालित रूप से उत्पन्न करता है, लेकिन यदि आप मैन्युअल रूप से एएनटीएलआर चलाते हैं, तो आपको इसे जोड़ना होगा -visitor विकल्प। - Lucas Trzesniewski
@ जोहान्स मैं हूँ नहीं का उपयोग करते हुए AstVisitor में BuildAstVisitor बिलकुल। AstVisitor के लिए बेस क्लास के रूप में प्रयोग किया जाता है EvaluateExpressionVisitor जिसका उपयोग अगले चरण में किया जाता है: BuildAstVisitor सीएसटी को एएसटी में परिवर्तित करता है, और EvaluateExpressionVisitor उस एएसटी पर बुलाया जाता है। मैं यह देखने के लिए देख सकता हूं कि मेरे पास अभी भी समाधान फाइलें हैं, लेकिन कोड का 100% उत्तर में है। - Lucas Trzesniewski
@ जोहान्स मैंने समाधान पाया, मैंने इसे अपलोड किया यहाँ सभी जेनरेट आउटपुट और निर्भरताओं के साथ कच्चे। यह सुंदर दिखने के लिए नहीं था, लगभग सबकुछ एक ही फाइल में है। दो Visit विधियां असंबंधित हैं, उनके पास समान नाम होता है, लेकिन दोनों वर्ग हैं आगंतुकों, ठीक है, वे एक ही नाम का उपयोग करें :) - Lucas Trzesniewski


मैंने एक छोटी जावा प्रोजेक्ट बनाई है जो आपको एएनटीएलआर इन-मेमोरी द्वारा उत्पन्न लेक्सर और पार्सर को संकलित करके तुरंत अपने एएनटीएलआर व्याकरण का परीक्षण करने की अनुमति देती है। आप इसे पार्सर में पास करके एक स्ट्रिंग को पार्स कर सकते हैं, और यह स्वचालित रूप से उस से एएसटी उत्पन्न करेगा जिसका उपयोग आपके एप्लिकेशन में किया जा सकता है।

एएसटी के आकार को कम करने के उद्देश्य से, आप एक नोडफिल्टर का उपयोग कर सकते हैं जिसमें आप गैर-टर्मिनलों के उत्पादन-नियम नाम जोड़ सकते हैं जिन्हें आप एएसटी का निर्माण करते समय विचार करना चाहते हैं।

कोड और कुछ कोड उदाहरण मिल सकते हैं https://github.com/julianthome/inmemantlr

आशा है कि उपकरण उपयोगी है ;-)


3
2018-06-27 11:29



मैंने आपकी 'छोटी' परियोजना का उपयोग करने की कोशिश की लेकिन आपके पास कोई टिप्पणी नहीं होने वाली सैकड़ों फाइलें हैं, यह पता लगाना असंभव है कि क्या हो रहा है। आपके पास रैपर कार्यों के अपने संस्करण में लिपटे सब कुछ है। एक उपयोगकर्ता को अपनी पूरी परियोजना को डाउनलोड करना होगा और इसका उपयोग करना होगा, और अपने नए वर्गों (जेनेरिक पार्सर ??) का उपयोग करना सीखना होगा। मैं अपने कोड में अपने स्वयं के एएसटी को बनाने का तरीका जानने के लिए अपने कोड का उपयोग नहीं कर सकता। - john ktejik
हाय जॉन इनमेमंटलर के कोड बेस में 48 जावा क्लासेस शामिल हैं (find inmemantlr-api/src/main -name "*.java" | nl) जिनमें से अधिकतर अच्छी तरह से टिप्पणी की जाती हैं (javadoc.io/doc/com.github.julianthome/inmemantlr-api/1.3.9)। ऊपर बताए गए बिंदुओं को चित्रित करने के लिए (एपीआई उपयोग, पारसी ट्री निर्माण), मैंने स्पष्टीकरण प्रदान किए हैं README.md और परीक्षण मामलों में प्रदान किया github.com/julianthome/inmemantlr/tree/master/inmemantlr-api/...। हालांकि, अगर आपको टूल के साथ समस्याएं हैं, तो आपकी मदद करने में खुशी होगी। कृपया मुझे एक ईमेल छोड़ दें या जिथब पर कोई समस्या बनाएं। - Julian
क्या यह हो सकता है कि आपने व्याकरण-v4 सबमिशन खींच लिया है (कृपया एक नज़र डालें inmemantlr-api/src/test/resources/grammars-v4)? असल में, यह मॉड्यूल inmemantlr के कोड-बेस का हिस्सा नहीं है; यह सुनिश्चित करने के लिए प्रयोग किया जाता है कि inmemantlr सभी व्याकरण-v4 व्याकरण पर काम करता है। हालांकि, निष्पादन के दौरान प्रतिबिंब प्रति डिफ़ॉल्ट नहीं खींचा जाता है git clone https://github.com/julianthome/inmemantlr। - Julian
@ जूलियन अद्भुत उपकरण। यह वास्तव में शक्तिशाली और उपयोग करने में आसान है। समुदाय के साथ साझा करने के लिए धन्यवाद। विकी में और उदाहरण देखना चाहते हैं। - Vaibhav Jain
@ वैभववैन बहुत बहुत धन्यवाद। यदि आपके पास दस्तावेज / उपकरण / एपीआई को सुधारने के बारे में कुछ सुझाव हैं, तो मुझे खुशी होगी अगर आप github प्रोजेक्ट पेज पर कोई समस्या बना सकते हैं;)। एक बार फिर धन्यवाद। - Julian