home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compiler / 2278 < prev    next >
Encoding:
Text File  |  1993-01-28  |  1.7 KB  |  42 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!ukma!cs.widener.edu!eff!world!iecc!compilers-sender
  3. From: Michael Dyck <dyck@cs.sfu.ca>
  4. Subject: parser-generators for RRPGs
  5. Reply-To: Michael Dyck <dyck@cs.sfu.ca>
  6. Organization: Compilers Central
  7. Date: Thu, 28 Jan 1993 02:02:26 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <93-01-206@comp.compilers>
  10. Keywords: parse, tools, question, comment
  11. Sender: compilers-sender@iecc.cambridge.ma.us
  12. Lines: 28
  13.  
  14. Regular right-part grammars (RRPGs) are a kind of phrase structure grammar
  15. akin to context-free grammars (CFGs).  In each production of an RRPG, the
  16. LHS is a single non-terminal (as in a CFG), but the RHS is a regular
  17. expression (or finite automaton) over the symbol set (rather than simply a
  18. sequence of symbols, as in a CFG).
  19.  
  20. There are various notations for writing RRPGs (or slight restrictions
  21. thereof), many called "extended BNF".
  22.  
  23. For example (from Modula-2):
  24.  
  25. if-statement = "IF" condition "THEN" statements
  26.                { "ELSIF" condition "THEN" statements }
  27.                [ "ELSE" statements ]
  28.                "END"
  29.  
  30. It seems like most grammars presented for human consumption are RRPGs, but
  31. most grammars presented for machine consumption are CFGs.  What
  32. parser-generators are available that accept some form of RRPG?
  33.  
  34. -Michael Dyck, dyck@cs.sfu.ca
  35. [I've seen occasional references to something called eyacc, which appeared
  36. to be an EBNF version of yacc.  Is it not the case that RRPGs can be
  37. mechanically translated to CFGs, in which case a preprocessor for a normal
  38. parser generator might make sense? -John]
  39. -- 
  40. Send compilers articles to compilers@iecc.cambridge.ma.us or
  41. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  42.