Abstract syntax tree: Difference between revisions

Revision as of 15:30, 25 September 2006

Revision as of 01:34, 14 October 2006

Line 1:

In [[computer science]], an '''abstract syntax tree''' (AST) is a [[finite set|finite]], [[labeled tree|labeled]], [[directed tree]], where the [[internal node|internal

nodes]] are labeled by operators, and the [[leaf node|leaf nodes]]s represent the operands of the node operators. Thus, the leaves have nullary operators, i.e., variables or constants. In computing, it is used in a [[parser]] as an intermediate between a [[parse tree]] and a [[data structure]], the latter which is often used as a [[compiler (computing)|compiler]] or [[interpreter (computing)|interpreter]]'s internal [[intermediate representation|representation]] of a [[computer program]] while it is being [[compiler optimization| optimized]] and from which code generation is performed. The range of all possible such structures is described by the [[abstract syntax]]. An AST differs from a parse tree by omitting nodes and edges for syntax rules that do not affect the

semantics of the program. The classic example of such an omission is grouping parentheses, since in an AST the grouping of operands is explicit in the tree structure.

Creating an AST in a [[parsing|parser]] for a language described by a [[context free grammar]], as nearly all programming languages are, is straightforward. Most rules in the grammar create a new node with the nodes edges being the symbols in the rule. Rules that do not contribute to the AST, such as grouping rules, merely pass through the node for one of their symbols. Alternatively, a parser can create a full parse tree, and a post-pass over the parse tree can convert it to an AST by removing the nodes and edges not used in the abstract syntax.

{{comp-sci-stub}}

==See also==

Line 31 ⟶ 29:

[[de:Abstract Syntax Tree]]

[[fr:Arbre Syntaxique Abstrait]]

{{comp-sci-stub}}