मैंने पढ़ा है कि अधिकांश प्रोग्रामिंग भाषाओं को संदर्भ मुक्त व्याकरण (सीएफजी) के रूप में पार्स किया जा सकता है। कम्प्यूटेशनल पावर की अवधि में, यह एक पुशडाउन गैर निर्धारक automaton के बराबर है। क्या मैं सही हू?
तकनीकी रूप से हाँ। उपयोगी रूप से, नहीं।
- आप तार का एक सेट की सोच रहे हैं, तो आप एक भाषा है:
वहाँ इन सवालों के बारे में सोचने के लिए कम से कम दो उपयोगी तरीके हैं।
- यदि आप यह तय करने के लिए एल्गोरिदम के बारे में सोच रहे हैं कि कोई स्ट्रिंग भाषा में है या नहीं, तो आपके पास निर्णय समस्या है।
कठिनाई है कि जब सबसे प्रोग्रामिंग भाषाओं एक अंतर्निहित संरचना है कि आसानी से एक विषय से मुक्त व्याकरण द्वारा वर्णित है है (Tcl एक दिलचस्प अपवाद है) कई वाक्य है कि विषय से मुक्त व्याकरण द्वारा वर्णित हैं नहीं कर रहे हैं वास्तव में "भाषा में," जहां "भाषा में" मेरा मतलब है "प्रश्न में भाषा में एक वैध कार्यक्रम।" इन अतिरिक्त वाक्यों को आमतौर पर स्थैतिक अर्थशास्त्र के किसी रूप से अस्वीकार कर दिया जाता है। उदाहरण के लिए, निम्न कथन सी कार्यक्रमों के विषय से मुक्त व्याकरण में एक वाक्य है, लेकिन इसे वैध सी कार्यक्रमों के सेट में ही नहीं है:
int f(void) { return n + 1; }
समस्या है कि यहाँ n दायरे में नहीं है। सी को "उपयोग से पहले घोषणा" की आवश्यकता होती है, और उस संदर्भ को संदर्भ-मुक्त व्याकरण का उपयोग करके व्यक्त नहीं किया जा सकता है।
कोई वास्तविक प्रोग्रामिंग भाषा के लिए एक विशिष्ट निर्णय प्रक्रिया सामने अंत एक संकलक या दुभाषिए की का हिस्सा है, और यह कम से कम दो भाग हैं: एक, पार्सर, एक पुशडाउन करने का फैसला सत्ता में बराबर है आटोमैटिक मशीन; लेकिन दूसरा अतिरिक्त चेक करता है जो कई शब्दों को अमान्य मानता है। यदि इन चेकों को किसी भी तरह की परिभाषा-पहले उपयोग की जाने वाली संपत्ति की आवश्यकता होती है, तो उन्हें पुशडाउन automaton या संदर्भ-मुक्त व्याकरण द्वारा नहीं किया जा सकता है।
यदि यह सच है, तो सीएफजी एक अप्रतिबंधित व्याकरण (यूजी) कैसे रख सकता है, जो पूरा हो रहा है?
एक सीएफजी — कुछ भी "पकड़" नहीं करता है, यह बस एक भाषा का वर्णन करता है।
... भले ही प्रोग्रामिंग भाषाओं को सीएफजी द्वारा वर्णित किया गया हो, फिर भी वे वास्तव में ट्यूरिंग मशीनों का वर्णन करने के लिए उपयोग किए जाते हैं, और इसलिए यूजी के माध्यम से।
आप यहां संकेत के कुछ महत्वपूर्ण स्तरों को छोड़ रहे हैं।
मुझे लगता है कि क्योंकि कंप्यूटिंग के कम से कम दो विभिन्न स्तरों की है, पहले, जो एक CFG की पार्स है, भाषा की संरचना से संबंधित (प्रतिनिधित्व?) वाक्य रचना पर केंद्रित है, जबकि अन्य पर केंद्रित प्रोग्रामिंग भाषा की क्षमताओं से संबंधित अर्थपूर्ण (भावना, डेटा की व्याख्या?) पूरी तरह से ट्यूरिंग कर रहा है। फिर, क्या ये धारणाएं सही हैं?
वे मुझे थोड़ा उलझन में लगते हैं, लेकिन आप सही रास्ते पर हैं। एक महत्वपूर्ण सवाल यह है कि "भाषा और प्रोग्रामिंग भाषा के बीच क्या अंतर है?" जवाब यह है कि प्रोग्रामिंग भाषा में कम्प्यूटेशनल व्याख्या है। कम्प्यूटेशनल व्याख्याएं कई अच्छी किस्मों में आती हैं, और उनमें से सभी ट्यूरिंग-पूर्ण नहीं हैं। लेकिन जादू व्याख्या में है, सिंटैक्स में नहीं, इसलिए चॉम्स्की पदानुक्रम यहां बहुत प्रासंगिक नहीं है।
मेरी बात साबित करने के लिए, एक चरम उदाहरण: नियमित भाषा [1-9][0-9]* निम्नलिखित व्याख्या के तहत ट्यूरिंग-पूर्ण है:
- SK-Combinator भाषा ट्यूरिंग पूरा हो गया है।
- केवल कई एसके कार्यक्रम हैं।
- उन्हें आसानी से विशिष्ट और निश्चित रूप से समझा जा सकता है।
- इसलिए हम एक एसके प्रोग्राम के साथ प्रत्येक सकारात्मक पूर्णांक को जोड़ सकते हैं।
- यदि हम मानक तरीके से सकारात्मक पूर्णांक के रूप में अंक के अनुक्रम की व्याख्या करते हैं, तो हम एसके प्रोग्राम के रूप में अंकों के समान अनुक्रम की समान व्याख्या कर सकते हैं, और इसके अलावा, किसी भी एसके प्रोग्राम को सीमित अनुक्रम का उपयोग करके व्यक्त किया जा सकता है अंक।
इसलिए पूर्णांक अक्षर की भाषा ट्यूरिंग-पूर्ण है।
यदि आपका सिर अब चोट नहीं पहुंचाता है, तो इसे चाहिए।
बहुत सारे संक्षेप! यदि आप बिना किसी एन्कोडिंग के संवाद कर सकते हैं, तो आप कभी भी प्रभावी नहीं होंगे। –
@ डोनलफेलो, दो (2) संक्षेप हैं, और यदि आप सीएफजी से पहले से परिचित नहीं हैं, तो आप वैसे भी सवाल का जवाब देने में सक्षम नहीं होंगे। –