Talk:Abstract syntax tree

Computing Start‑class Mid‑importance

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-importance on the project's importance scale.

Wording

"...since in an AST the grouping of operands is explicit in the tree structure." Wouldn't it make more sense to say "implicit."?

Please everybody sign posts adding 4 ~'s. It's implicit in the source code, where it is implied by the precedence and associativity rules, plus the arity of every operator (whether it is unary, binary, etc.). In the AST it is explicit: each operand node groups the operands it has as sons. --euyyn 23:37, 18 June 2006 (UTC)[reply]

Has anyone else ever thought of calling it the 'internal reptreesentation ...'?

NO

Confused about context

I'm afraid I'm a bit confused by the article. Does a parser create an abstract syntax tree as part of the compilation process for each individual program? That is, will there be a different abstract syntax tree for every C program I compile? Or is there one "abstract syntax tree" for the language of C, like with attribute grammars? -- Creidieki 18:07, 10 November 2005 (UTC)[reply]

Yes, the AST is created as part of the compilation process, so each different program has a different AST --Pezezin 11:53, 9 March 2006 (UTC)[reply]

Shunting yard algorithm

In the see also section, I just added a wikilink to Shunting yard algorithm. Though this currently redirects to Reverse Polish notation, it had already been suggested to split Shunting yard algorithm to a separate page. DFH 19:05, 23 August 2006 (UTC)[reply]

"Syntax tree"?

Syntax tree currently redirects here, but the term applies equally to concrete syntax trees, i.e. parse trees. As a linguist myself, may I just say: yo, comp sci kids, step off. By which I mean that the validity of this particular redirect should be carefully evaluated and appropriate disambiguation should be put into place after appropriate deliberation. Thank you. 69.140.12.199 05:32, 20 January 2007 (UTC)[reply]

Although you might assume "syntax tree" is an umbrella term for abstract and concrete syntax trees, I read the Dragon book carefully (which I think is the definitive book on the subject) and it states that

Syntax tree and Abstract syntax tree are synonymous
Parse tree and Concrete syntax tree are synonymous

I recently edited both articles to make this clear. Egriffin 15:55, 30 November 2007 (UTC)[reply]

Why would the dragon book be "definitive" on that distinction? The authors are not linguists, they simply borrow certain linguistic concepts, and there are many other books. HenkeB (talk) 17:26, 13 December 2008 (UTC)[reply]

So what is the difference between abstract and concrete syntax trees? Is the distinction made in [1] universally accepted? Rp (talk) 16:19, 16 May 2008 (UTC)[reply]

Between concrete and abstract syntax: yes; between parse trees and syntax trees: no, these are pretty lose terms. HenkeB (talk) 17:37, 13 December 2008 (UTC)[reply]

WikiProject Philosophy?

Since this is a topic in computer science, and is not related to Philosophy, I believe it should be removed from WikiProject Philosophy. Biomedtechnology 20:31, 26 September 2007 (UTC)[reply]

Link to "Tutorial"?

There is a link to a socalled "Tutorial", which I don't see much tutorial value in, it looks more like a proposal for a standard for ASTs (which to my mind seems rather futile). I'd think this article would actually be improved if the link was removed, but someone must have put it there for some reason? --Lasse Hillerøe Petersen (talk) 21:47, 12 August 2012 (UTC)[reply]

Design Patterns

This section takes it as a given or at least suggests that ASTs should be implemented in an object-oriented fashion, and, on the basis of this assumption, suggests the use of the Visitor pattern. However, this pattern is nothing but boilerplate to make up for the lack of pattern matching. If anything, this suggests object orientation is perhaps not the best paradigm for implementing ASTs.

Most grammars meant to be mechanically parsed are deterministically context-free and can be defined using Backus–Naur Form or Extended Backus–Naur Form. The former maps directly to algebraic data types. The latter also maps to algebraic data types, but takes a given that the standard library provides an option and a list type, which in turn can also be implemented using algebraic data types. So, perhaps a better suggestion would be the use of algebraic data types as the backbone for the implementation of ASTs. Eduardo León (talk) 21:35, 1 May 2013 (UTC)[reply]