🤙🏾 🚶🏼 👨🏾‍🎓 LALR (1) पार्सर्स के लिए एक कंपाइलर लिखना। LR जनरेटर का वर्णन 👈🏻 👸🏿 📞

प्रस्तावना

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

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

विकास क्यों आवश्यक है?

यदि आप पिछले भाग में उदाहरण के आदिम कोड को देखते हैं, तो आप देख सकते हैं कि एल्गोरिथ्म की जटिलता की गणना O (n) के रूप में की जाती है, जहाँ n इनपुट वर्णों की संख्या है। मैं तुरंत कहूंगा कि यह एल्गोरिदम के लिए एक बहुत अच्छा निशान है। उदाहरण के लिए, सबसे तेज़ छँटाई के लिए, जटिलता हे (n * log (n)) है। हालाँकि, इस कथन का एल्गोरिथ्म की जटिलता के बारे में क्या मतलब है? लेकिन इसका मतलब है कि हमें एन ऑपरेशन नहीं, बल्कि कम से कम सी * एन करना होगा, जहां सी एक स्थिर है। इस उदाहरण के लिए, स्थिरांक बहुत बड़ा है - सभी नियमों की लंबाई का योग, और आसानी से 100, 1000, और 10000 हो सकते हैं। अर्थात्, 10 वर्णों की एक स्ट्रिंग के लिए, हम एक लाख ऑपरेशनों का खर्च उठाएंगे। लेकिन यह पहले से ही बहुत खराब है।

इसलिए हमें स्वयं पार्सर के एल्गोरिथ्म में सुधार करने की आवश्यकता है। मूल विचार प्रत्येक चरण और आने वाले टर्मिनल के नियमों के बारे में जानना है, जिसमें यह प्रतीक, पिछले कई लोगों के साथ मिलकर, एक कनवल्शन (अंतिम K वर्णों की जगह, जिसमें पहले से ही गैर-टर्मिनल शामिल हैं, एक गैर-टर्मिनल में शामिल हो सकता है) और जिसमें - स्थानांतरण, अर्थात्, यह निर्धारित करते हुए कि इस टर्मिनल ने अपना स्थान कहां लिया है। मोटे तौर पर, अगर नियम A = 012 और B = 021 हैं, तो लाइन 01 नियम A के लिए एक ले-ओवर की ओर ले जाएगा, नियम B के अनुसार एक ले-ओवर के लिए 02 और नियम A के अनुसार 012 एक सजा के लिए। यह विचार पूर्वोक्त निरंतर C को 1 के करीब लाएगा। यह देखना आसान है कि यह योजना एफएसएम (राज्य मशीनों) की अवधारणा में बहुत अच्छी तरह से फिट बैठती है। सरल शब्दों में, यह एक दो-आयामी तालिका है, जो वर्तमान स्थिति संख्या और आने वाले प्रतीक द्वारा नया राज्य नंबर देती है। और इसलिए जब तक हम अंतिम स्थिति तक नहीं पहुंच जाते।

FSM बताता है

ठीक है, अच्छा है। मुझे लगता है कि यह स्पष्ट है कि राज्यों को नियमों में चरित्र की वर्तमान स्थिति को प्रतिबिंबित करना चाहिए - उपरोक्त उदाहरण ए और बी के लिए पहले पढ़े गए वर्ण 0, 1 के साथ, राज्य को "हम पहले से ही ए के 3 नियमों के पहले 2 अक्षर" के रूप में वर्णित किया जा सकता है। यदि हम नियम C = 013 जोड़ते हैं, तो राज्य कम विशिष्ट होगा: "हम पहले से ही 3 ए या सी" के पहले 2 अक्षर पढ़ चुके हैं। और फिर सब कुछ अगले चरित्र पर निर्भर करेगा - 2 या 3. यदि 2 आता है, तो राज्य पर जाएं "हम 3 ए से 3 वर्ण पढ़ते हैं" और फिर हम एक कन्वोकेशन का आयोजन करेंगे - 012 को चरित्र ए में 3 और सी के लिए क्रमशः - उसी तरह से बदल देंगे। यह स्पष्ट होना चाहिए।

