एलएल पार्सर: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 26: Line 26:


:<math>S\ \overset{(1)}{\Rightarrow}\ E\ \overset{(2)}{\Rightarrow}\ (E+E)\ \overset{(2)}{\Rightarrow}\ ((E+E)+E)\ \overset{(3)}{\Rightarrow}\ ((i+E)+E)\ \overset{(3)}{\Rightarrow}\ ((i+i)+E)\ \overset{(3)}{\Rightarrow}\ ((i+i)+i)</math>
:<math>S\ \overset{(1)}{\Rightarrow}\ E\ \overset{(2)}{\Rightarrow}\ (E+E)\ \overset{(2)}{\Rightarrow}\ ((E+E)+E)\ \overset{(3)}{\Rightarrow}\ ((i+E)+E)\ \overset{(3)}{\Rightarrow}\ ((i+i)+E)\ \overset{(3)}{\Rightarrow}\ ((i+i)+i)</math>
सामान्यतः, सबसे बाएं गैर-टर्मिनल का विस्तार करने के लिए नियम का चयन करते समय अनेक संभावनाएं होती हैं। पिछले उदाहरण के चरण 2 में, पार्सर को यह चुनना होगा कि नियम 2 या नियम 3 प्रयुक्त करना है :
सामान्यतः, सबसे बाएं गैर-टर्मिनल का विस्तार करने के लिए नियम का चयन करते समय अनेक संभावनाएं होती हैं। पिछले उदाहरण के फेज 2 में, पार्सर को यह चुनना होगा कि नियम 2 या नियम 3 प्रयुक्त करना है :


:<math>S\ \overset{(1)}{\Rightarrow}\ E\ \overset{(?)}{\Rightarrow}\ ?</math>
:<math>S\ \overset{(1)}{\Rightarrow}\ E\ \overset{(?)}{\Rightarrow}\ ?</math>
कुशल होने के लिए, पार्सर को जब भी संभव हो, बिना पीछे हटे, इस विकल्प को निश्चित रूप से चुनने में सक्षम होना चाहिए। कुछ ग्रामर के लिए, यह अपठित इनपुट (बिना पढ़े) पर द्रष्टि डालकर ऐसा कर सकता है। हमारे उदाहरण में, यदि पार्सर जानता है कि अगला अपठित प्रतीक है <math>(</math>एकमात्र सही नियम जिसका उपयोग किया जा सकता है वह 2 है।
कुशल होने के लिए, पार्सर को जब भी संभव हो, बिना पीछे हटे, इस विकल्प को निश्चित रूप से चुनने में सक्षम होना चाहिए। कुछ ग्रामर के लिए, यह अपठित इनपुट (बिना पढ़े) पर द्रष्टि डालकर ऐसा कर सकता है। हमारे उदाहरण में, यदि पार्सर जानता है कि अगला अपठित प्रतीक है <math>(</math>एकमात्र सही नियम जिसका उपयोग किया जा सकता है वह 2 है।




Line 36: Line 37:
हम उपरोक्त विश्लेषण का उपयोग निम्नलिखित औपचारिक परिभाषा देने के लिए कर सकते हैं:
हम उपरोक्त विश्लेषण का उपयोग निम्नलिखित औपचारिक परिभाषा देने के लिए कर सकते हैं:


होने देना <math>G</math> कांटेक्स्ट-फ्री ग्रामर बनें और <math>k \ge 1</math>. हम ऐसा कहते हैं <math>G</math> है <math>LL(k)</math>, यदि और केवल यदि किन्हीं दो सबसे बाईं व्युत्पत्तियों के लिए:
मान लीजिए <math>G</math> एक संदर्भ-मुक्त व्याकरण है और <math>k \ge 1</math> हम कहते हैं कि <math>G</math> <math>LL(k)</math> है, यदि और केवल यदि किन्हीं दो सबसे बाईं व्युत्पत्तियों के लिए:


# <math>S\ \Rightarrow\ \cdots\ \Rightarrow\ wA\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ w\beta\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ wu</math>
# <math>S\ \Rightarrow\ \cdots\ \Rightarrow\ wA\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ w\beta\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ wu</math>
# <math>S\ \Rightarrow\ \cdots\ \Rightarrow\ wA\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ w\gamma\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ wv</math>
# <math>S\ \Rightarrow\ \cdots\ \Rightarrow\ wA\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ w\gamma\alpha\ \Rightarrow\ \cdots\ \Rightarrow\ wv</math>
निम्नलिखित शर्त प्रयुक्त होती है: स्ट्रिंग का उपसर्ग <math>u</math> लम्बाई का <math>k</math> स्ट्रिंग के उपसर्ग के बराबर है <math>v </math> लम्बाई का <math>k</math> तात्पर्य <math>\beta\ =\ \gamma</math>.
निम्नलिखित नियम प्रयुक्त होती है: लंबाई <math>k</math> की स्ट्रिंग <math>u</math> का उपसर्ग लंबाई <math>k</math> की स्ट्रिंग <math>v </math> के उपसर्ग के सामान होता है। अर्थात <math>\beta\ =\ \gamma</math>
 
 
इस परिभाषा में, <math>S</math> प्रारंभ प्रतीक है और <math>A</math> कोई गैर-टर्मिनल है। पहले से व्युत्पन्न इनपुट <math>w</math>, और अभी तक अपठित <math>u</math> और <math>v</math> टर्मिनलों के तार हैं। ग्रीक अक्षर <math>\alpha</math> <math>\beta</math> और <math>\gamma</math> दोनों टर्मिनलों और गैर-टर्मिनलों (संभवतः रिक्त) की किसी भी स्ट्रिंग का प्रतिनिधित्व करते हैं। उपसर्ग की लंबाई लुकहेड बफ़र आकार से मेल खाती है, और परिभाषा कहती है कि यह बफ़र विभिन्न शब्दों के किन्हीं दो व्युत्पत्तियों के बीच अंतर करने के लिए पर्याप्त है।
 
=== पार्सर ===
 


इस परिभाषा में, <math>S</math> प्रारंभ प्रतीक है और <math>A</math> कोई भी गैर-टर्मिनल. पहले से ही व्युत्पन्न इनपुट <math>w</math>, और फिर भी अपठित <math>u</math> और <math>v</math> टर्मिनलों के तार हैं. यूनानी अक्षर <math>\alpha</math>, <math>\beta</math> और <math>\gamma</math> टर्मिनलों और गैर-टर्मिनलों (संभवतः खाली) दोनों की किसी भी स्ट्रिंग का प्रतिनिधित्व करें। उपसर्ग की लंबाई लुकहेड बफ़र आकार से मेल खाती है, और परिभाषा कहती है कि यह बफ़र विभिन्न शब्दों के किन्हीं दो व्युत्पत्तियों के बीच अंतर करने के लिए पर्याप्त है।


== पार्सर == <math>LL(k)</math> h> पार्सर [[नियतात्मक पुशडाउन ऑटोमेटन]] है जिसमें अगले पर द्रष्टि डालने की क्षमता होती है <math>k</math> बिना पढ़े इनपुट प्रतीक। इस झलक क्षमता का अनुकरण परिमित स्थिति स्थान में लुकहेड बफर सामग्री को संग्रहीत करके किया जा सकता है, क्योंकि बफर और इनपुट वर्णमाला दोनों आकार में सीमित हैं। नतीजतन, यह ऑटोमेटन को अधिक शक्तिशाली नहीं बनाता है, बल्कि सुविधाजनक अमूर्तता है।
<math>LL(k)</math> पार्सर एक [[नियतात्मक पुशडाउन ऑटोमेटन]] है जिसमें बिना पढ़े अगले <math>k</math> इनपुट प्रतीकों पर द्रष्टि डालने की क्षमता है। इस झलक क्षमता का अनुकरण परिमित स्थिति स्थान में लुकहेड बफर पदार्थ को संग्रहीत करके किया जा सकता है, क्योंकि बफर और इनपुट अल्फाबेट दोनों आकार में सीमित हैं। परिणाम स्वरुप, यह ऑटोमेटन को अधिक शक्तिशाली नहीं बनाता है, किन्तु एक सुविधाजनक एब्स्ट्रेक्ट है।


स्टैक वर्णमाला है <math>\Gamma = N \cup \Sigma</math>, कहाँ:
स्टैक अल्फाबेट <math>\Gamma = N \cup \Sigma</math> है, जहां:
* <math>N</math> गैर-टर्मिनलों का सेट है;
* <math>N</math> गैर-टर्मिनलों का सेट है;
* <math>\Sigma</math> विशेष एंड-ऑफ-इनपुट (ईओआई) प्रतीक के साथ टर्मिनल (इनपुट) प्रतीकों का सेट <math>\$</math>.
* <math>\Sigma</math> विशेष एंड-ऑफ-इनपुट (ईओआई) प्रतीक के साथ टर्मिनल (इनपुट) प्रतीकों का सेट <math>\$</math>.
पार्सर स्टैक में प्रारंभ में EOI के ऊपर प्रारंभिक प्रतीक होता है: <math>[\ S\ \$\ ]</math>. ऑपरेशन के दौरान, पार्सर बार-बार प्रतीक को बदल देता है <math>X</math> ढेर के शीर्ष पर:
पार्सर स्टैक में प्रारंभ में EOI के ऊपर प्रारंभिक प्रतीक होता है:<math>[\ S\ \$\ ]</math>। ऑपरेशन के समय, पार्सर बार-बार स्टैक के शीर्ष पर प्रतीक <math>X</math> को परिवर्तित कर देता है:
* कुछ के साथ <math>\alpha</math>, अगर <math>X \in N</math> और नियम है <math>X \to \alpha</math>;
*कुछ <math>\alpha</math> के साथ यदि <math>X \in N</math> और एक नियम <math>X \to \alpha</math> है
* साथ <math>\epsilon</math> (कुछ नोटेशन में <math>\lambda</math>), अर्थात। <math>X</math> यदि, स्टैक से हटा दिया गया है <math>X \in \Sigma</math>. इस मामले में, इनपुट प्रतीक <math>x</math> पढ़ा जाता है और यदि <math>x \neq X</math>, पार्सर इनपुट को अस्वीकार कर देता है।
*<math>\epsilon</math> के साथ (कुछ नोटेशन <math>\lambda</math> में), अर्थात <math>X</math> को स्टैक से हटा दिया जाता है, यदि <math>X \in \Sigma</math> है। इस स्थिति में, एक इनपुट प्रतीक <math>x</math> पढ़ा जाता है और यदि <math>x \neq X</math> है, तो पार्सर इनपुट को अस्वीकार कर देता है।
यदि स्टैक से हटाया जाने वाला अंतिम प्रतीक ईओआई है, तो पार्सिंग सफल है; ऑटोमेटन खाली स्टैक के माध्यम से स्वीकार करता है।
यदि स्टैक से हटाया जाने वाला अंतिम प्रतीक ईओआई है, तो पार्सिंग सफल है; ऑटोमेटन रिक्त स्टैक के माध्यम से स्वीकार करता है।


अवस्थाएँ और संक्रमण फलन स्पष्ट रूप से नहीं दिए गए हैं; इसके बजाय उन्हें अधिक सुविधाजनक पार्स तालिका का उपयोग करके निर्दिष्ट (उत्पन्न) किया जाता है। तालिका निम्नलिखित मानचित्रण प्रदान करती है:
अवस्थाएँ और संक्रमण फलन स्पष्ट रूप से नहीं दिए गए हैं; इसके अतिरिक्त उन्हें अधिक सुविधाजनक पार्स टेबल का उपयोग करके निर्दिष्ट (उत्पन्न) किया जाता है। टेबल निम्नलिखित मानचित्रण प्रदान करती है:
* पंक्ति: शीर्ष-स्टैक प्रतीक <math>X</math>
* पंक्ति: शीर्ष-स्टैक प्रतीक <math>X</math>
* कॉलम: <math>|w| \le k</math> लुकअहेड बफ़र सामग्री
* कॉलम: <math>|w| \le k</math> लुकअहेड बफ़र पदार्थ
* सेल: के लिए नियम संख्या <math>X \to \alpha</math> या <math>\epsilon</math>
* सेल: के लिए नियम संख्या <math>X \to \alpha</math> या <math>\epsilon</math>
यदि पार्सर वैध संक्रमण नहीं कर सकता है, तो इनपुट अस्वीकार कर दिया जाता है (खाली सेल)। तालिका को अधिक संक्षिप्त बनाने के लिए, आमतौर पर केवल गैर-टर्मिनल पंक्तियाँ प्रदर्शित की जाती हैं, क्योंकि टर्मिनलों के लिए क्रिया समान होती है।
यदि पार्सर वैध संक्रमण नहीं कर सकता है, तो इनपुट अस्वीकार कर दिया जाता है (रिक्त सेल)। टेबल को अधिक संक्षिप्त बनाने के लिए, सामान्यतः केवल गैर-टर्मिनल पंक्तियाँ प्रदर्शित की जाती हैं, क्योंकि टर्मिनलों के लिए क्रिया समान होती है।


== ठोस उदाहरण ==
== ठोस उदाहरण ==


=== सेट अप ===
=== सेट अप ===
LL(1) पार्सर की कार्यप्रणाली को समझाने के लिए हम निम्नलिखित छोटे LL(1) ग्रामर पर विचार करेंगे:
LL(1) पार्सर की कार्यप्रणाली को समझाने के लिए हम निम्नलिखित छोटे LL(1) ग्रामर पर विचार करेंगे


# एस → एफ
# S → F
# एस → ( एस + एफ )
# S → ( S + F )
# एफ → ए
# F → a


और निम्नलिखित इनपुट को पार्स करें:
और निम्नलिखित इनपुट को पार्स करें:


:( ए + ए )
:'''( a + a )'''


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


तालिका की प्रत्येक कोशिका ग्रामर के अधिकतम नियम (उसकी संख्या से पहचानी गई) की ओर इंगित कर सकती है। उदाहरण के लिए, उपरोक्त ग्रामर के लिए पार्सिंग तालिका में, गैर-टर्मिनल 'एस' और टर्मिनल '(' के लिए सेल नियम संख्या 2 की ओर इशारा करता है:
टेबल की प्रत्येक सेल ग्रामर के अधिकतम नियम (उसकी संख्या से पहचानी गई) की ओर संकेत कर सकती है। उदाहरण के लिए, उपरोक्त ग्रामर के लिए पार्सिंग टेबल में, गैर-टर्मिनल 'S' और टर्मिनल '(' के लिए सेल नियम संख्या 2 की ओर संकेत करता है:


:{| class="wikitable"
:{| class="wikitable"
Line 93: Line 99:
| {{sdash}}
| {{sdash}}
|}
|}
पार्सिंग तालिका बनाने के लिए एल्गोरिदम का वर्णन बाद के अनुभाग में किया गया है, किन्तु पहले देखते हैं कि पार्सर अपने इनपुट को संसाधित करने के लिए पार्सिंग तालिका का उपयोग कैसे करता है।
पार्सिंग टेबल बनाने के लिए एल्गोरिदम का वर्णन बाद के अनुभाग में किया गया है, किन्तु पहले देखते हैं कि पार्सर अपने इनपुट को संसाधित करने के लिए पार्सिंग टेबल का उपयोग कैसे करता है।


=== पार्सिंग प्रक्रिया ===
=== पार्सिंग प्रक्रिया ===


प्रत्येक चरण में, पार्सर इनपुट स्ट्रीम से अगले-उपलब्ध प्रतीक को पढ़ता है, और स्टैक से सबसे ऊपरी प्रतीक को पढ़ता है। यदि इनपुट प्रतीक और स्टैक-टॉप प्रतीक मेल खाते हैं, तो पार्सर उन दोनों को हटा देता है, इनपुट स्ट्रीम और स्टैक पर केवल बेजोड़ प्रतीकों को छोड़ देता है।
प्रत्येक फेज में, पार्सर इनपुट स्ट्रीम से अगले-उपलब्ध प्रतीक को पढ़ता है, और स्टैक से सबसे ऊपरी प्रतीक को पढ़ता है। यदि इनपुट प्रतीक और स्टैक-टॉप प्रतीक मेल खाते हैं, तो पार्सर उन दोनों को हटा देता है, इनपुट स्ट्रीम और स्टैक पर केवल बेजोड़ प्रतीकों को छोड़ देता है।


इस प्रकार, अपने पहले चरण में, पार्सर इनपुट प्रतीक '(' और स्टैक-टॉप प्रतीक 'S' को पढ़ता है। पार्सिंग तालिका निर्देश इनपुट प्रतीक '(' के शीर्ष वाले कॉलम और स्टैक-टॉप प्रतीक 'S' के नेतृत्व वाली पंक्ति से आता है; इस सेल में '2' होता है, जो पार्सर को नियम (2) प्रयुक्त करने का निर्देश देता है। पार्सर को 'S' को हटाकर स्टैक पर 'S' से '( S + F )' को फिर से लिखना होता है। 'स्टैक से और ')', 'F', '+', 'S', '(' को स्टैक पर धकेलें, और यह आउटपुट पर नियम संख्या 2 लिखता है। स्टैक तब बन जाता है:
इस प्रकार, अपने पहले फेज में, पार्सर इनपुट प्रतीक '(और स्टैक-टॉप प्रतीक 'S' को पढ़ता है। पार्सिंग टेबल निर्देश इनपुट प्रतीक '(शीर्ष वाले कॉलम और स्टैक-टॉप प्रतीक 'S' के नेतृत्व वाली पंक्ति से आता है; इस सेल में '2' होता है, जो पार्सर को नियम (2) प्रयुक्त करने का निर्देश देता है। पार्सर को 'S' को हटाकर स्टैक पर 'S' से '( S + F )' को फिर से लिखना होता है। 'F', '+', 'S',को स्टैक पर दाब, और यह आउटपुट पर नियम संख्या 2 लिखता है। स्टैक तब बन जाता है:<syntaxhighlight lang="abl">
 
[ (, S, +, F, ), $ ]
[(, एस, +, एफ, ), $ ]
</syntaxhighlight>दूसरे फेज में, पार्सर अपनी इनपुट स्ट्रीम और स्टैक से '(' को हटा देता है, क्योंकि वे अब मेल खाते हैं। स्टैक अब बन जाता है:<syntaxhighlight>
 
[ S, +, F, ), $ ]
दूसरे चरण में, पार्सर अपनी इनपुट स्ट्रीम और स्टैक से '(<nowiki/>' को हटा देता है, क्योंकि वे अब मेल खाते हैं। स्टैक अब बन जाता है:
</syntaxhighlight>
 
[एस, +, एफ, ), $ ]
 
अब पार्सर के इनपुट स्ट्रीम पर 'ए' और स्टैक टॉप के रूप में 'एस' है। पार्सिंग तालिका इसे ग्रामर से नियम (1) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 1 लिखने का निर्देश देती है। ढेर बन जाता है:


[एफ, +, एफ, ), $ ]


