Analizzatore sensibile all'indentazione utilizzando Parslet in Ruby?

Question

Sto tentando di analizzare una semplice sintassi sensibile all'indentazione utilizzando la libreria Parslet all'interno di Ruby.

Il seguente è un esempio di sintassi che sto cercando di analizzare:

level0child0 
level0child1 
    level1child0 
    level1child1 
    level2child0 
    level1child2 

L'albero risultante sarà simile modo:

[ 
    { 
    :identifier => "level0child0", 
    :children => [] 
    }, 
    { 
    :identifier => "level0child1", 
    :children => [ 
     { 
     :identifier => "level1child0", 
     :children => [] 
     }, 
     { 
     :identifier => "level1child1", 
     :children => [ 
      { 
      :identifier => "level2child0", 
      :children => [] 
      } 
     ] 
     }, 
     { 
     :identifier => "level1child2", 
     :children => [] 
     }, 
    ] 
    } 
] 

Il parser che ho ora in grado di analizzare il livello di nidificazione 0 e 1 nodi, ma non può analizzare passato che:

require 'parslet' 

class IndentationSensitiveParser < Parslet::Parser 

    rule(:indent) { str(' ') } 
    rule(:newline) { str("\n") } 
    rule(:identifier) { match['A-Za-z0-9'].repeat.as(:identifier) } 

    rule(:node) { identifier >> newline >> (indent >> identifier >> newline.maybe).repeat.as(:children) } 

    rule(:document) { node.repeat } 

    root :document 

end 

require 'ap' 
require 'pp' 

begin 
    input = DATA.read 

    puts '', '----- input ----------------------------------------------------------------------', '' 
    ap input 

    tree = IndentationSensitiveParser.new.parse(input) 

    puts '', '----- tree -----------------------------------------------------------------------', '' 
    ap tree 

rescue IndentationSensitiveParser::ParseFailed => failure 
    puts '', '----- error ----------------------------------------------------------------------', '' 
    puts failure.cause.ascii_tree 
end 

__END__ 
user 
    name 
    age 
recipe 
    name 
foo 
bar 

e 'chiaro che ho bisogno di un dinamicamente c contatore che prevede 3 nodi di indentazione per abbinare un identificatore a livello di annidamento 3.

Come posso implementare un parser di sintassi sensibile all'indentazione utilizzando Parslet in questo modo? È possibile?

Answer 1

Ci sono alcuni approcci.

1. analizzare il documento riconoscendo ogni riga come una raccolta di trattini e un identificatore, quindi applicare una trasformazione poi ricostruire la gerarchia basata sul numero di trattini.

2. Usa cattura per memorizzare il rientro corrente e si aspettano il nodo successivo per includere tale trattino e molto di più per abbinare come un bambino (non ho scavare in questo approccio tanto quanto il prossimo si è verificato a me)

3. Le regole sono solo metodi. Quindi puoi definire 'nodo' come metodo, il che significa che puoi passare i parametri! (Come segue)

Questo permette di definire node(depth) in termini di node(depth+1). Il problema con questo approccio, tuttavia, è che il metodo node non corrisponde a una stringa, genera un parser. Quindi una chiamata ricorsiva non finirà mai.

Questo è il motivo per cui esiste dynamic. Restituisce un parser che non viene risolto fino al punto in cui tenta di farlo corrispondere, permettendoti di recurse ora senza problemi.

vedere il codice seguente:

require 'parslet' 

class IndentationSensitiveParser < Parslet::Parser 

    def indent(depth) 
    str(' '*depth) 
    end 

    rule(:newline) { str("\n") } 

    rule(:identifier) { match['A-Za-z0-9'].repeat(1).as(:identifier) } 

    def node(depth) 
    indent(depth) >> 
    identifier >> 
    newline.maybe >> 
    (dynamic{|s,c| node(depth+1).repeat(0)}).as(:children) 
    end 

    rule(:document) { node(0).repeat } 

    root :document 
end 

Questa è la mia soluzione preferita.

Answer 2