इसके अलावा, हमें यह निर्धारित करने की आवश्यकता है कि कहां शुरू करना है और कब बंद करना है। इस उदाहरण में, शुरुआत "हम 3x ए या बी या सी से 0 वर्ण पढ़ते हैं"। समाप्ति भी स्पष्ट है - ए / बी / सी के लिए 3 संभव "3 का 3" राज्य। यही है, जब एक नियम के अनुसार एक सजा होती है, तो हम रोकते हैं। हालांकि, अगर यह एक आदिम के लिए काम करता है, तो यह इसे थोड़ा जटिल करने के लायक है, और सब कुछ टूट जाता है।

A = 0 A | 1

ऐसा व्याकरण एम शून्य और फिर 1 को अंत में परिभाषित करता है, उदाहरण के लिए, "0000001"। कठिनाई क्या है? और यह तथ्य कि अब हम यह निर्धारित नहीं कर सकते कि कब रुकना है। यही है, अगर हम कनवल्शनशन ए पर रुकते हैं, तो पहले कनवल्शन के तुरंत बाद (जब हम टर्मिनल 1 पढ़ते हैं, हम इसे ए में ध्वस्त कर देते हैं) और हम रुक जाते हैं और एक और एम कनोल्यूशन (नियम ए = 0 ए के अनुसार) नहीं करते हैं। इसलिए, एक व्याकरण विकसित करते समय, एक प्रारंभिक चरित्र की उपस्थिति पर प्रतिबंध लगाया जाता है, जिससे व्याकरण एकत्र किया जाएगा। एस = ए | B | सी। लेकिन इसके अलावा, विशेष प्रतीक एस 'और नियम एस' = एस को स्वचालित रूप से पार्सर में जोड़ा जाता है। और फिर इस नियम के दोषी होने की स्थिति में हमें पता चल जाएगा कि मिशन पूरा हो गया है, हम घर जा सकते हैं। इस प्रकार, हमने एक साथ प्रारंभिक स्थिति को निर्धारित किया - "हमने नियम एस 'द्वारा 1 से 0 वर्णों को गिना, और अंतिम एक।

अब राज्य कोडिंग के बारे में सोचने का समय है। खैर, हम अपनी इच्छाओं और अपेक्षाओं को सादे पाठ में नहीं लिखेंगे। विश्लेषक बस हमें समझ में नहीं आता है। हमें ऊपर उपयोग किए गए अधिकतम के मशीन प्रतिनिधित्व के बारे में सोचने की जरूरत है। वास्तव में, यह प्राथमिक है अगर हम उनकी आपस में तुलना करें। उनमें केवल 2 परिभाषित बिंदु होते हैं - नियम और इस नियम में वर्तमान स्थिति। और, जैसा कि उदाहरणों से देखा जा सकता है, एक राज्य में कई ऐसे सेट हो सकते हैं। क्लासिक में सेट को आइटम कहा जाता है। और वे इस तरह दिखते हैं: ए = 01 · 2, अर्थात्, उन्होंने नियम A = 012 में 2 वर्ण पढ़े।

एफएसएम तालिका

यह केवल एफएसएम को सेट करने के लिए ही रहता है और पार्सर वास्तव में तैयार है। राज्यों के बीच संक्रमण तालिका बहुत सरल रूप से बनाई गई है - दृढ़ संकल्प तब निर्धारित किया जाता है जब हम एक ऐसे राज्य का सामना करते हैं जिसमें सभी वर्णों के साथ एक नियम होता है। यही है, मार्कर (·) बहुत अंत में है। इसके अलावा, चूंकि तालिका में स्तंभ वर्तमान वर्ण द्वारा सेट किए गए हैं, हमें सभी संभावित टर्मिनलों का पता लगाना चाहिए जो ढहने वाले वर्ण का अनुसरण कर सकते हैं। यदि एक दृढ़ संकल्प का गठन किया जाता है, लेकिन फिर एक प्रतीक इस प्रकार है, अच्छी तरह से, जो कि व्याकरण के सामान्य तर्क द्वारा किसी भी तरह से वहां नहीं पाया जा सकता है, तो यह एक गलती है। एक उदाहरण:

 #start A A = B 2 B = 01

