![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 42BSD / usr.bin / struct|
Return to tree.c CVS log | Up to [CSRG BSD Unix] / 42BSD / usr.bin / struct |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)tree.c 4.1 (Berkeley) 2/11/83";
3: #endif not lint
4:
5: # include "y.tab.h"
6: #include "b.h"
7: #include <stdio.h>
8:
9:
10: addroot(string,type,n1,n2)
11: char *string;
12: int type;
13: struct node *n1, *n2;
14: {
15: struct node *p;
16: p = malloc(sizeof(*p));
17: p->left = n1;
18: p->right = n2;
19: p->op = type;
20: p->lit = malloc(slength(string) + 1);
21: str_copy(string,p->lit,slength(string) + 1);
22: return(p);
23: }
24:
25:
26: freetree(tree)
27: struct node *tree;
28: {
29: if (tree)
30: {freetree(tree->left);
31: freetree(tree->right);
32: freenode(tree);
33: }
34: }
35:
36: freenode(treenode)
37: struct node *treenode;
38: {
39: free(treenode->lit);
40: free(treenode);
41: }
42:
43: int compop[] { '&', '|', '<', '>', xxeq, xxle, xxne, xxge};
44: int notop[] { '|', '&', xxge, xxle, xxne, '>', xxeq, '<'};
45: char *opstring[] { "||", "&&", ">=", "<=", "!=", ">", "==", "<"};
46:
47: checkneg(tree,neg) /* eliminate nots if possible */
48: struct node *tree;
49: int neg;
50: {
51: int i;
52: struct node *t;
53: if (!tree) return(0);
54: for (i = 0; i < 8; ++i)
55: if (tree->op == compop[i]) break;
56: if (i > 1 && i < 8 && tree ->left ->op == '-' && str_eq(tree->right->lit,"0"))
57: {
58: t = tree->right;
59: tree->right = tree->left->right;
60: freenode(t);
61: t = tree->left;
62: tree->left = tree->left->left;
63: freenode(t);
64: }
65:
66:
67: if (neg)
68: {
69: if (tree ->op == '!')
70: {
71: t = tree->left;
72: freenode(tree);
73: return(checkneg(t,0));
74: }
75: if (i < 8)
76: {
77: tree->op = notop[i];
78: free(tree->lit);
79: tree->lit = malloc(slength(opstring[i])+1);
80: str_copy(opstring[i],tree->lit, slength(opstring[i])+1);
81: if (tree->op == '&' || tree->op == '|')
82: {
83: tree->left = checkneg(tree->left,1);
84: tree->right = checkneg(tree->right,1);
85: }
86: return(tree);
87: }
88: if (tree->op == xxident && str_eq(tree->lit,".false."))
89: str_copy(".true.",tree->lit, slength(".true.")+1);
90: else if (tree->op == xxident && str_eq(tree->lit,".true."))
91: {
92: free(tree->lit);
93: tree->lit = malloc(slength(".false.")+1);
94: str_copy(".false.",tree->lit, slength(".false.")+1);
95: }
96: else
97: {
98: tree = addroot("!",'!',tree,0);
99: tree->lit = malloc(2);
100: str_copy("!",tree->lit, slength("!")+1);
101: }
102: return(tree);
103: }
104: else
105: if (tree->op == '!')
106: {
107: t = tree;
108: tree = tree->left;
109: freenode(t);
110: return(checkneg(tree,1));
111: }
112: else
113: {tree->left = checkneg(tree->left,0);
114: tree->right = checkneg(tree->right,0);
115: return(tree);
116: }
117: }
118:
119: yield(tree,fprec)
120: struct node *tree;
121: int fprec; /* fprec is precedence of father of this node */
122: {
123: int paren,p;
124: static int oplast; /* oplast = 1 iff last char printed was operator */
125: if (!tree) return;
126: p = prec(tree ->op);
127: paren = (p < fprec || (oplast && tree->op == xxuminus)) ? 1 : 0;
128:
129: if (paren)
130: {
131: putout('(',"(");
132: oplast = 0;
133: }
134:
135: switch(tree->op)
136: {
137: case xxuminus:
138: tree->op = '-';
139: case '!':
140: putout(tree->op,tree->lit);
141: oplast = 1;
142: yield(tree->left,p);
143: break;
144: case '&':
145: case '|':
146: case '<':
147: case '>':
148: case xxeq:
149: case xxle:
150: case xxge:
151: case '+':
152: case '-':
153: case '*':
154: case '/':
155: case '^':
156: yield(tree->left,p);
157: putout(tree->op, tree->lit);
158: oplast = 1;
159: yield(tree->right,p);
160: break;
161: case xxidpar:
162: yield(tree->left,0);
163: putout('(',"(");
164: oplast = 0;
165: yield(tree->right,0);
166: putout('(',")");
167: oplast = 0;
168: break;
169: default:
170: yield(tree->left,p);
171: putout(tree->op, tree->lit);
172: oplast = 0;
173: yield(tree->right,p);
174: break;
175: }
176: if (paren)
177: {
178: putout(')',")");
179: oplast = 0;
180: }
181: }
182:
183: puttree(tree)
184: struct node *tree;
185: {
186: yield(tree,0);
187: freetree(tree);
188: }
189:
190:
191: prec(oper)
192: int oper;
193: {
194: switch(oper)
195: {
196: case ',': return(0);
197: case '|': return(1);
198: case '&': return(2);
199: case '!': return(3);
200:
201: case '<': case '>': case xxeq:
202: case xxne: case xxle: case xxge:
203: return(4);
204: case '+':
205: case '-': return(5);
206: case '*':
207: case '/': return(6);
208: case xxuminus: return(7);
209: case '^': return(8);
210: default: return(9);
211: }
212: }
213: str_copy(s,ptr,length) /* copy s at ptr, return length of s */
214: char *s, *ptr;
215: int length;
216: {int i;
217: for (i = 0; i < length; i++)
218: {
219: ptr[i] = s[i];
220: if (ptr[i] == '\0')
221: return(i + 1);
222: }
223: fprintf(2,"string %s too long to be copied by str_copy at address %d\n",
224: *s,ptr);
225: exit(1);
226: }
227: str_eq(s,t)
228: char s[],t[];
229: {int j;
230: for (j = 0; s[j] == t[j]; j++)
231: {if (s[j] == '\0') return(1);}
232: return(0);
233: }
234:
235: slength(s) /* return number of chars in s, not counting '\0' */
236: char *s;
237: {
238: int i;
239: if (!s) return(-1);
240: for (i = 0; s[i] != '\0'; i++);
241: return(i);
242: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.