मैं एक सत्य तालिका जेनरेटर कैसे बना सकता हूं?

Question

मैं एक व्यक्तिगत परियोजना के रूप में एक सत्य तालिका जेनरेटर लिखना चाहता हूं।

कई वेब-आधारित ऑनलाइन here और here हैं।

(Example screenshot of an existing Truth Table Generator)

मैं निम्नलिखित प्रश्न हैं:

• मैं कैसे की तरह भाव पार्स करने के बारे में जाना चाहिए: ((पी => क्यू) & (क्यू => आर)) => (पी => आर)
• क्या मुझे एंटलर या वाईएसीसी जैसे पार्सर जनरेटर का उपयोग करना चाहिए, या सीधे नियमित अभिव्यक्तियों का उपयोग करना चाहिए?
• एक बार मेरे पास अभिव्यक्ति पार्स हो जाने के बाद, मुझे सत्य तालिका बनाने के बारे में कैसे जाना चाहिए? अभिव्यक्ति के प्रत्येक खंड को अपने सबसे छोटे घटकों में विभाजित करने और तालिका के बाईं ओर से दाएं से निर्मित करने की आवश्यकता है। मैं इस तरह का कुछ मूल्यांकन कैसे करूं?

क्या कोई मुझे इन मनमाने ढंग से अभिव्यक्तियों के विश्लेषण के बारे में सुझाव दे सकता है और आखिरकार पारदर्शी अभिव्यक्ति का मूल्यांकन कर सकता है?

Answer 1

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

इस तरह के सिस्टम काम करने का तरीका औपचारिकरण है कि हम प्राकृतिक भाषाओं को कैसे समझते हैं। अगर मैं आपको एक वाक्य देता हूं: "कुत्ते, रोवर ने अपना खाना खा लिया।", सबसे पहले आप इसे शब्दों और विराम चिह्न में तोड़ देते हैं। "द", "स्पेस", "कुत्ता", "कॉम्मा", "स्पेस", "रोवर", ... यह "टोकनिंग" या "लेक्सिंग" है।

अगली चीज आप टोकन स्ट्रीम का विश्लेषण करने के लिए करते हैं यह देखने के लिए कि वाक्य व्याकरणिक है या नहीं। अंग्रेजी का व्याकरण बेहद जटिल है, लेकिन यह वाक्य बहुत सरल है। विषय-appositive-क्रिया-वस्तु। यह "पार्सिंग" है।

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

कंपाइलर्स के पास चौथा चरण होता है जो मनुष्य नहीं करते हैं, जो वे भाषा उत्पन्न करते हैं जो भाषा में वर्णित कार्यों का प्रतिनिधित्व करते हैं।

तो, यह सब करें। अपनी भाषा के टोकन को परिभाषित करके शुरू करें, बेस क्लास टोकन को परिभाषित करें और प्रत्येक के लिए व्युत्पन्न कक्षाओं का एक समूह परिभाषित करें। (आइडेंटिफायर टोकन, ऑर्टोकन, एंड टोकन, इम्प्लाइज टोकन, राइटपेरन टोकन ...)। फिर एक विधि लिखें जो एक स्ट्रिंग लेती है और एक आईनेमरेबल 'देता है। यह तुम्हारा लेक्सर है।

दूसरा, पता लगाएं कि आपकी भाषा का व्याकरण क्या है, और एक पुनरावर्ती मूल पार्सर लिखना जो एक अमूर्त वाक्य को एक अमूर्त वाक्यविन्यास पेड़ में तोड़ देता है जो आपकी भाषा में व्याकरणिक संस्थाओं का प्रतिनिधित्व करता है।

फिर उस विश्लेषक को लिखें जो उस पेड़ और आंकड़ों को देखता है, जैसे "मेरे पास कितने अलग-अलग मुक्त चर हैं?"

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

शुभकामनाएं!

Answer 2

मुझे लगता है कि एक पार्सर जनरेटर एक ओवरकिल है। आप इस समस्या को हल करने के लिए एक अभिव्यक्ति को पोस्टफिक्स और evaluating postfix expressions (या सीधे इन्फिक्स अभिव्यक्ति से अभिव्यक्ति वृक्ष का निर्माण करने और सत्य तालिका उत्पन्न करने के लिए) का उपयोग करने के विचार का उपयोग कर सकते हैं।

