LL grammar
औपचारिक भाषा सिद्धांत में, एल. एल. व्याकरण एक संदर्भ-मुक्त व्याकरण है जिसे एल. एल. पार्सर द्वारा पार्स किया जा सकता है, जो इनपुट को बाएं से दाएं पार्स करता है, और वाक्य की सबसे बाईं व्युत्पत्ति का निर्माण करता है (इसलिए एल. एल., एल. आर. पार्सर की तुलना में जो सबसे दाएं व्युत्पत्ति का निर्माण करता है)। एल. एल. व्याकरण वाली भाषा को एल. एल. भाषा के रूप में जाना जाता है। ये क्रमशः नियतात्मक संदर्भ-मुक्त व्याकरण (डी. सी. एफ. जी.) और नियतात्मक संदर्भ-मुक्त भाषाओं (डी. सी. एफ. एल.) के उपसमुच्चय हैं। एक का कहना है कि एक दिया गया व्याकरण या भाषा "एक एल. एल. व्याकरण/भाषा है" या बस "एल. एल. है" यह इंगित करने के लिए कि यह इस वर्ग में है। एल. एल. पार्सर तालिका-आधारित पार्सर होते हैं, जो एल. आर. पार्सर के समान होते हैं। एल. एल. व्याकरण को वैकल्पिक रूप से सटीक रूप से उन के रूप में वर्णित किया जा सकता है जिन्हें एक भविष्यसूचक पार्सर द्वारा पार्स किया जा सकता है-बिना बैकट्रैकिंग के एक पुनरावर्ती वंश पार्सर-और इन्हें आसानी से हाथ से लिखा जा सकता है। यह लेख एल. एल. व्याकरण के औपचारिक गुणों के बारे में है; पार्सिंग के लिए, एल. एल. पार्सर या रिकर्सिव डिसेंट पार्सर देखें। एक प्राकृतिक संख्या को देखते हुए, एक संदर्भ-मुक्त व्याकरण एक एल. एल. (के) व्याकरण है यदि प्रतीकों तक की लंबाई के प्रत्येक अंतिम प्रतीक स्ट्रिंग के लिए, प्रत्येक गैर-अंतिम प्रतीक के लिए, और प्रत्येक अंतिम प्रतीक स्ट्रिंग के लिए, अधिक से अधिक एक उत्पादन नियम है जैसे कि कुछ अंतिम प्रतीक स्ट्रिंग के लिए, स्ट्रिंग को प्रारंभ प्रतीक से प्राप्त किया जा सकता है, पहले नियम लागू करने के बाद से प्राप्त किया जा सकता है, और सहमत होने के पहले प्रतीक। एक वैकल्पिक, लेकिन समतुल्य, औपचारिक परिभाषा निम्नलिखित हैः एक एल. एल. (के) व्याकरण है यदि, मनमाने ढंग से व्युत्पत्तियों के लिए जब के पहले प्रतीक उनके साथ सहमत होते हैं, तो। अनौपचारिक रूप से, जब एक पार्सर अपने सबसे बाएं नॉन-टर्मिनल के साथ व्युत्पन्न होता है और पहले से ही इनपुट से उपभोग कर चुका होता है, तो उसे देखकर और वर्तमान इनपुट के अगले प्रतीकों को देखकर, पार्सर निश्चित रूप से उत्पादन नियम की पहचान कर सकता है। जब पिछले इनपुट पर विचार किए बिना भी नियम की पहचान संभव है, तो व्याकरण को एक मजबूत एल. एल. (के) व्याकरण कहा जाता है। एक मजबूत एल. एल. (के) व्याकरण की औपचारिक परिभाषा में, के लिए सार्वभौमिक परिमापक को हटा दिया जाता है, और के लिए "कुछ के लिए" परिमापक में जोड़ा जाता है। प्रत्येक एल. एल. (के) व्याकरण के लिए, संरचनात्मक रूप से समतुल्य मजबूत एल. एल. (के) व्याकरण का निर्माण किया जा सकता है। एल. एल. (के) भाषाओं का वर्ग समूहों का एक सख्ती से बढ़ता हुआ क्रम बनाता हैः एल. एल. (0) एल. एल. (1) एल. एल. (2)। यह निर्णायक है कि दिया गया व्याकरण जी एल. एल. (के) है या नहीं, लेकिन यह निर्णायक नहीं है कि क्या एक मनमाना व्याकरण कुछ के के लिए एल. एल. (के) है। यह भी निर्णायक है कि क्या दिया गया एल. आर. (के) व्याकरण भी कुछ एम के लिए एल. एल. (एम) व्याकरण है। प्रत्येक एल. एल. (के) व्याकरण भी एक एल. आर. (के) व्याकरण है। एक ε-मुक्त LL (1) व्याकरण भी एक SLR (1) व्याकरण है। खाली और गैर-खाली दोनों व्युत्पत्तियों वाले प्रतीकों के साथ एक एल. एल. (1) व्याकरण भी एक एल. ए. एल. आर. (1) व्याकरण है। केवल खाली व्युत्पत्ति वाले प्रतीकों के साथ एक एल. एल. (1) व्याकरण एल. ए. एल. आर. (1) हो भी सकता है और नहीं भी। एल. एल. व्याकरण में लेफ्ट रिकर्शन वाले नियम नहीं हो सकते हैं। प्रत्येक एल. एल. (के) व्याकरण जो ε-मुक्त है, उसे ग्रेबाख सामान्य रूप में एक समकक्ष एल. एल. (के) व्याकरण में बदला जा सकता है (जिसमें परिभाषा के अनुसार बाएं पुनरावृत्ति के साथ नियम नहीं हैं)। रेगुलर केस एक अंतिम वर्णमाला होने दें। के विभाजन को नियमित विभाजन कहा जाता है यदि प्रत्येक के लिए भाषा नियमित है। एक संदर्भ मुक्त व्याकरण होने दें और इसका एक नियमित विभाजन होने दें। हम कहते हैं कि यह एक एल. एल. () व्याकरण है यदि, मनमाने ढंग से व्युत्पत्तियों के लिए ऐसा है कि यह उसका अनुसरण करता है। एक व्याकरण जी को एल. एल.-नियमित (एल. एल. आर.) कहा जाता है यदि इसका एक नियमित विभाजन मौजूद है कि जी एल. एल. () है। एक भाषा एल. एल.-नियमित है यदि यह एल. एल.-नियमित व्याकरण द्वारा उत्पन्न की जाती है। एल. एल. आर. व्याकरण असंदिग्ध होते हैं और बाएं-पुनरावर्ती नहीं हो सकते हैं। प्रत्येक एल. एल. (के) व्याकरण एल. एल. आर. है। प्रत्येक एल. एल. (के) व्याकरण नियतात्मक है, लेकिन एक एल. एल. आर. व्याकरण मौजूद है जो नियतात्मक नहीं है। इसलिए एल. एल. आर. व्याकरण का वर्ग प्रत्येक के के लिए एल. एल. (के) के संयोजन से सख्ती से बड़ा है। यह निर्णायक है कि, एक नियमित विभाजन को देखते हुए, दिया गया व्याकरण एल. एल. () है या नहीं। हालाँकि, यह निर्णायक नहीं है कि एक मनमाना व्याकरण जी एलएलआर है या नहीं। यह इस तथ्य के कारण है कि यह तय करना कि क्या व्याकरण जी एक नियमित भाषा उत्पन्न करता है, जो जी के लिए एक नियमित विभाजन खोजने के लिए आवश्यक होगा, पोस्ट पत्राचार समस्या तक कम किया जा सकता है। प्रत्येक एलएलआर व्याकरण एलआर-नियमित (एलआरआर, एलआर (के) व्याकरण के लिए समतुल्य) है, लेकिन एक एलआर (1) व्याकरण मौजूद है जो एलएलआर नहीं है। ऐतिहासिक रूप से, एल. एल. आर. व्याकरण ने एल. आर. आर. व्याकरण के आविष्कार का अनुसरण किया। एक नियमित विभाजन को देखते हुए एक मूर मशीन का निर्माण किया जा सकता है ताकि पार्सिंग को दाएँ से बाएँ स्थानांतरित किया जा सके, नियमित उत्पादन के उदाहरणों की पहचान की जा सके। एक बार ऐसा करने के बाद, एक एल. एल. (1) पार्सर रैखिक समय में ट्रांसड्यूस्ड इनपुट को संभालने के लिए पर्याप्त है। इस प्रकार, एल. एल. आर. पार्सर एल. एल. (के) पार्सर से सख्ती से बड़े व्याकरण के एक वर्ग को संभाल सकते हैं, जबकि समान रूप से कुशल हैं। इसके बावजूद एल. एल. आर. के सिद्धांत का कोई बड़ा अनुप्रयोग नहीं है। एक संभावित और बहुत ही प्रशंसनीय कारण यह है कि एल. एल. (के) और एल. आर. (के) पार्सर के लिए उत्पादक एल्गोरिदम हैं, लेकिन एल. एल. आर./एल. आर. आर. पार्सर उत्पन्न करने की समस्या तब तक अनिश्चित है जब तक कि किसी ने पहले से नियमित विभाजन का निर्माण नहीं किया हो। लेकिन व्याकरण को देखते हुए एक उपयुक्त नियमित विभाजन के निर्माण की समस्या भी अनिश्चित है। सरल नियतात्मक भाषाएँ एक संदर्भ-मुक्त व्याकरण को सरल नियतात्मक, या बस सरल कहा जाता है, यदि यह ग्रेबाख सामान्य रूप में है (यानी। प्रत्येक नियम का रूप होता है), और एक ही नॉन-टर्मिनल के लिए अलग-अलग दाहिने हाथ की भुजाएँ हमेशा अलग-अलग टर्मिनलों से शुरू होती हैं। तारों के एक समूह को एक सरल नियतात्मक, या बस सरल, भाषा कहा जाता है, अगर इसमें एक सरल नियतात्मक व्याकरण है। ग्रेबाख सामान्य रूप में ε-मुक्त LL (1) व्याकरण वाली भाषाओं का वर्ग सरल नियतात्मक भाषाओं के वर्ग के बराबर होता है। इस भाषा वर्ग में नियमित समूह शामिल हैं जिनमें ε नहीं है। इसके लिए समतुल्यता निर्णायक है, जबकि समावेश नहीं है। एल. एल. व्याकरण, विशेष रूप से एल. एल. (1) व्याकरण, बहुत व्यावहारिक रुचि के हैं, क्योंकि उन्हें एल. एल. पार्सर या पुनरावर्ती वंश पार्सर द्वारा विश्लेषित करना आसान है, और इस कारण से एल. एल. (1) होने के लिए डिज़ाइन किए गए हैं। k के उच्च मूल्य वाले व्याकरण पर आधारित भाषाओं को पारंपरिक रूप से विश्लेषण करना मुश्किल माना गया है, हालांकि यह अब कम सच है क्योंकि मनमाने k के लिए LL (k) व्याकरण का समर्थन करने वाले पार्सर जनरेटरों की उपलब्धता और व्यापक उपयोग को देखते हुए। LL (k) और LL (*) पार्सरों की सूची के लिए पार्सर जनरेटरों की तुलना भी देखें।