如何在 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

“创建”身份的节点的子树中的 DFS 怎么样？

Answer 3

看看我周末破解的实现：

http://fsharprefactor.codeplex.com/

似乎工作 ：）

Answer 4

FSharpRefactor 0.1（预览版）在 Visual Studio Gallery 上发布。

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

干杯;)