Answer 3

जैसा कि मेहदद का उल्लेख है कि आप एक ही समय में पार्सिंग को रोल करने में सक्षम होना चाहिए क्योंकि यह एक लेक्सर/पार्सर के सिंटैक्स को सीखने के लिए ले जाएगा। अंतिम परिणाम जो आप चाहते हैं वह अभिव्यक्ति का कुछ सार सिंटेक्स ट्री (एएसटी) है जो आपको दिया गया है।

आपको फिर कुछ इनपुट जनरेटर बनाने की आवश्यकता है जो अभिव्यक्ति में परिभाषित प्रतीकों के लिए इनपुट संयोजन बनाता है।

फिर इनपुट इनपुट में फिर से शुरू करें, प्रत्येक इनपुट कॉम्बो के परिणाम उत्पन्न करें, नियमों (एएसटी) को पहले चरण में पार्स किया गया है।

मैं इसे कैसे करना होगा:

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

Answer 4

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

लेकिन बूलियन अभिव्यक्तियों के लिए हाथ से एक रिकर्सिव-मूल पार्सर बनाना आसान है, जो अभिव्यक्ति को "मूल्यांकन" के परिणामों की गणना करता है और देता है। इस तरह के एक पार्सर को अद्वितीय चर की संख्या निर्धारित करने के लिए पहले पास पर उपयोग किया जा सकता है, जहां "मूल्यांकन" का अर्थ है "प्रत्येक नए चर नाम के लिए कुंट 1"। एन चर के लिए सभी संभावित सत्य मानों का उत्पादन करने के लिए जेनरेटर लिखना तुच्छ है; मूल्यों के प्रत्येक सेट के लिए, बस पार्सर को फिर से कॉल करें और अभिव्यक्ति का मूल्यांकन करने के लिए इसका उपयोग करें, जहां मूल्यांकन का अर्थ है "ऑपरेटर के अनुसार उप-अभिव्यक्तियों के मानों को गठबंधन करें"।

formula = disjunction ; 
disjunction = conjunction 
       | disjunction "or" conjunction ; 
conjunction = term 
       | conjunction "and" term ; 
term = variable 
     | "not" term 
     | "(" formula ")" ; 

तुम्हारा और अधिक जटिल हो सकता है लेकिन बूलियन अभिव्यक्ति के लिए यह है कि और अधिक जटिल नहीं किया जा सकता:

आप एक व्याकरण की जरूरत है।

प्रत्येक व्याकरण नियम के लिए, लिखने 1 सबरूटीन स्ट्रिंग में एक वैश्विक "स्कैन" सूचकांक का उपयोग करता है को पार्स किया जाता:

int disjunction() 
// returns "-1"==> "not a disjunction" 
// in mode 1: 
// returns "0" if disjunction is false 
// return "1" if disjunction is true 
{ skipblanks(); // advance scan past blanks (duh) 
    temp1=conjunction(); 
    if (temp1==-1) return -1; // syntax error 
    while (true) 
    { skipblanks(); 
     if (matchinput("or")==false) return temp1; 
     temp2= conjunction(); 
     if (temp2==-1) return temp1; 
     temp1=temp1 or temp2; 
    } 
    end 

    int term() 
    { skipblanks(); 
    if (inputmatchesvariablename()) 
     { variablename = getvariablenamefrominput(); 
     if unique(variablename) then += numberofvariables; 
     return lookupvariablename(variablename); // get truthtable value for name 
     } 
    ... 
    } 

अपने पार्स दिनचर्या में से प्रत्येक इस जटिल के बारे में हो जाएगा। गंभीरता से।

Answer 5

आप http://code.google.com/p/pyttgen/source/browse/#hg/src पर पिटजेन प्रोग्राम का स्रोत कोड प्राप्त कर सकते हैं यह तार्किक अभिव्यक्तियों के लिए सत्य तालिकाओं को उत्पन्न करता है।प्लाई लाइब्रेरी पर आधारित कोड, इसलिए यह बहुत आसान है :)