CODEWITHSUNDEEP
compiler-construction
sanjoy saha
sanjoy saha

Reputation: 83

Can I convert any grammar to an operator precedence grammar?

Any grammar can I implement by operator precedence parsing?

Upvotes: 0

Views: 1503

Answers (2)

Scott McCaughrin
Scott McCaughrin

Reputation: 11

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!

Upvotes: 1

Austin Henley
Austin Henley

Reputation: 4633

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

Upvotes: 2

Related Questions