Non mi piace l'idea di tessere la conoscenza del processo di indentazione attraverso l'intera grammatica. Preferirei avere solo token di INDENT e DEDENT prodotti da altre regole che potessero essere utilizzate in modo simile ai caratteri "{" e "}" corrispondenti. Quindi la seguente è la mia soluzione. È una classe IndentParser che qualsiasi parser può estendere per ottenere i token generati nl, indent e decent.

require 'parslet' 

# Atoms returned from a dynamic that aren't meant to match anything. 
class AlwaysMatch < Parslet::Atoms::Base 
    def try(source, context, consume_all) 
    succ("") 
    end 
end 
class NeverMatch < Parslet::Atoms::Base 
    attr_accessor :msg 
    def initialize(msg = "ignore") 
    self.msg = msg 
    end 
    def try(source, context, consume_all) 
    context.err(self, source, msg) 
    end 
end 
class ErrorMatch < Parslet::Atoms::Base 
    attr_accessor :msg 
    def initialize(msg) 
    self.msg = msg 
    end 
    def try(source, context, consume_all) 
    context.err(self, source, msg) 
    end 
end 

class IndentParser < Parslet::Parser 

    ## 
    # Indentation handling: when matching a newline we check the following indentation. If 
    # that indicates an indent token or detent tokens (1+) then we stick these in a class 
    # variable and the high-priority indent/dedent rules will match as long as these 
    # remain. The nl rule consumes the indentation itself. 

    rule(:indent) { dynamic {|s,c| 
    if @indent.nil? 
     NeverMatch.new("Not an indent") 
    else 
     @indent = nil 
     AlwaysMatch.new 
    end 
    }} 
    rule(:dedent) { dynamic {|s,c| 
    if @dedents.nil? or @dedents.length == 0 
     NeverMatch.new("Not a dedent") 
    else 
     @dedents.pop 
     AlwaysMatch.new 
    end 
    }} 

    def checkIndentation(source, ctx) 
    # See if next line starts with indentation. If so, consume it and then process 
    # whether it is an indent or some number of dedents. 
    indent = "" 
    while source.matches?(Regexp.new("[ \t]")) 
     indent += source.consume(1).to_s #returns a Slice 
    end 

    if @indentStack.nil? 
     @indentStack = [""] 
    end 

    currentInd = @indentStack[-1] 
    return AlwaysMatch.new if currentInd == indent #no change, just match nl 

    if indent.start_with?(currentInd) 
     # Getting deeper 
     @indentStack << indent 
     @indent = indent #tells the indent rule to match one 
     return AlwaysMatch.new 
    else 
     # Either some number of de-dents or an error 

     # Find first match starting from back 
     count = 0 
     @indentStack.reverse.each do |level| 
     break if indent == level #found it, 

     if level.start_with?(indent) 
      # New indent is prefix, so we de-dented this level. 
      count += 1 
      next 
     end 

     # Not a match, not a valid prefix. So an error! 
     return ErrorMatch.new("Mismatched indentation level") 
     end 

     @dedents = [] if @dedents.nil? 
     count.times { @dedents << @indentStack.pop } 
     return AlwaysMatch.new 
    end 
    end 
    rule(:nl)   { anynl >> dynamic {|source, ctx| checkIndentation(source,ctx) }} 

    rule(:unixnl)  { str("\n") } 
    rule(:macnl)  { str("\r") } 
    rule(:winnl)  { str("\r\n") } 
    rule(:anynl)  { unixnl | macnl | winnl } 

end 

Sono sicuro che un sacco può essere migliorato, ma questo è quello che mi è venuta in mente finora.

Esempio utilizzo:

class MyParser < IndentParser 
    rule(:colon)  { str(':') >> space? } 

    rule(:space)  { match(' \t').repeat(1) } 
    rule(:space?)  { space.maybe } 

    rule(:number)  { match['0-9'].repeat(1).as(:num) >> space? } 
    rule(:identifier) { match['a-zA-Z'] >> match["a-zA-Z0-9"].repeat(0) } 

    rule(:block)  { colon >> nl >> indent >> stmt.repeat.as(:stmts) >> dedent } 
    rule(:stmt)  { identifier.as(:id) >> nl | number.as(:num) >> nl | testblock } 
    rule(:testblock) { identifier.as(:name) >> block } 

    rule(:prgm)  { testblock >> nl.repeat } 
    root :prgm 
end