अजगर शैली खरोज के लिए पेग

Question

कैसे आप निम्नलिखित पार्सर जेनरेटर में से किसी में एक Parsing Expression Grammar (PEG.js, Citrus, Treetop) जो अजगर/हास्केल/CoffeScript शैली खरोज संभाल कर सकते हैं लिखते थे मौजूदा प्रोग्रामिंग भाषा:

square x = 
    x * x 

---

cube x = 
    x * square x 

---

fib n = 
    if n <= 1 
    0 
    else 
    fib(n - 2) + fib(n - 1) # some cheating allowed here with brackets 

अद्यतन: ऊपर दिए गए उदाहरणों के लिए एक दुभाषिया लिखने की कोशिश न करें। मुझे केवल इंडेंटेशन समस्या में दिलचस्पी है। एक और उदाहरण निम्नलिखित पार्सिंग हो सकता है:

foo 
    bar = 1 
    baz = 2 
tap 
    zap = 3 

# should yield (ruby style hashmap): 
# {:foo => { :bar => 1, :baz => 2}, :tap => { :zap => 3 } } 

Answer 1

शुद्ध पीईजी इंडेंटेशन का विश्लेषण नहीं कर सकता है।

लेकिन peg.js कर सकते हैं।

मैंने एक त्वरित और गंदा प्रयोग किया (धोखाधड़ी के बारे में ईरा बैक्सटर की टिप्पणी से प्रेरित)।

/* Initializations */ 
{ 
    function start(first, tail) { 
    var done = [first[1]]; 
    for (var i = 0; i < tail.length; i++) { 
     done = done.concat(tail[i][1][0]) 
     done.push(tail[i][1][1]); 
    } 
    return done; 
    } 

    var depths = [0]; 

    function indent(s) { 
    var depth = s.length; 

    if (depth == depths[0]) return []; 

    if (depth > depths[0]) { 
     depths.unshift(depth); 
     return ["INDENT"]; 
    } 

    var dents = []; 
    while (depth < depths[0]) { 
     depths.shift(); 
     dents.push("DEDENT"); 
    } 

    if (depth != depths[0]) dents.push("BADDENT"); 

    return dents; 
    } 
} 

/* The real grammar */ 
start = first:line tail:(newline line)* newline? { return start(first, tail) } 
line = depth:indent s:text      { return [depth, s] } 
indent = s:" "*         { return indent(s) } 
text = c:[^\n]*         { return c.join("") } 
newline = "\n"          {} 

depths इंडेंटेशन का ढेर है। इंडेंट() इंडेंटेशन टोकन की एक सरणी देता है और शुरू होता है() सरणी को किसी धारा की तरह कुछ हद तक व्यवहार करने के लिए सरणी को अनचाहे करता है।

peg.js पाठ के लिए पैदा करता है:

alpha 
    beta 
    gamma 
    delta 
epsilon 
    zeta 
    eta 
theta 
    iota 

इन परिणामों:

[ 
    "alpha", 
    "INDENT", 
    "beta", 
    "gamma", 
    "INDENT", 
    "delta", 
    "DEDENT", 
    "DEDENT", 
    "epsilon", 
    "INDENT", 
    "zeta", 
    "DEDENT", 
    "BADDENT", 
    "eta", 
    "theta", 
    "INDENT", 
    "iota", 
    "DEDENT", 
    "", 
    "" 
] 

यह पार्सर भी बुरा इंडेंट फैल जाती है।

Answer 2

मुझे लगता है कि इस तरह की इंडेंटेशन-संवेदनशील भाषा संदर्भ-संवेदनशील है। मेरा मानना ​​है कि पीईजी केवल संदर्भ मुक्त लैंगुग कर सकता है।

ध्यान दें कि, जबकि nalply का जवाब निश्चित रूप से सही है कि PEG.js इसे बाहरी स्थिति (यानी डरावनी वैश्विक चर) के माध्यम से कर सकता है, यह नीचे जाने के लिए एक खतरनाक मार्ग हो सकता है (वैश्विक चर के साथ सामान्य समस्याओं से भी बदतर) । कुछ नियम प्रारंभ में मिलान कर सकते हैं (और उसके बाद अपने कार्यों को चला सकते हैं) लेकिन पैरेंट नियम विफल हो सकते हैं जिससे कार्रवाई अमान्य हो जाती है। यदि ऐसी कार्रवाई में बाहरी स्थिति बदल दी गई है, तो आप अमान्य स्थिति के साथ समाप्त हो सकते हैं। यह बहुत भयानक है, और झटके, उल्टी, और मौत का कारण बन सकता है। इसके लिए कुछ मुद्दे और समाधान यहां टिप्पणियों में हैं: https://github.com/dmajda/pegjs/issues/45

Answer 3

तो हम वास्तव में इंडेंटेशन के साथ क्या कर रहे हैं, सी-स्टाइल ब्लॉक की तरह कुछ बना रहा है, जिसमें अक्सर अपना खुद का शब्दावली होता है। अगर मैं ऐसी भाषा के लिए एक कंपाइलर लिख रहा था, तो मुझे लगता है कि मैं कोशिश करूँगा और लेक्सर इंडेंटेशन का ट्रैक रखेगा। जब भी इंडेंटेशन बढ़ता है तो यह '{' टोकन डाल सकता है। इसी तरह हर बार जब यह घटता है तो यह '}' टोकन को इन्सेट कर सकता है। फिर व्याख्यात्मक दायरे का प्रतिनिधित्व करने के लिए स्पष्ट घुंघराले ब्रेसिज़ के साथ एक अभिव्यक्ति व्याकरण लिखना अधिक सीधे आगे हो जाता है।

