home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / c / 19354 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.9 KB
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: How can you evaluate an arbitrary function?
  5. Message-ID: <4302@dozo.and.nl>
  6. Date: 7 Jan 93 09:16:09 GMT
  7. References: <1993Jan6.202453.8630@news.tufts.edu>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 96
  10.  
  11. In article <1993Jan6.202453.8630@news.tufts.edu> slahiri@jade.tufts.edu (Sandip Lahiri) writes:
  12. |Suppose you have to write a program which would accept any arbitrary 
  13. |function f(x) and calculate its values for x = ... . The program has 
  14. |to be written in C. How would you go about it ? [ ... ]
  15.  
  16. Two approaches come to mind:
  17.  
  18. - Use yacc and lex (or equivalent tools) to generate the parser and 
  19.   lexical analyzer for you; 
  20.  
  21. - Write your own parser and lexical analyzer.
  22.  
  23. The grammar for this particular language (well formed expressions) is
  24. not too difficult to construct. Many textbooks give skeletons of such
  25. a grammar (e.g. the Dragon Book) If you want to build your own parser,
  26. may I suggest to construct a right recursive grammar first (or more
  27. specifically: an LL(1) grammar) because the derivation of the actual
  28. C code from it is very easy to do. A short example may clarify things
  29. a bit. The following three rules:
  30.  
  31. E    = T { [+-] E }
  32. T    = F { [*/] T }
  33. F    = x | c | f ( E ) | ( E ) | - F
  34.  
  35. make up a fairly complete syntax for arithmetic expressions. (f = any
  36. function name, x = the function parameter, c = any constant) These rules
  37. can directly be translated to C as follows:
  38.  
  39. double E() {
  40.  
  41.     double Result = T();
  42.  
  43.     for(;;)
  44.         switch (Token()) {
  45.             case '+': Result+= T(); break;
  46.             case '-': Result-= T(); break;
  47.             default : PushBackToken();
  48.                   return Result;
  49.         }
  50.     return Result;
  51. }
  52.  
  53.  
  54. double T() {
  55.  
  56.     double Result = F();
  57.  
  58.     for(;;)
  59.         switch (Token()) {
  60.             case '*': Result+= F(); break;
  61.             case '/': Result-= F(); break;
  62.             default : PushBackToken();
  63.                   return Result;
  64.         }
  65.     return Result;
  66. }
  67.  
  68. double F() {
  69.  
  70.     double Result;
  71.  
  72.     switch (Token()) {
  73.         case 'x': return GetParValue();
  74.         case 'c': return GetConstValue();
  75.         case '-': return -F();
  76.         case '(': Result= E();
  77.               if (token() != ')') {
  78.                 perror("')' expected");
  79.                 abort();
  80.               }
  81.         case 'f': if (token() != ')') {
  82.                 perror("'(' expected");
  83.                 abort();
  84.               }
  85.               Result= E();
  86.               if (token() != ')') {
  87.                 perror("')' expected");
  88.                 abort();
  89.               }
  90.               return ApplyFunc(Result);
  91.         default : perror("Syntax error");
  92.               abort();
  93.     }
  94. }
  95.  
  96. Well, I hope you get the picture ... Recursive descent parsing is not
  97. the difficult part. Building a lexical analyzer can be a tedious job:
  98. it not only has to recognize floating point constants and function
  99. names (and parentheses, operators etc.) but it also has to transform
  100. the string representation of those constants into an internal repre-
  101. sentation (double type) It's much more convenient to use lex (or a
  102. similar tool) for that. 
  103.  
  104. I hope this helps a bit. Kind regards,
  105.  
  106. Jos aka jos@and.nl
  107.