Re: concrete vs. abstract syntax trees

eliben wrote:
> I'm trying to nail down the difference between concrete and abstract
> syntax trees. In my C parser (http://code.google.com/p/pycparser/) I
> construct an AST directly from the parser (which uses the yacc-like
> PLY Python module), and I'm not sure where the concrete syntax tree is
> in that process.


This link says that a "concrete syntax tree" is the same thing as parse
tree: http://en.wikipedia.org/wiki/Parse_tree


The parse tree, a function of the grammar only, contains the details of
the grammar components, and is what the grammar actions construct
(abstractly, in the most general construction). By contrast, the AST
just retains (by choice of the implementer) the parts important for
translation, by limiting the construction in the explicitly implemented
actions. For example, the expression a + b*c might be represented by the AST
                +
              / \
            a *
                  / \
                b c
The parse tree, for a grammar E -> T | E + T, T -> i | T * i, is
                E
              /|\
            E + T
            | /|\
            T T * i
            | |
            i i
where actions of the token i return different values a, b, c from the lexer.


      Hans Aberg

Return to the comp.compilers page.
Search the comp.compilers archives again.