यहां, B को दोषी ठहराने के दौरान, हमें यह देखना चाहिए कि 2 इस प्रकार हैं, और कोई अन्य वर्ण नहीं। मुझे लगता है कि इस सेट की गणना का तर्क समझ में आता है, और यदि नहीं, तो नीचे एक छद्म एल्गोरिथ्म होगा। इस बिंदु के अलावा, जब दोषी होते हैं, तो आपको इस बात पर ध्यान देने की आवश्यकता होती है कि किस अभिभावक द्वारा विश्लेषण किए जाने की आवश्यकता है। यही है, एक दृढ़ संकल्प चिन्ह आसानी से कई नियमों में भाग ले सकता है, और हमें यह स्पष्ट रूप से जानना होगा कि किस नियम में यह ऑपरेशन वर्तमान में चल रहा है ताकि संबंधित राज्य में स्विच किया जा सके। यह एक राज्य ढेर को बनाए रखने के द्वारा हल किया जाता है। जब स्थानांतरण (टर्मिनल प्राप्त करना और राज्य बदलना), हम स्टैक पर राज्य संख्या को धक्का देते हैं। और सजा के दौरान हम स्टैक एल तत्वों से निकालते हैं, जहां एल अभिव्यक्ति के दाईं ओर की लंबाई है (तत्वों का एक सेट जो एक गैर-समरूप में ढह जाता है)। और हम नए राज्य का सूचकांक रखते हैं, जो एक ही FSM तालिका द्वारा निर्धारित किया जाता है, जिसमें न्यूनतम नियम के बाईं ओर के नॉनटर्मिनल के बराबर कॉलम संख्या और स्टैक के शीर्ष पर लाइन संख्या - राज्य होता है। यह बोझिल लग सकता है, लेकिन यह वास्तव में सरल है। मैं उपरोक्त व्याकरण पर एल्गोरिथ्म के संचालन का वर्णन करूंगा।

  0.  0  1. ,  s0 {A = · B 2},  {0}  2. ,   = [s0, 0] = s1 {B = 0 · 1} ,  {0},  1  3. ,   = [s1, 1] = s2 {B = 0 1 ·} ,  {0, 1},  2  4. ,   [s2, 2]     (2 -  ),   = [s2, 2] = s3 {A = B · 2},  {B}  5. ,   = [s3, 2] = s4 {A = B 2 ·} ,  {B, 2},  EOF (   )  6. ,   = [s4, EOF] = s5 {S = A ·},  {A}  7. ,   = [s5, EOF] = s6  {S},  ,       ,

हमने सजा का पता लगा लिया है, लेकिन यह अभी तक स्पष्ट नहीं है कि हम राज्यों के बीच संक्रमण का निर्धारण कैसे करते हैं और वे कहां से आते हैं। और सब कुछ तुच्छ रूप से हल हो गया है - हम बस सभी उपलब्ध पात्रों (टर्मिनलों और गैर-टर्मिनलों) पर पुनरावृति करते हैं, वर्तमान स्थिति का विश्लेषण करने के लिए आवेदन करते हैं। यदि इसमें फॉर्म का एक आइटम {A = ... · X ...} है, जहां X एक इनलाइन वर्ण है, तो हम मार्कर को स्थानांतरित करते हैं (यह सिर्फ X प्रतीक का उपयोग है) और नए राज्य का आइटम प्राप्त करें {A = ... X · .. ।}। बेशक, अगर हमारे पास एक्स के लिए कई ऐसे आइटम हैं, तो नए राज्य में कई प्रविष्टियां भी होंगी। इसके अलावा, इस प्रक्रिया के दौरान, हम वांछित एफएसएम का निर्माण करते हैं: [sOld, X] = sNew। यह तालिका की लगभग समाप्त पंक्ति है। आपको बस इसमें कनवल्शन तत्व जोड़ने की जरूरत है।

