I'm trying to write a context-free grammar (to be feeded to lark) for parsing lambda calculus expressions. Basic version of it, as presented by most sources, looks like:
expr: variable | "(" expr ")" | application | abstraction abstraction: "λ" variable "." expr application: expr expr
I'd like the grammar to unambiguously parse expressions taking advantage of the notational conventions mentioned here on Wikipedia. While I'm able to modify the grammar to follow most of them, I got stuck with implementing this one: "The body of an abstraction extends as far right as possible".
For example, there are two parse trees for
λx.x λa.a - it can be both an application of two abstractions (
(λx.x)(λa.a) ) or an abstraction with an application in its body (
If the abstraction was greedy as it should be, only the second one would be correct.
Is it possible to write a grammar that would force (i.e., make it the only choice) greedy interpretation of abstractions? If so, how to do it?