Answer 4

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

grammar IndentedBlocks 
    rule top 
    # Initialise the indent stack with a sentinel: 
    &{|s| @indents = [-1] } 
    nested_blocks 
    { 
     def inspect 
     nested_blocks.inspect 
     end 
    } 
    end 

    rule nested_blocks 
    (
     # Do not try to extract this semantic predicate into a new rule. 
     # It will be memo-ized incorrectly because @indents.last will change. 
     !{|s| 
     # Peek at the following indentation: 
     save = index; i = _nt_indentation; index = save 
     # We're closing if the indentation is less or the same as our enclosing block's: 
     closing = i.text_value.length <= @indents.last 
     } 
     block 
    )* 
    { 
     def inspect 
     elements.map{|e| e.block.inspect}*"\n" 
     end 
    } 
    end 

rule block 
    indented_line  # The block's opening line 
    &{|s|    # Push the indent level to the stack 
     level = s[0].indentation.text_value.length 
     @indents << level 
     true 
    } 
    nested_blocks  # Parse any nested blocks 
    &{|s|    # Pop the indent stack 
     # Note that under no circumstances should "nested_blocks" fail, or the stack will be mis-aligned 
     @indents.pop 
     true 
    } 
    { 
     def inspect 
     indented_line.inspect + 
      (nested_blocks.elements.size > 0 ? (
      "\n{\n" + 
      nested_blocks.elements.map { |content| 
       content.block.inspect+"\n" 
      }*'' + 
      "}" 
     ) 
      : "") 
     end 
    } 
    end 

    rule indented_line 
    indentation text:((!"\n" .)*) "\n" 
    { 
     def inspect 
     text.text_value 
     end 
    } 
    end 

    rule indentation 
    ' '* 
    end 
end 

यहाँ एक छोटे से परीक्षण चालक कार्यक्रम है, तो आप इसे आसानी से कोशिश कर सकते हैं:

require 'polyglot' 
require 'treetop' 
require 'indented_blocks' 

parser = IndentedBlocksParser.new 

input = <<END 
def foo 
    here is some indented text 
    here it's further indented 
    and here the same 
     but here it's further again 
     and some more like that 
    before going back to here 
     down again 
    back twice 
and start from the beginning again 
    with only a small block this time 
END 

parse_tree = parser.parse input 

p parse_tree 

Answer 5

मैं जानता हूँ कि यह एक पुरानी धागा है, लेकिन मैं सिर्फ उत्तर देने के लिए कुछ PEGjs कोड जोड़ना चाहते थे। यह कोड पाठ के एक टुकड़े और "घोंसला" को "एएसटी-आश" संरचना के प्रकार में पार्स करेगा। यह केवल एक गहराई में जाता है और यह बदसूरत लग रहा है, इसके अलावा यह वास्तव में सही संरचना बनाने के लिए रिटर्न वैल्यू का उपयोग नहीं करता है लेकिन आपके सिंटैक्स का एक मेमोरी पेड़ रखता है और यह अंत में इसे वापस कर देगा। यह अच्छी तरह से अनावश्यक हो सकता है और कुछ प्रदर्शन मुद्दों का कारण बन सकता है, लेकिन कम से कम यह ऐसा करता है जो इसे माना जाता है।

नोट: सुनिश्चित करें कि आपके पास रिक्त स्थान के बजाय टैब हैं!

{ 
    var indentStack = [], 
     rootScope = { 
      value: "PROGRAM", 
      values: [], 
      scopes: [] 
     }; 

    function addToRootScope(text) { 
     // Here we wiggle with the form and append the new 
     // scope to the rootScope. 

     if (!text) return; 

     if (indentStack.length === 0) { 
      rootScope.scopes.unshift({ 
       text: text, 
       statements: [] 
      }); 
     } 
     else { 
      rootScope.scopes[0].statements.push(text); 
     } 
    } 
} 

/* Add some grammar */ 

start 
    = lines: (line EOL+)* 
    { 
     return rootScope; 
    } 


line 
    = line: (samedent t:text { addToRootScope(t); }) &EOL 
/line: (indent t:text { addToRootScope(t); }) &EOL 
/line: (dedent t:text { addToRootScope(t); }) &EOL 
/line: [ \t]* &EOL 
/EOF 

samedent 
    = i:[\t]* &{ return i.length === indentStack.length; } 
    { 
     console.log("s:", i.length, " level:", indentStack.length); 
    } 

indent 
    = i:[\t]+ &{ return i.length > indentStack.length; } 
    { 
     indentStack.push(""); 
     console.log("i:", i.length, " level:", indentStack.length); 
    } 

dedent 
    = i:[\t]* &{ return i.length < indentStack.length; } 
     { 
      for (var j = 0; j < i.length + 1; j++) { 
       indentStack.pop(); 
      } 
      console.log("d:", i.length + 1, " level:", indentStack.length); 
     } 

text 
    = numbers: number+ { return numbers.join(""); } 
    /txt: character+ { return txt.join(""); } 


number 
    = $[0-9] 

character 
    = $[ a-zA-Z->+] 
__ 
    = [ ]+ 

_ 
    = [ ]* 

EOF 
    = !. 

EOL 
    = "\r\n" 
    /"\n" 
    /"\r"