पार्सर के पास अब इनपुट स्ट्रीम पर 'ए' और स्टैक टॉप के रूप में 'एफ' है। पार्सिंग तालिका इसे ग्रामर से नियम (3) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 3 लिखने का निर्देश देती है। ढेर बन जाता है:
अब पार्सर के इनपुट स्ट्रीम पर 'A' और स्टैक टॉप के रूप में 'S' है। पार्सिंग टेबल इसे ग्रामर से नियम (1) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 1 लिखने का निर्देश देती है। संग्रह बन जाता है:<syntaxhighlight>
[ F, +, F, ), $ ]


[ए, +, एफ, ), $ ]
</syntaxhighlight>पार्सर के पास अब इनपुट स्ट्रीम पर 'A' और स्टैक टॉप के रूप में 'F' है। पार्सिंग टेबल इसे ग्रामर से नियम (3) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 3 लिखने का निर्देश देती है। संग्रह बन जाता है:<syntaxhighlight>
[ a, +, F, ), $ ]


पार्सर में अब इनपुट स्ट्रीम पर 'a' है और इसके स्टैक टॉप पर 'a' है। क्योंकि वे समान हैं, यह इसे इनपुट स्ट्रीम से हटा देता है और स्टैक के शीर्ष से पॉप कर देता है। पार्सर के पास इनपुट स्ट्रीम पर '+' होता है और '+' स्टैक के शीर्ष पर होता है, जिसका अर्थ है, 'ए' की तरह, इसे स्टैक से पॉप किया जाता है और इनपुट स्ट्रीम से हटा दिया जाता है। इस में यह परिणाम:
</syntaxhighlight>पार्सर में अब इनपुट स्ट्रीम पर 'a' है और इसके स्टैक टॉप पर 'a' है। क्योंकि वह समान हैं, यह इसे इनपुट स्ट्रीम से हटा देता है और स्टैक के शीर्ष से पॉप कर देता है। पार्सर के पास इनपुट स्ट्रीम पर '+' होता है और '+' स्टैक के शीर्ष पर होता है, जिसका अर्थ है, 'A' की तरह, इसे स्टैक से पॉप किया जाता है और इनपुट स्ट्रीम से हटा दिया जाता है। इस में यह परिणाम:


  [एफ, ), $ ]
  [F, ), $ ]


अगले तीन चरणों में पार्सर स्टैक पर 'एफ' को 'ए' से बदल देगा, आउटपुट स्ट्रीम में नियम संख्या 3 लिखेगा और स्टैक और इनपुट स्ट्रीम दोनों से 'ए' और ')' को हटा देगा। इस प्रकार पार्सर अपने स्टैक और इनपुट स्ट्रीम दोनों पर '$' के साथ समाप्त होता है।
अगले तीन फेजों में पार्सर स्टैक पर 'F' को 'A' से परिवर्तित कर देगा, आउटपुट स्ट्रीम में नियम संख्या 3 लिखेगा और स्टैक और इनपुट स्ट्रीम दोनों से 'A' और ')' को हटा देता है। इस प्रकार पार्सर अपने स्टैक और इनपुट स्ट्रीम दोनों पर '$' के साथ समाप्त होता है।


इस मामले में पार्सर रिपोर्ट करेगा कि उसने इनपुट स्ट्रिंग को स्वीकार कर लिया है और आउटपुट स्ट्रीम में नियम संख्याओं की निम्नलिखित सूची लिखेगा:
इस स्थिति में पार्सर रिपोर्ट करेगा कि उसने इनपुट स्ट्रिंग को स्वीकार कर लिया है और आउटपुट स्ट्रीम में नियम संख्याओं की निम्नलिखित सूची लिखेगा:


