PEG per Python stile di rientro

Question

Come ti scrivere un Parsing Expression Grammar in uno dei seguenti generatori Parser (PEG.js, Citrus, Treetop) che può gestire Python/Haskell/CoffeScript stile di rientro:

Esempi di un non-ancora- linguaggio di programmazione esistente:

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 

Aggiornamento: Non provare a scrivere un interprete per gli esempi sopra. Mi interessa solo il problema dell'indentazione. Un altro esempio potrebbe essere l'analisi seguente:

foo 
    bar = 1 
    baz = 2 
tap 
    zap = 3 

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

Answer 1

PEG puro non è in grado di analizzare il rientro.

Ma peg.js can.

Ho fatto un esperimento veloce e sporco (ispirato al commento di Ira Baxter sull'inganno).

/* 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 è una pila di rientranze. indent() restituisce un array di token di indentazione e start() scava la matrice per far sì che il parser si comporti in qualche modo come un flusso.

peg.js produce per il testo:

alpha 
    beta 
    gamma 
    delta 
epsilon 
    zeta 
    eta 
theta 
    iota 

questi risultati:

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

Questo parser cattura anche cattivi trattini.

Answer 2

Penso che un linguaggio sensibile all'indentazione del genere sia sensibile al contesto. Credo che PEG possa solo eseguire langauges senza contesto.

Si noti che, mentre la risposta di nalply è certamente corretta che PEG.js può farlo tramite lo stato esterno (cioè le temute variabili globali), può essere un percorso pericoloso da percorrere (peggio dei soliti problemi con le variabili globali) . Alcune regole possono inizialmente corrispondere (e quindi eseguire le loro azioni) ma le regole genitore possono fallire e quindi l'esecuzione dell'azione non è valida. Se lo stato esterno viene modificato in tale azione, puoi finire con uno stato non valido. Questo è terribile e potrebbe portare a tremori, vomito e morte. Alcuni problemi e soluzioni a questo sono nei commenti qui: https://github.com/dmajda/pegjs/issues/45

Answer 3

Quindi quello che stiamo facendo qui con indentazione è la creazione di qualcosa come blocchi in stile C che spesso hanno il loro ambito lessicale. Se stavo scrivendo un compilatore per un linguaggio come quello, penso che proverei a fare in modo che il lexer tenga traccia del rientro. Ogni volta che il rientro aumenta, potrebbe inserire un token '{'. Allo stesso modo ogni volta che diminuisce potrebbe inserire un gettone '}'. Quindi scrivere una grammatica di espressioni con parentesi graffe esplicite per rappresentare lo scope lessicale diventa più semplice.

Answer 4

È possibile farlo in Treetop utilizzando i predicati semantici.In questo caso è necessario un predicato semantico che rilevi la chiusura di un blocco rientrato nello spazio bianco a causa dell'occorrenza di un'altra linea che presenta la stessa o minore rientranza. Il predicato deve contare il rientro dalla linea di apertura e restituire true (blocco chiuso) se l'indentazione della riga corrente ha terminato alla stessa lunghezza o minore. Poiché la condizione di chiusura dipende dal contesto, non deve essere memoized. Ecco il codice di esempio che sto per aggiungere alla documentazione di Treetop. Nota che ho sovrascritto il metodo di ispezione SyntaxNode di Treetop per rendere più semplice la visualizzazione del risultato.

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 

Ecco un piccolo programma di test driver in modo da poter provare facilmente:

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

So che questo è un vecchio thread, ma volevo solo aggiungere del codice PEGjs alle risposte. Questo codice analizzerà un pezzo di testo e lo "anniderà" in una sorta di struttura "AST-ish". Ha solo una profondità e sembra brutto, inoltre non utilizza i valori di ritorno per creare la struttura giusta ma mantiene una struttura in memoria della sintassi e alla fine la restituirà. Questo potrebbe diventare ingombrante e causare alcuni problemi di prestazioni, ma almeno fa ciò che dovrebbe.

Nota: assicurarsi di disporre di schede anziché spazi!

{ 
    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"