如何在AST中找到标识符的用法？

问题描述：

鉴于以下AST定义和示例代码，找到在树中位置的标识符的所有用法，最好的算法是什么？如何在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)]

答

那么身份是“创建”的节点的子树中的DFS呢？

答

基本上任何种类的树节点与所需的属性过滤器是需要的。深度优先搜索（如在另一个答案中提出的）是枚举节点的一种方式。

但是，对于特定树节点中的特定标识符，人们通常想知道的是它所代表的“声明实体”是什么？否则，你会找到所有的参考资料，但它们是针对不同的实体的，这通常是没有用的。

这需要为相关应用程序语言构建符号表，然后在标识符节点和符号表条目之间构造一个映射。一个简单的枚举器不会构建符号表。

答

看看我砍死周末的实现：

http://fsharprefactor.codeplex.com/

似乎工作在Visual Studio库:)

答

FSharpRefactor 0.1（预览版）发行。

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

干杯）

如何在AST中找到标识符的用法？

相关推荐