अधिकतम-मंच कैसे कार्यान्वित किया जाता है?

Question

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

हालांकि, मेरा प्रश्न है, अधिकतम-मंच नियम लागू किया गया है? आंतरिक रूप से, लेक्सर सबसे लंबे समय तक संभव लेक्सम खोजने के लिए "जारी रखने" के बारे में कैसे जानता है?

धन्यवाद! प्रभाव में, tell() और seek() जैसे कार्यों के साथ उपलब्ध कराने के:

Answer 1

अधिक से अधिक मंच एल्गोरिथ्म DFA निष्पादक को परिवर्तनशील राज्य की एक छोटी राशि जोड़ने, और DFA निष्पादक की क्षमता "रिवाइंड" के लिए इनपुट जोड़कर कार्यान्वित किया जाता है।

यह भी ध्यान देने योग्य है कि डीएफए पूरा नहीं हुआ है, इस अर्थ में कि संक्रमण कार्य पूरा नहीं हुआ है। कुछ {state, input} जोड़े के पास परिभाषित परिणाम नहीं है। [नोट 2]

इसे ध्यान में रखते

, एल्गोरिथ्म इस प्रकार है के रूप में:

Set Accepted NFA State to ⊥ 
Set Accepted Position to Tell(Input Stream) 
Set State to Starting State 
Repeat: 
    If State ∈ Accepting: 
    Set Accepted NFA State to Accepting NFA State for State [Note 1] 
    Set Accepted Position to Tell(Input Stream) 
    Read one symbol from Input Stream into Next Symbol 
    If there is a transition from {State, Next Symbol} to New State: 
    Set State to New State 
    Continue the loop 
    Otherwise: 
    Rewind Input Stream to Accepted Position 
    Return Accepted NFA State 

एल्गोरिथ्म रिटर्न और नीचे ;, फिर कोई टोकन मान्यता दी गई थी और इनपुट धारा प्रारंभिक स्थिति को rewound किया गया होगा तो ।

---

नोट्स:

1. NFA आम तौर पर राज्यों और स्वीकार करने क्रियाओं के बीच एक स्पष्ट समरूपता है, लेकिन DFA निर्माण एल्गोरिथ्म विभिन्न कार्यों के साथ दो को स्वीकार NFA राज्यों में सम्मिलित कर सकते। इस मामले में, फ्लेक्स एल्गोरिदम इनपुट फ़ाइल में पहली क्रिया को प्राथमिकता देना है। उपर्युक्त एल्गोरिदम में, हम प्रत्येक स्वीकार्य डीएफए राज्य को एनएफए राज्य को स्वीकार करने वाले घटक को मैप करके इसका प्रतिनिधित्व करते हैं, जिसकी प्राथमिकता है।

2. अतिरिक्त (और अद्वितीय) sink राज्य जोड़कर डीएफए को पूरा करना आसान है जो गैर स्वीकार्य है और जिसमें केवल स्वयं ही संक्रमण हैं। फिर हम किसी भी अन्य अनिर्दिष्ट संक्रमण के लिए sink स्थिति को एक संक्रमण के रूप में जोड़ सकते हैं। अगर हम sink राज्य और नीचे कॉल करते हैं; तो यह स्पष्ट होगा कि प्रदान किए गए एल्गोरिदम को कैसे संशोधित किया जाए; व्यावहारिक रूप से, यह बिल्कुल जरूरी नहीं है क्योंकि अभ्यास में हमें परवाह नहीं है कि डीएफए अपूर्ण है। हालांकि, राज्य न्यूनीकरण एल्गोरिदम पर इसका कुछ प्रभाव पड़ता है।