Angesichts der folgenden AST-Definition und Beispielcode, was wäre der beste Algorithmus, um alle Verwendungen eines Bezeichners aufgrund seiner Position im Baum zu finden?Wie findet man Verwendungen eines Identifikators in einem 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)]