ANTLR4 परस्पर बाएं पुनरावर्ती त्रुटि

Question

पार्स करने मैं इस ANTLR 4 व्याकरण की है। समस्या क्या है और मैं इसे कैसे हल कर सकता हूं?

Answer 1

एंटर एक एलएल (*) पार्सर है, जो LL(k) parser से "बेहतर" कई तरीकों से है, लेकिन इसके कई फायदे हैं। इनमें से एक तथ्य यह है कि यह बाएं-रिकर्सन से निपट नहीं सकता है (वास्तव में, संस्करण 4 उसी नियम के भीतर बाएं-रिकर्सन से निपट सकता है)। त्रुटि क्या कह रही है कि आपके पास व्याकरण का बायां-रिकर्सन है, जो एलएल पार्सर्स के लिए एक झुकाव है।

यह आपके व्याकरण में इस निर्माण के कारण होता है:

constantFixedExpression: term ...; 
term: factor ...; 
factor: ('+' | '-')* (constantFixedExpression | ...) ...; 

के बाद से * ऑपरेटर का मतलब है 0 या उससे अधिक है, मैं 0 के साथ यह दृष्टांत सकते हैं, तो पार्सर यह कर देगा: "constantFixedExpression कोशिश, तो यह term को आजमाने की आवश्यकता है, इसलिए इसे factor को आजमाने की आवश्यकता है, इसलिए इसे constantFixedEXpression को आजमाने की आवश्यकता है, इसलिए यह [...] "और आपके पास एक अनंत लूप है।

---

सौभाग्य से, विषय से मुक्त औपचारिक व्याकरण बाएं प्रत्यावर्तन दूर करने के लिए एक समान परिवर्तन है!

A -> Aa | b 
-- becomes -- 
A -> bR 
R -> aA | ε 

या antlr अंकन में:: यह द्वारा सामान्य रूप से व्यक्त किया जा सकता

A: Aa | b; 
// becomes 
A: bR; 
R: (aA)?; 

अधिक इस प्रक्रिया के बारे में जानकारी आटोमैटिक मशीन में पाया जा सकता/किताबें या Wikipedia में grammars।

---

मैं आपके काम के रूप में बाएं-रिकर्सन को हटाने के लिए रिफैक्टरेशन के साथ अपने व्याकरण को सही कर दूंगा। हालांकि, मैं एक और बिंदु में छूना चाहता हूं: Antlr 4 बाएं-रिकर्सन कर सकता है! जैसा कि मैंने उल्लेख किया है, संस्करण 4 उसी नियम के भीतर बाएं-रिकर्सन से निपट सकता है। Antlr4 में, जैसा कि आप कर रहे हैं, सीधे पार्सिंग के अलावा ऑपरेटरों की प्राथमिकता और सहयोगीता को इंगित करने के तरीके हैं। चलो देखते हैं कि यह कैसे काम करता है:

expr: NUMBER 
     |<assoc=right> expr '^' expr 
     | expr '*' expr 
     | expr '/' expr 
     | expr '+' expr 
     | expr '-' expr; 

यह मूल कैलकुलेटर व्याकरण का एक उदाहरण है। शीर्ष पर ऑपरेटर उच्च प्राथमिकता वाले हैं, और नीचे वाले लोग निम्न प्राथमिकता के हैं। इसका अर्थ है 2+2*3 के बजाय 2+(2*3) के रूप में पार्स किया जाएगा। <assoc=right> निर्माण का मतलब ऑपरेटर को सही-सहयोगी में है, इसलिए 1^2^3 को (1^2)^3 के बजाय 1^(2^3) के रूप में पार्स किया जाएगा।

जैसा कि आप देख सकते हैं, बाएं-रिकर्सन वाले ऑपरेटरों को निर्दिष्ट करना बहुत आसान है, इसलिए एंटर 4 इन क्षणों में बड़ी सहायता है! मैं इस सुविधा का उपयोग करने के लिए अपने व्याकरण को फिर से लिखने की सलाह देता हूं।