शाब्दिक विश्लेषण व सिंटैक्स विश्लेषण

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

1. व्याकरण E → T X, X → + T X | ε, T → F Y, Y → * F Y | ε, F → ( E ) | id हेतु समुच्चय FOLLOW(T) है:

   1. { $, ) }
   2. { $, ), + }
   3. { $, ), *, + }
   4. { +, * }
   उत्तर देखें

   उत्तर: B — { $, ), + }

   { $, ), + }। E → T X में T के पश्चात् X आता है, अतः FIRST(X) − {ε} = { + } भीतर जाता है; और चूँकि X, ε व्युत्पन्न कर सकता है, FOLLOW(E) = { $, ) } में सब कुछ भी T के पश्चात् आता है। विकल्प A, FOLLOW(E) व FOLLOW(X) है, जो वस्तुतः भिन्न समुच्चय है — यह देखना कि E व X एक FOLLOW साझा करते हैं जबकि T व Y बड़ा वाला, सम्पूर्ण गणना पर अच्छी जाँच है। विकल्प C, FOLLOW(F) है, जो अतिरिक्त रूप से * उठाता है क्योंकि F के पश्चात् Y आता है। यहाँ काम करता यांत्रिक नियम यह है कि जब पश्चवर्ती अ-टर्मिनल लुप्त हो सके, तो वाम पक्ष का FOLLOW बहकर आ जाता है।

2. किसी व्याकरण में उत्पादन A → A α है। इससे निकलता है कि वह व्याकरण:

   1. LL(1) नहीं है
   2. LR(1) नहीं है
   3. अस्पष्ट है
   4. उसके FOLLOW समुच्चय नहीं हैं
   उत्तर देखें

   उत्तर: A — LL(1) नहीं है

   LL(1) नहीं। ऊपर-से-नीचे पार्सर स्टैक पर A देखकर A → A α चुनने पर कोई निवेश खपाए बिना पुनः A पुश करेगा, और अनंत काल ऐसा कर सकता है — अतः वाम-पुनरावर्तन किसी भी k हेतु LL(k) पर पूर्ण रोक है। परंतु वह LR हेतु कोई अवरोध ही नहीं, जो नीचे-से-ऊपर है और वाम-पुनरावर्तन स्वाभाविक रूप से सँभालता है, वस्तुतः उसे पसंद करता है क्योंकि वह स्टैक उथला रखता है। विकल्प C नामित करने योग्य त्रुटि है: वाम-पुनरावर्तन व अस्पष्टता असंबद्ध हैं, और मानक वाम-पुनरावर्ती व्यंजक व्याकरण पूर्णतः अनस्पष्ट है। व्यावहारिक परिणाम यह है कि वाम-पुनरावर्तन हटाना केवल ऊपर-से-नीचे पार्सर हेतु उठाया कदम है, और वही व्यंजक व्याकरण को ऊपर प्रयुक्त LL(1) रूप में बदलता है।

3. व्याकरण S′ → S, S → C C, C → c C | d हेतु प्रामाणिक LR(0) संग्रह में कितने आइटम समुच्चय हैं?

   संख्यात्मक उत्तर — मान टाइप करें।

   उत्तर देखें

   उत्तर: 7

   सात। S′ → · S का संवरण लें, फिर S, C, c व d पर बारंबार goto लगाएँ जब तक कोई नया समुच्चय न आए; रचना सात आइटम समुच्चयों पर समाप्त होती है। आँकड़ा दो बार महत्व रखता है, क्योंकि वह इस व्याकरण हेतु SLR(1) व LALR(1) सारणियों की अवस्थाओं की संख्या भी है — उनमें कोई स्वचालित्र नहीं बदलता, वे केवल यह बदलते हैं कि न्यूनन-प्रविष्टियाँ कैसे भरी जाएँ। केवल प्रामाणिक LR(1) के पास अधिक होतीं। अतः "SLR पार्सर में अवस्थाओं की संख्या" पूछता प्रश्न यही 7 चाहता है, और इसके बजाय LR(1) संग्रह निकालना गलत उत्तर हेतु अधिक काम है।

