What is the difference between an Abstract Syntax Tree and a Concrete Syntax Tree?

by

A concrete syntax tree represents the source text exactly in parsed form. In general, it conforms to the context-free grammar defining the source language.

However, the concrete grammar and tree have a lot of things that are necessary to make source text unambiguously parseable, but do not contribute to actual meaning. For example, to implement operator precedence, your CFG usually has several levels of expression components (term, factor, etc.), with the operators connecting them at the different levels (you add terms to get expressions, terms are composed of factors optionally multipled, etc.). To actually interpret or compile the language, however, you don’t need this; you just need Expression nodes that have operators and operands. The abstract syntax tree is the result of simplifying the concrete syntax tree down to the things actually needed to represent the meaning of the program. This tree has a much simpler definition and is thus easier to process in the later stages of execution.

You usually don’t need to actually build a concrete syntax tree. The action routines in your YACC (or Antlr, or Menhir, or whatever…) grammar can directly build the abstract syntax tree, so the concrete syntax tree only exists as a conceptual entity representing the parse structure of your source text.

More Related Contents:

  1. The Possibility of a “True” Quiz Generator [closed]
  2. Parse error: syntax error, unexpected T_STRING in app/design/frontend/base/default/template/catalog/product/new.phtml on line 37 [closed]
  3. Writing a parser like Flex/Bison that is usable on 8-bit embedded systems
  4. How to parse freeform street/postal address out of text, and into components
  5. Practical difference between parser rules and lexer rules in ANTLR?
  6. lexers vs parsers
  7. Parsing command line arguments in R scripts
  8. Import CSV file with mixed data types
  9. How does the ANTLR lexer disambiguate its rules (or why does my parser produce “mismatched input” errors)?
  10. How would you go about parsing Markdown? [closed]
  11. Malformed String ValueError ast.literal_eval() with String representation of Tuple
  12. Handling extra operators in Shunting-yard
  13. How can error reporting in grammars be improved?
  14. How to Traverse an NLTK Tree object?
  15. What’s the difference between parse trees and abstract syntax trees (ASTs)?
  16. Difference between constituency parser and dependency parser
  17. Looking for a clear definition of what a “tokenizer”, “parser” and “lexers” are and how they are related to each other and used?
  18. Converting a hexadecimal string to a decimal integer
  19. Reached end of file while parsing compilation error
  20. Use Scala parser combinator to parse CSV files
  21. Problem with parse a LocalDateTime using java 8
  22. How to identify whether a grammar is LL(1), LR(0) or SLR(1)?
  23. Is it a Lexer’s Job to Parse Numbers and Strings?
  24. How to manually parse a floating point number from a string
  25. Parse URL in shell script
  26. Parse clock time in java 8
  27. How to parse data in JSON format?
  28. How to convert jsonString to JSONObject in Java
  29. How to parse XML using vba
  30. How to provider user with autocomplete suggestions for given boost::spirit grammar?

Leave a Comment