I am playing with a lambda calculus and faced a question I find hard to reason about.

On the screenshot you may find the lambda calculus grammar. Is it an instance of the LL(k) grammar such that a recursive descent parser could handle it? How do you proof such a statement? What would be the best hint here?

Lambda calculus.


1 Answer 1


After some trivial factorization, I think it should be easy to prove it's LL(1) by constructing the LL(1) table for it. The grammar would be:

M ::= x | ( N )
N ::= λx.M | M M

Without the factorization, if you consider the simpler, obvious grammar:

M ::= x | (λx.Μ) | (Μ Μ)

it's not LL(1), as the second and third alternative share a common prefix (, but it's LL(2). In any case, you can definitely construct a recursive descent parser for it.

Edit: Adding a (non-standard, I must say) rule for redundant parentheses around terms complicates things. The following grammar is not LL(k) for any value of k:

M ::= x | (λx.Μ) | (Μ Μ) | (M)

The reason is that, in order to decide between the third and the fourth alternative, a predictive parser would have to read the common prefix (M, which can be arbitrarily long.

However, after factorization, the following equivalent grammar is again LL(1):

M ::= x | (N)
N ::= λx.Μ | Μ L
L ::= Μ | ε
  • $\begingroup$ But this way you won't be able to (x) for example or ((\x . x)), right? $\endgroup$
    – Zazaeil
    Mar 28 at 17:07
  • $\begingroup$ Seems that you are missing the M := (M) case, which indeed was not mentioned at the screenshot I've posted, yet assumed. $\endgroup$
    – Zazaeil
    Mar 28 at 17:14
  • 2
    $\begingroup$ @Zazaeil, I edited the answer. Let me comment, however, that redundant parentheses are not part of the lambda calculus grammar. $\endgroup$
    – nickie
    Mar 29 at 0:09
  • $\begingroup$ thanks, I didn't know that. $\endgroup$
    – Zazaeil
    Mar 29 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.