Return to expr.ym CVS log

Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / Graph

Annotation of Examples/AppKit/Graph/expr.ym, revision 1.1

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.