3 .so /usr/lib/tmac/tmac.m
6 \fIRecursive Data Types Made Simple with Ugen\fR
15 Recursive datatypes in an important class of data structures
16 we often use in, for instance, abstract syntax trees in compilers.
17 An example of a recursive data type is shown below
18 (written in some hypothetical language):
22 interior: (bintree, bintree);
26 The type bintree is a union of two variants: 'interior' which consists
27 of two bintrees, and 'leaf' which has an integer value associated to it.
29 The program \fIugen\fR is yet another tool which relieves the
30 the C-programmer from the burden of implementing the
31 constructor-, selector- and variant test functions associated to
33 .H 1 "How to use ugen"
34 Suppose the specification below is in a file called 'treedef.u'.
37 interior : < getleft: bintree; getright: bintree; >;
38 leaf : < getint: int; >;
45 creates two files: 'treedef.c' and 'treedef.h'.
46 The file 'treedef.h' will contain the following definitions:
48 typedef enum{ interior, leaf } Tbintree;
49 typedef .... *bintree;
51 The type 'Tbintree' is an enumerated type with the same identifiers as
52 the variants of the recursive data type,
53 the type 'bintree' is implemented as a pointer to something.
54 This file must be included in all files where the type 'bintree'
56 Furthermore, the file treedef.h also contains macro definitions for
57 the selector functions; these macroes simply use the corresponding function
58 in treedefs.c that returns a pointer to that intended field.
59 In this manner, updating of a field can be done by simple assignment,
64 The file 'treedef.c' will contain the following definitions.
69 /* The function tbintree returns the variant of the
72 Tbintree tbintree(t) bintree t; { ... }
74 /* Constructor function for variant interior.
76 bintree mkinterior(t1, t2) bintree t1, t2; { ... }
78 /* Its selector functions, returns pointers to a field in the node.
80 bintree *Xgetleft(t) bintree t; { ... }
81 bintree *Xgetright(t) bintree t; { ... }
84 /* Constructor function for variant leaf.
86 bintree mkleaf(i) int i; { ... }
88 /* Its selector function.
90 int getint(t) bintree t; { ... }
94 The pointers returned by the constructor functions are
95 returned by the memory allocation function \fImalloc\fR,
96 so one may use \fIfree\fR to reclaim storage, if that is desired.
98 The appendix contains the file listings of a complete program
99 that reads an expression on normal infix form and prints
100 it in prefix form, eg:
103 output: +(12, *(3, 5))
105 Lex and yacc has been used for lexical- and syntax analysis,
106 ugen for the intermediate tree form, and make maintains it all.
107 .HU "Appendix - Example of use of ugen"
117 %token PLUS TIMES LPAR RPAR INT
122 top : expr { root = $1; }
124 expr : expr PLUS expr { $$ = mkplus($1, $3); } |
125 expr TIMES expr { $$ = mktimes($1, $3); } |
126 LPAR expr RPAR { $$ = $2; } |
127 INT { $$ = mkinteger($1);}
129 yyerror(s) char *s; {
147 [0-9]+ { sscanf(yytext, "%d", &yylval);
153 int yywrap(){ return(1); }
163 if(! yyparse()) /* if no syntax errors .. */
173 prefixprint(gplusleft(t));
175 prefixprint(gplusright(t));
180 prefixprint(gtimesleft(t));
182 prefixprint(gtimesright(t));
186 printf("%d", getint(t));
197 plus :< gplusleft : tree;
200 times :< gtimesleft : tree;
203 integer :< getint : int;
211 pre : main.o y.tab.o lex.yy.o tree.o
212 cc main.o y.tab.o lex.yy.o tree.o -o pre
213 main.o : main.c tree.h
217 lex.yy.o: lex.yy.c y.tab.h
219 tree.o : tree.c tree.h
225 tree.c tree.h : tree.u