Как найти использование идентификатора в AST?

Question

Принимая во внимание следующее определение AST и пример кода, каков будет наилучший алгоритм для поиска всех использований идентификатора с учетом его положения в дереве?

AST Definition

type Literal
   = Char  of  char          // character literal
   | String of string        // string literal
   | Integer of  int         // integer literal
   | Float  of  float        // floating point literal   
   | Double of double 
   | Unit

type SrcCol = { startColumn : int; endColumn : int }

type SrcLine = { startLine : int; endLine : int }

type SrcLoc = { srcFilename : string; srcLine : SrcLine; srcColumn : SrcCol }     

type Pat =
    | PVar of 'a
    | PApp of Pat * Pat
    | PLit of Literal    
    | PWithTy of Pat * Type

type Exp 
    = Var      of 'a                           // variable    
    | Lam      of Pat list * Exp       // lambda abstraction
    | App      of Exp * Exp            // application    
    | Let      of Pat * Exp * Exp  // local definition    
    | Lit      of Literal                      // literal 
    | WithTy   of Exp * Type



Sample Code:

let f x = let g x = x                               
          g x 

AST instance of Sample Code
  [Let
                   (PApp
                      (PVar
                         ("f",
                          {srcFilename =
                            "test.fs";
                           srcLine = {startLine = 1;
                                      endLine = 1;};
                           srcColumn = {startColumn = 4;
                                        endColumn = 5;};}),
                       PVar
                         ("x",
                          {srcFilename =
                            "test.fs";
                           srcLine = {startLine = 1;
                                      endLine = 1;};
                           srcColumn = {startColumn = 6;
                                        endColumn = 7;};})),
                    Let
                      (PApp
                         (PVar
                            ("g",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 1;
                                         endLine = 1;};
                              srcColumn = {startColumn = 14;
                                           endColumn = 15;};}),
                          PVar
                            ("x",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 1;
                                         endLine = 1;};
                              srcColumn = {startColumn = 16;
                                           endColumn = 17;};})),
                       Var
                         ("x",
                          {srcFilename =
                            "test.fs";
                           srcLine = {startLine = 1;
                                      endLine = 1;};
                           srcColumn = {startColumn = 20;
                                        endColumn = 21;};}),
                       App
                         (Var
                            ("g",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 2;
                                         endLine = 2;};
                              srcColumn = {startColumn = 10;
                                           endColumn = 11;};}),
                          Var
                            ("x",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 2;
                                         endLine = 2;};
                              srcColumn = {startColumn = 12;
                                           endColumn = 13;};}))),Lit Unit)]

Answer 1

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

Однако, что обычно нужно знать для определенного идентификатора в конкретном узле дерева, что представляет собой «объявленная сущность»? В противном случае вы найдете все ссылки, но они относятся к разным объектам, и это, как правило, не помогает.

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

Answer 2

Посмотрите на реализацию, которую я взломал за выходные:

http://fsharprefactor.codeplex.com/

Кажется, что работает

Answer 3

А как насчет DFS в дочерних деревьях узла, где "идентификатор" "создан"?

Answer 4

FSharpRefactor 0.1 (версия для предварительного просмотра) Релиз в галерее Visual Studio.

http://visualstudiogallery.msdn.microsoft.com/339cbae9-911d-4f99-9033-3c3564676f45?SRC=Home

Приветствия;)