व्याकरण और कम से कम पार्सर को पहचानने के बारे में क्या है?

Question

मैं एक कंपाइलर बनाने के तरीके सीखने की कोशिश कर रहा हूं। ऐसा करने के लिए, मैंने संदर्भ-मुक्त भाषा के बारे में बहुत कुछ पढ़ा। लेकिन कुछ चीजें हैं जिन्हें मैं अभी तक नहीं प्राप्त कर सकता हूं।

चूंकि यह मेरा पहला कंपाइलर है, ऐसे कुछ अभ्यास हैं जिनके बारे में मुझे पता नहीं है। मेरे प्रश्नों को एक पार्सर जनरेटर बनाने के लिए दिमाग में पूछा जाता है, न कि एक कंपाइलर न तो एक लेक्सर। कुछ प्रश्न स्पष्ट हो सकते हैं ..

मेरे पढ़ने में से हैं: Bottom-Up Parsing, Top-Down Parsing, Formal Grammars। दिखाया गया चित्र आता है: Miscellanous Parsing। सभी स्टैनफोर्ड सीएस 143 कक्षा से आ रहे हैं।

यहाँ बिंदु हैं:

0) कैसे कर (अस्पष्ट/स्पष्ट) और (बाएं पुनरावर्ती/सही पुनरावर्ती) एक एल्गोरिथ्म या किसी अन्य के लिए की जरूरत को प्रभावित? क्या व्याकरण को अर्हता प्राप्त करने के अन्य तरीके हैं?

1) एक संदिग्ध व्याकरण एक है जिसमें कई पार्स पेड़ हैं। लेकिन क्या एक बाएं-व्युत्पन्न या दाएं-व्युत्पन्न की पसंद को पार्स पेड़ की एकता के लिए नेतृत्व नहीं करना चाहिए?

[संपादित करें: उत्तर here]

2,1) लेकिन फिर भी, k से संबंधित व्याकरण की अस्पष्टता है? मेरा मतलब है कि एलआर (2) व्याकरण देना, क्या यह एलआर (1) पार्सर के लिए संदिग्ध है और एलआर (2) एक के लिए संदिग्ध नहीं है?

[संपादित करें: नहीं, यह नहीं है, एक एलआर (2) व्याकरण का अर्थ है कि पार्सर को उपयोग करने के लिए सही नियम चुनने के लिए दो टोकन दिखने की आवश्यकता होगी। दूसरी तरफ, एक संदिग्ध व्याकरण वह होता है जो संभवतः कई पार्स पेड़ों की ओर जाता है। ]

2.2) तो एक एलआर (*) पार्सर, जब तक आप इसकी कल्पना कर सकें, तब तक कोई अस्पष्ट व्याकरण नहीं होगा और फिर संदर्भ मुक्त भाषाओं के पूरे सेट को पार्स कर सकता है?

[संपादित करें: ईआर बैक्सटर द्वारा उत्तर दिया गया, एलआर (*) जीएलआर से कम शक्तिशाली है, जिसमें यह एकाधिक पार्स पेड़ों को संभाल नहीं सकता है। ]

3) पिछले उत्तरों के आधार पर, निम्न विरोधाभासी क्या हो सकता है। एलआर पार्सिंग को ध्यान में रखते हुए, संदिग्ध व्याकरण ट्रिगर को ट्रिगर करते हैं-संघर्ष को कम करते हैं? क्या एक अस्पष्ट व्याकरण एक भी ट्रिगर कर सकता है? इसी तरह, संघर्ष को कम करने के बारे में क्या?

[संपादित करें: यह है, संदिग्ध व्याकरण शिफ्ट-कम करने और कम करने के कारण होते हैं-संघर्ष को कम करते हैं। Contrapositive द्वारा, अगर कोई संघर्ष नहीं है, व्याकरण univocal है। ]

4) बाएं-रिकर्सिव व्याकरण को पार्स करने की क्षमता एलएल (के) पर एलआर (के) पार्सर का लाभ है, क्या यह उनके बीच एकमात्र अंतर है?

[संपादित करें: हाँ। ]

5) देते G1:

G1 : 
S -> S + S 
S -> S - S 
S -> a 

5,1) G1 दोनों, राइट-पुनरावर्ती, पुनरावर्ती छोड़ दिया और अस्पष्ट है, मैं सही हूँ? क्या यह एक एलआर (2) व्याकरण है? कोई इसे स्पष्ट बना देगा:

G2 : 
S -> S + a 
S -> S - a 
S -> a 

5.2) क्या जी 2 अभी भी संदिग्ध है? क्या जी 2 के लिए एक पार्सर को दो लुकहेड चाहिए?कारक द्वारा हमारे पास है:

G3 : 
S -> S V 
V -> + a 
V -> - a 
S -> a 

5.3) अब, जी 3 के लिए एक पार्सर केवल एक लुकहेड की आवश्यकता है? इन परिवर्तनों के लिए काउंटर पार्ट्स क्या हैं? एलआर (1) न्यूनतम पार्सर आवश्यक है?

5.4) G1 पुनरावर्ती छोड़ दिया है क्रम में एक डालूँगा पार्सर के साथ यह पार्स करने के लिए, यह एक सही पुनरावर्ती व्याकरण में बदलने की एक जरूरत:

G4 : 
S -> a + S 
S -> a - S 
S -> a 

तो

G5 : 
S -> a V 
V -> - V 
V -> + V 
V -> a 

5,5) करता है जी 4 कम से कम एक एलएल (2) पार्सर की आवश्यकता है? जी 5 केवल एलएल (1) पार्सर द्वारा पारदर्शी है, जी 1-जी 5 एक ही भाषा को परिभाषित करता है, और यह भाषा है (ए (+/- ए)^एन)। क्या यह सच है ?

5.6) प्रत्येक व्याकरण जी 1 से जी 5 के लिए, यह न्यूनतम सेट क्या है?

6) आखिरकार, चूंकि कई अलग-अलग व्याकरण एक ही भाषा को परिभाषित कर सकते हैं, तो व्याकरण और संबंधित पार्सर को कैसे चुना जाता है? परिणामस्वरूप पार्स पेड़ imortant है? पार्स पेड़ का प्रभाव क्या है?

मैं बहुत कुछ पूछ रहा हूं, और मुझे वास्तव में एक पूर्ण उत्तर की उम्मीद नहीं है, फिर भी किसी भी मदद की बहुत सराहना की जाएगी।

पढ़ने के लिए Thx!

Answer 1

"कई व्याकरण एक ही लैंगेज परिभाषित कर सकते हैं, कोई कैसे चुनता है ..."?

आमतौर पर, आप एक है कि निम्नलिखित मानदंडों को पूरा चुनें:

धारणात्मक
• के रूप में सरल रूप में आप कर सकते हैं यह (निहितार्थ: दूसरों की तुलना में छोटे)
• भाषा के संदर्भ मैनुअल में शब्दावली जहां संभव पटरियों
• अपने पार्सर जेनरेटर की कमी

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

व्याकरण झुकाव को कम करने का एक तरीका एक पार्सर जेनरेटर चुनना है जो पूरी तरह से संदर्भ मुक्त व्याकरण को संभालता है। GLR parsing का यह बहुत महत्वपूर्ण फायदा है। मैं इसे 15 साल से इस्तेमाल कर रहा हूं और इसके साथ दर्जनों असली लैंगुग्स कर चुका हूं।