Abstract semantic graph (original) (raw)
In computer science, an abstract semantic graph (ASG) or term graph is a form of abstract syntax in which an expression of a formal or programming language is represented by a graph whose vertices are the expression's subterms. An ASG is at a higher level of abstraction than an abstract syntax tree (or AST), which is used to express the syntactic structure of an expression or program.
| Property | Value |
|---|---|
| dbo:abstract | In computer science, an abstract semantic graph (ASG) or term graph is a form of abstract syntax in which an expression of a formal or programming language is represented by a graph whose vertices are the expression's subterms. An ASG is at a higher level of abstraction than an abstract syntax tree (or AST), which is used to express the syntactic structure of an expression or program. ASGs are more complex and concise than ASTs because they may contain shared subterms (also known as "common subexpressions"). Abstract semantic graphs are often used as an intermediate representation by compilers to store the results of performing common subexpression elimination upon abstract syntax trees. ASTs are trees and are thus incapable of representing shared terms. ASGs are usually directed acyclic graphs (DAG), although in some applications graphs containing cycles may be permitted. For example, a graph containing a cycle might be used to represent the recursive expressions that are commonly used in functional programming languages as non-looping iteration constructs. The mutability of these types of graphs, is studied in the field of graph rewriting. The nomenclature term graph is associated with the field of term graph rewriting, which involves the transformation and processing of expressions by the specification of rewriting rules, whereas abstract semantic graph is used when discussing linguistics, programming languages, type systems and compilation. Abstract syntax trees are not capable of sharing subexpression nodes because it is not possible for a node in a proper tree to have more than one parent. Although this conceptual simplicity is appealing, it may come at the cost of redundant representation and, in turn, possibly inefficiently duplicating the computation of identical terms. For this reason ASGs are often used as an intermediate language at a subsequent compilation stage to abstract syntax tree construction via parsing. 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. (en) В информатике граф абстрактной семантики (ГАС) называется структура данных, используемая для представления или извлечения семантики выражения на формальном языке (например, на языке программирования). Граф абстрактной семантики — это более высокий уровень абстракции, чем дерево абстрактного синтаксиса (ДАС), которое используется для описания синтаксической структуры выражения или программы. Граф абстрактной семантики обычно конструируется из дерева абстрактного синтаксиса процессом обогащения и абстрагирования. Обогащением может быть, например, добавление обратных указателей, рёбер из вершины идентификатора (где используется переменная) в вершину, соответствующую объявлению этой переменной. Абстрагирование может включать удаление деталей, которые нужны только для синтаксического, но не семантического анализа. (ru) |
| dbo:wikiPageExternalLink | http://www.citeulike.org/user/hayashi/article/259537 http://www.swag.uwaterloo.ca/cppx/old_cppx_site/ https://web.archive.org/web/20080117121308/http:/www.citeulike.org/user/hayashi/article/259537 http://citeseer.ist.psu.edu/devanbu96generating.html |
| dbo:wikiPageID | 1137033 (xsd:integer) |
| dbo:wikiPageLength | 7557 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1087568871 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Programming_languages dbr:Parsing dbr:Cycle_(graph_theory) dbr:Variable_(programming) dbr:Intermediate_representation dbr:Compiler dbr:Compilers dbr:Name dbr:Graph_(data_structure) dbr:Graph_(discrete_mathematics) dbr:Common_subexpression_elimination dbr:Computer_science dbr:Identifier dbr:Linguistics dbr:Edge_(graph_theory) dbr:Formal_language dbr:Graph_rewriting dbr:Iteration dbr:Logical_consequence dbr:Functional_programming_language dbr:Term_(logic) dbr:Abstract_syntax dbr:Abstract_syntax_tree dbr:Abstraction_(computer_science) dbc:Formal_languages dbc:Graph_data_structures dbr:Syntax dbr:Code_refactoring dbr:Directed_acyclic_graph dbr:Intermediate_language dbr:Recursive dbr:Expression_(computer_science) dbr:Loop_(computing) dbr:Programming_language dbr:Semantic_Web dbr:Back-pointer dbr:Tree_(computer_science) dbr:Semantic_Grid dbr:Ontology_(computer_science) dbr:Abstract_syntax_trees dbr:Program_(computer_science) dbr:Declaration_(computer_science) dbr:Type_systems |
| dbp:wikiPageUsesTemplate | dbt:Cite_conference dbt:Cite_document dbt:Cite_web dbt:Clarify dbt:Reflist dbt:Formalmethods-stub dbt:Semantics |
| dct:subject | dbc:Formal_languages dbc:Graph_data_structures |
| gold:hypernym | dbr:Form |
| rdf:type | yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:Communication100033020 yago:DataStructure105728493 yago:Language106282651 yago:PsychologicalFeature100023100 yago:WikicatGraphDataStructures yago:Structure105726345 yago:WikicatFormalLanguages |
| rdfs:comment | In computer science, an abstract semantic graph (ASG) or term graph is a form of abstract syntax in which an expression of a formal or programming language is represented by a graph whose vertices are the expression's subterms. An ASG is at a higher level of abstraction than an abstract syntax tree (or AST), which is used to express the syntactic structure of an expression or program. (en) В информатике граф абстрактной семантики (ГАС) называется структура данных, используемая для представления или извлечения семантики выражения на формальном языке (например, на языке программирования). Граф абстрактной семантики — это более высокий уровень абстракции, чем дерево абстрактного синтаксиса (ДАС), которое используется для описания синтаксической структуры выражения или программы. (ru) |
| rdfs:label | Abstract semantic graph (en) Абстрактный семантический граф (ru) |
| owl:sameAs | freebase:Abstract semantic graph yago-res:Abstract semantic graph wikidata:Abstract semantic graph dbpedia-hr:Abstract semantic graph dbpedia-ru:Abstract semantic graph https://global.dbpedia.org/id/3EwEz |
| prov:wasDerivedFrom | wikipedia-en:Abstract_semantic_graph?oldid=1087568871&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Abstract_semantic_graph |
| is dbo:wikiPageDisambiguates of | dbr:ASG |
| is dbo:wikiPageWikiLink of | dbr:List_of_computing_and_IT_abbreviations dbr:Index_of_philosophy_articles_(A–C) dbr:Data_cube dbr:ASG dbr:Abstract_syntax_tree dbr:SourceMeter dbr:Universal_Networking_Language dbr:Semantic_network |
| is foaf:primaryTopic of | wikipedia-en:Abstract_semantic_graph |