हम एक LR (0) विश्लेषक लिखते हैं। जटिल के बारे में सरल शब्दों में

परिचय

शुभ दोपहर
मुझे रूसी में इस एल्गोरिथ्म का सरल और समझदार वर्णन नहीं मिला। मैंने इस अंतर को भरने का फैसला किया। सबसे पहले, यह क्या है? LR (0) पार्सर मुख्य रूप से एक पार्सर है। Parser का उद्देश्य टोकन की इनपुट स्ट्रीम (भाषा के मूल तत्व जो इनपुट कैरेक्टर स्ट्रीम के आधार पर उत्पन्न होता है, को संसाधित करना है, टोकन के उदाहरण एक संख्या, अल्पविराम, वर्ण हैं) और एक विशिष्ट प्रारूप में निर्दिष्ट भाषा के विवरण के साथ तुलना करते हैं। तुलना में एक निश्चित डेटा संरचना का निर्माण होता है, सबसे अधिक बार एक पेड़। इसके अलावा, यह संरचना अगले चरण में जाएगी - सिमेंटिक विश्लेषण, जहां कंपाइलर पहले से ही पेड़ के अर्थ को समझने की कोशिश कर रहा है।

पार्सर्स के 2 वर्ग हैं - अपस्ट्रीम और डाउनस्ट्रीम। पूर्व पत्तियों से शुरू होने वाले एक पेड़ का निर्माण करता है, जो इनपुट टोकन हैं, जबकि बाद वाले, इसके विपरीत, पेड़ की जड़ से शुरू होते हैं। दरअसल, LR का अर्थ है कि विश्लेषक बाएं से दाएं (L - 'लेफ्ट') स्ट्रीम को पढ़ेगा और नीचे से ऊपर एक ट्री बनाएगा (लेटर R, जिसका मतलब राइट है, कन्फ्यूज नहीं है, स्पष्टीकरण नीचे दिए गए हैं)। इंडेक्स 0 का मतलब है कि हम निम्नलिखित टोकन का पूर्वावलोकन नहीं करते हैं, लेकिन केवल वर्तमान के साथ काम करते हैं। इस प्रकार के विश्लेषक चुनने के क्या फायदे हैं?

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

इसके नुकसान भी हैं:

• निर्माण की सापेक्ष जटिलता।
• आप भाषा के विवरण की अस्पष्टता से विश्लेषक को एक मूर्ख में ड्राइव कर सकते हैं।

शब्दावली

एक टर्मिनल प्रतीक ( टर्मिनल ) एक प्रतीक है जो एक उपयोगकर्ता द्वारा विश्लेषक को दिया जा सकता है, हमारे मामले में, ये टोकन हैं।
गैर-प्रतीक चिह्न ( nonterminal , nonterminal ) - एक प्रतीक जो भाषा की एक वस्तु को दर्शाता है। उदाहरण के लिए, हम कहें कि प्रतीक A एक शब्द है। बेशक, हम ए के बजाय बहु-वर्ण नाम - शब्द चुन सकते हैं।
प्रसंग-मुक्त व्याकरण ( सीएफजी ) - प्रपत्र के नियमों का एक सेट , जहां ए एक नॉनटर्मिनल है, डब्ल्यू टर्मिनलों और नॉनटर्मिनल का एक मनमाना संग्रह है। लेख में मैं केवल व्याकरण का उपयोग करूंगा, इस संदर्भ से अर्थ मुक्त।
व्याकरण का एक छोटा सा उदाहरण, जिसके लिए हम एक विश्लेषक का निर्माण करेंगे:

यह व्याकरण दो संख्याओं - 0 और 1 पर अंकगणितीय संक्रियाओं के अधूरे सेट का वर्णन करता है। व्याकरण भाषा का वर्णन है। यह जांचने के लिए कि इनपुट स्ट्रीम हमारी भाषा से संबंधित है, या कहीं हमने एक सिंटैक्स त्रुटि की है (1+ के बजाय 1+ लिखा है), हम इस इनपुट स्ट्रीम को नियमों का पालन करने के लिए एक संभावित तरीके की तलाश कर रहे हैं, जो शुरुआती नॉन-टर्मिनल (हमारे पास ई) है। 1 + 1 के लिए, पथ ऐसा ई होगा, नियम 2 लागू करें, E + F, नियम 1, F + F, नियम 4, T + F, नियम 8, 1 + F, फिर से 4, 1 + T और अंत में आठवें, 1 + 1. जैसा कि आप देख सकते हैं, हम इनपुट स्ट्रिंग प्राप्त करने में सक्षम थे, इसका मतलब है कि यह वाक्यात्मक रूप से सही है।
अब हम विश्लेषक के नाम पर आर अक्षर को समझा सकते हैं। इसका मतलब है कि हम नियमों के चरम दाहिने हिस्से से स्वयंसिद्ध तक जाते हैं, अर्थात, सरल नियमों (7 और 8) से हम मूल (1) एकत्र करते हैं। एल-एनालाइजर (एलएल) नियमों के बाएं हिस्सों से विश्लेषण की अगली दिशा का चयन करने का प्रयास करता है।

