यहां एक महत्वपूर्ण विवरण यह है कि व्याकरण स्ट्रिंग स्वीकार नहीं करते हैं; वे तार उत्पन्न करते हैं। ग्रामर उन भाषाओं का विवरण हैं जो भाषा में निहित सभी संभावित तारों को उत्पन्न करने के साधन प्रदान करते हैं। यह बताने के लिए कि क्या भाषा में कोई विशेष स्ट्रिंग निहित है, आप पहचानकर्ता का उपयोग करेंगे, कुछ प्रकार के automaton जो किसी दिए गए स्ट्रिंग को संसाधित करते हैं और "हाँ" या "नहीं" कहते हैं।
एक context-free grammar (CFG) एक व्याकरण जहां है (जैसा कि आप का उल्लेख किया) प्रत्येक उत्पादन प्रपत्र एक → डब्ल्यू, जहां एक एक nonterminal है और w टर्मिनलों और nonterminals के एक स्ट्रिंग है। अनौपचारिक रूप से, एक सीएफजी एक व्याकरण है जहां किसी भी बिंदु पर किसी भी nonterminal को इसके किसी भी प्रोडक्शन में विस्तारित किया जा सकता है। व्याकरण की भाषा टर्मिनलों के तारों का सेट है जो प्रारंभ प्रतीक से प्राप्त की जा सकती हैं।
एक context-sensitive grammar (CSG) एक व्याकरण जहां प्रत्येक उत्पादन प्रपत्र मोम → wyx, जहां डब्ल्यू और एक्स हैं टर्मिनलों और nonterminals और y के तार भी टर्मिनलों के एक स्ट्रिंग है है। दूसरे शब्दों में, प्रोडक्शंस नियम देते हैं, "यदि आप किसी दिए गए संदर्भ में देखते हैं, तो आप स्ट्रिंग वाई द्वारा ए को प्रतिस्थापित कर सकते हैं।" यह एक दुर्भाग्यपूर्ण है कि इन व्याकरणों को "संदर्भ-संवेदनशील व्याकरण" कहा जाता है क्योंकि इसका मतलब है कि "संदर्भ मुक्त" और "संदर्भ-संवेदनशील" विरोध नहीं करते हैं, और इसका मतलब है कि व्याकरण के कुछ वर्ग हैं जो तर्कसंगत रूप से बहुत सारे संदर्भ लेते हैं खाते में जानकारी लेकिन औपचारिक रूप से संदर्भ-संवेदनशील नहीं माना जाता है।
यह निर्धारित करने के लिए कि क्या एक सीएफजी या सीएसजी में एक स्ट्रिंग निहित है, वहां कई दृष्टिकोण हैं। सबसे पहले, आप दिए गए व्याकरण के लिए एक पहचानकर्ता बना सकते हैं। सीएफजी के लिए, pushdown automaton (पीडीए) एक प्रकार का automaton है जो सटीक संदर्भ-मुक्त भाषाओं को स्वीकार करता है, और किसी भी सीएफजी को पीडीए में बदलने के लिए एक सरल निर्माण है। संदर्भ-संवेदनशील व्याकरण के लिए, आप जिस automaton का उपयोग करेंगे, उसे linear bounded automaton (LBA) कहा जाता है।
हालांकि, इन उपरोक्त दृष्टिकोण, अगर नैतिक व्यवहार करते हैं, तो वे बहुत कुशल नहीं हैं। यह निर्धारित करने के लिए कि एक सीएफजी की भाषा में एक स्ट्रिंग निहित है, वहां कहीं अधिक कुशल एल्गोरिदम हैं। उदाहरण के लिए, कई व्याकरणों में LL(k) या LR(k) उनके लिए बनाए गए पार्सर्स हो सकते हैं, जो आपको व्याकरण में एक स्ट्रिंग निहित करने का निर्णय लेते हैं (रैखिक समय में)।सभी व्याकरणों को Earley parser का उपयोग करके पार्स किया जा सकता है, जिसमें ओ (एन) यह निर्धारित कर सकता है कि व्याकरण में लम्बाई एन की एक स्ट्रिंग निहित है (दिलचस्प बात यह है कि यह ओ (एन) में किसी भी संगत सीएफजी को पार्स कर सकती है, और लुकहेड के साथ ओ (एन) समय में किसी भी एलआर (के) व्याकरण को पार्स कर सकते हैं!)। यदि आप पूरी तरह से सवाल में रुचि रखते थे "व्याकरण जी द्वारा उत्पन्न भाषा में स्ट्रिंग एक्स है?", तो इन दृष्टिकोणों में से एक उत्कृष्ट होगा। यदि आप जानना चाहते थे कि स्ट्रिंग एक्स कैसे उत्पन्न हुआ था (parse tree) ढूंढकर, आप इन जानकारी को भी प्रदान करने के लिए इन दृष्टिकोणों को अनुकूलित कर सकते हैं। हालांकि, सीएसजी को पार्स करना आम तौर पर पीएसपीएसीई-पूर्ण है, इसलिए उनके लिए कोई ज्ञात पार्सिंग एल्गोरिदम नहीं है जो सबसे खराब मामले बहुपद समय में चलते हैं। कुछ एल्गोरिदम हैं जो अभ्यास में जल्दी से चलते हैं, हालांकि। पार्सिंग तकनीक के लेखकों: एक प्रैक्टिकल गाइड (नीचे देखें) ने a fantastic page containing all sorts of parsing algorithms को एक साथ रखा है, जिसमें संदर्भ-संवेदनशील भाषाओं का विश्लेषण किया गया है।
आप, पार्स करने के बारे में जानने उत्कृष्ट पुस्तक "Parsing Techniques: A Practical Guide, Second Edition" Grüne और याकूब, जो निर्धारित करने के लिए एक स्ट्रिंग एक व्याकरण में निहित है कि क्या के लिए पार्स एल्गोरिदम के सभी प्रकार की चर्चा और, इसलिए यदि द्वारा बाहर की जाँच पर विचार में रुचि रखते हैं , यह पार्सिंग एल्गोरिदम द्वारा कैसे उत्पन्न होता है।
आशा है कि इससे मदद मिलती है!
[विकी व्याकरण] (http://en.wikipedia.org/wiki/Formal_grammar) में उदाहरण है, क्या यह उदाहरण है कि मुझे यह दिखाने के लिए लिखना चाहिए कि व्याकरण एक स्ट्रिंग स्वीकार करता है? लेकिन मैं सोच रहा था कि मैं इसे संदर्भ-मुक्त और संदर्भ-संवेदनशील – user1004413