home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Examples / AppKit / Graph / expr.ym < prev    next >
Encoding:
Text File  |  1992-04-20  |  7.9 KB  |  264 lines
  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) {}
  264.