इसके अलावा परिमित राज्य मशीनों ( FSM ) के बारे में उल्लेख के लायक है। यह एक मॉडल है जिसमें राज्यों का एक सेट और एक इनपुट स्ट्रीम है। मशीन प्रारंभिक अवस्था से शुरू होती है और वर्तमान और इनपुट प्रतीक के आधार पर अपना राज्य बदलती है। यही है, हम राज्य 0 से शुरू करते हैं, यदि इनपुट में प्रवेश करता है, तो ऑटोमेटन 1 राज्य में जाता है, और यदि बी 2 राज्य में। संक्रमण के यांत्रिकी एक तालिका द्वारा दिए गए हैं, जहां कॉलम वर्तमान स्थिति हैं, कॉलम इनपुट प्रतीक हैं।

एल्गोरिथ्म

विश्लेषक को काम करने के लिए कई चीजों की आवश्यकता होती है:

• इनपुट स्ट्रीम स्वयं, जिसका हम विश्लेषण करेंगे।
• स्टैक (डेटा संरचना जो LIFO (लास्ट इन फर्स्ट आउट) नियम का अनुपालन करती है) चादरों के ढेर के रूप में कल्पना करना सबसे आसान है - पार्सर राज्यों के लिए पत्ती को स्टैक में रखें, और स्टैक से तत्व की आवश्यकता होने पर पहले लें।
• एक्शन टेबल। वह बताती है कि वर्तमान स्थिति और इनपुट में वर्तमान चरित्र के साथ क्या करना है।
• रूपांतरण तालिका एक सहायक तालिका जिसका उपयोग किसी एक क्रिया में किया जाता है।

यहां यह स्पष्ट करना आवश्यक है कि विश्लेषक कैसे काम करेगा। वर्तमान स्थिति स्टैक के शीर्ष पर स्थित राज्य है। हम कार्यों की तालिका देखते हैं (सूचकांक वर्तमान इनपुट प्रतीक और वर्तमान स्थिति हैं)। इस तालिका में 4 प्रकार के रिकॉर्ड हो सकते हैं:

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

कोड रूप में, यह कुछ इस तरह दिखता है:

1. ढेर। धक्का ( राज्य [को ० ] ) ;
2. जबकि ( स्वीकृत )
3. {
4. राज्य * सेंट = ढेर। शीर्ष ( ) ;
5. टर्मिनल शब्द = एस [ inp_pos ] ;
6. अगर ( शर्तें। IsTerm ( शब्द ) )
7. त्रुटि ( ) ;
8. क्रिया * क्रिया = क्रिया। प्राप्त करें ( सेंट, शब्द ) ;
9. अगर ( कार्रवाई )
10. त्रुटि ( ) ;
11. स्विच ( क्रिया - > प्रकार )
12. {
13. मामला
14. स्वीकृत = सत्य ;
15. तोड़ना ;
16. मामला एक्शनशिफ्ट :
17. inp_pos ++ ;
18. ढेर। धक्का ( क्रिया - > राज्य ( ) ) ;
19. तोड़ना ;
20. मामला कार्रवाई :
21. नियम * नियम = क्रिया - > नियम ( ) ;
22. ढेर। पॉप ( नियम - > आकार ( ) ) ;
23. राज्य * transferState = transferTable। प्राप्त ( ढेर ) । शीर्ष ( ) , नियम - > वाम ( ) ) ;
24. अगर ( ट्रांसफरस्टैट )
25. त्रुटि ( ) ;
26. ढेर। धक्का ( transferState ) ;
27. तोड़ना ;
28. }
29. }

