# The origin and the meaning of “Abstract Syntax Tree”

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.

• 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. – fade2black Oct 3 '17 at 8:50
• 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. – Alexey Oct 3 '17 at 9:44
• 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? – Alexey Oct 5 '17 at 5:49
• 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 – Björn Lindqvist Oct 13 '17 at 16:23
• @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. – Alexey Oct 14 '17 at 10:32