पार्स पेड़ और व्युत्पन्न पेड़ों के बीच कोई अंतर?

Question

शब्द एएसटी (सार सिंटेक्स ट्री), पार्स पेड़ और व्युत्पन्न पेड़ विभिन्न व्याकरणों के बारे में बताते हैं जब व्याकरण के अनुरूप वर्णित पाठों के परिणाम का जिक्र करते हैं। मान लीजिए कि हम कंप्यूटर भाषाओं को पार्स करने के बारे में बात कर रहे हैं, क्या उनके मतभेद इतने मिनट हैं कि हम इन शर्तों का एक-दूसरे से उपयोग कर सकते हैं? यदि नहीं, तो हम शब्दों का सही तरीके से उपयोग कैसे करते हैं?

Answer 1

AFAIK, "व्युत्पन्न वृक्ष" और "पार्स पेड़" समान हैं।

Abstract syntax tree

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

Parse tree

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

उदाहरण के लिए स्रोत a = (1 + 2) * 3; लें। पार्स पेड़ दिखाई देगा:

ASSIGNMENT 
/ \ 
a expression 
    / \ 
expression * 
    |  \ 
    +   3 
    /\ 
    1 2 

Answer 2

पार्स/व्युत्पत्ति/कंक्रीट वाक्य रचना के पेड़ इसी अवधारणा के लिए सभी समानार्थक शब्द हैं:

ASSIGNMENT 
// |  \ 
// |  \ 
a = expression ; 
    / \ 
expression \ 
/| \  \ 
    ( + )  * 
    /\  \ 
    1 2  3 

जबकि सार वाक्य रचना पेड़ की तरह लग सकता है।

ऐसे पेड़ आमतौर पर केवल सिद्धांत चर्चाओं में उपयोग किए जाते हैं, क्योंकि उनमें बहुत सारे विवरण होते हैं जो लैंगेज प्रसंस्करण करने के लिए अनावश्यक लगते हैं; एक अभिव्यक्ति वृक्ष में, क्या आपको वास्तव में "(" और प्रतिनिधित्व करने के लिए किसी अन्य "का प्रतिनिधित्व करने के लिए नोड की आवश्यकता है?

"अमूर्त वाक्यविन्यास" पेड़ की धारणा वह है जो प्रोग्राम संरचना को उस स्तर के विस्तार से दर्शाती है जो अभ्यास में प्रसंस्करण के लिए पर्याप्त है; आपको आमतौर पर "(...)" के लिए नोड्स नहीं मिलते हैं।

एक दिलचस्प सवाल: सीएसटी से सीधे एएसटी का आकलन योग्य है? जवाब हाँ होना चाहिए, लेकिन लोग शायद ही कभी ऐसा करते हैं। वे क्या करते हैं "पार्सर रन के रूप में" अमूर्त वाक्यविन्यास "नोड्स का निर्माण करते हैं, और माता-पिता के लिए एक गोंद नोड के साथ बाल पार्स से नोड्स को इकट्ठा करने के लिए विज्ञापन (नियम कमी प्रक्रिया प्रक्रियात्मक लगाव) का उपयोग करते हैं। आईएमएचओ, वे ऐसा इसलिए करते हैं क्योंकि हम सभी को वाईएसीसी पर लाया गया है, और इसी तरह पारंपरिक रूप से किया जाता है। (हम भी फ्लिंट के साथ आग को हल्का करते थे।) एक कम बहाना है; ऐसा करने से इस प्रकार संकलक-निर्माता एएसटी की संरचना का पूरा नियंत्रण देता है और वह अतिरिक्त उत्पादन के मामले में बहुत कम है जो उत्पादन कर सकता है। इस तरह का एक विज्ञापन-पेड़ सीएसटी से गणना योग्य नहीं है, इसके अलावा पार्सर क्रियाओं में एम्बेडेड एक ही विज्ञापन-गणना गणना के अलावा।

मैंने एक अलग दृष्टिकोण का उपयोग किया है: my tools सीधे सीएसटी से एएसटी की गणना करें, सचमुच अप्रासंगिक विवरण छोड़कर, उदाहरण के लिए, गैर-मूल्य वाले टोकन (उदा।, उन व्यर्थ '(' ')' टोकन के साथ-साथ कीवर्ड), यूनरी प्रस्तुतियों के तारों को संपीड़ित करना, और वास्तविक सूची नोड्स में सूचियों के बराबर-बाएं-झुकाव वाले पेड़ों को परिवर्तित करना। ऐसा करने का लाभ यह है कि पार्सर सीधे व्याकरण नियमों से एएसटी की गणना कर सकता है। प्रक्रियात्मक अनुलग्नकों के साथ चारों ओर झुकाव नहीं। कोई गलत नहीं हो रहा है। इस तथ्य के बारे में कोई और चिंता नहीं कि our COBOL grammar में 3500 नियम हैं और मुझे अन्यथा उनमें से प्रत्येक के लिए प्रक्रियात्मक गुओ की आवश्यकता होगी, और मुझे हर बार गुओ के साथ सही और बेवकूफ़ बनाने के लिए मुझे अपने व्याकरण को सैकड़ों बार बदलना होगा। और हमारे उपकरण काम करते हैं जैसे कि वे सीधे सीएसटी पर काम करते हैं, जिससे पेड़ में हेरफेर के बारे में सोचना आसान हो जाता है, खासकर अगर आप व्याकरण नियमों पर सीधे देख रहे हैं। (यह सतह सिंटैक्स का उपयोग करके पैटर्न मिलान को बहुत आसान बनाता है: किसी भी पैटर्न के टुकड़े के लिए, एक सीधे कम्प्यूटेबल एएसटी है जो अनुरूप है)।

तो एएसटी और सीएसटी के बीच भेद उपयोगिता के मामले में वास्तविक है। लेकिन मुझे लगता है कि उन्हें सिर्फ आइसोमोर्फिक प्रस्तुतियों के रूप में माना जाना चाहिए।

Answer 3

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

ए व्युत्पन्न पेड़ बिल्कुल वही आकार होगा, लेकिन किसी दिए गए उत्पादन से अनुक्रम प्राप्त करने की प्रक्रिया द्वारा उत्पादित किया जाएगा।

है को पार्स दिए गए इनपुट अनुक्रम के लिए एक व्युत्पत्ति पाने की औपचारिक परिभाषा है, तो कोई आश्चर्य नहीं व्युत्पत्ति और पार्स पेड़ ही हैं।

कंक्रीटबनाम सार वाक्य रचना के पेड़ है कि पूर्व, इनपुट क्रम में प्रत्येक टोकन के लिए एक पत्ता नोड है जबकि बाद किसी भी टोकन कि व्याकरण का निरीक्षण से जाना जा सकता है को छोड़ देता है में मतभेद है। if <expr> then <statement> else <statement> end के लिए एक ठोस वाक्य रचना सबट्री अंतअगर के लिए लीफ़्स होगा, तो, बाकी , और , और अमूर्त एक नहीं होगा। (2+3) के लिए ठोस वाक्य रचना पेड़ होगा:

e 
    | 
(e) 
/|\   
| | | 
n + n 

सार एक होगा बस:

+ 
| | 
n n