home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / programm / 3152 next >
Encoding:
Internet Message Format  |  1992-11-15  |  2.8 KB
  1. Path: sparky!uunet!gatech!destroyer!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: dave@cs.arizona.edu (Dave Schaumann)
  3. Newsgroups: comp.programming
  4. Subject: Re: Parsing mathematical functions.
  5. Message-ID: <1992Nov15.174725.13958@organpipe.uug.arizona.edu>
  6. Date: 15 Nov 92 17:47:25 GMT
  7. References: <1e25e1INN8sr@matt.ksu.ksu.edu>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  10. Organization: University of Arizona
  11. Lines: 55
  12. In-Reply-To: strat@matt.ksu.ksu.edu (Steve Davis)
  13.  
  14. In article <1e25e1INN8sr@matt.ksu.ksu.edu>, strat@matt (Steve Davis) writes:
  15. >I've been thinking about a problem for a high-school level computer
  16. >programming contest.  The problem I was considering was one that would
  17. >input a function and two numbers, and output an approximation of the
  18. >function integral.  Of course the hard part for the computer isn't
  19. >getting the integral, it's parsing the mathematical function!
  20. >
  21. >Since this would be a high-school level contest, with solution
  22. >elegance being the next highest priority to having a working solution,
  23. >I would want to define the parsing problem in a simple and language
  24. >inspecific way.
  25.  
  26. IMHO, the first thing you should do is give up on standard expression format,
  27. unless knowledge of parsing techniques (like recursive descent) is common
  28. among your students.
  29.  
  30. A reasonable alternative you might consider is the so-called "reverse Polish
  31. notation", where all operators are in the postfix position:
  32.  
  33.   sqrt(x*x+y*y) becomes x x * y y * sqrt
  34.  
  35. The advantages of this notation is that it can be parsed (and thus,
  36. interpreted) in a simple left-to-right scan.  You'd probably still have
  37. to explain how to use a stack to evaluate the expression, though.
  38.  
  39. If you want to stick with standard expression format, it seems to me that
  40. you'd pretty much have to have a mini-compiler-writing course, to explain
  41. how operator precedence and evaluation order is captured by a grammar
  42. (which means parse trees, derivations, and probably at least an aside
  43. on ambiguity...)
  44.  
  45. >Where can I find discussion (on the Internet if
  46. >possible!) of this specific parsing problem.
  47.  
  48. Well, one of the canonical texts on parsing is
  49.  
  50.     _Compilers: Principles, Techniques and Tools_, by Aho, Sethi
  51.         and Ullman (ISBN 0-201-10088-1)
  52.  
  53. Perhaps more to the point of your query is
  54.  
  55.     _The UNIX Programming Environment_, by Kernighan and Pike
  56.         (ISBN 0-13-937681-X)
  57.  
  58. Chapter 8 of this book concerns itself with program development, and
  59. the program they develop starts as a 4-function calculator and is
  60. developed into an interpreter for a C-like language.
  61.  
  62. On the whole, I'd say your best course of action is to choose another
  63. problem for your contest, since judging by my experience, the knowledge
  64. required for the given program is way beyond anything the average
  65. high-schooler knows.
  66.  
  67. -- 
  68. Caught an internal error--.brainrc restored
  69.