: [2, 1, 3, 3 ]
: [2, 1, 3, 3 ]


यह वास्तव में इनपुट स्ट्रिंग के कांटेक्स्ट-फ्री ग्रामर # व्युत्पत्ति और सिंटेक्स ट्री के लिए नियमों की सूची है, जो है:
यह वास्तव में इनपुट स्ट्रिंग के कांटेक्स्ट-फ्री ग्रामर व्युत्पत्ति और सिंटेक्स ट्री के लिए नियमों की सूची है, जो है:
 
: एस → (एस + एफ) → (एफ + एफ) → (ए + एफ) → (ए + ए)


===C++=== में पार्सर कार्यान्वयन
:: S → '''(''' S '''+''' F ''')''' → '''(''' F '''+''' F ''')''' → '''( a +''' F ''')''' → '''( a + a )'''


उदाहरण लैंग्वेज के लिए तालिका-आधारित LL पार्सर का सी++ कार्यान्वयन नीचे दिया गया है:
=== C++ में पार्सर कार्यान्वयन ===
उदाहरण लैंग्वेज के लिए टेबल-आधारित LL पार्सर का C++ कार्यान्वयन नीचे दिया गया है:
<syntaxhighlight lang=cpp>
<syntaxhighlight lang=cpp>
#include <iostream>
#include <iostream>
Line 313: Line 315:
== टिप्पणियाँ ==
== टिप्पणियाँ ==


जैसा कि उदाहरण से देखा जा सकता है, पार्सर तीन प्रकार के चरण निष्पादित करता है जो इस बात पर निर्भर करता है कि स्टैक का शीर्ष नॉनटर्मिनल है, टर्मिनल है या विशेष प्रतीक $ है:
जैसा कि उदाहरण से देखा जा सकता है, पार्सर तीन प्रकार के फेज निष्पादित करता है जो इस बात पर निर्भर करता है कि स्टैक का शीर्ष नॉनटर्मिनल है, टर्मिनल है या विशेष प्रतीक $ है:
* यदि शीर्ष नॉनटर्मिनल है तो पार्सर इस नॉनटर्मिनल और इनपुट स्ट्रीम पर प्रतीक के आधार पर पार्सिंग तालिका में देखता है कि उसे स्टैक पर नॉनटर्मिनल को बदलने के लिए ग्रामर के किस नियम का उपयोग करना चाहिए। नियम की संख्या आउटपुट स्ट्रीम पर लिखी जाती है। यदि पार्सिंग तालिका इंगित करती है कि ऐसा कोई नियम नहीं है तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
* यदि शीर्ष नॉनटर्मिनल है तो पार्सर इस नॉनटर्मिनल और इनपुट स्ट्रीम पर प्रतीक के आधार पर पार्सिंग टेबल में देखता है कि उसे स्टैक पर नॉनटर्मिनल को परिवर्तित करने के लिए ग्रामर के किस नियम का उपयोग करना चाहिए। नियम की संख्या आउटपुट स्ट्रीम पर लिखी जाती है। यदि पार्सिंग टेबल संकेत करती है कि ऐसा कोई नियम नहीं है तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
* यदि शीर्ष टर्मिनल है तो पार्सर इसकी तुलना इनपुट स्ट्रीम पर प्रतीक से करता है और यदि वे बराबर हैं तो वे दोनों हटा दिए जाते हैं। यदि वे समान नहीं हैं तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
* यदि शीर्ष टर्मिनल है तो पार्सर इसकी तुलना इनपुट स्ट्रीम पर प्रतीक से करता है और यदि वह सामान हैं तो वे दोनों हटा दिए जाते हैं। यदि वह समान नहीं हैं तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
* यदि शीर्ष $ है और इनपुट स्ट्रीम पर भी $ है तो पार्सर रिपोर्ट करता है कि उसने इनपुट को सफलतापूर्वक पार्स कर लिया है, अन्यथा यह त्रुटि की रिपोर्ट करता है। दोनों ही स्थितियों में पार्सर बंद हो जाएगा.
* यदि शीर्ष $ है और इनपुट स्ट्रीम पर भी $ है तो पार्सर रिपोर्ट करता है कि उसने इनपुट को सफलतापूर्वक पार्स कर लिया है, अन्यथा यह त्रुटि की रिपोर्ट करता है। दोनों ही स्थितियों में पार्सर बंद हो जाता है.
इन चरणों को तब तक दोहराया जाता है जब तक पार्सर बंद नहीं हो जाता है, और फिर यह या तो इनपुट को पूरी तरह से पार्स कर लेगा और आउटपुट स्ट्रीम में कांटेक्स्ट-फ्री ग्रामर # व्युत्पत्ति और सिंटेक्स पेड़ लिखेगा या यह त्रुटि की सूचना देगा।
इन फेजों को तब तक दोहराया जाता है जब तक पार्सर बंद नहीं हो जाता है, और फिर यह या तो इनपुट को पूरी तरह से पार्स कर लेगा और आउटपुट स्ट्रीम में कांटेक्स्ट-फ्री ग्रामर व्युत्पत्ति और सिंटेक्स पेड़ लिखेगा या यह त्रुटि की सूचना देता है।
 
== एक LL(1) पार्सिंग टेबल का निर्माण ==
 
पार्सिंग टेबल को भरने के लिए, हमें यह स्थापित करना होगा कि पार्सर को कौन सा ग्रामर नियम चुनना चाहिए यदि वह अपने स्टैक के शीर्ष पर नॉनटर्मिनल A और अपने इनपुट स्ट्रीम पर प्रतीक देखता है।
 
यह देखना सरल है कि ऐसा नियम A → w के रूप का होना चाहिए और w के अनुरूप लैंग्वेज में a से प्रारंभ होने वाली कम से कम स्ट्रिंग होनी चाहिए।


== एक LL(1) पार्सिंग तालिका का निर्माण ==
इस उद्देश्य के लिए हम w के पहले सेट को परिभाषित करते हैं, जिसे यहां 'Fi' (w) के रूप में लिखा गया है, टर्मिनलों के सेट के रूप में जो w में कुछ स्ट्रिंग की प्रारंभ में पाया जा सकता है, प्लस ε यदि रिक्त स्ट्रिंग भी w से संबंधित है।


