parsing क्या फ्लेक्स/बाइसन के लिए कोई विकल्प है जो 8-बिट एम्बेडेड सिस्टम पर प्रयोग योग्य है?




embedded bison (5)

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

अगर मैं इसे अपने लिनक्स बॉक्स पर चलाने के लिए लिखूंगा, तो मैं फ्लेक्स / बाइसन का उपयोग कर सकता हूं। अब जब मैंने खुद को 8-बिट प्लेटफॉर्म पर प्रतिबंधित कर दिया है तो मुझे इसे सब कुछ करना है, या नहीं?


मैंने ATmega328p लिए लक्षित एक साधारण कमांड भाषा के लिए एक पार्सर लागू किया है। इस चिप में 32k रॉम और केवल 2k रैम है। राम निश्चित रूप से अधिक महत्वपूर्ण सीमा है - यदि आप अभी तक किसी विशेष चिप से बंधे नहीं हैं, तो जितना संभव हो उतना रैम चुनें। यह आपके जीवन को अधिक आसान बना देगा।

पहले मैंने फ्लेक्स / बाइसन का उपयोग करने पर विचार किया। मैंने दो प्रमुख कारणों से इस विकल्प के खिलाफ फैसला किया:

  • डिफ़ॉल्ट रूप से, फ्लेक्स और बायसन कुछ मानक लाइब्रेरी फ़ंक्शंस (विशेष रूप से I / O) पर निर्भर करते हैं जो उपलब्ध नहीं हैं या avr-libc में समान नहीं हैं। मुझे पूरा यकीन है कि समर्थित वर्कअराउंड हैं, लेकिन यह कुछ अतिरिक्त प्रयास है जिसे आपको ध्यान में रखना होगा।
  • एवीआर में हार्वर्ड आर्किटेक्चर है । सी को इसके लिए खाते में डिज़ाइन नहीं किया गया है, इसलिए डिफ़ॉल्ट रूप से निरंतर चर को रैम में भी लोड किया जाता हैflash और EEPROM में डेटा स्टोर और एक्सेस करने के लिए आपको विशेष मैक्रोज़ / फ़ंक्शंस का उपयोग करना होगा। फ्लेक्स और बाइसन कुछ अपेक्षाकृत बड़ी लुकअप टेबल बनाते हैं, और ये आपकी रैम को बहुत तेज़ी से खाएंगे। जब तक मैं गलत नहीं हूं (जो काफी संभव है) आपको विशेष फ्लैश और ईईपीरोम इंटरफेस का लाभ उठाने के लिए आउटपुट स्रोत को संपादित करना होगा।

फ्लेक्स और बाइसन को खारिज करने के बाद, मैं अन्य जेनरेटर टूल्स की तलाश में गया। यहां कुछ ऐसे हैं जिन्हें मैंने माना:

आप विकिपीडिया की तुलना को भी देखना चाहेंगे।

आखिरकार, मैंने लेक्सर और पार्सर दोनों को कोडिंग कर दिया।

पार्सिंग के लिए मैंने एक रिकर्सिव वंश पार्सर का इस्तेमाल किया। मुझे लगता है कि ईरा बैक्सटर ने पहले से ही इस विषय को कवर करने के लिए पर्याप्त काम किया है, और ऑनलाइन ट्यूटोरियल हैं।

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

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


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


आप उस कोड को उत्पन्न करने के लिए लिनक्स पर अपने मूल जीसीसी के साथ फ्लेक्स / बाइसन का उपयोग कर सकते हैं जिसे आप एम्बेडेड लक्ष्य के लिए अपने एवीआर जीसीसी के साथ क्रॉस-कंपाइल करेंगे।


