0

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?

2

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

0

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.

  • The more widely-used term is "parse tree". – Jörg W Mittag Feb 23 at 10:44
  • I guess there are some parsers that want to generate the exact same text as was passed, e.g. semantical reformatting in an IDE or modifying a user-written configuration file while preserving comments and indentation the user put in there – marstato Feb 23 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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