एलएएलआर पार्सर जेनरेटर कार्यान्वयन समस्या

Question

मैं वर्तमान में "कंपाइलर सिद्धांत तकनीकों और औजारों" (जिसे "ड्रैगन बुक" भी कहा जाता है) में वर्णित एलएएलआर पार्सर जनरेटर को लागू करने की कोशिश कर रहा हूं।

बहुत पहले से ही काम करता है। पार्सर जनरेटर वर्तमान में पूर्ण गोटो-ग्राफ उत्पन्न करने में सक्षम है।

Example Grammar: 
        S' --> S 
        S --> C C 
        C --> c C 
        C --> d 

Nonterminals: S', S, C 
Terminals: c, d 
Start: S' 

गोटो-ग्राफ:

I[0]---------------+  I[1]-------------+ 
| S' --> . S , $ |--S-->| S' --> S . , $ | 
| S --> . C C , $ |  +----------------+ 
| C --> . c C , c | 
| C --> . c C , d |  I[2]--------------+ 
| C --> . d , c |  | S --> C . C , $ |  I[3]--------------+ 
| C --> . d , d |--C-->| C --> . c C , $ |--C-->| S --> C C . , $ | 
+------------------+  | C --> . d , $ |  +-----------------+ 
    | |     +-----------------+ 
    | |   +--c--+ |  | 
    | |   |  | c  | 
    | |   |  v v  | 
    | |  I[4]--------------+ | 
    | c  | C --> c . C , c | | 
    | |  | C --> c . C , d | | 
    | |  | C --> c . C , $ | d 
    | |  | C --> . c C , c | | 
    | +---->| C --> . c C , d | | 
    |  | C --> . c C , $ | | 
    d  | C --> . d , c |--+ | 
    | +-----| C --> . d , d | | | 
    | |  | C --> . d , $ | | | 
    | |  +-----------------+ | | 
    | C       | | 
    | |  I[6]--------------+ | | 
    | |  | C --> c C . , c | d | 
    | +---->| C --> c C . , d | | | 
    |  | C --> c C . , $ | | | 
    |  +-----------------+ | | 
    |        | | 
    |  I[5]------------+ | | 
    |  | C --> d . , c |<---+ | 
    +------->| C --> d . , d |  | 
      | C --> d . , $ |<-----+ 
      +---------------+ 

मैं एल्गोरिथ्म को लागू करने के कार्यों की मेज उत्पन्न करने के लिए साथ trubbles है!

state | action  
     | c | d | $ 
------------------------ 
    0 | s4 | s5 | 
------------------------ 
    1 |  |  | acc 
------------------------ 
    2 | s4 | s5 | 
------------------------ 
    3 |  |  | r? 
------------------------ 
    4 | s4 | s5 | 
------------------------ 
    5 | r? | r? | r? 
------------------------ 
    6 | r? | r? | r? 

sx ... एक्स
rx राज्य में बदलाव ... एक्स

आर राज्य को कम: मेरे एल्गोरिथ्म ने निम्न उत्पादन की गणना करता है? इसका मतलब है कि मुझे नहीं पता कि कैसे राज्य (?) प्राप्त करने के लिए जिस पर पार्सर को कम करना चाहिए। क्या किसी को पाने के लिए एल्गोरिदम पता है? ऊपर गोटो ग्राफ का उपयोग कर?

यदि कुछ भी स्पष्ट रूप से पर्याप्त वर्णन नहीं किया गया है, तो कृपया पूछें और मैं इसे बेहतर समझाऊंगा! आपकी मदद के लिए धन्यवाद!

Answer 1

एक शिफ्ट एंट्री अगले राज्य द्वारा जिम्मेदार है, लेकिन एक कम प्रविष्टि उत्पादन को इंगित करती है।

जब आप स्थानांतरित करते हैं, तो आप अपने स्टैक पर एक राज्य संदर्भ दबाते हैं और अगले राज्य में जाते हैं।

जब आप कम करते हैं, तो यह एक विशिष्ट उत्पादन के लिए होता है। उत्पादन आपके ढेर पर एन राज्यों को स्थानांतरित करने के लिए ज़िम्मेदार था, जहां एन उस उत्पादन में प्रतीकों की संख्या है। जैसे एस के लिए एक, एस के लिए दो, और सी के लिए दो या एक (यानी सी के पहले या दूसरे विकल्प के लिए)।

एन प्रविष्टियों को ढेर से पॉप अप करने के बाद, आप उस राज्य में वापस आते हैं जहां आपने उस उत्पादन को संसाधित करना शुरू किया था। उस राज्य के लिए और नतीजे उत्पादन के परिणामस्वरूप, आप अगले राज्य को खोजने के लिए गोटो टेबल को देखते हैं, जिसे तब धक्का दिया जाता है।

तो कम प्रविष्टियां उत्पादन की पहचान करती हैं। वास्तव में परिणामस्वरूप nonterminal, और पॉप करने के लिए प्रतीकों की संख्या जानने के लिए पर्याप्त हो सकता है।

आपका तालिका इस प्रकार पढ़ना चाहिए

state | action  | goto 
     | c | d | $ | C | S 
------------------------------------ 
    0 | s4 | s5 |  | 2 | 1 
------------------------------------ 
    1 |  |  | acc |  | 
------------------------------------ 
    2 | s4 | s5 |  | 3 | 
------------------------------------ 
    3 |  |  | r0 |  | 
------------------------------------ 
    4 | s4 | s5 |  |  | 6 
------------------------------------ 
    5 | r3 | r3 | r3 |  | 
------------------------------------ 
    6 | r2 | r2 | r2 |  | 

जहां rx द्वारा उत्पादन एक्स को कम इंगित करता है।

Answer 2

आपको ढेर को पॉप करने और वहां से अगले राज्य को खोजने की आवश्यकता है।

Answer 3

आरएक्स का मतलब है: संख्या x के साथ उत्पादन का उपयोग कम करें!
तब सब कुछ स्पष्ट हो जाता है! उत्पादन के शरीर को सरल पॉप करें और सिर को शीर्ष पर वापस स्थानांतरित करें!