# What I want to do

I am trying to define a LL(1) grammar of the lambda-calculus.

# What I did

Here is the grammar:

1. $Term \to Abs$
2. $Term \to App$
3. $Abs \to \lambda \ id \ . \ Term$
4. $App \to Var \ AppSeq$
5. $AppSeq \to App$
6. $AppSeq \to \epsilon$
7. $Var \to id$
8. $Var \to (\ Term \ )$

Here are the FIRST sets:

• $FIRST(Term) = \{ \lambda, id, ( \}$
• $FIRST(Abs) = \{ \lambda \}$
• $FIRST(App) = \{ id, ( \}$
• $FIRST(AppSeq) = \{ id, (, \epsilon \}$
• $FIRST(Var) = \{ id, ( \}$

• $FOLLOW(Term) = \{ \$, ) \}$•$FOLLOW(Abs) = \{ \$, ) \}$
• $FOLLOW(App) = \{ \$, ) \}$•$FOLLOW(AppSeq) = \{ \$, ) \}$
• $FOLLOW(Var) = \{ \$, (, id \}$The dragon book give the following definition: A grammar G is LL(1) if and only if whenever A → α | β are two distinct productions of G, the following conditions hold: 1. FIRST(α) and FIRST(β) are disjoint sets 2. if ε is in FIRST(β), then FIRST(α) and FOLLOW(A) are disjoint sets 3. likewise if ε is in FIRST(α) # Question 1. Are my FIRST and FOLLOW sets correct? 2. If no, how can I make it LL(1)? • Why the so complicated initial grammar? Isn't$T \rightarrow id\; | \; (T\; T)\; | \; \lambda id.T$sufficient? – Wandering Logic Mar 28 '15 at 18:01 • I also started with something as simple, but it became complex when I tried to remove the need for parentheses for every application (i.e. encoding the rule of left-associativity). – authchir Mar 28 '15 at 18:12 • Closer after your edit, but I think$\mathrm{App} \rightarrow \mathrm{App}\; \mathrm{Var}\; |\; \mathrm{Var}\$. Yours is right associative rather than left. – Wandering Logic Mar 28 '15 at 21:20
• Is T the same as Term? – rici Mar 28 '15 at 21:45