प्रत्यावर्तन

Question

छोड़ दिया निकालने से निम्नलिखित व्याकरण प्रत्यावर्तन

E= E+T|T 
T= T*F|F 
F= a|b|c 

छोड़ दिया है यह कैसे दूर करने के लिए? क्या इसके लिए कोई सामान्य प्रक्रिया है?

Answer 1

हां, एक सामान्य प्रक्रिया है, उदाहरण देखें। wikipedia।

E = TE' 
E'= (e) | +TE' 
T = FT' 
T'= (e) | *FT' 
F = a | b | c 

यह उल्लेखनीय है कि इस + और * की संबद्धता बाएं से दाएं बदल देता है। यही है, जहां a + b + c से पहले (a + b) + c के रूप में पार्स किया गया था, अब इसे a + (b + c) के रूप में पार्स किया गया है।

यह अतिरिक्त और गुणा के लिए कोई समस्या नहीं है, लेकिन उदाहरण के लिए, यह घटाव और विभाजन के लिए एक समस्या होगी।

विकिपीडिया लेख में बाएं-रिकर्सन हटाने की प्रक्रिया और इसकी जटिलताओं पर अधिक जानकारी है।

Answer 2

जैसा कि अन्य ने बताया है, सही रिकर्सन के साथ बाएं रिकर्सन को बदलने के लिए एक सामान्य प्रक्रिया है। अन्य उत्तरों ने दिखाया है कि दी गई व्याकरण में बाएं रिकर्सन को हटाने के लिए उस सामान्य प्रक्रिया का उपयोग कैसे करें।

यहां एक ऐसा समाधान है जो दिए गए व्याकरण को उस व्याकरण के लिए विशिष्ट तरीके से पुनर्गठन करता है।

E= T+E|T 
T= F*T|F 
F= a|b|c 

Answer 3

सामान्य प्रक्रिया Wikipedia पर मिली है, उदाहरण के लिए। मैं E = E+T|T के लिए प्रदर्शित करूंगा:

E बाएं-रिकर्सिव गैर-टर्मिनल है। +T गैर-शून्य अनुक्रम (अल्फा) है। T अनुक्रम है जो ई (बीटा) से शुरू नहीं होता है।

हम "आराम" के लिए एक नया nonterminal बनाते हैं, यानी। गैर-शून्य अनुक्रम। यह रिकर्सन को संभालता है।

E' = epsilon|+TE'

और हम प्रत्यावर्तन को संभालने के लिए नई nonterminal उपयोग करने के लिए मूल नियम को बदला।

E = TE'

Answer 4

उत्पादन

E = E+T 
    | T 
T = T*F 
    | F 
F = a|b|c 

E= T ('+' T)* 
T= F ('*' F)* 
F= a|b|c 

को जाता है एक ही प्रसंस्करण जहां मुट्ठी ई असंबद्ध A(E,T) के साथ कार्रवाई की है बनाए रखने के लिए। नया संस्करण उपयोग करता है:

ret = T1; 
while(set.more()) ret = A(ret, set.pop_front().T);