जैसा कि आप देख सकते हैं, विश्लेषण में कुछ भी जटिल नहीं है। हालाँकि, पूरी ट्रिक ये ट्रिकी टेबल बनाने की है। सबसे पहले, आइए जानें कि पार्सर अवस्था क्या है। यह एल्गोरिथ्म का एक बहुत ही गैर-तुच्छ हिस्सा है। और नहीं, यह सिर्फ एक संख्या नहीं है। हमें कई नई अवधारणाओं को पेश करना होगा।
सबसे पहले, ये आइटम हैं। यह एक नई संपत्ति के साथ एक नियम है - एक मार्कर। एक मार्कर इंगित करता है कि वर्तमान में हम किस तत्व की उम्मीद कर रहे हैं। तदनुसार, प्रत्येक नियम n + 1 टोकन उत्पन्न करता है, जहां n नियम के दाईं ओर वर्णों की संख्या है। उदाहरण के लिए, नियम 3 लें। सर्कल में प्लस मार्कर के स्थान को इंगित करता है।

दूसरे पैराग्राफ में मार्कर, उदाहरण के लिए, इंगित करता है कि हम वर्तमान चरित्र के साथ माइनस साइन देखने की उम्मीद करते हैं। कई वस्तुओं को मिलाना वस्तुओं का एक समूह है। दरअसल, राज्य एक निश्चित तरीके से एक साथ इकट्ठे किए गए आइटमों का एक समूह है।

लेकिन राज्यों के साथ काम करने के लिए, हमें पहले सेट को बंद करना होगा। इसका मतलब है कि हम एक पूर्ण विश्लेषक शाखा प्राप्त करना चाहते हैं। यही है, अगर सेट में एक बिंदु है जहां मार्कर एक नॉनटर्मिनल को इंगित करता है (और हमारे मामले में सभी नॉनटर्मिनल बाएं हिस्से हैं), तो आपको संबंधित नॉनटर्मिनल को "तैनात" करने की आवश्यकता है। यह केवल उन वस्तुओं को जोड़ने से होता है जिनके बायें हिस्से इस अपरंपरागत होते हैं, और मार्कर पहले वर्ण को इंगित करता है। अपने आप से, हम इसे पुनरावर्ती रूप से विस्तारित करते हैं, यदि नए जोड़े गए पैराग्राफ में पहला चरित्र एक गैर-टर्मिनल है, तो हम इसे भी बंद कर देते हैं। जब तक हमें पूरा सेट नहीं मिल जाता। उस सेट को बंद करें जिसमें केवल एक बिंदु है (पिछले उदाहरण में नंबर 3):

एफ का विस्तार करने से, हमें अंक 2, 3, 4 मिलता है। 3 और 4 में, हमें फिर से एफ का विस्तार करने की पेशकश की जाती है, हालांकि, हमारे पास पहले से ही सेट में ये नियम हैं, इसलिए हम छोड़ देते हैं। लेकिन टी तैनात नहीं है, ऐसा करने पर, हमें 5 और 6. सब कुछ मिलता है, क्लोजर तैयार है।

1. के लिए (बंद आइटम में )
2. {
3. अगर ( shut_item। isClose )
4. जारी रखें ;
5. तत्व मार्कर = बंद_आइटम। मार्कर ( ) ;
6. यदि ( मार्कर प्रकार । ) ! = ElementNonTerm )
7. {
8. closed_item। isClose = true ;
9. जारी रखें ;
10. }
11. नॉनटर्मिनल नॉनटर्म = मार्कर। नॉनटर्म ( ) ;
12. आइटम = अनुप्रास - > पहला ( 0 , नॉनटर्म ) ;
13. जबकि ( आइटम। आइटम ) ( )
14. {
15. अगर ( आइटमसेट मौजूद है ) ( आइटम )
16. itemset। जोड़ें ( आइटम ) ;
17. आइटम। अगला ( 0 , नॉनटर्म ) ;
18. }
19. closed_item। isClose = true ;
20. }

यह समझने के बाद कि राज्य क्या हैं, हम उनका निर्माण शुरू कर सकते हैं। सबसे पहले, हम एक नया नियम पेश करते हैं, जो आउटपुट का आधार है और जिसके लिए हमें अंत में आना चाहिए।


पहला राज्य, निश्चित रूप से, इस नियम के आधार पर एक आइटम का समापन होगा और ई की ओर इशारा करते हुए एक मार्कर के साथ। अब हम एक अस्थायी परिमित राज्य मशीन की एक तालिका बनाना शुरू करते हैं, जो संक्रमण और कार्रवाई तालिकाओं के आधार के रूप में काम करेगा। हम राज्य को प्रतीकों की कसौटी के अनुसार समूहों में तोड़ते हैं जिससे मार्कर इंगित करता है। उदाहरण से बंद करने के लिए 4 समूह होंगे- एफ-समूह, टी-समूह, 0-समूह और 1-समूह। प्रत्येक समूह एक नए राज्य के लिए एक संक्रमण है। संक्रमण से पहला सूचकांक वह प्रतीक है जिसके द्वारा हम वास्तव में समूह (एफ, टी, 0, 1)। दूसरा सूचकांक वर्तमान स्थिति है। और तालिका में मूल्य वह स्थिति है जिस पर हम पास होंगे। इस प्रकार, हमें 4 नए राज्य मिलते हैं। उनका निर्माण करना काफी सरल है - समूह में प्रत्येक बिंदु पर हम मार्कर को ओंड स्थिति पर दाईं ओर ले जाते हैं और परिणामी सेट को बंद कर देते हैं। यह एक नया राज्य होगा।

