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
    Commented Mar 28, 2023 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
    Commented Mar 28, 2023 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
    Commented Mar 29, 2023 at 0:09
  • $\begingroup$ thanks, I didn't know that. $\endgroup$
    – Zazaeil
    Commented Mar 29, 2023 at 12:18

Your Answer

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

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