एंटरल लेक्सर टोकन जो समान तारों से मेल खाते हैं, क्या होगा यदि लालची लेजर गलती करता है?

Question

ऐसा लगता है कि कभी-कभी एंट्लर लेक्सर एक खराब विकल्प बनाता है जिस पर नियमों की धारा को टोकन करने के लिए उपयोग करने के लिए नियम ... मैं यह समझने की कोशिश कर रहा हूं कि एंटरल को स्पष्ट-से-मानव-सही विकल्प चुनने में कैसे मदद करें। मैं इस तरह पाठ पार्स हैं:

d/dt(x)=a 
a=d/dt 
d=3 
dt=4 

यह एक दुर्भाग्यपूर्ण वाक्य रचना कि एक मौजूदा भाषा का उपयोग करता है और मैं के लिए एक पार्सर लिखने के लिए कोशिश कर रहा हूँ है। "डी/डीटी (एक्स)" एक अंतर समीकरण के बाईं ओर का प्रतिनिधित्व कर रहा है। यदि आपको जरूरी है तो लिंगो को अनदेखा करें, बस यह जान लें कि यह "डी" द्वारा विभाजित नहीं है "डीटी"। हालांकि, "डी/डीटी" की दूसरी घटना वास्तव में "डी" द्वारा विभाजित "डी" है। ।!

यहाँ मेरी व्याकरण है:

grammar diffeq_grammar; 

program : (statement? NEWLINE)*; 

statement 
    : diffeq 
    | assignment; 

diffeq : DDT ID ')' '=' ID; 

assignment 
    : ID '=' NUMBER 
    | ID '=' ID '/' ID 
    ; 

DDT : 'd/dt('; 
ID : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n'|'\r'|'\n'; 

