How to construct an abstract syntax tree

问题:

I have a general idea of what an AST is, but I want to know how to construct one.

If you're given a grammar and a parse tree, how do you construct the AST?

How do you do it if you're given a grammar and an expression?

回答1:

Well, first off, the grammar is used to construct a parse tree from an expression. So if you already have a parse tree, you don't need the grammar.

Depending on how much work your parser does, the resulting tree that is formed from parsing an expression could already be an abstract syntax tree. Or it could be a simple parse tree which requires a second pass to construct the ast.

To construct the parse tree from a grammar and an expression, you would first have to convert your grammar into working code. Typically, you would split the work into a tokenizer which splits the input stream representing the expression into a list of tokens, and a parser which takes the list of tokens and constructs a parse tree\ast from it.

So the expression 1 + 2*(3+4) might be split into a list of tokens like this:

1 - int
+ - add_operator
2 - int
* - mul_operator
( - lparen
3 - int
+ - add_operator
4 - int
) - rparen

The first column is the actual text value. The second represents the token type. These tokens are fed into the parser, which is built from your grammar and recognizes the tokens and builds the parse tree.

So, how does one write the lexical tokenizer and the actual parser? You could roll your own by hand. Or, more commonly, use a parser generator like coco or antlr or lex/yacc. These tools take a description of your grammar and generate the code for a tokenzier and parser. (Code generators exist for most popular languages and some unpopular ones as well.)

How you construct your parser depends heavily on what language you use. How you would write a parser in Haskell is entirely different from how you would in, say, C.

• Here's a tutorial that shows you how to build your own recursive descent parser.

• Coco is a parser generator for various languages, which also comes with documentation on how to get started.

• If Python's your thing, then pyparsing maybe for you.

回答2:

I will answer this from a general perspective, without trying to talk about lexers and parsers.

A parse tree contains non-terminal symbols that are part of a context free grammar, and show the chain of productions to obtain a string consisting of terminal symbols, either recursively or not. So when you have the parse tree you don't need the grammar - you can derive the grammar from the parse tree.

An AST does not contain any non-terminal symbols. It only contains symbols.

Example:

 E
 |
 E + T
 |   |
 T   M * M
 |   |   |
 M   a   b
 |
 a

Which is a very quick version of showing a+a*b. Note, the way the abstract syntax tree is interpreted depends on the precedence of the tree, what type of traversal you do (in-order, pre-order, post-order) This would be a general function you code into your search tree. However, in general, the AST for that parse tree might look like this:

   +
 |   |
 a   * 
    | |
    a b