![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to expr.ym CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / Graph|
Return to expr.ym CVS log | Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / Graph |
1.1 root 1:
2: %{
3: /*
4: expr.ym
5:
6: This file defines the grammar for parsing expressions. To fully understand
7: this code you will need to understand yacc. The basic idea is that
8: the parse tree is built from the bottom up as larger and larger
9: sub-expressions are recognized by the grammar. The nodes of the tree
10: are created by the alloc* functions at the end of the file. These
11: functions are called by the rules of the grammar as various types of
12: sub-expressions are recognized. The one entry point to this file,
13: _EXPParseExpression() encapsulates all the lex and yacc glue necessary
14: to parse an expression.
15: */
16:
17: #import <stdlib.h>
18: #import <string.h>
19: #import <stdio.h>
20: #import "exprDefs.h"
21:
22: static Term *allocBinaryOpTerm(char op, Term *t1, Term *t2);
23: static Term *allocVarTerm(char *name);
24: static Term *allocConstantTerm(float value, BOOL isInt);
25: static Term *allocFuncTerm(char *name, TermList *args);
26: static void addAllocedTerm(Term *t);
27: static void yyerror(char *s);
28: extern yylex(), yyparse();
29:
30: /* globals used to build up results of the parse */
31: static NXHashTable *ValidFuncTerms; /* list of funcs we allow */
32: static NXHashTable *VarTerms; /* vars found in expression */
33: static Term *CompleteExpr; /* top of parse tree */
34: static BOOL ParseError; /* was there a parse error? */
35: static Term **TermsAlloced; /* terms alloced during parse */
36: static int NumTermsAlloced; /* #terms alloced during parse */
37: static NXZone *ParseZone; /* zone to allocate parse results in */
38:
39: /* initial size of TermsAlloced ptr array */
40: #define STACK_TERMS 200
41:
42: %}
43:
44: %token IDENTIFIER NUMBER INTEGER
45:
46: %union {
47: Term *node;
48: TermList *list;
49: float real;
50: int integer;
51: char *string;
52: char character;
53: }
54:
55: %token <real> NUMBER
56: %token <integer> INTEGER
57: %token <string> IDENTIFIER
58: %token <character> BADCHAR
59: %type <node> complete_expr expr function
60: %type <list> arglist
61:
62: %start complete_expr
63:
64: %left '+' '-'
65: %left '*' '/' '%'
66: %left UMINUS
67: %right '^'
68:
69: %%
70:
71: complete_expr: expr
72: { CompleteExpr = $$; }
73: ;
74:
75: expr : '(' expr ')'
76: { $$ = $2; }
77: | expr '+' expr
78: { $$ = allocBinaryOpTerm('+', $1, $3); }
79: | expr '-' expr
80: { $$ = allocBinaryOpTerm('-', $1, $3); }
81: | expr '*' expr
82: { $$ = allocBinaryOpTerm('*', $1, $3); }
83: | expr '/' expr
84: { $$ = allocBinaryOpTerm('/', $1, $3); }
85: | expr '%' expr
86: { $$ = allocBinaryOpTerm('%', $1, $3); }
87: | expr '^' expr
88: { $$ = allocBinaryOpTerm('^', $1, $3); }
89: | '-' expr %prec UMINUS
90: { $$ = _EXPAllocTerm(ParseZone, binOpTerm, 1, $2);
91: $$->data.binOp.op = '-';
92: }
93: | function
94: | IDENTIFIER
95: { $$ = allocVarTerm($1); }
96: | NUMBER
97: { $$ = allocConstantTerm($1, NO); }
98: | INTEGER
99: { $$ = allocConstantTerm($1, YES); }
100: ;
101:
102: function : IDENTIFIER '(' ')'
103: { $$ = allocFuncTerm($1, NULL); }
104: | IDENTIFIER '(' arglist ')'
105: { $$ = allocFuncTerm($1, $3); }
106: ;
107:
108: arglist : expr
109: { $$ = NXZoneMalloc(NXDefaultMallocZone(), sizeof(TermList));
110: $$->terms[0] = $1;
111: $$->num = 1;
112: }
113: | arglist ',' expr
114: { $$ = NXZoneRealloc(NXDefaultMallocZone(), $1,
115: sizeof(TermList) + $1->num*sizeof(Term *));
116: $$->terms[$$->num] = $3;
117: $$->num++;
118: }
119: ;
120:
121: %%
122:
123: /*
124: * The main entry point into this file. This routine sets up some globals
125: * and calls yyparse(), a routine generated by yacc, to do the actual parse.
126: * If the parse succeeds, the results are found in the globals, and are
127: * returned to the caller.
128: *
129: * Note because of the globals this files uses to communicate between this
130: * routine and the parsing guts, this is not thread safe (the yacc and lex
131: * internals probably aren't thread safe either). One easy solution to this
132: * would be to put a mutex lock around the whole parse.
133: *
134: * If there is a parse error, since the tree is built bottom up it can be
135: * difficult to free the data structures allocated before the error is
136: * detected. To solve this problem we keep a global buffer of pointers to
137: * the parse tree nodes as they are allocated. In the event of an error
138: * we can then easily free them all regardless of the state of the parse tree.
139: * Its also very important to empty the varTerms hash table in this case, so
140: * it is not returned full of freed nodes.
141: */
142: BOOL _EXPParseExpression(const char *text, NXHashTable *validTerms, Term **parseTree, NXHashTable *varTerms, NXZone *zone) {
143: int parseRet;
144: Term *termsAllocedStackSpace[STACK_TERMS];
145: int i;
146:
147: CompleteExpr = NULL; /* set globals to prepare for parsing */
148: VarTerms = varTerms;
149: ParseError = NO;
150: ValidFuncTerms = validTerms;
151: TermsAlloced = termsAllocedStackSpace;
152: NumTermsAlloced = 0;
153: ParseZone = zone;
154: _EXPPrepareToScan(text); /* sets up lex to scan the string */
155: parseRet = yyparse();
156: if (parseRet == 1 || ParseError) {
157: for (i = 0; i < NumTermsAlloced; i++)
158: _EXPFreeTerm(NULL, TermsAlloced[i]);
159: *parseTree = NULL;
160: NXEmptyHashTable(varTerms);
161: } else
162: *parseTree = CompleteExpr;
163: if (NumTermsAlloced > STACK_TERMS)
164: NXZoneFree(NXDefaultMallocZone(), TermsAlloced);
165: return !(parseRet == 1 || ParseError);
166: }
167:
168: /* allocates a new binary operator term */
169: static Term *allocBinaryOpTerm(char op, Term *t1, Term *t2) {
170: Term *newTerm;
171:
172: newTerm = _EXPAllocTerm(ParseZone, binOpTerm, 2, t1, t2);
173: newTerm->data.binOp.op = op;
174: addAllocedTerm(newTerm);
175: return newTerm;
176: }
177:
178: /*
179: * Allocates a new variable term. We first check to see if the variable has
180: * already been seen in this parse, and if so return the existing variable
181: * term. Otherwise we go ahead and allocate a new one.
182: */
183: static Term *allocVarTerm(char *name) {
184: Term *newTerm;
185: Term key;
186:
187: key.tag = varTerm;
188: key.data.var.name = name;
189: newTerm = NXHashGet(VarTerms, &key);
190: if (!newTerm) {
191: newTerm = _EXPAllocTerm(ParseZone, varTerm, 0);
192: newTerm->data.var.name = NXCopyStringBufferFromZone(name, ParseZone);
193: NXHashInsert(VarTerms, newTerm);
194: addAllocedTerm(newTerm);
195: }
196: free(name);
197: return newTerm;
198: }
199:
200: /* allocates a new constant term */
201: static Term *allocConstantTerm(float value, BOOL isInt) {
202: Term *newTerm;
203:
204: newTerm = _EXPAllocTerm(ParseZone, constantTerm, 0);
205: newTerm->data.constant.val = value;
206: newTerm->data.constant.isInt = isInt;
207: addAllocedTerm(newTerm);
208: return newTerm;
209: }
210:
211: /*
212: * Allocates a new function term. It looks up the function by name to see
213: * if it is one we know how to parse. If so, it makes sure the number of
214: * arguments being passed is correct for the function. If the function is
215: * unknown or the number of arguments is wrong, we record the fact that
216: * we've had a parse error in a global.
217: */
218: static Term *allocFuncTerm(char *name, TermList *args) {
219: Term *newTerm;
220: Function *func;
221: Function key;
222: TermList noArgs;
223:
224: if (!args) {
225: args = &noArgs;
226: args->num = 0;
227: }
228: key.name = (char *)name;
229: func = NXHashGet(ValidFuncTerms, &key);
230: newTerm = _EXPAllocTerm(ParseZone, funcTerm, args->num);
231: bcopy(args->terms, newTerm->subterms, args->num * sizeof(Term *));
232: newTerm->data.func.type = func;
233: if (!func || args->num < func->minArgs ||
234: (args->num > func->maxArgs && func->maxArgs != -1))
235: ParseError = YES;
236: NXZoneFree(NXDefaultMallocZone(), args);
237: free(name);
238: addAllocedTerm(newTerm);
239: return newTerm;
240: }
241:
242: /*
243: * Adds a term to the list of terms that we have allocated during this parse.
244: * This routine allocates more space for Term pointers if necessary. It knows
245: * not to free the initial buffer of these pointers, since that buffer is
246: * allocated on the stack by _EXPParseExpression().
247: */
248: static void addAllocedTerm(Term *t) {
249: Term **newSpace;
250:
251: if (!(NumTermsAlloced % STACK_TERMS) && NumTermsAlloced > 0) {
252: newSpace = NXZoneMalloc(NXDefaultMallocZone(),
253: (NumTermsAlloced + STACK_TERMS) * sizeof(Term *));
254: bcopy(TermsAlloced, newSpace, NumTermsAlloced * sizeof(Term *));
255: if (NumTermsAlloced > STACK_TERMS)
256: NXZoneFree(NXDefaultMallocZone(), TermsAlloced);
257: TermsAlloced = newSpace;
258: }
259: TermsAlloced[NumTermsAlloced++] = t;
260: }
261:
262: /* a piece of yacc glue called when there is a parse error */
263: static void yyerror(char *s) {}
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.