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:
- $Term \to Abs$
- $Term \to App$
- $Abs \to \lambda \ id \ . \ Term$
- $App \to Var \ AppSeq$
- $AppSeq \to App$
- $AppSeq \to \epsilon$
- $Var \to id$
- $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:
- FIRST(α) and FIRST(β) are disjoint sets
- if ε is in FIRST(β), then FIRST(α) and FOLLOW(A) are disjoint sets
- likewise if ε is in FIRST(α)
Question
- Are my FIRST and FOLLOW sets correct?
- If no, how can I make it LL(1)?
T
the same asTerm
? $\endgroup$ – rici Mar 28 '15 at 21:45