1
$\begingroup$

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, ( \}$

Here are FOLLOW sets:

  • $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)?
Improve this question
$\endgroup$
  • $\begingroup$ Why the so complicated initial grammar? Isn't $T \rightarrow id\; | \; (T\; T)\; | \; \lambda id.T$ sufficient? $\endgroup$ – Wandering Logic Mar 28 '15 at 18:01
  • $\begingroup$ 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). $\endgroup$ – authchir Mar 28 '15 at 18:12
  • $\begingroup$ Closer after your edit, but I think $\mathrm{App} \rightarrow \mathrm{App}\; \mathrm{Var}\; |\; \mathrm{Var}$. Yours is right associative rather than left. $\endgroup$ – Wandering Logic Mar 28 '15 at 21:20
  • $\begingroup$ @WanderingLogic: It has to be right associative for an LL grammar. (One reason not to use LL grammars, perhaps) $\endgroup$ – rici Mar 28 '15 at 21:41
  • $\begingroup$ Is T the same as Term? $\endgroup$ – rici Mar 28 '15 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.