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.
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.
Assembly
Soon...
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.
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