लेक्सिकल और सिंटैक्टिक विश्लेषण

लेक्सिकल और सिंटैक्टिक विश्लेषण एक कंपाइलर के फ्रंट एंड का निर्माण करते हैं, जो स्रोत टेक्स्ट को टोकन में तोड़ते हैं और एक पार्स या सिंटैक्स ट्री के रूप में इसकी व्याकरणिक संरचना को पहचानते हैं।

Definition

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

Scope

यह विषय लेक्सिकल विश्लेषण को शामिल करता है, जो नियमित भाषाओं और परिमित ऑटोमेटा का उपयोग करके कैरेक्टर स्ट्रीम को टोकन में परिवर्तित करता है, और सिंटैक्टिक विश्लेषण (पार्सिंग), जो एक संदर्भ-मुक्त व्याकरण के विरुद्ध एक प्रोग्राम की वाक्यांश संरचना को पहचानता है। इसमें टॉप-डाउन (LL) और बॉटम-अप (LR) पार्सिंग, पार्सर जनरेटर, अस्पष्टता और त्रुटि पुनर्प्राप्ति, और एब्स्ट्रैक्ट सिंटैक्स ट्री का निर्माण शामिल है।

Core questions

• प्रोग्राम संरचना का वर्णन करने के लिए नियमित और संदर्भ-मुक्त भाषाओं का उपयोग कैसे किया जाता है?
• LL और LR पार्सिंग के बीच क्या फायदे और नुकसान हैं?
• अस्पष्टता और पार्स त्रुटियों का पता कैसे लगाया जाता है और उन्हें कैसे संभाला जाता है?
• टोकन स्ट्रीम से एक एब्स्ट्रैक्ट सिंटैक्स ट्री का निर्माण कैसे किया जाता है?

Key theories

LR पार्सिंग

नुथ ने LR पार्सिंग की शुरुआत की, एक बॉटम-अप तकनीक जो LR व्याकरणों के व्यापक वर्ग को रैखिक समय में नियतात्मक रूप से पार्स करती है, जो कई पार्सर जनरेटर का आधार बनती है।

सामान्य संदर्भ-मुक्त पार्सिंग

अर्ली का एल्गोरिथम मनमाने संदर्भ-मुक्त व्याकरणों को पार्स करता है, जिसमें अस्पष्ट व्याकरण भी शामिल हैं, जब प्रतिबंधित नियतात्मक पार्सर अपर्याप्त होते हैं तो एक सामान्य विधि प्रदान करता है।

फ्रंट एंड के नियमित और संदर्भ-मुक्त आधार

ड्रैगन बुक स्कैनिंग के लिए नियमित अभिव्यक्तियों और परिमित ऑटोमेटा के उपयोग और पार्सिंग के लिए संदर्भ-मुक्त व्याकरणों को व्यवस्थित करती है, जिसमें मानक LL और LR निर्माण एल्गोरिथम शामिल हैं।

Clinical relevance

लेक्सिंग और पार्सिंग न केवल कंपाइलर के लिए बल्कि इंटरप्रेटर, लिंटर, फॉर्मेटर, IDE और डेटा-फॉर्मेट प्रोसेसर के लिए भी मूलभूत हैं। अच्छी त्रुटि पुनर्प्राप्ति के साथ मजबूत पार्सिंग किसी भी भाषा टूलिंग के डेवलपर अनुभव के लिए आवश्यक है।

History

1950 के दशक के अंत में चॉम्स्की के औपचारिक भाषा पदानुक्रम ने नियमित और संदर्भ-मुक्त भाषाओं का सिद्धांत प्रदान किया। नुथ ने 1965 में LR पार्सिंग को औपचारिक रूप दिया, और अर्ली ने 1970 में एक सामान्य संदर्भ-मुक्त एल्गोरिथम दिया। yacc जैसे पार्सर जनरेटर ने LR पार्सिंग को व्यावहारिक बनाया, जबकि बाद के काम ने पार्सिंग एक्सप्रेशन व्याकरण और कॉम्बिनेटर-आधारित पार्सर की खोज की।

Debates

जनरेटेड बनाम हस्तलिखित पार्सर

अभ्यासकर्ता औपचारिक व्याकरणों से पार्सर जनरेटर का उपयोग करने पर बहस करते हैं, जो संक्षिप्त और सत्यापन योग्य होते हैं, हस्तलिखित रिकर्सिव-डिसेंट पार्सर के खिलाफ, जो अक्सर अधिक कोड की लागत पर बेहतर त्रुटि संदेश और नियंत्रण देते हैं।

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

लेक्सर और पार्सर के बीच क्या अंतर है?

एक लेक्सर कच्चे वर्णों को पहचानकर्ताओं और ऑपरेटरों जैसे टोकन में समूहित करता है, जबकि एक पार्सर उन टोकन को भाषा के व्याकरण के अनुसार एक पदानुक्रमित सिंटैक्स ट्री में व्यवस्थित करता है।

LL और LR पार्सिंग के बीच क्या अंतर है?

LL पार्सर टॉप-डाउन काम करते हैं, इनपुट उपसर्ग से उत्पादन की भविष्यवाणी करते हैं, जबकि LR पार्सर बॉटम-अप काम करते हैं, मान्यता प्राप्त सबस्ट्रिंग को कम करते हैं; LR व्याकरणों के एक कड़ाई से बड़े वर्ग को संभालता है लेकिन निर्माण करना अधिक जटिल है।