Abstract syntax tree

An abstract syntax tree (AST) represents a program or expression as a hierarchy of nodes for meaningful constructs, omitting details such as punctuation and formatting.

Context-free grammar: A formal grammar whose production rules describe how strings can be formed from nested syntactic structures. Grammar rules define which AST structures a parser may construct.
Parsing: The process of analyzing a sequence of tokens according to a grammar to determine its syntactic structure. A parser constructs an AST from source text or tokens.
Compiler: A program that translates source code into another language or executable representation. Compilers use ASTs as an intermediate representation between parsing and later stages.
Concrete syntax tree: A tree representation that retains the grammatical details of source text, including punctuation and intermediate syntax. It preserves surface syntax that an abstract syntax tree discards.
Parse tree: A tree that records how a string is derived from a grammar, including intermediate grammatical symbols. It preserves grammar details that an AST typically removes.
Recursive descent parser: A top-down parser implemented as mutually recursive procedures for grammar rules. Its procedures can create AST nodes as they recognize language constructs.
Static analysis: The analysis of software without executing it, often to detect errors or enforce rules. AST inspection reveals constructs that tools can check without running the program.
Control-flow graph: A directed graph whose nodes represent program operations and whose edges represent possible execution paths. It organizes execution flow rather than the nested syntax represented by an AST.
Operator precedence: Rules that determine how operators bind in expressions with multiple operations. Precedence determines the tree structure of expressions such as multiplication mixed with addition.
Visitor pattern: A software design pattern that applies operations to elements of a structured object without placing those operations in the elements. Visitors provide a common way to traverse AST nodes for separate operations.

Linked from 12 pages