Describing a tree

Discussion in 'C Programming' started by Mok-Kong Shen, Jul 20, 2010.

  1. A possibly dumb question: Given a labeled or unlabeled tree
    (in the sense of graphs), how could one best use C to describe it?
    (I don't exactly know but have the impression that this might be
    rather simple in Lisp.)

    Thanks.

    M. K. Shen
    Mok-Kong Shen, Jul 20, 2010
    #1
    1. Advertising

  2. On Jul 20, 3:10 pm, Mok-Kong Shen <> wrote:
    > A possibly dumb question: Given a labeled or unlabeled tree
    > (in the sense of graphs), how could one best use C to describe it?
    > (I don't exactly know but have the impression that this might be
    > rather simple in Lisp.)
    >

    An informal and possibly bug-ridden specification of Lisp in C

    typedef struct cell
    {
    struct cell *next;
    struct cell *child;
    };

    typedef struct leaf
    {
    struct cell *next; /* set to null to indicate this is a leaf */
    void *symbol;
    };

    union conscell
    {
    struct cell;
    struct leaf;
    };

    union conscell nil;

    nil.leaf.next = 0;
    nil.leaf.symbol = 0;

    Basically you need two pointers for each node, and a hook to hang data
    off for the leaves. You need some way of flagging a leaf, so here we
    have the next pointer set to null. That means you need to set to "nil"
    to indicate termination.
    Malcolm McLean, Jul 20, 2010
    #2
    1. Advertising

  3. On 20 July, 13:10, Mok-Kong Shen <> wrote:

    > A possibly dumb question: Given a labeled or unlabeled tree
    > (in the sense of graphs), how could one best use C to describe it?


    what form is it in now or how are you going to enter it?

    /* tree.c */

    #include <stdio.h>

    typedef struct tree_tag
    {
    char *data;
    struct tree_tag *left;
    struct tree_tag *right;
    } Tree;


    void walk (Tree *tree)
    {
    if (tree != NULL)
    {
    printf ("%s ", tree->data);
    walk (tree->left);
    walk (tree->right);
    }
    }

    int main (void)
    {
    Tree yggdrasil[] =
    {
    {"red", &yggdrasil[1], &yggdrasil[2]},
    {"blue", &yggdrasil[3], &yggdrasil[4]},
    {"black", 0, 0},
    {"yellow", 0, 0},
    {"green", 0, 0}
    };

    walk (yggdrasil);
    return 0;
    }

    > (I don't exactly know but have the impression that this might be
    > rather simple in Lisp.)


    probably. But would you have to learn Lisp first? (not necessarily a
    bad idea). If you like s-exprs why not write a parser for them in C?
    Nick Keighley, Jul 20, 2010
    #3
  4. Richard Heathfield wrote:
    > Mok-Kong Shen wrote:
    >>
    >> A possibly dumb question: Given a labeled or unlabeled tree
    >> (in the sense of graphs), how could one best use C to describe it?

    >
    > I find it hard to disagree with you.
    >
    > What do you mean by "describe"? A data structure? A set of algorithms?
    >
    > What do you mean by "best"? Most widely popular? Most space-efficient?
    > Most time-efficient? Most flexible? (And if you mean most flexible, what
    > do you mean by "flexible"?...)
    >
    >> (I don't exactly know but have the impression that this might be
    >> rather simple in Lisp.)

    >
    >
    > Then why not do it in Lisp instead?


    I meant one could in Lisp (if my poor knowledge about Lisp doesn't
    betray me) write down the tree simply as a Lisp expression. Of course
    one could then process it in any way one likes. To your last question
    the answer is that I happen to be familiar a little bit more with C
    than with Lisp, so it's basically an issue of convenience to hope that
    similar simplicity were also possible in C.

    M. K. Shen
    Mok-Kong Shen, Jul 20, 2010
    #4
  5. On Jul 20, 4:24 pm, Mok-Kong Shen <> wrote:
    >
    > I meant one could in Lisp (if my poor knowledge about Lisp doesn't
    > betray me) write down the tree simply as a Lisp expression.
    >

    We can do this.

    You simply write a C function that accepts a character string, and
    returns a tree. The string contains a set of nested parentheses that
    specify the tree and the labels at its leaves. You then enter the
    trees in the C source file using an ordinary text editor. If the need
    to quote strings becomes a nuisance, you can read in the strings as
    data.
    Malcolm McLean, Jul 20, 2010
    #5
  6. Mok-Kong Shen <> writes:
    <snip>
    > I meant one could in Lisp (if my poor knowledge about Lisp doesn't
    > betray me) write down the tree simply as a Lisp expression.


    You can do this in C (modern C99 at least) like this:

    typedef struct node {
    const char *label;
    struct node *left, *right;
    } Node;

    /* and then inside a function such as main: */

    Node *my_tree =
    (Node){"root", &(Node){"left", 0, 0}, &(Node){"right", 0, 0}};

    This is not often done because C programs will typically have to process
    trees (or graphs) that are supplied as input data, not expressed
    literally in the code. It is trickier if the graph is not a tree, but
    that is true for Lisp as well (and you said you had a tree anyway).

    However, if language familiarity were not an issue, Lisp would the
    natural choice.

    --
    Ben.
    Ben Bacarisse, Jul 20, 2010
    #6
  7. On Tue, 20 Jul 2010, Ben Bacarisse wrote:

    > Mok-Kong Shen <> writes:
    > <snip>


    >> I meant one could in Lisp (if my poor knowledge about Lisp doesn't
    >> betray me) write down the tree simply as a Lisp expression.

    >
    > You can do this in C (modern C99 at least) like this:
    >
    > typedef struct node {
    > const char *label;
    > struct node *left, *right;
    > } Node;
    >
    > /* and then inside a function such as main: */
    >
    > Node *my_tree =
    > (Node){"root", &(Node){"left", 0, 0}, &(Node){"right", 0, 0}};


    Or, in C89,

    #include <stdlib.h>

    struct node
    {
    const char *label;
    struct node *left, *right;
    };

    static struct node *
    node(const char *label, struct node *left, struct node *right)
    {
    struct node *ret;

    ret = malloc(sizeof *ret);
    if (0 == ret) {
    abort();
    }
    ret->label = label;
    ret->left = left;
    ret->right = right;
    return ret;
    }

    int
    main(void)
    {
    struct node *root;

    root = node(
    "root",
    node("left", 0, 0),
    node("right", 0, 0)
    );
    return 0;
    }

    I think the relative order of two node() invocations is unspecified,
    except if there is a (recursive) ancestor-descendant relationship between
    the nodes constructed by said two invocations. For example, if we were to
    modify node() so that it prints "label", the order of "right" and "left"
    in the above would be unspecified. "root" would be printed in the end.

    Since function invocations don't overlap, you could avoid malloc() if you
    could ascertain a compile-time upper bound on the number of nodes:

    #define NNODES ((size_t)10)

    static struct node *
    node2(const char *label, struct node *left, struct node *right)
    {
    static struct node nodes[NNODES];
    static size_t used;
    struct node *ret;

    if (NNODES == used) {
    abort();
    }
    ret = nodes + used++;
    ret->label = label;
    ret->left = left;
    ret->right = right;
    return ret;
    }

    Finally, I think there might be an environmental limit on how deep you can
    nest the node() function calls... Yes, C89 5.2.4.1 "Translation limits"
    states, "32 nesting levels of parenthesized expressions within a full
    expression".

    lacos
    Ersek, Laszlo, Jul 20, 2010
    #7
  8. Mok-Kong Shen

    Gene Guest

    On Jul 20, 8:10 am, Mok-Kong Shen <> wrote:
    > A possibly dumb question: Given a labeled or unlabeled tree
    > (in the sense of graphs), how could one best use C to describe it?
    > (I don't exactly know but have the impression that this might be
    > rather simple in Lisp.)
    >
    > Thanks.
    >
    > M. K. Shen


    This is a brilliant question. Even in lisp there are many ways to do
    it. Which you choose depends on design goals and requirements. Some
    questions to consider:

    0. Does the tree have special structure (like a search tree, priority
    queue, or prefix tree)?
    1. How important is space efficiency? (Is the tree large compared to
    available memory?)
    2. How many children per node?
    3. Are children to be dynamically or statically identified/named?
    4. If the number of children varies, how widely?
    5. Is constant time access to parents required? Siblings?
    6. Are the data represented exogenously with respect to the tree?
    (I.e. is it already stored in another tree, so you only need to point
    to it?) Or will they be endogenous?
    7. Are tree nodes to be exogenous for some other data structure
    (pointed to by it)?
    8. Does the tree need to be persistent?
    9. Is a human-readable representation required?
    10. Do tree operations need to be atomic (in a multi-threading
    environment)?
    11. Do tree operations need to be transactions (in the database sense
    of commit/rollbacck)?
    12. Is it better to pre-allocate all tree storage or allocate on the
    fly? Is the max number of nodes limited?
    13. If the tree is ordered, do you need data ordinals?
    14. If the tree is for data access, does it need to be self-height-
    limiting or -balancing?
    15. Do tree operations need to be undoable?

    All these and others affect the "best" C representation. If you don't
    have many such criteria, then that's a criterion in itself. It
    alllows you can trade between simplicity and flexibility for future
    new requirements.

    If you narrow the question a bit, we can get to the details.
    Gene, Jul 20, 2010
    #8
  9. Gene wrote:

    > This is a brilliant question. Even in lisp there are many ways to do
    > it. Which you choose depends on design goals and requirements. Some
    > questions to consider:
    >
    > 0. Does the tree have special structure (like a search tree, priority
    > queue, or prefix tree)?
    > 1. How important is space efficiency? (Is the tree large compared to
    > available memory?)
    > 2. How many children per node?
    > 3. Are children to be dynamically or statically identified/named?
    > 4. If the number of children varies, how widely?
    > 5. Is constant time access to parents required? Siblings?
    > 6. Are the data represented exogenously with respect to the tree?
    > (I.e. is it already stored in another tree, so you only need to point
    > to it?) Or will they be endogenous?
    > 7. Are tree nodes to be exogenous for some other data structure
    > (pointed to by it)?
    > 8. Does the tree need to be persistent?
    > 9. Is a human-readable representation required?
    > 10. Do tree operations need to be atomic (in a multi-threading
    > environment)?
    > 11. Do tree operations need to be transactions (in the database sense
    > of commit/rollbacck)?
    > 12. Is it better to pre-allocate all tree storage or allocate on the
    > fly? Is the max number of nodes limited?
    > 13. If the tree is ordered, do you need data ordinals?
    > 14. If the tree is for data access, does it need to be self-height-
    > limiting or -balancing?
    > 15. Do tree operations need to be undoable?
    >
    > All these and others affect the "best" C representation. If you don't
    > have many such criteria, then that's a criterion in itself. It
    > alllows you can trade between simplicity and flexibility for future
    > new requirements.
    >
    > If you narrow the question a bit, we can get to the details.


    Actually I first came to the issue from a rather humble goal: Simply
    to describe something of the genre of natural trees, without any need
    of processing.

    M. K. Shen
    Mok-Kong Shen, Jul 20, 2010
    #9
  10. Mok-Kong Shen

    Dann Corbit Guest

    In article <i243o2$jcb$03$-online.com>, mok-kong.shen@t-
    online.de says...
    >
    > A possibly dumb question: Given a labeled or unlabeled tree
    > (in the sense of graphs), how could one best use C to describe it?
    > (I don't exactly know but have the impression that this might be
    > rather simple in Lisp.)


    The most generic way that I can imagine is a recursive skiplist of
    skiplists (each skiplist at any level can contain skiplists).
    In that way, the number of leaves for any node is arbitary.

    Otherwise, we will have a kind of tree which is not generic (e.g. a
    binary tree or a red-black tree or some other tree). A skiplist of
    skiplists can be any kind of tree.

    Abstract algorithms are much easier (for me) to code in C++ than in C.

    With C99 you could use variant arrays which would be another approach
    for generic behavior.

    My skiplist of skiplists idea assumes that it is possible to order the
    objects in some way. If this is not possible then a recursive linked
    list of linked lists is another alternative.

    So, my notion of a tree is a collection of nodes, each of which can have
    zero or more ancestors and which also has a root node. The type of the
    node should also be able to change at each level, if possible. In this
    way we might describe an arbitrary object as a tree (e.g. a house is a
    tree, with root object being house, which is a collection of rooms, each
    room consists of a collection of properties and a collection of
    contained items, etc.)
    Dann Corbit, Jul 20, 2010
    #10
  11. On Jul 20, 5:10 am, Mok-Kong Shen <> wrote:
    > A possibly dumb question: Given a labeled or unlabeled tree
    > (in the sense of graphs), how could one best use C to describe it?
    > (I don't exactly know but have the impression that this might be
    > rather simple in Lisp.)
    >
    > Thanks.
    >
    > M. K. Shen


    So, let's give an example:
    The LISP structure (A (B C) D (E (F G) H)) consists of 4 elements. The
    first and third of these are scalars, the second and fourth are lists.
    The last element is a list consisting of a scalar, a two-element list,
    and then a scalar,

    I suppose that it would be possible in C to create a polyvalent and
    variable argument function Construct_List to do the same thing that
    LISP's CONS function does and the equivalent to <LISP>(CONS Z (A (B C)
    D (E (F G) H)) )</LISP> would be
    <C>
    Z = Construct_List ('A', Construct_List ('B', 'C'), 'D',
    Construct_List ('E', Construct_List ('F, 'G'), 'H'));
    </C>

    C has a great syntax for stuffing arrays. It's not as good at stuffing
    lists, mainly because there is no native support for trees in C. There
    are probably list and tree packages all over the place the same as
    there is a standard library, but the lanaguage itself doesn't
    contemplate trees. You (or the package implementor) has to provide
    your own abstraction.
    Michael Angelo Ravera, Jul 20, 2010
    #11
  12. On Tue, 20 Jul 2010, Dann Corbit wrote:

    [snip]

    > Otherwise, we will have a kind of tree which is not generic (e.g. a
    > binary tree or a red-black tree or some other tree).


    A binary tree can be made "generic", just don't call the two child
    pointers "left" and "right"; call them "next_sibling" and "first_child".
    This leads to arbitrary arity ("arbitrarity", lol). IIRC, Malcolm McLean's
    first example in this thread was written like that.

    (Sorry for using "lol"; couldn't resist.)

    lacos
    Ersek, Laszlo, Jul 20, 2010
    #12
  13. Mok-Kong Shen

    Alan Curry Guest

    In article <>,
    Ben Bacarisse <> wrote:
    >Mok-Kong Shen <> writes:
    ><snip>
    >> I meant one could in Lisp (if my poor knowledge about Lisp doesn't
    >> betray me) write down the tree simply as a Lisp expression.

    >
    >You can do this in C (modern C99 at least) like this:
    >
    > typedef struct node {
    > const char *label;
    > struct node *left, *right;
    > } Node;
    >
    > /* and then inside a function such as main: */
    >
    > Node *my_tree =
    > (Node){"root", &(Node){"left", 0, 0}, &(Node){"right", 0, 0}};


    You don't need deep nesting to create a recursive structure. You can put the
    nodes in an array, like this:

    struct node {
    const char *label;
    const struct node *left, *right;
    };

    const struct node mytree[] = {
    {"root", &mytree[1], &mytree[2]},
    {"left", &mytree[3], 0},
    {"right", 0, &mytree[4]},
    {"leftleft", 0, 0},
    {"rightright", 0, 0}
    };

    Which lets you get the whole thing statically allocated in readonly memory.
    If you're generating a C representation of a tree that is originally
    represented in some other form, this is the way to go. I don't recommend
    writing it by hand though. It's too hard to make sure the links all point the
    the right places.

    --
    Alan Curry
    Alan Curry, Jul 20, 2010
    #13
  14. (Alan Curry) writes:

    > In article <>,
    > Ben Bacarisse <> wrote:
    >>Mok-Kong Shen <> writes:
    >><snip>
    >>> I meant one could in Lisp (if my poor knowledge about Lisp doesn't
    >>> betray me) write down the tree simply as a Lisp expression.

    >>
    >>You can do this in C (modern C99 at least) like this:
    >>
    >> typedef struct node {
    >> const char *label;
    >> struct node *left, *right;
    >> } Node;
    >>
    >> /* and then inside a function such as main: */
    >>
    >> Node *my_tree =
    >> (Node){"root", &(Node){"left", 0, 0}, &(Node){"right", 0, 0}};

    >
    > You don't need deep nesting to create a recursive structure. You can put the
    > nodes in an array, like this:


    Yes, I know. I should have been more clear. I was not saying this way
    the best way and certainly not the only way (actually I am not even
    saying it is a good way). I wanted only to dispel the idea that a tree
    can be written as a Lisp expression but not as a C expression.

    <snip static tree example>
    --
    Ben.
    Ben Bacarisse, Jul 21, 2010
    #14
  15. On 21 July, 07:54, "io_x" <> wrote:
    > "Nick Keighley" <> ha scritto nel messaggionews:...
    > > On 20 July, 13:10, Mok-Kong Shen <> wrote:



    > >> A possibly dumb question: Given a labeled or unlabeled tree
    > >> (in the sense of graphs), how could one best use C to describe it?

    >
    > > what form is it in now or how are you going to enter it?

    >
    > > /* tree.c */

    >
    > > #include <stdio.h>

    >
    > > typedef struct tree_tag
    > > {
    > >    char *data;
    > >    struct tree_tag *left;
    > >    struct tree_tag *right;
    > > } Tree;

    >
    > > void walk (Tree *tree)
    > > {
    > >    if (tree != NULL)
    > >    {
    > >        printf ("%s ", tree->data);
    > >        walk (tree->left);
    > >        walk (tree->right);
    > >    }
    > > }

    >
    > > int main (void)
    > > {
    > >    Tree yggdrasil[] =
    > >    {
    > >        {"red", &yggdrasil[1], &yggdrasil[2]},
    > >        {"blue", &yggdrasil[3], &yggdrasil[4]},
    > >        {"black", 0, 0},
    > >        {"yellow", 0, 0},
    > >        {"green", 0, 0}
    > >    };

    >
    > >    walk (yggdrasil);
    > >    return 0;
    > > }

    >
    > Error E2063 tree1.c 27: Illegal initialization in function main
    > *** 1 errors in Compile ***


    I'm surprised! It compiled and executed ok for me with an old Windows
    compiler. And on gcc unless I stuck -pedantic on... ok fair cop


    > your example not compile here; afther some try in C i wrote
    > it in RosAsm [one assembly + debugger]
    >
    > why not write all in assembly? it is 1000 times better than C ...


    go forth and multiply

    <snip>
    Nick Keighley, Jul 21, 2010
    #15
  16. On 20 July, 17:39, "io_x" <> wrote:
    > "Mok-Kong Shen" <> ha scritto nel messaggionews:i243o2$jcb$03$-online.com...


    > > A possibly dumb question: Given a labeled or unlabeled tree
    > > (in the sense of graphs), how could one best use C to describe it?
    > > (I don't exactly know but have the impression that this might be
    > > rather simple in Lisp.)

    >
    > i think one tree like one tree of directory
    > every node could have nodes [in number if 0,1,2,3,4,5,6 ecc.
    > that are other directory so all with the use of malloc]


    most other posts are describing binary (where their are only two
    possible children of each node) you are describing more general n-ary
    trees. Its trivial (well fairly easy to transform an n-arry tree into
    a binary tree.

    > something like
    >
    >          dir2  /--dir_B
    >         /     /
    >     dir1---dir3--dir_A
    >         \     \\
    >          dir4  \\---dir_D
    >                 \---dir_C


    each node has one branch pointing to its siblings (nodes having the
    same parent) and the other to its children


    > typedef struct node {
    >        char          *Data;
    >        struct node **Nodes;
    >
    > }Node;


    > where Nodes[0] is the node father [always 1]
    > Nodes[0]==0 only if that node is the root node
    >
    > Nodes==0 means one error
    >
    > but what about one structure like this
    >
    >          dir2  /--dir_B
    >         /  |  /    |
    >     dir1---dir3--dir_A
    >         \  |  \\     \
    >          dir4  \\---dir_D
    >                 \---dir_C
    >
    > it is a tree? i say no,


    it's not a tree, no


    > but in this case i would write that
    > using
    >
    > typedef struct node {
    >        char         *Data;
    >        struct node **NodesInThisNode;
    >        struct node **NodesToThisNode;
    >
    >
    >
    > }Node;


    any good book on algorithms will discuss all this and more
    Nick Keighley, Jul 21, 2010
    #16
  17. On 20 July, 19:41, Mok-Kong Shen <> wrote:


    > Actually I first came to the issue from a rather humble goal: Simply
    > to describe something of the genre of natural trees,


    "natural trees"!? You mean like The Larch? What properties natural
    trees do you wish to describe? Phylogeny? Morphology? Leaf count?
    Beetle count?

    > without any need of processing.


    I think turning a natural treee into a computer science tree is
    inevitably going to require some processing
    Nick Keighley, Jul 21, 2010
    #17
  18. Mok-Kong Shen

    Ian Collins Guest

    On 07/21/10 07:17 PM, Nick Keighley wrote:
    > On 21 July, 07:54, "io_x"<> wrote:
    >> "Nick Keighley"<> ha scritto nel messaggionews:...
    >>> On 20 July, 13:10, Mok-Kong Shen<> wrote:

    >
    >
    >>>> A possibly dumb question: Given a labeled or unlabeled tree
    >>>> (in the sense of graphs), how could one best use C to describe it?

    >>
    >>> what form is it in now or how are you going to enter it?

    >>
    >>> /* tree.c */

    >>
    >>> #include<stdio.h>

    >>
    >>> typedef struct tree_tag
    >>> {
    >>> char *data;
    >>> struct tree_tag *left;
    >>> struct tree_tag *right;
    >>> } Tree;

    >>
    >>> void walk (Tree *tree)
    >>> {
    >>> if (tree != NULL)
    >>> {
    >>> printf ("%s ", tree->data);
    >>> walk (tree->left);
    >>> walk (tree->right);
    >>> }
    >>> }

    >>
    >>> int main (void)
    >>> {
    >>> Tree yggdrasil[] =
    >>> {
    >>> {"red",&yggdrasil[1],&yggdrasil[2]},
    >>> {"blue",&yggdrasil[3],&yggdrasil[4]},
    >>> {"black", 0, 0},
    >>> {"yellow", 0, 0},
    >>> {"green", 0, 0}
    >>> };

    >>
    >>> walk (yggdrasil);
    >>> return 0;
    >>> }

    >>
    >> Error E2063 tree1.c 27: Illegal initialization in function main
    >> *** 1 errors in Compile ***

    >
    > I'm surprised! It compiled and executed ok for me with an old Windows
    > compiler. And on gcc unless I stuck -pedantic on... ok fair cop


    It's perfectly valid C.

    --
    Ian Collins
    Ian Collins, Jul 21, 2010
    #18
  19. Mok-Kong Shen

    Ian Collins Guest

    On 07/21/10 08:06 PM, io_x wrote:
    > "Nick Keighley"<> ha scritto nel messaggio
    > news:89a8d485-39f9-44af-> >>Error E2063 tree1.c 27: Illegal initialization in
    > function main
    >>> *** 1 errors in Compile ***

    >
    >> I'm surprised! It compiled and executed ok for me with an old Windows
    >> compiler. And on gcc unless I stuck -pedantic on... ok fair cop

    >
    > the C compiler not compile it due to the above error
    > but the C++ compiler compile it [i rename the file in tree1.cpp]


    A decent C++ compile will whinge about (but still compile) the
    assignments of string literals to char*. Alas, C compilers don't.

    --
    Ian Collins
    Ian Collins, Jul 21, 2010
    #19
  20. Mok-Kong Shen

    Stefan Ram Guest

    Mok-Kong Shen <> writes:
    >A possibly dumb question: Given a labeled or unlabeled tree
    >(in the sense of graphs), how could one best use C to describe it?


    I wrote this once:

    3
    / \
    / \
    1 4
    / \
    / \
    0 2

    main.c

    #include <stdio.h> /* printf, putchar */
    #include <stdlib.h> /* EXIT_SUCCESS */
    typedef struct tree
    { struct tree * left; int value; struct tree * right; } * TREE;
    void print( TREE const tree )
    { if( tree ){ putchar( '(' ); print( tree->left );
    printf( "%d", tree->value ); print( tree->right ); putchar( ')' ); }}
    extern struct tree t1, t0, t2, t4; struct tree t3 =


    { &t1, 3, &t4 },


    t1 ={ &t0, 1, &t2 }, t4 ={ 0, 4, 0 },


    t0 ={ 0, 0, 0 }, t2 ={ 0, 2, 0 };



    int main( void ){ print( &t3 ); putchar( '\n' ); return EXIT_SUCCESS; }

    ::std::cout

    (((0)1(2))3(4))

    You can actually see the tree in the source code. And this small
    portable program even contains a full-blown tree dumper that dumps
    the tree to stdout. The output format even is an S-expression, which
    you should like. The grammar is

    <tree> ::= [<entry>].
    <entry> ::= '(' <tree> <number> <tree> ')'.
    <number> ::= '0' | '1' | '2' | '3' | '4'.

    Look how nicely and directly the grammar determinates the
    structure of the function »print«!

    [] --> if,
    '(' <tree> ... --> { putchar( '(' ); ....
    Stefan Ram, Jul 21, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    391
  2. Jonathan Bromley

    Describing pipelined hardware

    Jonathan Bromley, Jun 6, 2006, in forum: VHDL
    Replies:
    50
    Views:
    1,979
    Ben Jones
    Jun 22, 2006
  3. ben
    Replies:
    4
    Views:
    424
  4. tascien

    Describing a webservice

    tascien, Feb 22, 2006, in forum: ASP .Net Web Services
    Replies:
    4
    Views:
    118
    Simon Hart
    Feb 23, 2006
  5. George George

    Describing degerate dna strings

    George George, Jan 16, 2009, in forum: Ruby
    Replies:
    11
    Views:
    248
    Jesús Gabriel y Galán
    Jan 17, 2009
Loading...

Share This Page