<p>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:</p>
<pre><code>M ::= x | ( N )
N ::= λx.M | M M
</code></pre>
<p>Without the factorization, if you consider the simpler, obvious grammar:</p>
<pre><code>M ::= x | (λx.Μ) | (Μ Μ)
</code></pre>
<p>it's not LL(1), as the second and third alternative share a common prefix <code>(</code>, but it's LL(2). In any case, you can definitely construct a recursive descent parser for it.</p>
<hr />
<p><strong>Edit:</strong> 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:</p>
<pre><code>M ::= x | (λx.Μ) | (Μ Μ) | (M)
</code></pre>
<p>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 <code>(M</code>, which can be arbitrarily long.</p>
<p>However, after factorization, the following equivalent grammar is again LL(1):</p>
<pre><code>M ::= x | (N)
N ::= λx.Μ | Μ L
L ::= Μ | ε
</code></pre>

CC BY-SA 4.0
2023-03-28T17:07:56.483Z
But this way you won't be able to `(x)` for example or `((\x . x))`, right?
Zazaeil
CC BY-SA 4.0
2023-03-28T17:14:42.717Z
Seems that you are missing the `M := (M)` case, which indeed was not mentioned at the screenshot I've posted, yet assumed.
Zazaeil
CC BY-SA 4.0
2023-03-29T00:09:14.140Z
@Zazaeil, I edited the answer. Let me comment, however, that redundant parentheses are not part of *the* lambda calculus grammar.
nickie
CC BY-SA 4.0
2023-03-29T12:18:12.470Z
thanks, I didn't know that.
Zazaeil
CC BY-SA 4.0
2023-03-26T22:24:04.323Z
2023-03-29T00:07:17.567Z
2023-03-29T00:07:17.567Z
nickie
<p>I am playing with a lambda calculus and faced a question I find hard to reason about.</p>
<p>On the screenshot you may find <em>the</em> lambda calculus grammar. Is it an instance of the <code>LL(k)</code> grammar such that a recursive descent parser could handle it? How do you proof such a statement? What would be the best hint here?</p>
<p><a href="https://i.sstatic.net/oKGU1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oKGU1.png" alt="Lambda calculus." /></a></p>

<lambda-calculus><parsing>
Is classical lambda calculus grammar an `LL(k)` one?
Zazaeil
# Is classical lambda calculus grammar an `LL(k)` one?

(Asked by: username_0 on 2023-03-26)

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.](https://i.sstatic.net/oKGU1.png)](https://i.sstatic.net/oKGU1.png)

**Tags:** lambda-calculus, parsing

---

## 1 answers

### Answer by username_1 on 2023-03-26. Score: 5 | Accepted answer

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 ::= Μ | ε

> **Comments:**
> **username_0**: But this way you won't be able to `(x)` for example or `((\x . x))`, right?  
> **username_0**: Seems that you are missing the `M := (M)` case, which indeed was not mentioned at the screenshot I've posted, yet assumed.  
> **username_1**: @Zazaeil, I edited the answer. Let me comment, however, that redundant parentheses are not part of *the* lambda calculus grammar.  
> **username_0**: thanks, I didn't know that.  

---