एक और महत्वपूर्ण बिंदु। फिर से, यदि हम अंतिम उदाहरण की ओर मुड़ते हैं, तो हम देख सकते हैं कि केवल {A = B · 2} और [s0, B] = sX को प्रारंभिक अवस्था {A = · B 2} से प्राप्त किया जा सकता है। लेकिन यह गलत है और कभी काम नहीं करेगा। सिर्फ इसलिए कि प्रारंभिक अवस्था के इनपुट पर हमें नॉन-टर्मिनल (B) नहीं मिलता है, लेकिन केवल एक इनपुट टर्मिनल (0, 1, 2) होता है। एल्गोरिथ्म के संचालन को सुनिश्चित करने के लिए, खाते को संभव घुमावों में लेना आवश्यक है (ऑपरेशन दृढ़ संकल्प के विपरीत है)। यही है, इस मामले में, व्याकरण से, हम देखते हैं कि हम बी का विस्तार कर सकते हैं और सशर्त रूप से {A = · 0 1 2} बोल सकते हैं, जो पूरी तरह से तर्क से मेल खाती है। मैंने जो वर्णन किया है उसे औपचारिक रूप देते हुए, यह लिखा जा सकता है: "यदि राज्य में {X = ... · Y ...} है, तो इसमें {Y = · ...}} के आइटम भी होने चाहिए। इस विस्तार प्रक्रिया को क्लोजर कहा जाता है।

