Abstract syntax tree: Difference between revisions

Revision as of 02:37, 6 June 2006

Revision as of 02:38, 6 June 2006

Line 1:

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

nodes]] are labeled by operators, and the [[leaf node|leaf nodes]] 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.