home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2264 < prev    next >
Encoding:
Text File  |  1993-01-28  |  2.2 KB  |  47 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: dww@inf.fu-berlin.de
  4. Subject: Benefits of hand-coded bottom-up parsers
  5. Reply-To: dww@inf.fu-berlin.de
  6. Organization: Free University of Berlin
  7. Date: Tue, 26 Jan 1993 11:31:57 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <93-01-190@comp.compilers>
  10. Keywords: parse, courses, LR(1)
  11. Sender: compilers-sender@iecc.cambridge.ma.us
  12. Lines: 33
  13.  
  14. I don't really want to fan the flame wars, but I must stress the benefits
  15. of hand-coding an LR parser if your goal is to understand parsing.
  16.  
  17. My advisor insisted that I hand code an LR-parser for a language with 59
  18. productions, mostly trivial. We fought about this for almost a year: I
  19. felt it was a waste of time, too messy, etc.  After a blazing fight I sat
  20. down and did it. I generated the yacc tables first, so that I knew where I
  21. was going. It took about 5 iterations and much gnashing of teeth before I
  22. was able to produce the yacc table myself.
  23.  
  24. I was then required to draw the state machine on a piece of paper. I
  25. complained. My advisor said: "Take a *big* piece of paper and get
  26. started!" I bought a roll of packing paper and began. During the process
  27. of fitting the 118 states and the over 300 transitions onto a flat piece
  28. of paper, I began to *really* understand what actually is happening during
  29. parsing. I saw how the prefixes are recognized.  I "discovered" a number
  30. of theorems that of course have been proved for ages. I now have an
  31. excellent "Gedankenmodell", a thought model of the bottom-up parsing
  32. process, and find it easy to understand theoretical papers about
  33. LR-parsing.
  34.  
  35. I don't think it is necessary to do such a large language, but even to
  36. hand-construct LR-tables for the expression grammar will give you a
  37. lasting insight into the parsing process. Of course, a large language
  38. gives you a nice big poster to hang on the walls - mine is 600x100 cm !
  39. --
  40. Debora Weber-Wulff                       dww@inf.fu-berlin.de
  41. Institut fuer Informatik                 +49 30 89691 124
  42. Nestorstr. 8-9
  43. D-W-1000 Berlin 31
  44. -- 
  45. Send compilers articles to compilers@iecc.cambridge.ma.us or
  46. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  47.