शिफ्ट-कम करें: कब कम करना बंद करें?

Question

मैं शिफ्ट-कम पार्सिंग के बारे में जानने की कोशिश कर रहा हूं। मान लीजिए कि हमें निम्नलिखित व्याकरण है, पुनरावर्ती नियम है कि आपरेशन के आदेश लागू करने, ANSI C Yacc grammar से प्रेरित का उपयोग कर:

S: A; 

P 
    : NUMBER 
    | '(' S ')' 
    ; 

M 
    : P 
    | M '*' P 
    | M '/' P 
    ; 

A 
    : M 
    | A '+' M 
    | A '-' M 
    ; 

और हम 1 + 2 पार्स करने के लिए उपयोग कर रहा पार्स पाली-को कम करना चाहते हैं। सबसे पहले, 1 को NUMBER के रूप में स्थानांतरित किया गया है। मेरा सवाल यह है कि, फिर यह पी को कम कर दिया जाता है, फिर एम, फिर ए, फिर आखिरकार एस? यह कैसे पता चलेगा कि कहां रुकना है?

मान लीजिए कि यह एस के सभी तरीकों को कम करता है, फिर '+' को बदल देता है। अब हम एक ढेर युक्त होगा:

S '+' 

हम पाली '2', में कटौती हो सकती है:

S '+' NUMBER 
S '+' P 
S '+' M 
S '+' A 
S '+' S 

अब, अंतिम पंक्ति के दोनों तरफ, एस हो सकता है पी, एम, ए, या NUMBER, और यह अभी भी इस अर्थ में मान्य होगा कि कोई भी संयोजन टेक्स्ट का सही प्रतिनिधित्व होगा। पार्सर इसे

A '+' M 

ताकि यह संपूर्ण अभिव्यक्ति को ए, फिर एस को कम कर सके? दूसरे शब्दों में, अगले टोकन को स्थानांतरित करने से पहले इसे कम करने के लिए कैसे पता चलता है? क्या यह एलआर पार्सर पीढ़ी में एक महत्वपूर्ण कठिनाई है?

---

संपादित करें: प्रश्न में नया इस प्रकार है।

अब मान लीजिए कि हम 1+2*3 पार्स करते हैं। कुछ बदलाव/कमी संचालन निम्नानुसार हैं:

Stack | Input | Operation 
---------+-------+---------------------------------------------- 
     | 1+2*3 | 
NUMBER | +2*3 | Shift 
A  | +2*3 | Reduce (looking ahead, we know to stop at A) 
A+  | 2*3 | Shift 
A+NUMBER | *3 | Shift (looking ahead, we know to stop at M) 
A+M  | *3 | Reduce (looking ahead, we know to stop at M) 

क्या यह सही है (दिया गया है, यह अभी तक पूरी तरह से विश्लेषण नहीं किया गया है)? इसके अलावा, 1 प्रतीक से दिखने से हमें A+MA को कम करने के लिए भी नहीं बताया जाता है, ऐसा करने के परिणामस्वरूप *3 पढ़ने के बाद एक अपरिहार्य वाक्यविन्यास त्रुटि होगी?

Answer 1

जिस समस्या का आप वर्णन कर रहे हैं वह LR(0) पार्सर्स बनाने के साथ एक मुद्दा है - यानी, नीचे-नीचे पार्सर्स जो वर्तमान में से परे प्रतीकों के लिए कोई भी मुखौटा नहीं करते हैं, वे पार्सिंग कर रहे हैं। आपके द्वारा वर्णित व्याकरण LR(0) व्याकरण प्रतीत नहीं होता है, यही कारण है कि आप इसे पार्स करने के लिए प्रयास करते समय परेशानी में भाग लेते हैं। यह LR(1) प्रतीत होता है, हालांकि, इनपुट में आगे 1 प्रतीक देखकर आप आसानी से निर्धारित कर सकते हैं कि शिफ्ट या कमी करना है या नहीं। इस मामले में, LR(1) पार्सर आगे देखेगा जब उसके पास 1 स्टैक पर था, तो अगला प्रतीक + है, और यह महसूस करें कि इसे पिछले A को कम नहीं करना चाहिए (क्योंकि यह एकमात्र चीज है जो इससे कम हो सकती है दूसरी स्थिति में + के साथ अभी भी एक नियम से मेल खाता है)।

LR व्याकरण की एक दिलचस्प संपत्ति है कि किसी भी व्याकरण जो k>1 के लिए LR(k) है के लिए, यह एक LR(1) व्याकरण जो बराबर है निर्माण करने के लिए संभव है। हालांकि, यह LR(0) तक सभी तरह से विस्तारित नहीं होता है - कई व्याकरण हैं जिन्हें LR(0) में परिवर्तित नहीं किया जा सकता है।

अधिक जानकारी के लिए यहाँ देखें LR(k) -नेस पर:

http://en.wikipedia.org/wiki/LR_parser

Answer 2

मैं Yacc/बाइसन पार्स एल्गोरिथ्म के बिल्कुल यकीन नहीं है और जब यह कम करने से अधिक स्थानांतरण पसंद है, तथापि मुझे लगता है कि बाइसन का समर्थन करता है पता एलआर (1) पार्सिंग जिसका अर्थ है कि इसमें एक लुकहेड टोकन है। इसका मतलब है कि टोकन तुरंत ढेर में नहीं पारित किए जाते हैं। इसके बजाय वे इंतजार करते हैं जब तक कि कोई और कमी न हो। फिर, यदि अगले टोकन को स्थानांतरित करना समझ में आता है तो यह उस ऑपरेशन को लागू करता है।

सबसे पहले, आपके मामले में, यदि आप 1 + 2 का मूल्यांकन कर रहे हैं, तो यह 1 स्थानांतरित हो जाएगा। इससे उस टोकन को ए को कम कर दिया जाएगा क्योंकि '+' लुकहेड टोकन इंगित करता है कि यह एकमात्र वैध पाठ्यक्रम है। चूंकि इसमें कोई कमी नहीं है, इसलिए यह '+' टोकन को ढेर पर बदल देगा और 2 को लुकहेड के रूप में रखेगा। यह 2 को स्थानांतरित करेगा और एम को कम करेगा क्योंकि ए + एम एक ए उत्पन्न करता है और अभिव्यक्ति पूर्ण हो जाती है।