Generating an AST directly vs. converting from a CST

Question

As I understand it, some parsers generate an abstract syntax tree on the fly, while others first generate a concrete syntax tree and then convert it. What are the tradeoffs between the two? Is there some way to tell what will be easier given a particular grammar?

Answer 1

Essentially, a concrete syntax tree is sensitive to the grammar of the language you are parsing, while an abstract syntax tree (AST) is not.

This allows an AST to provide flexibility that a concrete syntax tree cannot. For example, LLVM uses an AST to provide support for arbitrary programming languages, not just one.

Unlike concrete syntax trees, AST's support the use of metadata, such as annotations, properties and source code positioning information (useful for printing meaningful error messages). AST's do not contain inessential punctuation such as semicolons and braces. AST's embody the essence of a language, not its grammatical features; they enable useful tools like code analysis, reflection and code generation.

https://en.wikipedia.org/wiki/Abstract_syntax_tree
https://en.wikipedia.org/wiki/Parse_tree

Answer 2

This is opinionated, but probably if there is no requirement to exactly generate the source back then there is no need to preserve the unsignificant details in the resulted syntax tree.

It should be noted that quite often there is a separated step of lexical analysis which breaks text into tokens, and that step already may discard some details even before parsing step starts.

PS: I should say I have never thought what the "abstract" in AST could mean, and did not oppose it to any "concrete" kind of syntax tree. Maybe CST is not that widely used term.

Answer 3

What are the tradeoffs between the two?

When you have two separate structures, CST and an AST, you're maintaining more code than just using an AST. Generally, you'll want to have a reason for the cost of maintaining an additional data structure. Here are some that come to mind:

• The CST is automatically generated from a parser tool that's being used.
• You're using Bison and would prefer not to implement very much logic with the rules of the grammar.
• The language has complexities that require multiple passes on the source code.

Let me just give an example of the last bullet point. Suppose you have a C-like language that supports out-of-order function declarations. Here's what an example might look like of the source code.

int
foo(int a)
{
  return bar(a + 1);
}

int
bar(int b)
{
  return b + 2;
}

When the parser reaches the function call bar(a + 1), all it knows is that it sees something that looks like a function call. It doesn't know what function, though. At this point you would either:

• construct an AST-like function call and assign a field that indicates the call is unresolved (this would make type checking difficult, too)
• construct a parse tree containing the name token and expression list, and then later build a AST object when you can query the parse tree for a function declaration called bar.

If you prefer the second option, you'd create a concrete syntax tree.

Is there some way to tell what will be easier given a particular grammar?

Prefer using just an AST for simple grammars, and consider using a CST for more complex ones if the need arises. I think, in general, multi pass parsing requires a use of a CST. Just remember, the extra data structure does not come for free. You mostly rely on experience and/or good judgement to determine if it's worth the cost.

You can sometimes get away with using just one representation for even moderately complex grammars. Take for example, C++.

C++ has an extremely complex grammar and Clang basically uses a parse tree to represent it in memory. The documentation calls it an AST, but if you take a look at an AST dump from Clang, you'll see that it looks more like a concrete syntax tree. Here's an example C source file:

int
add_two_integers(int a, int b)
{
  return (a + b);
}

And here's the AST for it, from Clang:

`-FunctionDecl 0x15a4ee0 <example.c:1:1, line:5:1> line:2:1 add_two_integers 'int (int, int)'
  |-ParmVarDecl 0x15a4d88 <col:18, col:22> col:22 used a 'int'
  |-ParmVarDecl 0x15a4e08 <col:25, col:29> col:29 used b 'int'
  `-CompoundStmt 0x15a5098 <line:3:1, line:5:1>
    `-ReturnStmt 0x15a5088 <line:4:3, col:16>
      `-ParenExpr 0x15a5068 <col:10, col:16> 'int'
        `-BinaryOperator 0x15a5048 <col:11, col:15> 'int' '+'
          |-ImplicitCastExpr 0x15a5018 <col:11> 'int' <LValueToRValue>
          | `-DeclRefExpr 0x15a4fd8 <col:11> 'int' lvalue ParmVar 0x15a4d88 'a' 'int'
          `-ImplicitCastExpr 0x15a5030 <col:15> 'int' <LValueToRValue>
            `-DeclRefExpr 0x15a4ff8 <col:15> 'int' lvalue ParmVar 0x15a4e08 'b' 'int'

You'll notice that:

• All the source code locations are stored
• Is there anything really abstract about, say, ParenExpr? Not really. That's concrete syntax. There's never really a point in having that kind of expression in an AST.

So the take away is that you should try to use just one data structure, and use two if there's no other practical way.