Return to yytree.c CVS log

Up to [CSRG BSD Unix] / 40BSD / cmd / pi

Annotation of 40BSD/cmd/pi/yytree.c, revision 1.1

1.1     ! root        1: /* Copyright (c) 1979 Regents of the University of California */
        !             2: 
        !             3: static char sccsid[] = "@(#)yytree.c 1.1 8/27/80";
        !             4: 
        !             5: #include "whoami.h"
        !             6: #include "0.h"
        !             7: #include "tree.h"
        !             8: 
        !             9: extern int *spacep;
        !            10: 
        !            11: /*
        !            12:  * LIST MANIPULATION ROUTINES
        !            13:  *
        !            14:  * The grammar for Pascal is written left recursively.
        !            15:  * Because of this, the portions of parse trees which are to resemble
        !            16:  * lists are in the somewhat inconvenient position of having
        !            17:  * the nodes built from left to right, while we want to eventually
        !            18:  * have as semantic value the leftmost node.
        !            19:  * We could carry the leftmost node as semantic value, but this
        !            20:  * would be inefficient as to add a new node to the list we would
        !            21:  * have to chase down to the end.  Other solutions involving a head
        !            22:  * and tail pointer waste space.
        !            23:  *
        !            24:  * The simple solution to this apparent dilemma is to carry along
        !            25:  * a pointer to the leftmost node in a list in the rightmost node
        !            26:  * which is the current semantic value of the list.
        !            27:  * When we have completed building the list, we can retrieve this
        !            28:  * left end pointer very easily; neither adding new elements to the list
        !            29:  * nor finding the left end is thus expensive.  As the bottommost node
        !            30:  * has an unused next pointer in it, no space is wasted either.
        !            31:  *
        !            32:  * The nodes referred to here are of the T_LISTPP type and have
        !            33:  * the form:
        !            34:  *
        !            35:  *     T_LISTPP        some_pointer            next_element
        !            36:  *
        !            37:  * Here some_pointer points to the things of interest in the list,
        !            38:  * and next_element to the next thing in the list except for the
        !            39:  * rightmost node, in which case it points to the leftmost node.
        !            40:  * The next_element of the rightmost node is of course zapped to the
        !            41:  * NIL pointer when the list is completed.
        !            42:  *
        !            43:  * Thinking of the lists as tree we heceforth refer to the leftmost
        !            44:  * node as the "top", and the rightmost node as the "bottom" or as
        !            45:  * the "virtual root".
        !            46:  */
        !            47: 
        !            48: /*
        !            49:  * Make a new list
        !            50:  */
        !            51: newlist(new)
        !            52:        register int *new;
        !            53: {
        !            54: 
        !            55:        if (new == NIL)
        !            56:                return (NIL);
        !            57:        return (tree3(T_LISTPP, new, spacep));
        !            58: }
        !            59: 
        !            60: /*
        !            61:  * Add a new element to an existing list
        !            62:  */
        !            63: addlist(vroot, new)
        !            64:        register int *vroot;
        !            65:        int *new;
        !            66: {
        !            67:        register int *top;
        !            68: 
        !            69:        if (new == NIL)
        !            70:                return (vroot);
        !            71:        if (vroot == NIL)
        !            72:                return (newlist(new));
        !            73:        top = vroot[2];
        !            74:        vroot[2] = spacep;
        !            75:        return (tree3(T_LISTPP, new, top));
        !            76: }
        !            77: 
        !            78: /*
        !            79:  * Fix up the list which has virtual root vroot.
        !            80:  * We grab the top pointer and return it, zapping the spot
        !            81:  * where it was so that the tree is not circular.
        !            82:  */
        !            83: fixlist(vroot)
        !            84:        register int *vroot;
        !            85: {
        !            86:        register int *top;
        !            87: 
        !            88:        if (vroot == NIL)
        !            89:                return (NIL);
        !            90:        top = vroot[2];
        !            91:        vroot[2] = NIL;
        !            92:        return (top);
        !            93: }
        !            94: 
        !            95: 
        !            96: /*
        !            97:  * Set up a T_VAR node for a qualified variable.
        !            98:  * Init is the initial entry in the qualification,
        !            99:  * or NIL if there is none.
        !           100:  *
        !           101:  * if we are building pTrees, there has to be an extra slot for 
        !           102:  * a pointer to the namelist entry of a field, if this T_VAR refers
        !           103:  * to a field name within a WITH statement.
        !           104:  * this extra field is set in lvalue, and used in VarCopy.
        !           105:  */
        !           106: setupvar(var, init)
        !           107:        char *var;
        !           108:        register int *init;
        !           109: {
        !           110: 
        !           111:        if (init != NIL)
        !           112:                init = newlist(init);
        !           113: #      ifndef PTREE
        !           114:            return (tree4(T_VAR, NOCON, var, init));
        !           115: #      else
        !           116:            return tree5( T_VAR , NOCON , var , init , NIL );
        !           117: #      endif
        !           118: }
        !           119: 
        !           120:     /*
        !           121:      * set up a T_TYREC node for a record
        !           122:      *
        !           123:      * if we are building pTrees, there has to be an extra slot for 
        !           124:      * a pointer to the namelist entry of the record.
        !           125:      * this extra field is filled in in gtype, and used in RecTCopy.
        !           126:      */
        !           127: setuptyrec( line , fldlst )
        !           128:     int        line;
        !           129:     int        *fldlst;
        !           130:     {
        !           131: 
        !           132: #      ifndef PTREE
        !           133:            return tree3( T_TYREC , line , fldlst );
        !           134: #      else
        !           135:            return tree4( T_TYREC , line , fldlst , NIL );
        !           136: #      endif
        !           137:     }
        !           138: 
        !           139:     /*
        !           140:      * set up a T_FIELD node for a field.
        !           141:      *
        !           142:      * if we are building pTrees, there has to be an extra slot for
        !           143:      * a pointer to the namelist entry of the field.
        !           144:      * this extra field is set in lvalue, and used in SelCopy.
        !           145:      */
        !           146: setupfield( field , other )
        !           147:     int        *field;
        !           148:     int        *other;
        !           149:     {
        !           150: 
        !           151: #      ifndef PTREE
        !           152:            return tree3( T_FIELD , field , other );
        !           153: #      else
        !           154:            return tree4( T_FIELD , field , other , NIL );
        !           155: #      endif
        !           156:     }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.