Tracciare alberi di espressione in R

Question

So che è possibile creare un albero di espressioni in R utilizzando la funzione substitute. Diciamo che ho generato il seguente albero di espressione:

expT <- substitute(a+(2*b+c)) 

E 'possibile visualizzare l'albero di espressione in R, producendo qualcosa di simile:

so che ( è anche una funzione in R, ma vorrei ometterlo nella trama.

Answer 1

Ecco un approccio sfruttando la funzione di utils::getParseData e prestito da una funzione scritta per la parser package e utilizzando igraph per le immagini.La funzione collegata fa quasi ciò che volevi, ma i dati restituiti dalla funzione getParseData hanno nodi vuoti con i valori numerici/simboli/operatori ecc. Sulle foglie. Questo ha senso se si tenta di analizzare funzioni o espressioni ternarie o cose più complicate.

Questa funzione crea semplicemente un edgelist dai dati di analisi.

## 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) 
} 

La funzione successiva comprime l'albero di analisi rimuovendo tutti gli spazi vuoti '() {}' e rimanenti. L'idea è di spostare prima tutte le etichette su un livello nell'albero, quindi tagliare le foglie. Infine, tutti gli spazi delle espressioni nidificate ('() {}') vengono rimossi creando/distruggendo i bordi. Ho colorato i bordi blu dove sono stati rimossi i livelli di nidificazione da parentesi/parentesi graffe.

## 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) 
} 

Un esempio, un'espressione leggermente più nidificata. L'animazione mostra come l'albero originale è collassato.

## 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) 

Answer 2

È sicuramente possibile, ma non sono a conoscenza di una funzione esistente per farlo. Detto questo, è un bel esercizio. Date un'occhiata a Walking the AST with recursive functions (e leggete l'intero capitolo) per le istruzioni di base su come operare su un albero di espressioni.

Da questo, il resto è “relativamente” semplice:

• Per ciascun nodo, determinare il simbolo da stampare.
• Mantieni una coordinata (relativa) per il nodo corrente. Quando si ricorre l'espressione, questa coordinata viene aggiornata in base a ciò che si fa; ad esempio, sapete che gli argomenti di una chiamata di funzione devono essere centrati al di sotto della sua chiamata, quindi è possibile aggiornare la coordinata di conseguenza e quindi calcolare x a seconda di quanti argomenti ci sono. Gli operatori sono solo un caso speciale di questo.

Infine, è possibile utilizzare i simboli accanto alle loro coordinate così calcolate per tracciarli, l'uno rispetto all'altro.

Answer 3

Ecco po 'di codice ed i risultati che può essere utile e almeno fino al punto di essere in grado di "camminare" il "analizzare albero":

> 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 

ho pensato che avevo visto un invio in R-aiuto o r-devel di Thomas Lumley o Luke Tierney che ha fatto questo, ma finora non è riuscito a individuarlo. Ho trovato un post da @ G.Grothendieck che tira di programmazione a parte un albero sintattico che si potrebbe costruire su:

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 

Answer 4

Il seguente ottiene la maggior parte del tragitto. Simula lo pryr:::tree per esaminare in modo ricorsivo l'albero delle chiamate, quindi assegna i nodi data.tree. Avrei preferito igraph ma non intollerante ai nomi di nodi duplicati (ad esempio, + che vengono visualizzati due volte). Non riesco nemmeno a ottenere dendrogram per etichettare uno qualsiasi dei rami diversi dalla radice.

#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") 

che dà un output di testo ragionevole:

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

e grafica. Il simbolo della moltiplicazione non appare nel nodo mid-tree (non riesco a capire perché), ma in caso contrario, penso che questo faccia il lavoro.