A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Abstract Syntax Tree

An abstract syntax tree (AST) is a finite, labeled, directed tree, where the internal nodes are labeled by operators, and the 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 or interpreter's internal representation of a computer program while it is being 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 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.

Go up


Assembler

An assembler is a program that translates assembly language into binary instructions. Assembly language provides a friendlier representation for machine code than a computer’s 0s and 1s bytecode, that simplifies writing and reading programs. Symbolic names (mnemonics) for operations (labels) and locations are one facet of this representation. Another facet is programming facilities that increase a program’s clarity.

An assembler (that is a language processor, similar to a compiler) reads a single assembly language source file and produces an object file containing machine instructions in bytecode format and bookkeeping information that helps combine several object files into a program.

Go up


Assembly

Soon...

Go up


Attribute Grammar

An attribute grammar is an ordered eighttuple AG = (T, N, S, P, A, R, CC, TR) , where:
- N and T are finite alphabets;
- S is a distinguished symbol of N;
- P is a finite non-empty set pairs (L,R) such that L and R are in (N U T)*;
- A is the union of the inherited and sinthesized attributes of a non-terminal X in (N U T)* (if X in N then A(ttributes) (X) = S(inthesized)A(ttributes) U I(nherited)A(ttributes) and the intersection of this two sets is empty; if X in T then A(X) = SA(X) and A(S) = SA(S));
- R = U R(p) is a set of evaluation rules,
- CC = U CC(p) is a set of contextual conditions
- and TR is a set of translation rules.

An attribute grammar is a formalism to specify the syntax and semantics of a language; it defines the information that will need to be in the abstract syntax tree to successfully perform semantic analysis and code generation. This information is stored as attributes of the nodes of the abstract syntax tree.

The attributes (see also: Attributes) are divided into two groups, called synthesized attributes and inherited attributes.

1. The synthesized attributes of a symbol X0, at the root of a tree, store the values that result from attribute evaluation rules using the values of the synthesized attributes of its children nodes (Y1 to Yn) and its own inherited attributes.

2. The inherited attributes of a symbol Yi, i=1..n, at the leaves of a tree, store the values that result from attribute evaluation rules using the values of the synthesized attributes of its sibling nodes and inherited attributes of its parent node (the root of that tree).

Basically, synthesized attributes are used to pass semantic information up the parse tree (from leaves to the root), while inherited attributes are used to pass semantic information down the parse tree (propagating values from the root to the leaves). The first is information extracted (directly or after some computation) from the present substring, of the source text, under analysis and processing; the second corresponds to information, available from the context (substrings before or after), that should be taken into consideration for processing the present substring of the source text.

Go up


Attributes

"Attribute: quality, sign or mark which is charatetristic of something or somebody."

in An English-Reader's Dictionary, Oxford University Press

In general, a set of attributes is used to characterize a family of objects (a class); for a given object (a class instance), each "attribute" has a specific "value" that is said to be an object "property".

In the context of formal language definition, attributes are associated to grammar symbols (non-terminal, or terminal symbols) to specify the language semantics.
For a particular sentence in that language, the values of the set of attributes associated with the grammar axiom (or root symbol) define its specific meaning.
An attribute should be defined for each data item that should be known about each symbol, after the lexical and syntactical analysis of a sentence in order to do the static semantic analysis and its translation or processing.

See also: Inherited attributes, Sinthesized attributes

Go up


A B C D E F G H I J K L M N O P Q R S T U V W X Y Z