Парсер, чувствительный к отступам, использующий Parslet в Ruby?

Question

Я пытаюсь разобрать простой чувствительный к отступам синтаксис, используя библиотеку Parslet в Ruby.

Ниже приведен пример синтаксиса, который я пытаюсь проанализировать:

level0child0
level0child1
  level1child0
  level1child1
    level2child0
  level1child2

Результирующее дерево будет выглядеть так:

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

Парсер, который у меня есть, теперь может анализировать узлы вложенности уровня 0 и 1, но не может выполнить анализ этого:

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

Понятно, что мне нужен динамический счетчик, который ожидает, что 3 узла отступа будут соответствовать идентификатору на уровне вложенности 3.

Как я могу реализовать синтаксический анализатор, чувствительный к отступам, используя Parslet таким образом? Является ли это возможным?

Answer 1

Есть несколько подходов.

1. Выполните синтаксический анализ документа, распознав каждую строку как набор отступов и идентификатор, а затем примените преобразование, чтобы восстановить иерархию на основе количества отступов.

2. Используйте захваты для хранения текущего отступа и ожидайте, что следующий узел будет включать этот отступ и еще больше, чтобы он соответствовал как ребенок (я не слишком углублялся в этот подход, так как следующий пришёл мне в голову)

3. Правила - это просто методы. Таким образом, вы можете определить "узел" как метод, что означает, что вы можете передавать параметры! (следующее)

Это позволяет вам определить node(depth) с точки зрения node(depth+1), Проблема с этим подходом, однако, заключается в том, что node Метод не соответствует строке, он генерирует синтаксический анализатор. Таким образом, рекурсивный вызов никогда не закончится.

Вот почему dynamic существует. Он возвращает синтаксический анализатор, который не разрешен до тех пор, пока он не попытается сопоставить его, что позволяет вам теперь выполнять рекурсию без проблем.

Смотрите следующий код:

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

Это мое любимое решение.

Answer 2

Мне не нравится идея переплетения знаний о процессе отступа через всю грамматику. Я бы предпочел, чтобы токены INDENT и DEDENT создавались так, чтобы другие правила могли использовать аналогично тому, чтобы просто сопоставлять символы "{" и "}". Так что мое решение следующее. Это класс IndentParser что любой парсер может расширяться чтобы получить nl, indent, а также 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

Я уверен, что многое можно улучшить, но это то, что я придумал до сих пор.

Пример использования:

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