Построение деревьев выражений в R

Ответ 1

Вот подход, использующий функцию utils::getParseData и заимствование из функции, написанной для пакета parser, и используя igraph для визуальных эффектов. Связанная функция почти делает то, что вы хотели, но данные, возвращаемые функцией getParseData, имеют пустые узлы с численными значениями/символами/операторами и т.д. На листьях. Это имеет смысл, если вы пытаетесь разобрать функции или тройные выражения или более сложные вещи.

Эта функция просто создает edgelist из данных синтаксического анализа.

## https://github.com/halpo/parser/blob/master/R/plot.parser.R
## Modified slightly to return graph instead of print/add attr
parser2graph <- function(y, ...){
    y$new.id <- seq_along(y$id)
    h <- graph.tree(0) + vertices(id = y$id, label= y$text)
    for(i in 1:nrow(y)){
        if(y[i, 'parent'])
            h <- h + edge(c(y[y$id == y[i, 'parent'], 'new.id'], y[i, 'new.id']))
    }
    h <- set_edge_attr(h, 'color', value='black')
    return(h)
}

Следующая функция свертывает дерево разбора, удаляя все "() {}" и оставшиеся пробелы. Идея состоит в том, чтобы сначала перенести все ярлыки на один уровень в дереве, а затем закрепить листья. И, наконец, все пробелы из вложенных выражений ('() {}') удаляются путем создания/уничтожения ребер. Я покрасил края синим цветом, где были удалены уровни гнездования из скобок/фигурных скобок.

## Function to collapse the parse tree (removing () and {})
parseTree <- function(string, ignore=c('(',')','{','}'), ...) {
    dat <- utils::getParseData(parse(text=string))
    g <- parser2graph(dat[!(dat$text %in% ignore), ])
    leaves <- V(g)[!degree(g, mode='out')]                             # tree leaves
    preds <- sapply(leaves, neighbors, g=g, mode="in")                 # their predecessors
    vertex_attr(g, 'label', preds) <- vertex_attr(g, 'label', leaves)  # bump labels up a level
    g <- g - leaves                                                    # remove the leaves
    gaps <- V(g)[!nchar(vertex_attr(g, 'label'))]                      # gaps where ()/{} were
    nebs <- c(sapply(gaps, neighbors, graph=g, mode='all'))            # neighbors of gaps
    g <- add_edges(g, nebs, color='blue')                              # edges around the gaps
    g <- g - V(g)[!nchar(vertex_attr(g, 'label'))]                     # remove leaves/gaps
    plot(g, layout=layout.reingold.tilford, ...)
    title(string, cex.main=2.5)
}

Пример, немного более вложенное выражение. Анимация показывает, как сгенерировано исходное дерево.

## Example string
library(igraph)
string <- "(a/{5})+(2*b+c)"

parseTree(string,  # plus some graphing stuff
          vertex.color="#FCFDBFFF", vertex.frame.color=NA,
          vertex.label.font=2, vertex.label.cex=2.5,
          vertex.label.color="darkred", vertex.size=25,
          asp=.7, edge.width=3, margin=-.05)

Ответ 2

Следующее получает большую часть пути. Он имитирует pryr:::tree для рекурсивного изучения дерева вызовов, затем назначает data.tree Nodes. Я бы предпочел igraph, но он нетерпим к повторяющимся именам node (например, +, появляющимся дважды). Я также не могу получить dendrogram для обозначения любых ветвей, отличных от корня.

#install.packages("data.tree")
library(data.tree)

make_tree <- function(x) {
  if (is.atomic(x) && length(x) == 1) {
    as.character(deparse(x)[1])
  } else if (is.name(x)) {
    x <- as.character(x)
    if (x %in% c("(", ")")) {
      NULL
    } else {
      x
    }
  } else if (is.call(x)) {
    call_items <- as.list(x)
    node <- call_items[[1]]
    call_items <- call_items[-1]
    while (as.character(node) == "(" && length(call_items) > 0) {
      node <- call_items[[1]]
      call_items <- call_items[-1]
    }
    if (length(call_items) == 0) 
      return(make_tree(node))
    call_node <- Node$new(as.character(node))
    for (i in 1:length(call_items)) {
      res <- make_tree(call_items[[i]])
      if (is.environment(res))
        call_node$AddChildNode(res)
      else
        call_node$AddChild(res)
    }
    call_node
  } else
    typeof(x)
}

tree <- make_tree(quote(a+(2*b+c)))
print(tree)
plot(as.dendrogram(tree, edgetext = T), center = T, type = "triangle", yaxt = "n")

Что дает разумный вывод текста:

      levelName
1 +            
2  ¦--a        
3  °--+        
4      ¦--*    
5      ¦   ¦--2
6      ¦   °--b
7      °--c    

и графический. Символ умножения не отображается в середине дерева node (я не могу понять, почему), но в остальном я думаю, что это делает работу.

Ответ 3

Здесь приведен код и результаты, которые могут быть полезными и наименее точными, чтобы "ходить" по дереву разбора:

> parse( text="a+(2*b+c)")
expression(a+(2*b+c))
> parse( text="a+(2*b+c)")[[1]]
a + (2 * b + c)
> parse( text="a+(2*b+c)")[[1]][[1]]
`+`
> parse( text="a+(2*b+c)")[[1]][[2]]
a
> parse( text="a+(2*b+c)")[[1]][[3]]
(2 * b + c)
> parse( text="a+(2*b+c)")[[1]][[4]]
Error in parse(text = "a+(2*b+c)")[[1]][[4]] : subscript out of bounds
> parse( text="a+(2*b+c)")[[1]][[3]][[1]]
`(`
> parse( text="a+(2*b+c)")[[1]][[3]][[2]]
2 * b + c
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[1]]
`+`
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]]
2 * b
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[3]]
c
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]][[1]]
`*`
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]][[2]]
[1] 2
> parse( text="a+(2*b+c)")[[1]][[3]][[2]][[2]][[3]]
b

Я думал, что видел запись в R-help или r-devel Томасом Ламли или Люком Тирни, который сделал это, но до сих пор не смог найти его. Я нашел публикацию @G.Grothendieck, которая программным образом отделяет дерево синтаксического анализа, на которое вы можете опираться:

 e <- parse(text = "a+(2*b+c)") 
my.print <- function(e) { 
  L <- as.list(e) 
  if (length(L) == 0) return(invisible()) 
  if (length(L) == 1) 
     print(L[[1]]) 
     else sapply(L, my.print) 
return(invisible()) } 
my.print(e[[1]])
#----- output-----
`+`
a
`(`
`+`
`*`
[1] 2
b
c

Ответ 4

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

Из этого, остальное "относительно" прямо:

• Для каждого node определите символ для печати. ​​
• Поддерживать (относительную) координату для текущего node. При рекурсии выражения эта координата обновляется в зависимости от того, что вы делаете; например, вы знаете, что аргументы вызова функции должны быть центрированы ниже его вызова, поэтому вы можете соответствующим образом обновить координату y, а затем вычислить x в зависимости от количества аргументов. Операторы - это лишь частный случай.

Наконец, вы можете использовать символы вместе с их координатами, рассчитанными таким образом, чтобы их составлять относительно друг друга.