introduction to BNF, concrete syntax trees

Hi,

I'm just starting to look at BNF. I have to take a simple expression
like:

          (A + B * C) * D

and create a concrete syntax tree of it. Before I start writing my
application to parse the above, I need to understand how to do this on
a piece of paper. My first thought is to tokenize (by whitespace) every
component of the statement, then label its type. I have 3 types to
choose from:

f = factor
t = term
e = expression

with the following rules:

expression ::= exp "+" exp |
                                            exp "-" exp |
                                            term

term ::= term "*" factor |
                          term "\" factor |
                          factor

factor ::= number |
                            identifier |
                            "(" expression ")"

so it must be possible to keep looping through the tokens, merging
adjacent pairs that follow the above rules until I end up with one node
right? (more than one node would indicate an error in the expression?).

So my first pass would look like this:

                          f
                          |
----------------------------------
| |
| f e f t f | t f
| | | | | | | | |
( A + B * C ) * D

now I have to pass through again to try merging nodes I suppose. So the
first thing to look at is if I can merge any adjacent terms with
factors which would give me:

                          f
                          |
----------------------------------
| t | t
| | \ | | \
| f e f t f | t f
| | | | | | | | |
( A + B * C ) * D

pass through again I guess and try merging adjacent factors and terms
again. I am a bit confused here though. The A is just sitting there
unable to merge with anyone. But it can simply itself down to a term
right? So do I just now label it a term or leave it alone?

                              ------------ t ---
                            / \
                          f \
                          | \
---------------------------------- |
| t | |
| / | | |
| / t | t
| / | \ | | \
| f e f t f | t f
| | | | | | | | |
( A + B * C ) * D

Well I guess I just keep looping until there are no factors and terms
to merge. Then I can try merging adjacent terms and expressions:

                              ------------ t ---
                            / \
                          f \
                          | \
---------------------------------- |
| | |
| - e - | |
| / \ | |
| / t | |
| | / | | |
| | / t | t
| | / | \ | | \
| f e f t f | t f
| | | | | | | | |
( A + B * C ) * D

So again I'm not sure what to do with factors like the A that just have
been sitting there this whole time. Do I just keep simplying themselves
if possible from f -> t -> e?

Any advice would be great. A simple walk through of an expression like
A + B * C would be great.

Thanks,
Mark

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