पार्सिंग तालिका को भरने के लिए, हमें यह स्थापित करना होगा कि पार्सर को कौन सा ग्रामर नियम चुनना चाहिए यदि वह अपने स्टैक के शीर्ष पर नॉनटर्मिनल ए और अपने इनपुट स्ट्रीम पर प्रतीक देखता है।
नियमों A<sub>1</sub> → w<sub>1</sub>,…, A<sub>''n''</sub> → w<sub>''n''</sub> के साथ व्याकरण को देखते हुए, हम प्रत्येक नियम के लिए Fi(w<sub>''i''</sub>) और Fi(A<sub>''i''</sub>) की गणना इस प्रकार कर सकते हैं:
यह देखना सरल है कि ऐसा नियम A → w के रूप का होना चाहिए और w के अनुरूप लैंग्वेज में a से शुरू होने वाली कम से कम स्ट्रिंग होनी चाहिए।
#प्रत्येक Fi(A<sub>''i''</sub>) को रिक्त सेट के साथ प्रारंभ करें
इस उद्देश्य के लिए हम w के पहले सेट को परिभाषित करते हैं, जिसे यहां 'Fi' (w) के रूप में लिखा गया है, टर्मिनलों के सेट के रूप में जो w में कुछ स्ट्रिंग की शुरुआत में पाया जा सकता है, प्लस ε यदि खाली स्ट्रिंग भी w से संबंधित है।
#प्रत्येक नियम A<sub>''i''</sub> → w<sub>''i''</sub> के लिए Fi(w<sub>''i''</sub>) को Fi(A<sub>''i''</sub>) में जोड़ें, जहां Fi को इस प्रकार परिभाषित किया गया है:
नियम ए के साथ ग्रामर दिया गया<sub>1</sub> → डब्ल्यू<sub>1</sub>, …, ए<sub>''n''</sub> → डब्ल्यू<sub>''n''</sub>, हम Fi(''w'' की गणना कर सकते हैं<sub>''i''</sub>) और Fi(''ए''<sub>''i''</sub>) प्रत्येक नियम के लिए इस प्रकार है:
#* प्रत्येक टर्मिनल A के लिए Fi(aw') = { a }
# प्रत्येक Fi(''A'' को प्रारंभ करें<sub>''i''</sub>) खाली सेट के साथ
#* प्रत्येक नॉनटर्मिनल A के लिए Fi(Aw') = 'Fi'(A) जिसमें ε 'Fi'(A) में नहीं है
# Fi(w) जोड़ें<sub>''i''</sub>) से Fi(''ए''<sub>''i''</sub>) प्रत्येक नियम ए के लिए<sub>''i''</sub> → डब्ल्यू<sub>i</sub>, जहां Fi को इस प्रकार परिभाषित किया गया है:
#* प्रत्येक टर्मिनल ए के लिए Fi(aw') = { a }
#* प्रत्येक नॉनटर्मिनल ए के लिए Fi(Aw') = 'Fi'(A) जिसमें ε 'Fi'(A) में नहीं है
#* Fi(Aw' ) = ('Fi'(A) \ { ε }) ∪ Fi(w' ) 'Fi'(A) में ε के साथ प्रत्येक नॉनटर्मिनल A के लिए
#* Fi(Aw' ) = ('Fi'(A) \ { ε }) ∪ Fi(w' ) 'Fi'(A) में ε के साथ प्रत्येक नॉनटर्मिनल A के लिए
#* Fi(ε) = { ε }
#* Fi(ε) = { ε }
# Fi(w) जोड़ें<sub>''i''</sub>) से Fi(''ए''<sub>''i''</sub>) प्रत्येक नियम ए के लिए<sub>''i''</sub> → डब्ल्यू<sub>''i''</sub>
#प्रत्येक नियम A<sub>''i''</sub> → w<sub>''i''</sub> के लिए Fi(w<sub>''i''</sub>) को Fi(A<sub>''i''</sub>) में जोड़ें
# चरण 2 और 3 तब तक करें जब तक कि सभी Fi सेट समान न रहें।
# फेज 2 और 3 तब तक करें जब तक कि सभी Fi सेट समान न रहें।
परिणाम निम्नलिखित प्रणाली के लिए सबसे कम निश्चित बिंदु समाधान है:
परिणाम निम्नलिखित प्रणाली के लिए सबसे कम निश्चित बिंदु समाधान है:
* Fi(''A'') ⊇ Fi(''w'') प्रत्येक नियम A के लिए → ''w''
* Fi(''A'') ⊇ Fi(''w'') प्रत्येक नियम A के लिए → ''w''
* Fi(''a'') ⊇ { ''a'' }, प्रत्येक टर्मिनल ''a'' के लिए
* Fi(''a'') ⊇ { ''a'' }, प्रत्येक टर्मिनल ''a'' के लिए
* Fi(''w''<sub>0</sub> w<sub>1</sub>) ⊇ Fi('w''<sub>0</sub>) · में ( aq<sub>1</sub>), सभी शब्दों के लिए w<sub>0</sub> और डब्ल्यू<sub>1</sub>
* Fi(''w''<sub>0</sub> w<sub>1</sub>) ⊇ Fi('w''<sub>0</sub>) · Fi(w<sub>1</sub>), सभी शब्दों के लिए w<sub>0</sub> और w<sub>1</sub>''
* Fi(ε) ⊇ {ε}
* Fi(ε) ⊇ {ε}
जहां, यू और वी शब्दों के सेट के लिए, काटे गए उत्पाद को परिभाषित किया गया है <math>U \cdot V = \{ (uv):1 \mid u \in U, v \in V \}</math>, और w:1, लंबाई 2 या अधिक वाले शब्दों के प्रारंभिक लंबाई-1 उपसर्ग को दर्शाता है, या स्वयं w, यदि w की लंबाई 0 या 1 है।


दुर्भाग्य से, प्रथम-सेट पार्सिंग तालिका की गणना करने के लिए पर्याप्त नहीं हैं।
 
ऐसा इसलिए है क्योंकि किसी नियम का दाहिना भाग w अंततः खाली स्ट्रिंग पर फिर से लिखा जा सकता है।
जहां, U और V  शब्दों के सेट के लिए, काटे गए उत्पाद को <math>U \cdot V = \{ (uv):1 \mid u \in U, v \in V \}</math> द्वारा परिभाषित किया गया है, और w:1 यदि w की लंबाई 0 या 1 है, तो लंबाई 2 या अधिक वाले शब्दों के प्रारंभिक लंबाई-1 उपसर्ग या स्वयं w को दर्शाता है।
इसलिए पार्सर को नियम A → w का भी उपयोग करना चाहिए यदि ε 'Fi' (w) में है और यह इनपुट स्ट्रीम पर प्रतीक देखता है जो A का अनुसरण कर सकता है। इसलिए, हमें A के फॉलो-सेट की भी आवश्यकता है, जिसे यहां 'Fo' (A) के रूप में लिखा गया है, जिसे टर्मिनलों के सेट के रूप में परिभाषित किया गया है जैसे कि प्रतीकों αAaβ की स्ट्रिंग है जिसे प्रारंभ प्रतीक से प्राप्त किया जा सकता है। हम इनपुट स्ट्रीम के अंत को दर्शाने वाले विशेष टर्मिनल के रूप में '$' का उपयोग करते हैं, और प्रारंभ प्रतीक के रूप में S का उपयोग करते हैं।
 
दुर्भाग्य से, प्रथम-सेट पार्सिंग टेबल की गणना करने के लिए पर्याप्त नहीं हैं।
ऐसा इसलिए है क्योंकि किसी नियम का दाहिना भाग w अंततः रिक्त स्ट्रिंग पर फिर से लिखा जा सकता है।
इसलिए पार्सर को नियम A → w का भी उपयोग करना चाहिए यदि ε 'Fi' (w) में है और यह इनपुट स्ट्रीम पर प्रतीक देखता है जो A का अनुसरण कर सकता है। इसलिए, हमें A के फॉलो-सेट की भी आवश्यकता है, जिसे यहां 'Fo' (A) के रूप में लिखा गया है, जिसे टर्मिनलों के सेट के रूप में परिभाषित किया गया है जैसे कि प्रतीकों αAaβ की स्ट्रिंग है जिसे प्रारंभ प्रतीक से प्राप्त किया जा सकता है। हम इनपुट स्ट्रीम के अंत को दर्शाने वाले विशेष टर्मिनल के रूप में '$' का उपयोग करते हैं, और प्रारंभ प्रतीक के रूप में S का उपयोग करते हैं।                                                                                        


ग्रामर में नॉनटर्मिनलों के लिए फॉलो-सेट की गणना निम्नानुसार की जा सकती है:
ग्रामर में नॉनटर्मिनलों के लिए फॉलो-सेट की गणना निम्नानुसार की जा सकती है:
# 'Fo'(S) को { '$' } और अन्य सभी 'Fo'(A) से प्रारंभ करें<sub>''i''</sub>) खाली सेट के साथ
# 'Fo'(S) को { '$' } और अन्य सभी 'Fo'(A) से प्रारंभ करें<sub>''i''</sub>) रिक्त सेट के साथ
# अगर फॉर्म ए का नियम है<sub>''j''</sub> → वा<sub>i</sub>w' , फिर
# अगर फॉर्म A का नियम है<sub>''j''</sub> → वा<sub>i</sub>w' , फिर
#* यदि टर्मिनल a 'Fi'(w' ) में है, तो 'फॉर्म'(A) में a जोड़ें<sub>''i''</sub>)
#* यदि टर्मिनल a 'Fi'(w' ) में है, तो 'फॉर्म'(A) में a जोड़ें<sub>''i''</sub>)
#* यदि ε फ़ाइल'' में है, तो इसमें जोड़ें(''ए''<sub>''j''</sub>) से फॉर्म(''ए''<sub>''i''</sub>)
#* यदि ε फ़ाइल'' में है, तो इसमें जोड़ें(''ए''<sub>''j''</sub>) से फॉर्म(''ए''<sub>''i''</sub>)
#* यदि a' की लंबाई 0 है, तो 'To'(A) जोड़ें<sub>''j''</sub>) से फॉर्म(''ए''<sub>''i''</sub>)
#* यदि a' की लंबाई 0 है, तो 'To'(A) जोड़ें<sub>''j''</sub>) से फॉर्म(''ए''<sub>''i''</sub>)
# चरण 2 को तब तक दोहराएँ जब तक कि सभी फ़ो सेट समान न रहें।
# फेज 2 को तब तक दोहराएँ जब तक कि सभी फ़ो सेट समान न रहें।
यह निम्नलिखित प्रणाली को न्यूनतम निश्चित बिंदु समाधान प्रदान करता है:
यह निम्नलिखित प्रणाली को न्यूनतम निश्चित बिंदु समाधान प्रदान करता है:
* Fo(''S'') ⊇ {$}
* Fo(''S'') ⊇ {$}
* फॉर्म बी के प्रत्येक नियम के लिए Fo(''A'') ⊇ Fi(''w'')·Fo(''B'') → ... A w
* फॉर्म बी के प्रत्येक नियम के लिए Fo(''A'') ⊇ Fi(''w'')·Fo(''B'') → ... A w
   
   
अब हम सटीक रूप से परिभाषित कर सकते हैं कि पार्सिंग तालिका में कौन से नियम कहाँ दिखाई देंगे।
अब हम सटीक रूप से परिभाषित कर सकते हैं कि पार्सिंग टेबल में कौन से नियम कहाँ दिखाई देंगे।
यदि ''T''[''A'', ''a''] नॉनटर्मिनल ''A'' और टर्मिनल ''a'' के लिए तालिका में प्रविष्टि को दर्शाता है, तो
यदि ''T''[''A'', ''a''] नॉनटर्मिनल ''A'' और टर्मिनल ''a'' के लिए टेबल में प्रविष्टि को दर्शाता है, तो
: ''T''[''A'',''a''] में नियम ''A'' → ''w'' सम्मिलित है यदि और केवल यदि
: ''T''[''A'',''a''] में नियम ''A'' → ''w'' सम्मिलित है यदि और केवल यदि
:: ''a'' Fi(''w'') या में है
:: ''a'' Fi(''w'') या में है
Line 362: Line 369:
समान रूप से: ''T''[''A'', ''a''] में प्रत्येक ''a'' ∈ Fi(''w'') के लिए नियम ''A'' → ''w'' सम्मिलित है ·Fo(''ए'').
समान रूप से: ''T''[''A'', ''a''] में प्रत्येक ''a'' ∈ Fi(''w'') के लिए नियम ''A'' → ''w'' सम्मिलित है ·Fo(''ए'').


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


== एक LL(k) पार्सिंग तालिका का निर्माण ==
== एक LL(k) पार्सिंग टेबल का निर्माण ==


LL(1) पार्सर्स के निर्माण को निम्नलिखित संशोधनों के साथ के > 1 के लिए LL(k) में अनुकूलित किया जा सकता है:
LL(1) पार्सर्स के निर्माण को निम्नलिखित संशोधनों के साथ के > 1 के लिए LL(k) में अनुकूलित किया जा सकता है:
* काटे गए उत्पाद को परिभाषित किया गया है <math>U \cdot V = \{ (uv):k \mid u \in U, v \in V \}</math>, जहां w:k लंबाई > k, या w, वाले शब्दों की प्रारंभिक लंबाई-k उपसर्ग को दर्शाता है, यदि w की लंबाई k या उससे कम है,
* काटे गए उत्पाद को परिभाषित किया गया है <math>U \cdot V = \{ (uv):k \mid u \in U, v \in V \}</math>, जहां w:k लंबाई > k, या w, वाले शब्दों की प्रारंभिक लंबाई-k उपसर्ग को दर्शाता है, यदि w की लंबाई k या उससे कम है,
* Fo(''S'') = {$<sup>क</sup>}
* Fo(''S'') = {$<sup>क</sup>}
* Fi(ab) = Fi(a) प्रयुक्त करें<math>\cdot</math>Fi(β) LL(1) के लिए दिए गए Fi निर्माण के चरण 2 में भी है।
* Fi(ab) = Fi(a) प्रयुक्त करें<math>\cdot</math>Fi(β) LL(1) के लिए दिए गए Fi निर्माण के फेज 2 में भी है।
* एफओ निर्माण के चरण 2 में, ''ए'' के लिए<sub>j</sub>→ वा<sub>i</sub>w'<nowiki/> बस 'Fi' जोड़ें(w'<nowiki/>)<math>\cdot</math>फ़ो(''ए<sub>j</sub>) से 'फॉर्म'(ए<sub>i</sub>).
* Fओ निर्माण के फेज 2 में, A के लिए<sub>j</sub>→ वा<sub>i</sub>w' <nowiki/>बस 'Fi' जोड़ें(w')<nowiki/><math>\cdot</math>फ़ो(''ए<sub>j</sub>) से 'फॉर्म'(ए<sub>i</sub>).
जहां k लुकअहेड कांटेक्स्ट को पूरी तरह से ध्यान में रखने के लिए, इनपुट को k एंड-मार्कर '$' द्वारा प्रत्यय दिया जाता है। यह दृष्टिकोण ε के लिए विशेष मामलों को समाप्त करता है, और LL (1) मामले में समान रूप से प्रयुक्त किया जा सकता है।
जहां k लुकअहेड कांटेक्स्ट को पूरी तरह से ध्यान में रखने के लिए, इनपुट को k एंड-मार्कर '$' द्वारा प्रत्यय दिया जाता है। यह दृष्टिकोण ε के लिए विशेष मामलों को समाप्त करता है, और LL (1) स्थिति में समान रूप से प्रयुक्त किया जा सकता है।


