0
$\begingroup$

This question is closely related to Does an abstract syntax tree have to be a tree? and is partially answered there, but I would like to be more precise and to have more concise answers.

  1. What is the origin of the term?

  2. Are there any formal definitions of AST?

  3. If I understand correctly the spirit of the use of "AST" term, it is a misnomer: an AST is any combinatorial object or datum that one tries to represent by strings of characters using more or less simple syntax that should ideally reflect the internal structure of the object/datum. For example, in first-order logic and in lambda calculus, expressions like $(\forall x)(x = x)$ or $(\lambda x.x)$ do not really represent trees because bound variables introduce loops. Do I understand correctly?

Basically, I broke up here in simpler pieces a single question: What is AST? Without answering parts (1) and (2) the answer will probably be incomplete or hard to verify, and if (1) and (2) are answered, an answer to (3) probably should follow.

Update

I have realized that it is not the "syntax tree" that is abstract, but the syntax. This clarifies the terminology to me and makes this question less relevant. Basically, I parsed "abstract syntax tree" incorrectly.

I also provided an answer to the related question.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ You are asking three different questions while the rule is to ask one question per post. Furthermore, Wikipedia gives an unambiguous definition of AST plus reference, further reading, and external links. Did you read it? The "Dragon" book (both editions) also provides a good explanation of AST with examples. $\endgroup$
    – fade2black
    Oct 3, 2017 at 8:50
  • $\begingroup$ These questions are related and i suppose that with some luck they could be answered all in one paragraph. I remember having looked up the term in different places, including the Dragon Book, and found no formal non-circular and meaningful definition. This is from Wikipedia: "abstract syntax of data is its structure described as a data type". There are no clear references to the origin of the term. $\endgroup$
    – Alexey
    Oct 3, 2017 at 9:44
  • $\begingroup$ By the way, I have looked into two papers by Knuth: the one where he invented the LR parsing and another "The Genesis of Attribute Grammars", and he never mentions "abstract syntax" (but he does mention parse trees or derivation trees). Could it be for a good reason? $\endgroup$
    – Alexey
    Oct 5, 2017 at 5:49
  • 1
    $\begingroup$ For the origin of the term I found this quora answer: quora.com/Who-invented-the-abstract-syntax-tree However, it is clear from the article that is now online (probably wasn't in 2013), that McCarthy did not invent the AST: dtic.mil/docs/citations/AD0785050 $\endgroup$
    – Björn Lindqvist
    Oct 13, 2017 at 16:23
  • $\begingroup$ @BjörnLindqvist, thanks for the links. The article by McCarthy looks close to what i am looking for, i'll need to look into it. What in that article made you think that McCarthy did not invent abstract syntax or AST? By the way, it is not clear to me if the author of Quora answer understood the question, because he said that Knuth called AST "derivation trees", while derivation trees in Knuth's articles are concrete syntax trees, as i understand. $\endgroup$
    – Alexey
    Oct 14, 2017 at 10:32

1 Answer 1

Reset to default
1
$\begingroup$

You are asking three questions. I will answer one.

I don't think "abstract syntax tree" is a misnomer. It aims to represent the syntax of the expression. It is not claimed to represent all of the meaning (semantics) of the expression. The issue with bound variables that you mention relates to semantics rather than syntax.

Also, remember that names are merely that: references to some concept, to serve as an aid to communication. Sometimes the concept is subtle or nuanced enough that no name is going to fully represent all the complexities of the concept, so we choose the best name we can (while keeping it fairly short). And a name is just an aid to communication, so not all concepts have a fully precise, rigorous definition -- if it is used in a way that aids understanding and facilitates communication, that is often OK.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Also, "abstract" here is probably mostly used to differentiate from "concrete" syntax trees aka parse trees. $\endgroup$
    – Raphael ♦
    Oct 3, 2017 at 17:09
  • $\begingroup$ So, what is the syntax of an expression if you do not mean by this the "concrete syntax"? (For me syntax is the "concrete syntax", or if i try to think of some generalisation of it, i see no reason that there be no loops...) $\endgroup$
    – Alexey
    Oct 3, 2017 at 19:08
  • $\begingroup$ Of course my question was not about the name, but about the concept. As to semantics, so far it looks to me like "abstract syntax" is evoked in semantic contexts. $\endgroup$
    – Alexey
    Oct 14, 2017 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.