ट्रीटॉप व्याकरण अनंत लूप

Question

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

मेरा पार्सर इस तरह अभिनय कर रहा है जैसे इसमें अनंत लूप है, लेकिन बिना किसी स्टैक निशान के; यह ट्रैक करना मुश्किल साबित हो रहा है। क्या कोई मुझे एंट्री लेवल पार्सिंग/एएसटी गाइड की दिशा में इंगित कर सकता है? मुझे वास्तव में कुछ ऐसा करने की ज़रूरत है जो नियमों, सामान्य उपयोग आदि को ट्रिटॉप जैसे टूल का उपयोग करने के लिए सूचीबद्ध करे। मेरा पार्सर व्याकरण GitHub पर है, अगर कोई इसे सुधारने में मेरी सहायता करना चाहता है।

class { 
    initialize = lambda (name) { 
    receiver.name = name 
    } 

    greet = lambda { 
    IO.puts("Hello, #{receiver.name}!") 
    } 
}.new(:World).greet() 

Answer 1

मुझे वास्तव में Language Implementation Patterns by Parr का आनंद लिया गया; चूंकि पार ने ANTLR पार्सर जनरेटर बनाया है, यह वह टूल है जो वह पूरे पुस्तक में उपयोग करता है, लेकिन यह सब कुछ सीखने के लिए पर्याप्त होना चाहिए।

मुझे वास्तव में इसके बारे में क्या पसंद आया था, जैसा कि पिछले उदाहरण पर प्रत्येक उदाहरण बढ़ता था; वह एक विशाल एएसटी-सक्षम पार्सर के साथ शुरू नहीं करता है, इसके बजाय वह धीरे-धीरे उन समस्याओं को पेश करता है जिन्हें नौकरी करने के लिए अधिक से अधिक 'बैकएंड स्मारक' की आवश्यकता होती है, इसलिए किताब उस भाषा के साथ अच्छी तरह से स्केल करती है, जिसे पार्सिंग की आवश्यकता होती है।

मैं इसे थोड़ा और गहराई में कवर इच्छा किन भाषाओं का है कि एक लिख सकते हैं और क्या करें और मत करो के जब डिजाइनिंग भाषाओं के बारे में सलाह दे सकते हैं के प्रकार है। मैंने कुछ ऐसी भाषाएं देखी हैं जो पार्स के लिए एक बड़ा दर्द है और मुझे डिज़ाइन फैसलों के बारे में और जानना अच्छा लगेगा जो अलग-अलग हो सकते थे।

Answer 2

मैंने आपकी भाषा को एक .rb फ़ाइल में संकलित करने के लिए treetop से पूछा। यही कारण है कि मुझे खुदाई करने के लिए कुछ दे दी है में:

require 'treetop' 
load '/tmp/rip.rb' 
RipParser.new.parse('') 

यह लटकी हुई है:

$ tt -o /tmp/rip.rb /tmp/rip.treetop 

तब मैं पाश पुन: बनाने के लिए इस छोटे से ठूंठ इस्तेमाल किया। अब, वह दिलचस्प नहीं है! एक खाली स्ट्रिंग आपके प्रश्न में व्यवहार के साथ-साथ दर्जन-या-रेखा उदाहरण को पुन: उत्पन्न करती है।

यह पता लगाने के लिए कि यह कहां लटक रहा है, मैंने rip.rb को संपादित करने के लिए एक Emacs कीबोर्ड मैक्रो का उपयोग किया, प्रत्येक विधि के प्रवेश में एक डीबग कथन जोड़ना। उदाहरण के लिए: वहाँ से पता चलता है कि एक पूर्णांक को खाली स्ट्रिंग के लिए अनुमति दी है

[16, "root"] 
[21, "_nt_root"] 
[57, "_nt_statement"] 
... 
[3293, "_nt_eol"] 
[3335, "_nt_semicolon"] 
[3204, "_nt_comment"] 
[57, "_nt_statement"] 
[57, "_nt_statement"] 
[57, "_nt_statement"] 
... 

इसके अलावा डिबगिंग:

rule integer 
    digit* 
end 

def _nt_root 
    p [__LINE__, '_nt_root'] #DEBUG 
    start_index = index 

अब हम पाश के दायरे देख सकते हैं यह अप्रत्यक्ष रूप से एक कथन को खाली स्ट्रिंग होने की अनुमति देता है, और शीर्ष-स्तरीय नियम statement* हमेशा खाली बयान का उपभोग करने के लिए अनुमति देता है। पाश *+ को ठीक करता है बदल रहा है, लेकिन एक और समस्या का पता चलता है:

/tmp/rip.rb:777:in `_nt_object': stack level too deep (SystemStackError) 
     from /tmp/rip.rb:757:in `_nt_compound_object' 
     from /tmp/rip.rb:1726:in `_nt_range' 
     from /tmp/rip.rb:1671:in `_nt_special_literals' 
     from /tmp/rip.rb:825:in `_nt_literal_object' 
     from /tmp/rip.rb:787:in `_nt_object' 
     from /tmp/rip.rb:757:in `_nt_compound_object' 
     from /tmp/rip.rb:1726:in `_nt_range' 
     from /tmp/rip.rb:1671:in `_nt_special_literals' 
     ... 3283 levels... 

रेंज बाएं recursing है, परोक्ष रूप से, special_literals, literal_object, वस्तु, और compound_object के माध्यम से। ट्रीटॉप, जब बाएं रिकर्सन का सामना करना पड़ता है, तब तक ढेर खा जाता है जब तक कि यह पुक न हो जाए। मेरे पास उस समस्या के लिए त्वरित समाधान नहीं है, लेकिन कम से कम आपको अब से जाने के लिए एक स्टैक ट्रेस मिला है।

इसके अलावा, यह आपकी तत्काल समस्या नहीं है, लेकिन digit की परिभाषा विषम है: यह या तो एक अंक या एकाधिक हो सकती है। यह digit* या digit+ का कारण बनता है (संभावित रूप से) अवैध पूर्णांक 1________2।