2015-05-22 7 views
10

मैंने Regular Expression Matching: the Virtual Machine Approach पढ़ा और अब मैं नियमित अभिव्यक्ति को पार्स करने और उससे वर्चुअल मशीन बनाने की कोशिश करता हूं। टोकनाइज़र काम करता है और इसके टोकन बनाता है। उस चरण के बाद, मैं टोकन धारा से उलट पॉलिश अंकन बनाने तो अंत में मैं नियमित अभिव्यक्ति a|(b|c) सेनियमित अभिव्यक्ति से वर्चुअल मशीन

a b c | | 

मिलता है। खैर, अब कदम मैं कहाँ अटक: मैं एक सरणी

0: split 1, 3 
1: match 'a' 
2: jump 7 
3: split 4, 6 
4: match 'b' 
5: jump 7 
6: match 'c' 
7: noop 
ऊपर धारा से

प्राप्त करना चाहते हैं। और मुझे यह सही नहीं मिला ... मैं एक आउटपुट सरणी और प्रत्येक टोकन की प्रारंभिक स्थिति के लिए एक ढेर का उपयोग करता हूं। सबसे पहले, आउटपुट में 3 मान जोड़े जाते हैं (और यह स्टैक पर प्रारंभिक स्थिति है)।

output    stack 
------------------- ------ 
0: match 'a'  0: 0 
1: match 'b'  1: 1 
2: match 'c'  2: 2 

| के साथ, मैं ढेर से पिछले 2 पदों पॉप और split और jump विशिष्ट पदों पर डालें। मानों की गणना वर्तमान स्टैक लंबाई और मेरे द्वारा जोड़े गए तत्वों की मात्रा के आधार पर की जाती है। अंत में, मैं स्टैक पर अंतिम तत्व की नई स्टार्ट-स्थिति जोड़ता हूं (इस मामले में वही रहता है)।

output    stack 
------------------- ------ 
0: match 'a'  0: 0 
1: split 2, 4  1: 1 
2: match 'b' 
3: jump 5 
4: match 'c' 

यह ठीक लगता है। अब, अगले | पॉप है ...

output    stack 
------------------- ------ 
0: split 1, 3  0: 0 
1: match 'a' 
2: jump 7 
3: split 2, 4 
4: match 'b' 
5: jump 5 
6: match 'c' 

और यहाँ समस्या है। मुझे उन सभी पतों को अपडेट करना होगा जिन्हें मैंने पहले गणना की थी (लाइन 3 और 5)। यही वह नहीं है जो मैं चाहता हूं। मुझे लगता है, सापेक्ष पते में एक ही समस्या है (कम से कम यदि मान नकारात्मक हैं)।

तो मेरा सवाल यह है कि रेगेक्स से वीएम कैसे बनाएं। क्या मैं सही रास्ते पर हूं (आरपीएन-फॉर्म के साथ) या क्या कोई और (या/या आसान) तरीका है?

आउटपुट सरणी को एक पूर्णांक सरणी के रूप में संग्रहीत किया जाता है। split -command तथ्य 3 प्रविष्टियों में की जरूरत है, jump दो, ...

+1

एक regex-आभासी मशीन टैग और अधिक सटीक होगा – 1010

+0

मैं एक बहुत ही इसी तरह की परियोजना है और मैं आपको लगता है नहीं है पुनर्मूल्यांकन के बिना एक मौका है। यदि आप पेड़ की संरचना के बारे में सोचते हैं, तो आप 'स्प्लिट' आउटपुट के साथ '| '-node शुरू कर सकते हैं, पहले बच्चे को संसाधित कर सकते हैं,' कूद 'आउटपुट कर सकते हैं, दूसरे बच्चे को संसाधित कर सकते हैं और लौटने के बाद, पते को अपडेट कर सकते हैं 'विभाजन' और 'कूद'। यह एक पेड़ के भीतर आसान है - लेकिन यह अभी भी पुनर्मूल्यांकन है। –

उत्तर

0

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

+0

यह काम कर सकता है - लेकिन मुझे वास्तव में इसका विचार पसंद नहीं है ...;) कृपया मुझे गलत न करें। उत्तर देने के लिए धन्यवाद - मुझे उम्मीद है कि एक और, प्रत्यक्ष तरीका –

0

आरपीएन आपको आवश्यक आउटपुट बनाने का सबसे अच्छा तरीका नहीं है। यदि आपने इसके बजाय एएसटी बनाया है, तो कोड को रिकर्सिव ट्रैवर्सल के साथ उत्पन्न करना आसान होगा।

मान लें कि आपके पास एक OR नोड था, उदाहरण के लिए, दो बच्चों के साथ "बाएं" और "दाएं"। प्रत्येक नोड के लिए एक विधि generate(OutputBuffer), और एक या नोड के लिए कार्यान्वयन को लागू करता है इस प्रकार दिखाई देगा:

void generate(OutputBuffer out) 
{ 
int splitpos = out.length(); 
out.append(SPLIT); 
out.append(splitpos+3); //L1 
out.append(0); //reservation 1 
//L1 
left.generate(out); 
int jumppos = out.length(); 
out.append("JUMP"); 
out.append(0); //reservation 2 
//L2 
out.set(splitpos+2, out.length()); //reservation 1 = L2 
right.generate(out); 
//L3 
out.set(jumppos+1, out.length()); //reservation 2 = L3 
} 
+0

ओह ... मैंने अभी देखा है कि यह प्रश्न 6 महीने पुराना है! मुझे उम्मीद है कि आपने इसे पहले किसी भी तरह से समझ लिया था। मेरे पास एक ओपन सोर्स प्रोजेक्ट है जो डीएफए विधि लागू करता है। मैं व्यक्तिगत रूप से सोचता हूं कि रास्ता बहुत कूलर है, लेकिन इन सभी regex कार्यान्वयन बहुत मजेदार हैं –

संबंधित मुद्दे