Re: about syntax trees

On 21 Mar, 04:04, "grable" <grab...@gmail.com> wrote:
> 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))


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_trabajo/parser/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_trabajo/parser/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,

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