4. व्याकरण S → if S else S | if S | a, LL(1) नहीं है। उसकी LL(1) सारणी के कितने कोष्ठों में संघर्ष है?

   1. एक
   2. दो
   3. तीन
   4. कोई नहीं — वह LL(1) है
   उत्तर देखें

   उत्तर: A — एक

   एक। FIRST(S) = { if, a }, और दोनों if-उत्पादन if से आरंभ होते हैं, अतः दोनों एकमात्र कोष्ठ (S, if) में आ जाते हैं। तीसरा उत्पादन, S → a, अकेला (S, a) में जाता है। एक संघर्षित कोष्ठ, और व्याकरण को अयोग्य ठहराने हेतु वह पर्याप्त है। उस गणना से पृथक् करने योग्य गहन दोष है: व्याकरण अस्पष्ट है — if a else a के दो पार्स वृक्ष हैं — और अस्पष्टता LR(1) को भी बाहर करती है, अतः कितना भी लुकअहेड सहायता नहीं करता। अतः संकलक उसे व्याकरण के बाहर के नियम से सुलझाते हैं, प्रत्येक else को निकटतम अ-मिलान if से बाँधकर।

5. LR कुल के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक सही हो सकते हैं।)

   1. LALR(1) व SLR(1) पार्सरों की अवस्थाओं की संख्या समान होती है
   2. प्रत्येक LL(1) व्याकरण LR(1) है
   3. अस्पष्ट व्याकरण LALR(1) हो सकता है
   4. प्रामाणिक LR(1) को LALR(1) से अधिक अवस्थाएँ चाहिए हो सकती हैं
   उत्तर देखें

   उत्तर: A — LALR(1) व SLR(1) पार्सरों की अवस्थाओं की संख्या समान होती है; B — प्रत्येक LL(1) व्याकरण LR(1) है; D — प्रामाणिक LR(1) को LALR(1) से अधिक अवस्थाएँ चाहिए हो सकती हैं

   A, B व D। SLR(1) व LALR(1) दोनों LR(0) अवस्था-समुच्चय पर बने हैं और केवल इसमें भिन्न हैं कि न्यूनन-प्रविष्टियाँ कैसे निकाली जाएँ, अतः उनकी अवस्था-गणनाएँ सहमत हैं (A) — और प्रामाणिक LR(1), जो कोर विलीन करने के बजाय लुकअहेड पृथक् रखता है, के पास कहीं अधिक हो सकती हैं (D)। B अंतर्वेशन LL(1) ⊂ LR(1) है, और वह कठोर है, अतः विलोम विफल है। C असत्य है: अस्पष्टता का अर्थ एक माला हेतु दो पार्स वृक्ष है, और निर्धारणवादी पार्सर के पास चुनने का आधार नहीं, अतः कोई अस्पष्ट व्याकरण किसी भी प्रकार का LR नहीं। इसीलिए अस्पष्ट व्याकरण कोई सारणी बनने से पूर्व अयोग्य हो जाता है, और इसीलिए डैंगलिंग else को अधिक शक्तिशाली पार्सर के बजाय नीति से सँभाला जाता है।