इस व्याकरण lexer पहले "घ/डीटी (" पकड़ लेता है और टोकन डीडीटी करने के लिए इसे बदल जाता है का उपयोग करते समय बिल्कुल सही अब बाद में lexer देखता है दूसरा "डी" इसके बाद "/" और कहते हैं, "हमम, मैं इसे एक आईडी और एक '/' के रूप में मिलान कर सकता हूं या मैं लालची हो सकता हूं और डीडीटी से मेल खाता हूं।" लेक्सर लालची हो जाता है ... लेकिन यह बहुत कम जानता है, वहां है नहीं "(" कुछ धारा बाद में इनपुट स्ट्रीम में। "जब लेक्सर लापता दिखता है" ("यह एक मिस्मिटेड टोकन एक्सेप्शन फेंकता है!

एकमात्र समाधान जो मैंने पाया है, सभी नियमों को स्थानांतरित करना है एक के साथ पार्सर व्याकरण की तरह: अगर मैं पहले से ही काम कर कोड की पंक्तियों पहले व्याकरण काम कर पर निर्भर के हजारों नहीं था

grammar diffeq_grammar; 

program : (statement? NEWLINE)*; 

statement 
    : diffeq 
    | assignment; 

diffeq : ddt id ')' '=' id; 

assignment 
    : id '=' number 
    | id '=' id '/' id 
    ; 

ddt : 'd' '/' 'd' 't' '('; 
id : CHAR+; 
number : DIGIT+; 
CHAR : 'a'..'z'; 
DIGIT : '0'..'9'; 
NEWLINE : '\r\n'|'\r'|'\n'; 

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

मैं भविष्यवाणियों या अन्य चालों का उपयोग करने के साथ ठीक हूं, जब तक व्याकरण मूल रूप से वही रहता है (यानी, लेक्सर में नियम, लेक्सर में रहते हैं। और अधिकांश नियम छूटे रहते हैं।)।

आदर्श रूप से मैं डीडीटी के लिए किसी भी वैध एंटर कोड के साथ लेक्सर नियम संशोधित कर सकता हूं ... और किया जा सकता है।

मेरी लक्षित भाषा जावा है।

धन्यवाद!

अद्यतन

कुछ महान जवाब के लिए आप लोग धन्यवाद !! मैंने उस उत्तर को स्वीकार किया जो मेरे प्रश्न के अनुरूप सबसे अच्छा है। मेरे द्वारा उपयोग किया जाने वाला वास्तविक समाधान मेरे अपने उत्तर में है (स्वीकार किए गए उत्तर नहीं), और ऐसे कई उत्तर हैं जो काम कर सकते थे। पाठक, सभी उत्तरों की जांच करें; उनमें से कुछ आपके मामले से बेहतर हो सकते हैं।

Answer 1

मैं जब तक विधेय या अन्य चाल का उपयोग कर के साथ ठीक हूँ के रूप में व्याकरण मूल रूप से एक ही रहता है (जैसे कि, lexer में नियम, lexer में रहते हैं। और सबसे नियमों अछूता छोड़ दिया जाता है।)।

उस मामले में, चार-धारा में आगे देखने के लिए lexer मजबूर एक gated syntactic predicate का उपयोग कर यकीन है कि वहाँ वास्तव में "d/dt(" है बनाने के लिए।

एक डेमो:

grammar diffeq_grammar; 

@parser::members { 
    public static void main(String[] args) throws Exception { 
    String src = 
     "d/dt(x)=a\n" + 
     "a=d/dt\n" + 
     "d=3\n" + 
     "dt=4\n"; 
    diffeq_grammarLexer lexer = new diffeq_grammarLexer(new ANTLRStringStream(src)); 
    diffeq_grammarParser parser = new diffeq_grammarParser(new CommonTokenStream(lexer)); 
    parser.program(); 
    } 
} 

@lexer::members { 
    private boolean ahead(String text) { 
    for(int i = 0; i < text.length(); i++) { 
     if(input.LA(i + 1) != text.charAt(i)) { 
     return false; 
     } 
    } 
    return true; 
    } 
} 

program 
: (statement? NEWLINE)* EOF 
; 

statement 
: diffeq  {System.out.println("diffeq  : " + $text);} 
| assignment {System.out.println("assignment : " + $text);} 
; 

diffeq 
: DDT ID ')' '=' ID 
; 

assignment 
: ID '=' NUMBER 
| ID '=' ID '/' ID 
; 

DDT  : {ahead("d/dt(")}?=> 'd/dt('; 
ID  : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n' | '\r' | '\n'; 

अब आप डेमो चलाते हैं:

java -cp antlr-3.3.jar org.antlr.Tool diffeq_grammar.g 
javac -cp antlr-3.3.jar *.java 
java -cp .:antlr-3.3.jar diffeq_grammarParser

(जब Windows का उपयोग कर, पिछले आदेश में ; साथ : की जगह)

आप

निम्नलिखित आउटपुट देखेंगे:

diffeq  : d/dt(x)=a 
assignment : a=d/dt 
assignment : d=3 
assignment : dt=4

Answer 2

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

रिफैक्टरिंग सब एक विकल्प पर है, तो आप पार्सर और इस तरह lexer को बदल सकता है:

grammar diffeq_grammar; 

program : (statement? NEWLINE)* EOF; // <-- You forgot EOF 

statement 
    : diffeq 
    | assignment; 

diffeq : D OVER DT OPEN id CLOSE EQ id; // <-- here, id is a parser rule 

assignment 
    : id EQ NUMBER 
    | id EQ id OVER id 
    ; 

id : ID | D | DT; // <-- Nice trick, isn't it? 

D  : 'D'; 
DT  : 'DT'; 
OVER : '/'; 
EQ  : '='; 
OPEN : '('; 
CLOSE : ')'; 
ID  : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n'|'\r'|'\n'; 

आप उलटे पांव लौटने और Memoization इस काम करने के लिए सक्षम करने के लिए आवश्यकता हो सकती है (लेकिन उससे पहले उलटे पांव लौटने के बिना यह संकलन की कोशिश) ।

Answer 3

यहां समाधान का अंततः उपयोग किया गया है। मुझे पता है कि यह मेरी आवश्यकताओं में से एक का उल्लंघन करता है: पार्सर में लेक्सर और पार्सर नियमों में लेक्सर नियमों को रखने के लिए, लेकिन जैसा कि यह डीडीटी को डीडीटी में ले जाने के लिए मेरे कोड में कोई बदलाव नहीं करता है। इसके अलावा, dasblinkenlight अपने जवाब और टिप्पणियों में बेमेल ब्रैथेसिस के बारे में कुछ अच्छे अंक बनाता है।

grammar ddt_problem; 

program : (statement? NEWLINE)*; 

statement 
    : diffeq 
    | assignment; 

diffeq : ddt ID ')' '=' ID; 

assignment 
    : ID '=' NUMBER 
    | ID '=' ID '/' ID 
    ; 

ddt : (d=ID) { $d.getText().equals("d") }? '/' (dt=ID) { $dt.getText().equals("dt") }? '('; 
ID : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n'|'\r'|'\n';