1. firstState। जोड़ें ( आइटम। पहले ) ( ) ;
2. firstState। मेक क्लोजर ( ) ;
3. राज्यों। add ( firstState ) ;
4. size_t state_idx = 0 ;
5. जबकि ( state_idx < राज्यों का आकार । )
6. {
7. राज्य * st = स्टेट्स [ state_idx ] ;
8. समूहीकृत समूह = सेंट - > समूह ( ) ;
9. for ( group_class in group )
10. {
11. अगर ( group_class - > पहला। प्रकार ) ( = = ElementEnd )
12. जारी रखें ;
13. स्टेट न्यूस्टेट ( और आइटम, स्टेट्स। साइज ( ) ) ;
14. for ( group_item in group_class )
15. newState। जोड़ें ( group_item, group_item। MarkerInt ( ) + 1 ) ;
16. newState। मेक क्लोजर ( ) ;
17. स्टेट ओल्डस्टेट = स्टेट्स। खोजें ( newState )
18. अगर ( पुराना है )
19. {
20. राज्यों। add ( newState ) ;
21. fsmTable। जोड़ें ( सेंट, group_class - > पहले, newState ) ;
22. }
23. अन्यथा
24. fsmTable। जोड़ें ( सेंट, group_class - > पहले, पुरानेस्टेट ) ;
25. }
26. State_idx ++ ;
27. }

संक्रमण तालिका बहुत सरल रूप से बनाई गई है - हम स्तंभों को एफएसएम तालिका से स्थानांतरित करते हैं, जिनमें से सूचक गैर-टर्मिनल हैं।

एक्शन टेबल थोड़ा और दिलचस्प है। एफएसएम से एक हिस्सा भी स्थानांतरित किया जाता है, बदले में, टर्मिनल सूचकांकों के साथ कॉलम, जबकि राज्य पैरामीटर के साथ पारी की कार्रवाई जो मूल अंतरिक्ष यान तालिका में दर्ज की गई थी, तालिका कोशिकाओं को लिखा जाता है। फिर हम एक नया कॉलम '$' जोड़ते हैं, जो इनपुट लाइन के अंत को चिह्नित करता है। इस कॉलम में हम स्वीकृत घटना दर्ज करते हैं, जिसमें लिखा होता है कि क्या इंडेक्स-स्टेट में आइटम है । इसका मतलब है कि सफलता, प्राथमिक नियम में बदल गई और उसी समय इनपुट स्ट्रीम खत्म हो गई। इसके बाद दोषी पर कार्रवाई होती है। प्रत्येक राज्य के लिए जिसमें एक आइटम है , जहां डब्ल्यू टर्मिनलों और गैर-टर्मिनलों का कोई संयोजन है, हम पूरी पंक्ति में लिखते हैं (निश्चित रूप से, हमारा मतलब है कि केवल नि: शुल्क कोशिकाएं जो अन्य आदेशों द्वारा कब्जा नहीं की जाती हैं) कम आदेश, उस आइटम के संबंधित नियम के पैरामीटर के साथ।

1. fsmTable। FeedTransferTable ( ट्रांसफरटेबल ) ;
2. fsmTable। फीडएशनटेबल ( एक्शनटेबल ) ;
3. मद अंत इतिम् = आइटम। गेट इटेम ( 1 , 'एस' , एलिमेंट्स ( "ई" , नॉनटर्म ) ) ;
4. के लिए ( राज्यों में सेंट )
5. अगर ( सेंट है। इटेम ( एंड इटेम ) )
6. actionTable। जोड़ें ( सेंट, '$' , नया एक्शन ( ) ) ;
7. के लिए ( राज्यों में सेंट )
8. {
9. आइटम सूची = सेंट। GetReducable ( ) ;
10. के लिए ( सूची में सूची )
11. actionTable। जोड़ें ( सेंट, नई कार्रवाई ( listItem। GetRule ( ) ) ) ;
12. }

साहित्य

कम्पाइलर: सिद्धांत, तकनीक और उपकरण, 1986, अल्फ्रेड वी। अहो, रवि सेठी, जेफरी डी। उल्मैन