Where should the type information be 153

+--------------- ... Unlike LALR parsing, operator precedence parsing can be implemented by hand, and is more efficient than LL parsing in handling expressions. There are a few languages that can be implemented exclusively using operator precedence. I believe that many versions of Prolog naturally map to operator precedence parsing. The other forms of grammars may be distinguished from operator precedence depending on whether they are a subset, superset, or-overlapping set of the operator precedence techniques.I suspect there is not a usable form of non-overlapping grammar with operator precedence. +---------------

I'm not quite sure what you mean by "overlapping" here, but there is a very useful hybrid parsing technique which I first encountered in the early 1970's in the BLISS-10 compiler also see Wulf, et al, "The Design of an Optimizing Compiler", on BLISS-11, and have used with great success myself in several small projects: Combine a recursive descent parser for control structures (and other "large" features) with a simple-operator-precedence1 parser for arithmetic expressions. The way you hook these together is to make the LL(1) "keywords" be "operators" with a *very* high precedence (higher than any normal arithmetic operator), so that when you encounter one of them you always try to reduce it first. Since the recursive descent routines call the simple-operator-precedence parser to parse any subexpressions, the two styles weave back & forth nicely between themselves.

-Rob

1 As I recall it (sorry, I don't have the applicable texts here at the moment), the difference between general "operator precedence" grammars and "simple operator precedence" grammars is that the latter never permit two non-operators without an intervening operator. Multiple operators in a row is o.k. This simplifies the parser a *lot*, and means that a simple 4-lexeme sliding window The BLISS compilers called these SYM, DEL, FUTSYM, & FUTDEL, and the procedure to slide the window was called RUND, for "Read Until Next Delimiter".

----- San Mateo, CA 94403 (650)572-2607