Can I convert any grammar to an operator precedence grammar?

Any gramma开发者_如何学Pythonr can I implement by operator precedence parsing?

---

If you are asking if you can change the operator precedence of a language through the grammar, then the answer is: yes, of course.

If you are asking if you can parse a "typical" context-free grammar using Pratt's method of top down operator parsing, then the answer is no. BUT you can mix the two. A good article covering Pratt parsing that should give you some info on applying this to a recursive descent parser: http://effbot.org/zone/simple-top-down-parsing.htm

---

This is an excellent question, for which the answer is: yes. It appears as a doubly-starred problem (#4.21) in Chapter Four of the Hopcroft & Ullman text on Computability and Formal Languages. The answer (a summarized proof by construction) is also provided. Very briefly, it assumes pre-conversion to Reduced GNF, from which the final construction is performed to remove adjacent non-terminals. Not the most efficient construction, but it works (if you can follow the similar treatment for conversion to CNF and GNF earlier). Hope this helps!