Home > Archive > Compilers > March 2007 > about syntax trees
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
about syntax trees
|
|
| chinlu chinawa 2007-03-19, 10:16 pm |
| Hello,
I'm relatively new to parsing. I've managed to code a
recursive-descent ll(1) parser in c (thus, a
stack/table based one). My question is about syntax
trees.
If I trace each accepting operation with a printf,
this is what I get for the expression: a+b*c
accept on: a
accept on: +
accept on: b
accept on: *
accept on: c
However I can see ast's being more like this all over
the place:
+
/|\
b | a
*
c
But I cannot think of a way you get exactly this, any
pointers or advises? thanks so much.
| |
|
|
| grable 2007-03-21, 5:45 am |
| On Mar 19, 8:40 pm, chinlu chinawa <chinluchin...@yahoo.co.uk> wrote:
> Hello,
>
> I'm relatively new to parsing. I've managed to code a
> recursive-descent ll(1) parser in c (thus, a
> stack/table based one). My question is about syntax
> trees.
>
> If I trace each accepting operation with a printf,
> this is what I get for the expression: a+b*c
>
> accept on: a
> accept on: +
> accept on: b
> accept on: *
> accept on: c
>
> However I can see ast's being more like this all over
> the place:
>
> +
> /|\
> b | a
> *
> c
>
> But I cannot think of a way you get exactly this, any
> pointers or advises? thanks so much.
You could use something like this:
struct node {
int tag;
char* value;
struct node* left;
struct node* right;
}
struct node a = { ID, "a", NULL,NULL };
struct node b = { ID, "b", NULL,NULL };
struct node b = { ID, "c", NULL,NULL };
struct node op2 = { BINOP, "*", &b, &c };
struct node op1 = { BINOP, "+", &a, &op2 };
Resulting in a list like this:
(+ a (* b c))
| |
| Chinlu 2007-03-23, 10:05 pm |
| On 21 Mar, 04:04, "grable" <grab...@gmail.com> wrote:
> On Mar 19, 8:40 pm, chinlu chinawa <chinluchin...@yahoo.co.uk> wrote:
>
>
>
>
>
>
>
>
>
>
> You could use something like this:
>
> struct node {
> int tag;
> char* value;
> struct node* left;
> struct node* right;
>
> }
>
> struct node a = { ID, "a", NULL,NULL };
> struct node b = { ID, "b", NULL,NULL };
> struct node b = { ID, "c", NULL,NULL };
> struct node op2 = { BINOP, "*", &b, &c };
> struct node op1 = { BINOP, "+", &a, &op2 };
>
> Resulting in a list like this:
> (+ a (* b c))
Hello, thanks so much for your comments. Yes, I somewhat managed to
output a syntax-tree, but as soon as I wanted to go further and output
a parse-tree got stuck again.
I've uploaded the parser I've written, which implements what's
explained on the dragon book (chapter 4 - 2ed):
http://es.geocities.com/ucho_trabaj...er/parser.c.txt
(if anyone wants to look a it, only about the first 50 lines within
the main() function are relevant). I've also uploaded the output as
given by the debugging stuff I made it with:
http://es.geocities.com/ucho_trabajo/parser/output.txt
as well as an image of what the dragon book says the parse-tree for
this expression (a+b*c)
should be:
http://es.geocities.com/ucho_trabaj.../parse_tree.png
Now my question is, how do you guys use to output this parse-tree
programatically?, I'm not really understanding the book on this
regard, and though I've been trying and looking for info on this
haven't achieved it so far.
Beacuse this grammar has got three items max per rhs, we can see on
the image above that a production-node can have three outputs, but
what if the grammar used has more than three?. This is not possible to
mimic (or not exactly as the image shows) with a double linked list,
though it could with a single one.
As per how to output the parse-tree I've been thinking lately that I
could use a stack pushing and popping relevant nodes where to continue
adding nodes once filled a terminal one.
In any case, it could also happen that my implementaion of the parser
is a poorly implemented one (I haven't got any education on cs), so
any comments on either side will be much appreciated.
Best Regards,
| |
| leppoc@gmail.com 2007-03-23, 10:05 pm |
| > However I can see ast's being more like this all over
> the place:
>
> +
> /|\
> b | a
> *
> c
Hi,
A good idea is to use AST (Abstract Syntax Tree). To do so, make for
each type of Tree, a struct, or object.
e.g. in pseudo-code:
BinOp extends Tree {
Tree leftOperand
Tree rightOperand
Operator operator //+, -, *, /, % ....
}
IfThenElse extends Tree {
Tree condition
Tree thenPart
Tree elsePart
}
When you parse it with your recursive descent, you can almost directly
fill those trees.
Have Fun !
YC.
| |
| Hans-Peter Diettrich 2007-03-26, 8:32 am |
| leppoc@gmail.com wrote:
> A good idea is to use AST (Abstract Syntax Tree). To do so, make for
> each type of Tree, a struct, or object.
And don't forget to add an node type to the basic node structure, so
that a visitor can know who is who. An extended "operator" enum,
covering all node types, will be helpful.
> e.g. in pseudo-code:
>
> BinOp extends Tree {
> Tree leftOperand
> Tree rightOperand
> Operator operator //+, -, *, /, % ....
> }
>
> IfThenElse extends Tree {
> Tree condition
> Tree thenPart
> Tree elsePart
> }
>
> When you parse it with your recursive descent, you can almost directly
> fill those trees.
Trees should not be write-only. There exists no absolutely best
implementation for trees, but the list oriented approach (LISP...) IMO
is the most flexible one, with regards to postprocessing of trees.
DoDi
|
|
|
|
|