यह सब, अब सिद्धांत FSM पीढ़ी एल्गोरिथ्म और FSM- आधारित विश्लेषक दोनों को संकलित करने के लिए पर्याप्त है। निर्माण का छद्म कोड:

 /*      ,      */ function firstTerminal(X) { if (X.type == Terminal) return X; result = []; for (rule in rules) { //  X = Y ... if (rule.left == X) { //  , first(Y) result[] = first(rule.right[0]) } } return result; } //    ,     function nextTerminal(X) { result = []; for (rule in rules) { //  Y = ... X if (rule.right.end(X)) { /*   X   Y,   X     ,    Y */ result[] = nextTerminal(rule.left); } else { //  Y = ... X ... if (rule.right.has(X)) { //         result[] = firstTerminal(rule.right.next(X)); } } } return result; } //  function closeItem(I) { for (item in I) { //      Y = ... · X ..., X   if (item.markered.type == NonTerminal) { for (rule in rules) { //  X = ... if (rule.left == item.markered) { //   X = · ... I[] = {rule: rule, marker: 0}; } } } } } //        FSM function addReducing(I, FSM) { for (item in I) { //  X = ... · if (item.markered == item.end) { //     S = A,  A -   if (item.rule.left == _START_) { //   ,    ,    FSM[I.index, EOF] = Success; } else { //    ,      for (term in nextTerminal(item.rule.left)) { /* rule      :           */ FSM[I.index, term] = {operation: Reduce, rule: item.rule}; } } } } } //     I    X function shiftState(I, X) { result = []; for (item in I) { //  Y = ... · X ... if (item.markered == X) { //      result[] = {rule: item.rule, marker: item.marker + 1}; } } return closeItem(result); } //    function buildFSM() { FSM = {}; //     S = · A states = [closeItem({rule: {S = A}, marker: 0})]; for (state in states) { //      addReducing(state, FSM); for (X in symbols) { new = states[] = shiftState(state, X); //   FSM[state.index, X] = {operation: Shift, index: new.index}; } } }

एल्गोरिथम कोड:

 input >> term; accepted = false; /*   0 ,      ,   ==   */ stack = [0]; while (!accepted) { //   - stack.top() state = FSM[stack.top(), term]; switch (state) { case Success: accepted = true; break; case Shift: //      stack.push(state.index); input >> term; break; case Reduce: //  L  stack.pop(state.rule.right.length); // state.rule.left -     // stack.pop() -  ,   X stack.push(FSM[stack.pop(), state.rule.left]); //     {..., Y, ..., Z}  {..., X}   X = Y ... Z break; default: throw SyntaxError; } }

एल्गोरिथ्म का और सुधार। एसएलआर (1)

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

 A = B 2 | C B = C 0 | 1 C = B States: S0: [{S = · A}, {A = · B 2}, {A = · C}, {B = · C 0}, {B = · 1}, {C = · B}] S1: [{S = A ·}],   S0   A S2: [{A = B · 2}, {C = B ·}],   S0   B ... SX: [{A = B 2 ·}],   S2   2

व्याकरण में प्रपत्र 10 ... 02 और 10 ... 0 की पंक्तियों का वर्णन किया गया है। नेक्स्टबोल = [0, 2, ईओएफ]। और फिर हमें यह मिलता है कि एफएसएम [एस 2, 2] के लिए हमें नियम C = B के अनुसार एक कनवल्शन करने की आवश्यकता है, लेकिन उसी क्षण नियम A = B 2 के अनुसार हमें उसी टर्मिनल 2 पर राज्य S2 द्वारा SX में स्थानांतरण करना चाहिए। । यह दुखद है। यह इसलिए हुआ क्योंकि बिंदु C = B के लिए S2 की स्थिति में हमें A = C EOF के आधार पर केवल EOF की प्रतीक्षा करनी चाहिए, और कोई 2 या 0. वे केवल भविष्य में दिखाई दे सकते हैं।

हां। यह एक सिंथेटिक उदाहरण है, लेकिन वास्तव में ऐसे जाल वाले व्याकरण हैं। इसके अलावा, यह इतना दुर्लभ नहीं है। समाधान स्पष्ट है - उन बिंदुओं का निर्धारण जो अनुमान को प्रतीक के अनुसार उत्पन्न करते हैं। यही है, {C = B ·} सशर्त रूप से {C = B · [उम्मीद EOF]} या संक्षिप्तता {C = B ·, EOF} में बदल जाता है। केवल 2 अंक प्रभावित होते हैं - अंकों की पीढ़ी (यह एक नए प्रारूप के अंक बनाने के लिए आवश्यक है) और एक दृढ़ संकल्प के साथ कोशिकाओं की पीढ़ी। यही है, वहाँ केवल 2 कार्य हैं closeItem () और addReducing ():

 //  function closeItem(I) { for (item in I) { //      Y = ... · X ..., X   if (item.markered.type == NonTerminal) { for (rule in rules) { //  X = ... if (rule.left == item.markered) { // X -   if (item.nextMarkered == item.end) { //       first = item.expect; } else { //        first = firstTerminal(item.nextMarkered); } //     for (expect in first) { //   X = · ... I[] = {rule: rule, marker: 0, expect: expect}; } } } } } } //        FSM function addReducing(I, FSM) { for (item in I) { //  X = ... · if (item.markered == item.end) { //     S = A,  A -   if (item.rule.left == _START_) { //   ,    ,    FSM[I.index, EOF] = Success; } else { /*      ,       */ FSM[I.index, item.expect] = {operation: Reduce, rule: item.rule}; } } } }

शीर्ष - LALR (1)

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

एक रास्ता खोजना मुश्किल नहीं है - हम राज्यों को जोड़ते हैं जो केवल अपेक्षित प्रतीक में भिन्न होते हैं। उदाहरण के लिए: [{A = B, 0}, {B = C, 0}] और [{A = B, 1}, {B = C, 1}]। क्यों सुरक्षित है?

संक्रमण के दौरान एक नए राज्य का निर्माण करते समय, हम किसी भी तरह से अपेक्षित प्रतीक का उपयोग नहीं करते हैं, इसलिए यदि s0 और s1 कर्नेल (अपेक्षित प्रतीक को छोड़कर आइटम का भाग) में समान हैं, तो s2 से X द्वारा उत्पन्न s2 और s1 से X द्वारा उत्पन्न s2 भी कर्नेल में समान हैं। । इस प्रकार, हम आसानी से s0 और s1 को sn0, s2 और s3 में sn1 के साथ जोड़ सकते हैं, और उनके बीच संबंध बना सकते हैं। यह पूरी तरह से सही है।
एफएसएम तालिका का दूसरा भाग दृढ़ संकल्प है। लेकिन यहाँ यह स्पष्ट है कि परिभाषा के अनुसार, वे प्रतिच्छेद नहीं कर सकते हैं, क्योंकि राज्यों में अलग-अलग उम्मीद के प्रतीक हैं, तो इसी उम्मीद के प्रतीक के लिए केवल 1 सेल में संकल्प दर्ज किए जाते हैं। और वे दर्द रहित रूप से संयुक्त हो सकते हैं।

इस प्रकार, अंत में हमें एक ही LR (0) मिलता है, लेकिन व्याकरण प्रतिबंध के बिना।

लेख के अंश

भाग 1. मूल सिद्धांत
भाग 2. LR जनरेटर का विवरण
भाग 3. एलआर-जनरेटर के लेखन और संभव सुविधाओं की विशेषताएं

LALR (1) पार्सर्स के लिए एक कंपाइलर लिखना। LR जनरेटर का वर्णन