एक व्याकरण एलएल बनाना (1)

Question

मेरे पास निम्नलिखित व्याकरण है:

एस → एस एस बी एस | बी एस एस एस | ε

चूंकि मैं इसके लिए एक छोटा संकलक लिखने की कोशिश कर रहा हूं, इसलिए मैं इसे एलएल (1) बनाना चाहता हूं। मैं देखता हूं कि यहां पहला/अनुसरण संघर्ष होता है, और मुझे पता है कि मुझे इसे हल करने के लिए प्रतिस्थापन का उपयोग करना है, लेकिन मुझे बिल्कुल यकीन नहीं है कि इसके बारे में कैसे जाना है। यहां मेरा प्रस्तावित व्याकरण है, लेकिन मुझे यकीन नहीं है कि यह सही है:

एस-> एएसबीटी | epsilon

टी-> बीएफएएफ | एप्सिलॉन

F-> एप्सिलॉन

किसी को बाहर करने में मदद कर सकते हैं?

Answer 1

उसकी original paper on LR parsing में, नुथ इस भाषा है, जिसमें उन्होंने conjectures "इस भाषा के लिए छोटा संभव स्पष्ट व्याकरण है:" के लिए निम्नलिखित व्याकरण देता

एस → और एप्सिलॉन; | एएबीएस | बीबीएएस

ए → और ईपीएसलॉन; | एएबीए

बी → और ईपीएसलॉन; | बीबीएबी

सहजता से, यह एएस और बीएस की किसी भी स्ट्रिंग को पूरी तरह से संतुलित करने वाले ब्लॉक में तोड़ने की कोशिश करता है। कुछ ब्लॉक बी के साथ शुरू होते हैं और अंत में होते हैं, जबकि अन्य बी के साथ शुरू होते हैं और एक के साथ समाप्त होते हैं।

हम पहले की गणना और सेट का पालन करें इस प्रकार कर सकते हैं:

पहले (एस) = {& एप्सिलॉन ;, a, b}

पहले (ए) = {& एप्सिलॉन ;, एक}

पहले (बी) = {और एप्सिलॉन ;, b}

का पालन करें (एस) = {$}

का पालन करें (ए) = {b}

0,123,

का पालन करें (बी) = {a}

इस आधार पर, हम मिल निम्नलिखित डालूँगा (1) पार्स तालिका:

| a | b | $ 
--+-------+-------+------- 
S | aAbS | bBaS | e 
A | aAbA | e | 
B | e | bBaB | 

और इसलिए इस व्याकरण है न केवल एलआर (1) , लेकिन यह एलएल (1) भी है।

आशा है कि इससे मदद मिलती है!