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




embedded bison (4)

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

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

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


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


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


यदि आप पार्सर्स को कोड करने का एक आसान तरीका चाहते हैं, या आप अंतरिक्ष पर तंग हैं, तो आपको एक रिकर्सिव वंश पार्सर को कोड-कोड करना चाहिए; ये अनिवार्य रूप से एलएल (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