एएनटीएलआर: बैकट्रैक के बीच अंतर और आगे देखो?

Question

मैं एएनटीएलआर के सापेक्ष नया हूं। मैं एक बहुत ही आसान व्याकरण है:

start : 
('A' 'B' 'C' '1' 
|'A' 'B' 'C' '2' 
|'A' 'B' 'C' '3' 
) 
; 

मुझे लगता है कि मैं पहले से ही आगे देखो और बैक ट्रैकिंग की अवधारणा (जो वाक्यात्मक विधेय के साथ काम करता है) की मूल बातें समझ। तो यह व्याकरण k = 4 या बैकट्रैक = सत्य के साथ काम करता है। लेकिन सटीक अंतर क्या है और मुख्य प्रश्न यह है कि मैं कब उपयोग करता हूं? मैंने इंटरनेट पर जवाब खोजने की कोशिश की लेकिन सफल नहीं हुआ।

Answer 1

मुझे पुस्तक "निश्चित परिभाषा संदर्भ" में मेरे प्रश्न के लिए सैद्धांतिक वर्णन मिला, जो मेरी समझ के लिए भी महत्वपूर्ण था। हो सकता है कि कुछ अन्य जो खुद को समान प्रश्न पूछते हैं, पुस्तक के इस स्निपेट में भी मदद करेंगे।

पृष्ठ 262

Answer 2

आपका व्याकरण किसी भी विकल्प के बिना एएनटीएलआर v3 में काम करता है।

के विकल्प एएनटीएलआर को शास्त्रीय एलएल (के) पार्सिंग तक सीमित करता है। बैकट्रैकिंग का अर्थ है - यदि पार्सर भविष्यवाणी नहीं कर सकता है, तो किस नियम का उपयोग करना है, यह सिर्फ कोशिश करता है, बैकट्रैक और फिर कोशिश करता है। बैकट्रैकिंग विकल्प का उपयोग तब करना चाहिए जब एएनटीएलआर दिए गए व्याकरण के लिए आगे-आगे डीएफए नहीं बना सकता है। एएनटीएलआर वी 3 नियमित अभिव्यक्तियों से डीएफए का निर्माण बहुत आसान बना सकता है, लेकिन इसमें रिकर्सिव नियमों के साथ इसकी कठिनाइयां हैं। उदाहरण के लिए, यह व्याकरण काम करता है:

start: recursive_rule ';' 
    | recursive_rule ':' 
    ; 

recursive_rule : (ID)* '%' 
       ; 

यह व्याकरण नीचे समान है, लेकिन रिकर्सन के माध्यम से व्यक्त किया गया है। ANTLR DFA का निर्माण नहीं कर सकते के लिए यह (मैं वास्तव में पता नहीं क्यों) है, तो आप पर उलटे पांव लौटने स्विच करने की आवश्यकता:

start options {backtrack=true;} : recursive_rule ';' 
           | recursive_rule ':' 
           ; 

recursive_rule : ID recursive_rule 
       |'%' 
       ; 

कश्मीर विकल्प पार्सर के प्रदर्शन में सुधार करने के लिए इस्तेमाल किया जाता है। मैं एलएल (*) से एलएल (के) को प्रतिबंधित करने के किसी अन्य कारण को नहीं जानता।