Abstract syntax

In computer science, the abstract syntax of data is its structure described as a data type (possibly, but not necessarily, an abstract data type), independent of any particular representation or encoding.[1] This is particularly used in the representation of text in computer languages,[2] which are generally stored in a tree structure as an abstract syntax tree. Abstract syntax, which only consists of the structure of data, is contrasted with concrete syntax, which also includes information about the representation. For example, concrete syntax includes features like parentheses (for grouping) or commas (for lists), which are not included in the abstract syntax, as they are implicit in the structure.

Abstract syntaxes are classified as first-order abstract syntax (FOAS), if the structure is abstract but names (identifiers) are still concrete (and thus requires name resolution), and higher-order abstract syntax, if the names themselves are abstract.[3]

  1. ^ Fiore, M.; Plotkin, G.; Turi, D. (1999). "Abstract syntax and variable binding". Proceedings. 14th Symposium on Logic in Computer Science (Cat. No. PR00158). pp. 193–202. doi:10.1109/LICS.1999.782615. ISBN 0-7695-0158-3. S2CID 7384052. Retrieved 2023-11-02.
  2. ^ "ASTLOG: A language for examining abstract syntax trees". DSL'97: Proceedings of the Conference on Domain-Specific Languages on Conference on Domain-Specific Languages (DSL), 1997. USENIX Association. 15 October 1997. p. 18.
  3. ^ Pfenning, F.; Elliott, C. (1988-06-01). "Higher-order abstract syntax". ACM SIGPLAN Notices. 23 (7): 199–208. doi:10.1145/960116.54010. ISSN 0362-1340.