Превращение дерева разбора Treetop в абстрактное синтаксическое дерево (AST)

Question

Я упростил грамматику, выраженную в Treetop, и пытаюсь отфильтровать вывод синтаксического анализатора в AST, используя пользовательские узлы.

grammar Elem

 rule top
   lpar 'top' space 
      args_:(lpar 'args' space ((ident / number) space?)* rpar)  space? 
   rpar <Top>
 end

 rule ident
   [a-zA-Z] [a-zA-Z0-9_]* <Ident>
 end

 rule number
   [0-9]+ <Number>
 end

 rule space
  [\s]+
 end

 rule lpar
  space? '(' space? 
 end

 rule rpar
  space? ')' space? 
 end
end

По сути, он может анализировать следующий пример:

(top (args foo bar 42))

Все пользовательские узлы наследуют Treetop::Runtime::SyntaxNode

Теперь мне нужно отфильтровать дерево разбора, сгенерированное Treetop, в AST.

Я следую стратегии, описанной здесь, но безуспешно: мой AST просто пуст...

Мой драйвер компилятора выглядит следующим образом:

require 'treetop'
require 'pp'

require_relative 'elem'
require_relative 'node_extension'

class ElemCompiler
  def initialize
    @parser=ElemParser.new
  end

  def compile filename
    puts "==> compiling #{filename}"
    @ast=parse(filename)
    puts "==> AST in memory. Good."
  end

  def parse filename
    pp tree=@parser.parse(IO.read(filename))
    pp clean(tree)
  end

  private

  def clean(root_node)
    return if(root_node.elements.nil?)
    pp root_node.elements.collect {|node| node.class.name =="Treetop::Runtime::SyntaxNode" }
    pp root_node.elements.delete_if{|node| node.class.name == "Treetop::Runtime::SyntaxNode" }
    root_node.elements.each {|node| clean(node) }
  end


end

 compiler=ElemCompiler.new.parse ARGV[0]

Что мне не хватает?

Answer 1

Ваш код действительно правильно анализирует предоставленное выражение.

Однако в методе clean есть небольшая ошибка:

def clean(root_node)
    return if(root_node.elements.nil?)
    pp root_node.elements.collect {|node| node.class.name =="Treetop::Runtime::SyntaxNode" }
    pp root_node.elements.delete_if{|node| node.class.name == "Treetop::Runtime::SyntaxNode" }
    root_node.elements.each {|node| clean(node) }
end

Метод clean возвращает последнее вычисленное выражение, которое является каждым методом элементов массива. То, что вы хотите вернуть, на самом деле является корневым узлом, поэтому линия pp clean(tree) будет на самом деле печатать результирующее чистое дерево, а не результат каждого выражения.

Вы можете решить двумя способами, один добавляет root_node в качестве выражения возврата:

def clean(root_node)
    (...)
    pp root_node.elements.delete_if{|node| node.class.name == "Treetop::Runtime::SyntaxNode" }
    root_node  # here
end

Или вы можете изменить метод разбора на следующий:

def parse filename
    pp tree = @parser.parse(IO.read(filename))
    clean(tree) # we clean the tree
    pp tree     # since tree is an object, side-effects will persist here
end

Однако я бы не советовал чистить дерево. У меня был действительно плохой опыт при этом. Это правда, что вы получаете более чистую структуру, которую вы можете понять гораздо лучше, поскольку Treetop часто хранит много информации, которая вам на самом деле не нужна, но вы рискуете потерять, например, возможность ссылаться на проанализированные выражения с их идентификаторами (пользовательские метки). или автоматически определенные методы доступа к элементам для нетерминальных символов) (это ссылка на веб-архив).

Кроме того, в некоторых случаях очистка узла только потому, что его имя класса "Treetop::Runtime::SyntaxNode" просто неверна, потому что в некоторых случаях вам нужно использовать модуль, а не класс, для расширения ваших узлов, и в этом случае имя класса узла по-прежнему будет "Treetop::Runtime::SyntaxNode", но узел будет очищен от дерева, и вы потеряете функциональность смешанного модуля.

Дайте мне знать, если я был ясен (к сожалению, сайт документации, кажется, не работает, у него было довольно много полезных примеров, которые я хотел бы показать вам, и, поскольку я уже давно не играю с грамматиками, я не очень Помни это).