Return to README CVS log

Up to [Research Unix] / researchv10no / cmd / twig

Annotation of researchv10no/cmd/twig/README, revision 1.1

1.1     ! root        1: Installation Procedure
        !             2: ----------------------
        !             3: To install twig, you must decide in which directories to place:
        !             4: 
        !             5: (1) the twig compiler binary, and
        !             6: (2) the twig template files.
        !             7: 
        !             8: Once you have made these two decisions, you should edit the makefile and
        !             9: set the variable INSTALL to the value of (1), and the variable TEMPLATES to
        !            10: (2).  The definitions of INSTALL and TEMPLATES should be near the beginning
        !            11: of the makefile.  The installation can then be completed by typing:
        !            12: 
        !            13:        make install
        !            14: 
        !            15: Once a user has written a twig specification, the command twig is used to
        !            16: compile it.  The compilation creates two files called walker.c,
        !            17: containing several subroutines, and symbols.h, containing definitions.
        !            18: Walker.c is compiled and linked with the rest of the user program, and
        !            19: tree matching occurs when the user's program calls a subroutine called _match.
        !            20: More details about twig specifications, and how to interface to the
        !            21: subroutines in walker.c is given in the ``Twig Reference Manual'', AT&T Bell
        !            22: Laboratories, Computing Science Technical Report #120.
        !            23: 
        !            24: Addendum to the ``Twig Reference Manual''
        !            25: -----------------------------------------
        !            26: 
        !            27: 1.     In a node declaration, the user can override the automatic numbering
        !            28:        of a node id by expliciting assigning a number using the ``= int''
        !            29:        construct.  However, the user must then assign a number to all
        !            30:        of the node ids.  In other words, the user must either assign
        !            31:        numbers to each of the node ids, or to none of them.  The ids must
        !            32:        have unique numbers.
        !            33: 
        !            34: 2.     The default action of executing the labelled leaves from
        !            35:        right to left is inadequate.  ``Execution,'' as used here, is in
        !            36:        the sense as described in the ``Twig Reference Manual.''  Although
        !            37:        one could simulate any execution order by using a top-down rule, and
        !            38:        explicitly requesting the execution of labelled leaves with the tDO
        !            39:        macro, it is tedious to do so.  For example, implementing a Sethi-Ullman
        !            40:        style register allocator  in such a fashion is extremely awkward.
        !            41:        To alleviate this tedium, reordering scheme has been proposed, and
        !            42:        implemented by Andrew Appel of Princeton University.  It is included
        !            43:        in this version of twig.
        !            44: 
        !            45:        A function, ``_do'' performs the execution of the matches.  This
        !            46:        function is part of the walker.c file generated by twig.  In versions
        !            47:        of the walker without reordering, _do performs the call:
        !            48: 
        !            49:                _evalleaves(winner->lleaves);
        !            50: 
        !            51:        where winner->lleaves are the labelled leaves of the winning match.
        !            52:        Lleaves has type ``__match *[], '' and is a NULL terminated sequence
        !            53:        of matches for the labelled leaves in left to right order.  Calling
        !            54:        tDO with an element of lleaves executes the match associated with
        !            55:        the labelled leaf.
        !            56: 
        !            57:        Reordering is accomplished by changing the call to _evalleaves with
        !            58:        the statement:
        !            59: 
        !            60:                REORDER(winner->lleaves);
        !            61: 
        !            62:        REORDER is a macro, or function defined by the user that may execute
        !            63:        the leaves in any order.  If the user does not define REORDER then
        !            64:        twig will generate a default, which is to call _evalleaves.
        !            65: 
        !            66:        For example, if the user wishes to execute the leaves in the order of
        !            67:        decreasing cost, the following definition could be used.
        !            68: 
        !            69:        prologue {
        !            70:        ...
        !            71:        #define REORDER(list)   reorder(list)
        !            72:        ...
        !            73:        }
        !            74: 
        !            75:        ...
        !            76: 
        !            77:        insert {
        !            78: 
        !            79:        reorder(list)
        !            80:                __match **list;
        !            81:        {
        !            82:                int i, j, n;
        !            83:                __match *index[16];
        !            84: 
        !            85:                /* copy list into index */
        !            86:                for(n=0; list[n]; n++) index[n] = list[n];
        !            87: 
        !            88:                /* insertion sort */
        !            89:                for(j=0;j<n;j++)
        !            90:                    for(i=j; i>0; i--)
        !            91:                        if(index[i]->cost > index[i-1]->cost) {
        !            92:                                /* swap them */
        !            93:                                __match *temp = index[i];
        !            94:                                index[i] = index[i-1]; index[i-1] = p;
        !            95:                        }
        !            96: 
        !            97:                /* now execute */
        !            98:                for(j=0;j<n;j++)
        !            99:                        tDO(index[j]);
        !           100:        }
        !           101: 
        !           102:        }
        !           103: 
        !           104: 
        !           105: 3.     In a top-down rule, there is often a desire to execute all the
        !           106:        labelled leaves after performing some preparatory actions.  This
        !           107:        could be done by saying
        !           108: 
        !           109:                tDO($%1$); tDO($%2$); ...
        !           110: 
        !           111:        However, the short hand notation, ``EVAL;'' provides the same function.
        !           112:        
        !           113: 4.     In the previous version of twig, Walker.c had a reference to
        !           114:        walker.h.  Hence the user had to compile walker.c with the command:
        !           115: 
        !           116:                cc -Iinclude_dir -c walker.c
        !           117: 
        !           118:        where include_dir was the directory containing walker.h.
        !           119:        The reference to walker.h has been eliminated by inserting walker.h
        !           120:        into all the template files that could generate walker.c.
        !           121:        Therefore the new compile command is:
        !           122: 
        !           123:                cc -c walker.c
        !           124: 
        !           125: 5.     Twig assigns numbers to the node symbols, which are used to identify
        !           126:        nodes to the tree matcher.  In the previous version of twig, the
        !           127:        tree matcher actually recognized ``M_NODE|number'' as the value
        !           128:        assigned to the node symbol rather than just plain ``number.''
        !           129:        This was completely undocumented.  The current version fixed the
        !           130:        tree matcher to recognize ``number'' as the correct value associated
        !           131:        with a node symbol.
        !           132: 
        !           133: 6.     Twig now uses dynamic initialization of costs rather than static
        !           134:        initialization.  This permits the user to declare COST as structure.
        !           135: 
        !           136: 7.     Many cost metrics used in twig programs are additive.  That is,
        !           137:        the cost of a match is some constant cost plus the sum of the
        !           138:        costs of the matches at the labelled leaves.  The macros ZEROCOST, and
        !           139:        ADDCOST provide an easy way to implement this.  For example, if costs
        !           140:        are integers, then the definition
        !           141: 
        !           142:        #define ZEROCOST        1
        !           143:        #define ADDCOST(accum,y)        (accum) += (y)
        !           144: 
        !           145:        would cause twig to generate, for rules without a cost part, code that
        !           146:        calculate the default cost as one plus the sum of the costs of the
        !           147:        matches at the labelled leaves.
        !           148: 
        !           149:        ZEROCOST, and ADDCOST must both be defined, if the above facility is
        !           150:        to be used.  DEFAULT_COST must not be defined when ADDCOST is defined.
        !           151: 
        !           152: 8. Changes made by Keutzer (allegra!keutzer) and Appel (research!appel)
        !           153:        
        !           154:        modifications by keutzer:
        !           155:        
        !           156:        char c ->int c 
        !           157:        all over lex.c
        !           158:        
        !           159:        varargs added in _mtG in walker.c 
        !           160:                may be too expensive for some people. 
        !           161:                code is not portable to a SUN4 without it however.
        !           162:        
        !           163:        "short int"'s were changed to "short"'s for UTS compatability.
        !           164:        
        !           165:        The  NODE struct pointed to by a NODEPTR now needs a "mark" field.
        !           166:         
        !           167:        A printTree(NODEPTR n) routine must also be supplied by the  user.
        !           168:         
        !           169:        If you were using the values of nodes in your symbols.h file
        !           170:        then the command
        !           171:                cc -g -c -DDUMPNAMES sym.c
        !           172:        should be used to compile sym.c.

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