6. शाब्दिक विश्लेषक से यह जाँचा नहीं जा सकता कि प्रोग्राम में कोष्ठक संतुलित हैं, क्योंकि:

   1. वह संकलक में बहुत पहले चलता है
   2. संतुलित कोष्ठक नियमित भाषा नहीं हैं
   3. उसके पास प्रतीक-सारणी नहीं है
   4. कोष्ठक टोकन नहीं हैं
   उत्तर देखें

   उत्तर: B — संतुलित कोष्ठक नियमित भाषा नहीं हैं

   लेक्सर परिमित स्वचालित्र है, अतः वह ठीक नियमित भाषाएँ पहचानता है — और संतुलित कोष्ठक मानक अ-नियमित भाषा है, जिसे अपरिबद्ध गणना चाहिए जो कोई नियत अवस्था-संख्या नहीं दे सकती। वह समस्या-वर्ग के विषय में कथन है, पाइपलाइन में लेक्सर के स्थान (विकल्प A) या उसकी आँकड़ा-संरचनाओं (विकल्प C) के विषय में नहीं। कोष्ठक निश्चित रूप से टोकन हैं (विकल्प D); लेक्सर प्रसन्नता से प्रत्येक की सूचना देता है और सरलतः यह नहीं कह सकता कि वे युग्मित होते हैं या नहीं। उन्हें मिलाना पार्सर का काम है, और वह संदर्भ-मुक्त समस्या है यही कारण है कि पार्सर स्टैक प्रयोग करते हैं।

7. LL(1) पार्सिंग सारणी भरने में किसी अ-टर्मिनल A का FOLLOW समुच्चय देखा जाता है:

   1. A के प्रत्येक उत्पादन हेतु
   2. केवल A के उन उत्पादनों हेतु जिनका दक्षिण पक्ष ε व्युत्पन्न कर सके
   3. कभी नहीं
   4. केवल जब A आरंभ प्रतीक हो
   उत्तर देखें

   उत्तर: B — केवल A के उन उत्पादनों हेतु जिनका दक्षिण पक्ष ε व्युत्पन्न कर सके

   प्रत्येक उत्पादन A → α, FIRST(α) के प्रत्येक टर्मिनल के अंतर्गत भरा जाता है; FOLLOW(A) केवल तब प्रयुक्त होता है जब α, ε व्युत्पन्न कर सके, क्योंकि वही एक स्थिति है जहाँ पार्सर को A को कुछ नहीं में विस्तारित करने और आगे जो आए उसे A के बुलाने वाले से सँभलवाने का निर्णय करना होता है। व्यावहारिक लाभ वास्तविक है: ε-उत्पादनों से रहित व्याकरण में FOLLOW सारणी को कभी स्पर्श नहीं करता, अतः उसकी गणना व्यर्थ काम है — और ऊपर के व्यंजक व्याकरण में केवल X व Y के FIRST समुच्चयों में ε है, और ठीक वहीं उनके FOLLOW समुच्चय अपना मूल्य चुकाते हैं। आरंभ से पूर्व ε-उत्पादन जाँचना बताता है कि आपको कितनी गणना चाहिए।

8. yacc या bison जैसा उपकरण कौन-सा पार्सर उत्पन्न करता है?

   1. LL(1)
   2. SLR(1)
   3. LALR(1)
   4. प्रामाणिक LR(1)
   उत्तर देखें

   उत्तर: C — LALR(1)

   LALR(1), और कारण वह सौदा है जो वह करता है: वह SLR(1) से कठोरतः अधिक शक्तिशाली है जबकि LR(0) जितनी ही अवस्थाएँ रखता है, क्योंकि वह कोर साझा करती LR(1) अवस्थाएँ विलीन करता है। प्रामाणिक LR(1) उससे भी अधिक शक्तिशाली है पर उसे कहीं अधिक अवस्थाएँ चाहिए हो सकती हैं, जिसने इन उपकरणों के लिखे जाने के समय उसे अव्यावहारिक बनाया और वह अब भी प्रायः सारणी-आकार के योग्य नहीं। विलयन की एक लागत जानने योग्य है: कोर विलीन करना ऐसे न्यूनन–न्यूनन संघर्ष ला सकता है जो प्रामाणिक LR(1) में न होते, अतः कोई व्याकरण LR(1) हो सकता है और LALR(1) नहीं — और ठीक इसीलिए अनुक्रम तुल्य लेबलों के समुच्चय के बजाय कठोर अंतर्वेशनों की श्रृंखला है।