Abstract Syntax Tree

Transforms a language into data by lexing (separating the words into a sequence of tokens) and parsing (applying syntactical rules to the tokens).

Once in a data structure, you can programatically analyze or even modify the language by iterating over the tokens.

Examples:

• Writing a linter for TypeScript
• Detecting usage of unsafe in Rust crates

Links to this note

• Visitor Pattern

  A pattern for traversing a tree of heterogeneous objects. Decoupling the algorithm for traversing the tree and the code operating on the objects leads to a much cleaner (and easily extensible) code.