कंपाइलरः एलएल (0) आणि एलआर (0) पार्सर्समध्ये काय फरक आहे. एलएल (0) पार्सर्स अशी एखादी गोष्ट आहे का?


उत्तर 1:

हा प्रश्न एलएल (0) पार्सर्सवर केंद्रित असल्याचे दिसते आहे, म्हणून आपण त्यांना परिभाषित करूया. एक एलएल (0) पार्सर, उत्पादन सुरु असताना टोकनचा वापर करून डावीकडून उजवी पार्स करते की कोणते उत्पादन वापरावे हे ठरवण्यासाठी. त्या 0 टोकन म्हणजे काय, याचा अर्थ असा आहे की पार्सर कोणते उत्पादन लागू करायचे ते निर्धारित करण्यासाठी विश्लेषित मजकूराचा वापर करू शकत नाही. याचा अर्थ असा की पार्सर कोणतीही निवड करू शकत नाही. हे टोकनच्या अनुक्रमणाने नेमके अनुक्रम विश्लेषित करण्यापूर्वी हे माहित असले पाहिजे. टोकनचा क्रम निश्चित केला जाणे आवश्यक आहे, याचा अर्थ असा आहे की पार्सर पार्स करणारा एकच अनुक्रम असू शकतो. अशाप्रकारे, आपल्याकडे असे एक विश्लेषक असू शकेल जे "हॅलो वर्ल्ड!" स्वीकारेल यासारख्या व्याकरणासह:

ध्येय: "हॅलो" व्हाइटस्पेस "वर्ल्ड" उद्गार-चिन्ह;

लक्षात घ्या की लेक्झर टोकनशी कसे जुळतात हे केवळ भिन्न भिन्नता आहेत.

(मला आशा आहे की संकेतन स्पष्ट आहे - हे मी याॅक ++ मध्ये वापरत असलेल्या मूळ रूपात आहे. कोट केलेले तार टोकन आहेत, जसे की कोणतेही परिभाषित केलेले नाहीत.)

विश्लेषक नेहमीच टोकनच्या समान क्रमांची अपेक्षा करतो. आमच्या पहिल्या उदाहरणाप्रमाणेच, फक्त एकच नियम असणे आवश्यक नाही. हे असे दिसू शकते.

ध्येयः हॅलो-पार्ट व्हाईटस्पेस एंड-पार्ट;

हॅलो-भाग: हॅलो 1;

हॅलो 1: "हॅलो";

शेवटचा भाग: जगातील भाग शेवटचा भाग;

जागतिक भाग: "विश्व";

शेवटचा भाग: "!";

तथापि, कोणत्याही नियमात कोणतेही "किंवा" (|) ऑपरेटर कसे नसतात आणि नॉन-टर्मिनल प्रति नियम फक्त एकच आहे याची नोंद घ्या. हे असेच आहे जे पार्सरला कोणत्याही नियमात कोणताही भेदभाव न करता टोकन (पार्कर कोणत्या मार्गाने जातो हे निवडणारे टोकन) कसे वापरावे हे जाणून घेण्यास अनुमती देते, ज्यामुळे व्याकरण एलएल (0) होते.

आता, रिकर्सिव उत्पादन वापरणे शक्य आहे आणि तरीही एलएल (0) व्याकरण आहे? उत्तर "नाही" आहे. आमच्याकडे रिकर्सिव नियम असल्यास काय होते ते पाहूया.

ध्येय: "x" ध्येय "y";

लक्षात ठेवा, आम्हाला नॉन-टर्मिनल प्रति केवळ एक नियम अनुमत आहे आणि "किंवा" ऑपरेटर नाही. जेव्हा, जेव्हा आपण ध्येय पुन्हा पुन्हा घेण्यास उद्युक्त करतो तेव्हा आपण आपल्याला अशा मार्गाकडे नेले पाहिजे जिथे आपण पुन्हा त्या रिकर्सीव्ह विनंती, अनंत पळवाटकडे येऊ. स्वत: ला सिद्ध करा की आम्ही आमची या घरट्याची घरटी कशी आहे किंवा रिकर्सन अप्रत्यक्ष आहे याने काही फरक पडत नाही. त्याचा परिणाम नेहमी अनंत पळवाटात होईल.

अशा प्रकारे, एलएल (0) व्याकरणाने टोकनची एक मर्यादित यादी विश्लेषित करणे आवश्यक आहे, अगदी एक मर्यादित यादी (प्रत्येक वेळी समान यादी).

एलआर (0) च्या अर्थातील फरक लक्षात घ्या. एलआर (के) पार्सरला उत्पादनामध्ये भेदभाव करण्यासाठी कोणतेही (जितके आवडते तितके) टोकन वापरण्याची अनुमती आहे, तसेच उत्पादन कमी होते की नाही हे निर्धारित करण्यासाठी कमी करते तेव्हा संदर्भातून के टोकन पर्यंत. एलआर (0) प्रकरणात ते कमी करायचे की नाही हे निर्धारित करण्यासाठी अतिरिक्त टोकन वापरू शकत नाही. नियमातील टोकन कमी करण्याच्या आधारे हे सोपे निर्णय घेणे आवश्यक आहे. येथे एक साधा एलआर (0) व्याकरण आहे:

ध्येय: "x" | "(" ध्येय ")";

हे व्याकरण कित्येक संख्या कंसात घेरलेल्या "x" चे विश्लेषण करते. लक्षात घ्या की तो "x" टोकन आणि कोणता नियम लागू करायचा हे ठरवण्यासाठी "(" टोकन) वापरू शकतो. एलआर (0) मध्ये 0 नियमानुसार टोकनचा वापर प्रतिबंधित करत नाही, जसे 0 एलएल (0) मध्ये. केवळ एक गोष्ट प्रतिबंधित करते टोकनचा वापर (संदर्भानुसार, टर्मिनल नसलेल्या काही वापराच्या नियमानंतर) कमी करण्याचा निर्णय घेताना. या व्याकरणाला कमी करण्याचा निर्णय घेण्याची आवश्यकता नाही. पहिल्या पर्यायानुसार, ते पाहिल्यावर कमी होते दुसर्‍या "x" ने ")" पाहिल्यानंतर कमी होते. नियमातील टोकन नियम नेमका कधी कमी करायचा हे ठरवतात.


उत्तर 2:

एलएल (0) पार्सरचा अर्थ असा आहे की पुढे न दिसता डावीकडून व्युत्पन्न वापरून ते डावीकडून उजवीकडे टोकन प्रवाहावर प्रक्रिया करतात. सैद्धांतिकदृष्ट्या, एलएल (0) पार्सर्स शक्य आहेत, परंतु ते अस्तित्वात असले तरीही, मी त्यांचा जास्त वापर करत नाही. एलएल (0) पार्सर्सना अंदाज आहे की सध्याच्या नॉन-टर्मिनलवर आधारित कोणती प्रॉडक्शन लागू करावी लागेल शून्य दिसावी. अशा व्याकरणांमध्ये, प्रत्येक नॉन टर्मिनलशी फक्त एकच उत्पादन संबंधित असू शकते आणि कोणतीही पुनरावृत्ती होऊ नये.

एलआर (0) पार्सर्सचा अर्थ असा आहे की ते शून्यासह राइटस्टॉस्ट व्युत्पन्न वापरून, डावीकडून उजवीकडे टोकन प्रवाहावर प्रक्रिया करतात. याचा अर्थ असा की ते पार्सेचे झाड तळापासून वरपर्यंत तयार करतात, तर एलएल (0) पार्सर्स पार्स ट्री वरुन तळाशी बांधतात.