How do I reduce my parse tree into an abstract syntax tree?

Question

What are the general strategies for reducing a parse tree (ie. concrete syntax tree) into an abstract syntax tree?

For example, I have the following grammar rule:

statement_list : statement
               | statement_list statement

which, if left as a parse tree, will generate fanning output that looks like

program
        statement_list
                statement_list
                        statement
                                definition
                                        p_type
                                        assignment
                statement
                        definition
        statement
                assign
                        assignment

If I concatenate the children of each node (since a statement list has no inherent meaning after parsing), I can achieve the following

program
        definition
                p_type
                assignment
        definition
        assign
                assignment

This worked well - however, I'm unaware of any "rules" for doing this. Are there specific grammar rules I should be looking to simplify? Is it a matter of feel, or is there a more mechanistic process?

Fecula

You can go for squishy "look and feel" but that mostly a lot of work. You can do this essentially mechanically by removing the nodes that you can regenerate using the grammar. See https://mcmap.net/q/82595/-what-is-the-difference-between-an-abstract-syntax-tree-and-a-concrete-syntax-tree – Univalence

Answer 1

It's not a matter of "feel". An abstract syntax tree depends on the meaning (semantics) of what's been parsed, and I think these would be the rules:

1. Remove nodes for tokens that don't add meaning. Those are intermediate keywords (like "then"), separators (like comma) and brackets (like parenthesis).
2. Promote meaningful tokens (like "if") to be the parent of other tokens in the same rule.

There's no single recipe. It depends on what the phrases in the target language mean.

Floro

I appreciate the answer, but it feels like you're contradicting yourself. You say that "It's not a matter of 'feel'" but your rules depend on the language. If there were some metrics to go by then I would agree it's not a matter of feel, but as it stands it certainly feels that way. – Fecula

I'll admit any day that design (language design in particular) is 50/50 engineering/feel. Is that any good? – Floro

Yes, of course, sorry - I forgot to come back to this question. Thanks for the help. – Fecula