1990 के दशक के मध्य तक, यह व्यापक रूप से माना जाता था कि LL(k) पार्सिंग (k > 1 के लिए) अव्यावहारिक थी,{{Citation needed|date=February 2007}} चूंकि सबसे व्यर्थ स्थिति में पार्सर तालिका में k में घातीय फ़ंक्शन आकार होगा। यह धारणा 1992 के आसपास [[ बारहसिंगे के शाखादार सींग |बारहसिंगे के शाखादार सींग]] के जारी होने के बाद धीरे-धीरे बदल गई, जब यह प्रदर्शित किया गया कि अनेक [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज को पार्सर के सबसे व्यर्थ स्थिति वाले व्यवहार को ट्रिगर किए बिना LL(k) पार्सर द्वारा कुशलतापूर्वक पार्स किया जा सकता है। इसके अलावा, कुछ मामलों में LL पार्सिंग असीमित लुकहेड के साथ भी संभव है। इसके विपरीत, [[yacc]] जैसे पारंपरिक पार्सर जनरेटर निश्चित वन-टोकन लुकहेड के साथ प्रतिबंधित LR पार्सर का निर्माण करने के लिए LALR पार्सर|LALR(1) पार्सर तालिकाओं का उपयोग करते हैं।
1990 के दशक के मध्य तक, यह व्यापक रूप से माना जाता था कि LL(k) पार्सिंग (k > 1 के लिए) अव्यावहारिक थी,{{Citation needed|date=February 2007}} चूंकि सबसे व्यर्थ स्थिति में पार्सर टेबल में k में घातीय फ़ंक्शन आकार होगा। यह धारणा 1992 के आसपास [[ बारहसिंगे के शाखादार सींग |बारहसिंगे के शाखादार सींग]] के जारी होने के बाद धीरे-धीरे परिवर्तित कर गई, जब यह प्रदर्शित किया गया कि अनेक [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज को पार्सर के सबसे व्यर्थ स्थिति वाले व्यवहार को ट्रिगर किए बिना LL(k) पार्सर द्वारा कुशलतापूर्वक पार्स किया जा सकता है। इसके अलावा, कुछ मामलों में LL पार्सिंग असीमित लुकहेड के साथ भी संभव है। इसके विपरीत, [[yacc]] जैसे पारंपरिक पार्सर जनरेटर निश्चित वन-टोकन लुकहेड के साथ प्रतिबंधित LR पार्सर का निर्माण करने के लिए LALR पार्सर|LALR(1) पार्सर टेबलओं का उपयोग करते हैं।


==संघर्ष==
==संघर्ष==
Line 384: Line 391:
मान लीजिए A गैर-टर्मिनल है। FIRST(A) टर्मिनलों का सेट (परिभाषित) है जो A से प्राप्त किसी भी स्ट्रिंग की पहली स्थिति में दिखाई दे सकता है। FOLLOW(A) यूनियन ओवर है:<ref>{{Cite web|title=एलएल व्याकरण|url=http://www.cs.uaf.edu/~cs331/notes/LL.pdf|url-status=live|archive-url=https://web.archive.org/web/20100618193203/http://www.cs.uaf.edu/~cs331/notes/LL.pdf|archive-date=2010-06-18|access-date=2010-05-11}}</ref>
मान लीजिए A गैर-टर्मिनल है। FIRST(A) टर्मिनलों का सेट (परिभाषित) है जो A से प्राप्त किसी भी स्ट्रिंग की पहली स्थिति में दिखाई दे सकता है। FOLLOW(A) यूनियन ओवर है:<ref>{{Cite web|title=एलएल व्याकरण|url=http://www.cs.uaf.edu/~cs331/notes/LL.pdf|url-status=live|archive-url=https://web.archive.org/web/20100618193203/http://www.cs.uaf.edu/~cs331/notes/LL.pdf|archive-date=2010-06-18|access-date=2010-05-11}}</ref>
# FIRST(B) जहां B कोई गैर-टर्मिनल है जो औपचारिक ग्रामर के दाईं ओर A के ठीक बाद आता है#ग्रामर का वाक्य-विन्यास।
# FIRST(B) जहां B कोई गैर-टर्मिनल है जो औपचारिक ग्रामर के दाईं ओर A के ठीक बाद आता है#ग्रामर का वाक्य-विन्यास।
# अनुसरण करें(बी) जहां बी फॉर्म बी → डब्ल्यूए के नियम का कोई शीर्ष है।
# अनुसरण करें(बी) जहां बी फॉर्म बी → wए के नियम का कोई शीर्ष है।


=== LL(1) संघर्ष ===
=== LL(1) संघर्ष ===
Line 393: Line 400:
एक ही गैर-टर्मिनल प्रतिच्छेद के लिए दो अलग-अलग ग्रामर नियमों का पहला सेट।
एक ही गैर-टर्मिनल प्रतिच्छेद के लिए दो अलग-अलग ग्रामर नियमों का पहला सेट।
LL(1) प्रथम/प्रथम संघर्ष का उदाहरण:
LL(1) प्रथम/प्रथम संघर्ष का उदाहरण:
  एस -> ई | ई 'ए'
  एस -> ई | ई 'A'
  ई -> 'बी' | ε
  ई -> 'बी' | ε
FIRST(E) = {b, ε} और FIRST(E a) = {b, a}, इसलिए जब तालिका बनाई जाती है, तो उत्पादन नियम S के टर्मिनल b के तहत संघर्ष होता है।
FIRST(E) = {b, ε} और FIRST(E a) = {b, a}, इसलिए जब टेबल बनाई जाती है, तो उत्पादन नियम S के टर्मिनल b के तहत संघर्ष होता है।


===== विशेष मामला: बाईं पुनरावृत्ति =====
===== विशेष मामला: बाईं पुनरावृत्ति =====
Line 403: Line 410:


==== पहला/अनुसरण संघर्ष ====
==== पहला/अनुसरण संघर्ष ====
ग्रामर नियम का पहला और अगला सेट ओवरलैप होता है। पहले सेट में [[खाली स्ट्रिंग]] (ε) के साथ, यह अज्ञात है कि कौन सा विकल्प चुनना है।
ग्रामर नियम का पहला और अगला सेट ओवरलैप होता है। पहले सेट में [[खाली स्ट्रिंग|रिक्त स्ट्रिंग]] (ε) के साथ, यह अज्ञात है कि कौन सा विकल्प चुनना है।
LL(1) संघर्ष का उदाहरण:
LL(1) संघर्ष का उदाहरण:
  एस -> ए 'ए' 'बी'
  एस -> A 'A' 'बी'
  ए -> 'ए' | ε
  ए -> 'A' | ε
A का पहला सेट {a, ε} है, और अगला सेट {a} है।
A का पहला सेट {a, ε} है, और अगला सेट {a} है।


Line 418: Line 425:
  ए -> एक्स बी
  ए -> एक्स बी
  बी -> वाई जेड | ε
  बी -> वाई जेड | ε
इसे तब प्रयुक्त किया जा सकता है जब दो विकल्प ही प्रतीक से शुरू होते हैं जैसे FIRST/FIRST संघर्ष।
इसे तब प्रयुक्त किया जा सकता है जब दो विकल्प ही प्रतीक से प्रारंभ होते हैं जैसे FIRST/FIRST संघर्ष।


उपरोक्त FIRST/FIRST संघर्ष उदाहरण का उपयोग करते हुए और उदाहरण (अधिक जटिल):
उपरोक्त FIRST/FIRST संघर्ष उदाहरण का उपयोग करते हुए और उदाहरण (अधिक जटिल):
  एस -> ई | ई 'ए'
  एस -> ई | ई 'A'
  ई -> 'बी' | ε
  ई -> 'बी' | ε
बन जाता है (एकल गैर-टर्मिनल में विलय)
बन जाता है (एकल गैर-टर्मिनल में विलय)
  एस -> 'बी' | ε | 'बी' 'ए' | 'ए'
  एस -> 'बी' | ε | 'बी' 'A' | 'A'
फिर वाम-फैक्टरिंग के माध्यम से, बन जाता है
फिर वाम-फैक्टरिंग के माध्यम से, बन जाता है
  एस -> 'बी' ई | इ
  एस -> 'बी' ई | इ
  ई -> 'ए' | ε
  ई -> 'A' | ε


==== प्रतिस्थापन ====
==== प्रतिस्थापन ====
Line 440: Line 447:
  ई -> ई '+' टी
  ई -> ई '+' टी
  ई -> टी
  ई -> टी
यह नियम और कुछ नहीं बल्कि '+' से अलग की गई Ts की सूची है। रेगुलर एक्सप्रेशन फॉर्म T ('+' T)* में।
यह नियम और कुछ नहीं किन्तु '+' से अलग की गई Ts की सूची है। रेगुलर एक्सप्रेशन फॉर्म T ('+' T)* में।
अतः नियम को इस प्रकार पुनः लिखा जा सकता है
अतः नियम को इस प्रकार पुनः लिखा जा सकता है
  ई -> टी जेड
  ई -> टी जेड
Line 448: Line 455:


चूँकि, सभी कांटेक्स्ट-फ्री ग्रामर में समतुल्य LL(k)-ग्रामर नहीं होता है, उदाहरण के लिए:
चूँकि, सभी कांटेक्स्ट-फ्री ग्रामर में समतुल्य LL(k)-ग्रामर नहीं होता है, उदाहरण के लिए:
  एस -> ए | बी
  एस -> A | बी
  ए -> 'ए' ए 'बी' | ε
  ए -> 'A' A 'बी' | ε
  बी -> 'ए' बी 'बी' 'बी' | ε
  बी -> 'A' बी 'बी' 'बी' | ε
यह दिखाया जा सकता है कि इस ग्रामर द्वारा उत्पन्न लैंग्वेज को स्वीकार करने वाला कोई LL(k)-ग्रामर उपस्थित नहीं है।
यह दिखाया जा सकता है कि इस ग्रामर द्वारा उत्पन्न लैंग्वेज को स्वीकार करने वाला कोई LL(k)-ग्रामर उपस्थित नहीं है।


Revision as of 13:46, 4 August 2023

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

एक LL पार्सर को LL(k) पार्सर कहा जाता है यदि यह किसी वाक्य को पार्स करते समय पार्सिंग लुकहेड के K टोकन (पार्सर) का उपयोग करता है। ग्रामर को LL ग्रामर या LL(k) ग्रामर कहा जाता है यदि उससे LL(k) पार्सर का निर्माण किया जा सकता है। औपचारिक लैंग्वेज को LL(k) लैंग्वेज कहा जाता है यदि उसमें LL(k) ग्रामर होते है। प्रत्येक k ≥0 के लिए LL(k) लैंग्वेज का सेट LL(k+1) लैंग्वेज में उचित रूप से समाहित है।[1] इसका परिणाम यह है कि सभी कांटेक्स्ट-फ्री लैंग्वेज को LL(k) पार्सर द्वारा पहचाना नहीं जा सकता है।

एक LL पार्सर को LL-रेगुलर (LLआर) कहा जाता है यदि यह LL-रेगुलर लैंग्वेज को पार्स करता है।[2][3][4] LL-नियमित ग्रामर की कक्षा में प्रत्येक के के लिए प्रत्येक LL(k) ग्रामर सम्मिलित है। प्रत्येक LLआर ग्रामर के लिए LLआर पार्सर उपस्थित होता है जो ग्रामर को रैखिक समय में पार्स करता है।

दो नामकरण बाह्य पार्सर प्रकार LL(*) और LL(परिमित) हैं। पार्सर को LL(*)/LL(परिमित) कहा जाता है यदि वह LL(*)/LL(परिमित) पार्सिंग रणनीति का उपयोग करता है। [5][6] LL(*) और LL(परिमित) पार्सर कार्यात्मक रूप से पार्सिंग अभिव्यक्ति ग्रामर पार्सर के निकट हैं। LL (परिमित) पार्सर अनैतिक LL(k) ग्रामर को लुकहेड और लुकहेड तुलनाओं की मात्रा में इष्टतम रूप से पार्स कर सकता है। LL (*) रणनीति द्वारा पार्स करने योग्य ग्रामर के वर्ग में वाक्यात्मक और अर्थ संबंधी विधेय के उपयोग के कारण कुछ कांटेक्स्ट-संवेदनशील भाषाएं सम्मिलित हैं और उनकी पहचान नहीं की गई है। यह सुझाव दिया गया है कि LL (*) पार्सर्स को ऊपर से नीचे पार्सिंग लैंग्वेज पार्सर्स के रूप में उत्तम माना जाता है।[7]

लोकप्रिय गलत धारणा के विपरीत, LL (*) पार्सर सामान्यतः LLR नहीं होते हैं, और निर्माण द्वारा गारंटी दी जाती है कि वह औसतन व्यर्थ प्रदर्शन करेंगे (रैखिक समय के विरुद्ध सुपर-रैखिक) और सबसे व्यर्थ स्थिति में बहुत व्यर्थ (रैखिक समय के विरुद्ध घातीय) है।

LL ग्रामर, विशेष रूप से LL (1) ग्रामर, बहुत व्यावहारिक रुचि के हैं, क्योंकि इन ग्रामर के लिए पार्सर का निर्माण करना सरल है, और अनेक कंप्यूटर लैंग्वेज को इस कारण से LL (1) के रूप में डिज़ाइन किया गया है।[8] LL पार्सर टेबल-आधारित हो सकते हैं, अर्थात एलआर पार्सर के समान, किन्तु LL ग्रामर को रिकर्सन डिसेंट पार्सर द्वारा भी पार्स किया जा सकता है। वाइट और गूस (1984) के अनुसार,[9] LL(k) ग्रामर स्टर्न्स और लुईस (1969) द्वारा प्रस्तुत किया गया था।[10]


अवलोकन

किसी दिए गए कांटेक्स्ट-फ्री ग्रामर के लिए, पार्सर कांटेक्स्ट-फ्री ग्रामर व्युत्पन्न और सिंटेक्स ट्री को खोजने का प्रयास करता है। इस प्रकार ग्रामर का उदाहरण दिया गया है :

के लिए सबसे बाईं व्युत्पत्ति है:

सामान्यतः, सबसे बाएं गैर-टर्मिनल का विस्तार करने के लिए नियम का चयन करते समय अनेक संभावनाएं होती हैं। पिछले उदाहरण के फेज 2 में, पार्सर को यह चुनना होगा कि नियम 2 या नियम 3 प्रयुक्त करना है :

कुशल होने के लिए, पार्सर को जब भी संभव हो, बिना पीछे हटे, इस विकल्प को निश्चित रूप से चुनने में सक्षम होना चाहिए। कुछ ग्रामर के लिए, यह अपठित इनपुट (बिना पढ़े) पर द्रष्टि डालकर ऐसा कर सकता है। हमारे उदाहरण में, यदि पार्सर जानता है कि अगला अपठित प्रतीक है एकमात्र सही नियम जिसका उपयोग किया जा सकता है वह 2 है।


सामान्यतः, A पार्सर आगे प्रतीकों को देख सकता है। चूँकि, व्याकरण को देखते हुए, यह निर्धारित करने की समस्या कि क्या कुछ के लिए पार्सर उपस्थित है जो इसे पहचानता है, अनिर्णीत है। प्रत्येक k के लिए, एक ऐसी भाषा होती है जिसे पार्सर द्वारा नहीं पहचाना जा सकता है, किन्तु द्वारा पहचाना जा सकता है

हम उपरोक्त विश्लेषण का उपयोग निम्नलिखित औपचारिक परिभाषा देने के लिए कर सकते हैं:

मान लीजिए एक संदर्भ-मुक्त व्याकरण है और हम कहते हैं कि है, यदि और केवल यदि किन्हीं दो सबसे बाईं व्युत्पत्तियों के लिए:

निम्नलिखित नियम प्रयुक्त होती है: लंबाई की स्ट्रिंग का उपसर्ग लंबाई की स्ट्रिंग के उपसर्ग के सामान होता है। अर्थात


इस परिभाषा में, प्रारंभ प्रतीक है और कोई गैर-टर्मिनल है। पहले से व्युत्पन्न इनपुट , और अभी तक अपठित और टर्मिनलों के तार हैं। ग्रीक अक्षर और दोनों टर्मिनलों और गैर-टर्मिनलों (संभवतः रिक्त) की किसी भी स्ट्रिंग का प्रतिनिधित्व करते हैं। उपसर्ग की लंबाई लुकहेड बफ़र आकार से मेल खाती है, और परिभाषा कहती है कि यह बफ़र विभिन्न शब्दों के किन्हीं दो व्युत्पत्तियों के बीच अंतर करने के लिए पर्याप्त है।

पार्सर

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

स्टैक अल्फाबेट है, जहां:

  • गैर-टर्मिनलों का सेट है;
  • विशेष एंड-ऑफ-इनपुट (ईओआई) प्रतीक के साथ टर्मिनल (इनपुट) प्रतीकों का सेट .

पार्सर स्टैक में प्रारंभ में EOI के ऊपर प्रारंभिक प्रतीक होता है:। ऑपरेशन के समय, पार्सर बार-बार स्टैक के शीर्ष पर प्रतीक को परिवर्तित कर देता है:

  • कुछ के साथ यदि और एक नियम है
  • के साथ (कुछ नोटेशन में), अर्थात को स्टैक से हटा दिया जाता है, यदि है। इस स्थिति में, एक इनपुट प्रतीक पढ़ा जाता है और यदि है, तो पार्सर इनपुट को अस्वीकार कर देता है।

यदि स्टैक से हटाया जाने वाला अंतिम प्रतीक ईओआई है, तो पार्सिंग सफल है; ऑटोमेटन रिक्त स्टैक के माध्यम से स्वीकार करता है।

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

  • पंक्ति: शीर्ष-स्टैक प्रतीक
  • कॉलम: लुकअहेड बफ़र पदार्थ
  • सेल: के लिए नियम संख्या या

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

ठोस उदाहरण

सेट अप

LL(1) पार्सर की कार्यप्रणाली को समझाने के लिए हम निम्नलिखित छोटे LL(1) ग्रामर पर विचार करेंगे

  1. S → F
  2. S → ( S + F )
  3. F → a

और निम्नलिखित इनपुट को पार्स करें:

( a + a )

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

टेबल की प्रत्येक सेल ग्रामर के अधिकतम नियम (उसकी संख्या से पहचानी गई) की ओर संकेत कर सकती है। उदाहरण के लिए, उपरोक्त ग्रामर के लिए पार्सिंग टेबल में, गैर-टर्मिनल 'S' और टर्मिनल '(' के लिए सेल नियम संख्या 2 की ओर संकेत करता है:

( ) a + $
S 2 — 1 — —
F — — 3 — —

पार्सिंग टेबल बनाने के लिए एल्गोरिदम का वर्णन बाद के अनुभाग में किया गया है, किन्तु पहले देखते हैं कि पार्सर अपने इनपुट को संसाधित करने के लिए पार्सिंग टेबल का उपयोग कैसे करता है।

पार्सिंग प्रक्रिया

प्रत्येक फेज में, पार्सर इनपुट स्ट्रीम से अगले-उपलब्ध प्रतीक को पढ़ता है, और स्टैक से सबसे ऊपरी प्रतीक को पढ़ता है। यदि इनपुट प्रतीक और स्टैक-टॉप प्रतीक मेल खाते हैं, तो पार्सर उन दोनों को हटा देता है, इनपुट स्ट्रीम और स्टैक पर केवल बेजोड़ प्रतीकों को छोड़ देता है।

इस प्रकार, अपने पहले फेज में, पार्सर इनपुट प्रतीक '(और स्टैक-टॉप प्रतीक 'S' को पढ़ता है। पार्सिंग टेबल निर्देश इनपुट प्रतीक '(शीर्ष वाले कॉलम और स्टैक-टॉप प्रतीक 'S' के नेतृत्व वाली पंक्ति से आता है; इस सेल में '2' होता है, जो पार्सर को नियम (2) प्रयुक्त करने का निर्देश देता है। पार्सर को 'S' को हटाकर स्टैक पर 'S' से '( S + F )' को फिर से लिखना होता है। 'F', '+', 'S',को स्टैक पर दाब, और यह आउटपुट पर नियम संख्या 2 लिखता है। स्टैक तब बन जाता है:

[ (, S, +, F, ), $ ]

दूसरे फेज में, पार्सर अपनी इनपुट स्ट्रीम और स्टैक से '(' को हटा देता है, क्योंकि वे अब मेल खाते हैं। स्टैक अब बन जाता है:

[ S, +, F, ), $ ]


अब पार्सर के इनपुट स्ट्रीम पर 'A' और स्टैक टॉप के रूप में 'S' है। पार्सिंग टेबल इसे ग्रामर से नियम (1) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 1 लिखने का निर्देश देती है। संग्रह बन जाता है:

[ F, +, F, ), $ ]

पार्सर के पास अब इनपुट स्ट्रीम पर 'A' और स्टैक टॉप के रूप में 'F' है। पार्सिंग टेबल इसे ग्रामर से नियम (3) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 3 लिखने का निर्देश देती है। संग्रह बन जाता है:

[ a, +, F, ), $ ]

पार्सर में अब इनपुट स्ट्रीम पर 'a' है और इसके स्टैक टॉप पर 'a' है। क्योंकि वह समान हैं, यह इसे इनपुट स्ट्रीम से हटा देता है और स्टैक के शीर्ष से पॉप कर देता है। पार्सर के पास इनपुट स्ट्रीम पर '+' होता है और '+' स्टैक के शीर्ष पर होता है, जिसका अर्थ है, 'A' की तरह, इसे स्टैक से पॉप किया जाता है और इनपुट स्ट्रीम से हटा दिया जाता है। इस में यह परिणाम: 

[F, ), $ ]

अगले तीन फेजों में पार्सर स्टैक पर 'F' को 'A' से परिवर्तित कर देगा, आउटपुट स्ट्रीम में नियम संख्या 3 लिखेगा और स्टैक और इनपुट स्ट्रीम दोनों से 'A' और ')' को हटा देता है। इस प्रकार पार्सर अपने स्टैक और इनपुट स्ट्रीम दोनों पर '$' के साथ समाप्त होता है।

इस स्थिति में पार्सर रिपोर्ट करेगा कि उसने इनपुट स्ट्रिंग को स्वीकार कर लिया है और आउटपुट स्ट्रीम में नियम संख्याओं की निम्नलिखित सूची लिखेगा:

[2, 1, 3, 3 ]

यह वास्तव में इनपुट स्ट्रिंग के कांटेक्स्ट-फ्री ग्रामर व्युत्पत्ति और सिंटेक्स ट्री के लिए नियमों की सूची है, जो है:

S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

C++ में पार्सर कार्यान्वयन

उदाहरण लैंग्वेज के लिए टेबल-आधारित LL पार्सर का C++ कार्यान्वयन नीचे दिया गया है: 

#include <iostream>
#include <map>
#include <stack>

enum Symbols {
	// the symbols:
	// Terminal symbols:
	TS_L_PARENS,	// (
	TS_R_PARENS,	// )
	TS_A,		// a
	TS_PLUS,	// +
	TS_EOS,		// $, in this case corresponds to '\0'
	TS_INVALID,	// invalid token

	// Non-terminal symbols:
	NTS_S,		// S
	NTS_F		// F
};

/*
Converts a valid token to the corresponding terminal symbol
*/
Symbols lexer(char c)
{
	switch (c)
	{
		case '(':  return TS_L_PARENS;
		case ')':  return TS_R_PARENS;
		case 'a':  return TS_A;
		case '+':  return TS_PLUS;
		case '\0': return TS_EOS; // end of stack: the $ terminal symbol
		default:   return TS_INVALID;
	}
}

int main(int argc, char **argv)
{
	using namespace std;

	if (argc < 2)
	{
		cout << "usage:\n\tll '(a+a)'" << endl;
		return 0;
	}

	// LL parser table, maps < non-terminal, terminal> pair to action
	map< Symbols, map<Symbols, int> > table;
	stack<Symbols>	ss;	// symbol stack
	char *p;	// input buffer

	// initialize the symbols stack
	ss.push(TS_EOS);	// terminal, $
	ss.push(NTS_S);		// non-terminal, S

	// initialize the symbol stream cursor
	p = &argv[1][0];

	// set up the parsing table
	table[NTS_S][TS_L_PARENS] = 2;
	table[NTS_S][TS_A] = 1;
	table[NTS_F][TS_A] = 3;

	while (ss.size() > 0)
	{
		if (lexer(*p) == ss.top())
		{
			cout << "Matched symbols: " << lexer(*p) << endl;
			p++;
			ss.pop();
		}
		else
		{
			cout << "Rule " << table[ss.top()][lexer(*p)] << endl;
			switch (table[ss.top()][lexer(*p)])
			{
				case 1:	// 1. S → F
					ss.pop();
					ss.push(NTS_F);	// F
					break;

				case 2:	// 2. S → ( S + F )
					ss.pop();
					ss.push(TS_R_PARENS);	// )
					ss.push(NTS_F);		// F
					ss.push(TS_PLUS);	// +
					ss.push(NTS_S);		// S
					ss.push(TS_L_PARENS);	// (
					break;

				case 3:	// 3. F → a
					ss.pop();
					ss.push(TS_A);	// a
					break;

				default:
					cout << "parsing table defaulted" << endl;
					return 0;
			}
		}
	}

	cout << "finished parsing" << endl;

	return 0;
}


पायथन में पार्सर कार्यान्वयन

# All constants are indexed from 0
TERM = 0
RULE = 1

# Terminals
T_LPAR = 0
T_RPAR = 1
T_A = 2
T_PLUS = 3
T_END = 4
T_INVALID = 5

# Non-Terminals
N_S = 0
N_F = 1

# Parse table
table = [[ 1, -1, 0, -1, -1, -1],
         [-1, -1, 2, -1, -1, -1]]

RULES = [[(RULE, N_F)],
         [(TERM, T_LPAR), (RULE, N_S), (TERM, T_PLUS), (RULE, N_F), (TERM, T_RPAR)],
         [(TERM, T_A)]]

stack = [(TERM, T_END), (RULE, N_S)]

def lexical_analysis(inputstring):
    print("Lexical analysis")
    tokens = []
    for c in inputstring:
        if c   == "+": tokens.append(T_PLUS)
        elif c == "(": tokens.append(T_LPAR)
        elif c == ")": tokens.append(T_RPAR)
        elif c == "a": tokens.append(T_A)
        else: tokens.append(T_INVALID)
    tokens.append(T_END)
    print(tokens)
    return tokens

def syntactic_analysis(tokens):
    print("Syntactic analysis")
    position = 0
    while len(stack) > 0:
        (stype, svalue) = stack.pop()
        token = tokens[position]
        if stype == TERM:
            if svalue == token:
                position += 1
                print("pop", svalue)
                if token == T_END:
                    print("input accepted")
            else:
                print("bad term on input:", token)
                break
        elif stype == RULE:
            print("svalue", svalue, "token", token)
            rule = table[svalue][token]
            print("rule", rule)
            for r in reversed(RULES[rule]):
                stack.append(r)
        print("stack", stack)

inputstring = "(a+a)"
syntactic_analysis(lexical_analysis(inputstring))


टिप्पणियाँ

जैसा कि उदाहरण से देखा जा सकता है, पार्सर तीन प्रकार के फेज निष्पादित करता है जो इस बात पर निर्भर करता है कि स्टैक का शीर्ष नॉनटर्मिनल है, टर्मिनल है या विशेष प्रतीक $ है:

  • यदि शीर्ष नॉनटर्मिनल है तो पार्सर इस नॉनटर्मिनल और इनपुट स्ट्रीम पर प्रतीक के आधार पर पार्सिंग टेबल में देखता है कि उसे स्टैक पर नॉनटर्मिनल को परिवर्तित करने के लिए ग्रामर के किस नियम का उपयोग करना चाहिए। नियम की संख्या आउटपुट स्ट्रीम पर लिखी जाती है। यदि पार्सिंग टेबल संकेत करती है कि ऐसा कोई नियम नहीं है तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
  • यदि शीर्ष टर्मिनल है तो पार्सर इसकी तुलना इनपुट स्ट्रीम पर प्रतीक से करता है और यदि वह सामान हैं तो वे दोनों हटा दिए जाते हैं। यदि वह समान नहीं हैं तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
  • यदि शीर्ष $ है और इनपुट स्ट्रीम पर भी $ है तो पार्सर रिपोर्ट करता है कि उसने इनपुट को सफलतापूर्वक पार्स कर लिया है, अन्यथा यह त्रुटि की रिपोर्ट करता है। दोनों ही स्थितियों में पार्सर बंद हो जाता है.

इन फेजों को तब तक दोहराया जाता है जब तक पार्सर बंद नहीं हो जाता है, और फिर यह या तो इनपुट को पूरी तरह से पार्स कर लेगा और आउटपुट स्ट्रीम में कांटेक्स्ट-फ्री ग्रामर व्युत्पत्ति और सिंटेक्स पेड़ लिखेगा या यह त्रुटि की सूचना देता है।

एक LL(1) पार्सिंग टेबल का निर्माण

पार्सिंग टेबल को भरने के लिए, हमें यह स्थापित करना होगा कि पार्सर को कौन सा ग्रामर नियम चुनना चाहिए यदि वह अपने स्टैक के शीर्ष पर नॉनटर्मिनल A और अपने इनपुट स्ट्रीम पर प्रतीक देखता है।

यह देखना सरल है कि ऐसा नियम A → w के रूप का होना चाहिए और w के अनुरूप लैंग्वेज में a से प्रारंभ होने वाली कम से कम स्ट्रिंग होनी चाहिए।

इस उद्देश्य के लिए हम w के पहले सेट को परिभाषित करते हैं, जिसे यहां 'Fi' (w) के रूप में लिखा गया है, टर्मिनलों के सेट के रूप में जो w में कुछ स्ट्रिंग की प्रारंभ में पाया जा सकता है, प्लस ε यदि रिक्त स्ट्रिंग भी w से संबंधित है।

नियमों A1 → w1,…, An → wn के साथ व्याकरण को देखते हुए, हम प्रत्येक नियम के लिए Fi(wi) और Fi(Ai) की गणना इस प्रकार कर सकते हैं:

  1. प्रत्येक Fi(Ai) को रिक्त सेट के साथ प्रारंभ करें
  2. प्रत्येक नियम Ai → wi के लिए Fi(wi) को Fi(Ai) में जोड़ें, जहां Fi को इस प्रकार परिभाषित किया गया है:
    • प्रत्येक टर्मिनल A के लिए Fi(aw') = { a }
    • प्रत्येक नॉनटर्मिनल A के लिए Fi(Aw') = 'Fi'(A) जिसमें ε 'Fi'(A) में नहीं है
    • Fi(Aw' ) = ('Fi'(A) \ { ε }) ∪ Fi(w' ) 'Fi'(A) में ε के साथ प्रत्येक नॉनटर्मिनल A के लिए
    • Fi(ε) = { ε }
  3. प्रत्येक नियम Ai → wi के लिए Fi(wi) को Fi(Ai) में जोड़ें
  4. फेज 2 और 3 तब तक करें जब तक कि सभी Fi सेट समान न रहें।

परिणाम निम्नलिखित प्रणाली के लिए सबसे कम निश्चित बिंदु समाधान है:

  • Fi(A) ⊇ Fi(w) प्रत्येक नियम A के लिए → w
  • Fi(a) ⊇ { a }, प्रत्येक टर्मिनल a के लिए
  • Fi(w0 w1) ⊇ Fi('w0) · Fi(w1), सभी शब्दों के लिए w0 और w1
  • Fi(ε) ⊇ {ε}


जहां, U और V शब्दों के सेट के लिए, काटे गए उत्पाद को द्वारा परिभाषित किया गया है, और w:1 यदि w की लंबाई 0 या 1 है, तो लंबाई 2 या अधिक वाले शब्दों के प्रारंभिक लंबाई-1 उपसर्ग या स्वयं w को दर्शाता है।

दुर्भाग्य से, प्रथम-सेट पार्सिंग टेबल की गणना करने के लिए पर्याप्त नहीं हैं। ऐसा इसलिए है क्योंकि किसी नियम का दाहिना भाग w अंततः रिक्त स्ट्रिंग पर फिर से लिखा जा सकता है। इसलिए पार्सर को नियम A → w का भी उपयोग करना चाहिए यदि ε 'Fi' (w) में है और यह इनपुट स्ट्रीम पर प्रतीक देखता है जो A का अनुसरण कर सकता है। इसलिए, हमें A के फॉलो-सेट की भी आवश्यकता है, जिसे यहां 'Fo' (A) के रूप में लिखा गया है, जिसे टर्मिनलों के सेट के रूप में परिभाषित किया गया है जैसे कि प्रतीकों αAaβ की स्ट्रिंग है जिसे प्रारंभ प्रतीक से प्राप्त किया जा सकता है। हम इनपुट स्ट्रीम के अंत को दर्शाने वाले विशेष टर्मिनल के रूप में '$' का उपयोग करते हैं, और प्रारंभ प्रतीक के रूप में S का उपयोग करते हैं।

ग्रामर में नॉनटर्मिनलों के लिए फॉलो-सेट की गणना निम्नानुसार की जा सकती है:

  1. 'Fo'(S) को { '$' } और अन्य सभी 'Fo'(A) से प्रारंभ करेंi) रिक्त सेट के साथ
  2. अगर फॉर्म A का नियम हैj → वाiw' , फिर
    • यदि टर्मिनल a 'Fi'(w' ) में है, तो 'फॉर्म'(A) में a जोड़ेंi)
    • यदि ε फ़ाइल में है, तो इसमें जोड़ें(एj) से फॉर्म(एi)
    • यदि a' की लंबाई 0 है, तो 'To'(A) जोड़ेंj) से फॉर्म(एi)
  3. फेज 2 को तब तक दोहराएँ जब तक कि सभी फ़ो सेट समान न रहें।

यह निम्नलिखित प्रणाली को न्यूनतम निश्चित बिंदु समाधान प्रदान करता है:

  • Fo(S) ⊇ {$}
  • फॉर्म बी के प्रत्येक नियम के लिए Fo(A) ⊇ Fi(w)·Fo(B) → ... A w

अब हम सटीक रूप से परिभाषित कर सकते हैं कि पार्सिंग टेबल में कौन से नियम कहाँ दिखाई देंगे। यदि T[A, a] नॉनटर्मिनल A और टर्मिनल a के लिए टेबल में प्रविष्टि को दर्शाता है, तो

T[A,a] में नियम A → w सम्मिलित है यदि और केवल यदि
a Fi(w) या में है
ε Fi(w) में है और a Fo(A) में है।

समान रूप से: T[A, a] में प्रत्येक a ∈ Fi(w) के लिए नियम A → w सम्मिलित है ·Fo(ए).

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

एक LL(k) पार्सिंग टेबल का निर्माण

LL(1) पार्सर्स के निर्माण को निम्नलिखित संशोधनों के साथ के > 1 के लिए LL(k) में अनुकूलित किया जा सकता है:

  • काटे गए उत्पाद को परिभाषित किया गया है , जहां w:k लंबाई > k, या w, वाले शब्दों की प्रारंभिक लंबाई-k उपसर्ग को दर्शाता है, यदि w की लंबाई k या उससे कम है,
  • Fo(S) = {$क}
  • Fi(ab) = Fi(a) प्रयुक्त करेंFi(β) LL(1) के लिए दिए गए Fi निर्माण के फेज 2 में भी है।
  • Fओ निर्माण के फेज 2 में, A के लिएj→ वाiw' बस 'Fi' जोड़ें(w')फ़ो(एj) से 'फॉर्म'(एi).

जहां k लुकअहेड कांटेक्स्ट को पूरी तरह से ध्यान में रखने के लिए, इनपुट को k एंड-मार्कर '$' द्वारा प्रत्यय दिया जाता है। यह दृष्टिकोण ε के लिए विशेष मामलों को समाप्त करता है, और LL (1) स्थिति में समान रूप से प्रयुक्त किया जा सकता है।

1990 के दशक के मध्य तक, यह व्यापक रूप से माना जाता था कि LL(k) पार्सिंग (k > 1 के लिए) अव्यावहारिक थी,[citation needed] चूंकि सबसे व्यर्थ स्थिति में पार्सर टेबल में k में घातीय फ़ंक्शन आकार होगा। यह धारणा 1992 के आसपास बारहसिंगे के शाखादार सींग के जारी होने के बाद धीरे-धीरे परिवर्तित कर गई, जब यह प्रदर्शित किया गया कि अनेक प्रोग्रामिंग लैंग्वेज को पार्सर के सबसे व्यर्थ स्थिति वाले व्यवहार को ट्रिगर किए बिना LL(k) पार्सर द्वारा कुशलतापूर्वक पार्स किया जा सकता है। इसके अलावा, कुछ मामलों में LL पार्सिंग असीमित लुकहेड के साथ भी संभव है। इसके विपरीत, yacc जैसे पारंपरिक पार्सर जनरेटर निश्चित वन-टोकन लुकहेड के साथ प्रतिबंधित LR पार्सर का निर्माण करने के लिए LALR पार्सर|LALR(1) पार्सर टेबलओं का उपयोग करते हैं।

संघर्ष

जैसा कि परिचय में बताया गया है, LL(1) पार्सर उन लैंग्वेज को पहचानते हैं जिनमें LL(1) ग्रामर होते हैं, जो कांटेक्स्ट-फ्री ग्रामर का विशेष मामला है; LL(1) पार्सर सभी कांटेक्स्ट-फ्री लैंग्वेज को नहीं पहचान सकते। LL(1) भाषाएँ एलआर(1) लैंग्वेज का उचित उपसमूह हैं, जो बदले में सभी कांटेक्स्ट-फ्री लैंग्वेज का उचित उपसमूह हैं। कांटेक्स्ट-फ्री ग्रामर को LL(1) ग्रामर बनाने के लिए, कुछ विरोध उत्पन्न नहीं होने चाहिए, जिनका वर्णन हम इस खंड में करते हैं।

शब्दावली

मान लीजिए A गैर-टर्मिनल है। FIRST(A) टर्मिनलों का सेट (परिभाषित) है जो A से प्राप्त किसी भी स्ट्रिंग की पहली स्थिति में दिखाई दे सकता है। FOLLOW(A) यूनियन ओवर है:[11]

  1. FIRST(B) जहां B कोई गैर-टर्मिनल है जो औपचारिक ग्रामर के दाईं ओर A के ठीक बाद आता है#ग्रामर का वाक्य-विन्यास।
  2. अनुसरण करें(बी) जहां बी फॉर्म बी → wए के नियम का कोई शीर्ष है।

LL(1) संघर्ष

LL(1) संघर्ष के दो मुख्य प्रकार हैं:

पहला/प्रथम संघर्ष

एक ही गैर-टर्मिनल प्रतिच्छेद के लिए दो अलग-अलग ग्रामर नियमों का पहला सेट। LL(1) प्रथम/प्रथम संघर्ष का उदाहरण: 

एस -> ई | ई 'A'
ई -> 'बी' | ε

FIRST(E) = {b, ε} और FIRST(E a) = {b, a}, इसलिए जब टेबल बनाई जाती है, तो उत्पादन नियम S के टर्मिनल b के तहत संघर्ष होता है।

विशेष मामला: बाईं पुनरावृत्ति

बायाँ प्रत्यावर्तन सभी विकल्पों के साथ प्रथम/प्रथम संघर्ष का कारण बनेगा। 

ई -> ई '+' पद | alt1 | alt2

पहला/अनुसरण संघर्ष

ग्रामर नियम का पहला और अगला सेट ओवरलैप होता है। पहले सेट में रिक्त स्ट्रिंग (ε) के साथ, यह अज्ञात है कि कौन सा विकल्प चुनना है। LL(1) संघर्ष का उदाहरण: 

एस -> A 'A' 'बी'
ए -> 'A' | ε

A का पहला सेट {a, ε} है, और अगला सेट {a} है।

LL(1) संघर्षों का समाधान

वाम फैक्टरिंग

एक सामान्य वाम-कारक को दूर कर दिया गया है। 

ए -> एक्स | एक्स वाई जेड

बन जाता है 

ए -> एक्स बी
बी -> वाई जेड | ε

इसे तब प्रयुक्त किया जा सकता है जब दो विकल्प ही प्रतीक से प्रारंभ होते हैं जैसे FIRST/FIRST संघर्ष।

उपरोक्त FIRST/FIRST संघर्ष उदाहरण का उपयोग करते हुए और उदाहरण (अधिक जटिल): 

एस -> ई | ई 'A'
ई -> 'बी' | ε

बन जाता है (एकल गैर-टर्मिनल में विलय) 

एस -> 'बी' | ε | 'बी' 'A' | 'A'

फिर वाम-फैक्टरिंग के माध्यम से, बन जाता है 

एस -> 'बी' ई | इ
ई -> 'A' | ε

प्रतिस्थापन

अप्रत्यक्ष या FIRST/FOLLOW विरोधों को दूर करने के लिए नियम को दूसरे नियम में प्रतिस्थापित करना। ध्यान दें कि इससे प्रथम/प्रथम विरोध उत्पन्न हो सकता है।

वाम पुनरावर्तन निष्कासन

देखना।[12] सामान्य विधि के लिए, बायाँ प्रत्यावर्तन#बायाँ प्रत्यावर्तन हटाना देखें। बाएँ पुनरावर्तन को हटाने का सरल उदाहरण: निम्नलिखित उत्पादन नियम ने ई पर रिकर्सन छोड़ दिया है 

ई -> ई '+' टी
ई -> टी

यह नियम और कुछ नहीं किन्तु '+' से अलग की गई Ts की सूची है। रेगुलर एक्सप्रेशन फॉर्म T ('+' T)* में। अतः नियम को इस प्रकार पुनः लिखा जा सकता है 

ई -> टी जेड
Z -> '+' T Z
जेड -> ε

अब कोई वाम पुनरावृत्ति नहीं है और किसी भी नियम पर कोई टकराव नहीं है।

चूँकि, सभी कांटेक्स्ट-फ्री ग्रामर में समतुल्य LL(k)-ग्रामर नहीं होता है, उदाहरण के लिए: 

एस -> A | बी
ए -> 'A' A 'बी' | ε
बी -> 'A' बी 'बी' 'बी' | ε

यह दिखाया जा सकता है कि इस ग्रामर द्वारा उत्पन्न लैंग्वेज को स्वीकार करने वाला कोई LL(k)-ग्रामर उपस्थित नहीं है।

यह भी देखें

टिप्पणियाँ

  1. ↑ Rosenkrantz, D. J.; Stearns, R. E. (1970). "नियतिवादी टॉप डाउन व्याकरण के गुण". Information and Control. 17 (3): 226–256. doi:10.1016/s0019-9958(70)90446-8.
  2. ↑ Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "एलएल-नियमित व्याकरण". Instytutu Maszyn Matematycznych: 107–119.
  3. ↑ Jarzabek, Stanislav; Krawczyk, Tomasz (Nov 1975). "एलएल-नियमित व्याकरण". Information Processing Letters. 4 (2): 31–37. doi:10.1016/0020-0190(75)90009-5.
  4. ↑ David A. Poplawski (Aug 1977). एलएल-नियमित भाषाओं के गुण (Technical Report). Purdue University, Department of Computer Science.
  5. ↑ Parr, Terence and Fisher, Kathleen (2011). "एलएल (*) एएनटीएलआर पार्सर जनरेटर की नींव". ACM SIGPLAN Notices. 46 (6): 425–436. doi:10.1145/1993316.1993548.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  6. ↑ Belcak, Peter (2020). "इष्टतम एलएल(के) पार्सिंग के लिए एलएल(परिमित) पार्सिंग रणनीति". arXiv:2010.07874 [cs.PL].
  7. ↑ Ford, Bryan (2004). "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation". ACM SIGPLAN Notices. doi:10.1145/982962.964011.
  8. ↑ Pat Terry (2005). C# और Java के साथ संकलन. Pearson Education. pp. 159–164. ISBN 9780321263605.
  9. ↑ William M. Waite and Gerhard Goos (1984). संकलक निर्माण. Texts and Monographs in Computer Science. Heidelberg: Springer. ISBN 978-3-540-90821-0. Here: Sect. 5.3.2, p. 121-127; in particular, p. 123.
  10. ↑ Richard E. Stearns and P.M. Lewis (1969). "संपत्ति व्याकरण और तालिका मशीनें". Information and Control. 14 (6): 524–549. doi:10.1016/S0019-9958(69)90312-X.
  11. ↑ "एलएल व्याकरण" (PDF). Archived (PDF) from the original on 2010-06-18. Retrieved 2010-05-11.
  12. ↑ Modern Compiler Design, Grune, Bal, Jacobs and Langendoen


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एलएल_पार्सर&oldid=240382’