Abstract semantic graph
Encyclopedia
In computer science
, an abstract semantic graph
(ASG) is a data structure
used in representing or deriving the semantics
of an expression in a formal language
(for example, a programming language
). An abstract semantic graph is a higher level abstraction than an abstract syntax tree
(or AST), which is used to express the syntactic structure
of an expression or program.
An abstract semantic graph is typically constructed from an abstract syntax tree by a process of enrichment and abstraction. The enrichment can for example be the addition of back-pointers, edges from an identifier
node (where a variable
is being used) to a node representing the declaration
of that variable. The abstraction can entail the removal of details which are relevant only in parsing
, not for semantics.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, an abstract semantic graph
Graph (data structure)
In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
(ASG) is a data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
used in representing or deriving the semantics
Formal semantics of programming languages
In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation...
of an expression in a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
(for example, a programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
). An abstract semantic graph is a higher level abstraction than an abstract syntax tree
Abstract syntax tree
In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...
(or AST), which is used to express the syntactic structure
Syntax
In linguistics, syntax is the study of the principles and rules for constructing phrases and sentences in natural languages....
of an expression or program.
An abstract semantic graph is typically constructed from an abstract syntax tree by a process of enrichment and abstraction. The enrichment can for example be the addition of back-pointers, edges from an identifier
Identifier
An identifier is a name that identifies either a unique object or a unique class of objects, where the "object" or class may be an idea, physical [countable] object , or physical [noncountable] substance...
node (where a variable
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
is being used) to a node representing the declaration
Declaration (computer science)
In programming languages, a declaration specifies the identifier, type, and other aspects of language elements such as variables and functions. It is used to announce the existence of the element to the compiler; this is important in many strongly-typed languages that require variables and their...
of that variable. The abstraction can entail the removal of details which are relevant only in parsing
Parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
, not for semantics.
External links
- Article "CPPX - C/C++ Fact Extractor" by Tom Dean
- Paper "Generating Testing and Analysis Tools with Aria" by Premkumar T. Devanbu, David S. Rosenblum and Alexander L. Wolf
- Paper "Towards Portable Source Code Representations Using XML" by Evan Mamas and Kostas Kontogiannis
- Paper "Dex: a semantic-graph differencing tool for studying changes in large code bases"