A part of my senior project is to create a framework to allow users to use their own grammar in Pyret. A good framework would need to prohibit ambiguous grammar that users might write.

One way to do this would be to require users to write a grammar that is accepted by LALR parser generator, since LALR parser generator will result in a conflict when the grammar is ambiguous. Note that the converse is not true: there could be conflict while the grammar is not ambiguous. This is exactly the situation that we are in because Pyret is currently using GLR parser generator which accept all context-free grammars. And Pyret does have some grammar that require unbounded and non-local lookahead, so LALR is not directly applicable.

There are two solutions that I am considering:

• Rewrite Pyret grammar so that it can be accepted by LALR parser generator. This doesn’t seem applicable since Pyret is widely use by a lot of people
• Use PEG

PEG at first glance seems really nice: linear time parsing, unambiguous by construction, and pretty expressive. However, I found that it could be very deceptive as well.

Y combinator seems to be something mysterious. Several people have been trying to understand the intuition why it works. I have seen "A Lecture on the Why of Y" by Matthias Felleisen before, and while it does give me some insight, I still feel confused in some degree. That doesn’t prevent me from recommending this lecture to other people I talked to because it’s the best one I have seen so far.

Recently I thought about the fixed point combinator again and finally gained some good insight. I think it’s worth sharing here.