पहिया का पुन: आविष्कार करने के बजाय, LUA पर एक नज़र डालें : www.lua.org । यह एक व्याख्यात्मक भाषा है जिसे अन्य सॉफ़्टवेयर में एम्बेड किया जाना है और एम्बेडेड सिस्टम जैसे छोटे पैमाने पर सिस्टम पर उपयोग किया जाता है। बिल्ट-इन प्रक्रियात्मक सिंटैक्स पार्सिंग पेड़, नियंत्रण तर्क, गणित और परिवर्तनीय समर्थन - किसी चीज को फिर से शुरू करने की आवश्यकता नहीं है कि हजारों अन्य पहले ही डीबग और इस्तेमाल हो चुके हैं। और यह एक्स्टेंसिबल है, जिसका अर्थ है कि आप अपने स्वयं के सी कार्यों को जोड़कर व्याकरण में जोड़ सकते हैं।


यदि आप पार्सर्स को कोड करने का एक आसान तरीका चाहते हैं, या आप अंतरिक्ष पर तंग हैं, तो आपको एक रिकर्सिव वंश पार्सर को कोड-कोड करना चाहिए; ये अनिवार्य रूप से एलएल (1) पार्सर्स हैं। यह उन भाषाओं के लिए विशेष रूप से प्रभावी है जो मूल के रूप में "सरल" हैं। (मैंने 70 के दशक में इनमें से कई को वापस किया था!)। अच्छी खबर यह है कि इनमें कोई लाइब्रेरी कोड नहीं है; बस आप क्या लिखते हैं।

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

फिर यदि आपके पास फॉर्म का बीएनएफ नियम है:

 X = A B C ;

नियम (एक्स, ए, बी, सी) में प्रत्येक आइटम के लिए एक सबराउटिन बनाएं जो एक बुलियन कहता है "मैंने इसी वाक्यविन्यास निर्माण को देखा"। एक्स के लिए, कोड:

subroutine X()
     if ~(A()) return false;
     if ~(B()) { error(); return false; }
     if ~(C()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end X;

इसी प्रकार ए, बी, सी के लिए

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

यदि आपका बीएनएफ नियम रिकर्सिव है ... चिंता न करें। बस रिकर्सिव कॉल कोड। यह व्याकरण नियमों को संभालता है जैसे:

T  =  '('  T  ')' ;

इसे कोड किया जा सकता है:

subroutine T()
     if ~(left_paren()) return false;
     if ~(T()) { error(); return false; }
     if ~(right_paren()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end T;

यदि आपके पास वैकल्पिक विकल्प के साथ बीएनएफ नियम है:

 P = Q | R ;

फिर वैकल्पिक विकल्प के साथ कोड पी:

subroutine P()
    if ~(Q)
        {if ~(R) return false;
         return true;
        }
    return true;
end P;

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

L  =  A |  L A ;

आप इसे इस प्रकार कोड कर सकते हैं:

subroutine L()
    if ~(A()) then return false;
    while (A()) do // loop
    return true;
end L;

आप इस तरह एक या दो दिनों में कई सौ व्याकरण नियमों को कोड कर सकते हैं। भरने के लिए और विवरण हैं, लेकिन यहां मूल बातें पर्याप्त से अधिक होनी चाहिए।

यदि आप अंतरिक्ष पर वास्तव में तंग हैं, तो आप एक आभासी मशीन बना सकते हैं जो इन विचारों को लागू करता है। यही वह है जो मैंने 70 के दशक में किया था, जब 8 के 16 बिट शब्द आप प्राप्त कर सकते थे।

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

अगस्त 2014:

मुझे "एक पार्सर के साथ एएसटी बनाने के लिए" के लिए बहुत से अनुरोध मिलते हैं। इस पर ब्योरे के लिए, जो अनिवार्य रूप से इस उत्तर को विस्तृत करता है, मेरा अन्य SO उत्तर https://.com/a/25106688/120163

जुलाई 2015:

बहुत सारे लोग हैं जो एक साधारण अभिव्यक्ति मूल्यांकनकर्ता लिखना चाहते हैं। आप ऐसा ही कर सकते हैं जो उपरोक्त "एएसटी बिल्डर" लिंक सुझाता है; बस पेड़ नोड्स बनाने के बजाय अंकगणित करें। यहां एक अभिव्यक्ति मूल्यांकनकर्ता इस तरह से किया गया है ।





avr-gcc